asyan.org
добавить свой файл
1
Метод Ньютона для розв’язування систем нелінійних рівнянь
Систему нелінійних рівнянь у загальному випадку можна зобразити у вигляді
(1)
тобто як п функцій fi від п невідомих хі, причому функції fi не обов'язково лінійно залежать від змінних хі.

Позначимо вектор змінних через X = (x1, x2, …, xn),а вектор функцій через F = (f1, f2,…, fп). Тоді систему (1) можна записати у формі
F(X) = 0. (2)
Завдання полягав в тому, щоб знайти розв'язок цієї системи. Слід сказати, що на даний час не існує математичної теорії, яка дозволяла б у загальному вигляді розв'язати питання про існування та число розв'язків системи (2). їх може не бути зовсім, може бути один, декілька або нескінченна множина. Крім того, важливою особливістю системи нелінійних рівнянь є те, що для їх розв'язування не можна використати прямі методи, зокрема, метод послідовного виключення невідомих. Усі розроблені методи є ітераційними, а найефективнішим і широко вживаним є метод Ньютона.
1.Стандартний метод Ньютона
Метод Ньютона базується на лінеаризації задачі і заміні розв'язування нелінійної системи (2) на послідовність розв'язувань лінійних систем ( найчастіше прямими методами).

Будемо вважати, що система рівнянь (2) має розв'язок; позначимо його через вектор X* = (х1*, х2*,..., хп*) і розкладемо кожну функцію в ряд Тейлора в околі розв'язку



де Rіп - члени другого і вищих порядків.

Вважаючи, що X дуже близьке до X*, знехтуємо членами вищих порядків і запишемо систему рівнянь в лінеаризованій формі:

(3)
або в іншому вигляді
(4)
де
– матриця Якобі (якобіан) системи (1)
Враховуючи, що ^ X* є розв'язком системи, згідно з (2) можемо записати:
F(X*) = 0.
Звідси випливає, що і праву частину (4) також можна прирівняти до нуля:

(5)
Розв'язком системи (5) є нове значення вектора ^ X, яке не точно дорівнює значенню вектора X* (оскільки знехтували членами другого і вищих порядків). Використовуючи верхні індекси для позначення послідовності ітерацій, можна записати
(6)
Звідси
(7)
де [J(XK)]–1 - обернена матриця Якобі; К = 0, 1, 2, ... .

У достатньо широкому околі розв'язку X* ітераційний процес (7) збігається, якщо det J(Хк) ≠ 0.

Ітераційний процес закінчується при виконанні умови
(8)
де Σ - задана гранична похибка уточнень коренів системи (1).

Таким чином, алгоритм стандартного методу Ньютона можна розбити, на декілька кроків.
Крок 1. Вибір вектора початкових уточнень
Х(0)-(х1(0), х2(0), ..., хп(0)).
Крок 2. Обчислення елементів матриці Якобі.

Крок 3. Обчислення елементів оберненої матриці Якобі.

Крок 4. Перемноження значень функції (див. формулу (7))

Крок 5. Одержаний на кроці 4 вектор віднімається від вектора ХК, у результаті чого одержується покращений вектор розв'язку ХК+1.

Крок 6. Перевірка умови закінчення ітерацій (8). Якщо вона не виконується, то за вектор початкових уточнень приймається вектор ХК+1 і проводиться наступна ітерація, починаючи з кроку 2.
При використанні стандартного методу Ньютона слід мати на увазі наступне.

1. Стандартний метод Ньютона надзвичайно ефективний.

2. Збіжність на початку ітераційного процесу, як правило, лінійна.

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

4. Бувають випадки, коли метод розбігається або спостерігається зациклювання ітерацій. Тому необхідно обмежувати максимальну кількість ітерацій деяким попередньо заданим числом.
Основний недолік методу полягає в повторних обчисленнях на кожному кроці вектора F(XK) , матриці Якобі J(XK), оберненої матриці Якобі [J(XK)]–1. Тому на практиці досить часто з метою зменшення витрат машинного часу використовують стандартний метод Ньютона без обертання матриці Якобі.

Позначаючи
(9)

перепишемо (6) у вигляді
(10)
Таким чином, задача зводиться до пошуку вектора поправок (приростів) ΔХК із системи лінійних алгебраїчних рівнянь (10), у якій матрицею коефіцієнтів при невідомих ΔхіK є матриця Якобі J(XK), а вектором-стовпцем вільних членів служить вектор значень функції – F(XK). Розв'язуючи цю систему одним із відомих методів ( як правило, це представники групи прямих методів – метод Гауса з вибором головних елементів, метод LU – факторизації та ін.) , знаходимо ΔХК. Значення ХK+1 визначаємо із виразу
(11)
Приклад. Уточнити корені системи нелінійних рівнянь

стандартним методом Ньютона без обертання якобіана при початкових наближеннях коренів x10 = 3,4; x20 = 2,2.

Знайдемо вирази для функцій

за якими будуть визначатись елементи матриці Якові:

Обчислимо значення функцій та елементів матриці Якобі в точці Х0 = (х10, х20):

Розв'яжемо згідно з (10) систему лінійних рівнянь відносно приростів

Уточнені значення коренів визначаються за формулою (11):

Наступна ітерація проводиться таким чином:

знаходяться значення функцій та елементів матриці Якобі в точці Х1 = (х11, х21) і розв'язується відповідна система лінійних рівнянь:


Звідси

Отже,

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

де h - фіксоване достатньо мале число, наприклад ,1*10-9.
3. Модифікований метод Ньютона
При використанні стандартного методу Ньютона на кожній ітерації доводиться обчислювати новий якобіан J(XK) , хоч зрозуміло, що при закінченні ітерацій він повинен прийняти стабільне значення J(X*), де X* –розв'язок. У модифікованому або спрощеному методі Ньютона якобіан J(XK) заміняють правильно підібраною матрицею А. Звичайно, найкращим, але практично недосяжним варіантом була б заміна А = J(X*), де X* - розв'язок.

Але на практиці користуються компромісним рішенням:

– вибирають за А якобіан з початковій точці J(X0), a ітерації проводять за наступною формулою

– зберігають А протягом певного числа ітерацій;

– на певній r-й ітерації змінюють А, прирівнюючи її якобіану J(Xr) і з новим значенням знову виконують певне число ітерацій і т.д.

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