Métodos iterativos
Los métodos iterativos resuelven grandes sistemas lineales (y no lineales) generando una secuencia de aproximaciones sucesivamente mejores, aprovechando la escasez para manejar problemas demasiado grandes para la factorización directa.
Definition
Los métodos iterativos son algoritmos que aproximan la solución de un sistema de ecuaciones produciendo una secuencia de iteraciones que convergen a la solución, en lugar de calcularla en un número fijo y finito de operaciones como lo hace un método directo.
Scope
Esta área cubre las iteraciones estacionarias clásicas, los métodos de subespacio de Krylov, como los algoritmos de gradiente conjugado y GMRES, los métodos multigrid y las técnicas de precondicionamiento que aceleran la convergencia; trata la teoría de la convergencia, el papel del espectro y el número de condición, y los cálculos sin matriz que explotan la escasez y que hacen que estos métodos sean escalables.
Sub-topics
Core questions
- ¿Cuándo son preferibles los métodos iterativos a los métodos directos y por qué la escasez los favorece?
- ¿Cómo construyen los métodos de subespacio de Krylov aproximaciones óptimas a partir únicamente de productos matriz-vector?
- ¿Cómo rige el espectro o el número de condición de la matriz la velocidad de convergencia?
- ¿Cómo transforman el precondicionamiento y el multigrid una iteración de convergencia lenta en una rápida?
Key theories
- Aproximación de subespacio de Krylov
- Los métodos de Krylov buscan la mejor aproximación a la solución dentro del subespacio generado por productos sucesivos matriz-vector aplicados al residuo, requiriendo solo la acción de la matriz y convergiendo en un número de pasos regido por las propiedades espectrales de la matriz.
- Convergencia y condicionamiento
- La tasa de convergencia de los solucionadores iterativos depende de la distribución de valores propios y del número de condición de la matriz (precondicionada); la agrupación de valores propios o la reducción del número de condición mediante el precondicionamiento acelera drásticamente la convergencia.
- Aceleración multinivel
- Los métodos multigrid combinan el suavizado en mallas finas con correcciones de malla gruesa para eliminar componentes de error en cada escala, logrando tasas de convergencia independientes del tamaño del problema para muchos problemas elípticos.
Clinical relevance
Los métodos iterativos son indispensables para los enormes sistemas lineales dispersos que surgen de la discretización de ecuaciones diferenciales parciales en la simulación de ingeniería y física, así como en la optimización, el aprendizaje automático, el análisis de redes y la reconstrucción de imágenes; su bajo consumo de memoria y su operación sin matriz los convierten en el único enfoque factible cuando los sistemas alcanzan millones o miles de millones de incógnitas.
History
Los métodos de relajación clásicos fueron estudiados por Gauss, Seidel y, posteriormente, Southwell; el método del gradiente conjugado de Hestenes y Stiefel (1952) y el desarrollo de GMRES y otros métodos de Krylov, multigrid (Fedorenko, Brandt) y el precondicionamiento moderno a finales del siglo XX establecieron los solucionadores iterativos como el estándar para grandes sistemas dispersos.
Key figures
- Magnus Hestenes
- Eduard Stiefel
- Yousef Saad
- Achi Brandt
Related topics
Seminal works
- saad2003
- greenbaum1997
Frequently asked questions
- ¿Cuándo se debe utilizar un método iterativo en lugar de uno directo?
- Los métodos iterativos se prefieren para sistemas muy grandes y dispersos donde una factorización directa requeriría una memoria prohibitiva debido al relleno. Solo necesitan aplicar la matriz a los vectores, por lo que explotan la escasez y se escalan a problemas con millones de incógnitas.
- ¿Por qué es tan importante el precondicionamiento?
- La velocidad de convergencia de los solucionadores iterativos depende en gran medida del espectro de la matriz. Un precondicionador transforma el sistema en uno equivalente con un espectro más favorable, a menudo convirtiendo una iteración impracticamente lenta en una de convergencia rápida.