img027 (41)

31

(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 3 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^2 - 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.^31 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
	^3) W algorytmie Crouta można stosować procedurę pełnego wyboru elementu podstawowego, co wiąże się jednak z dalszym wzrostem nakładu obliczeniowego.

r