Metodo di Jacobi
# Metodo di Jacobi

In analisi numerica il metodo di Jacobi è un metodo iterativo per la risoluzione di sistemi lineari, un metodo cioè che calcola la soluzione di un sistema di equazioni lineari dopo un numero teoricamente infinito di passi. Per calcolare tale risultato il metodo utilizza una successione $x^{(k)}$ che converge verso la soluzione esatta del sistema lineare e ne calcola progressivamente i valori arrestandosi quando la soluzione ottenuta è sufficientemente vicina a quella esatta. Fu ideato dal matematico tedesco Carl Jacobi.

## Premessa

### Idea

Scrivendo la matrice A come differenza A = M - N, dove M è una matrice invertibile (ovvero non singolare, con determinante non nullo), allora la soluzione x di Ax = b risolve anche le equazioni

    $Mx=Nx+b$
    $x=M^{-1}(Nx+b).$

### Algoritmo generico

Partendo da un qualunque vettore $x_0,$ si può allora costruire una successione di vettori $x_k$ come

    $x^{k+1}=M^{-1}(Nx^{k}+b).$

Se questa successione converge ad un vettore x, allora Ax = b.

### Propagazione dell'errore

Per misurare la distanza dei termini della successione $x_k$ dalla soluzione e controllare se la successione converge, si può considerare un vettore differenza

    $e^{k}=x^{k}-x.$

La successione dei vettori differenza è data dalla ricorsione

    $e^{k+1}=x^{k+1}-x=M^{-1}(Nx^{k}+b)-M^{-1}(Nx+b)=M^{-1}N(x^{k}-x)=(M^{-1}N)e^{k}$

ovvero

    $e^{k}=(M^{-1}N)^{k}e^{0}$

### Convergenza

L'algoritmo converge se e solo se la successione delle differenze $e_k$ tende al vettore nullo.

La convergenza è garantita, indipendentemente dalla scelta iniziale di $x_0,$ se e solo se tutti gli autovalori di B = $M^{−1}N$ = $M^{−1}A$ - I hanno norma inferiore a 1, ovvero se il raggio spettrale (il valore massimo tra i moduli degli autovalori) è inferiore a 1.

Si può dimostrare che se A è una matrice a diagonale dominante per righe allora l'algoritmo converge (la stessa cosa vale per il Metodo di Gauss-Seidel).

## Metodo di Jacobi

Il metodo di Jacobi consiste nell'applicare l'algoritmo precedente con M = D, la matrice diagonale con la stessa diagonale di A.

È necessario che A non abbia elementi nulli sulla diagonale, perché D dev'essere invertibile. In caso contrario è possibile operare su A con una matrice di permutazione P, in modo che non vi siano elementi nulli sulla diagonale; la stessa permutazione va applicata al vettore b delle soluzioni ( PAx=Pb ).

### Come sistema lineare

La formula ricorsiva diventa ora

    $x^{k+1}=-D^{-1}\left((A-D)x^{k}-b\right)$

Leggendo il metodo di Jacobi su un sistema lineare, la scrittura x = $-D^{−1}((A$ - D)x - b) corrisponde ad isolare una variabile per ogni riga:

    ${\begin{cases}a_{1,1}x+a_{1,2}y+a_{1,3}z=b_{1}\\a_{2,1}x+a_{2,2}y+a_{2,3}z=b_{2}\\a_{3,1}x+a_{3,2}y+a_{3,3}z=b_{3}\end{cases}}\Leftrightarrow {\begin{cases}a_{1,1}x=-a_{1,2}y-a_{1,3}z+b_{1}\\a_{2,2}y=-a_{2,1}x-a_{2,3}z+b_{2}\\a_{3,3}z=-a_{3,1}x-a_{3,2}y+b_{3}\end{cases}}\Leftrightarrow {\begin{cases}x=-{\frac {a_{1,2}}{a_{1,1}}}y-{\frac {a_{1,3}}{a_{1,1}}}z+{\frac {b_{1}}{a_{1,1}}}\\y=-{\frac {a_{2,1}}{a_{2,2}}}x-{\frac {a_{2,3}}{a_{2,2}}}z+{\frac {b_{2}}{a_{2,2}}}\\z=-{\frac {a_{3,1}}{a_{3,3}}}x-{\frac {a_{3,2}}{a_{3,3}}}y+{\frac {b_{3}}{a_{3,3}}}\end{cases}}$Esempio di metodo di Jacobi applicato alla matrice A = [[2.8, 4.41],[-2.31, 4.91]] e al vettore b = [-2, -5].

La ricorsione sui vettori è allora definita da

    ${\begin{cases}x_{k+1}=-{\frac {a_{1,2}}{a_{1,1}}}y_{k}-{\frac {a_{1,3}}{a_{1,1}}}z_{k}+{\frac {b_{1}}{a_{1,1}}}\\y_{k+1}=-{\frac {a_{2,1}}{a_{2,2}}}x_{k}-{\frac {a_{2,3}}{a_{2,2}}}z_{k}+{\frac {b_{2}}{a_{2,2}}}\\z_{k+1}=-{\frac {a_{3,1}}{a_{3,3}}}x_{k}-{\frac {a_{3,2}}{a_{3,3}}}y_{k}+{\frac {b_{3}}{a_{3,3}}}\end{cases}}$

In generale, la ricorsione si può esprimere come

    $x_{i}^{(k+1)}={\frac {b_{i}-\sum \limits _{j\neq i}\,a_{ij}\,x_{j}^{(k)}}{a_{ii}}}$

## Aspetto computazionale

Il metodo di Jacobi richiede di tenere in memoria almeno due vettori (2n), ma i calcoli possono essere svolti in parallelo sulle componenti. Una volta calcolata la matrice B, per ogni iterazione il calcolo di ognuna delle n componenti richiede n - 1 moltiplicazioni e n - 1 somme.

## Recenti sviluppi

Nel 2014, è stata pubblicata una nuova versione dell'algoritmo, detta metodo di Jacobi con rilassamento programmato dei vincoli presso la Johns Hopkins University. Il nuovo metodo è stato dichiarato essere 200 volte più rapido.

