Il metodo delle potenze

Il metodo più semplice per la soluzione del problema agli autovalori è il cosiddetto metodo delle potenze o di Von Mises. Si assuma che gli autovalori di $A$ siano ordinati $\left\vert \lambda_1 \right\vert \geq \left\vert \lambda_2 \right\vert \geq \ldots \geq \left\vert \lambda_n \right\vert$ e che gli $n$ autovettori corrispondenti siano linearmente indipendenti. Scelto arbitrariamente nello spazio $\Re^n$ il vettore iniziale $\bz_0$ e costruita la successione di vettori $\bz_k$ mediante la formula ricorrente:

$$\bz_{k+1} = A \bz_k$$ (2)

il modulo dell'autovalore massimo di $A$ si ottiene come limite del rapporto fra due norme di $\bz_{k+1}$ e $\bz_k$:

$$\left\vert \lambda_1 \right\vert = \lim_{k \rightarrow \infty} \frac{\left\vert \bz_{k+1} \right\vert}{\left\vert \bz_k \right\vert}$$ (3)

L'implementazione dello schema definito dalle (2) e (3) è immediata. Infatti, dopo aver inizializzato l'iterazione scegliendo $\bz_0$, si procede a calcolare $\bz_1$ mediante la (2) e la prima approssimazione di $\left\vert \lambda_1 \right\vert$ dal rapporto $\left\vert \bz_1 \right\vert/\left\vert \bz_0 \right\vert$. Si torna quindi alla (2), si determina $\bz_2$ e la nuova approssimazione di $\left\vert \lambda_1 \right\vert$. La convergenza viene raggiunta quando lo scarto fra due iterate successive risulta inferiore ad una prefissata tolleranza. Si possiede, pertanto, una stima di $\lambda_1$ e l'ultimo vettore della successione $\bz_k$ rappresenta una stima dell'autovettore $\bv_1$.

Il metodo delle potenze per il calcolo dell'autovalore massimo risulta poco costoso in termini computazionali, dovendo calcolare un solo prodotto matrice-vettore per ciascuna iterazione. Si verifica che la convergenza dello schema è lineare con fattore asintotico pari al rapporto $\left\vert \lambda_2 \right\vert/\left\vert \lambda_1 \right\vert$. Se la matrice $A$ è simmetrica e definita positiva, come normalmente accade nella soluzione di problemi agli elementi finiti, l'uso della norma euclidea nella (3) consente di raddoppiare la velocità di convergenza.

Il metodo delle potenze può essere utilizzato anche per determinare tutti gli altri autovalori ed autovettori di $A$ seguendo il cosiddetto procedimento di deflation. Dopo aver determinato $\lambda_1$ e $\bv_1$, si costruisce la matrice $A_1$:

$$A_1 = A - \bv_1 \ba_1^T$$ (4)

dove $\ba_1$ è il vettore con componenti pari agli elementi della prima riga di $A$ e l'autovettore $\bv_1$ viene normalizzato in modo da avere la prima componente unitaria. La matrice $A_1$ avrà pertanto la prima riga nulla e può essere ridotta all'ordine $n-1$ eliminando anche la prima colonna. Ora $\lambda_2$ risulta l'autovalore massimo di $A_1$ e può essere determinato mediante il metodo delle potenze. Il vettore $\bz$ a cui si converge è legato all'autovettore $\bv_2$ dalla relazione:

$$\bv_2 = \bv_1 + c \bz$$ (5)

in cui si è aggiunta una prima componente nulla a $\bz$. Premoltiplicando ambo i membri della (5) per $\ba_1$ si ricava la costante $c$ come:

$$c = \frac{\lambda_2-\lambda_1}{\ba_1^T \bz}$$ (6)

e quindi $\bv_2$. Ripetendo il procedimento costituito dalla successione delle (4), (5) e (6) si possono ottenere tutti i $\lambda_i$ ed i corrispodenti $\bv_i$. Si noti che, nel caso in cui la matrice $A$ sia simmetrica e definita positiva, si può sfruttare l'ortogonalità degli autovettori e sostituire la $A_1$ della (4) con:

$$A_1 = A - \lambda_1 \bv_1 \bv_1^T$$ (7)

ripetendo poi l'applicazione del metodo delle potenze.

Si osservi che, tuttavia, la tecnica di deflation non può essere realisticamente sfruttata per la determinazione degli ultimi autovalori di $A$, sia perchè sarebbe necessario applicare il metodo dell potenze $n$ volte con matrici di dimensione minore ma via via sempre più piene, sia perchè ben presto gli errori di arrotondamento sui primi autovalori ed autovettori si propagherebbero rendendo del tutto inaffidabili le stime degli ultimi $\lambda_i$.

Il metodo delle potenze può essere ancora sfruttato per il calcolo dell'autovalore minimo di $A$ ricordando che, per le note proprietà delle matrici, $A^{-1}$ possiede come autovalori i reciproci degli autovalori di $A$, e quindi l'autovalore massimo di $A^{-1}$ è $1/\lambda_n$. Pertanto $\lambda_n$ può essere determinato applicando il metodo delle potenze alla matrice $A^{-1}$, la quale, tuttavia, non può essere in genere calcolata esplicitamente. Si costruirà pertanto una successione di vettori $\bz_k$ tali che:

$$\bz_{k+1} = A^{-1} \bz_k \;\;\; \Rightarrow \;\;\; A \bz_{k+1} = \bz_k$$ (8)

risolvendo, cioè, ad ogni iterazione un sistema lineare. Se la matrice $A$ è simmetrica e definita positiva, si può, ad esempio, applicare lo schema GCM ad ogni iterazione del metodo delle potenze. È chiaro, tuttavia, che per tale via la ricerca dell'autovalore minimo di un problema risulta particolarmente dispendiosa.