Схема Горнера — Википедия
Схе́ма Го́рнера (или правило Горнера, метод Горнера, метод Руффини-Горнера) — алгоритм вычисления значения многочлена, записанного в виде суммы мономов (одночленов), при заданном значении переменной. Метод Горнера позволяет найти корни многочлена[1], а также вычислить производные полинома в заданной точке. Схема Горнера также является простым алгоритмом для деления многочлена на бином вида . Метод назван в честь Уильяма Джорджа Горнера, однако Паоло Руффини опередил Горнера на 15 лет, а китайцам этот способ был известен еще в XIII веке.
Описание алгоритма
[править | править код]Задан многочлен
Пусть требуется вычислить значение данного многочлена при фиксированном значении . Представим многочлен в следующем виде:
Определим следующую последовательность:
- …
- …
Искомое значение есть . Покажем, что это так.
В полученную форму записи подставим и будем вычислять значение выражения, начиная с внутренних скобок. Для этого будем заменять подвыражения через :
Использование схемы Горнера для деления многочлена на бином
[править | править код]При делении многочлена на получается многочлен с остатком (см. теорема Безу).
При этом коэффициенты результирующего многочлена удовлетворяют рекуррентным соотношениям
Таким же образом можно определить кратность корней (использовать схему Горнера для нового полинома). Также схему можно использовать для нахождения коэффициентов при разложении полинома по степеням :
Схема Горнера может использоваться для нахождения производных многочлена:
Примеры использования
[править | править код]Рассчитать для Используем синтетическое деление:
x₀│ x³ x² x¹ x⁰ 3 │ 2 −6 2 −1 │ 6 0 6 └──────────────────────── 2 0 2 5
Здесь в первой строке записаны значение и коэффициенты многочлена.
Значения (по столбцам) в третьей строке соответствуют сумме значений первой и второй строки (), а значения второй строки произведению x на значение в третьей строке предыдущего столбца ().
Например, если мы видим, что — значения в третьей строке. Так синтетическое деление базируется на методе Горнера.
Разделим на :
2 │ 1 −6 11 −6 │ 2 −8 6 └──────────────────────── 1 −4 3 0
Новый многочлен .
Пусть и . Разделим на , используя метод Горнера.
2 │ 4 −6 0 3 │ −5 ────┼──────────────────────┼─────── 1 │ 2 −2 −1 │ 1 └──────────────────────┼─────── 2 −2 −1 1 │ −4
Третья строка — сумма первых двух, деленная на два. Каждое значение второй строки совпадает с значением третьей строки в предыдущем столбце. Ответ на деление:
Также с помощью схемы Горнера можно вычислять значение числа в позиционной системе исчисления.
Примечания
[править | править код]- ↑ Если целочисленный многочлен обладает целыми корнями, то они будут найдены среди делителей свободного члена. Курош А. Г. § 57. Рациональные корни целочисленных многочленов // Курс высшей алгебры. — Наука. — Москва, 1968. Архивировано 18 октября 2013 года.
См. также
[править | править код]Литература
[править | править код]- Левитин А. В. Глава 6. Метод преобразования: Схема Горнера и возведение в степень // Алгоритмы. Введение в разработку и анализ — М.: Вильямс, 2006. — С. 284—291. — 576 с. — ISBN 978-5-8459-0987-9
- Волков Е. А. § 2. Вычисление значений многочлена. Схема Горнера // Численные методы. — Учеб. пособие для вузов. — 2-е изд., испр. — М.: Наука, 1987. — 248 с.
- С. Б. Гашков. § 14. Схема Горнера и перевод из одной позиционной системы в другую // Системы счисления и их применение. — М.: МЦНМО, 2004. — С. 37—39. — (Библиотека «Математическое просвещение»). — ISBN 5-94057-146-8.
Ссылки
[править | править код]- Схема Горнера
- Вычисление многомерных полиномов — обобщение схемы Горнера на случай полинома от нескольких переменных.
- Метод Горнера в комплексном поле