Rozkład LU macierzy
: 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]}\)
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]}\)