img080 (18)

85

Dowodzi się [7], że warunek (4.61) jest spełniony na przykład, gdy macierz A jest symetryczna i dodatnio określona.

Z twierdzenia 4.1 otrzymuje się natomiast, że ciąg iteracji w metodzie Gaussa-Seidla jest zbieżny, jeżeli dowolna nonna macierzy (L + D)^] • U, zgodna z zadaną normą w R", ma wartość mniejszą od jedności. Dowodzi się między innymi [8], że jeżeli dla macierzy A współczynników danego układu równań spełniony jest jeden z warunków (4.46) lub (4.47), to ciąg kolejnych przybliżeń w metodzie Gaussa-Seidla jest zbieżny do rozwiązania danego równania, choć niekoniecznie szybciej niż w metodzie Jacobiego.

Oszacowanie dokładności przybliżonego wyznaczenia wektora rozwiązania jc po k iteracjach otrzymuje się ze wzoru

■*(*)-* H-

1- (.l + d)¹ u

(4.62)

(patrz p. 3.2.1, wzór (3.69) w tekście twierdzenia Banacha), gdzie norma macierzy jest normą indukowaną przez ustaloną normę w przestrzeni R". Normę macierzową ||-||2 można zastąpić we wzorze normą ||-||_E . Wzór (4.62) jest słuszny przy spełnieniu warunku dostatecznego zbieżności ze względu na wykorzystywane w nim normy. Warunki na zakończenie obliczeń mają taką samą postać, jak dla metody Jacobiego, to znaczy wymagają spełnienia nierówności (4.49) i/lub (4.50).

Metoda Jacobiego i metoda Gaussa-Seidla są przykładami metod przybliżonych rozwiązywania układów równań liniowych. Szereg dalszych uwag ogólnych dotyczących zastosowania metody iteracji prostej do przybliżonego wyznaczania rozwiązań równań liniowych można znaleźć w [7, 8, 19]. Tam też znaleźć można więcej rozważań dotyczących warunków na zbieżność i szybkości zbieżności ciągów kolejnych przybliżeń, jak również dotyczących błędów zaokrągleń.

Drugą obszerną grupę metod przybliżonego rozwiązywania układów równań liniowych stanowią algorytmy gradientowe [19].

W rozdziale 2 zostały przedstawione dwie podstawowe metody dokładne rozwiązywania układów równań liniowych, oparte na algorytmach skończonych: metoda eliminacji Gaussa i metoda dekompozycji LU. Realizacja algorytmu każdej z tych metod wymaga dla otrzymania rozwiązania układu n równań liniowych z n niewiadomymi w przybliżeniu n² miejsc w pamięci komputera i wykonania około «³/3 działań mnożenia i dzielenia, gdzie nie uwzględniono oszczędności wynikających z ewentualnej rzadkości macierzy współczynników układu. Z drugiej strony, dla rozwiązania tego samego układu równań z zastosowaniem jednego z algorytmów wykorzystujących metodę iteracji prostej, należy w każdym kroku iteracji wykonać n² działań mnożenia. Wynika stąd, że omawiane w tym rozdziale algorytmy iteracyjne są porównywalne pod względem nakładu obliczeniowego z algorytmami dokładnymi w przypadku liczby niezbędnych iteracji nie większej niż n. Liczba działań mnożenia jest wówczas nie większa niż n ■ n~- r?. Jednak już najprostsze przykłady pokazują [8], że liczba iteracji potrzebnych do uzyskania zadowalającej dokładności jest na ogół, w przypadku omawianych algorytmów, bardzo duża, to znaczy znacznie większa od