Модифікований метод Ньютона.

Перерахуємо недоліки методу Ньютона, на усунення яких спрямовані різні його модифікації:

складність завдання початкового наближення, якого метод сходиться;

необхідність обчислення на кожній ітерації матриці Якобі, що може вимагати суттєвих обчислювальних витрат;

необхідність вирішення кожної ітерації системи лінійних алгебраїчних рівнянь;

вимога невиродженості матриці Якобі.

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

Метод Ньютона зі шматково-постійною матрицею.

Щоб зменшити обчислювальні витрати на ітерації, матриця Якобі у цій модифікації залишається постійною протягом кількох кроків. Число кроків m, на яких Jпостійна, задається в такій модифікації як параметр, або момент перерахування матриці Якобі визначається умовою

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

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

Метод Ньютона-Рафсона.

Щоб забезпечити збіжність методу обраного початкового наближення, застосовується модифікація, звана методом Ньютона-Рафсона. Обчислення (k+ 1) -го наближення у цій модифікації здійснюється за правилом

де - параметр, значення якого на k-ї ітерації вибирається з умови

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

Методи продовження за параметром.

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

Нехай під час вирішення системи

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

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

Як можна вибрати функції

Розіб'ємо відрізок крапками на інтервалів. Отримаємо шукану послідовність систем:

Метод Ньютона для погано обумовлених завдань.

Якщо матриця Якобі погано зумовлена, похибка вирішення лінійної системи.

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

у разі погано обумовлених матриць при обчисленні вектора поправок залучають систему

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

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

x = x -α f(x) f(x).(3.56)

Вибір α здійснюється таким чином, щоб

f(x) → min;

це гарантує виконання нерівності

f(x) ≤ f(x).

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

Метод Марквардта

Цей метод є комбінацією методів Коші і Ньютона, в якій вдало поєднуються позитивні властивості обох методів. Водночас під час використання методу Марквардта потрібноінформація про значення других похідних цільової функції. Вище було зазначено, що градієнт вказує напрямок найбільшого локального збільшення функції, а рух у напрямку, протилежному градієнту, з точки х(0) , розташованої на значній відстані від точки мінімуму х*,зазвичай призводить до суттєвого зменшення цільової функції. З іншого боку, напрями ефективного пошуку навколо точки мінімуму визначаються за методом Ньютона. Проста ідеяоб'єднання методів Коші та Ньютона було покладено в основу алгоритму, розробленого Марквардтом у 1963 р. Відповідно до цього методу напрямок пошуку визначається рівністю

s(x(k)) = – [Н(k) + λ (k) I] -1 f (x(k)). (3.57)

При цьому у формулі (3.42) слід покласти α(k) = +1, оскільки параметр λ дозволяє не тільки змінювати напрямок пошуку, але й регулювати довжину кроку. Символом Iтут позначена одинична матриця, т. е. матриця, всі елементи якої дорівнюють нулю, крім діагональних елементів, рівних +1. на початковій стадіїпошуку параметру λ (0) приписується велике значення(наприклад, 10 4), так що

[Н(0) + λ (0) I] -1 = [λ (0) I] -1 = I. (3.58)

Таким чином, великим значеннямλ (0) відповідає напрямок пошуку s( x (0)) → f (x(0)). З формули (3.57) можна зробити висновок, що при зменшенні λ до нуля s(x)змінюється від напрямку, протилежного градієнту, до напрямку, що визначається методом Ньютона. Якщо після першого кроку отримано точку з меншим значенням цільової функції (тобто. f(х (1)) < f(x(0))), слід вибрати λ (1)< λ (0) и реализовать еще один шаг; в противном случае следует положить λ (0) = βλ (0) , где β >1, і знову реалізувати попередній крок. Нижче наведено кроки алгоритму.

Алгоритм Марквардта

Крок 1. х(0) - початкове наближення до х *; М- максимальна (допустима) кількість ітерацій; ε-параметр збіжності.

Крок 2.Покласти k= 0, λ (0) = 10 4 .

Крок 3. Обчислити компоненти f (x(k)).

Крок 4. Чи виконується нерівність

|| f (x(k))||< ε?

Так: перейти до кроку 11.

Крок 5. Чи виконується нерівність k ≥ M?

Так: перейти до кроку 11.

Ні: перейти до наступного кроку.

Крок 6. Обчислити s(x(k)) = – [Н(k) + λ (k) I] -1 f (x(k)).

Крок 7.Покласти x = x s(x).

Крок 8. Чи виконується нерівність f(x) < f(x)?

Так: перейти до кроку 9.

Ні: перейти до кроку 10.

Крок 9.Покласти λ(k+1) = ½λ(k) та k = k+ 1. Перейти до кроку 3.

Крок 10.Покласти λ(k) = 2λ(k). Перейти до кроку 6.

Крок 11. Друк результатів та зупинок.

Метод Марквардта характеризується відносною простотою, властивістю зменшення цільової функції при переході від ітерації до ітерації, високою швидкістю збіжності в околиці точки мінімуму х*, атакож відсутністю процедури пошуку вздовж прямої. Головний недолік методу полягає у необхідності обчислення Н(k) та подальшого вирішення системи лінійних рівнянь, що відповідає (3.57). Цей метод широко використовується при вирішенні завдань, у яких f(x)записується як суми квадратів 1) , тобто.

f(x) = f(x) + f(x) +…+ f(x). (3.59)

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

Метод Ньютона та метод січучих

Метод Ньютонау разі простого речового кореня має вигляд

x k+1 = x k - ――― , k = 1,2,…. (8.6)

f ′(x k)

у разі кореня кратності r

x k +1 - x k

f ′(x k)―――― + f(x k) = 0 .

Оцінка похибки така:

|х k - x *| £ q |x 0 - x *|, k = 1,2,….

M p+1 | x 0 - x * |

q = ―――――< 1.

m p p(p + 1)

Можна скористатися оцінкою похибки як у методі простої ітерації, враховуючи, що метод Ньютона

sx) = x – p ――

x k+1 = x k - ――― , k = 0, 1, ….

f′(x 0)

застосовують у тому випадку, коли хочуть уникнути багаторазового обчислення похідної ¦¢(x k).

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

(x k - x k -1) f (x k)

x k+1 = x k - ――――――

f(x k) – f(x k-1)

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

ЗАВДАННЯ ДО ЛАБОРАТОРНОЇ РОБОТИ.

1.Отделить речові коріння аналітично чи графічно.

2.Уточнити коріння розподілом відрізка навпіл (якщо це можливо) з точністю до 0.1.

3.Уточнити коріння заданим методом із заданою точністю.

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

4.Перевірити результати підстановкою знайдених значень рівняння.

ВАРІАНТИ

1. Знайти все коріння рівняння

1000000 x 4 - 3000 x 3 + 1000002 x 2 - 3000 x + 2 = 0

з точністю 0.0001 методом а) Ньютона б) січучих.

2. Знайти усі корені рівняння

x 4 - 10001.01 x 3 -9800.01 x 2 - 999901 x + 10000 = 0

з точністю 0.001 а) методом Ньютона; б) Модифікованим методом Ньютона.

3. Знайти все коріння рівняння

на відрізку з точністю 0.001 методом Ньютона.

4. Знайти усі корені рівняння

5. Знайти корінь рівняння

x 4 - 20 x 3 + 101 x 2 - 20 x + 1 = 0

на відрізку [-1,1] з точністю 0.0001 методом Ньютона з параметрами

заданої точності.

6. Знайти корінь рівняння

7. Знайти усі корені рівняння

x 5 - 3 x 2 + 1 = 0

методом парабол із точністю 0.0005.

8. Знайти речові корені рівняння

9. З'ясувати, до якого з коренів 0, 1,-1 рівняння

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

10. Знайти все коріння рівняння

x 3 + 3 x 2 - 1 = 0

методом простої ітерації із точністю 0. 0005.

11. Знайти усі корені рівняння

х 4 – 10000.01 x 3 +101 x 2 – 10000.01 х + 100 = 0

з точністю до 0.001 а) методом Ньютона; б) модифікованим методом Ньютона.

12. Знайти корінь рівняння

arccos (x/2) = x 2

на відрізку а) методом Ньютона; б) модифікованим методом Ньютона.

13. Знайти усі корені рівняння

x 4 - 0.015х3 + 0.3х 2 + х - 1 = 0

14. Знайти корінь рівняння

х 3 – sin (2x) = 1

методом парабол із точністю 0.001.

15. Знайти все коріння рівняння

х 3 - 1777х 2 + 777 = 0

на відрізку [-1,1] методом парабол з точністю до 0.0001

16. Знайти все коріння рівняння

5555х 4 - 555х 3 - 55х 2 - 5х = 0

з точністю 0.00001 методом а) Ньютона б) січучих.

17. Знайти корінь рівняння

arctg (7x) = 0.2

на відрізку [-1,1] а) методом Ньютона; б) модифікованим методом Ньютона.

18 . Знайти корінь рівняння

sin (x 4) = 1 - 2x

методом парабол із точністю 0.0001.

19 . Знайти корінь рівняння

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

20. Знайти усі корені рівняння

x 3 - 45x 2 + 43 = 0

на відрізку [-2,1] а) модифікованим методом Ньютона б) методом січучих.

21 . Знайти корінь рівняння

arcsin(x) + e x = 2

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

22. Знайти все коріння рівняння

54x 4 + x 2 - 0.0000001 = 0

з точністю 0.00001 методом а) Ньютона б) січучих.

23. Знайти все коріння рівняння

tg (x/3) - x 3 = 0

методом парабол із точністю 0.001.

24. Знайти все коріння рівняння

12x 4 + 11x 3 -10x 2 -999 = 0

на відрізку [-3.5,3] з точністю 0.0001 методом Ньютона з параметрами

р=1 та р=2. Порівняти кількості ітерацій, необхідні для досягнення

заданої точності.

25 . Знайти корінь рівняння

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

ВІДПОВІДІ:1) 0,0100; 0,0200 2) 0,688; 10000 3) 0,107; 0,155; 0,361 4) –1,32; 0; 1,32 5) 0,0917; 0,1125 6) 0 7) –0,5611; 0,5992; 1,348 8) –0,637; 1,41 9) –1; 0; 1 10) -2,879; -0,6527; 0,5321 11) 0,231; 10000 12) 1,01817183 13) –1,1468; 0,66935; 1 14) 1,191 15) -0,6611; 0,6614 16) –0,09811;0,19695 17) 0,028959 18) 0,4746 19) 0,987 20) –0,9672; 0,9884; 44,98 21) 0,4369 22) +/- 0,0003 23) +/- 0,581; 0 24) -3,36; 2,875 25) 1,2784.

Модифікований метод Ньютона ґрунтується на методі Ньютона. Якщо похідна змінюється незначно на відрізку, можна припустити.

Звідси для кореня рівняння отримуємо послідовні наближення

N = 0,1,2 ... (1.16)

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

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

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

Модифікований метод Ньютона має лінійну збіжність

Метод гарантує відсутність поділу на нуль, якщо .

приклад. Рівняння.

Застосовують метод Ньютона параметром, т.к. корінь має кратність p = 2. Візьмемо початкове наближення і отримуємо. Корінь знайдено.

приклад. Рівняння.

Корінь ізольований на відрізку. Похибка Eps дорівнює 0.000001

Метод Ньютона сходиться за 5 ітерацій, модифікований метод Ньютона за 19 ітерацій половинного поділуза 22 ітерації. Схожість методу ітерацій залежить від вибору параметра. При збіжність досягається за 24 ітерації, збіжність за 11 ітерацій, збіжність за 6 ітерацій, збіжність за 25 ітерацій.

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

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

обчисленої за відомими наближеннями та.

Відповідно виходить наступна формула методу січень

. (1.18)

Даний метод є двокроковим (бо треба знати два попередні кроки для виконання нового кроку). Цим він відрізняється від усіх раніше наведених методів – однокрокових.

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

Інтегрування функцій Постановка задачі

Нехай на відрізку встановлено безперервну функцію. Побудуємо розбиття відрізка крапками на часткові відрізки:

Довжина відрізків дорівнює.

Назвемо інтегральну суму

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

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

Як можна визначити інтеграл на практиці? Для цього зазвичай використовують формулу Ньютона – Лейбніца:

де P(x) - Первісна функції F(x) , тобто.

Формула Ньютона - Лейбніца грає велику роль у математичний аналіз. Але чи можна її застосовувати під час вирішення завдання на комп'ютері? Можна, але не завжди (бо первісна не завжди існує).

Чи зручно її застосовувати при складанні програм? Ні, потрібно знати первісну. Крім того, якщо функція задана графіком або таблицею, то інтеграл від неї формулою не обчислиш.

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

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

Відповідні формули називають формулами чисельного інтегрування чи квадратурними формулами 5 .

Крок розбиття в цьому випадку вважають за формулою.