El algoritmo de Lanczos es un método iterativo ideado por Cornelius Lanczos que adapta los métodos de potencias para encontrar los m valores propios y vectores propios "más útiles" (tendiendo hacia los extremos más altos o más bajos) de una matriz hermítica de n×n, donde m suele ser, aunque no necesariamente, mucho menor que n. Aunque computacionalmente eficiente en principio, el método tal como se formuló inicialmente no era útil debido a su inestabilidad numérica. En 1970, Ojalvo y Newman demostraron cómo hacer el método numéricamente estable y lo aplicaron a la solución de estructuras de ingeniería muy grandes sometidas a carga dinámica. Esto se logró mediante un método para purificar los vectores de Lanczos (es decir, reortogonalizando repetidamente cada vector recién generado con todos los generados previamente) con cualquier grado de precisión, lo cual, cuando no se realizaba, producía una serie de vectores altamente contaminados por aquellos asociados con las frecuencias naturales más bajas.
En su trabajo original, estos autores también sugirieron cómo seleccionar un vector inicial (es decir, usar un generador de números aleatorios para seleccionar cada elemento del vector inicial) y sugirieron un método determinado empíricamente para calcular m, el número reducido de vectores (es decir, debería seleccionarse como aproximadamente 1,5 veces el número de valores propios precisos deseados). Poco después, su trabajo fue seguido por Paige, quien también proporcionó un análisis de errores. En 1988, Ojalvo produjo una historia más detallada de este algoritmo y una prueba de error de valores propios eficiente.
Resumen del Algoritmo
Se introduce una matriz hermítica A de tamaño n×n y, opcionalmente, un número de iteraciones m (por defecto, sea m=n). Estrictamente hablando, el algoritmo no necesita acceso a la matriz explícita, sino solo a una función v↦Av que calcula el producto de la matriz por un vector arbitrario. Esta función se llama como máximo m veces. Se produce una matriz V de n×m con columnas ortonormales y una matriz tridiagonal simétrica real T=VAV de tamaño m×m. Si m=n, entonces V es unitaria y A=VTV. La iteración de Lanczos es propensa a la inestabilidad numérica; cuando se ejecuta en aritmética no exacta, deben tomarse medidas adicionales (como se describe en secciones posteriores) para garantizar la validez de los resultados.
El algoritmo procede generando una secuencia de vectores ortonormales v1, v2, ..., vm que forman una base para el subespacio de Krylov. Comenzando con un vector arbitrario v1 de norma 1, cada paso calcula un nuevo vector aplicando la matriz A, ortogonalizando contra el vector anterior y normalizando. Los coeficientes αj y βj forman las entradas diagonales y fuera de la diagonal de la matriz tridiagonal T, cuyos valores propios aproximan los de A.
Estabilidad Numérica y Reortogonalización
El algoritmo de Lanczos original sufría de pérdida de ortogonalidad debido al redondeo de coma flotante, lo que conducía a valores propios espurios y vectores propios inexactos. La estabilización de 1970 por Ojalvo y Newman introdujo la reortogonalización completa: cada vector recién generado se ortogonaliza contra todos los generados previamente. Esto purifica los vectores de Lanczos y restaura la estabilidad numérica, aunque a costa de un mayor costo computacional. El análisis de errores de Paige a principios de la década de 1970 proporcionó límites teóricos sobre los efectos del redondeo y justificó el enfoque de reortogonalización.
Aplicaciones en Aprendizaje Automático
En el Machine learning, el algoritmo de Lanczos se utiliza para problemas de valores propios a gran escala, como el cálculo de los valores propios principales de matrices de covarianza en PCA o agrupamiento espectral. También se emplea en Deep learning para aproximar el espectro del hessiano de redes neuronales, lo que ayuda en el análisis de optimización y generalización. La capacidad del algoritmo para trabajar solo con productos matriz-vector lo hace adecuado para matrices muy grandes que surgen en modelos de lenguaje grandes y sistemas de IA generativa, donde el almacenamiento explícito de matrices es inviable.
Métodos Relacionados y Extensiones
El algoritmo de Lanczos está estrechamente relacionado con el método del gradiente conjugado para resolver sistemas lineales, ya que ambos construyen subespacios de Krylov. También se conecta con la iteración de Arnoldi para matrices no hermíticas. Variantes como el algoritmo de Lanczos por bloques manejan múltiples vectores iniciales, y el método de Lanczos reiniciado implícitamente (utilizado en ARPACK) mejora la convergencia y el uso de memoria. Estas extensiones están implementadas en bibliotecas numéricas como LAPACK y SciPy, lo que convierte al algoritmo en una herramienta estándar en la computación científica.
Impacto Histórico y Uso Moderno
Desde su estabilización, el algoritmo de Lanczos se ha aplicado a la ingeniería estructural, la química cuántica y el procesamiento de señales. En el contexto de la Artificial intelligence, sustenta muchos métodos espectrales utilizados en el análisis de datos y la compresión de modelos. La eficiencia y robustez del algoritmo lo han convertido en una piedra angular del álgebra lineal numérica, con investigación continua para mejorar su estabilidad y paralelización para hardware moderno como GPU y aceleradores de IA especializados.
Véase También
- power-iteration
- eigenvalue-decomposition
- krylov-subspace
- conjugate-gradient