Metodo delle potenze

Il metodo delle potenze è un semplice metodo iterativo per il calcolo approssimato dell'autovalore di modulo massimo di una matrice e il corrispondente autovettore.

Il metodo

Sia $A\in \mathbb {C} ^{n\times n}$ diagonalizzabile con autovalori $\lambda _{1},\lambda _{2},\ldots ,\lambda _{n}$ tali che $|\lambda _{1}|>|\lambda _{2}|\geq \ldots \geq |\lambda _{n}|\geq 0.$

Fissato un vettore $x_{0}\in \mathbb {C} ^{n}$ (la cui proiezione sull'autospazio relativo a $\lambda _{1}$ è non nulla), si genera la successione $x_{k}=Ax_{k-1}$ per $k=1,2,\ldots$

Si può allora dimostrare che la successione degli $x_{k}$ tende all'autovettore relativo all'autovalore di modulo massimo.

Convergenza

Siccome $A$ è per ipotesi diagonalizzabile, esiste una base di autovettori $v_{1},v_{2},\ldots ,v_{n}$.

Allora il vettore $x_{0}$ può essere riscritto come

$x_{0}=\sum _{i=1}^{n}\alpha _{i}v_{i}$

e conseguentemente, per la definizione di autovalore di una matrice, il risultato della $k$-esima iterazione come:

$x_{k}=A^{k}x_{0}=\sum _{i=1}^{n}\alpha _{i}A^{k}v_{i}=\sum _{i=1}^{n}\alpha _{i}\lambda _{i}^{k}v_{i}.$

Adesso, per comodità di notazione, spostiamo gli indici da pedice in apice: $x_{k}=x^{(k)}$ e $x^{(k)}=\sum _{i=1}^{n}\alpha _{i}\lambda _{i}^{k}v^{(i)}.$

Indicando con $x_{r}^{(k)}$ e $v_{r}^{(i)}$ le componenti $r$-esime dei vettori $x^{(k)}$ e $v^{(i)}$, per gli indici $j$ per cui $x_{j}^{(k)}\neq 0$ e $v_{j}^{(1)}\neq 0$ si ha:

${\frac {x_{j}^{(k+1)}}{x_{j}^{(k)}}}=\lambda _{1}{\frac {\alpha _{1}v_{j}^{(1)}+\sum _{i=2}^{n}\alpha _{i}({\frac {\lambda _{i}}{\lambda _{1}}})^{k+1}v_{j}^{(i)}}{\alpha _{1}v_{j}^{(1)}+\sum _{i=2}^{n}\alpha _{i}({\frac {\lambda _{i}}{\lambda _{1}}})^{k}v_{j}^{(i)}}}.$

E poiché ${\frac {|\lambda _{i}|}{|\lambda _{1}|}}<1$ per $i\geq 2$ si ha:

$\lim _{k\rightarrow \infty }{\frac {x_{j}^{(k+1)}}{x_{j}^{(k)}}}=\lambda _{1}.$

Quindi da un certo indice $k$ in poi l'autovalore $\lambda _{1}$ può essere approssimato con il rapporto indicato.

Con questo metodo si può approssimare anche l'autovettore $v_{1}$. Infatti si ha:

${\frac {x^{(k+1)}}{x_{j}^{(k)}}}=\lambda _{1}{\frac {\alpha _{1}v^{(1)}+\sum _{i=2}^{n}\alpha _{i}({\frac {\lambda _{i}}{\lambda _{1}}})^{k+1}v^{(i)}}{\alpha _{1}v_{j}^{(1)}+\sum _{i=2}^{n}\alpha _{i}({\frac {\lambda _{i}}{\lambda _{1}}})^{k}v_{j}^{(i)}}}.$

E passando al limite (poiché $\alpha _{1}\neq 0$) si ottiene:

$\lim _{k\rightarrow \infty }{\frac {x^{(k+1)}}{x_{j}^{(k)}}}={\frac {v^{(1)}}{v_{j}^{(1)}}},$

che sarebbe l'autovettore $v^{(1)}$ opportunamente normalizzato.

Implementazione

Il metodo delle potenze non viene praticamente mai implementato nella formulazione data, poiché dopo pochi passi si potrebbero avere problemi di underflow o overflow. Per evitare questi problemi è necessario eseguire a ogni passo una normalizzazione del vettore ottenuto, costruendo una successione $x_{k}=Ax_{k-1},$ per $k=1,2,\ldots ,$ così definita:

${\begin{cases}y_{k}=Ax_{k-1}\\x_{k}={\frac {y_{k}}{\beta _{k}}},\end{cases}}$

dove $\beta _{k}$ è uno scalare tale che $\|x_{k}\|=1$ (tipicamente si prende la norma euclidea di $y_{k}$).

Utilizzi

Il metodo delle potenze è scarsamente utilizzato poiché permette il calcolo dei soli autovalori e autovettori dominanti. Trova però degli impieghi in specifici problemi: ad esempio è alla base del metodo utilizzato da Google per il proprio algoritmo di PageRank.

Varianti

Esistono numerose varianti del metodo delle potenze. La più famosa è quella del metodo delle potenze inverse che permette il calcolo approssimato dell'autovalore in modulo minore e del rispettivo autovettore. L'algoritmo si basa sull'osservazione che l'autovalore minore in modulo di una matrice, sarà l'autovalore dominante della matrice inversa.

Per il calcolo di un autovalore di modulo compreso fra il massimo ed il minimo autovalore si può invece utilizzare il metodo delle potenze inverse con shift, abbinato ai teoremi di Gerschgorin sulla localizzazione degli autovalori: modificando la matrice tramite un parametro $\mu ,$ il metodo trova l'autovalore di modulo più prossimo al valore del parametro.

Bibliografia

• D. Bini, M. Capovani, O. Menchi (1988): Metodi Numerici per l'Algebra Lineare, Zanichelli, ISBN 88-08-06438-7