Metodi iterativi per la Risoluzione di Sistemi Lineari

uni
Idea:

$$\underset{k\to \infty }{\lim }{x}^{(k)}=x$$

con $k$ iterazioni.

Metodi di punto fisso

$$x=Hx+c⟹x=(I-GA)x+Gb$$

con $G$ matrice non singolare qualsiasi.

Processo iterativo:

$$x^{(k+1)}=H{x}^{(k)}+c,k=0,1,...$$

• $x^{(0)}$ approssimazione iniziale della soluzione.
• $H$ matrice di iterazione

Theorem

Condizione necessaria e sufficiente affinché un metodo iterativo della forma $x^{(k+1)}=H{x}^{(k)}+c$ sia convergente per qualunque vettore iniziale $x^{(0)}$, è che la sua matrice di iterazione $H$ sia convergente

Corollari:

• per la convergenza è necessaria e sufficiente $\rho (H)<1$
• condizione sufficiente per la convergenza è l’esistenza di una norma naturale per cui: $||H||<1$

Criteri di stop

1. restringere il residuo $\frac{|r^{(k)}}{|b|}<\delta$
2. restringere la variazione di errore $|x^{(k+1)}-x^{(k)}|<\delta$

Idea

$$A=D-E-F$$

dove:

• $D$ è la diagonale di $A$
• $E$ è l’opposta della triangolare inferiore a diagonale nulla
• $F$ è l’opposta della triangolare superiore a diagonale nulla

$$Ax=b⟹(D-E-F)x=b$$ $$\{\begin{array}{l}{x}^{(0)}\\ x^{(k+1)}=H{x}^{(k)}+c\text{equazione di punto fisso}\end{array}$$

Metodo di Jacobi

$$H_J=D^{-1}(E+F)$$

• Ogni iterazione costa $O(n^2)$.

$$(H_J{)}_{ij}=\{\begin{array}{ll}-\frac{a_{ij}}{a_{ii}}& \text{se}i\ne j\\ 0& \text{se}i=j\end{array}$$

Equazione:

$$x_i^{(k+1)}=\frac{1}{a_{ii}}(b_i-\underset{(E+F)\cdot x}{\underbrace{\sum _{\begin{array}{c}j=1\\ j\ne i\end{array}}^n{a}_{ij}{x}_j^{(k)}}})$$

• per calcolare $x_j^{(k+1)}$ servono tutte le entrate di $x^{(k)}$, quindi non posso sovrascriverlo finché non ho tutto $x^{(k+1)}$.

Metodo di Gauss-Seidel

$$H_{GS}=(D-E{)}^{-1}\cdot Fc=(D-E{)}^{-1}\cdot b$$

• costo di ogni iterazione: $O(n^2)$.

Considerazioni

Sia Jacobi sia Gauss-Seidel necessitano di elementi non nulli sulla diagonale, possiamo quindi trovare permutazioni $\Pi Ax=\Pi b$ in modo da trovare una permutazione $\Pi x$ di $x$.

Teorema

se $A$ è a predominanza diagonale forte oppure è irriducibile e a predominanza diagonale debole (matrice non singolare) allora il metodo di Jacobi e quello di Gauss-Seidel convergono (hanno però due dimostrazioni diverse).