| |||||
МЕНЮ
| НАХОЖДЕНИЕ ВСЕХ ДЕЙСТВИТЕЛЬНЫХ КОРНЕЙ АЛГЕБРАИЧЕСКОГО МНОГОЧЛЕНА МЕТОДОМ ДЕЛЕНИЯ ОТРЕЗКА ПОПОЛАМ (БИСЕКЦИИ) И МЕТОДОМ ХОРД И КАСАТЕЛЬНЫХ С УКАЗАННОЙ ТОЧНОСТЬЮ И УЧЕТОМ ВОЗМОЖНОЙ КРАТНОСТИ КОРНЕЙНАХОЖДЕНИЕ ВСЕХ ДЕЙСТВИТЕЛЬНЫХ КОРНЕЙ АЛГЕБРАИЧЕСКОГО МНОГОЧЛЕНА МЕТОДОМ ДЕЛЕНИЯ ОТРЕЗКА ПОПОЛАМ (БИСЕКЦИИ) И МЕТОДОМ ХОРД И КАСАТЕЛЬНЫХ С УКАЗАННОЙ ТОЧНОСТЬЮ И УЧЕТОМ ВОЗМОЖНОЙ КРАТНОСТИ КОРНЕЙФедеральная Авиационная Служба России МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ ГРАЖДАНСКОЙ АВИАЦИИ Кафедра прикладной математики Курсовая работа защищена с оценкой _________________. .__________________________. Руководитель доцент, к.т.н. Лукина О. П. .__________________________. подпись КУРСОВАЯ РАБОТА по теме НАХОЖДЕНИЕ ВСЕХ ДЕЙСТВИТЕЛЬНЫХ КОРНЕЙ АЛГЕБРАИЧЕСКОГО МНОГОЧЛЕНА МЕТОДОМ ДЕЛЕНИЯ ОТРЕЗКА ПОПОЛАМ (БИСЕКЦИИ) И МЕТОДОМ ХОРД И КАСАТЕЛЬНЫХ С УКАЗАННОЙ ТОЧНОСТЬЮ И УЧЕТОМ ВОЗМОЖНОЙ КРАТНОСТИ КОРНЕЙ (Пояснительная записка к курсовой работе по дисциплине «Численные методы») Работу выполнили студенты 5-го курса специальности 01.02 Козлов Сергей Александрович /Козлов С.А./------------------------. Семенчихин Владимир Владимирович /Семенчихин В.В./------------------------ . 28.X/1999 года. МОСКВА - 1999 АННОТАЦИЯ В данной курсовой работе рассмотрен принцип нахождения корней алгебраического многочлена следующими численными методами: метод бисекции, метод хорд и касательных, метод разложения на множители с учетом определяемой точности и проверки кратности корней, а также в среде Visual Basic for Applications 6.0 была разработана программа, реализующая этот поиск и проверку. В пояснительной записке приводится описание как самих численных методов, так и программы, включая примеры и «экранные копии». 1. ТЕХНИЧЕСКОЕ ЗАДАНИЕ Разработать программу для вычисления корней алгебраического многочлена следующими численными методами : методом половинного деления, методом хорд и касательных, методом разложения на множители, а также обеспечить вычисление значений корней с указываемой точностью и проверку кратности корней. Среда разработки программы – произвольная. 2. ПРЕДМЕТНАЯ ОБЛАСТЬ 2.1. Описание численных методов Численные методы позволяют найти решения определенных задач, заранее зная, что полученные результаты будут вычислены с определенной погрешностью, поэтому для многих численных методов необходимо заранее знать «уровень точности», которому будет соответствовать полученное решение. В этой связи задача нахождения корней многочлена вида (1) F(x)=a0+a1x+a2x2+…+anxn (1) представляет особый интерес, т.к. формулы нахождения корней даже кубического уравнения достаточно сложны, а если необходимо отыскать корни многочлена, степень которого равна, например, 5 – то без помощи численных методов не обойтись, тем боле, что вероятность наличия у такого многочлена натуральных (или целых, или точных корней с с «короткой» дробной частью) довольно мала, а формул для нахождения корней уравнения степени, превышающей 4, не существует.[1] Де-факто все дальнейшие операции будут сводиться лишь к уточнению корней, интервалы которых приблизительно известны заранее. Проще всего эти «приблизительные» корни находить, используя графические методы. Для нахождения корней многочлена существует несколько численных методов, но мы остановимся на тех из них: методе итераций, методе хорд и касательных и методе половинного деления. 2.2.1. Метод хорд и касательных (комбинированный) Данный метод основан на построении схематического графика функции, определении интервалов его пересечения с осью абсцисс и последующим «сжатием» этого интервала при помощи строимых хорд и касательных к графику этой функции. Надо отметить, что существуют также отдельно метод хорд (дает значение корня с недостатком) и метод касательных (с избытком). Однако преимущество комбинированного метода заключается в «двустороннем сжатии» рассматриваемого отрезка. Рассмотрим следующий случай: - дана функция F(x) и построен ее график; - определена допустимая погрешность Q - на основании графика определен отрезок [a,b], на котром график функции пересекает ось абсцисс, следовательно, на этом отрезке рис.1 - существует корень рассматриваемого многочлена. (обозначим его через A) Дальнейший алгоритм сводится к следующим действиям: 1. строим касательную к графику функции в точке F(b) 2. вычисляем координату х пересечения касательной с осью абсцисс по формуле (3) и обозначаем ее через b’ 3. строим к графику функции хорду, проходящую через точки F(a) и F(b). 4. Вычисляем точку пересечения хорды с осью абсцисс по формуле (2) и обозначаем ее через a'. a’=a- ?a , где [pic] (2) b’=b- ?b , где (3) Таким образом мы получаем новый отрезок [a’ , b’], котроый (по определениям хорды и касательной) по-прежнему содержи решение уравнения A. 5. Теперь принимаем отрезок [a’,b’] за новый отрезок [a,b] и повторяем шаги 1-4 до тех пор, пока разность F(b)-F(a) не станет меньше первоначально заложенной погрешности Q. Отметим также, что после этого рекомендуется в качестве искомого решения взять среднее арифметическое F(a) и F(b). Замечание к методу хорд и касательных. В рассмотренном случае производная F’(x)>0, т.е. график «выпуклый» и b>a. При работе с каждым отдельным случаем необходимо находить производные функции первого и второго порядков и, сообразуясь с ее знаком, определять a и b. Возможны четыре случая: y y F(x) F(x) x x а) б) y y F(x) F(x) x x в) г) а) F’(x) < 0 F’’(x) > 0 б) F’(x) > 0 F’’(x) > 0 в) F’(x) < 0 F’’(x) < 0 г) F’(x) > 0 F’’(x) < 0 | |Способ хорд |Способ касательных | |F’(x)F’’(x) > 0 |С недостатком |С избытком | |F’(x)F’’(x) < 0 |С ибытком |С недостатком | Таким образом, если хорда (касательная) дает значение корня с избытком, то этот корень берется с качестве новой правой границы, а если с недостатком – то левой. В обоих случаях точный корень лежит между точками пересечения хорды и касательной с осью абсцисс. Замечание 2 к методу хорд и касательных. Так как для решения поставленной задачи требуется отыскание производной функции F(x), метод хорд и касательных достаточно трудно реализуем на программном уровне, т.к. правила вычисления производных в общем виде довольно громоздки для «понимания» ЭВМ; при непосредственном указании производной для каждой степени многочлена память компьютера серьезно загружается, что очень замедляет работу, а задание функции и, соответственно, ее производной непосредственно в программном коде – недопустимо. Однако, используя данный метод, сходимость интервала к корню происходит наиболее быстро, особенно если совместить метод хорд и касательных с методом бисекции, т.к. середина нового отрезка зачастую дает вполне удовлетворительное решение. 2.2.2. Метод итераций Пятый шаг алгоритма хорд и касательных определял возврат к первому шагу и последующую цикличность хода, т.е. метод хорд и касательных являлся итерационным. Другой метод, также основанный на повторах так и был назван – «метод итераций». Суть его заключается в следующем: - дана функция F(x); - определена допустимая погрешность Q; - определен некоторый интервал [ a , b ], точно содержащий решение уравнения. - Определено некоторое число z, принадлежащее [ a , b ] (назовем z «нулевым приближением») Для получения следующего приближения подставим в формулу (1) вместо X Z, получим: [pic]x1=F(z) (4) и, продолжая аналогично, [pic] x2=F(x1) [pic]x3=F(x2) (5) … xn=F(xn-1) Таким образом, получаем некоторую последовательность, и, если ее предел (6) limxn=A, n>( (6) то А является искомым корнем. Данный метод является исключительно аналитическим, что упрощает его машинную реализацию, однако содержит следующие недостатки: - необходимость выбора нулевого приближения (ведь то, что интуитивно для человека, для ЭВМ может стать довольно сложной задачей) - наконец, полученная последовательность просто может не сходиться, и тогда решение найдено не будет. Эти контраргументы стали основанием для отклонения метода итераций при выборе алгоритмизируемого метода. 2.2.3. Метод половинного деления (метод бисекции) рис.2 Метод половинного деления (известный еще и как «метод деления отрезка пополам») также является рекурсивным, т.е. предусматривает повторение с учетом полученных результатов. Суть метода половинного деления заключается в следующем: - дана функция F(x); - определена допустимая погрешность Q; - определен некоторый интервал [ a , b ], точно содержащий решение уравнения. 1. Вычисляем значение координаты Е, беря середину отрезка [a , b], т.е. Е= (a + b ) / 2 (7) 2. Вычисляем значения F(a), F(b), F(E), и осуществляем следующую проверку: Если F(E)>Q, то корень с указанной точностью найден. Если F(E) ma Then ma = curcell.Value If curcell.Value <> 0 Then Ao = curcell.Value Next curcell DetectBorders = 1 + (ma * Ao) End Function UNIT2 Sub auto_open() Sheets("Лист1").Select Form_Main.Show End Sub FORM_ABOUT Private Sub CommandButton1_Click() Form_About.Hide End Sub FORM_KOEFF Private Sub CommandButton1_Click() ko = TextBox1.Value st = TextBox2.Value Select Case st Case 0 Range("A21").Value = ko Case 1 Range("A1") = ko Case 2 Range("A2") = ko Case 3 Range("A3") = ko Case 4 Range("A4") = ko Case 5 Range("A5") = ko Case 6 Range("A6") = ko Case 7 Range("A7") = ko Case 8 Range("A8") = ko Case 9 Range("A9") = ko Case 10 Range("A10") = ko Case 11 Range("A11") = ko Case 12 Range("A12") = ko Case 13 Range("A13") = ko Case 14 Range("A14") = ko Case 15 Range("A15") = ko Case 16 Range("A16") = ko Case 17 Range("A17") = ko Case 18 Range("A18") = ko Case 19 Range("A19") = ko Case 20 Range("A20") = ko Case Else MsgBox ("Выход за пределы допустимых значений") st = st - 1 End Select TextBox1.Value = 0 TextBox2.Value = st + 1 End Sub Private Sub CommandButton2_Click() Form_Koeff.Hide End Sub Private Sub CommandButton3_Click() Range("a1").Value = 0 Range("a2").Value = 0 Range("a3").Value = 0 Range("a4").Value = 0 Range("a5").Value = 0 Range("a6").Value = 0 Range("a7").Value = 0 Range("a8").Value = 0 Range("a9").Value = 0 Range("a10").Value = 0 Range("a11").Value = 0 Range("a12").Value = 0 Range("a13").Value = 0 Range("a14").Value = 0 Range("a15").Value = 0 Range("a16").Value = 0 Range("a17").Value = 0 Range("a18").Value = 0 Range("a19").Value = 0 Range("a20").Value = 0 Range("a21").Value = 0 End Sub Private Sub UserForm_initialize() st = 0 ko = 0 TextBox1.Value = ko TextBox2.Value = st End Sub FORM_KORNI Private Sub CommandButton1_Click() ListBox1.Clear TextBox1.Value = 0 Form_Korni.Hide End Sub Private Sub CommandButton2_Click() Range("Toc").Value = TextBox1.Value Call FindKor 'Call Perenos End Sub Sub FindKor() Range("Curright") = Range("Right").Value Range("Curleft") = -Range("Right").Value - 0.333 'Range("right").Value = DetectBorders Range("Stepleft").Value = Range("right").Value * (-1) - 0.333 Do nashli = False Call MoveLe If Sgn(F(Range("curleft").Value)) = Sgn(F(Range("curright").Value)) Then End If If Sgn(F(Range("curleft").Value)) <> Sgn(F(Range("curright").Value)) Then Do ' nashli = True Range("Curcenter").Value = ((Range("curleft").Value) + (Range("curright").Value)) / 2 If Abs(F(Range("Curcenter").Value)) > Range("toc").Value Then If Sgn(F(Range("curleft").Value)) <> Sgn(F(Range("curcenter").Value)) Then Range("curright").Value = Range("curcenter").Value Else: Range("curleft").Value = Range("curcenter").Value If Abs(F(Range("Curcenter").Value)) Range("right").Value Or nashli = True End Sub Sub Horda_Kas() 'Sub FindKor() Range("Curright") = Range("Right").Value Range("Curleft") = -Range("Right").Value - 0.333 'Range("right").Value = DetectBorders Range("Stepleft").Value = Range("right").Value * (-1) - 0.333 Do MoveLe If Sgn(F(Range("curleft").Value)) <> Sgn(F(Range("curright").Value)) Then Do ' nashli = True If F1(Range("curleft").Value) * F2(Range("curleft").Value) > 0 Then Range("curleft").Value = Range("curleft").Value - ((Range("curright").Value - Range("curleft").Value) * (F(Range("Curleft").Value) / (F(Range("Curright").Value - F(Range("Curleft").Value))))) Range("Curright").Value = Range("curright").Value - F(Range("curright").Value) / F1(Range("curright").Value) End If If F1(Range("curleft").Value) * F2(Range("curleft").Value) < 0 Then Range("curright").Value = Range("curleft").Value - ((Range("curright").Value - Range("curleft").Value) * (F(Range("Curleft").Value) / (F(Range("Curright").Value - F(Range("Curleft").Value))))) Range("Curleft").Value = Range("curright").Value - F(Range("curright").Value) / F1(Range("curright").Value) End If If Abs(Abs(F(Range("Curright").Value))) - Abs(F(Range("Curleft").Value)) 0 Then ListBox1.AddItem (((Range("Curleft").Value) + (Range("Curright").Value)) / 2) 'If ((Range("Curleft").Value) + (Range("Curright").Value)) < 0 Then ListBox1.AddItem (((Range("Curleft").Value) + (Range("Curright").Value)) / 2) Range("Koren").Value = Range("Curleft").Value End If Loop Until Abs(F(Range("Curright").Value)) - Abs(F(Range("Curleft").Value)) Range("right").Value Or nashli = True End Sub Sub MoveLe() Range("stepleft").Value = Range("stepleft").Value + 0.333 Range("curLeft").Value = Range("stepleft").Value Range("Curright").Value = Range("Curleft").Value + 0.333 Range("Curcenter").Value = ((Range("curleft").Value) + (Range("curright").Value)) / 2 End Sub Private Sub CommandButton3_Click() Horda_Kas End Sub Private Sub UserForm_Deactivate() ListBox1.Clear TextBox1.Value = 0 End Sub Sub Perenos() Range("a1").Value = Range("L1").Value Range("a2").Value = Range("L2").Value Range("a3").Value = Range("L3").Value Range("a4").Value = Range("L4").Value Range("a5").Value = Range("L5").Value Range("a6").Value = Range("L6").Value Range("a7").Value = Range("L7").Value Range("a8").Value = Range("L8").Value Range("a9").Value = Range("L9").Value Range("a10").Value = Range("L10").Value Range("a11").Value = Range("L11").Value Range("a12").Value = Range("L12").Value Range("a13").Value = Range("L13").Value Range("a14").Value = Range("L14").Value Range("a15").Value = Range("L15").Value Range("a16").Value = Range("L16").Value Range("a17").Value = Range("L17").Value Range("a18").Value = Range("L18").Value Range("a19").Value = Range("L19").Value End Sub FORM_MAIN Private Sub CommandButton1_Click() Form_Koeff.Show End Sub Private Sub CommandButton2_Click() Form_Mnogo.Show End Sub Private Sub CommandButton3_Click() Gra Form_Main.Height = 84 Sheets("D1").Select Form_WP.Show Form_Main.Height = 360 Sheets("Лист1").Select End Sub Private Sub CommandButton4_Click() Form_Korni.Show End Sub Private Sub CommandButton5_Click() Application.Quit End Sub Private Sub CommandButton7_Click() Form_About.Show End Sub Private Sub CommandButton8_Click() ActiveWorkbook.Save End Sub Private Sub UserForm_initialize() Sheets("Лист1").Select Form_Main.Height = 360 End Sub FORM_MNOGO Dim mn As String Private Sub CommandButton1_Click() Form_Mnogo.Hide End Sub Private Sub UserForm_activate() mn = "F(x)=" If Range("a20") > 0 Then mn = mn + Range("a20").Text + "X^20" If Range("a20") < 0 Then mn = mn + Range("a20").Text + "X^20" If Range("a19") > 0 Then mn = mn + " + " + Range("a19").Text + "X^19" If Range("a19") < 0 Then mn = mn + Range("a19").Text + "X^19" If Range("a18") > 0 Then mn = mn + " + " + Range("a18").Text + "X^18" If Range("a18") < 0 Then mn = mn + Range("a18").Text + "X^18" If Range("a17") > 0 Then mn = mn + " + " + Range("a17").Text + "X^17" If Range("a17") < 0 Then mn = mn + Range("a17").Text + "X^17" If Range("a16") > 0 Then mn = mn + " + " + Range("a16").Text + "X^16" If Range("a16") < 0 Then mn = mn + Range("a16").Text + "X^16" If Range("a15") > 0 Then mn = mn + " + " + Range("a15").Text + "X^15" If Range("a15") < 0 Then mn = mn + Range("a15").Text + "X^15" If Range("a14") > 0 Then mn = mn + " + " + Range("a14").Text + "X^14" If Range("a14") < 0 Then mn = mn + Range("a14").Text + "X^14" If Range("a13") > 0 Then mn = mn + " + " + Range("a13").Text + "X^13" If Range("a13") < 0 Then mn = mn + Range("a13").Text + "X^13" If Range("a12") > 0 Then mn = mn + " + " + Range("a12").Text + "X^12" If Range("a12") < 0 Then mn = mn + Range("a12").Text + "X^12" If Range("a11") > 0 Then mn = mn + " + " + Range("a11").Text + "X^11" If Range("a11") < 0 Then mn = mn + Range("a11").Text + "X^11" If Range("a10") > 0 Then mn = mn + " + " + Range("a10").Text + "X^10" If Range("a10") < 0 Then mn = mn + Range("a10").Text + "X^10" If Range("a9") > 0 Then mn = mn + " + " + Range("a9").Text + "X^9" If Range("a9") < 0 Then mn = mn + Range("a9").Text + "X^9" If Range("a8") > 0 Then mn = mn + " + " + Range("a8").Text + "X^8" If Range("a8") < 0 Then mn = mn + Range("a8").Text + "X^8" If Range("a7") > 0 Then mn = mn + " + " + Range("a7").Text + "X^7" If Range("a7") < 0 Then mn = mn + Range("a7").Text + "X^7" If Range("a6") > 0 Then mn = mn + " + " + Range("a6").Text + "X^6" If Range("a6") < 0 Then mn = mn + Range("a6").Text + "X^6" If Range("a5") > 0 Then mn = mn + " + " + Range("a5").Text + "X^5" If Range("a5") < 0 Then mn = mn + Range("a5").Text + "X^5" If Range("a4") > 0 Then mn = mn + " + " + Range("a4").Text + "X^4" If Range("a4") < 0 Then mn = mn + Range("a4").Text + "X^4" If Range("a3") > 0 Then mn = mn + " + " + Range("a3").Text + "X^3" If Range("a3") < 0 Then mn = mn + Range("a3").Text + "X^3" If Range("a2") > 0 Then mn = mn + " + " + Range("a2").Text + "X^2" If Range("a2") < 0 Then mn = mn + Range("a2").Text + "X^2" If Range("a1") > 0 Then mn = mn + " + " + Range("a1").Text + "X" If Range("a1") < 0 Then mn = mn + Range("a8").Text + "X" If Range("a21") > 0 Then mn = mn + " + " + Range("a21").Text If Range("a21") < 0 Then mn = mn + Range("a21").Text TextBox1.Value = mn End Sub FORM_WP Private Sub Label1_Click() Call Gra End Sub Private Sub CommandButton1_Click() Sheets("D1").Print End Sub Private Sub CommandButton2_Click() Form_WP.Hide Call Gra End Sub Private Sub UserForm_Click() Form_WP.Hide End Sub ____________________________ VoID InVaSiON HG © VI Function 2.0 beta ----------------------- [1] -B>B D0:B 1K; 4>:070= 8725AB=K@5=L >1=0@C65= !"- 1 0 B=C 0 =C 1 0 1 [pic] [pic] F(C) < B>G=>ABL =0 Этот факт был доказан известными математиками Абелеи и Галуа. ----------------------- [pic] Знаки F(В) и F(C) разные Корень обнаружен СТОП 1 0 B=C 0 А=C 1 0 1 [pic] [pic] F(C) < точность Знаки F(A) и F(C) разные С= (А+В) / 2 Поиск корней - начало 0 1 0 1 Стоп Корень бонаружен. F(B) -F(A) (хорда с избытком, касательная с недостатком0) Начало ? |
ИНТЕРЕСНОЕ | |||
|