GMRES §

The method GMRES stants for Generalized Minimum RESidual, è un metodo di Krylov in quanto cerca la soluzione $x_k$ minimizzando la norma euclidea del residuo nel sottospazio affine $W_k$:

$$x_k=argmi{n}_{v\in W_k}\Vert b-Av{\Vert }_2.\Vert r_k{\Vert }_2=\underset{v\in W_k}{\min }\Vert b-Av{\Vert }_2$$

L’Arnoldi iteration ci da una base ortonormale del $k$-esimo sottospazio di Krylov, dunque il vettore ottimo $v\in W_k=x_0+{\mathcal{K}}_k(A,r_0)$, $v=x_0+V_{k}y$

$$r_k=b-A{x}_k=b-A(x_0+V_{k}y)=r_0-A{V}_{k}y$$

usando la proprietà delle matrici $V$ ed $H$ dell’iterazione di Arnoldi ottengo:

$$r_k=r_0-V_{k+1}{\hat{H}}_{k}y$$

ma siccome $V$ è una base ortgonormale del sottopazio di Krylov $K(A,r_0)$, il residuo iniziale non è altro che la prima colonna della matrice $V$, riscalato:

$$r_k=V_{k+1}(\Vert r_0{\Vert }_2{e}_1-{\hat{H}}_{k}y)$$

Siccome $V_{k+1}$ ha colonne ortonormali, trovare al passo $k$ una soluzione che minimizza il residuo, è equivalente a risolvere il problema di minimizzazzione:

$$\underset{y\in {\mathbb{R}}^k}{\min }\Vert \Vert r_0{\Vert }_2{e}_1-{\hat{H}}_{k}y{\Vert }_2$$

che è un Problema dei minimi quadrati in dimensione $k$ (inferiore ad $n$!).

Dato che $W_n={\mathbb{R}}^n$, se non è avvenuto breakdown prima, GMRES termina in al più $n$ passi (in artimetica esatta).

Breakdown §

Nel caso di breakdown al passo $m<n$, sappiamo che $A{V}_m=V_m{H}_m$ dunque

$$r_m=V_m(\Vert r_0\Vert e_1-H_{m}y)$$