Границы корней многочленов

Вернуться к пункту 2.

Повторять до тех пор, пока степень многочлена не обнулится.[3,c.11]

2.СХЕМА ГОРНЕРА     

Разделить с остатком многочлен 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)

	an	an-1	an-2	…	a0
c	bn-1	bn-2 = cbn-1+ an-1	bn-3 = cbn-2+an-2	…	r = cb0 + a0

 

 

Коэффициенты  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.

	3	0	-5	3	-1
2	3	6	7	17	33

 

 

Получим неполное частное s (x) =3x³+6x²+7x+17 и остаток r=33. заметим, что одновременно мы вычислили значение многочлена f (2) =33.

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

Таблица 3.

	3	0	-5	3	-1
-2	3	-6	7	-11	21

 

 

В результате имеем 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. Но с₂?с₁, т.е. с₂-с₁?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). Положив в последнем равенстве х=с₃ с учетом того, что f (c₃) =0, с₃?с1, с₃?с₂, получим, что с₃ - корень многочлена 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) ?0.

Пусть теперь 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 (c) =g (c). Тогда h (c) = f (c) - g (c) =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 (c) =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 (c) =1. Следовательно, f (a) =g (a), f (b) =g (b), f (c) =g (c). Видим, что многочлены f (x) и g (x), не являющиеся многочленами степени выше, чем 2, принимают одинаковые значения при трех различных значениях переменной. Значит, f (x) =g (x).

3. УНИВЕРСАЛЬНЫЙ МЕТОД НАХОЖДЕНИЯ ГРАНИЦ МНОГОЧЛЕНА. МЕТОД НЬЮТОНА

Одним из наиболее распространенных методов поиска корней уравнений  является метод Ньютона и его  модификации. Пусть требуется решить уравнение . Будем считать, что x является решением уравнения. Разложим функцию f(x) в ряд в точке x0 близкой к точке x и ограничимся только первыми двумя членами разложения.

Поскольку x – корень уравнения, то . Следовательно,

Таким образом, если нам известно приближенное значение корня уравнения, то полученное уравнение позволяет его уточнить. Понятно, что процесс уточнения  можно повторять многократно, до тех пор, пока значение функции не будут отличаться от нуля на величину меньшую, чем заданная точность поиска. Очередное k-е приближение находится по формуле

Ограничившись в разложении только первыми двумя членами, мы фактически заменили функцию f(x) на прямую линию, касательную в точке x0, поэтому метод Ньютона еще называют методом касательных. Далеко не всегда бывает удобно находить аналитическое выражение для производной функции. Однако, в этом и нет особой необходимости: поскольку на каждом шаге мы получаем приближенное значение корня, можно для его вычисления использовать приближенное значение производной.[6,c.10]

В качестве малой величины можно взять, например, заданную точность вычислений , тогда расчетная формула примет вид

(1.1)

С другой стороны, для вычисления производной  можно воспользоваться значениями функции, полученными на двух предыдущих шагах,

(1.2)

В таком виде метод называется методом  секущих (secant method). При этом, однако, возникает проблема с вычислением первого приближения. Обычно полагают, что , то есть первый шаг вычислений проводится с использованием формулы (1.1), а все последующие – с использованием формулы (1.2). Именно эта вычислительная схема реализована в пакете Mathcad. Используя метод секущих, мы не можем гарантировать, что корень находится между двумя последними приближениями. Можно, однако, для вычисления очередного приближения использовать границы интервала, на котором функция меняет знак. Такой метод называется методом хорд (false position method).

4. ТЕОРЕМА ШТУРМА

     

Теорема Штурма. Если действительные числа а и Ь, a<ib, не являются корнями многочлена / (х), не имеющего кратных корней, то W(a)=W(b) и разность W(a)—W(b) равна числу действительных корней многочлена f(x), заключенных между а и b.

Количество вещественных корней многочлена на интервале может быть оценено  при помощи теоремы Штурма.

Ряд Штурма (система Штурма) для вещественного многочлена — последовательность многочленов, позволяющая эффективно определять количество корней многочлена на промежутке и приближённо вычислять их с помощью теоремы Штурма. Ряд и теорема названы именем французского математика Жака Штурма.[2.c,34]

Рассмотрим многочлен f(x) с вещественными коэффициентами. Конечная упорядоченная последовательность отличных от нуля многочленов с вещественными коэффициентами называется рядом Штурма для многочлена f(x), если выполнены следующие условия: не имеет корней;

 

если  и , то ;

если  ,

 

то произведение меняет знак с минуса на плюс, когда x, возрастая, проходит через точку c, т.е. когда существует такое δ > 0, что