Нахождение всіх дійсних коренів алгебраического багаточлена методом розподілу відрізка наполовину (бисекции) і методом хорд і дотичних з зазначеної точностью і урахуванням можливої кратності корней

Федеральна Авіаційна Служба России.

МОСКОВСЬКИЙ ДЕРЖАВНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ ГРОМАДЯНСЬКОЇ АВИАЦИИ.

Кафедра прикладної математики.

Курсова робота захищена з оцінкою _________________. .__________________________. Керівник доцент, к.т.н. Лукина Про. П. .__________________________. подпись.

КУРСОВА РАБОТА.

по теме.

ПЕРЕБУВАННЯ ВСІХ ДІЙСНИХ КОРЕНІВ АЛГЕБРАИЧЕСКОГО БАГАТОЧЛЕНА МЕТОДОМ РОЗПОДІЛУ ВІДРІЗКА НАПОЛОВИНУ (БИСЕКЦИИ) І МЕТОДОМ ХОРД І ДОТИЧНИХ З УКАЗАННОЙ.

ТОЧНОСТЬЮ І УРАХУВАННЯМ МОЖЛИВОЇ КРАТНОСТІ КОРНЕЙ.

(Пояснювальна записка до курсової роботу з дисципліни «Чисельні методы»).

Роботу виконали студенти 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. обчислюємо координату x перетину дотичній з віссю абсцис за такою формулою (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 () ко = 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 ко = 0 TextBox1. Value = ко 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)) 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²⁰ «If Range («a20 ») < 0 Then mn = mn + Range («a20 »).Text + «X²⁰ «.

If Range («a19 ») > 0 Then mn = mn + «+ «+ Range («a19 »).Text + «X¹⁹ «If Range («a19 ») < 0 Then mn = mn + Range («a19 »).Text + «X¹⁹ «.

If Range («a18 ») > 0 Then mn = mn + «+ «+ Range («a18 »).Text + «X¹⁸ «If Range («a18 ») < 0 Then mn = mn + Range («a18 »).Text + «X¹⁸ «.

If Range («a17 ») > 0 Then mn = mn + «+ «+ Range («a17 »).Text + «X¹⁷ «If Range («a17 ») < 0 Then mn = mn + Range («a17 »).Text + «X¹⁷ «.

If Range («a16 ») > 0 Then mn = mn + «+ «+ Range («a16 »).Text + «X¹⁶ «If Range («a16 ») < 0 Then mn = mn + Range («a16 »).Text + «X¹⁶ «.

If Range («a15 ») > 0 Then mn = mn + «+ «+ Range («a15 »).Text + «X¹⁵ «If Range («a15 ») < 0 Then mn = mn + Range («a15 »).Text + «X¹⁵ «.

If Range («a14 ») > 0 Then mn = mn + «+ «+ Range («a14 »).Text + «X¹⁴ «If Range («a14 ») < 0 Then mn = mn + Range («a14 »).Text + «X¹⁴ «.

If Range («a13 ») > 0 Then mn = mn + «+ «+ Range («a13 »).Text + «X¹³ «If Range («a13 ») < 0 Then mn = mn + Range («a13 »).Text + «X¹³ «.

If Range («a12 ») > 0 Then mn = mn + «+ «+ Range («a12 »).Text + «X¹² «If Range («a12 ») < 0 Then mn = mn + Range («a12 »).Text + «X¹² «.

If Range («a11 ») > 0 Then mn = mn + «+ «+ Range («a11 »).Text + «X¹¹ «If Range («a11 ») < 0 Then mn = mn + Range («a11 »).Text + «X¹¹ «.

If Range («a10 ») > 0 Then mn = mn + «+ «+ Range («a10 »).Text + «X¹⁰ «If Range («a10 ») < 0 Then mn = mn + Range («a10 »).Text + «X¹⁰ «.

If Range («a9 ») > 0 Then mn = mn + «+ «+ Range («a9 »).Text + «X⁹ «If Range («a9 ») < 0 Then mn = mn + Range («a9 »).Text + «X⁹ «.

If Range («a8 ») > 0 Then mn = mn + «+ «+ Range («a8 »).Text + «X⁸ «If Range («a8 ») < 0 Then mn = mn + Range («a8 »).Text + «X⁸ «.

If Range («a7 ») > 0 Then mn = mn + «+ «+ Range («a7 »).Text + «X⁷ «If Range («a7 ») < 0 Then mn = mn + Range («a7 »).Text + «X⁷ «.

If Range («a6 ») > 0 Then mn = mn + «+ «+ Range («a6 »).Text + «X⁶ «If Range («a6 ») < 0 Then mn = mn + Range («a6 »).Text + «X⁶ «.

If Range («a5 ») > 0 Then mn = mn + «+ «+ Range («a5 »).Text + «X⁵ «If Range («a5 ») < 0 Then mn = mn + Range («a5 »).Text + «X⁵ «.

If Range («a4 ») > 0 Then mn = mn + «+ «+ Range («a4 »).Text + «X⁴ «If Range («a4 ») < 0 Then mn = mn + Range («a4 »).Text + «X⁴ «.

If Range («a3 ») > 0 Then mn = mn + «+ «+ Range («a3 »).Text + «X³ «If Range («a3 ») < 0 Then mn = mn + Range («a3 »).Text + «X³ «.

If Range («a2 ») > 0 Then mn = mn + «+ «+ Range («a2 »).Text + «X² «If Range («a2 ») < 0 Then mn = mn + Range («a2 »).Text + «X² «.

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=KABL.

=0 Це було доведено відомими математиками Абелеи і Галуа.

———————————- [pic].

Знаки F (В) і F© разные Корень обнаружен.

СТОП.

B=C.

А=C.

[pic].

[pic].

F© < точность Знаки F (A) і F© разные.

З= (А+В) / 2.

Поиск коренів — начало.

Стоп Корень бонаружен.

F (B) -F (A) (хорда з головою, дотична з недостатком0).

Начало.