Info nr 8, 25. nov
MLM7205	Lineaaralgebra rakendused   6.0 EAP 	Sügis 2014

Teema: 2.7. Võrrandisüsteemide lahendamine iteratsioonimeetodil 

Vt [T] Tammeraid, I. (1999) Lineaaralgebra rakendused. Tallinn: TTÜ kirjastus, punkt 2.7, lk 170 - 178

Selle teema me esitame allpool lühemalt ja ülevaatlikumalt.

Võrrandisüsteemi vaatleme maatrikskujul   A x = b ,  kus  A  R n  n  (vt lk 172) . Esitame  A  kujul  A = M – N (öeldakse, et on antud  A  lagu, vt lk 174) . Selle eesmärk on , et maatriks  M  R n  n  oleks lihtne, nt diagonaal- või kolmnurkmaatriks. 

Seega süsteem võtab kuju  ( M – N ) x = b   ehk  M x = N x + b .  Kui  M  R n  n  on lihtne , siis on, vähemalt formaalselt, ka lihtne leida pöördmaatriksit  M - 1  R n  n . Seega eelmisest võrrandist saame avaldada

x = M - 1 N x + M - 1 b ,                           (*)

mis tekitab idee iteratsioonimeetodist (mõelge nt Newtoni meetodi peale) kujul

x ( k  + 1)= M - 1 N x ( k ) + M - 1 b .                 (**)

Olgu  x ( 0 )  nn alglähend, st võrrandi  A x = b  ligikaudne lahend või isegi juhuslikult võetud, nt sageli nullvektor. Siis iteratsioonivalemiga  (**)  arvutades saadakse lähendite jada  x ( 1 )  , x ( 2 )  , ... , x ( m )  , ... . Võib juhtuda, et saadud lähendite jada koondub vektoriks  x * , st et  lim k    || x ( k ) - x * || = 0  mingi normi  || . ||  mõttes. Koonduvuse juhtumil järeldub võrdusest  (**)  võrdus  (*)  ja oleme saanud, et  x *  on võrrandi  A x = b  lahend.
Tegelikkuses ei saa lõpmatult palju lähendeid arvutada, aga on loogiline, et küllalt suure  m  korral  x ( m )  ≈ x * ja sellega oleme saanud ligikaudse lahendi, milleks on  x ( m ) .

Millal koondumine toimub, selgitatakse teoreemidega.

Def. Maatriksit  T = M - 1 N  nimet-e iteratsioonimaatriksiks.

Teor. 1. Iteratsioon  (**)  koondub iga alglähendi  x ( 0 )  korral parajasti siis, kui leidub norm, et  || T || < 1 . 

Teor. 2. Iteratsioon  (**)  koondub iga alglähendi  x ( 0 )  korral parajasti siis, kui spektraalraadius  ρ ( T ) < 1 .

Jacobi iteratsioonimeetod saadakse, kui  M = D  on  A  peadiagonaal. 

Töötage läbi lk 173, näide 7.2.1

Gauss-Seideli iteratsioonimeetod saadakse, kui  M = L  on  A  alumine kolmnurkmaatriks . Sellisel juhul võtab valem  (**)  kuju
x ( k  + 1)= x ( k ) - L - 1 A x ( k ) + L - 1 b .                 (***)

Teor. 3. Kui  A  R n  n  on domineeriva diagonaaliga (st et iga peadiagonaali elemendi absoluutväärtus on suurem kui sama rea ülejäänud elementide absoluutväärtuste summa ), siis Jacobi ja Gauss-Seideli meetodid koonduvad iga alglähendi korral ning viimane koondub kiiremini (st et G-Seideli iteratsioonimaatriksi spektraalraadius on väikesem Jacobi omast).  

Näide. Lahendame G-Seideliga võrrandit  A x = b ,  kus  A =    ja  b = ( 6  9 ) T . Selle täpne lahend on 
x = ( 1  2 ) T .  Siin võrdus  A = M – N = L – ( L - A )  võtab kuju 

A =  =   -   ,
kus
L =  , millest saame  L- 1  = .  Valemi  (***) jaoks on vaja arvutada  
L- 1 A  =  =       ning   L- 1 b  =  =  = . 

Maatriks  A  on domineeriva diagonaaliga (vt teor. 3) , seega võtame alglähendiks suvalise vektori, nt  
x ( 0 ) = ( 0  0) T . Siis valemist  (***)  saame juhul  k = 0  
x ( 1 )  =  L- 1 b  = .
Järgmise lähendi  x ( 2 )  saame valemist  (***)  juhul  k = 1 .  Arvutame :

x ( 2 )  = L - 1 b - L - 1 A x ( k ) + L - 1 b =   -  =  =   .

Näete, juba kolmandal sammul oleme täpsel lahendil üsna lähedal.

Ülesanne . Lahendage sama näide Jacobi iteratsiooniga.

Edu!
AK