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

Разделить с остатком многочлен f (x) на ненулевой многочлен g (x) — это значит представить f (x) в виде:

f (x) =g (x) s (x) +r (x),.

где s (x) и r (x) -многочлены и либо r (x) =0, либо ст. r (x) < ст. g (x). S (x) назовем неполным частным, а r (x) — остатком при делении f (x) на g (x).

Неполное частное при делении можно найти с помощью простого правила, называемого схемой Горнера, которое, кстати, позволяет найти и остаток. [4, c. 29].

Пусть:

f (x) =a_nxⁿ+a_n-1x^n-1+ … +a₁x+a_0, a_n?0.

— многочлен n-й степени. При делении его на x — c мы получим неполное частное s (x) и остаток r, т. е.:

f (x) = (x — c) s (x) + r.

Так как ст. f (x) = n, а ст. (x — c) = 1, то:

ст. s (x) = n — 1, т. е. s (x) = b_n-1x^n-1 + b_n-2x^n-2 + … + b₁x+ b₀, b_n-1? 0.

Таким образом, имеем равенство:

a_nxⁿ+a_n-1x^n-1+ … +a₁x+a₀ = (x — c) (b_n-1x^n-1+b_n-2x^n-2+ …+b₁x+b₀) +r.

Многочлены, стоящие в левой и правой частях этого соотношения, равны, а значит, равны их соответствующие коэффициенты. Приравняем их, раскрыв предварительно скобки и приведя подобные члены в правой части данного равенства. Получим:

a= b_n-1,a_-1 = b_n-2 — cb_n-1,a_-2 = b_n-3 — cb_n-2,

a₂ = b₁ — cb_2,a₁ = b₀ — cb_1,a₀ = r — cb₀.

Напомним, что требуется найти неполное частное, т. е. его коэффициенты, и остаток.

Выразим их из полученных равенств:

b_n-1 = a_n,.

b _n-2 = cb_n-1 + a_n-1,b _n-3 = cb_n-2 + a _n-2,

b₁ = cb₂ + a_2,b₀ = cb₁ +a_1,r = cb₀ + a_0.

Мы нашли формулы, по которым можно вычислять коэффициенты неполного частного s (x) и остаток r. При этом вычисления оформляются в виде следующей таблицы; она называется схемой Горнера.

Таблица 1. Коэффициенты f (x)

Коэффициенты s (x) остаток.

В первую строку этой таблицы записывают подряд все коэффициенты многочлена f (x), оставляя первую клетку свободной. Во второй строке в первой клетке записывают число c.

Остальные клетки этой строки заполняют, вычисляя один за другим коэффициенты неполного частного s (x) и остаток r. Во второй клетке записывают коэффициент b_n-1, который, как мы установили, равен a_n.

Коэффициенты, стоящие в каждой последующей клетке, вычисляются по такому правилу: число c умножается на число, стоящее в предыдущей клетке, и к результату прибавляется число, стоящее над заполняемой клеткой. Чтобы запомнить, скажем, пятую клетку, т. е. найти стоящий в ней коэффициент, нужно c умножить на число, находящееся в четвертой клетке, и к результату прибавить число, стоящее над пятой клеткой.

Разделим, например, многочлен:

f (x) =3x⁴-5x²+3x-1.

на х-2 с остатком, используя схему Горнера.

При заполнении первой строки этой схемы нельзя забывать о нулевых коэффициентах многочлена.

Так, коэффициенты f (x) — это числа 3, 0, — 5, 3, — 1. И еще следует помнить, что степень не полного частного на единицу меньше степени многочлена f (x).

Итак, выполняем деление по схеме Горнера:

Таблица 2

Получим неполное частное:

s (x) =3x³+6x²+7x+17.

и остаток r=33. заметим, что одновременно мы вычислили значение многочлена f (2) =33.

Разделим теперь тот же многочлен f (x) на х+2 с остатком. В этом случае с=-2. получим:

Таблица 3

В результате имеем:

f (x) = (x+2) (3x³-6x²+7x-11) +21.

Ранее мы установили, что, если с — корень многочлена f (x) делится на х-с. Сейчас обобщим это утверждение.

Пусть с ₁, с ₂, …, с_m — различные корни многочлена f (x). Тогда f (x) делится на х-с ₁, т. е.

f (x) = (x-c₁) s₁ (x).

Положим в этом равенстве х=с ₂. Получим:

f (c₂) = (c₂-c₁) s₁ (c₂).

f (c₂) =0, то (с ₂-с ₁) s₁ (c₂) =0.

S₁ (c₂) =0. Таким образом, с ₂ — корень многочлена s₁ (x).

Отсюда следует, что s₁ (x) делится на х-с ₂, т. е.:

s₁ (x) = (x-c₂) s₂ (x).

Подставим полученное выражение для s₁ (x) в равенство f (x) = (x-c₁) s₁ (x). Имеем:

f (x) = (x-c₁) (x-c₂) s₂ (x).

S₂ (x) = (x-c₃) s₃ (x),.

f (x) = (x-c₁) (x-c₂) (x-c₃) s₃ (x) и т. д.

Продолжив эти рассужденья для оставшихся корней с ₄, с ₅, …, с_m, мы, наконец, получим:

f (x) = (x-c₁) (x-c₂) … (х-с_m) s_m (x).

Т.е. доказано формулируемое ниже утверждение.

Если с ₁, с ₂, …, с_m — различные корни многочлена f (x), то f (x) можно представить в виде:

f (x) = (x-c₁) (x-c₂)… (x-c_m) s_m (x).

Отсюда вытекает важное следствие.

Если с ₁, с ₂,…, с_m — различные корни многочлена f (x), то f (x) делится на многочлен (х-с ₁) (х-с ₂) … (х-с_m).

Как мы уже отмечали, одной из важных задач в теории многочленов является задача отыскания корней многочлена. В связи с этим существенным представляется вопрос о их числе. В самом деле, если дан какой-то многочлен и уже найдено, скажем, 10 его корней, то нужно знать, следует ли продолжать поиски. А вдруг этот многочлен больше не имеет корней? В таких случаях нам будет полезна приводимая ниже теорема. [8, c. 56].

Число различных корней ненулевого многочлена f (x) не больше, чем его степень. Действительно, если f (x) корней не имеет, то ясно, что теорема верна. Пусть теперь f (x) имеет m корней с ₁, с ₂, …, с_m, причем все они различны. Тогда, по только что доказанному f (x) делится на (х-с ₁) (х-с ₂) … (х-с_m). В таком случае: метод многочлен ньютон горнер ст. f (x)= ст. ((х-с ₁) (х-с ₂) … (х-с_m)) =ст. (х-с ₁) + ст. (х-с ₂) +…+ст. (х-с_m) =m,.

т.е. ст. f (x)m, а m — это число корней рассматриваемого многочлена.

А вот у нулевого многочлена бесконечно много корней, ведь его значение для любого х равно 0. В частности, по этой причине ему и не предписывают никакой определенной степени.

Из только что доказанной теоремы следует такое утверждение.

Если многочлен f (x) не является многочленом степени, большей, чем n, и имеет более, чем n корней, то f (x) — нулевой многочлен.

В самом деле, из условий этого утверждения следует, что-либо f (x) — нулевой многочлен, либо ст. f (x)n. Если предположить, что многочлен f (x) не нулевой, то ст. f (x)n, и тогда f (x) имеет не более, чем n корней. Приходим к противоречию. Значит, f (x) — ненулевой многочлен.

Пусть f (x) и g (x) — ненулевые многочлены степени, не большей, чем n. Если эти многочлены принимают одинаковые значения при n+1 значении переменной х, то f (x) =g (x).

Для доказательства рассмотрим многочлен h (x) =f (x) — g (x). Ясно, что — либо h (x) =0, либо ст. h (x)n, т. е. h (x) не является многочленом степени, большей, чем n. Пусть теперь число с такое, что f © =g ©. Тогда h © = f (c) — g © =0, т. е. с — корень многочлена h (x). Следовательно, многочлен h (x) имеет n+1 корень, а когда, как только что доказано, h (x) =0, т. е. f (x) =g (x).

Если же f (x) и g (x) принимают одинаковые значения при всех значениях переменной х, то эти многочлены тем более равны.

Эта теорема весьма эффективно используется при доказательстве некоторых числовых тождеств. [8, c. 34].

Докажем, например, что для любых попарно различных чисел а, b, с и любого числа х.

(((x-b) (x-c)) / ((a-b) (a-c))) + (((x-a) (x-c)) ((b-a) (b-c))) + (((x-a) (x-b)) ((c-a) (c-b))) =1.

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

Будем рассматривать х как переменную. Тогда, как нетрудно заметить, в левой части тождества находится многочлен, который мы обозначим f (x). Переменная х входит в этот многочлен самое большое в степени 2, т. е. ст. f (x)?2. в правой части того же тождества — так же многочлен: g (x) =1.

Найдем теперь значение многочленов f (x) и g (x) при х=a, b, c. Ясно, что g (a) =g (b) =g © =1. Далее,.

f (a) = (((a-b) (a-c)) / ((a-b) (a-c))) + (((a-a) (a-c)) ((b-a) (b-c))) + (((a-a) (a-b)) ((c-a) (c-b))) =1.

Аналогично f (b) =f © =1. Следовательно, f (a) =g (a), f (b) =g (b), f © =g ©. Видим, что многочлены f (x) и g (x), не являющиеся многочленами степени выше, чем 2, принимают одинаковые значения при трех различных значениях переменной. Значит, f (x) =g (x).