Метод Горнера

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

В полученную форму записи P(x) подставим x = x₀ и будем вычислять значение выражения, начиная со внутренних скобок. Для этого будем заменять подвыражения через 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(a_{n-1} + b_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₀ = a₀, b_k = a_k + cb_{k − 1}.

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

См. также

• Деление многочленов столбиком (англ.)
• Деление столбиком

Литература

• Ананий В. Левитин Глава 6. Метод преобразования: Схема Горнера и возведение в степень // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms. — М.: «Вильямс», 2006. — С. 284-291. — ISBN 0-201-74395-7

Ссылки

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