Metoda dekompozycji LU
metoda dokładna rozwi
ą
zywania
układów równa
ń
liniowych
Metoda dekompozycji LU
metoda dokładna rozwi
ą
zywania
układów równa
ń
liniowych
Metoda dekompozycji LU
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
U x = y
Najpierw musimy obliczy
ć
macierz L i macierz U
(1)
(2)
Macierz U
( ) ( )
( )
( )
( )
( )
=
1
0
0
0
1
0
0
1
0
1
3
3
2
2
2
23
1
1
1
13
1
12
L
M
O
M
M
M
L
L
L
n
n
n
a
a
a
a
a
a
U
Macierz L
( )
( ) ( )
( ) ( ) ( )
( ) ( ) ( )
( )
=
n
nn
n
n
n
a
a
a
a
a
a
a
a
a
a
L
M
O
M
M
M
L
L
L
3
3
2
2
1
1
3
33
2
32
1
31
2
22
1
21
1
11
0
0
0
0
0
0
L
(3)
(4)
=
⋅
44
43
42
41
34
33
32
31
24
23
22
21
14
13
12
11
34
24
23
14
13
12
44
43
42
41
33
32
31
22
21
11
1
0
0
0
1
0
0
1
0
1
0
0
0
0
0
0
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
u
u
u
u
u
u
l
l
l
l
l
l
l
l
l
l
Algorytm Crouta
Przykład dla n = 4
Pomocnicza macierz
Q
=
44
43
42
41
34
33
32
31
24
23
22
21
14
13
12
11
l
l
l
l
u
l
l
l
u
u
l
l
u
u
u
l
Q
(5)
(6)
16
14
10
4
15
13
9
3
12
11
8
2
7
6
5
1
Elementy macierzy Q, dla n = 4, s
ą
obliczane w kolejno
ś
ci zaznaczonej
w poni
Ŝ
szej tablicy
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.
=
44
43
42
41
34
33
32
31
24
23
22
21
14
13
12
11
l
l
l
l
u
l
l
l
u
u
l
l
u
u
u
l
Q
Bior
ą
c pod uwag
ę
zale
Ŝ
no
ść
(5), wykonujemy obliczenia dla kolejnego elementu
ij
a
w postaci iloczynu i-tego wiersza macierzy L i j-tej kolumny macierzy U
1
11
11
⋅
=
l
a
11
11
a
l
=
,
1
21
21
⋅
=
l
a
21
21
a
l
=
,
1
31
31
⋅
=
l
a
31
31
a
l
=
,
1
41
41
⋅
=
l
a
41
41
a
l
=
,
12
11
12
u
l
a
⋅
=
11
12
12
l
a
u
=
,
13
11
13
u
l
a
⋅
=
11
13
13
l
a
u
=
,
14
11
14
u
l
a
⋅
=
11
14
14
l
a
u
=
,
=
44
43
42
41
34
33
32
31
24
23
22
21
14
13
12
11
l
l
l
l
u
l
l
l
u
u
l
l
u
u
u
l
Q
22
12
21
22
l
u
l
a
+
⋅
=
12
21
22
22
u
l
a
l
⋅
−
=
,
32
12
31
32
l
u
l
a
+
⋅
=
12
31
32
32
u
l
a
l
⋅
−
=
,
42
12
41
42
l
u
l
a
+
⋅
=
12
41
42
42
u
l
a
l
⋅
−
=
,
23
22
13
21
23
u
l
u
l
a
⋅
+
⋅
=
22
13
21
23
23
l
u
l
a
u
⋅
−
=
,
24
22
14
21
24
u
l
u
l
a
⋅
+
⋅
=
22
14
21
24
24
l
u
l
a
u
⋅
−
=
,
=
44
43
42
41
34
33
32
31
24
23
22
21
14
13
12
11
l
l
l
l
u
l
l
l
u
u
l
l
u
u
u
l
Q
33
23
32
13
31
33
l
u
l
u
l
a
+
⋅
+
⋅
=
23
32
13
31
33
33
u
l
u
l
a
l
⋅
−
⋅
−
=
,
43
23
42
13
41
43
l
u
l
u
l
a
+
⋅
+
⋅
=
23
42
13
41
43
43
u
l
u
l
a
l
⋅
−
⋅
−
=
,
34
33
24
32
14
31
34
u
l
u
l
u
l
a
⋅
+
⋅
+
⋅
=
33
24
32
14
31
34
34
l
u
l
u
l
a
u
⋅
−
⋅
−
=
,
44
34
43
24
42
14
41
44
l
u
l
u
l
u
l
a
+
⋅
+
⋅
+
⋅
=
34
43
24
42
14
41
44
44
u
l
u
l
u
l
a
l
⋅
−
⋅
−
⋅
−
=
.
=
44
43
42
41
34
33
32
31
24
23
22
21
14
13
12
11
l
l
l
l
u
l
l
l
u
u
l
l
u
u
u
l
Q
L y = b
→
y
U x = y
→
x
Przykład dla n = 3
=
⋅
3
2
1
3
2
1
33
32
31
22
21
11
0
0
0
b
b
b
y
y
y
l
l
l
l
l
l
=
⋅
3
2
1
3
2
1
23
13
12
1
0
0
1
0
1
y
y
y
x
x
x
u
u
u
=
33
32
31
23
22
21
13
12
11
l
l
l
u
l
l
u
u
l
Q
Przykład
Zaleta metody – dla danej konfiguracji układu elektronicznego
mo
Ŝ
liwo
ść
zmiany wektora wyrazów wolnych b, bez zmiany macierzy L i U
5
2
1
1
6
1
2
1
5
1
1
2
3
2
1
3
2
1
3
2
1
=
+
+
=
+
+
=
+
+
x
x
x
x
x
x
x
x
x