Nei sistemi lineari del tipo $Ax=b$, dove la matrice dei coefficienti $A \in \R^{n \times n}$ è sparsa o di elevate dimensioni ($n>10^6$), si utilizzano dei metodi iterativi che attraverso una sequenza di approssimazioni da $x^{(0)}$ fino a $x^{(k)}$, convergono alla soluzione del sistema.

$$ \lim_{k \rightarrow \infty} {\|x^{(k)}-x\|}=0 $$

<aside> 💡

Fill-in ⇒ fenomeno causato dall’uso di metodi diretti in matrici troppo sparse. Durante la risoluzione del sistema, elementi inizialmente nulli vengono riempiti.

</aside>

La costruzione della successione termina secondo un criterio di arresto.

Qualità ed efficienza del metodo sono determinate dalla sua convergenza e dalle iterazioni

Decomposizione additiva

Tecnica generale per ottenere un metodo iterativo a partire da una matrice $A \in \mathbb F^{n \times n}$.

• $M$ → matrice invertibile
• $N=M-A$

$$ A= M−N $$

Da questo si ottiene che il sistema può essere definito come segue:

$$ Ax=b \iff (M-N)x=b \iff Mx=Nx+b \iff x=\red Px+\blue q $$

• $\red P=M^{-1} N$ → matrice iterazione
• $\blue q=M^{-1} b$ → vettore costante

Il sistema al passo k genera una successione:

$$ x^{(k)}=Px^{(k-1)}+q \ \ \ \ \ k=1,2,\cdots,n $$

Metodi iterativi

Data una matrice $A =(a_{ij})\in R^{n \times n}$ invertibile con elementi diagonali non nulli $a_{ii}\not =0$

Gauss-Seidel

Definito dal partizionamento di $G=M^{-1}N$