Relajación (método iterativo)

En matemáticas numéricas , los métodos de relajación son métodos iterativos para resolver sistemas de ecuaciones , incluidos los sistemas no lineales. ^[1]

Los métodos de relajación se desarrollaron para resolver grandes sistemas lineales dispersos , que surgieron como discretizaciones de ecuaciones diferenciales en diferencias finitas . ^{[2] [3]} También se utilizan para la solución de ecuaciones lineales para problemas de mínimos cuadrados lineales ^[4] y también para sistemas de desigualdades lineales, como los que surgen en la programación lineal . ^{[5] [6] [7]} También se han desarrollado para resolver sistemas de ecuaciones no lineales. ^[1]

Los métodos de relajación son importantes especialmente en la solución de sistemas lineales utilizados para modelar ecuaciones diferenciales parciales elípticas , como la ecuación de Laplace y su generalización, la ecuación de Poisson . Estas ecuaciones describen problemas de valores en el borde , en los que los valores de la función solución se especifican en el borde de un dominio; el problema es calcular una solución también en su interior. Los métodos de relajación se utilizan para resolver las ecuaciones lineales resultantes de una discretización de la ecuación diferencial, por ejemplo, por diferencias finitas. ^{[2] [3] [4]}

La relajación iterativa de soluciones se denomina comúnmente suavizado porque con ciertas ecuaciones, como la ecuación de Laplace , se asemeja a la aplicación repetida de un filtro de suavizado local al vector de solución. Estos no deben confundirse con los métodos de relajación en optimización matemática , que aproximan un problema difícil mediante un problema más simple cuya solución "relajada" proporciona información sobre la solución del problema original. ^[7]

Problema modelo de la teoría del potencial

Cuando φ es una función real suave sobre los números reales, su segunda derivada se puede aproximar mediante:

${\displaystyle {\frac {d^{2}\varphi (x)}{{dx}^{2}}}={\frac {\varphi (x{-}h)-2\varphi (x)+\varphi (x{+}h)}{h^{2}}}\,+\,{\mathcal {O}}(h^{2})\,.}$

Usando esto en ambas dimensiones para una función φ de dos argumentos en el punto ( x , y ), y resolviendo para φ( x , y ), el resultado es:

${\displaystyle \varphi (x,y)={\tfrac {1}{4}}\left(\varphi (x{+}h,y)+\varphi (x,y{+}h)+\varphi (x{-}h,y)+\varphi (x,y{-}h)\,-\,h^{2}{\nabla }^{2}\varphi (x,y)\right)\,+\,{\mathcal {O}}(h^{4})\,.}$

Para aproximar la solución de la ecuación de Poisson:

${\displaystyle {\nabla }^{2}\varphi =f\,}$

numéricamente en una cuadrícula bidimensional con espaciado de cuadrícula h , el método de relajación asigna los valores dados de la función φ a los puntos de la cuadrícula cerca del límite y valores arbitrarios a los puntos interiores de la cuadrícula, y luego realiza repetidamente la asignación φ := φ* en los puntos interiores, donde φ* se define por:

${\displaystyle \varphi ^{*}(x,y)={\tfrac {1}{4}}\left(\varphi (x{+}h,y)+\varphi (x,y{+}h)+\varphi (x{-}h,y)+\varphi (x,y{-}h)\,-\,h^{2}f(x,y)\right)\,,}$

hasta la convergencia. ^{[2] [3]}

El método ^{[2] [3]} se puede generalizar fácilmente a otros números de dimensiones.

Convergencia y aceleración

Si bien el método converge en condiciones generales, por lo general avanza más lentamente que los métodos de la competencia. No obstante, el estudio de los métodos de relajación sigue siendo una parte fundamental del álgebra lineal, porque las transformaciones de la teoría de la relajación proporcionan excelentes precondicionadores para nuevos métodos. De hecho, la elección del precondicionador suele ser más importante que la elección del método iterativo. ^[8]

Se pueden utilizar métodos multigrid para acelerar los métodos. Primero se puede calcular una aproximación en una cuadrícula más gruesa (normalmente, el espaciado doble 2 h ) y utilizar esa solución con valores interpolados para los otros puntos de la cuadrícula como asignación inicial. Esto también se puede hacer de forma recursiva para el cálculo más grueso. ^{[8] [9]}

Véase también

• En sistemas lineales, las dos clases principales de métodos de relajación son los métodos iterativos estacionarios y los métodos del subespacio de Krylov más generales .
• El método Jacobi es un método de relajación sencillo.
• El método de Gauss-Seidel es una mejora del método de Jacobi.
• La sobrerelajación sucesiva se puede aplicar a cualquiera de los métodos de Jacobi y Gauss-Seidel para acelerar la convergencia.
• Métodos multigrid

Notas

1. Ortega, JM; Rheinboldt, WC (2000). Solución iterativa de ecuaciones no lineales en varias variables . Classics in Applied Mathematics. Vol. 30 (reimpresión de la edición de 1970 de Academic Press). Filadelfia, PA: Society for Industrial and Applied Mathematics (SIAM). pp. xxvi+572. ISBN 0-89871-461-3.Señor 1744713  .
2. Richard S. Varga 2002 Matrix Iterative Analysis , segunda edición (de la edición de Prentice Hall de 1962), Springer-Verlag.
3. David M. Young, Jr. Solución iterativa de sistemas lineales grandes , Academic Press, 1971. (reimpreso por Dover, 2003)
4. Abraham Berman, Robert J. Plemmons , Matrices no negativas en las ciencias matemáticas , 1994, SIAM. ISBN 0-89871-321-8 . 
5. Murty, Katta G. (1983). "16 Métodos iterativos para desigualdades lineales y programas lineales (especialmente 16.2 Métodos de relajación y 16.4 Algoritmos SOR iterativos que preservan la escasez para programación lineal)". Programación lineal . Nueva York: John Wiley & Sons Inc. pp. 453–464. ISBN 0-471-09725-X.Sr. 0720547  .
6. Goffin, J.-L. (1980). "El método de relajación para resolver sistemas de desigualdades lineales". Matemáticas de la investigación de operaciones . 5 (3): 388–414. doi :10.1287/moor.5.3.388. JSTOR  3689446. MR  0594854.
7. Minoux, M. (1986). Programación matemática: teoría y algoritmos . Egon Balas (prólogo) (traducido por Steven Vajda de la edición francesa de Dunod (1983, París). Chichester: A Wiley-Interscience Publication. John Wiley & Sons, Ltd., págs. xxviii+489. ISBN 0-471-90170-9. MR  0868279. (2008 Segunda ed., en francés: Programmation mathématique: Théorie et algoritmos . Ediciones Tec & Doc, París, 2008. xxx+711 págs. .).
8. Yousef Saad , Métodos iterativos para sistemas lineales dispersos , 1.ª edición, PWS, 1996.
9. William L. Briggs, Van Emden Henson y Steve F. McCormick (2000), Un tutorial sobre cuadrículas múltiples Archivado el 6 de octubre de 2006 en Wayback Machine (2.ª ed.), Filadelfia: Sociedad de Matemáticas Industriales y Aplicadas , ISBN 0-89871-462-1 . 

Referencias

• Abraham Berman, Robert J. Plemmons, Matrices no negativas en las ciencias matemáticas , 1994, SIAM. ISBN 0-89871-321-8 . 
• Ortega, JM; Rheinboldt, WC (2000). Solución iterativa de ecuaciones no lineales en varias variables . Classics in Applied Mathematics. Vol. 30 (reimpresión de la edición de 1970 de Academic Press). Filadelfia, PA: Society for Industrial and Applied Mathematics (SIAM). pp. xxvi+572. ISBN. 0-89871-461-3.Señor 1744713  .
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Sección 18.3. Métodos de relajación". Recetas numéricas: el arte de la computación científica (3.ª ed.). Nueva York: Cambridge University Press. ISBN 978-0-521-88068-8.
• Yousef Saad , Métodos iterativos para sistemas lineales dispersos , 1.ª edición, PWS, 1996.
• Richard S. Varga 2002 Matrix Iterative Analysis , segunda edición (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)

Lectura adicional

• Southwell, RV (1940) Métodos de relajación en la ciencia de la ingeniería . Oxford University Press, Oxford.
• Southwell, RV (1946) Métodos de relajación en física teórica . Oxford University Press, Oxford.
• John. D. Jackson (1999). Electrodinámica clásica . Nueva Jersey: Wiley. ISBN 0-471-30932-X.
• MNO Sadiku (1992). Técnicas numéricas en electromagnetismo . Boca Raton: CRC Pres.
• P.-B. Zhou (1993). Análisis numérico de campos electromagnéticos . Nueva York: Springer.
• P. Grivet, P. W. Hawkes, A. Septier (1972). Óptica electrónica, 2.ª edición . Pergamon Press. ISBN 9781483137858 . 
• DWO Heddle (2000). Sistemas de lentes electrostáticas, 2.ª edición . CRC Press. ISBN 9781420034394 . 
• Erwin Kasper (2001). Avances en imágenes y física electrónica, vol. 116, Cálculo numérico del campo para óptica de partículas cargadas . Academic Press. ISBN 978-0-12-014758-8 .