metoda dokładna rozwiązywania układów równań liniowych
A x = b
det A ≠ 0
A x = b
[L U] x = b
A = L U
L – macierz trójkątna dolna, otrzymana z macierzy A, U – macierz trójkątna górna, otrzymana z macierzy A L y = b
(1)
U x = y
(2)
Najpierw musimy obliczyć macierz L i macierz U
( )1 ( )1
( )1
L
1 a
a
a
12
(13
1 n
2)
(2)
0 1
L
a
a
23
2 n
U =
(3)
L
0 0
1
a
(3)
3 n
M
M
M
O
M
0 0
0 L 1
Macierz L
( )
1
L
a
0
0
0
(1 )11 (2)
a
a
L
0
0
21
22
L = ( )
1
(2) (3) L
a
a
a
0
(4)
31
32
33
M
M
M
O
M
( )1 (2) (3)
( n)
a
a
a
L a
n 1
n 2
n 3
nn
Algorytm Crouta Przykład dla n = 4
l
0
0
0 1
u
u
u
a
a
a
a
11
12
13
14
11
12
13
14
l
l
0
0
0
1
u
u
a
a
a
a
21
22
23
24
21
22
23
24
⋅
=
(5)
l
l
l
0
0
0
1
u
a
a
a
a
31
32
33
34 31
32
33
34
l
l
l
l
0
0
0
1
a
a
a
a
41
42
43
44
41
42
43
44
Pomocnicza macierz Q
l
u
u
u
11
12
13
14
l
l
u
u
21
22
23
24
Q =
(6)
l
l
l
u
31
32
33
34
l
l
l
l
41
42
43
44
Elementy macierzy Q, dla n = 4, są obliczane w kolejności zaznaczonej w poniższej tablicy
1
5
6
7
l
u
u
u
2
8
11 12
11
12
13
14
l
l
u
u
21
22
23
24
Q =
3
9
13 15
l
l
l
u
31
32
33
34
l
l
l
l
41
42
43
44
4 10 14 16
Numer oznacza kolejność obliczania elementów.
Najpierw obliczamy elementy macierzy L (pierwsza kolumna), potem elementy macierzy U (pierwszy wiersz, bez pierwszego elementu, który jest równy 1),
potem elementy macierzy L (druga kolumna), potem elementy macierzy U (druga kolumna, ale bez pierwszego elementu, który jest równy 0),
potem elementy macierzy L, itd.
Biorąc pod uwagę zależność (5), wykonujemy obliczenia dla kolejnego elementu aij
w postaci iloczynu i-tego wiersza macierzy L i j-tej kolumny macierzy U
a = l ⋅1 l = a , 11
11
11
11
a
= l ⋅1 l = a , 21
21
21
21
a = l ⋅1 l = a , 31
31
31
31
l
u
u
u
a
= l ⋅1 l = a , 11
12
13
14
41
41
41
41
l
l
u
u
21
22
23
24
Q =
l
l
l
u
31
32
33
34
a
l
l
l
l
41
42
43
44
a = l ⋅ u
12
u =
,
12
11
12
12
l 11
a
a = l ⋅ u
13
u =
,
13
11
13
13
l 11
a
a = l ⋅ u
14
u =
,
14
11
14
14
l 11
= l ⋅ u + l l = a − l ⋅ u , 22
21
12
22
22
22
21
12
a
= l ⋅ u + l l = a − l ⋅ u , 32
31
12
32
32
32
31
12
a
= l ⋅ u + l l = a − l ⋅ u , 42
41
12
42
42
42
41
12
l
u
u
u
11
12
13
14
l
l
u
u
21
22
23
24
Q =
l
l
l
u
31
32
33
34
l
l
l
l
41
42
43
44
a − l ⋅ u
a
= l ⋅ u + l ⋅ u 23
21
13
u
=
,
23
21
13
22
23
23
l 22
a − l ⋅ u
a
= l ⋅ u + l ⋅ u 24
21
14
u
=
,
24
21
14
22
24
24
l 22
= l ⋅ u + l ⋅ u + l l = a − l ⋅ u − l ⋅ u , 33
31
13
32
23
33
33
33
31
13
32
23
a
= l ⋅ u + l ⋅ u + l l = a − l ⋅ u − l ⋅ u , 43
41
13
42
23
43
43
43
41
13
42
23
a − l ⋅ u − l ⋅ u a
= l ⋅ u + l ⋅ u + l ⋅ u 34
31
14
32
24
u
=
,
34
31
14
32
24
33
34
34
l 33
l
u
u
u
11
12
13
14
a
= l ⋅ u + l ⋅ u + l ⋅ u + l
44
41
14
42
24
43
34
44
l
l
u
u
21
22
23
24
Q =
l
= a − l ⋅ u − l ⋅ u − l ⋅ u .
44
44
41
14
42
24
43
34
l
l
l
u
31
32
33
34
l
l
l
l
41
42
43
44
0
0 y
b
L y = b
→ y
11
1
1
l
l
0
y
b
21
22
⋅ 2 =
2
l
l
l
y
b
31
32
33
3
3
1 u
u x
y
12
13 1 1
0
1
u
x
y
23
⋅ 2 =
U x = y
→ x
2
0
0
1 x
y
3
3
l
u
u
11
12
13
Q = l
l
u
21
22
23
Przykład dla n = 3
l
l
l
31
32
33
2 x +1 x +1 x = 5
1
2
3
1 x + 2 x +1 x = 6
1
2
3
1 x +1 x + 2 x = 5
1
2
3
Zaleta metody – dla danej konfiguracji układu elektronicznego możliwość zmiany wektora wyrazów wolnych b, bez zmiany macierzy L i U