Metodo di Gauss-Seidel

Questa voce o sezione sull'argomento matematica non cita le fonti necessarie o quelle presenti sono insufficienti.

In analisi numerica il metodo di Gauss-Seidel è un metodo iterativo, simile al metodo di Jacobi, per la risoluzione di un sistema lineare, scritto nella forma matriciale ${\displaystyle Ax=b.}$

Come per il metodo di Jacobi, la matrice ${\displaystyle A}$ viene scritta come differenza di due matrici: ${\displaystyle A=M-N.}$ Nel metodo di Gauss-Seidel si prendono ${\displaystyle M=L,}$ matrice triangolare inferiore, e ${\displaystyle N=-U,}$ matrice triangolare superiore con diagonale nulla.

Preso un qualunque vettore ${\displaystyle x_{0},}$ si costruisce quindi una successione di vettori per iterazione (come per il metodo di Jacobi)

${\displaystyle x_{k+1}=L^{-1}(Ux_{k}+b).}$

Come per il metodo di Jacobi, la ricorrenza si può ottenere riscrivendo il sistema di equazioni lineari in modo da isolare una variabile per ogni riga. In questo caso, tuttavia, ogni nuova componente di ${\displaystyle x_{k+1}}$ viene immediatamente sostituita per il calcolo delle successive

Ad esempio, se con il metodo di Jacobi in un sistema 3x3 si utilizza la ricorrenza

${\displaystyle {\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}}}$

con il metodo di Gauss-Seidel si utilizza la ricorrenza

${\displaystyle {\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+1}-{\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+1}-{\frac {a_{3,2}}{a_{3,3}}}y_{k+1}+{\frac {b_{3}}{a_{3,3}}}\end{cases}}}$

Come per il metodo di Jacobi, la successione converge indipendentemente dalla scelta di ${\displaystyle x_{0}}$ se e solo se la matrice ${\displaystyle B=M^{-1}N=L^{-1}U}$ ha tutti autovalori con valore assoluto minore di 1.

Una condizione sufficiente perché questo avvenga è che ${\displaystyle A}$ sia una matrice a diagonale dominante per righe o per colonne in senso stretto. (Questa condizione implica la non singolarità di ${\displaystyle A,}$ quindi l'unicità della soluzione.)

Per risolvere il sistema lineare si utilizza quindi una successione ${\displaystyle x^{(k)}}$ che converge verso la soluzione ${\displaystyle x}$ del sistema lineare. Siano ${\displaystyle A=(a_{ij})}$ e ${\displaystyle b=(b_{i})}$, la successione è costruita come segue:

${\displaystyle x_{i}^{(k+1)}={\frac {b_{i}-\sum \limits _{j<i}a_{ij}x_{j}^{(k+1)}-\sum \limits _{j>i}a_{ij}x_{j}^{(k)}}{a_{ii}}}.}$

A differenza del metodo di Jacobi, il metodo di Gauss-Seidel richiede di tenere in memoria un solo vettore, purché i calcoli non vengano svolti in parallelo.

Considerando il fatto che per calcolare la componente ${\displaystyle i}$-esima ${\displaystyle x_{i}^{(k+1)}}$ del nuovo vettore della successione si utilizzano le ${\displaystyle j<i}$ componenti ${\displaystyle x_{j}^{(k+1)}}$ già calcolate, si osserva che una iterazione del metodo di Gauss-Seidel equivale a due iterazioni del metodo di Jacobi (che utilizza soltanto le componenti del vecchio vettore ${\displaystyle x_{i}^{(k)}}$), quindi nel metodo di Gauss-Seidel si eseguano meno iterazioni e, quindi, converge più velocemente. Tuttavia la complessità computazionale non varia ed entrambi i due metodi hanno una complessità di ${\displaystyle O(n^{2})}$ iterazioni.

• Metodo di Jacobi
• Successive Over Relaxation

• (EN) Eric W. Weisstein, Metodo di Gauss-Seidel, su MathWorld, Wolfram Research.

V · D · M Algebra
Numeri	Naturali · Interi · Razionali · Irrazionali · Algebrici · Trascendenti · Reali · Complessi · Numero ipercomplesso · Numero p-adico · Duali · Complessi iperbolici
Principi fondamentali	Principio d'induzione · Principio del buon ordinamento · Relazione di equivalenza · Relazione d'ordine · Associatività della potenza
Algebra elementare	Equazione · Disequazione · Polinomio · Triangolo di Tartaglia · Teorema binomiale · Teorema del resto · Lemma di Gauss · Teorema delle radici razionali · Regola di Ruffini · Criterio di Eisenstein · Criterio di Cartesio · Disequazione con il valore assoluto · Segno · Metodo di Gauss-Seidel · Polinomio simmetrico · Funzione simmetrica
Elementi di Calcolo combinatorio	Fattoriale · Permutazione · Disposizione · Combinazione · Dismutazione · Principio di inclusione-esclusione
Concetti fondamentali di Teoria dei numeri	Primi Numero primo · Teorema dell'infinità dei numeri primi · Crivello di Eratostene · Crivello di Atkin · Test di primalità · Teorema fondamentale dell'aritmetica Divisori Interi coprimi · Identità di Bézout · MCD · mcm · Algoritmo di Euclide · Algoritmo esteso di Euclide · Criteri di divisibilità · Divisore Aritmetica modulare Teorema cinese del resto · Piccolo teorema di Fermat · Teorema di Eulero · Funzione φ di Eulero · Teorema di Wilson · Reciprocità quadratica
Teoria dei gruppi	Gruppi Gruppo (finito · ciclico · abeliano) · Gruppo primario · Gruppo quoziente · Gruppo nilpotente · Gruppo risolubile · Gruppo simmetrico · Gruppo diedrale · Gruppo semplice · Gruppo sporadico · Gruppo mostro · Gruppo di Klein · Gruppo dei quaternioni · Gruppo generale lineare · Gruppo ortogonale · Gruppo unitario · Gruppo unitario speciale · Gruppo residualmente finito · Gruppo spaziale · Gruppo profinito · Out(Fn) · Parola · Prodotto diretto · Prodotto semidiretto · Prodotto intrecciato Teoremi Alternativa di Tits · Teorema di isomorfismo · Teorema di Lagrange · Teorema di Cauchy · Teoremi di Sylow · Teorema di Cayley · Teorema di struttura dei gruppi abeliani finiti · Lemma della farfalla · Lemma del ping-pong · Classificazione dei gruppi semplici finiti Sottoinsiemi Sottogruppo · Sottogruppo normale · Sottogruppo caratteristico · Sottogruppo di Frattini · Sottogruppo di torsione · Classe laterale · Classe di coniugio · Serie di composizione Omomorfismo · Isomorfismo · Automorfismo interno · Automorfismo esterno · Permutazione · Presentazione di un gruppo · Azione di gruppo
Teoria degli anelli	Anello (artiniano · noetheriano · locale) · Caratteristica · Ideale (primo · massimale) · Dominio (a fattorizzazione unica · a ideali principali · euclideo) · Matrice · Anello semplice · Anello degli endomorfismi · Teorema di Artin-Wedderburn · Modulo · Dominio di Dedekind · Estensione di anelli · Teorema della base di Hilbert · Anello di Gorenstein · Base di Gröbner · Prodotto tensoriale · Primo associato
Teoria dei campi	Campo · Polinomio irriducibile · Polinomio ciclotomico · Teorema fondamentale dell'algebra · Campo finito · Automorfismo · Endomorfismo di Frobenius Estensioni Campo di spezzamento · Estensione di campi · Estensione algebrica · Estensione separabile · Chiusura algebrica · Campo di numeri · Estensione normale · Estensione di Galois · Estensione abeliana · Estensione ciclotomica · Teoria di Kummer Teoria di Galois Gruppo di Galois · Teoria di Galois · Teorema fondamentale della teoria di Galois · Teorema di Abel-Ruffini · Costruzioni con riga e compasso
Altre strutture algebriche	Magma · Semigruppo · Corpo · Spazio vettoriale · Algebra su campo · Algebra di Lie · Algebra differenziale · Algebra di Clifford · Gruppo topologico · Gruppo ordinato · Quasi-anello · Algebra di Boole
argomenti	Teoria delle categorie · Algebra lineare · Algebra commutativa · Algebra omologica · Algebra astratta · Algebra computazionale · Algebra differenziale · Algebra universale

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