Metodă simplă de iterație pentru rezolvarea sistemelor de ecuații liniare (lent). Rezolvarea numerică a sistemelor de ecuații algebrice liniare

Avantajul metodelor iterative este aplicabilitatea lor la sisteme necondiționate și sisteme de ordin înalt, autocorecția și ușurința de implementare pe un PC. Metodele iterative pentru a începe calculul necesită o aproximare inițială a soluției dorite.

Trebuie remarcat faptul că condițiile și rata de convergență a procesului iterativ depind în esență de proprietățile matricei A 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ă formulele recurente

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

Matrice G iar vectorul se obțin ca rezultat al transformării sistemului (2.1).

Pentru convergență (2.26 A) este necesar şi suficient pentru |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ă A are o predominanță 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 considerat fie zero, fie unitate, sau vectorul în sine este luat din (2.26).

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

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

Lăsa A = Î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 .

Punând - B –1 C = G, B–1 = , obținem (2.26).

Din condițiile de convergență (2.27) și (2.28) se vede că reprezentarea A = ÎN+ CU nu poate fi arbitrară.

Dacă matricea A satisface condițiile (2.28), apoi ca matrice ÎN puteți alege triunghiul inferior:

, a ii ¹ 0.

; Þ ; Þ ; Þ

Alegând parametrul a, ne putem asigura că || G|| = ||E+a A|| < 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 recursive:

(2.28A)

Dacă în matrice A nu exista predominanta diagonala, ea trebuie realizata cu ajutorul unor transformari liniare care sa nu le incalce echivalenta.

Ca exemplu, luați în considerare sistemul

(2.29)

După cum se poate observa, î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țiți (1) cu a, (2) cu b, adăugați ambele ecuații și alegeți a și b în ecuația rezultată, 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 dominanță (1), înmulțim cu g, (2) înmulțim cu d și scădem (1) din (2). obține

(3d - 2g) X 1+(2d+1,8g) 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. Drept urmare, obținem sistemul

(2.30)

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

sau

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

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 de forma (2.26 A) se numeste prin simpla iterare .

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

unde simbolul || ... || înseamnă norma.

Exemplul 2.1. Folosind metoda iterației simple cu o precizie de e = 0,001, rezolvați sistemul ecuatii lineare:

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

0,001 GBP.

Să estimăm convergența prin 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. Înlocuim valorile vectorului în (2.26 A):

Continuând calculele, vom introduce 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 A).

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

; . (2.31)

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

Þ (2.32)

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

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

Schema bloc a algoritmului de găsire a soluției SLAE prin metoda iterații simple conform formulelor de lucru (2.28 A) este prezentată în fig. 2.4.

O caracteristică 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ă pe exemplul sistemului (2.31) ( n= 3, w = 1, e = 0,001):

= ; .

bloc 1. Introduceți datele inițiale A, , noi, 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 numărului de iterații.

bloc 6. Resetați contorul de erori curent.

ÎN bucla II modifică numerele de rând ale matricei Ași vector .

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

Mergeți la bucla imbricată III, bloc9 - contorul numerelor coloanelor matricei A: 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) - mergeți la blocul 11.

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

În blocul 10, starea j ¹ i executat, deci mergeți la blocul 11.

bloc 11: s= 2 – (–1) × X 0 3 \u003d 2 - (-1) × 0 \u003d 2, după care trecem la blocul 9, în care j creste cu unu ( j= 4). Sens j Mai mult n (n= 3) – terminați bucla și mergeți la blocul 12.

bloc 12: s = s / A 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. Verificați starea d > de: 0,5 > 0, prin urmare, mergeți la blocul 17, în care atribuim de= 0,5 și returnează prin referință " A» la pasul următor al ciclului II - la blocul7, î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) - mergeți 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ă mergem 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/ A 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. Verificați starea d > de: 0,2 < 0,5; следовательно, возвращаемся по ссылке «A» la pasul următor al ciclului II – la bloc7.

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

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

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

Prin blocul 10, trecem la blocul 11.

bloc 11: s= 6 – 1 × 0 = 6. Terminați ciclul III și treceți la blocul 12.

bloc 12: s = s/ A 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 (ținând cont de referințele „ A" Și " CU”) ieșiți din ciclul II și mergeți la blocul 18.

bloc 18. Măriți numărul de iterații aceasta = aceasta + 1 = 0 + 1 = 1.

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

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

Treceți la ciclul II pe blocul 7 și efectuați 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 Seidel converge.

Prin formule (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.

cometariu. Dacă pentru același sistem iterația simplă și metodele Seidel converg, 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, în timp ce metoda Seidel diverge și invers. Pentru ambele metode, dacă || G|| aproape de unitate, rata de convergență este foarte scăzută.

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ă după formula

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

Relaxare- slăbirea treptată a oricărei stări a organismului după încetarea factorilor care au determinat această stare (fizică. tehn.).

Exemplul 2.4. Luați î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.

În această secțiune, luăm în considerare un proces de iterație staționară atunci când matricea și parametrul de iterație nu depind de indice , și demonstrați următoarea teoremă în condiții suficiente pentru convergența ei.

teorema lui Samarsky

Lăsa este o matrice definită pozitivă auto-adjunctă:

,
,

este o matrice definită pozitivă, - număr pozitiv:

,
.

Apoi, pentru orice alegere de aproximare zero un proces iterativ care este definit de formula recursivă , converge către soluția sistemului original.

Înainte de a trece la demonstrarea teoremei, să discutăm mai detaliat principala sa cerință, definiția pozitivă a matricei.
. Această cerință poate fi rescrisă astfel:

,
,
.

adică, în special, se presupune că matricea este definit pozitiv. În plus, inegalitatea determină intervalul în care parametrul se poate modifica :

.

După aceste observații, trecem la demonstrarea teoremei. Să exprimăm din raport prin :

și înlocuiți în formula recurentă secvența iterativă. Ca rezultat, obținem:

.

Diferența dintre formula iterativă și este că este omogenă.

Matrice este pozitiv definit. Prin urmare, este nedegenerat și are invers
. Cu ajutorul ei relație de recurență poate fi rezolvată cu privire la
:

, Asa de
.

Înmulțirea ambelor părți ale egalității din stânga cu matricea , obținem încă o relație de recurență

.

Luați în considerare succesiunea funcționalelor pozitive:

.

Să compunem o expresie similară pentru
și transformați-l folosind formule recurente și:

Din autoajungerea matricei iar formulele urmează

Ca rezultat, formula ia forma:

Astfel, succesiunea funcționalelor sub rezerva conditiei
formează o succesiune monoton necrescătoare mărginită de jos de zero

.

,

Unde
este o constantă strict pozitivă. Ca urmare, conform și vom avea

Din această inegalitate și convergența șirului de funcționale urmează că
la
. La randul lui
, Asa de

Teorema a fost demonstrată.

1. Metodă simplă de iterație.

Acest nume a fost dat metodei în care, ca matrice se alege matricea de identitate:
, și parametrul iterativ presupus a fi independent de numărul de iterație . Cu alte cuvinte, metoda iterației simple este o metodă staționară explicită la următoarea iterație
se calculează prin formula recursivă

Vom presupune că matricea satisface condiția teoremei lui Samarskii,
, apoi formula care determină limita intervalului de convergență față de parametrul iterativ , ia forma

.

Lăsa
- baza ortonormală a vectorilor proprii ai operatorului corespunzător matricei . Prin definiție pozitivă, toate valorile sale proprii sunt pozitive. Să le considerăm numerotate în ordine descrescătoare:

Să descompunăm vectorul
conform bazei vectorilor proprii

Ca rezultat, din formulă rezultă că metoda iterației simple converge pentru oricare aparţinând intervalului

.

Vom construi un studiu suplimentar al metodei iterației simple pe o analiză specifică a formulei recursive. Să introducem matricea operatorului de tranziție

,

și rescrieți formula ca

.

În același timp, eroarea
va satisface o relație de recurență similară, doar omogenă

.

Să demonstrăm două leme care ne permit să investigăm mai în detaliu condițiile de convergență a metodei iterației simple.

Lema 1

Fie operatorul care generează matricea , are un vector propriu cu valoare proprie , apoi operatorul de tranziție generat de matrice , are și un vector propriu , dar cu valoare proprie

.

Dovada este elementară. Se realizează prin verificare directă

Pentru o matrice autoadjunctă matrice este, de asemenea, autoadjunct. Prin urmare, norma sa este determinată de cea mai mare valoare proprie în valoare absolută
:

.

Lema 2

Pentru ca metoda simplă de iterație să convergă către soluția sistemului pentru orice alegere de aproximare inițială, este necesar și suficient ca toate valorile proprii ale operatorului de tranziție au fost modulo mai puțin de unu:

,

Adecvarea. Condiția înseamnă că norma matricei , conform, va fi mai mică decât unitate:
. Drept urmare, obținem

La
.

Necesitate. Să presupunem că printre valorile proprii a gasit cel putin unul , care nu satisface condiția lemei, adică

.

Să alegem termenul zero al secvenței iterative în formă
, Unde soluția sistemului, atunci termenul zero al secvenței de eroare va coincide cu vectorul propriu operator de sărituri :
. Ca rezultat, formula recurentă pentru următorii membri ai secvenței de erori va lua forma:

,
.

adică
. Necesitatea îndeplinirii inegalității pentru toate valorile proprii pentru că se dovedeşte convergenţa metodei iteraţiei simple.

Lema 2 definește programul pentru investigarea ulterioară a convergenței metodei de iterație simplă: este necesar să se stabilească intervalul de variație a parametrilor sub care toate valorile proprii satisfac inegalitatea. Este ușor de făcut. Pe fig. 1 prezintă grafice ale funcțiilor liniare descrescătoare
. Toate vin din același punct
,
și coboară din cauza coeficienților negativi la , și funcția cu cea mai rapidă scădere
. Când capătă sens
, condiția ca aceasta încetează să mai fie îndeplinită:

, la
.

Valoare găsită este limita intervalului de convergență al metodei iterației simple

.

Cunoaștem deja această inegalitate. A fost obținută mai devreme din teorema lui Samarskii ca o condiție suficientă pentru convergență. O analiză suplimentară bazată pe Lema 2 ne permite să rafinăm rezultatul. Acum am stabilit că apartenența parametrului de iterație intervalul este o condiție necesară și suficientă pentru convergența metodei iterației simple.

Să ne întoarcem la studiul ratei de convergență a metodei. O estimare a erorii arată că aceasta scade conform legii unei progresii geometrice cu numitor

.

Luați în considerare fig. 2, care ne va ajuta să analizăm această formulă. Este similar cu Fig. 1, doar că arată grafice ale non-funcțiilor
, și modulele acestora. La mic toate valorile proprii
sunt pozitive, iar cea mai mare dintre ele este
, care scade odata cu cresterea la cea mai mică viteză. Cu toate acestea, trecând prin punct
valoare proprie
, schimbând semnul, devine negativ. Ca rezultat, acum modulul său cu o creștere nu scade, ci crește
apropiindu-se de valoarea limită a unităţii.

Găsiți pe segment
punct , în care funcția descrescătoare
comparativ cu o funcţie crescătoare
. Este determinat de ecuație

care dă

.

Ca rezultat, obținem:

Cea mai mică valoare a sa este norma matriceală ajunge la
:

.

Formula arată că pentru o matrice necondiționată, chiar și cu alegerea optimă a parametrului de iterație
norma matriceală este aproape de unitate, astfel încât convergența metodei iterației simple se dovedește a fi lentă în acest caz.

În concluzie, observăm că formula care determină limita intervalului de convergență , și formula pentru valoarea optimă a parametrului iterativ prezintă interes în primul rând teoretic. De obicei, la rezolvarea SLAE, cele mai mari și mai mici numere caracteristice ale matricei sunt necunoscute, deci calculați cantitățile Și nu este posibil în avans. Ca rezultat, parametrul iterativ adesea este necesar să se selecteze direct în procesul de calcule prin încercare și eroare.

Sarcina 2.

Să considerăm un sistem de două ecuații cu două necunoscute

și construiți o soluție aproximativă pentru aceasta folosind metoda iterației simple.

Să scriem imediat soluția sistemului

,
,

pentru a-l putea apoi compara cu membrii secvenței iterative.

Să ne întoarcem la soluția sistemului prin metoda iterației simple. Matricea sistemului are forma

.

Este auto-adjunct și pozitiv definit, deoarece

Să compunem ecuația caracteristică pentru matrice și găsiți-i rădăcinile:

,

,

Ele pot fi utilizate pentru a determina limita intervalului de convergență Și valoare optimă parametru de iterație :

,
.

Pentru a construi o secvență iterativă, alegem o anumită valoare a parametrului iterativ pe intervalul de convergență, de exemplu,
. În acest caz, formula recurentă pentru termenii secvenței iterative ia forma:

, Unde

Luați cea mai simplă aproximare inițială
și scrieți primii termeni ai secvenței iterative , calculând pentru fiecare dintre ele discrepanța
. Ca rezultat, obținem:

,
,
,

,
,
,

,
,
,

,
,
.

Norma reziduurilor, deși lent, dar scade, ceea ce indică convergența procesului. Același lucru se poate observa din compararea termenilor secvenței iterative cu rezolvarea sistemului. Convergența lentă se datorează condiționalității slabe a matricei :

.

Metoda iterațiilor simple se bazează pe înlocuirea ecuației inițiale cu o ecuație echivalentă:

Fie cunoscută aproximarea inițială a rădăcinii x = x 0. Inlocuindu-l in partea dreapta ecuația (2.7), obținem o nouă aproximare , apoi într-un mod similar obținem etc.:

. (2.8)

Nu în toate condițiile, procesul iterativ converge către rădăcina ecuației X. Să luăm în considerare acest proces mai detaliat. Figura 2.6 prezintă o interpretare grafică a unui proces unidirecțional convergent și divergent. Figura 2.7 prezintă procese convergente și divergente în două sensuri. Un proces divergent se caracterizează printr-o creștere rapidă a valorilor argumentului și funcției și blocarea programului corespunzător.

Cu un proces în două sensuri, este posibilă o buclă, adică o repetiție nesfârșită a acelorași valori ale funcției și argumentului. Buclele separă un proces divergent de unul convergent.

Din grafice se poate observa că atât în ​​procesele unilaterale, cât și în cele cu două fețe, convergența către rădăcină este determinată de panta curbei de lângă rădăcină. Cu cât panta este mai mică, cu atât convergența este mai bună. După cum știți, tangenta pantei curbei este egală cu derivata curbei într-un punct dat.

Prin urmare, cu cât este mai puțin aproape de rădăcină, cu atât procesul converge mai repede.

Pentru ca procesul iterativ să fie convergent, trebuie să fie satisfăcută următoarea inegalitate în vecinătatea rădăcinii:

Se poate face trecerea de la ecuația (2.1) la ecuația (2.7). căi diferite in functie de tipul functiei f(x).Într-o astfel de tranziție, este necesar să se construiască o funcție în așa fel încât condiția de convergență (2.9) să fie îndeplinită.

Luați în considerare unul dintre algoritmii generali pentru trecerea de la ecuația (2.1) la ecuația (2.7).

Înmulțim părțile stânga și dreaptă ale ecuației (2.1) cu o constantă arbitrară bși adaugă la ambele părți necunoscutul X.În acest caz, rădăcinile ecuației originale nu se vor schimba:

Introducem notația și treceți de la relația (2.10) la ecuația (2.8).

Alegerea arbitrară a constantei b va asigura îndeplinirea condiţiei de convergenţă (2.9). Condiția (2.2) va fi criteriul de terminare pentru procesul iterativ. Figura 2.8 prezintă o interpretare grafică a metodei iterațiilor simple cu metoda de reprezentare descrisă (scalele de-a lungul axelor X și Y sunt diferite).

Dacă funcția este aleasă sub forma , atunci derivata acestei funcții va fi . Cea mai mare rată de convergență va fi atunci la iar formula iterativă (2.11) trece în formula lui Newton. Astfel, metoda lui Newton are cel mai înalt grad de convergență dintre toate procesele iterative.

Implementarea software a metodei iterațiilor simple se face sub forma unei proceduri de subrutină Iteras(PROGRAMUL 2.1).

Întreaga procedură constă practic dintr-o singură buclă Repeat ... Until, care implementează formula (2.11) ținând cont de condiția de încheiere a procesului iterativ (formula (2.2)).

Protecția buclei este integrată în procedură prin numărarea numărului de bucle folosind variabila Niter. În exercițiile practice, trebuie să vă asigurați, prin rularea programului, cum afectează alegerea coeficientului bși aproximarea inițială asupra procesului de găsire a rădăcinii. La modificarea coeficientului b natura procesului iterativ pentru funcția studiată se modifică. Mai întâi devine cu două fețe, apoi bucle (Fig. 2.9). Scala de-a lungul axelor XȘi Y diferit. Un modul b și mai mare duce la un proces divergent.

Compararea metodelor de rezolvare aproximativă a ecuațiilor

Compararea metodelor de rezolvare numerică a ecuațiilor descrise mai sus a fost efectuată folosind un program care vă permite să observați procesul de găsire a rădăcinii într-o formă grafică pe ecranul computerului. Procedurile incluse în acest program și implementarea metodelor comparate sunt prezentate mai jos (PROGRAMUL 2.1).

Orez. 2.3-2.5, 2.8, 2.9 sunt copii ale ecranului PC-ului la sfârșitul procesului iterativ.

În toate cazurile, am luat drept funcție studiată ecuație pătratică x 2 -x-6 = 0, având solutie analitica x 1 = -2 și x 2 = 3. Eroarea și aproximările inițiale au fost luate egale pentru toate metodele. Rezultatele căutării rădăcină x= 3 prezentate în figuri sunt după cum urmează. Metoda dihotomiei converge cel mai lent - 22 de iterații, cel mai rapid - metoda iterațiilor simple la b = -0,2 - 5 iterații. Nu există nicio contradicție aici cu afirmația că metoda lui Newton este cea mai rapidă.

Derivată a funcției studiate la un punct X= 3 este egal cu -0,2, adică calculul în acest caz a fost efectuat practic prin metoda Newton cu valoarea derivatei în punctul rădăcinii ecuației. La modificarea coeficientului b rata de convergență scade și procesul de convergență treptat are mai întâi cicluri, apoi devine divergent.

Metoda iterației simple, 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ă, acestea 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 în 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. Metoda simplă de iterație are următorul algoritm:

1. Verificarea 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 modul decât suma elementelor diagonalelor laterale în modulo), atunci metoda simplă iterațiile este convergentă.

2. Matricea sistemului original nu are întotdeauna dominanță diagonală. În astfel de cazuri, sistemul poate fi modificat. Ecuațiile care satisfac condiția de convergență sunt lăsate neatinse, iar cu cele care nu, formează combinații liniare, 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 la ambele părți ale unei astfel de ecuații se adaugă termeni de forma c i *x i, ale căror semne trebuie să coincidă cu semnele elementelor diagonale.

3. Transformarea sistemului rezultat în forma normală:

x - =β - +α*x -

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

α ij = -(a ij / a ii)

i = b i /a ii
Ar trebui să vă asigurați din nou că sistemul rezultat vedere 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) - aproximare initiala, exprimam prin ea x (1) , apoi prin x (1) exprimam x (2) . Formula generalași sub formă de matrice arată astfel:

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

Calculăm până ajungem la precizia necesară:

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

Deci, să ne uităm la metoda simplă de iterație în practică. 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ă modulo.

Vedem că doar a treia ecuație satisface condiția de convergență. Transformăm prima și a doua ecuație, adăugăm a doua la prima ecuație:

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

Scădeți primul din al treilea:

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ă readucem sistemul la 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, adică 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ă ne apropiem de valorile 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, totuși, pentru a rezolva această ecuație, a trebuit să petrecem mult timp și să facem calcule greoaie.

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

Condiția de convergență a procesului iterativ.Metoda Jacobi.Metoda Seidel

Metodă simplă de iterație

Un sistem liniar ecuații algebrice

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

Apoi, se alege aproximarea 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
(norma matricei). Criteriul de terminare pentru iterații depinde de metoda iterativă aplicată.

metoda Jacobi .

Cea mai simplă modalitate de a aduce sistemul într-o formă convenabilă pentru iterare este următoarea:

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 prin formulele:

Componentele vectorului d se calculează prin formulele:

Formula de calcul a metodei iterației simple este:

sau în notația 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 prin metoda Jacobi.

Să fie dat sistemul de ecuații:

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

Aducem sistemul într-o formă convenabilă pentru iterare:

Alegem o aproximare inițială, de exemplu,

este vectorul părții drepte.

Apoi prima iterație arată astfel:

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

Aflați 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 vectorilor:

Deoarece
precizia specificată este 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 aproximare a necunoscutului X i la i>1 utilizare deja găsită (n+1)- apropiindu-se de necunoscut X 1 ,X 2 , ...,X i - 1 , nu n aproximarea, ca în metoda Jacobi.

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

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

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

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

Aducem sistemele într-o formă convenabilă pentru iterații:

Rețineți că condiția de convergență
efectuat numai pentru primul sistem. Calculăm 3 prime aproximări ale soluției în fiecare caz.

primul sistem:

Soluția exactă vor fi valorile: X 1 = 1.4, X 2 = 0.2 . Procesul iterativ converge.

al 2-lea sistem:

Se poate observa că procesul iterativ diverge.

Soluție exactă X 1 = 1, X 2 = 0.2 .

al 3-lea sistem:

Se poate observa că procesul iterativ a făcut buclă.

Soluție exactă X 1 = 1, X 2 = 2 .

Fie matricea sistemului de ecuații A simetrică și definită pozitiv. Apoi, pentru orice alegere a aproximării inițiale, metoda Seidel converge. Condiții suplimentare privind micimea normei unor matrice nu sunt impuse aici.

Metodă simplă de iterație.

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

X=X-τ(A X- b), τ este un parametru iterativ.

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

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

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

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

În acest caz
ia valoarea minimă egală cu:

Exemplul 3 Rezolvarea sistemelor de ecuații liniare prin iterație simplă. (în MathCAD)

Fie sistemul de ecuații Ax = b

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

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

Calculați parametrul iterativ și verificați condiția de convergență

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

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

Soluție exactă

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