Konvergencija iterativne metode

Iterativni postupci, koje smo upravo definirali, opisani su formulom #math2429#

#tex2html_wrap_indisplay36941#

gdje je #tex2html_wrap_inline36943# matrica tipa #tex2html_wrap_inline36945# definirana od slučaja do slučaja na različite načine pomoću matrice #tex2html_wrap_inline36947# Razmotrimo sada probleme konvergencije navedenih metoda.

Definicija 16   Neka je #tex2html_wrap_inline36950# simetrična matrica. Kažemo da je #tex2html_wrap_inline36952# pozitivno definitna, ako vrijedi #math2430#

#tex2html_wrap_indisplay36954#

Lema 3   Neka je #tex2html_wrap_inline36957# simetrična pozitivno definitna matrica tipa #tex2html_wrap_inline36959# Tada su vlastite vrijednosti #math2431##tex2html_wrap_inline36961# od matrice #tex2html_wrap_inline36963# pozitivne, i vrijedi #math2432#

#tex2html_wrap_indisplay36965#

za svaki #math2433##tex2html_wrap_inline36967#
<#12283#>Dokaz. Budući da je matrica #tex2html_wrap_inline36969# simetrična, postoji #tex2html_wrap_inline36971# međusobno okomitih i jediničnih vektora #math2434##tex2html_wrap_inline36973# u #math2435##tex2html_wrap_inline36975# i brojevi #math2436##tex2html_wrap_inline36977# takvih, da je #math2437#

#tex2html_wrap_indisplay36979#

Zbog pozitivne definitnosti #math2438#

#tex2html_wrap_indisplay36981#

Dokažimo sada drugu tvrdnju. Primijetimo najprije da vlastiti vektori #math2439##tex2html_wrap_inline36983# matrice #tex2html_wrap_inline36985# čine ortonormiranu bazu u #math2440##tex2html_wrap_inline36987# To znači da se bilo koji vektor #math2441##tex2html_wrap_inline36989# može prikazati kao njihova linearna kombinacija. #math2442#

#tex2html_wrap_indisplay36991#

Zbog linearnosti djelovanja matrice #tex2html_wrap_inline36993# na vektore #math2443#

#tex2html_wrap_indisplay36995#

Tako je #math2444#

#tex2html_wrap_indisplay36997#

#math2445#

#tex2html_wrap_indisplay36999#

Odatle #math2446#

#tex2html_wrap_indisplay37001#

#math2447##tex2html_wrap_inline37003#<#12283#>

Teorem 25   Neka je #tex2html_wrap_inline37006# simetrična, pozitivno definitna matrica. Iterativni postupak #math2448#

#tex2html_wrap_indisplay37008#

konvergira za bilo koju početnu aproksimaciju #math2449##tex2html_wrap_inline37010# ako i samo ako je #math2450#

#tex2html_wrap_indisplay37012#


<#12284#>Dokaz. 1. Dokažimo najprije da iz #math2451#

#tex2html_wrap_indisplay37014#

slijedi konvergencija iterativnog postupka. Doista #math2452#

#tex2html_wrap_indisplay37016#

i odatle #math2453#

#tex2html_wrap_indisplay37018#

Odatle možemo, na isti način kao kod računanja apriorne ocjene greške kod metode iteracije (v. #apr:ocj#9020>), zaključiti #math2454#

#tex2html_wrap_indisplay37020#

Budući da je #tex2html_wrap_inline37022# #math2455#

#tex2html_wrap_indisplay37024#

pa niz #math2456##tex2html_wrap_inline37026# konvergira. Neka je #math2457#

#tex2html_wrap_indisplay37028#

Tada je #math2458#

#tex2html_wrap_indisplay37030#

#math2459#

#tex2html_wrap_indisplay37032#

i prema tome niz konvergira k rješenju #math2460##tex2html_wrap_inline37034#
2. Dokažimo obrat, tj. da iz konvergencije postupka slijedi
#math2461#

#tex2html_wrap_indisplay37036#

Iz #math2462#

#tex2html_wrap_indisplay37038#

i #math2463#

#tex2html_wrap_indisplay37040#

slijedi #math2464#

#tex2html_wrap_indisplay37042#

Zbog pretpostavke #math2465#

#tex2html_wrap_indisplay37044#

slijedi #math2466#

#tex2html_wrap_indisplay37046#

Ako se to događa za svaku početnu aproksimaciju #math2467##tex2html_wrap_inline37048# onda mora biti #math2468#

#tex2html_wrap_indisplay37050#

Budući da je #tex2html_wrap_inline37052# simetrična matrica, ona se može dijagonalizirati, tj. postoji regularna matrica #tex2html_wrap_inline37054# takva, da vrijedi #math2469#

#tex2html_wrap_indisplay37056#;SPMnbsp; ;SPMnbsp;<#1#>za <#1#>#tex2html_wrap_indisplay37057#

Odatle #math2470#

#tex2html_wrap_indisplay37059#

#math2471#

#tex2html_wrap_indisplay37061#

#math2472#

#tex2html_wrap_indisplay37063#

Ako pomnožimo s lijeva s #tex2html_wrap_inline37065# i s desna s #tex2html_wrap_inline37067#, slijedi #math2473#

#tex2html_wrap_indisplay37069#

Prema tome #math2474#

#tex2html_wrap_indisplay37071#

Zbog #math2475##tex2html_wrap_inline37073# to je moguće samo ako je #math2476#

#tex2html_wrap_indisplay37075#

#math2477##tex2html_wrap_inline37077#<#12284#>

Na isti način kao kod metode iteracije prilikom traženja nultočke funkcije možemo naći apriornu ocjenu greške #math2478#

#tex2html_wrap_indisplay37079#

i aposteriornu ocjenu greške #math2479#

#tex2html_wrap_indisplay37081#

Ovi rezultati su dobiveni uz pretpostavku da je #tex2html_wrap_inline37083# 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 #tex2html_wrap_inline37085# 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 #math2480##tex2html_wrap_inline37087# više nema smisla, jer u skupu kompleksnih brojeva nemamo prirodni uređaj. Umjesto toga imamo ovu definiciju.

Definicija 17   Neka je #tex2html_wrap_inline37090# matrica tipa #tex2html_wrap_inline37092# i neka su #math2481##tex2html_wrap_inline37094# njezine vlastite vrijednosti. Broj #math2482#

#tex2html_wrap_indisplay37096#

se zove spektralni radius matrice #tex2html_wrap_inline37098#

Očito je u slučaju simetričnosti i pozitivne definitnosti matrice #tex2html_wrap_inline37100# #math2483#

#tex2html_wrap_indisplay37102#

Može se dokazati sljedeći teorem

Teorem 26   Iterativni postupak #math2484#

#tex2html_wrap_indisplay37105#

konvergira za bilo koju početnu aproksimaciju #math2485##tex2html_wrap_inline37107# ako i samo ako je #math2486#

#tex2html_wrap_indisplay37109#

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 #math2487##tex2html_wrap_inline37111# Tada vrijedi
<#37118#>1.<#37118#>
#math2488##tex2html_wrap_inline37113#
<#37119#>2.<#37119#>
#math2489##tex2html_wrap_inline37115#
<#37120#>3.<#37120#>
#math2490##tex2html_wrap_inline37117#
Ako je bilo koji od ovih brojeva na desnoj strani manji od #tex2html_wrap_inline37122# spektralni radius je nužno manji od #tex2html_wrap_inline37124# Naglasimo da se ovdje ne radi o spektralnom radiusu matrice #tex2html_wrap_inline37126# već matrice #tex2html_wrap_inline37128#

Primjer 3.12   Ispitati konvergenciju Jacobijeve i Gauss-Seidelove metode u primjeru #pr:sustav#9214>. Rješenje. Kod Jacobijeve metode imamo #math2491#

#tex2html_wrap_indisplay37131#

a kod Gauss-Seidelove #math2492#

#tex2html_wrap_indisplay37133#

Matrica sustava, kako je na početku napisan, je #math2493#

#tex2html_wrap_indisplay37135#

Ako primijenimo Jacobijevu metodu, imamo #math2494#

#tex2html_wrap_indisplay37137#

Vlastite vrijednosti su #math2495##tex2html_wrap_inline37139# pa je spektralni radius #math2496##tex2html_wrap_inline37141# Kod Gauss-Seidelove metode imamo još lošiji rezultat #math2497#

#tex2html_wrap_indisplay37143#

Vlastite vrijednosti su #math2498##tex2html_wrap_inline37145# pa je spektralni radius #math2499##tex2html_wrap_inline37147# Kad prvu jednadžbu stavimo na treće mjesto, Jacobijeva metoda daje #math2500#

#tex2html_wrap_indisplay37149#

vlastite vrijednosti su #math2501##tex2html_wrap_inline37151# pa je spektralni radius #math2502##tex2html_wrap_inline37153# #math2503#

#tex2html_wrap_indisplay37155#

vlastite vrijednosti su #math2504##tex2html_wrap_inline37157# pa je spektralni radius #math2505##tex2html_wrap_inline37159# Ako se radi Gauss-Seidelovom OR metodom, spektralni radius postaje #math2506##tex2html_wrap_inline37161# za #math2507##tex2html_wrap_inline37163#

Primjer 3.13   Neka je matrica sustava #math2508#

#tex2html_wrap_indisplay37166#

Treba ispitati da li Jacobijev i Gauss-Seidelov postupak konvergiraju. Rješenje. U Jacobijevom postupku je #math2509#

#tex2html_wrap_indisplay37168#

Njezine vlastite vrijednosti su #math2510#

#tex2html_wrap_indisplay37170#

spektralni radius je #math2511#

#tex2html_wrap_indisplay37172#

i prema tome Jacobijeva metoda konvergira za svaku početnu aproksimaciju. Kod Gauss-Seidelove metode je #math2512#

#tex2html_wrap_indisplay37174#

Njezine vlastite vrijednosti su #math2513#

#tex2html_wrap_indisplay37176#

spektralni radius je sada #math2514#

#tex2html_wrap_indisplay37178#

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 matrice #tex2html_wrap_inline37180# rastu prema #tex2html_wrap_inline37182# U slučajevima kad su vrlo blizu broju #tex2html_wrap_inline37184# OR metode postaju vrlo efikasne u smislu brzine konvergencije.