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]

Se desarrollaron métodos de relajación para resolver grandes sistemas lineales dispersos , que surgieron como discretizaciones en diferencias finitas de ecuaciones diferenciales . ^{[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 la frontera , en los que los valores de la función solución se especifican en la frontera 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 potencial.

Cuando φ es una función uniforme de valores reales en 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})\,.}$

Usar esto en ambas dimensiones para una función φ de dos argumentos en el punto ( x , y ) y resolver para φ ( x , y ) da como resultado:

${\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 φ* está definido 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 generaliza fácilmente a otros números de dimensiones.

Convergencia y aceleración

Si bien el método converge en condiciones generales, normalmente avanza más lentamente que los métodos competidores. No obstante, el estudio de los métodos de relajación sigue siendo una parte central del álgebra lineal, porque las transformaciones de la teoría de la relajación proporcionan excelentes precondiciones 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 de redes múltiples para acelerar los métodos. Primero se puede calcular una aproximación en una cuadrícula más gruesa (generalmente el doble espacio de 2 h ) y usar esa solución con valores interpolados para los otros puntos de la cuadrícula como asignación inicial. Luego, esto también se puede hacer de forma recursiva para realizar un cálculo más aproximado. ^{[8] [9]}

Ver también

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

Notas

1. Ortega, JM; Rheinboldt, WC (2000). Solución iterativa de ecuaciones no lineales en varias variables . Clásicos en Matemática Aplicada. vol. 30 (Reimpresión de la edición de Academic Press de 1970). Filadelfia, PA: Sociedad de Matemáticas Industriales y Aplicadas (SIAM). págs.xxvi+572. ISBN 0-89871-461-3. SEÑOR  1744713.
2. Richard S. Varga 2002 Análisis iterativo matricial , segunda ed. (de la edición de Prentice Hall de 1962), Springer-Verlag.
3. David M. Young, Jr. Solución iterativa de grandes sistemas lineales , 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 dispersión para programación lineal)". Programación lineal . Nueva York: John Wiley & Sons Inc. págs. 453–464. ISBN 0-471-09725-X. SEÑOR  0720547.
6. Goffin, J.-L. (1980). "El método de relajación para la resolución de 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. SEÑOR  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 (1983 París: Dunod)). Chichester: una publicación de Wiley-Interscience. 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 de redes 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 . Clásicos en Matemática Aplicada. vol. 30 (Reimpresión de la edición de Academic Press de 1970). Filadelfia, PA: Sociedad de Matemáticas Industriales y Aplicadas (SIAM). págs.xxvi+572. ISBN 0-89871-461-3. SEÑOR  1744713.
• Prensa, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Sección 18.3. Métodos de relajación". Recetas numéricas: el arte de la informática 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 Análisis iterativo matricial , 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)

Lectura adicional

• Southwell, RV (1940) Métodos de relajación en ciencias de la ingeniería . Prensa de la Universidad de Oxford, Oxford.
• Southwell, RV (1946) Métodos de relajación en física teórica . Prensa de la Universidad de Oxford, 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 Electromagnética . Boca Ratón: CRC Pres.
• P.-B. Zhou (1993). Análisis Numérico de Campos Electromagnéticos . Nueva York: Springer.
• P. Grivet, PW Hawkes, A. Septier (1972). Óptica Electrónica, 2ª edición . Prensa de Pérgamo. ISBN 9781483137858 . 
• DWO Heddle (2000). Sistemas de lentes electrostáticas, 2.ª edición . Prensa CRC. ISBN 9781420034394 . 
• Erwin Kasper (2001). Avances en imágenes y física electrónica, vol. 116, Cálculo de campo numérico para óptica de partículas cargadas . Prensa académica. ISBN 978-0-12-014758-8 .