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.

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

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

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

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

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

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

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

${\displaystyle 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: ${\displaystyle x_{k}=x^{(k)}}$ e ${\displaystyle x^{(k)}=\sum _{i=1}^{n}\alpha _{i}\lambda _{i}^{k}v^{(i)}.}$

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

${\displaystyle {\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é ${\displaystyle {\frac {|\lambda _{i}|}{|\lambda _{1}|}}<1}$ per ${\displaystyle i\geq 2}$ si ha:

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

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

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

${\displaystyle {\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é ${\displaystyle \alpha _{1}\neq 0}$) si ottiene:

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

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

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 ${\displaystyle x_{k}=Ax_{k-1},}$ per ${\displaystyle k=1,2,\ldots ,}$ così definita:

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

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

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.^[1]

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 ${\displaystyle \mu ,}$ il metodo trova l'autovalore di modulo più prossimo al valore del parametro.

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

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica