4. Metode iterative de rezolvare a sistemelor de ecuații liniare#
Metodele exacte de rezolvare a sistemelor de ecuații liniare au complexitatea temporală \(O(n^3)\) (indiferent dacă se utilizează o factorizare LU, o factorizare QR sau eliminarea gaussiană), unde \(n\in\mathbb{N}^*\) reprezintă numărul de ecuații, resepctiv numărul de necunoscute ale sistemului.
De aceea, căutăm o altă variantă, o aproximare iterativă ce obține o complexitate temporală de ordinul \(O(\alpha n^2)\), unde \(\alpha\) este o variabilă pe care o putem controla, mai precis, numărul de pași utilizați de algoritm.
Metodele iterative sunt mai puțin vulnerabile la erorile de rotunjire în cazul în care:
-
Sistemul este dominant diagonal;
Matrice dominant diagonalăO matrice se consideră dominant diagonală dacă valoarea absolută a elementelor aflate pe diagonala principală este mai mare sau egală cu suma valorilor absolute ale tuturor elementelor liniei aferente fiecăruia, cu excepția celui de pe diagonala principală.
Matematic, dacă \(A\in\mathbb{R}^{n\times n}\), \(n\in\mathbb{N}^*\), atunci:
\[|A_{ii}|\geq\sum_{j\neq i}|A_{ij}|,\,\forall i\in\overline{1,n} \] -
De obicei, sistemul de ecuații este sparse (rar - majoritatea coeficienților sunt nuli);
-
Fiecare iterație nu este afectată de erorile de rotunjire de la precedenta iterație.
Acest subcapitol va prezenta aceste noțiuni, explicând:
-
Metoda lui Jacobi;
-
Metoda Gauss-Seidel;
-
Metoda suprarelaxării;
-
Metoda gradientului descendent.
Capitolul se încheie cu un număr de exerciții propuse și cu o mulțime de materiale suplimentare ce vă pot ajuta să înțelegeți și mai bine conținutul.
Licență#
The book "Metode Numerice", written by Valentin-Ioan Vintilă, is licensed under CC BY-NC-SA 4.0 
