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

                                                   СОДЕРЖАНИЕ:

ВВЕДЕНИЕ

1. МЕТОДЫ НАХОЖДЕНИЯ ГРАНИЦ МНОГОЧЛЕНА

1.1. Метод хорд и касательных (комбинированный)

1.2. Метод итераций

1.3. Метод половинного деления (метод бисекции)

1.4. Метод разложения на множители

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

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

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

5. РЕШЕНИЕ ЗАДАЧ НА ВЫЧИСЛЕНИЕ ГРАНИЦ МНОГОЧЛЕНА

ЗАКЛЮЧЕНИЕ

 СПИСОК ЛИТЕРАТУРЫ

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ВВЕДЕНИЕ     

Способ  нахождения корней линейных и квадратичных многочленов, то есть способ решения  линейных и квадратных уравнений, был  известен ещё в древнем мире. Поиски формулы для точного решения  общего уравнения третьей степени продолжались долгое время (следует упомянуть метод, предложенный Омаром Хайямом), пока не увенчались успехом в первой половине XVI века в трудах Сципиона дель Ферро, Никколо Тарталья и Джероламо Кардано. Формулы для корней квадратных и кубических уравнений позволили сравнительно легко получить формулы для корней уравнения четвертой степени.[3,c.67]      

То, что корни общего уравнения пятой  степени и выше не выражаются при  помощи рациональных функций и радикалов  от коэффициентов было доказано норвежским математиком Нильсом Абелем в 1826 г. Это совсем не означает, что корни такого уравнения не могут быть найдены. Во-первых, в частных случаях, при некоторых комбинациях коэффициентов корни уравнения при некоторой изобретательности могут быть определены. Во-вторых, существуют формулы для корней уравнений 5-й степени и выше, использующие, однако, специальные функции — эллиптические или гипергеометрические (см., к примеру, корень Бринга).      

В случае, если все коэффициенты многочлена рациональны, то нахождение его корней приводится к нахождению корней многочлена с целыми коэффициентами. Для рациональных корней таких многочленов существуют алгоритмы нахождения перебором кандидатов с использованием схемы Горнера, причем при нахождении целых корней перебор может быть существенно уменьшен приемом чистки корней. Также в этом случае можно использовать полиномиальный LLL-алгоритм.  Для приблизительного нахождения (с любой  требуемой точностью) вещественных корней многочлена с вещественными  коэффициентами используются итерационные методы, например, метод секущих, метод бисекции, метод Ньютона. Количество вещественных корней многочлена на интервале может быть оценено при помощи теоремы Штурма.[8,c.56]

1. МЕТОДЫ НАХОЖДЕНИЯ ГРАНИЦ МНОГОЧЛЕНА

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

В этой связи задача нахождения корней многочлена вида (1)

F(x)=a0+a1x+a2x2+…+anxn       (1) 

представляет особый интерес, т.к. формулы нахождения корней даже кубического уравнения достаточно сложны, а если необходимо отыскать корни многочлена, степень которого равна, например, 5 – то без помощи численных методов не обойтись, тем  боле, что вероятность наличия  у такого многочлена натуральных (или  целых, или точных корней с с «короткой» дробной частью) довольно мала, а формул для нахождения корней уравнения степени, превышающей 4, не существует.[1,c.23] Де-факто все дальнейшие операции будут сводиться лишь к уточнению корней, интервалы которых приблизительно известны заранее. Проще всего эти «приблизительные» корни находить, используя графические методы.

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

1.1. Метод хорд и касательных (комбинированный)

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

Надо отметить, что существуют также отдельно метод хорд (дает значение корня с недостатком) и  метод касательных (с избытком). Однако преимущество комбинированного метода заключается в «двустороннем  сжатии» рассматриваемого отрезка.[2,c.54]

Рассмотрим следующий  случай:

дана функция F(x) и построен ее график;

определена допустимая  погрешность Q

Рис.1

на основании графика  определен отрезок [a,b], на котром график функции пересекает ось абсцисс, следовательно, на этом отрезке (рис.1)

существует корень рассматриваемого многочлена. (обозначим его через A)  

Дальнейший алгоритм  сводится к следующим действиям:

строим касательную к  графику функции в точке F(b)

вычисляем координату х пересечения касательной с осью абсцисс по формуле (3) и обозначаем ее через b’

строим к графику функции  хорду, проходящую через точки F(a)  и F(b).

Вычисляем точку пересечения  хорды с осью абсцисс по формуле (2) и обозначаем ее через a'.

a’=a- Da , где                                              (2)

b’=b- Db , где                                        (3)

Таким образом мы получаем новый отрезок [a’ , b’], котроый (по определениям хорды и касательной) по-прежнему содержи решение уравнения A.

Теперь принимаем отрезок [a’,b’] за новый отрезок [a,b] и повторяем шаги 1-4 до тех пор, пока разность F(b)-F(a) не станет меньше первоначально заложенной погрешности Q. Отметим также, что после этого рекомендуется в качестве искомого решения взять среднее арифметическое F(a) и F(b).

       Замечание к методу хорд и касательных. В рассмотренном случае производная F’(x)>0, т.е. график «выпуклый» и b>a. При работе с каждым отдельным случаем необходимо находить производные функции первого и второго порядков и, сообразуясь с ее знаком, определять a и b.

	Способ хорд	Способ касательных
F’(x)F’’(x) > 0	С недостатком	С избытком
F’(x)F’’(x) < 0	С ибытком	С недостатком

Таким образом, если хорда (касательная) дает значение корня с избытком, то этот корень берется с качестве новой правой границы, а если с недостатком – то левой. В обоих случаях точный корень лежит между точками пересечения хорды и касательной с осью абсцисс.[5,c.90]

         Замечание 2 к методу хорд и касательных. Так как для решения поставленной задачи требуется  отыскание производной функции F(x), метод хорд и касательных достаточно трудно реализуем на программном уровне, т.к. правила вычисления производных в общем виде довольно громоздки  для «понимания» ЭВМ; при непосредственном указании производной для каждой степени многочлена память компьютера серьезно загружается, что очень замедляет работу, а задание функции и, соответственно, ее производной непосредственно в программном коде – недопустимо. Однако, используя данный метод, сходимость интервала к корню происходит наиболее быстро, особенно если совместить метод хорд и касательных с методом бисекции, т.к. середина нового отрезка зачастую дает вполне удовлетворительное решение.[9,c.12]

1.2. Метод итераций

      Пятый шаг алгоритма хорд и касательных определял возврат к первому шагу и последующую цикличность хода, т.е. метод хорд и касательных являлся итерационным. Другой метод, также основанный на повторах так и был назван – «метод итераций».[2,c.7] Суть его заключается в следующем:

дана функция F(x);

определена допустимая  погрешность Q;

определен некоторый интервал [ a , b ], точно содержащий решение уравнения.

Определено некоторое  число z, принадлежащее [ a , b ] (назовем z «нулевым приближением»)

Для получения следующего приближения подставим в формулу (1) вместо X Z, получим:

x1=F(z)     (4)

и, продолжая аналогично,

x2=F(x1)                                                                     

x3=F(x2)     (5)

…

xn=F(xn-1)                                                                    

Таким образом, получаем некоторую  последовательность, и, если ее предел limxn=A,          n®v          (6)

то А является искомым корнем.

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

необходимость выбора нулевого приближения (ведь то, что интуитивно для человека, для ЭВМ может  стать довольно сложной задачей)

наконец, полученная последовательность просто может не сходиться, и тогда  решение найдено не будет.

Эти контраргументы стали  основанием для отклонения метода итераций при выборе алгоритмизируемого метода.[4,c.71]

1.3. Метод половинного деления (метод бисекции)

 рис.2

Метод половинного деления (известный еще и как «метод деления отрезка пополам») также  является рекурсивным, т.е. предусматривает  повторение с учетом полученных результатов .[3,c.43]

Суть метода половинного  деления заключается в следующем:

дана функция F(x);

определена допустимая  погрешность Q;

определен некоторый интервал [ a , b ], точно содержащий решение уравнения.

Вычисляем значение координаты Е, беря середину отрезка [a , b], т.е. Е= (a + b ) / 2                                                                                        (7)

Вычисляем значения F(a), F(b), F(E), и осуществляем следующую проверку: Если F(E)>Q, то корень с указанной точностью найден. Если F(E)<Q, т.е. необходимая точность еще не достигнута, то формируем два интервала: [a , E] и [E , b] проверяем знаки F(a), F(b), F(E). На концах одного из этих интервалов знаки функции будут одинаковы, а на друго различны (иначе Е  - искомый корень). И именно то интервал, на концах  которого знаки различны, мы берем за основу при следующей итерации, т.е. приравниваем к Е либо a, либо  b.

Переходим к пункту 1.

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

1.4. Метод разложения на множители

       Данный метод является полностью аналитическим, однако полностью зависим от других. Главным его преимуществом является то, что в данном методе не происходит потери кратных корней. Поясним на примере:

Пусть дан многочлен F(x) = 2x3-11x2+20x-12                                  (11)

Его можно записать в виде: F(x) = (x+2)2(2x-3)                    (12)

У многочлена n-степени, как  известно, n корней, а из (12) следует, что корнями F(x) являются –2 и 1,5, причем корень –2 является кратным, т.е. фактически это два одинаковых корня. При отыскании же корней любым из вышеописанных методов «второй» корень –2 будет потерян, т.к. график функции будет иметь лишь две точки пересечения с осью абсцисс. [5, c.41]

Чтобы избежать этого применяется  метод разложения на множители. Суть его заключается в следующем: каждый многочлен вида (1) можно представить  в виде      (x+h1)(x+h2)…(x+hn)*H = 0               (13) ,

или                    F(x) = (x+h)(bn-1xn-1+…b1)+b0                    (14)

где h1…hn – корни уравнения, а Н – произведение множителей х, вынесенных за скобки ( Н никак не влияет на уравнение, т.к. от него избавляются, деля на Н обе части (13). При этом не исключено, что некоторые h могут быть взаимно равны, что и свидетельствует о наличии кратного корня.    

 Для вычисления значений  новых коэффициентов в (14) используются  формулы:

bn=an

bn-1=bnh+an-1                                                                                                  (15)

bn-2=bn-1h+an-2 

…

Таким образом, алгоритм этого  метода выглядит следующим образом:

Определить границы корней уравнения;

При помощи любого из вышеописанных  методов найти один корень уравнения;

Применяя формулы (14) и (15) сформировать новый многочлен степени, на 1 меньшей предыдущего.