Metodo di Jacobi: differenze tra le versioni
m Bot: Aggiungo: pt:Método de Jacobi |
m Modificato incipit |
||
Riga 1: | Riga 1: | ||
In [[analisi numerica]] il '''metodo di Jacobi''' è un [[metodo iterativo]] per la risoluzione di [[Sistema di equazioni lineari|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 (matematica)|successione]] <math>x^{(k)}</math> che [[Convergenza|converge]] verso la soluzione esatta del sistema lineare e ne computa progressivamente i valori arrestandosi quando la soluzione ottenuta è sufficientemente vicina a quella esatta. |
|||
== Idea == |
== Idea == |
||
A partire da un <math>x^{(0)}</math> iniziale dato, la successione <math>x^{(k+1)}=F(x^{(k)})</math> con <math>k \in \N</math> è definita come |
A partire da un <math>x^{(0)}</math> iniziale dato, la successione <math>x^{(k+1)}=F(x^{(k)})</math> con <math>k \in \N</math> è definita come |
||
<br> |
<br> |
||
Riga 63: | Riga 62: | ||
Questo metodo ha un costo computazionale dell'ordine di 3n²+2n per ogni iterazione, è facilmente parallelizzabile contrariamente al [[metodo di Gauss-Seidel]] che, tuttavia, converge più velocemente (nella maggior parte dei casi). |
Questo metodo ha un costo computazionale dell'ordine di 3n²+2n per ogni iterazione, è facilmente parallelizzabile contrariamente al [[metodo di Gauss-Seidel]] che, tuttavia, converge più velocemente (nella maggior parte dei casi). |
||
Verificare che la complessità computazionale non sia: 2n²+2n!! |
Verificare che la complessità computazionale non sia: 2n²+2n!! |
||
== Bibliografia == |
|||
* {{cita libro|cognome=Quarteroni|nome=Alfio|wkautore=Alfio Quarteroni|coautori=Riccardo Sacco; Fausto Saleri|titolo=Matematica numerica||edizione=3<sup>a</sup> edizione|anno=2008|mese=gennaio|editore=Springer Verlag|città=Milano|id=ISBN 978-88-470-0782-6|pagine=Pagg.111-158|capitolo=Risoluzione di sistemi lineari con metodi iterativi|cid=quarteroni}} |
|||
{{Portale|matematica}} |
{{Portale|matematica}} |
Versione delle 13:17, 28 nov 2009
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 che converge verso la soluzione esatta del sistema lineare e ne computa progressivamente i valori arrestandosi quando la soluzione ottenuta è sufficientemente vicina a quella esatta.
Idea
A partire da un iniziale dato, la successione con è definita come
dove M è una matrice non singolare (cioè con determinante non nullo e quindi invertibile)
dove F è una funzione affine.
Algoritmo
Se x è la soluzione di allora .
Stima dell'errore
Sia il vettore errore
Poniamo , da cui .
Convergenza
L'algoritmo converge se .
Teorema : Condizione necessaria e sufficiente affinché è che il raggio spettrale (cioè il più grande autovalore in modulo) di B sia strettamente inferiore a 1.
Teorema : Il metodo converge per tutti i sistemi lineari con matrice a diagonale dominante .
Metodo di Jacobi
Si decompone la matrice A come segue: A = D-L-U dove D è la matrice diagonale, -L la parte triangolare inferiore e -U la parte triangolare superiore. Nel metodo di Jacobi si pongono M = D e N = L+U (mentre nel metodo di Gauss-Seidel, M = D-L e N = U).
Osservando che la i-esima riga della matrice si può scrivere come
si ricava facilmente una espressione che rappresenta in termini più "algoritmici" il passo di iterazione del metodo:
Residuo
Sia il vettore residuo, in cui è il vettore di errore (vedi sopra). Possiamo scrivere con che calcoliamo come segue: .
Test d'arresto
Per il test d'arresto utilizziamo il vettore residuo. Data una tolleranza prefissata , abbiamo :
Conclusione
Questo metodo ha un costo computazionale dell'ordine di 3n²+2n per ogni iterazione, è facilmente parallelizzabile contrariamente al metodo di Gauss-Seidel che, tuttavia, converge più velocemente (nella maggior parte dei casi). Verificare che la complessità computazionale non sia: 2n²+2n!!
Bibliografia
- 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.