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

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

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

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

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

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

${\displaystyle P(x)=a_{0}+x(a_{1}+x(a_{2}+\cdots x(a_{n-1}+a_{n}x)\dots )).}$

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

${\displaystyle b_{n}=a_{n},}$

${\displaystyle b_{n-1}=a_{n-1}+b_{n}x_{0},}$

…

${\displaystyle b_{i}=a_{i}+b_{i+1}x_{0},}$

…

${\displaystyle b_{0}=a_{0}+b_{1}x_{0}.}$

Искомое значение ${\displaystyle P(x_{0})}$ есть ${\displaystyle b_{0}}$. Покажем, что это так.

В полученную форму записи ${\displaystyle P(x)}$ подставим ${\displaystyle x=x_{0}}$ и будем вычислять значение выражения, начиная с внутренних скобок. Для этого будем заменять подвыражения через ${\displaystyle b_{i}}$:

${\displaystyle {\begin{aligned}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{aligned}}}$

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

При делении многочлена ${\displaystyle a_{0}x^{n}+a_{1}x^{n-1}+\cdots +a_{n-1}x+a_{n}}$ на ${\displaystyle x-c}$ получается многочлен ${\displaystyle b_{0}x^{n-1}+b_{1}x^{n-2}+\cdots +b_{n-2}x+b_{n-1}}$ с остатком ${\displaystyle b_{n}}$ (см. теорема Безу).

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

${\displaystyle b_{0}=a_{0},\quad b_{k}=a_{k}+cb_{k-1}.}$

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

${\displaystyle P(x)=b_{n}+b_{n-1}(x-c)+b_{n-2}(x-c)^{2}+\cdots +b_{0}(x-c)^{n}.}$

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

${\displaystyle P^{(k)}(c)=k!b_{n-k}.}$

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

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

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

Здесь в первой строке записаны значение ${\displaystyle x_{0}}$ и коэффициенты многочлена.

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

Например, если ${\displaystyle a_{3}=2,a_{2}=-6,a_{1}=2,a_{0}=-1}$ мы видим, что ${\displaystyle b_{3}=2,b_{2}=0,b_{1}=2,b_{0}=5}$ — значения в третьей строке. Так синтетическое деление базируется на методе Горнера.

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

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

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

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

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

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

${\displaystyle {\frac {f_{1}(x)}{f_{2}(x)}}=2x^{3}-2x^{2}-x+1-{\frac {4}{2x-1}}.}$

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