Mme El Kyal 2020-2021

Université Ibn Zohr

Ensa, 1
ère année du cycle ingénieur

Analyse Numérique
T.D. Systèmes linéaires et non linéaires

    
2 −1 x1 1
Exercice 1 On considère le système linéaire Ax = b suivant : =
−1 2 x2 2
1. La matrice A du système est elle convergente ?
2. Etudier la concergence de la méthode de Jacobi.
Exercice 2
Etant donné le système suivant : 
 x1 + 2x2 = 1
x1 + x2 = 2
x1 + x2 + x3 = 1


1. Ecrire explicitement les méthodes itératives de Jacobi et Gauss-Seidel.

2. Ecrire les matrices d'itérations de Jacobi et de Gauss-Seidel.
3. Etudier la convergence de Jacobi et de Gauss-Seidel.
4. Illustrez les résultats théoriques de convergence en calculant les 2 premiers itérés de Gauss-Seidel
en prenant comme point de départ le vecteur (x01 , x02 , x03 ) = (0, 0, 0).
Exercice 3 Calculer le rayon spectral de la matrice de la méthode de Jacobi et de la matrice de la
méthode de Gauss-Seidel pour la résolution du système Ax = b
1.  
1 2 −2
A= 1 1 1 
2 2 1
2.  
2 −1 1
A= 2 2 2 
−1 −1 2
Que peut-on déduire ?
Exercice 4 On considère le système linéaire Ax = b avec :
 
1 2(1 − β) 0
A= 1 2 0 
0 0 1

où β est un paramètre réel.

1. Ecrire explicitement les itérations de Jacobi et de Gaus-Seidel.
2. Sans calculer les matrices d'itérations, donner une condition susantes sur le paramètre β pour
que les deux méthodes convergent.
3. Calculer les matrices d'itération TJ et TG.S
4. Etablir pour quelles valeurs de β les deux méthodes sont convergentes.
5. Indiquer quel est le rapport entre les vitesses de convergence de ces méthodes.

1
Exercice 5
Soit A une matrice carrée d'ordre n > 0, A = (aij )i,j=1,...,n inversible et b ∈ IRn . On veut résoudre le
système linéaire
Ax = b
On note D la matrice diagonale constituée de la diagonale de A. Soit α 6= 0, on étudie la méthode
itérative
x(k+1) = (I − αD−1 A)x(k) + αD−1 b.
1. Montrer que la méthode est consistante i.e. si (x(k) )k≥0 converge vers x alors x est solution du
système Ax = b.
2. Exprimer les coecients de la matrice D−1 A en fonction de ceux de A.
3. On suppose que 0 < α ≤ 1 et que A est à diagonale strictement diminante
(a) Montrer que la méthode est bien dénie (i.e D est inversible).
(b) Montrer que kI − αD−1 Ak∞ < 1
(c) En déduire que la méthode est convergente.
Exercice 6
Soit le système suivant :  
1 α α
 α 1 α 
α α 1
où α est un paramètre réel.
1. Pour quelles valeurs de α la matrice A est elle inversible ?
2. Pour quelles valeurs de α la convergence de la méthode de Jacobi est-elle assurée ?
3. Donner la matrice d'itérations TJ de la méthode de Jacobi, pour quelles valeurs de α la méthode
de Jacobi converge pour ce système linéaire ?
4. Pour quelles valeurs de α la convergence de la méthode de Gauss-Seidel est-elle assurée ?
5. Donner la matrice d'itérations TGS de la méthode de Gauss-Seidel.
Exercice 7
Dans Mn (R), on considère la matrice tridiagonale suivante :
 
a b 0 ··· ··· 0
 ... ... ... 
 b 0 
... ... ... .. 
 
. 

 0
A(a, b) =  .. ... ... ... ...
, a, b ∈ R
.
 
 0 
... ... ...
 
 
 0 b 
0 ··· ··· 0 b a

1. On supposera que a = 0 et b = 1. Vérier que pour tout k = 1, · · · , n,

kπ 2kπ nkπ t
Uk = (sin( ), sin( ), · · · , sin( ))
n+1 n+1 n+1

est un vecteur propre de A(0, 1) associé à la valeur propre λk = 2 cos( n+1

kπ
) (On utilise la relation
α−β α+β
trigonométrique : sin(α) + sin(β) = 2 cos( ) sin( )).
2 2
2. En déduire le spectre de A(a, b) pour a et b quelconques.

2
 3. On veut étudier le problème
−u00 (x) = f (x), x ∈]0, 1[,
(

u(0) = u(1) = 0

Soit h = N +1 avec N ∈ N . Le problème

1 ∗ discrétisé correspondant est : étant donné le vecteur
F = (fi )1≤i≤N trouver U = (ui )1≤i≤N tel que

 − h12 (ui+1 − 2ui + ui−1 ) = fi ,


1 ≤ i ≤ N,
(1)
u0 = uN +1 = 0


Montrer que le système (1) est équivalent à la résolution de AU = F où on explicitera la matrice

A = (aij )1≤i,j≤N .
4. Calculer les valeurs propres de la matrice TJ de Jacobi.
5. Calculer ρ(TJ ) et déduire la convergence de cette méthode.
Exercice 8
Etant donnée la fonction dénie par/
x2 + y 2
 
 
x 2y
g =
 
y 4 − x2 − y 2

2x
1. Trouver les point xes de g .
2. Chercher si ces points xes sont attratifs ou répulsifs.
Exercice 9

1. Obtenir les points xes de l'application :

q
x1 = 2 − x22
√
x2 = x1

2. Vérier si ces points xes sont attractifs.

3. Eectuer les trois premières itérations de la méthode du poin xe à partir de x(0) = (0, 0).
Correction 1
    
2 −1 x1 1
On considère le système linéaire Ax = b : =
−1 2 x2 2
1. La matrice A du système est elle convergente ?
On
%(A) = 3 > 1
alors la matrice A et divergente.
2. Etudier la concergence de la méthode de Jacobi.
Puisque la matrice A est à diagonale strictement dominante alors la méthode de Jacobi appliquée
à ce système converge.
Correction 2

Correction 3

3
  
1 2 −2
1. A =  1 1 1  :
2 2 1
Avec A = D − L − U ,
 
0 −2 2
Jacobi : M = D = I , N = L + U =  −1 0 −1  et
−2 −2 0
 
0 −2 2
−1
TJ = M N =  −1 0 −1 
−2 −2 0
3
det(λI − TJ ) = λ =⇒ sp(TJ ) = {0} =⇒ ρ(TJ ) = 0
   
1 0 0 0 −2 2
Gauss-Seidel : M = D − L =  1 1 0 , N =  0 0 −1  et
2 2 1 0 0 0
 
0 −2 2
TGS = M −1 N =  0 2 −3 
0 0 1
sp(TGS ) = {0, 2, 1} =⇒ ρ(TGS ) = 2.
Conclusion : la méthode de Jacobi converge et la méthode de Gauss-Seidel diverge.
 
2 −1 1
2. A =  2 2 2  :
−1 −1 2
Jacobi : M = D 
= 2I ,
  
0 1 −1 0 1 −1
N = L + U =  −2 0 −2  et TJ = M −1 N = 21  −2 0 −2 
1 1 0 1 1 0
3
√ √
det(λI − TJ ) = λ + 5λ =⇒ sp(TJ ) = {0, ± 5} =⇒ ρ(TJ ) = 5
 
2 0 0
Gauss-Seidel : M = D − L =  2 2 0 ,
−1 −1 2
   
0 1 −1 0 0.5 −0.5
N =  0 0 −2  et H = M −1 N =  0 −0.5 −0.5 
0 0 0 0 0 −0.5
sp(TGS ) = {0, ±0.5} =⇒ ρ(TGS ) = 0.5.
Conclusion : la méthode de Jacobi diverge et la méthode de Gauss-Seidel converge.
La conclusion générale est que : lorsque les méthodes de Jacobi et de Gauss-Seidel sont les deux
convergentes alors c'est la méthode de Gauss-Seidel qui converge plus rapidement que celle de
Jacobi.
Correction 4
On considère le système linéaire Ax = b avec :
 
1 2(1 − β) 0
A= 1 2 0 
0 0 1

où β est un paramètre réel.

1. Ecrire explicitement les itérations de Jacobi et de Gaus-Seidel.

4
 (a) La méthode de Jacobi :
x(0) donné dans IR3


pour k ∈ IN ∗





 (k+1) (k)
x1 = b1 − 2(1 − β)x2
(k+1) b2 1 (k)
− x1


 x2 =


 (k+1)
 2 2
x3 = b3
(b) La méthode de Gauss-Seidel :
x(0) donné dans IR3


pour k ∈ IN ∗





 (k+1) (k)
x1 = b1 − 2(1 − β)x2
(k+1) b2 (k)
+ (1 − β)x2


 x2 =


 (k+1)
 2
x3 = b3

2. Sans calculer les matrices d'itérations, donner une condition susantes sur le paramètre β pour
que les deux méthodes convergent.
On sait que si A est une matrice à diagonale strictement dominante, alors les méthodes de
Gauss-Seidel et de Jacobi sont convergentes. On voit bien que cette condition est satisfaite par
la deuxième et la troisième ligne de la matrice A. Il sut alors d'imposer
1 > |2(1 − β)|,

d'où
1 3
<β< .
2 2
3. Calculer les matrices d'itération TJ et TG.S
D'après la première question, on a :
 
0 2(β − 1) 0
TJ  − 12 0 0 
0 0 0
et  
0 2(β − 1) 0
TG−S  0 1−β 0 
0 0 0
4. Etablir pour quelles valeurs de β les deux méthodes sont convergentes.
(a) Pour la méthode de Jacobi, les valeurs propres de TJ sont :
√
si

± √1 − β β≤1
λ1 = 0, λ2,3 =
±i β − 1 si β>1

alors p
%(TJ ) = |1 − β|
Alors la méthode de Jacobi converge si et seulement si
0<β<2

(b) Pour la méthode de Gauss-Seidel, les valeurs propres de TG−S sont :

λ1,2 = 0, λ3 = 1 − β

5
 alors
%(TG−S ) = |1 − β|
Alors la méthode de Jacobi converge si et seulement si
0<β<2

5. Indiquer quel est le rapport entre les vitesses de convergence de ces méthodes.
On voit que %(TG−S ) = %(TJ )2 , alors, en cas de convergence, %(TG−S ) < %(TJ ) et donc la
méthode de Gauss-Seidel converge plus vite que celle de Jacobi.
Correction 5

Soit A une matrice carrée d'ordre n > 0, A = (aij )i,j=1,...,n inversible et b ∈ IRn . On veut résoudre le
système linéaire
Ax = b
On note D la matrice diagonale constituée de la diagonale de A. Soit α 6= 0, on étudie la méthode
itérative
x(k+1) = (I − αD−1 A)x(k) + αD−1 b.
1. Montrer que la méthode est consistante i.e. si (x(k) )k≥0 converge vers x alors x est solution du
système Ax = b.

On fait tendre k vers +∞, on obtient

x = (I − αD1 A)x + αD1 b

ou encore
α(D−1 A)x = αD−1 b
Alors Ax = b car α 6= 0.
2. Exprimer les coecients de la matrice D−1 A en fonction de ceux de A.

Soient {i, j} ∈ 1, ..., n. Alors le coecient (D−1 A)ij est donné par
n
X
(D−1 A) ij = (D−1 )ik (A)kj
k=1
= (D−1 )ii (A)ij
aij
=
aii
ou encore
si
(
1 i=j
(D−1 A)ij = aij
si i 6= j
aii
3. On suppose que 0 < α ≤ 1 et que A est à diagonale strictement diminante
(a) Montrer que la méthode est bien dénie (i.e D est inversible).

La méthode est bien dénie si et seulement si D1 existe, autrement dit

aii 6= 0∀1 ≤ i ≤ n

Or, X
∀i, 1 ≤ i ≤ n, |aii| > |aij| ≥ 0
j6=i

Alors |aii| > 0 . D'où la méthode est bien dénie.

6
 (b) Montrer que kI − αD−1 Ak∞ < 1
Posons Jα = I − αD−1 A Les coecients de Jα sont donnés par

si
(
1−α i=j
(Jα )ij = aij
−α si i 6= j
aii
Fixons i dans 1, ..., n. Alors
Pn P
j=1 |(Jα )ij | = |(Jα )ii | + =i |(Jα )ij |
j6P
j6=i |aij |
= |1 − α| + |α|
|aii |
< |1 − α| + |α|
= 1

Alors n
X
max |(Jα )ij | < 1
i
j=1

c-à-d
kJα k∞ < 1.

(c) En déduire que la méthode est convergente.

On a kJα k∞ < 1, donc le rayon spectral de la matrice d'itération Jα de la méthode satisfait
ρ(Jα ) < 1., qui montre que la méthode est convergente.
Remarque Pour α = 1, la méthode ci-dessus est celle de Jacobi.
Correction 6
Soit le système suivant :  
1 α α
 α 1 α 
α α 1
où α est un paramètre réel.
1. Pour quelles valeurs de α la matrice A est elle inversible ?
Il sut que
−1
det(A) 6= 0 ou encore α 6= 1 et α 6= .
2
2. Pour quelles valeurs de α la convergence de la méthode de Jacobi est-elle assurée ?
Pour que la méthode de Jacobi converge, il sut que la matrice A soit à diagonale strictement
dominante, c-à-d
1 > 2|α|
. autrement dit
1 1
− <α< .
2 2
3. Donner la matrice d'itérations TJ de la méthode de Jacobi, pour quelles valeurs de α la méthode
de Jacobi converge pour ce système linéaire ?
 
0 −α −α
TJ =  −α 0 −α 
−α −α 0

La méthode de Jacobi converge ⇔ %(TJ ) < 1 or %(TJ ) = 2|α| alors

1 1
La méthode de Jacobi converge ⇔ α ∈] − , [.
2 2

7
 4. Pour quelles valeurs de α la convergence de la méthode de Gauss-Seidel est-elle assurée ? Pour
que la méthode de Gauss-Seidel converge, il sut que la matrice A soit à diagonale strictement
dominante, c-à-d
1 > 2|α|
. autrement dit
1 1
− <α< .
2 2
5. Donner la matrice d'itérations TGS de la méthode de Gauss-Seidel.
La matrice de Gauss-Seidel est
 
0 −α −α
TGS = 0 α2 α2 − α 
2 3 2
0 α − α −α(α − α) + α 2

Correction 7

Dans Mn (R), on considère la matrice tridiagonale suivante :

 
a b 0 ··· ··· 0
 ... ... ... 
 b 0 
... ... ... .. 
 
. 

 0
A(a, b) =  .. ... ... ... ...
, a, b ∈ R
.
 
 0 
... ... ...
 
 
 0 b 
0 ··· ··· 0 b a

1. On supposera que a = 0 et b = 1. Vérier que pour tout k = 1, · · · , n,

kπ 2kπ nkπ t
Uk = (sin( ), sin( ), · · · , sin( ))
n+1 n+1 n+1

est un vecteur propre de A(0, 1) associé à la valeur propre λk = 2 cos( n+1

kπ
) (On utilise la relation
α−β α+β
trigonométrique : sin(α) + sin(β) = 2 cos( ) sin( )).
2 2
Pour tout j = 1, · · · , n, il faut calculer : xj+1 + xj−1 avec xj = sin( n+1
jkπ
).
En utilisant la relation trigonométrique :
a−b a+b
sin(a) + sin(b) = 2 cos( ) sin( )
2 2
on obtient pour tout j = 1, · · · , n :

xj+1 + xj−1 = sin( (j+1)kπ (j−1)kπ

n+1 ) + sin( n+1 )
kπ
= 2 cos( n+1 )xj

d'où, uk est un vecteur propre associé à la valeur propre λk = 2 cos( n+1

kπ
).
2. En déduire le spectre de A(a, b) pour a et b quelconques.
On a A(a, b) = aIn + bA(0, 1).
Si b = 0, A(a, 0) = aIn ce qui donne sp(A(a, 0)) = {a}.
Supposons que b 6= 0, alors :
λ ∈ sp(A(a, b)) =⇒ ∃v 6= 0/A(a, b)v = λv
=⇒ A(0, 1)v = λ−a λ−a
b v =⇒ b ∈ sp(A(0, 1))

8
 de plus
λ ∈ sp(A(0, 1)) =⇒ ∃v 6= 0/A(0, 1)v = λv
=⇒ A(a, b)v = aIn v + bA(0, 1)v = (a + bλ)v =⇒ a + bλ ∈ sp(A(a, b))
D'où, sp(A(a, b)) = {a + 2b cos( n+1
kπ
), k = 1, · · · , n}.
3. On veut étudier le problème
−u00 (x) = f (x), x ∈]0, 1[,
(

u(0) = u(1) = 0

Soit h = N +1 avec N ∈ N . Le problème

1 ∗ discrétisé correspondant est : étant donné le vecteur
F = (fi )1≤i≤N trouver U = (ui )1≤i≤N tel que
 − h12 (ui+1 − 2ui + ui−1 ) = fi ,

1 ≤ i ≤ N,
(1)
u0 = uN +1 = 0


Montrer que le système (1) est équivalent à la résolution de AU = F où on explicitera la matrice

A = (aij )1≤i,j≤N .

Le système s'écrit :


 −2u1 +u2 = f1


1  .

− 2 ..
h 



uN −1 −2uN = fN


ce qui donne le système AU = F avec :

 
2 −1 0 0
1  −1 2 −1... 0 
A= 2 .
h  ..
 

−1 2 −1 
0 ··· 0 −1 2
et  
f1

 f2 

 f3 
..
 
F =
.

 
..
 
.
 
 
fN
4. Calculer les valeurs propres de la matrice TJ de Jacobi.
A = D − L − U avec
   
0 0 0 0 0 1 0 0
2 1  1 ...
 0  1  ... 0 
D = 2 I, L = 2  .  et U = 2  ..
h  ..
  
h h  .

0  1 
0 ··· 0 1 0 0 ··· 0 0 0
d'où :  
0 1 0 ··· 0
1 1 0
 1 0 
TJ = D−1 L + D−1 U =  .
2  ..



0 ··· 0 1 0

9
5. Calculer ρ(TJ ) et déduire la convergence de cette méthode.
kπ
D'après les questions précédentes : sp(TJ ) = {cos( ); k = 1, . . . , n} alors
n+1
kπ
ρ(TJ ) = max cos( )
1≤k≤n n+1
or
kπ
0< <π
n+1
alors
kπ
| cos( )| < 1
n+1
d'où la méthode de Jacobi converge.

10