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 abarcado por las imágenes de b bajo las primeras r potencias de A (a partir de ), que es, ^{[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 lleva el nombre del ingeniero naval y matemático aplicado 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)}$.
• Dejar . Entonces son linealmente independientes a menos que , para todos y . También lo 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}$
• Considere dónde está el polinomio mínimo de . Tenemos . Además, para cualquier , existe un límite 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. ^{[ se necesita aclaración ]}

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 la teoría del control , especialmente aquellas relacionadas con la controlabilidad y la observabilidad , implican verificar el rango del subespacio de Krylov. Estas pruebas equivalen a encontrar el intervalo de los Gramianos asociados con los mapas de sistema/salida, de modo que los subespacios incontrolables e inobservables sean 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 algunos) valores propios de matrices dispersas grandes o para resolver grandes sistemas de ecuaciones lineales. Intentan evitar las operaciones matriz-matriz, sino multiplicar vectores por la matriz y trabajar 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 denominan métodos subespaciales de Krylov; se encuentran entre los métodos más exitosos disponibles actualmente en álgebra lineal numérica. Estos métodos se pueden utilizar en situaciones donde existe un algoritmo para calcular la multiplicación matriz-vector sin que exista una representación explícita de , dando lugar a métodos libres de matrices . ${\displaystyle b}$ ${\displaystyle Ab}$ ${\displaystyle A}$ ${\displaystyle A^{2}b}$ ${\displaystyle A}$

Asuntos

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

Métodos existentes

Los métodos subespaciales 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 residual mínimo).

Ver también

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

Referencias

1. Nocedal, Jorge; Wright, Stephen J. (2006). Optimización numérica . Serie Springer sobre investigación operativa e ingeniería financiera (2ª ed.). Nueva York, Nueva York: Springer. pag. 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 la ecuación mediante la cual se determinan en problemas técnicos 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

Otras lecturas

• Nevanlinna, Olavi (1993). Convergencia de iteraciones para ecuaciones lineales . Conferencias de Matemáticas ETH Zürich. Basilea: Birkhäuser Verlag. págs. viii+177 págs. 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 subespaciales de Krylov con aplicación en solucionadores de flujo de fluidos incompresibles", Wiley, ISBN 978-1119618683 (septiembre de 2020).