În matematica computațională o metodă iterativă este o procedură matematică care utilizează o valoare inițială pentru a genera un șir de soluții aproximative îmbunătățite pentru o clasă de probleme, în care a i-a aproximare (numită „iterare”) este în funcție de cele anterioare.
O implementare specifică, cu criterii de terminare pentru o metodă iterativă dată, cum ar fi , , metoda lui Newton sau precum , este un algoritm al unei metode iterative sau o metodă de aproximare succesivă. O metodă iterativă este dacă secvența corespunzătoare converge pentru aproximări inițiale date. De obicei, se efectuează o analiză de convergență riguroasă din punct de vedere matematic a unei metode iterative. Totuși, metodele iterative euristice sunt și ele comune.
Prin contrast, metodele directe încearcă să rezolve problema într-o secvență finită de operații. În absența erorilor de rotunjire metodele directe ar oferi o soluție exactă (de exemplu, rezolvarea unui sistem liniar de ecuații prin eliminare gaussiană). Metodele iterative sunt adesea singura opțiune pentru rezolvarea . Totuși, metodele iterative sunt adesea utile chiar și pentru probleme liniare cu multe variabile (uneori de ordinul milioanelor), unde metodele directe ar fi prohibitiv de costisitoare (și în unele cazuri imposibile) chiar și cu cea mai bună putere de calcul disponibilă.
Istoric În Tratat despre coardă și sinus Jamshīd al-Kāshī a folosit metode iterative pentru a calcula cu mare precizie sinusul lui 1° și . O metodă iterativă timpurie (de tip ) pentru rezolvarea unui sistem liniar a apărut într-o scrisoare a lui Carl Friedrich Gauss către un student al său. El a propus rezolvarea unui sistem de ecuații prin rezolvarea repetată a componentei în care reziduul era cel mai mare.
Teoria metodelor iterative staționare a fost pusă la punct odată cu lucrările lui D.M. Young începând cu anii 1950. Metoda gradientului conjugat a fost, de asemenea, inventată în anii 1950, cu dezvoltări independente de către Cornelius Lanczos, Magnus Hestenes și Eduard Stiefel, dar natura și aplicabilitatea sa au fost înțelese greșit la acea vreme. Abia în anii 1970 s-a realizat că metodele bazate pe conjugare funcționează foarte bine pentru ecuațiile cu derivate parțiale, în special cele de tip eliptic.
Puncte fixe atractive Dacă o ecuație poate fi pusă sub forma , iar o soluție x este un punct fix atractiv al funcției atunci se poate începe cu un punct din bazinul de atracție al lui x, și fie pentru și fie ca șirul să fie convergent spre soluția x. Aici xn este a n-a aproximație (iterație) a lui iar este următoarea (a n+1-a) iterație a lui . Alternativ, pentru a nu interfera cu indicii cu alte semnificații, în metodele numerice se pot folosi indici superiori în paranteze (de exemplu, ). Dacă funcția este derivabilă continuu, o condiție suficientă pentru convergență este ca a derivatei să fie strict mărginită de 1 într-o vecinătate a punctului fix. Dacă această condiție este valabilă în punctul fix, atunci trebuie să existe o vecinătate bazin de atracție suficient de mică.
Sisteme liniare În cazul unui sistem de ecuații liniare, cele două clase principale de metode iterative sunt metodele iterative staționare și metodele mai generale ale .
Metode iterative staționare Descriere Metodele iterative staționare rezolvă un sistem liniar cu un operator care îl aproximează pe cel original și, pe baza unei măsurători a erorii din rezultat (), generează o „ecuație de corecție” pentru care acest proces este repetat. Deși aceste metode sunt ușor de obținut, implementat și analizat, convergența este garantată doar pentru o clasă limitată de matrici.
Definiție O metodă iterativă este definită prin:
și pentru un sistem liniar dat cu soluția exactă:
O metodă iterativă se numește „liniară” dacă există o matrice astfel încât
unde această matrice este matricea de iterație. O metodă iterativă cu o matrice de iterație dată, este convergentă dacă este valabilă
O teoremă importantă afirmă că pentru o metodă iterativă dată matricea sa de iterație este convergentă dacă și numai dacă raza sa spectrală, este subunitară:
Metodele iterative de bază funcționează prin divizarea matricei în
iar aici matricea trebuie să fie ușor inversabilă. Acum, metoda iterativă este definită prin
sau, echivalent,
Din aceasta rezultă că matricea de iterație este dată de:
Exemple Exemple tipice de metode iterative staționare care utilizează o divizare a matricei cum ar fi
unde este doar diagonala lui este partea triunghiulară strict inferioară a lui respectiv este partea triunghiulară strict superioară a lui
Metoda Jacobi ponderată: : Metoda Gauss–Seidel: :
Metodele iterative staționare liniare sunt numite și .
Metode Krîlov peste subspații Metodele Krîlov peste subspații Charles George Broyden, Maria Terasa Vespucci: Krylov Solvers for Linear Algebraic Systems: Krylov Solvers, Elsevier, ISBN 0-444-51474-0, (2004). funcționează prin formarea unei baze a șirului de puteri matriciale succesive înmulțite cu reziduul inițial (secvența Krîlov). Aproximările soluției sunt apoi formate prin minimizarea reziduului peste subspațiul format. Prototipul metodei din această clasă este , care presupune că matricea sistemului, este simetrică . Pentru simetrică (și posibil nedefinită) se lucrează cu metoda reziduurilor minime (). În cazul matricilor asimetrice, au fost obținute metode precum metoda reziduurilor minime generalizate () și metoda gradientului biconjugat ().
Convergența metodelor Krîlov peste subspații Întrucât aceste metode formează o bază, este evident că metoda converge în N iterații, unde N este dimensiunea sistemului. Totuși, în prezența erorilor de rotunjire această afirmație nu este valabilă; în plus, în practică N poate fi foarte mare, iar procesul iterativ atinge o precizie suficientă deja mult mai devreme. Analiza acestor metode este dificilă, depinzând de o funcție complicată a .
Precondiționări Operatorul de aproximare care apare în metodele iterative staționare poate fi încorporat și în metodele Krîlov peste subspații, cum ar fi GMRES (alternativ, metode Krîlov precondiționate pot fi luate în considerare pentru accelerarea metodelor iterative staționare), unde acestea devin transformări ale operatorului original într-unul probabil mai bine condiționat. Construcția precondiționărilor este o arie vastă de cercetare.
Metode de aproximări succesive Metode matematice de aproximări succesive sunt: Metoda Heron de obținere a radicalului dintr-un număr Metoda iterativă de calcul a punctelor fixe Mijloace de obținere a zerourilor funcțiilor:
Metoda lui Newton Chestiuni legate de ecuații diferențiale: privind existența soluțiilor unei ecuații diferențiale Metode Runge–Kutta pentru soluționarea numerică a ecuațiilor diferențiale
Note
Vezi și Analiză numerică
Legături externe
Templates for the Solution of Linear Systems Y. Saad: Iterative Methods for Sparse Linear Systems, 1st edition, PWS 1996
Categorie:Analiză numerică