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

Схема Горнера – способ деления многочлена

\[P_n(x)=\sum\limits_{i=0}^{n}a_{i}x^{n-i}=a_{0}x^{n}+a_{1}x^{n-1}+a_{2}x^{n-2}+\ldots+a_{n-1}x+a_n\]

на бином \(\displaystyle{x-a}\). Подробное описание этого метода с теоретическим обоснованием можно прочесть в книге А. Г. Куроша "Курс высшей алгебры" (параграф №22). Здесь же мы обсудим сугубо практическую реализацию данного алгоритма.

Для оформления расчётов с использованием схемы Горнера составляют таблицу, первая строка которой содержит коэффициенты заданного многочлена (они выделены для наглядности синим цветом). Первым элементом второй строки будет число \(\displaystyle{a}\), взятое из бинома \(\displaystyle{x-a}\):

\[ P_n(x) =\normblue{a_{0}}x^{n}+\normblue{a_{1}}x^{n-1}+\normblue{a_{2}}x^{n-2}+\ldots +\normblue{a_{n-1}}x+\normblue{a_n}\\ \]

\[ \begin{array} {c|c|c|c|c|c|c|c} & \normblue{a_0} & \normblue{a_1} & \normblue{a_2} & \normblue{a_3} & \ldots & \normblue{a_{n-1}} & \normblue{a_n} \\ \hline a & & & & & & & \end{array} \]

Вторая строка таблицы заполняется постепенно. Второй элемент этой строки (обозначим его \(\displaystyle{b_0}\)) равен \(\displaystyle{a_0}\), т.е., по сути, мы просто переносим вниз число \(\displaystyle{a_0}\):

\[ \begin{array} {c|c|c|c|c|c|c|c} & a_0 & a_1 & a_2 & a_3 & \ldots & a_{n-1} & a_n \\ \hline a & b_0=a_0 & & & & & & \end{array} \]

Остальные элементы второй строки заполняются с использованием однотипных вычислений. Следующий элемент второй строки, который мы обозначим как \(\displaystyle{b_1}\), получается по такой формуле: \(\displaystyle{b_1=a\cdot{b_0}+a_1}\):

\[ \begin{array} {c|c|c|c|c|c|c|c} & a_0 & \boxed{a_1} & a_2 & a_3 & \ldots & a_{n-1} & a_n \\ \hline \boxed{a} & \boxed{b_0} & b_1=a\cdot{b_0}+a_1 & & & & & \end{array} \]

Далее находим элемент \(\displaystyle{b_2}\) по формуле \(\displaystyle{b_2=a\cdot{b_1}+a_2}\):

\[ \begin{array} {c|c|c|c|c|c|c|c} & a_0 & a_1 & \boxed{a_2} & a_3 & \ldots & a_{n-1} & a_n \\ \hline \boxed{a} & b_0 & \boxed{b_1} & b_2=a\cdot{b_1}+a_2 & & & & \end{array} \]

Аналогично вычисляем и элемент \(\displaystyle{b_3=a\cdot{b_2}+a_3}\):

\[ \begin{array} {c|c|c|c|c|c|c|c} & a_0 & a_1 & a_2 & \boxed{a_3} & \ldots & a_{n-1} & a_n \\ \hline \boxed{a} & b_0 & b_1 & \boxed{b_2} & b_3=a\cdot{b_2}+a_3 & & & \end{array} \]

Далее находим \(\displaystyle{b_4}\), \(\displaystyle{b_5}\) и так далее. В целом, общая формула для вычисления \(\displaystyle{b_i}\), где \(\displaystyle{i\ge{1}}\), будет такой:

\[ b_i = a\cdot{b_{i-1}}+a_i \]

В конечном итоге мы вычислим последний элемент \(\displaystyle{b_n = a\cdot{b_{n-1}}+a_n}\), и на этом работа будет закончена. Заполненная таблица будет иметь такой вид:

\[ \begin{array} {c|c|c|c|c|c|c|c} & a_0 & a_1 & a_2 & a_3 & \ldots & a_{n-1} & a_n \\ \hline a & b_0 & b_1 & b_2 & b_3 & \ldots & b_{n-1} & b_n \end{array} \]

После деления исходного многочлена n-ой степени \(\displaystyle{P_n(x)}\) на бином \(\displaystyle{x-a}\), получим многочлен, степень которого на единицу меньше исходного, т.е. равна \(\displaystyle{n-1}\). Последнее число второй строки, т.е. \(\displaystyle{b_n}\), есть остаток от деления \(\displaystyle{P_n(x)}\) на \(\displaystyle{x-a}\):

\[ a_{0}x^{n}+a_{1}x^{n-1}+a_{2}x^{n-2}+\ldots+a_{n-1}x+a_n =(x-a)\cdot\left(b_{0}x^{n-1}+b_{1}x^{n-2}+\ldots+b_{n-1}\right)+b_n \]

Если вспомнить теорему Безу, то можно сформулировать и так: число \(\displaystyle{b_n}\) равно значению многочлена \(\displaystyle{P_n(x)}\) при \(\displaystyle{x=a}\), т.е. \(\displaystyle{b_n = P_n (a)}\).

Если \(\displaystyle{b_n=0}\), то исходный многочлен делится на бином \(\displaystyle{x-a}\) нацело, т.е. число \(\displaystyle{a}\) является корнем этого многочлена.

Задача №1

Условие

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

Решение

Для сокращения записи обозначим заданный многочлен как \(\displaystyle{P(x)}\), т.е. \(\displaystyle{P(x)=7x^4-x^3+5x^2-11}\). Для начала составим таблицу из двух строк. В первой строке запишем коэффициенты многочлена \(\displaystyle{P(x)}\), расположенные по убыванию степеней переменной \(\displaystyle{x}\). Заметьте, что данный многочлен не содержит \(\displaystyle{x}\) в первой степени, т.е. коэффициент перед \(\displaystyle{x}\) в первой степени равен 0:

\[ 7\cdot{x^4}-1\cdot{x^3}+5\cdot{x^2}+0\cdot{x}+(-11) \]

Так как мы делим на \(\displaystyle{x-\normred{1}}\), то в первой ячейке второй строки запишем число \(\displaystyle{\normred{1}}\). Таблица, которую мы станем заполнять, имеет такой вид:

\[ \begin{array} {c|c|c|c|c|c} & 7 & -1 & 5 & 0 & -11 \\ \hline \normred{1} & & & & & \end{array} \]

Во вторую ячейку второй строки запишем число \(\displaystyle{7}\), просто перенеся его вниз из второй ячейки первой строки:

\[ \begin{array} {c|c|c|c|c|c} & \normgreen{7} & -1 & 5 & 0 & -11 \\ \hline 1 & \normgreen{7} & & & & \end{array} \]

Следующую ячейку заполним по такому принципу: \(\displaystyle{\normred{1}\cdot\normgreen{7}+\normblue{(-1)}=6}\):

\[ \begin{array} {c|c|c|c|c|c} & 7 & \normblue{\boxed{-1}} & 5 & 0 & -11 \\ \hline \normred{\boxed{1}} & \normgreen{\boxed{7}} & \normred{1}\cdot\normgreen{7}+\normblue{(-1)}=6 & & & \end{array} \]

Разумеется, обычно само действие в ячейку не записывают, выполняя его в уме. Пишут лишь готовый результат:

\[ \begin{array} {c|c|c|c|c|c} & 7 & -1 & 5 & 0 & -11 \\ \hline 1 & 7 & 6 & & & \end{array} \]

Теперь заполним четвёртую ячейку второй строки – аналогично предыдущему: \(\displaystyle{\normred{1}\cdot\normgreen{6}+\normblue{5}=11}\):

\[ \begin{array} {c|c|c|c|c|c} & 7 & -1 & \normblue{\boxed{5}} & 0 & -11 \\ \hline \normred{\boxed{1}} & 7 & \normgreen{\boxed{6}} & 11 & & \end{array} \]

Для пятой ячейки получим: \(\displaystyle{\normred{1}\cdot\normgreen{11}+\normblue{0}=11}\):

\[ \begin{array} {c|c|c|c|c|c} & 7 & -1 & 5 & \normblue{\boxed{0}} & -11 \\ \hline \normred{\boxed{1}} & 7 & 6 & \normgreen{\boxed{11}} & 11 & \end{array} \]

И, наконец, для последней, шестой ячейки, имеем: \(\displaystyle{\normred{1}\cdot\normgreen{11}+\normblue{(-11)}=0}\):

\[ \begin{array} {c|c|c|c|c|c} & 7 & -1 & 5 & 0 & \normblue{\boxed{-11}} \\ \hline \normred{\boxed{1}} & 7 & 6 & 11 & \normgreen{\boxed{11}} & 0 \end{array} \]

Числа, расположенные во второй строке (между единицей и нулём), есть коэффициенты многочлена, полученного после деления \(\displaystyle{P(x)}\) на \(\displaystyle{x-1}\). Последнее число во второй строке (ноль) равно остатку от деления многочлена \(\displaystyle{P(x)}\) на \(\displaystyle{x-1}\). Остаток равен нулю, т.е. многочлен \(\displaystyle{P(x)}\) делится на \(\displaystyle{x-1}\) нацело. Для наглядности я запишу полученный результат, выделив коэффициенты разными цветами:

\[ \begin{array} {c|c|c|c|c|c} & 7 & -1 & 5 & 0 & -11 \\ \hline \normred{1} & \normblue{7} & \normblue{6} & \normblue{11} & \normblue{11} &\normgreen{0} \end{array} \]

\[ P(x) =(x-\normred{1})\cdot\left(\normblue{7}\cdot{x^3}+\normblue{6}\cdot{x^2}+\normblue{11}\cdot{x^1}+\normblue{11}\right)+\normgreen{0} =(x-1)\left(7x^3+6x^2+11x+11\right) \]

Полученный нами результат можно ещё охарактеризовать так: значение многочлена \(\displaystyle{P(x)}\) при \(\displaystyle{x=1}\) равно нулю. Так как значение многочлена \(\displaystyle{P(x)}\) при \(\displaystyle{x=1}\) равно нулю, то единица является корнем многочлена \(\displaystyle{P(x)}\).

Ответ:

\(\displaystyle{7x^4-x^3+5x^2-11 = (x-1)\left(7x^3+6x^2+11x+11\right)}\)

Задача №2

Условие

Разделить многочлен \(\displaystyle{x^4+3x^3+4x^2-5x-47}\) на \(\displaystyle{x+3}\) по схеме Горнера.

Решение

Для сокращения записи обозначим заданный многочлен как \(\displaystyle{P(x)}\), т.е. \(\displaystyle{P(x)=x^4+3x^3+4x^2-5x-47}\). Сразу оговорим, что выражение \(\displaystyle{x+3}\) нужно представить в форме \(\displaystyle{x-(-3)}\). В схеме Горнера будет участвовать именно \(\displaystyle{-3}\). Выполняем преобразования, аналогичные сделанным в задаче №1:

\[ \begin{array} {c|c|c|c|c|c} & 1 & 3 & 4 & -5 & -47 \\ \hline -3 & 1 & 0 & 4 & -17 & 4 \end{array} \]

Так как степень исходного многочлена \(\displaystyle{P(x)}\) равна четырём, то в результате деления получим многочлен третьей степени.

\[ P(x) =(x+3)\left(x^3+0\cdot x^2 +4x-17\right)+4 =(x+3)\left(x^3+4x-17\right)+4 \]

Полученный результат означает, что многочлен \(\displaystyle{P(x)}\) делится на бином \(\displaystyle{x+3}\) не нацело. Остаток от деления \(\displaystyle{P(x)}\) на \(\displaystyle{x+3}\) равен \(\displaystyle{4}\). Этот же результат означает, что значение многочлена \(\displaystyle{P(x)}\) при \(\displaystyle{x=-3}\) равно \(\displaystyle{4}\), т.е. \(\displaystyle{P(-3)=4}\). Кстати, это несложно перепроверить непосредственной подстановкой \(\displaystyle{x=-3}\) в заданный многочлен:

\[ x^4+3x^3+4x^2-5x-47 =(-3)^4+ {3} \cdot (-3)^3 +4\cdot(-3)^2 - {5} \cdot (-3)-47 =4 \]

Т.е. схему Горнера можно также использовать, если необходимо найти значение многочлена при заданном значении переменной.

Ответ:

\(\displaystyle{x^4+3x^3+4x^2-5x-47=(x+3)\left(x^3+4x-17\right)+4}\)

Если наша цель – найти все корни многочлена, то схему Горнера можно применять несколько раз подряд: до тех пор, пока мы не исчерпаем все корни, как рассмотрено в задаче №3.

Задача №3

Условие

Найти все целочисленные корни многочлена \(\displaystyle{x^6+2x^5-21x^4-20x^3+71x^2+114x+45}\), используя схему Горнера. Разложить многочлен на множители.

Решение

Для сокращения записи обозначим заданный многочлен как \(\displaystyle{P(x)}\), т.е.

\[P(x)=x^6+2x^5-21x^4-20x^3+71x^2+114x+45\]

Коэффициенты рассматриваемого многочлена есть целые числа. В этом случае действует такое правило:

Пусть коэффициенты многочлена \(\displaystyle{P_n(x)}\) являются целыми числами. Если данный многочлен имеет целый корень \(\displaystyle{k}\), то число \(\displaystyle{k}\) будет делителем свободного члена многочлена \(\displaystyle{P_n(x)}\), т.е. \(\displaystyle{a_0}\) нацело делится на \(\displaystyle{k}\).

Иными словами, целочисленные корни многочлена с целыми коэффициентами нужно искать среди делителей его свободного члена. Конечно, это вовсе не означает, что все делители свободного члена непременно будут корнями многочлена. Данное правило говорит лишь о том, что если целый корень есть, то свободный член делится на него.

Свободный член рассматриваемого в задаче многочлена равен 45, т.е. если многочлен и имеет целые корни, то они являются делителями числа 45. Число 45 нацело делится на \(\displaystyle{\pm{1}}\), \(\displaystyle{\pm{3}}\), \(\displaystyle{\pm{5}}\), \(\displaystyle{\pm{9}}\), \(\displaystyle{\pm{15}}\), \(\displaystyle{\pm{45}}\). Все эти числа могут быть корнями рассматриваемого многочлена. Проверим, к примеру, число \(\displaystyle{1}\):

Таблица №1

\[ \begin{array} {c|c|c|c|c|c|c|c} & 1 & 2 & -21 & -20 & 71 & 114 & 45 \\ \hline 1 & 1 & 3 & -18 & -38 & 33 & 147 & 192 \end{array} \]

Как видите, значение многочлена \(\displaystyle{P(x)}\) при \(\displaystyle{x=1}\) равно \(\displaystyle{192}\) (последнее число во второй строке), а не \(\displaystyle{0}\), посему единица не является корнем данного многочлена. Так как проверка для единицы окончилась неудачей, проверим значение \(\displaystyle{x=-1}\). Новую таблицу составлять не будем, а продолжим использование табл. №1, дописав в нее новую (третью) строку. Вторую строку, в которой проверялось значение \(\displaystyle{1}\), выделим красным цветом и в дальнейших рассуждениях использовать её не будем.

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

Таблица №2

Итак, значение многочлена \(\displaystyle{P(x)}\) при \(\displaystyle{x=-1}\) равно нулю, т.е. \(\displaystyle{P(-1)=0}\). Это значит, что число \(\displaystyle{-1}\) есть корень многочлена \(\displaystyle{P(x)}\). Частным от деления многочлена \(\displaystyle{P(x)}\) на бином \(\displaystyle{x-(-1)=x+1}\) будет многочлен \(\displaystyle{Q_1(x)=x^5+x^4-22x^3+2x^2+69x+45}\), коэффициенты которого взяты из третьей строки табл. №2. Результат вычислений представим в такой форме:

\[ P(x) =(x+1)\left(x^5+x^4-22x^3+2x^2+69x+45\right) =(x+1)Q_1(x) \tag{3.1} \]

Продолжим поиск целочисленных корней. Теперь уже нужно искать корни многочлена \(\displaystyle{Q_1(x)}\). Опять-таки, целочисленные корни этого многочлена ищем среди делителей его свободного члена, – числа \(\displaystyle{45}\). Попробуем ещё раз проверить число \(\displaystyle{-1}\). Новую таблицу составлять не будем, а продолжим использование предыдущей табл. №2, т.е. допишем в нее еще одну строку:

Итак, число \(\displaystyle{-1}\) является корнем многочлена \(\displaystyle{Q_1(x)}\). При этом частным от деления \(\displaystyle{Q_1(x)}\) на \(\displaystyle{x+1}\) будет многочлен \(\displaystyle{Q_2(x)=x^4-22x^2+24x+45}\):

\[ Q_1(x)=(x+1)\left(x^4-22x^2+24x+45\right) =(x+1)Q_2(x) \tag{3.2} \]

Учитывая равенство (3.2), равенство (3.1) можно переписать в такой форме:

\[ P(x)=(x+1)Q_1(x) =(x+1)(x+1)Q_2(x) =(x+1)^2 Q_2(x) \tag{3.3} \]

Теперь уже нужно искать корни многочлена \(\displaystyle{Q_2(x)}\), – естественно, среди делителей его свободного члена (числа \(\displaystyle{45}\)). Проверим еще раз число \(\displaystyle{-1}\):

Число \(\displaystyle{-1}\) является корнем многочлена \(\displaystyle{Q_2(x)}\). Частным от деления многочлена \(\displaystyle{Q_2(x)}\) на \(\displaystyle{x+1}\) будет многочлен \(\displaystyle{Q_3(x)=x^3-x^2-21x+45}\), т.е.

\[ Q_2(x) =(x+1)\left(x^3-x^2-21x+45\right) =(x+1)Q_3(x) \tag{3.4} \]

С учетом равенства (3.4), равенство (3.3) перепишем в такой форме:

\[ P(x)=(x+1)^2 Q_2(x) =(x+1)^2(x+1)Q_3(x) =(x+1)^3 Q_3(x) \tag{3.5} \]

Теперь ищем корни многочлена \(\displaystyle{Q_3(x)}\). Проверим еще раз число \(\displaystyle{-1}\):

\[ \begin{array} {c|c|c|c|c|c|c|c} & 1 & 2 & -21 & -20 & 71 & 114 & 45 \\ \hline \normred{1} & \normred{1} & \normred{3} & \normred{-18} & \normred{-38} & \normred{33} & \normred{147} & \normred{192}\\ \hline -1 & 1 & 1 & -22 & 2 & 69 & 45 & 0 \\ \hline -1 & 1 & 0 & -22 & 24 & 45 & 0 & \\ \hline -1 & 1 & -1 & -21 & 45 & 0 & & \\ \hline -1 & 1 & -2 & -19 & 64 & & & \end{array} \]

Проверка окончилась неудачей. Выделим шестую строку красным цветом и попробуем проверить иное число, например, число \(\displaystyle{3}\):

В остатке ноль, посему число \(\displaystyle{3}\) – корень многочлена \(\displaystyle{Q_3(x)}\). Частным от деления многочлена \(\displaystyle{Q_3(x)}\) на \(\displaystyle{x-3}\) будет многочлен \(\displaystyle{Q_4(x)=x^2+2x-15}\):

\[ Q_3(x) =(x-3)\left(x^2+2x-15\right) =(x-3)Q_4(x) \]

Теперь равенство (3.5) можно переписать так:

\[ P(x)=(x+1)^3 Q_3(x) =(x+1)^3(x-3) Q_4(x) \tag{3.6} \]

Проверим ещё раз число \(\displaystyle{3}\) – не является ли оно корнем многочлена \(\displaystyle{Q_4(x)}\):

Полученный результат можно записать так (это продолжение равенства (3.6)):

\[ P(x) =(x+1)^3(x-3)Q_4(x) =(x+1)^3(x-3)(x-3)(x+5) =(x+1)^3(x-3)^2(x+5) \tag{3.7} \]

Из последней скобки видно, что число \(\displaystyle{-5}\) также является корнем данного многочлена. Итак,

\[P(x)=(x+1)^3(x-3)^2(x+5)\]

Числа \(\displaystyle{-1}\), \(\displaystyle{3}\), \(\displaystyle{-5}\) – корни данного многочлена. Причем так как скобка \(\displaystyle{(x+1)}\) в третьей степени, то \(\displaystyle{-1}\) – корень кратности 3; так как скобка \(\displaystyle{(x-3)}\) во второй степени, то \(\displaystyle{3}\) – корень кратности 2; так как скобка \(\displaystyle{(x+5)}\) в первой степени, то \(\displaystyle{x=-5}\) – корень кратности 1 (простой корень).

Вообще, обычно оформление таких примеров состоит из таблицы, в которой перебираются возможные варианты корней, и ответа:

Из таблицы следует вывод, полученный нами ранее с подробным решением:

\[P(x)=(x+1)^3(x-3)^2(x+5)\]

Ответ:

\(\displaystyle{-1}\), \(\displaystyle{3}\), \(\displaystyle{-5}\).

Задача №4

Условие

Убедиться, что числа \(\displaystyle{2}\) и \(\displaystyle{-5}\) являются корнями многочлена \(\displaystyle{3x^6+9x^5-28x^4+6x^3-30x^2-30x+100}\). Разделить заданный многочлен на биномы \(\displaystyle{x-2}\) и \(\displaystyle{x+5}\).

Решение

Как и ранее, для сокращения записи обозначим заданный многочлен как \(\displaystyle{P(x)}\), т.е.

\[P(x)=3x^6+9x^5-28x^4+6x^3-30x^2-30x+100\]

Степень многочлена \(\displaystyle{P(x)}\) равна \(\displaystyle{6}\). После деления на два заданных бинома степень заданного многочлена уменьшится на \(\displaystyle{2}\), т.е. станет равна \(\displaystyle{4}\).

\[ \begin{array} {c|c|c|c|c|c|c|c} & 3 & 9 & -28 & 6 & -30 & -30 & 100 \\ \hline \normblue{2} & 3 & 15 & 2 & 10 & -10 & -50 & 0 \\ \hline \normpurple{-5} & \normgreen{3} & \normgreen{0} & \normgreen{2} & \normgreen{0} & \normgreen{-10} & 0 & \end{array} \]

\[ P(x)=(x-\normblue{2})\cdot(x-(\normpurple{-5}))\cdot\left(\normgreen{3}\cdot{x^4}+\normgreen{0}\cdot{x^3}+\normgreen{2}\cdot{x^2} + \normgreen{0}\cdot{x} + (\normgreen{-10})\right) =(x-2)(x+5)\left(3x^4+2x^2-10\right) \]

В конце хотелось бы подчеркнуть, что схема Горнера, разумеется, работает не только для целочисленных корней. Однако в практических задачах данный метод в подавляющем большинстве случаев применяется для перебора целых значений, так как использование схемы Горнера для поиска корней, не являющихся целыми числами, является довольно затруднительным.