Алгоритм Горнера

Для того чтобы понять принцип работы алгоритма (который также называют «схемой Горнера» или «методом Горнера»), разберемся, что с его помощью можно делать, откуда берется этот алгоритм, как именно и почему он работает.

Алгоритм Горнера помогает решать две алгебраические задачи:

Решение уравнений высших степеней;
Работа с многочленами.

Все это можно делать и без использования алгоритма, однако его преимущество заключается в скорости.

Выведем схему Горнера

Пусть нам нужно найти корни многочлена $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).$

Далее, с помощью примеров, рассмотрим, как алгоритм работает на практике.

Решение задач на делимость многочленов. Применение алгоритма Горнера

Определим ключевые понятие для решения задач.

Определение 1

$f(x), g(x) \in \mathbb{P} { [ x ] },\quad g(x) \neq 0$ . $f(x)$ делится на $g(x)$
$\Big( f(x)$ $\vdots$ $g(x)\Big)$ , если $f$ представимо в следующем виде: $f(x)=g(x) \cdot h(x),\quad где \quad h(x) \in \mathbb{P} [x].$

Определение 2

Пусть $f(x), g(x),h(x) \in \mathbb{P} { [ x ] }$ , если $h(x)$ $|$ $f(x)$ и $h(x)$ $|$ $g(x)$ , то $h(x)$ называется общим делителем $f(x)$ , $g(x)$ .

Алгоритм Горнера

Алгоритм вычисления значения многочлена, записанного в виде суммы мономов, при заданном значении переменной.
$f(x)=a_{n}x^n+a_{n-1}x^{n-1}+\dots+a_1x+a_0$
$q(x)=b_{n-1}x^{n-1}+b_{n-2}x^{n-2}+\dots+b_1x+b_0$
$f(x)=(x-\alpha)q(x)+f(\alpha)$
Умножаем $q(x)$ на $x-\alpha$ и приравниваем:

	$\large f(x)=(x-\alpha)q(x)+f(\alpha)$
$\large n$	$\large a_n=b_{n-1}$	$\large b_{n-1}=a_n$
$\large n-1$	$\large a_{n-1}=b_{n-2}-\alpha b_{n-1}$	$\large b_{n-2}=a_{n-1}+\alpha b_{n-1}$
$\large n-2$	$\large a_{n-2}=b_{n-3}-\alpha b_{n-2}$	$\large b_{n-3}=a_{n-2}+\alpha b_{n_2}$
$\large \vdots$	$\large \dots$	$\large \dots$
$\large 1$	$\large a_1=b_0-\alpha b_1$	$\large b_0=a_1+\alpha b_1$
$\large 0$	$\large a_0=f(\alpha)-\alpha b_0$	$\large f(\alpha)=a_0+\alpha b_0$

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

	$\large a_n$	$\large a_{n-1}$	$\large a_{n-2}$	$\large \dots$	$\large a_1$	$\large a_0$
$\large \alpha$	$\large b_{n-1}$	$\large b_{n-2}$	$\large b_{n-3}$	$\large \dots$	$\large b_0$	$\large f(\alpha)$

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

Задача 1

Указать делит ли многочлен $g(x)$ многочлен $f(x).$

Алгоритм:

Делим первый элемент делимого на старший элемент делителя, помещаем результат под чертой.
Умножаем делитель на полученный выше результат деления. Записываем результат под первыми двумя элементами делимого.
Вычитаем полученный после умножения многочлен из делимого, записываем результат под чертой.
Если степень полученного многочлена в пункте 3 меньше степени делителя – завершаем процесс, в противном случае – перейти к пункту 5.
Повторяем предыдущие 4 шага, используя в качестве делимого многочлен, записанный под чертой.

$\large f(x)=x^3-12x^2-42 \quad g(x)=x-3$

$\large x^3$	$\large —$	$\large 12x^2$	$\large +$	$\large 0x$	$\large -$	$\large 42$	$\large x$	$\large -$	$\large 3$	$\large$	$\large$
$\large x^3$	$\Large -$	$\large 3x^2$	$\large$	$\large$	$\large$	$\large$	$\large x^2$	$\large -$	$\large 9x$	$\large -$	$\large 27$
$\large$	$\large -$	$\large 9x^2$	$\large +$	$\large 0x$	$\large -$	$\large 42$	$\large$	$\large$	$\large$	$\large$	$\large$
$\large$	$\large -$	$\large 9x^2$	$\large +$	$\large 27x$	$\large$	$\large$	$\large$	$\large$	$\large$	$\large$	$\large$
$\large$	$\large$	$\large$	$\large -$	$\large 27x$	$\large -$	$\large 42$	$\large$	$\large$	$\large$	$\large$	$\large$
$\large$	$\large$	$\large$	$\large -$	$\large 27x$	$\large +$	$\large 81$	$\large$	$\large$	$\large$	$\large$	$\large$
$\large$	$\large$	$\large$	$\large$	$\large$	$\large -$	$\large 123$	$\large$	$\large$	$\large$	$\large$	$\large$

Ответ: $r(x)=-123 \Rightarrow g(x)$ не делит $f(x)$ .

$\large f(x)=x^2+3x+2 \quad g(x)=x+2$

$\large x^2$	$\large +$	$\large 3x$	$\large +$	$\large 2$	$\large x$	$\large +$	$\large2$
$\large x^2$	$\large +$	$\large x$			$\large x$	$\large +$	$\large 1$
		$\large 2x$	$\large +$	$\large 2$
		$\large 2x$	$\large +$	$\large 2$
				$\Large 0$

Ответ: $r(x)=0 \Rightarrow g(x)$ делит $f(x)$ .

Задача 2

Найти частное и остаток от деления на линейный двучлен используя метод Горнера.
$\large f(x)=2x^4-3x^3-x^2+4x+13$ $\large Линейный \quad двучлен:\quad x-1$
Применим предложенный выше алгоритм:

	$\large a_4=2$	$\large a_3=-3$	$\large a_2=-1$	$\large a_1=4$	$\large a_0=13$
$\large \alpha=1$	$\large b_3=a_4$ $b_3=2$	$\large b_2=a_3+\alpha b_3$ $b_2=-1$	$\large b_1=a_2+\alpha b_2$ $b_1=-2$	$\large b_0=a_1+\alpha b_1$ $b_0=2$	$\large f(\alpha)=15$

Ответ: $q(x)=2x^3-x^2-2x+2, \quad f(\alpha)=15$ .

Список литературы:

Конспект по линейной алгебре и геометрии. 1 курс. Геннадий Сергеевич Белозеров. Глава 3.
Сканави М. И. Элементарная математика. — 2-е изд., перераб. и доп. — М.: Наука, 1972. — 142—147 c.
Волков Е. А. § 2. Вычисление значений многочлена. Схема Горнера — Учеб. пособие для вузов. — 2-е изд., испр. — М.: Наука, 1987. — 248 с.

Тест на тему: Решение задач на делимость многочленов. Применение алгоритма Горнера.

	$1$	$-8$	$7$	$-4$	$16$	$24$
$2$	$1$

	$1$	$-8$	$7$	$-4$	$16$	$24$
$2$	$1$	$-6$

	$1$	$-8$	$7$	$-4$	$16$	$24$
$2$	$1$	$-6$	$-5$	$-14$	$-12$	$0$

	$1$	$0$	$-8$	$14$	$-9$	$2$
$1$	$1$	$1$	$-7$	$7$	$-2$	$0$

	$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$

Метка: Алгоритм Горнера

Алгоритм Горнера

Выведем схему Горнера

Примеры решения задач

Почему алгоритм Горнера работает?

Дополнительные примеры решения задач

Алгоритм Горнера

Навигация (только номера заданий)

Информация

Результаты

Рубрики

1.

Элементы сортировки

2.

3.

4.

5.

6.

Смотрите также

Решение задач на делимость многочленов. Применение алгоритма Горнера

Определение 1

Определение 2

Алгоритм Горнера

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

Задача 1

Алгоритм:

Задача 2

Список литературы:

Навигация (только номера заданий)

Информация

Результаты

Рубрики

1.

2.

3.

4.

5.

Элементы сортировки

6.

	$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$

	$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$

	$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$

	$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$

	$1$	$-2-i$	$0$	$-3-2i$	$5$
$1-i$	$1$	$-1-2i$	$-3-i$	$-7$	$2-7i$

Средний результат
Ваш результат

Средний результат
Ваш результат