img024 (42)

28

*

y

*

JC

rozwiązania nosi nazwę metody dekompozycji LU [6 - 8, 19].

Należy zauważyć, że w metodzie dekompozycji LU nie ulega przekształceniu wektor wyrazów wolnych b. Jest to korzystne w przypadku, który często ma miejsce w zastosowaniach, gdy dane równanie (2.33) ma być rozwiązywane wielokrotnie dla różnych wartości wektora wyrazów wolnych. Wówczas w układzie równań (2.41), (2.42) macierze współczynników L i U pozostają niezmienione, a zmianie ulega jedynie składowa b wektora wyrazów wolnych

~b~

_y_

a w konsekwencji i składowa j tego wektora. W przypadku metody eliminacji Gaussa należałoby dla każdego nowego wektora wyrazów wolnych b realizować cały algorytm od początku. Ponieważ główny nakład obliczeniowy w metodzie dekompozycji LU wiąże się z realizacją rozkładu macierzy współczynników na czynniki L i U, uzyskuje się tu w omawianym przypadku znaczne oszczędności.

Inną zaletą metody dekompozycji LU jest w tym kontekście również to, że czynniki rozkładu LU zachowują na ogół strukturę macierzy rzadkich, jeżeli dana macierz A jest macierzą rzadką [6]. Należy tu nadmienić, że macierz odwrotna AT^X do danej macierzy rzadkiej A na ogół nie zachowuje struktury macierzy rzadkiej. A zatem w przypadku wielokrotnego rozwiązywania danego równania (2.33), przy zmieniającym się wektorze wyrazów wolnych, wyznaczenie macierzy A~^x i korzystanie ze wzoru x = A '¹ ■ b nie daje możliwości zaoszczędzenia nakładu obliczeniowego w związku z ewentualną możliwością uwzględnienia rzadkości macierzy ,4.

W celu otrzymania czynników rozkładu LU dla danej nieosobliwej macierzy kwadratowej A można wykorzystać algorytm eliminacji Gaussa w etapie eliminacji w przód. Ten sposób wyznaczenia czynników rozkładu LU nosi w literaturze nazwę algorytmu Gaussa [8]. Rozkład LU dla macierzy A można uzyskać również w inny sposób, rozważając na przykład równanie L ■ U = A jako układ n równań z n² niewiadomymi, którymi są elementy macierzy L i U. Odpowiedni algorytm, w którym równania są rozwiązywane na przemian kolumnami i wierszami, i który jest równoważny pod względem nakładu obliczeniowego algorytmowi Gaussa, nosi w literaturze nazwę algorytmu Crouta [6], gdy macierz górna U jest macierzą z jedynkami na głównej przekątnej lub algorytmu Doolittle’a [8], gdy macierz L jest macierzą z jedynkami na głównej przekątnej.

Opisany poniżej algorytm Crouta obliczania czynników rozkładu LU jest metodą rekurencyjnego obliczania elementów macierzy L i U bez przepisywania wyników pośrednich, które ma miejsce w etapie eliminacji w przód algorytmu Gaussa. Element a,_m, na przykład, jest w etapie eliminacji w przód przepisywany n + 1 razy, przyjmując wartość