Rozkład LU
Artur Piękosz
Politechnika Krakowska
Kraków, 2012
Artur Piękosz
Mamy rozwiązać duży układ równań postaci
Ax = b.
Założymy, że macierz A jest kwadratowa nieosobliwa.
Problem
Jak szybko rozwiązać duży układ równań liniowych? Jak ominąć liczenie wyznacznika z definicji?
Idea bazowa: zrobić wiele zer w rozważanych macierzach.
Idea Gaussa: wyeliminować po kolei zmienne w kolejnych równaniach, dochodząc do jednego równania z jedną zmienną.
Inaczej: przekształcić macierz współczynników do postaci trójkątnej górnej, czyli zrobić same zera pod przekątną.
Artur Piękosz
Konkretyzacja idei: przekształcić macierz A do postaci macierzy trójkątnej górnej za pomocą układu współczynników tworzących macierz trójkątną dolną.
Inaczej: rozłożyć daną macierz współczynników A na iloczyn macierzy trójkątnej dolnej i macierzy trójkątnej górnej.
A = LU
Jeśli mamy już rozkład LU, to rozwiązujemy układ równań Ly = b
na pomocnicze zmienne y , a następnie rozwiązujemy układ równań
Ux = y
na oryginalne zmienne x .
Artur Piękosz
Przykład
1 2 3
Jeśli rozłożymy macierz A =
3 2 1
na iloczyn
2 1 3
1
0
0 1
2
3
12
3
1
0
0 −4 −8 , to układ równań Ax =
24
2 3/4 1
0
0
3
36
12
13
rozwiązujemy szybko: y =
−12
−11
oraz x =
.
21
7
Możemy wybrać warianty:
a) macierz L ma tylko jedynki na przekątnej (metoda Doolittle’a),
b) macierz U ma tylko jedynki na przekątnej (metoda Crouta).
Artur Piękosz
Mamy przedstawić macierz A w postaci iloczynu macierzy L i U. W przypadku metody Doolittle’a mamy mieć
1
0
0 u
11
u 12
u 1 n
a 11 a 12
a 1 n
l 21
1
0 0
u 22
u 2 n
a 21
a 22
a 2 n
=
.
. . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . .
ln 1 ln 2
1
0
0
unn
an 1 an 2
ann
Łatwo znajdujemy pierwszy wiersz macierzy U: u 11 = a 11, u 12 = a 12, ..., u 1 n = a 1 n.
Następnie łatwo znajdujemy pierwszą kolumnę macierzy L: a
a
a
a
l
21
21
n 1
n 1
21 =
=
, ..., ln 1 =
=
.
u 11
a 11
u 11
a 11
Mając te informacje, możemy teraz znaleźć drugi wiersz macierzy U, następnie drugą kolumnę macierzy L, i tak dalej.
Artur Piękosz
Oczywiście układy równań 3 na 3 (lub 4 na 4) i tak rozwiązalibyśmy wyznacznikami, rozważmy więc przykład układu o 5 równaniach i 5 niewiadomych. Weźmy następującą macierz współczynników
3 5 5 2 2
2
5 0 0 1
A =
4
5 3 5 0 .
0 4 5 3 2
3 6 6 5 5
Wyznaczymy rozkład LU metodą Doolittle’a.
Artur Piękosz
Bez trudu obliczamy
u 11 = 3, u 12 = 5, u 13 = 5, u 14 = 2, u 15 = 2.
Następnie znajdujemy
2
4
l 21 = , l 31 = , l 41 = 0, l 51 = 1.
3
3
Mamy zatem
1
0
0
0
0 3
5
5
2
2
3 5 5 2 2
2
1
0
0
0
0 u
2 5 0 0 1
3
22
u 23 u 24 u 25
4
l
0
0
u
=
4 5 3 5 0
3
32
1
0
0
33
u 34 u 35
0 l
0
0
0
u
0 4 5 3 2
42
l 43
1
0
44
u 45
1 l 52 l 53 l 54 1
0
0
0
0
u 55
3 6 6 5 5
Artur Piękosz
Następnie znajdujemy drugi wiersz macierzy U
5
−10
−4
−1
u 22 = , u 23 =
, u 24 =
, u 25 =
3
3
3
3
oraz drugą kolumnę macierzy L
12
3
l 32 = −1, l 42 =
, l 52 = .
5
5
Mamy teraz
1
0
0
0
0 3 5
5
2
2
3 5 5 2 2
2
−10
−4
−1
1
0
0
0
0
5
2 5 0 0 1
3
3
3
3
3
4
−1
1
0
0
0 0
u
=
4 5 3 5 0 .
3
33
u 34 u 35
0
12
l
0 0
0
u
0 4 5 3 2
5
43
1
0
44
u 45
1
3
l
0 0
0
0
u
3 6 6 5 5
5
53
l 54 1
55
Artur Piękosz
Analogicznie znajdujemy trzeci wiersz macierzy U, trzecią kolumnę macierzy L, czwarty wiersz macierzy U, czwartą kolumnę macierzy L i piąty wiersz macierzy U. Ostatecznie rozkładem jest
1
0
0
0
0 3 5
5
2
2
3 5 5 2 2
2
−10
−4
−1
1
0
0
0
0
5
2 5 0 0 1
3
3
3
3
3
4
−1
1
0
0
0 0
−7
1
−3
=
4 5 3 5 0 .
3
0
12
−13
1
0 0 0
0
282
−97
0 4 5 3 2
5
7
35
35
1
3
−3
74
1
0 0
0
0
475
3 6 6 5 5
5
7
141
141
Możemy teraz szybko rozwiązywać układy równań z naszą macierzą współczynników A oraz dowolną kolumną wyrazów wolnych b.
Artur Piękosz
1
1
249
−2
−
0
80
3
Dla b =
0 mamy y = −2 oraz x =
1
273
.
950
0
−74
−283
35
0
−49
−98
141
Uwagi
1. Rozwiązując układy równań z kolejnymi wektorami bazy kanonicznej jako b (czyli z kolumnami macierzy jednostkowej) otrzymujemy kolumny macierzy A−1 (odwrotnej do A).
2. Z rozkładu LU łatwo obliczyć można także wyznacznik macierzy A.
Artur Piękosz
Uwagi
3. Tym razem rozkład sie udał, ale możemy mieć problem dzielenia przez zero. Dlatego czasem trzeba zmieniać kolejność równań, co jest równoważne z mnożeniem macierzy A przez macierz permutacji P (macierz odwzorowania liniowego permutującego zmienne). Mamy wtedy rozkład PA = LU.
Rozwiązanie układu równań Ax = b jest równoważne rozwiązaniu układu równań PAx = Pb.
Artur Piękosz
Złożoność obliczeniowa rozkładu LU (zarówno metody Doolittle’a, jak i metody Crouta) to O( n 3). Dokładniej, potrzeba około 1 n 3 mnożeń, około 1 n 3 dodawań oraz tylko 3
3
około 1 n 2 dzieleń.
2
Tymczasem złożoność obliczeniowa wzorów Cramera liczonych ze wzoru jawnego na wyznacznik to aż O( n( n + 1)!) operacji.
Uwaga
Jeśli macierz A ma współczynniki całkowite, to i obliczenia wyznaczników dokonywane są na liczbach całkowitych (dzielenie występuje tylko na ostatnim etapie rozwiązywania układu ze wzorów Cramera).
Artur Piękosz
Po angielsku:
Wikipedia (http://en.wikipedia.org/) pod hasłami: Numerical linear algebra
LU decomposition
http://www.mymathlib.com/matrices/linearsystems/
http://numericalmethods.eng.usf.edu/
Gaussian Elimination
LU Decomposition
http://math.fullerton.edu/mathews/n2003/lufactormod.html Po polsku:
Wikipedia (http://pl.wikipedia.org) pod hasłami: Rozkład macierzy
Metoda LU
http://wazniak.mimuw.edu.pl/index.php?title=MN05
Artur Piękosz