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, mediante diferencias finitas. [4] [3] [2]
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 solución. Estos no deben confundirse con los métodos de relajación en la 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 uniforme de valor real en los números reales, su segunda derivada se puede aproximar mediante:
Usar esto en ambas dimensiones para una función φ de dos argumentos en el punto ( x , y ), y despejar φ ( x , y ), da como resultado:
Para aproximar la solución de la ecuación de Poisson:
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 de la cuadrícula interior, y luego realiza repetidamente la asignación φ: = φ * en los puntos interiores, donde φ * se define por:
hasta la convergencia. [3] [2]
El método, esbozado aquí para dos dimensiones, [3] [2] se generaliza 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 preacondicionador 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 espacio doble 2 h , y usar esa solución con valores interpolados para los otros puntos de la cuadrícula como asignación inicial. Entonces, esto también se puede hacer de forma recursiva para el cálculo más grueso. [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 simple.
- 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 de redes múltiples
Notas
- ^ a b Ortega, JM; Rheinboldt, WC (2000). Solución iterativa de ecuaciones no lineales en varias variables . Clásicos de Matemática Aplicada. 30 (Reimpresión de 1970 Academic Press ed.). Filadelfia, PA: Sociedad de Matemáticas Industriales y Aplicadas (SIAM). págs. xxvi + 572. ISBN 0-89871-461-3. Señor 1744713 .
- ^ a b c d Richard S. Varga 2002 Matrix Iterative Analysis , Segunda ed. (de la edición de Prentice Hall de 1962), Springer-Verlag.
- ^ a b c d David M. Young, Jr. Solución iterativa de grandes sistemas lineales , Academic Press, 1971. (reimpreso por Dover, 2003)
- ^ a b Abraham Berman, Robert J. Plemmons , Matrices no negativas en las ciencias matemáticas , 1994, SIAM. ISBN 0-89871-321-8 .
- ^ 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 .
- ^ Goffin, J.-L. (1980). "El método de relajación para resolver sistemas de desigualdades lineales". Matemáticas. Oper. Res . 5 (3): 388–414. doi : 10.1287 / moor.5.3.388 . JSTOR 3689446 . Señor 0594854 .
- ^ a b 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. Señor 0868279 . (2008 Segunda ed., En francés: Programmation mathématique: Théorie et algorítmes . Ediciones Tec & Doc, París, 2008. xxx + 711 pp.).
- ^ a b Yousef Saad , Métodos iterativos para sistemas lineales dispersos , primera edición, PWS, 1996.
- ^ William L. Briggs, Van Emden Henson y Steve F. McCormick (2000), A Multigrid Tutorial Archivado 2006-10-06 en Wayback Machine (2nd ed.), Philadelphia: Society for Industrial and Applied Mathematics , 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 de Matemática Aplicada. 30 (Reimpresión de 1970 Academic Press ed.). Filadelfia, PA: Sociedad de Matemáticas Industriales y Aplicadas (SIAM). págs. xxvi + 572. ISBN 0-89871-461-3. Señor 1744713 .
- Presione, 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 , primera edición, PWS, 1996.
- 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)
Otras lecturas
- 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 electromagnetismo . Boca Ratón: CRC Pres.
- P.-B. Zhou (1993). Análisis numérico de campos electromagnéticos . Nueva York: Springer.