Rješavanje sustava jednadžbi jednostavnom iteracijom. Sloughovo rješenje jednostavnim ponavljanjem

Tema 3. Rješenje linearnih sustava algebarske jednadžbe iterativne metode.

Gore opisane izravne metode za rješavanje SLAE nisu vrlo učinkovite pri rješavanju velikih sustava (tj. kada vrijednost n dovoljno velik). U takvim slučajevima, iterativne metode su prikladnije za rješavanje SLAE.

Iterativne metode za rješavanje SLAE(njihov drugi naziv su metode sukcesivna aproksimacija do rješenja) ne daju točno rješenje SLAE, već daju samo aproksimaciju rješenja, a svaki sljedeća aproksimacija dobiva se iz prethodnog i točniji je od prethodnog (pod uvjetom da konvergencija ponavljanja). Početna (ili tzv. nulta) aproksimacija bira se blizu predloženog rješenja ili proizvoljno (može se uzeti kao vektor desne strane sustava). Točno rješenje nalazi se kao granica takvih aproksimacija jer njihov broj teži beskonačnosti. U pravilu, za konačan broj koraka (tj. ponavljanja) ova granica nije dosegnuta. Stoga se u praksi koncept točnost rješenja, naime neki pozitivan i dovoljno mali broj e a proces izračunavanja (iteracija) se provodi sve dok se relacija ne ispuni .

Ovdje je aproksimacija rješenja dobivenog nakon broja iteracije n , te je točno rješenje SLAE (koje nije unaprijed poznato). Broj ponavljanja n = n (e ) potrebna za postizanje navedene točnosti za specifične metode može se dobiti iz teoretskih razmatranja (tj. postoje formule za izračun). Kvaliteta različitih iterativnih metoda može se usporediti prema broju ponavljanja potrebnih za postizanje iste točnosti.

Za proučavanje iterativnih metoda na konvergencija morate znati izračunati norme matrica. Norma matrice- ovo je nešto brojčana vrijednost, koji karakterizira veličinu elemenata matrice u apsolutnoj vrijednosti. U viša matematika postoji nekoliko razne vrste matrične norme, koje su obično ekvivalentne. U našem tečaju koristit ćemo samo jedan od njih. Naime, pod matrična norma razumjet ćemo najveća vrijednost među zbrojevima apsolutnih vrijednosti elemenata pojedinih redaka matrice. Da bi se označila norma matrice, njen naziv sastoji se od dva para okomitih crtica. Dakle, za matricu A pod njegovom normom podrazumijevamo količinu

. (3.1)

Tako je, na primjer, norma matrice A iz primjera 1 sljedeća:

Za rješavanje SLAE najčešće se koriste tri iterativne metode

Metoda jednostavne iteracije

Jacobijeva metoda

Guass-Seidel metoda.

Metoda jednostavne iteracije uključuje prijelaz s pisanja SLAE u izvornom obliku (2.1) na pisanje u obliku

(3.2)

ili, što je također matrični oblik,

x = S × x + D , (3.3)

C - matrica koeficijenata transformiranog sustava dimenzija n ´ n

x - vektor nepoznanica, koji se sastoji od n komponenta

D - vektor desnih dijelova transformiranog sustava koji se sastoji od n komponenta.

Sustav u obliku (3.2) može se prikazati u skraćenom obliku

Iz ovog pogleda jednostavna iteracijska formulaće izgledati

Gdje m - broj iteracije i - vrijednost x j na m - korak iteracije. Zatim, ako proces iteracije konvergira, s povećanjem broja ponavljanja, uočit će se

To dokazao proces iteracije konvergira, Ako norma matrice D htjeti manje od jedinicas.

Ako uzmemo vektor slobodnih članova kao početnu (nultu) aproksimaciju, tj. x (0) = D , To granica pogreške ima oblik

(3.5)

ovdje ispod x * je točno rješenje sustava. Stoga,

Ako , zatim prema dana točnoste može se unaprijed izračunati potreban broj ponavljanja. Naime, iz relacije

nakon neznatnih transformacija dobivamo

. (3.6)

Izvođenjem takvog broja iteracija zajamčeno je osigurana zadana točnost pronalaženja rješenja sustava. Ova teorijska procjena potreban iznos iteracijski koraci su donekle preskupi. U praksi se potrebna točnost može postići u manje ponavljanja.

Rješenja zadanog SLAE zgodno je tražiti metodom jednostavne iteracije uz unos dobivenih rezultata u tablicu sljedećeg oblika:

	x 1	x 2		x n

Posebno treba istaknuti da kod rješavanja SLAE ovom metodom najteže i najteže je transformirati sustav iz oblika (2.1) u oblik (3.2). Ove transformacije moraju biti ekvivalentne, tj. koji ne mijenjaju rješenje izvornog sustava i osiguravaju vrijednost norme matrice C (nakon što ih učinite) manje od jednog. Ne postoji jedinstveni recept za takve transformacije. Ovdje je u svakom slučaju potrebno pokazati kreativnost. Smatrati primjeri, u kojem će se dati neki načini transformacije sustava u traženi oblik.

Primjer 1 Nađimo rješenje sustava linearnih algebarskih jednadžbi metodom jednostavne iteracije (s točnošću e= 0.001)

Ovaj sustav se na najjednostavniji način svodi na traženi oblik. Prebacujemo sve članove s lijeve strane na desnu stranu, a zatim zbrajamo obje strane svake jednadžbe x i (ja =1, 2, 3, 4). Dobivamo transformirani sustav sljedećeg oblika

.

Matrica C i vektor D u ovom slučaju će biti kako slijedi

C = , D = .

Izračunajte normu matrice C . Dobiti

Kako se pokazalo da je norma manja od jedan, osigurana je konvergencija metode jednostavne iteracije. Kao početnu (nultu) aproksimaciju uzimamo komponente vektora D . Dobiti

, , , .

Pomoću formule (3.6) izračunavamo potreban broj iteracijskih koraka. Odredimo najprije normu vektora D . Dobiti

.

Dakle, za postizanje navedene točnosti potrebno je izvršiti najmanje 17 iteracija. Napravimo prvu iteraciju. Dobiti

Nakon što smo izvršili sve aritmetičke operacije, dobivamo

.

Nastavljajući na isti način, izvodimo daljnje korake ponavljanja. Njihovi rezultati su sažeti u sljedećoj tablici ( D - najveća vrijednost komponente rješenja se mijenjaju između trenutnog i prethodnog koraka)

M

Budući da je već nakon desetog koraka razlika između vrijednosti u zadnje dvije iteracije postala manja od navedene točnosti, proces iteracije se prekida. Kao pronađeno rješenje uzimamo vrijednosti dobivene u zadnjem koraku.

Primjer 2

Učinimo isto kao u prethodnom primjeru. Dobiti

Matrica C takav sustav će

C =.

Izračunajmo njegovu normu. Dobiti

Očito, iterativni proces za takvu matricu neće konvergirati. Potrebno je pronaći drugi način transformacije zadanog sustava jednadžbi.

Preuredimo njegove pojedinačne jednadžbe u izvorni sustav jednadžbi tako da treći redak postane prvi, prvi - drugi, drugi - treći. Zatim, transformirajući ga na isti način, dobivamo

Matrica C takav sustav će

C =.

Izračunajmo njegovu normu. Dobiti

Budući da matrična norma C pokazalo se da je manji od jedinice, tako transformirani sustav je pogodan za rješavanje jednostavnom iteracijom.

Primjer 3 Transformiramo sustav jednadžbi

u oblik koji bi omogućio korištenje metode jednostavne iteracije pri rješavanju.

Postupimo najprije slično primjeru 1. Dobivamo

Matrica C takav sustav će

C =.

Izračunajmo njegovu normu. Dobiti

Očito, iterativni proces za takvu matricu neće konvergirati.

Kako bismo transformirali izvornu matricu u oblik prikladan za primjenu metode jednostavne iteracije, postupit ćemo na sljedeći način. Prvo formiramo "međusustav" jednadžbi u kojem

- prva jednadžba je zbroj prve i druge jednadžbe izvornog sustava

- druga jednadžba- zbroj udvostručene treće jednadžbe s drugom minus prva

- treća jednadžba- razlika između treće i druge jednadžbe izvornog sustava.

Kao rezultat, dobivamo ekvivalent izvornom "srednjem" sustavu jednadžbi

Iz njega je lako dobiti drugi sustav, "međusustav".

,

i iz njega se obratio

.

Matrica C takav sustav će

C =.

Izračunajmo njegovu normu. Dobiti

Iterativni proces za takvu matricu bit će konvergentan.

Jacobijeva metoda pretpostavlja da su svi dijagonalni elementi matrice A izvornog sustava (2.2) nisu jednaki nuli. Tada se izvorni sustav može prepisati kao

(3.7)

Iz takvog zapisa nastaje sustav iteracijska formula Jacobijeva metoda

Uvjet za konvergenciju iterativnog procesa Jacobijeve metode je uvjet tzv dijagonalna dominacija u izvornom sustavu (forme (2.1)). Analitički, ovaj uvjet se piše kao

. (3.9)

Treba napomenuti da ako u danom sustavu jednadžbi, uvjet konvergencije Jacobijeve metode (tj. uvjet dijagonalne dominacije) nije zadovoljen, u mnogim slučajevima to je moguće pomoću ekvivalentne transformacije izvorni SLAE da svoje rješenje dovede do rješenja ekvivalentnog SLAE u kojem je ovaj uvjet zadovoljen.

Primjer 4 Transformiramo sustav jednadžbi

u oblik koji bi omogućio korištenje Jacobijeve metode u njegovom rješavanju.

Taj smo sustav već razmatrali u primjeru 3, pa ćemo s njega prijeći na tamo dobiveni "srednji" sustav jednadžbi. Lako je ustanoviti da je za njega zadovoljen uvjet dijagonalne dominacije, pa ga transformiramo u oblik potreban za primjenu Jacobijeve metode. Dobiti

Iz njega dobivamo formulu za izvođenje proračuna pomoću Jacobijeve metode za zadani SLAE

Uzimajući kao početnu, tj. nula, aproksimacija vektora slobodnih članova izvršit će sve potrebne izračune. Rezultate sažimamo u tablici

m					D

Dovoljno visoka točnost dobiveno rješenje je postignuto u šest ponavljanja.

Gauss-Seidel metoda je poboljšanje Jacobijeve metode i također pretpostavlja da svi dijagonalni elementi matrice A izvornog sustava (2.2) nisu jednaki nuli. Tada se izvorni sustav može prepisati u obliku sličnom Jacobijevoj metodi, ali donekle različitom od nje

Ovdje je važno upamtiti da ako je gornji indeks u znaku zbroja manji od indeksa, tada se zbrajanje ne izvodi.

Ideja Gauss-Seidelove metode leži u činjenici da su autori metode vidjeli mogućnost ubrzanja procesa proračuna u odnosu na Jacobijevu metodu zbog činjenice da su u procesu sljedeće iteracije, pronašavši novu vrijednost x 1 Limenka Odjednom koristiti ovu novu vrijednost u istoj iteraciji za izračun ostalih varijabli. Slično, dalje, pronalaženje nove vrijednosti x 2 možete ga također odmah koristiti u istoj iteraciji itd.

Na temelju toga, iteracijska formula za Gauss-Seidel metodu Ima sljedeći pogled

Dovoljno zauvjet konvergencije iterativni proces Gauss-Seidel metode je još uvijek isti uvjet dijagonalna dominacija (3.9). Stopa konvergencije ova metoda je nešto viša nego kod Jacobijeve metode.

Primjer 5 Sustav jednadžbi rješavamo Gauss-Seidelovom metodom

Ovaj sustav smo već razmatrali u primjerima 3 i 4, pa ćemo s njega odmah prijeći na transformirani sustav jednadžbi (vidi primjer 4), u kojem je zadovoljen uvjet dijagonalne dominacije. Iz njega dobivamo formulu za izvođenje izračuna pomoću Gauss-Seidelove metode

Uzimajući vektor slobodnih članova kao početnu (tj. nultu) aproksimaciju, izvodimo sve potrebne izračune. Rezultate sažimamo u tablici

m

U pet iteracija postignuta je prilično visoka točnost dobivenog rješenja.

Prednost iterativnih metoda je njihova primjenjivost na loše uvjetovane sustave i sustave visokog reda, njihova samokorekcija i jednostavnost implementacije na računalu. Iterativne metode za početak izračuna zahtijevaju početnu aproksimaciju željenog rješenja.

Treba napomenuti da uvjeti i brzina konvergencije iterativnog procesa bitno ovise o svojstvima matrice A sustava i na izbor početnih aproksimacija.

Da bi se primijenila metoda ponavljanja, izvorni sustav (2.1) ili (2.2) mora se svesti na oblik

nakon čega se provodi iterativni proces prema rekurentne formule

, k = 0, 1, 2, ... . (2.26A)

Matrica G i vektor dobiveni su kao rezultat transformacije sustava (2.1).

Za konvergenciju (2.26 A) je potrebno i dovoljno za |l ja(G)| < 1, где lja(G) - Svi svojstvene vrijednosti matrice G. Do konvergencije će doći i ako || G|| < 1, так как |lja(G)| < " ||G||, gdje je " bilo koji.

Simbol || ... || znači norma matrice. Pri određivanju njegove vrijednosti najčešće se zaustavljaju na provjeri dva uvjeta:

||G|| = ili || G|| = , (2.27)

Gdje . Konvergencija je također zajamčena ako je izvorna matrica A ima dijagonalnu prevlast, tj.

. (2.28)

Ako je (2.27) ili (2.28) zadovoljeno, metoda iteracije konvergira za bilo koju početnu aproksimaciju. Najčešće se za vektor uzima ili nula ili jedinica, ili se sam vektor uzima iz (2.26).

Postoji mnogo pristupa transformaciji izvornog sustava (2.2) s matricom A da se osigura oblik (2.26) ili da se zadovolje uvjeti konvergencije (2.27) i (2.28).

Na primjer, (2.26) se može dobiti na sljedeći način.

Neka A = U+ S, det U¹ 0; Zatim ( B+ S)= Þ B= −C+ Þ Þ B –1 B= −B –1 C+ B–1 , odakle je = − B –1 C+ B –1 .

Stavljanje - B –1 C = G, B–1 = , dobivamo (2.26).

Iz uvjeta konvergencije (2.27) i (2.28) vidljivo je da je reprezentacija A = U+ S ne može biti proizvoljna.

Ako matrica A zadovoljava uvjete (2.28), zatim kao matrica U možete odabrati donji trokutasti:

, a ii ¹ 0.

; Þ ; Þ ; Þ

Odabirom parametra a možemo osigurati || G|| = ||E+ a A|| < 1.

Ako (2.28) prevladava, tada se transformacija u (2.26) može izvršiti rješavanjem svakog ja jednadžbu sustava (2.1) s obzirom na x i prema sljedećim rekurzivnim formulama:

(2.28A)

Ako se u matrici A nema dijagonalne dominacije, mora se postići uz pomoć nekih linearne transformacije koji ne narušavaju njihovu istovjetnost.

Kao primjer, razmotrite sustav

(2.29)

Kao što se vidi, u jednadžbama (1) i (2) nema dijagonalne dominacije, ali u (3) ima, pa je ostavljamo nepromijenjenom.

Postignimo dijagonalnu dominaciju u jednadžbi (1). Pomnožite (1) s a, (2) s b, dodajte obje jednadžbe i odaberite a i b u dobivenoj jednadžbi tako da postoji dijagonalna dominacija:

(2a + 3b) x 1 + (-1,8a + 2b) x 2 +(0,4a - 1,1b) x 3 = a.

Uzimajući a = b = 5, dobivamo 25 x 1 + x 2 – 3,5x 3 = 5.

Za transformaciju jednadžbe (2) s dominacijom (1), množimo s g, (2) množimo s d i oduzimamo (1) od (2). Dobiti

(3d - 2g) x 1+(2d+1,8g) x 2 +(-1,1d - 0,4g) x 3 = −g .

Stavljajući d = 2, g = 3, dobivamo 0 x 1 + 9,4 x 2 – 3,4 x 3 = -3. Kao rezultat, dobivamo sustav

(2.30)

Ova tehnika se može koristiti za pronalaženje rješenja za široku klasu matrica.

ili

Uzimajući kao početnu aproksimaciju vektor = (0,2; -0,32; 0) T, riješit ćemo ovaj sustav pomoću tehnologije (2.26 A):

k = 0, 1, 2, ... .

Proces izračuna se zaustavlja kada se dvije susjedne aproksimacije vektora rješenja poklapaju u točnosti, tj.

.

Tehnologija iterativno rješenje vrsta (2.26 A) je imenovan jednostavnom iteracijom .

Razred apsolutna greška za metodu jednostavne iteracije:

gdje je simbol || ... || znači norma.

Primjer 2.1. Metodom jednostavne iteracije s točnošću e = 0,001 riješite sustav linearne jednadžbe:

Broj koraka koji daju odgovor točan na e = 0,001 može se odrediti iz relacije

£0,001.

Procijenimo konvergenciju formulom (2.27). Ovdje || G|| = = max(0,56; 0,61; 0,35; 0,61) = 0,61< 1; = 2,15. Значит, сходимость обеспечена.

Kao početnu aproksimaciju uzimamo vektor slobodnih članova, tj. = (2,15; -0,83; 1,16; 0,44) T. Vrijednosti vektora zamijenimo u (2.26 A):

Nastavljajući s izračunima, rezultate ćemo unijeti u tablicu:

k	x 1	x 2	x 3	x 4
	2,15	–0,83	1,16	0,44
	2,9719	–1,0775	1,5093	–0,4326
	3,3555	–1,0721	1,5075	–0,7317
	3,5017	–1,0106	1,5015	–0,8111
	3,5511	–0,9277	1,4944	–0,8321
	3,5637	–0,9563	1,4834	–0,8298
	3,5678	–0,9566	1,4890	–0,8332
	3,5760	–0,9575	1,4889	–0,8356
	3,5709	–0,9573	1,4890	–0,8362
	3,5712	–0,9571	1,4889	–0,8364
	3,5713	–0,9570	1,4890	–0,8364

Konvergencija u tisućinkama događa se već na 10. koraku.

Odgovor: x 1 » 3.571; x 2 » -0,957; x 3 » 1.489; x 4"-0,836.

Ovo se rješenje također može dobiti pomoću formula (2.28 A).

Primjer 2.2. Za ilustraciju algoritma pomoću formula (2.28 A) razmotriti rješenje sustava (samo dvije iteracije):

; . (2.31)

Pretvorimo sustav u oblik (2.26) prema (2.28 A):

Þ (2.32)

Uzmimo početnu aproksimaciju = (0; 0; 0) T. Zatim za k= 0 očito vrijednost = (0,5; 0,8; 1,5) T. Zamijenimo ove vrijednosti u (2.32), tj. za k= 1 dobivamo = (1,075; 1,3; 1,175) T.

Pogreška e 2 = = max(0,575; 0,5; 0,325) = 0,575.

Blok dijagram algoritma za pronalaženje rješenja SLAE metodom jednostavne iteracije prema radnim formulama (2.28 A) prikazan je na sl. 2.4.

Značajka blok dijagrama je prisutnost sljedećih blokova:

- blok 13 - njegova svrha se raspravlja u nastavku;

- blok 21 - prikaz rezultata na ekranu;

– blok 22 – verifikacija (indikator) konvergencije.

Analizirajmo predloženu shemu na primjeru sustava (2.31) ( n= 3, w = 1, e = 0,001):

= ; .

Blok 1. Unesite početne podatke A, , w, e, n: n= 3, w = 1, e = 0,001.

ciklus I. Postavite početne vrijednosti vektora x 0ja I x i (ja = 1, 2, 3).

Blok 5. Resetirajte brojač broja ponavljanja.

Blok 6. Resetirajte trenutni brojač grešaka.

U petlja II mijenja brojeve redaka matrice A i vektor .

Ciklus II:ja = 1: s = b 1 = 2 (blok 8).

Idite na ugniježđenu petlju III, blok9 - brojač brojeva stupaca matrice A: j = 1.

Blok 10: j = ja, stoga se vraćamo na blok 9 i povećavamo j po jedinici: j = 2.

U bloku 10 j ¹ ja(2 ¹ 1) - idite na blok 11.

Blok 11: s= 2 – (–1) × x 0 2 \u003d 2 - (-1) × 0 \u003d 2, idite na blok 9, u kojem j povećati za jedan: j = 3.

U bloku 10 stanje j ¹ ja izvršeno, pa idite na blok 11.

Blok 11: s= 2 – (–1) × x 0 3 \u003d 2 - (-1) × 0 \u003d 2, nakon čega idemo na blok 9, u kojem j povećati za jedan ( j= 4). Značenje j više n (n= 3) – završite petlju i idite na blok 12.

Blok 12: s = s / a 11 = 2 / 4 = 0,5.

Blok 13: w = 1; s = s + 0 = 0,5.

Blok 14: d = | x i – s | = | 1 – 0,5 | = 0,5.

Blok 15: x i = 0,5 (ja = 1).

Blok 16. Provjerite stanje d > de: 0,5 > 0, dakle, idemo na blok 17, u kojem dodjeljujemo de= 0,5 i vrati referencom " A» do sljedećeg koraka ciklusa II - do bloka7, u kojem ja povećati za jedan.

Ciklus II: ja = 2: s = b 2 = 4 (blok 8).

j = 1.

Kroz blok 10 j ¹ ja(1 ¹ 2) - idite na blok 11.

Blok 11: s= 4 – 1 × 0 = 4, idite na blok 9, u kojem j povećati za jedan: j = 2.

U bloku 10 uvjet nije ispunjen pa idemo na blok 9 u kojem j povećati za jedan: j= 3. Po analogiji prelazimo na blok 11.

Blok 11: s= 4 – (–2) × 0 = 4, nakon čega završavamo ciklus III i idemo na blok 12.

Blok 12: s = s/ a 22 = 4 / 5 = 0,8.

Blok 13: w = 1; s = s + 0 = 0,8.

Blok 14: d = | 1 – 0,8 | = 0,2.

Blok 15: x i = 0,8 (ja = 2).

Blok 16. Provjerite stanje d > de: 0,2 < 0,5; следовательно, возвращаемся по ссылке «A» na sljedeći korak II ciklusa – na blok7.

Ciklus II: ja = 3: s = b 3 = 6 (blok 8).

Idi na ugniježđenu petlju III, blok 9: j = 1.

Blok 11: s= 6 – 1 × 0 = 6, idite na blok 9: j = 2.

Kroz blok 10, idemo do bloka 11.

Blok 11: s= 6 – 1 × 0 = 6. Završite ciklus III i prijeđite na blok 12.

Blok 12: s = s/ a 33 = 6 / 4 = 1,5.

Blok 13: s = 1,5.

Blok 14: d = | 1 – 1,5 | = 0,5.

Blok 15: x i = 1,5 (ja = 3).

Prema bloku 16 (uzimajući u obzir reference " A"I" S”) izađite iz ciklusa II i idite na blok 18.

Blok 18. Povećajte broj ponavljanja to = to + 1 = 0 + 1 = 1.

U blokovima 19 i 20 ciklusa IV zamjenjujemo početne vrijednosti x 0ja primljene vrijednosti x i (ja = 1, 2, 3).

Blok 21. Ispisujemo međuvrijednosti trenutne iteracije, in ovaj slučaj: = (0,5; 0,8; 1,5)T, to = 1; de = 0,5.

Prelazimo na ciklus II na bloku 7 i izvodimo razmatrane izračune s novim početne vrijednosti x 0ja (ja = 1, 2, 3).

Nakon čega dobivamo x 1 = 1,075; x 2 = 1,3; x 3 = 1,175.

Ovdje, dakle, Seidelova metoda konvergira.

Po formulama (2.33)

k	x 1	x 2	x 3
	0,19	0,97	–0,14
	0,2207	1,0703	–0,1915
	0,2354	1,0988	–0,2118
	0,2424	1,1088	–0,2196
	0,2454	1,1124	–0,2226
	0,2467	1,1135	–0,2237
	0,2472	1,1143	–0,2241
	0,2474	1,1145	–0,2243
	0,2475	1,1145	–0,2243

Odgovor: x 1 = 0,248; x 2 = 1,115; x 3 = –0,224.

Komentar. Ako za isti sustav metode jednostavne iteracije i Seidel konvergiraju, tada je Seidelova metoda poželjnija. Međutim, u praksi područja konvergencije ovih metoda mogu biti različita, tj. metoda jednostavne iteracije konvergira, a Seidelova metoda divergira i obrnuto. Za obje metode, ako je || G|| blizu jedinica, stopa konvergencije je vrlo niska.

Za ubrzanje konvergencije koristi se umjetna tehnika – tzv metoda opuštanja . Njegova bit leži u činjenici da je sljedeća vrijednost dobivena metodom ponavljanja x i (k) preračunava se prema formuli

gdje se w obično mijenja od 0 do 2 (0< w £ 2) с каким-либо шагом (h= 0,1 ili 0,2). Parametar w odabran je tako da se konvergencija metode postigne u minimalnom broju iteracija.

Opuštanje- postupno slabljenje bilo kojeg stanja tijela nakon prestanka djelovanja čimbenika koji su to stanje uzrokovali (fizičko-tehnički).

Primjer 2.4. Razmotrite rezultat pete iteracije pomoću formule za opuštanje. Uzmimo w = 1,5:

Kao što vidite, dobiven je rezultat gotovo sedme iteracije.

UVOD

1. SPORO RJEŠAVANJE METODOM JEDNOSTAVNE ITERACIJE

1.1 Opis metode rješenja

1.2 Pozadina

1.3 Algoritam

1.4 Program QBasic

1.5 Rezultat programa

1.6 Provjera rezultata programa

2. PROČIŠĆAVANJE KORIJENA TANGENTNOM METODOM

2.1 Opis metode rješenja

2.2 Početni podaci

2.3 Algoritam

2.4 Program QBasic

2.5 Rezultat programa

2.6 Provjera rezultata programa

3. NUMERIČKA INTEGRACIJA PREMA PRAVILU PRAVOKUTNIKA

3.1 Opis metode rješenja

3.2 Početni podaci

3.3 Algoritam

3.4 Program QBasic

3.5 Provjera rezultata programa

4.1 Opće informacije O programu

4.1.1 Svrha i razlikovna obilježja

4.1.2 Ograničenja WinRAR-a

4.1.3 Zahtjevi sustava WinRAR

4.2 WinRAR sučelje

4.3 Načini upravljanja datotekama i arhivama

4.4 Korištenje kontekstnih izbornika

ZAKLJUČAK

BIBLIOGRAFIJA

UVOD

Ovaj seminarski rad je razvoj algoritama i programa za rješavanje sustava linearnih algebarskih jednadžbi Gaussovom metodom; nelinearna jednadžba metodom akorda; Za numerička integracija prema pravilu trapeza.

Algebarskim jednadžbama nazivaju se jednadžbe koje sadrže samo algebarske funkcije (cijela, racionalna, iracionalna). Konkretno, polinom je cijela algebarska funkcija. Jednadžbe koje sadrže druge funkcije (trigonometrijske, eksponencijalne, logaritamske i druge) nazivaju se transcendentalnima.

Metode rješavanja sustava linearnih algebarskih jednadžbi dijele se u dvije skupine:

točne metode, koje su konačni algoritmi za izračunavanje korijena sustava (rješavanje sustava pomoću inverzna matrica, Cramerovo pravilo, Gaussova metoda itd.),

· iterativne metode koje omogućuju dobivanje rješenja sustava sa zadanom točnošću pomoću konvergentnih iterativnih procesa (iteracijska metoda, Seidelova metoda itd.).

Zbog neizbježnog zaokruživanja rezultati ujednačeni precizne metode su približni. Štoviše, kada se koriste iterativne metode, dodaje se pogreška metode.

Rješavanje sustava linearnih algebarskih jednadžbi jedan je od glavnih problema računalne linearne algebre. Iako je problem rješavanja sustava linearnih jednadžbi relativno rijetko od samostalnog interesa za aplikacije, sama sposobnost rješavanja takvih sustava često ovisi o sposobnosti učinkovitog rješavanja takvih sustava. matematičko modeliranješirok izbor računalno potpomognutih procesa. Značajan dio numeričkih metoda za rješavanje različitih (osobito nelinearnih) problema uključuje rješavanje sustava linearnih jednadžbi kao elementarnog koraka odgovarajućeg algoritma.

Da bi sustav linearnih algebarskih jednadžbi imao rješenje potrebno je i dovoljno da rang glavne matrice bude jednako rangu proširena matrica. Ako je rang glavne matrice jednak rangu proširene matrice i jednak je broju nepoznato, tada sustav ima jedinstveno rješenje. Ako je rang glavne matrice jednak rangu proširene matrice, ali manji broj nepoznato, tada sustav ima beskonačan broj rješenja.

Jedna od najčešćih metoda za rješavanje sustava linearnih jednadžbi je Gaussova metoda. Ova metoda je poznata u razne opcije preko 2000 godina. Gaussova metoda je klasična metoda za rješavanje sustava linearnih algebarskih jednadžbi (SLAE). Ovo je metoda sekvencijalno isključenje varijable pri korištenju elementarne transformacije sustav jednadžbi sveden je na ekvivalentni sustav stepenastog (ili trokutastog) oblika, iz kojeg se sve ostale varijable pronalaze sekvencijalno, počevši od zadnje (po broju) varijable.

Strogo govoreći, gore opisana metoda ispravno se naziva Gauss-Jordanova metoda eliminacije, budući da je varijacija Gaussove metode koju je opisao geodet Wilhelm Jordan 1887.). Također je zanimljivo napomenuti da je u isto vrijeme kad i Jordan (a prema nekim izvorima i prije njega), ovaj algoritam izumio Clasen (B.-I. Clasen).

Pod, ispod nelinearne jednadžbe shvaćene kao algebarske i transcendentne jednadžbe oblika , gdje je x - pravi broj, A - nelinearna funkcija. Za rješavanje ovih jednadžbi koristi se metoda akorda – iterativna numerička metoda približan nalaz korijena. Kao što je poznato, mnoge jednadžbe i sustavi jednadžbi nemaju analitička rješenja. Prije svega, ovo se odnosi na većinu transcendentalnih jednadžbi. Također je dokazano da je nemoguće konstruirati formulu kojom bi bilo moguće riješiti proizvoljnu algebarsku jednadžbu stupnja višeg od četvrtog. Osim toga, u nekim slučajevima jednadžba sadrži koeficijente koji su poznati samo približno, pa se, posljedično, pojavljuje problem točna definicija korijeni jednadžbe su besmisleni. Za njihovo rješavanje koriste se iterativne metode sa zadanim stupnjem točnosti. Riješiti jednadžbu iterativnom metodom znači utvrditi ima li ona korijene, koliko korijena i pronaći vrijednosti korijena sa potrebnom točnošću.

Problem pronalaženja korijena jednadžbe f(x) = 0 iterativnom metodom sastoji se od dvije faze:

odvajanje korijena - pronalaženje približne vrijednosti korijena ili segmenta koji ga sadrži;

· prečišćavanje aproksimativnih korijena - dovođenje na zadani stupanj točnosti.

određeni integral funkcija f(x) uzeta u intervalu od a prije b, naziva se granica kojoj teži integralni zbroj kada svi intervali ∆x i teže nuli. Prema pravilu trapeza, potrebno je zamijeniti graf funkcije F (x) ravnom linijom koja prolazi kroz dvije točke (x 0, y 0) i (x 0 + h, y 1), te izračunati vrijednost elementa integralnog zbroja kao površine trapeza: .

RJEŠENJE SPOROSTI METODOM JEDNOSTAVNE ITERACIJE

1.1 Opis metode konstantne iteracije

Sustavi algebarskih jednadžbi (SLAE) imaju oblik:

ili, kada je napisano u matričnom obliku:

U praksi se koriste dvije vrste metoda numeričko rješenje SLAE - izravni i neizravni. Pri korištenju izravnih metoda, SLAE se svodi na jedan od posebnih oblika (dijagonalni, trokutasti) koji vam omogućuje točno dobivanje željenog rješenja (ako postoji). Najčešća izravna metoda za rješavanje SLAE je Gaussova metoda. Iterativne metode koriste se za pronalaženje približnog rješenja SLAE sa zadanom točnošću. Treba napomenuti da iterativni proces ne konvergira uvijek rješenju sustava, već samo kada niz aproksimacija dobivenih u izračunima teži točnom rješenju. Kod rješavanja SLAE metodom jednostavne iteracije, pretvara se u oblik kada je samo jedna od traženih varijabli na lijevoj strani:

Davši neke početne aproksimacije xi, i=1,2,…,n, zamijenite ih u desna strana izraze i računati nove vrijednosti x. Proces se ponavlja do maksimuma ostataka određenih izrazom:

ne postaje manja od zadane točnosti ε. Ako je maksimalno odstupanje pri k-ta iteracija bit će veća od najvećeg odstupanja pri k-1-ta iteracija, tada se proces abnormalno prekida, jer iterativni proces se razilazi. Kako bi se smanjio broj ponavljanja, nove x vrijednosti mogu se izračunati korištenjem rezidualnih vrijednosti iz prethodne iteracije.

Predavanje Iterativne metode rješavanja sustava algebarskih linearnih jednadžbi.

Uvjeti konvergencije iterativnog procesa Jacobijeva metoda Seidelova metoda

Metoda jednostavne iteracije

Razmatran je sustav linearnih algebarskih jednadžbi

Da bi se primijenile iterativne metode, sustav se mora svesti na ekvivalentan oblik

Zatim se odabire početna aproksimacija rješenja sustava jednadžbi i pronalazi niz aproksimacija korijenu.

Da bi iterativni proces konvergirao, dovoljno je da uvjet
(matrična norma). Kriterij prekida za iteracije ovisi o primijenjenoj iterativnoj metodi.

Jacobijeva metoda .

Najjednostavniji način da se sustav dovede u oblik pogodan za iteraciju je sljedeći:

Iz prve jednadžbe sustava izražavamo nepoznanicu x 1 , iz druge jednadžbe sustava izražavamo x 2 itd.

Kao rezultat, dobivamo sustav jednadžbi s matricom B, u kojoj su nula elemenata na glavnoj dijagonali, a preostali elementi se izračunavaju po formulama:

Komponente vektora d izračunavaju se po formulama:

Formula za izračun metode jednostavne iteracije je:

ili u koordinatnom zapisu izgleda ovako:

Kriterij za završetak iteracija u Jacobijevoj metodi ima oblik:

Ako
, tada možemo primijeniti jednostavniji kriterij za završetak ponavljanja

Primjer 1 Rješenje sustava linearnih jednadžbi Jacobijevom metodom.

Neka je dan sustav jednadžbi:

Potrebno je točno pronaći rješenje sustava

Dovodimo sustav u oblik pogodan za ponavljanje:

Biramo početnu aproksimaciju, na primjer,

je vektor desne strane.

Tada prva iteracija izgleda ovako:

Na sličan se način dobivaju sljedeće aproksimacije rješenja.

Nađite normu matrice B.

Koristit ćemo normu

Budući da je zbroj modula elemenata u svakom retku 0,2, tada
, pa je kriterij za završetak iteracija u ovom problemu

Izračunajmo norme razlika vektora:

Jer
navedena točnost se postiže u četvrtoj iteraciji.

Odgovor: x 1 = 1.102, x 2 = 0.991, x 3 = 1.0 1 1

Seidelova metoda .

Metoda se može smatrati modifikacijom Jacobijeve metode. Glavna ideja je da pri izračunavanju sljedećeg (n+1)-to približavanje nepoznatom x ja na i>1 upotreba već pronađena (n+1)- približavanje nepoznatom x 1 ,x 2 , ...,x i - 1 , ne n th aproksimacije, kao u Jacobijevoj metodi.

Formula izračuna metode u koordinatnom zapisu izgleda ovako:

Uvjeti konvergencije i kriterij završetka za iteracije mogu se uzeti isto kao u Jacobijevoj metodi.

Primjer 2 Rješavanje sustava linearnih jednadžbi Seidelovom metodom.

Razmotrimo paralelno rješenje 3 sustava jednadžbi:

Sustave dovodimo u oblik pogodan za iteracije:

Primijetimo da uvjet konvergencije
izvodi samo za prvi sustav. U svakom slučaju izračunavamo 3 prve aproksimacije rješenja.

1. sustav:

Točno rješenje bit će vrijednosti: x 1 = 1.4, x 2 = 0.2 . Iterativni proces konvergira.

2. sustav:

Može se vidjeti da se iterativni proces razlikuje.

Točno rješenje x 1 = 1, x 2 = 0.2 .

3. sustav:

Može se vidjeti da je iterativni proces petljao.

Točno rješenje x 1 = 1, x 2 = 2 .

Neka je matrica sustava jednadžbi A simetrična i pozitivno određena. Zatim, za bilo koji izbor početne aproksimacije, Seidelova metoda konvergira. Ovdje se ne postavljaju dodatni uvjeti na malost norme neke matrice.

Metoda jednostavne iteracije.

Ako je A simetrična i pozitivno određena matrica, tada se sustav jednadžbi često svodi na ekvivalentan oblik:

x=x-τ(A x- b), τ je iterativni parametar.

Formula izračuna metode jednostavne iteracije u ovom slučaju je:

x (n+1) =x n- τ (A x (n) - b).

a parametar τ > 0 bira se tako da po mogućnosti minimalna vrijednost

Neka su λ min i λ max minimalna i maksimalna svojstvena vrijednost matrice A. Optimalni izbor je parametar

U ovom slučaju
prihvaća minimalna vrijednost jednak:

Primjer 3 Rješavanje sustava linearnih jednadžbi jednostavnom iteracijom. (u MathCAD-u)

Neka je sustav jednadžbi Ax = b

Za izgradnju iterativnog procesa pronaći svoje brojevi matrice A:

- koristi ugrađenu funkciju za pronalaženje svojstvenih vrijednosti.

Izračunajte iterativni parametar i provjerite uvjet konvergencije

Uvjet konvergencije je zadovoljen.

Uzmimo početnu aproksimaciju - vektor x0, postavimo točnost na 0,001 i pronađemo početne aproksimacije pomoću donjeg programa:

Točno rješenje

Komentar. Ako program vrati rez matrice, tada možete vidjeti sve pronađene iteracije.