Processing math: 100%

Метка: деление многочленов

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

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

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

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

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

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

Пусть нам нужно найти корни многочлена P(x), то есть решить уравнение P(x)=0. P(x) представим в виде: n∑i=0aixi=anxn+an−1xn−1+…+ a1x+a0. Решение может осуществляться методами, которые используют производные (если нам нужно найти только действительные корни), а также любыми итерационными способами. Последний требует многократного вычисления значений многочлена.

По следствию из теоремы Безу, многочлен P(x) можно представить в виде: P(x)=(x−x0)Q(x)+R(x), где Q(x) — результат деления P(x) на (x−x0), R(x) — остаток от этого деления. Обозначим Q(x) как bn−1xn−1+bn−2xn−2+…+b0. Перепишем наш многочлен: anxn+an−1xn−1+…+a1x+a0⏟P(x)≡≡(x−x0)(bn−1xn−1+bn−2xn−2+…+b0)⏟Q(x)+R(x). Для того чтобы вычислить значения многочлена, нам необходимо при заданном x=x0 найти степени xk0, (k=¯1,n), результаты умножить на коэффициенты (bn−1,bn−2,…,b0), а получившееся сложить. Однако, чтобы ускорить процесс и вдвое сократить количество умножений, можно воспользоваться алгоритмом Горнера. Выведем его.

Алгоритм берет свое начало из теоремы Безу, которая звучит так: если многочлен P(x) разделить на двучлен (x−x0), то остаток от этого деления будет равен значению P(x) на элементе x0, т.е. (остаток)R(x)=P(x0).

В тождестве (1) умножим (x−x0) на Q(x). Получаем anxn+an−1xn−1+…+a1x+a0≡≡bn−1xn+bn−2xn−1+…+b0x−−x0bn−1xn−1−x0bn−2xn−2−…−x0b0+R(x). Теперь приравняем коэффициенты при одинаковых степенях x: bn−1=an; bn−2=an−1+x0bn−1; …; R(x)=a0+x0b0. Приходим к исходному: R(x)=P(x0). Результаты оформим в виде таблицы:

an an−1 … a0
x0 bn−1 bn−2 … R(x)

Эта таблица и есть схемой Горнера.

Замечание: помимо значения остатка R(x), алгоритм дает нам Q(x) (неполное частное). Также, если остаток R(x)=0, то x0— корень многочлена P(x).

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

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

  1. Разделить многочлен P5(x)=x5−8x4+7x3−4x2+16x+24 на (x−2).
    Решение
  2. Определить кратность корня x0=1 многочлена P5(x)=x5−8x3+14x2−9x+2.
    Решение
  3. При каких значениях A и B многочлен P4(x)=Ax4+Bx2+1 делится на (x−1)2?
    Решение
  4. Дан многочлен P4(x)=x4−(2+i)x3−(3+2i)x+5 над полем \usepackageamsfontsC. Разделить его с остатком на (x−x0), где x0=1−i, попутно вычислив P4(x0).
    Решение

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

После ознакомления с примерами решения задач, можно приступить к изучению данного вопроса. Представим многочлен уже привычным нам образом P(x)=anxn+an−1xn−1+…+a1x+a0. Сделаем самое очевидное действие — вынесем x за скобки: x(anxn−1+an−1xn−2+…+a1)+a0. Если мы повторим это действие n−1 раз, то получим x(x(x…⏟n−1(anx+an−1)+…)+a1)+a0. Алгоритм Горнера работает вне зависимости от того, какая степень у многочлена — схема универсальна. Посмотрим на примере. P7(x)=x7+5x6−2x5−x4+3x2−8x+11==x(x6+5x5−2x4−x3+3x−8)+11==x(x(x5+5x4−2x3−x2+3)−8)+11==x(x(x(x4+5x3−2x2−x+0)+3)−8)+11==x(x(x(x(x3+5x2−2x−1)+0)+3)−8)+11==x(x(x(x(x(x2+5x−2)−1)+0)+3)−8)+11==x(x(x(x(x(x⏟(n−1)=(7−1)=6(x+5)−2)−1)+0)+3)−8)+11==x(x(x(x(x(x((1⋅x)+5)−2)−1)+0)+3)−8)+11. Отсюда видим, для того чтобы посчитать выражение (2), мы должны 1 (коэффициент перед x7) умножить на x, результат прибавить к 5 (коэффициент перед x6), опять умножить на x и т.д. То есть мы делаем все то, что и в схеме Горнера.

Почему разложение P(x)=(x−x0)Q(x)+R(x) — верно? Начнем с арифметики. Возьмем какое-то натуральное число a. Как гласит нам основная теорема арифметики, его всегда можно представить в виде произведения двух других чисел с остатком, то есть a=s⋅q+r. Например, 7=2⋅3+1, 8=4⋅2+0. Разложение такого типа единственно, причем 0⩽r<s.

Тоже самое происходит и с многочленами. Допустим, мы хотим разделить многочлен P(x) на Q(x) с остатком. Значит P(x) можно записать как P(x)=S(x)⋅Q(x)+R(x), где 0⩽degR(x)<degQ(x).

Если Q(x)=(x−x0) (линейный многочлен), то его степень — единица. Тогда результатом деления любого многочлена на линейный, будет какой-то новый многочлен степени на единицу меньше, и остаток — многочлен нулевой степени (любое число в степени 0 − это 1). Следовательно, остатком всегда будет просто число. Именно его мы ищем в схеме Горнера в конце каждой строки.

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

  1. Разложить многочлен P6(x)=x6+6x5+3x4−28x3−9x2+54x−27 по степеням (x−1).
    Решение
  2. Найти все рациональные корни многочлена P7(x)=9x7+3x6−23x5+4x4−5x3+23x2−13x+2.
    Решение

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

Тест на проверку знаний по теме «Алгоритм Горнера»

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

  1. Алгебра: Теоремы и алгоритмы: учеб. пособие / Н. И. Яцкин. — Иваново: Иван. гос. ун-т, 2006. — 506с. (c.383-394, 501-503)
  2. Основы численных методов: Учебник для вузов/В.М.Вержбицкий. — М.: Высш. шк., 2002. — 840c. (с.272-275)
  3. Личный конспект, составленный на основе лекций Белозерова Г.С.