Odwrtotność macierzy używając rozkładu LU

Przestrzenie wektorowe, bazy, liniowa niezależność, macierze.... Formy kwadratowe, twierdzenia o klasyfikacji...
jjc
Użytkownik
Użytkownik
Posty: 12
Rejestracja: 20 mar 2012, o 02:55
Płeć: Mężczyzna
Lokalizacja: PL
Podziękował: 1 raz

Odwrtotność macierzy używając rozkładu LU

Post autor: jjc »

Witam.

Nie do końca wiem jak wygląda algorytm odwracania macierzy z użyciem LU
Moja macierz:
\(\displaystyle{ A = \begin{bmatrix}3 & 1 & 6\\2 & 1 & 3\\1 & 1 & 1\end{bmatrix}}\)
Wiem też że:
\(\displaystyle{ A^{-1} = (LU)^{-1} = U^{-1}L^{-1}}\)
Nie wiem natomiast jak mam obliczyć \(\displaystyle{ L^{-1}}\) oraz \(\displaystyle{ U^{-1}}\)

Bardzo proszę o pomoc.
miodzio1988

Odwrtotność macierzy używając rozkładu LU

Post autor: miodzio1988 »

Np eliminacją Gaussa. Dwa kroki dokładnie wtedy robimy
jjc
Użytkownik
Użytkownik
Posty: 12
Rejestracja: 20 mar 2012, o 02:55
Płeć: Mężczyzna
Lokalizacja: PL
Podziękował: 1 raz

Odwrtotność macierzy używając rozkładu LU

Post autor: jjc »

Prosiłbym o więcej wyjaśnień.
Przede wszystkim czy mógłbyś jakoś w miarę przystępnie wytłumaczyć sam rozkład (najszybsza/najłatwiejsza metoda),
oraz co się dzieje w następnych krokach?
Obliczeniami postaram się zając sam.

EDIT:
ok, +/- wiem jak dokonać rozkładu, jednak co dalej aby macierz odwrócić?
Chodzi głównie o macierz górnotrójkątną ponieważ w dolnotrójkątnej zmienia się chyba tylko wartości pod diagonalą (dodatnie na ujemne i odwrotnie)
Awatar użytkownika
Mariusz M
Użytkownik
Użytkownik
Posty: 6903
Rejestracja: 25 wrz 2007, o 01:03
Płeć: Mężczyzna
Lokalizacja: 53°02'N 18°35'E
Podziękował: 2 razy
Pomógł: 1246 razy

Odwrtotność macierzy używając rozkładu LU

Post autor: Mariusz M »

\(\displaystyle{ AA^{-1}=I}\)

Możesz macierz odwrotną rozbić na kolumny i rozwiązać
\(\displaystyle{ 2n}\) trójkątnych układów równań liniowych
(każdy układ trójkątny w czasie \(\displaystyle{ O\left( n^2\right)}\))

Rozkład LU

0. Wprowadzasz kolumnę w której przechowujesz pozycję jedynek w macierzy permutacji
1. Szukasz w kolumnie poniżej przekątnej elementu o największej wartości bezwzględnej
Jeśli element ten będzie miał większą wartość bezwzględną niż ten co na przekątnej zamieniasz
wiersze (także w dodatkowej kolumnie)
2. Wiersz przepisujesz bez zmian a kolumnę dzielisz przez element na głównej przekątnej
3. Modyfikujesz wartość elementów pozostałej części macierzy
\(\displaystyle{ a_{ij}=a_{ij}-a_{i1}a_{1j}}\)
Wykonujesz kroki \(\displaystyle{ 1\cdots 3}\) dla macierzy o wymiarach \(\displaystyle{ \left( n-1\right)\times\left( n-1\right)}\)
(dla macierzy z wykreśloną pierwszą kolumną i pierwszym wierszem)
jjc
Użytkownik
Użytkownik
Posty: 12
Rejestracja: 20 mar 2012, o 02:55
Płeć: Mężczyzna
Lokalizacja: PL
Podziękował: 1 raz

Odwrtotność macierzy używając rozkładu LU

Post autor: jjc »

Hm... w notatkach znalazłem zarys algorytmu, wydaje mi się że różni się od podanego przez Ciebie,
zastanawiałem się czy mógłbym liczyć na drobne wyjaśnienie
kroki w nim rozpoczynają się od:
\(\displaystyle{ L^{(1)}A^{(1)} =
\begin{bmatrix}1 & 0 & 0\\- \frac{2}{3} & 1 & 0\\ - \frac{1}{3}& 0 & 1\end{bmatrix}
\begin{bmatrix}3 & 1 & 6\\2 & 1 & 3\\1 & 1 & 1\end{bmatrix} =
\begin{bmatrix}3 & 1 & 6\\0 & \frac{1}{3} & -1\\0 & \frac{2}{3} & -1\end{bmatrix}}\)

\(\displaystyle{ L^{(1)}A^{(1)} = ...}\)
Nie wiem na jakiej zasadzie dobrane zostały elementy pod przekątną w \(\displaystyle{ L^{(1)}}\),
czy tylko tak "na oko" aby wyzerować elementy pod przekątną w pierwszej kolumnie \(\displaystyle{ A^{(2)}}\) czy też jest na to jakiś wzór?
Rozumiem że na przekątnej w \(\displaystyle{ L^{(1..n)}}\) mają być zawsze same 1?
Awatar użytkownika
Mariusz M
Użytkownik
Użytkownik
Posty: 6903
Rejestracja: 25 wrz 2007, o 01:03
Płeć: Mężczyzna
Lokalizacja: 53°02'N 18°35'E
Podziękował: 2 razy
Pomógł: 1246 razy

Odwrtotność macierzy używając rozkładu LU

Post autor: Mariusz M »

\(\displaystyle{ A = \begin{bmatrix}3 & 1 & 6\\2 & 1 & 3\\1 & 1 & 1\end{bmatrix}}\)

\(\displaystyle{ \begin{bmatrix}3 & 1 & 6\\2 & 1 & 3\\1 & 1 & 1\end{bmatrix}\\
\begin{bmatrix}3 & 1 & 6\\ \frac{2}{3} & 1 & 3\\ \frac{1}{3} & 1 & 1\end{bmatrix}\\
\begin{bmatrix}3 & 1 & 6\\ \frac{2}{3} & \frac{1}{3} & -1\\ \frac{1}{3} & \frac{2}{3} & -1\end{bmatrix}\\
\begin{bmatrix}3 & 1 & 6\\ \frac{1}{3} & \frac{2}{3} & -1\\ \frac{2}{3} & \frac{1}{3} & -1\end{bmatrix}\\
\begin{bmatrix}3 & 1 & 6\\ \frac{1}{3} & \frac{2}{3} & -1\\ \frac{2}{3} & \frac{1}{2} & -1\end{bmatrix}\\
\begin{bmatrix}3 & 1 & 6\\ \frac{1}{3} & \frac{2}{3} & -1\\ \frac{2}{3} & \frac{1}{2} & - \frac{1}{2} \end{bmatrix}\\}\)


W twoim algorytmie wykonujesz eliminację Gaussa macierzowo

Mnożysz macierz wyjściową przez taką macierz aby wyzerować żądany element

Twój algorytm działa mniej więcej tak

\(\displaystyle{ E^{\left( 3,2\right) }E^{\left( 3,1\right) }E^{\left( 2,1\right) }A=U\\
A=\left(E^{\left( 3,2\right) }E^{\left( 3,1\right) }E^{\left( 2,1\right) } \right)^{-1}U\\
A=\left(\left( E^ {\left( 2,1\right)}\right)^{-1}\left( E^{\left( 3,1\right) }\right) ^{-1}\left( E^{\left( 3,2\right) }\right) ^{-1}\right)U\\}\)
jjc
Użytkownik
Użytkownik
Posty: 12
Rejestracja: 20 mar 2012, o 02:55
Płeć: Mężczyzna
Lokalizacja: PL
Podziękował: 1 raz

Odwrtotność macierzy używając rozkładu LU

Post autor: jjc »

genialnie! teraz sprawa jest już jasna
+1 dla Ciebie
ODPOWIEDZ