1.3 Метод простих ітерацій
Із вихідної системи (1.2.1) шляхом еквівалентних перетворень переходимо до системи виду:
(1.3.1)Ітераційний процес, який визначається формулами
,можна почати, задав початкове приближення
. Достатньою умовою збіжності ітераційного процесу є одно з двох умов: чи .Розпишемо першу умову:
при при .Розпишемо другу умову:
при при .Розглянемо один із способів приведення системи (1.2.1) до виду (1.3.1), допустиме збіжній ітерації.
Нехай задана система другого порядку виду:
.Потрібно привести її до виду:
.Множимо перше рівняння системи на невідому постійну
, друге - на , потім додаємо їх і добавляємо в обидві частини рівняння . Отримаємо перше рівняння перетвореної системиде
.Далі, помножимо перше рівняння системи на невідому сталу
, друге - на , потім додамо їх і добавляємо в обидві частини рівняння . Тоді друге рівняння перетвореної системи буде мати видде
.Невідомі сталі
визначимо з допустимі умови збіжності и .Запишемо ці умови більш детально:
Припустимо, що вирази під знаком модуля дорівнюють нулю, і отримаємо систему з чотирьох рівнянь з чотирма невідомими для визначення сталих
: .При такому виборі параметрів умови збіжності будуть дотримані, якщо часткові похідні функцій
і будуть змінюватись не дуже швидко в околі точки .Щоб розв’язати систему, потрібно задати початкове приближення
и обчислити значення похідних і , в цій точці. Обчислення здійснюється на кожному кроці ітерацій, при цьому , , .Метод простих ітерацій є найбільш універсальним і простим для реалізації на ЭОМ. Якщо система має великий порядок, то застосування даного метода, який має повільну швидкість збіжності, не рекомендується. В цьому випадку, використовують метод Ньютона, який має швидшу збіжність.
1.4 Метод Ньютона для розв’язання
Нехай (
) — деяка послідовність невироджених n-матриць. Тоді, очевидно, послідовність задач , k = 0,1,2,...маємо ті ж розв’язки, що і вихідне рівняння F(x)=0, і для приближеного знаходження цих розв’язків можна формально записати ітераційний процес
, k = 0,1,2,... (1.4.1)Який має вигляд метода простих ітерацій (1.3.1) при
. У випадку - це дійсно МПІ з лінійною збіжністю послідовності ( ) Якщо же різні за різних k, то формула (1.4.1) визначає велику кількість ітераційних методів з матричними параметрами . Розглянемо деякі з цих методів.Припустимо
, де— матриця Якобі вектор-функція F(x). Підставимо це
в (1.4.1), отримаємо явну формулу метода Ньютона , (1.4.2)Цю формулу, що вимагає перетворення матриць на кожній ітерації, можна переписати в неявному вигляді:
. (1.4.3)Використання (1.4.3) припускає при кожному k = 0,1,2,... розв’ язок лінійної алгебраїчної системи
відносно векторній поправці
, а потім добавлення цієї поправки до поточного наближення для отримання наступного: .До розв’язку таких лінійних систем можна використовувати найрізноманітніші методи як прямі, так і ітераційні в залежності від розмірності n розв’язуваної задачі і специфіки матриць Якобі
.Порівнюючи (1.4.3) з формальним розкладом F(x) в ряд Тейлера
,бачимо, що послідовність (
) в методі Ньютона отримується в результаті заміни при кожному k=0,1,2,... нелінійного рівняння F(x) = 0 чи, при допустимій гладкості F(x)), рівняннялінійним рівняння
тобто з покроковою лінеаризацією. Як наслідок цього факту, можна полягати, що при допустимій гладкості F(x) і достатньо гарному початковому наближенні
збіжність, яка виникає методом Ньютона послідовності ( ) до розв’язку буде квадратичною і в багаторазовому випадку.Новим, порівняно з скалярним випадком, фактором, який ускладнює використання метода Ньютона до розв’язання n-вимірних систем, є необхідність розв’язання n-вимірних лінійних задач на кожній ітерації, обчислення яких збільшується зі збільшенням n, тобто кажучи, непропорційно швидко. Зменшення таких затрат є одним з напрямків модифікації метода Ньютона.