Power iteration for matrices with power series entries

Sintesi Tecnica: Iterazione di Potenza per Matrici con Ingressi in Serie di Potenze

Definizione del Problema
Il documento affronta il problema della ricerca di autovalori e autovettori per matrici con ingressi in campi di serie di potenze, nello specifico il campo di Levi-Civita $\mathbb{C}$ e il campo delle serie di Puiseux. Sebbene la ricerca delle radici dei polinomi su questi campi sia un problema ben studiato nella geometria algebrica e nella fisica (ad esempio, sistemi hamiltoniani, reti elettriche), la risoluzione di problemi di autovalori per matrici su tali campi ha ricevuto un'attenzione limitata. I metodi esistenti, come il calcolo delle radici del polinomio caratteristico, sono descritti come computazionalmente costosi. Gli autori mirano ad adattare il classico metodo dell'iterazione di potenza — una tecnica numerica standard per matrici complesse — a questi campi non-archimediani, dove le definizioni standard di convergenza non si applicano direttamente.

Metodologia e Quadro Teorico
Il nucleo della metodologia si basa sulle proprietà del campo di Levi-Civita ($\mathbb{R}$ e $\mathbb{C}$), che è un campo ordinato non-archimediano, Cauchy-completo, reale-chiuso (e algebricamente chiuso, per $\mathbb{C}$). Gli autori distinguono tra due tipi di convergenza in questo contesto:

1. Convergenza Forte: Convergenza rispetto alla topologia dell'ordine.
2. Convergenza Debole: Convergenza dei coefficienti nel senso usuale, che è cruciale per le rappresentazioni in serie di potenze.

Gli autori stabiliscono diversi risultati ausiliari riguardanti la convergenza debole, tra cui:

• La continuità della convergenza debole sotto addizione e moltiplicazione per sequenze "regolari" (sequenze con unione di supporti a sinistra finiti).
• La convergenza debole degli inversi ($1/a_k \to 1/a$) e delle radici quadrate ($\sqrt{a_k} \to \sqrt{a}$) sotto specifiche condizioni (ad esempio, $a[0] \neq 0$).
• Un criterio per la convergenza debole basato sulla convergenza uniforme dei coefficienti su sottoinsiemi limitati del supporto.

L'Algoritmo di Iterazione di Potenza
Il documento dimostra che il metodo dell'iterazione di potenza converge debolmente per matrici diagonalizzabili sul campo di Levi-Civita $\mathbb{C}$ sotto le seguenti condizioni:

1. La matrice ha al massimo ingressi finiti (ovvero, la valutazione $\lambda(a_{ij}) \geq 0$).
2. Esiste un autovalore unico con il valore assoluto strettamente maggiore della sua "parte complessa" (il coefficiente del termine $d^0$, indicato con $\nu[0]$).
3. Il vettore iniziale ha una componente non nulla nella direzione dell'autovettore dominante.

Nello specifico, se $\nu_1$ è l'autovalore dominante tale che $|\nu_1[0]| > |\nu_2[0]| \geq \dots$, la sequenza di vettori normalizzati $x_k / \|x_k\|$ converge debolmente all'autovettore dominante normalizzato. Inoltre, il quoziente di Rayleigh $u_k^* A u_k / \|u_k\|^2$ converge debolmente all'autovalore dominante.

Per gestire matrici che inizialmente non soddisfano la condizione di "al massimo finiti" o dove l'autovalore dominante non è immediatamente ovvio, gli autori propongono una strategia di scalatura:

• Spostare gli ingressi della matrice tramite la valutazione minima $q_0$ per creare una matrice $A' = d^{-q_0}A$.
• Analizzare la matrice della "parte complessa" $\pi(A')$ (la matrice dei coefficienti allo $0$-esimo).
• Se $\pi(A')$ possiede un autovalore dominante, l'iterazione di potenza può essere applicata alla matrice scalata per trovare l'autovalore e l'autovettore dominante della matrice originale.

Questo approccio è esteso al campo delle serie di Puiseux, che è un sottocampo del campo di Levi-Civita, permettendo al metodo di essere applicato a matrici con ingressi in serie di Puiseux.

Risultati Chiave

• Teorema 5.5: Stabilisce che se una matrice diagonalizzabile $A$ (possibilmente con ingressi infinitamente grandi o piccoli) può essere scalata in modo che la sua matrice "parte complessa" abbia un autovalore strettamente dominante, il metodo dell'iterazione di potenza trova con successo l'autovalore di modulo maggiore e il corrispondente autovettore.
• Corollario 5.7: Conferma che il metodo si applica a matrici diagonalizzabili sul campo delle serie di Puiseux, producendo risultati all'interno dello stesso campo.
• Dimostrazioni di Convergenza: Il documento fornisce dimostrazioni rigorose per la convergenza debole della sequenza di vettori e del quoziente di Rayleigh, utilizzando la regolarità delle sequenze e la continuità delle operazioni algebriche nel campo di Levi-Civita.

Implementazione e Risultati Sperimentali
Gli autori hanno implementato l'algoritmo in Python. Hanno testato il metodo sulla matrice compagna di un polinomio di grado 21 sul campo delle serie di Puiseux $\mathbb{R}\{\{t\}\}$.

• Complessità: Per le matrici compagne, la complessità temporale è stimata in $O(n d_t \log(d_t))$, dove $n$ è la dimensione della matrice e $d_t$ è il massimo grado della variabile $t$ negli ingressi. Per matrici arbitrarie, è $O(n^2 d_t \log(d_t))$.
• Prestazioni: In un caso di test specifico (polinomio di grado 21), l'algoritmo è confluito alla radice più grande (approssimata come $100 + t + \dots$) in 100 iterazioni. L'errore è diminuito significativamente, raggiungendo magnitudini di $10^{-12}$ a $10^{-14}$ per la maggior parte delle componenti. Il tempo di esecuzione è stato di circa 135 secondi su un Lenovo p50 per 100 iterazioni.
• Osservazioni: Gli autori notano che le prestazioni possono essere notevolmente migliorate con una versione modificata dell'algoritmo. Menzionano inoltre l'implementazione dell'iterazione inversa del vettore, dell'iterazione di sottospazio e dell'algoritmo QR come strumenti complementari per trovare i vettori rimanenti o tutti i vettori simultaneamente.

Significatività e Rivendicazioni
Il documento sostiene di fornire il primo algoritmo di iterazione di potenza progettato specificamente per matrici con ingressi in serie di potenze. Gli autori sostengono che questo metodo non è solo teoricamente interessante, ma apre anche la strada allo sviluppo di ulteriori approcci numerici per la ricerca di radici di polinomi multivariati. Suggeriscono che questi nuovi approcci potrebbero offrire una stabilità e un'efficienza migliori rispetto ai metodi esistenti che si basano sul calcolo delle radici dei polinomi caratteristici. Il lavoro colma il divario tra la geometria algebrica (dove le serie di Puiseux sono comuni) e l'algebra lineare numerica, adattando un metodo iterativo fondamentale ai campi non-archimediani.