Subespacio de Krylov

Subespacio lineal generado a partir de un vector sobre el que actúa una serie de potencias de una matriz

En álgebra lineal , el subespacio de Krylov de orden r generado por una matriz A de n por n y un vector b de dimensión n es el subespacio lineal generado por las imágenes de b bajo las primeras r potencias de A (empezando por ), es decir, ^{[1] [2]} ${\displaystyle A^{0}=I}$

${\displaystyle {\mathcal {K}}_{r}(A,b)=\operatorname {span} \,\{b,Ab,A^{2}b,\ldots ,A^{r-1}b\}.}$

Fondo

El concepto recibe su nombre del matemático aplicado e ingeniero naval ruso Alexei Krylov , quien publicó un artículo sobre el concepto en 1931. ^[3]

Propiedades

• ${\displaystyle {\mathcal {K}}_{r}(A,b),A\,{\mathcal {K}}_{r}(A,b)\subset {\mathcal {K}}_{r+1}(A,b)}$.
• Sean . Entonces son linealmente independientes a menos que , para todos , y . Por lo tanto, es la dimensión máxima de los subespacios de Krylov . ${\displaystyle r_{0}=\operatorname {dim} \operatorname {span} \,\{b,Ab,A^{2}b,\ldots \}}$ ${\displaystyle \{b,Ab,A^{2}b,\ldots ,A^{r-1}b\}}$ ${\displaystyle r>r_{0}}$ ${\displaystyle {\mathcal {K}}_{r}(A,b)\subset {\mathcal {K}}_{r_{0}}(A,b)}$ ${\displaystyle r}$ ${\displaystyle \operatorname {dim} {\mathcal {K}}_{r_{0}}(A,b)=r_{0}}$ ${\displaystyle r_{0}}$ ${\displaystyle {\mathcal {K}}_{r}(A,b)}$
• La dimensión máxima satisface y . ${\displaystyle r_{0}\leq 1+\operatorname {rank} A}$ ${\displaystyle r_{0}\leq n}$
• Consideremos , donde es el polinomio mínimo de . Tenemos . Además, para cualquier , existe un para el cual este límite es estricto, es decir . ${\displaystyle \dim \operatorname {span} \,\{I,A,A^{2},\ldots \}=\deg \,p(A)}$ ${\displaystyle p(A)}$ ${\displaystyle A}$ ${\displaystyle r_{0}\leq \deg \,p(A)}$ ${\displaystyle A}$ ${\displaystyle b}$ ${\displaystyle r_{0}=\deg \,p(A)}$
• ${\displaystyle {\mathcal {K}}_{r}(A,b)}$es un submódulo cíclico generado por el módulo de torsión , donde es el espacio lineal en . ${\displaystyle b}$ ${\displaystyle k[x]}$ ${\displaystyle (k^{n})^{A}}$ ${\displaystyle k^{n}}$ ${\displaystyle k}$
• ${\displaystyle k^{n}}$se puede descomponer como la suma directa de los subespacios de Krylov. ^{[ aclaración necesaria ]}

Usar

Los subespacios de Krylov se utilizan en algoritmos para encontrar soluciones aproximadas a problemas de álgebra lineal de alta dimensión . ^[2] Muchas pruebas de sistemas dinámicos lineales en teoría de control , especialmente aquellas relacionadas con la controlabilidad y la observabilidad , implican la comprobación del rango del subespacio de Krylov. Estas pruebas son equivalentes a encontrar el lapso de los gramianos asociados con los mapas de sistema/salida, de modo que los subespacios incontrolables e inobservables son simplemente el complemento ortogonal del subespacio de Krylov. ^[4]

Los métodos iterativos modernos , como la iteración de Arnoldi , se pueden utilizar para encontrar uno (o unos pocos) valores propios de matrices dispersas grandes o para resolver grandes sistemas de ecuaciones lineales. Intentan evitar las operaciones matriz-matriz, sino que multiplican los vectores por la matriz y trabajan con los vectores resultantes. Comenzando con un vector , se calcula , luego se multiplica ese vector por para encontrar y así sucesivamente. Todos los algoritmos que funcionan de esta manera se conocen como métodos del subespacio de Krylov; se encuentran entre los métodos más exitosos actualmente disponibles en álgebra lineal numérica. Estos métodos se pueden utilizar en situaciones en las que existe un algoritmo para calcular la multiplicación matriz-vector sin que haya una representación explícita de , lo que da lugar a métodos sin matriz . ${\displaystyle b}$ ${\displaystyle Ab}$ ${\displaystyle A}$ ${\displaystyle A^{2}b}$ ${\displaystyle A}$

Asuntos

Debido a que los vectores generalmente se vuelven casi linealmente dependientes pronto debido a las propiedades de la iteración de potencia , los métodos que se basan en el subespacio de Krylov con frecuencia involucran algún esquema de ortogonalización , como la iteración de Lanczos para matrices hermíticas o la iteración de Arnoldi para matrices más generales.

Métodos existentes

Los métodos de subespacio de Krylov más conocidos son el gradiente conjugado , IDR(s) (reducción de dimensión inducida), GMRES (residuo mínimo generalizado), BiCGSTAB (gradiente biconjugado estabilizado), QMR (residuo cuasi mínimo), TFQMR (QMR sin transposición) y MINRES (método de residuo mínimo).

Véase también

• Método iterativo , que tiene una sección sobre métodos del subespacio de Krylov

Referencias

1. Nocedal, Jorge; Wright, Stephen J. (2006). Optimización numérica . Serie Springer en investigación de operaciones e ingeniería financiera (2.ª ed.). Nueva York, NY: Springer. p. 108. ISBN 978-0-387-30303-1.
2. Simoncini, Valeria (2015), "Subespacios de Krylov", en Nicholas J. Higham; et al. (eds.), The Princeton Companion to Applied Mathematics , Princeton University Press, págs. 113-114
3. Krylov, AN (1931). "О численном решении уравнения, которым в технических вопросах определяются частоты малых колебаний материальных систем" [Sobre la solución numérica de ecuaciones por las cuales se determinan en técnica Problemas de las frecuencias de pequeñas vibraciones de sistemas materiales]. Izvestiia Akademii Nauk SSSR (en ruso). 7 (4): 491–539.
4. Hespanha, Joao (2017), Teoría de sistemas lineales , Princeton University Press

Lectura adicional

• Nevanlinna, Olavi (1993). Convergencia de iteraciones para ecuaciones lineales . Lecciones de matemáticas en la Escuela Politécnica Federal de Zúrich. Basilea: Birkhäuser Verlag. pp. viii+177 pp. ISBN 3-7643-2865-7.Señor 1217705  .
• Saad, Yousef (2003). Métodos iterativos para sistemas lineales dispersos (2.ª ed.). SIAM . ISBN 0-89871-534-2.OCLC 51266114  .
• Gerard Meurant y Jurjen Duintjer Tebbens: ”Métodos de Krylov para sistemas lineales no simétricos: de la teoría a los cálculos”, Springer Series in Computational Mathematics, vol. 57, (octubre de 2020). ISBN 978-3-030-55250-3 , url=https://doi.org/10.1007/978-3-030-55251-0. 
• Iman Farahbakhsh: "Métodos del subespacio de Krylov con aplicación en solucionadores de flujo de fluidos incompresibles", Wiley, ISBN 978-1119618683 (septiembre de 2020).