Metode Iterative pentru rezolvarea Ax = b-metoda lui Jacobi

poate cea mai simplă metodă iterativă pentru rezolvarea Ax = b este metoda lui Jacobi. Rețineți că simplitatea acestei metode este atât bună, cât și rea: bună, deoarece este relativ ușor de înțeles și, prin urmare, este un prim gust bun al metodelor iterative; rău, deoarece nu este de obicei utilizat în practică (deși utilitatea sa potențială a fost reconsiderată odată cu apariția calcul paralel). Totuși, este un bun punct de plecare pentru a învăța despre metode iterative mai utile, dar mai complicate.

având în vedere o aproximare curentă

x(k) = (x1(k), x2(k), x3(k), …, xn(k))

pentru x, strategia metodei lui Jacobi este de a utiliza prima ecuație și valorile curente ale lui x2(k), x3(k), …, xn(k) pentru a găsi o nouă valoare x1(k+1) găsiți o nouă valoare XI(k) folosind ecuația i și valorile vechi ale celorlalte variabile. Adică, având în vedere valorile curente x(k) = (x1(k), x2(k), …, xn(k)), găsiți valori noi rezolvând pentru

x(k+1) = (x1(k+1), x2(k+1), …, xn (k+1))

în

acest sistem poate fi scris și ca

pentru a fi clar, indicele I înseamnă că xi (k) este elementul i al vectorului

x(k) = (x1(k), x2(k),…, xi(k),…, xn(k)),

și superscript k corespunde iterației particulare (nu puterii k a lui xi).

dacă scriem D, L și U pentru diagonală, triunghiular inferior strict și triunghiular superior strict și, respectiv, părți ale lui a,

apoi metoda lui Jacobi poate fi scrisă în notație matrice-vector ca

Exemplul 1

să aplicăm metoda lui Jacobi sistemului

.

la fiecare pas, având în vedere valorile curente x1 (k), x2 (k), x3(k), rezolvăm pentru x1(k+1), x2(k+1) și x3 (k+1) în

.

deci, dacă presupunerea noastră inițială x(0) = (x1(0), x2(0), x3(0)) este Vectorul zero 0 = (0,0,0 — – o presupunere inițială comună dacă nu avem câteva informații suplimentare care ne determină să alegem altele — atunci găsim x (1) =(x1(1), x2(1), x3 (1)) prin rezolvarea

deci x(1) = (x1(1), x2 (1), x3(1)) = (3/4, 9/6, -6/7) ≈ (0.750, 1.500, -0.857). Repetăm acest proces pentru a găsi o secvență de aproximări din ce în ce mai bune x(0), x(1), x(2), … . Prezentăm rezultatele în tabelul de mai jos, cu toate valorile rotunjite la 3 zecimale.

suntem interesați de eroarea e la fiecare iterație între soluția adevărată x și aproximarea x(k): E(k) = x − x(k) . Evident, de obicei nu cunoaștem adevărata soluție x. cu toate acestea, pentru a înțelege mai bine comportamentul unei metode iterative, este edificator să folosim metoda pentru a rezolva un sistem Ax = b pentru care cunoaștem adevărata soluție și analizăm cât de repede aproximările converg la adevărata soluție. Pentru acest exemplu, soluția adevărată este x = (1, 2, -1).

norma unui vector ||x|| ne spune cât de mare este vectorul în ansamblu (spre deosebire de cât de mare este fiecare element al vectorului). Norma vectorială cea mai frecvent utilizată în algebra liniară este norma l2:

de exemplu, dacă x = (1, 2, -1), atunci

în acest modul, vom folosi întotdeauna norma l2 (inclusiv pentru normele matricei în tutorialele ulterioare), astfel încât / / / / semnifică întotdeauna|| ||2.

în scopurile noastre, observăm că ||x|| va fi mic exact atunci când fiecare dintre elementele x1, x2, …, xn în x = (x1, x2, …, xn ) este mic. În tabelul următor, norma erorii devine progresiv mai mică pe măsură ce eroarea din fiecare dintre cele trei elemente x1, x2, x3 devine mai mică sau, cu alte cuvinte, pe măsură ce aproximările devin progresiv mai bune.