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


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

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

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

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

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

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

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

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

alpha-ij= - (Aij / Aii)

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

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

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

x(0)- початкове наближення, висловимо через нього х(1), далі через х(1) висловимо х(2). Загальна формула а матричному вигляді виглядає так:

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

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

max | xi(K) -xi(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) = 0,4762
0,8511

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

0,08835
x(1)= 0,486793
0,446639

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

0,215243
x(2)= 0,405396
0,558336

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

0,18813

x(7)= 0,441091

0,544319

0,188002

x(8) = 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

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

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

Поділися в соц мережах:

Увага, тільки СЬОГОДНІ!