Next: Aproksimacija funkcije i numerička
Up: Rješavanje sustava jednadžbi
Previous: Gauss-Seidelova OR-metoda (SOR metoda)
  Contents
Konvergencija iterativne metode
Iterativni postupci, koje smo upravo definirali, opisani su formulom
gdje je
matrica tipa
definirana od slučaja do slučaja
na različite načine pomoću matrice
Razmotrimo sada probleme
konvergencije navedenih metoda.
Definicija 17
Neka je

simetrična matrica. Kažemo da je
pozitivno
definitna, ako vrijedi
Lema 3
Neka je

simetrična pozitivno definitna matrica tipa

Tada su vlastite vrijednosti

od
matrice

pozitivne, i vrijedi
za svaki
Dokaz. Budući da je matrica
simetrična, postoji
međusobno okomitih i jediničnih vektora
u
i brojevi
takvih, da je
Zbog pozitivne definitnosti
Dokažimo sada drugu tvrdnju. Primijetimo
najprije da vlastiti vektori
matrice
čine ortonormiranu bazu u
To znači da se bilo koji vektor
može prikazati kao njihova linearna
kombinacija.
Zbog linearnosti djelovanja matrice
na vektore
Tako je
Odatle

Teorem 23
Neka je

simetrična, pozitivno definitna matrica. Iterativni postupak
konvergira za bilo koju početnu aproksimaciju

ako i samo ako je
Dokaz. 1. Dokažimo najprije da iz
slijedi konvergencija iterativnog postupka. Doista
i odatle
Kako to vrijedi za svaki
imamo
Budući da je
pa niz
konvergira. Neka je
Tada je
i prema tome niz konvergira k rješenju
2. Dokažimo obrat, tj. da iz konvergencije postupka slijedi
Iz
i
slijedi
Zbog pretpostavke
slijedi
Ako se to događa za svaku početnu aproksimaciju
onda matrica
mora biti nulmatrica, tj. mora biti
Budući da je
simetrična matrica, ona se može dijagonalizirati,
tj. postoji regularna matrica
takva, da vrijedi
![% latex2html id marker 28758
$\displaystyle G^k = X\,\left[\begin{array}{cccc}
...
...ddots & \vdots \\
0 & 0 & \cdots & \lambda_n^k(G)
\end{array}\right]\,X^{-1},$](img2158.gif)
za
Odatle
Budući da je
regularna matrica, slijedi
Prema tome
Zbog
to je moguće samo ako je

Formalno na isti način kao kod metode iteracije prilikom traženja
nultočke funkcije možemo naći apriornu ocjenu greške
i aposteriornu ocjenu greške
Ovi rezultati su dobiveni uz pretpostavku da je
simetrična
pozitivno definitna matrica. To je važan slučaj, koji se pojavljuje
prilikom približnog rješavanja rubnih i rubno-početnih problema
varijacijskim metodama. Međutim, može se dogoditi da
ne
ispunjava ovaj uvjet. Ipak, dobiveni rezultati vrijede i tada uz neke
modifikacije.
Prije svega, budući da u općem slučaju vlastite vrijednosti mogu
biti kompleksni brojevi, broj
više nema
smisla, jer u skupu kompleksnih brojeva nemamo prirodni
uređaj. Umjesto toga imamo ovu definiciju.
Definicija 18
Neka je

matrica tipa

i neka su

njezine vlastite
vrijednosti. Broj
se zove
spektralni radius matrice

Očito je u slučaju simetričnosti i pozitivne definitnosti matrice
Može se dokazati sljedeći teorem
Teorem 24
Iterativni postupak
konvergira za bilo koju početnu aproksimaciju

ako i samo ako je
Tako se problem konvergencije iterativnog postupka svodi na problem
ocjene spektralnog radiusa, odnosno najveće po modulu (apsolutnoj
vrijednosti) vlastite vrijednosti matrice, i to ocjene odozgo. Ima
raznih ocjena te vrste. Navedimo neke od njih. Neka je
Tada vrijedi
- 1.
-
- 2.
-
- 3.
-

Ako je bilo koji od ovih brojeva na desnoj strani manji od
spektralni radius je nužno manji od
U nekim slučajevima je bilo
Tada je, prema 2, dovoljno da bude apsolutna vrijednost
dijagonalnog elementa matrice
veća od sume apsolutnih vrijednosti
ostalih elemenata u retku.
Primjer 3.3
Neka je matrica sustava
Treba ispitati da li Jacobijev i Gauss-Seidelov postupak konvergiraju.
Rješenje. U Jacobijevom postupku je
Njezine vlastite vrijednosti su
spektralni radius je
i prema tome Jacobijeva metoda konvergira za svaku početnu
aproksimaciju.
Kod Gauss-Seidelove metode je
Njezine vlastite vrijednosti su
spektralni radius je sada
pa prema tome Gauss-Seidelova metoda također konvergira za svaku
početnu aproksimaciju, i to brže nego Jacobijeva.
S porastom reda matrice, uz isti tridijagonalni oblik, vlastite
vrijednosti matrica
rastu prema
U slučajevima kad su vrlo
blizu broju
OR metode postaju vrlo efikasne u smislu brzine
konvergencije.
Next: Aproksimacija funkcije i numerička
Up: Rješavanje sustava jednadžbi
Previous: Gauss-Seidelova OR-metoda (SOR metoda)
  Contents
Salih Suljagic
1999-01-27