Метод Ньютона для розв’язування систем нелінійних рівнянь
Систему нелінійних рівнянь у загальному випадку можна зобразити у вигляді
EMBED Equation.3 (1)
тобто як п функцій fi від п невідомих хі, причому функції fi не обов'язково лінійно залежать від змінних хі.
Позначимо вектор змінних через X = (x1, x2, …, xn),а вектор функцій через F = (f1, f2,…, fп). Тоді систему (1) можна записати у формі
F(X) = 0. (2)
Завдання полягав в тому, щоб знайти розв'язок цієї системи. Слід сказати, що на даний час не існує математичної теорії, яка дозволяла б у загальному вигляді розв'язати питання про існування та число розв'язків системи (2). їх може не бути зовсім, може бути один, декілька або нескінченна множина. Крім того, важливою особливістю системи нелінійних рівнянь є те, що для їх розв'язування не можна використати прямі методи, зокрема, метод послідовного виключення невідомих. Усі розроблені методи є ітераційними, а найефективнішим і широко вживаним є метод Ньютона.
1.Стандартний метод Ньютона
Метод Ньютона базується на лінеаризації задачі і заміні розв'язування нелінійної системи (2) на послідовність розв'язувань лінійних систем ( найчастіше прямими методами).
Будемо вважати, що система рівнянь (2) має розв'язок; позначимо його через вектор X* = (х1*, х2*,..., хп*) і розкладемо кожну функцію в ряд Тейлора в околі розв'язку
EMBED Equation.3
де Rіп - члени другого і вищих порядків.
Вважаючи, що X дуже близьке до X*, знехтуємо членами вищих порядків і запишемо систему рівнянь в лінеаризованій формі:
EMBED Equation.3 (3)
або в іншому вигляді
EMBED Equation.3 (4)
де
EMBED Equation.3 – матриця Якобі (якобіан) системи (1)
Враховуючи, що X* є розв'язком системи, згідно з (2) можемо записати:
F(X*) = 0.
Звідси випливає, що і праву частину (4) також можна прирівняти до нуля:
EMBED Equation.3 (5)
Розв'язком системи (5) є нове значення вектора X, яке не точно дорівнює значенню вектора X* (оскільки знехтували членами другого і вищих порядків). Використовуючи верхні індекси для позначення послідовності ітерацій, можна записати
EMBED Equation.3 (6)
Звідси
EMBED Equation.3 (7)
де [J(XK)]–1 - обернена матриця Якобі; К = 0, 1, 2, ... .
У достатньо широкому околі розв'язку X* ітераційний процес (7) збігається, якщо det J(Хк) ? 0.
Ітераційний процес закінчується при виконанні умови
EMBED Equation.3 (8)
де ? - задана гранична похибка уточнень коренів системи (1).
Таким чином, алгоритм стандартного методу Ньютона можна розбити, на декілька кроків.
Крок 1. Вибір вектора початкових уточнень
Х(0)-(х1(0), х2(0), ..., хп(0)).
Крок 2. Обчислення елементів матриці Якобі.
Крок 3. Обчислення елементів оберненої матриці Якобі.
Крок 4. Перемноження значень функції (див. формулу (7))
EMBED Equation.3
Крок 5. Одержаний на кроці 4 вектор віднімається від вектора ХК, у результаті чого одержується покращений вектор розв'язку ХК+1.
Крок 6. Перевірка умови закінчення ітерацій (8). Якщо вона не виконується, то за вектор початкових уточнень приймається вектор ХК+1 і проводиться наступна ітерація, починаючи з кроку 2.
При використанні стандартного методу Ньютона слід мати на увазі наступне.
1. Стандартний метод Ньютона надзвичайно ефективний.
2. Збіжність на початку ітераційного процесу, як правило, лінійна.
3. Починаючи з деякого кроку ( уточнити його попередньо неможливо), збіжність різко прискорюється і стає квадратичною.
4. Бувають випадки, коли метод розбігається або спостерігається зациклювання ітерацій. Тому необхідно обмежувати максимальну кількість ітерацій деяким попередньо заданим числом.
Основний недолік методу полягає в повторних обчисленнях на кожному кроці вектора F(XK) , матриці Якобі J(XK), оберненої матриці Якобі [J(XK)]–1. Тому на практиці досить часто з метою зменшення витрат машинного часу використовують стандартний метод Ньютона без обертання матриці Якобі.
Позначаючи
EMBED Equation.3 (9)
перепишемо (6) у вигляді
EMBED Equation.3 (10)
Таким чином, задача зводиться до пошуку вектора поправок (приростів) ?ХК із системи лінійних алгебраїчних рівнянь (10), у якій матрицею коефіцієнтів при невідомих ?хіK є матриця Якобі J(XK), а вектором-стовпцем вільних членів служить вектор значень функції – F(XK). Розв'язуючи цю систему одним із відомих методів ( як правило, це представники групи прямих методів – метод Гауса з вибором головних елементів, метод LU – факторизації та ін.) , знаходимо ?ХК. Значення ХK+1 визначаємо із виразу
EMBED Equation.3 (11)
Приклад. Уточнити корені системи нелінійних рівнянь
EMBED Equation.3
стандартним методом Ньютона без обертання якобіана при початкових наближеннях коренів x10 = 3,4; x20 = 2,2.
Знайдемо вирази для функцій
EMBED Equation.3
за якими будуть визначатись елементи матриці Якові:
EMBED Equation.3 EMBED Equation.3
Обчислимо значення функцій та елементів матриці Якобі в точці Х0 = (х10, х20):
EMBED Equation.3 EMBED Equation.3
Розв'яжемо згідно з (10) систему лінійних рівнянь відносно приростів EMBED Equation.3
EMBED Equation.3
Уточнені значення коренів визначаються за формулою (11):
EMBED Equation.3
Наступна ітерація проводиться таким чином:
знаходяться значення функцій та елементів матриці Якобі в точці Х1 = (х11, х21) і розв'язується відповідна система лінійних рівнянь:
EMBED Equation.3 EMBED Equation.3
EMBED Equation.3
Звідси
EMBED Equation.3
Отже,
EMBED Equation.3
2. Метод Ньютона з якобіаном із кінцевих різниць
У цьому методі замість похідних, що входять до складу якобіана, використовуються їхні наближені значення в точці ХК
EMBED Equation.3
де h - фіксоване достатньо мале число, наприклад ,1*10-9.
3. Модифікований метод Ньютона
При використанні стандартного методу Ньютона на кожній ітерації доводиться обчислювати новий якобіан J(XK) , хоч зрозуміло, що при закінченні ітерацій він повинен прийняти стабільне значення J(X*), де X* –розв'язок. У модифікованому або спрощеному методі Ньютона якобіан J(XK) заміняють правильно підібраною матрицею А. Звичайно, найкращим, але практично недосяжним варіантом була б заміна А = J(X*), де X* - розв'язок.
Але на практиці користуються компромісним рішенням:
– вибирають за А якобіан з початковій точці J(X0), a ітерації проводять за наступною формулою
EMBED Equation.3
– зберігають А протягом певного числа ітерацій;
– на певній r-й ітерації змінюють А, прирівнюючи її якобіану J(Xr) і з новим значенням знову виконують певне число ітерацій і т.д.
Отже, якобіан обчислюється тільки час від часу, за рахунок чого досягається економія машинного часу. Однак, збіжність методу при цьому стає практично лінійною.