En álgebra lineal numérica , el método de Gauss-Seidel , también conocido como método de Liebmann o método de desplazamiento sucesivo , es un método iterativo que se utiliza para resolver un sistema de ecuaciones lineales . Lleva el nombre de los matemáticos alemanes Carl Friedrich Gauss y Philipp Ludwig von Seidel , y es similar al método Jacobi . A pesar de que se puede aplicar a cualquier matriz con los no-cero elementos en las diagonales, la convergencia sólo se garantiza si la matriz es o bien estrictamente diagonal dominante , [1] o simétrica y positivo definido . Sólo se mencionó en una carta privada de Gauss a su alumno Gerling en 1823. [2] Seidel no entregó una publicación antes de 1874.
Descripción
El método de Gauss-Seidel es una técnica iterativa para resolver un sistema cuadrado de n ecuaciones lineales con x desconocida :
Está definido por la iteración
dónde es la k- ésima aproximación o iteración dees la siguiente o k + 1 iteración de, y la matriz A se descompone en un componente triangular inferior, y un componente triangular estrictamente superior es decir, . [3]
Con más detalle, escriba A , x y b en sus componentes:
Entonces, la descomposición de A en su componente triangular inferior y su componente triangular estrictamente superior viene dada por:
El sistema de ecuaciones lineales se puede reescribir como:
El método Gauss-Seidel ahora resuelve el lado izquierdo de esta expresión para x , usando el valor anterior para x en el lado derecho. Analíticamente, esto se puede escribir como:
Sin embargo, al aprovechar la forma triangular de , los elementos de x ( k +1) se pueden calcular secuencialmente usando sustitución hacia adelante :
El procedimiento generalmente se continúa hasta que los cambios realizados por una iteración están por debajo de cierta tolerancia, como un residuo suficientemente pequeño .
Discusión
La fórmula de elementos para el método de Gauss-Seidel es extremadamente similar a la del método de Jacobi .
El cálculo de x ( k +1) utiliza los elementos de x ( k +1) que ya se han calculado, y solo los elementos de x ( k ) que no se han calculado en la iteración k + 1. Esto significa que, a diferencia del método de Jacobi, solo se requiere un vector de almacenamiento, ya que los elementos se pueden sobrescribir a medida que se calculan, lo que puede ser ventajoso para problemas muy grandes.
Sin embargo, a diferencia del método de Jacobi, los cálculos para cada elemento no se pueden realizar en paralelo . Además, los valores en cada iteración dependen del orden de las ecuaciones originales.
Gauss-Seidel es lo mismo que SOR (sobre-relajación sucesiva) con.
Convergencia
Las propiedades de convergencia del método de Gauss-Seidel son dependientes de la matriz A . Es decir, se sabe que el procedimiento converge si:
- A es simétrico positivo-definido , [5] o
- A es estricta o irreductiblemente dominante en diagonal . [6]
El método de Gauss-Seidel a veces converge incluso si no se cumplen estas condiciones.
Algoritmo
Dado que los elementos se pueden sobrescribir a medida que se calculan en este algoritmo, solo se necesita un vector de almacenamiento y se omite la indexación de vectores. El algoritmo es el siguiente:
Entradas: A , b Salida: φElija una aproximación inicial φ para la repetición de la solución hasta la convergencia para i desde 1 hasta n do σ ← 0 para j desde 1 hasta n do si j ≠ i entonces σ ← σ + a ij φ j end if end ( j -loop) φ i ← ( b i - σ ) / a ii final ( i- bucle) comprobar si se alcanza la convergenciafin (repetir)
Ejemplos de
Un ejemplo de la versión matricial
Un sistema lineal mostrado como es dado por:
- y
Queremos usar la ecuación
en la forma
dónde:
- y
Debemos descomponernos en la suma de un componente triangular inferior y un componente triangular superior estricto :
- y
El inverso de es:
- .
Ahora podemos encontrar:
Ahora tenemos y y podemos usarlos para obtener los vectores iterativamente.
Primero que nada, tenemos que elegir : solo podemos adivinar. Cuanto mejor sea la suposición, más rápido funcionará el algoritmo.
Suponemos:
Entonces podemos calcular:
Como era de esperar, el algoritmo converge a la solución exacta:
De hecho, la matriz A es estrictamente diagonalmente dominante (pero no definida positiva).
Otro ejemplo para la versión matricial
Otro sistema lineal mostrado como es dado por:
- y
Queremos usar la ecuación
en la forma
dónde:
- y
Debemos descomponernos en la suma de un componente triangular inferior y un componente triangular superior estricto :
- y
El inverso de es:
- .
Ahora podemos encontrar:
Ahora tenemos y y podemos usarlos para obtener los vectores iterativamente.
Primero que nada, tenemos que elegir : solo podemos adivinar. Cuanto mejor sea la suposición, más rápido se ejecutará el algoritmo.
Suponemos:
Entonces podemos calcular:
Si probamos la convergencia, encontraremos que el algoritmo diverge. De hecho, la matriz A no es diagonalmente dominante ni definida positiva. Entonces, convergencia a la solución exacta
no está garantizado y, en este caso, no ocurrirá.
Un ejemplo de la versión de la ecuación
Supongamos k ecuaciones dadas donde x n son vectores de estas ecuaciones y el punto de partida x 0 . A partir de la primera ecuación, resuelva para x 1 en términos dePara las siguientes ecuaciones, sustituya los valores anteriores de x s.
Para dejarlo claro, considere un ejemplo.
Resolviendo para y da:
Supongamos que elegimos (0, 0, 0, 0) como aproximación inicial, entonces la primera solución aproximada viene dada por
Utilizando las aproximaciones obtenidas, se repite el procedimiento iterativo hasta alcanzar la precisión deseada. Las siguientes son las soluciones aproximadas después de cuatro iteraciones.
La solución exacta del sistema es (1, 2, −1, 1) .
Un ejemplo usando Python y NumPy
El siguiente procedimiento numérico simplemente se repite para producir el vector solución.
importar numpy como npITERATION_LIMIT = 1000# inicializar la matriz A = np . matriz ([[ 10. , - 1. , 2. , 0. ], [ - 1. , 11. , - 1. , 3. ], [ 2. , - 1. , 10. , - 1. ], [ 0. , 3. , - 1. , 8. ]]) # inicializa el vector RHS b = np . matriz ([ 6.0 , 25.0 , - 11.0 , 15.0 ])imprimir ( "Sistema de ecuaciones:" ) para i en rango ( A . forma [ 0 ]): fila = [ " {0: 3g} * x {1} " . formato ( A [ i , j ], j + 1 ) para j en rango ( A . forma [ 1 ])] de impresión ( "[ {0} ] = [ {1: 3g} ]" . formato ( "+" . unirse ( fila ), b [ i ]))x = np . zeros_like ( b ) para it_count en el rango ( 1 , ITERATION_LIMIT ): x_new = np . zeros_like ( x ) de impresión ( "Iteration {0} : {1} " . formato ( it_count , x )) para i en rango ( A . forma [ 0 ]): s1 = np . punto ( A [ i , : i ], x_new [: i ]) s2 = np . punto ( A [ i , i + 1 :], x [ i + 1 :]) x_new [ i ] = ( b [ i ] - s1 - s2 ) / A [ i , i ] si np . allclose ( x , x_new , rtol = 1e-8 ): romper x = x_newprint ( "Solución: {0} " . format ( x )) error = np . punto ( A , x ) - b print ( "Error: {0} " . formato ( error ))
Produce la salida:
Sistema de ecuaciones : [ 10 * x1 + - 1 * x2 + 2 * x3 + 0 * x4 ] = [ 6 ] [ - 1 * x1 + 11 * x2 + - 1 * x3 + 3 * x4 ] = [ 25 ] [ 2 * x1 + - 1 * x2 + 10 * x3 + - 1 * x4 ] = [ - 11 ] [ 0 * x1 + 3 * x2 + - 1 * x3 + 8 * x4 ] = [ 15 ] Iteración 1 : [ 0 . 0. 0. 0. ] iteración 2 : [ 0,6 2.32727273 - 0,98727273 0,87886364 ] iteración 3 : [ 1.03018182 2.03693802 - 1.0144562 0.98434122 ] Iteration 4 : [ 1.00658504 2.00355502 - 1,00252738 0,99835095 ] Iteration 5 : [ 1,00086098 2,00029825 - 1.00030728 0.99984975 ] iteración 6 : [ 1.00009128 2.00002134 - 1.00003115 0.9999881 ] Iteration 7 : [ 1,00000836 2,00000117 - 1,00000275 0,99999922 ] Iteration 8 : [ 1,00000067 2,00000002 - 1.00000021 0.99999996 ] iteración 9 : [ 1.00000004 1.99999999 - 1,00000001 1. ] Iteration 10 : [ 1. 2. - 1. 1. ] Solución : [ 1. 2. - 1. 1. ] Error : [ 2.06480930e-08 - 1.25551054e-08 3.61417563e-11 0.00000000e + 00 ]
Programa para resolver arbitrarios no. de ecuaciones usando Matlab
El siguiente código usa la fórmula
función x = gauss_seidel ( A, b, x, iters ) para i = 1 : iters para j = 1 : tamaño ( A , 1 ) x ( j ) = ( b ( j ) - suma ( A ( j , :) . * x ) + A ( j , j ) * x ( j )) / A ( j , j ); final finalfinal
Ver también
- Relajación excesiva sucesiva
- Método de Kaczmarz (un método "orientado a filas", mientras que Gauss-Seidel está "orientado a columnas". Véase, por ejemplo, este artículo ).
- Método iterativo. Sistemas lineales
- Propagación de creencias gaussianas
- División de matriz
- Iteración de Richardson
Notas
- ^ Sauer, Timothy (2006). Análisis numérico (2ª ed.). Pearson Education, Inc. pág. 109. ISBN 978-0-321-78367-7.
- ^ Gauss 1903 , pág. 279; enlace directo .
- ^ Golub y Van Loan 1996 , p. 511.
- ^ Golub y Van Loan 1996 , eqn (10.1.3).
- ^ Golub y Van Loan 1996 , Thm 10.1.2.
- ^ Bagnara, Roberto (marzo de 1995). "Una prueba unificada de la convergencia de los métodos de Jacobi y Gauss-Seidel". Revisión SIAM . 37 (1): 93–97. doi : 10.1137 / 1037008 . JSTOR 2132758 .
Referencias
- Gauss, Carl Friedrich (1903), Werke (en alemán), 9 , Gotinga: Köninglichen Gesellschaft der Wissenschaften.
- Golub, Gene H .; Van Loan, Charles F. (1996), Computaciones matriciales (3.a ed.), Baltimore: Johns Hopkins, ISBN 978-0-8018-5414-9.
- Black, Noel y Moore, Shirley. "Método Gauss-Seidel" . MathWorld .
Este artículo incorpora texto del artículo Gauss-Seidel_method en CFD-Wiki que está bajo la licencia GFDL .
enlaces externos
- "Método Seidel" , Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
- Gauss – Seidel de www.math-linux.com
- Gauss-Seidel del Instituto de métodos numéricos holísticos
- Iteración de Gauss Siedel de www.geocities.com
- El método Gauss-Seidel
- Bickson
- Código de Matlab
- Ejemplo de código C