Rozkład LU macierzy

Zbiór wzorów, definicji i najczęściej poruszanych problemów z Algebry.
Awatar użytkownika
mariuszm
Użytkownik
Użytkownik
Posty: 6695
Rejestracja: 25 wrz 2007, o 01:03
Płeć: Mężczyzna
Lokalizacja: 53°02'N 18°35'E

Rozkład LU macierzy

Post autor: mariuszm » 29 wrz 2009, o 23:39

Za pomocą rozkładu LU można rozwiązać układ równań liniowych lub
obliczyć wartość wyznacznika macierzy

Macierz może zostać rozłożona na iloczyn macierzy [latex]\left[ A\right]_{n \times n}= \left[L \right] _{n \times n}\left[U \right] _{n \times n}[/latex] za pomocą eliminacji Gaussa

Czasami jednak nie uda nam się rozłożyć macierzy za pomocą eliminacji Gaussa
Należy wówczas zastosować eliminację Gaussa z częściowym wyborem elementu podstawowego
aby otrzymać rozkład [latex]\left[ P\right]_{n \times n}\left[ A\right]_{n \times n}= \left[L \right] _{n \times n}\left[U \right] _{n \times n}[/latex]

Częściowy wybór elementu podstawowego polega na tym że zanim przystąpimy do eliminacji
szukamy elementu największego co do wartości bezwzględnej w danej kolumnie [latex]\left| a_{ij}\right| \ i \ge j[/latex]
Trzeba również wprowadzić nową kolumnę w której będą przechowywane pozycje jedynek w macierzy permutacji

Macierz [latex]\left[U \right]_{n \times n}[/latex]
jest macierzą po eliminacji Gaussa

Macierz [latex]\left[L \right]_{n \times n}[/latex]
jest macierzą współczynników użytych do zerowania odpowiednich elementów macierzy [latex]\left[A \right]_{n \times n}[/latex]

Rozkładu LU można też dokonać metodą Doolittle'a
Ze wzoru na mnożenie macierzy otrzymujemy układ równań liniowych o [latex]n^{2}[/latex]
niewiadomych
Układ ten dość łatwo jest rozwiązać metodą podstawiania

Teraz pokażę jak użyć rozkładu LU do rozwiązywania układów równań liniowych

Zapiszmy układ równań liniowych w postaci macierzowej

[latex]\left[A \right]_{n \times n}\left[X \right]_{n \times 1}=\left[B \right]_{n \times 1}[/latex]

[latex]\left[L \right]_{n \times n}\left[U \right]_{n \times n}\left[X \right]_{n \times 1}=\left[B \right]_{n \times 1}[/latex]

Pomnóżmy lewostronnie przez [latex]\left[L \right]_{n \times n}^{-1}[/latex]

[latex]\left[L \right]_{n \times n}^{-1}\left[L \right]_{n \times n}\left[U \right]_{n \times n}\left[X \right]_{n \times 1}=\left[L \right]_{n \times n}^{-1}\left[B \right]_{n \times 1}[/latex]

[latex]\left[U \right]_{n \times n}\left[X \right]_{n \times 1}=\left[L \right]_{n \times n}^{-1}\left[B \right]_{n \times 1}[/latex]

Niech [latex]\left[L \right]_{n \times n}^{-1}\left[B \right]_{n \times 1}= \left[Y \right] _{n \times 1}[/latex]

Wówczas otrzymamy

[latex]\left[U \right]_{n \times n}\left[X \right]_{n \times 1}=\left[Y \right]_{n \times 1}[/latex]

[latex]\left[L \right]_{n \times n}^{-1}\left[B \right]_{n \times 1}= \left[Y \right] _{n \times 1}[/latex]

Pomnóżmy powyższe równanie lewostronnie przez [latex]\left[L \right] _{n \times n}[/latex]

[latex]\left[L \right] _{n \times n}\left[L \right]_{n \times n}^{-1}\left[B \right]_{n \times 1}= \left[L \right] _{n \times n}\left[Y \right] _{n \times 1}[/latex]

[latex]\left[B \right]_{n \times 1}= \left[L \right] _{n \times n}\left[Y \right] _{n \times 1}[/latex]

[latex]\left[L \right] _{n \times n}\left[Y \right] _{n \times 1}=\left[B \right]_{n \times 1}[/latex]


Ostatecznie otrzymujemy

[latex]\begin{cases} \left[L \right] _{n \times n}\left[Y \right] _{n \times 1}=\left[B \right]_{n \times 1} \\ \left[U \right]_{n \times n}\left[X \right]_{n \times 1}=\left[Y \right]_{n \times 1} \end{cases}[/latex]

Pierwszy układ równań liniowych należy rozwiązać za pomocą postępowania wprzód
Drugi układ równań liniowych należy rozwiązać za pomocą postępowania wstecz

Rozkładu LU można także użyć do obliczenia wyznacznika macierzy
Jeżeli nie potrzeba było używać metody z częściowym wyborem elementu podstawowego
to przy założeniu że na macierzy L elementy diagonalne (na głównej przekątnej) są równe jeden
wyznacznik jest równy iloczynowi elementów diagonalnych macierzy U
Jeżeli użyliśmy metody z wyborem elementu podstawowego to znak wyznacznika ustalamy przy pomocy macierzy permutacji

Przykład :

[latex]\left[ \begin{array}{cccc}2&4&5&8 \\1&7&2&4\\3&9&6&1\\8&2&9&7 \end{array} \right] \left[ \begin{array}{c} x_{1}&x_{2}&x_{3}&x_{4} \end{array} \right] = \left[ \begin{array}{c} 87&49&79&121\end{array} \right][/latex]

rozkład LU

[latex]\left[ \begin{array}{cccc}2&4&5&8 \\1&7&2&4\\3&9&6&1\\8&2&9&7 \end{array} \right][/latex]
[latex]w_{2}- \frac{1}{2}w_{1}[/latex]
[latex]\left[ \begin{array}{cccc}2&4&5&8 \\0&5&- \frac{1}{2} &0\\3&9&6&1\\8&2&9&7 \end{array} \right][/latex]
[latex]w_{3}- \frac{3}{2}w_{1}[/latex]
[latex]\left[ \begin{array}{cccc}2&4&5&8 \\0&5&- \frac{1}{2} &0\\0&3&- \frac{3}{2} &-11\\8&2&9&7 \end{array} \right][/latex]
[latex]w_{4}-4w_{1}[/latex]
[latex]\left[ \begin{array}{cccc}2&4&5&8 \\0&5&- \frac{1}{2} &0\\0&3&- \frac{3}{2} &-11\\0&-14&-11&-25 \end{array} \right][/latex]
[latex]w_{3}- \frac{3}{5} w_{2}[/latex]
[latex]\left[ \begin{array}{cccc}2&4&5&8 \\0&5&- \frac{1}{2} &0\\0&0&- \frac{6}{5} &-11\\0&-14&-11&-25 \end{array} \right][/latex]
[latex]w_{4}- \left( - \frac{14}{5} \right) w_{2}[/latex]
[latex]\left[ \begin{array}{cccc}2&4&5&8 \\0&5&- \frac{1}{2} &0\\0&0&- \frac{6}{5} &-11\\0&0&- \frac{62}{5} &-25 \end{array} \right][/latex]
[latex]w_{4}- \frac{31}{3} w_{3}[/latex]
[latex]\left[ \begin{array}{cccc}2&4&5&8 \\0&5&- \frac{1}{2} &0\\0&0&- \frac{6}{5} &-11\\0&0&- 0 & \frac{266}{3} \end{array} \right][/latex]

[latex]\left[ \begin{array}{cccc}2&4&5&8 \\1&7&2&4\\3&9&6&1\\8&2&9&7 \end{array} \right]=
\left[ \begin{array}{cccc}1&0&0&0 \\ \frac{1}{2}&1&0&0\\ \frac{3}{2}& \frac{3}{5}&1&0\\4&- \frac{14}{5}& \frac{31}{3}&1\end{array} \right]\left[ \begin{array}{cccc}2&4&5&8 \\0&5&- \frac{1}{2} &0\\0&0&- \frac{6}{5} &-11\\0&0&- 0 & \frac{266}{3} \end{array} \right][/latex]


[latex]\left[ \begin{array}{cccc}1&0&0&0 \\ \frac{1}{2}&1&0&0\\ \frac{3}{2}& \frac{3}{5}&1&0\\4&- \frac{14}{5}& \frac{31}{3}&1\end{array} \right] \left[ \begin{array}{c}y_{1}&y_{2}&y_{3}&y_{4}\end{array} \right]= \left[ \begin{array}{c}87&49&79&121 \end{array} \right][/latex]

[latex]\begin{cases} y_{1}=87 \\ \frac{87}{2}+y_{2}=49\\ \frac{261}{2}+ \frac{33}{10}+y_{3}=79\\348- \frac{154}{10}-\frac{31 \cdot 274}{15} +y_{4}=121 \end{cases}[/latex]
[latex]\begin{cases} y_{1}=87 \\ y_{2}=49- \frac{87}{2}= \frac{98-87}{2}= \frac{11}{2} \\ y_{3}=79- \frac{261}{2}- \frac{33}{10}= \frac{790-1305-33}{10}= \frac{790-1338}{10}= -\frac{548}{10}= -\frac{274}{5}\\y_{4}=121-348+ \frac{154}{10}+ \frac{31 \cdot 274}{15}= \frac{-681+1745}{3}= \frac{1064}{3} \end{cases}[/latex]


[latex]\left[ \begin{array}{cccc}2&4&5&8 \\0&5&- \frac{1}{2} &0\\0&0&- \frac{6}{5} &-11\\0&0&- 0 & \frac{266}{3} \end{array} \right] \left[ \begin{array}{c}x_{1}&x_{2}&x_{3}&x_{4} \end{array} \right]= \left[ \begin{array}{c}87& \frac{11}{2}&- \frac{274}{5}& \frac{1064}{3} \end{array} \right][/latex]

[latex]\begin{cases} x_{4}= \frac{1064}{3} \cdot \frac{3}{266}=4 \\ x_{3}=- \frac{5}{6} \left( - \frac{274}{5}+44 \right)=- \frac{5}{6} \left( \frac{-274+220}{5} \right)=- \frac{ \left(-54 \right) }{6} =9 \\x_{2}= \frac{1}{5} \left( \frac{11}{2}+ \frac{9}{2} \right)= \frac{1}{5} \cdot \frac{20}{2}=2\\x_{2}= \frac{1}{2} \left(87-32-45-8 \right)= \frac{1}{2} \left(87-85 \right) = \frac{1}{2} \cdot 2=1 \end{cases}[/latex]

[latex]\left[ \begin{array}{c}x_{1}&x_{2}&x_{3}&x_{4} \end{array}\right]= \left[ \begin{array}{c}1&2&9&4 \end{array}\right][/latex]

Awatar użytkownika
mariuszm
Użytkownik
Użytkownik
Posty: 6695
Rejestracja: 25 wrz 2007, o 01:03
Płeć: Mężczyzna
Lokalizacja: 53°02'N 18°35'E

Rozkład LU macierzy

Post autor: mariuszm » 14 paź 2009, o 06:05

Rozkład LU z wyborem elementu podstawowego 1. Wprowadzamy nową kolumnę w której będziemy przechowywać pozycje jedynek w macierzy permutacji 2. W kolumnie szukamy elementu o największej wartości bezwzględnej i jeśli znajdziemy to zamieniamy wiersze 3. Dzielimy wszystkie elementy w kolumnie poniżej elementu podstawowego przez element podstawowy 4. Obliczamy uzupełnienie Schura 5.Powtarzamy kroki 2..4 n-1 razy Uzupełnienie Schura \(a_{ij}=a_{ij}-a_{ik}\cdot a_{k,j}\) gdzie k jest numerem iteracji Rozkładu LU można dokonać jeszcze w ten sposób \(\begin{cases} lu_{ij}=a_{ij}- \sum_{k=1}^{i-1}lu_{ik}lu_{kj} \ i \geq j \\ lu_{ji}= \frac{a_{ji}- \sum_{k=1}^{i-1}lu_{jk}lu_{ki} }{lu_{ii}} \ i<j \end{cases}\) Zaletą rozkładu LU jest to że można w prosty sposób rozwiązywać kilka układów równań różniących się tylko kolumną wyrazów wolnych Jednym z takich przykładów jest obliczanie macierzy odwrotnej Rozwiązujemy n układów równań gdzie kolumna wyrazów wolnych jest kolejną kolumną macierzy jednostkowej Jeżeli używamy rozkładu LU z wyborem elementu głównego to kolumny macierzy odwrotnej ustawiamy zgodnie z macierzą permutacji \(\begin{bmatrix} 3&2&7\\0&4&2\\2&3&1\end{bmatrix}\) \(w_{3}- \frac{2}{3}w_{1}\) \(\begin{bmatrix} 3&2&7\\0&4&2\\0& \frac{5}{3} &- \frac{11}{3} \end{bmatrix}\) \(w_{3}- \frac{5}{12}w_{2}\) \(\begin{bmatrix} 3&2&7\\0&4&2\\0&0&- \frac{9}{2} \end{bmatrix}\) \(\begin{bmatrix} 3&2&7\\0&4&2\\2&3&1\end{bmatrix}= \begin{bmatrix} 1&0&0 \\ 0&1&0\\ \frac{2}{3}& \frac{5}{12}& 1 \end{bmatrix} \cdot \begin{bmatrix} 3&2&7 \\ 0&4&2\\0&0&- \frac{9}{2} \end{bmatrix}\) \(\begin{bmatrix} 1&0&0 \\ 0&1&0\\ \frac{2}{3}& \frac{5}{12}& 1 \end{bmatrix} \begin{bmatrix} y_{1} \\ y_{2}\\y_{3} \end{bmatrix}= \begin{bmatrix} 1 \\ 0\\0 \end{bmatrix}\) \(\begin{cases} y_{1}=1 \\ y_{2}=0\\y_{3}=- \frac{2}{3} \end{cases}\) \(\begin{bmatrix} 3&2&7 \\ 0&4&2\\0&0&- \frac{9}{2} \end{bmatrix} \begin{bmatrix} x_{1} \\ x_{2}\\x_{3} \end{bmatrix}= \begin{bmatrix} 1 \\ 0\\- \frac{2}{3} \end{bmatrix}\) \(\begin{cases} x_{3}=- \frac{2}{3} \cdot \frac{ \left( -2\right) }{9}= \frac{4}{27}= \frac{8}{54}\\ x_{2}= \frac{1}{4} \left( 0- \frac{2 \cdot 8}{54} \right)=- \frac{4}{54}\\ x_{1}=\frac{1}{3} \left(1- \frac{56}{54}-2 \frac{ \left( -4\right) }{54} \right)= \frac{1}{3} \left( \frac{54-56+8}{54} \right) = \frac{1}{3} \cdot \frac{6}{54}= \frac{2}{54} \end{cases}\) \(\begin{bmatrix} 1&0&0 \\ 0&1&0\\ \frac{2}{3}& \frac{5}{12}& 1 \end{bmatrix} \begin{bmatrix} y_{1} \\ y_{2}\\y_{3} \end{bmatrix}= \begin{bmatrix} 0 \\ 1\\0 \end{bmatrix}\) \(\begin{cases} y_{1}=0 \\ y_{2}=1\\y_{3}=- \frac{5}{12} \end{cases}\) \(\begin{bmatrix} 3&2&7 \\ 0&4&2\\0&0&- \frac{9}{2} \end{bmatrix} \begin{bmatrix} x_{1} \\ x_{2}\\x_{3} \end{bmatrix}= \begin{bmatrix} 0 \\ 1\\- \frac{5}{12} \end{bmatrix}\) \(\begin{cases} x_{3}=- \frac{5}{12} \cdot \frac{ \left( -2\right) }{9}= \frac{10}{108}= \frac{5}{54}\\ x_{2}= \frac{1}{4} \left( 1- \frac{2 \cdot 5}{54} \right)= \frac{11}{54}\\x_{1}= \frac{1}{3} \left(- \frac{35}{54}-2 \frac{ \left( 11\right) }{54} \right)= \frac{1}{3} \left( \frac{-35-22}{54} \right) = \frac{1}{3} \cdot \frac{-57}{54}= -\frac{19}{54} \end{cases}\) \(\begin{bmatrix} 1&0&0 \\ 0&1&0\\ \frac{2}{3}& \frac{5}{12}& 1 \end{bmatrix} \begin{bmatrix} y_{1} \\ y_{2}\\y_{3} \end{bmatrix}= \begin{bmatrix} 0 \\ 0\\1 \end{bmatrix}\) \(\begin{cases} y_{1}=0 \\ y_{2}=0\\y_{3}=1 \end{cases}\) \(\begin{bmatrix} 3&2&7 \\ 0&4&2\\0&0&- \frac{9}{2} \end{bmatrix} \begin{bmatrix} x_{1} \\ x_{2}\\x_{3} \end{bmatrix}= \begin{bmatrix} 0 \\ 0\\1 \end{bmatrix}\) \(\begin{cases} x_{3}=1 \cdot \frac{ \left( -2\right) }{9}= \frac{-2}{9}= -\frac{12}{54}\\ x_{2}= \frac{1}{4} \left( - \frac{2 \cdot \left(-12 \right) }{54} \right)= \frac{6}{54}\\x_{1}= \frac{1}{3} \left(- \frac{7 \cdot \left(-12 \right) }{54}-2 \frac{ \left(6\right) }{54} \right)= \frac{1}{3} \left( \frac{84-12}{54} \right) = \frac{1}{3} \cdot \frac{72}{54}= \frac{24}{54} \end{cases}\) \(A^{-1}= \frac{1}{54} \begin{bmatrix} 2&-19&24 \\-4&11&6\\8&5&-12 \end{bmatrix}\)

ODPOWIEDZ