img027 (41)

(2.46)

<hj =^ay ^dla i = j,j + l — ,n. (2.49) ■ 5

Leżeli j = to obliczenia są zakończone. Jeżeli nie, to wykonanie procedury jest kie-i cteć do kroku 6.

Kmió

L zupełniane są wyrazy y-tego wiersza tablicy Q według wzoru

— ^dla i = j + l,j + 2,—,n. (2.50)

>3 >

Krok 7

Zay podstawiana jest liczbay+ 1. Wykonanie procedury jest kierowane do kroku 4. ■ Liczba działań mnożenia i dzielenia wymaganych przez algorytm Crouta wynosi

! ' ^m24

1 3 1

—n--n,

3 3

ego ele-znajdu-obliczo-tapisany >0 doko-

i Lczba wymaganych działań dodawania i odejmowania jest równa

1 ₃ 1 2 1

— n--n + — n.

3 2 6

"‘iromiast dla rozwiązania układu równań (2.41) i (2.42) z macierzami współczynników, :trzymanymi w wyniku dekompozycji LU macierzy A współczynników danego układu równań (2.33), należy wykonać n~ mnożeń i dzieleń oraz n² - n dodawań i odejmowań.

Warunkiem dostatecznym wykonalności działań algorytmu Crouta dekompozycji LU jest. aby wszystkie minory główne dekomponowanej macierzy A były różne od zera.

cładu na

Z przedstawionego opisu algorytmu Crouta wynika, że warunkiem koniecznym jego realizowalności jest nieosobliwość macierzy A. Nieosobliwość macierzy A nie jest jednak warunkiem dostatecznym pomyślnego wykonania działań algorytmu. W trakcie realizacji

blicy Q

ilgorytmu Crouta może bowiem nastąpić zatrzymanie wykonywania jego działań w wyniku zaistnienia dzielenia przez element q= Ijj, który dla pewnego j = 1, 2, 1 może przyjąć wartość równą zero.

Również, podobnie jak w metodzie eliminacji Gaussa, na ogół uzasadnione jest ze względu na zmniejszający się błąd zaokrągleń takie przenumerowywanie wierszy danej

(2.47)

macierzy kwadratowej A w każdym kroku j algorytmu Crouta, aby element qjj = Ijj miał wartość bezwzględną największą z możliwych. Z obu wymienionych wyżej powodów algorytm Crouta jest uzupełniany procedurą częściowego wyboru elementu podstawowego.³¹ Za wyjątkiem kroku 1 realizacja procedury częściowego wyboru elementu podstawo-

(2.48)

wego wymaga przy tym dodatkowych obliczeń. W kroku 4 algorytmu należy bowiem obliczyć wszystkie wartości q,j dla /' =j,j + 1, •••, n, i wybrać tę, której wartość bezwzględna jest największa. Następnie należy zamienić miejscami wiersze o numerach j oraz ; w obu macierzach A i Q i kontynuować obliczenia w kroku 4. Zapamiętywanie przestawienia

³⁾ W algorytmie Crouta można stosować procedurę pełnego wyboru elementu podstawowego, co wiąże się jednak z dalszym wzrostem nakładu obliczeniowego.