Метод січучих (метод хорд)

У цьому й наступному розділіРозглянемо модифікації методу Ньютона.

Як видно з формули (2.13), метод Ньютона вимагає для реалізації обчислення похідної, що обмежує його застосування. Метод січучих позбавлений цього недоліку. Якщо похідну замінити її наближенням:

f"(x n) ,

то замість формули (2.13) отримаємо

x n +1 = x n -. . (2.20)

Це означає, що дотичні замінені січними. Метод січучих є двокроковим методом для обчислення наближення x n +1 необхідно обчислити два попередні наближення x n та x n - 1 і, зокрема, на першій ітерації треба знати два початкові значення x 0 та x 1 .

Формула (2.20) є розрахунковою формулою методу січучих. На рис. 2.9 наведено геометричну ілюстрацію методу січучих.

Чергове наближення x n +1 виходить як точка перетину з віссю OXсічної, що з'єднує точки графіка функції f(x) з координатами ( x n -1 , f(x n - 1)) та ( x n, f(x n)).

Збіжність методу . Збіжність методу січучих встановлює наступна теорема.

Теорема 2.4 Нехай x* - простий корінь рівняння f(x) = 0, і в деякій околиці цього кореня функція fдвічі безперервно диференційована, причому f"(x) 0. Тоді знайдеться така мала -околиця кореня x* , що з довільному виборі початкових наближень x 0 та x 1 з цієї околиці ітераційна послідовність, визначена за формулою (2.20), сходиться і справедлива оцінка:

|x n+ 1 - x * | C|x n - x * | p , n 0, p= 1.618. (2.21)

Порівняння оцінок (2.15) та (2.21) показує, що p< 2, и метод секущих сходится медленнее, чем метод Ньютона. Но в методе Ньютона на каждой итерации надо вычислять и функцию, и производную, а в методе секущих - только функцию. Поэтому при одинаковом объеме вычислений в методе секущих можно сделать примерно вдвое больше итераций и получить более высокую точность.

Так само, як і метод Ньютона, при невдалому виборі початкових наближень (далеко від кореня) метод сік може розходитися. Крім того, застосування методу січучих ускладнюється через те, що в знаменник розрахункової формули методу (2.20) входить різниця значень функції. Поблизу кореня ця різниця мала, і метод втрачає стійкість.

Критерій закінчення. Критерій закінчення ітерацій методу січуть такий самий, як і для методу Ньютона. За заданої точності >

|x n - x n - 1 | < . (2.22)

Приклад 2.4.

Застосуємо метод січень для обчислення позитивного коренярівняння 4(1 - x 2) - e x= 0 з точністю = 10 -3 .

Корінь цього рівняння знаходиться на відрізку, оскільки f(0) = 3> 0, а f (1) = -e < 0. Подсчитаем вторую производную функции: f"(x) = -8 - e x . Умова f(x)f "(x) 0 виконується для точки b= 1. Як початкове наближення візьмемо x 0 = b= 1. Як друге початкове значення візьмемо x 1 = 0.5. Проведемо обчислення за розрахунковою формулою (2.20). Результати наведено у табл. 2.4.

Таблиця 2.4

	x n

Метод хибного становища

Розглянемо ще одну модифікацію методу Ньютона.

Нехай відомо, що простий корінь x* Рівняння f(x) = 0 знаходиться на відрізку [ a, b] і на одному з кінців відрізка виконується умова f(x)f"(x) 0. Візьмемо цю точку як початкове наближення. Нехай для певності це буде b. Покладемо x 0 = a.Будемо проводити з точки B =(b, f(b)) прямі через розташовані на графіку функції точки B nз координатами ( x n , f(x n), n = 0, 1, … . Абсциса точки перетину такої прямої з віссю OXє чергове наближення x n+ 1 .

Геометрична ілюстрація методу наведено на рис. 2.10.

Прямі цьому малюнку замінюють дотичні у методі Ньютона (рис. 2.8). Ця заміна ґрунтується на наближеній рівності

f"(x n) . (2.23)

Замінимо в розрахунковій формулі Ньютона (2.13) похідну f"(x n) правою частиноюнаближеної рівності (2.23). В результаті отримаємо розрахункову формулуметоду хибного становища:

x n +1 = x n -.. (2.24)

Метод помилкового положення має лише лінійну збіжність. Східність тим вища, що менше відрізок [ a, b].

Критерій закінчення. Критерій закінчення ітерацій методу хибного становища такий самий, як і методу Ньютона. При заданій точності > 0 обчислення потрібно вести доти, доки не буде виконано нерівність

|x n - x n - 1 | < . (2.25)

приклад 2.5.

Застосуємо метод помилкового положення для обчислення кореня рівняння x 3 + 2x - 11 = 0 з точністю = 10 -3 .

Корінь цього рівняння знаходиться на відрізку, оскільки f(1) = -8 < 0, а f(2) = 1 > 0. Для прискорення збіжності візьмемо більш вузький відрізок, оскільки f(1.9) < 0, а f(2) > 0. Друга похідна функції f(x) = x 3 + 2x - 11 дорівнює 6 x.Умова f(x)f"(x) 0 виконується для точки b= 2. Як початкове наближення візьмемо x 0 = a= 1.9. За формулою (2.24) маємо

x 1 = x 0 -. = 1.9 + 1.9254.

Продовжуючи ітераційний процес, отримаємо результати, наведені у табл. 2.5.

Таблиця 2.5

	x n

Метод січучих

При знаходженні нулів функції f, для якої обчислення f"(x)утруднено, часто найкращим вибором, Чим метод Ньютона, є метод посічених. У цьому алгоритмі починають із двома вихідними числами x 1 і х 2 . На кожному кроці x k+1 отримують з x k і x k-1 як єдиний нуль лінійної функції, що приймає значення f(x k) x k і f(x k-1) x k-1 . Ця лінійна функціяпредставляє січучу до кривої у = f(х), що проходить через її точки з абсцисами x k і x k-1 - звідси назва метод січучих.

Нехай - абсциси кінців хорди, - рівняння сік, що містить хорду. Знайдемо коефіцієнти та із системи рівнянь:

Віднімемо з першого рівняння друге:

Потім знайдемо коефіцієнти та:

Рівняння набуває вигляду:

Таким чином, тепер можемо знайти перше наближення до кореня, отримане методом січення:

Тепер візьмемо координати та й повторимо всі виконані операції, знайшовши нове наближення до кореня. Таким чином, ітераційна формуламетоду січучих має вигляд:

Повторювати операцію слід до тих пір, поки не стане менше чи одно заданому значеннюпохибки.

Приклад розв'язання задачі методом січень

У Delphi напишемо програмудля розрахунку коренів рівнянь методом січень:

procedure TForm1.Button1Click(Sender: TObject);

var ck1, x0, x1, x2, eps:real;

x1:=StrToFloat(Form1.Edit1.Text);

x2:=StrToFloat(Form1.Edit2.Text);

eps:=StrToFloat(Form1.Edite.Text);

(Уточнення кореня за ітераційною формою)

x2:=x1-(x0-x1)*f(x1)/(f(x0)-f(x1));

until abs(x2-x1)

(Прикінцеві обчислення)

ck2:= (ck1-c01)/2+c02;

ck3:= (-ck1+c01)/2+c03;

ck4:=(-2*ck1+2*c01)/2+c04;

(Виведення результатів у полі Memo)

Form1.Memo2.clear;

Form1.Memo2.Lines.Add ("Метод поділу навпіл");

Form1.Memo2.Lines.Add

("ck1 =" + FloatToStr(ck1));

Form1.Memo2.Lines.Add

("ck2 =" + FloatToStr(ck2));

Form1.Memo2.Lines.Add

("ck3 =" + FloatToStr(ck3));

Form1.Memo2.Lines.Add

("ck4 =" + FloatToStr(ck4));

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

• 1 Геометричний опис методу січучих
• 2 Алгебраїчне опис методу січучих
• 3 Метод хорд з ітераційною формулою
• 4 Приклад використання методу січень
• 5 Збіжність методу січучих
• 6 Критерій та швидкість збіжності методу хорд
• 7 Історична довідка
• 8 Приклад коду
• 9 Модифікації
• 10 Див.
• 11 Література
• 12 Примітки
• 13 Посилання

Геометричний опис методу січучих

Шукатимемо нуль функції. Виберемо дві початкові точки і проведемо через них пряму. Вона перетне вісь абсцис у точці. Тепер знайдемо значення функції з абсцисою. Тимчасово вважатимемо коренем на відрізку. Нехай точка має абсцис і лежить на графіку. Тепер замість точок і ми візьмемо точку та точку. Тепер з цими двома точками проробимо ту ж операцію і так далі, тобто отримуватимемо дві точки і повторюватимемо операцію з ними. Відрізок, що з'єднує останні дві точки, перетинає вісь абсцис у точці, значення абсцис якої можна приблизно вважати коренем. Ці дії потрібно повторювати до того часу, доки отримаємо значення кореня з необхідним наближенням.

Алгебраїчне опис методу січучих

Нехай - абсциси кінців хорди, - рівняння сік, що містить хорду. Знайдемо коефіцієнти та із системи рівнянь:

Віднімемо з першого рівняння друге:

Потім знайдемо коефіцієнти та:

Рівняння набуває вигляду:

Таким чином, тепер можемо знайти перше наближення до кореня, отримане методом січення:

Тепер візьмемо координати та й повторимо всі виконані операції, знайшовши нове наближення до кореня. Таким чином, ітераційна формула методу січених має вигляд:

Повторювати операцію слід до того часу, поки стане менше чи дорівнює заданому значенню похибки.

Метод хорд з ітераційною формулою

Перші три ітерації методу хорд. Синім намальовано функцію f(x), червоними проводяться хорди.

Іноді методом січучих називають метод з ітераційною формулою

Цей метод вважатимуться різновидом методу простої ітерації, і він має меншу швидкість збіжності. Далі для певності цей метод називатимемо методом хорд, а метод, описаний у попередньому розділі, методом січучих.

Приклад використання методу січень

Вирішимо рівняння методом січучих. Задамося точністю ε=0.001 і візьмемо як початкові наближення і кінці відрізка, на якому відокремлений корінь: і, числові значення і вибрані довільно. Обчислення ведуться доти, доки виконується нерівність.

У прикладі, в значення підставляється, а значення підставляється. Значення це буде числове значення, отримане за цією формулою. надалі підставляємо у формулу значення, а значення.

За цією формулою послідовно отримуємо (підкреслені вірні цифри): (картинка з методу хорд, але не січучих, прохання розділити розділи)

Метод січучих. Перший випадок; ; ; ; ; ; ; ; ; ;

Перевіримо, що метод працює і в тому випадку, якщо й обрані по одну й ту саму сторону від кореня (тобто якщо корінь не відділений на відрізку між початковими наближеннями). Візьмемо для того ж рівняння і. Тоді: (картинка вже не з методу січучих, а з методу дихотомії)

Метод січучих. Другий випадок; ; ; ; ; ; ; ;

Ми отримали те саме значення кореня за таку ж кількість ітерацій.

Збіжність методу січучих

Ітерації методу січучих сходяться до кореня, якщо початкові величини and досить близькі до кореня. Метод січучих є швидким. Порядок збіжності α дорівнює золотому перерізу

Таким чином, порядок збіжності більший за лінійний, але не квадратичний, як у спорідненого методу Ньютона.

Цей результат справедливий, якщо двічі диференційована і корінь не є кратним.

Як і більшості швидких методів, для методу січучих важко сформулювати умови збіжності. Якщо початкові точки досить близькі до кореня, то метод сходиться, але немає загального визначення достатньої близькості. Східність методу визначається, наскільки функція «хвилясті» в. Наприклад, якщо в інтервалі є точка, в якій процес може не сходитися.

Критерій та швидкість збіжності методу хорд

Якщо - двічі безперервно диференційована функція, і знак зберігається на проміжку, то отримані наближення будуть сходитися до кореня монотонно. Якщо корінь рівняння знаходиться на відрізку, похідні і на цьому проміжку безперервні і зберігають постійні знаки і, то можна довести, що похибка наближеного рішення прагне нуля, тобто метод сходиться і сходиться зі швидкістю геометричної прогресії (при цьому кажуть, що він має лінійну швидкість збіжності).

Історична довідка

Першим, хто міг знайти наближені рішення кубічних рівнянь, був Діофант, тим самим заклавши основу методу хорд. Роботи Діофанта, що збереглися, повідомляють про це. Однак першим, хто зрозумів його методи, був Ферма у XVII столітті, а першим, хто дав пояснення методу хорд, був Ньютон (1670-ті рр.).

Приклад коду

Приклад функції обчислення кореня методом хорд на відрізку Сі/Сі++.

Double f(double x) (return sqrt(fabs(cos(x))) - x; // Замінити функцією, коріння якої ми шукаємо) // a, b - межі хорди, epsilon - необхідна похибка double findRoot(double a, double b, double epsilon) ( while(fabs(b - a) > epsilon) ( a = b - (b - a) * f(b)/(f(b) - f(a)); b = a - (a - b) * f(a)/(f(a) - f(b)); ) // a - i-1, b - i-тий члени return b;

Модифікації

Метод хибного становища (англ.)відрізняється від методу, що січуть тільки тим, що щоразу беруться не останні 2 точки, а ті точки, які знаходяться навколо кореня.

Див. також

• Метод Ньютона (метод дотичних)
• Метод простої ітерації
• Зворотня параболічна інтерполяція

Література

1. Демидович Б.П. та Марон І.А. Основи обчислювальної математики. – Наука, 1970. – С. 664.
2. Бахвалів, Жидків, Кобельків. Чисельні методи. – Наука. - ISBN 5-94774-060-5.

Примітки

1. Алгебра
2. Математика та її історія. Джон Стілвелл

Посилання

• Рішення рівнянь методом хорд онлайн
• «Методи рішення алгебраїчних рівнянь» на сайті www.petrsu.ru
• "Методи дихотомії" на сайті www.epikoiros.narod.ru
• Ю. Губар, Курс «Вступ до математичне моделювання» Лекція 4: Чисельні методи розв'язання нелінійних рівнянь // Інтуїт.ру, 15.03.2007

метод хорд, метод хорд gif, метод хорд онлайн, метод хорд приклад

Метод хорд Інформація про

МІНІСТЕРСТВО ОСВІТИ І НАУКИ РФ

ФЕДЕРАЛЬНА ДЕРЖАВНА БЮДЖЕТНА

ОСВІТНЯ УСТАНОВА

ВИЩОЇ ПРОФЕСІЙНОЇ ОСВІТИ

«САМАРСЬКИЙ ДЕРЖАВНИЙ

АРХІТЕКТУРНО-БУДІВЕЛЬНИЙ УНІВЕРСИТЕТ»

Кафедра прикладної математикита обчислювальної техніки

ExcelіMathcad

МЕТОДИЧНІ ВКАЗІВКИ

до виконання лабораторних робіт

з дисципліни «Обчислювальна математика»

Розв'язання нелінійних рівнянь уExcel таMathcad: Метод. указ. / Упоряд. , - Самара: ЗДАСУ, 20с.

Методичні вказівки розроблено відповідно до Державного освітнім стандартомвивчення дисципліни "Обчислювальна математика".

Розглянуто реалізацію чисельних методів при вирішенні нелінійних рівнянь та систем рівнянь в Excel та MathCad. Наведено варіанти завдань для індивідуального виконання та питання для самоконтролю та тестування.

Призначені для студентів спеціальності 230201 – « Інформаційні системита технології» всіх форм навчання.

Рецензент до. ф-м. н.

Ó , складання, 2012

ã ЗДАСУ, 2012

1.2 Відділення коріння
1.5 Метод хорд
1.6 Метод Ньютона (дотичних)
1.7 Комбінований метод
1.8 Метод ітерацій
2.2 Вирішення систем нелінійних рівнянь методом Ньютона
3 Завдання до лабораторних робіт
Лабораторна № 1. Відділення коренів та стандартні інструменти вирішення не лінійного рівняння
Лабораторна №2. Порівняння методів уточнення коренів нелінійного рівняння
Лабораторна №3. Розв'язання систем нелінійних рівнянь
Лабораторна № 4. Програмування методів розв'язання нелінійних рівнянь та систем
4 Питання та тести для самоконтролю

1 Розв'язання нелінійного рівняння

1.1 Загальні відомості про рішення нелінійного рівняння

Як правило, нелінійне рівняння загального вигляду f(х)=0неможливо вирішити аналітично. Для практичних завдань достатньо знайти наближене значення x, у певному сенсі близьке до точного вирішення рівняння хточн.

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

Досягнута точність може оцінюватися або «за функцією» (у знайденій точці x, функція досить близька до 0, тобто виконується умова | f(x)|≤ef, де efнеобхідна точність по осі ординат), або «за аргументом» (знайдено досить невеликий відрізок [ a,b], Усередині якого знаходиться корінь, тобто. | b-a|≤ex, де exпотрібна точність по осі абсцис).

1.2 Відділення коріння

Відділення коренів може здійснюватися поєднанням графічногоі аналітичногодослідження функції. Таке дослідження спирається на теорему Вейєрштраса, відповідно до якої для безперервної на відрізку [ a,b]функції f(х) та будь-якого числа y, що відповідає умові f(a)≤y≤f(b), існує на цьому відрізку точка x, в якій функція дорівнює y. Отже, для безперервної функціїдостатньо знайти відрізок, на кінцях якого функція має різні знаки, і можна бути впевненим, що на цьому відрізку є корінь рівняння f(х)=0.

Для низки методів уточнення бажано, щоб знайдений першому етапі відрізок містив лише одне корінь рівняння. Ця умова виконується, якщо функція на відрізку монотонна. Монотонність можна перевірити або за графіком функції, або за знаком похідної.

прикладЗнайти з точністю до цілих всікоріння нелінійного рівняння y(x)=x3 ‑ 10x + 7 = 0а) побудувавши таблицю та б) побудувавши графік. Знайти корінь рівняння на виділеному відрізку, використовуючи опції «Підбір параметра» та «Пошук рішення».

РішенняСтворимо в Excel таблицю, Що містить аргументи та значення функції і по ній побудуємо точкову діаграму . На малюнку 1 наведено знімок рішення.

На графіку видно, що рівняння має три корені, що належать відрізкам [-4, -3], та . Ці відрізки можна виявити і спостерігаючи за зміною знаків функції таблиці. За побудованим графіком можна дійти невтішного висновку, що у зазначених відрізках функція f(x) монотонна і, отже, кожному з них міститься лише з одному кореню.

Такий самий аналіз може бути виконаний і в пакеті Mathcad. Для цього достатньо набрати визначення функції f(x) , використовуючи оператор присвоювання (:=) та природні загальноприйняті позначення математичних операційі стандартних функцій, встановити цикл для зміни аргументу, наприклад, а потім вивести на екран таблицю значень функції (розташованими в одному рядку командами x= f(x)= ) та графік. Цикл можна задати, наприклад, командою x:=-5,-4.5…5 . Крок циклу формується шляхом завдання початкового і наступного за ним значень змінної, а перед кінцевим значенням змінної ставиться точка з комою, яка візуально відображається на екрані у вигляді крапки.

https://pandia.ru/text/78/157/images/image002_56.jpg" width="640" height="334">

Рисунок 1 – Таблиця та графік для відділення коріння нелінійного рівняння

1.3 Уточнення коренів стандартними засобами Excel та Mathcad

У всіх методах уточнення коренів необхідно задати початкове наближення, яке потім уточнюватиметься. Якщо рівняння має кілька коренів, в залежності від обраного початкового наближення буде знайдено одне з них. При невдало обраному початковому наближенні рішення може бути знайдено. Якщо в результаті першого етапу розрахунків вже виділено відрізок, що містить єдиний корінь рівняння, як початкове наближення можна взяти будь-яку точку цього відрізка.

В Excel для уточнення значень коренів можна використовувати опції "Підбір параметра" та "Пошук рішення". Приклад оформлення рішення наведено на рисунках 2 та 3.

https://pandia.ru/text/78/157/images/image004_31.jpg" width="501" height="175 src=">

Рисунок 3 – Результати використання засобів вирішення рівнянняExcel

У Mathcad для уточнення коренів рівняння можна використовувати функцію root(….) або блок рішення. Приклад використання функції root(…) наведено малюнку 4, а блоку рішення малюнку 5. Слід звернути увагу, що у блоці рішення (після заголовка блоку Given) між лівою та правою частинами рівняння повинен стояти жирний знак рівності(тотожності), який можна отримати вибором з відповідної палітри інструментів, або натисканням клавіші одночасно Ctrlі = .

243" height="31">

Рисунок 5 – Рішення рівняння з використанням блоку розв'язанняMathcad

Як бачимо, кожен стандартний інструмент знаходить рішення рівняння з певною точністю. Ця точність залежить від методу, який використовується в пакеті та, певною мірою, налаштувань пакета. Керувати точністю результату тут досить складно, а то й неможливо.

У той же час дуже просто побудувати власну таблицю або написати програму, що реалізують один із методів уточнення коренів. Тут можна використовувати критерії точності розрахунку, що задаються користувачем. При цьому досягається і розуміння процесу розрахунків без опори на принцип Митрофанушки: «Візник є, довезе».

Далі розглянуто кілька найпоширеніших методів. Зазначимо очевидний момент: за інших рівних умовах той методуточнення коренів буде більш ефективним, в якому результат з тією ж похибкою знайдено з меншимчислом обчислень функції f(x)(при цьому досягається і максимальна точність при однаковій кількостіобчислень функції).

1.4 Метод розподілу відрізка навпіл

У цьому вся методі кожному кроці відрізок ділиться на дві рівні частини. Потім порівнюють знаки функції на кінцях кожної з двох половинок (наприклад, за знаком твору значень функцій на кінцях), визначають ту з них, в якій міститься рішення (знаки функції на кінцях повинні бути різні), і. звужують відрізок, переносячи в знайдену точку його межу ( аабо b). Умовою закінчення служить трохи відрізка, де міститься корінь («точність по x»), або близькість до значення значення функції в середині відрізка («точність по y»). Рішенням рівняння вважають середину відрізка, знайденого на останньому етапі.

приклад. Побудувати таблицю для уточнення кореня рівняння x3 –10 x+7=0 на відрізку [-4, -3] шляхом розподілу відрізка навпіл. Визначити скільки кроків треба зробити методом поділу відрізка навпіл і яка при цьому досягається точність по х,для досягнення точності з y, що дорівнює 0,1; 0,01; 0, 001.

РішенняДля вирішення можна використовувати табличний процесор Excel, що дозволяє автоматично продовжувати рядки. На першому кроці заносимо в таблицю значення лівого та правого кінців вибраного початкового відрізка та обчислюємо значення середини відрізка з=(a+b)/2, а потім вводимо формулу для обчислення функції у точці a (f(a)) і розтягуємо (копіюємо) її для обчислення f(c) та f(b). В останньому стовпці обчислюємо вираз ( b-a)/2, що характеризує ступінь точності обчислень. Усі набрані формули можна скопіювати до другого рядка таблиці.

На другому етапі необхідно автоматизувати процес пошуку тієї половини відрізка, де міститься корінь. Для цього використовується логічна функція ЯКЩО ( Меню: ВставкаФункціяЛогічні). Для нового лівого краю відрізка ми перевіряємо істинність умови f(a)*f(c)>0, якщо воно вірне, то ми як нове значення лівого кінця відрізка беремо число c a, c a. Аналогічно для нового правого краю відрізка ми перевіряємо істинність умови f(c)* f(b)>0, якщо воно вірне, то ми як нове значення правого кінця відрізка беремо число c(Т. К. Ця умова показує, що кореня на відрізку [ c, b] ні), інакше залишаємо значення b.

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

Ітераційний процес завершується, коли чергове значення останньому стовпці стає меншим, ніж заданий показник точності ex. При цьому значення середини відрізка в останньому наближенні приймається як наближене значення шуканого кореня нелінійного рівняння. На малюнку 6 наведено знімок рішення. Для побудови аналогічного процесу в Mathcad можна використовувати бланк, подібний до наведеного на малюнку 7. Число кроків N може змінюватись до досягнення в таблиці результатів необхідної точності. При цьому таблиця автоматично подовжуватиметься або коротшатиме.

Отже, одним із трьох коренів нелінійного рівняння x 3 – 10x+ 7=0, знайденим з точністю e=0,0001, є x= - 3,46686. Як бачимо, він справді належить відрізку [-4; -3].

https://pandia.ru/text/78/157/images/image018_6.jpg" width="563" height="552 src=">

Рисунок 7 – Уточнення кореня методом поділу відрізка навпілMathcad

1.5 Метод хорд

У цьому методі нелінійна функція f(x)на відокремленому інтервалі [ а, b] замінюється лінійною – рівнянням хорди, т. е. прямий сполучає граничні точки графіка на відрізку. Умова застосування методу – монотонність функції на початковому відрізку, що забезпечує єдиність кореня у цьому відрізку. Розрахунок за методом хорд аналогічний розрахунку методом поділу відрізка навпіл, але тепер на кожному кроці нова точка xвсередині відрізка [ a, b] розраховується за будь-якою з наступних формул:

(х) > 0 ), або права його межа: x0 = b(якщо f(b) f"(х)>0). Розрахунок нового наближення на наступному кроці i+1 проводиться за формулою:

https://pandia.ru/text/78/157/images/image021_4.jpg" width="596" height="265 src=">

Рисунок 8 – Уточнення кореня методом дотичних до Excel

Розрахунки Mathcad виконуються аналогічно. При цьому значне полегшення доставляє наявність у цьому пакеті оператора, що автоматично обчислює похідну функції.

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

За певних умов може використовуватись спрощений метод Ньютона, У якому похідна обчислюється лише один раз – у початковій точці. При цьому використовується видозмінена формула

.

Природно, що спрощений метод зазвичай вимагає більшого числакроків.

Якщо обчислення похідної пов'язане з серйозними труднощами (наприклад, якщо функція задана не аналітичним виразом, а програмою, що обчислює її значення), використовується модифікований методНьютона, який отримав назву - метод січучих. Тут похідна приблизно обчислюється за значеннями функції у двох послідовних точках, тобто використовується формула

.

У методі січучих необхідно задатися не однією, а двома початковими точками – x0 і x1 . Крапка x1зазвичай задається зрушенням x0до іншої межі відрізка на малу величину, наприклад, 0.01.

1.7 Комбінований метод

Можна показати, що якщо на початковому відрізку у функції f(x)зберігаються незмінними знаки першої та другої похідних, то методи хорд і Ньютона наближаються до кореня з різних. У комбінованому методідля підвищення ефективності на кожному кроці використовує обидва алгоритми одночасно. При цьому інтервал, де міститься корінь, скорочується з обох сторін, що зумовлює іншу умову закінчення пошуку. Пошук можна припинити, як тільки всередині інтервалу, отриманого на черговому кроці значення функції стане по модулю меншим, ніж попередньо заданої похибки ef.

Якщо, відповідно до сформульованого вище правила, метод Ньютона застосовується до правої межі відрізка, для обчислень використовуються формули:

https://pandia.ru/text/78/157/images/image025_10.gif" width="107" height="45 src=">.

Якщо метод Ньютона застосовується до лівої межі, – у попередніх формулах змінюються місцями позначення aі b.

1.8 Метод ітерацій

Для застосування цього методу вихідне рівняння f(x)=0перетворюють на вигляд: x=y(х). Потім обирають початкове значення х0і підставляють його в ліву частину рівняння, отримуючи, загальному випадку, x1 = y(х0)¹ х0¹ y(х1), оскільки х0взято довільно і не є коренем рівняння. Отримане значення х1розглядають як чергове наближення до кореня. Його знову підставлять у праву частину рівняння та одержують наступне значення х2=y(х1)). Розрахунок продовжують за формулою хi+1=y(хі). Послідовність, що утворюється таким чином: х0, х1, х2, х3 х4,...за певних умов сходитися до кореня хточн.

Можна показати, що ітераційний процес сходиться за умови
|y’ (x) | < 1 на [a, b].

Існують різні способиперетворення рівняння f(x)= 0 до виду y(х) = х, причому в конкретному випадку одні з них приведуть до того, що сходить, а інші - до процесу обчислень, що розходиться.

Один із способів, полягає у застосуванні формули

https://pandia.ru/text/78/157/images/image027_10.gif" width="188" height="44 src=">

де М= max | y’ (x)| на [ a, b].

2 Розв'язання систем нелінійних рівнянь

2.1 Загальні відомості щодо вирішення систем нелінійних рівнянь

Систему nнелінійних рівнянь з nневідомими x1, x2, ..., xnзаписують у вигляді:

де F1, F2,…, Fn- Функції незалежних змінних, серед яких є нелінійні.

Як і у разі систем лінійних рівнянь, рішенням системи є такий вектор X*, який при підстановці звертає одночасно всі рівняння системи до тотожності.

https://pandia.ru/text/78/157/images/image030_8.gif" width="191" height="56">

Початкові значення x0 і y0 визначаються графічно. Для знаходження кожного наступного наближення (xi+1 , yi+1 ) використовують вектор значень функцій та матрицю значень їх перших похідних, розраховані в попередній точці (xi, yi) .

https://pandia.ru/text/78/157/images/image032_5.gif" width="276" height="63 src=">

Для розрахунку нових наближень на кроці i+1використовується матрична формула

https://pandia.ru/text/78/157/images/image034_4.gif" width="303" height="59 src=">.

Наведені формули особливо легко записати в Mathcad, де є оператори для обчислення похідних та дій з матрицями. Однак при правильному використанні матричних операційці формули досить просто записуються і Excel. Щоправда, тут доведеться заздалегідь одержати формули для обчислення похідних. Для аналітичного обчислення похідних також можна використовувати Mathcad.

2.3 Розв'язання систем нелінійних рівнянь методами ітерацій

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

https://pandia.ru/text/78/157/images/image036_5.gif" width="114" height="57 src=">.

Якщо одне з рішень системи та початкові значення x0 і y0 лежать в області D, що задається нерівностями: a ≤ x ≤ b, c ≤ y ≤ d, то розрахунок за методом простих ітераційсходиться при виконанні в області Dспіввідношень:

https://pandia.ru/text/78/157/images/image038_5.gif" width="75 height=48" height="48">< 1.

У методі ітерацій Зейделядля кожного розрахунку використовують вже знайдені найточніші значення кожної змінної. Для випадку двох змінних, що розглядається, така логіка призводить до формул.

0 " style="border-collapse:collapse;border:none">

Інструмент (опція)

Початкове наближення

Коріньx

f(x)

3. Відсортувати отримані результати за точністю рішення.

Далеко не завжди буває зручно знаходити аналітичний вираз для похідної функції, у такому разі можна використовувати метод сікних.

Для початку ітераційного процесу необхідно задати два початкові наближення х 0 і х 1 .

Якщо х 0 і x 1 розташовані досить близько один до одного, то похідну можна замінити її наближеним значенням у вигляді відношення збільшення функції рівного
до відношення збільшення аргументу рівного ( x 1 – x 0 ):

(1.4)

Таким чином, формула методу січучих може бути отримана з формули Ньютона (1.2) заміною похідною виразом (1.4) і записана у вигляді:

(1.5)

Однак слід пам'ятати, що при цьому немає необхідності, щоб значення функції
і
обов'язково мали різний знак, як у методі половинного поділу.

Процес знаходження кореня при використанні методу січучих можна вважати закінченим, коли виконується така умова:

(6)

Метод січучих дещо поступається методу Ньютона у швидкості збіжності, проте не вимагає обчислень похідної лівої частини рівняння.

Таким чином, для реалізації методу посічених необхідно:

Результатом проведення лабораторної роботиє програма, що реалізує один з описаних методів з рішенням контрольного прикладу згідно з отриманим індивідуальним завданням.

1. Вирішення систем лінійних рівнянь

   1. загальні положення

При вирішенні великого класу прикладних завдань виникає потреба у знаходженні коріння СЛАУ. Методи вирішення СЛАУ можна розділити на два великі класи: точні та ітераційні.

Точні методи вирішення, наприклад метод Гауса,дають, взагалі кажучи, точне значення коренів СЛАУ, при цьому при коректному складанні програми точність визначається лише похибками, пов'язаними із округленням та поданням чисел в ЕОМ.

Ітераційні методи рішення СЛАУ характеризується тим, що точне рішення системи вони можуть, взагалі кажучи, давати лише як межу певної нескінченної послідовності векторів. Вихідне наближення при цьому розшукується якимось іншим способом або задається довільно. При виконанні певних вимог можна отримати досить швидко схожий до рішення ітераційний процес. До цього класу методів належать: метод ітераційта метод Зейделя.

1. Метод Гауса

Розглянемо завдання розв'язання системи рівнянь виду:

(2.1)

Відомо, що система (2.1) має єдине рішення, якщо її невироджена матриця (тобто визначник матриці відмінний від нуля). У разі виродженості матриці система може мати нескінченну кількість рішень (якщо ранг матриці та ранг розширеної матриці, отриманої додаванням до стовпця вільних членів рівні) або не мати рішень зовсім (якщо ранг матриці та розширеної матриці не збігаються).

Систему (2.1) можна записати в матрично-векторній формі АХ = В,

де А - матриця коефіцієнтів системи, що містить n рядків та n стовпців;

У - заданий вектор правих частин;

Х – шуканий вектор.

Метод Гауса заснований на відомому зі звичайного шкільного курсу алгебри метод винятків. Комбінуючи будь-яким чином рівняння системи, домагаються того, що у всіх рівняннях, крім одного, буде виключено одне з невідомих. Потім виключають інше невідоме, третє тощо.

Розглянемо систему рівнянь розміру
. Алгоритм гауссового виключення складається з кількох кроків. Якщо система записана у вигляді (2.1), то перший крок полягає у виключенні з останніх n-1 рівнянь. Це досягається відніманням з другого рівняння першого, помноженого на
, з третього рівняння першого, помноженого на
, і т.д. Цей процес призводить до перетвореної системи рівнянь:

(2.2)

,
, i, j=2,….,n.

Застосовуючи тепер той самий процес до останніх n-1 рівнянь системи (2.2), виключаємо з останніх n-2 рівнянь і т.д., доки вся система не приведеться до трикутної форми:

, (2.3)

де верхні індекси, власне кажучи, вказують, скільки разів змінювалися відповідні коефіцієнти. Цим завершується фаза прямого виключення (або приведенням до трикутної форми) алгоритму гауссового виключення. Рішення трикутної системи (2.3) тепер легко виходить на фазі зворотної підстановки, під час якої рівняння системи (2.3) вирішуються у порядку:

(2.4)

При цьому всі діагональні коефіцієнти мають бути відмінними від нуля.

Існує велика кількість модифікацій обчислювальних схем, що реалізують метод Гауса. Як приклад розглянемо компактну схему Гауса. Для прикладу обрано СЛАУ 3-го порядку.

4*x1 - 9*x2 + 2*x3 = 2

2 * x 1 - 4 * x 2 + 4 * x 3 = 3

1*x 1 + 2*x 2 + 2*x 3 = 1,

яка в матричній формі записується у вигляді:

(2.5)

Перший основний крок гауссового виключення полягає у виключенні першої змінної x 1 з другого та третього рівнянь. Якщо з другого рівняння системи відняти перше, помножене на 0.5, і третього рівняння відняти перше, помножене на –0.25, то отримаємо еквівалентну систему рівнянь:

(2.6)

Другий основний крок полягає у виключенні із третього рівняння. Це може бути зроблено відніманням з третього рівняння другого, помноженого на –0.5, що призводить до системи виду:

(2.7)

Зроблені операції називаються елементарними перетвореннями рядків. До цього моменту завершується перша частина алгоритму гауссового виключення, яку зазвичай називають прямим винятком або приведенням до трикутної форми. Ця частина завершується тоді, коли всі елементи останнього рядка системи, крім правого, звертаються в нуль.

Друга частина алгоритму полягає у вирішенні отриманої верхньої трикутної системи. Це легко здійснюється за допомогою процесу зворотної підстановки. Останнє рівняння системи (2.7) має вигляд 4 x 3 =2.5 . Отже, x 3 =0.625 . Підставляючи тепер це значення у друге рівняння: 0.5 . x 2 +3 . 0.625=2 .

Звідси x 2 =0.25 . Підстановка цих значень і у перше рівняння дає або x 1 =0.75 . Щоб перевірити знайдене рішення, виконаємо множення

,

результат, якого збігається із правою частиною (2.5).

Процес гауссового виключення можна дуже компактно записати як алгоритму.

Прямий виняток

для k=1,….., n-1,

для i=k+1,….n:

;

для j=k,…..,n:

Зворотнє встановлення

для k=n, n-1,….., 1:

При складанні програми для ЕОМ, що реалізує цей алгоритм, слід звернути увагу на те, що елементи, що послідовно перетворюються в ході цього процесу
можна записувати в ті ж осередки пам'яті, де розташовувалися елементи вихідної матриці . На це вказує п'ятий рядок алгоритму. Якщо це зроблено, то вихідна матриця, зрозуміло, буде зіпсована.

При розробці алгоритму, що реалізує метод Гауса, на першому етапі рекомендується перетворити вихідну матрицю на вигляд, коли на головній діагоналі вибудовуються максимальні по абсолютної величиниКоефіцієнти. При цьому якщо хоча б одне значення коефіцієнта, що стоїть на головній діагоналі, дорівнює нулю, застосовувати метод Гауса не можна.