Metodi iterativi di punto fisso.

Dato il sistema di n equazioni, lineari o nonlineari,

$$F(x)=0 \leqno(2.1)$$

dove $F:R^n\to R^n$, si chiama equazione di punto fisso una sua formulazione equivalente nella forma

$$x=T(x). \leqno(2.2)$$

Dalla forma (2.2), dato un punto iniziale x⁽⁰⁾, é possibile definire per ricorrenza la successione

$$x^{(k+1)}=T(x^{(k)}). \leqno(2.3)$$

Nel caso la successione x^(k) converga ad un certo $\bar x$, si caratterizza la velocitá di convergenza tramite il piú grande esponente $\gamma$ che permette di verificare la disuguaglianza

$$\Vert x^{(k+1)} - \bar x\Vert\le C\Vert x^{(k)} - \bar x\Vert^\gamma \leqno(2.4)$$

per una qualche costante C. Ad esempio, se $\gamma=1$ si parla di convergenza lineare, se $\gamma=2$ di convergenza quadratica.

Risultati fondamentali

$\bullet$ Se esiste un insieme chiuso $E\subseteq R^n$ tale che $T(E)\subseteq E$ e che $\Vert T(x) - T(y)\Vert\le L\Vert x - y\Vert$ per ogni $x,y\in E$ con L<1, allora l'equazione (2.2) ha soluzione unica $\bar x$ in E, e se $x^{(0)}\in E$, allora $\bar x=\lim_k x^{(k)}$. La convergenza di x^(k)verso x é (almeno) lineare.

$\bullet$ Se n=1, allora l'equazione F(x)=0 si puó sempre porre nella forma (2.2) ponendo $T(x)=x-\alpha F(x)$. Se esiste una radice $\bar x$e $\alpha=1/F'(\bar x)$, allora la successione x^(k) converge quadraticamente a $\bar x$ per ogni x⁽⁰⁾ in un opportuno intorno di $\bar x$.

$\bullet$ Se il sistema (2.1) é lineare, ovvero F(x)=Ax-b, allora si puó definire la iterazione (2.3) nella forma (metodo di Jacobi):

$$x_j^{(k+1)}={1\over a_{jj}}\left(b_j - \sum_{i\not=j} a_{ji}x_i^{(k)}\right) ~~~~(j=1,\ldots,n) \leqno(2.5)$$

e se la matrice A é strettamente dominate diagonale , la successione x^(k) converge alla unica soluzione del sistema lineare per ogni $x^{(0)}\in R^n$.

$\bullet$ Se in (2.5) si sceglie di utilizzare nella stessa iterazione le variabili appena calcolate, si ottiene lo schema (metodo di Gauss-Seidel):

$$x_j^{(k+1)}={1\over a_{jj}}\left(b_j - \sum_{i<j} a_{ji}x_i^{... ...um_{i>j} a_{ji}x_i^{(k)}\right) ~~~~(j=1,\ldots,n) \leqno(2.6)$$

ed anche in questo caso se A é strettamente dominate diagonale , la successione x^(k) converge alla unica soluzione del sistema lineare per ogni $x^{(0)}\in R^n$. Lo stesso risultato si ottiene se A é definita positiva.