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₀, 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₀, se e solo se tutti gli autovalori di B = M⁻¹N = M⁻¹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⁻¹((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.

Bibliografia

• Alfio Quarteroni, Riccardo Sacco; Fausto Saleri, Risoluzione di sistemi lineari con metodi iterativi, in Matematica numerica, 3ª edizione, Milano, Springer Verlag, gennaio 2008, Pagg.111-158, ISBN 978-88-470-0782-6.
• (EN) Acton, F. S. Numerical Methods That Work, 2nd printing. Washington, DC: Math. Assoc. Amer., pp. 161–163, 1990.
• (EN) Bronshtein, I. N. and Semendyayev, K. A. Handbook of Mathematics, 3rd ed. New York: Springer-Verlag, p. 892, 1997.
• (EN) Hageman, L. and Young, D. Applied Iterative Methods. New York: Academic Press, 1981.
• (EN) Press, W. H.; Flannery, B. P.; Teukolsky, S. A.; and Vetterling, W. T. Numerical Recipes in FORTRAN: The Art of Scientific Computing, 2nd ed. Cambridge, England: Cambridge University Press, pp. 864–866, 1992.
• (EN) Varga, R. Matrix Iterative Analysis. Englewood Cliffs, NJ: Prentice-Hall, 1962.
• (EN) Young, D. Iterative Solutions of Large Linear Systems. New York: Academic Press, 1971.

Voci correlate

• Carl Jacobi
• Convergenza
• Metodo iterativo
• Sistema di equazioni lineari
• Successione (matematica)

Collegamenti esterni

• (EN) Eric W. Weisstein, Metodo di Jacobi, su MathWorld, Wolfram Research.
• (EN) Jacobi Method from www.math-linux.com, su math-linux.com.
• (EN) Module for Jacobi and Gauss–Seidel Iteration, su math.fullerton.edu. URL consultato il 10 marzo 2013 (archiviato dall'url originale il 15 maggio 2007).
• (EN) Numerical matrix inversion, su pagerank.suchmaschinen-doktor.de.

Controllo di autorità	GND (DE) 4314623-5