Next: Aproksimacija funkcije i numerička Up: Numerička matematika Previous: Rješavanje jednadžbi Contents Index
Subsections

- Iterativne metode
- Jacobijeva metoda
- Gauss-Seidelova metoda
- OR (overrelaxation) metode
  - Jacobijeva OR-metoda (JOR metoda)
  - Gauss-Seidelova OR-metoda (SOR metoda)
- Konvergencija iterativne metode

#
Rješavanje sustava jednadžbi

##
Iterativne metode

Želimo riješiti sustav linearnih algebarskih jednadžbi

koji matrično zapisan glasi

gdje je

To je matrična jednadžba, i mi ćemo često o sustavu jednadžbi govoriti kao o jednadžbi, misleći na ovu matričnu jednadžbu. Pretpostavimo da je regularna matrica. Tada jednadžba ima rješenje, i označimo to rješenje sa

Osnovna ideja iterativnih metoda se sastoji u sljedećem. Stavimo

gdje su i također kvadratne matrice -tog reda. Jednadžbu tada možemo prepisati kao

Ako s označimo -tu aproksimaciju rješenja, onda pomoću formule

možemo naći -vu aproksimaciju rješenja.

Naravno, da bi postupak uopće krenuo, treba biti zadana početna aproksimacija Nadalje, matrica mora biti regularna i relativno jednostavna, da bismo imali rješenje i da bismo ga mogli relativno jednostavno izračunati. Također postupak nas mora približavati k rješenju, tj. postupak mora biti takav da

Opišimo sada neke od iterativnih metoda.

##
Jacobijeva metoda

Pretpostavimo da su elementi na glavnoj dijagonali matrice različiti od nule (ako je potrebno, premještanjem redaka u regularnoj matrici se to uvijek može postići). Rastavimo kako slijedi

gdje je

Tako je donja, gornja trokutasta, a je dijagonalana matrica. Ako stavimo

imamo iterativni postupak oblika

Budući da su elementi na glavnoj dijagonali matrice a prema tome i matrice različiti od nule, postoji Inverz od dijagonalne matrice se vrlo lako računa. Iz slijedi Tako gornju jednadžbu možemo pomnožiti s lijeva s pa imamo sljedeći algoritam.

Algoritam 7 (Jacobijeva metoda) Proizvoljno izaberemo početnu aproksimaciju

i zatim računamo sljedeće aproksimacije po formuli

odnosno

gdje je

Budući da dijelimo s poželjno je, ako je to moguće, poredati retke u matrici (jednadžbe u sustavu) tako da svaki element na glavnoj dijagonali bude po apsolutnoj vrijednosti veći od sume apsolutnih vrijednosti ostalih elemenata u retku u kojem se nalazi.

##
Gauss-Seidelova metoda

Gauss-Seidelova metoda je poboljšanje Jacobijeve metode u sljedećem smislu.

Pod pretpostavkom da je

-ta aproksimacija rješenja, -vu nalazimo iz sustava

Dakle koji smo izračunali iz prve jednadžbe pomoću komponenti -te aproksimacije rješenja, koristimo odmah u drugoj, trećoj, ..., -toj jednadžbi; koristimo u trećoj, četvrtoj, ..., -toj jednadžbi; itd. Taj sustav možemo zapisati u matričnom obliku

odnosno

Tako imamo formulu iterativnog postupka

Nedostatak ove formule je u tome što treba naći inverz matrice što je teže nego naći inverz od Zato radimo malo drukčije. Pomnožimo ovu jednadžbu s

Odatle

Tako dolazimo do sljedećeg algoritma.

Algoritam 8 (Gauss-Seidelova metoda) Izaberemo proizvoljnu početnu aproksimaciju

i zatim računamo sljedeće aproksimacije po formuli

odnosno

gdje je

Primjer 3.10 Riješiti sljedeći sustav jednadžbi

Rješenje. Radi jednostavnosti ćemo radije vektorstupac rješenja pisati u obliku Ako počnemo s Jacobijeva metoda daje redom sljedeće aproksimacije.

Gauss-Seidelova metoda daje

Međutim, ako se promijeni poredak jednadžbi, tako da prva jednadžba dođe na treće mjesto, druga na prvo, a treća na drugo, tj. ako sustav napišemo u obliku

onda Jacobijevom metodom dobivamo

a Gauss-Seidelovom

Inače, rješenje na pet decimala točno, je

##
OR (overrelaxation) metode

Navedene metode se mogu poboljšati, obzirom na konvergentnost i brzinu konvergencije, na sljedeći način.

Matrica se rastavi kako slijedi

gdje su i matrice tipa ovisne o parametru Osim toga treba biti regularna. Parametar se zove parametar relaksacije. Tada je

| (3.11)

Zbog regularnosti postoji Stavimo

Uvrstimo u (3.11), dobivamo

Iterativni postupak je tada dan formulom

| (3.12)

Parametar relaksacije treba odabrati tako da postupak što brže konvergira.

###
Jacobijeva OR-metoda (JOR metoda)

Imamo

Neka je regularna matrica. Stavimo

Tada je

Tako imamo sljedeći algoritam

Algoritam 9 (Jacobijeva OR-metoda) Proizvoljno izaberemo početnu aproksimaciju

i zatim računamo sljedeće aproksimacije po formuli

odnosno

gdje je i

Primijetimo da za Jacobijeva OR metoda postaje Jacobijeva metoda.

###
Gauss-Seidelova OR-metoda (SOR metoda)

Imamo

Neka je regularna matrica. Stavimo

Tada je

Tako je

Računanje nije jednostavno, pa radimo nešto drukčije. Polazimo od prethodne jednadžbe

odnosno

Pomnožimo ovu jednadžbu s

Tako imamo sljedeći algoritam

Algoritam 10 (Gauss-Seidelova OR-metoda) Proizvoljno izaberemo početnu aproksimaciju

i zatim računamo sljedeće aproksimacije po formuli

odnosno

gdje je i

Primijetimo da za SOR metoda postaje Gauss-Seidelova metoda.

Broj treba uzeti tako da je Optimalna vrijednost ovisi o konkretnom problemu koji se rješava.

Primjer 3.11 Riješiti sustav u primjeru 3.10 OR metodama.

Rješenje. Jacobijeva OR metoda ne daje ništa bolje rezultate kad se uzme Gauss-Seidelova OR metoda za daje

##
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 16 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 25 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

Odatle možemo, na isti način kao kod računanja apriorne ocjene greške kod metode iteracije (v. 3.2.2), zaključiti

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 mora biti

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

za

Odatle

Ako pomnožimo s lijeva s i s desna s , slijedi

Prema tome

Zbog to je moguće samo ako je

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 17 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 26 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 Naglasimo da se ovdje ne radi o spektralnom radiusu matrice već matrice

Primjer 3.12 Ispitati konvergenciju Jacobijeve i Gauss-Seidelove metode u primjeru 3.10.

Rješenje. Kod Jacobijeve metode imamo

a kod Gauss-Seidelove

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

Ako primijenimo Jacobijevu metodu, imamo

Vlastite vrijednosti su pa je spektralni radius

Kod Gauss-Seidelove metode imamo još lošiji rezultat

Vlastite vrijednosti su pa je spektralni radius

Kad prvu jednadžbu stavimo na treće mjesto, Jacobijeva metoda daje

vlastite vrijednosti su pa je spektralni radius

vlastite vrijednosti su pa je spektralni radius Ako se radi Gauss-Seidelovom OR metodom, spektralni radius postaje za

Primjer 3.13 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 matrice 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: Numerička matematika Previous: Rješavanje jednadžbi Contents Index