Metodo di Jacobi

Da Wikipedia, l'enciclopedia libera.

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.

Algoritmo[modifica | modifica sorgente]

Idea[modifica | modifica sorgente]

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[modifica | modifica sorgente]

Partendo da un qualunque vettore x0, si può allora costruire una successione di vettori xk come

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

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

Propagazione dell'errore[modifica | modifica sorgente]

Per misurare la distanza dei termini della successione xk 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[modifica | modifica sorgente]

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

La convergenza è garantita, indipendentemente dalla scelta iniziale di x0, se e solo se tutti gli autovalori di B = M-1N = M-1A - I hanno norma inferiore a 1, ovvero se il raggio spettrale (l'estremo superiore dei moduli degli autovalori) è inferiore a 1.

Metodo di Jacobi[modifica | modifica sorgente]

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 dele soluzioni ( PAx=Pb ).

Come sistema lineare[modifica | modifica sorgente]

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^{(k+1)}_i={\frac{b_i-\sum_{j\neq i}a_{ij}x^{(k)}_j}{a_{ii}}}

Convergenza[modifica | modifica sorgente]

Si può dimostrare che se A è una matrice a diagonale dominante per righe allora l'algoritmo converge.

Aspetto computazionale[modifica | modifica sorgente]

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[modifica | modifica sorgente]

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

Bibliografia[modifica | modifica sorgente]

  • Alfio Quarteroni, Riccardo Sacco; Fausto Saleri, Risoluzione di sistemi lineari con metodi iterativi in Matematica numerica, 3a 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[modifica | modifica sorgente]

Note[modifica | modifica sorgente]

  1. ^ http://phys.org/news/2014-06-19th-century-math-tactic-makeoverand.html

Collegamenti esterni[modifica | modifica sorgente]

matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica