Power iteration for matrices with power series entries

Resumen Técnico: Iteración de Potencia para Matrices con Entradas de Series de Potencias

Planteamiento del Problema
El artículo aborda el problema de encontrar autovalores y autovectores para matrices con entradas en campos de series de potencias, específicamente el campo de Levi-Civita $\mathbb{C}$ y el campo de series de Puiseux. Si bien la búsqueda de raíces de polinomios sobre estos campos es un problema bien estudiado en la geometría algebraica y la física (por ejemplo, sistemas hamiltonianos, redes eléctricas), la resolución de problemas de autovalores matriciales sobre estos campos ha recibido una atención limitada. Los métodos existentes, como el cálculo de las raíces del polinomio característico, se describen como computacionalmente costosos. Los autores pretenden adaptar el método clásico de iteración de potencia —una técnica numérica estándar para matrices complejas— a estos campos no arquimedianos, donde las definiciones de convergencia estándar no se aplican directamente.

Metodología y Marco Teórico
El núcleo de la metodología reside en las propiedades del campo de Levi-Civita ($\mathbb{R}$ y $\mathbb{C}$), que es un campo ordenado, no arquimediano, Cauchy-completo, real-cerrado (y algebraicamente cerrado, para $\mathbb{C}$). Los autores distinguen entre dos tipos de convergencia en este contexto:

1. Convergencia Fuerte: Convergencia con respecto a la topología de orden.
2. Convergencia Débil: Convergencia de los coeficientes en el sentido usual, lo cual es crucial para las representaciones de series de potencias.

Los autores establecen varios resultados auxiliares relativos a la convergencia débil, incluyendo:

• La continuidad de la convergencia débil bajo la suma y la multiplicación para secuencias "regulares" (secuencias con uniones de soporte con soporte finito a la izquierda).
• La convergencia débil de los inversos ($1/a_k \to 1/a$) y las raíces cuadradas ($\sqrt{a_k} \to \sqrt{a}$) bajo condiciones específicas (por ejemplo, $a[0] \neq 0$).
• Un criterio de convergencia débil basado en la convergencia uniforme de los coeficientes en subconjuntos acotados del soporte.

El Algoritmo de Iteración de Potencia
El artículo demuestra que el método de iteración de potencia converge débilmente para matrices diagonalizables sobre el campo de Levi-Civita $\mathbb{C}$ bajo las siguientes condiciones:

1. La matriz tiene entradas, a lo sumo, finitas (es decir, la valoración $\lambda(a_{ij}) \geq 0$).
2. Existe un autovalor único con el valor absoluto estrictamente mayor de su "parte compleja" (el coeficiente del término $d^0$, denotado como $\nu[0]$).
3. El vector inicial tiene un componente no nulo en la dirección del autovector dominante.

Específicamente, si $\nu_1$ es el autovalor dominante tal que $|\nu_1[0]| > |\nu_2[0]| \geq \dots$, la secuencia de vectores normalizados $x_k / \|x_k\|$ converge débilmente al autovector dominante normalizado. Además, el cociente de Rayleigh $u_k^* A u_k / \|u_k\|^2$ converge débilmente al autovalor dominante.

Para manejar matrices que inicialmente no cumplen la condición de "a lo sumo finitas" o donde el autovalor dominante no es inmediatamente obvio, los autores proponen una estrategia de escalado:

• Desplazar las entradas de la matriz mediante la valoración mínima $q_0$ para crear una matriz $A' = d^{-q_0}A$.
• Analizar la "parte compleja" de la matriz $\pi(A')$ (la matriz de los coeficientes de orden $0$).
• Si $\pi(A')$ tiene un autovalor dominado, la iteración de potencia puede aplicarse a la matriz escalada para hallar el autovalor y el autovector dominante de la matriz original.

Este enfoque se extiende al campo de series de Puiseux, que es un subcampo del campo de Levi-Civita, permitiendo que el método se aplique a matrices con entradas de series de Puiseux.

Resultados Clave

• Teorema 5.5: Establece que si una matriz diagonalizable $A$ (posiblemente con entradas infinitamente grandes o pequeñas) puede ser escalada de tal manera que su matriz de "parte compleja" tenga un autovalor estrictamente dominante, el método de iteración de potencia encuentra con éxito el autovalor de mayor módulo y su correspondiente autovector.
• Corolario 5.7: Confirma que el método es aplicable a matrices diagonalizables sobre el campo de series de Puiseux, arrojando resultados dentro del mismo campo.
• Pruebas de Convergencia: El artículo proporciona pruebas rigurosas para la convergencia débil de la secuencia de vectores y del cociente de Rayleigh, utilizando la regularidad de las secuencias y la continuidad de las operaciones algebraicas en el campo de Levi-Civita.

Implementación y Resultados Experimentales
Los autores implementaron el algoritmo en Python. Probaron el método con la matriz compañera de un polinomio de grado 21 sobre el campo de series de Puiseux $\mathbb{R}\{\{t\}\}$.

• Complejidad: Para matrices compañeras, la complejidad temporal se estima en $O(n d_t \log(d_t))$, donde $n$ es la dimensión de la matriz y $d_t$ es el grado máximo de la variable $t$ en las entradas. Para matrices arbitrarias, es $O(n^2 d_t \log(d_t))$.
• Rendimiento: En un caso de prueba específico (polinomio de grado 21), el algoritmo convergió a la raíz más grande (aproximada como $100 + t + \dots$) tras 100 iteraciones. El error disminuyó significativamente, alcanzando magnitudes de $10^{-12}$ a $10^{-14}$ para la mayoría de los componentes. El tiempo de ejecución fue de aproximadamente 135 segundos en una Lenovo p50 para 100 iteraciones.
• Observaciones: Los autores señalan que el rendimiento puede mejorarse considerablemente con una versión modificada del algoritmo. También mencionan la implementación de la iteración de vector inverso, la iteración de subespacio y el algoritmo QR como herramientas complementarias para hallar los vectores restantes o todos los vectores simultáneamente.

Significancia y Reivindicaciones
El artículo afirma proporcionar el primer algoritmo de iteración de potencia diseñado específicamente para matrices con entradas de series de potencias. Los autores postulan que este método no solo es teóricamente interesante, sino que también abre la puerta al desarrollo de nuevos enfoques numéricos para hallar raíces de polinomios multivariados. Sugieren que estos nuevos enfoques podrían ofrecer una mayor estabilidad y eficiencia en comparación con los métodos existentes que dependen del cálculo de las raíces del polinomio característico. El trabajo cierra la brecha entre la geometría algebraica (donde las series de Puiseux son comunes) y el álgebra lineal numérica al adaptar un método iterativo fundamental a campos no arquimedianos.