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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Схе́ма Го́рнера (или правило Горнера, метод Горнера) — алгоритм вычисления значения многочлена, записанного в виде суммы мономов (одночленов), при заданном значении переменной. Метод Горнера позволяет найти корни многочлена[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

Ссылки[править | править исходный текст]