Dekompozycja LU
Rodryg Jaroszewski Kevin Wolny
Wydział Informatyki
Politechnika Poznańska
11.12.2012
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 1 / 32
Zakres Zagadnień
1
Dekompozycja LU
Co to jest dekompozycja LU
Macierze L i U
Algorytm dekompozycji
2
Przykłady
Dla macierzy dwuwymiarowej
Dla macierzy trójwymiarowej
3
Odwrotności
Dlaczego odwrotności?
Wymnażanie odwrotności macierzy eliminacji
Wymnażanie macierzy eliminacji
4
Zastosowania
Obliczanie układów równań
Wyliczanie wyznacznika macierzy A
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 2 / 32
Dekompozycja LU
Dekompozycja LU jest jest to najprostsza faktoryzacja macierzy,
pozwala również na szybkie wyliczenie wyznacznika macierzy A.
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 3 / 32
Dekompozycja LU
Dekompozycja LU jest jest to najprostsza faktoryzacja macierzy,
pozwala również na szybkie wyliczenie wyznacznika macierzy A.
Polega na rozbiciu macierzy A na dwa czynniki: L i U.
A = LU
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 3 / 32
Dekompozycja LU
Dekompozycja LU jest jest to najprostsza faktoryzacja macierzy,
pozwala również na szybkie wyliczenie wyznacznika macierzy A.
Polega na rozbiciu macierzy A na dwa czynniki: L i U.
A = LU
Co to jest L?
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 3 / 32
Dekompozycja LU
Dekompozycja LU jest jest to najprostsza faktoryzacja macierzy,
pozwala również na szybkie wyliczenie wyznacznika macierzy A.
Polega na rozbiciu macierzy A na dwa czynniki: L i U.
A = LU
Co to jest L?
Co to jest U?
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 3 / 32
Macierz górnotrójkątna U
Macierz górnotrójkątna to taka macierz, której wszystkie współczynniki
poniżej głównej przekątnej są równe zero.
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 4 / 32
Macierz górnotrójkątna U
Macierz górnotrójkątna to taka macierz, której wszystkie współczynniki
poniżej głównej przekątnej są równe zero.
îÅ‚ Å‚Å‚
u11 u12 u13
ðÅ‚
U = 0 u22 u23ûÅ‚
0 0 u33
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 4 / 32
Macierz górnotrójkątna U
Macierz górnotrójkątna to taka macierz, której wszystkie współczynniki
poniżej głównej przekątnej są równe zero.
îÅ‚ Å‚Å‚
u11 u12 u13
ðÅ‚
U = 0 u22 u23ûÅ‚
0 0 u33
Przykład
îÅ‚ Å‚Å‚
2 3 4
ðÅ‚0
U = 5 3ûÅ‚
0 0 2
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 4 / 32
Macierz dolnotrójkątna L
Macierz dolnotrójkątna to taka macierz, której wszystkie współczynniki
powyżej głównej przekątnej są równe zero oraz wspołczynniki na
głównej przekątnej są równe jeden.
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 5 / 32
Macierz dolnotrójkątna L
Macierz dolnotrójkątna to taka macierz, której wszystkie współczynniki
powyżej głównej przekątnej są równe zero oraz wspołczynniki na
głównej przekątnej są równe jeden.
îÅ‚ Å‚Å‚
1 0 0
ðÅ‚l21
L = 1 0ûÅ‚
l31 l32 1
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 5 / 32
Macierz dolnotrójkątna L
Macierz dolnotrójkątna to taka macierz, której wszystkie współczynniki
powyżej głównej przekątnej są równe zero oraz wspołczynniki na
głównej przekątnej są równe jeden.
îÅ‚ Å‚Å‚
1 0 0
ðÅ‚l21
L = 1 0ûÅ‚
l31 l32 1
Przykład
îÅ‚ Å‚Å‚
1 0 0
ðÅ‚-3
L = 1 0ûÅ‚
4 2 1
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 5 / 32
Algorytm dekompozycji LU
Aby doprowadzić macierz do postaci A = LU należy wykonać
następujące kroki:
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 6 / 32
Algorytm dekompozycji LU
Aby doprowadzić macierz do postaci A = LU należy wykonać
następujące kroki:
Eliminacja wg Gaussa macierzy A
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 6 / 32
Algorytm dekompozycji LU
Aby doprowadzić macierz do postaci A = LU należy wykonać
następujące kroki:
Eliminacja wg Gaussa macierzy A
Znalezienie macierzy eliminacji
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 6 / 32
Algorytm dekompozycji LU
Aby doprowadzić macierz do postaci A = LU należy wykonać
następujące kroki:
Eliminacja wg Gaussa macierzy A
Znalezienie macierzy eliminacji
Pomnożenie przez odwrotności macierzy eliminacji
w odwrotnej kolejności
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 6 / 32
Algorytm dekompozycji LU
Aby doprowadzić macierz do postaci A = LU należy wykonać
następujące kroki:
Eliminacja wg Gaussa macierzy A
Znalezienie macierzy eliminacji
Pomnożenie przez odwrotności macierzy eliminacji
w odwrotnej kolejności
Wymnożenie macierzy po lewej stronie macierzy U
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 6 / 32
Algorytm dekompozycji LU
Aby doprowadzić macierz do postaci A = LU należy wykonać
następujące kroki:
Eliminacja wg Gaussa macierzy A
Znalezienie macierzy eliminacji
Pomnożenie przez odwrotności macierzy eliminacji
w odwrotnej kolejności
Wymnożenie macierzy po lewej stronie macierzy U
Zapisanie równania jako A = LU
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 6 / 32
Przykład
Krok 1: Eliminacja wg Gaussa
Doprowadz
my macierz A do postaci LU
1 5
A =
2 3
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 7 / 32
Przykład
Krok 1: Eliminacja wg Gaussa
Doprowadz
my macierz A do postaci LU
1 5
A =
2 3
Po eliminacji wg Gaussa otrzymujemy macierz
1 5
B =
0 -7
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 7 / 32
Przykład
Krok 1: Eliminacja wg Gaussa
Doprowadz
my macierz A do postaci LU
1 5
A =
2 3
Po eliminacji wg Gaussa otrzymujemy macierz
1 5
B =
0 -7
Jak widać, wszystkie współczynniki macierzy B poniżej głównej
przekątnej są równe zero. Z tego wynika, że jest to już macierz U.
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 7 / 32
Przykład
Krok 2: Znalezienie macierzy eliminacji
EliminacjÄ™ wykonuje dla nas macierz eliminacji E21, z indeksem 21
ponieważ produkuje nam zero na pozycji 21 w macierzy A.
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 8 / 32
Przykład
Krok 2: Znalezienie macierzy eliminacji
EliminacjÄ™ wykonuje dla nas macierz eliminacji E21, z indeksem 21
ponieważ produkuje nam zero na pozycji 21 w macierzy A.
Macierz ta wygląda następująco:
1 0
E21 =
-2 1
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 8 / 32
Przykład
Krok 2: Znalezienie macierzy eliminacji
EliminacjÄ™ wykonuje dla nas macierz eliminacji E21, z indeksem 21
ponieważ produkuje nam zero na pozycji 21 w macierzy A.
Macierz ta wygląda następująco:
1 0
E21 =
-2 1
Dlaczego tak? Ponieważ (zgodnie z eliminacją wg Gaussa) odjęliśmy
dwa razy pierwszy wiersz od drugiego wiersza.
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 8 / 32
Przykład
Krok 2: Znalezienie macierzy eliminacji
EliminacjÄ™ wykonuje dla nas macierz eliminacji E21, z indeksem 21
ponieważ produkuje nam zero na pozycji 21 w macierzy A.
Macierz ta wygląda następująco:
1 0
E21 =
-2 1
Dlaczego tak? Ponieważ (zgodnie z eliminacją wg Gaussa) odjęliśmy
dwa razy pierwszy wiersz od drugiego wiersza.
E21A = U
1 0 1 5 1 5
=
-2 1 2 3 0 -7
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 8 / 32
Przykład
Krok 3: Pomnożenie przez macierze odwrotne w odwrotnej kolejności
Macierz odwrotna do E21 to
1 0
-1
E21 =
2 1
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 9 / 32
Przykład
Krok 3: Pomnożenie przez macierze odwrotne w odwrotnej kolejności
Macierz odwrotna do E21 to
1 0
-1
E21 =
2 1
Skoro przy eliminacji odejmujemy dwa razy pierwszy wiersz to
operacją odwrotną będzie dodanie dwa razy pierwszego wiersza.
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 9 / 32
Przykład
Krok 3: Pomnożenie przez macierze odwrotne w odwrotnej kolejności
Macierz odwrotna do E21 to
1 0
-1
E21 =
2 1
Skoro przy eliminacji odejmujemy dwa razy pierwszy wiersz to
operacją odwrotną będzie dodanie dwa razy pierwszego wiersza.
Poprzez mnożenie obu stron przez macierz odwrotną do E21
doprowadzamy do równania
-1 -1
E21 E21 A = E21 U
I
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 9 / 32
Przykład
Krok 3: Pomnożenie przez macierze odwrotne w odwrotnej kolejności
Macierz odwrotna do E21 to
1 0
-1
E21 =
2 1
Skoro przy eliminacji odejmujemy dwa razy pierwszy wiersz to
operacją odwrotną będzie dodanie dwa razy pierwszego wiersza.
Poprzez mnożenie obu stron przez macierz odwrotną do E21
doprowadzamy do równania
-1 -1
E21 E21 A = E21 U
I
Wniosek
Aby znalez
ć macierz odwrotną do macierzy eliminacji, zmieniamy
znaki współczynników poniżej głównej przekątnej na przeciwne.
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 9 / 32
Przykład
Kroki 4 i 5: Wymnożenie macierzy i zapisanie równania jako A = LU
Wszystkie macierze z lewej strony macierzy U
-1
A = E21 U
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 10 / 32
Przykład
Kroki 4 i 5: Wymnożenie macierzy i zapisanie równania jako A = LU
Wszystkie macierze z lewej strony macierzy U
-1
A = E21 U
wymnażamy (w tym przypadku jest to tylko jedna macierz), w ten
sposób powstaje macierz L.
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 10 / 32
Przykład
Kroki 4 i 5: Wymnożenie macierzy i zapisanie równania jako A = LU
Wszystkie macierze z lewej strony macierzy U
-1
A = E21 U
wymnażamy (w tym przypadku jest to tylko jedna macierz), w ten
sposób powstaje macierz L.
1 0
-1
L = E21 =
2 1
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 10 / 32
Przykład
Kroki 4 i 5: Wymnożenie macierzy i zapisanie równania jako A = LU
Wszystkie macierze z lewej strony macierzy U
-1
A = E21 U
wymnażamy (w tym przypadku jest to tylko jedna macierz), w ten
sposób powstaje macierz L.
1 0
-1
L = E21 =
2 1
Tak powstaje równanie A = LU
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 10 / 32
Przykład
Kroki 4 i 5: Wymnożenie macierzy i zapisanie równania jako A = LU
Wszystkie macierze z lewej strony macierzy U
-1
A = E21 U
wymnażamy (w tym przypadku jest to tylko jedna macierz), w ten
sposób powstaje macierz L.
1 0
-1
L = E21 =
2 1
Tak powstaje równanie A = LU
1 5 1 0 1 5
=
2 3 2 1 0 -7
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 10 / 32
Kolejny przykład
Dla macierzy trójwymiarowej
Dla macierzy dwuwymiarowej dekompozycja nie wymaga większego
wysiłku, ponieważ wykonywana jest tylko jedna eliminacja i dlatego
powstaje tylko jedna macierz eliminacji (E21).
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 11 / 32
Kolejny przykład
Dla macierzy trójwymiarowej
Dla macierzy dwuwymiarowej dekompozycja nie wymaga większego
wysiłku, ponieważ wykonywana jest tylko jedna eliminacja i dlatego
powstaje tylko jedna macierz eliminacji (E21).
Sprawa komplikuje się dla macierzy trójwymiarowych. . .
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 11 / 32
Przykład
Kroki 1 i 2: Eliminacja wg Gaussa i znajdowanie macierzy eliminacji
Przeprowadz
my teraz dekompozycję dla macierzy trójwymiarowej A:
îÅ‚ Å‚Å‚
2 4 -2
ðÅ‚
A = 4 9 -3ûÅ‚
-2 -3 7
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 12 / 32
Przykład
Kroki 1 i 2: Eliminacja wg Gaussa i znajdowanie macierzy eliminacji
Przeprowadz
my teraz dekompozycję dla macierzy trójwymiarowej A:
îÅ‚ Å‚Å‚
2 4 -2
ðÅ‚
A = 4 9 -3ûÅ‚
-2 -3 7
Dla macierzy trójwymiarowych eliminacja wg Gaussa zajmuje trzy
kroki, zamiast jednego. Dlatego też, powstaną trzy macierze eliminacji.
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 12 / 32
Przykład
Kroki 1 i 2: Eliminacja wg Gaussa i znajdowanie macierzy eliminacji
Przeprowadz
my teraz dekompozycję dla macierzy trójwymiarowej A:
îÅ‚ Å‚Å‚
2 4 -2
ðÅ‚
A = 4 9 -3ûÅ‚
-2 -3 7
Dla macierzy trójwymiarowych eliminacja wg Gaussa zajmuje trzy
kroki, zamiast jednego. Dlatego też, powstaną trzy macierze eliminacji.
Krok pierwszy
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
1 0 0 2 4 -2 2 4 -2
ðÅ‚-2 ðÅ‚ ûÅ‚
E21A = 1 0ûÅ‚ ðÅ‚ 4 9 -3ûÅ‚ = 0 1 1
0 0 1 -2 -3 7 -2 -3 7
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 12 / 32
Przykład
Kroki 1 i 2: Eliminacja wg Gaussa i znajdowanie macierzy eliminacji
Przeprowadz
my teraz dekompozycję dla macierzy trójwymiarowej A:
îÅ‚ Å‚Å‚
2 4 -2
ðÅ‚
A = 4 9 -3ûÅ‚
-2 -3 7
Dla macierzy trójwymiarowych eliminacja wg Gaussa zajmuje trzy
kroki, zamiast jednego. Dlatego też, powstaną trzy macierze eliminacji.
Krok pierwszy
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
1 0 0 2 4 -2 2 4 -2
ðÅ‚-2 ðÅ‚ ûÅ‚
E21A = 1 0ûÅ‚ ðÅ‚ 4 9 -3ûÅ‚ = 0 1 1
0 0 1 -2 -3 7 -2 -3 7
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 12 / 32
Przykład
Kroki 1 i 2: Eliminacja wg Gaussa i znajdowanie macierzy eliminacji
Krok drugi
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
1 0 0 2 4 -2 2 4 -2
ðÅ‚0 ûÅ‚ ðÅ‚0 ûÅ‚
E31(E21A) = 1 0ûÅ‚ ðÅ‚ 0 1 1 = 1 1
1 0 1 -2 -3 7 0 1 5
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 13 / 32
Przykład
Kroki 1 i 2: Eliminacja wg Gaussa i znajdowanie macierzy eliminacji
Krok drugi
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
1 0 0 2 4 -2 2 4 -2
ðÅ‚0 ûÅ‚ ðÅ‚0 ûÅ‚
E31(E21A) = 1 0ûÅ‚ ðÅ‚ 0 1 1 = 1 1
1 0 1 -2 -3 7 0 1 5
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 13 / 32
Przykład
Kroki 1 i 2: Eliminacja wg Gaussa i znajdowanie macierzy eliminacji
Krok drugi
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
1 0 0 2 4 -2 2 4 -2
ðÅ‚0 ûÅ‚ ðÅ‚0 ûÅ‚
E31(E21A) = 1 0ûÅ‚ ðÅ‚ 0 1 1 = 1 1
1 0 1 -2 -3 7 0 1 5
Krok trzeci
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
1 0 0 2 4 -2 2 4 -2
ðÅ‚0 ûÅ‚ ðÅ‚0 ûÅ‚
E32(E31E21A) = 1 0ûÅ‚ ðÅ‚0 1 1 = 1 1
0 -1 1 0 1 5 0 0 4
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 13 / 32
Przykład
Kroki 1 i 2: Eliminacja wg Gaussa i znajdowanie macierzy eliminacji
Krok drugi
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
1 0 0 2 4 -2 2 4 -2
ðÅ‚0 ûÅ‚ ðÅ‚0 ûÅ‚
E31(E21A) = 1 0ûÅ‚ ðÅ‚ 0 1 1 = 1 1
1 0 1 -2 -3 7 0 1 5
Krok trzeci
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
1 0 0 2 4 -2 2 4 -2
ðÅ‚0 ûÅ‚ ðÅ‚0 ûÅ‚
E32(E31E21A) = 1 0ûÅ‚ ðÅ‚0 1 1 = 1 1
0 -1 1 0 1 5 0 0 4
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 13 / 32
Przykład
Kroki 1 i 2: Eliminacja wg Gaussa i znajdowanie macierzy eliminacji
Krok drugi
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
1 0 0 2 4 -2 2 4 -2
ðÅ‚0 ûÅ‚ ðÅ‚0 ûÅ‚
E31(E21A) = 1 0ûÅ‚ ðÅ‚ 0 1 1 = 1 1
1 0 1 -2 -3 7 0 1 5
Krok trzeci
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
1 0 0 2 4 -2 2 4 -2
ðÅ‚0 ûÅ‚ ðÅ‚0 ûÅ‚
E32(E31E21A) = 1 0ûÅ‚ ðÅ‚0 1 1 = 1 1
0 -1 1 0 1 5 0 0 4
W ostatniej macierzy wszystkie elementy poniżej głównej przekątnej
równe są zero. Wniosek: jest to macierz U.
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 13 / 32
Przykład
Krok 3: Pomnożenie przez odwrotności macierzy eliminacji w odwrotnej kolejności
Powstaje równanie:
E32E31E21A = U
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 14 / 32
Przykład
Krok 3: Pomnożenie przez odwrotności macierzy eliminacji w odwrotnej kolejności
Powstaje równanie:
E32E31E21A = U
Mnożymy obustronnie przez odwrotności macierzy eliminacji w
odwrotnej kolejności
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 14 / 32
Przykład
Krok 3: Pomnożenie przez odwrotności macierzy eliminacji w odwrotnej kolejności
Powstaje równanie:
E32E31E21A = U
Mnożymy obustronnie przez odwrotności macierzy eliminacji w
odwrotnej kolejności
-1 -1 -1 -1 -1 -1
E21 E31 E32 E32E31E21A = E21 E31 E32 U
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 14 / 32
Przykład
Krok 3: Pomnożenie przez odwrotności macierzy eliminacji w odwrotnej kolejności
Powstaje równanie:
E32E31E21A = U
Mnożymy obustronnie przez odwrotności macierzy eliminacji w
odwrotnej kolejności
-1 -1 -1 -1 -1 -1
E21 E31 E32 E32E31E21A = E21 E31 E32 U
Macierze po lewej stronie sprowadzajÄ… siÄ™ do macierzy jednostkowych:
-1 -1 -1 -1 -1 -1
E21 E31 E32 E32 E31 E21 A = E21 E31 E32 U
I
I
I
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 14 / 32
Przykład
Krok 4: Wymnożenie macierzy po lewej stronie macierzy U
Z tego skomplikowanego równania zostaje
-1 -1 -1
A = E21 E31 E32 U
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 15 / 32
Przykład
Krok 4: Wymnożenie macierzy po lewej stronie macierzy U
Z tego skomplikowanego równania zostaje
-1 -1 -1
A = E21 E31 E32 U
-1 -1 -1
Macierze E21 E31 E32 wymnażamy od lewej strony
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 15 / 32
Przykład
Krok 4: Wymnożenie macierzy po lewej stronie macierzy U
Z tego skomplikowanego równania zostaje
-1 -1 -1
A = E21 E31 E32 U
-1 -1 -1
Macierze E21 E31 E32 wymnażamy od lewej strony
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
1 0 0 1 0 0 1 0 0
-1 -1
ðÅ‚2 ðÅ‚
E21 E31 = 1 0ûÅ‚ ðÅ‚ 0 1 0ûÅ‚ = 2 1 0ûÅ‚
0 0 1 -1 0 1 -1 0 1
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 15 / 32
Przykład
Krok 4: Wymnożenie macierzy po lewej stronie macierzy U
Z tego skomplikowanego równania zostaje
-1 -1 -1
A = E21 E31 E32 U
-1 -1 -1
Macierze E21 E31 E32 wymnażamy od lewej strony
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
1 0 0 1 0 0 1 0 0
-1 -1
ðÅ‚2 ðÅ‚
E21 E31 = 1 0ûÅ‚ ðÅ‚ 0 1 0ûÅ‚ = 2 1 0ûÅ‚
0 0 1 -1 0 1 -1 0 1
-1
Wynik jeszcze pomnożymy przez E32
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 15 / 32
Przykład
Krok 4: Wymnożenie macierzy po lewej stronie macierzy U
Z tego skomplikowanego równania zostaje
-1 -1 -1
A = E21 E31 E32 U
-1 -1 -1
Macierze E21 E31 E32 wymnażamy od lewej strony
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
1 0 0 1 0 0 1 0 0
-1 -1
ðÅ‚2 ðÅ‚
E21 E31 = 1 0ûÅ‚ ðÅ‚ 0 1 0ûÅ‚ = 2 1 0ûÅ‚
0 0 1 -1 0 1 -1 0 1
-1
Wynik jeszcze pomnożymy przez E32
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
1 0 0 1 0 0 1 0 0
ðÅ‚ ðÅ‚
2 1 0ûÅ‚ ðÅ‚0 1 0ûÅ‚ = 2 1 0ûÅ‚
-1 0 1 0 1 1 -1 1 1
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 15 / 32
Przykład
Krok 5: Zapisanie równania jako A = LU
W ten sposób doprowadzamy do równania
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 16 / 32
Przykład
Krok 5: Zapisanie równania jako A = LU
W ten sposób doprowadzamy do równania
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
2 4 -2 1 0 0 2 4 -2
ðÅ‚ ðÅ‚ ûÅ‚
4 9 -3ûÅ‚ = 2 1 0ûÅ‚ ðÅ‚0 1 1
-2 -3 7 -1 1 1 0 0 4
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 16 / 32
Przykład
Krok 5: Zapisanie równania jako A = LU
W ten sposób doprowadzamy do równania
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
2 4 -2 1 0 0 2 4 -2
ðÅ‚ ðÅ‚ ûÅ‚
4 9 -3ûÅ‚ = 2 1 0ûÅ‚ ðÅ‚0 1 1
-2 -3 7 -1 1 1 0 0 4
A = LU
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 16 / 32
Dlaczego odwrotności?
Wielu z was zapewne zastanawia się, dlaczego przerzucaliśmy całą
"grupkę" macierzy eliminacji, zamiast na początku wymnożyć je i
dopiero przerzucić. W tej części wykładu zostanie to wyjaśnione.
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 17 / 32
Dlaczego odwrotności?
Wielu z was zapewne zastanawia się, dlaczego przerzucaliśmy całą
"grupkę" macierzy eliminacji, zamiast na początku wymnożyć je i
dopiero przerzucić. W tej części wykładu zostanie to wyjaśnione.
Porównajmy dwie możliwości:
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 17 / 32
Dlaczego odwrotności?
Wielu z was zapewne zastanawia się, dlaczego przerzucaliśmy całą
"grupkę" macierzy eliminacji, zamiast na początku wymnożyć je i
dopiero przerzucić. W tej części wykładu zostanie to wyjaśnione.
Porównajmy dwie możliwości:
-1 -1 -1
Wymnożenie macierzy E21 E31 E32
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 17 / 32
Dlaczego odwrotności?
Wielu z was zapewne zastanawia się, dlaczego przerzucaliśmy całą
"grupkę" macierzy eliminacji, zamiast na początku wymnożyć je i
dopiero przerzucić. W tej części wykładu zostanie to wyjaśnione.
Porównajmy dwie możliwości:
-1 -1 -1
Wymnożenie macierzy E21 E31 E32
Wymnożenie macierzy E32E31E21
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 17 / 32
Opcja 1.
Wymnażanie odwrotności macierzy eliminacji
Wymnażanie odwrotności macierzy eliminacji ćwiczyliśmy już przy
samej dekompozycji LU, zróbmy to jednak jeszcze raz.
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 18 / 32
Opcja 1.
Wymnażanie odwrotności macierzy eliminacji
Wymnażanie odwrotności macierzy eliminacji ćwiczyliśmy już przy
samej dekompozycji LU, zróbmy to jednak jeszcze raz.
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
1 0 0 1 0 0 1 0 0
-1 -1
ðÅ‚2 ðÅ‚
E21 E31 = 1 0ûÅ‚ ðÅ‚ 0 1 0ûÅ‚ = 2 1 0ûÅ‚
0 0 1 -1 0 1 -1 0 1
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 18 / 32
Opcja 1.
Wymnażanie odwrotności macierzy eliminacji
Wymnażanie odwrotności macierzy eliminacji ćwiczyliśmy już przy
samej dekompozycji LU, zróbmy to jednak jeszcze raz.
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
1 0 0 1 0 0 1 0 0
-1 -1
ðÅ‚2 ðÅ‚
E21 E31 = 1 0ûÅ‚ ðÅ‚ 0 1 0ûÅ‚ = 2 1 0ûÅ‚
0 0 1 -1 0 1 -1 0 1
-1
Wynik jeszcze pomnożymy przez E32
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 18 / 32
Opcja 1.
Wymnażanie odwrotności macierzy eliminacji
Wymnażanie odwrotności macierzy eliminacji ćwiczyliśmy już przy
samej dekompozycji LU, zróbmy to jednak jeszcze raz.
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
1 0 0 1 0 0 1 0 0
-1 -1
ðÅ‚2 ðÅ‚
E21 E31 = 1 0ûÅ‚ ðÅ‚ 0 1 0ûÅ‚ = 2 1 0ûÅ‚
0 0 1 -1 0 1 -1 0 1
-1
Wynik jeszcze pomnożymy przez E32
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
1 0 0 1 0 0 1 0 0
ðÅ‚ ðÅ‚
2 1 0ûÅ‚ ðÅ‚0 1 0ûÅ‚ = 2 1 0ûÅ‚
-1 0 1 0 1 1 -1 1 1
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 18 / 32
Opcja 1.
Wymnażanie odwrotności macierzy eliminacji
Wymnażanie odwrotności macierzy eliminacji ćwiczyliśmy już przy
samej dekompozycji LU, zróbmy to jednak jeszcze raz.
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
1 0 0 1 0 0 1 0 0
-1 -1
ðÅ‚2 ðÅ‚
E21 E31 = 1 0ûÅ‚ ðÅ‚ 0 1 0ûÅ‚ = 2 1 0ûÅ‚
0 0 1 -1 0 1 -1 0 1
-1
Wynik jeszcze pomnożymy przez E32
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
1 0 0 1 0 0 1 0 0
ðÅ‚ ðÅ‚
2 1 0ûÅ‚ ðÅ‚0 1 0ûÅ‚ = 2 1 0ûÅ‚
-1 0 1 0 1 1 -1 1 1
Jak wiemy, jest to już macierz L.
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 18 / 32
Opcja 1.
Wymnażanie odwrotności macierzy eliminacji
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
1 0 0 1 0 0 1 0 0
ðÅ‚2 1 0ûÅ‚ ðÅ‚
0 1 0ûÅ‚ ðÅ‚0 1 0ûÅ‚
0 0 1 -1 0 1 0 1 1
-1 -1 -1
E21 E31 E32
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 19 / 32
Opcja 1.
Wymnażanie odwrotności macierzy eliminacji
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
1 0 0 1 0 0 1 0 0
ðÅ‚2 1 0ûÅ‚ ðÅ‚
0 1 0ûÅ‚ ðÅ‚0 1 0ûÅ‚
0 0 1 -1 0 1 0 1 1
-1 -1 -1
E21 E31 E32
Jak widać, współczynniki poszczególnych macierzy po prostu
"wskoczyły" do wyniku.
îÅ‚ Å‚Å‚
1 0 0
ðÅ‚
L = 2 1 0ûÅ‚
-1 1 1
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 19 / 32
Opcja 1.
Wymnażanie odwrotności macierzy eliminacji
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
1 0 0 1 0 0 1 0 0
ðÅ‚2 1 0ûÅ‚ ðÅ‚
0 1 0ûÅ‚ ðÅ‚0 1 0ûÅ‚
0 0 1 -1 0 1 0 1 1
-1 -1 -1
E21 E31 E32
Jak widać, współczynniki poszczególnych macierzy po prostu
"wskoczyły" do wyniku.
îÅ‚ Å‚Å‚
1 0 0
ðÅ‚
L = 2 1 0ûÅ‚
-1 1 1
Cały czas są na swoich miejscach!
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 19 / 32
Opcja 2.
Wymnażanie macierzy eliminacji
Zobaczmy co się stanie, gdy przemnożymy od lewej strony macierze
eliminacji E32E31E21.
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 20 / 32
Opcja 2.
Wymnażanie macierzy eliminacji
Zobaczmy co się stanie, gdy przemnożymy od lewej strony macierze
eliminacji E32E31E21.
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
1 0 0 1 0 0 1 0 0
ðÅ‚0 ðÅ‚0
E32E31 = 1 0ûÅ‚ ðÅ‚0 1 0ûÅ‚ = 1 0ûÅ‚
0 -1 1 1 0 1 1 -1 1
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 20 / 32
Opcja 2.
Wymnażanie macierzy eliminacji
Zobaczmy co się stanie, gdy przemnożymy od lewej strony macierze
eliminacji E32E31E21.
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
1 0 0 1 0 0 1 0 0
ðÅ‚0 ðÅ‚0
E32E31 = 1 0ûÅ‚ ðÅ‚0 1 0ûÅ‚ = 1 0ûÅ‚
0 -1 1 1 0 1 1 -1 1
Wynik jeszcze pomnożymy przez E21
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 20 / 32
Opcja 2.
Wymnażanie macierzy eliminacji
Zobaczmy co się stanie, gdy przemnożymy od lewej strony macierze
eliminacji E32E31E21.
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
1 0 0 1 0 0 1 0 0
ðÅ‚0 ðÅ‚0
E32E31 = 1 0ûÅ‚ ðÅ‚0 1 0ûÅ‚ = 1 0ûÅ‚
0 -1 1 1 0 1 1 -1 1
Wynik jeszcze pomnożymy przez E21
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
1 0 0 1 0 0 1 0 0
ðÅ‚0 1 0ûÅ‚ ðÅ‚-2 1 0ûÅ‚ = ðÅ‚-2 1 0ûÅ‚
1 -1 1 0 0 1 3 -1 1
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 20 / 32
Opcja 2.
Wymnażanie macierzy eliminacji
Zobaczmy co się stanie, gdy przemnożymy od lewej strony macierze
eliminacji E32E31E21.
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
1 0 0 1 0 0 1 0 0
ðÅ‚0 ðÅ‚0
E32E31 = 1 0ûÅ‚ ðÅ‚0 1 0ûÅ‚ = 1 0ûÅ‚
0 -1 1 1 0 1 1 -1 1
Wynik jeszcze pomnożymy przez E21
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
1 0 0 1 0 0 1 0 0
ðÅ‚0 1 0ûÅ‚ ðÅ‚-2 1 0ûÅ‚ = ðÅ‚-2 1 0ûÅ‚
1 -1 1 0 0 1 3 -1 1
Skąd wzięła się ta trójka?
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 20 / 32
Opcja 2.
Wymnażanie macierzy eliminacji
îÅ‚ Å‚Å‚
1 0 0
ðÅ‚-2 1 0ûÅ‚
E32E31E21 =
3 -1 1
Skąd wzięła się ta trójka?
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 21 / 32
Opcja 2.
Wymnażanie macierzy eliminacji
îÅ‚ Å‚Å‚
-2 -4 -2
ðÅ‚-4
A = -9 -3ûÅ‚
-2 -3 -7
Skąd wzięła się ta trójka?
Aby odpowiedzieć na to pytanie, prześledz
my etapy eliminacji wg
Gaussa macierzy A:
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 21 / 32
Opcja 2.
Wymnażanie macierzy eliminacji
îÅ‚ Å‚Å‚
-2 -4 -2
ðÅ‚-0
A = -1 -1ûÅ‚
-2 -3 -7
Skąd wzięła się ta trójka?
Aby odpowiedzieć na to pytanie, prześledz
my etapy eliminacji wg
Gaussa macierzy A:
odjęliśmy dwa razy wiersz pierwszy od wiersza drugiego
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 21 / 32
Opcja 2.
Wymnażanie macierzy eliminacji
îÅ‚ Å‚Å‚
-2 -4 -2
ðÅ‚-0
A = -1 -1ûÅ‚
-0 -1 -5
Skąd wzięła się ta trójka?
Aby odpowiedzieć na to pytanie, prześledz
my etapy eliminacji wg
Gaussa macierzy A:
odjęliśmy dwa razy wiersz pierwszy od wiersza drugiego
dodaliśmy wiersz pierwszy do wiersza trzeciego
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 21 / 32
Opcja 2.
Wymnażanie macierzy eliminacji
îÅ‚ Å‚Å‚
-2 -4 -2
ðÅ‚-0
A = -1 -1ûÅ‚
-0 -0 -4
Skąd wzięła się ta trójka?
Aby odpowiedzieć na to pytanie, prześledz
my etapy eliminacji wg
Gaussa macierzy A:
odjęliśmy dwa razy wiersz pierwszy od wiersza drugiego
dodaliśmy wiersz pierwszy do wiersza trzeciego
odjęliśmy wiersz drugi od wiersza trzeciego
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 21 / 32
Opcja 2.
Wymnażanie macierzy eliminacji
îÅ‚ Å‚Å‚
-2 -4 -2
ðÅ‚-0
A = -1 -1ûÅ‚
-0 -0 -4
Skąd wzięła się ta trójka?
Aby odpowiedzieć na to pytanie, prześledz
my etapy eliminacji wg
Gaussa macierzy A:
odjęliśmy dwa razy wiersz pierwszy od wiersza drugiego
dodaliśmy wiersz pierwszy do wiersza trzeciego
odjęliśmy wiersz drugi od wiersza trzeciego
Uwaga!
Nie zapominajmy, że w wierszu drugim jest już dwa razy ujemny
wiersz pierwszy! Oprócz odjęcia drugiego wiersza dodaliśmy również
dwa razy wiersz pierwszy, co daje w sumie trzy wiersze.
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 21 / 32
Wnioski
Gdy mnożyliśmy macierze eliminacji, pojawiała się tajemnicza trójka,
której nie przewidzieliśmy. Przy mnożeniu odwrotności macierzy
eliminacji problem ten zniknÄ…Å‚. Wniosek jest prosty:
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 22 / 32
Wnioski
Gdy mnożyliśmy macierze eliminacji, pojawiała się tajemnicza trójka,
której nie przewidzieliśmy. Przy mnożeniu odwrotności macierzy
eliminacji problem ten zniknÄ…Å‚. Wniosek jest prosty:
Twierdzenie
Gdy mnożymy macierze odwrotne, wystarczy przepisać współczynniki
na odpowiadające im miejsca bezpośrednio do macierzy L.
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 22 / 32
Wnioski
Gdy mnożyliśmy macierze eliminacji, pojawiała się tajemnicza trójka,
której nie przewidzieliśmy. Przy mnożeniu odwrotności macierzy
eliminacji problem ten zniknÄ…Å‚. Wniosek jest prosty:
Twierdzenie
Gdy mnożymy macierze odwrotne, wystarczy przepisać współczynniki
na odpowiadające im miejsca bezpośrednio do macierzy L.
Współczynniki te można zapisywać od razu podczas eliminacji wg
Gaussa macierzy A, by następnie zmienić ich znak i wpisać do
macierzy L.
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 22 / 32
Zastosowania
Macierz w postaci A = LU pozwala między innymi na:
Szybkie obliczanie układów równań
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 23 / 32
Zastosowania
Macierz w postaci A = LU pozwala między innymi na:
Szybkie obliczanie układów równań
Wyliczenie wyznacznika macierzy A
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 23 / 32
Zastosowania
Macierz w postaci A = LU pozwala między innymi na:
Szybkie obliczanie układów równań
Wyliczenie wyznacznika macierzy A
O to w zasadzie nam chodzi. Dekompozycja LU pozwala na
zmniejszenie liczby operacji potrzebnych do rozwiązywania układów
równań.
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 23 / 32
Zastosowania
Macierz w postaci A = LU pozwala między innymi na:
Szybkie obliczanie układów równań
Wyliczenie wyznacznika macierzy A
O to w zasadzie nam chodzi. Dekompozycja LU pozwala na
zmniejszenie liczby operacji potrzebnych do rozwiązywania układów
równań.
Dlaczego? Spójrzmy.
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 23 / 32
Złożoność obliczeniowa
Ile operacji należy wykonać, aby doprowadzić macierz A do postaci
A = LU?
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 24 / 32
Złożoność obliczeniowa
Ile operacji należy wykonać, aby doprowadzić macierz A do postaci
A = LU?
Co to jest operacja?
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 24 / 32
Złożoność obliczeniowa
Ile operacji należy wykonać, aby doprowadzić macierz A do postaci
A = LU?
Co to jest operacja?
Typową operacją wykonywaną w metodzie Gaussa jest mnożenie i
odejmowanie, więc traktujemy te dwa działania jako jedną operację.
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 24 / 32
Złożoność obliczeniowa
Ile operacji należy wykonać, aby doprowadzić macierz A do postaci
A = LU?
Co to jest operacja?
Typową operacją wykonywaną w metodzie Gaussa jest mnożenie i
odejmowanie, więc traktujemy te dwa działania jako jedną operację.
Twierdzenie
Dla macierzy o wymiarach n × n liczba operacji potrzebnych do
1
sprowadzenia macierzy do postaci A = LU wynosi H" n3
3
Co to w zasadzie dla nas oznacza?
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 24 / 32
Złożoność obliczeniowa
Jest to ważny aspekt optymalizacji algorytmów rozwiązujących takie
układy.
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 25 / 32
Złożoność obliczeniowa
Jest to ważny aspekt optymalizacji algorytmów rozwiązujących takie
układy.
Jeżeli dodamy tylko jedną kolumnę (np. kolumnę z wynikami), to ilość
obliczeń potrzebnych na wyliczenie potrzebnych nam wyników spada
do n2.
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 25 / 32
Złożoność obliczeniowa
Jest to ważny aspekt optymalizacji algorytmów rozwiązujących takie
układy.
Jeżeli dodamy tylko jedną kolumnę (np. kolumnę z wynikami), to ilość
obliczeń potrzebnych na wyliczenie potrzebnych nam wyników spada
do n2.
Wniosek
Przewaga rozkładu LU nad eliminacją wg Gaussa polega na tym, iż
przy pomocy rozkładu LU mozna rozwiązywać dowolnie wiele równań
z takimi samymi lewymi stronami (macierzami), przy czym  kosztownÄ…
część, a więc samą faktoryzację, oblicza się tylko raz.
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 25 / 32
Wyliczanie wyznacznika macierzy A
Aby obliczyć wyznacznik macierzy A posłużymy się twierdzeniem
Cauchy ego o wyznacznikach:
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 26 / 32
Wyliczanie wyznacznika macierzy A
Aby obliczyć wyznacznik macierzy A posłużymy się twierdzeniem
Cauchy ego o wyznacznikach:
Twierdzenie Cauchy ego
det(AB) = det A · det B
gdzie det A oznacza wyznacznik macierzy A.
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 26 / 32
Wyliczanie wyznacznika macierzy A
Aby obliczyć wyznacznik macierzy A posłużymy się twierdzeniem
Cauchy ego o wyznacznikach:
Twierdzenie Cauchy ego
det(AB) = det A · det B
gdzie det A oznacza wyznacznik macierzy A.
Stąd, aby obliczyć wyznacznik macierzy A, wystarczy policzyć
wyznaczniki macierzy L oraz U.
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 26 / 32
Wyliczanie wyznacznika macierzy A
Wyznacznik macierzy L
Jak wiemy, macierz L wygląda następująco:
îÅ‚ Å‚Å‚
1 0 0
ðÅ‚l21
L = 1 0ûÅ‚
l31 l32 1
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 27 / 32
Wyliczanie wyznacznika macierzy A
Wyznacznik macierzy L
Jak wiemy, macierz L wygląda następująco:
îÅ‚ Å‚Å‚
1 0 0
ðÅ‚l21
L = 1 0ûÅ‚
l31 l32 1
Obliczmy jej wyznacznik (wg reguły Sarrusa):
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 27 / 32
Wyliczanie wyznacznika macierzy A
Wyznacznik macierzy L
Jak wiemy, macierz L wygląda następująco:
îÅ‚ Å‚Å‚
1 0 0
ðÅ‚l21
L = 1 0ûÅ‚
l31 l32 1
Obliczmy jej wyznacznik (wg reguły Sarrusa):
det L = 1 · 1 · 1 + l21 · l32 · 0 + l31 · 0 · 0 - 0 · 1 · l31 - 0 · l32 · 1 - 1 · 0 · l21
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 27 / 32
Wyliczanie wyznacznika macierzy A
Wyznacznik macierzy L
Jak wiemy, macierz L wygląda następująco:
îÅ‚ Å‚Å‚
1 0 0
ðÅ‚l21
L = 1 0ûÅ‚
l31 l32 1
Obliczmy jej wyznacznik (wg reguły Sarrusa):
det L = 1 · 1 · 1 + l21 · l32 · 0 + l31 · 0 · 0 - 0 · 1 · l31 - 0 · l32 · 1 - 1 · 0 · l21
0
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 27 / 32
Wyliczanie wyznacznika macierzy A
Wyznacznik macierzy L
Jak wiemy, macierz L wygląda następująco:
îÅ‚ Å‚Å‚
1 0 0
ðÅ‚l21
L = 1 0ûÅ‚
l31 l32 1
Obliczmy jej wyznacznik (wg reguły Sarrusa):
det L = 1 · 1 · 1 + l21 · l32 · 0 + l31 · 0 · 0 - 0 · 1 · l31 - 0 · l32 · 1 - 1 · 0 · l21
0
Czyli po prostu 1.
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 27 / 32
Wyliczanie wyznacznika macierzy A
Wyznacznik macierzy U
Natomiast macierz U wygląda następująco:
îÅ‚ Å‚Å‚
u11 u12 u13
ðÅ‚
U = 0 u22 u23ûÅ‚
0 0 u33
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 28 / 32
Wyliczanie wyznacznika macierzy A
Wyznacznik macierzy U
Natomiast macierz U wygląda następująco:
îÅ‚ Å‚Å‚
u11 u12 u13
ðÅ‚
U = 0 u22 u23ûÅ‚
0 0 u33
Obliczmy jej wyznacznik (wg reguły Sarrusa):
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 28 / 32
Wyliczanie wyznacznika macierzy A
Wyznacznik macierzy U
Natomiast macierz U wygląda następująco:
îÅ‚ Å‚Å‚
u11 u12 u13
ðÅ‚
U = 0 u22 u23ûÅ‚
0 0 u33
Obliczmy jej wyznacznik (wg reguły Sarrusa):
det U = u11·u22·u33+0·0·u13+0·u12·u23-u13·u22·0-u12·0·u33-u11·u23·0
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 28 / 32
Wyliczanie wyznacznika macierzy A
Wyznacznik macierzy U
Natomiast macierz U wygląda następująco:
îÅ‚ Å‚Å‚
u11 u12 u13
ðÅ‚
U = 0 u22 u23ûÅ‚
0 0 u33
Obliczmy jej wyznacznik (wg reguły Sarrusa):
Ponownie te elementy są równe zero:
0 · 0 · u13 + 0 · u12 · u23 - u13 · u22 · 0 - u12 · 0 · u33 - u11 · u23 · 0
0
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 28 / 32
Wyliczanie wyznacznika macierzy A
Wyznacznik macierzy U
Natomiast macierz U wygląda następująco:
îÅ‚ Å‚Å‚
u11 u12 u13
ðÅ‚
U = 0 u22 u23ûÅ‚
0 0 u33
Obliczmy jej wyznacznik (wg reguły Sarrusa):
Ponownie te elementy są równe zero:
0 · 0 · u13 + 0 · u12 · u23 - u13 · u22 · 0 - u12 · 0 · u33 - u11 · u23 · 0
0
Zostaje nam
det U = u11 · u22 · u33
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 28 / 32
Wnioski
det A = det U = u11 · u22 · u33
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 29 / 32
Wnioski
det A = det U = u11 · u22 · u33
Twierdzenie
Aby obliczyć wyznacznik macierzy A wystarczy tylko wymnożyć
elementy z głównej przekątnej macierzy U.
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 29 / 32
Wnioski
det A = det U = u11 · u22 · u33
Twierdzenie
Aby obliczyć wyznacznik macierzy A wystarczy tylko wymnożyć
elementy z głównej przekątnej macierzy U.
Dzięki dekompozycji LU ponownie zaoszczędziliśmy sporo czasu.
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 29 / 32
Przykład
Szybkie wyliczanie wyznacznika macierzy A
Skorzystamy z macierzy A, dla której przeprowadzaliśmy
dekompozycję wczesniej na tym wykładzie:
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
2 4 -2 1 0 0 2 4 -2
ðÅ‚ ðÅ‚ ûÅ‚
4 9 -3ûÅ‚ = 2 1 0ûÅ‚ ðÅ‚0 1 1
-2 -3 7 -1 1 1 0 0 4
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 30 / 32
Przykład
Szybkie wyliczanie wyznacznika macierzy A
îÅ‚ Å‚Å‚
2 4 -2
ðÅ‚
A = 4 9 -3ûÅ‚
-2 -3 7
Obliczamy wyznacznik tradycyjnie (reguła Sarrusa)
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 31 / 32
Przykład
Szybkie wyliczanie wyznacznika macierzy A
îÅ‚ Å‚Å‚
2 4 -2
ðÅ‚
A = 4 9 -3ûÅ‚
-2 -3 7
Obliczamy wyznacznik tradycyjnie (reguła Sarrusa)
det A =
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 31 / 32
Przykład
Szybkie wyliczanie wyznacznika macierzy A
îÅ‚ Å‚Å‚
2 4 -2
ðÅ‚
A = 4 9 -3ûÅ‚
-2 -3 7
Obliczamy wyznacznik tradycyjnie (reguła Sarrusa)
det A =
= 2·9·7+4·(-3)·(-2)+(-2)·4·(-3)-(-2)·9·(-2)-(-3)·(-3)·2-7·4·4
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 31 / 32
Przykład
Szybkie wyliczanie wyznacznika macierzy A
îÅ‚ Å‚Å‚
2 4 -2
ðÅ‚
A = 4 9 -3ûÅ‚
-2 -3 7
Obliczamy wyznacznik tradycyjnie (reguła Sarrusa)
det A =
= 2·9·7+4·(-3)·(-2)+(-2)·4·(-3)-(-2)·9·(-2)-(-3)·(-3)·2-7·4·4
= 126 + 24 + 24 - 36 - 18 - 112
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 31 / 32
Przykład
Szybkie wyliczanie wyznacznika macierzy A
îÅ‚ Å‚Å‚
2 4 -2
ðÅ‚
A = 4 9 -3ûÅ‚
-2 -3 7
Obliczamy wyznacznik tradycyjnie (reguła Sarrusa)
det A =
= 2·9·7+4·(-3)·(-2)+(-2)·4·(-3)-(-2)·9·(-2)-(-3)·(-3)·2-7·4·4
= 126 + 24 + 24 - 36 - 18 - 112
= 8
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 31 / 32
Przykład
Szybkie wyliczanie wyznacznika macierzy A
A teraz korzystając z dekompozycji LU wiemy, że
det A = det U = u11 · u22 · u33
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 32 / 32
Przykład
Szybkie wyliczanie wyznacznika macierzy A
A teraz korzystając z dekompozycji LU wiemy, że
det A = det U = u11 · u22 · u33
îÅ‚ Å‚Å‚
2 4 -2
ðÅ‚0 ûÅ‚
U = 1 1
0 0 4
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 32 / 32
Przykład
Szybkie wyliczanie wyznacznika macierzy A
A teraz korzystając z dekompozycji LU wiemy, że
det A = det U = u11 · u22 · u33
îÅ‚ Å‚Å‚
2 4 -2
ðÅ‚0 ûÅ‚
U = 1 1
0 0 4
det U = 2 · 1 · 4 = 8
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 32 / 32
Przykład
Szybkie wyliczanie wyznacznika macierzy A
A teraz korzystając z dekompozycji LU wiemy, że
det A = det U = u11 · u22 · u33
îÅ‚ Å‚Å‚
2 4 -2
ðÅ‚0 ûÅ‚
U = 1 1
0 0 4
det U = 2 · 1 · 4 = 8
Oczywiście, oba wyniki muszą się zgadzać.
Dzięki dekompozycji LU obliczenia są o wiele prostsze. Również ilość
czasu potrzebnego na wyliczenie wyznacznika spada znaczÄ…co.
R. Jaroszewski, K. Wolny Dekompozycja LU 11.12.2012 32 / 32