Метод простої ітерації для розв`язання систем лінійних рівнянь (слау)

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

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

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- ε

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

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

Відео: Рішення систем лінійних рівнянь, урок 5/5. ітераційні методи

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

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

Відео: Лекція 6: Прямі та ітераційні методи рішення систем лінійних алгебраїчних рівнянь

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

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, тобто умова виконується.

Відео: Лекція 15: Рішення систем нелінійних рівнянь

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

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

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