Método de Gauss-Seidel

En anàlisis numèric el método de Gauss-Seidel és un método iterativo utilisat per a resoldre sistemes d'equacions llineals. El método es diu aixina en honor als matemàtics alemans Carl Friedrich Gauss i Philipp Ludwig von Seidel i és similar al método de Jacobi.

Encara que este método pot aplicar-se a qualsevol sistema d'equacions llineals que produïxca una matriu (quadrada, naturalment puix per a que existixca solució única, el sistema deu tindre tantes equacions com a incògnites) de coeficients en els elements de la seua diagonal no-nuls, la convergència del método solament es garantisa si la matriu és diagonalment dominant o si és simètrica i, al mateix temps, definida positiva.

Descripció

És un método iterativo, lo que significa que es partix d'una aproximació inicial i es repetix el procés fins a aplegar a una solució en un marge d'error tan chicotet com es vullga. Busquem la solució a un sistema d'equacions llineals, en notació matricial:

$Ax=b,$

a on:

$A=\left(\begin{array}{cccc}{a}_{11}& a_{12}& \cdots & a_{1n}\\ a_{21}& a_{22}& \cdots & a_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ a_{n1}& a_{n2}& \cdots & a_{nn}\end{array}\right),x=\left(\begin{array}{c}{x}_1\\ x_2\\ ⋮\\ x_n\end{array}\right),b=\left(\begin{array}{c}{b}_1\\ b_2\\ ⋮\\ b_n\end{array}\right).$

El método de iteración Gauss-Seidel es computa, per a la iteración $(k+1)$:

$x^{(k+1)}=M{x}^{(k)}+c.$

a on

$A=N-P$

definim

$M=N^{-1}P$

i

$c=N^{-1}b$,

a on els coeficients de la matriu N es definixen com $n_{ij}=a_{ij}$ si $i\le j$, $n_{ij}=0$ si $i>j$, açò és, la matriu N és triangular superior.

Considerant el sistema $Ax=b,$ en la condició de que $a_{ii}\ne 0,i=1,\mathrm{...},n$. Llavors podem escriure la fòrmula de iteración del método

$x_i^{(k+1)}=\frac{-\sum _{1\le j\le i-1}{a}_{ij}{x}_j^{(k+1)}-\sum _{i+1\le j\le n}{a}_{ij}{x}_j^{(k)}+b_i}{a_{ii}},i=1,\mathrm{...},n$(*)

La diferència entre este método i el de Jacobi és que, en este últim, les millores a les aproximacions no s'utilisen fins a completar les iteraciones.

Convergència

Per a vore els casos en que convergix el método primer mostrarem que es pot escriure de la següent forma:

$x^{(k+1)}=M{x}^{(k)}+c,k=1,2,\mathrm{3...}$ (**)

(el terme $x^{(k)}$ és l'aproximació obtinguda despuix de la k-ésima iteración) este modo d'escriure la iteración és la forma general d'un método iterativo estacionario.

Primerament devem demostrar que el problema llineal $Ax=b$ que volem resoldre es pot representar en la forma (**), per este motiu devem tractar d'escriure la matriu A com la suma d'una matriu triangular inferior, una diagonal i una triangular superior A=(L+D+O), D=diag($a_{ii}$). Fent els rebuges necessaris escrivim el método d'esta forma

$x^{(k+1)}={-(L+D)}^{-1}U{x}^{(k)}+{(L+D)}^{-1}b$

per lo tant M=-(L+D)^-1 O i c=(L+D)^-1b

Ara podem vore que la relació entre els errors, el qual es pot calcular en sostraure x=Bx+c de (**)

$x^{(k+1)}-x=M(x^{(k)}-x)=\mathrm{...}=M^{(k+1)}(x^{(0)}-x).$

Supongam ara que ${\lambda }_i$, i= 1, ..., n, són els valors propis que corresponen als vectores propis $u_i$, i= 1,..., n, els quals són linealmente independents, llavors podem escriure l'error inicial

$x^{(0)}-x={\alpha }_1{u}_1+\mathrm{...}+{\alpha }_n{u}_n$

$x^{(k)}-x={\alpha }_1{\lambda }_1^k{u}_1+\mathrm{...}+{\alpha }_n{\lambda }_n^k{u}_n$(***)

Per lo tant la iteración convergix si i només si $|{\lambda }_i|<1,\mathrm{\forall }i=1,\dots ,n$. D'este fet es desprén la següent teorema:

Vore també

• Método de Jacobi
• Método de Sobre-Relaixació Successiva (SOR)