6.10 Méthode de Krylov

résolution itérative de $Ax=b$ avec $A$ non singulière de dimension $n$.

principe:

soit $x_{0}$ un vecteur initial, on veut calculer une nouvelle estimation $x_{1}$telle que le résidu $r_{1}=b-A.x_{1}$ soit plus petit en norme que $r_{0}=b-A.x_{0}$. Pour cela on choisit une direction de descente $v_{1}=r_{0}$, et on impose que la projection du nouveau résidu soit orthogonale à une direction $w_{1}=A.v_{1}$.

$$x_{1}=x_{0}+\alpha_{0}v_{1} avec r_{1}=b-A.x_{1} \perp w_{1}$$

englishméthode du résidu minimum sous Maple

Généralisation:

on choisit un sous espace $H_{m}$ comme direction de descente au lieu d'un vecteur.

Méthode de projection:

soit $H_{m}$un sous espace de dimension $m$ de $\mathcal{R}^{n}$ et $L_{m}$ un second sous espace . On cherche une correction $\delta_{0}$ dans $H_{m}$ telle que le résidu soit perpendiculaire à $L_{m}$. On choisit $m\ll n$ de façon à ce que le système projeté soit de dimension petite ($m\sim10-20$)

$$x_{1}=x_{0}+\delta_{0} \mbox{{t.q.} }\delta_{0}\in H_{m} \mbox{{ et }}Ax_{1}=R_{0}-A\delta_{0}\perp L_{m}$$

espace de Krylov:

on choisit un vecteur $v_{1}$, et on construit le sous-espace de Krylov $H_{m}=\{ v_{1},A.v_{1},A^{2}v_{1},...A^{m-1}v_{1}\}$. (remarque $H_{n}=\mathcal{R}^{n}$). L'espace orthogonal $L_{m}$

6.10.1 préconditionnement

Pour améliorer la convergence, on préconditionne le système en effectuant par exemple une factorisation incompléte de $A$:

$$A=L.U+R$$

où $L$ et $U$ ont la même structure creuse que $A$.

Le système préconditionné s'écrit:

$$A.x=B \leadsto L^{-1}AU^{-1} y=L^{-1}b avec x=U^{-1}y$$