Схема Горнера

Схе́ма Го́рнера (или правило Горнера, метод Горнера) — алгоритм вычисления значения многочлена, записанного в виде суммы мономов (одночленов), при заданном значении переменной. Метод Горнера позволяет найти корни многочлена^{[источник не указан 667 дней]}, а также вычислить производные полинома в заданной точке. Схема Горнера также является простым алгоритмом для деления многочлена на бином вида . Метод назван в честь Уильяма Джорджа Горнера (англ.).

Содержание

1 Описание алгоритма
2 Использование схемы Горнера для деления многочлена на бином
3 См. также
4 Литература
5 Ссылки

Описание алгоритма

Задан многочлен :

Пусть требуется вычислить значение данного многочлена при фиксированном значении . Представим многочлен в следующем виде:

Определим следующую последовательность:

…

Искомое значение . Покажем, что это так.

В полученную форму записи подставим и будем вычислять значение выражения, начиная со внутренних скобок. Для этого будем заменять подвыражения через :

$\begin{align} P(x_0) & = a_0 + x_0(a_1 + x_0(a_2 + \cdots x_0(a_{n-1} + a_n x_0)\dots)) \\ & = a_0 + x_0(a_1 + x_0(a_2 + \cdots x_0(b_{n-1})\dots)) \\ & {} \ \ \vdots \\ & = a_0 + x_0(b_1) \\ & = b_0 \end{align}$

Использование схемы Горнера для деления многочлена на бином

При делении многочлена на получается многочлен с остатком .

При этом коэффициенты результирующего многочлена удовлетворяют рекуррентным соотношениям:

, .

Таким же образом можно определить кратность корня (использовать схему Горнера для нового полинома). Так же схему можно использовать для нахождения коэффициентов при разложении полинома по степеням:

См. также

Литература

Ананий В. Левитин Глава 6. Метод преобразования: Схема Горнера и возведение в степень // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms. — М.: «Вильямс», 2006. — С. 284-291. — ISBN 0-201-74395-7
Волков Е. А. § 2. Вычисление значений многочлена. Схема Горнера // Численные методы. — Учеб. пособие для вузов. — 2-е изд., испр. — М.: Наука, 1987. — 248 с.
С. Б. Гашков §14. Схема Горнера и перевод из одной позиционной системы в другую // Системы счисления и их применение. — М.: МЦНМО, 2004. — С. 37-39. — (Библиотека «Математическое просвещение»). — ISBN 5-94057-146-8

Ссылки

Схема Горнера
Вычисление многомерных полиномов - обобщение схемы Горнера на случай полинома от нескольких переменных.

Light-industry-up.ru

Экосистема промышленности

Публикации