--- title: VISI601_CMI (5c) Méthodes itératives type: slide slideOptions: transition: slide progress: true slideNumber: true --- # Méthodes itératives > [name=Jacques-Olivier Lachaud][time=January 2022][color=#907bf7] > (Les images peuvent être soumises à des droits d'auteur. Elles sont utilisées ici exclusivement dans un but pédagogique) ###### tags: `visi601` Retour à [VISI601_CMI (Main) Algorithmique numérique](https://codimd.math.cnrs.fr/s/IWTaBkA9m) --- ## Principe et intérêt des méthodes itératives Trouver une solution à $A\mathbf{x}=\mathbf{b}$, par approximations successives de la solution, via des produits matrice/vecteur et additions :::info Méthode itérative: $\mathbf{x}^{(0)} \,\text{donné}, \quad \mathbf{x}^{(k+1)}=B\mathbf{x}^{(k)}+\mathbf{f},\quad$ $B$ matrice d'itération ::: * Si $A$ est pleine, chaque itération coûte $O(n^2)$ flops, donc si la méthode converge en $N$ itérations, et $N <n$, méthode compétitive * Si $A$ est creuse, $n_{nz}=O(n)$, chaque itération coûte $O(n)$ flops, donc si la méthode converge en $N$ itérations, et $N <n^2$, méthode compétitive :::warning Arrêt lorsque $\|A\mathbf{x}^{k}-\mathbf{b}\| < \epsilon$ ou $\|\mathbf{x}^{k}-\mathbf{x}^{k-1}\| < \epsilon$, la solution n'est pas exacte. ::: --- ## Aspects communs des méthodes itératives Méthode itérative: $\mathbf{x}^{(0)} \,\text{donné}, \quad \mathbf{x}^{(k+1)}=B\mathbf{x}^{(k)}+\mathbf{f},\quad$ $B$ matrice d'itération Méthode **consistante** ssi $\mathbf{x}=B\mathbf{x}+\mathbf{f} \Leftrightarrow \mathbf{f}=(Id-B)A^{-1}\mathbf{b}$ :::success Si la méthode est consistante, alors la méthode est convergente ssi le rayon spectral de $B$ est $<1$. ::: Nb: rayon spectral $\rho(B)$ = plus grande valeur propre, et $\rho(B)\le\|B\|_{*}$ --- ## Méthodes itératives linéaires $\mathbf{x}^{(0)}$ donné, on résoud $P\mathbf{x}^{(k+1)}=N\mathbf{x}^{(k)}+\mathbf{b},\quad$ $P$ préconditionneur On note $r^{(k)}=\mathbf{b}-A\mathbf{x}^{(k)}$ le **résidu**, et $A=P-N$ $$ \begin{align*} \mathbf{x}^{(k+1)} &= \underbrace{P^{-1} N}_{B} \mathbf{x}^{(k)}+\underbrace{P^{-1}\mathbf{b}}_{\mathbf{f}} \\ &= P^{-1}N \mathbf{x}^{(k)} + P^{-1}(\mathbf{r}^{(k)} + (P-N) \mathbf{x}^{(k)}) \\ &= \mathbf{x}^{(k)} + P^{-1}\mathbf{r}^{(k)} \end{align*} $$ Clairement, si le résidu tend vers 0, la suite $\mathbf{x}^{(k)}$ converge. --- ## Méthode de Jacobi $x_i^{(k+1)} = \frac{1}{a_{ii}} \left(b_i - \sum_{j \neq i} a_{ij} x_j^{(k)} \right), \quad i=1, \ldots,n.$ $$ \underbrace{\begin{bmatrix} a_{11} & 0 & \ldots & 0\\ 0 & a_{22} & \ddots & \vdots\\ \vdots & \ddots & \ddots & 0\\ 0 & \cdots & 0 & a_{nn} \end{bmatrix}}_{P:=D} \begin{bmatrix} x_1^{(k+1)}\\ x_2^{(k+1)} \\ \vdots \\ x_n^{(k+1)} \end{bmatrix}= \underbrace{\begin{bmatrix} 0 & -a_{12} & \ldots & -a_{1n}\\ -a_{21} & 0 & \ddots & \vdots\\ \vdots & \ddots & \ddots & -a_{n-1n}\\ -a_{n1} & \cdots & -a_{nn-1} &0 \end{bmatrix}}_{N:=D-A} \begin{bmatrix} x_1^{(k)}\\ x_2^{(k)} \\ \vdots \\ x_n^{(k)} \end{bmatrix}+ \begin{bmatrix} b_1\\ b_2 \\ \vdots \\ b_n \end{bmatrix} $$ $D$ est triviale à inverser. Matrice d'itération $B_J=P^{-1}N=D^{-1}(D-A)=I-D^{-1}A$ Si diagonale strict. dominante, le rayon spectral de $B_J$ est $<1$ **Jacobi** : $\mathbf{x}^{(k+1)}=B_J \mathbf{x}^{(k)} + D^{-1}\mathbf{b}\quad$ ou $\quad \mathbf{x}^{(k+1)}=\mathbf{x}^{(k)} + D^{-1}\mathbf{r}^{(k)}$ --- ## Méthode de Jacobi sur-relaxée **Jacobi over relaxation (JOR)** : $\mathbf{x}^{(k+1)}=\omega(B_J \mathbf{x}^{(k)} + D^{-1}\mathbf{b})+(1-\omega)\mathbf{x}^{(k)}$ Matrice d'itération $B_{J}(\omega)=\omega B_J+(1-\omega)I$ $\mathbf{x}^{(k+1)}=\mathbf{x}^{(k)} + \omega D^{-1}\mathbf{r}^{(k)}$ JOR est consistante et coïncide avec Jacobi pour $\omega=1$ --- ## Méthode de Gauss-Seidel $x_i^{(k+1)} = \frac{1}{a_{ii}} \left(b_i - \sum_{j=1}^{i-1} a_{ij} x_j^{(k+1)} - \sum_{j = i+1}^n a_{ij} x_j^{(k)} \right), \quad i=1, \ldots,n.$ $$ \underbrace{\begin{bmatrix} a_{11} & 0 & \ldots & 0\\ a_{12} & a_{22} & \ddots & \vdots\\ \vdots & \ddots & \ddots & 0\\ a_{n2} & \cdots & a_{nn-1} & a_{nn} \end{bmatrix}}_{P:=D-E} \begin{bmatrix} x_1^{(k+1)}\\ x_2^{(k+1)} \\ \vdots \\ x_n^{(k+1)} \end{bmatrix}= \underbrace{\begin{bmatrix} 0 & -a_{12} & \ldots & -a_{1n}\\ 0 & 0 & \ddots & \vdots\\ \vdots & \ddots & \ddots & -a_{n-1n}\\ 0 & \cdots & 0 &0 \end{bmatrix}}_{N:=D-A-E=F} \begin{bmatrix} x_1^{(k)}\\ x_2^{(k)} \\ \vdots \\ x_n^{(k)} \end{bmatrix}+ \begin{bmatrix} b_1\\ b_2 \\ \vdots \\ b_n \end{bmatrix} $$ avec $E$ l'opposée de la partie triangulaire inférieure de $A$, et $F$ celui de la partie triangulaire supérieure, i.e. $A=D-E-F$ **Gauss-Seidel** matrice d'itération $B_{GS}=(D-E)^{-1}F$ $\mathbf{x}^{(k+1)}=\mathbf{x}^{(k)}+(D-E)^{-1}\mathbf{r}^{(k)}$ --- ## Méthode de Gauss-Seidel avec sur-relaxation (SOR) **Successive over relaxation (SOR)** : $x_i^{(k+1)} = \frac{\omega}{a_{ii}} \left(b_i - \sum_{j=1}^{i-1} a_{ij} x_j^{(k+1)} -\sum_{j = i+1}^n a_{ij} x_j^{(k)} \right) + (1-\omega)x_i^{(k)}, \quad i=1, \ldots,n.$ $(I-\omega D^{-1}E)\mathbf{x}^{(k+1)}=\left(\omega D^{-1}F +(1-\omega)I\right) \mathbf{x}^{(k)} + D^{-1}\mathbf{b}$ Matrice d'itération $B_{GS}(\omega)=(I - \omega D^{-1}E)^{-1} \lbrack (1-\omega)I + \omega D^{-1}F \rbrack.$ $\mathbf{x}^{(k+1)}=\mathbf{x}^{(k)} + \left(\frac{1}{\omega} D - E \right)^{-1} \mathbf{r}^{(k)}$ SOR est consistante et coïncide avec GS pour $\omega=1$. --- ## Convergence de Jacobi et Gauss-Seidel :::success Si $A$ est une matrice à diagonal dominante stricte, alors Jacobi et Gauss-Seidel sont convergentes ::: ==Exemple== Si dominance non stricte, convergence non assurée Soit $A = \begin{bmatrix} 1 & -1 \\ 1 & 1 \end{bmatrix}$, alors Jacobi s'écrit: $\mathbf{x}^{(k+1)} = \begin{bmatrix} 0 & 1 \\ -1 & 0 \end{bmatrix} \mathbf{x}^{(k)} + \mathbf{b}.$ On voit que si on cherche $A \mathbf{x} = \mathbf{0}$, et $\mathbf{x}^{(0)} = \begin{bmatrix} 1 & 0 \end{bmatrix}^T$, on obtient successivement: $\mathbf{x}^{(1)} = \begin{bmatrix} 0 & -1 \end{bmatrix}^T, \mathbf{x}^{(2)} = \begin{bmatrix} -1 & 0 \end{bmatrix}^T, \mathbf{x}^{(3)} = \begin{bmatrix} 0 & 1 \end{bmatrix}^T, \mathbf{x}^{(4)} = \begin{bmatrix} 1 & 0 \end{bmatrix}^T.$ --- ## Convergence de Jacobi et Gauss-Seidel * Si $A$ et $2D-A$ sont sym.def.pos. (sdp) alors Jacobi (J) est convergente * Si $A$ est sdp alors JOR est convergente pour $0<\omega<\rho(D^{-1}A)$ * Si $A$ est sdp alors Gauss-Seidel (GS) est convergente * Si $A$ tridiagonale sdp, alors J et GS sont convergentes, avec $\rho(B_{GS})=\rho^2(B_J)$ * Si J converge, alors JOR converge pour $0<\omega\le 1$ * Si $A$ est spd, alors SOR est convergente pour $0<\omega<2$ * Si $A$ est à diag. dominante stricte, alors SOR est convergente pour $0<\omega\le 1$ Toutes ces propriétés sont liées au rayon spectral inférieur à 1.