Metoda LU

Metoda LU (ang. lower – dolny, upper górny) – metoda rozwiązywania układu równań liniowych. Nazwa pochodzi od użytych w tej metodzie macierzy trójkątnych, tj. dolnotrójkątnej (dolnej) i górnotrójkątnej (górnej). Metoda pozwala także na szybkie wyliczenie wyznacznika macierzy układu.

Opis metody LUEdytuj

Niech dany będzie układ równań liniowych:

 

gdzie   – macierz współczynników,   – wektor niewiadomych,   – wektor danych.

W metodzie LU macierz współczynników   zapisywana jest jako iloczyn pewnych macierzy dolnej   i górnej  

 

gdzie:

 

Układ równań przyjmuje wówczas postać

 

a jego rozwiązanie sprowadza się do rozwiązania dwóch układów równań z macierzami trójkątnymi:

 
 

Ostatecznie liczba mnożeń, potrzebnych do wyznaczenia wektora   wynosi   dodawań  

Wyznacznik macierzy   tej postaci można obliczyć korzystając z twierdzenia Cauchy’ego:

 

oraz z faktu, że wyznacznik macierzy trójkątnej jest iloczynem elementów na przekątnej:

 
 

Ponadto przeważnie przy rozkładzie LU na przekątnej jednej z macierzy znajdują się jedynki – wtedy wyznacznik macierzy   jest równy wyznacznikowi albo macierzy   albo   którego obliczenie wymaga wykonania   mnożeń (zamiast  ).

Zalety metody:

  • bardzo oszczędna gospodarka pamięcią,
  • wymaga najmniejszej liczby operacji w porównaniu z innymi metodami dokładnymi (nie biorąc pod uwagę procedur specjalnych).

Rozkład LUEdytuj

Podstawowym problemem numerycznym w tej metodzie jest dokonanie rozkładu LU macierzy współczynników. Żeby ten rozkład macierzy był jednoznaczny, zakłada się, że elementy na głównej przekątnej jednej z macierzy,   albo   są równe 1.

Rozkład LU jest wyznaczany za pomocą metody Doolittle’a (opisana niżej).

Ta metoda nie jest niezawodna[1], tzn. podczas obliczeń może wystąpić dzielenie przez zero. Istnieje jej modyfikacja pozbawiona tej wady, nazywana metodą Doolittle-Crouta, w której wykorzystuje się częściowy wybór elementu podstawowego[2].

Element podstawowy to taki element w macierzy   który jest używany do rugowania zmiennych (czyli zerowania odpowiadających im współczynników) z kolejnych równań. Przy stosowaniu metody Doolittle’a wybiera się element podstawowy zawsze z przekątnej głównej, i jeśli   jest równe zero, metoda zawodzi.

W metodach zmodyfikowanych wybierany jest ten element z danej  -tej kolumny, który ma największy moduł[3]. Następnie wiersz, w którym znajduje się wybrany element, zamieniany jest z  -tym wierszem, co powoduje, że element podstawowy pojawia się na przekątnej głównej. To gwarantuje, że podczas obliczeń nie wystąpi dzielenie przez zero.

Jednocześnie te zmodyfikowane metody nie zawsze dają rozkład LU macierzy  [2]. Może się zdarzyć, że otrzymany rozkład LU dotyczy macierzy   w której dokonano takich samych przestawień wierszy, jak podczas eliminacji zmiennych[4]. Jednak ma to znaczenie (i komplikuje obliczenia) tylko wtedy, gdy rozkład LU służy do wyznaczenia macierzy odwrotnej; w innych zadaniach nie odgrywa roli.

Metoda Doolittle’aEdytuj

W metodzie tej równość   traktuje się jako układ   równań z   niewiadomymi[5]. Te niewiadome to elementy   dla   (elementy poniżej przekątnej), oraz   dla   (elementy na i powyżej przekątnej), przy założeniu, że na diagonali macierzy   znajdują się 1:

 

Wyznaczanie kolejnych elementów macierzy   i   robi się naprzemiennie, tj. raz wyznacza wiersz macierzy   raz kolumnę macierzy  

Wzory ogólne na poszczególne elementy macierzy rozkładu przedstawiają się następująco:

dla wszystkich  
  dla  
  dla  

Z ostatniego równania wynika, że metoda nie zadziała, gdy  

Liczba działań potrzebna do rozkładu[5]:

  • mnożenia:  
  • dodawania:  

Przykład (macierz 3x3)Edytuj

 

Pierwszy wiersz macierzy U:

 
 
 
 

Pierwsza kolumna macierzy L:

 
 
 

Drugi wiersz macierzy U:

 
 
 

Druga kolumna macierzy L:

 
 

Trzeci wiersz macierzy U:

 
 

Metoda GaussaEdytuj

Wersja pamięciożernaEdytuj

Do macierzy, której rozkładu dokonujemy dopisujemy lewostronnie macierz jednostkową. Na prawym bloku macierzy wykonujemy operacje elementarne takie jak w metodzie Gaussa (odejmowanie mnożenie). W lewym bloku macierzy zapisujemy współczynniki użyte do eliminacji.

 

Wersja wymagająca mniej pamięciEdytuj

Przepisujemy wiersz bez zmian, a elementy w kolumnie poniżej głównej przekątnej dzielimy przez element znajdujący się na głównej przekątnej.

Dla pozostałej części macierzy obliczamy uzupełnienie Schura:

 

Powyższe kroki wykonujemy dla  

Gdy któryś z elementów na głównej przekątnej wynosi zero, to rozkład   nie istnieje, ale można spróbować dokonać rozkładu LU dla pewnej permutacji wierszy macierzy  

Dla każdej nieosobliwej macierzy kwadratowej   można dokonać rozkładu   macierzy powstałej z pewnej permutacji wierszy macierzy  

Metoda CroutaEdytuj

Metoda ta jest analogiczną do metody Doolittle’a, różnica polega na tym, że diagonala macierzy U jest wypełniona liczbami 1.

 

Przykład rozwiązania układu równańEdytuj

Zostanie użyta ta sama macierz współczynników, jak w przykładzie dla metody Doolittle’a:

 

Teraz zostaną zapisane dwa układy równań z macierzami trójkątnymi   i  

 
 

Najpierw zostanie wyznaczony wektor   z pierwszego układu równań   Rozwiązanie układu równań z macierzą trójkątną jest bardzo proste: wyznaczane są kolejno elementy wektora niewiadomych   następnie, gdy znane jest   można wyznaczyć   a na końcu   ponieważ znane są   i  

  1.  
  2.  
  3.  

Teraz drugi układ równań przyjmuje postać:

 

Sposób rozwiązywania jest analogiczny jak dla pierwszego układu, z tym że elementy wektora   są wyznaczane „od końca”:

  1.  
  2.  
  3.  

Ostatecznie wynikiem jest wektor  

Przykład obliczania wyznacznikaEdytuj

Ponownie wykorzystane zostaną wyniki z przykładu dla metody Doolittle’a:

 

Ponieważ na przekątnej macierzy   są jedynki, dlatego wyznacznik macierzy  [6].

Zobacz teżEdytuj

PrzypisyEdytuj

BibliografiaEdytuj