Power iteration for matrices with power series entries

Resumo Técnico: Iteração de Potência para Matrizes com Entradas de Séries de Potências

Enunciado do Problema
O artigo aborda o problema de encontrar autovalores e autovetores para matrizes com entradas em corpos de séries de potências, especificamente o campo de Levi-Civita $\mathbb{C}$ e o campo de séries de Puiseux. Embora encontrar raízes de polinômios sobre esses campos seja um problema bem estudado na geometria algébrica e na física (por exemplo, sistemas hamiltonianos, redes elétricas), a resolução de problemas de autovalores matriciais sobre esses campos tem recebido pouca atenção. Métodos existentes, como o cálculo das raízes do polinômio característico, são descritos como computacionalmente dispendiosos. Os autores visam adaptar o método clássico da iteração de potência — uma técnica numérica padrão para matrizes complexas — para esses corpos não arquimedianos, onde as definições padrão de convergência não se aplicam diretamente.

Metodologia e Estrutura Teórica
O núcleo da metodologia baseia-se nas propriedades do campo de Levi-Civita ($\mathbb{R}$ e $\mathbb{C}$), que é um corpo ordenado, não arquimediano, Cauchy-completo, real-fechado (e algebricamente fechado, para $\mathbb{C}$). Os autores distinguem dois tipos de convergência neste contexto:

1. Convergência Forte: Convergência em relação à topologia da ordem.
2. Convergência Fraca: Convergência dos coeficientes no sentido usual, o que é crucial para representações de séries de potências.

Os autores estabelecem vários resultados auxiliares relativos à convergência fraca, incluindo:

• A continuidade da convergência fraca sob adição e multiplicação para sequências "regulares" (sequências com uniões de suporte com suporte à esquerda finito).
• A convergência fraca de inversos ($1/a_k \to 1/a$) e raízes quadradas ($\sqrt{a_k} \to \sqrt{a}$) sob condições específicas (por exemplo, $a[0] \neq 0$).
• Um critério para convergência fraca baseado na convergência uniforme de coeficientes em subconjuntos limitados do suporte.

O Algoritmo de Iteração de Potência
O artigo prova que o método de iteração de potência converge fracamente para matrizes diagonalizáveis sobre o campo de Levi-Civita $\mathbb{C}$ sob as seguintes condições:

1. A matriz possui entradas, no máximo, finitas (ou seja, a valoração $\lambda(a_{ij}) \geq 0$).
2. Existe um autovalor único com o maior valor absoluto de sua "parte complexa" (o coeficiente do termo $d^0$, denotado por $\nu[0]$).
3. O vetor inicial possui um componente não nulo na direção do autovetor dominante.

Especificamente, se $\nu_1$ é o autovalor dominante tal que $|\nu_1[0]| > |\nu_2[0]| \geq \dots$, a sequência de vetores normalizados $x_k / \|x_k\|$ converge fracamente para o autovetor dominante normalizado. Além disso, o quociente de Rayleigh $u_k^* A u_k / \|u_k\|^2$ converge fracamente para o autovalor dominante.

Para lidar com matrizes que inicialmente não satisfazem a condição de "no máximo finitas" ou onde o autovalor dominante não é imediatamente óbvio, os autores propõem uma estratégia de escalonamento:

• Deslocar as entradas da matriz pela valoração mínima $q_0$ para criar uma matriz $A' = d^{-q_0}A$.
• Analisar a matriz da "parte complexa" $\pi(A')$ (a matriz dos coeficientes de ordem zero).
• Se $\pi(A')$ possui um autovalor dominante, a iteração de potência pode ser aplicada à matriz escalonada para encontrar o autovalor e o autovetor dominante da matriz original.

Esta abordagem é estendida ao campo de séries de Puiseux, que é um subcampo do campo de Levi-Civita, permitindo que o método seja aplicado a matrizes com entradas de séries de Puiseux.

Resultos Principais

• Teorema 5.5: Estabelece que, se uma matriz diagonalizável $A$ (possivelmente com entradas infinitamente grandes ou pequenas) puder ser escalonada de modo que sua matriz de "parte complexa" possua um autovalor estritamente dominante, o método de iteração de potência encontra com sucesso o autovalor de maior módulo e o autovetor correspondente.
• Corolário 5.7: Confirma que o método se aplica a matrizes diagonalizáveis sobre o campo de séries de Puiseux, produzindo resultados dentro do mesmo campo.
• Provas de Convergência: O artigo fornece provas rigorosas para a convergência fraca da sequência de vetores e do quociente de Rayleigh, utilizando a regularidade das sequências e a continuidade das operações algébricas no campo de Levi-Civita.

Implementação e Resultados Experimentais
Os autores implementaram o algoritmo em Python. Eles testaram o método na matriz companheira de um polinômio de grau 21 sobre o campo de séries de Puiseux $\mathbb{R}\{\{t\}\}$.

• Complexidade: Para matrizes companheiras, a complexidade de tempo é estimada em $O(n d_t \log(d_t))$, onde $n$ é a dimensão da matriz e $d_t$ é o grau máximo da variável $t$ nas entradas. Para matrizes arbitrárias, é $O(n^2 d_t \log(d_t))$.
• Desempenho: Em um caso de teste específico (polinômio de grau 21), o algoritmo convergiu para a maior raiz (aproximada como $100 + t + \dots$) em 100 iterações. O erro diminuiu significativamente, atingindo magnitudes de $10^{-12}$ a $10^{-14}$ para a maioria dos componentes. O tempo de execução foi de aproximadamente 135 segundos em um Lenovo p50 para 100 iterações.
• Observações: Os autores observam que o desempenho pode ser fortemente melhorado com uma versão modificada do algoritmo. Eles também mencionam a implementação de iteração de vetor inverso, iteração de subespaço e o algoritmo QR como ferramentas complementares para encontrar os vetores restantes ou todos os vetores simultaneamente.

Significância e Alegações
O artigo afirma fornecer o primeiro algoritmo de iteração de potência projetado especificamente para matrizes com entradas de séries de potências. Os autores postulam que este método não é apenas teoricamente interessante, mas também abre as portas para o desenvolvimento de novas abordagens numéricas para encontrar raízes de polinômios multivariados. Eles sugerem que essas novas abordagens podem oferecer melhor estabilidade e eficiência em comparação com métodos existentes que dependem do cálculo de raízes de polinômios característicos. O trabalho faz a ponte entre a geometria algébrica (onde as séries de Puiseux são comuns) e o cálculo numérico linear ao adaptar um método iterativo fundamental para corpos não arquimedianos.