Рішення систем нелінійних рівнянь. Метод ітерацій. Метод Ньютона–Канторовича (стр. 2 из 3)

Тоді значення , для якого функція прийме мінімальне значення, визначається із умови Про диференціювавши рівняння (3) по і враховуючи, що получимо

(4)

Оскільки в методі найшвидшого спуску компоненти градієнта мають вигляд

то формула (4) після підстановки цих рівнянь перейде до вигляду

(5)

Формула (5) дуже складна оскільки потребує рахування других часних похідних.

На практиці завжди використовується наступний варіант знаходження

.

Нехай значення Ф (Х) змінюється вздовж напрямку градієнта

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

Вона буде розраховуватися наступним чином:

. (6)

Як бачимо, в цьому випадку

рахується просто, але сходження метода може бути дуже повільно. Тому інколи на практиці використовують наступну модифікацію.

Для кожної ітерації метода рахують значення функціонала при

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

(7)

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

, але метод сходиться набагато швидше.

Інколи характер Ф (Х) такий, що аналітичне рівняння для частних похідних має надто складний вигляд і рахувати їх надто складно.

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

Порядок рахування в методі найшвидшого спуска наступний:

знаходиться аналітичне рівняння для градієнта

;

вибирають початкове приближення вектора невідомих

;

вираховують координати градієнта

в точці ;

вираховують шаг по градієнту

по формулам (6) або (7);

вираховують уточнений вектор невідомих

.

Далі процес повторюється з пункту 3 до сходження.

1.2.1 Приклад рішення системи нелінійних рівнянь методом спуска

Методом найшвидшого спуска приблизно розрахувати корені системи

розміщенні в області початку координат.

Маємо:

Тут та

Підставляємо нульове приближення, будемо мати:

та

по формулам получимо перше приближення

Аналогічно находимо друге приближення

. Маємо:

.

1.3 Метод Ньютона-Канторовича

Метод Ньютона-Канторовича, придатний для проведення розрахунків в Excel. Як і в методі Ньтона для нелінійних рівнянь для знаходження кореня системи нелінійних рівнянь необхідно спочатку якимсь чином знайти початкове наближення до цього кореня (тобто вектор

),

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

, и (. (i - номер ітерації,, i ³ 0) ) використовується також матриця A (розмірності n ´ n), що складається з приватних похідних по всіх компонентах вектора :

:

Розглянемо ці методи для випадку n=2, тобто коли рівнянь в системі два і невідомих теж дві. В цьому випадку

, та .

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

. Тоді можна приблизно записати

, (8)

На основі формула (8) будується ітараційна формула. А саме,

вибирається так, щоб .

Тоді (у загальному вигляді) ітераційна формула матиме вигляд

(9)

В методі Ньютона цю ітераційну формулу перетворять до вигляду

(10)

У координатному вигляді формула (10) представляє систему з двох рівнянь щодо двох невідомих xi+1 и yi+1.

У матричному вигляді рішення її матиме вигляд

допоміжний вектор-стовпець z, що містить n елементів.

(11)

Ітераційна формула методу в матричному записі має наступний вигляд

z_j = - A^-1 (x_j)×F (x_j)

x_{j +1} = x_j + z_j, (12)

тут j - номер ітерації,

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

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

Для випадку n=2 система рівнянь найчастіше має такий вигляд: