Rozwiązywanie układów równań metodą dekompozycji LU
Załó\
my, \
e trzeba wielokrotnie rozwiązywać układ równań liniowych
dla tej samej macierzy współczynników A, ale dla ró\
nych wektorów B.
Metody eliminacji Gaussa i Gaussa-Jordana nie sÄ… efektywne do tego celu, gdy\
wymagajÄ… operacji
zarówno na macierzy A, jak i na wektorze B pomimo tego, \
e macierz A jest zawsze taka sama.
W takim przypadku korzystniejsze jest zastosowanie metody LU, polegającej na rozkładzie zadanej
macierzy A na iloczyn dwóch macierzy trójkątnej dolnej L i górnej U.
Zatem
IstotÄ™ tej operacji opisuje poni\
sza zale\
ność zapisana dla macierzy rzędu 3:
0 0
1
1 0 0
0 0
1
Otrzymujemy:
Załó\
my, \
e macierze trójkątne L i U są znane. Wówczas problem rozwiązania układu równań względem
wektora kolumnowego X mo\
na podzielić na dwa etapy. W pierwszym etapie z równania:
wyznacza się wektor D, który związany jest z poszukiwanym rozwiązaniem następująco:
Zatem drugi etap polega na wyznaczeniu wektora X z równania zapisanego powy\
ej.
Oba wymienione etapy procesu rozwiązywania realizowane są we względnie prosty sposób, a to dzięki
trójkątnym macierzom L i U.
Po wprowadzeniu nowego wektora B oblicza się tylko nowy wektor D, a następnie wyznacza wektor X
stanowiÄ…cy poszukiwane rozwiÄ…zanie. Macierze L i U nie sÄ… przetwarzane na nowo, co w istotnym stopniu
zmniejsza ilość obliczeń.
O macierzach tych we wstępie zało\
ono, \
e są znane. W ogólnym przypadku do i ich wyliczenia u\
ywa
się następujących wzorów rekurencyjnych:
1
- 1 -
Rozwiązywanie układów równań metodą dekompozycji LU
Wyznaczanie kolejnych elementów macierzy L i U robi się naprzemiennie, tj. raz wyznacza wiersz
macierzy U, raz kolumnÄ™ macierzy L.
Liczba działań potrzebna do rozkładu:
" mno\
enia:
" dodawania: .
Przykład (macierz 3x3)
5 3 2
1 2 0
3 0 4
Pierwszy wiersz macierzy U:
5
3
2
Pierwsza kolumna macierzy L:
1 1
5
1 1 3
· 3
5 5
Drugi wiersz macierzy U:
1 7
2 · 3
5 5
1 2
0 · 2
5 5
Druga kolumna macierzy L:
1 5 3 5 9 9
· · 0 · 3 ·
7 5 7 5 5
Trzeci wiersz macierzy U:
6 18 140 42 18 80 16
4
5 35 35 35 35 35 7
- 2 -
Rozwiązywanie układów równań metodą dekompozycji LU
1 0 0 5 3 2
1 7 2
5 3 2
1 0 0
1 2 0 5 5 5
·
3 9 16
3 0 4
1 0 0
5 5 7
- 3 -