Skocz do zawartości

  •  
  • Mini kompendium
  • MimeTeX
  • Regulamin

Zdjęcie

rozkład LU

STUDIA

  • Nie możesz napisać tematu
  • Zaloguj się aby odpowiedzieć
10 odpowiedzi w tym temacie

#1 xawery

xawery

    Operator całkujący

  • Użytkownik
  • 374 postów
5
Mały Pomocnik I
  • Płeć:Mężczyzna

Napisano 02.01.2014 - 09:53

\begin{bmatrix}1&1&1&1\\2&2&2&2\\4&6&8&8\\-2&-3&-4&-5\\2&3&4&5\end{bmatrix}

 

Jak rozłożyć to za pomocą LU ?


Użytkownik xawery edytował ten post 02.01.2014 - 09:54

  • 0

Afroman

    Kombinator

  • Użytkownik
3
  • Płeć:Kobieta

Napisano 25.09.2011 - 17:55

#2 hmm

hmm

    Operator całkujący

  • VIP
  • 478 postów
312
Instruktor I
  • Płeć:Mężczyzna

Napisano 03.01.2014 - 10:10

Zwykle tą metodę stosuje się do macierzy kwadratowych, ta nie jest kwadratowa więc przynajmniej jedna z macierzy L,U też nie będzie kwadratowa. Nie będą to więc typowe macierze trójkątne. Można jednak znaleźć podobne rozkłady (metoda nie będzie jednoznaczna), np.:

 

\begin{bmatrix}1&0&0\\2&0&0\\4&2&0\\-2&-1&1\\2&1&-1\end{bmatrix}\begin{bmatrix}1&1&1&1\\0&1&2&2\\0&0&0&-1\end{bmatrix}

 

Czy taki rozkład Ci odpowiada? Wtedy jeśli chcesz napiszę jak do niego doszedłem.


  • 1

#3 xawery

xawery

    Operator całkujący

  • Użytkownik
  • 374 postów
5
Mały Pomocnik I
  • Płeć:Mężczyzna

Napisano 03.01.2014 - 11:24

Faktycznie, mnożenie daje mi prawidłowy wynik!

BArdzo chętnie poznam metodę, ale wymagam tego, abym potem potrafił ją zastosować do innych przykładów :D


  • 0

#4 hmm

hmm

    Operator całkujący

  • VIP
  • 478 postów
312
Instruktor I
  • Płeć:Mężczyzna

Napisano 04.01.2014 - 16:28

*
Najwyższa ocena

Metoda jest mniej więcej taka sama, jak dla macierzy kwadratowych, tylko czasem trzeba trochę bardziej uważać a czasem zgadywać  :)

 

Przede wszystkim, macierz L musi mieć wymiary 5\times n a U wymiary n\times 4 dla pewnego n. Zakładając, że macierz po prawej jest macierzą schodkową, na pewno każdy jej wiersz o numerze większym od 4 będzie zerowy. Stąd można założyć, że n\leq 4 (dla n>4 nadmiarowe kolumny macierzy L nie będą miały wpływu na wynik bo będą przemnożone przez zerowe wiersze macierzy U). Próbując znaleźć macierze L,U założyłem na początku, że n=4, dopiero na końcu okazało się że można zmniejszyć n do 3. Według mnie wynika to z tego, że macierz którą chcemy rozłożyć na iloczyn ma rząd 3 (prawdopodobnie od razu można by było zakładać że n jest równe rzędowi, chociaż nie próbowałem tego udowodnić więc głowy nie dam).

 

Wyjściowe założenie było więc takie:

\begin{bmatrix}?&0&0&0\\?&?&0&0\\?&?&?&0\\?&?&?&?\\?&?&?&?\end{bmatrix}\begin{bmatrix}?&?&?&?\\0&?&?&?\\0&0&?&?\\0&0&0&?\end{bmatrix}=\begin{bmatrix}1&1&1&1\\2&2&2&2\\4&6&8&8\\-2&-3&-4&-5\\2&3&4&5\end{bmatrix}

 

Patrzymy jak powstaje pierwszy wiersz w macierzy po prawej. Widzimy, że gdyby element l_{11} macierzy L był równy , to pierwszy wiersz po prawej musiałby być zerowy, a skoro nie jest to l_{11}\neq 0 i możemy przyjąć że l_{11}=1. Wtedy pierwszy wiersz macierzy U musi być identyczny z pierwszym wierszem macierzy po prawej. Ustaliliśmy więc, że będzie:

\begin{bmatrix}1&0&0&0\\?&?&0&0\\?&?&?&0\\?&?&?&?\\?&?&?&?\end{bmatrix}\begin{bmatrix}1&1&1&1\\0&?&?&?\\0&0&?&?\\0&0&0&?\end{bmatrix}=\begin{bmatrix}1&1&1&1\\2&2&2&2\\4&6&8&8\\-2&-3&-4&-5\\2&3&4&5\end{bmatrix}

 

Dalej patrzymy na pierwszą kolumnę macierzy po prawej. Z tego jak ona powstaje widzimy, że musi być równa pierwszej kolumnie macierzy L. Czyli po uzupełnieniu dostajemy:

 

\begin{bmatrix}1&0&0&0\\2&?&0&0\\4&?&?&0\\-2&?&?&?\\2&?&?&?\end{bmatrix}\begin{bmatrix}1&1&1&1\\0&?&?&?\\0&0&?&?\\0&0&0&?\end{bmatrix}=\begin{bmatrix}1&1&1&1\\2&2&2&2\\4&6&8&8\\-2&-3&-4&-5\\2&3&4&5\end{bmatrix}

 

Dalej bierzemy drugi wiersz macierzy po prawej. Żeby otrzymać jego elementy trzeba przemnożyć elementy z drugiego wiersza macierzy L i kolejnych kolumn macierzy U. Daje nam to trzy równości: l_{22}u_{22}=0, l_{22}u_{23}=0, l_{22}u_{24}=0. Więc albo l_{22}=0, albo drugi wiersz macierzy U jest zerowy. Gdyby jednak drugi wiersz U był zerowy, to pierwsza i druga kolumna macierzy U byłyby identyczne, a wtedy pierwsza i druga kolumna macierzy po prawej też musiałyby być identyczne. Ponieważ te kolumny się różnią, to u_{22}\neq 0 (przyjmiemy u_{22}=1) i musi zachodzić równość l_{22}=0. Udało się więc ustalić, że nasz rozkład będzie miał postać:

 

\begin{bmatrix}1&0&0&0\\2&0&0&0\\4&?&?&0\\-2&?&?&?\\2&?&?&?\end{bmatrix}\begin{bmatrix}1&1&1&1\\0&1&?&?\\0&0&?&?\\0&0&0&?\end{bmatrix}=\begin{bmatrix}1&1&1&1\\2&2&2&2\\4&6&8&8\\-2&-3&-4&-5\\2&3&4&5\end{bmatrix}

 

Teraz patrzymy na drugą kolumnę macierzy po prawej i dowiemy się stąd jak wygląda druga kolumna macierzy L. Widzimy, że tak naprawdę żeby dostać tę kolumnę macierzy po prawej, musimy dodać do siebie pierwszą i drugą kolumnę macierzy L, więc druga kolumna jest różnicą odpowiednich kolumn. Mamy w ten sposób:

 

\begin{bmatrix}1&0&0&0\\2&0&0&0\\4&2&?&0\\-2&-1&?&?\\2&1&?&?\end{bmatrix}\begin{bmatrix}1&1&1&1\\0&1&?&?\\0&0&?&?\\0&0&0&?\end{bmatrix}=\begin{bmatrix}1&1&1&1\\2&2&2&2\\4&6&8&8\\-2&-3&-4&-5\\2&3&4&5\end{bmatrix}

 

Teraz wypada popatrzeć na elementy trzeciego wiersza macierzy po prawej. Ponieważ dwa kroki wcześniej nie wyznaczyliśmy wszystkich elementów drugiego wiersza macierzy U, to teraz nie będziemy mieli jednoznacznego rozwiązania powstających równań tj.:

\{4+2u_{23}+l_{33}u_{33}=8\\4+2u_{24}+l_{33}u_{34}=8

Możemy więc wybrać jakieś możliwe rozwiązanie i jeśli będziemy miel szczęście, to dostaniemy nasz rozkład, a jeśli  otrzymamy sprzeczność to zawsze możemy wrócić do tego punktu i wybrać inne rozwiązanie. Przyjąłem, że l_{33}=0, bo to daje możliwość wyznaczenia elementów drugiego wiersza macierzy U. Jeśli mój wybór jest dobry, to rozkład będzie miał postać:

 

\begin{bmatrix}1&0&0&0\\2&0&0&0\\4&2&0&0\\-2&-1&?&?\\2&1&?&?\end{bmatrix}\begin{bmatrix}1&1&1&1\\0&1&2&2\\0&0&?&?\\0&0&0&?\end{bmatrix}=\begin{bmatrix}1&1&1&1\\2&2&2&2\\4&6&8&8\\-2&-3&-4&-5\\2&3&4&5\end{bmatrix}

 

Teraz jak łatwo się domyślić zabieramy się za elementy z trzeciej kolumny macierzy po prawej. Patrząc na to jak one powstają, odczytujemy, że u_{33}=0:

 

\begin{bmatrix}1&0&0&0\\2&0&0&0\\4&2&0&0\\-2&-1&?&?\\2&1&?&?\end{bmatrix}\begin{bmatrix}1&1&1&1\\0&1&2&2\\0&0&0&?\\0&0&0&?\end{bmatrix}=\begin{bmatrix}1&1&1&1\\2&2&2&2\\4&6&8&8\\-2&-3&-4&-5\\2&3&4&5\end{bmatrix}

 

W tym momencie widać, że można zredukować wymiary macierzy. Dlaczego? Mamy u_{44}=cu_{34} dla pewnej stałej c. Patrząc na ostatnią kolumnę i na dwa ostatnie wiersze będziemy mieli równości:

\{-2-2+l_{43}u_{34}+l_{44}cu_{34}=-5\\2+2+l_{53}u_{34}+l_{54}cu_{34}=5

To oznacza, że u_{34} nie może być równe , załóżmy więc że wynosi 1. Wtedy powyższy układ redukuje się do:

\{l_{43}+cl_{44}=-1\\l_{53}+cl_{54}=1

Widać, że możliwym rozwiązaniem jest przyjęcie że piąty wiersz macierzy L jest wierszem czwartym przemnożonym przez -1. Ale też, jeśli dla dowolnego takiego rozwiązania zastąpimy l_{43} przez l'_{43}=l_{43}+cl_{44}, to l_{44}'=0 i ostatnia kolumna macierzy L jest zerowa. Z tego powodu możemy usunąć zarówno tę kolumnę jak i ostatni wiersz macierzy U. W wyniku otrzymamy dokładnie tę parę macierzy L,U, które podałem w poprzednim poście.


Użytkownik hmm edytował ten post 04.01.2014 - 16:28

  • 4

#5 janusz

janusz

    Wielki Analityk

  • +Mods
  • 3130 postów
1450
Starszy Wykładowca I
  • Płeć:Mężczyzna

Napisano 04.01.2014 - 18:48

Do rozkładu A= LU macierzy dowolnych wymiarów i rozwiązywania układów równań przez ten rozkład stosuje się metody: Choleskie'go, Doittle'a. Crouta i Banachiewicza.

Zachęcam do podręczników  Metod Numerycznych.


  • 1

#6 xawery

xawery

    Operator całkujący

  • Użytkownik
  • 374 postów
5
Mały Pomocnik I
  • Płeć:Mężczyzna

Napisano 04.01.2014 - 20:27

Potem to wszytko sprobuję przeczytać co napisałeś, a tak na marginiesie:

http://math.stackexc...n-square-matrix

Z tym idzie sobie jakoś dać radę to rozwiązać ? Tzn tą metdoą da radę mój przykład ?


  • 0

#7 hmm

hmm

    Operator całkujący

  • VIP
  • 478 postów
312
Instruktor I
  • Płeć:Mężczyzna

Napisano 04.01.2014 - 22:35

Pewnie że się da, wynik będzie trochę inny choćby dlatego że ja starałem się przedstawić rozkład LU a nie PLU - z permutacją (a w tym przykładzie już na samym początku zerujesz drugi wiersz czyli będziesz potrzebował permutacji). Poza tym tam jest założenie, że macierz L jest kwadratowa a U ma takie wymiary jak wyjściowa macierz (dodatkowe wiersze i kolumny praktycznie nic nie wniosą ale może przyjmuje się z jakichś powodów takie założenie). 

 

Rozkład otrzymany tą drugą metodą byłby taki:

\begin{bmatrix}1&0&0&0&0\\2&0&0&1&0\\4&1&0&0&0\\-2&-\frac{1}{2}&1&0&0\\2&\frac{1}{2}&-1&0&1\end{bmatrix}\begin{bmatrix}1&1&1&1\\0&2&4&4\\0&0&0&-1\\0&0&0&0\\0&0&0&0\end{bmatrix}

czyli:

\begin{bmatrix}1&0&0&0&0\\0&0&1&0&0\\0&0&0&1&0\\0&1&0&0&0\\0&0&0&0&1\end{bmatrix}\begin{bmatrix}1&1&1&1\\2&2&2&2\\4&6&8&8\\-2&-3&-4&-5\\2&3&4&5\end{bmatrix}=\begin{bmatrix}1&0&0&0&0\\4&1&0&0&0\\-2&-\frac{1}{2}&1&0&0\\2&0&0&1&0\\2&\frac{1}{2}&-1&0&1\end{bmatrix}\begin{bmatrix}1&1&1&1\\0&2&4&4\\0&0&0&-1\\0&0&0&0\\0&0&0&0\end{bmatrix}

(na tamtej stronie jest błąd, nie każda macierz permutacji jest swoją odwrotnością, dotyczy to tylko macierzy transpozycji).

 

Ta metoda prawdopodobnie mniej nadaje się do obliczeń (na komputerze, bo ludzie często mają swoje indywidualne upodobania ;)). Ma ona jednak na pewno swoje zalety. Między innymi natychmiast widać to, o czym pisałem, że (jeśli się chce) można zredukować n do rzędu macierzy.


  • 2

#8 xawery

xawery

    Operator całkujący

  • Użytkownik
  • 374 postów
5
Mały Pomocnik I
  • Płeć:Mężczyzna

Napisano 05.01.2014 - 13:32

A możesz mi wytłumaczyć tutaj tą "angielską" wersję ? Okrponie mi na tym zależy, bo nie ma tego w internecie.


  • 0

#9 hmm

hmm

    Operator całkujący

  • VIP
  • 478 postów
312
Instruktor I
  • Płeć:Mężczyzna

Napisano 06.01.2014 - 15:25

Pierwszym krokiem jest sprowadzenie przy pomocy operacji elementarnej do macierzy schodkowej. To co dostaniemy, to będzie macierz U. Bardzo ważne jest, żeby zapamiętać jakie operacje elementarne stosowaliśmy. Na naszym przykładzie:

\begin{bmatrix}1&1&1&1\\2&2&2&2\\4&6&8&8\\-2&-3&-4&-5\\2&3&4&5\end{bmatrix}

operacja pierwsza: w_2\leftarrow w_2-2w_1

\begin{bmatrix}1&1&1&1\\0&0&0&0\\4&6&8&8\\-2&-3&-4&-5\\2&3&4&5\end{bmatrix}

operacja druga: w_3\leftarrow w_3-4w_1

\begin{bmatrix}1&1&1&1\\0&0&0&0\\0&2&4&4\\-2&-3&-4&-5\\2&3&4&5\end{bmatrix}

operacja trzecia: w_4\leftarrow w_4+2w_1

\begin{bmatrix}1&1&1&1\\0&0&0&0\\0&2&4&4\\0&-1&-2&-3\\2&3&4&5\end{bmatrix}

operacja czwarta: w_5\leftarrow w_5-2w_1

\begin{bmatrix}1&1&1&1\\0&0&0&0\\0&2&4&4\\0&-1&-2&-3\\0&1&2&3\end{bmatrix}

operacja piąta: zamieniamy w_2 z w_3

\begin{bmatrix}1&1&1&1\\0&2&4&4\\0&0&0&0\\0&-1&-2&-3\\0&1&2&3\end{bmatrix}

operacja szósta: w_4\leftarrow w_4+\frac{1}{2}w_2

\begin{bmatrix}1&1&1&1\\0&2&4&4\\0&0&0&0\\0&0&0&-1\\0&1&2&3\end{bmatrix}

operacja siódma: w_5\leftarrow w_5-\frac{1}{2}w_2

\begin{bmatrix}1&1&1&1\\0&2&4&4\\0&0&0&0\\0&0&0&-1\\0&0&0&1\end{bmatrix}

operacja ósma: zamieniamy w_3 z w_4

\begin{bmatrix}1&1&1&1\\0&2&4&4\\0&0&0&-1\\0&0&0&0\\0&0&0&1\end{bmatrix}

operacja dziewiąta: w_5\leftarrow w_5+w_3

\begin{bmatrix}1&1&1&1\\0&2&4&4\\0&0&0&-1\\0&0&0&0\\0&0&0&0\end{bmatrix}

 

Teraz musimy znaleźć macierz L. Bierzemy macierz jednostkową 5\times 5 i wykonujemy na niej odwrotność tego co zrobiliśmy przed chwilą z wyjściową macierzą. To znaczy wykonujemy operacje w odwrotnej kolejności i będą to operacje odwrotne do tych które wykonywaliśmy. Pierwsza operacja musi być więc operacją odwrotną do operacji dziewiątej. To znaczy, zamiast dodawać do piątego wiersza trzeci, trzeba go odjąć. Następną operacją będzie operacja odwrotna do ósmej czyli w tym przypadku dokładnie ta sama operacja (transpozycja jest odwrotna sama do siebie). Wypiszę po kolei jakie będziemy otrzymywać macierze:

\begin{bmatrix}1&0&0&0&0\\0&1&0&0&0\\0&0&1&0&0\\0&0&0&1&0\\0&0&0&0&1\end{bmatrix}\rightarrow \begin{bmatrix}1&0&0&0&0\\0&1&0&0&0\\0&0&1&0&0\\0&0&0&1&0\\0&0&-1&0&1\end{bmatrix}\rightarrow \begin{bmatrix}1&0&0&0&0\\0&1&0&0&0\\0&0&0&1&0\\0&0&1&0&0\\0&0&-1&0&1\end{bmatrix}\rightarrow \begin{bmatrix}1&0&0&0&0\\0&1&0&0&0\\0&0&0&1&0\\0&0&1&0&0\\0&\frac{1}{2}&-1&0&1\end{bmatrix}\rightarrow \begin{bmatrix}1&0&0&0&0\\0&1&0&0&0\\0&0&0&1&0\\0&-\frac{1}{2}&1&0&0\\0&\frac{1}{2}&-1&0&1\end{bmatrix}\rightarrow \begin{bmatrix}1&0&0&0&0\\0&0&0&1&0\\0&1&0&0&0\\0&-\frac{1}{2}&1&0&0\\0&\frac{1}{2}&-1&0&1\end{bmatrix}\rightarrow \begin{bmatrix}1&0&0&0&0\\0&0&0&1&0\\0&1&0&0&0\\0&-\frac{1}{2}&1&0&0\\2&\frac{1}{2}&-1&0&1\end{bmatrix}\rightarrow \begin{bmatrix}1&0&0&0&0\\0&0&0&1&0\\0&1&0&0&0\\-2&-\frac{1}{2}&1&0&0\\2&\frac{1}{2}&-1&0&1\end{bmatrix}\rightarrow \begin{bmatrix}1&0&0&0&0\\0&0&0&1&0\\4&1&0&0&0\\-2&-\frac{1}{2}&1&0&0\\2&\frac{1}{2}&-1&0&1\end{bmatrix}\rightarrow \begin{bmatrix}1&0&0&0&0\\2&0&0&1&0\\4&1&0&0&0\\-2&-\frac{1}{2}&1&0&0\\2&\frac{1}{2}&-1&0&1\end{bmatrix}

 

Nie podoba nam się w tym rozkładzie to, że macierz L nie jest dolnotrójkątna. Aby to poprawić, wystarczy zamienić wiersze tak jak poprzednio tj. drugi z trzecim i trzeci z czwartym. Wtedy jednak w wyniku nie dostaniemy wyjściowej macierzy M tylko macierz PM, gdzie P jest macierzą pewnej permutacji. Jaką? P dostaniemy z macierzy jednostkowej wykonując te same permutacje co przed chwilą na L, tj. najpierw zamieniając wiersz drugi z trzecim a potem trzeci z czwartym.


  • 1

#10 xawery

xawery

    Operator całkujący

  • Użytkownik
  • 374 postów
5
Mały Pomocnik I
  • Płeć:Mężczyzna

Napisano 07.01.2014 - 00:35

Ok, dzięki wielkie!

Jedna jeszcze prośba. Podpowiedz jak zachowywac się przy macierzach niekwadratowych, tzn wiadomo, że trzeba zeschodkować macierz - żeby dostać macierz U. Ale konstruując macierz L jakich wymiarów powinniśmy wziąć macierz?


  • 0

#11 hmm

hmm

    Operator całkujący

  • VIP
  • 478 postów
312
Instruktor I
  • Płeć:Mężczyzna

Napisano 09.01.2014 - 00:21

Ok, dzięki wielkie!

Jedna jeszcze prośba. Podpowiedz jak zachowywac się przy macierzach niekwadratowych, tzn wiadomo, że trzeba zeschodkować macierz - żeby dostać macierz U. Ale konstruując macierz L jakich wymiarów powinniśmy wziąć macierz?

Masz na myśli tę drugą metodę? Wtedy L jest macierzą kwadratową i ma tyle kolumn ile wierszy ma macierz U - żeby dało się je pomnożyć.


  • 0





Tematy podobne do: rozkład LU     x