Схема (метод) Горнера. Примеры. Разложение многочлена на множители
Пример 1
Пример 2
Пример 3
Пример 4
РАЗЛОЖЕНИЕ МНОГОЧЛЕНА НА МНОЖИТЕЛИ ПО СХЕМЕ ГОРНЕРА
5x5 — 2x4 — 25x3 + 10x2 + 20x — 8
Для начала нужно методом подбора найти один корень. Обычно он является делителем свободного члена. В данном случае делителями числа -8 являются ±1, ±2, ±4, ±8. Начнем их подставлять по-очереди:
1: 5 — 2 — 25 + 10 + 20 — 8 = 0 ⇒ число 1 является корнем многочлена
Мы нашли 1 из корней многочлена. Корнем многочлена является 1, а значит исходный многочлен должен делиться на x — 1. Для того, чтобы выполнить деление многочленов, воспользуемся схемой Горнера:
| 5 | -2 | -25 | 10 | 20 | -8 | |
| 1 |
В верхней строке выставляются коэффициенты исходного многочлена.
В первой ячейке второй строки ставится найденный нами корень 1. Во второй строке пишутся коэффициенты многочлена, который получится в результате деления. Они считаются так:
| Во вторую ячейку второй строки запишем число 5, просто перенеся его из соответствующей ячейки первой строки. | ||||||||||||||
| 1 ∙ 5 — 2 = 3 | ||||||||||||||
| 1 ∙ 3 — 25 = -22 | ||||||||||||||
| 1 ∙ (-22) + 10 = -12 | ||||||||||||||
| 1 ∙ (-12) + 20 = 8 | ||||||||||||||
| 1 ∙ 8 — 8 = 0 |
Последнее число — это остаток от деления.
Если он равен 0, значит мы все верно посчитали.
Таким образом мы исходный многочлен разложили на множители:
5x5 — 2x4 — 25x3 + 10x2 + 20x — 8 = (x — 1)(5x4 + 3x3 — 22x2 — 12x + 8)
Опять ищем корень среди делителей свободного члена. Делителями числа 8 являются ±1, ±2, ±4, ±8.
1: 5 + 3 — 22 — 12 + 8 = -18 ⇒ число 1 не является корнем многочлена
-1: 5 — 3 — 22 + 12 + 8 = 0 ⇒ число -1 является корнем многочлена
Напишем найденный корень в нашу схему Горнера и начнем заполнять пустые ячейки:
| Во вторую ячейку третьей строки запишем число 5, просто перенеся его из соответствующей ячейки второй строки. | |||||||||||||||||||||
| -1 ∙ 5 + 3 = -2 | |||||||||||||||||||||
| -1 ∙ (-2) — 22 = -20 | |||||||||||||||||||||
| -1 ∙ (-20) — 12 = 8 | |||||||||||||||||||||
| -1 ∙ 8 + 8 = 0 |
Таким образом мы исходный многочлен разложили на множители:
5x5 — 2x4 — 25x3 + 10x2 + 20x — 8 = (x — 1)(x + 1)(5x3 — 2x2 — 20x + 8)
Теперь найдем корень многочлена 5x3 — 2x2 — 20x + 8.
Делителями числа 8 являются ±1, ±2, ±4, ±8.
1: 5 — 2 — 20 + 8 = -9 ⇒ число 1 не является корнем многочлена
-1: -5 — 2 + 20 + 8 = 29 ⇒ число -1
не является корнем многочлена2: 5 ∙ 8 — 2 ∙ 4 — 20 ∙ 2 + 8 = 0 ⇒ число 2 является корнем многочлена
| Во вторую ячейку четвертой строки запишем число 5, просто перенеся его из соответствующей ячейки третьей строки. | ||||||||||||||||||||||||||||
| 2 ∙ 5 — 8 = 8 | ||||||||||||||||||||||||||||
| 2 ∙ 8 — 20 = -4 | ||||||||||||||||||||||||||||
| 2 ∙ (-4) + 8 = 0 |
Таким образом мы исходный многочлен разложили на множители:
5x5 — 2x4 — 25x3 + 10x2 + 20x — 8 = (x — 1)(x + 1)(x — 2)(5x2 + 8x — 4)
Многочлен 5x 2 + 8x — 4 тоже можно разложить на множители.
Для этого можно решить квадратное уравнение через дискриминант, а можно поискать корень среди делителей числа -4. Так или иначе, мы придем к выводу, что корнем этого многочлена является число -2
| Во вторую ячейку четвертой строки запишем число 5, просто перенеся его из соответствующей ячейки третьей строки. | |||||||||||||||||||||||||||||||||||
| -2 ∙ 5 + 8 = -2 | |||||||||||||||||||||||||||||||||||
| -2 ∙ (-2) — 4 = 0 |
Таким образом мы исходный многочлен разложили на линейные множители:
5x5 — 2x4 — 25x 3 + 10x2 + 20x — 8 = (x — 1)(x + 1)(x — 2)(x + 2)(5x — 2)
А корнями многочлена являются:
x = ±1; ±2; 0.
{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}
$$
Вторая строка таблицы заполняется постепенно. Второй элемент этой строки (обозначим его $b_0$) равен $a_0$, т.е., по сути, мы просто переносим вниз число $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} $$Следующий элемент второй строки, который мы обозначим как $b_1$, получается по такой формуле: $b_1=a\cdot{b_0}+a_1$:
Далее находим элемент $b_2$ по формуле $b_2=a\cdot{b_1}+a_2$:
$$ \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=a\cdot{b_1}+a_2 & & & & \end{array} $$Аналогично вычисляем и элемент $b_3=a\cdot{b_2}+a_3$:
$$ \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=a\cdot{b_2}+a_3 & & & \end{array} $$Далее находим $b_4$, $b_5$ и так далее.
2}+\normblue{0}\cdot{x}+\normblue{(-11)}\\
$$
Так как мы делим на $x-\normred{1}$, то в первой ячейке второй строки запишем число $\normred{1}$. Таблица, с которой мы будем работать, имеет такой вид:
$$ \begin{array} {c|c|c|c|c|c} & \normblue{5} & \normblue{5} & \normblue{1} & \normblue{0} & \normblue{-11} \\ \hline \normred{1} & & & & & \end{array} $$Начнём заполнять пустые ячейки во второй строке. Во вторую ячейку второй строки запишем число $5$, просто перенеся его вниз из второй ячейки первой строки:
$$ \begin{array} {c|c|c|c|c|c} & \normgreen{5} & 5 & 1 & 0 & -11 \\ \hline 1 & \normgreen{5} & & & & \end{array} $$Следующую ячейку заполним по такому принципу: $\normred{1}\cdot\normgreen{5}+\normpurple{5}=\normblue{10}$:
$$ \begin{array} {c|c|c|c|c|c} & 5 & \normpurple{5} & 1 & 0 & -11 \\ \hline \normred{1} & \normgreen{5} & \normblue{10} & & & \end{array} $$Аналогично заполним и четвертую ячейку второй строки: $\normred{1}\cdot\normgreen{10}+\normpurple{1}=\normblue{11}$:
$$ \begin{array} {c|c|c|c|c|c} & 5 & 5 & \normpurple{1} & 0 & -11 \\ \hline \normred{1} & 5 & \normgreen{10} & \normblue{11} & & \end{array} $$Для пятой ячейки получим: $\normred{1}\cdot\normgreen{11}+\normpurple{0}=\normblue{11}$:
$$ \begin{array} {c|c|c|c|c|c} & 5 & 5 & 1 & \normpurple{0} & -11 \\ \hline \normred{1} & 5 & 10 & \normgreen{11} & \normblue{11} & \end{array} $$И, наконец, для последней, шестой ячейки, имеем: $\normred{1}\cdot\normgreen{11}+\normpurple{(-11)}=\normblue{0}$:
$$ \begin{array} {c|c|c|c|c|c} & 5 & 5 & 1 & 0 & \normpurple{-11} \\ \hline \normred{1} & 5 & 10 & 11 & \normgreen{11} &\normblue{0} \end{array} $$Числа, расположенные во второй строке (между единицей и нулём), есть коэффициенты многочлена, полученного после деления $P(x)$ на $x-1$.
6$) равен единице. В этом случае целочисленные корни многочлена нужно искать среди делителей свободного члена, т.е. среди делителей числа 45. Для заданного многочлена такими корнями могут быть числа $45; \; 15; \; 9; \; 5; \; 3; \; 1$ и $-45; \; -15; \; -9; \; -5; \; -3; \; -1$. Проверим, к примеру, число $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} $$
Как видите, значение многочлена $P(x)$ при $x=1$ равно $192$ (последнее число в второй строке), а не $0$, посему единица не является корнем данного многочлена. Так как проверка для единицы окончилась неудачей, проверим значение $x=-1$. Новую таблицу составлять не будем, а продолжим использование табл. №1, дописав в нее новую (третью) строку. Вторую строку, в которой проверялось значение $1$, выделим красным цветом и в дальнейших рассуждениях использовать её не будем.
2-21x+45$. Проверим еще раз число $-1$:
Проверка окончилась неудачей. Выделим шестую строку красным цветом и попробуем проверить иное число, например, число $3$:
$$ \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 \normred{-1} & \normred{1} & \normred{-2} & \normred{-19} & \normred{64} & & & \\ \hline 3 & 1 & 2 & -15 & 0 & & & \end{array} $$В остатке ноль, посему число $3$ – корень рассматриваемого многочлена.
2+2x-15\right)
\end{equation}
$$
Проверим ещё раз число $3$:
$$ \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 \normred{-1} & \normred{1} & \normred{-2} & \normred{-19} & \normred{64} & & & \\ \hline 3 & 1 & 2 & -15 & 0 & & & \\ \hline 3 & 1 & 5 & 0 & & & & \end{array} $$Полученный результат можно записать так (это продолжение равенства (6)):
$$ \begin{equation} P(x)=(x+1)^3(x-3)\left(x^2+2x-15\right) =(x+1)^3(x-3)(x-3)(x+5) =(x+1)^3(x-3)^2(x+5) \end{equation} $$Из последней скобки видно, что число $-5$ также является корнем данного многочлена.
2(x+5)$$
Числа $-1$, $3$, $-5$ – корни данного многочлена. Причем, так как скобка $(x+1)$ в третьей степени, то $-1$ – корень третьего порядка; так как скобка $(x-3)$ во второй степени, то $3$ – корень второго порядка; так как скобка $(x+5)$ в первой степени, то $x=-5$ – корень первого порядка (простой корень).
Вообще, обычно оформление таких примеров состоит из таблицы, в которой перебираются возможные варианты корней, и ответа:
$$ \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 \normred{-1} & \normred{1} & \normred{-2} & \normred{-19} & \normred{64} & & & \\ \hline 3 & 1 & 2 & -15 & 0 & & & \\ \hline 3 & 1 & 5 & 0 & & & & \end{array} $$Из таблицы следует вывод, полученный нами ранее с подробным решением:
$$ P(x)=(x+1)^3(x-3)\left(x^2+2x-15\right)=(x+1)^3(x-3)^2(x+5)$$Ответ: $-1$, $3$, $-5$.
2-10\right)
$$
Конечно, данный метод подбора малоэффективен в общем случае, когда корни не являются целыми числами, но для целочисленных корней метод довольно-таки неплох.
Вернуться к списку тем
Задать вопрос на форуме
Записаться на занятия
Онлайн-занятия по высшей математике
Метод Хорнера — Ximera
Теоретически легко вычислить численное значение многочлен путем вычисления . Вам нужно вычислить большие мощности, чтобы сделать этот.Существует алгоритм, сокращающий вычисление для произвольных многочленов и числа к более простым умножениям и добавлениям. Алгоритм также имеет особый побочный эффект, заключающийся в получении частного от деления на . Этот алгоритм известен как метод Хорнера . Мы объясняем это здесь с помощью пример.
Разделить на . Вызов многочлена . Воспользуемся методом Хорнера для вычисления значения в точке ,
и мы получаем частное бесплатно. Вы можете, конечно, также рассчитать с вашим
калькулятор, но тогда вам все равно придется использовать деление Горнера или Евклидово деление, если вам нужно
частное.
Стартовая схема выглядит так
где коэффициенты находятся в верхней строке. Теперь мы опускаем первый коэффициент (т.е. ), умножьте его на слева и запишите результат во второй строке под второй коэффициент (т.е. под ):
Складываем и вместе, записываем результат внизу и умножаем на лево и снова напишите результат во второй строке под , а затем добавьте к этому :
Снова умножаем нижнее на левое, пишем произведение под, складываем и получить номер в правом нижнем углу:
Теперь схема завершена, и мы можем доказать, что самое правое число в дно всегда является числовым значением многочлена в точке , и что остальные числа в нижней строке всегда являются коэффициентами частного деленное на .
Таким образом, частное равно , а остаток равен , или
В качестве примера евклидова деления мы разделили на . Мы также можем выполнить это деление по методу Горнера:Таким образом: .
Обратите внимание, что остаток, таким образом, также представляет собой числовое значение дивиденда для , потому что
Найдите все делители .
Обратите внимание, что это та же самая задача, что и «разложить этот многочлен на множители».
Кандидаты в делители формы , с целым числом, должны быть делителями . А Возможный способ решить это упражнение — проверить для всех целых делителей числа 24, являются ли их числовое значение равно нулю. Если вы начнете с самого маленького, вы сразу повезло, потому что , и поэтому является делителем . Теперь мы можем искать численные значения делителей и , но легче вычислить с помощью Хорнера что
и поэтому . Повторим вопрос для многочлена . Окончательный результат будет. Это очень четко и полно объяснено в следующем видео, в котором Хорнер правило также объясняется в начале.
В разделе о линейных делителях мы учитывали .Поскольку является делителем .
Рассчитываем частное по методу Хорнера. 9к$
или
f(x) = a 0 + a 1 x + a 2 x 2 + .
.. + a n x n
Где a k — действительные числа, представляющие полиномиальные коэффициенты, а
x k — полиномиальные переменные.
Говорят, что приведенный выше полином имеет степень n th , т. е. deg(f(x)) = n , где n представляет наивысший переменный показатель степени.
Правило Хорнера для полиномиального деления — это алгоритм, используемый для упрощения процесса вычисления многочлена f(x) при некотором значении x = x 0 делением полинома на мономы (многочлены 1-й -й степени). Каждый моном включает максимум один процесс умножения и один процесс сложения. Результат, полученный от одного монома, добавляется к результату, полученному от следующего монома, и так далее в режиме накопительного сложения. Этот процесс деления также известен как синтетическое деление.
Чтобы пояснить вышеизложенное, давайте перепишем полином в его расширенной форме;
f(x 0 ) = a 0 + a 1 x 0 + a 2 x 0 2 + .
.. + a н х 0 н
Это также может быть записано как:
f(x 0 ) = a 0 + x 0 (a 1 + x 0 (a 2 + x 0 ( 3 + … + (а n-1 + a n x 0 )….)
Алгоритм, предложенный этим правилом, основан на оценке мономов, образованных выше, начиная с монома в самой внутренней скобке и продвигаясь к оценке мономов во внешней скобке.
Алгоритм выполняется по следующим шагам:
1. Положим k = n
2. Пусть b k = a k
3. Пусть b k — 1 = a k — 1 + b k x 0
4. Пусть k = k — 1
5. Если k ≥ 0 , то перейти к шагу 3
Иначе Конец
Этот алгоритм также можно представить графически, рассмотрев полином степени 5 , определяемый следующим образом:
f(x) = а 0 + а 1 х + а 2 х 2 + а 3 х 3 + а 4 х 4 + 5 x 5
который можно оценить в x = x 0 , переставив его как:
f(x 0 ) = a 0 + x 0 (a 1 + x 0 (a 2 + x 0 ( а 3 + х 0 (а 4 + а 5 х 0 ))))
Другой способ представить результаты с использованием этого алгоритма — использовать таблицу, приведенную ниже:
| К | 5 | 4 | 3 | 2 | 1 | 0 |
| б 5 = а 5 | б 4 = а 4 + х 0 б 5 | б 3 = а 3 + х 0 б 4 | б 2 = а 2 + х 0 б 3 | б 1 = а 1 + х 0 б 2 | б 0 = а 0 + х 0 б 1 |
Пример: Вычисление многочлена f(x) = x 4 + 3x 3 + 5x 2 + 7x + 9 при x = 2
Решение:
Так как полином имеет степень 4 , то n = 4
| К | 4 | 3 | 2 | 1 | 0 |
| Шаг | б 4 = 1 | б 3 = 3 + 2 * 1 | б 2 = 5 + 2 * 5 | б 1 = 7 + 2 * 15 | б 0 = 9 + 2 * 37 |
| Результат | 1 | 5 | 15 | 37 | 83 |
Следовательно, f(2) = 83.
Почему мы должны это делать?
Обычно при вычислении полинома с определенным значением мы привыкли подставлять это значение в полином и выполнять вычисления. Для этого мы также можем использовать или разработать приложение для математических вычислений, что необходимо, когда мы имеем дело со сложными полиномами высокой степени.
То, как компьютер обрабатывает проблему, зависит главным образом от того, как вы, как программист, описываете ее компьютеру. Вы можете разработать приложение для решения полинома прямой подстановкой или синтетическим делением по правилу Горнера. Единственная разница между этими двумя подходами заключается в скорости, с которой компьютер решит задачу в любом случае.
Преимущество правила Горнера состоит в том, что оно уменьшает количество операций умножения. Зная, что время обработки компьютером одного процесса умножения в 5-20 раз превышает время обработки процесса сложения, вы можете сказать, что разработка вашего приложения для вычисления полинома с использованием правила Хорнера значительно улучшит время выполнения, затрачиваемое компьютером.