---
# System prepended metadata

title: Untitled

---

**TD méthodes itératives**

Exercice 1: 
On considère la matrice 
$$
A=
\left(
\begin{array}{ccc}
1 & -2 & -2\\
-1 & 1 & -1 \\
2 & -2 & 1
\end{array}
\right)
$$
Soit $b\in \mathbb{R}^3$, on veut résoudre le système $Ax=b$. 

1. Etudier la convergence de la méthode de  Jacobi.
La méthode de Jacobi s'écrit
$$
\left\{
\begin{array}{l}
x_0\mbox{ donné }\\
Dx_{k+1}=(E+F)x_k+b
\end{array}
\right.
$$
où 
$$
D=
\left(
\begin{array}{ccc}
1 & 0 & 0\\
0 & 1 & 0\\
0 & 0 & 1
\end{array}
\right),
E=
\left(
\begin{array}{ccc}
0 & 0 & 0\\
1 & 0 & 0\\
-2 & 2 & 0
\end{array}
\right)
\mbox{ et }
F=
\left(
\begin{array}{ccc}
0 & 2 & 2\\
0 & 0 & 1\\
0 & 0 & 0
\end{array}
\right)
$$
La matrice d'itération s'écrit $B_J=D^{-1}(E+F)$:
$$
B_J=
\left(
\begin{array}{ccc}
0 & 2 & 2\\
1 & 0 & 1\\
-2 & 2 & 0
\end{array}
\right)
$$
Calculons le rayon spectral de $B_J$. 
$$
det(B_J-\lambda I)=
\left|
\begin{array}{ccc}
-\lambda & 2 & 2\\
1 & -\lambda & 1\\
-2 & 2 & -\lambda
\end{array}
\right|
=
\left|
\begin{array}{ccc}
-\lambda & 2-\lambda & 2\\
1 & 1-\lambda & 1\\
-2 & 0 & -\lambda
\end{array}
\right|
$$
$$
\begin{array}{cl}
det(B_J-\lambda I) &=(2+\lambda)(2(1-\lambda))+(2-\lambda)(-\lambda(1-\lambda)-(2-\lambda))\\
&= (2+\lambda)(2-2\lambda)+(2-\lambda)(-\lambda+\lambda^2-2+\lambda)\\
&=\not 4+\not{2\lambda}-\not{4\lambda}-\not{2\lambda^2}+\not{2\lambda^2}-\not{4}-\lambda^3+{\not 2\lambda}\\
&=-\lambda^3
\end{array}
$$
Ainsi $\lambda=0$ est une valeur propre triple d'où $\rho(B_J)=0<1$.
La méthode de Jacobi converge. 
2. Etudier la convergence de la méthode de Gauss-Seidel.
$$
\left\{
\begin{array}{l}
x_0\mbox{ donné }\\
(D-E)x_{k+1}=F x_k+b
\end{array}
\right.
$$

$M=D-E$ est définie par:
$$
M=
\left(
\begin{array}{ccc}
1 & 0 & 0\\
-1 & 1 & 0\\
2 & -2 & 1
\end{array}
\right)
$$

$$
\left\{
\begin{array}{l}
x_1=y_1\\
-x_1+x_2=y_2\\
2x_1-2x_2+x_3=y_3
\end{array}
\right.
\Longleftrightarrow
\left\{
\begin{array}{l}
x_1=y_1\\
x_2=y_1+y_2\\
x_3=2y_2+y_3
\end{array}
\right.
$$
Ainsi, $M^-1$ est donnée par
$$
M^{-1}=
\left(
\begin{array}{ccc}
1 & 0 & 0\\
1 & 1 & 0\\
0 & 2 & 1
\end{array}
\right)
$$
La matrice d'itération s'écrit
$$
B_{GS}=M^{-1}F=
\left(
\begin{array}{ccc}
0 & 2 & 2\\
0 & 2 & 3\\
0 & 0 & 2
\end{array}
\right)
$$
Calculons le rayon spectral de $B_{GS}$. 
$$
det(B_{GS}-\lambda I)=
\left|
\begin{array}{ccc}
\lambda & 2 & 2\\
0 & 2-\lambda & 3\\
0 & 0 & 2-\lambda
\end{array}
\right|=-\lambda(2-\lambda)(2-\lambda)
$$
$B_{GS}$ a deux valeurs propres distinctes: $\lambda_1=0$ et $\lambda_2=2$, d'où $\rho(B_{GS})>1$. 
La méthode diverge. 

Exercice 2
Soient $A$ et $B$ deux matrices réelles d'ordre $n$ avec $A$ inversible et $a,b$ deux
vecteurs de $\mathbb{R}^n$. On considère les deux itérations suivantes
$$(1)
\left\{
\begin{array}{l}
x_{k+1}=By_k + a\\
y_{k+1}=Ax_k + b
\end{array}
\right.
k\in\mathbb{N}
$$
avec $x_0,\;y_0\in\mathbb{R}^n$ donnés.

1. Déterminer une condition nécessaire et suffisante de convergence des deux suites de vecteurs. 
 Si $(x_k)$ converge vers $x$ et $(y_k)$ converge vers $y$, alors $x$ et $y$ sont solutions des systèmes
$$
\left\{
\begin{array}{l}
x=By+a\\
y=Ax+b
\end{array}
\right.
$$
d'où
$$
x=BAx+Bb+a
$$
et
$$
y=ABy+Aa+b
$$

On a donc
$$(I-BA)x=Bb+a$$
 $$(I-AB)y=Aa+b$$. On a:
$$\left\{\begin{array}{l}x_{k+1}=B(Ax_{k-1}+b)+a=BAx_{k-1}+Bb+a\\
y_{k+1}=A(By_{k-1}+a)+b = ABy_{k-1}+Aa+b\end{array}\right.$$
et donc $(x_k)$ converge ssi $\rho (BA) <1$ et $(y_k)$ converge ssi $\rho
(AB)<1$.



2. Soit $z_k=(x_k,y_k)^T\in\mathbb{R}^{2n}$. Montrer que (1) peut s'écrire
$$
z_{k+1}=Cz_k+c
$$
où $C$ est une matrice d'ordre $2n$. Expliciter $C$ et $c$.
 
 $z_{k+1}=Cz_k+c$ avec
  $C=\left(\begin{array}{cc}0&B\\A&0\end{array}\right),
  c=\left(\begin{array}{c}a\\b\end{array}\right)$



3. Monter que $\rho^2(C)=\rho(AB)$.

Soit $\lambda$ valeur propre de $C$ et $z=(x,y)^T$ vecteur
  propre associé
$$Cz=\lambda z\Leftrightarrow\left\{\begin{array}{l}By=\lambda x\\Ax=\lambda
    y\end{array}\right.\Rightarrow ABy=\lambda Ax=\lambda^2 y\Rightarrow$$
$\lambda^2$ est valeur propre de $AB$.

Soit maintenant $\alpha$ valeur propre de $AB$ $\Leftrightarrow \exists u\neq 0: \quad
ABu=\alpha u$. On pose $\beta^2=\alpha$ et $x=Bu$, $y=\beta u$
$$C\left(\begin{array}{c}x\\y\end{array}\right)= \left(\begin{array}{c}\beta
    Bu\\ABu\end{array}\right)=\left(\begin{array}{c}\beta Bu\\\beta^2
    u\end{array}\right)=\beta\left(\begin{array}{c} Bu\\\beta
    u\end{array}\right)=\beta \left(\begin{array}{c}x\\y\end{array}\right)$$
et donc $\rho^2 (C)=\rho (AB)$


4. On considère maintenant les deux itérations suivantes
$$
(2)
\left\{
\begin{array}{l}
x_{k+1}=By_k + a\\
y_{k+1}=Ax_{k+1} + b
\end{array}
\right.
k\in\mathbb{N}
$$
Donner une condition nécessaire et suffisante de convergence. 
5.  Montrer que (2) est équivalent à 
$$
z_{k+1}=Dz_{k}+d
$$
où $D$ est une matrice d'ordre $2n$. 
Montrer que $\rho(D)=\rho(AB)$.
$$
\left\{
\begin{array}{l}
x_{k+1}=By_k + a\\
y_{k+1}=A(By_{k}+a) + b=ABy_k+Aa+b
\end{array}
\right.
$$
De plus, $x_{k+1}=BAx_{k}+Bb+a$
Les conditions pour que la suite $(x_k,y_k)^T$ converge sont $\rho(AB)<1$ et $\rho(BA)<1$.


 $D=\left(\begin{array}{cc}0&B\\0&AB\end{array}\right),\quad
  d=\left(\begin{array}{c}a\\Aa+b\end{array}\right)$.

Comme précédemment, on considère $\lambda$ une valeur propre de $D$, alors si $z$ est un vecteur propre on a
$$
Dz=\lambda z \Longleftrightarrow
\left\{
\begin{array}{l}
By=\lambda x\\
ABy=\lambda y
\end{array}
\right.
$$
D'après la deuxième equation, $\lambda$ est valeur propre de $AB$.\\ 

Si $\mu$ est valeur propre de $AB$ et $y$ un vecteur propre associé à $\mu$ alors
$$
ABy=\mu y
$$
On a 
$$
By=\mu A^{-1}y
$$
On pose $x=A^{-1}y$, et $\mu$ est valeur propre de $D$, d'où $\rho(D)=\rho(AB)$. 



6. On appelle taux de convergence asymptotique de la matrice
  itérative $M$ le nombre
$$
R(M)=-\ln(\rho(M)).
$$
On pose $e^k=x^k-x^*$ l'erreur de l'itéré d'ordre $k$.

a. Montrer que le nombre d'itérations $k$ pour réduire l'erreur
  d'un facteur $\varepsilon$,
  i.e. $\displaystyle{\frac{\|e^k\|}{\|e^0\|}}\leq \varepsilon$
  vérifie
$$
k\geq \frac{-\ln\varepsilon}{R(M)}.
$$
    b. Comparer le taux de convergence des algorithmes (1) et (2).

