Método de Gauss-Seidel

Método de Gauss-Seidel

En análisis numérico el método de Gauss-Seidel es un método iterativo utilizado para resolver sistemas de ecuaciones lineales. El método se llama así en honor a los matemáticos alemanes Carl Friedrich Gauss y Philipp Ludwig von Seidel y es similar al método de Jacobi.

Aunque este método puede aplicarse a cualquier sistema de ecuaciones lineales que produzca una matriz (cuadrada, naturalmente pues para que exista solución el sistema debe tener tantas ecuaciones como incógnitas) de coeficientes con los elementos de su diagonal no-nulos, la convergencia del método solo se garantiza si la matriz es diagonalmente dominante o si es simétrica y, a la vez, definida positiva.

Contenido

Descripción

Es un método iterativo, lo que significa que se parte de una aproximación inicial y se repite el proceso hasta llegar a una solución con un margen de error tan pequeño como se quiera. Buscamos la solución a un sistema de ecuaciones lineales, en notación matricial:

A x = b,\,

donde:

A=\begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\a_{n1} & a_{n2} & \cdots & a_{nn} \end{bmatrix}, \qquad x = \begin{bmatrix} x_{1} \\ x_2 \\ \vdots \\ x_n \end{bmatrix} , \qquad b = \begin{bmatrix} b_{1} \\ b_2 \\ \vdots \\ b_n \end{bmatrix}.

El método de iteración Gauss-Seidel se computa, para la iteración (k+1)\,:

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

donde

A = N-P\,

definimos

M = N^{-1}P\,

y

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

donde los coeficientes de la matriz N se definen como n_{ij} = a_{ij}\, si i{\leq}j, n_{ij} = 0 \, si i>j\,.

Considerando el sistema Ax=b,\, con la condición de que a_{ii}{\neq}0, i= 1, ..., n\, . Entonces podemos escribir la fórmula de iteración del método

x_i^{(k+1)}=\frac{-\sum_{1{\leq}j{\leq}i-1}a_{ij}x_{j}^{(k+1)}-\sum_{i+1{\leq}j{\leq}n}a_{ij}x_{j}^{(k)}+b_i}{a_{ii}}, i=1,...,n \, (*)

La diferencia entre este método y el de Jacobi es que, en este último, las mejoras a las aproximaciones no se utilizan hasta completar las iteraciones.

Convergencia

Teorema: Suponga una matriz A \in R(n,n) es una matriz no singular que cumple la condición de

|a_{\mu \mu}|>\sum_{1{\leq}\nu{\leq}n, \nu{\neq}\mu} |a_{\mu \nu}| \, ó \sum_{1{\leq}\nu{\leq}n, \nu{\neq}\mu} |a_{\nu \mu}|, 1{\leq}\mu{\leq}n \, .

Entonces el método de Gauss-Seidel converge a una solución del sistema de ecuaciones, y la convergencia es por lo menos tan rápida como la convergencia del método de Jacobi.

Para ver los casos en que converge el método primero mostraremos que se puede escribir de la siguiente forma:

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

(el término x^{(k)} \, es la aproximación obtenida después de la k-ésima iteración) este modo de escribir la iteración es la forma general de un método iterativo estacionario.

Primeramente debemos demostrar que el problema lineal Ax = b que queremos resolver se puede representar en la forma (**), por este motivo debemos tratar de escribir la matriz A como la suma de una matriz triangular inferior, una diagonal y una triangular superior A=(L+D+U), D=diag( a_{ii} \, ). Haciendo los despejes necesarios escribimos el método de esta forma

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


por lo tanto M=-(L+D)-1 U y c=(L+D)-1b

Ahora podemos ver que la relación entre los errores, el cuál se puede calcular al substraer x=Bx+c de (**)

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

Supongamos ahora que \lambda_i \, , i= 1, ..., n, son los valores propios que corresponden a los vectores propios ui, i= 1,..., n, los cuales son linealmente independientes, entonces podemos escribir el error inicial

x^{(0)}-x=\alpha_{1}u_{1}+...+\alpha_{n}u_{n} \,
x^{(k)}-x=\alpha_{1}\lambda_{1}^{k}u_{1}+...+\alpha_{n}\lambda_{n}^{k}u_{n} \, (***)

Por lo tanto la iteración converge si y sólo si | λi|<1, i= 1, ..., n. De este hecho se desprende el siguiente teorema:

Teorema: Una condición suficiente y necesaria para que un método iterativo estacionario x^{(k+1)}=Mx^{(k)}+c \, converja para una aproximación arbitraria x^{(0)} es que

\rho(M)=max_{1{\leq}i{\leq}n}|\lambda_i|<1 \,

donde ρ(M) es el radio espectral de M.

Explicación

Se elige una aproximación inicial para x^{0}\,.
Se calculan las matrices M y el vector c con las fórmulas mencionadas. El proceso se repite hasta que xk sea lo suficientemente cercano a xk − 1, donde k representa el número de pasos en la iteración.Se tiene que despejar de la ecuacion una de variable distinta y determinante.Si al sumar los coeficientes de las variables divididos entre si da 1 y -1 es más probable que el despeje funcione. Y se debe de despejar en cada ecuacion una variable distinta, una forma de encontrar que variable despejar es despejando la variable que tenga el mayor coeficiente.

Ejemplos:

3x-y+z=1
x-5y+z=8
x-y+4z=11

Despejes:

x=(1+y-z)/3 y=(8-x-z)/-5 z=(11-x+y)/4

Despues se necesita iniciar con las iteraciones,el valor inicial no es importante lo importante es usar las iteraciones necesarias, para darte cuenta cuantas iteraciones son necesarias necesitas observar cuando los decimales se estabilicen en dos decimales pero se tiene que tener en cuenta que se tiene que seguir con las iteraciones aunque una de las variables sea estable si las démas no han llegado al valor buscado. Se sustituye los valores en los despejes, usando para cada despeje el nuevo valor encontrado.

k x y z
0 0 0 0
1 0.333 -1.600 2.750
2 -1.117 -0.983 2.267
3 -0.750 -1.370 2.783
4 -1.051 -1.193 2.595
... ... ... ...
10 -0.982 -1.259 2.679
11 -0.979 -1.261 2.681
12 -0.980 -1.260 2.680
13 -0.980 -1.260 2.680
-0.980 -1.260 2.680

Estos son los resultados estimados para las variables y podemos observar que los decimales se estabilizaron en dos decimales.

Algoritmo

El método de Gauss-Seidel se puede escribir en forma de algoritmo de la siguiente manera:

Algoritmo Método de Gauss-Seidel

función Gauss-Seidel (A, x0)

//x0 es una aproximación inicial a la solución//
para k\gets 1 hasta convergencia hacer
para i\gets 1 hasta n\, hacer
\sigma\gets 0
para j\gets 1 hasta n\, hacer
si j \neq i\, entonces
σ = σ + aijxj
fin para
x_i = {{\left( {b_i - \sigma } \right)} \over {a_{ii} }}
fin para
comprobar si se alcanza convergencia
fin para

Enlaces externos


Wikimedia foundation. 2010.

Игры ⚽ Поможем сделать НИР

Mira otros diccionarios:

  • Seidel — «Seidel» puede referirse a: Philipp Ludwig von Seidel, matemático y astrónomo del siglo XIX. «Seidel», cráter lunar nombrado en honor del matemático del siglo XIX. «Método de Gauss Seidel», método numérico usado para resolver sistemas de… …   Wikipedia Español

  • Método de Jacobi — En análisis numérico el método de Jacobi es un método iterativo, usado para resolver sistemas de ecuaciones lineales del tipo Ax = b. El algoritmo toma su nombre del matemático alemán Carl Gustav Jakob Jacobi. El método de Jacobi consiste en usar …   Wikipedia Español

  • Philipp Ludwig von Seidel — Este artículo trata sobre el matemático y astrónomo del siglo XIX. Para otros usos de este término, véase Seidel (desambiguación). Philipp Ludwig Ritter von Seidel (*24 de octubre de 1821, Dos Puentes, Alemania – † 13 de agosto de 1896, Múnich)… …   Wikipedia Español

  • Sistema de ecuaciones lineales — En matemáticas y álgebra lineal, un sistema de ecuaciones lineales, también conocido como sistema lineal de ecuaciones o simplemente sistema lineal, es un conjunto de ecuaciones lineales sobre un cuerpo o un anillo conmutativo. Un ejemplo de… …   Wikipedia Español

  • Análisis numérico — El análisis numérico o cálculo numérico es la rama de las matemáticas que se encarga de diseñar algoritmos para, a través de números y reglas matemáticas simples, simular procesos matemáticos más complejos aplicados a procesos del mundo real. El… …   Wikipedia Español

  • Teorema de Ostrwoski y Reich — Saltar a navegación, búsqueda El Teorema de Ostrwoski Reich es un teorema asociado a las técnicas de relajación en Análisis Numérico que puede enunciarse como sigue: Sea un sistema lineal de ecuaciones de la forma A{x}={b}, siendo A la matriz de… …   Wikipedia Español

  • Teorema de Ostrowski y Reich — El Teorema de Ostrwoski Reich es un teorema asociado a las técnicas de relajación en Análisis numérico que puede enunciarse como sigue: Sea un sistema lineal de ecuaciones de la forma A{x}={b}, siendo A la matriz de coeficientes, {x} el vector de …   Wikipedia Español

Compartir el artículo y extractos

Link directo
… Do a right-click on the link above
and select “Copy Link”