Схема Горнера (или метод Горнера, правило Горнера) — это эффективный алгоритм для вычисления значения многочлена, а также для деления многочлена на двучлен вида x−c.
Метод минимизирует количество арифметических операций (прежде всего умножения), что делает его особенно полезным при ручных вычислениях и программировании.
Метод был описан Уильямом Джорджем Горнером в XIX веке, но идеи, лежащие в основе метода, встречались в работах более ранних математиков.
Формулировка схемы Горнера
Пошаговое выполнение
- Начать с коэффициента старшего члена (например, an).
- Умножить его на заданное значение x0.
- Сложить результат с ближайшим слева коэффициентом (an−1), список идет до a0.
- Повторять операцию до конца списка коэффициентов (всего n раз).
Пример 1. Вычисление значения многочлена при x=2
Найти значение многочлена f(2):
f(x) = x^4 + 3x^3 + 5x^2 + 7x + 9
Способ 1. Подстановка
\begin{aligned}
f(2) &= 2^4 + 3 \cdot 2^3 + 5 \cdot 2^2 + 7 \cdot 2 + 9 \\
&= 16 + 3 \cdot 8 + 5 \cdot 4 + 14 + 9 \\
&= 16 + 24 + 20 + 14 + 9 \\
&= 40 + 20 + 14 + 9 \\
&= 60 + 14 + 9 \\
&= 74 + 9 = 83
\end{aligned}Способ 2. Схема Горнера
\begin{array}{c|ccccc}
& 1 & 3 & 5 & 7 & 9 \\
x=2 & \downarrow & 2 & 10 & 30 & 74 \\
\hline
& 1 & 5 & 15 & 37 & \mathbf{83} \\
\end{array}1 \cdot 2 = 2, 2 + 3 = 5\\ 5 \cdot 2 = 10, 10 + 5 = 15\\ 5 \cdot 2 = 30, 30 + 7 = 37\\ 37 \cdot 2 = 74, 74 + 9 = 83\\
Ответ:
f(2) = 83
Визуализация (скобочная форма)
f(x)=9+x(7+x(5+x(3+x(1))))
Пример 2. Деление многочлена на x−1
Разделить многочлен P(x) на многочлен x−1, используя схему Горнера.
P(x) = 7x^4 - x^3 + 5x^2 - 11
Записываем коэффициенты P(x) с учётом нулевого коэффициента при x
7x^4 - 1x^3 + 5x^2 + 0x - 11
Запишем коэффициенты в верхний ряд и подставим x0=1:
\begin{array}{c|ccccc}
& 7 & -1 & 5 & 0 & -11 \\
1 & \downarrow & 7 & 6 & 11 & 11 \\
\hline
& 7 & 6 & 11 & 11 & 0 \\
\end{array}Последнее значение b0=0 — остаток от деления.
P(x) = (x - 1)(7x^3 + 6x^2 + 11x + 11)
Ответ: Многочлен делится на x−1 без остатка. Q(x)=7x3+6x2+11x+11.
Пример 3. Проверка корня многочлена
Проверим, является ли x=2 корнем многочлена P(x):
P(x) = 2x^3 - 3x^2 - 6x + 5
Способ 1: Непосредственная подстановка
\begin{aligned}
P(2) &= 2 \cdot 2^3 - 3 \cdot 2^2 - 6 \cdot 2 + 5 \\
&= 2 \cdot 8 - 3 \cdot 4 - 12 + 5 \\
&= 16 - 12 - 12 + 5 \\
&= 4 - 12 + 5 = -8 + 5 = -3 \neq 0
\end{aligned}Способ 2: Схема Горнера
\begin{array}{c|cccc}
& 2 & -3 & -6 & 5 \\
2 & \downarrow & 4 & 2 & -8 \\
\hline
& 2 & 1 & -4 & -3 \\
\end{array}Остаток b0=−3≠0, значит x=2 не является корнем.
Пример 4. Разложение многочлена на множители
Разложить на множители многочлен Р(х), зная что x = 2 — корень.
P(x) = x^3 - 3x^2 - 4x + 12
Решение
\begin{array}{c|cccc}
& 1 & -3 & -4 & 12 \\
2 & \downarrow & 2 & -2 & -12 \\
\hline
& 1 & -1 & -6 & 0 \\
\end{array}Ответ
P(x) = (x - 2)(x^2 - x - 6) = (x - 2)(x - 3)(x + 2)
Пример 5. Нахождение нескольких корней
Найти все корни P(x)
P(x) = x^3 - 6x^2 + 11x - 6
Решение
\begin{array}{c|cccc}
& 1 & -6 & 11 & -6 \\
1 & \downarrow & 1 & -5 & 6 \\
\hline
& 1 & -5 & 6 & 0 \\
\end{array}Получаем
P(x) = (x - 1)(x^2 - 5x + 6) = (x - 1)(x - 2)(x - 3)
Ответ: 1, 2, 3
Пример 6. Нахождение корней многочлена 5-й степени
Важные моменты для многочлена 5-й степени:
- Максимум 5 корней (с учётом кратности).
- Рациональные корни — только среди делителей p/q : все делители свободного члена a0 → это возможные числители p , все делители старшего коэффициента an → это возможные знаменатели q .Если старший коэффициент an=1 (многочлен приведённый), то q=±1 , и все рациональные корни — целые числа, являющиеся делителями a0 .
- Если не нашли ни одного рационального корня — возможно, все корни иррациональные или комплексные. Тогда схема Горнера не поможет найти их напрямую.
Найти все корни многочлена:
P(x) = x^5 - 5x^4 + 5x^3 + 5x^2 - 6x
Шаг 1. Вынесение общего множителя
P(x) = x(x^4 - 5x^3 + 5x^2 + 5x - 6)
Первый корень: x1 = 0
Шаг 2. Поиск целых корней многочлена 4-й степени
Q(x) = x^4 - 5x^3 + 5x^2 + 5x - 6
Делители свободного члена:
(-6): \pm1, \pm2, \pm3, \pm6 \
Проверяем x = 1
\begin{array}{c|ccccc}
& 1 & -5 & 5 & 5 & -6 \\
1 & \downarrow & 1 & -4 & 1 & 6 \\
\hline
& 1 & -4 & 1 & 6 & 0 \\
\end{array}Остаток 0 ⇒ x 2= 1 — корень
Проверяем x = 2
R(x) = x^3 - 4x^2 + x + 6
\begin{array}{c|cccc}
& 1 & -4 & 1 & 6 \\
2 & \downarrow & 2 & -4 & -6 \\
\hline
& 1 & -2 & -3 & 0 \\
\end{array}Остаток 0 ⇒ x3 = 2 — корень
Проверяем x = 3
S(x) = x^2 - 2x - 3
\begin{array}{c|ccc}
& 1 & -2 & -3 \\
3 & \downarrow & 3 & 3 \\
\hline
& 1 & 1 & 0 \\
\end{array}Остаток 0 ⇒ x4 = 3 — корень
Проверяем x = -1
T(x) = x + 1
\begin{array}{c|cc}
& 1 & 1 \\
-1 & \downarrow & -1 \\
\hline
& 1 & 0 \\
\end{array}Остаток 0 ⇒ x 5= -1 — корень
Шаг 3. Полное разложение
\begin{aligned}
P(x) &= x(x - 1)(x - 2)(x - 3)(x + 1) \\
&= x(x + 1)(x - 1)(x - 2)(x - 3)
\end{aligned}Ответ
\boxed{-1,\ 0,\ 1,\ 2,\ 3}Достаточно было дойти до квадратного уравнения.
Задания
10 заданий на применение схемы Горнера с разным уровнем сложности.
1. Вычисление значения многочлена
Найдите P(3) для многочлена P(x)=2x3−5x2+x−4.
Решение
2. Деление многочлена на двучлен
Разделите P(x)=x4−6x3+11x2−6x на (x−2) с помощью схемы Горнера.
Решение
3. Проверка корня
Является ли x=−1 корнем многочлена P(x)=3x4+2x3−x2+4x+2?
Решение
4. Разложение многочлена
Представьте P(x)=4x3−8x2−11x+15 в виде (x−3)⋅Q(x)+R.
Решение
5. Нахождение коэффициентов
Найдите коэффициенты bi и остаток R при делении P(x)=x5−1 на (x−1).
Решение
6. Многочлен с пропущенными степенями
Вычислите P(−2) для P(x)=2x4−3x2+5x−7 (учтите нулевые коэффициенты).
Решение
7. Двойное применение схемы Горнера
Разделите P(x)=x3−4x2+5x−2 на (x−1) дважды, чтобы убедиться, что x=1 — двойной корень.
Решение
8. Отрицательный корень
Найдите P(−3) для P(x)=2x4+5x3−x2+6.
Решение
9. Многочлен высокой степени
Разделите P(x)=x6−64 на (x−2).
Решение
10. Обратная задача
Многочлен P(x) при делении на (x−4) даёт остаток R=10. Известно, что коэффициенты bi в схеме Горнера: b2=3, b1=2, b0=5. Найдите P(x) (степень 3).
Решение
Дополнительно
Источник: ссылка