Метод простої ітерації для розв'язання систем лінійних рівнянь (СЛАР)

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

Розглянемо, як даний метод реалізується при вирішенні СЛАР. Метод простої ітерації має наступний алгоритм:

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

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

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

3. Перетворення отриманої системи до нормального вигляду:

x^-= Beta-^-+alpha- * x^-

Це можна зробити безліччю способів, наприклад, так: з першого рівняння виразити х₁ через інші невідомі, з другого- х₂, з третього-х₃ і т.д. При цьому використовуємо формули:

alpha-_ij= - (A_ij / A_ii)

_i= B_i/ A_ii
Слід знову переконатися, що отримана система нормального вигляду відповідає умові збіжності:

sum- (j = 1) | alpha-_ij| Le- 1, при цьому i = 1,2, ... n

4. Починаємо застосовувати, власне, сам метод послідовних наближень.

x⁽⁰⁾- початкове наближення, висловимо через нього х⁽¹⁾, далі через х⁽¹⁾ висловимо х⁽²⁾. Загальна формула а матричному вигляді виглядає так:

x^(N)= beta-^-+alpha- * x^(N-1)

Обчислюємо, поки не досягнемо необхідної точності:

max | x_i(K) -x_i(K + 1) le- epsilon-

Отже, давайте розберемо на практиці метод простої ітерації. Приклад:
Вирішити СЛАР:

4,5x1-1.7x2 + 3.5x3 = 2
3.1x1 + 2.3x2-1.1x3 = 1
1.8x1 + 2.5x2 + 4.7x3 = 4 з точністю epsilon- = 10^-3

Подивимося, переважають чи по модулю діагональні елементи.

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

7,6x1 + 0.6x2 + 2.4x3 = 3

З третього віднімемо перший:

-2,7x1 + 4.2x2 + 1.2x3 = 2

Ми перетворили вихідну систему в рівноцінну:

7,6x1 + 0.6x2 + 2.4x3 = 3
-2,7x1 + 4.2x2 + 1.2x3 = 2
1.8x1 + 2.5x2 + 4.7x3 = 4

Тепер наведемо систему до нормального вигляду:

x1 = 0.3947-0.0789x2-0.3158x3
x2 = 0.4762 + 0.6429x1-0.2857x3
x3 = 0.8511-0.383x1-0.5319x2

Перевіряємо збіжність ітераційного процесу:

0.0789 + 0.3158 = 0,3947 le- 1
0.6429 + 0.2857 = 0.9286 le- 1
0.383+ 0.5319 = 0.9149 le- 1, тобто умова виконується.

0,3947
Початкове наближення х⁽⁰⁾ = 0,4762
0,8511

Підставляємо дані значення в рівняння нормального вигляду, отримуємо такі значення:

0,08835
x⁽¹⁾= 0,486793
0,446639

Підставляємо нові значення, отримуємо:

0,215243
x⁽²⁾= 0,405396
0,558336

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

0,18813

x⁽⁷⁾= 0,441091

0,544319

0,188002

x⁽⁸⁾ = 0,44164

0,544428

Перевіримо правильність отриманих результатів:

4,5 * 0,1880 -1.7 * 0,441 + 3.5 * 0,544 = 2,0003
3.1 * 0,1880 + 2.3 * 0,441-1.1x * 0,544 = 0,9987
1.8 * 0,1880 + 2.5 * 0,441 + 4.7 * 0,544 = 3,9977

Результати, отримані при підстановці знайдених значень в вихідні рівняння, повністю задовольняють умовам рівняння.

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