7.2 Il metodo delle potenze

Il metodo delle potenze è un metodo di tipo iterativo utilizzato per approssimare l'autovalore di modulo massimo, che si fonda sul seguente teorema:

Teorema 7.2.1   Sia $A\in\mathbf{C}^{n\times n}$ una matrice con autovalori soddisfacenti le condizioni^7.1

$$\vert\lambda_{1}\vert>\vert\lambda_{2}\vert\ge\ldots\ge\vert\lambda_{n}\vert$$

e sia $z^{(0)}\in\mathbf{C}^{n}$ un vettore arbitrario. Allora il processo iterativo

$$y^{(0)} = z^{(0)}$$

$$y^{(k)} = Ay^{(k-1)}\qquad k=1,2,\ldots$$

è tale che

$$\lim_{k\rightarrow+\infty}\frac{y^{(k)}}{y_{j}^{(k)}}=v, \q... ...)^{H}}Ay^{(k)}}{\stackrel{}{y^{(k)^{H}}y^{(k)}}}=\lambda_{1},$$

dove $j$ è un indice per cui $y_{j}^{(k)}\neq 0$, $v$ è l'autovettore associato a $\lambda_{1}$ e $y^{(k)^{H}}$ ? il trasposto coniugato^7.2 di $y^{(k)}$.

DIMOSTRAZIONE. La diagonalizzabilità di $A$ implica l'esistenza di $n$ autovettori $x^{(i)}, i=1,2,\ldots,n$ linearmente indipendenti e quindi che il vettore $z^{(0)}$ possa rappresentarsi nella forma

$$\bgroup\color{darkgreen} z^{(0)}=\sum_{i=1}^{n}c_{i}x^{(i)} \egroup$$

dove è lecito supporre che sia $c_{1}\neq 0$. Segue che

$$y^{(k)} = A^{k}y^{(0)}=A^{k}(c_{1}x^{(1)}+\ldots+c_{n}x^{(n)})$$ (7.2)

$$= c_{1}A^{k}x^{(1)}+\ldots+c_{n}A^{k}x^{(n)}= c_{1}\lambda_{1}^{k}x^{(1)}+\ldots+c_{n}\lambda_{n}^{k}x^{(n)}$$

$$= \Bigg(c_{1}x^{(1)}+\sum_{i=2}^{n}c_{i}\Big(\frac{\lambda_{i}} {\lambda_{1}}\Big)^{k}x^{(i)}\Bigg)$$

e in particolare per ogni indice $j$,

$$y_{j}^{(k)}=\Bigg(c_{1}x_{j}^{(1)}+\sum_{i=2}^{n}c_{i} \Big(\frac{\lambda_{i}}{\lambda_{1}}\Big)^{k}x_{j}^{(i)}\Bigg)$$ (7.3)

Scegliendo $y_{j}^{(k)}\neq 0$, tenendo conto dell'ipotesi sui moduli degli autovalori e dividendo membro a membro la (7.2) per la (7.3), si ottiene

$$\bgroup\color{darkgreen} \lim_{k\rightarrow\infty}\frac{y^{(k)}}{y_{j}^{(k)}}=b_{1}x^{(1)}=v \egroup$$

dove $b_{1}=1/x_{j}^{(1)}$, perciò il vettore $v$ è l'autovettore associato a $\lambda_{1}$, come afferma la tesi. Si ha quindi

$$\bgroup\color{darkgreen} Av=\lambda_{1}v \egroup$$

e anche

$$\bgroup\color{darkgreen} v^{H}Av=\lambda_{1}v^{H}v \egroup$$

da cui

$$\bgroup\color{darkgreen} \frac{v^{H}Av}{v^{H}v}=\lambda_{1} \egroup$$

infine, tenendo conto dell'equazione precedente, si ha

$$\bgroup\color{darkgreen} \lim_{k\rightarrow+\infty}\frac{y^{... ...rightarrow+\infty} \frac{v^{H}Av}{v^{H}v}=\lambda_{1} \egroup$$

per cui è dimostrato il teorema. $\Box$
Il rapporto

$$\bgroup\color{darkgreen} R\left(y^{(k)}\right)=\frac{y^{(k)^{H}}Ay^{(k)}}{y^{(k)^{H}}y^{(k)}} \egroup$$

è chiamato quoziente di Rayleigh. L' algoritmo appena considerato puó dar luogo a situazioni di overflow/underflow nel caso in cui il valore delle componenti in valore assoluto sia o troppo grande o troppo piccolo. È necessaria allora un'operazione di scaling, applicando a priori diversi tipi di norma di vettore. Si costruisce pertanto una successione di vettori $\{z^{(k)}\}$ nel seguente modo

$$\bgroup\color{darkgreen} \left.\begin{array}{ccc} y^{(k)} &... ...}}{\alpha_{k}} \end{array}\right\}\qquad k=1,2,\ldots \egroup$$

dove $z^{(0)}$ è ancora arbitrario e $\alpha_{k}$ è una costante di normalizzazione opportuna. Se ad esempio $\alpha_{k}$ è una componente di massimo modulo di $y^{(k)}$ scelta, a partire da un certo $k$, sempre con lo stesso indice, risulta $\vert\vert z^{(k)}\vert\vert _{\infty}=1$. Nelle ipotesi del teorema, si dimostra che

$$\bgroup\color{darkgreen} \lim_{k\rightarrow+\infty}z^{(k)}=w... ...\rightarrow+\infty} R\left(z^{(k)}\right)=\lambda_{1} \egroup$$

dove $w$ è l'autovettore associato a $\lambda_{1}$.
[caption=Calcola l'autovalore dominante con il metodo delle potenze, label=codici/potenze.m, showstringspaces=false, frame=tRBl, extendedchars=true, basicstyle=pcrm, numbers=left, commentstyle= , frameround=fttt, stepnumber=1, numberstyle=, keywordstyle= , language=Matlab]codici/potenze.m

Esempi di potenze.m da pag.