Для того чтобы понять принцип работы алгоритма (который также называют «схемой Горнера» или «методом Горнера»), разберемся, что с его помощью можно делать, откуда берется этот алгоритм, как именно и почему он работает.
-
Алгоритм Горнера помогает решать две алгебраические задачи:
- Решение уравнений высших степеней;
- Работа с многочленами.
Все это можно делать и без использования алгоритма, однако его преимущество заключается в скорости.
Выведем схему Горнера
Пусть нам нужно найти корни многочлена $P\left(x\right),$ то есть решить уравнение $P\left(x\right)=0.$ $P\left(x\right)$ представим в виде: $$\displaystyle\sum\limits_{i=0}^n{a_{i}x^i} = a_{n}x^n + a_{n-1}x^{n-1} + \ldots +\ a_{1}x + a_{0}. $$ Решение может осуществляться методами, которые используют производные (если нам нужно найти только действительные корни), а также любыми итерационными способами. Последний требует многократного вычисления значений многочлена.
По следствию из теоремы Безу, многочлен $P\left(x\right)$ можно представить в виде: $$P\left(x\right) = \left(x-x_{0}\right)Q\left(x\right) + R\left(x\right),$$ где $Q\left(x\right)\ — $ результат деления $P\left(x\right)$ на $\left(x-x_{0}\right),\ R\left(x\right)\ — $ остаток от этого деления. Обозначим $Q\left(x\right)$ как $b_{n-1}x^{n-1} + b_{n-2}x^{n-2} + \ldots + b_{0}.$ Перепишем наш многочлен: \begin{multline}\underbrace{a_{n}x^n + a_{n-1}x^{n-1} + \ldots + a_{1}x + a_{0}}_{P\left(x\right)} \equiv \\ \equiv \left(x-x_{0}\right)\underbrace{\left(b_{n-1}x^{n-1} + b_{n-2}x^{n-2} + \ldots + b_{0}\right)}_{Q\left(x\right)} + R\left(x\right). \end{multline} Для того чтобы вычислить значения многочлена, нам необходимо при заданном $x = x_{0}$ найти степени $x_{0}^k,\ \left(k = \overline{1,n}\right),$ результаты умножить на коэффициенты $\left(b_{n-1}, b_{n-2}, \ldots, b_{0}\right)$, а получившееся сложить. Однако, чтобы ускорить процесс и вдвое сократить количество умножений, можно воспользоваться алгоритмом Горнера. Выведем его.
Алгоритм берет свое начало из теоремы Безу, которая звучит так: если многочлен $P\left(x\right)$ разделить на двучлен $\left(x-x_{0}\right),$ то остаток от этого деления будет равен значению $P\left(x\right)$ на элементе $x_{0},$ т.е. (остаток)$R\left(x\right) = P\left(x_{0}\right).$
В тождестве $\left(1\right)$ умножим $\left(x-x_{0}\right)$ на $Q\left(x\right)$. Получаем $$a_{n}x^n + a_{n-1}x^{n-1} + \ldots + a_{1}x + a_{0} \equiv \\ \equiv b_{n-1}x^n + b_{n-2}x^{n-1} + \ldots + b_{0}x-\\-x_{0}b_{n-1}x^{n-1}-x_{0}b_{n-2}x^{n-2}-\ldots-x_{0}b_{0} + R\left(x\right).$$ Теперь приравняем коэффициенты при одинаковых степенях $x:$ $b_{n-1} = a_{n};\ b_{n-2} = a_{n-1}+x_{0}b_{n-1};\ \ldots;\ R\left(x\right) = a_{0}+x_{0}b_{0}.$ Приходим к исходному: $R\left(x\right)=P\left(x_{0}\right).$ Результаты оформим в виде таблицы:
| $a_n$ | $a_{n-1}$ | $\ldots$ | $a_0$ | |
| $x_0$ | $b_{n-1}$ | $b_{n-2}$ | $\ldots$ | $R\left(x\right)$ |
|---|
Эта таблица и есть схемой Горнера.
Замечание: помимо значения остатка $R\left(x\right),$ алгоритм дает нам $Q\left(x\right)$ (неполное частное). Также, если остаток $R\left(x\right)=0,$ то $x_{0} — $ корень многочлена $P\left(x\right).$
Далее, с помощью примеров, рассмотрим, как алгоритм работает на практике.
Примеры решения задач
-
Разделить многочлен $P_{5}\left(x\right) = x^5-8x^4+7x^3-4x^2+16x+24$ на $\left(x-2\right).$
РешениеВместо деления уголком, воспользуемся алгоритмом Горнера:
$1$ $-8$ $7$ $-4$ $16$ $24$ $2$ $1$ В ячейки, выделенные розовым, записываем коэффициенты многочлена $P_5\left(x\right),$ а в желтую ячейку — $x_0.$ Оставшееся место в таблице будем заполнять вычислениями. Первое число всегда сносим без изменений.
$1$ $-8$ $7$ $-4$ $16$ $24$ $2$ $1$ $-6$ $x_0$ умножаем на число в ячейке напротив, складываем со следующим коэффициентом $P_5\left(x\right),$ и под ним записываем результат (в зеленой ячейке). Дальше продолжаем выполнять действия, которые указаны выше. Получаем таблицу:
$1$ $-8$ $7$ $-4$ $16$ $24$ $2$ $1$ $-6$ $-5$ $-14$ $-12$ $0$ Область, выделенная голубым — это получившиеся коэффициенты нового многочлена $Q\left(x\right),$ а фиолетовым — остаток $R\left(x\right).$
Ответ: $P_5\left(x\right) = x^5-8x^4+7x^3-4x^2+16x+24= \\ =\left(x-2\right)\left(x^4-6x^3-5x^2-14x^2-12x\right) + 0.$
Заметим, что степень $Q\left(x\right)$ всегда на $1$ меньше степени $P\left(x\right).$ Также, выше было сказано, что если $R\left(x\right)=0,$ то $x_{0} — $ корень многочлена. В данном случае $x_{0}$ является корнем $P_{5}\left(x\right).$
[свернуть] -
Определить кратность корня $x_{0}=1$ многочлена $P_{5}\left(x\right)=x^5-8x^3+14x^2-9x+2.$
РешениеКратность корня определяется количеством нулевых остатков от деления $P\left(x\right)$ на $\left(x-x_{0}\right).$ Воспользуемся схемой Горнера:
$1$ $0$ $-8$ $14$ $-9$ $2$ $1$ $1$ $1$ $-7$ $7$ $-2$ $0$ Так как $R\left(x\right)=0,$ мы можем проверить, является ли $x_0=1$ корнем для уже нового многочлена $Q\left(x\right).$ Продолжаем заполнять таблицу по тому же принципу.
$1$ $0$ $-8$ $14$ $-9$ $2$ $1$ $1$ $1$ $-7$ $7$ $-2$ $0$ $1$ $1$ $2$ $-5$ $2$ $0$ $1$ $1$ $3$ $-2$ $0$ $1$ $1$ $4$ $2$ В последней строке мы получили ненулевой остаток. Значит, вычисления можно закончить. Определяем кратность по количеству нулей на «лесенке». Записываем получившееся разложение: $$P_5\left(x\right) = x^5-8x^3+14x^2-9x+2 = \left(x-1\right)^3\left(x^2+3x-2\right).$$
Ответ: $x_0$ для многочлена $P_5\left(x\right)$ является корнем третьей кратности.
[свернуть] -
При каких значениях $A$ и $B$ многочлен $P_4\left(x\right) = Ax^4 + Bx^2 + 1$ делится на $\left(x-1\right)^2?$
РешениеПерефразируем условие задачи для лучшего понимания: при каких $A$ и $B$ число $x_0$ будет корнем $P_4\left(x\right)$, кратности не ниже $2?$ Воспользуемся алгоритмом Горнера.
$A$ $0$ $B$ $0$ $1$ $1$ $A$ $A$ $A+B$ $A+B$ $A+B+1$ $1$ $A$ $2A$ $3A+B$ $4A+2B$ $1$ $A$ $3A$ $6A+B$ Можем сделать вывод, что кратность корня будет не ниже двух тогда и только тогда, когда $\begin{cases}A + B + 1 = 0 \\ 4A + 2B = 0\end{cases}.$ Отсюда $A = 1, B= -2.$ Однако, есть вероятность, что при этих же значениях $A$ и $B$ кратность корня будет больше. Для этого мы и записали последнюю строку в таблице. Не составляет труда проверить, что $6A + B = 6 \cdot 1 + \left(-2\right) = 4 \neq 0 \Rightarrow$ кратность корня равна двум, ни больше, ни меньше.
Ответ: $\left(x-1\right)^2$ делит $P_4\left(x\right) \Leftrightarrow A=1,\ B=-2.$ $\left(x-1\right)^3$ не делит $P_4\left(x\right)$ ни при полученных значениях $A$ и $B,$ ни при каких других.
[свернуть] -
Дан многочлен $P_4\left(x\right) = x^4-\left(2+i\right)x^3-\left(3+2i\right)x + 5$ над полем $\usepackage{amsfonts}\mathbb{C}$. Разделить его с остатком на $\left(x-x_0\right),$ где $x_0 = 1-i,$ попутно вычислив $P_4\left(x_0\right).$
РешениеИспользуем схему Горнера таким же образом, как в примерах выше.
$1$ $-2-i$ $0$ $-3-2i$ $5$ $1-i$ $1$ $-1-2i$ $-3-i$ $-7$ $2-7i$ - $1-i-2+i = \mathbf{-1-2i};$
- $\left(-1-2i\right)\left(1-i\right) = -1+i-2i+2i^2 = -1-i-2 = \mathbf{-3-i};$
- $\left(-3-i\right)\left(1-i\right) = -3+3i-i+i^2 = -3+2i-1 = -4+2i; \\ -4+2i-3-2i = \mathbf{-7};$
- $\left(-7\right)\left(1-i\right) = -7-7i; \\ -7-7i+5 = \mathbf{2-7i}.$
Ответ: $P_4\left(x\right) = \left(x-\left(1-i\right)\right)\left(x^3+\left(-1-2i\right)x^2+\left(-3-i\right)x-7\right)+\left(2-7i\right);$ $P_4\left(x_0\right) = 2-7i.$
[свернуть]
Почему алгоритм Горнера работает?
После ознакомления с примерами решения задач, можно приступить к изучению данного вопроса. Представим многочлен уже привычным нам образом $P\left(x\right) = a_{n}x^n + a_{n-1}x^{n-1} + \ldots + a_{1}x + a_{0}.$ Сделаем самое очевидное действие — вынесем $x$ за скобки: $x\left(a_{n}x^{n-1} + a_{n-1}x^{n-2} + \ldots + a_{1}\right) + a_{0}.$ Если мы повторим это действие $n-1$ раз, то получим $$\underbrace{x(x(x\ldots}_{n-1}\left(a_{n}x+a_{n-1}\right)+\ldots \left)+a_1\right)+a_0.$$ Алгоритм Горнера работает вне зависимости от того, какая степень у многочлена — схема универсальна. Посмотрим на примере. \begin{multline}P_7\left(x\right) = x^7+5x^6-2x^5-x^4+3x^2-8x+11 = \\ = x\left(x^6+5x^5-2x^4-x^3+3x-8\right)+11 = \\ = x\left(x\left(x^5+5x^4-2x^3-x^2+3\right)-8\right)+11 = \\ = x\left(x\left(x\left(x^4+5x^3-2x^2-x+0\right)+3\right)-8\right)+11 = \\ = x\left(x\left(x\left(x\left(x^3+5x^2-2x-1\right)+0\right)+3\right)-8\right)+11 = \\ = x\left(x\left(x\left(x\left(x\left(x^2+5x-2\right)-1\right)+0\right)+3\right)-8\right)+11 = \\ = \underbrace{x(x(x(x(x(x}_{(n-1)=(7-1)=6} (x+5)-2)-1)+0)+3)-8)+11 = \\ = x\left(x\left(x\left(x\left(x\left(x\left(\left(1\cdot x\right)+5\right)-2\right)-1\right)+0\right)+3\right)-8\right)+11. \end{multline} Отсюда видим, для того чтобы посчитать выражение $\left(2\right),$ мы должны $1$ (коэффициент перед $x^7$) умножить на $x,$ результат прибавить к $5$ (коэффициент перед $x^6$), опять умножить на $x$ и т.д. То есть мы делаем все то, что и в схеме Горнера.
Почему разложение $P\left(x\right) = \left(x-x_0\right)Q\left(x\right)+R\left(x\right)$ — верно? Начнем с арифметики. Возьмем какое-то натуральное число $a.$ Как гласит нам основная теорема арифметики, его всегда можно представить в виде произведения двух других чисел с остатком, то есть $a = s \cdot q + r.$ Например, $7 = 2 \cdot 3 +1,$ $8 = 4 \cdot 2 + 0.$ Разложение такого типа единственно, причем $0 \leqslant r < s.$
Тоже самое происходит и с многочленами. Допустим, мы хотим разделить многочлен $P\left(x\right)$ на $Q\left(x\right)$ с остатком. Значит $P\left(x\right)$ можно записать как $P\left(x\right) = S\left(x\right) \cdot Q\left(x\right) + R\left(x\right),$ где $0 \leqslant \deg{R}\left(x\right) < \deg{Q}\left(x\right).$
Если $Q\left(x\right) = \left(x-x_0\right)$ (линейный многочлен), то его степень — единица. Тогда результатом деления любого многочлена на линейный, будет какой-то новый многочлен степени на единицу меньше, и остаток — многочлен нулевой степени (любое число в степени $0\ -$ это $1$). Следовательно, остатком всегда будет просто число. Именно его мы ищем в схеме Горнера в конце каждой строки.
Дополнительные примеры решения задач
-
Разложить многочлен $P_6(x) = x^6+6x^5+3x^4-28x^3-9x^2+54x-27$ по степеням $\left(x-1\right).$
РешениеОтвет будет выглядеть как формула Тейлора: $P\left(x\right) = h_n\left(x-x_0\right)^n+ h_{n-1}\left(x-x_0\right)^{n-1} + h_{n-2}\left(x-x_0\right)^{n-2} + \ldots + \\ + h_{2}\left(x-x_0\right)^2 + h_{1}\left(x-x_0\right) + h_0.$
Общий вид схемы Горнера для решения задачи:
$a_n$ $a_{n-1}$ $a_{n-2}$ $\ldots$ $a_2$ $a_1$ $a_0$ $x_0$ $b_{n-1}$ $b_{n-2}$ $b_{n-3}$ $\ldots$ $b_1$ $b_0$ $h_0$ $x_0$ $с_{n-1}$ $с_{n-2}$ $с_{n-3}$ $\ldots$ $с_1$ $h_1$ $x_0$ $d_{n-1}$ $d_{n-2}$ $d_{n-3}$ $\ldots$ $h_2$ $\ldots$ $\ldots$ $\ldots$ $\ldots$ $\mathinner{\mkern2mu\raise1pt\hbox{.}\mkern2mu \raise4pt\hbox{.}\mkern2mu\raise7pt\hbox{.}\mkern1mu}$ $x_0$ $f_{n-1}$ $f_{n-2}$ $h_{n-2}$ $x_0$ $g_{n-1}$ $h_{n-1}$ $x_0$ $h_n$ $a_n = b_{n-1} = c_{n-1} = d_{n-1} = \ldots = f_{n-1} = g_{n-1} = h_n.$
$1$ $6$ $3$ $-28$ $-9$ $54$ $-27$ $1$ $1$ $7$ $10$ $-18$ $-27$ $27$ $0$ $1$ $1$ $8$ $18$ $0$ $-27$ $0$ $1$ $1$ $9$ $27$ $27$ $0$ $1$ $1$ $10$ $37$ $64$ $1$ $1$ $11$ $48$ $1$ $1$ $12$ $1$ $1$ Ответ: $P_6\left(x\right)=64\left(x-1\right)^3+48\left(x-1\right)^4+12\left(x-1\right)^5+\left(x-1\right)^6.$
[свернуть] -
Найти все рациональные корни многочлена $P_7\left(x\right) = 9x^7+3x^6-23x^5+4x^4-5x^3+23x^2-13x+2.$
РешениеВ таких заданиях всегда в первую очередь проверяются корни $\pm 1$ и их кратность. Получается разложение $P\left(x\right) = \left(x-1\right)^{k}\left(x+1\right)^{l}g\left(x\right),$ где $k\ — $ кратность корня $1,$ $l\ $ кратность корня $-1,$ $g\left(x\right) = b_{m}x^m + b_{m-1}x^{m-1} + \ldots + b_{1}x + b_0$ $\left(m = n-k-l\right).$ Числа $\pm 1$ не являются корнями $g\left(x\right)$.
Введём $x_0=\displaystyle\frac{s}{t},$ где $s \in \mathcal{S},\ t \in \mathcal{T},\ x_0 \in \mathcal{X},\ \mathcal{S}\ — $ множество всех делителей $a_0,$ $\mathcal{T}\ — $ множество всех положительных делителей $a_n,$ $\mathcal{X}\ — $ множество всех дробей, которые потенциально являются корнями.
Отбор потенциальных корней (кроме $\pm 1$) приводит к множествам: $$\mathcal{S} = \big\{s \in \mathbb{Z} : s|b_0\big\},\ \mathcal{T} = \big\{t \in \mathbb{Z} : \left(t|b_m \right)\wedge\left(t>0 \right)\big\},$$ $$\mathcal{X} = \bigg\{\displaystyle\frac{s}{t} \in \mathbb{Q} : s \in \mathcal{S},\ t \in \mathcal{T}\bigg\}.$$ Их формирование будет происходить уже для $g\left(x\right).$
Сначала проверим по Горнеру, являются ли $\pm 1$ корнями $P_7\left(x\right).$
$9$ $3$ $-23$ $4$ $-5$ $23$ $-13$ $2$ $1$ $9$ $12$ $-11$ $-7$ $-12$ $11$ $-2$ $0$ $1$ $9$ $21$ $10$ $3$ $-9$ $2$ $0$ $1$ $9$ $30$ $40$ $43$ $34$ $36$ $-1$ $9$ $12$ $-2$ $5$ $-14$ $16$ По таблице видно, что $x_0=1\ — $ корень второй кратности, а $x_0=-1$ корнем не является. Получаем разложение: $$P_7\left(x\right) = \left(x-1\right)^{2}g\left(x\right),$$ $$g\left(x\right) = 9x^5+21x^4+10x^3+3x^2-9x+2.$$Также мы определили значения $g\left(1\right) = 36$ и $g\left(-1\right) = 16.$
Для свободного члена $b_0 = 2$ формируем $\mathcal{S}\ — $ множество всех его целых делителей, а для $b_m = 9$ формируем $\mathcal{T}\ — $ множество всех его натуральных делителей. \begin{eqnarray*}\mathcal{S} = \{2;\ -2;\ 1;\ -1\},\ \mathcal{T} = \{9;\ 3;\ 1\}. \end{eqnarray*}
Формируем множество $\mathcal{X},$ которое состоит из всех вариаций $x_0 = \displaystyle\frac{s}{t},$ где $s \in \mathcal{S},$ а $t \in \mathcal{T}.$ Все полученные числа записываем дробями: $$\mathcal{X} = \bigg\{\displaystyle\frac29;\ \displaystyle\frac23;\ \displaystyle\frac21;\ \displaystyle\frac{-2}9;\ \displaystyle\frac{-2}3;\ \displaystyle\frac{-2}1;\ \displaystyle\frac19;\ \displaystyle\frac13;\ \displaystyle\frac11;\ \displaystyle\frac{-1}9;\ \displaystyle\frac{-1}3;\ \displaystyle\frac{-1}1\bigg\}.$$
Сразу вычеркиваем дроби со значениями $\pm 1.$ То что остается, проверяем на двух тестах:
- $t-s|g \left(1 \right);$
- $t+s|g \left(-1 \right).$
Все тесты проходят дроби: $$\mathcal{X}^\prime = \bigg\{-2;\ \displaystyle\frac13;\ \displaystyle-\frac{1}3\bigg\}.$$
Теперь, каждое из этих чисел проверим с помощью алгоритма Горнера.
$9$ $21$ $10$ $3$ $-9$ $2$ $-2$ $9$ $3$ $4$ $-5$ $1$ $0$ $-2$ $9$ $-15$ $34$ $-73$ $-145$ $\displaystyle\frac13$ $9$ $6$ $6$ $-3$ $0$ $\displaystyle\frac13$ $9$ $9$ $9$ $0$ $\displaystyle\frac13$ $9$ $12$ $13$ $\displaystyle-\frac13$ $9$ $6$ $7$ Нам подходят строки с нулевым остатком. Запишем получившееся разложение: $g\left(x\right) = \left(x-\displaystyle\frac13\right)^2\left(x+2\right)\left(9x^2+9x+9\right) = \\ = 9\left(x-\displaystyle\frac13\right)^2\left(x+2\right)\left(x^2+x+1\right).$
У нас появился квадратный трехчлен, который может дать нам новые корни. Однако у него отрицательный дискриминант, следовательно, корней больше нет.
Ответ: корни $P_7\left(x\right):\ 1;\ -2;\ \displaystyle\frac13.$
[свернуть]
Алгоритм Горнера
Тест на проверку знаний по теме «Алгоритм Горнера»
Смотрите также
- Алгебра: Теоремы и алгоритмы: учеб. пособие / Н. И. Яцкин. — Иваново: Иван. гос. ун-т, 2006. — 506с. (c.383-394, 501-503)
- Основы численных методов: Учебник для вузов/В.М.Вержбицкий. — М.: Высш. шк., 2002. — 840c. (с.272-275)
- Личный конспект, составленный на основе лекций Белозерова Г.С.