Analyse numérique I

Mohamed LAMNII
 Table des Matières

1 Résolution numérique de systèmes linéaires AX = B . . . . . . . . . . . . . . . . . . . 4

1.1 Méthodes directes de résolution de AX = B 4
1.1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.2 Méthode de Gauss sans pivot . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.1.3 Méthode de Gauss avec pivot . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.1.4 Factorisation LU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.1.5 Factorisation de Cholesky(matrice symétrique) . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.2 Méthodes itératives 15
1.2.1 Quelques rappels sur les matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.2.2 Méthodes classiques(Jacobi, Gauss Seidel, Relaxation) . . . . . . . . . . . . . . . . . . . 15

2 Résolution de l’équation f (x) = 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.1 Rappels et notations 19
2.2 Méthode du point fixe 21
2.3 Méthode de Newton 24
2.4 Méthode de Newton modifiée 26
2.5 Méthode de dichotomie 26
2.6 Méthode de la sécante 28
2.7 Méthode de fausse position ( Regula Falsi) 29
 1. Résolution numérique de systèmes linéaires AX = B

1.1 Méthodes directes de résolution de AX = B

1.1.1 Introduction
Exemples :(
x1 − x2 = 0 L1
Résoudre (S) :
x1 + x2 = 2 L2
− Par substitution
L1 → x1 = x2
L2 → 2x1 = 2 ⇒ x1 = 1 ⇒ x2 = x1 = 1

− Par combinaison de lignes

L1 → x1 − x2 = 0 L2′ ← L2 − L1 ⇒ 2x2 = 2 − 0 = 2 ⇒ x2 = 1 = x1
− Par inversion de la matrice
Le système (S) s’écrit sous la forme AX = B avec :
     
1 −1 x1 0
A= , X= et B=
1 1 x2 2
 
1 t 1 1
det A = 2, A−1 = det A com A = 1
2 −1 1
Si A−1 existe alors X = A−1 B
   1 1
   
x1 2 2
0 1
= =
x2 − 12 1
2 2 1

− Par méthode de Cramer

det (Ai )
xi =
det(A)
1.1 Méthodes directes de résolution de AX = B 5

où det (Ai ) désigne le déterminant de la matrice obtenue en remplaçant la ieme colonne de A par le
vecteur b.
0 −1
2 1
x1 = =1
1 −1
1 1
1 0
1 2
x2 = = 1.
1 −1
1 1

Résoudre
4x1 + 15x2 + 3x3 − 17x4 = −18

 L1


 +13x2 + 5x3 + 4x4 = 0 L2
S′ :




 −2x3 + 5x4 = 8 L3

7x4 = 14 L4
    
4 15 3 −17 x1 −18
 0 13 5 4   x2
    0 
(S) 
 0 0 −2
= 
5   x3   8 
0 0 0 7 x4 14

Résolution par remontée (en commençant par x4 )

14
L4 → x4 = =2
7
(8 − 5 × 2)
L3 → x3 = =1
−2
(0 − 4 × 2 − 5 × 1)
L2 → x2 = = −1
13
(−18 + 17 × 2 − 3 × 1 + 15 × 1)
L1 → x1 = =7
4
Système triangulaire : cas général


 u11 x1 + u12 x2 + · · · + u1n xn = b1 L1
u22 x2 + · · · + u2n xn = b2 L2


(ST ) : .. .... ..


 . . . .
unn xn = bn Ln


Le système ( ST ) s’écrit sous la forme UX = B.

On suppose que ukk ̸= 0, pour k = 1, · · · , n, alors :
xn = ubnnn
xn−1 = (bn−1 − un−1n x!n ) /un−1n−1
j=n
xi = bi − ∑ ui j x j /uii , i = n − 1, . . . .1
j=i+1
Algorithme de résolution pour UX = B
 6 Chapitre 1. Résolution numérique de systèmes linéaires AX = B

bn
xn =
un,n
Pour i = n − 1 à 1
xi = bi
Pour j = i + 1 à n
xi = xi − ui j x j
Fin pour j
xi
xi =
uii
Fin pour i

R 1-) La matrice U est dite triangulaire supérieure. Elle est inversible si tous les termes diagonaux
sont non nuls et
detU = u11 × u22 × · · · × unn
2-) La matrice triangulaire inférieure se traite de façon similaire.
3-) le nombre d’opérations nécéssaires est :
n(n−1)
2 multiplications, n(n−1)
2 additions et n divisions soit au total n2 opérations

1.1.2 Méthode de Gauss sans pivot

Elle consiste à ramener un système linéaire de la forme AX = B (avec A est une matrice pleine)
à un système de la forme UX = D (avec U une matrice triangulaire supérieure) puis à résoudre ce
dernier par la méthode de remontée.

■ Exemple 1.1 Résoudre


 3x1 + 5x2 + 2x3 = 8 L1
S′ :


0x1 + 8x2 + 2x3 = −7 L2
6x1 + 2x2 + 8x3 = 26 L3


 (1)
 (1)
 3x1 + 5x2 + 2x3 = 8
 L1 ← L1  3x1 + 5x2 + 2x3 = 8
 L1 ← L1
(1) (1)
Etape1 : 0 + 8x2 + 2x3 = −7 L2 ← L2 Etape2 : 0 + 8x2 + 2x3 = −7 L2 ← L2
(1) (2) (1) (1)
 
0 − 8x2 + 4x3 = 10 L3 ← L3 − 2L1 0 + 0 + 6x3 = 3 L3 ← L3 + L2
 
D’où :

1
x3 =
2
x2 = (−7 − 2x3 ) /8 = −1
x1 = (8 − 2x3 − 5x2 ) /3 = 4
■
1.1 Méthodes directes de résolution de AX = B 7

Dans le cas général on a :


(0) (0) (0) (0) (0)

 a11 x1 + a12 x2 + a13 x3 + · · · + a1n xn = b1
 a(0) x + a(0) x + a(0) x + · · · + a(0) x = b(0)


21 1 22 2 23 3 2n n 2
(S0 ) . . . .

 .
. .
. . . = ..

 (0)
 (0) (0) (0) (0)
an1 x1 + an2 x2 + an3 x3 + · · · + ann xn = bn
(0)
(0) ai1
Etape1 : On suppose a11 ̸= 0 et on pose mi1 = (0)
a11
(0)
On remplace la ligne Li par
(1) (0) (0)
Li ← Li − mi1 L1 pour i = 2, 3, · · · , n

Donc
(1) (0) (0)
ai j = ai j − mi1 a1 j pour i, j = 2, 3, · · · ; n
(1) (0) (0)
bi = bi − mi1 b1 pour i = 2, 3, · · · ; n
(1)
(1) ai2 (1)
Etape2 : A nouveau, on suppose a22 ̸= 0 et on pose mi2 = (1) On remplace la ligne Li par
a22
(2) (1) (1)
Li ← Li − mi2 L2 pour i = 3, · · · , n
(2) (1) (1)
ai j = ai j − mi2 a2 j pour i, j = 3, · · · , n
et
(2) (1) (1)
bi = bi − mi2 b2 pour i = 3, · · · , n
On obtient alors le système (S2 ) suivant :

(0) (0) (0) (0) (0)

 a11 x1 + a12 x2 + a13 x3 + · · · + a1n xn = b1
 0 + a(1) x + a(1) x + · · · + a(1) x (1)


22 2 23 3 2n n = b2
(S2 ) : .. .. ..


 . . .
 (2) (2) (2)
0 + 0 + an3 x3 + · · · + ann xn = bn


(k−1)
En supposant qu’à chaque étape on a akk ̸= 0, on poursuit la la transformation jusq’à l’obtention
d’un système triangulaire

(0) (0) (0) (0)

 a11 x1 + a12 x2 + · · · + a1n xn = b1
(1) (1) (1)

0 + a22 x2 + · · · + a2n xn

 = b2
(Sn−1 ) : .. .. ..


 . . .
 (n−1) (n−1)
0 + 0 + 0 + · · · + 0 + ann xn = bn


On obtient alors la solution en commençant par :

(n−1)
bn
xn = (n−1) , xn−1 , xn−2 , · · · , x2 , x1
ann

Ecriture matricielle :
8 Chapitre 1. Résolution numérique de systèmes linéaires AX = B
 
(0) (0) (0) (0)
a11 a12 · · · · · · a1n b1
 ··· ··· ··· ··· ··· ··· 
 
ètape 0 : A(0) = A = 
 ··· ··· ··· ··· ··· ··· 

(0) (0) (0)
a1n · · · · · · · · · ann bn
 (0) (0) (0) (0)

a11 a12 · · · · · · a1n b1
 0 a(1) (1)
· · · · · · a2n b2 
(1) 

22
ètape 1 : A(1) =  .. 
 0 ··· ··· ··· ··· . 
 
(1) (1) (1)
0 an2 ··· ··· ann bn
(0) (0) (0) (0)
 
a a12 · · · ··· a1n b1
 11 (1) (1) (1)
a22 · · · ···

 0 a2n b2 
ètape n-1 : A(n−1) =  .. 
 0 0 ··· ··· ··· .
 

(n−1) (n−1)
0 0 ··· 0 ann bn
Matrices élementaires de Gauss

Soient les matrices  

1
 −m21 1 0 
M1 = 
 
.. .
0 ..

 . 
−mn1 1
 
1
 .. 

 0 . 

 0 1 
Mk = 
 
.. .. 

 . −mk+1k . 

 .. .. .. 
 . . . 
0 −mk+1k 1

En posant ek = (0, · · · , 1, 0, · · · , 0)⊤ et mk = (0, · · · , 0, mk+1k , · · · , mnk )⊤ , on obtient :

−1
Mk = I − mk e⊤k et on vérifie facilement que Mk est inversible et que Mk = I + mk ek .
⊤

On montre alors que :

Etape 1 : A(1) = M1 A(0)
Etape k : A(k) = Mk A(k−1) = Mk Mk−1 · · · M2 M1 A(0)
Etape n-1 :U = A(n−1) = Mn−1 · · · M2 M1 A(0) .

(k−1) (k−1)
R Le procédé suppose que tous les akk ̸= 0. Si à une étape k on a akk = 0 et s’il ya au moins
(k−1)
un des aik ̸= 0 ( i = k + 1, · · · .n ) on permute les lignes k et i et on continue.
Sinon ça voudrait dire que la matrice A n’est pas inversible.

En utilisant la méthode de Gauss sans pivot, le nombre d’opérations nécéssaires au calcul de la

1.1 Méthodes directes de résolution de AX = B 9

solution de AX = B est égal à :

2 3 3 2 7
n + n − n
3 2 6
dont n(n−1)(2n+5)
6 additions, n(n−1)(2n+5)
6 multiplications et n(n+1)
2 divisions.
La méthode de Cramer nécéssite environ n(n + 1)! opérations.
Par exemple
N 4 5 10
Gauss 62 115 805
Cramer 480 3600 399168000
Matrices émentaires de permutation

Les matrices élémentaires de permutation sont de la form

R Ik,I A échange les lignes k et I de A alors que AIk,I échange les colonnes k et I de A. On a encore
−1 ⊤.
Ik,I = Ik,I = Ik,l

■ Exemple 1.2 Soit A la matrice donnée par :

   
1 2 3 0 0 1
A =  4 5 6  et I13 =  0 1 0 
7 8 9 1 0 0
   
7 8 9 3 2 1
alors I13 A =  4 5 6  et Al13 =  6 5 4 . ■

1 2 3 9 8 7

Définition 1.1 Une matrice de permutation est un produit de matrices élémentaires de permuta-
tion.
 10 Chapitre 1. Résolution numérique de systèmes linéaires AX = B

1.1.3 Méthode de Gauss avec pivot

■ Exemple 1.3 Soit à résoudre le système

10−10 x1 + x2 = 1


x1 − x2 = 0

La solution théorique est x1 = x2 = 1/ 1 + 10−10 ≃ 1. Cependant, la résolution du système par la

méthode de Gauss donne des résultats différents selon qu’on l’applique avec ou sans pivot.

i) Si on applique la méthode de Gauss sans pivot on obtient

(1)
a21 1
m21 = = = 1010
(1)
a11 10−10

10−10 x1 + x2 = 1
(
et (S2 )
−1 − 1010 x2 = −1010

1010
qui donne pour solution approchée x2 = 1+1010
≃ 1 et x1 ≃ 0.

ii) Si on adopte la stratégie du pivot partiel qui consiste à mettre en première ligne celle dont le
coefficient de x1 est le plus grand en module alors on permute les lignes pour obtenir le système

x1 − x2 = 0
(S1 )
10−10 x1 + x2 = 1

10−10
Pour lequel m21 = 1 = 10−10 et qui conduit à la solution approchée : x2 ≃ 1 et x1 = x2 ≃ 1. ■

A travers cet exemple simple, on voit donc le problème que peut poser un pivot trop petit (a
cause des erreurs d’arrondi). Pour éviter de diviser par des pivots trop petits pouvant conduire à des
solutions absurdes, on peut adopter automatiquement une stratégie du pivot

- Stratégie du pivot partiel (La méthode de Gauss avec pivot partiel) : A chaque étape k : on
(k)
choisit akk tel que :
(k) (k)
akk = max aik .
i≥k

(k)
On permute alors les lignes d’indices i et k pour amener en position de pivot l’élément aik .
Matriciellement, cette opération revient à multiplier la matrice A(k) par une matrice de permutation
Ikl avant d’appliquer l’élimination de Gauss.
La méthode de Gauss avec pivot partiel s’écrit donc :

A(2) = M1 I1i A(1) , · · · · · · , A(n) = Mn−1 In−1i · · · M1 I1i A(1) = U

où les Mi sont des matrices élémentaires de Gauss et les Iki des matrices de permutation pour i ≥ k.
Si à une étape k on n’a pas besoin de pivoter, l’écriture reste valable avec Iki = I où I désigne la
matrice identité.
 1.1 Méthodes directes de résolution de AX = B 11
(k)
- Stratégie du pivot total (La méthode de Gauss avec pivot total) : A chaque étape k, on prend akk tel
que :
(k) (k)
akk = max ai j
i≥k
j≥k
On effectue alors des permutations de lignes et de colonnes pour amener en position de pivot
l’élément akij . Ce qui reviendrait à multiplier la matrice A(k) par deux matrices de permutation P et Q,
l’une à droite pour permuter les lignes et l’autre à gauche pour permuter les colonnes.
A(2) = M1 I1i A(1) I1 j
.. ..
.=.
A(n) = Mn−1 In−1i · · · M1 I1i A(1) I1 j · · · In−1 j

1.1.4 Factorisation LU
(k−1)
Théorème 1.1 Si tous les akk ̸ 0 alors la matrice A peut-etre décomposée sous la forme
=
A = LU où U = A(n−1) est une matrice triangulaire supérieure et

L = M1−1 M2−1 · · · Mn−1

−1
 
1 0 ··· ··· 0
 m21 1
 0 ··· ··· 

= m 31 m 32 1 0 ··· 

 ··· ··· ··· 1 0 
mn1 mn2 · · · mnn−1 1

est une matrice triangulaire inférieure.

Preuve :
(1) Mk est inversible car det Mk = 1 pour k = 1, · · · , n − 1
(2) Mk−1 est de la forme de Mk en changeant les les termes −mik en mik , i = k + 1, · · · , n
(3) (Mn−1 Mn−2 · · · M1 )−1 = M1−1 M2−1 · · · Mn−1
−1

(9) Le produit M1−1 M2−1 · · · Mn−1

−1
est une matrice triangulaire inférieure
 
1 0 ··· ··· 0
 m21 1
 0 ··· ··· 

L =  m31 m32 1
 0 ··· 
. ■
 ··· ··· ··· 1 0 
mn1 mn2 · · · mnn−1 1

Théorème 1.2 (Condition suffisante de la factorisation LU )

Soit A une matrice carrée d’ordre n telle que toutes les sous-matrices d’ordre k(k ≤ n)
 
a11 · · · a1k
Ak =  ... .. .. 

. . 
ak1 · · · akk

soient inversibles, alors il existe une matrice triangulaire inférieure L avec lii = 1 et une matrice
12 Chapitre 1. Résolution numérique de systèmes linéaires AX = B

triangulaire supérieure U telles que A = LU. De plus, cette factorisation est unique.
Preuve :
On a A1 = a11 comme det(A1) ̸= 0 =⇒ a11 ̸= 0 a11 non nul, donc on peut appliquer la méthode
d’élimination de Gauss sans pivot on obtient

A(2) = M1 A(1) (P1 = I)

Supposons que nous ayons pu appliquer la méthode de Gauss sans pivot jusqu’à l’étape k c.à. d
P1 = P2 = · · · Pk−1 = I il s’ensuit que
i=1
A(k) = Mk−1 Mk−2 · · · M1 A = ∏ Mi A.
i=k−1

Posons G = Mk−1 Mk−2 · · · M1 on a : A(k) = GA.

 (1) (1) (1) (1) 
a11 a12 · · · a1k · · · a1n
   
1 0 ··· 0 ··· 0 a11 a12 · · · a1k · · · a1n
(2) (2) (2) 
 0 a22 · · · a2k · · · a2n   ∗ 1 ··· 0 ··· 0 a21 a22 · · · a2k · · · a2n 

 .   
 . .. .. .. .. ..   .. .. .. .. . . ..   .. .. .. .. .. .. 
 . . . . . .  

. . . . . . × .
 . . . . . 
(k) (k)  = 
∗ ∗ ··· 1 ··· 0  ak1 ak2 · · · akk · · · akn 

 0 0 · · · akk · · · akn    


. . .. . .. . . . .. .. . . ..   .. .. .. .. .. .. 
  .. ..
 . .. .. ..  . . . .
 . . . . .  . . . . 
0 0 ··· a
(k)
··· a
(k) ∗ ∗ ··· ∗ ··· 1 an1 an2 · · · ank · · · ann
nk nn

(k) (k)
Par un produit par blocs on obtient : Ak = Gk Ak et donc det(Ak ) = det(Ak ) car det(Gk ) = 1.
D’où
(1) (k)
a11 × · · · × akk = det (Ak ) .
(k)
Comme det (Ak ) ̸= 0 =⇒ akk ̸= 0 Donc nous pouvons appliquer la méthode d’élimination de Gauss
sans pivot à l’étape k (Pk = I) Ce qui implique qu’on peut prendre P1 = · · · = Pn−1 = I Et avoir
MA = U et donc A = M −1U
Unicité

Supposons qu’il existe L1 , L2 ,U1 et U2 telles que A = L1U1 = L2U2 , comme L2 et U1 sont inversibles
alors L2−1 L1 = U2U1−1 .
Mais le premier membre de cette égalité est une matrice triangulaire inférieure à diagonale unité et
le second membre est une matrice triangulaire supérieure. Donc on a L2−1 L1 = U2U1−1 = I. On a de
meme L1−1 L2 = U1−1U2 = I ; d’où I1 = L2 et U1 = U2 .
■ Exemple 1.4 
 −x1 + x2 + 2x3 = 2
Résoudre (S′ ) :
3x1 − x2 + x3 = 6
−x1 + 3x2 + 4x3 = 4

   
−1 1 2 −1 1 2
(1)
Donc A =  3 −1 1  =⇒ A =  0 2 7 
−1 3 4 0 2 2
   
1 0 0 1 0 0
−1
on a M1 =  3 1 0 , =⇒ M1 =
  −3 1 0 
−1 0 1 1 0 1
 1.1 Méthodes directes de résolution de AX = B 13
   
1 0 0 1 0 0
On a M2 =  0 1 0  , =⇒ M2−1 =  0 1 0 
0 −1 1 0 1 1
   
−1 1 2 1 0 0
Donc U = M2 M1 A =  0 2 7  et L = M1−1 M2−1 =  −3 1 0 
0 0 −5 1 1 1
Résoudre AX = B revient à résoudre LUX = B qu’on résoud en 2 étapes :
(1) LY = B donne y1 = 2; y2 = 6 + 3y1 = 12 et y3 = 4 − y1 − y2 = −10
(2) UX = Y donne x3 = −10
−5 = 2; x2 =
12−14
2 = −1 ;

x1 = −(2 − 4 + 1) = 1

1.1.5 Factorisation de Cholesky(matrice symétrique)

Définition 1.2 Une matrice A est dite symétrique si elle est égale à sa transposée, c.à.d, At = A.

Définition 1.3 Le produit scalaire canonique sur Rn est défini comme l’application

⟨., .⟩ : Rn × Rn → R
n
(u, v) 7→ ∑ ui vi
i=1
n
∑ ui vi = ⟨u, v⟩ = ⟨v, u⟩ = vt u = ut v
i=1

Définition 1.4 Une matrice A est dite définie positive, (resp. semi définie positive) si pour tout
x ∈ Rn∗ , on a ⟨Ax, x⟩ > 0, (resp. ⟨Ax, x⟩ ≥ 0).

Propriétés
- Une matrice définie positive est inversible ;
- Si A est inversible, alors At A est symétrique et définie positive ;
- Si A est définie positive, alors toutes les sous-matrices Ak d’ordre k(k ≤ n) sont définies positives.
En particulier tous les éléments diagonaux sont positifs.

Théorème 1.3 (de Cholesky)

Si A est une matrice symétrique, définie positive, il existe (au moins) une matrice réelle triangulaire
inférieure L telle que A = LL⊤ .
Si de plus on impose aux éléments diagonaux de L d’être strictement positifs, alors la factorisation
est unique.

Preuve :
Remarquons d’abord que si A est définie positive, alors toutes les sous-matrices d’ordre k sont
inversibles. Le théorème 1.2 permet d’affirmer l’existence de deux matrices L et U telles que A = LU.
Ce que nous cherchons ici c’est de factoriser en utilisant une seule matrice L.
√ √
Raisonnons par récurrence sur k. Si k = 1, A = a11 > 0 donc a11 = a11 · a11 .
14 Chapitre 1. Résolution numérique de systèmes linéaires AX = B

Supposons qu’on ait pu factoriser pour toute matrice d’ordre k − 1 c.à.d Ak−1 = Lk−1 Ltk−1 .
Soit Ak une matrice d’ordre k et posons :
 
  a1k
Ak−1 v
Ak = avec v =  ...  .
 
vt akk
ak−1k

Considérons alors la matrice Lk obtenue à partir de Lk−1 comme suit :

 
  l1k
Lk−1 0
Lk = avec l =  ... 
 
lt lkk
lk−1k

Le produit matriciel Lk Ltk donne :

Lk−1 Ltk−1 Lk−1 l

 
Lk Ltk = 2
l t Ltk−1 l t l + lkk

Par identification on obtient :

Lk−1 Ltk−1 = Ak−1 (1.1)

Lk−1 l = v (1.2)
t 2
l l + lkk = akk (1.3)

i) L’équation 1.2 permet alors de résoudre un système et d’obtenir la solution qui est
√ le vecteur l.
ii) L’équation 1.3 permet d’obtenir la dernière inconnue du problème, à savoir lkk = akk − l t l et on
peut choisir lkk > 0.

Détermination pratique de L
n n
On a A = LLt donc ai j = ∑ lip ltp j = ∑ lip l j p .
p=1 p=1
j
Comme L est triangulaire inferieure on a : ai j = ∑ lip l j p avec i ≥ j.
p=1
La 1 re colonne (
a11 = l112

ai1 = li1 l11 pour i = 2, · · · , n

 √
l11 = a11
=⇒
li1 = al11i1 pour i = 2, · · · , n

La kième colonne 
k k−1
∑ lkp = lkk2 + ∑ lkp2

 akk =



p=1 p=1
 k

 aik =


 ∑ lip lkp pour i = k + 1, · · · , n
p=1
 1.2 Méthodes itératives 15
 v
k−1
 u
u
∑ lkp2




l kk = t akk −

 p=1
=⇒ k−1
aik − ∑ lip Ikp





 p=1
lik = pour i = k + 1, · · · , n

lkk

1.2 Méthodes itératives

1.2.1 Quelques rappels sur les matrices
Soit A = (ai j )1≤i, j≤n une matrice carrée.
1. A est dite à diagonale strictement dominante en colonnes si elle vérifie :
i=n
∑ ai j < a j j , 1 ≤ j ≤ n
i=1,i̸= j

2. A est dite à diagonale strictement dominante en lignes si elle vérifie :

j=n
∑ ai j < |aii | , 1 ≤ i ≤ n
j=1, j̸=i

3. Une norme matricielle ∥.∥ vérifie les 4 propriétés suivantes :

i) ∥A∥ = 0 ⇔ A = 0
ii) ∥λ A∥ = |λ |∥A∥ pour tout λ ∈ R
iii) ∥A + B∥ ≤ ∥A∥ + ∥B∥
iv) ∥AB∥ ≤ ∥A∥∥B∥

4. (I + B) est inversible si ∥B∥ < 1 et de plus (I + B)−1 ≤ 1

1−∥B∥
5. ∥A∥∞ = max1≤i≤n ∑ j=n i=n
j=1 ai j ; ∥A∥1 = max1≤ j≤n ∑i=1 ai j
ρ(A) = max1≤ j≤n |λi (A)| est dite norme spectrale (λi (A) : valeur propore de A)

1.2.2 Méthodes classiques(Jacobi, Gauss Seidel, Relaxation)

Pour résoudre le système
Ax = b
on utilise des méthodes, dites indirectes, du type

x(k+1) = T x(k) +C (1.4)

où T est une matrice obtenue à partir de A et c un vecteur dépendant de A et b.

On écrit A sous la forme A = M − N
En supposant M inversible, on a : x = M −1 Nx + M −1 b et ceci suggère un procédé itératif du type
1.4 avec T = M −1 N et C = M −1 b.
Il ya plusieurs façons d’écrire A sous la forme A = M − N.
Dans le cadre de ce cours on se limitera aux cas les plus utilisés à partir de : A = D − L −U où
♢ D est une matrice diagonale contenant les éléments diagonaux de A,
16 Chapitre 1. Résolution numérique de systèmes linéaires AX = B

♢ L est une matrice triangulaire inférieure stricte (avec des zéros sur la diagonale) contenant
les éléments sous la diagonale de A,
♢ U est une matrice triangulaire supérieure stricte (avec des zéros sur la diagonale) contenant
les éléments au-dessus de la diagonale de A.
- Méthode de Jacobi : M = D, N = L +U.
- Méthode de Gauss-Seidel : M = D − L, N = U.
- Méthode de relaxation : A = A(ω) = M(ω) − N(ω), avec M(ω) = ω1 D − L, N(ω) = 1−ω ω D +U où
ω est un scalaire.

Définition 1.5 Une méthode de type (1.2.2) est dite convergente si pour tout x(0) initial on a :

lim x(k) = x
k→∞

Si une telle limite existe, alors elle vérifie :

x = Tx+c

Définition 1.6 On appelle erreur de la méthode (à la kieme itération) la quantité :

e(k) = x(k) − x

Avec e(0) = x(0) − x on obtient e(k) = T k e(0)

la méthode est convergente si limk→∞ T k = 0

Méthode de Jacobi :
Si A = (ai j ) la méthode de Jacobi consiste à choisir ; M = D = diag (aii ) et N = L +U = (−ai j )i,̸= j
le schéma itératif est comme suit :

x(k+1) = D−1 (L +U)x(k) + D−1 b = TJ x(k) + c

La matrice TJ = D−1 (L +U) est dite matrice de Jacobi associée à A

Si x(0) est le vecteur initial donné, l’algorithme de Jacobi est de la forme :
j=n
(k+1) 1 (k) bi
xi =− ∑ ai j x j + ; i = 1, · · · ., n
aii j=1, j̸=i aii
Explicitement, on obtient :
(k+1) (k) (k)
a11 x1 = −a12 x2 − · · · − a1n xn + b1
.. .. ..
. . .
(k+1) (k) (k)
ann xn = −an1 x1 − · · · − ann−1 xn−1 + bn

Une condition suffisante pour que la méthode de Jacobi converge est :

ρ (TJ ) < 1 ou ∥TJ ∥∞ < 1

Méthode de Gauss-Seidel :
Pour cette méthode, les matrices M et N sont données par :
1.2 Méthodes itératives 17

M = D − L (supposé inversible) et N = U où D, L et U proviennent de l’écriture A = D − L −U, le

schéma itératif est comme suit :

(D − L)x(k+1) = Ux(k) + b

ou encore
x(k+1) = (D − L)−1Ux(k) + (D − L)−1 b
en explicitant (1.2.3) on obtient :
(k+1) (k) (k)
a11 x1 = −a12 x2 − · · · − a1n xn + b1
(k+1) (k+1) (k) (k)
a22 x2 = −a21 x1 − a23 x3 − · · · − a2n xn + b2
.. .. ..
. . .
(k+1) (k+1) (k+1) (k) (k)
aii xi = −ai1 x1 · · · − aii−1 xi−1 − aii+1 xi+1 − · · · − ain xn + b2
.. .. ..
. . .
(k+1) (k+1) (k+1)
ann xn = −an1 x1 − · · · − ann−1 xn−1 + bn
ou encore (
x(0)  
(k+1) (k+1) (k)
xi = − a1ii ∑i−1 a x
j=1 i j j + ∑n
a x
j=i+1 i j j − bi , i = 1, . . . , n

La matrice TGS = (D − L)−1U est dite matrice de Gauss-Seidel associée à A

Théorème 1.4 Si A est une matrice carrée à diagonale strictement dominante en lignes alors la
méthode de Jacobi converge.

Preuve :
Si A est une matrice carrée à diagonale strictement dominante en lignes alors on a : ∑ j=n
j=1, j̸=i ai j <
j=n
1
|aii | , 1 ≤ i ≤ n(∗) ou encore :
∑ j=1, j̸=i ai j < 1, 1 ≤ i ≤ n.
|aii |  
−a
Par ailleurs TJ = D−1 (L +U) = (ti j ) avec ti j = aiii j si i ̸= j et tii = 0

j=n j=n
1
∥TJ ∥∞ = max ∑ ti j = max ∑ ai j < 1 ■
1≤i≤n j=1 1≤i≤n |aii |
j=1, j̸=i

Exercice
Montrer un résultat analogue avec preuve similaire si A est strictement dominante en colonnes.

Théorème 1.5
Si A est une matrice carrée à diagonale strictement dominante en lignes alors la méthode de
Gauss-Seidel converge

Preuve :
on montre que ∥TGS ∥∞ = (D − L)−1U ∞
< 1 en passant par :

∥T x∥∞
∥T ∥∞ = max
x̸=0 ∥x∥∞
18 Chapitre 1. Résolution numérique de systèmes linéaires AX = B

On pose y = T x = (D − L)−1Ux
qui donne (D − L)y = Ux et Dy = Ly +Ux ou encore y = D−1 Ly + D−1Ux
Soit k l’indice tel que |yk | = max |yi | = ∥y∥∞ = ∥T x∥∞
1≤i≤n
j=k−1 j=n
D−1 L D−1U



On a yk = ∑ y +
kj j ∑ x
kj j
j=1 j=k+1
j=k−1 j=n
ak j ak j
d’où |yk | ≤ ∑ ∥y∥∞ + ∑ ∥x∥∞
j=1 |akk | j=k+1 |akk |
!
j=k−1 j=n
ak j ∥y∥∞ ak j
et : 1− ∑ ∥x∥ ≤ ∑
j=1 |akk | j=k+1 |akk |
∞

j=n
ak j
∑
∥y∥∞ j=k+1 |akk |
soit enfin : ∥x∥∞ ≤ 
j=k−1
 <1 ■
ak j 
1−

∑ |akk |

j=1

Méthode de relaxation
Si on considère des matrices M et N dépendantes d’un paramètre ω on obtient :
A = M(ω) − N(ω)
1 1−ω
avec M(ω) = D − L et N(ω) = D +U
ω ω

 −1    −1
1 1−ω 1
T (ω) = D−L D +U et c(ω) = D−L b
ω ω ω

−1
T (ω) = I − ωD−1 L (1 − ω)I + ωD−1U

R - Si ω = 1, on retrouve la méthode de Gauss-Seidel.

- Si ω > 1, on parle de sur-relaxation.
- Si ω < 1, on parle de sous-relaxation.

Théorème 1.6
Condition nécessaire de convergence de la méthode de relaxation : 0 < ω < 2

Preuve :  −1  
1 1−ω
T (ω) = D−L D +U
ω ω
Si les valeurs propres de T (ω) sont notées λi (ω) on a :
1−w
n


det ω D +U
det(T (ω)) = ∏ λi (ω) = = (1 − ω)n .
det ω1 D − L


i=1

D’où ρ (Tω ) ≥ [|1 − ω|n ]1/n = |1 − ω|.

Pour que la méthode converge, il est nécessaire d’avoir ρ(T (ω)) < 1 et par conséquent |1 − ω| < 1
d’où ω ∈]0, 2[. ■
 2. Résolution de l’équation f (x) = 0

2.1 Rappels et notations

Définition 2.1
Soit k un réel strictement positif et g une fonction définie sur un intervalle [a, b] de R à valeurs
dans R. La fonction g est dite Lipschitzienne de rapport de k (encore dite k - Lipschitzienne) si
pour tous x et y de [a, b] on a : |g(x) − g(y)| ≤ k|x − y|.

Définition 2.2
Soit g une fonction k-Lipschitzienne sur [a, b]. La fonction g est dite contractante de rapport de
contraction k si k ∈]0, 1[.

■ Exemple 2.1 La fonction g(x) = sin(x) est Lipschitzienne de rappport k = 1 ■

Exercice
Montrer que la La fonction g(x) = 31 cos(x) est Lipschitzienne et déterminer le rappport k.
Définition 2.3 Soit g une fonction définie sur un intervalle [a, b] de R à valeurs dans R la fonction
g est dite uniformément continue sur [a, b] si : ∀ε ≥ 0, ∃η tel que ∀x et y de [a, b] vérifiant
|y − x| ≤ η, on ait |g(y) − g(x)| ≤ ε

R Toute fonction Lipschitzienne sur [a, b] est unfiormément continue sur [a, b].

Théorème 2.1 (des Valeurs Intermédiaires)

Soit f une fonction définie et continue sur un intervalle fermé borné [a, b] de R. Alors pour
tout réel θ appartenant à f ([a, b]), il existe un réel c ∈ [a, b] tel que θ = f (c). Si de plus f est
strictement monotone alors le point c est unique.
20 Chapitre 2. Résolution de l’équation f (x) = 0

Théorème 2.2 (des Valeurs Intermédiaires cas particulier θ = 0 ).

Soit f une fonction définie et continue sur un intervalle [a, b] et vérifiant f (a) × f (b) ≤ 0, alors il
existe un réel c ∈ [a, b] tel que f (c) = 0.
Si de plus f est strictement monotone alors le point c est unique.

Théorème 2.3 (de Rolle)

Soit f une fonction définie sur [a, b] et à valeurs dans R. Si f est continue sur [a, b], dérivable sur
]a, b[ et vérifie f (a) = f (b), alors il existe un réel c ∈]a, b [ tel que : f ′ (c) = 0

Théorème 2.4 (des Accroissements Finis)

Soit f une fonction définie sur [a, b] et à valeurs dans R Si f est continue sur [a, b] et dérivable sur
]a, b[, alors il existe un réel c ∈]a, b[ tel que :

f (b) − f (a) = (b − a) × f ′ (c)

Théorème 2.5 (Formule de Taylor)

Soit f une fonction de classe Cn sur [a, b] dont la dérivée f (n+1) est définie sur ]a, b[, alors il existe
un réel c ∈]a, b[ tel que :

1 1
f (b) = f (a) + (b − a) f ′ (a) + . . . (b − a)n f (n) (a) + (b − a)n+1 f (n+1) (c)
n! (n + 1)!

Théorème 2.6 (Formule de MacLaurin)

Soit f une fonction de classe Cn sur un intervalle I contenant 0 et telle que f (n) soit dérivable à
l’intrérieur de I. Alors ∀x ∈ I, il existe un réel c strictement compris entre 0 et x tel que :
1 2 ′′ 1 1
f (x) = f (0) + x f (1) (0) + x f (0) + . . . xn f (n) (0) + xn+1 f (n+1) (c).
2! n! (n + 1)!

Définition 2.4
Soit θ un réel et f une fonction définie sur un intervalle I de R et à valeurs dans R. θ est dit zéro
de f si f (θ ) = 0

Définition 2.5
Soit θ un réel et g une fonction définie sur un intervalle I de R et à valeurs dans R.
θ est dit point fixe de g si g(θ ) = θ .

Lemme 2.7
Soit I un intervalle de R et f une fonction définie sur I et à valeurs dans R. Alors la recherche
des zéros de f est équivalente à la recherche des points fixes de la fonction g définie sur I par :
g(x) = x − f (x)
Preuve :
En effet, si f (θ ) = 0 alors g(θ ) = θ − f (θ ) = θ et inversement, si g(θ ) = θ alors f (θ ) = θ −g(θ ) =
θ − θ = 0. ■
 2.2 Méthode du point fixe 21

Lemme 2.8
Soit g une fonction de classe C1 sur [a, b]. S’il existe un réel k ≥ 0 tel que : |g′ (x)| ≤ k ∀x ∈ [a, b]
alors la fonction g est k − Lipschitzienne sur [a, b].
Preuve :
Il suffit d’appliquer le théorème des accroissements finis à la fonction g sur [x, y] avec x ≤ y. Donc
il existe c ∈]x, y [ tel que : g(y) − g(x) = (y − x)g′ (c) et comme on a : |g′ (c)| ≤ k, il s’ensuit que :
|g(y) − g(x)| ≤ k|x − y| ■
Définition 2.6
Soit (un ) une suite admettant pour limite θ . On appelle erreur de la nème étape le réel défini par
en = un − θ

Définition 2.7
On dit que la convergence de (un ) vers θ est d’order p si :
|en+1 |
lim p = C où p et C sont des réels > 0
n→∞ |en |
Si p = 1 (avec C < 1) la convergence est dite linéaire
Si p = 2 on dit que la convergence est quadratique.

R L’ordre de convergence p n’est pas nécessairement un entier.

Définition 2.8 On dira que le réel δ est une approximation du réel α avec la precision ε si :

|α − δ | ≤ ε

En particulier, on dira que le terme un0 d’une suite (un ) approche la limite θ avec précision ε si
|un0 − θ | ≤ ε.
1


■ Exemple 2.2 la suite (un ) =
n tend vers zéro quand n tend vers l’infini. Si on veut une précision
ε = 10−1 , il suffit de prendre n0 tel que n10 ≤ 10−1 ou encore n0 ≥ 10 mais si on exige une precision
de 10−5 alors on doit prendre n0 tel que n10 ≤ 10−5 c.a.d n0 ≥ 105 ■

R
   
Il est important de saisir la notion de vitesse de convergence. Par exemple, les suites 1n , n12 , n14
convergent vers zéro quand n tend vers l’infini mais la vitesse de convergence diffère d’une
suite à l’autre.

2.2 Méthode du point fixe

Pour résoudre l’équation f (x) = 0 on pose x = g(x)
L’équation x = g(x) est utilisée pour construire une suite (un schéma itératif ) (xn )n∈N définie par
récurrence comme suit : 
x0 donné
xn+1 = g (xn ) ∀n ∈ N
Si (xn ) converge vers θ et si g est continue, on aura nécessairement θ = g(θ ) c.à.d θ est point fixe
de g et donc solution de l’équation f (x) = 0.
22 Chapitre 2. Résolution de l’équation f (x) = 0

Théorème 2.9 Soit g une fonction k-contractante sur [a, b] et à valeurs dans [a, b], et (un ) la suite
récurrente définie par : u0 ∈ [a, b], u0 donné et un+1 = g (un ) pour tout n ≥ 0
Alors :
1- la suite ( un ) converge vers un réel θ
2- la fonction g admet un point fixe unique
kn
3- Pour tout n ∈ N∗ on a : |un − θ | ≤ 1−k |u1 − u0 |

Preuve :
Tout d’abord, comme u0 ∈ [a, b] et que g : [a, b] → [a, b], on a un ∈ [a, b] pour tout n ∈ N. Ensuite, le
fait que g soit une fonction k-contractante implique que :

|un+1 − un | = |g (un ) − g (un−1 )| ≤ k |un − un−1 | pour tout n ≥ 1.

Par conséquent on obtient :

|un+1 − un | ≤ kn |u1 − u0 | pour tout n ≥ 0

A l’aide de cette inégalité on montre que la suite (un ) vérifie :

1 n
|un+p − un | ≤ k |u1 − u0 |
1−k
En effet : Pour tous p ∈ N∗ et n ∈ N on a :

|un+p − un | ≤ |un+p − un+p−1 | + |un+p−1 − un+p−2 | + . . . |un+2 − un+1 | + |un+1 − un |

≤ kn+p−1 |u1 − u0 | + kn+p−2 |u1 − u0 | .. + kn+1 |u1 − u0 | + kn |u1 − u0 |
1 − kp n
≤ k |u1 − u0 |
1−k
1 n
≤ k |u1 − u0 |
1−k
Cette inégalité nous permet de prouver que la suite (un ) est de Cauchy. En effet : Comme kn −−−−→ 0
n−→+∞
1−k
alors pour tout ε > 0, il existe n0 tel que pour tout n ≥ n0 on ait : kn ≤ |u1 −u0 | ε et par suite :
1 n
1−k k |u1 − u0 | ≤ ε Donc pour tout ε > 0, il existe n0 tel que pour tout n ≥ n0 on ait :

1−k
|un+p − un | ≤ kn ≤ε
|u1 − u0 |
La suite ( un ) est donc de Cauchy et par conséquent elle converge vers une limite θ . Comme la
fonction g est continue sur [a, b], que un+1 = g (un ) et que

un ∈ [a, b]∀n ∈ N

alors on a : limn→∞ un = θ = g(θ ) c-a-d : θ est un point fixe de g

Unicité du point fixe :
Supposons que g admet un autre point fixe α different de θ alors on a : |g(α) − g(θ )| = |α − θ | ≤
k|α − θ | ou encore (1 − k)|α − θ | ≤ 0 mais comme k < 1, alors α = θ Enfin, en faisant tendre p
kn
vers l’infini dans l’inégalité |un+p − un | ≤ 1−k |u1 − u0 |, on obtient :

kn
|θ − un | ≤ |u1 − u0 | ∀n ∈ N∗ ■
1−k
2.2 Méthode du point fixe 23

Théorème 2.10 (condition de convergence locale)

Soit g une fonction de classe C1 au voisinage θ . Si g(θ ) = θ et |g′ (θ )| < 1, alors il existe ε
strictement positif tel que : ∀u0 ∈ Iε = [θ − ε, θ + ε], la suite (un ) = (g (un−1 )) est définie et
converge vers θ , l’unique solution de g(x) = x dans Iε

Preuve :
l’objectif est de montrer qu’il existe un intervalle Iε = [θ − ε, θ + ε] tel que pour tout u0 ∈ Iε , la
suite un = g (un−1 ) est définie et converge vers θ , qui est l’unique solution de g(x) = x dans Iε .

Puisque g est de classe C1 au voisinage de θ , la dérivée g′ est continue en θ .

Par conséquent, pour tout η > 0, il existe ε > 0 tel que pour tout x ∈ Iε = [θ − ε, θ + ε], on a :

g′ (x) − g′ (θ ) < η
1−|g′ (θ )|
Choisissons η = 2 . Alors, pour tout x ∈ Iε , on a :

1 − |g′ (θ )| 1 + |g′ (θ )|
g′ (x) ≤ g′ (θ ) + η < g′ (θ ) + = <1
2 2
Ainsi, |g′ (x)| < 1 pour tout x ∈ Iε .

D’après l’inégalité des accroissements finis, pour tout x, y ∈ Iε , il existe c entre x et y tel que :

|g(x) − g(y)| = g′ (c) · |x − y|

Puisque |g′ (c)| < 1 pour tout c ∈ Iε , on a :

|g(x) − g(y)| ≤ k|x − y|

1+|g′ (θ )|
où k = 2 < 1. Ainsi, g est une contraction sur Iε .

Montrons que g envoie Iε dans Iε . Pour tout x ∈ Iε , on a :

|g(x) − θ | = |g(x) − g(θ )| ≤ k|x − θ | ≤ kε < ε

Donc, g(x) ∈ Iε , et g est stable sur Iε . Par application du théoreme 2.9 on trouve le resultat.

R
- Si |g′ (θ )| = 1, la suite peut converger ou diverger
- Si |g′ (θ )| ≥ 1 et si la suite possède une infinité de termes différents de θ , alors la suite ne
peut converger.
En effet, si on suppose que la suite converge vers θ on obtient :
un+1 − θ = (un − θ ) g′ (cn ) avec cn compris entre un et θ et de là on aboutit à une contradiction
en supposant que un est assez proche de θ de telle sorte que :

g′ (cn ) ≥ 1 =⇒ |un+1 − θ | ≥ |un − θ |

Théorème 2.11 Si la suite récurrente définie par : u0 ∈ [a, b], u0 donné et un+1 = g (un ) , ∀n ≥ 0,
converge linéairement vers θ et si g est de classe C1 sur [a, b], alors C = limn→∞ |e|en+1
n|
|
= |g′ (θ )|.
 24 Chapitre 2. Résolution de l’équation f (x) = 0

Preuve :
Il suffit d’appliquer le théorème des accroissements finis : |en+1 | = |un+1 − θ | = |g (un ) − g(θ )| =
|(un − θ ) g′ (cn )| et de là on obtient
|en+1 |
lim = lim g′ (cn ) = g′ (θ )
n→∞ |en | n→∞

R On veut résoudre numériquement l’équation f (x) = 0. On constate qu’il existe plusieurs façon
d’écrire cette équation sous la forme d’un problème de point fixe c’est-à-dire sous la forme
g(x) = x. Par exemple on à les trois écritures suivantes :

x2 − 2x − 3 =0
=⇒ x2 = 2x + 3
√
=⇒ g1 (x) = ± 2x + 3

x2 − 2x − 3 = 0 =⇒ 2x = x2 − 3
x2 − 3
=⇒ x = g2 (x) =
2
2 2
x − 2x − 3 = 0 =⇒ x = 2x + 3
2x + 3
=⇒ x = g3 (x) =
x
Les trois équations admettent pour points fixes -1 et 3 . Pour la convergence locale ou globale
il faut étudier |g′i (x)| , |g′i (−1)| et |g′i (3)| i = 1, 2, 3

2.3 Méthode de Newton

En prenant la fonction g définie par : g(x) = x − ff′(x)
(x) ,
on obtient le procédé de Newton donné par :
x0 donné , xn+1 = xn − ff′(x n) ′
(xn ) pour n ≥ 0 avec f (xn ) ̸= 0.

L’idée consiste à remplacer la fonction f par la droite tangente à sa courbe aux point (xi , f (xi )) ,
l’intersection de cette droite avec l’axe (ox) détermine le point xi+1 .

Théorème 2.12 Soit f ∈ C 2 ([a, b]) satisfaisant les conditions suivantes :

1. f (a) × f (b) < 0
2. ∀x ∈]a, b [, f ′ (x) ̸= 0
3. f ′′ est de singe constant sur [a, b] (convexité ou concavité)
Alors la méthode de Newton converge vers l’unique solution θ de f (x) = 0 dans [a, b] et ceci pour
n’importe quel choix de x0 ∈ [a, b].

Preuve :
Considérons le cas f (a) · f (b) < 0, f ′ (x) < 0 et f ′′ (x) < 0 D’après i) et ii), il existe une solution
θ ∈ [a, b] tel que f (θ ) D’autre part
f (θ ) − f (xn ) 1 ′′
2 f (c)
xn+1 − θ = xn − θ + = (xn − θ ) avec xn ≤ c ≤ θ
f ′ (xn ) 2 f ′ (xn )
2.3 Méthode de Newton 25

Par conséquent, le signe de xn+1 − θ est celui de f ′′ (c) f ′ (xn ). Si f ′ (x) < 0 et f ′′ (x) < 0 alors
xn+1 ≥ θ pour tout n ≥ 0, (xn ) est donc minorée par θ à partir de x1 Pour montrer que la suite (xn )
est décroissante, on distingue deux cas :
(1) Si x0 > θ
Comme f ′ (x) < 0 =⇒ f est décroissante sur [a, b] =⇒ f (x) ≥ 0 ∀x ∈ [a, θ ] et f (x) ≤ 0 ∀x ∈
[θ , b] car f (a). f (b) < 0
Donc f (x0 ) ≤ 0 =⇒ ff′(x 0) f (x0 )
(x0 ) ≥ 0 =⇒ x1 = x0 − f ′ (x0 ) ≤ x0
=⇒ θ ≤ x1 ≤ x0
Par récurrence on montre que xn+1 ≤ xn pour tout n ≥ 0

(2) Si x0 < θ
Comme f ′ (x) < 0 =⇒ f est décroissante sur [a, b] =⇒ f (x) ≥ 0 ∀x ∈ [a, θ ] et f (x) ≤ 0 ∀x ∈
[θ , b] car f (a). f (b) < 0 Donc f (x0 ) ≥ 0 =⇒ ff′(x 0) f (x0 )
(x0 ) ≤ 0 =⇒ x1 = x0 − f ′ (x0 ) ≥ x0 Or xn+1 ≥ θ ∀n ≥
0 =⇒ x1 ≥ θ Donc f (x1 ) ≤ 0 =⇒ ff′(x 1) f (x1 )
(x1 ) ≥ 0 =⇒ x2 = x1 − f ′ (x1 ) ≤ x1 =⇒ θ ≤ x2 ≤ x1 Par récurrence
on montre que xn+1 ≤ xn pour tout n ≥ 1
Donc xn est une suite décroissante et minorée =⇒ xn est convergente vers l’unique solution θ de
f (x) = 0 dans [a, b] ■

Calcul de l’ordre de la méthode de Newton

Des développements limités de f et f ′ au point de θ donnent :
e2k ′′ e2
f (xk ) = f (θ ) + ek f ′ (θ ) + f (θ ) + ε1 (ek )e2k = ek f ′ (θ ) + k f ′′ (θ ) + ε1 (ek )e2k (car f (θ ) = 0)
2 2
f ′ (xk ) = f ′ (θ ) + ek f ′′ (θ ) + ε2 (ek )ek
f (xk ) f (xk )
et comme xk+1 = xk − f ′ (xk ) alors : ek+1 = ek − f ′ (xk ) ce qui donne :
1 ′′
ek+1 2 f (θ ) + ε1 (ek ) − ε2 (ek )
=
2
ek f (θ ) + ek f ′′ (θ ) + ε2 (ek )ek
′

ek+1 f ′′ (θ )
Par passage à la limite on trouve : lim = .
k→+∞ e2
k 2 f ′ (θ )
La méthode de Newton a donc, une convergence d’ordre 2 ou de convergence quadratique.
 26 Chapitre 2. Résolution de l’équation f (x) = 0

■ Exemple 2.3 On se propose de calculer une racine de la fonction f (x) = x2 − 4 dans l’intervalle [
0,52].
f est continue sur [0, 52] et on a f (0) = −4 et f (52) = 2700
Nous allons utiliser la méthode de Newton pour calculer une estimation de cette racine avec x0 = 52
k xk−1 f (xk−1 ) xk f (xk ) err k
1 52 2700 26 674 26
2 26 674.0015 13.0960 167.5063 12.9424
3 13.0960 167.5063 6.7007 40.8999 6.3953
4 6.7007 40.8999 3.6488 9.3141 3.0519
5 3.6488 9.3141 2.3725 1.6289 1.2763
6 2.3725 1.6289 2.0292 0.1178 0.3433
7 2.0292 0.1178 2.0002 0.0008 0.0290
■

2.4 Méthode de Newton modifiée

(x)
En prenant la fonction g définie par : g(x) = x − f f′ (x 0)
, f ′ (x0 ) ̸= 0
on obtient la méthode de Newton modifiée comme suit :
x0 donné , xn+1 = xn − ff′(x n)
(x0 ) pour n ≥ 0.
On montre (en utilisant des memes démarches que la méthode de Newton) alors que cette méthode
est d’ordre 1.
Cette méthode est un cas particuliers de la méthode de la corde donnée par :
f (xn )
xn+1 = xn − .
q

2.5 Méthode de dichotomie

Soit une fonction f fonction définie continue sur [a, b] vérifiant f (a) f (b) ≤ 0.
La fonction f admet donc au moins un zéro θ ∈ [a, b].
La méthode de dichotomie consiste à approcher θ par encadrement, en réduisant à chaque étape la
longueur de l’intervalle de moitié selon l’algorithme suivant :
Etape 1
On pose a0 = a et b0 = b on pose c0 = a0 +b 2
0
puis on teste si c0 = θ c’est terminé, sinon :
Si f (a0 ) f (c0 ) < 0 alors θ ∈ [a0 , c0 ] on pose alors a1 = a0 et b1 = c0 puis c1 = a1 +b
2
1

Si f (b0 ) f (c0 ) < 0 alors θ ∈ [c0 , b0 ] on pose alors a1 = c0 et b1 = b0 puis c1 = a1 +b

2
1

b0 −a0
Aprés cette étape la longueur de [a1 , b1 ] est égale à 2 = b−a 2
Etape 2
on recommence le procédé de l’étape 1 .
Etape k
A chaque étape k du procédé, soit on tombe sur un ck = θ soit on diminue la longueur de l’intervalle
de moitié.
Théorème 2.13 Les ak , bk et ck satisfont les propriétés suivantes :
(1) [ak+1 , bk+1 ] ⊂ [ak , bk ]
2.5 Méthode de dichotomie 27

(2) bk+1 − ak+1 = bk −a

2
k −a0
= b20k+1
(3) La suite (ck ) converge vers θ
(9) |ck − θ | ≤ 2b−a
k+1

Preuve :
1)- Pour k ≥ 0 on a ck = ak +b 2
k
et [ak+1 , bk+1 ] = [ak , ck ] ou [ak+1 , bk+1 ] = [ck , bk ] .
Donc [ak+1 , bk+1 ] ⊂ [ak , bk ]
2)- On a par construction bk+1 − ak+1 = bk −a 2 , montrons par récurrence que : bk − ak =
k b−a
2k
Pour k = 0 la relation est vérifiée
Si on suppose que la relation est vraie à l’ordre k bk − ak = b−a


2k
alors on a :

1 1 b−a b−a
bk+1 − ak+1 = (bk − ak ) = = k+1
2 2 2k 2

3)- Par construction θ ∈ [ak , bk ] et ck = ak +b

2
k
est le milieu de [ak , bk ]
bk −ak b−a
Donc |ck − θ | ≤ 2 ≤ 2k+1
En d’autres termes, on a : θ − 2b−a b−a
k+1 ≤ ck ≤ θ + 2k+1

et comme 2b−a
k+1 −−−−→ 0 on déduit que limk→∞ ck = θ ■
n−→+∞

R Le théorème précédent permet de calculer à l’avance le nombre minimal n ∈ N d’itérations

assurant la précision ε, en effet Pour que cn vérifie |cn − θ | ≤ 2b−a
n+1 à la n
ième itération, il suffit
b−a
que n vérifie : 2n+1 ≤ ε
On a alors :
b−a
|cn − θ | ≤ n+1 ≤ ε
2
Donc
b−a b−a
≤ ε ⇐⇒ ≤ 2n+1
2n+1 ε 
b−a
⇐⇒ log ≤ (n + 1) log(2)
ε
log(b − a) − log(ε)
⇐⇒ −1 ≤ n
log(2)

À chaque itération, l’intervalle [an , bn ] est divisé par 2.

Ainsi, |en+1 | ≈ 21 |en | → Convergence linéaire (p = 1) avec un taux C = 12 .
■ Exemple 2.4 On se propose de calculer une racine de la fonction f (x) = x2 − 4 dans l’intervalle
[0, 3].
f est continue sur [0, 3] et on a f (0) = −4 et f (3) = 5
Donc f (0) × f (3) < 0 et d’après le théorème des valeurs intermédiaires, f possède une racine sur
[0, 3].
Nous allons utiliser la méthode de dichotomie pour calculer une estimation de cette racine.
Le tableau d’itérations suivant récapitule les étapes de résolution de l’équation f(x) = 0 par la
méthode de dichotomie. La précision demandée est = 10−3 .

■
 28 Chapitre 2. Résolution de l’équation f (x) = 0
!

TABLE 2.1 – Méthode de dichotomie pour f (x) = x2 − 4 sur [0, 3] (précision 10−3 )
k ak f (ak ) bk f (bk ) ck f (ck ) errk
0 0.0000 -4.0000 3.0000 5.0000 1.5000 -1.7500 3.0000
1 1.5000 -1.7500 3.0000 5.0000 2.2500 1.0625 1.5000
2 1.5000 -1.7500 2.2500 1.0625 1.8750 -0.4844 0.7500
3 1.8750 -0.4844 2.2500 1.0625 2.0625 0.2539 0.3750
4 1.8750 -0.4844 2.0625 0.2539 1.9688 -0.1230 0.1875
5 1.9688 -0.1230 2.0625 0.2539 2.0156 0.0627 0.0938
6 1.9688 -0.1230 2.0156 0.0627 1.9922 -0.0311 0.0469
7 1.9922 -0.0311 2.0156 0.0627 2.0039 0.0157 0.0234
8 1.9922 -0.0311 2.0039 0.0157 1.9980 -0.0078 0.0059
9 1.9980 -0.0078 2.0039 0.0157 2.0010 0.0039 0.0029

2.6 Méthode de la sécante

Bien que la méthode de Newton est très utilisée dans la pratique, son principal inconvénient
vient du fait de l’utilisation à chaque itération de la dérivée.
Quand la fonction f n’est pas définie explicitement, on n’a pas toujours accès à sa dérivée.
C’est pourquoi nous allons voir maintenant la méthode de la sécante qui n’utilise pas la dérivée de f .
Connaissant xk−1 et xk alors on définie xk+1 comme étant le point d’intersection de l’axe des abscisses
avec la droite passant par (xk−1 , f (xk−1 )) et (xk , f (xk )).
L’équation de cette droite est donnéée par :

y − f (xk ) x − xk
= .
f (xk ) − f (xk−1 ) xk − xk−1

Ainsi y = 0 implique que

xk − xk−1
xk+1 = xk − f (xk ) , ∀k ≥ 0.
f (xk ) − f (xk−1 )

L’algorithme ne peut démarrer que si on dispose de deux valeurs x0 , x1 proches, si possible, de la

solution recherchée de x. (
x0 , x1 données ;
−xk−1
xk+1 = xk − f (xxk k)− f (xk−1 ) f (xk )
√
Si f est deux fois dérivable, f ′ (θ ) ̸= 0,la méthode de la sécante a un ordre de convergence = 1+ 5
2 ≃
1.618. En d’autres termes, on a

|xn+1 − θ | < C |xn − θ |1.618 .

En effet : On a
f (xn ) (xn − xn−1 ) f (xn ) (en − en−1 )
xn+1 = xn − ⇔ en+1 = en − ,
f (xn ) − f (xn−1 ) f (xn ) − f (xn−1 )

f (xn ) = f (xn − θ + θ ) = f (en + θ ) .

 2.7 Méthode de fausse position ( Regula Falsi) 29

La formule de Taylor en θ s’écrit :

f ′′ (θ ) 2
f (θ + δ ) = f (θ ) + f ′ (θ ) δ + δ +...
2
On remplace δ , par en et en−1 et on remplace dans la secante. Il s’en suit :

f ′′ (θ ) en en−1
en+1 ≃
2 f ′ (θ )

On cherche p (l’ordre de convergence) tel que

en+1 ≃ Cenp
Un calcul simple montre que p est la solution positive de :
√
2 1+ 5
p − p−1 = 0 ⇒ p = (le nombre d’or)
2
De 1 < p < 2, on déduit que la convergence n’est pas linéaire et elle a’est pas quadratique. On
parle de convergence superlinéaire

2.7 Méthode de fausse position ( Regula Falsi)

Au lieu de prendre à chaque étape ck qui est le milieu de l’intervalle [ ak , bk ], la méthode
de fausse position prend le point d’intersection de l’axe des abscisses avec la droite passant par
(ak , f (ak )) et (bk , f (bk )). L’équation de cette droite est donnée par :

x−a y − f (a)
=
b−a f (b) − f (a)
Elle coupe l’axe des abscisses au point : Mk (ck , 0) où :

ak − bk
ck = ak − f (ak )
f (ak ) − f (bk )
En suite on procède comme dans le cas de dichotomie en testant : Si f (ak ) f (ck ) < 0 alors
θ ∈ [ak , ck ] on pose alors ak+1 = ak et bk+1 = ck Si f (bk ) f (ck ) < 0 alors θ ∈ [ck , bk ] on pose
alors ak+1 = ck et bk+1 = bk puis on cherche à nouveau la droite passanrt par (ak+1 , f (ak+1 )) et
(bk+1 , f (bk+1 ))