I

TERACYJNE

 

METODY

 

ROZWIĄZYWANIA

 

UKŁADÓW

 

RÓWNAŃ

 

LINIOWYCH

1.1. M

ETODA

 

ITERACJI

 

PROSTYCH

Ogólny   schemat   obliczeń   iteracyjnych   przedstawia   metoda   iteracji   prostych.   Za   jej 

pomocą można rozwiązać układ równań liniowych (o n niewiadomych) (1.1.1)

Układ ten można zapisać w postaci

przyjmując, że 

oraz

Przy założeniu, że elementy główne macierzy     są różne od zera (czyli  

  dla 

), należy przekształcić układ 1.1.1 w taki sposób, aby wyznaczyć z pierwszego 

równania  , z drugiego równania  , itd. aż do  .

Dostajemy

Otrzymany układ można zapisać równoważnie w postaci (1.1.2)

gdzie:

, 

 

dla 

oraz

 

dla 

, 

Przyjmując

oraz

układ 1.1.2 można zapisać w postaci macierzowej jako

Otrzymaną równość wykorzystuje się do uzyskania kolejnych przybliżeń rozwiązania 

układu.   W tym   celu,   jako   rozwiązanie   początkowe,   obiera   się   dowolny   wektor  

 

(np. wektor zerowy) i oblicza się kolejne iteracje

(przybliżenie pierwsze),

(przybliżenie drugie) itd. Stąd ogólny wzór iteracyjny (1.1.3)

Kolejne przybliżenia 

,  

, … ,  

, … utworzą ciąg wektorów. Jeżeli istnieje 

granica tego ciągu  

, wtedy     jest rozwiązaniem układu równań liniowych. 

Aby powyższa granica istniała, to ciąg wektorów 

, 

, … musi być ciągiem zbieżnym. 

Zbieżność tego ciągu jest równoważna zbieżności metody iteracyjnej.

2

1.3. M

ETODA

 J

ACOBIEGO

Jedną   z   metod   iteracyjnych   jest   metoda   Jacobiego  [1,   4,   7,   8].   Jej   macierz     jest 

macierzą przekątniową o elementach 

 takich, jak w  , czyli

Wtedy proces iteracyjny zapisuje się jako

Inaczej można go zapisać w postaci

dla 

 oraz iteracji 

.

Metoda ta będzie zbieżna wtedy i tylko wtedy, gdy  

. Biorąc normę 

Jeżeli dla wszystkich   spełniona jest nierówność 

, to

.

Zatem prawdziwe są twierdzenia:

Twierdzenie 3

 

 a (Mocne kryterium sumy wierszy)

 

 

Metoda Jacobiego jest zbieżna dla wszystkich macierzy   spełniających warunek (1.3.1):

dla 

.

Twierdzenie 3b (Mocne kryterium sumy kolumn)

Metoda Jacobiego zbiega dla wszystkich macierzy   spełniających warunek (1.3.2):

3

dla 

.

Macierz   spełniająca warunek 1.3.1 (1.3.2) nazywana jest macierzą ściśle diagonalnie 

dominującą według wierszy (według kolumn).

Równoważnie można powiedzieć, że jeśli macierz   jest dominująca przekątniowo, to 

dla dowolnego wektora początkowego metoda Jacobiego tworzy ciąg zbieżny do rozwiązania 
układu 

.

1.4. M

ETODA

 G

AUSSA

-S

EIDLA

W metodzie tej macierz   przedstawia się w postaci 

, gdzie   - macierz 

diagonalna,     - macierz trójkątna dolna, zaś     - macierz trójkątna górna [1, 7, 8]. Wtedy 
układ równań 

 można przedstawić w postaci

Zatem dla wzoru 1.2.1  

. Dlatego proces iteracyjny można zapisać w postaci

Równoważna postać tego procesu to

dla 

 oraz iteracji 

.

Zapis ten dobrze pokazuje różnicę pomiędzy tą metodą iteracyjną a metodą Jacobiego. 

Widać, że metoda Gaussa-Seidla, wyznaczając w jednym kroku iteracyjnym kolejne elementy 
wektora  

,   korzysta   zarówno   z   wartości   wektora  

  jak   i   z   wyznaczonych   już 

elementów wektora  

. W metodzie Jacobiego natomiast nowe przybliżenia składowych 

rozwiązania wykorzystywane są dopiero w kolejnej iteracji, dzięki czemu można je obliczać 
jednocześnie.

Kryterium zbieżności metody Gaussa-Seidla jest takie samo jak dla metody Jacobiego, 

co pokazuje poniższe twierdzenie:

Twierdzenie 4

4

Jeśli macierz     jest dominująca przekątniowo, to metoda Gaussa-Seidla jest zbieżna  

dla dowolnego wektora początkowego.

5