Métodos del Subespacio de Krylov

Los métodos del subespacio de Krylov resuelven grandes sistemas lineales dispersos extrayendo la mejor aproximación del subespacio generado por productos repetidos matriz-vector, necesitando solo la acción de la matriz en lugar de sus entradas.

Definition

Un método del subespacio de Krylov es un solucionador iterativo que, en el m-ésimo paso, busca una solución aproximada en el subespacio de Krylov m-dimensional generado por el residuo y sus imágenes sucesivas bajo la matriz, eligiendo el iterado mediante una condición de proyección o minimización.

Scope

Este tema cubre el subespacio de Krylov y su construcción mediante los procesos de Arnoldi y Lanczos, el método del gradiente conjugado para sistemas simétricos definidos positivos, MINRES y GMRES para matrices simétricas indefinidas y generales, métodos de biorthogonalización como BiCGSTAB, y la teoría de convergencia que vincula el número de iteraciones con el espectro y el número de condición.

Core questions

• ¿Qué es el subespacio de Krylov y cómo se construye una base ortonormal para él de forma estable?
• ¿Por qué el método del gradiente conjugado es óptimo y de recurrencia corta para sistemas simétricos definidos positivos?
• ¿Cómo maneja GMRES los sistemas no simétricos generales y por qué requiere un almacenamiento creciente?
• ¿Cómo determinan las propiedades espectrales de la matriz la tasa de convergencia?

Key theories

Método del gradiente conjugado

Para sistemas simétricos definidos positivos, el método del gradiente conjugado minimiza la norma energética del error sobre el subespacio de Krylov utilizando una recurrencia corta de tres términos, convergiendo en a lo sumo n pasos en aritmética exacta y mucho más rápido cuando los valores propios están agrupados.

GMRES y el proceso de Arnoldi

Para matrices generales, GMRES utiliza el proceso de Arnoldi para construir una base de Krylov ortonormal y minimiza la norma residual sobre el subespacio, pero debido a que no existe una recurrencia corta en general, debe almacenar todos los vectores base, lo que motiva las variantes reiniciadas.

Mechanisms

Cada método multiplica repetidamente un vector por la matriz para extender el subespacio de Krylov y ortogonaliza la nueva dirección contra las anteriores. Para matrices simétricas, el proceso de Lanczos produce una proyección tridiagonal y una recurrencia corta, por lo que los métodos del gradiente conjugado y MINRES solo necesitan unos pocos vectores de almacenamiento. Para matrices no simétricas, el proceso de Arnoldi produce una proyección de Hessenberg superior completa, y GMRES minimiza el residuo resolviendo un pequeño problema de mínimos cuadrados en cada paso, a costa de almacenar toda la base; el reinicio limita este costo. La convergencia está dictada por cuán favorablemente se distribuyen los valores propios, lo que el precondicionamiento está diseñado para mejorar.

Clinical relevance

Los métodos de Krylov, especialmente el gradiente conjugado precondicionado y GMRES, son los solucionadores estándar en códigos de simulación de elementos finitos y volúmenes finitos, optimización a gran escala y computación científica en general; su naturaleza sin matriz les permite resolver sistemas con millones o miles de millones de incógnitas que ningún método directo podría factorizar.

History

El método del gradiente conjugado fue introducido por Hestenes y Stiefel en 1952 y el proceso de Lanczos subyacente en 1950; su pleno poder como solucionadores iterativos fue reconocido en la década de 1970, y el desarrollo de GMRES por Saad y Schultz en 1986 y de métodos biorthogonales estabilizados extendió el enfoque a sistemas no simétricos generales.

Key figures

• Magnus Hestenes
• Eduard Stiefel
• Cornelius Lanczos
• Yousef Saad
• Henk van der Vorst

Seminal works

• saad2003
• greenbaum1997

Frequently asked questions

¿Por qué el método del gradiente conjugado solo funciona para matrices simétricas definidas positivas?

Su recurrencia corta y eficiente y su optimalidad en la norma energética dependen de que la matriz sea simétrica definida positiva. Para matrices simétricas indefinidas o no simétricas, se requieren diferentes métodos como MINRES o GMRES, generalmente con más almacenamiento o trabajo por paso.

¿Por qué GMRES necesita tanta memoria?

Para una matriz no simétrica general, no existe una recurrencia corta que mantenga la base de Krylov ortogonal, por lo que GMRES debe almacenar cada vector base para minimizar el residuo. El GMRES reiniciado limita la memoria descartando periódicamente la base, a costa de una convergencia más lenta.