Métodos de Krylov para sistemas lineales dispersos de ecuaciones. El teorema de Faber-Manteuffel

Abstract

El trabajo consta de cuatro capítulos, cuyo contenido pasamos a describir: 1. El primer capítulo motiva los métodos iterativos para la resolución de sistemas lineales, describiendo con carácter general la metodología de los métodos que en cada iteración determinan la aproximación a la solución mediante proyección sobre un subespacio apropiado. En los métodos de Krylov estos subespacios son precisamente subespacios de Krylov. La construcción de bases ortogonales de estos subespacios es el objeto del algoritmo de Arnoldi, para matrices no simétricas, y el algoritmo simétrico de Lanczos cuando la matriz del sistema es simétrica, para los que se dan las correspondientes interpretaciones matriciales. 2. Aunque en el Grado se estudia el método gradiente conjugado para sistemas con matriz simétrica y definida positiva, se recupera en este capítulo su formulación como un método de proyeccién sobre un subespacio apropiado de Krylov, probando el teorema de convergencia. La parte más novedosa del capítulo aborda la descripción de otros métodos de Krylov, para sistemas lineales con matrices simétricas pero no definidas positivas o sistemas con matrices simplemente no simétricas: FOM (ortogonalización completa), GMRES (residuos mínimos generalizados), GMRES(m) (residuos mínimos generalizados con truncación) y MINRES (residuos mínimos). Estos métodos se implementarán en rutinas MATLAB propias en la experimentación numérica que ilustra los mismos en el capítulo 4. Las limitaciones de tiempo y espacio dejan fuera de cobertura otros métodos de Krylov de interés práctico: Bi-CG (gradientes biconjugados), Bi-CGSTAB (gradientes biconjugados estabilizados),etc., pero los métodos presentados ilustran ya el gran costo que supone el no disponer de recurrencias cortas para la construcción de los sucesivos iterantes, y que motiva el problema teórico que abordamos en el siguiente capítulo. 3. En 1981 Gene Golub planteó la cuestión de si sería posible para sis- temas lineales con matrices no simétricas construir un método que en cada iteración optimizara sobre un espacio de Krylov con respecto a una norma proveniente de un producto interno y que requiriera únicamente recurrencias de tres términos, tal y como ocurre en el método gradiente conjugado. Faber y Manteuffel caracterizaron las matrices para las que esto es posible, respondiendo negativamente a la cuestión salvo para situaciones que ya eran bien conocidas: o bien el polinomio mínimo de la matriz es cúbico, o la matriz es hermética o la matriz adjunta de la matriz del sistema (matriz traspuesta conjugada) se expresa como un polinomio lineal de la propia matriz. La formulación y prueba del teorema de Faber y Manteuffel es el objetivo del tercer capítulo. La prueba necesita de bastantes resultados técnicos de la teoría de matrices, de algunos de los cuales hacemos uso en base a su estudio a lo largo del Grado: por ejemplo, polinomio mínimos de un vector y de una matriz, propiedades generales de las matrices normales, producto exterior de vectores, etc. 4. El cuarto capítulo ilustra algunos experimentos numéricos con los métodos gradiente conjugado, MINRES y GMRES sobre problemas test con matrices grandes y dispersas que se toman de la colección Harwell- Boeing en el Matrix Market, un depósito de matrices test para la comparaci ón de algoritmos de álgebra lineal. Como en algunos de los experimentos fué necesario preacondicionar previamente las matrices, se describe este proceso de forma somera cuando se implementa utilizando la factorización LU o de Cholesky incompletas de la matriz del sistema.