Ітераційні методи розв’язування СЛАР (Система лінійних алгебраїчних рівнянь)

1. ІТЕРАЦІЙНІ МЕТОДИ РОЗВ’ЯЗУВАННЯ СЛАР

Ітераційні методи полягають в тому, що розв’язок x системи
знаходиться як границя послідовних наближень x(k) при
k , де k номер ітерації (Якобі, Зейделя, варіаційного
типу).
(k )
x розв' язок lim x
k
Правило зупинки || x(k+1) - x(k) ||
||x(k)||
або
або
.
≤ ε зад
|| x(k+1) - x(k) || ≤ εзад
|| x(k+1) - x(k) ||
||
x(0) -
x(k) ||
≤ ε зад
1

2. МЕТОД ПРОСТОЇ ІТЕРАЦІЇ

Припустимо, що
aii 0, i 1, n
і перетворимо систему
a11 x1 a12 x2 ... a1n xn b1 ,
a x a x ... a x b ,
21 1
22 2
2n n
2
..............................................
an1 x1 an 2 x2 ... ann xn bn ,
до вигляду
x1 12 x2 13 x3 ... 1n xn 1 ,
x x x ... x ,
2
21 1
23 3
2n n
2
..............................................
xn n1 x1 n 2 x2 ... n , n 1 xn 1 n ,
де
ij
aij
,i j
b
aii
, i
aii
0, i j
ij
2

3.

α
11 12 ... 1n
...
21
22
2n
,
..................
n1 n 2 ... nn
β
1
2
:
n
x(k+1) = αx(k) + β, k=0,1,2…
або у розгорнутому вигляді
xi( 0) i ,
n
xi( k 1) ij x (jk ) i ,
i 1, n,
k 0,1,2,...
j 1
3

4.

4

5.

5

6.

6

7. ЗБІЖНІСТЬ МЕТОДУ ПРОСТОЇ ІТЕРАЦІЇ

Для збіжності процесу обчислень необхідно, щоб виконувалась
умова
||α|| < 1.
Відповідно для різних матричних норм:
n
n
l2 2 ij 1,
j 1 i 1
n
l max | ij | 1,
i
j 1
n
l0 max | ij | 1.
j
i 1
7

8. Теорема

Якщо матриця α системи рівнянь x(k+1) = αx(k) + β
задовольняє одну із умов
l2
n
n
2
ij
1,
j 1 i 1
l max
i
l0 max
j
n
|
j 1
ij
| 1,
ij
| 1.
n
|
i 1
то ця система рівнянь має єдиний розв’язок
x* = (x*1, x*2…, x*n), який можна обчислити як границю
послідовності {x (k+1)}, починаючи з довільного початкового
вектора x(0) = (x(0)1, x(0)2…, x(0)n)
8

9. ПОХИБКИ МЕТОДУ ПРОСТОЇ ІТЕРАЦІЇ

Глобальна похибка розв’язку на двох сусідніх ітераціях
||x(k+1) – x*|| = ||α|| ||x(k) – x*||
Локальні похибки, що отримані на двох сусідніх ітераціях
x
( k 1)
x
*
x ( k 1) x*
α
1 α
α
x ( k 1) x ( k ) .
k 1
1 α
x (1) x (0) .
Метод простої ітерації слід завершити, якщо стане справедливою
нерівність:
( k 1)
i
max | x
i
x
(k )
i
1 l
|
.
l
де ε – наперед задана точність обчислень.
Аналогічні умови дійсні і для інших матричних норм.
9

10. МЕТОД ЯКОБІ

( k 1)
i
x
1
aii
i 1
n
(k )
(k )
bi aij x j aij x j , i 1, n, k 0,1, 2,....
j 1
j i 1
Запишемо метод Якобі в матричній формі. Для цього
запишемо матрицю A як:
A = L + D + U.
a11 0
0 a
22
D
... ...
0 0
... 0
0
0 a12 ... a1n
a
0 ... a
... 0
0
2n
, U
, L 21
... ...
... ...
... ...
... a33
a
a
...
0
0
n1 n 2
10

11. МЕТОД ЯКОБІ

Запишемо СЛАР як:
(L + D + U)x = b
або
Dx = b - (L + U)x.
Тоді у матричній формі метод Якобі має вид:
Dx(k+1) = b - (L + U)x(k)
З
x(k+1) = - D-1(L + U)x(k) + D-1b
видно, що матриця перетворення ітераційного
методу x(k+1) = αx(k) + β має вид:
α = - D-1(L + U).
11

12. МЕТОД ЯКОБІ

При цьому
i j,
aij aii ,
i, j
i j.
0,
Для збіжності методу Якобі достатньо, щоб матриця α
мала домінуючу головну діагональ:
|| || max
i
n
aij
j 1, j i
aii
1
тобто
aii
n
j 1, j i
aij , i 1, n.
12

13. МЕТОД ЯКОБІ

x 2y 3
x 4 y 3
x ( k 1) 3 2 y ( k )
(k )
x
3
y ( k 1)
4
13

14. МЕТОД ГАУССА-ЗЕЙДЕЛЯ

( k 1)
i
x
Маємо
1
aii
i 1
n
( k 1)
(k )
bi aij x j aij x j , i 1, n, k 0,1, 2,....
j 1
j i 1
(L + D)x = b - Ux
У матричній формі метод Гаусса-Зейделя записується як:
(L + D) х(k+ 1) = b - Uх(k).
де матриця перетворення має вигляд
α = - (D + L)-1U
Умови збіжності методів Якобі і Гаусса-Зейделя ідентичні.
14

15.

15

16.

16

17. ПОХИБКИ МЕТОДУ ГАУССА-ЗЕЙДЕЛЯ

Локальна похибка за наближеннями, що отримані на двох
сусідніх ітераціях
x
(k )
x
*
U
1
x ( k ) x ( k 1) .
Метод Гаусса-Зейделя слід завершити, якщо стане справедливою
нерівність:
x
(k )
x
( k 1)
U
1 α
,
де ε – наперед задана точність обчислень.
Аналогічні умови дійсні і для інших матричних норм.
17

18.

2 x y 2,
x 2 y 2,
2 1
A
, (k ) 1
( k 1)
1
2
x (2 y
),
2
y
(k )
x* = 0.4;
1 (k )
( x 2).
2
y* = 1.2
k
xk
yk
0
0
0
1
1
3/2
2
1/4
9/8
3
7/16 39/32
18

19.

2 x y 2,
x 2 y 2,
2 1
A
,
1 2
y ( k ) ( 2 x( k 1) 2), x( k ) ( 2 2 y ( k ) ).
x=0,4; y=1,2
k
yk
xk
0
0
0
1
2
2
2
-2
-6
3
14
26
4
-50
-102
19

20. КАНОНІЧНА ФОРМА ІТЕРАЦІЙНИХ МЕТОДІВ

D 1
КАНОНІЧНА ФОРМА ІТЕРАЦІЙНИХ МЕТОДІВ
Канонічною формою однокрокових ітераційних методів
розв’язування СЛАР називається їх запис у вигляді:
B k 1 (x ( k 1) x( k ) )
k 1
Ax ( k ) b
де Bk+1 − матриця, яка задає ітераційний метод; k+1− ітераційний
параметр, що задає швидкість збіжності методу.
Якщо Bk+1 = E метод називається явним (інакше неявним).
Якщо Bk+1= B та k+1 = , метод називається стаціонарним
(нестаціонарним в іншому випадку).
Канонічна форма методів Якобі та Зейделя
D(x( k 1) x( k ) ) Ax( k ) b
(D L)(x( k 1) x( k ) ) Ax( k ) b
20

21. МЕТОД РЕЛАКСАЦІЇ

Умови збіжності можна покращити, якщо ввести
коефіцієнт демпфірування для врахування нев’язки
0 2
( k 1)
i
x
(1 ) x
(k )
i
i 1
bi aij x
aii
j 1
( k 1)
j
aij x , k 0,1, 2,....
j i 1
n
(k )
j
Тоді метод простої ітерації перетворюється на
метод верхньої релаксації (якщо вибрати для
1 2 ), який
прискорення збіжності
застосовується для розв’язання систем лінійних
рівнянь великої розмірності , або метод нижньої
релаксації ( 1 2 ) .
( k 1)
( L D)x
[(1 )D U]x
(k )
b
21

22.

1.25
22

23.

23

24.

24

25.

Метод релаксації
25

26. РОЗВ’ЯЗАННЯ СИСТЕМ НЕЛІНІЙНИХ РІВНЯНЬ

РОЗВ’ЯЗАННЯ СИСТЕМ НЕЛІНІЙНИХ РІВНЯНЬ
У загальному випадку системa нелінійних рівнянь
записується у вигляді
f1 ( x1 , x2 , ..., xn ) 0,
f 2 ( x1 , x2 , ..., xn ) 0,
... ... ...
f n ( x1 , x2 , ..., xn ) 0,
де fi ( x1 , x2 , ..., xn ), i 1, 2, ..., n − функції дійсних
змінних x1 , x2 , ..., xn .
Систему можна записати у вигляді
F( x ) 0,
де
x ( x1 , x2 , ..., xn )T ;
F(x) ( f1 (x), f 2 (x), ..., f n (x))T .
26

27.

Для методу простої ітерації можна записати:
( k 1)
де
x
(x ),
( x) ( 1 ( x), 2 ( x), ..., n ( x))T .
(k )
На першій ітерації на основі початкового
наближення наступне знаходять за формулами:
(1)
i
x
i ( x , x , ..., x ), i 1, 2, ..., n.
(0)
1
(0)
2
(0)
n
У загальному вигляді, якщо знайдене k-е
наближення x1( k ) , x2( k ) , ..., xn( k ) , то k +1 знаходять за
формулами:
( k 1)
i
x
i ( x , x , ..., x ), i 1, 2, ..., n.
(k )
1
(k )
2
(k )
n
Збіжність забезпечується, якщо:
J( x) „ M 1,
27

28.

де J( x ) – матриця Якобі,
1
x1
2
( x) J ( x) x1
...
n
x1
1
x2
2
x2
...
n
x2
...
...
...
...
1
xn
2
xn .
...
n
xn
Одним із серйозних недоліків методу простих
ітерацій є складність вибору функцій i ,які б
задовольняли достатню умову збіжності.
28

29.

Узагальнений метод Ньютона:
x( k 1) x( k )
F( x
(k )
W(x
)
(k )
f1
x1
f 2
F ( x) W ( x) x1
...
f n
x1
)
,
k 0, 1, 2, ... ,
f1
x2
f 2
x2
...
f n
x2
...
...
...
...
f1
xn
f 2
xn .
...
f n
xn
29

30.

f1
(k ) (k )
(k )
(k ) (k )
(k ) f1
f ( x , x ,..., x ) f ( x , x ,..., x )
x1 ...
xn ,
1 1
2
n
1 1
2
n
x1
xn
f 2
(k ) (k )
(k )
(k ) (k )
(k ) f 2
f ( x , x ,..., x ) f ( x , x ,..., x )
x1 ...
xn ,
2 1
2
n
2 1
2
n
x1
xn
...
f n
(k ) (k )
(k )
(k ) (k )
(k ) f n
f ( x , x ,..., x ) f ( x , x ,..., x )
x1 ...
xn ,
n 1
2
n
n 1
2
n
x1
xn
30

31.

31

32.

32

33.

Щоб уникнути процедури обертання матриці
Якобі, метод Ньютона реалізують у вигляді:
A(x(k ) )x(k 1) b(x(k ) ),
де
A(x(k ) ) W(x(k ) ) і b(x(k ) ) W(x(k ) )x(k ) F(x(k ) ).
33