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

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

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

Задан многочлен $P(x)$:

$P(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \ldots + a_n x^n, \quad a_i \in \mathbb{R}$.

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

$P(x) = a_0 + x(a_1 + x(a_2 + \cdots x(a_{n-1} + a_n x) \dots))$.

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

$b_n = a_n\,\!$

$b_{n-1} = a_{n-1} + b_n x\,\!$

…

$b_i = a_i + b_{i+1} x\,\!$

…

$b_0 = a_0 + b_1 x\,\!$

Искомое значение $P(x_0) = b_0$. Покажем, что это так.

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

$\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}$

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

При делении многочлена $a_0 x^n + a_1 x^{n-1} + \cdots + a_{n-1} x + a_n$ на $~x - c$ получается многочлен $b_0 x^{n-1} + b_1 x^{n-2} + \cdots + b_{n-2} x + b_{n-1}$ с остатком $~b_n$.

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

$~b_0 = a_0$, $~b_k = a_k + c b_{k-1}$.

Таким же образом можно определить кратность корней (использовать схему Горнера для нового полинома). Так же схему можно использовать для нахождения коэффициентов при разложении полинома по степеням$~ x - c$: $P(x) = A_0 + A_1 (x-c) + A_2 (x-c)^2 + \cdots + A_{n} (x-c)^{n}$

Примечания

1. ↑ Если целочисленный многочлен обладает целыми корнями, то они будут найдены среди делителей свободного члена. Курош А.Г §57 Рациональные корни целочисленных многочленов // Курс высшей алгебры. — Наука. — Москва, 1968.

См. также

• Деление многочленов столбиком
• Деление столбиком

Литература

• Ананий В. Левитин Глава 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

Ссылки

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