En álgebra lineal numérica , el método de sobre-relajación sucesiva ( SOR ) es una variante del método de Gauss-Seidel para resolver un sistema lineal de ecuaciones , lo que resulta en una convergencia más rápida. Se puede utilizar un método similar para cualquier proceso iterativo de convergencia lenta .
Fue ideado simultáneamente por David M. Young Jr. y por Stanley P. Frankel en 1950 con el propósito de resolver automáticamente sistemas lineales en computadoras digitales. Los métodos de relajación excesiva se habían utilizado antes del trabajo de Young y Frankel. Un ejemplo es el método de Lewis Fry Richardson y los métodos desarrollados por RV Southwell . Sin embargo, estos métodos fueron diseñados para ser computados por calculadoras humanas , requiriendo cierta experiencia para asegurar la convergencia a la solución, lo que los hizo inaplicables para la programación en computadoras digitales. Estos aspectos se discuten en la tesis de David M. Young Jr. [1]
Formulación
Dado un sistema cuadrado de n ecuaciones lineales con x desconocido :
dónde:
Entonces A se puede descomponer en un componente diagonal D , y componentes triangulares estrictamente inferior y superior L y U :
dónde
El sistema de ecuaciones lineales se puede reescribir como:
para una constante ω > 1, llamada factor de relajación .
El método de sobre-relajación sucesiva es una técnica iterativa que resuelve el lado izquierdo de esta expresión para x , utilizando el valor anterior para x en el lado derecho. Analíticamente, esto se puede escribir como:
dónde es la k- ésima aproximación o iteración de y es la siguiente o k + 1 iteración de. Sin embargo, al aprovechar la forma triangular de ( D + ωL ), los elementos de x ( k +1) se pueden calcular secuencialmente usando sustitución hacia adelante :
Convergencia
La elección del factor de relajación ω no es necesariamente fácil y depende de las propiedades de la matriz de coeficientes. En 1947, Ostrowski demostró que sies simétrico y positivo-definido entonces por . Por lo tanto, sigue la convergencia del proceso de iteración, pero generalmente estamos interesados en una convergencia más rápida en lugar de solo una convergencia.
Tasa de convergencia
La tasa de convergencia para el método SOR se puede derivar analíticamente. Uno debe asumir lo siguiente
- el parámetro de relajación es apropiado:
- Matriz de iteración de Jacobi tiene solo valores propios reales
- El método de Jacobi es convergente:
- existe una solución única: .
Entonces, la tasa de convergencia se puede expresar como [2]
donde el parámetro de relajación óptimo viene dado por
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 suposición inicial a la solución repetir hasta convergencia para i desde 1 hasta n do para j desde 1 hasta n hacer si j ≠ i entonces end if end ( j -loop) final ( i -loop) comprobar si se alcanza la convergenciafin (repetir)
- Nota
- también se puede escribir , ahorrando así una multiplicación en cada iteración del bucle for externo.
Ejemplo
Se nos presenta el sistema lineal
Para resolver las ecuaciones, elegimos un factor de relajación. y un vector de conjetura inicial . Según el algoritmo de sobre-relajación sucesiva, se obtiene la siguiente tabla, que representa una iteración ejemplar con aproximaciones, que idealmente, pero no necesariamente, encuentra la solución exacta, (3, -2, 2, 1) , en 38 pasos.
Iteración | ||||
---|---|---|---|---|
1 | 0,25 | -2,78125 | 1.6289062 | 0.5152344 |
2 | 1.2490234 | -2,2448974 | 1.9687712 | 0.9108547 |
3 | 2.070478 | -1.6696789 | 1.5904881 | 0,76172125 |
... | ... | ... | ... | ... |
37 | 2.9999998 | -2,0 | 2.0 | 1.0 |
38 | 3,0 | -2,0 | 2.0 | 1.0 |
A continuación se ofrece una implementación simple del algoritmo en Common Lisp.
;; Establezca el formato de coma flotante predeterminado en "long-float" para ;; Asegurar el funcionamiento correcto en una gama más amplia de números. ( setf * read-default-float-format * 'long-float )( defparameter + NÚMERO-MÁXIMO-DE-ITERACIONES + 100 "El número de iteraciones más allá del cual el algoritmo debe dejar de funcionar, independientemente de su solución actual. Un número mayor de iteraciones puede proporcionar un resultado más preciso, pero impone requisitos de rendimiento más altos ". )( declamar ( tipo ( entero 0 * ) + NÚMERO-MÁXIMO-DE-ITERACIONES + ))( defun get-errors ( computed-solution exact-solution ) "Para cada componente del vector COMPUTED-SOLUTION, recupera su error con respecto al vector EXACT-SOLUTION esperado, devolviendo un vector de valores de error. --- Mientras que ambos ingresan Los vectores deben tener el mismo tamaño, esta condición no está marcada y el más corto de los dos determina el número de elementos del vector de salida . --- La fórmula establecida es la siguiente: Sea resultVectorSize = min (computedSolution.length, exactSolution.length) Let resultVector = nuevo vector de resultVectorSize Para i de 0 a (resultVectorSize - 1) resultVector [i] = exactSolution [i] - computedSolution [i] Devuelve resultVector " ( declare ( type ( vector number * ) computed-solution )) ( declare ( tipo ( número de vector * ) solución-exacta )) ( mapa ' ( número de vector * ) #' - solución-exacta-solución calculada )) ( defun es-convergente ( errores & clave ( tolerancia a errores 0,001 )) "Comprueba si se alcanza la convergencia con respecto al vector ERRORES que registra la discrepancia entre el vector calculado y la solución exacta. --- La convergencia se cumple si y sólo si cada componente de error absoluto es menor o igual que el ERROR-TOLERANCIA, es decir: Para todo e en ERRORES, se mantiene: abs (e) <= errorTolerancia. " ( declare ( tipo ( número de vector * ) errores )) ( declare ( tipo número error-tolerancia )) ( flet (( error-es-aceptable ( error ) ( declare ( tipo número error )) ( <= ( error abs ) error-tolerancia ))) ( cada # ' error-es -acceptable errores ))) ( defun make-zero-vector ( size ) "Crea y devuelve un vector de SIZE con todos los elementos establecidos en 0." ( declare ( type ( integer 0 * ) size )) ( make-array size : initial-element 0.0 : tipo de elemento 'número ))( defun sucesivo-sobre-relajación ( A b omega & clave ( phi ( make-zero-vector ( longitud b ))) ( convergence-check # ' ( lambda ( iteration phi ) ( declare ( ignore phi )) ( > = iteración + MÁXIMO-NÚMERO-DE-ITERACIONES + )))) "Implementa el método de sobre-relajación sucesiva (SOR), aplicado sobre las ecuaciones lineales definidas por la matriz A y el vector del lado derecho B, empleando el factor de relajación OMEGA, devolviendo el vector de solución calculado. --- El primer paso del algoritmo, la elección de un PHI de suposición inicial, está representado por el parámetro de palabra clave opcional PHI, que por defecto es un vector cero de la misma estructura que B. Si se proporciona, este vector será En cualquier caso, el vector PHI constituye el valor de resultado de la función. --- La condición de terminación es implementada por CONVERGENCE-CHECK, un predicado opcional lambda (iteration phi) => generalized-boolean que devuelve T, que significa el inmediato terminación, al lograr la convergencia, o NIL, señalización continua funcionamiento uant, de lo contrario. En su configuración predeterminada, el CONVERGENCE-CHECK simplemente acepta la ascensión de la iteración al `` + MAXIMUM-NUMBER-OF-ITERATIONS + '', ignorando la precisión lograda del vector PHI. " ( Declare ( type ( array number ( * * ) ) A )) ( declare ( type ( vector number * ) b )) ( declare ( type number omega )) ( declare ( type ( vector number * ) phi )) ( declare ( type ( function (( integer 1 * ) ( vector number * )) * ) convergence-check )) ( let (( n ( array-dimension A 0 ))) ( declare ( type ( integer 0 * ) n )) ( loop for iteration from 1 by 1 do ( loop for i desde 0 debajo de n por 1 do ( let (( rho 0 )) ( declare ( escriba el número rho )) ( bucle para j desde 0 debajo de n por 1 do ( when ( / = j i ) ( let (( a [ij] ( aref a i j )) ( phi [j] ( aref phi j ))) ( incf rho ( * un [ij] phi [j] ))))) ( setf ( aref phi i ) ( + ( * ( - 1 omega ) ( aref phi i )) ( * ( / omega ( aref A i i )) ( - ( aref b i ) rho )))))) ( formato T "~ & ~ d. Solución = ~ a" iteración phi ) ;; Compruebe si se alcanza la convergencia. ( cuando ( funca ll iteración de verificación de convergencia phi ) ( retorno )))) ( el ( número de vector * ) phi )) ;; Convoca la función con los parámetros ejemplares. ( Dejar que (( A ( make-array ( lista 4 4 ) : iniciales-contents ' (( 4 -1 -6 0 ) ( -5 -4 10 8 ) ( 0 9 4 -2 ) ( 1 0 -7 5 ) ))) ( b ( vector 2 21 -12 -6 )) ( omega 0,5 ) ( exacta-solución ( vector 3 -2 2 1 ))) ( sucesiva-sobre-relajación A b omega : convergencia-check #' ( lambda ( iteración phi ) ( declare ( type ( integer 0 * ) iteration )) ( declare ( type ( vector number * ) phi )) ( let (( errors ( get-errors phi exact-solution ))) ( declare ( type ( vector número * ) errores )) ( formato T "~ & ~ d. errores = ~ a" errores de iteración ) ( o ( errores convergentes : tolerancia de error 0.0 ) ( > = iteración + NÚMERO-MÁXIMO-DE-ITERACIONES + )) ))))
Una implementación Python simple del pseudocódigo proporcionado anteriormente.
importar numpy como npdef sor_solver ( A , b , omega , initial_guess , convergence_criteria ): "" " Esta es una implementación del pseudocódigo proporcionado en el artículo de Wikipedia. Argumentos: A: matriz numpy nxn. b: vector numpy dimensional n. omega: relajación factor. initial_guess: una suposición de solución inicial para que el solucionador comience. convergence_criteria: la máxima discrepancia aceptable para considerar la solución actual como adecuada. Devuelve: phi: vector de solución de dimensión n. "" " paso = 0 phi = initial_guess [: ] residual = np . linalg . norma ( np . matmul ( A , phi ) - b ) # residual inicial mientras residual > convergence_criteria : para i en rango ( A . forma [ 0 ]): sigma = 0 para j en rango ( A . forma [ 1 ]): si j ! = i : sigma + = A [ i , j ] * phi [ j ] phi [ i ] = ( 1 - omega ) * phi [ i ] + ( omega / A [ i , i ]) * ( b [ i ] - sigma ) residual = np . linalg . norma ( np . matmul ( A , phi ) - b ) paso + = 1 print ( "Paso {} Residual: {: 10.6g} " . formato ( paso , residual )) return phi# Un caso de ejemplo que refleja el del artículo de Wikipedia residual_convergence = 1e-8 omega = 0.5 # Factor de relajaciónA = np . matriz ([[ 4 , - 1 , - 6 , 0 ], [ - 5 , - 4 , 10 , 8 ], [ 0 , 9 , 4 , - 2 ], [ 1 , 0 , - 7 , 5 ]])b = np . matriz ([ 2 , 21 , - 12 , - 6 ])initial_guess = np . ceros ( 4 )phi = sor_solver ( A , b , omega , initial_guess , residual_convergence ) print ( phi )
Relajación excesiva sucesiva simétrica
La versión para matrices simétricas A , en la que
se conoce como sobre-relajación sucesiva simétrica , o ( SSOR ), en el que
y el método iterativo es
Los métodos SOR y SSOR se acreditan a David M. Young Jr. .
Otras aplicaciones del método
Se puede utilizar una técnica similar para cualquier método iterativo. Si la iteración original tuviera la forma
entonces la versión modificada usaría
Sin embargo, la formulación presentada anteriormente, utilizada para resolver sistemas de ecuaciones lineales, no es un caso especial de esta formulación si se considera que x es el vector completo. Si se usa esta formulación en su lugar, la ecuación para calcular el siguiente vector se verá como
dónde . Valores de se utilizan para acelerar la convergencia de un proceso de convergencia lenta, mientras que los valores de se utilizan a menudo para ayudar a establecer la convergencia de un proceso iterativo divergente o acelerar la convergencia de un proceso de sobreimpulso .
Hay varios métodos que establecen de forma adaptativa el parámetro de relajación. basado en el comportamiento observado del proceso convergente. Por lo general, ayudan a alcanzar una convergencia súper lineal para algunos problemas, pero fallan para otros.
Ver también
Notas
- ^ Young, David M. (1 de mayo de 1950), Métodos iterativos para resolver ecuaciones en diferencias parciales de tipo elíptico (PDF) , Tesis de doctorado, Universidad de Harvard , consultado el 15 de junio de 2009
- ^ Hackbusch, Wolfgang (2016). "4.6.2". Solución iterativa de grandes sistemas dispersos de ecuaciones | SpringerLink . Ciencias Matemáticas Aplicadas. 95 . doi : 10.1007 / 978-3-319-28483-5 . ISBN 978-3-319-28481-1.
Referencias
- Este artículo incorpora texto del artículo Successive_over-relajación_method _-_ SOR en CFD-Wiki que está bajo la licencia GFDL .
- Abraham Berman, Robert J. Plemmons , Matrices no negativas en las ciencias matemáticas , 1994, SIAM. ISBN 0-89871-321-8 .
- Black, Noel y Moore, Shirley. "Método de sobrerelajación sucesiva" . MathWorld .
- A. Hadjidimos, sobrerelajación sucesiva (SOR) y métodos relacionados , Journal of Computational and Applied Mathematics 123 (2000), 177-199.
- Yousef Saad , Métodos iterativos para sistemas lineales dispersos , primera edición, PWS, 1996.
- La copia de Netlib de "Plantillas para la solución de sistemas lineales", de Barrett et al.
- Richard S. Varga 2002 Matrix Iterative Analysis , Segunda ed. (de la edición de Prentice Hall de 1962), Springer-Verlag.
- David M. Young Jr. Solución iterativa de grandes sistemas lineales , Academic Press, 1971. (reimpreso por Dover, 2003)
enlaces externos
- Módulo para el Método SOR
- Solucionador de sistema lineal tridiagonal basado en SOR, en C ++