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

Схе́ма Го́рнера (или правило Горнера, метод Горнера, метод Руффини-Горнера) — алгоритм вычисления значения многочлена, записанного в виде суммы мономов (одночленов), при заданном значении переменной. Метод Горнера позволяет найти корни многочлена, а также вычислить производные полинома в заданной точке. Схема Горнера также является простым алгоритмом для деления многочлена на бином вида [math]\displaystyle{ x - c }[/math]. Метод назван в честь Уильяма Джорджа Горнера, однако Паоло Руффини опередил Горнера на 15 лет, а китайцам этот способ был известен еще в XIII веке.

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

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

[math]\displaystyle{ 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}. }[/math]

Пусть требуется вычислить значение данного многочлена при фиксированном значении [math]\displaystyle{ x = x_0 }[/math]. Представим многочлен [math]\displaystyle{ P(x) }[/math] в следующем виде:

[math]\displaystyle{ P(x) = a_0 + x(a_1 + x(a_2 + \cdots x(a_{n-1} + a_n x) \dots)). }[/math]

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

[math]\displaystyle{ b_n = a_n, }[/math]

[math]\displaystyle{ b_{n-1} = a_{n-1} + b_n x_0, }[/math]

…

[math]\displaystyle{ b_i = a_i + b_{i+1} x_0, }[/math]

…

[math]\displaystyle{ b_0 = a_0 + b_1 x_0. }[/math]

Искомое значение [math]\displaystyle{ P(x_0) }[/math] есть [math]\displaystyle{ b_0 }[/math]. Покажем, что это так.

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

[math]\displaystyle{ \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} }[/math]

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

При делении многочлена [math]\displaystyle{ a_0 x^n + a_1 x^{n-1} + \cdots + a_{n-1} x + a_n }[/math] на [math]\displaystyle{ x - c }[/math] получается многочлен [math]\displaystyle{ b_0 x^{n-1} + b_1 x^{n-2} + \cdots + b_{n-2} x + b_{n-1} }[/math] с остатком [math]\displaystyle{ b_n }[/math] (см. теорема Безу).

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

[math]\displaystyle{ b_0 = a_0, \quad b_k = a_k + c b_{k-1}. }[/math]

Таким же образом можно определить кратность корней (использовать схему Горнера для нового полинома). Также схему можно использовать для нахождения коэффициентов при разложении полинома по степеням [math]\displaystyle{ (x - c) }[/math]:

[math]\displaystyle{ P(x) = b_n + b_{n-1} (x - c) + b_{n-2} (x - c)^2 + \cdots + b_0 (x - c)^n. }[/math]

Схема Горнера может использоваться для нахождения производных многочлена:

[math]\displaystyle{ P^{(k)}(c) = k!b_{n-k}. }[/math]

Примеры использования

Рассчитать [math]\displaystyle{ f(x)=2x^3-6x^2+2x-1 }[/math] для [math]\displaystyle{ x=3. }[/math] Используем синтетическое деление:

 x₀│   x³    x²    x¹    x⁰
 3 │   2    −6     2    −1
   │         6     0     6
   └────────────────────────
       2     0     2     5

Здесь в первой строке записаны значение [math]\displaystyle{ x_0 }[/math] и коэффициенты многочлена.

Значения (по столбцам) в третьей строке соответствуют сумме значений первой и второй строки ([math]\displaystyle{ b_{n-1} = a_{n-1} + b_n x_0 }[/math]), а значения второй строки произведению x на значение в третьей строке предыдущего столбца ([math]\displaystyle{ b_n x_0 }[/math]).

Например, если [math]\displaystyle{ a_3 = 2, a_2 = -6, a_1 = 2, a_0 = -1 }[/math] мы видим, что [math]\displaystyle{ b_3 = 2, b_2 = 0, b_1 = 2, b_0 = 5 }[/math] — значения в третьей строке. Так синтетическое деление базируется на методе Горнера.

Разделим [math]\displaystyle{ x^3-6x^2+11x-6 }[/math] на [math]\displaystyle{ x-2 }[/math]:

 2 │   1    −6    11    −6
   │         2    −8     6
   └────────────────────────
       1    −4     3     0

Новый многочлен [math]\displaystyle{ x^2-4x+3 }[/math].

Пусть [math]\displaystyle{ f_1(x)=4x^4-6x^3+3x-5 }[/math] и [math]\displaystyle{ f_2(x)=2x-1 }[/math]. Разделим [math]\displaystyle{ f_1(x) }[/math] на [math]\displaystyle{ f_2\,(x) }[/math], используя метод Горнера.

  2 │  4    −6    0    3   │   −5
────┼──────────────────────┼───────
  1 │        2   −2   −1   │    1
    └──────────────────────┼───────
       2    −2   −1    1   │   −4

Tретья строка — сумма первых двух, деленная на два. Каждое значение второй строки совпадает с значением третьей строки в предыдущем столбце. Ответ на деление:

[math]\displaystyle{ \frac{f_1(x)}{f_2(x)}=2x^3-2x^2-x+1-\frac{4}{2x-1}. }[/math]

Также с помощью схемы Горнера можно вычислять значение числа в позиционной системе исчисления.

См. также

• Деление многочленов столбиком
• Деление столбиком
• Метод Лиля

Литература

• Шаблон:Source
• Волков Е. А. § 2. Вычисление значений многочлена. Схема Горнера // Численные методы. — Учеб. пособие для вузов. — 2-е изд., испр. — М.: Наука, 1987. — 248 с.
• С. Б. Гашков. § 14. Схема Горнера и перевод из одной позиционной системы в другую // Системы счисления и их применение. — М.: МЦНМО, 2004. — С. 37—39. — (Библиотека «Математическое просвещение»). — ISBN 5-94057-146-8.

Ссылки

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