6.8 Méthode de décomposition

6.8.1 Construction d'une suite itérative

Décomposition

de A = E - F avec E inversible

$$A.X=B\Leftrightarrow X=E^{-1}.(F.X+B)$$

Algorithme

 

Dans la pratique, on utilise que 2 vecteurs $X1=X^{k}$et $X2=X^{k+1}$

6.8.2 Convergence

• Erreur $e^{(k)}=X^{(k)}-X$
• par récursion $e^{(k+1)}=G^{k+1}.e^{(0)}$
  avec $G=E^{-1}.F$ matrice de l'itération
• La suite $\{ X^{(k)}\}$ converge si
  
  $$\lim_{k\rightarrow\infty}{e^{(k)}}=0$$
  
  

théorème:

la méthode itérative $e^{(k+1)}=G.e^{(k)}$ converge si et seulement si le rayon spectral $\rho(G)$ de la matrice G est strictement inférieur à 1. Par définition

$$\rho(G)=\max_{i=1,n}{\left\vert\lambda_{i}\right\vert}$$

où $\lambda_{i}$ est la $i^{ieme}$ valeur propre de G

remarque:

théorème du point fixe
$F(x)=G.x$ avec $F'(x)=G$ converge si $\left\Vert G\right\Vert <1$

6.8.3 Méthode de Jacobi

6.8.3.1 description de la méthode

• décomposition de A : $A=D-E-F$
• D : diagonale de A
  $D_{ii}=A_{ii}$ et $D_{ij}=0$ si $i\neq j$
• E : matrice triangulaire inférieure
  $E_{ij}=A_{ij}$ si $i>j$ et $E_{ij}=0$ si $i\le j$
• F : matrice triangulaire supérieure
  $F_{ij}=A_{ij}$ si $i<j$ et $F_{ij}=0$ si $i\ge j$

itération

de Jacobi

$$D.X^{(k+1)}=(E+F).X^{(k)}+B$$

$$X_{i}^{(k+1)}=X_{i}^{(k)}+\frac{1}{A_{ii}}(B_{i}-\sum_{j=1}^{n}A_{ij}.X_{j}^{(k)})$$

$$X_{i}^{(k+1)}=X_{i}^{(k)}+\frac{1}{A_{ii}}R_{i}^{(k)}$$

6.8.3.2 convergence de la méthode

théorème:

Si A est une matrice à diagonale dominante, alors la méthode de Jacobi converge

définition:

matrice à diagonale dominante
A est à diagonale dominante si

$$\forall i \left\vert A_{ii}\right\vert>\sum_{j=1;j\neq i}^{n}\left\vert A_{ii}\right\vert$$

Algorithme

 

6.8.4 Méthode de Gauss-Seidel

6.8.4.1 description de la méthode

• utilisation de $X_{i}^{(k+1)}$ dès que calculé
  $A=D-E-F$ et $(D-E).X=F.X+B$
• itération de Gauss-Seidel
• matrice de l'itération $G=(D-E)^{-1}.F$
  
  $$X^{(k+1)}=(D-E)^{-1}.F.X^{(k)}+(D-E)^{-1}.B$$
  
  
  
  
  $$X_{i}^{(k+1)}=\frac{(B_{i}-\sum_{j=1}^{i-1}A_{ij}.X_{j}^{(k+1)}-\sum_{j=i+1}^{n}A_{ij}.X_{j}^{(k)})}{A_{ii}}$$
  
  
  Attention on ne calcul pas $G^{-1}$ explicitement

6.8.4.2 convergence de la méthode

théorème:

Si A est une matrice à diagonale dominante, alors la méthode de Gauss-Seidel converge

Algorithme

 

6.8.4.3 Variante SOR (successive overrelaxation méthod)

paramêtre $\omega$ d'accélération de la convergence

$$X^{(k+1)}=\omega X_{GS}^{(k+1)}+(1-\omega)X^{k}$$

$$X^{(k+1)}=(D-\omega E)^{-1}(\omega F+(1-\omega)D)X^{k}+\omega(D-\omega E)^{-1}B$$

6.8.4.4 Exemple

englishméthode GaussSeidel et SOR sous Maple