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: 6712
Rejestracja: 25 wrz 2007, o 01:03
Płeć: Mężczyzna
Lokalizacja: 53°02'N 18°35'E
Pomógł: 1216 razy

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 \(\displaystyle{ \left[ A\right]_{n \times n}= \left[L \right] _{n \times n}\left[U \right] _{n \times n}}\) 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 \(\displaystyle{ \left[ P\right]_{n \times n}\left[ A\right]_{n \times n}= \left[L \right] _{n \times n}\left[U \right] _{n \times n}}\)

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 \(\displaystyle{ \left| a_{ij}\right| \ i \ge j}\)
Trzeba również wprowadzić nową kolumnę w której będą przechowywane pozycje jedynek w macierzy permutacji

Macierz \(\displaystyle{ \left[U \right]_{n \times n}}\)
jest macierzą po eliminacji Gaussa

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

Rozkładu LU można też dokonać metodą Doolittle'a
Ze wzoru na mnożenie macierzy otrzymujemy układ równań liniowych o \(\displaystyle{ n^{2}}\)
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

\(\displaystyle{ \left[A \right]_{n \times n}\left[X \right]_{n \times 1}=\left[B \right]_{n \times 1}}\)

\(\displaystyle{ \left[L \right]_{n \times n}\left[U \right]_{n \times n}\left[X \right]_{n \times 1}=\left[B \right]_{n \times 1}}\)

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

\(\displaystyle{ \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}}\)

\(\displaystyle{ \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}}\)

Niech \(\displaystyle{ \left[L \right]_{n \times n}^{-1}\left[B \right]_{n \times 1}= \left[Y \right] _{n \times 1}}\)

Wówczas otrzymamy

\(\displaystyle{ \left[U \right]_{n \times n}\left[X \right]_{n \times 1}=\left[Y \right]_{n \times 1}}\)

\(\displaystyle{ \left[L \right]_{n \times n}^{-1}\left[B \right]_{n \times 1}= \left[Y \right] _{n \times 1}}\)

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

\(\displaystyle{ \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}}\)

\(\displaystyle{ \left[B \right]_{n \times 1}= \left[L \right] _{n \times n}\left[Y \right] _{n \times 1}}\)

\(\displaystyle{ \left[L \right] _{n \times n}\left[Y \right] _{n \times 1}=\left[B \right]_{n \times 1}}\)


Ostatecznie otrzymujemy

\(\displaystyle{ \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}}\)

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 :

\(\displaystyle{ \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]}\)

rozkład LU

\(\displaystyle{ \left[ \begin{array}{cccc}2&4&5&8 \\1&7&2&4\\3&9&6&1\\8&2&9&7 \end{array} \right]}\)
\(\displaystyle{ w_{2}- \frac{1}{2}w_{1}}\)
\(\displaystyle{ \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]}\)
\(\displaystyle{ w_{3}- \frac{3}{2}w_{1}}\)
\(\displaystyle{ \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]}\)
\(\displaystyle{ w_{4}-4w_{1}}\)
\(\displaystyle{ \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]}\)
\(\displaystyle{ w_{3}- \frac{3}{5} w_{2}}\)
\(\displaystyle{ \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]}\)
\(\displaystyle{ w_{4}- \left( - \frac{14}{5} \right) w_{2}}\)
\(\displaystyle{ \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]}\)
\(\displaystyle{ w_{4}- \frac{31}{3} w_{3}}\)
\(\displaystyle{ \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]}\)

\(\displaystyle{ \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]}\)


\(\displaystyle{ \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]}\)

\(\displaystyle{ \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}}\)
\(\displaystyle{ \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}}\)


\(\displaystyle{ \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]}\)

\(\displaystyle{ \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}}\)

\(\displaystyle{ \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]}\)
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

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

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
\(\displaystyle{ 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

\(\displaystyle{ \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

\(\displaystyle{ \begin{bmatrix} 3&2&7\\0&4&2\\2&3&1\end{bmatrix}}\)

\(\displaystyle{ w_{3}- \frac{2}{3}w_{1}}\)

\(\displaystyle{ \begin{bmatrix} 3&2&7\\0&4&2\\0& \frac{5}{3} &- \frac{11}{3} \end{bmatrix}}\)

\(\displaystyle{ w_{3}- \frac{5}{12}w_{2}}\)

\(\displaystyle{ \begin{bmatrix} 3&2&7\\0&4&2\\0&0&- \frac{9}{2} \end{bmatrix}}\)

\(\displaystyle{ \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}}\)

\(\displaystyle{ \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}}\)

\(\displaystyle{ \begin{cases} y_{1}=1 \\ y_{2}=0\\y_{3}=- \frac{2}{3} \end{cases}}\)

\(\displaystyle{ \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}}\)

\(\displaystyle{ \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}}\)


\(\displaystyle{ \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}}\)

\(\displaystyle{ \begin{cases} y_{1}=0 \\ y_{2}=1\\y_{3}=- \frac{5}{12} \end{cases}}\)

\(\displaystyle{ \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}}\)

\(\displaystyle{ \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}}\)

\(\displaystyle{ \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}}\)

\(\displaystyle{ \begin{cases} y_{1}=0 \\ y_{2}=0\\y_{3}=1 \end{cases}}\)

\(\displaystyle{ \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}}\)

\(\displaystyle{ \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}}\)


\(\displaystyle{ A^{-1}= \frac{1}{54} \begin{bmatrix} 2&-19&24 \\-4&11&6\\8&5&-12 \end{bmatrix}}\)

ODPOWIEDZ