ANALYSE

NUMÉRIQUE I
Exercices corrigés

Dr. Hafidha SEBBAGH

Dr. Ibtissem DIDI

Ecole supérieure en sciences

appliquées Tlemcen
2018
Manuscrit d’analyse numérique I
Exercices corrigés

Hafidha DALI YOUCEF née SEBBAGH

Docteur en mathématiques option analyse numérique
Ibtissem DIDI
Docteur en automatique option contrôle des processus
Préface

Ce manuscrit est destiné aux élèves inscrit en deuxième année cycle préparatoire,
à l'école supérieure en sciences appliquées. Son contenu, correspond au programme
ociel de la matière Analyse numérique du premier semestre. Il a été rédigé dans le
but de permettre d'avoir un outil de travail et de référence recouvrant les connaissances
qui leur sont demandés.
L'objet de ce manuscrit est de proposer une explication succincte des concepts vu
en cours, en plus des exercices corrigés permettant d'orienter les raisonnements vers
d'autres domaines (physique, économies, etc.), cela an d'exhiber l'intérêt et l'omni-
présence de l'analyse numérique au sens large.

3
Table des matières

1 Résolution des équations non linéaires 8

1.1 Méthode de dichotomie . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.1.1 Principe de la méthode . . . . . . . . . . . . . . . . . . . . . . . 8
1.1.2 Convergence de la méthode . . . . . . . . . . . . . . . . . . . . 9
1.1.3 Test d'arrêt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.1.4 Exercices corrigés . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.1.5 Exercices supplémentaires . . . . . . . . . . . . . . . . . . . . . 15
1.2 Méthode de point xe . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.2.1 Principe de la méthode . . . . . . . . . . . . . . . . . . . . . . . 16
1.2.2 Convergence de la méthode . . . . . . . . . . . . . . . . . . . . 16
1.2.3 Test d'arrêt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.2.4 Ordre de convergence . . . . . . . . . . . . . . . . . . . . . . . . 19
1.2.5 Exercices corrigés . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.2.6 Exercices supplémentaires . . . . . . . . . . . . . . . . . . . . . 34
1.3 Méthode de Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
1.3.1 Principe de la méthode . . . . . . . . . . . . . . . . . . . . . . . 35
1.3.2 Convergence de la méthode . . . . . . . . . . . . . . . . . . . . 35
1.3.3 Test d'arrêt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
1.3.4 Ordre de convergence . . . . . . . . . . . . . . . . . . . . . . . . 36
1.3.5 Méthode de Newton modiée . . . . . . . . . . . . . . . . . . . 37
1.3.6 Exercices corrigés . . . . . . . . . . . . . . . . . . . . . . . . . . 38
1.3.7 Exercices supplémentaires . . . . . . . . . . . . . . . . . . . . . 47
1.4 Méthode de la sécante . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
1.4.1 Principe de la méthode . . . . . . . . . . . . . . . . . . . . . . . 48
1.4.2 Convergence de la méthode . . . . . . . . . . . . . . . . . . . . 48
1.4.3 Critère d'arrêt . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
1.4.4 Exercices corrigés . . . . . . . . . . . . . . . . . . . . . . . . . . 49

2 Résolution des systèmes linéaires 52

2.1 Méthodes directes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
2.1.1 Méthode de Gauss . . . . . . . . . . . . . . . . . . . . . . . . . 53
2.1.2 Méthode LU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
2.1.3 Méthode de Cholesky . . . . . . . . . . . . . . . . . . . . . . . . 58
2.1.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
2.1.5 Exercices corrigés . . . . . . . . . . . . . . . . . . . . . . . . . . 61
2.1.6 Exercices supplémentaires . . . . . . . . . . . . . . . . . . . . . 71
2.2 Méthodes itératives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
2.2.1 Le principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
2.2.2 Étude de la convergence . . . . . . . . . . . . . . . . . . . . . . 72
2.2.3 Critère d'arrêt . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

4
 2.2.4 Méthode de Jacobi . . . . . . . . . . . . . . . . . . . . . . . . . 75
2.2.5 Méthode de Gauss-Seidel . . . . . . . . . . . . . . . . . . . . . . 76
2.2.6 Convergence de la méthode de Jacobi et de Gauss-Seidel . . . . 76
2.2.7 Méthode de Relaxation . . . . . . . . . . . . . . . . . . . . . . . 77
2.2.8 Exercices corrigés . . . . . . . . . . . . . . . . . . . . . . . . . . 80
2.2.9 Exercices supplémentaires . . . . . . . . . . . . . . . . . . . . . 93

3 Annexe 95
3.1 Théorème des valeurs intermédiaires . . . . . . . . . . . . . . . . . . . . 95
3.2 Théorème de Pythagore . . . . . . . . . . . . . . . . . . . . . . . . . . 95
3.3 Théorème de Thalès . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
3.4 Éléments matricielles . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
3.4.1 Inverse des matrices . . . . . . . . . . . . . . . . . . . . . . . . 96
3.4.2 Matrices triangulaires . . . . . . . . . . . . . . . . . . . . . . . . 96
3.4.3 Transposée d'une matrice . . . . . . . . . . . . . . . . . . . . . 96
3.4.4 Matrices symétriques . . . . . . . . . . . . . . . . . . . . . . . . 96
3.4.5 Déterminant d'une matrice . . . . . . . . . . . . . . . . . . . . . 97
3.4.6 Matrices dénies positives . . . . . . . . . . . . . . . . . . . . . 97
3.4.7 Normes matricielles . . . . . . . . . . . . . . . . . . . . . . . . . 98
3.4.8 Conditionnement d'une matrice . . . . . . . . . . . . . . . . . . 99

5
Introduction générale

E n mathématiques, il existe des problèmes qui ne peuvent pas être résolu ana-
lytiquement, par exemple, les équations algébriques de degré ≥ 5. Pour la
résolution de ce type d'équations il a été prouver qu'il n'existe pas de formule
par radicaux.

Aussi, dans certains cas les solutions analytiques existent mais sont complètement
inecaces à mettre en oeuvre en pratique, comme la résolution d'un système linéaire
Ax = b dont la solution est x = A−1 b où le calcul de A−1 devient rapidement intolé-
rable lorsque la taille de la matrice augmente. Donc souvent pour résoudre un problème
mathématique on fait appel à l'analyse numérique.

analyse numérique
L' comprend deux mots : l'analyse qui fait référence aux mathé-
matiques et le mot numérique qui fait référence au traitement informatique.
En d'autres termes c'est l'élaboration des méthodes de calcul mathématiques adap-
tées aux traitement par ordinateur qui ont pour but la résolution des problèmes concrets
qui se posent dans diérentes disciplines : physique, economie, ingénierie, etc. Ces pro-
blèmes doivent être bien posés c'est-à-dire que la solution existe, unique et dépend
continûment des données du système.

Il existe souvent plusieurs méthodes numériques pour résoudre un tel système qui
doivent être stables et bien conditionné . Cela signie que ces méthodes donnent des
résultats satisfaisants quelques soit la nature des données initiales traités par l'ordina-
teur et qu'elles soient insensibles aux petites variations de ces données.

Développer une méthode numérique revient a créer un algorithme qui est un pro-
cessus constitué par un ensemble d'opérations et de règles opératoires données pour un
calcul.

Exemple d'Algorithme : Résolution de l'équation réelle : ax + bx + c = 0

Algorithme :
1. Lire a,b, et c
2. Si a = 0
Si b = 0
Si c = 0 alors il existe une innité de solutions
Sinon il n'y a pas de solution
FinSi
−c
Sinon la solution est x =
b
FinSi

6
 Sinon calculer le discriminent ∆ = b2 − 4ac
Si ∆ < 0 alors il n'y a pas de solutions réelles
FinSi
−b
Si ∆ = 0 alors il existe une solution double x =
2a
FinSi √ √
−b − ∆ −b + ∆
Si ∆ > 0 alors il existe deux solutions x = et x =
2a 2a
FinSi
FinSi
3. Acher la solution x

La résolution par des algorithmes numériques entraîne inévitablement l'introduction

et la propagation d'erreurs d'arrondi. De plus, il est souvent nécessaire d'introduire
d'autres erreurs liées au fait qu'un ordinateur ne peut eectuer que de manière ap-
proximative des calculs impliquant un nombre inni d'opérations arithmétiques. Par
exemple, le calcul de la somme d'une série ne pourra être accompli qu'en procédant
à une troncature convenable. On doit donc dénir un problème numérique, dont la
solution dière de la solution mathématique exacte d'une erreur, appelée erreur de
troncature [1].

L'objet de ce manuscrit est d'introduire les méthodes numériques pour la résolution

Dichotomie point xe Newton sécante
des équations non linéaires ( , , et ) et des systèmes
linéaires (méthodes directes : élimination de Gauss factorisation LU Cholesky
, et ;
méthodes itératives : Jacobi Gauss Seidel relaxation
, et ). On va rappeler dans un
premier temps le principe de chaque méthode et par la suite nous allons traiter des
exercices pour mieux comprendre ces méthodes.

7
Chapitre 1
Résolution des équations non linéaires

L'objet de ce chapitre est la résolution de l'équation f (x) = 0, où f est une fonction

de R dans R. Comme exemple d'équation non linéaire on a l'équation d'état d'un gaz.
On veut déterminer le volume V occupé par un gaz de température T et de pression
p. L'équation d'état (c'est-à-dire l'équation qui lie p, V et T ) est
"  2 #
N
p+a (V − N b) = kN T,
V

où a et b sont deux coecients dépendants de la nature du Gaz, N est le nombre

de molécules contenues dans le volume V et k est la constante de Boltzmann. Il
faut donc résoudre une équation non linéaire d'inconnue V . Pour la résolution de ce
type d'équation, les méthodes analytiques sont limitées à certaines formes algébriques
(an xn + an−1 xn−1 + ...... + a0 ), n < 5 ou formes particulières. Par conséquent pour les
autres formes il faut utiliser les méthodes numériques pour trouver ou approcher les
racines.
Ces méthodes là consistent d'abord à :
1. Localiser le (ou les) zéro(s) de f en procédant à l'étude du graphe de f , puis
utiliser le théorème des valeurs intermédiaires (voir annexe) an de trouver un
intervalle qui contient une unique racine.
2. Trouver la solution en utilisant l'une des méthodes suivantes.

1.1 Méthode de dichotomie

La dichotomie est un mot grec qui signie :

tomie : vient de couper

dicho : · · · en deux.
1.1.1 Principe de la méthode
On considère un intervalle [a, b] et une fonction f de [a, b] dans R. On suppose que
f (a) × f (b) < 0 et que l'équation f (x) = 0, admet une unique solution α ∈ [a, b] .

8
 La méthode de dichotomie consiste à construire une suite (xn ) qui converge vers α
de la manière suivante :
Soit c0 le milieu de [a, b]. La racine se trouve
alors dans l'un des deux intervalles [a, c0 ] ou
[c0 , b] où bien elle est égale à c0 .

 Si f (a) × f (c0 ) < 0, alors α ∈ ] a, c0 [ . On

pose a1 = a, b1 = c0 .
 Si f (a) × f (c0 ) = 0, alors α = c0 .
 Si f (a) × f (c0 ) > 0, alors α ∈ ] c0 , b [ . On
pose a1 = c0 , b1 = b.

On prend alors c1 le milieu de [a1 , b1 ]. On

construit ainsi une suite
a+b a1 + b 1 an + b n
c0 = , c1 = , · · · , cn =
2 2 2
telle que |an − bn | <  avec  > 0.
Remarque 1 Cet algorithme réduit à chaque pas l'amplitude de la localisation d'un
facteur 2. L'erreur est donc réduite d'un facteur 2 à chaque itération. En 20 itérations
par exemple, l'erreur sera 10 fois l'erreur initiale. Cette méthode est relativement
−6

lente. Par contre elle converge dans tous les cas où la fonction change de signe au
voisinage de la racine. C'est une méthode que nous qualierons tout-terrain, lente mais
quasiment infaillible.
1.1.2 Convergence de la méthode
Théorème 1 Soit f une fonction continue sur [a, b], vériant f (a) × f (b) < 0 et soit
l'unique solution de f (x) = 0. Si l'algorithme de dichotomie arrive jusqu'à
α ∈ [a, b]
l'étape alors on a l'estimation :
n
b−a
|α − cn | ≤
2n+1
Par conséquent la suite (c ) converge vers α. C'est ainsi vrai si c
n n∈N n =α [2].
1.1.3 Test d'arrêt
Pour que la valeur de cn de la suite de la nième itération soit une valeur approchée
de α à  > 0 près. Il sut que n vérie :
b−a
≤
2n+1
On a alors
b−a
|α − cn | ≤ ≤
2n+1

9
Ce qui permet de calculer à l'avance le nombre nécessaire n ∈ N d'itérations assurant
la précision .
 
b−a
ln
b−a b−a 
n+1
≤  ⇐⇒ ≤ 2n+1 ⇐⇒ n ≥ −1
2  ln(2)
1.1.4 Exercices corrigés

Exercice 1 On considère l'équation f (x) = x exp(x) − 1 = 0.

2

1. Trouver un intervalle I = [a, b] de longueur 1 contenant la racine α de f (x).

2. Calculer le nombre d'itérations nécessaires pour avoir la solution avec une
précision  = 10 .
−4

3. Calculer les cinq premiers itérés en utilisant la méthode de dichotomie.

Solution
1. D'après le graphe de f , on remarque qu'il
existe un α ∈ [0, 1].
Vérions le en utilisant le théorème des va-
leurs intermédiaires :
*f est continue sur [0, 1].
*f (0) × f (1) = (−1) × (1.71) < 0.
*f 0 (x) = x exp(x)(2 + x) > 0 sur [0, 1].
Donc d'après le théorème des valeurs inter-
médiaires il existe un unique α ∈ [0, 1].
2. On a
|b − a|
<
2n+1
on a a = 0 et b = 1, donc pour  = 10−3 , on obtient :
ln(103 )
n≥ −1
ln(2)
⇒ n ≥ 8, 96

10
 3. On va utiliser le tableau suivant pour calculer α :
an + b n
n an bn f (an ) f (bn ) cn = f (cn )
2
0 0 1 ⊕ 0.5
1 0.5 1 ⊕ 0.75 ⊕
2 0.5 0.75 ⊕ 0.625
3 0.625 0.75 ⊕ 0.6875
4 0.6875 0.75 ⊕ 0.71875 ⊕
5 0.6875 0.71875 ⊕ 0.703125
6 0.703125 0.71875 ⊕ 0.7109375
7 0.703125 0.7109375 ⊕ 0.70703125
8 0.703125 0.70703125 ⊕ 0.705078125
9 0.703125 0.705078125 ⊕ 0.704101562
10 0.703125 0.704101562 ⊕ 0.70387031
11 0.703125 0.70387031 ⊕ 0.703497655

À partir de ce tableau, on a :

|b11 − a11 | = 7.45 × 10−4 < 10−3

Donc
α ' 0.703497655

Exercice 2 Soit f (x) = x − 1.10.

12

1. Donner une approximation de (1.10) dans l'intervalle [1, 1.1], en utilisant

1

la méthode de dichotomie avec une tolérance de 10 .

12
−3

2. Calculer le nombre d'itérations nécessaires pour avoir la solution avec une

précision de 10 . −3

Solution

1. On a :
*f (1) × f (1.1) = −0.10 × 2.038 < 0
*f 0 (x) = 12x11 > 0 sur [1, 1.1]
*f continue sur [1, 1.1]
Donc d'après le théorème des valeurs intermédiaires, il existe une racine dans
[1, 1.1].
On va utiliser le tableau suivant pour estimer la solution.

11
 an + b n
n an bn f (an ) f (bn ) cn = f (cn )
2
0 1 1.10 ⊕ 1.05 ⊕
1 1 11.05 ⊕ 1.025 ⊕
2 1 1.025 ⊕ 1.0125 ⊕
3 1 1.0125 ⊕ 1.00625
4 1.00625 1.0125 ⊕ 1.00937 ⊕
5 1.00625 1.00937 ⊕ 1.00781
6 1.00781 1.00937 ⊕ 1.00859 ⊕
7 1.00781 1.00859 ⊕ 1.00820 ⊕

À partir de ce tableau, on a :

|b7 − a7 | = 7.8 × 10−4 < 10−3

Donc 1
(1.10) 12 ' 1.00820
2. on a :  
1 0.1
n ≥ ln −1
2 
n ≥ 5.64
Cela veut dire qu'on a au minimum 6 itérations pour estimer la solution à 10−3
près.

Exercice 3 Soit f (x) = −39 − 43x + 39x − 5x .2 3

1. Montrer que l'équation f (x) = 0 admet des racines et isoler chacune d'elles
dans un intervalle. .
2. Calculer la solution x ∈ [2, 3] par la méthode de dichotomie pour un  = 10 . −3

Solution
1. Df = R
f 0 (x) = −43 + 78x − 15x2
Calculons le ∆ pour résoudre l'équation
f 0 (x) = 0.
∆ = (−78)2 − 4(−43)(−15) = 3504
donc, on a :
 √
 −78 − 3504
 x1 =
 = 4.57
−30
√
 −78 + 3504
 x2 =
 = 0.62
−30

12
 Alors on a le tableau de variations suivant :

x −∞ 0.62 4.57 +∞

f 0 (x) − 0 + 0 −

+∞ 101.7
f (x)
−51.86 −∞

D'après tableau de variations de f et le graphe de f (x), on remarque qu'il existe

deux solutions positives et une solution négative.

α1 ∈ [2, 3], α2 ∈ [5, 7] et α3 ∈ [−1, 0]

2. On a :
*f (2) × f (3) = −9 × 48 < 0
*f 0 (x) > 0 sur [2, 3]
*f continue sur [2, 3]
Donc d'après le théorème des valeurs intermédiaires, il existe une unique solution
α1 ∈ [2, 3].

an + b n
n an bn f (an ) f (bn ) cn = f (cn )
2
0 2 3 ⊕ 2.5 ⊕
1 2 2.5 ⊕ 2.25 ⊕
2 2 2.25 ⊕ 2.125
3 2.125 2.25 ⊕ 2.1875 ⊕
4 2.125 2.1875 ⊕ 2.15625
5 2.15625 2.1875 ⊕ 2.171875 ⊕
6 2.15625 2.171875 ⊕ 2.1640625
7 2.1640625 2.171875 ⊕ 2.16796875 ⊕
8 2.164625 2.16796875 ⊕ 2.166015625 ⊕
9 2.164625 2.166015625 ⊕ 2.165038813
10 2.165038813 2.166015625 ⊕ 2.165527219

A partir de ce tableau, on voit que

|b10 − a10 | = 9.768 × 10−4 < 10−3
donc
α1 ' 2.165527219

Exercice 4 Soit la fonction f (x) = cosh(x) + cos(x) − γ.

1. Pour γ = 1, 2, 3, étudier la fonction f et trouver graphiquement un intervalle
γ

qui contient le zéro de f .

2. Calculer les zéros positifs def par la méthode de dichotomie avec une tolé-
γ

rance de 10 .
γ
−3

13
Solution
Étude de fγ :
On a
exp(x) + exp(−x)
cosh(x) =
2
exp(x) − exp(−x)
sinh(x) =
2
alors,
* lim fγ (x) = +∞
x→±∞
*fγ0 (x) = sinh(x) − sin(x) = 0 ⇐⇒ x = 0

Rappellons nous que :

Pour x > 0, on a sin(x) < x < sinh(x)
et pour x < 0, on a sinh(x) < x < sin(x).
*fγ00 (x) = cosh(x) − cos(x) > 0 pour tout x 6= 0.

Donc d'après le graphe de fγ , on a :

 Pour γ = 1, la fonction n'a pas de zéro réel,
 Pour γ = 2, la fonction a un unique zéro α = 0 qui est de multiplicité quatre
(c'est-à-dire : f2 (α) = f20 (α) = f200 (α) = f2(3) (α) = 0 et f2(4) (α) 6= 0),
 Pour γ = 3, la fonction a deux zéros distincts, un dans l'intervalle [−2, −1] et
l'autre dans [1, 2].
Méthode de dichotomie :
 Pour γ = 1, la fonction n'a pas de zéro réel,
 Pour γ = 2, on ne peut pas utiliser la méthode de dichotomie pour trouver un
intervalle [a, b] sur lequel f2 (a) × f2 (b) < 0.
 Pour le cas γ = 3, on va calculer le zéro qui se trouve dans l'intervalle [1, 2],
pour cela utilisons le tableau suivant :
an + b n
n an bn f (an ) f (bn ) cn = f (cn )
2
0 1 2 ⊕ 1.5
1 1.5 2 ⊕ 1.75 ⊕
2 1.5 1.75 ⊕ 1.625 ⊕
3 1.5 1.625 ⊕ 1.5625
4 1.5625 1.625 ⊕ 1.59375
5 1.59375 1.625 ⊕ 1.609375
6 1.609375 1.625 ⊕ 1.6171875
7 1.6171875 1.625 ⊕ 1.62109375
8 1.62109375 1.625 ⊕ 1.623046875
9 1.623046875 1.625 ⊕ 1.624023438
10 1.624023438 1.625 ⊕ 1.624511719

À partir de ce tableau, on a

|b10 − a10 | = 9.765 × 10−4 < 10−3

donc
α ' 1.624511719

14
 Exercice 5 On considère le problème du calcul de l ∈ [0, π] tel que l = 1− 41 cos(l).
1. Montrer qu'on peut utiliser la méthode de dichotomie pour approcher l.
2. Que vaut l'approximation de l après 3 itérations? Quelle est l'erreur maxi-
male qu'on obtient après 3 itérations?.
Solution
1. Soit f : [0, π] → R la fonction dénie par
1
f (x) = 1 − cos(x) − x
4
on a :
* f ∈ C ∞.
* f (0) × f (π) = 0.75 × (−1.89) < 0.
1
* f 0 (x) = sin(x) − 1 < 0.
4
Donc d'après le théorème des valeurs intermé-
diaires, il existe un unique l tel que f (l) = 0.
Alors on peut utiliser la méthode de dichotomie
pour approcher l.
On remarque aussi que le graphe de la fonction
f nous montre qu'il existe un unique zéro dans
l'intervalle [0, π].
2. Utilisons le tableau suivant pour calculer les trois itérations :
an + b n
n an bn f (an ) f (bn ) cn = f (cn )
2
0 0 π ⊕ π/2
1 0 π/2 ⊕ π/4 ⊕
2 π/4 π/2 ⊕ 3π/8
3 π/4 3π/8 ⊕ 5π/16

5π
À partir de ce tableau, on a l ≈ . L'erreur qu'ont obtient après trois itérations est
16
b−a π
au plus égale à la largeur de l'intervalle [a3 , b3 ], c'est-à-dire inférieure à 3 = .
2 8

1.1.5 Exercices supplémentaires

Exercice 6 On veut calculer les racines de l'équation

√
x π 3
f (x) = − sin(x) + + =0
2 6 2

dans l'intervalle . Peut-on appliquer la méthode de dichotomie pour calcu-

h π i
− ,π
ler les racines de cette équation? Pourquoi? Dans le cas où c'est possible, estimer
2

15
 le nombre minimal d'itérations nécessaires pour calculer le(s) zéro(s) avec une to-
lérance de  = 10 , après avoir choisi un intervalle convenable.
−10

Exercice 7 (Fond d'investissement)

Un compte d'épargne donne un taux T ∈ [0, 1] d'intérêt par an avec un virement
annuel d'intérêts sur le compte. Cela signie que si le premier janvier 2017 on met
v euros sur ce compte, à la n de la n année (i.e. au 31 décembre 2017+n) on en
ème

retire v (1 + T ) euros. On décide alors d'ajouter au début de chaque année encore

n

v euros. Cela signie qui si on verse ces v euros le premier janvier 2017+m avec
0 < m < n, au 31 décembre 2017+n ajoutent v (1 + T ) euros. Si à la n de
n−m

la n année on en retire un capital de M > v euros. Quel est le taux d'intérêts

ième

annuel de cet investissement?

Indication :
À la n de la nième année, le capital versé au premier janvier 2017 est devenu v (1 + T )n ,
celui versé au premier janvier 2018 est devenu v (1 + T )n−1 , par conséquent, le capital
nal M est relié aux taux d'intérêts annuel T par la relation
n
X (1 + T )n − 1 1+T
M =v (1 + T )k = v =v ((1 + T )n − 1) .
k=1
(1 + T ) − 1 T

On en déduit que T est racine de l'équation algébrique non linéaire f (T ) = 0 où

1+T
f (T ) = v ((1 + T )n − 1) .
T

Donc il reste à étudier la fonction f (T ).

Supposons que v=1000 euros et qu'après 5 ans M=6000 euros. On calcul la solution
en utilisant la méthode de dichotomie à 10−12 près.
1.2 Méthode de point xe
1.2.1 Principe de la méthode
Le principe de cette méthode consiste à transformer l'équation f (x) = 0 en une
équation équivalente g(x) = x où g est une fonction bien choisie. Ceci est toujours
possible en posant g(x) = x − f (x). Le point α est alors un point xe de g .
Approcher les zéros de f revient à approcher les points xe de g . Le choix de la fonction
g est motivé par les exigences du théorème du point xe.
1.2.2 Convergence de la méthode
Théorème 2 ( Théorème du point xe) (condition susante de convergence glo-
bale)
Soit g une fonction de classe C sur un intervalle [a, b] ⊂ R telle que :
1

1. g(x) ∈ [a, b] , ∀x ∈ [a, b] (on dit que l'intervalle [a, b] est stable par g(x). Si on
écrit I = [a, b], alors g(I) ⊂ I .
16
 2. ∃k ∈ R, 0 < k < 1 tel que |g (x)| ≤ k < 1, k = max |g (x)|. On dit que g est
0 0

strictement contractante
x∈[a,b]

Alors
 g admet un unique point xe dans I = [a, b].
 Pour tout x ∈ [a, b], la suite (x ) dénie par la récurrence :
0 n n∈N

xn+1 = g(xn )
Vérie :
∀n ∈ N, xn ∈ [a, b] et lim x = α
n→+∞
n

Théorème 3 (Condition de convergence locale)

Soient α ∈ R et g(x) une fonction de classe C dénie sur un voisinage de α.
1

Pour x ∈ R donné. On dénit la suite (x ) par la récurrence x = g(x ). Alors si

g(α) = α et |g (x)| < 1, il existe un h > 0 tel que pour tout x appartenant à l'intervalle
0 n n n+1 n
0

I = [α − h, α + h], on a :
0

∀n ∈ N, x ∈ I et lim x = α
n n
n→+∞

Enn, α est l'unique solution de l'équation g(x) = x sur I .

Corollaire 1 Soit α une solution de l'équation g(α) = α et g continue au voisinage
0

de α, alors on a les trois cas suivants :

 Point xe attractif : Si |g (x)| < 1 alors il existe un intervalle [a, b] contenant
0

α pour lequel ∀x ∈ [a, b] la suite (x ) dénie par x = g(x ) converge vers

α.
0 n n∈N n+1 n

 Point répulsif : Si |g (x)| > 1 alors ∀x

0
6= 0 la suite (x ) dénie par
= g(x ) ne converge pas vers α.
0 n n∈N
x n+1 n

17
  Point xe douteux : Si |g (x)| = 1, on ne peut pas conclure, il peut y
0

avoir convergence ou divergence. Pour cela on doit trouver un bon g qui vérie
|g (x)| < 1.
0

Remarque 2 Lorsque α est un1 point répulsif de g, celle-ci devient bijective au voisi-
nage de α et (g ) (α) = |g (α)| < 1. Par conséquent, le point α devient un point
−1 0
0

attractif de g . En eet, si |g (α)| > 1 alors g est strictement monotone au voisinage

−1 0

de α.
1.2.3 Test d'arrêt
On a la suite (xn ) converge vers α tel que g(α) = α. En xant la tolérance  on estime
qu'on atteint la précision  dès qu'il existe un n0 ∈ N tel que :
|xn0 +1 − xn0 | < 
Néanmoins, la situation devient plus concrète lorsque g 0 est négative au voisinage de
α. En eet :
Proposition 1 Soit g : [a, b] −→ [a, b] de classe C . On suppose que g admet un
1

unique point xe α ∈ [a, b] vériant −1 < g (x) < 0 pour tout x dans l'intervalle de
0

convergence V de α. Soit la suite (x ) dénie par :

α n

x0 ∈ Vα
xn+1 = g(xn ); ∀n ≥ 0

18
Alors
∀n ∈ N, |x − α| ≤ |xn+1 −x | n+1 n

Par conséquent, soit n tel que |x − α| < , alors (x ) approche α à  près.

0 n0 n0

Pour la démonstration (voir [2]).

Estimation de l'erreur :
Le nombre minimal d'itérations pour que la solution soit approchée avec une pré-
cision  est :
|xn − α| < 
Sachant que
kn
|xn − α| ≤ |x1 − x0 |
1−k
Donc h i
(1−k)
ln |x1 −x0 |
n> , k = max |g 0 (x)|
ln(k) I

1.2.4 Ordre de convergence

Dénition 1 On dit que la convergence de (x ) vers α est d'ordre p (p ∈ R ) s'il ∗

existe une constante c > 0 telle que

n +

= c avec e = |x − α|
e n+1
lim p n n
n→+∞ e n

Dénition 2
 Lorsque p = 1, la convergence de x vers α est dite linéaire.
 Lorsque p = 2, la convergence de x vers α est dite quadratique.
n
n

Théorème 4 Si la suite (x ) , dénie par x = g(x ) converge vers α et si g est

susamment dérivable au voisinage de α, alors l'ordre de la méthode est donné par :
n n n+1 n

g 0 (α) = g 00 (α) = ....g (p−1) (α) = 0



g (p) (α) 6= 0
De plus on :
en+1 g (p) (α)
lim p =
n→+∞ en p!
Donc on remarque que plus p est grand plus la vitesse de la convergence est rapide.
Pour la démonstration (voir [3]).
Concernant la méthode du point xe on a p = 1 donc la convergence est linéaire,
car on a :

en+1 = xn+1 − α = g(xn ) − g(α) = g 0 (α)en + en (n)

où (n) → 0 quand n −→ +∞.
Alors
en+1
lim = g 0 (α)
n→+∞ en

Donc dès que g 0 (α) 6= 0 la convergence est d'ordre 1.

19
Remarque 3 La convergence de la méthode du point xe est de type linéaire donc lente
et souvent dicile à réaliser en pratique. De plus certains points xes dits instables ne
peuvent être atteints.
1.2.5 Exercices corrigés

Exercice 8 Pour approcher les racines réelles de la fonction f : R → R par

f (x) = x2 − 3x + 2 exp(x)

On veut utiliser la méthode du point xe suivante :

 x donné

0

= ϕ(x ) pour tout n ∈ N où ϕ(x) =

2
x +2
 x n+1 n
3
1. Montrer qu'il existe deux racines réelles l < l de f .
2. Faire l'étude graphique de la convergence de la méthode de point xe et mon-
1 2

trer que :
 Si x ∈] − 2, 2[ alors la suite converge vers l .
 Si x = ±2 alors x = l pour tout n ∈ N.
0 1

 Si x < −2 où x > 2 alors la suite diverge vers +∞.

0 n 2

3. Notons par [a, b] l'intervalle maximal contenant l pour lequel le théorème de

0 0

point xe s'applique. Calculer a et b et expliquer pourquoi la suite converge

1

vers l même si x ∈] − 2, 2[\[a, b] .

1 0

Solution
1. D'après le graphe de f , il existe deux solutions, l1 = 1 et l2 = 2.

2. Comparons le graphe de ϕ à l'identité :

L'étude graphique montre que la suite converge quelque soit x0 ∈ [−2, 2]. Plus
précisément, on voit que :

20
  Si x0 = −2 et x0 = 2 alors x2 = 2
pour tout n ∈ N∗ .
 Si x0 ∈]−2, −1[ et x0 ∈]1, 2[ alors
xn & 1 pour tout n ∈ N∗ .
 Si x0 = −1 et x0 = 1 alors x2 = 1
pour tout n ∈ N∗ .
 Si x0 ∈] − 1, 1[ alors xn % 1 pour
tout n ∈ N∗ .
 Si x0 > 2 alors xn % +∞ pour
tout n ∈ N∗ .
3. L'intervalle maximale pour appliquer le théorème de point xe est déni comme
2
le plus grand intervalle pour lequel |ϕ0 (x)| < 1 c'est-à-dire −1 < x < 1. Donc
3
x ∈ ] − 1.5, 1.5 [ .
On remarque que ] − 1.5, 1.5[⊂ [−2, 2]. Or si x0 ∈ [−2, −1.5[ ou x0 ∈ [1.5, 2[,
alors x1 = ϕ(x0 ) < |x0 | ∈]1, 2[ car ϕ(x) < x lorsque x ∈]1, 2[ et on montre que
la suite (xn )n∈N est décroissante et minorée par l1 donc convergente.
Comme l'unique limite possible est l1 on conclut que xn & l1 .

Exercice 9 Pour approcher les racines réelles de la fonction

f :R→R
x 7−→ x3 − x2 − 1

On utilise deux méthodes de point xe :

x donné


pour tout n ∈ N
0
xn+1 = ϕ(xn )

où
ϕ(x) = ϕ1 (x) = x3 − x2 + x − 1 et ϕ(x) = ϕ (x) = √x + 1
2
3 2

1. Montrer qu'il existe une unique racine réelle l de f . Montrer que l ∈ [1, 2].
2. Étudier la convergence des deux méthodes de point xe et, si elles convergent,
donner l'ordre de convergence.
3. Calculer l pour un  = 10 près.
−3

Solution

1. Étude de f
*Df = R et f est de classe C ∞ ,
* lim f (x) = ±∞,
x→±∞
 
2
*f (x) = 3x − 2x, f (x) = 0 ⇒ (x = 0) ∨ x =
0 2 0
.
3

21
 Voici le tableau de variations suivant :

2
x −∞ 0 +∞
3
f 0 (x) + 0 − 0 +

−1 +∞
f (x)
−∞ −1.14

*f (1) × f (2) = (−1) × 1 < 0.

*f 0 (x) > 0 sur [1, 2].
Donc d'après le théorème des
valeurs intermédiaires il existe
un unique l ∈ [1, 2] tel que
f (l) = 0.

2. La convergence de ϕ1 et ϕ2

 Étude de ϕ1
Soit ϕ1 (x) = x3 − x2 + x − 1
*Dϕ1 = R et lim ϕ1 (x) = ±∞,
x→±∞
*ϕ1 (x) = 3x2 − 2x + 1 et ϕ1 (x) = 6x − 2,
0 00

1
*ϕ1 (x) = 0 ⇔ x = .
00

3
Voici le tableau de variations de ϕ1 :

x 1 2

ϕ001 (x) +

9
ϕ01 (x)
2
5
ϕ1 (x)
0

On remarque que le max ϕ1 (x) = 9 > 1. Donc elle n'est pas contractante
0

x∈[1,2]
et que ∀x ∈ [1, 2], ϕ1 (x) ∈
/ [1, 2]. Donc elle n'est pas stable, alors on conclut
que ϕ1 (xn ) est divergente.

22
  Étude de√ϕ2
Soit ϕ2 = 3 x2 + 1,
*Dϕ2 = R et lim ϕ2 (x) = ±∞,
x→±∞

2x 2 −2 2 (x2 − 3)
*ϕ2 (x) = (x + 1) 3 et ϕ2 (x) = − .
0 00

3 9 (x2 + 1) 53
√
*ϕ2 (x) = 0 ⇔ x = ± 3.
00

Voici le tableau de variations de ϕ2 :

√
x 1 3 2

ϕ002 (x) + 0 −

0.458
ϕ02 (x)
0.419 0.455
1.70
ϕ2 (x)
1.25

On remarque que le max ϕ2 (x) = 0.458 < 1. Donc elle est contractante
0

x∈[1,2]
et que ∀x ∈ [1, 2], ϕ2 (x) ∈ [1, 2]. Donc elle est stable, alors on conclut que
ϕ2 (xn ) est convergente.
3. Le calcul de l
x0 1 x5 1.456889588
x1 1.25992105 x6 1.461623151
x2 1.37284419 x7 1.463775528
x3 1.423531047 x8 1.464754438
x4 1.446474295

On remarque que
|x7 − x8 | = 9.78 × 10−4 < 10−3
alors

l ' x8 = 1.464754438

Exercice 10 On considère la fonction f dénie par :

f (x) = ln(x) − arctan(x), x > 0
1. Montrer que l'équation f (x) = 0 admet une unique racine α qu'on localisera
dans un intervalle I entre deux entiers consécutifs.
2. On considèrela suite dénie par :
x =3
= g(x ) avec g(x) = x − ln(x) + arctan(x)
0
x n+1 n

Montrer que sa limite est α et en déduire le nombre d'itérations N qui assure

que
|xN − α| < 10−6

23
 3. Soit la suite 
x0 = 3
avec h(x) = tan(ln(x))
xn+1 = h(xn )
Cette suite converge t-elle vers α ?
4. On dénit la suite

x0 = 3
avec k(x) = exp(arctan(x))
xn+1 = k(xn )

Montrer qu'elle converge vers α et donner le nombre d'itérations P pour que

|xp − α| < 10−6

5. Déterminer la racine α de f (x) = 0 par l'une des trois méthodes précédentes

en justiant le choix de la méthode utilisée.

Solution
1. Étude de f
D'après le graphe de f on remarque qu'il
existe un unique zéro entre 3 et 4. Vérions
le en utilisant le théorème des valeurs inter-
médiaires.
*f (3) × f (4) = (−0.15) × 0.06 < 0,
*f est continue sur [3, 4],
1 1
*f 0 (x) = − 2 > 0 sur [3, 4].
x x +1
D'après le théorème des valeurs intermé-
diaires, il existe un unique α ∈ [3, 4] tel que
f (α) = 0.
2. La convergence de g
Soit g(x) = x − ln(x) + arctan(x).
Pour montrer que la suite xn+1 converge vers α, il sut de montrer que g est
contractante et stable sur [3, 4].
x−1 1 1 2x
g 0 (x) = + 2 et g 00 (x) = 2 − 2 .
x x +1 x (x + 1)2
Voici le tableau de variations de g :

x 3 4

g 00 (x) +

0.80
g 0 (x)
0.76
3.93
g(x)
3.15

24
 On remarque que le max |g 0 (x)| = k1 = 0.80 < 1, donc g est contractante et
x∈[3,4]
que ∀x ∈ [3, 4], g(x) ∈ [3, 4], donc g est stable. Alors g(xn ) converge vers α.

Nombre d'itérations
k1N
|xn − α| ≤ |x1 − x0 | < 10−6
1 − k1
 
(1−k1 )10−6
ln |x1 −x0 |
N>
ln(k1 )
N > 60.63
donc on prend

N = 61
3. Étude de la convergence de h
Soit h(x) = tan(ln(x)),
1 1
h0 (x) = [1 + tan2 (ln(x))] et h00 (x) = 2 [1 + tan2 (ln(x))]
x x
Voici le tableau de variations de h :

x 3 4

h00 (x) +

7.42
h0 (x)
1.61
5.35
h(x)
1.95

On remarque que le max |h0 (x)| = k2 = 7.42 > 1, donc h n'est pas contractante
x∈[3,4]
et que ∀x ∈ [3, 4], h(x) ∈
/ [3, 4], donc h n'est pas stable. Alors h(xn ) ne converge
pas vers α.
4. Étude de la fonction k
Soit k(x) = exp(arctan(x)),
1 −2x + 1
k 0 (x) = exp(arctan(x)) et k 00 (x) = 2 exp(arctan(x)),
x2 +1 x +1

25
 Voici le tableau de variations de k :

x 3 4

k 00 (x) −

0.34
k 0 (x)
0.22
3.76
k(x)
3.48

On remarque que le max |K 0 (x)| = k3 = 0.34 < 1, donc k est contractante et

x∈[3,4]
que ∀x ∈ [3, 4], k(x) ∈ [3, 4], donc k est stable. Alors k(xn ) converge vers α.
Nombre d'itérations
k3P
|xP − α| ≤ |x1 − x0 | < 10−6
1 − k3
 −6

ln (1−k 3 )10
|x1 −x0 |
P >
ln(k3 )
P > 12.52
donc on prend

P = 13
5. Le calcul de α
Pour estimer α on utilise la troisième méthode car P < N , donc xn+1 = k(xn )
avec k(x) = exp(arctan(x)).

x0 3 x6 3.692362115
x1 3.487013964 x7 3.692529274
x2 3.638287909 x8 3.69252771452
x3 3.678721749 x9 3.692584779
x4 3.689077084 x10 3.692584779
x5 3.691699757 x11 3.692585457

On remarque que
|x11 − x10 | = 6.7 × 10−7 < 10−6
donc
α ' x11 = 3.692585457

26
Exercice 11 Soit la fonction f (x) = x −x 1 − exp(−x)
1. Tracer l'allure du graphe de f , puis en déduire que l'équation f (x) = 0
possède une racine α négative et une racine α positive. Localiser chacun
de ces deux entiers successifs.
1 2

2. Pour déterminer ces racines, on utilise dans un premier temps la méthode

du point xe. Pour cela on propose les deux algorithmes suivants :
(k+1)
x = g (x ), avec g (x) = 1 + x exp(−x)
1
k
1

(k+1)
x = g (x ), avec g (x) = (x − 1) exp(x)
2
k
2

a- Vérier que les points xes de ces algorithmes sont des racines de l'équa-
tion f (x) = 0 puis étudier leur convergence. S'il y a convergence, dire vers
qu'elle racine.
b- Donner une approximation à 10 près, de la racine α en initialisant les
−5

itérations par x = 2.
2
(0)

Solution

1. Le graphe de f
D'après le graphe de f , on remarque qu'il existe
deux racines, α1 ∈ [−1, 0] et α2 ∈ [1, 2], on a :

 Pour α1 :
*f (−1) × f (0) < 0,
*f continue sur [−1, 0],
*f 0 (x) = x12 + exp(−x) > 0 sur [−1, 0].
Donc d'après le théorème des valeurs
intermédiaires il existe un unique
α1 ∈ [−1, 0] tel que f (α1 ) = 0.

 Pour α2 :
*f (1) × f (2) = −0.36 × 0.36 < 0,
*f continue sur [1, 2],
*f 0 (x) = x12 + exp(−x) > 0 sur [1, 2].
Donc d'après le théorème des valeurs in-
termédiaires il existe un unique α2 ∈
[1, 2] tel que f (α2 ) = 0.

a-
(i) Soit x(k+1) = g1 (xk ), avec g1 (x) = 1 + x exp(−x), vérions que les points
xes de cet algorithme sont des racines de l'équation f (x) = 0.

Pour α1 :
Montrons que g1 (α1 ) = α1 ⇐⇒ f (α1 ) = 0.

27
 g1 (α1 ) = α1 ⇐⇒ 1 + α1 exp(−α1 ) = α1
α1 − 1
⇐⇒ exp(−α1 ) =
α1
α1 − 1
⇐⇒ − exp(−α1 ) = 0
α1
⇐⇒ f (α1 ) = 0

Pour α2 :
Montrons que g1 (α2 ) = α2 ⇐⇒ f (α2 ) = 0.

g1 (α2 ) = α2 ⇐⇒ 1 + α2 exp(−α2 ) = α2
α2 − 1
⇐⇒ exp(−α2 ) =
α2
α2 − 1
⇐⇒ − exp(−α2 ) = 0
α2
⇐⇒ f (α2 ) = 0

Étude de la convergence de g1

Pour α1 ∈ [−1, 0] :
g10 (x) = (1 − x) exp(−x) et g100 (x) = (x − 2) exp(−x)

Voici le tableau de variations de g1 :

x −1 0

g100 (x) −

5.43
g10 (x)
1
1
g1 (x)
−1.71

D'après ce tableau, on remarque que le max |g10 (x)| = 5.43 > 1, donc g1 n'est
x∈[−1,0]
pas contractante et que ∀x ∈ [−1, 0], g1 (x) ∈
/ [−1, 0], donc g1 n'est pas stable.
Alors g1 (xn ) ne converge pas vers α1 .

28
Pour α2 ∈ [1, 2] :
g10 (x) = (1 − x) exp(−x) et g100 (x) = (x − 2) exp(−x)

Voici le tableau de variations de g1 :

x 1 2

g100 (x) −

0
g10 (x)
−0.13
1.36
g1 (x)
1.27

D'après ce tableau, on remarque que le max |g10 (x)| = 0.13 < 1, alors g1 est
x∈[−1,0]
contractante et que ∀x ∈ [1, 2], g1 (x) ∈ [1, 2], donc g1 est stable. Alors que g1 (xn )
converge vers α2 .
(ii) Soit x(k+1) = g2 (xk ), avec g2 (x) = (x − 1) exp(x), vérions que les points
xes de cet algorithme sont des racines de l'équation f (x) = 0.

Pour α1 :
Montrons que g2 (α1 ) = α1 ⇐⇒ f (α1 ) = 0.

g2 (α1 ) = α1 ⇐⇒ (α1 − 1) exp(α1 ) = α1

α1 − 1
⇐⇒ exp(α1 ) = 1
α1
α1 − 1
⇐⇒ = exp(α1 − 1)
α1
α1 − 1
⇐⇒ − exp(α1 − 1) = 0
α1
⇐⇒ f (α1 ) = 0

Pour α2 :
Montrons que g2 (α2 ) = α2 ⇐⇒ f (α2 ) = 0.

g2 (α2 ) = α2 ⇐⇒ (α2 − 1) exp(α2 ) = α2

α2 − 1
⇐⇒ exp(α2 ) = 1
α2
α2 − 1
⇐⇒ = exp(α2 − 1)
α2
α2 − 1
⇐⇒ − exp(α2 − 1) = 0
α2
⇐⇒ f (α2 ) = 0

29
Etude de la convergence de g2

Pour α1 ∈ [−1, 0] :

g20 (x) = x exp(x) et g200 (x) = (x + 1) exp(x).

Voici le tableau de variations de g2 :

x −1 0

g200 (x) +

0
g20 (x)
−0.36
−0.73
g2 (x)
−1

D'après ce tableau, on remarque que le max |g20 (x)| = 0.36 < 1, donc g2 est
x∈[−1,0]
contractante, et que ∀x ∈ [−1, 0], g2 (x) ∈ [−1, 0], donc g2 est stable. Alors g2 (xn )
converge vers α1 .
Pour α2 ∈ [1, 2] :

g20 (x) = x exp(x) et g200 (x) = (x + 1) exp(x).

Voici le tableau de variations de g2 :

x 1 2

g200 (x) +

14.77
g20 (x)
2.71
7.38
g2 (x)
0

D'après ce tableau, on remarque que le max |g20 (x)| = 14.77 > 1, donc g2 n'est
x∈[1,2]
pas contractante, et que ∀x ∈ [1, 2], g2 (x) ∈
/ [1, 2], donc g2 n'est pas stable. Alors
g2 (xn ) ne converge pas vers α2 .
b-
Pour calculer α2 ∈ [1, 2], on va utiliser l'algorithme suivant :

x(k+1) = g1 (xk ), avec g1 (x) = 1 + x exp(−x)

30
 x(0) 2 x(4) 1.350031356
x(1) 1.270670566 x(5) 1.349971507
x(2) 1.356605268 x(6) 1.349976937
x(3) 1.349371373

On remarque que
x(6) − x(5) = 5.43 × 10−6 < 10−5
donc
α2 ' x(6) = 1.349976937

Exercice 12 On propose de résoudre une équation f (x) = 0 en utilisant la méthode

de point xe. Dans chaque cas déterminer les points xes et leur nature. Tracer le
graphe de ϕ et quelques points de la suite.

1.ϕ : [0, 1] −→ R 2.ϕ : [0, 1] −→ R 3.ϕ : [0, 1] −→ R

1 1 1
x 7−→ x(1 − x) x 7−→ x(1 + x) x 7−→ x(1 − x2 )
2 2 2

Solution
1. ϕ : [0, 1] −→ R
1
x 7−→ x(1 − x)
2
1
ϕ0 (x) = − x et ϕ00 (x) = −1.
2

1
x 0 1
2
ϕ00 (x) − 0 −

1
ϕ0 (x) 0 1
2 −
2
1
ϕ(x) 8
0 0

31
D'après le tableau de varia-
tions de ϕ, on remarque que
le max |ϕ0 (x)| = 0.5 < 1 et
x∈[0,1]
ϕ(0) = 0, donc l1 = 0 est un point
xe attractif.

2. ϕ : [0, 1] −→ R
1
x 7−→ x(1 + x)
2
1
ϕ (x) = + x et ϕ00 (x) = 1.
0
2
Voici le tableau de variations de ϕ :

x 0 1

ϕ00 (x) +

1.5
ϕ0 (x)
0.5
1
ϕ(x)
0

D'après le tableau de variations de

ϕ, on remarque que ϕ(0) = 0 et
ϕ(1) = 1, donc l1 = 0 et l2 = 1
sont deux points xes, et on a :
ϕ0 (l1 ) = 0.5 ∈] − 1, 1[, donc l1 est
attractif.
ϕ0 (l2 ) = 1.5 > 1, donc l2 est répul-
sif.
3. ϕ : [0, 1] −→ R
1
x 7−→ x(1 + x2 )
2
1 3 2
ϕ (x) = + x et ϕ00 (x) = 3x.
0
2 2

32
 Voici le tableau de variations de ϕ :

x 0 1

ϕ00 (x) +

2
ϕ0 (x)
0.5
1
ϕ(x)
0

D'après le tableau de variations de

ϕ, on remarque que : ϕ(0) = 0 et
ϕ(1) = 1, donc l1 = 0 et l2 = 1
sont deux points xes, et on a :
ϕ0 (l1 ) = 0.5 ∈] − 1, 1[, donc l1 est
attractif.
ϕ0 (l2 ) = 2 > 1, donc l2 est répulsif.

Exercice 13 (Évolution d'un capital)

On investit un capital C . Le placement a un taux de 5% par an et des frais de
gestion xes de 50 UM (unité monétaire) qui sont prélevés chaque année.
0

1. Décrire la suite récurrente qui décrit l'évolution du placement.

2. Donner les points xes du système et indiquer s'ils sont attractifs ou répul-
sifs.
3. Étudier l'évolution du capital au l des ans selon la valeur de C .0

Solution
1. Notons un le capital au début de la nième année, alors on a :

un = 0
un+1 = (1 + 5%)un − 50 = 1.05un − 50, ∀n ∈ N

2. Soit un+1 = ϕ(un ) avec ϕ(x) = 1.05x − 50.

On a
ϕ(α) = α ⇐⇒ 1.05α − 50 = α
α = 1000
Donc l'unique point xe du système est α = 1000.
De plus ϕ0 (x) = 1.05 > 1, il s'agit donc d'un point xe répulsif.
3.  Si C0 > 1000 alors un → +∞,
 Si C0 = 1000 alors un = 1000, pour tout n ∈ N,
 Si C0 < 1000 alors un → −∞.

33
1.2.6 Exercices supplémentaires

Exercice 14 Soit h(x) = 2 tan(x) − x, x ∈ [0, π2 [.

Calculer h (1) par la méthode du point xe, avec la précision  = 10 .
−1 −6

On se propose de calculer 13 en trouvant les racines réelles de l'ap-

r
Exercice 15 4

plication f de R dans R dénie par f (x) = x − 13 .

4

1. Situer les deux racines de f (c'est-à-dire indiquer deux intervalles qui

contiennent chacun une et une seule racine).
2. Soit g la fonction dénie sur [0, 1] par
x(9x4 + 5)
g(x) =
3(5x4 + 1)

(a) Faire l'étude complète de la fonction g et la comparer à l'identité.

(b) Soit la suite (x ) dénie par
n n∈N

xn+1 = g(xn ), x0 ∈]0, 1[

À l'aide des graphes de g et de l'identité sur [0, 1], dessiner la suite

(x ) sur l'axe des abscisses. Observer graphiquement la convergence.
(c) Justier mathématiquement la convergence observée graphiquement.
n n∈N

(d) Calculer l'ordre de convergence de la méthode.

34
1.3 Méthode de Newton

Isaac Newton (25 décembre 1642 J - 20

mars 1727 J, ou 4 janvier 1643 G - 31 mars
1727 G) est un physicien, mathématicien, phi-
losophe, alchimiste, astronome et théologien
anglais, puis britannique. Figure embléma-
tique des sciences, il est surtout reconnu pour
avoir fondé la mécanique classique, pour sa
théorie de la gravitation universelle et la créa-
tion, en concurrence avec Gottfried Wilhelm
Leibniz, du calcul innitésimal. Il est aussi
connu pour la généralisation du théorème du
binôme et l'invention dite de la méthode de
Newton permettant de trouver des approxi-
mations d'un zéro (ou racine) d'une fonction
d'une variable réelle à valeurs réelles.

1.3.1 Principe de la méthode

On suppose que la fonction est dérivable sur l'intervalle [a, b]. Le principe de la
méthode de Newton qu'on appelle aussi la méthode de la tangente, consiste à choisir
un point x0 de l'intervalle de dénition de f , et on considère la tangente à la courbe
représentative de f en (x0 , f (x0 )). Soit x1 l'abscisse de l'intervalle de la tangente avec
l'axe des abscisses. Puisque la tangente est proche de la courbe, on peut espérer que
x1 donne une meilleure estimation d'une solution de l'équation f (x) = 0 que x0 . On
recommence alors le procédé à partir de x1 et on construit par récurrence une suite
(xn ) dénie par :
f (xn )
xn+1 = xn −
f 0 (xn )
 L'équation de la tangente est donnée
par :
[y − f (x0 )]
= f 0 (x0 ).
(x − x0 )
 La racine de la tangente est donnée par :
x0 − f (x0 )
x1 =
f 0 (x0 )
.
1.3.2 Convergence de la méthode
Théorème 5 ( Théorème de Newton) (condition susante de convergence globale)
Soit f : [a, b] → R de classe C vériant :
2

1. f (a) × f (b) < 0

2. f (x) 6= 0, ∀x ∈ [a, b]
0

3. f (x) 6= 0, ∀x ∈ [a, b]
00

35
 4. Partant d'un point x qui satisfait l'inégalité
0

f (x0 ).f 00 (x0 ) > 0

(vérié par un certain choix de x ∈ [a, b])

Si les conditions énoncées, ci-dessus, sont satisfaites, alors le processus de Newton :
0

 x choisi

0
f (xn )
 xn+1 = g(xn ) = xn −
f 0 (xn )
Converge pour ce choix de x vers l'unique solution α de f (x).
De plus, nous avons l'estimation suivante :
0

M
|xn − α| ≤ |xn−1 − α|2 , ∀n > 0
2m
avec
M = max |f 0 (x)| , m = min |f 00 (x)|
x∈[a,b] x∈[a,b]

Cette inégalité peut s'écrire en fonction de x 0

 2n −1
M
|xn − α| ≤ |x0 − α|2n , ∀n ∈ N
2m

Théorème 6 (Condition de convergence locale)

Soit f une fonction de classe C de l'intervalle [a, b] dans R, avec a < b. Supposons
2

qu'il existe un α ∈ [a, b] tel que f (α) = 0 et f (α) 6= 0. Alors il existe δ > 0 tel que pour
0

tout x ∈ [α − δ, α + δ], la suite des itérés de Newton converge vers α quand n → +∞

(voir chap2).
0

1.3.3 Test d'arrêt

Les itérations s'achèvent dés que
|xn+1 − xn | <  (∗)

où  est une tolérance xée. En fait, si on note en = α − xn l'erreur à l'itération n, on a

en+1 = α − xn+1 = g(α) − g(xn ) = g 0 (ξn )en

avec ξn entre xn et α, et
xn+1 − xn = α − xn − α + xn+1 = en − en+1 = (1 − g 0 (ξn ))en

Or, si n est susamment grand, g 0 (ξn ) ≈ g 0 (α) = 0 et donc

en ∼
= xn+1 − xn

L'erreur qu'on commet lorsque l'on adopte le critère (∗) est donc plus petite que la
tolérance xée.
1.3.4 Ordre de convergence
Théorème 7 On suppose que f (α) 6= 0, alors si la suite (x ) des itérés de Newton
0

converge, sa vitesse de convergence est (au moins) quadratique.

n n∈N

36
Remarque 4 Dans ce qui précède, nous avons supposé que la fonction f dont nous
cherchons le zéro α vérie f (α) = 0 et f (α) 6= 0. Autrement dit, nous avons supposé
0

que α est une racine simple de f . Maintenant la question qui se pose est : que se passe-
t-il quand α est une racine de f de multiplicité m ≥ 2 ?
Si on garde la même fonction g que précédemment, la méthode de Newton perd son
caractère de convergence quadratique. En eet on peut écrire
f (x) = (x − α) h(x) avec h(α) 6= 0
m

Donc
(x − α)m h(x) (x − α)h(x)
g(x) = x − = x −
m(x − α)m−1 h(x) + (x − α)m h0 (x) mh(x) + (x − α)h0 (x)
et g(x) − g(α) 1
lim =1− 6= 0,
x−α m
ce qui implique en terme de suite que
x→+∞

|xn+1 − α| 1
→1− ∈]0, +∞[
|xn − α| m
Ceci se traduit par une convergence linéaire et pas du tout quadratique. Pour récupérer
cette dernière, on fait appel à la méthode de Newton modiée.
1.3.5 Méthode de Newton modiée
On suppose que α est une racine de multiplicité m ≥ 2, c'est-à-dire :
f (x) = (x − α)m h(x) avec h(α) 6= 0
On suppose que f ∈ C 2 ([a, b]) et par conséquent h l'est aussi, on dénit alors la fonction
g par :
f (x)
g(x) = x − m
f 0 (x)
Dans ce cas,
g(x) − g(α)
lim g(x) = = 0,
x→α x−α
ce qui implique
|xn+1 − α|
lim =0
x→+∞ |xn − α|
et
|xn+1 − α| h0 (α)
lim =
x→+∞ |x − α|2 mh(α)
n

Remarque 5 Les méthodes quadratiques sont plus intéressantes que les méthodes li-
néaires car leur vitesse de convergence est plus rapide. Des méthodes d'ordre plus élevé
seraient encore plus rapides mais plus lourdes à mettre en place et sont plus utilisées
dans la pratique.
Il n'est pas toujours possible de choisir avec certitude un x de départ dans la zone de
convergence. Il pourra alors y avoir, même si la suite converge, une phase de recherche
0

dans laquelle il n'y a pas réduction progressive de l'erreur, il pourra y avoir divergence.
La méthode de Newton nécessite le calcul des dérivées f (x), c'est un inconvénient dans
0

la pratique où l'on ne dispose pas toujours d'expression analytique pour la fonction f .

37
1.3.6 Exercices corrigés

Exercice 16 Soit la fonction f (x) = (x + 2) . 2

5

1. Déterminer de manière analytique, l'unique racine de f.

2. En appliquant la méthode de Newton, peut-on déterminer cette racine? Jus-
tier.

Solution
Soit la fonction f (x) = (x + 2) 5 .
2

1. f (x) = 0 ⇔ x = −2.
Donc l'unique racine de f est -2.
2. D'après le graphe de f on remarque qu'il
existe un unique α ∈ [−3, 0].
Vérions le par le théorème des valeurs in-
termédiaires.
*f (−3) × f (0) = −1 × 1.31 < 0,
*f est continue sur [−3, 0],
2 3
*f 0 (x) = (x + 2)− 5 < 0 sur [−3, 0].
5
Donc d'après le théorème des valeurs inter-
médiaires il existe un unique α ∈ [−3, 0].
 Procédure de Newton :
*f ∈ C 2 ([−3, 0]),
2 3
*f 0 (x) = (x + 2)− 5 < 0. Pour x 6= −2
5
On a f 0 (−2) n'est pas dénie donc elle diverge. Alors on ne peut pas appliquer
la méthode de Newton.

Exercice 17 Soit la fonction dénie par :

f (x) = exp(x) − 4 cos(x) = 0

1. Séparer graphiquement les racines de f (x) et déduire le nombre de racines.

2. Chercher à une précision  = 10 h π près,
−5
une racine de f (x) par la mé-
thode de Newton dans l'intervalle 4 , 2 . Justier le choix de x et tester
πi

− x | < 10 .
0
−5
|x n+1 n

38
Solution
Soit la fonction dénie par : f (x) = exp(x) − 4 cos(x) = 0.
1. Le graphe de f

hπ π i
2. On a α ∈ , .
4 2
 Procédure de Newton
h π π i
*f ∈ C ∞
, ,
4 2
π  π  hπ π i
*f ×f = −0.63 × 4.81 < 0 ⇒ α ∈ , ,
4 2 4 2
π π
*f 0 (x) = exp(x) − 4 sin(x) > 0 sur ] , [
4 2
π π
*f 00 (x) = exp(x) + 4 cos(x) > 0 sur ] , [
4 2
Donc on peut appliquer la méthode de Newton.

 Le choix de x0
π  π 
f ×f 00
= 4.81 × 4.81 > 0.
2 2
π
Donc on prend x0 = .
2
Alors le processus de Newton est :
 π
 x0 =

2
f (xn ) exp(xn ) − 4 cos(xn )
 xn+1 = g(xn ) = xn − 0
 = xn − ,
f (xn ) exp(xn ) + 4 sin(xn )

converge vers la solution α.

39
Exercice 18 On considère l'équation f (x) = x − A (1)
2

1. Montrer que la méthode de Newton appliquée à (1) conduit à l'algorithme :

, n = 0, 1, ...; x donné
 
1 A
x =
n+1 x + n 0
2 x n

2. Montrer que cette suite converge quadratiquement vers √A.

Solution
1. L'algorithme de la méthode de Newton s'écrit :
f (xn )
xn+1 = xn − , n = 0, 1....; x0 donné.
f 0 (xn )

Appliqué à l'équation (1), il devient :

x2 − A x2 + A
 
1 A
xn+1 = xn − n = n = xn +
2xn 2xn 2 xn

2. L'ordre de convergence d'une méthode est tel que :

ϕ0 (α) = ϕ00 (α) = .... = ϕ(k−1) (α) = 0 et ϕ(k) (α), où α est solution de l'équation
ϕ(α) = α.

√
 
1 A
Dans le cas présent, on a : ϕ(x) = x+ et α = A, d'où :
2 x
   
1 A 1 A
0
ϕ (x) = 1 − 2 et ϕ (α) =
0
1− =0
2 x 2 A
 
1 2Ax A 1
00
ϕ (x) = 4
= 3 et ϕ00 (α) = √
2 x x A
La méthode est donc d'ordre 2.

Exercice 19 Entre deux murs (verticaux) parallèles, on place deux échelles en les
croisant. La première fait 3 mètres de long, la seconde 2 mètres. On constate qu'elles
se croisent à une hauteur de 1 mètre.
En utilisant la méthode de Newton, calculer approximativement la largeur du couloir
avec une tolérance de 10 .
−3

40
 Solution

On pose :
AD=x
AB=y
CD=z

En utilisant le théorème de Pythagore (voir An-

nexe), on a :
Pour le triangle DAC : x2 + z 2 = 9 (1)
Pour le triangle ABD : x + y = 4
2 2
(2)
On en déduit par soustraction de (1) par (2) :
z2 − y2 = 5 (3)

En utilisant le théorème de Thalès (voir Annexe), avec les parallèles (AB), (EF) et
(CD), on a :
EF AF EF FD EF AF EF FD
= et = , soit = et =
AB AD CD AD y AD z AD
1 AF 1 FD
comme EF = 1 : = (4) et = (5)
y AD z AD
On en déduit par addition de (4) et (5) :
1 1 AF FD AF + F D
+ = + =
y z AD AD AD
On peut noter que AF + F D = AD
1 1 AD 1 1
Donc : + = ou encore + = 1
y z AD y z
1 1 1 z 1 z
On en déduit = 1 − soit = − ou y =
y z y z z z−1
z2
En remplaçant l'expression de y dans (3), on obtient : z 2 − =5
(z − 1)2
ou z 2 (z − 1)2 − z 2 = 5(z − 1)2
puis par simplications successives, on obtient : z 4 − 2z 3 − 5z 2 + 10z − 5 = 0
Tout d'abord, posons f (z) = z 4 − 2z 3 − 5z 2 + 10z − 5, représentée par le graphe
suivant

41
 D'après ce graphe, on remarque qu'il existe deux solutions α1 ∈ [−2.5, −2] et
α2 ∈ [2.5, 3]. On a
*f (−3) × f (−2) = 55 × −13 ≤ 0
*f est continue sur [2.5, 3]
*f 0 (z) = 4z 3 − 6z 2 − 10z + 10 > 0

D'après le théorème des valeurs intermédiaires il existe un unique α = α2 ∈ [2.5, 3]

tel que f (α) = 0.
Procédure de Newton
*f est de classe C 2 ([2.5, 3]),
*f 0 (z) = 4z 3 − 6z 2 − 10z + 10 > 0 sur [2.5, 3],
*f 00 (z) = 12z 2 − 12z − 10 > 0 sur [2.5, 3],
donc le procédé de Newton est le suivant :
donné

 z0
f (zn ) z 4 − 2z 3 − 5z 2 + 10z − 5
 zn+1 = g(zn ) = zn − = zn −
f 0 (zn ) 4z 3 − 6z 2 − 10z + 10

Le choix de z0
On a f (3) × f 00 (3) = 7 × 62 > 0. Donc on a le tableau suivant :

z0 3
z1 2.794117647
z2 2.739447775
z3 2.735739747
z4 2.735723253

À partir de ce tableau, on a

|z4 − z3 | = 1.64 × 10−5 < 10−3

alors
α ' 2.735723253
Donc pour z = 2.735723253 en remplaçant z dans (1) : x2 + z 2 = 9 on obtient

x = 1.231185722

Alors la largeur du couloir est 1.231 mètres.

Exercice 20 Soit f une application de R dans R dénie par

f (x) = exp(x2 ) − 4x2

On se propose de trouver les racines réelles de f .

1. Localiser les 4 racines de f .
2. Montrer qu'il y a une racine x̂ comprise entre 0 et 1.
3. Écrire la méthode de Newton pour la recherche des zéros de la fonction f .

42
 4. Soit la méthode de point xe

 xk+1 = ϕ(xk )
(1)
x0 ∈]0, 1[


avec ϕ l'application de R dans R dénie par

p
exp(x2 )
ϕ(x) =
2
Examiner la convergence de cette méthode et préciser l'ordre de convergence.
5. Entre la méthode de Newton et la méthode de point xe (1), quelle est la
plus ecace? Justier la réponse.

Solution
1. D'après le graphe de f , on remarque qu'il y a
quatre racines : α1 ∈ [−2, −1], α2 ∈ [−1, 0],
α3 ∈ [0, 1] et α4 ∈ [1, 2].
2. Montrons qu'il existe un unique x̂ ∈ [0, 1],
pour cela utilisons le théorème des valeurs
intermédiaires.
*f (0) × f (1) = 1 × −1.28 < 0,
*f continue sur [0, 1],
*f 0 (x) = 2x[exp(x) − 4] < 0.
Donc il existe un unique x̂ ∈ [0, 1].
3. Soit la méthode de Newton :
f (xk ) exp(x2k ) − 4x2k
xk+1 = xk − = x k −
f 0 (xk ) 2xk (exp(x2k ) − 4)

4. Étude de la convergence de la méthode (1)

p
exp(x2 )
Soit ϕ(x) =
r 2
exp(x2 )
r
e
On a : 0 < < <1
4 4
Donc ϕ :]0, 1[−→]0, 1[. De plus on a :
1 p
ϕ0 (x) = x exp(x2 ),
2
1p
00
ϕ (x) = exp(x2 )(1 + x),
2

43
 Voici le tableau de variations de ϕ :

x 0 1

ϕ00 (x) +

0.82
ϕ0 (x)
0
0.82
ϕ(x)
0.5

D'après le tableau de variations de ϕ, on remarque que :

∀x ∈ [0, 1], |ϕ0 (x)| = 0.82 < 1, alors elle est contractante.
∀x ∈ [0, 1], ϕ(x) ∈ [0, 1], alors elle est stable. Donc on conclut que ϕ est conver-
gente.
1 p
De plus on a : ϕ0 (x̂) = x̂ exp(x̂2 ) = x̂ϕ(x̂) = x̂2 6= 0 (car ϕ(x̂) = x̂).
2
Donc la méthode (1) converge seulement à l'ordre 1.
5. Puisque x̂ est une racine simple de f , la méthode de Newton converge à l'ordre
2 tandis que la méthode de point xe (1) converge à l'ordre 1, donc la méthode
de Newton est plus ecace.

Exercice 21 Soit la fonction f (x) = 1 − 3 exp(−x), x ∈ R

1. Montrer que l'équation f (x) = 0 a une unique racine α qu'on localisera dans
un intervalle I entre deux entiers consécutifs.
2. Appliquer à f (x) la méthode de Newton pour trouver α.
3. Sur quelle fonction dénit-on les itérations du point xe?
4. Calculer α avec la méthode de point xe.
5. Calculer α avec la méthode de dichotomie.
6. Calculer α avec la méthode de Newton.
Tous les calculs se font à la précision  = 10 . −3

44
Solution

1. D'après le graphe de f , on remarque qu'il

existe une racine dans [1, 2]. On a :
*f (1) × f (2) = −0.10 ∗ 0.59 < 0.
*f est continue sur [1, 2].
*f 0 (x) = 3 exp(−x) > 0.
Donc d'après le théorème des valeurs inter-
médiaires, il existe un unique α ∈ [1, 2].

2. Méthode de Newton
*f ∈ C 2 ([1, 2]),
*f 0 (x) = 3 exp(−x) sur [1, 2]
*f 00 (x) = −3 exp(−x) sur [1, 2]
donc le procédé de Newton est le suivant :
donné

 x0
f (xn ) 1
 xn+1 = g(xn ) = xn − 0
= (xn + 1) −
f (xn ) 3 exp(−xn )

Le choix de x0
On a f (1) × f 00 (1) = −0.10 × −1.10 > 0. Donc on prend x0 = 1.
3. Calcul de α par la méthode de point xe
Soit g(x) = x − 1 + 3 exp(−x)
α est un point xe de g c'est-à-dire g(α) = α ⇐⇒ f (α) = 0
α − 1 + 3 exp(−α) = α ⇐⇒ −1 + 3 exp(−α) = 0 ⇐⇒ 1 − 3 exp(−α) = 0 ⇐⇒
f (α) = 0
Étudions la convergence de la méthode :
g 0 (x) = 1 − 3 exp(−x)
g 00 (x) = 3 exp(−x)

x 1 ln(3) 2

g 00 (x) + 0 +

0.59
g 0 (x) 0
−0.1
1.10 1.40
g(x)
1.09

D'après le tableau de variations de g , on remarque que :

max |g 0 (x)| = k = 0.59 < 1, donc g est contractante.
x∈[1,2]

45
 x0 1
x1 1.103638324
x2 1.098624898
x3 1.098612289

∀x ∈ [1, 2], g(x) ∈ [1, 2], donc g est stable. Alors g converge vers α.

On a
|x3 − x2 | = 1.26 × 10−5 < 10−3
alors
α ' 1.09861228
4. Calcul de α par la méthode de Dichotomie
an + b n
n an bn f (an ) f (bn ) cn = f (cn )
2
0 1 2 ⊕ 1.5 ⊕
1 1 1.5 ⊕ 1.25 ⊕
2 1 1.25 ⊕ 1.125 ⊕
3 1 1.125 ⊕ 1.0625
4 1.0625 1.125 ⊕ 1.09375
5 1.09375 1.125 ⊕ 1.109375 ⊕
6 1.09375 1.109375 ⊕ 1.1015625 ⊕
7 1.09375 1.1015625 ⊕ 1.09765625
8 1.09765625 1.1015625 ⊕ 1.099609375 ⊕
9 1.09765625 1.099609375 ⊕ 1.098632813 ⊕
10 1.09765625 1.098632813 ⊕ 1.098144532

On a
|x10 − x9 | = 9.76 × 10−4 < 10−3
Donc
α ' 1.098144532
5. Calcul de α par la méthode de Newton
1
Soit ϕ(x) = x + 1 −
3 exp(−x)

x0 1
x1 1.093906057
x2 1.098601232
x3 1.098612289

On a
|x3 − x2 | = 1.10 × 10−5 < 10−3
alors
α ' 1.09861228

46
1.3.7 Exercices supplémentaires

Exercice 22 Le but de cet exercice est de calculer la racine cubique d'un nombre
positif a.
Soit g la fonction dénie sur R par
∗
+

(a > 0 xé)
2 a
g(x) = x + 2
3 3x
1. Faire l'étude complète de la fonction g.
2. Soit la suite (x ) dénie par :
n n∈N

xn+1 = g(xn )

Étudier la convergence de la méthode de point xe.

3. Calculer l'ordre de la méthode.
4. Expliciter la méthode de Newton pour la recherche du zéro de la fonction f
dénie par f (x) = x − a. Que remarque-t-on?
3

Exercice 23 On veut résoudre l'équation exp(−αx) = x avec 0 < α < 1.

1. Vérier que cette équation admet une unique solution notée l , dans R.
2. Écrire la méthode de Newton pour résoudre l'équation exp(−αx) = x avec
α

0 < α < 1.
3. Soit g : R → R la fonction dénie par exp(αx). On dénit la suite récur-
rente : 
 u ∈R 0
(1)
un+1 = g(un )


 On veut montrer que u converge vers l . Pour cela comparer d'abord le

graphe de g à l'identité et observer graphiquement la convergence.
n α

 Justier mathématiquement la convergence observée graphiquement.

4. Parmi la méthode de Newton et la méthode de point xe (1), la quelle faut-il
préférer vis-à-vis de la vitesse de convergence.

47
1.4 Méthode de la sécante
1.4.1 Principe de la méthode
C'est une méthode du type :
xn + 1 = F (xn , xn−1 , ..., xn−N )

La méthode de Newton est rapide mais nécessite le

calcul de la dérivée de f en tout point xn , ce qu'on
a pas toujours. La plus simple et la plus ancienne
est la méthode de la sécante. Elle consiste à se
donner deux points x0 et x1 , tracer la droite qui
passe par les points (x0 , f (x0 )) et (x1 , f (x1 )), elle
coupe l'axe des x en x2 et on recommence avec les
points x1 et x2 .
L'algorithme s'écrit :
xn − xn−1
xn+1 = xn − f (xn )
f (xn ) − f (xn−1 )

1.4.2 Convergence de la méthode

Théorème 8 Soit f une fonction de classe C dans un voisinage ]α − r, α + r[ d'une
2

racine α de f avec f (α) 6= 0. Alors il existe un δ < r tel que si x et x ∈]α − δ, α + δ[,
0

alors x converge vers α, et

0 1
n

|xn+1 − α| ≤ C(δ) |xn − α| |xn−1 − α|

avec λn
C(δ) |x − α| ≤ δ (C(δ))
n

où λ est la suite de Fibonacci dénie par :

n

λn+1 = λn + λn−1 , λ0 = λ1 = 1

Remarque
La méthode de la sécante ne converge aussi que si l'on part susamment près de la
racine,
|en+1 | ≤ c |en |λ , λ ≈ 1.6 nombre d'or
√
1+ 5
C'est une convergence superlinéaire qui a pour ordre de convergence .
2

1.4.3 Critère d'arrêt

L'algorithme de la sécante n'est évidemment pas complet tant qu'on n'a pas précisé
un critère d'arrêt. Généralement, xn converge vers la solution x∞ cherchée ce qui signie
que pour n grand, xn est voisin de x∞ . Sans plus d'informations il est dicile de savoir
ce que signie numériquement "n grand", et c'est là où il y a une diculté fréquente
en analyse numérique.
Un critère d'arrêt souvent utilisé consiste à choisir à priori une tolérance  et à terminer
l'algorithme lorsque
|xn+1 − xn | ≤  (1)

48
Ce n'est pas complètement satisfaisant ; pour s'en convaincre, on peut penser à la suite :
1 1
xn = 1 + + ... +
2 n
qui vérie lim |xn+1 − xn | = 0.
n→+∞
Puisqu'on veut résoudre f (x) = 0, un autre critère d'arrêt possible consiste à s'ar-
rêter lorsque
|f (xn )| <  (2)
Un autre critère d'arrêt possible consiste à s'arrêter lorsqu'un numéricien rigoureux
décide de s'arrêter que lorsque les deux critères (1) et (2) sont simultanément vériés.
Dans le cas de la méthode de la sécante, on peut utiliser

|f (xn ) − f (xn−1 )| < 

Ce critère d'arrêt a l'avantage d'éviter une possible division par 0.

Pour éviter à l'ordinateur de tourner sans s'arrêter lorsqu'il n'y a pas convergence,
il est évidemment indispensable de toujours mettre un critère limitant le nombre total
d'itérations.
1.4.4 Exercices corrigés

Exercice 24 Soit f (x) = x − 0.2 sin(x) − 0.5

1. Montrer que l'équation f (x) = 0 admet une unique racine dans I .
2. Calculer cette racine en utilisant la méthode de la sécante avec une tolérance
de 10 .
−3

Solution

1. D'après le graphe de f , on remarque qu'il

existe une unique racine dans l'intervalle
[0.5, 1].
Utilisant le théorème des valeurs intermé-
diaires pour le montrer. On a
*f (0.5) × f (1) = −0.09 × 0.33 < 0,
*f continue sur [0.5, 1],
*f 0 (x) = 1 − 0.2 cos(x) > 0 sur [0.5, 1]
Alors il existe un unique α ∈ [0.5, 1] tel que
f (α) = 0.

2. L'algorithme de la sécante est :


 x−1 = 0.5, x0 = 1
xn − xn−1
 xn+1 = xn = f (xn )
f (xn ) − f (xn−1 )

49
 On a le tableau suivant :
x0 1
x1 0.61212248
x2 0.61549349
x3 0.61546816

On a
|x3 − x2 | = 2.533 × 10−5 < 10−3
alors
α ' 0.61546816

Exercice 25 Estimer √10, en utilisant la méthode de la sécante avec une tolérance

de 10 .−4

Solution
Soit f (x) = x2 − 10.

D'après le graphe de f on remarque qu'il existe

une racine dans l'intervalle [3, 4]
Vérions le, en utilisant le théorème des valeurs
intermédiaires.
f (3) × f (4) = −1 × 6 < 0,
*f continue sur [3, 4],
*f 0 (x) = 2x > 0 sur [3, 4]
Alors il existe un unique α ∈ [3, 4] tel que
f (α) = 0.

L'algorithme de la sécante est :


 x−1 = 3, x0 = 4
xn − xn−1
 xn+1 = xn = f (xn )
f (xn ) − f (xn−1 )
On a le tableau suivant :
x0 4
x1 3.142857143
x2 3.16
x3 3.16201117318
x4 3.16224648985
x5 3.16227401437

On a
|x5 − x4 | = 2.75 × 10−5 < 10−4
alors
α ' 3.16227401437

50
 La méthode Avantages Inconvénients

Dichotomie - La convergence est assurée ; - Vitesse de convergence linéaire donc lente ;

- On a un encadrement de la solution ; - Sensible aux erreurs d'arrondi ;
x2
- Un seul calcul de la fonction à chaque itération. Comme par exemple, la fonction f (x) = ex − 1 − x −
2
qui s'annule théoriquement en x = 0 seulement. Par
contre numériquement, elle change de signe un grand
nombre de fois autour de x = 0.

Point xe - Son analyse mathématique est relativement aisée et - Convergence souvent dicile à réaliser en pratique ;
permet d'en déduire celle de la méthode de Newton ;
- Joue un rôle considérable pour adapter des algorithmes - Convergence lente de type linéaire ;
linéaires à des situations non linéaires.

51
- Certains points xes dits instables, ne peuvent être
atteints.

Méthode de - Convergence rapide ; - Peut diverger ou converger vers un autre zéro que celui
Newton cherché si la donnée initiale est mal choisie ;
- Relativement stable et peu sensible aux erreurs d'ar- - Nécessite le calcul de la dérivée de la fonction, ce qui
rondis si f 0 (x∞ ) n'est pas trop petit. est numériquement dicile si on le connais pas explici-
tement ;
- Chaque étape nécessite deux évaluations de la fonction.

Méthode de la - Nécessite une seule évaluation de la fonction à chaque - Peut diverger si les données initiales sont mal choisis ;
sécante étape ;
- Convergence relativement rapide mais moins que celle - Le calcul de f (xn ) − f (xn−1 ) peut produire des erreurs
de Newton. de chute.
Chapitre 2
Résolution des systèmes linéaires

La résolution des systèmes linéaires est considérée comme l'un des deux problèmes
fondamentaux de l'analyse numérique matricielle et cette résolution intervient à divers
domaines, en particulier lorsqu'il s'agit de modéliser puis résoudre numériquement des
problèmes comme par exemple en :
 Électricité : recherche des intensités du courant dans un circuit électronique
en utilisant les lois des noeuds et des mailles ;
 Chimie : l'équilibre des équations des réactions chimiques ;
 Algèbre linéaire : recherche des vecteurs propres d'une matrice carrée asso-
ciés à une valeur propre donnée, déterminer le noyau d'un endomorphisme en
dimension nie (système homogène) ;
 Géométrie analytique : étudier la position relative des droites et des plans
dans l'espace ;
 Optimisation : minimisation ou maximisation d'une fonction quadratique ;
 Analyse numérique : interpolation polynomiale (matrice de Vandermonde),
résolution numérique des équations aux dérivées partielles (méthodes des dié-
rences nies où les matrices rencontrées sont tridiagonales).

Position du problème. Le problème consiste à trouver la solution du système

d'équations 

 a11 x1 + a12 x2 + · · · + a1n xn = b1
 a21 x1 + a22 x2 + · · · + a2n xn = b2

..


 .
 a x + a x + ··· + a x = b
n1 1 n2 2 nn n n

On cherche à résoudre le système Ax = b avec A est une matrice à coecients réels de

taille n × n, b un vecteur de Rn et x l'inconnu à chercher de Rn .
Remarque 6 Si b = 0 le système est dit homogène, donc il admet au moins une
solution x = 0 qui est la solution nulle ou triviale.
Remarque 7 Si det(A) 6= 0, alors le système admet une unique solution. Donc pour
résoudre un système d'équations linéaires on cherche à remplacer le système initial par
un autre plus simple, ayant la même solution. Pour cela, il existe deux grandes familles
de méthode de résolution : les méthodes directes et les méthodes itératives.

52
2.1 Méthodes directes
Les méthodes directes de résolution des systèmes linéaires sont des méthodes dans
lesquelles la solution est obtenue de façon exacte en un nombre ni d'opérations soit
par triangularisation soit par décomposition de la matrice A.
Remarque 8 On n'utilise jamais les formules de Cramer car elles nécessitent le calcul
du déterminant qui requièrent un nombre trop important d'opérations élémentaires.
Remarque 9 On ne calcule pas A pour ensuite faire x = A b avec x = (u · · · u ) .
−1 −1 T

En eet, le calcul de A = (u , u , · · · , u ), décrit par ces vecteurs colonnes, revient

1 n
−1
1 2 n

 . 
 
0
 . 
déjà à résoudre n systèmes linéaires : Ax =  1.  = e , ce qui est bien-sûre trop
i i
 . 

coûteux pour résoudre un seul système.

0

2.1.1 Méthode de Gauss

Johann Carl Friedrich Gauss

(30 avril 1777-23 février 1855) est un ma-
thématicien, astronome et physicien al-
lemand. Doté d'un grand génie, il a ap-
porté de très importantes contributions à
ces trois sciences, surnommé "Le prince
des mathématiciens ", il est considéré
comme l'un des plus grand mathémati-
ciens de tous les temps.

Principe de la méthode
La méthode consiste à construire une matrice inversible M telle que M A soit une
matrice triangulaire supérieure. Le système initial Ax = b est alors équivalent par
multiplicité à gauche par M au système triangulaire M Ax = M b. Donc la méthode de
Gauss se décompose en trois étapes :
1ière étape : Trouver une matrice inversible M telle que la matrice M A soit trian-
gulaire supérieure.
2ième étape : Calcul simultané du vecteur M b.
3ième étape : Résolution du système triangulaire supérieure M Ax = M b (remon-
tée).
Commençons par décrire étape par étape la méthode dans sa forme de base, en
considérant le système linéaire Ax = b, A étant une matrice inversible d'ordre n.
Supposons de plus que le terme a11 de la matrice A est non nul. Nous pouvons alors
éliminer l'inconnu x2 des lignes 2 à n du système en leur retranchant respectivement
a
la première ligne multiplier par le coecient i1 , i = 2, n.
a11

53
 En notant A(2) et b(2) la matrice et le vecteur du second membre résultant de ces
opérations, on a alors
ai1 ai1
a1j et bi = bi − b1 , i, j = 2, n
(2) (2)
aij = aij −
a11 a11

et le système A(2) x = b(2) est équivalent au système de départ. En supposant que le

coecient diagonal a(2)
22 6= 0 de A , on peut procéder à l'élimination de l'inconnu x3
(2)

des lignes 3 à n de ce système, et ainsi de suite.

On obtient sous l'hypothèse a(2)
kk 6= 0, k = 1, n − 1, une suite nie de matrices A ,
(k)

k ≥ 2 de la forme :
 (k) (k) (k) (k) 
a11 a12 · · · a1k · · · a1n
 
 (k) (k) (k)

 0
 a22 ··· a2k ··· a2n 

 
 .. .. .. .. .. ..
 
 . . . . . .


 
A(k) =



(k) (k)
 0
 0 · · · akk · · · akn 

 
 . .. .. .. .. ..
 
 .. . . . . .


 
 
(k)
0 0 ··· 0 · · · ann
et telles que le système A(k) x = b(k) est triangulaire supérieure. Les quantités a(k)
kk ,
k = 1, n − 1 sont appelées pivots et l'on a supposé qu'elles étaient non nulles à chaque
étape, les formules permettant de passer du k ième système linéaire au (k + 1)ième se
résumant à :
(k) (k)
aik aik
(k+1)
aij =
(k)
aij − a
(k)
(k) kj
et (k+1)
bi =
(k)
bi − b
(k) k
(k)
, i, j = 2, n
akk akk
En pratique, pour une résolution "à la main" d'un système linéaire Ax = b par cette
méthode, il est commode d'appliquer l'élimination à la matrice "augmentée" (A b).
On remarque qu'il faut s'assurer que a(k)
kk n'est pas nul ni même trop petit avant
chaque opérations. Pour cela, on adopte une stratégie du pivot.
1. Stratégie du pivot partiel : on détermine l'élément a(k) ik tel que k ≤ i ≤ n et

(k) (k)
aik = max apk
k≤p≤n

on permute alors les lignes d'indices i et k pour amener en position de pivot

l'élément a(k)
ik .

2. Stratégie du pivot total : on détermine l'élément aij(k) tel que k ≤ i, j ≤ n et

(k) (k)
aij = max alp
k≤l,p≤n

on eectue alors des permutations de lignes et de colonnes pour ramener en

position de pivot l'élément a(k)
ij .

54
Erreur d'arrondi et choix du pivot
Revenons à présent sur le choix du pivot à chaque étape de l'élimination. Si à la k ième
étape l'élément a(k)
kk est non nul, il semble naturel de l'utiliser comme pivot. Cependant,
à cause des erreurs d'arrondi existant en pratique, cette manière de procéder est en
générale à proscrire, comme l'illustre l'exemple suivant :
Exemple numérique : Supposons que les calculs sont eectués en virgule ottante
dans le système décimal, considérons le système
10−4 1
    
x1 1
=
1 1 x2 2

dont la solution est x1 = 1.0001 et x2 = 0.9999. En prenant a11 = 10−4 , on obtient le

système triangulaire suivant
10−4
    
1 x1 1
=
0 9999 x2 9998

mais la version machine prend la version arrondie

10−4 1
    
x1 1
=
0 104 x2 104

ainsi la solution numérique calculée est

x1 = 0 et x2 = 1

qui est très éloignée de la véritable solution du système.

Si par contre, on commence par échanger les deux équations du système pour utiliser
le nombre 1 comme pivot, on trouve
    
1 1 x1 2
=
0 0.9999 x2 0.9998

d'où la solution numérique calculée est

x2 = 1 et x1 = 2 − x2 = 1

ce qui est correct à 10−4 près.

En général, le changement de pivot n'a pas un eet aussi spectaculaire que dans
l'exemple ci-dessus, mais il en demeure pas au moins essentiel lorsque les calculs sont
eectués en arithmétique à virgule ottante. De fait pour éviter la propagation d'er-
reurs et obtenir une meilleure stabilité numérique de la méthode, on peut utiliser pour
le choix du pivot :pivot partiel pivot total
et .

Calcul du nombre d'opérations

n3 − n
La mise en oeuvre de la méthode du pivot nécessite additions-soustractions,
3
n(n − 1)
autant de multiplications et divisions, soit un total d'opérations de l'ordre de
2
2n3
.
3

55
Quantication de l'erreur
Les solutions obtenues numériquement ne sont que des valeurs approchées de la
solution exacte. En général, si x est la solution exacte du système Ax = b et x̃ est la
solution approchée calculée, nous avons donc les relations suivantes : Ax − b = 0 et
Ax̃ − b = r où r est appelé le résidu
.
Soit z l'erreur commise sur la solution x = x̃ + z . On montre facilement que z vérie
la relation Az + r = 0. Ainsi, on peut calculer l'erreur z à partir du résidu r.
Remarque 10 Malgré les avantages de la méthode de Gauss, elle n'est vraiment utili-
sée en analyse numérique que pour résoudre des problèmes où la matrice A n'a aucune
propriété particulière. Sinon, des algorithmes performants lui seront préférés (factori-
sation LU et Cholesky).
2.1.2 Méthode LU
Principe de la méthode
Le principe de la méthode est de se ramener à résoudre deux systèmes triangulaires.
Soit le système Ax = b, où A est une matrice dont tous les mineurs principaux sont
non nuls, alors pour la résolution on procède par les étapes suivantes :
1. Décomposition de A : A = LU avec L matrice triangulaire inférieure à dia-
gonale unité (c'est-à-dire : lii = 1) et U triangulaire supérieure.
2. Résolution du système triangulaire inférieure : Ly = b (déscente).
3. Résolution du système triangulaire supérieure : U x = y (remontée).

A=LU Ly = b
Ax = b −→ LU x = b −→
Ux = y
Notons
akik
lik =
akkk
Cette méthode est intéressante lorsqu'on doit résoudre beaucoup de systèmes du
types :
Axj = bj
car L et U sont calculées une fois pour toute et nous n'avons plus qu'à les utiliser pour
chacun des cas.

L'existence et l'unicité de la décomposition

Théorème 9 Soit A ∈ M (R) une matrice dont tous les mineurs principaux sont
non nuls. Il existe un unique couple de matrices (L, U ), avec L triangulaire inférieure
n

à diagonale unité et U triangulaire supérieure tel que A = LU .

Proposition 2 Si A est une matrice à diagonale strictement dominante alors elle
admet une factorisation LU .
Remarque 11 La décomposition LU permet de calculer facilement le déterminant de
A, qui est égal au produit des éléments diagonaux de la matrice U .
En eet :
n
Y
det(A) = det(LU ) = det(L) × det(U ) = 1 × det(U ) = uii
i=1

56
Théorème 10 Soit A une matrice d'ordre n inversible. Alors il existe une matrice P
(resp. des matrices P et Q) tenant compte d'une stratégie de pivot partiel (resp. total),
une matrice triangulaire inférieure L, dont les éléments sont inférieures ou égaux à 1
en valeur absolue, et une matrice triangulaire supérieure U telle que :
P A = LU (resp. P AQ = LU )

Démonstraion. voir [5]

Exemple 1 Considérons la matrice inversible
 
1 2 3
 
(1)
 
A=A  2 4 5
= 

 
7 8 9

On a alors 
1 2 3

 
(2)
 
A  0 0 −1
= 

 
0 −6 −12
et l'élimination s'interrompe à l'issue de la seconde étape, le pivot a (2)
. En échan-
=0
geant la deuxième et la troisième ligne, on arrive à 22

 
1 2 3
 
(2)
 
A =
 0 −6 −12 =U

 
0 0 −1

Les matrices d'élimination aux deux étapes eectuées sont respectivement

   
1 0 0 1 0 0

et E
   
(1)
  (2)
 
E  −2 1 0
=  0 1 0
=
 
 
   
−7 0 1 0 0 1

et la matrice P est la matrice de permutation

 
1 0 0
 
 
 0 0 1
P = 

 
0 1 0

d'où 
1 0 0

 
 
 2 1 0
L= 

 
7 0 1

57
Dans le cas d'une factorisation de type P A = LU , la résolution du système linéaire
Ax = b après factorisation s'eectue en appliquant tout d'abord la matrice de per-
mutation P au vecteur b pour obtenir le second membre P b et en résolvant ensuite
le système Ly = P b par une méthode de descente, puis le système U x = y par une
méthode de remontée.

Complexité de l'algorithme
n3 − n
Une décomposition LU pour la résolution d'un système linéaire nécessite :
3
2n3 − 3n2 + n
multiplications, additions, à l'étape de décomposition en un produit LU .
6
n3
Soit donc un total de l'ordre de , de plus la remontée et la descente nécessitent un
3
ordre de n2 . On note que pour n grand on néglige les puissances de n inférieures à 3, ce
qui permet de dire que le travail essentiel se trouve dans la décomposition elle-même.
2.1.3 Méthode de Cholesky

André-Louis Cholesky (15 octobre

1875-31 août 1918) était un mathémati-
cien et un militaire français. Il a eectué
sa carrière dans les services géographiques
de l'armée. C'est pour résoudre des pro-
blèmes de moindres carrés posés par la
géodésie que Cholesky inventa la décom-
position qui porte aujourd'hui son nom.

Principe de la méthode
La décomposition de Cholesky n'est qu'une variante de la décomposition LU pour
des matrices particulières. Dans toute cette section A ∈ Mn (R) est une matrice carrée
réelle symétrique dénie positive. Pour la résolution du système Ax = b, on procède
par les étapes suivantes :
1. Décomposition de A : A = LLT avec L matrice triangulaire inférieure à
éléments diagonaux positifs.
2. Résolution du système triangulaire inférieure : Ly = b (déscente).
3. Résolution du système triangulaire supérieure : LT x = y (remontée).

A=LLT T Ly = b
Ax = b −→ LL x = b −→
LT x = y
On détermine {lij } à l'aide du système d'équations
i
X
aij = lik ljk , 1≤i≤j≤n
k=1

58
où
···
 
l11 0 0
 .. . . . . . . ..
 . . 
L= .

.. 0

 ln−1,1 
ln1 · · · · · · lnn
Donc la résolution peut se faire de proche en proche, colonne par colonne, comme suit :
 v
 u i−1
lorsque i = j
 u X
taii − 2
lii = lik






 k=1

 i−1
X

a − lik ljk

ij




k=1
lorsque i > j

 lji =

lii

L'existence et l'unicité de la décomposition

Théorème 11 Soit A ∈ M (R) une matrice symétrique dénie positive. Alors il existe
(au moins) une matrice réelle triangulaire inférieure L telle que A = LL . De plus, on
n
T

peut imposer que les éléments diagonaux de la matrice L soient strictement positifs et
la décomposition A = LL correspondante est alors unique.
T

Évaluation du nombre d'opérations

n3 n3 n2
La méthode de Cholesky ne requiert que : multiplications, additions, divi-
6 6 2
sions. La méthode de Cholesky est donc fortement conseillée (plutôt que Gauss) quand
la matrice est symétrique dénie positive. Elle a aussi l'avantage de se révéler plus stable
√
par rapport aux erreurs d'arrondi. Notons également l'estimation a priori |lik | < aii ,
∀i = 1, · · · , n, ∀k = 1, · · · , i, provenant de la relation
i
X
2
lik = aii
k=1

et qui assure que les lik ne deviendront jamais trop grand.

2.1.4 Conclusion
Dans ce chapitre on a vu les quatre méthodes directes de résolution des systèmes
linéaires qu'on a étudié théoriquement. Voici un tableau récapitulatif résumant notre
travail et dans lequel on compare le coût des quatre méthodes en citant quelques
avantages et inconvénients.

59
 La méthode Le coût Avantages Inconvénients
 
2n3
L'élimination O - Résolution d'un seul système linéaire (comparaison - On échange la structure de A ;
3
de Gauss avec les autres méthodes) ;
- Utilisation des opérations élémentaires d'additions et - Blocage dans le cas d'un pivot nul sans pivotement ;
de multiplications.
- L'implémentation sur machine donne généralement de
mauvais résultats à cause des erreurs d'arrondi qui s'ac-
cumulent.

 
n3
Factorisation O - Cette méthode est très utile lors de la résolution d'une - La résolution d'un seul système linéaire nécessite deux
3
LU suite de systèmes de même matrice A où seul le vecteur systèmes linéaires triangulaires de matrices L et U (sto-
b change ; ckage de deux matrices L et U ) ;

60
- Utilisation des opérations élémentaires d'additions et -Particularité de la matrice carrée A (mineurs princi-
multiplications. paux non nuls).

 
4n3
Cholesky O - Cette méthode est très utile lors de la résolution d'une - Elle ne permet pas la résolution linéaire d'un système
3
suite de systèmes de même matrice A où seul le vecteur quelconque (particularité de la matrice A carrée symé-
b change ; trique dénie positive) ;
- Elle nécessite le calcul d'une seule matrice L ; - La résolution d'un seul système linéaire nécessite la ré-
solution de deux systèmes linéaires triangulaires de ma-
trices L et LT ;
- Elle demande une place mémoire deux fois inférieure
à celle de la factorisation LU car on ne doit stocker que
L.
 D'après le tableau on constate que la méthode de Cholesky est la moins coûteuse
parmi les autres.

2.1.5 Exercices corrigés

Exercice 26 Soit le système d'équations suivant


 3x − y + 2z = r
−x + 2y − 3z = s
x + 2y + z = t


avec, r, s, t ∈ R.
1. Ecrire ce système sous la forme matricielle AX = b.
2. Résoudre le système par la méthode de Gauss.

Solution
1. Soit le système linéaire suivant :
    
3 −1 2 x r
 −1 2 −3   y  =  s 
1 2 1 z t
| {z } | {z } | {z }
A X b

Commençons d'abord par rendre la matrice (A|b) triangulaire supérieure

 
3 −1 2 | r → L1
(A|b) =  −1 2 −3 | s  → L2
1 2 1 | t → L3
 
3 −1 2 | r → L1



|
 5 7 r  (−1)
−→  −0 − | s+  → L2 = L2 − L1

3 3 3  3
|
 
 
 7 1 r  1
0 | t− → L3 = L3 − L1
3 3 3 3
 
3 −1 2 | r → L1

 | 

 5 7 r 
 0
−→  − | s +  → L2
3 3 3 
|
 
7
 
 54 15t − 12r − 21s  → L3 = L3 − L2
0 0 | 5
15 15

61
 On obtient le système d'équations suivant


 3x − y + 2z = r




 5
 7 9
y− z = s+
 3 3 3


15t − 12r − 21s


 54

 z =
15 15
En résolvant ce système on obtient la solution suivante :
1
 
  (8r + 5s − t)

 x 18 

   
   1 
 y  =  18 (−2r + s + 7t)
x=   

   
 
z  1 
(−4r + −7s + 5t)
18

Exercice 27 Soit le système linéaire Ax = b

    
6 1 1 x1 12
 2 4 0   x2  =  0 
1 2 6 x3 6

1. Résoudre le système linéaire par la méthode d'élimination de Gauss.

2. Factoriser la matrice A et résoudre le système linéaire.

Solution

1. Commençons d'abord par rendre la matrice (A|b) triangulaire supérieure

 
6 1 1 | 12 → L1
(A|b) =  −2 4 −0 | 0  → L2
1 2 6 | 6 → L3
 
6 1| 12
1 → L1

 | 

 11 1  −1
−→ 
 0 − | −4  → L2 = L2 − L1
3 3  3
|
 
 
 11 35  1
0 | 4 → L3 = L3 − L1
6 6 6

62
 | 12 → L1
 
6 1 1
 | 
11 1
 
−→  0

− | −4 
 → L2
 3 3 
 | 
1
0 0 6 | 6 → L3 = L3 − L2
2

On obtient le système d'équations suivant



 6x1 + x2 + x3 = 12



11 1

x2 − x3 = −4


 3 3



6x3 = 6

En résolvant ce système on obtient la solution suivante :

   
x1 2
   
   
x =  x2  =  −1 
  

   
x3 1

2. On pose A = LU , avec
 

6 1 1
 1 0 0
 
   
 1
11 1 
  
U = 0 −  et L =  3 1 0 
 

 3 3  



 
 1 1 
0 0 6 1
6 2
on a alors 
y = Ux
LU x = b ⇐⇒
Ly = b


 y1 = 12


 
 y1 = 12

 1

Ly = b ⇐⇒ y 1 + y 2 = 0 =⇒ y2 = −4
3
y3 = 6

 



 1 1
 y1 + y2 + y3 = 6

6 2


 6x1 + x2 + x3 = 12
 
 x1 = 2


11 1

U x = y ⇐⇒ x2 − x3 = −4 =⇒ x2 = −1


 3 3 
x3 = 1



6x3 = 6

63
 Alors la solution de ce système est
 
2
 
 
x=
 −1 

 
1

Exercice 28 Résoudre lorsqu'il est possible les deux systèmes Ax = b et Bx = b,

par la factorisation LU avec :
    
1 2 3 1 2 3 1
A =  2 4 5 ,B =  7 8 9  et b= 0 
7 8 9 2 4 5 1

Solution
1. Soit la matrice  
1 2 3
A= 2 4 5 
7 8 9
Vérions si on peut faire la factorisation LU de A.
     
4 5 2 3 2 3
∆3 = det(A) = det − 2 det + 7 det
8 9 8 9 4 5
= −2 6= 0
Par suite A est inversible.
∆1 = det(A1 ) = 1 6= 0
 
1 2
∆2 = det(A2 ) = det =0
2 4
Donc on ne peut pas factoriser A sans utiliser la technique du pivot. En eet,
  → L1
1 2 3
  −2
→ L2 = L2 − L1
 
 2 4 5
A= 1


 
7 8 9 7
→ L3 = L3 − L1
1
 
1 2 3
−→  0 0 −1 
0 −6 −12

Soit la matrice  
1 2 3
B= 7 8 9 
2 4 5

64
 Vérions si on peut faire la factorisation LU de B .
     
8 9 2 3 2 3
∆3 = det(B) = det − 7 det + 2 det
4 5 4 5 8 9

= 6 6= 0
Donc B est inversible.
∆1 = det(B1 ) = 1 6= 0
 
1 2
∆2 = det(B2 ) = det = −6 6= 0
7 8
Donc on peut factoriser B . La factorisation LU de la matrice B est donc
 
1 2 3 → L1
B= 7 8 9  → L2
2 4 5 → L3
 
1 2 3 → L1
−→  0 −6 −12  → L2 = L2 − 7L1
0 0 −1 → L3 = L3 − 2L2

   
1 0 0 1 2 3
L =  7 1 0  , U =  0 −6 −12 
2 0 1 0 0 −1

2. Résoudre le système Bx = b.

y = Ux
LU x = b ⇐⇒
Ly = b


 y1 = 1 
 y1 = 1



Ly = b ⇐⇒ 7y1 + y2 = 0 =⇒ y2 = −7
y3 = −1

 


2y1 + y3 = 1


x1 + 2x2 + 3x3 = 1

 1
 x1 = − 3

 


 
U x = y ⇐⇒ −6x2 − 12x3 = −7 =⇒ 5
x2 = −
 x =1 6

 


 
−x3 = −1 3


Alors la solution de ce système est

 
1
 −3 
 
 
x =  −5 
 
 6 
 
 
1

65
 Exercice 29 On considère le système Ax = b, où
  
3 2 1 4
A=  1 2 3 ,b =
  8 
2 1 1 4

1. Résoudre le système par la méthode de LU .

2. Résoudre le système A x = b sans calculer A .
2 2

Solution
1. Calculons d'abord les matrices L et U , pour cela on va faire la triangularisation
de la matrice A.
 
3 2 1 → L1
A= 1 2 3  → L2
2 1 1 → L3
 
3 2 1 → L1
 
 
 4 8  1
−→  0 3
  → L2 = L2 − L1
 3 
 3
 
 1 1  2
0 − → L3 = L3 − L1
3 3 3

→ L1
 
3 2 1
 
4 8 
 
−→  0

 → L2 = L2
 3 3 
1
 
0 0 1 → L3 = L3 + L2
4

La factorisation LU de la matrice A est donc

   
1 0 0 1 2 3
L =  7 1 0  , U =  0 −6 −12 
2 0 1 0 0 −1

Résoudre le système Ax = b.

y = Ux
LU x = b ⇐⇒
Ly = b


 y1 = 4

 
 y1 = 4


 1
 
y + y = 8 20
Ly = b ⇐⇒ 3
1 2 =⇒ y2 =
  3
y3 = 3

 


 2 1
 y1 − y2 + y3 = 4

3 4

66
 

 3x1 + 2x2 + x3 = 4
 
 x1 = 1


4 8 20

U x = y ⇐⇒ x2 + x3 = =⇒ x2 = −1


 3 3 3 
x3 = 3



x3 = 3
Alors la solution de ce système est
 
1
 
 
x=
 −1 

 
3

2. 
2 z = Ax
A x = b ⇐⇒ AAx = b ⇐⇒
Az = b
Alors  
1
 
 
z = x =  −1 


 
3
car le système Ax = b admet une unique solution.
Il sut donc de résoudre le système Ax = z avec le même L et U .

y = Lz
Ux = y


 y1 = 1

 
 y1 = 1


 1
 
y1 + y2 = −1 4
Ly = z ⇐⇒ 3 =⇒ y2 = −
  3
y3 = 2

 


 2 1
 y1 − y2 + y3 = 3

3 4


 3x1 + 2x2 + x3 = 1
 
 x1 = 3


4 8 4

U x = y ⇐⇒ x2 + x3 = − =⇒ x2 = −5


 3 3 3 
x3 = 2



x3 = 2
Alors la solution de ce système est
 
3
 
 
 −5 
x= 
 
2

67
 Exercice 30 Soit α un paramètre réel et soient les matrices A , P et le vecteur b
dénis par
α

 

2 4 1
 
1 0 0
 0
Aα =  α −2 −1  , P =  0 0 1  et  3 
b= − 
2
2 3 2 0 1 0 −1

1. À quelle condition sur α, la matrice A est inversible?

2. À quelle condition sur α, la matrice A admet-elle une décomposition LU
α

(sans pivot)?
α

3. Soit α = −1. Calculer, si elle existe, la décomposition LU de la matrice

M = PA .
4. Soit α = −1. Résoudre le système linéaire Ax = b en résolvant le système
α

linéaire M x = P b.
Solution
1. La matrice Aα est inversible si et seulement si det(Aα ) 6= 0.
     
−2 −1 4 1 4 1
det(Aα ) = 2 det − α det + 2 det
3 2 3 2 −2 −1
= −6 − 5α
6
Donc la matrice Aα est inversible si et seulement si α 6= − .
5
2. La matrice Aα admet une décomposition LU si et seulement si les mineurs
principaux de Aα sont non nuls.
A1 = 2 6= 0
 
2 4
A2 = det
α −2
= −4(1 + α)
Par conséquent, la matrice Aα admet une décomposition LU (sans pivot) si et
seulement si α 6= −1.
3. Si α = −1, la matrice Aα n'admet pas de décomposition LU sans pivot. La
matrice P échange les lignes 2 et 3 de la matrice A et on obtient la matrice
    
1 0 0 2 4 1 2 4 1
M = P A−1 =  0 0 1   −1 −2 −1  =  2 3 2 
0 1 0 2 3 2 −1 −2 −1
La matrice M admet une décomposition LU (sans pivot) et l'on a
par conséquent, on obtient la décomposition LU suivante de la matrice M
 
1 0 0  
 1 1 0  2 4 1
L=  , U =  0 −1 −1 
   
1
1 0 0 −
 
− 0 1 2
2
68
  
2 4 1 → L1
M = 2 3 2  → L2
−1 −2 −1 → L3


2 4 1
 → L1
 
  2
−→  0 −1 1 → L2 = L2 − L1
 


 2
1
 
0 0 − (−1)
2 → L3 = L3 − L1
2

4. Pour résoudre le système linéaire M x = P b, il sut de résoudre les deux sys-

tèmes triangulaires suivants :


 y1 = 0 
 y1 = 0



 
Ly = b ⇐⇒ y1 + y 2 = −1 =⇒ y2 = −1

  y3 = − 3

 − 1 y1 + y3 = − 3


 2
2 2

 2x1 + 4x2 + x3 = 0
19

 
 x1 = −

 

U x = y ⇐⇒ −x2 + x3 = −1 =⇒ 2
  x2 = 4
x3 = 3
 
1 3


 − x3 = −

2 2
Alors la solution de ce système est
19 

−
 2 
 
x= 4 
 
 
 
3

Exercice 31 On considère la matrice

1 1
 
1

 2 2 
  
  1
 1 1 
, b =  0 
A= 1

 2 2 
 1
 
 1 1 
1
2 2
1. Montrer que A est symétrique dénie positive.
2. Trouver une matrice triangulaire inférieure L = (l ) ∈ M (R) telle que
l > 0 et LL = A (factorisation de Cholesky de A).
ij n
T

3. Résoudre le système linéaire Ax = b. En déduire le déterminant de A.

ii

69
Solution
1. On a
1 1
 
 1 2 2 
 
 
T
 1 1 
A =
 2 1 =A
 2 

 
 1 1 
1
2 2
Alors A est symétrique.
∆1 = a11 = 1 > 0
 
1
 1 2  3
∆2 = det  = >0
 
 1  4
1
2
     
1 1 1 1 1
 1 2  1  2 2  1  2 2 
 1
   
∆3 = det   − det   + det  = >0

 1  2  1  2  1  2
1 1 1
2 2 2
Alors A est dénie positive.
2. √
l11 = a11 = 1
a21 1
l21 = =
l11 2
a31 1
l31 = =
l11 2
√
3
q
2
l22 = a22 − l21 =
2
a32 − l31 l21 1
l32 = = √
l22 2 3
√
2
q
2 2
l33 = a33 − l31 − l32 = √
3
Alors  
1 0 0
√
 
 
 1 3 

L= 0 
 2 2 

√ 
 

 1 1 2 
√ √
2 2 3 3

70
 3. Résoudre le système Ax = b. On a
 
1 1
 1 2 2
 
 √ 
3 1 
T
 
L = 0

√ 

 2 2√ 3 

 2 
0 0 √
3

T y = LT x
LL x = b ⇐⇒
Ly = b

y1 = 1 
y1 = 1


 
√
 
  1
 y2 = − √
 
 1 3

 

y1 + y2 = 0 3
Ly = b ⇐⇒ 2 2 =⇒
  √
√
 

 
 2 3
1 1 2  y3 = √

 

 y1 + √ y2 + √ y3 = 1

 3 2
2 2 3 3

1 1

 x1 + x 2 + x3 = 1
2 2




√

 
 x1 = 1

 3

1 1
T
L x = y ⇐⇒ x 2 + √ x 3 = − √ =⇒ x2 = −1
2 2 3 3
x 3 = 1

 



 √ √

 2 2 3
 √ x3 = √


3 3 2
Alors la solution de ce système est
 
1
 
 
x=
 −1 

 
1

1
det(LLT ) = det(L) × det(LT ) = (det(L))2 =
2

2.1.6 Exercices supplémentaires

Exercice 32 Résoudre le système suivant par la méthode de Gauss, avec a, b ∈ R.


 ax + by + z = 1
x + aby + z = b
x + by + az = 1


71
 Exercice 33 On considère la matrice
   
1 2 −3 −1
A =  2 −12 , b =  0 
−3 2 0 1

1. Montrer que A est symétrique dénie positive.

2. Résoudre le système linéaire par la méthode de Cholesky.
3. En déduire le déterminant de A.

2.2 Méthodes itératives

2.2.1 Le principe
Étant donné le système Ax = b à résoudre, les méthodes itératives de résolution des
systèmes linéaires consistent à calculer les valeurs successives d'une suite de vecteurs
x(k) convergeant vers la solution x quand k −→ ∞.

lim x(k) = x (1)

k→+∞

On décompose A en A = M − N où M est une matrice inversible alors

Ax = b ⇐⇒ M x = N x + b

conduit à l'itération
M x(k+1) = N x(k) + b, k≥0
x(k+1) = M −1 N x(k) + M −1 b
Alors
M −1 N = B et M −1 b = c
La suite (x(k) )k∈N est obtenue à partir d'un vecteur initial arbitraire x(0) , par une
relation de récurrence de la forme
x(k+1) = Bx(k) + c, ∀k ∈ N (2)

où la matrice B est carrée, appelée matrice d'itération de la méthode, et le vecteur c

dépendant de la matrice A et du second membre de b du système à résoudre.
2.2.2 Étude de la convergence
Dénition 3 On dit que la méthode itérative est convergente si l'on a (1) pour tout
initialisation x dans R .
(0) n

Dénition 4 Une méthode itérative de la forme (2) est dite consistante avec le système
linéaire Ax = b si B et c vérient
x = Bx + c

le vecteur x étant la solution du système Ax = b, ou de manière équivalente

c = (In − B)A−1 b

72
Dénition 5 On appelle erreur (resp. résidu) à l'itération k (k ∈ N) de la méthode
itérative le vecteur
e = x − x ( resp. r = b − Ax )
(k) (k) (k) (k)

où x = A b est la solution du système Ax = b.

−1

On déduit de ces dénitions qu'une méthode itérative consistante de la forme (2)

converge si et seulement si
lim e(k) = 0
k→+∞

Soit encore si
lim r(k) = lim Ae(k) = 0
k→+∞ k→+∞

Théorème 12 Si une méthode de la forme (2) est consistante, celle ci est convergente
si et seulement si ρ(B) < 1.
Démonstration . Voir [5]
Lemme 1 Pour toute matrice carrée B, et toute norme matricielle
1
lim Bk k
= ρ(B) (3)
k→+∞

Démonstration . Voir [4]

2.2.3 Critère d'arrêt

En pratique, il conviendrait de mettre n aux calculs à la première itération pour
laquelle l'erreur est "susamment petite", c'est-à-dire le premier entier naturel k tel
que
e(k) = x(k) − x ≤ 
où  est une tolérance xée et k.k est une norme vectorielle donnée. Cependant on ne
sait généralement pas évaluer l'erreur, puisque la solution x n'est pas connue, et il faut
donc avoir recours à un autre critère d'arrêt. Deux possibilités s'imposent alors.
1ière possibilité : Tout d'abord, les résidus r(k) = b − Ax(k) étant très facile à
calculer, on peut tester si
r(k) ≤ δ
avec δ une tolérance xée. Puisque l'on a

e(k) = x(k) − x = x(k) − A−1 b = A−1 r(k) ≤ A−1 r(k)

on doit choisir δ tel que


δ≤
kA−1 k
Ce critère peut par conséquent être trompeur si la norme de A−1 est grande et qu'on ne
dispose pas d'une bonne estimation de cette dernière. Il est en général plus judicieux
de considérer dans le test d'arrêt un résidu normalisé
r(k)
≤δ
kr0 k

73
ou encore
r(k)
≤δ
kbk
2ième possibilité : Correspond au choix de l'initialisation x(0) . Dans ce cas on obtient
le contrôle suivant de l'erreur relative
e(k) r(k)
≤ A−1 ≤ cond(A)δ
kxk kxk

où cond(A) désigne le conditionnement de la matrice A relativement à la norme subor-

donnée k.k considérée (voir Annexe).

Un autre critère parfois utilisé dans la pratique est basé sur l'incrément x(k+1) −
x ,k ∈ N . L'erreur d'une méthode itérative de la forme (2) vériant la récurrence
(k)

x(k+1) = Bx(k) , ∀k ∈ N, on obtient par l'utilisation de l'inégalité triangulaire

e(k+1) ≤ kBk e(k) ≤ kBk e(k+1) + x(k+1) − x(k)

, ∀k ∈ N

d'où
kBk
e(k+1) ≤ x(k+1) − x(k)


∀k ∈ N
1 − kBk

Théorème 13 (Convergence et équivalence)

Soit B ∈ M (C) les assertions suivantes sont équivalentes :
1. lim B = 0 (autrement dit lim B = 0 pour k.k quelconque sur M (C)).
n

k k
n
k→+∞ k→+∞

2. Pour tout x ∈ C , lim B x = 0 (autrement dit lim B x = 0 pour k.k

n k k

quelconque sur M (C)).

k→+∞ k→+∞

3. ρ(B) < 1
n

4. Il existe une norme matricielle telle que kBk < 1.

Démonstration . Voir [6]
Théorème 14 Soit A une matrice hermitienne dénie positive, si la matrice hermi-
tienne M ∗
+ N est dénie positive, alors ρ(B) < 1.

Démonstration . Voir [6]

74
2.2.4 Méthode de Jacobi

Charles Gustave Jacob Jacobi, ou

Carl Gustav Jakob Jacobi (10 dé-
cembre 1804 - 18 février 1851), est un ma-
thématicien allemand surtout connu pour ses
travaux sur les intégrales elliptiques, les équa-
tions aux dérivées partielles et leur application
à la mécanique analytique. Il était le frère du
physicien Moritz von Jacobi, découvreur de la
galvanoplastie.

Principe de la méthode
Soit encore Ax = b le système linéaire à résoudre. La méthode de Jacobi correspond
à la décomposition de la matrice A sous la forme A = D − E − F avec D matrice diago-
nale constituée des éléments diagonaux aii de A, E et F sont des matrices triangulaires
dénies par
si i > j si i < j
 
aij aij
(−E)ij = et (−F )ij =
0 sinon 0 sinon
On suppose que A ne possède pas de zéros sur sa diagonale. Dans cette méthode, on
prend
M = D et N = E + F
L'avantage de cette méthode est que dans ce cas là, M est très facile à inverser. La
méthode de Jacobi s'exprime alors par la suite
donné

x(0)
x (k+1)
= D−1 (E + F )x(k) + D−1 b pour tout entier k ≥ 0
La matrice d'itération de Jacobi est donnée par

J = D−1 (E + F )

On observe que la méthode de Jacobi correspond à l'écriture ligne par ligne suivante
n
!
(k+1) 1 X (k)
xi = bi − aij xj , i = 1, · · · , n, k ∈ N
aii j=1,j6=i

75
2.2.5 Méthode de Gauss-Seidel

Philipp Ludwig von Seidel (24 octobre

1821 à Deux-Ponts et mort le 13 août 1896
à Munich), était un mathématicien, physicien
de l'optique et astronome allemand. Seidel est
connu pour la méthode de Gauss-Seidel sur la
résolution des équations numériques. Il étudia
les aberrations optiques du premier ordre qu'il
décompose en cinq polynômes dits polynômes
de Seidel.

Principe de la méthode
Dans cette méthode, on prend

M = D − E et N = F

La méthode de Gauss-Seidel s'exprime alors par la suite

donné

x(0)
x (k+1)
= (D − E)−1 F x(k) + (D − E)−1 b pour tout entier k ≥ 0
La matrice d'itération de Gauss-Seidel est donnée par

G = (D − E)−1 F

On observe que la méthode de Gauss-Seidel correspond à l'écriture ligne par ligne

suivante
i−1 n
!
(k+1) 1 X (k+1)
X (k)
xi = bi − aij xj − aij xj , i = 1, · · · , n, k ∈ N
aii j=1 j=i+1

2.2.6 Convergence de la méthode de Jacobi et de Gauss-Seidel

Soit e(k) le vecteur erreur.

e(k+1) = Je(k) = J (k+1) e(0) resp. e(k+1) = Ge(k) = G(k+1) e(0)

L'algorithme de Jacobi (resp. Gauss-Seidel) converge si

 
lim e (k)
= 0 ⇐⇒ lim J (k)
=0 resp. lim G (k)
=0
k→+∞ k→+∞ k→+∞

Théorème 15 Une condition nécessaire et susante pour que

resp. lim G = 0
 
(k) (k)
lim J =0
k→+∞ k→+∞

est que
ρ(J) < 1 ( resp.ρ(G) < 1)
76
Théorème 16 Les méthodes de Gauss-Seidel et Jacobi convergent ∀x pour les sys- (0)

tèmes linéaires dont la matrice est à diagonale strictement dominante.

Démonstration . Voir [5]
Théorème 17 Soit A une matrice tridiagonale, alors les rayons spectraux des mé-
thodes de Gauss-Seidel et de Jacobi sont reliés par
ρ(G) = [ρ(J)]2

Ainsi pour ce type de matrice, les deux méthodes convergent ou divergent simultanément
et si elles convergent, Gauss-Seidel est plus rapide.
Démonstration . Voir [6]

2.2.7 Méthode de Relaxation

Principe de la méthode
C'est une méthode intermédiaire entre les deux méthodes précédentes dépendant
d'un paramètre w. Ce paramètre est déterminé pour obtenir une convergence plus
rapide. Dans cette méthode, on prend
1 1−ω
M= D − E et N = D+F
ω ω
où ω est un paramètre de relaxation.
La méthode de relaxation s'exprime alors par la suite
donné
 (0)
 x  −1    −1
1 1−ω 1
 x (k+1)
= D−E D+F x (k)
+ D−E b pour tout entier k ≥ 0
ω ω ω

La matrice de relaxation est donnée par  

 −1 
1 1−ω
Lω = D−E D+F
ω ω
La méthode de Gauss-Seidel correspond au cas ω = 1.
La méthode de relaxation s'écrit ligne par ligne comme une extrapolation de la
composante obtenue par Gauss-Seidel. On a

(relax) = ωxi (Gauss-Seidel) + (1 − ω)xi (relax)

(k+1) (k+1) (k)
xi

Proposition 3 Lorsque ρ( L ) ≥ |1 − ω| la méthode de relaxation ne peut converger

que si 0 < ω < 2.
ω

Démonstration . Voir [4]

Théorème 18 On suppose que A est symétrique dénie positive. Alors la méthode
de relaxation converge pour tout ω ∈]0, 2[ (en particulier la méthode de Gauss-Seidel
converge).
Démonstration . Voir [4]

77
Remarque 12 On peut montrer que si D E et D F sont à éléments positives ou
−1 −1

nuls, alors, dès que la méthode de Jacobi converge, il en est de même de celle de Gauss-
Seidel. De plus, la convergence de celle ci est au moins aussi rapide. Ce phénomène
n'est pas systématique comme on peut le voir dans l'exercice 36.
Cependant, pour de nombreux systèmes, surtout lorsqu'ils proviennent de la discré-
tisation d'équations aux dérivées partielles, la méthode de Gauss-Seidel converge plus
vite que celle de Jacobi. De plus pour une large famille de tels systèmes, on peut montrer
qu'il existe un paramètre ω optimal pour lequel la méthode de relaxation est considé-
∗

rablement plus ecace. Le nombre d'itérations nécessaires pour atteindre une précision
donnée chute considérablement lorsque ω est voisin de ω . ∗

On va énoncer sans démonstration un résultat dans ce sens. Pour cela, on a besoin de

la dénition suivante :
A étant décomposée comme précédemment, on note

L = D−1 E, U = D−1 F

d'où
A = D(I − L − U ), J =L+U
Lω = (I − ωL)−1 ((1 − ω)I + ωU )

Dénition 6 On dira que A est de type (V ), si α 6= 0, les valeurs propres de J(α) =

1
αL + U
α
sont indépendantes de α.
Remarque 13 On montre que les matrices tridiagonales sont de type (V ). De nom-
breuses matrices provenant de la discrétisation d'équations aux dérivées partielles sont
également de type (V ). Cette notion a été introduite par Varga qui utilise la terminologie
"consistently ordered matrices".
On a le résultat général suivant :
Théorème 19 Soit A de type (V ). Alors
1. ρ(G) = ρ(J) 2

Donc la méthode de Gauss-Seidel converge si et seulement si celle de Jacobi

converge et elle converge alors deux fois plus vite.
2. Si, de plus, les valeurs propres de J sont réelles et ρ(J) < 1, alors le graphe de
ρ(L ) a l'allure suivante :
ω

Plus précisément, on a
78
 !2
2 ρ(J)
ω∗ = p , ρ( L∗ω ) = p
1+ 1− ρ(J)2 1 + 1 − ρ(J)2
et

 ω−1 si ω ≤ ω ≤ 2 ∗

si 0 ≤ ω ≤ ω
r
1 2 2 1 2 2 ∗
 1 − ω + ω ρ(J) + ωρ(J) 1 − ω + ω ρ(J)
2 4

Remarque 14 Le plus souvent, ω est déterminé expérimentalement. Noter à ce pro-

∗

pos que la dérivée à gauche de ρ( L ) en ω = ω est ∞. On aura donc plutôt intérêt

∗

à surévaluer ω car une erreur à droite sur ω sera moins sensible qu'une erreur à
ω
∗ ∗

gauche.
Nombre d'opérations
Il faut noter que chaque itération nécessite (Dans Gauss-Seidel par exemple) : N (N −1)
multiplications+(N −1) additions+1 division ' 2N 2 opérations, si la matrice est pleine
(matrice contenant moins de zéros).
Pour être comparable à la méthode de Gauss, il faut donc que la précision voulue
N
soit obtenue en moins de itérations. Dans la pratique, on constate que les méthodes
3
itératives sont surtout avantageuses lorsque la matrice est creuse ( une matrice conte-
nant beaucoup de zéros) : à chaque itération, le nombre d'opérations est d'ordre kN où
k est une constante xe directement proportionnelle au nombre d'éléments non nuls.
De plus, il sut de stocker les éléments non nuls de A. C'est le dernier point qui est
essentiel dans le choix des méthodes itératives pour les grands systèmes creux : Une
factorisation de type Gauss ou Cholesky, même si elle préserve la structure-bande,
remplit "les trous" à l'intérieur de la bande et nécessite donc plus d'espace mémoire.
Pour N grand, on a le tableau suivant :

Méthodes Nombre d'itérations Nombre d'opérations

4 2 4 3
Jacobi N log N k N log N
π2 π2

2 2 2 3
Gauss Seidel N log N k N log N
π2 π2

1 1
Relaxation N log N k N 2 log N
π π

79
2.2.8 Exercices corrigés

Exercice 34 On considère la matrice suivante

 
4 −1 0
 −1 4 −1 
0 −1 4

1. Etudier la convergence des méthodes de Jacobi et Gauss-Seidel pour cette

matrice.
2. Vérier que ρ(G) = ρ(J) , où G et J désignent respectivement les matrices
2

d'itération des méthodes de Gauss-Seidel et Jacobi.

Solution
1. Soit A = D − E − F avec
     
4 0 0 0 0 0 0 1 0
D =  0 4 0  , E =  1 0 0  et F =  0 0 1 
0 0 4 0 1 0 0 0 0

Pour la méthode de Jacobi :

Soit J = D−1 (E + F ) la matrice de Jacobi
1
 
 4 0 0 
   
  0 1 0
1
D−1  et (E + F ) =
 
=  1 0 1 
 0 4
0 



 0 1 0
 1 
0 0
4
Alors
1
 
 0 4
0 
 
 
 1 1 
J =
 4 0 
 4 

 
 1 
0 0
4
Pour étudier la convergence de la méthode de Jacobi, on va calculer le rayon
spectral de J .
1
 
 −λ 4 0 
 
 
 1 1 
det(J − λI) = det 
 4 −λ 4


 
 
 1 
0 −λ
4

80
  
2 1
= λ −λ +
8
1 1
Les valeurs propres sont : λ1 = 0, λ2 = √ et λ3 = − √ . Alors
8 8
 
1 1
ρ(J) = max 0, √ = √ <1
8 8
Donc la méthode de Jacobi converge.

Pour la méthode de Gauss-Seidel :

Soit G = (D − E)−1  
4 0 0
(D − E) =  −1 4 0 
0 −1 4
det (D − E) = 64 6= 0
1
 
 4 0 0 
 
 
−1
 1 1 
(D − E) =   16 4 0


 
 
 1 1 1 
64 16 4
Alors
1
 
0 0 

 4 
 
 1 1 
G=
 0 16

 4 

 
 1 1 
0
64 16
Pour étudier la convergence de la méthode de Gauss-Seidel, on va calculer le
rayon spectral de G.
1
 
−λ 0

 4 

 
 1 1 
det(G − λI) =   0 16 − λ

 4 

 
 1 1 
0 −λ
64 16
 
2 1
= λ −λ +
8
1
Les valeurs propres sont : λ1 = λ2 = 0 et λ3 = . Alors
8
 
1 1
ρ(G) = max 0, = <1
8 8
Donc la méthode de Gauss-Seidel converge.

81
 2. On a  2
1 1
ρ(G) = = √ = ρ(J)2
8 8
Alors la méthode de Gauss-Seidel converge plus rapidement que celle de Jacobi.

Exercice 35 Soit α et β deux réels. On considère les matrices

   
2 α 0 1 β β
Aα =  α 2 α  , Cβ =  β 1 β 
0 α 2 β β 1

1. Pour quelles valeurs de α (resp. β) la matrice A (resp. C ) est elle dénie

positive?
α β

2. Écrire la matrice d'itération de la méthode de Jacobi associée à A (resp.

C ). Pour quelles valeurs de α (resp. β ) cette méthode converge- t-elle?
α

3. Écrire la matrice d'itération de la méthode de Gauss-Seidel associée à A et

β

calculer son rayon spectral. Pour quelles valeurs de α a-t-on la convergence

α

de cette méthode?
Solution

1. Pour Aα :
∆1 = 2 > 0
 
2 α
∆2 = det = 4 − α2 > 0 ssi − 2 < α < 2
α 2
 
2 α 0 √ √
∆3 = det α 2
 α  = 8 − 4α2 > 0 ssi − 2 < α < 2
0 α 2
√ √
Donc Aα est dénie positive si et seulement si α ∈ ] − 2, 2 [ .
Pour Cβ :
∆1 = 1 > 0
 
1 β
∆2 = det = 1 − β 2 > 0 ssi − 1 < β < 1
β 1
 
1 β 0  
1 1
∆3 = det  β 1 β = β+ (β − 1)2 > 0 ssi β > −
2 2
0 β 1
1
Donc la matrice Cβ est dénie positive si et seulement si β ∈ ] − , 1 [ .
2
2. Soit
     
2 0 0 0 0 0 0 −α 0
D =  0 2 0  , E =  −α 0 0  et F =  0 0 −α 
0 0 2 0 −α 0 0 0 0

82
 Pour Aα :  α 
0 − 0
 α 2 α 
J = D−1 (E + F ) =  − 0 −
 
 2 2

α 
0 − 0
2
Pour étudier la convergence de la méthode de Jacobi, on va calculer le rayon
spectral de J .
 α 
−λ − 0
 α 2 α  
α2

2
det(J − λI) =  − −λ −  = −λ λ −
 
 2 α 2  2
0 − −λ
2
α α
Les valeurs propres sont : λ1 = 0, λ2 = √ et λ3 = − √ .
2 2
On a  
|α| |α|
ρ(J) = max 0, √ =√
2 2
Alors
|α| √ √
ρ(J) < 1 ⇐⇒ √ < 1 ⇐⇒ − 2 < α < 2
2
√ √
Alors la méthode de Jacobi converge pour α ∈ ] − 2, 2 [ .
Pour Cβ :  
0 −β −β
J = D−1 (E + F ) =  −β 0 −β 
−β −β 0
Pour étudier la convergence de la méthode de Jacobi, on va calculer le rayon
spectral de J .
 
−λ −β −β
det(J − λI) =  −β −λ −β  = −λ λ2 − β 2

−β −β −λ

Les valeurs propres sont : λ1 = 0, λ2 = β et λ3 = −β .

3. Soit G = (D − E)−1 F  
2 0 0
D−E = α 2 0 
0 α 2
det(D − E) = 8 6= 0

1
 
0 0
 2 
 
 
 α 1
(D − E)−1

 −4
=
2
0 

 
 
 α2 α 1 
−
8 4 2

83
 Alors  α 
0 − 0
 2 
 
α2
 
 α 
 0
G= − 
 4 2 

 
 α3 α2 
0
8 4
Calculons le rayon spectral de G pour étudier la convergence de la méthode de
Gauss-Seidel.
 α 
−λ − 0
 2 
 
α2
   2 
 α  = λ2 α − λ

det(G − λI) = 
 0 −λ −
 4 2 
 2
 
 α3 α2 
0 −λ
8 4
α2
Les valeurs propres sont : λ1 = λ2 = 0 et λ3 = .
2
Alors
α 2 √ √
ρ(G) = < 1 ⇐⇒ − 2 < α < 2
2
√ √
Donc la méthode de Gauss-Seidel converge pour α ∈ ] − 2, 2 [

Exercice 36 Soit 
1 2 −2


A= 1 1 1 
2 2 1
1. Montrer que ρ(J) < 1 < ρ(G), où G et J désignent respectivement les
matrices d'itérations des méthodes de Gauss-Seidel et Jacobi.
2. Soit maintenant 
2 −1 1


A= 2 2 2 
−1 −1 2
Montrer que ρ(G) < 1 < ρ(J)

Solution
1. Soit  
1 2 −2
A= 1 1 1 
2 2 1
Calculons le rayon spectral de J ensuite de G. Soient
     
1 0 0 0 0 0 0 −2 2
D =  0 1 0  , E =  −1 0 0  et F =  0 0 −1 
0 0 1 −2 −2 0 0 0 0

84
 On a  
0 −2 2
J = D−1 (E + F ) =  −1 0 −1 
−2 −2 0
 
−λ −2 2
det(J − λI) =  −1 −λ −1  = −λ3
−2 −2 −λ
Les valeurs propres sont :λ1 = λ2 = λ3 = 0.
Alors
ρ(J) = 0 < 1
Soit G = (D − E)−1 F 

1 0 0
D−E = 1 2 0 
2 2 1
det(D − E) = 1 6= 0
 
1 0 0
(D − E)−1 =  −1 1 0 
0 −2 1
Alors  
0 −2 2
G =  0 2 −3 
0 0 2
 
−λ −2 2
det(G − λI) =  0 2 − λ −3  = −λ (2 − λ)2
0 0 2−λ
Les valeurs propres sont :λ1 = 0 et λ2 = λ3 = 2.
Alors
ρ(G) = 2 > 1
Donc
ρ(J) < 1 < ρ(G)
2. Soit  
2 −1 1
A= 2 2 2 
−1 −1 2
Calculons le rayon spectral de J ensuite de G. Soient
     
2 0 0 0 0 0 0 1 −1
D =  0 2 0  , E =  −2 0 0  et F =  0 0 −2 
0 0 2 1 1 0 0 0 0
On a  
1 1
 0 2 −2 
 
 
J = D−1 (E + F ) =  −1 0 −1 
 
 
 
 1 
0 0
2

85
  
1 1
 −λ − 
2  2

  1
det(J − λI) =  −1 −λ −1  = −λ3 − λ +
 
  4
 
 1 
0 −λ
2
Les valeurs propres sont : λ1 = 0.236733, λ2 = −0.118366 + i 1.0208 et λ3 = λ2 .
Alors
ρ(J) = max {|λ1 | , |λ2 | , |λ3 |} = |λ2 | = |λ3 | = 1.02764 > 1
Soit G = (D − E)−1 F
 
2 0 0
D−E = 2 2 0 
−1 −1 2

det(D − E) = 8 6= 0

1
 
 2 0 0 
 
 
 1 1
(D − E)−1

=
 −2 0 
 2 

 
 1 1 
0
4 2
Alors
1 1
 
 0 2 −2 
 
 
 1 1 
G= 0 −
 − 
 2 2 

 
 1 
0 0 −
2
1 1
 
 −λ 2
−
2 
 
   2
 1 1  1
det(G − λI) =  0 − − λ
 −  = −λ λ +
 2 2   2
 
 1 
0 0 − −λ
2
1
Les valeurs propres sont : λ1 = 0 et λ2 = λ3 = − .
2
Alors
1
ρ(G) = <1
2
Donc
ρ(G) < 1 < ρ(J)

86
 Exercice 37 Considérons le système linéaire Ax = b avec
 
α 0 γ
A= 0 α β 
0 δ α

avec α, β, γ et δ des paramètres réels.

Donner des conditions susantes sur ces coecients pour avoir la convergence de
la méthode de Jacobi (resp. Gauss-Seidel).

Solution
1. La méthode de Jacobi :
Une condition susante pour que la méthode de Jacobi converge est que la
matrice A soit à diagonale dominante stricte ce qui équivaut à imposer

 |α| > |γ|
|α| > |β|
|α| > |δ|


Cela veut dire que

|α| > max {|β| , |γ| , |δ|}
2. La méthode de Gauss-Seidel :
La condition précédente est aussi susante pour la convergence de Gauss-Seidel.
Une autre condition pour la convergence de cette méthode est que la matrice A
soit symétrique dénie positive.
La symétrie : 
γ=0
β=δ
et on obtient  
α 0 0
A= 0 α β 
0 β α
Elle est dénie positive si ses valeurs propres sont positives.
On a
λ1 = α, λ2 = α − β et λ3 = α + β
Donc il faut que α > 0 et α > |β|.
On note dans ce cas que lorsque A est symétrique dénie positive elle est aussi
à diagonale dominante stricte.

Exercice 38 Considérons le système linéaire suivant

    
6 1 1 x1 12
 2 4 0   x2  =  0 
1 2 6 x3 6

87
 1. Étudier la convergence de la méthode de Jacobi puis approcher la solution
avec 3 itérations à partir de x = (2, 2, 2).
(0)

2. Faire la même chose avec la méthode de gauss-Seidel.

Solution
1. 
 6x1 + x2 + x3 = 12
Ax = b ⇐⇒ 2x1 + 4x2 = 0
x1 + 2x2 + 6x3 = 6


1 1

x 1 = − x2 − x3 + 2





 6 6


1

⇐⇒ x2 = − x1


 2


 x3 = − 1 x1 − 1 x2 + 1



6 3
d'où le procédé itératif de Jacobi
1 (k) 1 (k)

(k+1)
 x 1 = − x − x +2
6 2 6 3







1 (k)

(k+1)
x2 = − x1


 2



 x(k+1)
 1 (k) 1 (k)
= − x1 − x +1

3
6 3 2
On en déduit alors la matrice de Jacobi
1 1
 
 0 −6 −6 
 
 
 1 
J = −
 0 0 
 2


 
 1 1 
− − 0
6 3
1 1
 
 −λ − 6 − 6 
 
 
 = −λ3 + λ − 1
 1 
det(J − λI) = det  − −λ 0
 2


 9 36
 
 1 1 
− − −λ
6 3
Les valeurs propres sont : λ1 = 0.210425− i 0.147395, λ2 = λ1 et λ3 = −0.42085.
Alors
ρ(J) = max {|λ1 | , |λ2 | , |λ3 |} = |λ3 | = 0.42085 < 1
Donc la méthode de Jacobi converge.
Voici maintenant le tableau qui représente la solution approchée après 3 itéra-
tions :

88
 x(0) x(1) x(2) x(3)
2 1.333 2.1666 1.925
2 -1 -0.666 −1.083
2 0 1.111 0.8611

2. Pour la méthode de Gauss-Seidel je laisse le calcul au lecteur.

Exercice 39 Soit le système linéaire


 4x1 + 3x2 + 3x3 = 10
3x1 + 4x2 + 3x3 = 10 (2.2.1)
3x1 + 3x2 + 4x3 = 10


1. Écrire les méthodes de Jacobi et de Gauss-Seidel pour ce système.

2. Étudier la convergence des deux méthodes.
3. Calculer les 3 premiers itérés.

Solution
1. Méthode de Jacobi :
3 3 10


 x 1 = − x2 − x3 +



 4 4 4


3 3 10

(2.2.1) ⇐⇒ x2 = − x1 − x3 +


 4 4 4


 x3 = − 3 x1 − 3 10


x2 +

4 4 4
D'où le système itéré
3 (k) 3 (k) 5

(k+1)
 x1 = − x2 − x +
4 3




 4 2


3 (k) 3 (k) 5

(k+1)
x2 = − x1 − x +


 4 4 3 2



 x(k+1)
 3 (k) 3 (k) 5
= − x1 − x +

3
4 4 2 2
d'où
3 3 5
   
 0 − − 
 4 4   2 
 
   
 3 3  ∗
 5 
J =
 −4 0 − ,b = 
  
 4   2 

   
 3 3   5 
− − 0
4 4 2

89
 Méthode de Gauss-Seidel :
3 3 5


 x1 = − x2 − x3 +



 4 4 2


3 3 5

(2.2.1) ⇐⇒ x2 = − x1 − x3 +


 4 4 2


 x3 = − 3 x1 − 3 5


x2 +

4 4 2
D'où le système itéré
3 (k) 3 (k) 5 3 (k) 3 (k) 5
 
(k+1) (k+1)

 x 1 = − x 2 − x 3 + 
 x 1 = − x2 − x3 +



 4 4 2 


 4 4 2

 

3 (k+1) 3 (k) 5 9 (k) 3 (k) 5
 
(k+1) (k+1)
x2 = − x1 − x3 + ⇐⇒ x2 = x1 − x3 +


 4 4 2 

 16 16 8

 


 x(k+1)
 3 (k+1) 3 (k+1) 5  x3(k+1) = 9 x(k)

 45 (k) 65
= − x1 − x2 + 1 + x +
 
3
4 4 2 64 64 2 32
d'où
3 3 5
   
 0 −4 −4   2 
   
   
 9 3  ∗
 5 
G= 0 − ,b =  

 16 16 

 8 
 
   
 9 45   65 
0
64 64 32
2. Calculons le rayon spectral des deux méthodes
3 3
 
−λ − −

 4 4 

 
 3 3 
det(J − λI) = det   − 4 −λ − 4


 
 
 3 3 
− − −λ
4 4
  
3 2 3 18
= −λ − λ − λ+
4 4 16
3 3
Les valeurs propres sont : λ1 = λ2 = et λ3 = − .
4 2
Donc  
3 3 3
ρ(J) = max , = >1
4 2 2
Alors la méthode de Jacobi ne converge pas.
3 3
 
 −λ −
4
−
4 
 
 
 9 3 
det(G − λI) = det 
 0 16 − λ − 16


 
 
 9 45 
0 −λ
64 64
90
  
2 81 27
= −λ λ − λ +
64 64
Les valeurs propres sont : λ1 = 0, λ2 = 0.6328125 − i 0.14637 et λ3 = λ2 .
ρ(G) = max {0, |λ2 | , |λ3 |} = |λ2 | = 0.649519696 < 1
alors la méthode de Gauss-Seidel converge.
3. Pour calculer les 3 premiers itérés on utilise la méthode de Gauss-Seidel car elle
converge

x(0) x(1) x(2) x(3)

5/2 0.5078125 0.79895 0.95313
5/8 0.595703 0.64651 0.7231675
65/32 1.67236 1.41598 1.242776

Exercice 40 Soit A une matrice carrée d'ordre 3 telle que A = I 3 −E−F avec
   
0 −2 0 0 0 0
E =  −1 0 0  et F = 0 0 0 
0 0 0 −1 −1 0

1. Montrer que A est inversible.

2. Soit 0 <√ω < 2. Montrer que la matrice ω1 I −E est inversible si et seulement
3

si ω 6= 22 .
√
3. Pour 0 < ω < 2, ω 6= 22 , on considère pour la résolution de Ax = b, la
méthode itérative dénie par
x ∈ R et ∀k ∈ N,
   
(0) ? 1 1−ω
(k+1) (k) 0
I −E x 3 = F+ I x +b 3
ω ω
et on pose
 −1  
1 1−ω
Lω = I3 − E F+ I3
ω ω
Calculer en fonction de ω les valeurs propre de L et son rayon spectral.
4. Pour quelles valeurs de ω cette méthode converge -t-elle?
ω

5. Déterminer ω ∈]0, 2[ vériant

∗
o √
2
ρ ( Lω∗ ) = min { ρ ( Lω ) /ω ∈ ] 0, 2 [ , ω 6= 2

Solution
Soit 
1 2 0
A = I3 − E − F =  1 1 0 
1 1 1

91
1.
det(A) = 1 6= 0
Alors A est inversible.
1
2. on a 0 < ω < 2, calculons le déterminant de I3 − E . Soit
ω
1
 
2 0
   ω 
1  1 
I3 − E =  0
 0 
ω ω 
 1 
0 0
ω
 
1 1
I3 − E = 3 1 − 2ω 2


det
ω ω
   
1 1 2


det I3 − E = 0 ⇐⇒ = 0 ∨ 1 − 2ω = 0
ω ω3
√
2
Puisque 0 < ω < 2, on prend la solution 1 − 2ω 2 = 0, ce qui donne ω = .
  √ 2
1 2
Donc pour que I3 − E soit inversible il faut que ω 6= .
ω 2
 −1  
1 1−ω
3. Lω = I3 − E F+ I3
ω ω
1−ω
 
0 0 
   ω
1−ω  1−ω 
F+ I3 =  0 0 
ω  ω 
 1−ω 
−1 −1
ω
et
ω 2ω 2
 
 1 − 2ω 2 − 1 − 2ω 2 0 
 −1  
1  
I3 − E =
 ω2 ω 
ω  − 0

 1 − 2ω 2 1 − 2ω 2


 
0 0 ω
d'où
1−ω 2ω(1 − ω)
 
− 0

 1 − 2ω 2 1 − 2ω 2 

 
Lω =  ω(1 − ω) 1−ω
 
 − 0

1 − 2ω 2 1 − 2ω 2

 
 
−ω −ω 1−ω
1−ω 2ω(1 − ω)
 
 1 − 2ω 2 − λ − 1 − 2ω 2 0 
 
 
det ( Lω −Iλ) = 
 ω(1 − ω) 1−ω 
 − −λ 0

 1 − 2ω 2 1 − 2ω 2


 
−ω −ω 1−ω−λ

92
   
1−ω 1−ω
= (1 − ω − λ) −λ + √ −λ − √
1 + 2ω 1 + 2ω
1−ω 1−ω
Les valeurs propres sont : λ1 = 1 − ω , λ2 = − √ et λ3 = √ .
1 + 2ω 1 + 2ω
Donc ( )
|1 − ω|
ρ ( Lω ) = max |1 − ω| , √
1 + 2ω
|1 − ω|
Soit le graphe de |1 − ω| et √
1 + 2ω

D'après ce graphe on remarque que

ρ ( Lω ) = |1 − ω| , pour 0 < ω < 2
4. On a ρ ( Lω ) < 1, alors la méthode converge pour 0 < ω < 2.
5. D'après le graphe on remarque aussi que
√ o
ω ∗ = 1 tel que ρ ( Lω∗ ) = min { ρ ( Lω ) /ω ∈ ] 0, 2 [ , ω 6= 2
2

2.2.9 Exercices supplémentaires

 
1 a a
Exercice 41 Soit a ∈ R etA= a 1 a 
a a 1
1. Pour quelles valeurs de , est-elle dénie positive?
a A
2. Pour quelles valeurs de , La méthode de Gauss-Seidel converge-t-elle?
a
3. Écrire la matrice J de l'itération de Jacobi.
4. Pour quelles valeurs de a, la méthode de Jacobi converge-t-elle?
5. Écrire la matrice G de l'itération de Gauss-Seidel.
6. Pour quelles valeurs de a, La méthode de Gauss-Seidel converge-t-elle plus
vite que celle de Jacobi?

93
Exercice 42 On considère le système linéaire Ax = b, où
   
2 −1 0 3
A =  −1 2 −1  et b =  −5 
0 −1 2 5

1. Écrire la matrice de Jacobi et celle de Gauss-Seidel.

2. Étudier la convergence de la méthode de Jacobi et celle de Gauss-Seidel.
3. On note par err = x − x l'erreur commise à l'étape k. Estimer le
(k) (k)

nombre minimal d'itérations nécessaires pour que l'erreur à l'étape k soit

∗

telle que
err(k) ≤ 10−4 err(0)
4. En utilisant la méthode adéquate, estimer la solution à 10 près.
−4

94
Chapitre 3
Annexe

3.1 Théorème des valeurs intermédiaires

Théorème 20 Si la fonction f est continue dans [a, b] et f (a) × f (b) < 0 alors ∃α ∈
] a, b [ tel que f (α) = 0. Si de plus f est strictement monotone dans [a, b] alors α est
unique dans [a, b] .

3.2 Théorème de Pythagore

Théorème 21 Si un triangle ABC est rectangle en C , alors AB 2
= AC 2 + BC 2 .

3.3 Théorème de Thalès

Théorème 22 Soit un triangle ABC , et deux points D et E des droites (AB) et (AC)
de sorte que la droite (DE) soit parallèle à la droite (BC) comme le montre la gure
suivante :

Alors on a : AD AE DE
= =
AB AC BC

95
3.4 Éléments matricielles
3.4.1 Inverse des matrices
Dénition 7 Notons M (R) l'ensemble des matrices carrées d'ordre n à coecients
réels. La matrice A ∈ M (R) est dite inversible s'il existe une matrice M (R) notée
n

A telle que
n n
−1

AA−1 = A−1 A = In

3.4.2 Matrices triangulaires

Dénition 8 Une matrice A = (a ) ∈ M (R) est dite triangulaire inférieure
([Link] supérieure), si ∀i < j (resp. i > j), i, j ∈ {1, 2, · · · , n} : a = 0.
ij 1≤i,j≤n n

ij

Remarque 15 Une matrice qui est à la fois triangulaire inférieure et triangulaire

supérieure est dite diagonale.
Proposition 4 Soit A = (a ) ∈ M (R).
1. Si A est triangulaire inférieure (resp. supérieure) et inversible, alors A est
ij 1≤i,j≤n n

−1

triangulaire inférieure (resp. supérieure).

2. Si A est triangulaire inférieure (resp. supérieure), alors
A inversible ⇐⇒ a 6= 0, ∀i, j ∈ {1, 2, · · · , n}
ii

3.4.3 Transposée d'une matrice

Dénition 9 Soit A ∈ M . On dénit la matrice transposée de A et on note A T

la matrice de M (R) par

n,m(R)

n,m

AT = (aij ) ∈ Mm,n (R)

Proposition 5 Soit A ∈ M n,m (R) et B ∈ M m,p (R) , on a

(AB)T = B T AT

Proposition 6 Soit A ∈ M (R) inversible, alors A est inversible et on a :

n
T

(AT )−1 = (A−1 )T

qui sera noté A . −T

3.4.4 Matrices symétriques

Dénition 10 Une matrice A ∈ M (R) est symétrique si A = A.
n
T

Proposition 7 Notons S (R) l'ensemble des matrices carrées symétrique d'ordre n.

Si A ∈ M (R) inversible et B une matrice quelconque, alors on a : A+A ∈ S (R)
n
T

et les matrices BB et B B sont symétriques.

n n
T T

96
3.4.5 Déterminant d'une matrice
On note Ωn l'ensemble des permutations d'ordre n.
Dénition 11 Soit A ∈ M (R). On dénit le déterminant de A comme suit :
n

Y
det(A) = Σ(σ) ai,σ(i)
σ∈Ωn

où (σ) est la signature de σ.

Proposition 8 Si A, B ∈ M (R), on a
n

det(AB) = det(A) × det(B) = det(BA)

et T
det(A ) = det(A)
Le déterminant d'une matrice triangulaire ou diagonale est égal au produit des éléments
diagonaux. En particulier det(I ) = 1.n

3.4.6 Matrices dénies positives

Dénition 12 Une matrice A ∈ M (R) symétrique est dite dénie positive si :
n

∀x ∈ Rn , xT Ax ≥ 0

∀x ∈ Rn , xT Ax = 0 ⇐⇒ x = 0

Proposition 9 Si A est une matrice carrée réelle inversible, alors A A est une matrice
T

symétrique dénie positive.

Proposition 10 Si A ∈ M (R) est une matrice dénie positive, alors det(A) > 0 et
∀i ∈ {1, 2, · · · , n}, a > 0.
n

ii

Remarque 16 Une matrice dénie positive est inversible, mais la réciproque n'est pas
vrai.
Dénition 13 (Mineurs principaux) Soit A = (a ) ∈ M (R) une matrice. On
appelle mineurs principaux de A les éléments des matrices
ij 1≤i,j≤n n

.. . . . ..
 
a11 · · · a1k
Ak = 
 

ak1 · · · akk

pour k entier compris entre 1 et n.

Théorème 23 (Critère de sylvester)
Soit A ∈ M (R), il y a équivalence entre :
1. A dénie positive.
n

2. A symétrique et tous les mineurs principaux sont strictement positifs.

Dénition 14 Une matrice symétrique A est dénie positive si toutes ses valeurs
propres sont strictement positives.
97
3.4.7 Normes matricielles
Dénition 15 Étant donné V un espace vectoriel sur R ou C, on appelle norme sur
V toute application (qu'on notera k.k) de V dans [0, +∞[ telle que :
1. kxk = 0 ⇐⇒ x = 0 pour x ∈ V .
2. ∀x ∈ V , ∀λ ∈ R (ou C), kλxk = |λ| kxk (homogénéité).
3. ∀x, y ∈ V ,kx + yk ≤ kxk + kyk (inégalité triangulaire).
En particulier, on a les normes classiques de Rn (ou Cn ).

N N
! 21
X X
kxk1 = |xi | , kxk2 = x2i , kxk∞ = max |xi |
1≤i≤N
i=1 i=1

Plus généralement, on peut considérer

N
! p1
X
kxkp = xpi ,1 ≤ p ≤ ∞
i=1

La notation kxk∞ utilisée ci-dessus provient du fait que

∀x ∈ Rn , lim kxkp = max |xi | (= kxk∞ )

p→∞ 1≤i≤N

Norme sur l'espace vectoriel des matrices

Une matrice carrée d'ordre N est la donnée de N 2 réels (ou complexes) : elle peut
donc être identiée à un élément de RN fournit une norme sur l'espace des matrices.
2

Ainsi, si A = [aij ], on peut poser

N
! 12
kAk = max |aij | ou kAk =
X
a2ij
1≤i,j≤N
i,j=1

Cependant, pour qu'une norme soit pratiquement utiliser, il faut qu'elle soit compatible
avec le produit des matrices, ce qui nous conduit à exiger cette propriété :

kABk ≤ kAk kBk

Dénition 16 On appelle norme matricielle toute norme sur l'espace vectoriel des
matrices vériant ci-dessus.
Étant donné une norme vectorielle k.k dénie sur Rn , il existe une norme matricielle
naturellement associée à k.k : on l'appelle norme matricielle induite par k.k et elle est
dénie par :  
kAxk
kAk = max = max kAxk
kxk6=0 kxk kxk=1

Proposition 11 1. kAk ∞ = max |aij |

2. kAk
1≤i≤N

1 = max |aij |
1≤j≤N

98
 3. kAk = pρ(A A) où A = Ā (adjointe de A)
∗ ∗ t

et ρ(M ) désigne le rayon spectral de la matrice M dénit par

2

ρ(M ) = max {|λ | ; λ valeurs propres de M }

i i
1≤i≤N

Dans le cas particulier où A est symétrique, kAk = ρ(A). 2

Remarque 17  Toute racine carrée d'une valeur propre de A A est appelée ∗

valeur singulière de A. Si A est normale (c'est-à-dire A A = AA ), alors ∗ ∗

ρ(A A) = ρ(A). Dans tout les cas ρ(A A) = ρ(AA )

p ∗ ∗
∗

 kAk et kAk se calculent simplement à partir de la matrice A contrairement

à kAk ∞ 1

 On utilise aussi la norme, dite de Fröbenius

2

N
! 21
X 1
kAkF = a2ij = (T race(A∗ A)) 2
i,j=1

Il s'agit d'une norme matricielle, mais non induite par une norme vectorielle.
Dénition 17 Une matrice A = (a ) ∈ M (C) est dite " à diagonale dominante " si
pour chaque i ∈ [1 : n], on a
ij n

N
X
|aij | ≤ |aii |
j=1,j6=i

Elle sera dite " à diagonale dominante stricte " si toutes ces égalités sont strictes.
Corollaire 2 Une matrice à diagonale dominante stricte est inversible.

3.4.8 Conditionnement d'une matrice

Quand on veut résoudre numériquement Ax = b avec A ∈ Mn (C), n >> 1, divers
facteurs inuent sur la précision du résultat :
 Incertitude sur les données (expérimentales) de A et/ou de b.
 Erreur dans la représentation des coecients de A et b avec un nombre ni
décimales (ordinateur).
 Erreurs d'arrondi lors des calculs.
 Erreurs prévisibles de l'algorithme, notamment lors des calculs approchés par
des méthodes itératives.
Considérons le système linéaire
Ax = b (3.4.1)
Considérons une petite perturbation de b notée δb. La solution correspondante est
perturbée soit
A(x + δx) = b + δb (3.4.2)
On va mesurer la variation relative de x en fonction de celle de b. Pour cela, on prend
k.k une norme quelconque sur Rn .
de (3.4.1) et (3.4.2), on tire
A(δx) = δb ⇔ δx = A−1 (δb)

99
Utilisant la norme matricielle induite, on a

kδxk ≤ A−1 kδbk

par ailleurs, avec (3.4.1)

kbk ≤ kAk kxk
ces deux inégalités donnent
kδxk kδbk
≤ A−1 kAk (3.4.3)
kxk kbk

cette estimation sur la variation de x est en fait optimale puisqu'on peut trouver x0 tel
que kAx0 k = kAk kx0 k et δb tel que kA−1 k kδbk = kA−1 (δb)k.
Ainsi la variation relative en x sera d'autant plus grande que le nombre kA−1 k kAk
est plus grand : on l'appelle conditionnement de A relatif à la norme k.k.
Dénition 18 On appelle conditionnement de la matrice A (dans la norme matricielle
k.k), le nombre −1
cond(A) = A kAk
Si on travail avec k.k , on notera le conditionnement associé cond .
p p

C'est le même nombre qui intervient lors de la variation des coecients de A : Suppo-
sons, en eet que A soit perturbée par une matrice ∆A, alors

Ax = b

(A + ∆A) (x + δx) = b
=⇒ A (δx) + ∆A (x + δx) = 0
=⇒ δx = −A−1 ∆A (x + δx)
=⇒ kδxk ≤ A−1 k∆Ak kx + δxk
kδxk k∆Ak
=⇒ ≤ cond(A)
kx + δxk kAk

Remarque 18 On ne modie pas le conditionnement d'une matrice en la multipliant

par un scalaire, par contre, on peut diminuer cond A en multipliant certaines lignes ou
certaines colonnes par les coecients non nuls : il s'agit de l'équilibrage de la matrice.
2

C'est une technique de pré-conditionnement très utilisée en pratique.

Exemple de système linéaire mal conditionné
   
10 7 8 7 32
 7 5 6 5   23 
A=
 8
,b =  
6 10 9   33 
7 5 9 1 31

et la solution  
1
 1 
x= 
 1 
1

100
Le système perturbé
    
10 7 8 7 x1 + δx1 32.1
 7 5 6 5   x2 + δx2
    22.9 
 = 
 8 6 10 9   x3 + δx3   33.1 
7 5 9 1 x4 + δx4 30.9

a pour solution  
9.2
 −12.6 
 
 4.5 
−1.1
1
Ainsi une erreur relative de sur les données entraîne une erreur relative de l'ordre
200
10
de du résultat (erreur ampliée de 2000).
1
De même
    
10 7 8.1 7.2 x1 + ∆x1 32
 7.08 5.04 6 5   x2 + ∆x2   23 
  = 
 8 5.98 9.89 9   x3 + ∆x3   33 
6.99 4.99 9 9.98 x4 + ∆x4 31

a pour solution  
−81
 137 
 
 −34 
22
pourtant, la matrice est " bonne " (symétrique, de déterminant 1, donc loin de 0). Son
inverse est donné par  
25 −41 10 −6
 −41 68 −17 10 
A−1 =
 10 −17 5 −3 


−6 10 −3 2
Mais les valeurs propres de A sont

λ1 ' 0.01015 < λ2 ' 0.8431 < λ3 ' 3.858 < λ4 ' 30.2877

si bien que
λ4
cond2 (A) = ' 2984
λ1
est grand, d'autre part
       
1 8.2 32 0.1
 , δx =  −13.6  , b =  −0.1 
 1     23  
x=
 1   3.5 
 , δb =  
 33   0.1 
1 −2.1 31 −0.1

de sorte que
kδxk2 kδbk2
≤ cond2 (A)
kxk2 kbk2

101
Bibliographie

[1] Gloria Faccanoni, Analyse numérique Recueil d'exercices corrigés et aide-mémoire.,

2013-2014.
[2] Chokri, Bekkey, Zouhaier et Helali, http ://[Link].u-
[Link]/wims/modules/U3/analysis/[Link]/doc/les/[Link].
[3] Hassen Douzi, https ://[Link]/doc/52713874/Poly-AN-Douzi.
[4] Michel Pierre et Antoine Henrot, Analyse Numérique, cours de Takéo Takahashi,
cours électif CE33, Ecole des Mines de Nancy, 2013-2014.
[5] Guillaume Legendre, Méthodes Numériques. Introduction à l'analyse numérique et
au calcul scientique, cours, DAUPHINE université Paris, 2009-2010.
[6] R. S. Wilson, cf. P. G. Ciarlet, Introduction à l'analyse numérique matricielle et à
l'optimisation, livre, édition Dunod, 1999.
[7] G. Bontempi, Calcul Formel et Numérique, Département d'informatique, Boulevard
de Triomphe-CP212, 2014 .

102