De aici rezultă că α ≈ | φ ′ (ξ) | (\displaystyle \alpha \aprox |\varphi "(\xi)|). Astfel, pentru ca metoda să converge, este suficient ca ∀ x ∈ [ a , b ] | φ ′ (x) | ≤ 1. (\displaystyle \forall x\in \quad |\varphi "(x)|\leq 1.)

Algoritm general al aproximărilor succesive[ | ]

Așa cum se aplică în cazul general al ecuațiilor operatorului, această metodă este numită metoda aproximărilor succesive sau metoda simplă de iterație. Cu toate acestea, ecuația poate fi transformată în maparea contracției, care are aceeași rădăcină, în moduri diferite. Acest lucru dă naștere unui număr de metode particulare care au rate de convergență atât liniare, cât și mai mari.

Așa cum se aplică SLAU[ | ]

Luați în considerare sistemul:

( a 11 x 1 + … + a 1 n x n = b 1 … a n 1 x 1 + … + a n n x n = b n (\displaystyle \left\((\begin(array)(ccc)a_(11)x_(1)+ \ldots +a_(1n)x_(n)&=&b_(1)\\\ldots &&\\a_(n1)x_(1)+\ldots +a_(nn)x_(n)&=&b_(n) \end(matrice))\dreapta.)

Pentru aceasta, calculul iterativ va arăta astfel:

(x 1 x 2 ⋮ x n) i + 1 = (a 11 + 1 a 12 … a 1 n a 21 a 22 + 1 … a 2 n ⋮ ⋮ ⋱ ⋮ a n 1 a n 2 … a n n + 1) (x 1 x 2) ) ⋮ x n) i - (b 1 b 2 ⋮ b n) (\displaystyle \left((\begin(array)(c)x_(1)\\x_(2)\\\vdots \\x_(n)\ final (matrice))\right)^(i+1)=\left((\begin(array)(cccc)a_(11)+1&a_(12)&\ldots &a_(1n)\\a_(21)&a_ ( 22)+1&\ldots &a_(2n)\\\vdots &\vdots &\ddots &\vdots \\a_(n1)&a_(n2)&\ldots &a_(nn)+1\end(array))\ dreapta )\left((\begin(array)(c)x_(1)\\x_(2)\\\vdots \\x_(n)\end(array))\right)^(i)-\left ((\begin(array)(c)b_(1)\\b_(2)\\\vdots \\b_(n)\end(array))\right))

Metoda va converge la o rată liniară dacă ‖ a 11 + 1 … a 1 n ⋮ ⋱ ⋮ a n 1 … a n n + 1 ‖< 1 {\displaystyle \left\|{\begin{array}{ccc}a_{11}+1&\ldots &a_{1n}\\\vdots &\ddots &\vdots \\a_{n1}&\ldots &a_{nn}+1\end{array}}\right\|<1}

Barele verticale duble înseamnă o normă de matrice.

Rezolvarea ecuației f(x)=0 prin metoda lui Newton, aproximare inițială: x 1 =a.

metoda lui Newton (metoda tangentei)[ | ]

Caz unidimensional[ | ]

Optimizarea transformării ecuației originale f (x) = 0 (\displaystyle f(x)=0)în maparea contracției x = φ (x) (\displaystyle x=\varphi (x)) vă permite să obțineți o metodă cu o rată de convergență pătratică.

Pentru ca maparea să fie cât mai eficientă, este necesar ca în punctul următoarei iterații x ∗ (\displaystyle x^(*)) executat φ ′ (x ∗) = 0 (\displaystyle \varphi "(x^(*))=0). Vom căuta o soluție la această ecuație în formă φ (x) = x + α (x) f (x) (\displaystyle \varphi (x)=x+\alpha (x)f(x)), apoi:

Să folosim ce f (x) = 0 (\displaystyle f(x)=0), și obținem formula finală pentru α (x) (\displaystyle \alpha (x)):

Având în vedere acest lucru, funcția de contracție va lua forma:

Apoi algoritmul pentru găsirea unei soluții numerice a ecuației f (x) = 0 (\displaystyle f(x)=0) reduce la o procedură de calcul iterativă:

Metode iterative

Metodele iterative presupun implementarea următoarelor trei etape: construirea unui proces iterativ care converge către soluția exactă pentru calcularea aproximărilor succesive (adică construirea unei secvențe de vectori care converg către soluția exactă). ; determinarea criteriului de convergenţă al acestui proces, care permite determinarea momentului de realizare a preciziei cerute; studiul ratei de convergență și optimizarea procesului iterativ în vederea reducerii numărului de operații necesare pentru a obține acuratețea necesară.

Metodele iterative fac posibilă obținerea unei soluții cu o precizie predeterminată, dacă convergența metodei este dovedită. Metodele iterative nu dau o soluție strict exactă, deoarece se realizează ca limită a unei secvențe de vectori. Metoda directă oferă în general o soluție exactă, dar din cauza erorilor de rotunjire care apar pe toate computerele, aceasta nu poate fi atinsă și a priori este chiar greu de apreciat cât de mult diferă această soluție de cea exactă. În legătură cu cele de mai sus, metodele iterative fac uneori posibilă obținerea unei soluții cu o mai mare acuratețe decât cele directe.

Luați în considerare câteva metode iterative pentru rezolvarea ecuațiilor liniare.

Metodă simplă de iterație

În metoda iterației simple, sistemul (2.1) de ecuații algebrice liniare ax = b se reduce la un sistem echivalent al formei

Soluția sistemului (2.9) și, în consecință, soluția sistemului original (2.1) este căutată ca limită a șirului de vectori pentru:

k = 0, 1, 2,…,(2.10)

unde este aproximarea inițială pentru vectorul soluție.

O condiție suficientă pentru convergența metodei iterației simple este determinată de următoarea teoremă.

TEOREMA 1. Dacă vreo normă a matricei compatibilă cu norma considerată a vectorului este mai mică decât unitatea (), atunci succesiunea în metoda iterației simple converge către soluția exactă a sistemului (2.9) cu o rată nu mai mică decât rata a unei progresii geometrice cu numitor pentru orice aproximare initiala .

DOVADA. Pentru a demonstra teorema, introducem o eroare . Scăzând egalitatea (2.10) din relație, obținem . Trecând la norme, avem

Rețineți că inegalitatea din expresia anterioară este condiția de consistență pentru norma matricei și vectorului. În cazul în care un , apoi pentru orice vector inițial de eroare (sau altfel, pentru orice vector inițial ), rata de eroare tinde spre zero nu mai lentă decât o progresie geometrică cu numitorul .

Dacă alegem norma ca normă matriceală sau apoi, pentru a rezolva problema convergenței metodei iterației simple, se poate folosi corolarul din teorema 1: metoda iterației simple converge dacă una din următoarele condiții este îndeplinită pentru matrice:

, i =1,2, …, n,

, j = 1, 2, …, n.(2.11)

Cel mai simplu și cel mai comun mod de a aduce sistemul Ax=b la forma (2.9), convenabilă pentru iterații, este selectarea elementelor diagonale, cu fiecare i-a ecuația se rezolvă în raport cu i-a necunoscut:

, i = 1, 2, …, n, (2.12)

iar metoda simplă de iterație poate fi scrisă ca

Matricea are apoi forma

.

Elementul acestei matrice poate fi scris ca unde este simbolul Kronecker. În acest caz, o condiție suficientă pentru convergența metodei iterației simple poate fi formulată ca condiție pentru dominanța elementelor diagonale ale matricei DAR, care rezultă din (2.11) și notația matricei , i.e.

i = 1, 2, …, n.

Subliniem încă o dată că formele considerate ale condiției pentru convergența metodei iterației sunt doar suficiente. Execuția lor garantează convergența metodei, dar eșecul lor în cazul general nu înseamnă că metoda iterației simple diverge. O condiție necesară și suficientă pentru convergența metodei de iterație simplă este condiția ca partea întreagă (unde este valoarea proprie maximă modulo a matricei DAR); această condiție este rar utilizată în practica computațională.

Să ne întoarcem la întrebarea de a estima eroarea soluției. Sunt interesante două relații de estimare a erorii soluției: prima raportează norma erorii de norma diferenței a două aproximări succesive și poate fi folosită pentru estimarea erorii numai în procesul de calcule; al doilea raportează norma erorii la normele vectorului aproximării inițiale și vectorului termenului liber în sistem (2.9). Relațiile necesare sunt date de următoarele două teoreme.

TEOREMA 2. Dacă vreo normă a matricei consecventă cu norma considerată a vectorului X

. (2.13)

DOVADA. Să scădem egalitatea (2.10) din egalitate:

Scăzând din ambele părți valoarea de aproximare, transformăm acest raport în forma

Trecând la norme, obținem

Deoarece, prin ipoteza teoremei,

Folosind relaţia din care rezultă că in sfarsit obtinem:

TEOREMA 3. Dacă orice normă este o matrice compatibilă cu norma considerată a vectorului X, mai mic de unu (), atunci are loc următoarea estimare a erorii:

Să facem două observații. În primul rând, relația (2.13) poate fi scrisă ca

ceea ce face posibilă obținerea unei estimări a erorii pe baza rezultatelor primelor două iterații. În primul rând, când se utilizează metoda iterației, se recomandă uneori să se folosească norma diferenței a două aproximări succesive ca estimare a erorii de calcul. Din corelațiile pentru eroare rezultă că acest lucru nu este adevărat în cazul general. Dacă norma este aproape de unitate, atunci coeficientul la poate fi destul de mare.

Erorile iterațiilor succesive sunt legate de relație

acestea. eroarea se modifică liniar la un pas. Se spune că metoda are convergență liniară sau convergență de ordinul întâi. Cu toate acestea, numărul de iterații necesare pentru a obține acuratețea necesară depinde de valoarea și de aproximarea inițială a .

Astfel, folosind ca exemplu metoda simplă de iterație, sunt demonstrate trei etape ale metodelor iterative: construcția unei secvențe de vectori generați prin formula (1.10); determinarea condiției de convergență conform teoremei 1 și o estimare a ratei de convergență folosind teoremele 2 și 3.

metoda Seidel

Metoda simplă de iterație nu folosește posibilitatea aparent evidentă de a îmbunătăți convergența procesului iterativ - introducerea imediată a componentelor nou calculate ale vectorului în calcul. Această posibilitate este utilizată în metoda iterativă Seidel. Procesul iterativ pentru sistemul (2.9) se desfășoară în acest caz conform relației

i = 1, 2, …, n (2.14)

sau pentru sistem (1.1)

Fără a intra în detalii, observăm că metoda iterației Seidel duce adesea într-adevăr la o convergență mai rapidă decât metoda iterației simple. Cu toate acestea, există cazuri în care metoda iterației Seidel converge mai lent decât metoda iterației simple și chiar cazuri în care metoda iterației simple converge, dar metoda iterației Seidel diverge.

Rețineți că metoda Seidel converge, dacă matricea DAR pozitiv definit și simetric.

Să arătăm că metoda iterației Seidel este echivalentă cu o metodă simplă de iterație cu o matrice și un vector special construite în relația (2.10). Pentru a face acest lucru, scriem sistemul (2.14) sub forma Matrice (E-H) este o matrice triunghiulară inferioară cu elemente diagonale egale cu unu. Prin urmare, determinantul acestei matrice este diferit de zero (egal cu unu) și are o matrice inversă. Apoi

Comparând această relație cu soluția (2.10), putem concluziona că metoda iterației Seidel este într-adevăr echivalentă cu metoda iterației simple în sensul că, pentru a stabili condiția și criteriul de convergență pentru metoda iterației Seidel, se pot folosi teoremele date. pentru metoda simplă de iterație, dacă setăm Procesul iterativ pentru sistemul (2.12) poate fi scris și într-o formă mai generală și anume

Să fie dat un sistem de n ecuații algebrice cu n necunoscute:

Algoritmul metodei de iterație simplă:

Rețineți că aici și în cele ce urmează, indicele denotă componenta corespunzătoare a vectorului de necunoscute, iar superscriptul denotă numărul de iterație (aproximație).

Apoi se formează un proces matematic ciclic, fiecare ciclu al căruia reprezintă o iterație. Ca rezultat al fiecărei iterații, se obține o nouă valoare a vectorului de necunoscute. Pentru a organiza procesul iterativ, scriem sistemul (1) în forma de mai sus. În acest caz, termenii de pe diagonala principală sunt normalizați și rămân la stânga semnului egal, în timp ce restul sunt transferați în partea dreaptă. Sistem redus de ecuații se pare ca:

observa asta nu va fi niciodată atins, totuși, cu fiecare iterație ulterioară, vectorul necunoscutelor se apropie din ce în ce mai mult de soluția exactă.

12. Principala formulă iterativă utilizată în metoda iterației simple pentru rezolvarea unei ecuații neliniare:

13. Criteriu de oprire a procesului iterativ în metoda iterației simple pentru rezolvarea unei ecuații neliniare:

Procesul iterativ se încheie dacă pentru fiecare i-a componentă a vectorului de necunoscute este îndeplinită condiția de obținere a preciziei.
observa asta soluție exactă în metoda simplă de iterație nu va fi niciodată atins, cu toate acestea, cu fiecare iterație ulterioară, vectorul necunoscutelor se apropie din ce în ce mai mult de soluția exactă

14. Criterii de alegere a funcției auxiliare F(x) pentru segmentul de iterație al intervalului :

La efectuarea unui test de matematică pentru rezolvarea metodei iterației simple, trebuie mai întâi verificată condiția de convergență. Pentru convergența metodei, este necesar și suficient ca în matricea A valorile absolute ale tuturor elementelor diagonale să fie mai mari decât suma modulelor tuturor celorlalte elemente din rândul corespunzător:

Dezavantajul metodelor iterative Aceasta este o condiție de convergență destul de strictă, care este departe de a fi îndeplinită pentru toate sistemele de ecuații.

Dacă condiția de convergență este îndeplinită, atunci în etapa următoare este necesar să se stabilească aproximarea inițială a vectorului de necunoscute, care este de obicei vectorul zero:

15. Metoda Gauss utilizată pentru rezolvarea sistemelor de ecuații liniare prevede:

Metoda se bazează pe transformarea matricei în formă triunghiulară. Acest lucru se realizează prin eliminarea secvenţială a necunoscutelor din ecuaţiile sistemului.

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 într-o 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 secundare î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 îndeplinesc condiția de convergență sunt lăsate neatinse, iar cu cele care nu, formează combinații liniare, i.e. î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 de formă normală satisface condiția 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 generală 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ă când 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 substituirea valorilor găsite în ecuațiile originale îndeplinesc 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.