O algoritmo de Lanczos é um método iterativo concebido por Cornelius Lanczos que adapta os métodos de potência para encontrar os m autovalores e autovetores "mais úteis" (tendendo aos extremos mais altos ou mais baixos) de uma matriz Hermitiana n×n, onde m é frequentemente, mas não necessariamente, muito menor que n. Embora computacionalmente eficiente em princípio, o método como formulado inicialmente não era útil devido à sua instabilidade numérica. Em 1970, Ojalvo e Newman mostraram como tornar o método numericamente estável e o aplicaram à solução de estruturas de engenharia muito grandes sujeitas a carregamento dinâmico. Isso foi alcançado usando um método para purificar os vetores de Lanczos (ou seja, reortogonalizando repetidamente cada vetor recém-gerado com todos os vetores gerados anteriormente) a qualquer grau de precisão, o que, quando não realizado, produzia uma série de vetores altamente contaminados por aqueles associados às frequências naturais mais baixas.
Em seu trabalho original, esses autores também sugeriram como selecionar um vetor inicial (ou seja, usar um gerador de números aleatórios para selecionar cada elemento do vetor inicial) e sugeriram um método determinado empiricamente para determinar m, o número reduzido de vetores (ou seja, ele deveria ser selecionado como aproximadamente 1,5 vezes o número de autovalores precisos desejados). Logo depois, seu trabalho foi seguido por Paige, que também forneceu uma análise de erros. Em 1988, Ojalvo produziu uma história mais detalhada desse algoritmo e um teste eficiente de erro de autovalor.
Visão Geral do Algoritmo
Insira uma matriz Hermitiana A de tamanho n×n e, opcionalmente, um número de iterações m (por padrão, seja m=n). Estritamente falando, o algoritmo não precisa de acesso à matriz explícita, mas apenas de uma função v↦Av que calcula o produto da matriz por um vetor arbitrário. Essa função é chamada no máximo m vezes. Produza uma matriz n×m V com colunas ortonormais e uma matriz tridiagonal simétrica real T=VAV de tamanho m×m. Se m=n, então V é unitária, e A=VTV. A iteração de Lanczos é propensa à instabilidade numérica; quando executada em aritmética não exata, medidas adicionais (como descritas nas seções posteriores) devem ser tomadas para garantir a validade dos resultados.
O algoritmo procede gerando uma sequência de vetores ortonormais v1, v2, ..., vm que formam uma base para o subespaço de Krylov. Começando com um vetor arbitrário v1 de norma 1, cada passo calcula um novo vetor aplicando a matriz A, ortogonalizando contra o vetor anterior e normalizando. Os coeficientes αj e βj formam as entradas diagonais e fora da diagonal da matriz tridiagonal T, cujos autovalores aproximam os de A.
Estabilidade Numérica e Reortogonalização
O algoritmo de Lanczos original sofria de perda de ortogonalidade devido ao arredondamento de ponto flutuante, levando a autovalores espúrios e autovetores imprecisos. A estabilização de 1970 por Ojalvo e Newman introduziu a reortogonalização completa: cada vetor recém-gerado é ortogonalizado contra todos os vetores gerados anteriormente. Isso purifica os vetores de Lanczos e restaura a estabilidade numérica, embora ao custo de uma sobrecarga computacional aumentada. A análise de erros de Paige no início dos anos 1970 forneceu limites teóricos sobre os efeitos do arredondamento e justificou a abordagem de reortogonalização.
Aplicações em Aprendizado de Máquina
Em aprendizado de máquina, o algoritmo de Lanczos é usado para problemas de autovalores em larga escala, como calcular os principais autovalores de matrizes de covariância em PCA|análise de componentes principais ou agrupamento espectral. Ele também é empregado em aprendizado profundo para aproximar o espectro da Hessiana de redes neurais, o que auxilia na análise de otimização e generalização. A capacidade do algoritmo de trabalhar apenas com produtos matriz-vetor o torna adequado para matrizes muito grandes que surgem em grandes modelos de linguagem e sistemas de IA generativa, onde o armazenamento explícito da matriz é inviável.
Métodos Relacionados e Extensões
O algoritmo de Lanczos está intimamente relacionado ao método do gradiente conjugado para resolver sistemas lineares, pois ambos constroem subespaços de Krylov. Ele também se conecta à iteração de Arnoldi para matrizes não Hermitianas. Variantes como o algoritmo de Lanczos em bloco lidam com múltiplos vetores iniciais, e o método de Lanczos reiniciado implicitamente (usado no ARPACK) melhora a convergência e o uso de memória. Essas extensões são implementadas em bibliotecas numéricas como LAPACK e SciPy, tornando o algoritmo uma ferramenta padrão na computação científica.
Impacto Histórico e Uso Moderno
Desde sua estabilização, o algoritmo de Lanczos foi aplicado à engenharia estrutural, química quântica e processamento de sinais. No contexto de inteligência artificial, ele sustenta muitos métodos espectrais usados em análise de dados e compressão de modelos. A eficiência e robustez do algoritmo o tornaram uma pedra angular da álgebra linear numérica, com pesquisa contínua em melhorar sua estabilidade e paralelização para hardware moderno, como GPUs e aceleradores de IA especializados.
Ver Também
- iteração de potência
- decomposição em autovalores
- subespaço de Krylov
- gradiente conjugado