Precondicionamiento y métodos de Krylov

El tamaño del residuo no dice por sí solo el tamaño del error.

Una κ grande puede hacer poco informativa la cota, aunque el residuo sea pequeño. El algoritmo usa productos Av y una regla de parada que fija norma, escalas y tolerancia.

El espacio contiene todas sus combinaciones lineales. La búsqueda se hace en x₀+, no solo en uno de los vectores de la lista.

Hay m generadores, pero su dimensión puede ser menor.

Si los productos generan un subespacio invariante, un método apropiado puede terminar antes de la dimensión total. Dependencia exacta y pérdida numérica de independencia se tratan de forma distinta.

CG elige que minimiza esa norma de error A sobre x₀+.

Sus direcciones son conjugadas: ᵀAp_j=0 si i≠j.

No tienen por qué ser ortogonales euclídeamente. La propiedad se garantiza aquí para SPD y aritmética exacta.

Mientras ≠0, usa . El denominador es positivo para una dirección no nula por SPD.

Si el nuevo residuo es cero se termina.

Si no, .

En dimensión n, CG termina en a lo sumo n pasos exactos. Con redondeo puede perder ortogonalidad; esa cifra no es un límite práctico garantizado.

Una cota clásica de CG es . Es una cota superior, no la trayectoria exacta del error.

Si A tiene pocos autovalores distintos, un polinomio de bajo grado puede anular todas las componentes del error. El agrupamiento espectral puede favorecer convergencia más rápida que la cota extrema. Para matrices no normales no se traslada este análisis como si todas fueran SPD.

Para sistemas generales invertibles, GMRES usa Arnoldi para construir una base ortonormal del espacio de Krylov. Resuelve un pequeño problema de mínimos cuadrados y elige el candidato con menor ∥b−Ax∥₂ en ese espacio afín.

Almacenar y ortogonalizar todos los vectores cuesta cada vez más. GMRES reiniciado limita la memoria, pero puede perder convergencia o estancarse. CG y GMRES pueden dar puntos distintos incluso sobre una matriz SPD porque minimizan cantidades distintas.

Escogemos M SPD y barato de resolver.

La matriz transformada es SPD.

PCG implementa esa geometría usando z=M⁻¹r mediante resoluciones con M, sin necesitar formar la raíz o una inversa densa.

M⁻¹A es similar a la matriz transformada, pero puede no ser simétrica euclídeamente. Por eso aplicar CG ordinario a una matriz transformada arbitrariamente y llamarla simétrica no justifica el algoritmo. Las recurrencias de PCG usan productos rᵀz y la estructura de M.

M=A sería perfecto para la condición, pero resolver Mz=r puede ser el problema original. Un buen precondicionador combina construcción asequible, aplicación barata y mejora de convergencia. Jacobi, factorizaciones incompletas y multigrid explotan estructuras diferentes.

Con precondicionamiento izquierdo, GMRES minimiza un residual transformado. Con precondicionamiento derecho se conservan las ecuaciones originales en la minimización habitual. Hay que observar el residual que importa y contabilizar memoria, preparación y productos, además de iteraciones.

Durante la iteración se actualiza r por recurrencias para ahorrar trabajo. El redondeo puede separarlo de b−Ax; recalcular el residual real permite comprobar la parada. Una tolerancia combina a menudo una parte absoluta y otra relativa al dato o al residuo inicial.

Si el problema requiere una cota de error, se incorpora la condición o una estimación específica. También se revisan simetría, positividad y compatibilidad del precondicionador. Terminar en n pasos exactos, conservar ortogonalidad o una cota de convergencia no son afirmaciones independientes de esas condiciones.