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

Обычно многочлен записывают в виде

$f(x)=\sum_{k=0}^{n} a_k x^k$

или, в развёрнутом виде,

$f(x)=a_0+a_1x+a_2x^2+\dots+a_nx^n,$

где действительные числа $a_0, a_1, \dots, a_n$ называются коэффициентами многочлена, а $x$ является переменной.

Если ${a_n\ne 0},$ говорят, что многочлен имеет степень $n,$ то есть ${\deg f(x)=n},$ где $n$ равно наибольшему показателю степени переменной.

Как работает схема Горнера

Схема Горнера (её называют также методом Горнера или правилом Горнера) представляет собой алгоритм, который упрощает вычисление значения многочлена $f(x)$ при заданном значении ${x=x_0}.$ Многочлен записывают как цепочку вложенных друг в друга выражений первой степени. Для каждого из них нужно не более одного умножения и одного сложения, а результат каждого шага используется на следующем. Те же вычисления позволяют разделить многочлен на ${x-x_0},$ поэтому в англоязычной литературе метод называют также синтетическим делением.

Чтобы объяснить это, запишем значение многочлена в точке $x_0$ в развёрнутом виде:

$f(x_0)=a_0+a_1x_0+a_2x_0^2+\dots+a_nx_0^n$

Последовательно вынося $x_0$ за скобки, получаем запись

$f(x_0)=a_0+x_0(a_1+x_0(a_2+x_0(a_3+\dots+{x_0(a_{n-1}+a_nx_0)\dots)))}$

Алгоритм вычисляет выражения в скобках одно за другим, начиная с самых внутренних скобок и двигаясь наружу.

Он состоит из следующих шагов:

1. Положим ${k=n}.$
2. Положим ${b_k=a_k}.$
3. Вычислим ${b_{k-1}=a_{k-1}+x_0b_k}.$
4. Уменьшим $k$ на $1.$
5. Если ${k\ge 1},$ возвращаемся к шагу 3; иначе останавливаемся.

Последнее найденное число и есть значение многочлена: ${b_0=f(x_0)}.$

Возьмём, например, многочлен пятой степени:

$f(x)=a_0+a_1x+a_2x^2+a_3x^3+a_4x^4+a_5x^5$

Его значение при ${x=x_0}$ находят, преобразовав многочлен к виду

$f(x_0)=a_0+x_0(a_1+x_0(a_2+x_0(a_3+{x_0(a_4+a_5x_0))))}$

Шаги алгоритма можно записать в таблицу:

$k$	$b_k$
$5$	${b_5=a_5}$
$4$	${b_4=a_4+x_0b_5}$
$3$	${b_3=a_3+x_0b_4}$
$2$	${b_2=a_2+x_0b_3}$
$1$	${b_1=a_1+x_0b_2}$
$0$	${b_0=a_0+x_0b_1}$

Пример. Найдите значение многочлена ${f(x)=x^4+3x^3+5x^2+7x+9}$ при ${x=2}.$

Решение. Это многочлен четвёртой степени, поэтому ${n=4}.$ Здесь ${x_0=2},$ а коэффициенты таковы: ${a_4=1},$ ${a_3=3},$ ${a_2=5},$ ${a_1=7}$ и ${a_0=9}.$

$k$	Шаг	Результат
$4$	${b_4=1}$	$1$
$3$	${b_3=3+2\cdot 1}$	$5$
$2$	${b_2=5+2\cdot 5}$	$15$
$1$	${b_1=7+2\cdot 15}$	$37$
$0$	${b_0=9+2\cdot 37}$	$83$

Таким образом, ${f(2)=83}.$

Схема Горнера в виде таблицы

На практике записывают только числа, размещая их в таблице из трёх строк. Эту таблицу тоже называют схемой Горнера. В первой строке стоят коэффициенты многочлена, слева записано число $x_0,$ а третья строка заполняется слева направо:

$\begin{array}{c|cccc|c} & a_n & a_{n-1} & \cdots & a_1 & a_0 \\ x_0 & & x_0b_n & \cdots & x_0b_2 & x_0b_1 \\ \hline & b_n & b_{n-1} & \cdots & b_1 & b_0\end{array}$

1. В первую строку запишите коэффициенты в порядке убывания степеней $x.$ Если какой-то степени нет, на её месте запишите $0.$
2. Перенесите первый коэффициент в третью строку: ${b_n=a_n}.$
3. Умножьте только что записанное число на $x_0$ и запишите произведение во вторую строку следующего столбца.
4. Сложите два числа этого столбца и запишите сумму под ними, в третьей строке.
5. Повторяйте шаги 3 и 4, пока не заполните последний столбец.

Для многочлена ${x^4+3x^3+5x^2+7x+9}$ и ${x_0=2}$ из примера выше схема выглядит так:

$\begin{array}{r|rrrr|r} & 1 & 3 & 5 & 7 & 9 \\ 2 & & 2 & 10 & 30 & 74 \\ \hline & 1 & 5 & 15 & 37 & 83\end{array}$

Последнее число третьей строки равно значению многочлена: ${f(2)=83}.$

Деление на двучлен первой степени

Третья строка схемы даёт не только значение $f(x_0).$

Для проверки раскроем скобки в правой части. Коэффициент при $x^n$ равен ${b_n=a_n},$ а коэффициент при каждой меньшей степени $x^k$ равен ${b_k-x_0b_{k+1}},$ то есть $a_k,$ так как ${b_k=a_k+x_0b_{k+1}}.$

Подставив в равенство ${x=x_0},$ снова получим ${f(x_0)=b_0}.$ Это и есть теорема Безу: остаток от деления многочлена $f(x)$ на ${x-x_0}$ равен $f(x_0).$

В примере выше третья строка состоит из чисел $1;$ $5;$ $15;$ $37$ и $83,$ поэтому частное равно ${x^3+5x^2+15x+37},$ а остаток равен $83$:

${x^4+3x^3+5x^2+7x+9}={(x-2)(x^3+5x^2+15x+37)}+83$

Пример. Разделите ${f(x)=2x^4-3x^2+5x-7}$ на ${x+2}.$

Решение. Так как ${x+2=x-(-2)},$ имеем ${x_0=-2}.$ В многочлене нет члена с $x^3,$ поэтому коэффициент при $x^3$ равен $0,$ и первая строка такова: $2;$ $0;$ $-3;$ $5;$ $-7.$

$\begin{array}{r|rrrr|r} & 2 & 0 & -3 & 5 & -7 \\ -2 & & -4 & 8 & -10 & 10 \\ \hline & 2 & -4 & 5 & -5 & 3\end{array}$

Частное равно ${2x^3-4x^2+5x-5},$ а остаток равен $3$:

${2x^4-3x^2+5x-7}={(x+2)(2x^3-4x^2+5x-5)}+3$

Проверка по теореме Безу: ${f(-2)}={2\cdot 16-3\cdot 4+5\cdot(-2)-7}={32-12-10-7}={3}.$

Корни и разложение на множители

Если остаток $b_0$ равен $0,$ то ${f(x_0)=0}.$ Число $x_0$ является корнем многочлена, и многочлен делится на ${x-x_0}$ без остатка:

$f(x)=(x-x_0)\,q(x)$

Поэтому схема Горнера удобна при разложении на множители. Если многочлен с целыми коэффициентами имеет целый корень, то этот корень является делителем свободного члена $a_0.$ Делители $a_0$ проверяют один за другим, и схема Горнера каждый раз показывает, является ли число корнем, и сразу даёт частное. Если последнее число третьей строки не равно $0,$ то число не является корнем, и проверяют следующий делитель.

Пример. Разложите на множители многочлен ${x^3-6x^2+11x-6}.$

Решение. Делители свободного члена: $\pm 1;$ $\pm 2;$ $\pm 3$ и $\pm 6.$ Начнём с ${x_0=1}$:

$\begin{array}{r|rrr|r} & 1 & -6 & 11 & -6 \\ 1 & & 1 & -5 & 6 \\ \hline & 1 & -5 & 6 & 0\end{array}$

Остаток равен $0,$ значит, число $1$ является корнем и ${x^3-6x^2+11x-6}={(x-1)(x^2-5x+6)}.$ Перейдём к частному ${x^2-5x+6}$ и возьмём ${x_0=2}$:

$\begin{array}{r|rr|r} & 1 & -5 & 6 \\ 2 & & 2 & -6 \\ \hline & 1 & -3 & 0\end{array}$

Остаток снова равен $0,$ поэтому ${x^2-5x+6}={(x-2)(x-3)}.$ Следовательно,

${x^3-6x^2+11x-6}={(x-1)(x-2)(x-3)}$

Рациональные корни ищут так же: если несократимая дробь $\frac{p}{q}$ является корнем многочлена с целыми коэффициентами, то $p$ является делителем $a_0,$ а $q$ является делителем старшего коэффициента $a_n.$

Делитель вида mx + n

По схеме Горнера можно делить и на любой многочлен первой степени ${mx+n}.$ Его корень равен ${x_0=-\frac{n}{m}},$ и ${mx+n=m(x-x_0)},$ поэтому

$f(x)={(x-x_0)\,q(x)+b_0}={(mx+n)\cdot\frac{q(x)}{m}+b_0}$

Заполняем схему для $x_0,$ а затем делим коэффициенты частного на $m.$ Остаток не меняется.

Пример. Разделите ${3x^3-5x^2+2x+3}$ на ${2x-1}.$

Решение. Корень делителя равен ${x_0=\frac12}.$

$\def\arraystretch{2.3}\begin{array}{r|rrr|r} & 3 & -5 & 2 & 3 \\ \dfrac12 & & \dfrac32 & -\dfrac74 & \dfrac18 \\ \hline & 3 & -\dfrac72 & \dfrac14 & \dfrac{25}{8}\end{array}$

При делении на ${x-\frac12}$ получаем частное ${3x^2-\frac72x+\frac14}$ и остаток $\frac{25}{8}.$ Делим коэффициенты частного на $2$:

${3x^3-5x^2+2x+3}={(2x-1)\left(\frac32x^2-\frac74x+\frac18\right)}+\frac{25}{8}$

Если делитель имеет вторую или более высокую степень, используйте деление многочленов уголком.

Зачем нужна схема Горнера?

Обычно, чтобы найти значение многочлена при некотором значении переменной, мы подставляем это значение в многочлен и выполняем вычисления. Для этого можно воспользоваться готовой компьютерной программой или написать свою, а при работе со сложными многочленами высоких степеней без программы не обойтись.

То, как компьютер решает задачу, зависит главным образом от того, как вы, программист, её опишете. Программа может вычислять значение многочлена прямой подстановкой или по схеме Горнера. Единственное различие между этими двумя подходами состоит в скорости, с которой компьютер получает ответ.

Преимущество схемы Горнера в том, что она уменьшает число умножений. При прямой подстановке, если каждую степень вычислять заново, для члена $a_kx^k$ нужно $k$ умножений, поэтому для многочлена степени $n$ их потребуется ${1+2+\dots+n}={\frac{n(n+1)}{2}}.$ Схема Горнера требует только $n$ умножений и $n$ сложений. Для многочлена десятой степени это $10$ умножений вместо $55.$ Сложений в обоих способах $n,$ поэтому весь выигрыш приходится на умножения, и для многочленов высоких степеней программа, использующая схему Горнера, работает заметно быстрее.

Упражнения

Решите задачи по схеме Горнера, а затем откройте ответы. Каждый шаг можно проверить и с помощью калькулятора выше.

1. Найдите $f(3)$ для многочлена ${f(x)=2x^3-5x^2+x-7}.$

$\begin{array}{r|rrr|r} & 2 & -5 & 1 & -7 \\ 3 & & 6 & 3 & 12 \\ \hline & 2 & 1 & 4 & 5\end{array}$

${f(3)=5}.$

2. Разделите ${x^4-2x^3+4x-5}$ на ${x-1}.$

Члена с $x^2$ нет, поэтому первая строка такова: $1;$ $-2;$ $0;$ $4;$ $-5.$

$\begin{array}{r|rrrr|r} & 1 & -2 & 0 & 4 & -5 \\ 1 & & 1 & -1 & -1 & 3 \\ \hline & 1 & -1 & -1 & 3 & -2\end{array}$

Частное равно ${x^3-x^2-x+3},$ а остаток равен $-2.$

3. Найдите остаток от деления ${f(x)=x^5-3x^2+2}$ на ${x+1}.$

Здесь ${x_0=-1},$ а первая строка такова: $1;$ $0;$ $0;$ $-3;$ $0;$ $2.$

$\begin{array}{r|rrrrr|r} & 1 & 0 & 0 & -3 & 0 & 2 \\ -1 & & -1 & 1 & -1 & 4 & -4 \\ \hline & 1 & -1 & 1 & -4 & 4 & -2\end{array}$

Остаток равен $-2.$ Проверка: ${f(-1)}={-1-3+2}={-2}.$

4. Докажите, что число $-2$ является корнем многочлена ${3x^3+7x^2-4},$ и разложите многочлен на множители.

Члена с $x$ нет, поэтому первая строка такова: $3;$ $7;$ $0;$ $-4.$

$\begin{array}{r|rrr|r} & 3 & 7 & 0 & -4 \\ -2 & & -6 & -2 & 4 \\ \hline & 3 & 1 & -2 & 0\end{array}$

Остаток равен $0,$ значит, число $-2$ является корнем и ${3x^3+7x^2-4}={(x+2)(3x^2+x-2)}.$ Корни многочлена ${3x^2+x-2}$ равны $-1$ и $\frac23,$ поэтому ${3x^3+7x^2-4}={(x+2)(x+1)(3x-2)}.$

5. Разделите ${4x^3-3x+5}$ на ${2x+1}.$

Здесь ${x_0=-\frac12},$ а первая строка такова: $4;$ $0;$ $-3;$ $5.$

$\def\arraystretch{2.3}\begin{array}{r|rrr|r} & 4 & 0 & -3 & 5 \\ -\dfrac12 & & -2 & 1 & 1 \\ \hline & 4 & -2 & -2 & 6\end{array}$

При делении на ${x+\frac12}$ получаем частное ${4x^2-2x-2}$ и остаток $6.$ Разделив коэффициенты частного на $2,$ получим ${4x^3-3x+5}={(2x+1)(2x^2-x-1)}+6.$