Il metodo delle potenze

Questo metodo è utilizzato proprio per risolvere il problema di determinare l'autovalore dominante; a questo scopo viene richiesto che

$$\vert{\lambda}_1\vert>\vert{\lambda}_2\vert \geq \vert{\lambda}_3\vert \geq \cdots \geq \vert{\lambda}_n\vert\mbox{.}$$

Un'altra ipotesi richiesta è che $A$ sia diagonalizzabile, cioè che $\exists x_1 , \cdots , x_n$ autovettori corrispondenti agli ${\lambda}_i$ autovalori di $A$ tali che siano linearmente indipendenti. In questo caso la matrice è detta diagonalizzabile e $x_1, \cdots, x_n$ formano una base per $\mathbb{C}^n$.

Il metodo procede come segue: dato

$$z_0 \in \mathbb{C}^n$$

un vettore qualunque, per quanto detto sopra, potrà essere scritto come

$$z_0 = \sum_{i=1}^{n} {\alpha}_i x_i \qquad \mbox{per} \quad {\alpha}_i \in \mathbb{C} \quad \mbox{opportuni;}$$

a questo punto, si genera la successione

$$\left\{ \begin{array}{l} y_0 = z_0 \\ y_k = A{y}_{k-1} \end{array} \right.$$

Le proprietà di questa successione sono:

1. $y_k = A^k z_0$;
   
2. $y_k = \sum_{i=1}^{n}{\alpha}_i{\lambda}_i^k x_i$ infatti, vediamo per induzione che
   
   $$k=0 \qquad y_0=\sum_{i=1}^n {\alpha}_i x_i = z_0$$
   
   
   ora supponiamo vero l'asserto per $k-1$ e dimostriamolo per $k$:
   $$\begin{eqnarray*} y_k & = & Ay_{k-1}=A \sum_{i=1}^n {\alpha}_i{\lambda}_i^{k-1}... ...^{k-1} \lambda x_i = \sum_{i=1}^{n}{\alpha}_i{\lambda}_i^k x_i \end{eqnarray*}$$
   
   
   
   

Con ${\alpha}_1 \neq 0$ e sfruttando il fatto che ${\lambda}_1$ è dominante, si ottiene

$$y_k = {\lambda}_1^k \left[{\alpha}_1 x_1 + \sum_{i=2}^n {\al... ...tackrel{k \gg 1}{\longrightarrow} {\lambda}_1^k {\alpha}_1 x_1$$

$$\left( \vert{\lambda}_1\vert \neq 0 \mbox{ poiche maggiore di qualcosa che al minimo è zero } \right)$$

Notiamo che il vettore $y_k$ tende ad allinearsi nella direzione di $x_1$, autovettore dominante.

Osserviamo adesso che

$$y_k^* y_k \simeq \left( \bar{\alpha}_1 \bar{\lambda}_1^k x_1... ...}_1 \vert}^2 {\vert {\lambda}_1^k \vert}^2 {\Vert x \Vert}_2^2$$

$$y_k^* y_{k+1} \simeq {\vert {\alpha}_1 \vert}^2 {\vert {\lamb... ...}^{2k} {\lambda}_1 {\Vert x \Vert}_2^2 = {\lambda}_1 y_k^* y_k$$

a questo punto possiamo definire

$${\sigma}_k = \frac{y_k^* y_{k+1}}{y_k^* y_k} \rightarrow {\lambda}_1 \quad \mbox{ per } k \rightarrow +\infty$$

Questo algoritmo oltre all'autovalore dominante trova anche l'autovettore associato, infatti $y_k$ tende ad essere un autovettore corrispondente a ${\lambda}_1$.

Il metodo procede come segue:

$$(z_0 =) \underbrace{y_0 \longrightarrow y_1=A}_{ {\sigma}_0} ... ...rray}{c} \\ \cdots \\ \longrightarrow {\lambda}_1 \end{array}}$$

Implementando così l'algoritmo potrebbe dare origine ad errori di underflow ed overflow. Questi inconvenienti derivano dal fatto che per calcolare ${\sigma}_k$ dobbiamo calcolare $y_k$ e questo tende a $+ \infty$ se ${\lambda}_1 > 1$ mentre tende a $0$ se ${\lambda}_1 < 1$; l'underflow si può dire che sia un problema "nascosto" poichè in quel caso $y_k \rightarrow 0$ ma poi si vedrebbe che l'algoritmo non converge ad una approssimazione accettabile.

Allora si cercano delle modifiche all'algoritmo per ovviare a questi inconvenienti:

$$\left\{ \begin{array}{lr} {\hat{y}}_0 = z_0 & \\ t_k = \... ...= 1 \right) \\ \hat{{y}}_{k+1} =A t_k \end{array} \right.$$

La successione adesso procede come segue:

$$\begin{array}{ccc} {\hat{y}}_0 & & {\hat{y}}_1 \\ \downarrow & \nearrow & \downarrow \\ t_0 & & t_1 \end{array}$$

Aver normalizzato il vettore ${\hat{y}}_k$ rende $A t_k$ il prodotto di una matrice per un vettore di norma uno che non diventa mai troppo grande. Quello che interessa a noi è un'approssimazione di ${\lambda}_1$; si nota allora che

$$t_k=\frac{A^k z_0}{ {\Vert A^k z_0 \Vert}_2}$$

$$y_{k+1} = \frac{A^{k+1} z_0}{ {\Vert A^{k} z_0 \Vert}_2}$$

A partire da questi due valori si può scrivere

$$t_k^* A t_k =\frac{ {\left( A^k z_0 \right) }^* A \left( A^k z_0 \right)}{ {\Vert A^k z_0\Vert}_2^2}$$

$$t_k^* t_k =\frac{ {\left( A^k z_0 \right) }^* \left( A^k z_0 \right)}{ {\Vert A^k z_0\Vert}_2^2}$$

a questo punto siamo in grado di definite

$${\hat{\sigma}}_k = \frac{t_k^* {\hat{y}}_{k+1}}{t_k^* t_k} = ... ... = {\sigma}_k \qquad {\hat{\sigma}}_k \rightarrow {\lambda}_1$$

esattamente uguale a ${\sigma}_k$ di prima; ma per ottenere ${\hat{\sigma}}_k$ ho bisogno di $t_k$ e ${\hat{y}}_{k+1}$, che numericamente non danno problemi. A questo punto il nuovo algoritmo è il seguente:

$$\left. \begin{array}{c} {\hat{y}}_0 = z_0 \\ \\ t_0 =... ...\Vert}_2} \end{array} \right\} \longrightarrow \quad \cdots$$

e questo può essere implementato.

Come criteri di arresto possiamo prendere indifferentemente

$$\vert {\hat{\sigma}}_{k+1} - {\hat{\sigma}}_k \vert < toll \qquad \mbox{ oppure}$$

$$\left\vert \frac{{\hat{\sigma}}_{k+1} - {\hat{\sigma}}_k}{{\hat{\sigma}}_k} \right\vert < toll$$

ma inoltre dobbiamo porre un limite massimo alle iterazioni; questo è dovuto al fatto che è richiesto che la matrice ammetta autovalore dominante, se non lo ammette l'algoritmo potrebbe non convergere. Se usciamo dall'algoritmo perché si è raggiunto il massimo numero di iterazioni concesse, si può dire che non si è raggiunta un'approssimazione di ${\lambda}_1$.