Metoda iterațiilor simple slăbește viteza pașilor de lucru. Rezolvarea slough folosind metoda simplă de iterație

27.09.2019 | Finanţa

Subiectul 3. Rezolvarea sistemelor liniare ecuații algebrice metode iterative.

Metodele directe de rezolvare a SLAE-urilor descrise mai sus nu sunt foarte eficiente atunci când se rezolvă sisteme cu dimensiuni mari (adică atunci când valoarea n suficient de mare). În astfel de cazuri, metodele iterative sunt mai potrivite pentru rezolvarea SLAE-urilor.

Metode iterative pentru rezolvarea SLAE-urilor(al doilea nume al acestora este metode de aproximare succesivă a soluției) nu oferă o soluție exactă a SLAE, ci doar o aproximare a soluției, iar fiecare aproximare ulterioară se obține din cea anterioară și este mai precisă decât cea anterioară ( cu condiția ca convergenţă iterații). Aproximația inițială (sau așa-numita zero) este aleasă în apropierea soluției așteptate sau în mod arbitrar (vectorul părții drepte a sistemului poate fi luat ca acesta). Soluția exactă se găsește ca limită a unor astfel de aproximări, deoarece numărul lor tinde spre infinit. De regulă, această limită nu este atinsă într-un număr finit de pași (adică iterații). Prin urmare, în practică, conceptul este introdus acuratețea soluției, și anume, este dat un număr pozitiv și suficient de mic e iar procesul de calcule (iterații) se realizează până când relația este satisfăcută .

Iată aproximarea soluției obținute după numărul de iterație n , a este soluția exactă a SLAE (care este necunoscută în prealabil). Numărul de iterații n = n (e ) , necesare pentru a obține o acuratețe dată pentru anumite metode, pot fi obținute din considerente teoretice (adică, există formule de calcul pentru aceasta). Calitatea diferitelor metode iterative poate fi comparată cu numărul de iterații necesare pentru a obține aceeași acuratețe.

Pentru a studia metode iterative pe convergenţă trebuie să fii capabil să calculezi normele matricelor. Norma matricei- aceasta este o anumită valoare numerică care caracterizează dimensiunea elementelor matricei în valoare absolută. ÎN matematică superioară sunt mai multe diverse tipuri norme de matrice, care sunt de obicei echivalente. În cursul nostru vom folosi doar unul dintre ele. Anume sub norma matriceală vom înțelege valoarea maximă dintre sumele valorilor absolute ale elementelor rândurilor individuale ale matricei. Pentru a indica norma matricei, numele acesteia este inclus în două perechi de bare verticale. Deci, pentru matrice O prin norma sa intelegem cantitatea

. (3.1)

Deci, de exemplu, norma matricei A din Exemplul 1 se găsește după cum urmează:

Cele mai multe aplicare largă Pentru a rezolva SLAE am obținut trei metode iterative

Metodă simplă de iterație

metoda Jacobi

Metoda Guass-Seidel.

Metodă simplă de iterație implică o tranziție de la scrierea SLAE în forma sa originală (2.1) la scrierea în formă

(3.2)

sau, care este, de asemenea, același, sub formă de matrice,

x = CU × x + D , (3.3)

C - matricea coeficienților sistemului de dimensiuni transformate n ´ n

x - vector de necunoscute constând din n componentă

D - vector al părților drepte ale sistemului transformat, constând din n componentă.

Sistemul în forma (3.2) poate fi reprezentat într-o formă redusă

Pe baza acestui punct de vedere formulă simplă de iterație va arăta ca

Unde m - numărul iterației și - valoarea x j pe m -al-lea pas de iterație. Apoi, dacă procesul de iterație converge, odată cu creșterea numărului de iterații se va observa

S-a dovedit că procesul de iterație converge, Dacă normă matrici D voinţă mai putine unitatis.

Dacă luăm vectorul termenilor liberi ca aproximare inițială (zero), i.e. x (0) = D , Asta magnitudinea erorii arata ca

(3.5)

aici mai jos x * soluția exactă a sistemului este înțeleasă. Prin urmare,

Dacă , apoi conform precizie specificatăe poate fi calculată în avans numărul necesar de iterații. Și anume din relație

după mici transformări obținem

. (3.6)

Atunci când se efectuează un astfel de număr de iterații, precizia specificată a găsirii unei soluții pentru sistem este garantată. Această estimare teoretică a numărului necesar de pași de iterație este oarecum supraestimată. În practică, precizia necesară poate fi obținută în mai puține iterații.

Este convenabil să căutați soluții pentru un anumit SLAE utilizând o metodă simplă de iterație prin introducerea rezultatelor obținute într-un tabel de următoarea formă:

x 1	x 2	*x n*

Trebuie remarcat mai ales că în rezolvarea SLAE-urilor folosind această metodă cel mai complex și consumator de timp este de a transforma sistemul din forma (2.1) în forma (3.2). Aceste transformări trebuie să fie echivalente, adică. neschimbarea soluției sistemului original și asigurarea valorii normei matricei C (după completarea lor) unitate mai mică. Nu există o singură rețetă pentru a efectua astfel de transformări. Aici, în fiecare caz concret, este necesar să fii creativ. Să luăm în considerare exemple, care va oferi câteva modalități de a transforma sistemul în forma necesară.

Exemplul 1. Să găsim o soluție la un sistem de ecuații algebrice liniare folosind metoda simplă de iterație (cu precizie e= 0.001)

Acest sistem este adus la forma cerută în cel mai simplu mod. Să mutăm toți termenii din partea stângă la dreapta și apoi să adăugăm la ambele părți ale fiecărei ecuații x i (i =1, 2, 3, 4). Obținem un sistem transformat de următoarea formă

Matrice C și vector D în acest caz va fi după cum urmează

C = , D = .

Să calculăm norma matricei C . Primim

Deoarece norma s-a dovedit a fi mai mică decât unitatea, este asigurată convergența metodei iterației simple. Ca aproximare inițială (zero), luăm componentele vectorului D . Primim

, , , .

Folosind formula (3.6), calculăm numărul necesar de pași de iterație. Să determinăm mai întâi norma vectorului D . Primim

Prin urmare, pentru a obține precizia specificată, este necesar să efectuați cel puțin 17 iterații. Să facem prima iterație. Primim

După ce am efectuat toate operațiile aritmetice, obținem

Continuând în mod similar, vom efectua pași suplimentari de iterație. Rezumăm rezultatele lor în tabelul următor ( D- cea mai mare modificare a componentelor soluției între pașii actuali și anteriori)

M

Deoarece după al zecelea pas diferența dintre valorile la ultimele două iterații a devenit mai mică decât precizia specificată, vom opri procesul de iterație. Ca soluție găsită, vom lua valorile obținute la ultimul pas.

Exemplul 2.

Să procedăm mai întâi în mod similar cu exemplul anterior. Primim

Matrice C va exista un astfel de sistem

C =.

Să-i calculăm norma. Primim

Evident, procesul de iterație pentru o astfel de matrice nu va fi convergent. Este necesar să găsim o altă modalitate de a transforma sistemul dat de ecuații.

Să rearanjam ecuațiile sale individuale în sistemul original de ecuații, astfel încât a treia linie să devină prima, prima - a doua, a doua - a treia. Apoi, transformându-l în același mod, obținem

Matrice C va exista un astfel de sistem

C =.

Să-i calculăm norma. Primim

Deoarece norma matricei C s-a dovedit a fi mai mic decât unitatea, sistemul transformat în acest fel este potrivit pentru rezolvare prin metoda simplă a iterației.

Exemplul 3. Să transformăm sistemul de ecuații

la o formă care să permită utilizarea metodei simple de iterație în rezolvarea acesteia.

Să procedăm mai întâi în mod similar cu exemplul 1. Obținem

Matrice C va exista un astfel de sistem

C =.

Să-i calculăm norma. Primim

Evident, procesul de iterație pentru o astfel de matrice nu va fi convergent.

Pentru a transforma matricea originală într-o formă convenabilă pentru aplicarea metodei iterației simple, procedăm după cum urmează. În primul rând, formăm un sistem „intermediar” de ecuații în care

- prima ecuație este suma primei și a doua ecuații ale sistemului original

- a doua ecuație- suma de două ori a treia ecuație cu a doua minus prima

- a treia ecuație- diferența dintre a treia și a doua ecuație a sistemului original.

Ca rezultat, obținem un sistem „intermediar” de ecuații echivalent cu cel original

Din el este ușor să obțineți un alt sistem, un sistem „intermediar”.

iar din ea s-a transformat

Matrice C va exista un astfel de sistem

C =.

Să-i calculăm norma. Primim

Procesul de iterație pentru o astfel de matrice va fi convergent.

metoda Jacobi presupune că toate elementele diagonale ale matricei O ale sistemului original (2.2) nu sunt egale cu zero. Apoi sistemul original poate fi rescris ca

(3.7)

Dintr-o astfel de înregistrare se formează sistemul formula de iterație a metodei Jacobi

Condiția pentru convergența procesului iterativ al metodei Jacobi este așa-numita condiție dominanta diagonaleiîn sistemul original (tip (2,1)). Analitic, această condiție este scrisă în formă

. (3.9)

Trebuie remarcat faptul că, dacă într-un sistem dat de ecuații nu este îndeplinită condiția de convergență a metodei Jacobi (adică condiția de dominanță a diagonalei), în multe cazuri este posibil, prin intermediul transformărilor echivalente ale SLAE inițial. , pentru a-și reduce soluția la soluția unui SLAE echivalent în care această condiție este îndeplinită.

Exemplul 4. Să transformăm sistemul de ecuații

la o formă care să permită folosirea metodei Jacobi în rezolvarea acesteia.

Am considerat deja acest sistem în Exemplul 3, așa că să trecem de la el la sistemul „intermediar” de ecuații obținut acolo. Este ușor de stabilit că condiția sa de dominanță diagonală este satisfăcută, așa că să o transformăm în forma necesară aplicării metodei Jacobi. Primim

Din aceasta obținem o formulă pentru efectuarea calculelor folosind metoda Jacobi pentru un SLAE dat

Luând-o ca inițială, adică zero, vector de aproximare a termenilor liberi, vom efectua toate calculele necesare. Să rezumam rezultatele într-un tabel.

m					D

Precizia destul de mare a soluției obținute a fost obținută în șase iterații.

Metoda Gauss-Seidel este o îmbunătățire a metodei Jacobi și, de asemenea, presupune că toate elementele diagonale ale matricei O ale sistemului original (2.2) nu sunt egale cu zero. Apoi sistemul original poate fi rescris într-o formă similară cu metoda Jacobi, dar ușor diferită de aceasta

Este important de reținut aici că, dacă în semnul de însumare indicele superior este mai mic decât indicele inferior, atunci nu se efectuează o însumare.

Ideea metodei Gauss-Seidel este că autorii metodei au văzut oportunitatea de a accelera procesul de calcul în raport cu metoda Jacobi datorită faptului că în procesul următoarei iterații, după ce au găsit o nouă valoare x 1 Can imediat utilizați această nouă valoare în aceeași iterație pentru a calcula variabilele rămase. În mod similar, mai departe, după ce a găsit o nouă valoare x 2 de asemenea, îl puteți utiliza imediat în aceeași iterație etc.

Pe baza acestui fapt, formula de iterație pentru metoda Gauss-Seidel are următoarea formă

Suficientclauza de convergenta procesul de iterație al metodei Gauss-Seidel este aceeași condiție dominanta diagonalei (3.9). Viteza de convergență Această metodă este puțin mai mare decât în metoda Jacobi.

Exemplul 5. Să rezolvăm sistemul de ecuații folosind metoda Gauss-Seidel

Am considerat deja acest sistem în exemplele 3 și 4, așa că ne vom trece imediat de la acesta la sistemul transformat de ecuații (vezi exemplul 4), în care condiția pentru dominanța diagonalei este îndeplinită. Din aceasta obținem o formulă pentru efectuarea calculelor folosind metoda Gauss-Seidel

Luând vectorul termenilor liberi ca aproximare inițială (adică zero), efectuăm toate calculele necesare. Să rezumam rezultatele într-un tabel.

m

O precizie destul de mare a soluției rezultate a fost obținută în cinci iterații.

Avantajul metodelor iterative este aplicabilitatea lor la sisteme necondiționate și sisteme de ordin înalt, auto-corecția și ușurința de implementare pe un PC. Pentru a începe calculele, metodele iterative necesită specificarea unei aproximări inițiale a soluției dorite.

Trebuie remarcat faptul că condițiile și rata de convergență a procesului iterativ depind în mod semnificativ de proprietățile matricei O sistem și asupra alegerii aproximărilor inițiale.

Pentru a aplica metoda iterației, sistemul original (2.1) sau (2.2) trebuie redus la forma

după care procesul iterativ se realizează după formule recurente

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

Matrice Gși vector sunt obținute ca rezultat al transformării sistemului (2.1).

Pentru convergență (2.26 O) este necesar şi suficient pentru ca |l i(G)| < 1, где li(G) - Toate valori proprii matrici G. Convergența va avea loc și dacă || G|| < 1, так как |li(G)| < " ||G||, unde „este oricare.

Simbol || ... || înseamnă norma matricei. La determinarea valorii sale, se opresc cel mai adesea la verificarea a două condiții:

||G|| = sau || G|| = , (2.27)

Unde . Convergența este, de asemenea, garantată dacă matricea originală O are dominanță diagonală, adică

. (2.28)

Dacă (2.27) sau (2.28) este satisfăcută, metoda iterației converge pentru orice aproximare inițială. Cel mai adesea, vectorul este luat fie zero, fie unitate, sau vectorul însuși este luat din (2.26).

Există multe abordări pentru transformarea sistemului original (2.2) cu matricea O pentru a asigura forma (2.26) sau a satisface condițiile de convergență (2.27) și (2.28).

De exemplu, (2.26) poate fi obținută după cum urmează.

Lasă O = ÎN+ CU, det ÎN#0; Apoi ( B+ CU)= Þ B= −C+ Þ Þ B –1 B= −B –1 C+ B–1, de unde= − B –1 C+ B –1 .

Punerea - B –1 C = G, B–1 = , obținem (2.26).

Din condiţiile de convergenţă (2.27) şi (2.28) este clar că reprezentarea O = ÎN+ CU nu poate fi arbitrară.

Dacă matricea O satisface condițiile (2.28), apoi ca matrice ÎNîl puteți selecta pe cel triunghiular inferior:

, a ii ¹ 0.

; Þ ; Þ ; Þ

Alegând parametrul a, ne putem asigura că || G|| = ||E+ a O|| < 1.

Dacă (2.28) prevalează, atunci transformarea în (2.26) se poate face prin rezolvarea fiecărui i ecuația sistemului (2.1) în raport cu x i conform următoarelor formule recurente:

(2.28O)

Dacă în matrice O nu există o dominanță diagonală ea trebuie realizată folosind niște transformări liniare care să nu le încalce echivalența.

Ca exemplu, luați în considerare sistemul

(2.29)

După cum puteți vedea, în ecuațiile (1) și (2) nu există dominanță diagonală, dar în (3) există, așa că o lăsăm neschimbată.

Să obținem dominanța diagonală în ecuația (1). Înmulțim (1) cu a, (2) cu b, adunăm ambele ecuații și în ecuația rezultată alegem a și b astfel încât să existe o dominanță diagonală:

(2a + 3b) X 1 + (–1,8a + 2b) X 2 +(0,4a – 1,1b) X 3 = a.

Luând a = b = 5, obținem 25 X 1 + X 2 – 3,5X 3 = 5.

Pentru a transforma ecuația (2) cu predominanța (1) înmulțiți cu g, (2) înmulțiți cu d și scădeți (1) din (2). Primim

(3d – 2g) X 1 + (2d + 1,8 g) X 2 +(–1,1d – 0,4g) X 3 = −g.

Punând d = 2, g = 3, obținem 0 X 1 + 9,4 X 2 – 3,4 X 3 = −3. Ca rezultat, obținem sistemul

(2.30)

Această tehnică poate fi utilizată pentru a găsi soluții pentru o clasă largă de matrici.

Luând vector = (0,2; –0,32; 0) ca aproximare inițială T, vom rezolva acest sistem folosind tehnologia (2.26 O):

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

Procesul de calcul se oprește atunci când două aproximări învecinate ale vectorului soluție coincid în precizie, i.e.

Tehnologia soluției iterative a formei (2.26 O) numit metoda simplă de iterație .

Nota eroare absolută pentru metoda simplă de iterație:

unde este simbolul || ... || înseamnă normal.

Exemplul 2.1. Folosind o metodă simplă de iterație cu o precizie de e = 0,001, rezolvați sistemul ecuații liniare:

Numărul de pași care dau un răspuns precis la e = 0,001 poate fi determinat din relație

0,001 GBP.

Să estimăm convergența folosind formula (2.27). Aici || G|| = = max(0,56; 0,61; 0,35; 0,61) = 0,61< 1; = 2,15. Значит, сходимость обеспечена.

Ca o aproximare inițială, luăm vectorul termenilor liberi, adică = (2,15; –0,83; 1,16; 0,44) T. Să înlocuim valorile vectoriale în (2.26 O):

Continuând calculele, introducem rezultatele în tabel:

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

Convergența în miimi are loc deja la pasul 10.

Răspuns: X 1 » 3.571; X 2 "-0,957; X 3 » 1.489; X 4 "-0,836.

Această soluție poate fi obținută și folosind formulele (2.28 O).

Exemplul 2.2. Pentru a ilustra algoritmul folosind formule (2.28 O) luați în considerare soluția sistemului (doar două iterații):

; . (2.31)

Să transformăm sistemul în forma (2.26) conform (2.28 O):

Þ (2.32)

Să luăm aproximarea inițială = (0; 0; 0) T. Atunci pentru k= 0 este evident că valoarea = (0,5; 0,8; 1,5) T. Să înlocuim aceste valori în (2.32), adică când k= 1 obținem = (1,075; 1,3; 1,175) T.

Eroare e 2 = = max(0,575; 0,5; 0,325) = 0,575.

Diagrama bloc a algoritmului pentru găsirea unei soluții la SLAE folosind metoda iterații simple conform formulelor de lucru (2.28 O) este prezentată în fig. 2.4.

O caracteristică specială a diagramei bloc este prezența următoarelor blocuri:

– blocul 13 – scopul acestuia este discutat mai jos;

– blocul 21 – afișarea rezultatelor pe ecran;

– blocul 22 – verificarea (indicatorul) convergenței.

Să analizăm schema propusă folosind exemplul sistemului (2.31) ( n= 3, w = 1, e = 0,001):

= ; .

Bloc 1. Introduceți datele inițiale O, ,w,e, n: n= 3, w = 1, e = 0,001.

Ciclul I. Setați valorile inițiale ale vectorilor x 0iŞi x i (i = 1, 2, 3).

Bloc 5. Resetați contorul de iterații.

Bloc 6. Resetați contorul de erori curent la zero.

ÎN ciclul II, numerele rândurilor matricei sunt modificate Oși vector.

Ciclul II:i = 1: s = b 1 = 2 (blocul 8).

Mergeți la bucla imbricată III, blocul 9 – contorul numărului coloanei matriceale O: j = 1.

Bloc 10: j = i, prin urmare, revenim la blocul 9 și creștem j pe unitate: j = 2.

În blocul 10 j ¹ i(2 ¹ 1) – trecem la blocul 11.

Bloc 11: s= 2 – (–1) × X 0 2 = 2 – (–1) × 0 = 2, mergeți la blocul 9, în care j creste cu unu: j = 3.

În blocul 10 starea j ¹ i este îndeplinită, așa că să trecem la blocul 11.

Bloc 11: s= 2 – (–1) × X 0 3 = 2 – (–1) × 0 = 2, după care trecem la blocul 9, în care j creste cu unu ( j= 4). Sens j Mai mult n (n= 3) – terminăm ciclul și trecem la blocul 12.

Bloc 12: s = s / o 11 = 2 / 4 = 0,5.

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

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

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

Bloc 16. Verificarea stării d > de: 0,5 > 0, prin urmare, mergeți la blocul 17, în care atribuim de= 0,5 și reveniți folosind linkul „ O» la pasul următor al ciclului II – la blocul 7, în care i creste cu unu.

Ciclul II: i = 2: s = b 2 = 4 (blocul 8).

j = 1.

Prin blocul 10 j ¹ i(1 ¹ 2) – trecem la blocul 11.

Bloc 11: s= 4 – 1 × 0 = 4, mergeți la blocul 9, în care j creste cu unu: j = 2.

În blocul 10 condiția nu este îndeplinită, așa că trecem la blocul 9, în care j creste cu unu: j= 3. Prin analogie, trecem la blocul 11.

Bloc 11: s= 4 – (–2) × 0 = 4, după care terminăm ciclul III și trecem la blocul 12.

Bloc 12: s = s/ o 22 = 4 / 5 = 0,8.

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

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

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

Bloc 16. Verificarea stării d > de: 0,2 < 0,5; следовательно, возвращаемся по ссылке «O» la următoarea etapă a ciclului II - la blocul 7.

Ciclul II: i = 3: s = b 3 = 6 (blocul 8).

Mergeți la bucla imbricată III, blocul 9: j = 1.

Bloc 11: s= 6 – 1 × 0 = 6, mergeți la blocul 9: j = 2.

Folosind blocul 10, trecem la blocul 11.

Bloc 11: s= 6 – 1 × 0 = 6. Terminăm ciclul III și trecem la blocul 12.

Bloc 12: s = s/ o 33 = 6 / 4 = 1,5.

Bloc 13: s = 1,5.

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

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

Conform blocului 16 (inclusiv referințele „ O" Și " CU„) părăsim ciclul II și trecem la blocul 18.

Bloc 18. Creșterea numărului de iterații ea = ea + 1 = 0 + 1 = 1.

În blocurile 19 și 20 ale ciclului IV înlocuim valorile inițiale X 0i valorile obtinute x i (i = 1, 2, 3).

Bloc 21. Tipărim valori intermediare ale iterației curente, în acest caz: = (0,5; 0,8; 1,5) T, ea = 1; de = 0,5.

Trecem la ciclul II la blocul 7 și efectuăm calculele considerate cu noi valori inițiale X 0i (i = 1, 2, 3).

După care primim X 1 = 1,075; X 2 = 1,3; X 3 = 1,175.

Aici, deci, metoda lui Seidel converge.

Conform formulelor (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

Răspuns: x 1 = 0,248; x 2 = 1,115; x 3 = –0,224.

Comentariu. Dacă iterația simplă și metodele Seidel converg pentru același sistem, atunci metoda Seidel este de preferat. Cu toate acestea, în practică, zonele de convergență ale acestor metode pot fi diferite, adică metoda iterației simple converge, dar metoda Seidel diverge și invers. Pentru ambele metode, dacă || G|| aproape de unitate, viteza de convergență este foarte mică.

Pentru a accelera convergența, se folosește o tehnică artificială - așa-numita metoda de relaxare . Esența sa constă în faptul că următoarea valoare obținută prin metoda iterației x i (k) se recalculează folosind formula

unde w este de obicei modificat în intervalul de la 0 la 2 (0< w £ 2) с каким-либо шагом (h= 0,1 sau 0,2). Parametrul w este selectat astfel încât convergența metodei să fie realizată într-un număr minim de iterații.

Relaxare– o slăbire treptată a oricărei stări a organismului după încetarea factorilor care au determinat această stare (ingineria fizică).

Exemplul 2.4. Să luăm în considerare rezultatul celei de-a cincea iterații folosind formula de relaxare. Să luăm w = 1,5:

După cum puteți vedea, rezultatul aproape a celei de-a șaptea iterații a fost obținut.

Prelegere Metode iterative pentru rezolvarea unui sistem de ecuații liniare algebrice.

Condiția de convergență a procesului iterativ

Metodă simplă de iterație

Se consideră un sistem de ecuații algebrice liniare

Pentru a aplica metode iterative, sistemul trebuie redus la o formă echivalentă

Apoi se selectează o aproximare inițială a soluției sistemului de ecuații și se găsește o succesiune de aproximări la rădăcină.

Pentru ca procesul iterativ să convergă, este suficient ca condiția să fie îndeplinită
(norma matricei). Criteriul de încheiere a iterațiilor depinde de metoda iterativă utilizată.

metoda Jacobi .

Cel mai simplu mod de a aduce sistemul într-o formă convenabilă pentru iterare este după cum urmează:

Din prima ecuație a sistemului exprimăm necunoscutul x 1, din a doua ecuație a sistemului pe care o exprimăm x 2, etc.

Ca rezultat, obținem un sistem de ecuații cu matricea B, în care zero elemente sunt pe diagonala principală, iar elementele rămase sunt calculate folosind formulele:

Componentele vectorului d sunt calculate folosind formulele:

Formula de calcul pentru metoda iterației simple este:

sau în notație de coordonate arată astfel:

Criteriul pentru terminarea iterațiilor în metoda Jacobi are forma:

Dacă
, atunci putem aplica un criteriu mai simplu pentru terminarea iterațiilor

Exemplul 1. Rezolvarea unui sistem de ecuații liniare folosind metoda Jacobi.

Să fie dat sistemul de ecuații:

Este necesar să găsiți o soluție la sistem cu acuratețe

Să reducem sistemul la o formă convenabilă pentru iterare:

Să alegem o aproximare inițială, de exemplu,

- vector al părții drepte.

Apoi prima iterație arată astfel:

Următoarele aproximări ale soluției se obțin în mod similar.

Să găsim norma matricei B.

Vom folosi norma

Deoarece suma modulelor elementelor din fiecare rând este 0,2, atunci
, deci criteriul pentru terminarea iterațiilor în această problemă este

Să calculăm normele diferențelor vectoriale:

Deoarece
precizia specificată a fost atinsă la a patra iterație.

Răspuns: x 1 = 1.102, x 2 = 0.991, x 3 = 1.0 1 1

metoda Seidel .

Metoda poate fi considerată ca o modificare a metodei Jacobi. Ideea principală este că atunci când se calculează următorul (n+1)-a abordare a necunoscutului x i la eu >1 utilizare deja găsită (n+1)- e apropiindu-se de necunoscut x 1 ,x 2 , ...,x i - 1 și nu n aproximarea, ca în metoda Jacobi.

Formula de calcul a metodei în notație de coordonate arată astfel:

Condițiile de convergență și criteriul pentru terminarea iterațiilor pot fi luate la fel ca în metoda Jacobi.

Exemplul 2. Rezolvarea sistemelor de ecuații liniare folosind metoda Seidel.

Să considerăm în paralel soluția a 3 sisteme de ecuații:

Să reducem sistemele la o formă convenabilă pentru iterații:

Rețineți că condiția de convergență
făcut numai pentru primul sistem. Să calculăm 3 primele aproximări ale soluției în fiecare caz.

primul sistem:

Soluția exactă va fi următoarele valori: x 1 = 1.4, x 2 = 0.2 . Procesul iterativ converge.

al 2-lea sistem:

Se poate observa că procesul de iterație diverge.

Solutie exacta x 1 = 1, x 2 = 0.2 .

al 3-lea sistem:

Se poate observa că procesul iterativ a decurs în cicluri.

Solutie exacta x 1 = 1, x 2 = 2 .

Fie matricea sistemului de ecuații A simetrică și definită pozitiv. Apoi, pentru orice alegere de aproximare inițială, metoda Seidel converge. Nu sunt impuse condiții suplimentare cu privire la micimea normei unei anumite matrice.

Metodă simplă de iterație.

Dacă A este o matrice definită simetrică și pozitivă, atunci sistemul de ecuații este adesea redus la forma echivalentă:

x=x-τ (A x- b), τ – parametru de iterație.

Formula de calcul a metodei de iterație simplă în acest caz are forma:

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

iar parametrul τ > 0 este ales astfel încât să minimizeze, dacă este posibil, valoarea

Fie λ min și λ max valorile proprii minime și maxime ale matricei A. Alegerea optimă a parametrului este

În acest caz
ia o valoare minimă egală cu:

Exemplul 3. Rezolvarea sistemelor de ecuații liniare folosind metoda iterației simple. (în MathCAD)

Să fie dat sistemul de ecuații Ax = b

Pentru a construi procesul iterativ, găsim valori proprii matricele A:

- folosește o funcție încorporată pentru a găsi valori proprii.

Să calculăm parametrul de iterație și să verificăm condiția de convergență

Condiția de convergență este îndeplinită.

Să luăm aproximarea inițială - vector x0, să setăm precizia la 0,001 și să găsim aproximațiile inițiale folosind programul de mai jos:

Solutie exacta

Comentariu. Dacă programul returnează matricea rez, atunci puteți vizualiza toate iterațiile găsite.

Metoda simplă a iterației, numită și metoda aproximării succesive, este un algoritm matematic pentru găsirea valorii unei mărimi necunoscute prin rafinarea ei treptat. Esența acestei metode este că, după cum sugerează și numele, exprimând treptat pe cele ulterioare de la aproximarea inițială, se obțin rezultate din ce în ce mai rafinate. Această metodă este folosită pentru a găsi valoarea unei variabile în funcţie dată, precum și la rezolvarea sistemelor de ecuații, atât liniare, cât și neliniare.

Să luăm în considerare modul în care această metodă este implementată atunci când rezolvăm SLAE-uri. Metoda simplă de iterație are următorul algoritm:

1. Verificarea îndeplinirii condiției de convergență în matricea originală. Teorema de convergență: dacă matricea originală a sistemului are dominanță diagonală (adică, în fiecare rând, elementele diagonalei principale trebuie să fie mai mari în valoare absolută decât suma elementelor diagonalelor secundare în valoare absolută), atunci metoda iterației este convergentă.

2. Matricea sistemului original nu are întotdeauna o predominanță diagonală. În astfel de cazuri, sistemul poate fi convertit. Ecuațiile care satisfac condiția de convergență sunt lăsate neatinse, iar combinații liniare se fac cu cele care nu, adică. înmulțiți, scădeți, adăugați ecuații între ele până când se obține rezultatul dorit.

Dacă în sistemul rezultat există coeficienți incomozi pe diagonala principală, atunci termenii formei cu i * x i se adaugă la ambele părți ale unei astfel de ecuații, ale căror semne trebuie să coincidă cu semnele elementelor diagonale.

3. Transformarea sistemului rezultat în formă normală:

x - =β - +α*x -

Acest lucru se poate face în multe moduri, de exemplu, astfel: din prima ecuație, exprimă x 1 în termeni de alte necunoscute, din a doua - x 2, din a treia - x 3 etc. În acest caz folosim formulele:

α ij = -(a ij / a ii)

i = b i /a ii
Ar trebui să vă asigurați din nou că sistemul rezultat aspect normal corespunde condiției de convergență:

∑ (j=1) |α ij |≤ 1, în timp ce i= 1,2,...n

4. Începem să aplicăm, de fapt, metoda însăși a aproximărilor succesive.

x (0) este aproximarea inițială, vom exprima x (1) prin ea, apoi vom exprima x (2) prin x (1). Formula generalași sub formă de matrice arată astfel:

x (n) = β - +α*x (n-1)

Calculăm până când obținem precizia necesară:

max |x i (k)-x i (k+1) ≤ ε

Deci, să punem în practică metoda simplă de iterație. Exemplu:
Rezolvați SLAE:

4,5x1-1,7x2+3,5x3=2
3,1x1+2,3x2-1,1x3=1
1,8x1+2,5x2+4,7x3=4 cu precizie ε=10 -3

Să vedem dacă elementele diagonale predomină în modul.

Vedem că doar a treia ecuație satisface condiția de convergență. Să transformăm primul și al doilea și să adăugăm al doilea la prima ecuație:

7,6x1+0,6x2+2,4x3=3

Din al treilea îl scadem pe primul:

2,7x1+4,2x2+1,2x3=2

Am convertit sistemul original într-unul echivalent:

7,6x1+0,6x2+2,4x3=3
-2,7x1+4,2x2+1,2x3=2
1,8x1+2,5x2+4,7x3=4

Acum să aducem sistemul la forma sa normală:

x1=0,3947-0,0789x2-0,3158x3
x2=0,4762+0,6429x1-0,2857x3
x3= 0,8511-0,383x1-0,5319x2

Verificăm convergența procesului iterativ:

0.0789+0.3158=0,3947 ≤ 1
0.6429+0.2857=0.9286 ≤ 1
0,383+ 0,5319= 0,9149 ≤ 1, i.e. condiția este îndeplinită.

0,3947
Estimarea inițială x(0) = 0,4762
0,8511

Înlocuind aceste valori în ecuația de formă normală, obținem următoarele valori:

0,08835
x(1) = 0,486793
0,446639

Înlocuind noi valori, obținem:

0,215243
x(2) = 0,405396
0,558336

Continuăm calculele până când ne apropiem de valori care satisfac condiția dată.

x (7) = 0,441091

Să verificăm corectitudinea rezultatelor obținute:

4,5*0,1880 -1.7*0,441+3.5*0,544=2,0003
3,1*0,1880+2,3*0,441-1,1x*0,544=0,9987
1.8*0,1880+2.5*0,441+4.7*0,544=3,9977

Rezultatele obținute prin înlocuirea valorilor găsite în ecuațiile originale satisfac pe deplin condițiile ecuației.

După cum putem vedea, metoda simplă de iterație oferă rezultate destul de precise, dar pentru a rezolva această ecuație a trebuit să petrecem mult timp și să facem calcule greoaie.