szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna
PostNapisane: 29 wrz 2009, o 23:39 
Użytkownik
Avatar użytkownika

Posty: 6685
Lokalizacja: 53°02'N 18°35'E
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 \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 \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 \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 \left[U \right]_{n \times n}
jest macierzą po eliminacji Gaussa

Macierz \left[L \right]_{n \times n}
jest macierzą współczynników użytych do zerowania odpowiednich elementów macierzy \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 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

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

\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 \left[L \right]_{n \times n}^{-1}

\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}

\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 \left[L \right]_{n \times n}^{-1}\left[B \right]_{n \times 1}= \left[Y \right] _{n \times 1}

Wówczas otrzymamy

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

\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 \left[L \right] _{n \times n}

\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}

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

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


Ostatecznie otrzymujemy

\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 :

\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

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

\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]

\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}
\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}


\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]

\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}

\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]
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2019
Góra
Mężczyzna
PostNapisane: 14 paź 2009, o 06:05 
Użytkownik
Avatar użytkownika

Posty: 6685
Lokalizacja: 53°02'N 18°35'E
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}
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Rozkład LU macierzy - zadanie 2  edo_900  0
 Rozkład LU macierzy - zadanie 4  matinf  5
 Rozkład LU macierzy - zadanie 5  marpus  5
 Rozkład LU macierzy - zadanie 3  matinf  0
 Wyznacznik macierzy - metoda Chió  Gouranga  2
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl