T. Moulahi & I.

Mahfoudhi 1

Le contenu du cours :
 Rappel sur les éléments de l’analyse matricielle

 Résolution du système linéaire

 Zéros d’une fonction non linéaire.

 Approximation polynomiale

 Quelques exercices corrigés.

Chapitre 1

Eléments d’analyse matricielle

1.1 Valeurs propres et vecteurs propres

Soient n ∈ N∗ et Mn (R) L’ensemble des matrices carrées de dimension n.
Définition 1.1.1 On appelle valeur propre de A tout réel λ tel qu’il existe au moins un
vecteur non nul u vérifiant Au = λu.
Définition 1.1.2 On appelle vecteur propre de A tout vecteur non nul u tel qu’il existe
un réel λ vérifiant : Au = λu.
On dit que u est un vecteur propre de A associé à la valeur propre λ
Exemple 1.1.3 Soient
   
2 −1 1 2
A=  0 1 1  et X =  1 
1 0 0 1
   
4 2
On a AX =  2  = 2  1  = 2X. Dans ce cas, X est un vecteur propre de A associé
2 1
à la valeur propre λ = 2.
Définition 1.1.4 Lorsque λ est une valeur propre de A, on appelle sous espace propre de
A associé à λ l’ensemble : Eλ = {u ∈ E; Au = λu} est un s.e.v de E.
De plus, Eλ = ker{A − λI)u = 0} où Id est l’identité

1.2 Polynôme caractéristique

Définition 1.2.1 On appelle polynôme caractéristique de la matrice A, le polynôme PA
de degré n définit par PA (λ) = det(A − λI). et sont équation caractéristique s’ecrit sous
cette forme :
PA (λ) = 0

2
T. Moulahi & I. Mahfoudhi 3

Remarque 1.2.2 Les racines réelles du polynôme caractéristique étant les valeurs propres
de A. En général, on cherchera à déterminer une factorisation du polynôme PA pour avoir
les valeurs propres explicites.
 
1 −1 −1
Exemple 1.2.3 Déterminer les valeurs propres de A =  −1 1 1 
   −1 1 3 
1 − λ −1 −1  −λ −λ 0 
 

PA (λ) = det(A − λI) =  −1 1 − λ 1  =L1 ←L1 +L2  0 −λ −2 + λ
  −1

 1 3 − λ L2 ←L2 −L3  −1 1 3−λ 
−1 −1 0   0 −1 0 
  

= λ  0 −λ −2 + λ = λ  λ −λ −2 + λ C1 ← C1 − C2
  
−1 1 3−λ  −2 1 3−λ 
 
 0 −1 0   
  λ −2 + λ
PA (λ) = λ  λ −λ −2 + λ = λ 
    = λ(−λ2 + 5λ − 4)
−2 1 −2 3 − λ 
3−λ 
Les valeurs propres de A sont λ = 0, λ = 1 et λ = 4

Remarque 1.2.4 ∗ Si 0 est une valeur propre alors la matrice n’est pas inversible
∗ Le nombre des valeurs propres de A ∈ Mn (R) est au plus égal à n

Définition 1.2.5 On dit que λ est une valeur propre d’ordre de multiplicité nλ lorsque λ
est une racine d’ordre de multiplicité nλ dans PA .
 
1 −1 3
Exemple 1.2.6 Soit A =  0 4 0  PA (λ) = −(2 + λ)(4 − λ)2
3 2 1
Les valeurs propres de A sont λ = −2 d’ordre de multiplicité 1 et λ = 4 d’ordre de
multiplicité 2

Proposition 1.2.7 (valeurs propres de l’inverse d’une matrice)

Pour toute matrice A ∈ Mn (C) inversible on a :
λ ∈ λ(A)\{0} ⇐⇒ λ−1 ∈ λ(A−1 )

Définition 1.2.8 (Matrice positive) Une matrice A ∈ Mn (R) est dite positive si pour tout
X ∈ Rn et X 6= 0, on a
< AX, X >≥ 0 ⇐⇒ les valeurs propres sont positives

Définition 1.2.9 (Matrice définie positive) Une matrice A ∈ Mn (R) est dite définie positive
si pour tout X ∈ Rn et X 6= 0, on a
< AX, X >> 0 ⇐⇒ les valeurs propres sont strictement positives

Proposition 1.2.10 (valeurs propres d’une matrice triangulaire) Les valeurs propres
d’une matrice triangulaire (Inf. ou Sup.) sont ses éléments diagonaux :
4 Analyse Numerique

1.3 Diagonalisation
Définition 1.3.1 Une matrice est diagonalisable si elle est semblable à une matrice diagonale
Si A est diagonalisable, on a A = P DP −1 où D est une matrice diagonale et P est la matrice
de passage de la base initiale à une base formée par les vecteurs propres.

Exercice
 1.3.2 SoitA la matrice d’un endomorphisme f de R3 dans la base canonique
2 −1 2
A= 0 1 0 
3 1 −3
On donne les vecteurs u(1, 5, 2) ; v(1, 0, −3) et w(2, 0, 1)

1) Vérifier que B 0 = (u, v, w) est une base de R3

2) Trouver la matrice D de f dans la base B 0 .

Proposition 1.3.3 Si dim E = n et si A admet n valeurs propres distinctes alors f est diago-
nalisable

Théorème 1.3.4 . Soit A ∈ Mn (R), alors nous avons :

• A est diagonalisable si et seulement si il existe une base de E formée de vecteurs propres
de A
• A est diagonalisable si et seulement si la somme des dimensions des sous espaces propres
associées aux différentes valeurs propres de A est égale à la dimension de E

Proposition 1.3.5 A est diagonalisable si et seulement si la dimension du sous espace propre

associé à chacune des valeurs propres λi est égale à l’ordre de multiplicité de λi .

1.4 Pratique de la diagonalisation

Etape 1 Calculer PA puis factoriser
PA (λ) = det(A − λI)
Etape 2 Déterminer les valeurs propres λi
Si PA contient un facteur du second degré sans racines réelles alors A n’est pas diagona-
lisable
Etape 3 Déterminer chaque sous espace propre Eλi = ker(A − λi In )
dim Eλi = n − dim Im(A − λi In ) = n − rang(A − λi In )
Etape 4 Conclure
Si pour tout λi on a : dim Eλi = mi (mi étant l’ordre de multiplicité de λi ) alors A
est diagonalisable. Alors, on obtient une base de E formée de vecteurs propres de f en
réunissant les bases des Eλi .
 
0 1 1
Exemple 1.4.1 Trouver une matrice diagonale semblable à A =  1 0 1 
1 1 0
T. Moulahi & I. Mahfoudhi 5

Réponce
1) Le polynôme caractéristique
   
−λ 1 1  −λ − 1 1 + λ 0 
   
PA (λ) = det(A − λI) =  1 −λ 1  =L1 ←L1 −L2  0
   −λ − 1 1 + λ
 1 1 −λ L2 ←L2 −L3  1 1 −λ 
   
−1 1 0  −1 1 0 
2
 2

= (1 + λ)  0 −1 1  = (1 + λ)  0 −1 1  L3 ← L3 + L1
1 1 −λ 0 2 −λ
 
−1 1 
PA (λ) = −(1 + λ)2   = (2 − λ)(1 + λ)2
2 −λ
Les valeurs propres de A sont λ = 2 d’ordre de multiplicité 1 et λ = −1 d’ordre de
multiplicité 2.
2) Calculons la dimension du sous espace propre associé à λ = −1
 
1 1 1
rg(A + I3 ) = rg  1 1 1  = 1 signifie dim ker(A + I3 ) = 2
1 1 1

Donc A est diagonalisable.

3) Cherchons une base de vecteurs propres :
Soit E−1 = {u ∈ R3 ; (A + I3 )u = 0} le sous espace propre associé à la valeur propre
λ = −1
On aura x + y + z = 0 ⇔ x = −y − z
E−1 = {(−y − z, y, z)} = {y(−1, 1, 0) + z(−1, 0, 1)}
D’où u1 (−1, 1, 0) u2 (−1, 0, 1)
Soit E2 ={u ∈ R3 ; (A − 2I3 )u = 0} le sous espace propre associé à la valeur propre λ = 2
 −2x + y + z = 0
On aura x − 2y + z = 0 ⇔x=y=z
x + y − 2z = 0

D’où u3 (1, 1, 1) et (u1 , u2 , u3 ) est une base de vecteurs propres
   
−1 −1 1 −1 0 0
P = 1 0 1  et D = P −1 AP =  0 −1 0 
0 1 1 0 0 2

Exemple 1.4.2 Les matrices suivantes sont elles diagonalisables ?

   
3 −1 1 1 2 −2
A=  2 0 1  et B =  2 1 −2 
0 1 1 2 2 3

1.5 Application : Puissance d’une matrice

Si A = P DP −1 alors ∀n ∈ N on a An = P Dn P −1 . On peut facilement la prouver par récur-
rence.
6 Analyse Numerique

— Pour n = 0, on a A0 = P D0 P −1 = I est vrai.

— On suppose que pour n donné An = P Dn P −1 , montrer que la propriété est vraie à l’ordre
n+1
 
3 0 −1
Exercice 1.5.1 Soit A =  0 1 0 
2 −1 −1
1) Montrer que A est diagonalisable puis donner une matrice P inversible et une matrice D
semblable à A telle que A = P DP −1
2) En déduire An

1.6 Théorème de Cayley-Hamilton

Théorème 1.6.1 Si A ∈ Mn (R) alors PA (A) = 0
 
−1 1 2
Exemple 1.6.2 Soit A =  0 1 0 
2 −1 −1
• Calculer le polynôme caractéristique de A
• Déterminer les réels a, b et c telle que An = cI + bA + aA2

Reponse : Vérifier que PA (X) = −X 3 − X 2 + 5X − 3.

Vérifier que 1 et (−3) sont les valeurs propres de A (soit X n un polynôme de degré n, le reste
de la division euclidienne de X n par P (X) est un polynôme de la forme aX 2 + bX + c)
1est une racine double et (−3) racine simple de P (X), d’où le système :
 a+b+c=1
2a + b = n résoudre ce système
9a − 3b + c = (−3)n

On applique
 le Théorème de Caylay-Hamilton
 on aura 
An = 15 3 1 n I + 1 + 1 n − 1 (−3)n A + − 1 + 1 n + 1 (−3)n A2




16 − 4 n + 16 (−3) 8 2 8 16 4 16
Exercice :
   
1 −1 3 1
1) Soient A =  −1 1 3  et v =  1 
1 1 1 1
(a) Calculer Av
(b) Sachant que A est diagonalisable, trouver ses valeurs propres sans calculer le poly-
nôme caractéristique
Indication : det A = det D et T r(A) = T r(D)
2) Répondre par vrai ou faux en justifiant
(a) Si A est inversible alors A est diagonalisable
(b) Si A ∈ M4 (R) qui admet λ1 valeur propre d’ordre de multiplicité 1 et λ2 valeur
propre d’ordre de multiplicité 3 telle que dim Eλ2 = 2 alors A est diagonalisable.
T. Moulahi & I. Mahfoudhi 7

(c) Si A inversible alors AB et BA sont semblables et ont le même polynôme caracté-

ristique
 
−1 0 0 0 0
 0 5 0 0 0 
 
(d) La matrice A =   0 0 −1 0 0  est-elle diagonalisable ?

 0 0 0 5 −2 
0 0 0 0 2

1.7 Normes vectorielle et matricielles

Définition 1.7.1 (Rayon Spectral) Soit A ∈ Mn (R) une matrice. On définit son rayon spec-
tral comme la plus grande valeur propre en valeur absolue ρ(A) := max |λ|.
λ∈λ(A)

Définition 1.7.2 (Déterminant) Soit A ∈ Mn (R) une matrice. On définit son déterminant
par : det(A) := Πλ∈λ(A) λ.
Exemple 1.7.3 Déterminer les valeurs propres, rayon spectral et le déterminant de la matrice
A
 
4 0 2
A= 0 1 3 .
0 3 1
Théorème 1.7.4 (Caractérisation des matrices inversibles) Soit A une matrice de Mn (C).
Les propriétés suivantes sont équivalentes.
1 A est inversible
2 det(A) 6= 0
3 Ker(A) = {0 ∈ Rn }
4 dim(A) = n
Définition 1.7.5 (Norme vectorielle) Une norme sur E un K−espace vectoriel est une ap-
plication . N : E −→ R+ vérifiant :
— ∀x ∈ E, N (x) = 0 =⇒ x = 0
— ∀(x, λ) ∈ E × K, N (λx) = |λ|N (x)
— ∀(x, y) ∈ E × E, N (x + y) ≤ N (x) + N (y)
Exercice 1.7.6 — 1) Montrer
v que les applications suivantes sont des normes dans Rn .
u n n
uX X
||x||2 := t x2i , ||x||1 := max |xi | et ||x||∞ := |xi |
1≤i≤n
i=1 i=1

— 2) Montrer que ∀x, y ∈ Rn on a : |||x|| − ||y||| | ≤ ||x − y||

Définition 1.7.7 (Norme matricielle) Soit ||.|| une norme vectorielle sur C. On définit la
norme matricielle subordonné à la norme vectorielle ||.|| par :
||Ax||
∀A ∈ Cn,n |||A||| := sup
x∈Cn ,x6=0 ||x||

Exercice 1.7.8 Montrer que ∀A ∈ Cn,n , |||A||| := sup||z||=1 ||Az||

Chapitre 2

Résolution du système linéaire AX=b 1

2.1 Méthode directe (Gauss, LU, Cholesky)

Dans ce paragraphe, on va étudier quelques méthodes directes permettant de résoudre le
système

AX = b (2.1)

Avec A ∈ Mn (R), l’ensemble des matrices carrées n × n coefficients réels, et b ∈ Rn .

Une méthode directe est une méthode qui permet de résoudre le système (2.1) en un nombre
fini d’opérations et permettant d’obtenir la solutions exacte. Dans cette section, on présente les
méthodes suivantes :
- la méthode d’élimination de Gauss,
- la méthode de la décomposition LU ,
- la méthode de Cholesky

2.1.1 Méthode d’élimination de Gauss

L’idée de cette méthode est de se ramener à un système linéaire dont la matrice est triangulaire
supérieure, on obtient ensuite la solution par simple remontée.

Exemple 2.1.1 On cherche à résoudre le système suivant :



 2x + 3y + 3z + t = 15
−4x − 6y + 3z + 2t = 3


 −x +y+z+t=5
−2x − y + z + t = 1


1. Ce chapitre est le contenu du document [?, ?, ?]

8
T. Moulahi & I. Mahfoudhi 9

La méthode de Gauss, consiste à éliminer x des lignes 2,3 4, puis y des lignes 3,4, puis z de
la ligne 4. On obtient alors la valeur de t et on en déduit les autres valeurs on remontant. Le
système (3.2) s’écrit sous forme matricielle Ax = b.
    
2 3 3 1 x 15
 −4 −6 3 2   y   3 
 −1 1 1 1   z  =  5  (2.2)
    

−2 −1 1 1 t 1

Étape 1 On pose A1 = A et on note a1i,j , 1 ≤ i, j ≤ 4 l’élément (i, j) de la matrice A. Lorsqu’il

est non nul. On effectue alors pour toute ligne Li , 2 ≤ i ≤ 4 :

a1i,1
Li ← Li − L1
a11,1

On obtient     
2 3 3 1 x 15
 0 0 9 4   y   33 
  =  (2.3)
 0 5 5 3 
z   25 
2 2 2 2
0 2 4 2 t 16
Étape 2 : On pose A2 la matrice, le pivot a22,2 de la nouvelle matrice est nul. On échange la
deuxième ligne par la troisième. On obtient
    
2 3 3 1 x 15
 0 5 5 3   y   25 
 2 2 2   =  2  (2.4)
 0 0 9 4   z   33 
0 2 4 2 t 16

Le pivot est maintenant a22,2 = 52 . On effectue :

a4,2 4
L4 ← L4 − L2 = L4 − L1
a2,2 5

ce qui donne     
2 3 3 1 x 15
 0 5 5 3 
y   25 
 2 2 2  = 2  (2.5)
 0 0 9 4   z   33 
4
0 0 2 5 t 6
Étape 3 : On obtient la matrice A3 . Le pivot est maintenant a33,3 = 9. On effectue :

a4,3 2
L4 ← L4 − L3 = L4 − L3
a3,3 9

ce qui donne     
2 3 3 1 x 15
 0 5 5 3    25 
 2 2 2  y  =  2  (2.6)
 0 0 9 4   z   33 
−4 −4
0 0 0 45 t 3
10 Analyse Numerique

Étape 4 La matrice obtenue est maintenant triangulaire superière, et on peut résoudre le

système par remontée. On trouve    
x 6
 y   −1 
 = 
 z   −3 
t 15

Algorithme Méthode de Gauss

De l’exemple précédent on peut tirer l’algorithme suivant :
— Pour k allant de 1 à n − 1 Si tous les éléments sous le pivot dans la colonne k est nulle,
passer à la colonne suivante.
— Si l’élément ak,k est nul, et s’il existe un élément non nul, sous le pivot, dans la colonne
k permuter la ligne i avec la ligne k où i est le plus petit entier supérieur à k tel que ai,k
soit non nul.

— Ensuite, pour tout i > k, effectuer l’opération

ai,k
Li ←− Li − Lk
ak,k

2.1.2 Méthode de décomposition LU

La méthode de décomposition LU consiste à factoriser la matrice A en un produit de deux
matrices triangulaires A = LU .
où L est triangulaire inferieure (lower) et U est triangulaire superieure (upper).

Théorème 2.1.2 (Méthode de décomposition LU ) Soit A une matrice dont toutes les sous-
matrices diagonales sont inversibles. Alors Il existe un unique couple (L, U ), avec U triang. sup.,
et L triang. inf. à diagonale unité tel que A = LU

La résolution du système linéaire Ax = b est alors ramenée à la résolution de deux systémes

Ly = b et U x = y

Exemple 2.1.3 Justifier puis effectuer la factorisation LU de la matrice A :

 
4 2 2
 2 10 7  .
2 7 21

2.1.3 Méthode de Cholesky

La méthode de Cholesky s’applique aux matrices réelles symétriques définies positives.
Elle consiste en une factorisation A = BB t , où B est une matrice triangulaire inférieure, dans

Théorème 2.1.4 (Méthode de Cholesky) Soit A une matrice réelle symétrique définie posi-
tive. Alors il existe une unique matrice réelle B triangulaire inférieure, telle que tous ses éléments
diagonaux soient positifs et qui vérifie : A = BB t
T. Moulahi & I. Mahfoudhi 11

Le but de ramener la résolution de l’équation linéaire Ax = b à la résolution de deux équations

By = b et B t x = y.

Exemple 2.1.5 Justifier puis effectuer la factorisation de Cholesky de la matrice A :

 
4 2 2
 2 10 7  .
2 7 21

2.2 Méthode itérative(Jacobi, Gauss-Seidel)

Pour résoudre AX = b on décomposer la matrice A = G − H avec G inversible. Alors :

AX = b ⇔ GX = HX + b ⇔ X = MX + N

On définit la suite récurrente pour cette problème :

X 0 donnée initial


X k+1 = M X k + N

Théorème 2.2.1 (condition nécessaire et suffisante de convergence) La suite X (k) ainsi

définie converge pour tout X (0) si et seulement si ρ(M ) < 1
La convergence d’autant plus rapide que ρ(M ) plus petit

2.2.1 Méthode de Jacobi

On remarque que si les éléments diagonaux de A sont non nuls, alors on peut décomposer la
matrice A sous cette forme :
— A=D−E−F
— D : diagonale de A.
— E : triangulaire inférieure avec des 0 sur le diagonale.
— F : triangulaire supérieure avec des 0 sur le diagonale.

AX = b ⇔ DX = (E + F )X + b ⇔ X = X − D−1 AX + D−1 b

Exemple 2.2.2 Écrire la décomposition de Jacobi pour la matrice A suivante :

 
4 2 2
A =  2 10 7  .
2 7 21
12 Analyse Numerique

Définition 2.2.3 (Matrice à diagonale strictement dominante) Soit A une matrice de

Mn (R). On dit que A est une matrice à diagonale strictement dominante si.
n
X Xn
∀ i = 1, . . . , n |aii | > aij ou |aii | > aji
j=1,j6=i j=1,j6=i

Théorème 2.2.4 Si A est une matrice à diagonale strictement dominante alors la méthode de
Jacobi appliquée au système AX = b est convergente pour tout X (0) .

Remarque 2.2.5 A est une matrice à diagonale strictement dominante est une condition suffi-
sante (non nécessaire).  
1 2 −2
Contre exemple : Soit A = 1 1 1 , la méthode de Jacobi converge (ρ(J) < 1) pour la
2 2 1
résolution du système AX = b. Mais A n’est pas à diagonale strictement dominante.

Algorithme Méthode de Jacobi :



 X(0) vecteur initial

  ||X(k+1) − X(k) ||2 
2

Tant que ≥ ε && k < N Faire

(k+1) 2
||X ||2
X(k+1) = X(k) − D−1 AX(k) + D−1 b





k = k + 1;


Exemple 2.2.6 1) Etudier la convergence de la méthode de Jacobi pour les systèmes suivants :

10 x + y = 11
(S1 )
2 x + 10 y = 12

2 x + 10 y = 12
(S2 )
10 x + y = 11
2) Comparer les deux systèmes :

Remarque 2.2.7 Les deux systèmes (S1) et (S2) l’une converge et que l’autre diverge par la
méthode de Jacobi. On peut conclure que : le choix du systèmes depend des variables x et y.
Même si les deux systemes sont égales.

2.2.2 Méthode de Gauss-Seidel

La méthode de Gauss-Seidel est une méthode itérative de résolution d’un système linéaire
Ax = b, où A = (aij )1≤i,j≤n est une matrice avec les aii 6= 0
la méthode, consiste à décomposer la matrice A sous cette forme :
— A=P −N
— P := D − E triangulaire inférieure avec des éléments diagonaux de A sur le diagonale.
— N := F triangulaire supérieure avec des 0 sur le diagonale.
T. Moulahi & I. Mahfoudhi 13

Ce qui implique l’équation :

AX = b ⇔ PX = NX + b ⇔ X = X − P −1 AX + P −1 b

Théorème 2.2.8 Si A est une matrice à diagonale strictement dominante.

Alors la méthode de Gauss-Seidel appliquée au système AX = b est convergente pour tout X (0) .

Théorème 2.2.9 Si A est une matrice définie positive.

Alors la méthode de Gauss-Seidel appliquée au système AX = b est convergente pour tout X (0) .

Remarque 2.2.10 - Les méthodes de Jacobi et de Gauss-Seidel sont appelées les techniques
de relaxation
- La méthode de Gauss-Seidel converge plus vite que la méthode de Jacobi

Algorithme Méthode de Gauss-Seidel :



 X(0) vecteur initial

  ||X(k+1) − X(k) ||2 
2

Tant que ≥ ε && k < N Faire

(k+1) 2
||X ||2
X(k+1) = X(k) − P −1 AX(k) + P −1 b





k = k + 1;


Exemple 2.2.11 1) Etudier la convergence de la méthode de Gauss-Seidel pour les systèmes

suivants : 
10 x + y = 11
(S1 )
2 x + 10 y = 12

2 x + 10 y = 12
(S2 )
10 x + y = 11
2) Comparer les deux systèmes

Remarque 2.2.12 Les deux systèmes (S1) et (S2) l’une converge et que l’autre diverge par la
méthode de Gauss-Seidel. On peut conclure que : le choix du systèmes depend des variables x et
y. Même si les deux systemes sont égales.
Chapitre 3

Zéros de fonctions non-linéaires 1

3.1 Introduction
L’objet essentiel de ce chapitre est la résolution numerique des équatiions non linéaires. Étant
donné une fonction

f :I⊂R→R (3.1)
Une valeur α ∈ I, telle que f (α) = 0 est appelée racine ou zéro de la fonction f .
En générale, il n’existe pas des formules qui permettent le calcul des valeurs exactes des
racines de la fonction f . Pour cette raison, on s’intéresse à chercher l’approximation des racines
de f à l’aide des méthodes numériques.
Les méthodes employées pour approcher une racine α de f sont en générale des méthodes
itératives : elles consistent à construire une suite (xn ), telle que

lim xn = α.
n→∞

Définition 3.1.1 Une valeur α est une racine séparée ou localisée de la fonction f s’il existe un
intervalle J ⊂ I, tel que α est l’unique racine f dans l’intervalle J .

Définition 3.1.2 Soit xn unr suite convergente vers la solution α de l’équation f (x) = 0. On
pose en = xn − α. La suite xn est dite convergente d’ordre p ≥ 1 s’il existe une constante finie
C > 0, telle que
|en+1 |
lim = C.
n→∞ |en |p

- La constante C est appelée facteur de convergence ou constante asymptotique de l’erreur.

- Si p = 1, on dit que la convergence de la suite xn est linéaire.

1. Ce chapitre est le contenu du document [?, ?, ?]

14
T. Moulahi & I. Mahfoudhi 15

- Si p = 2, on dit que la convergence de la suite xn est quadratique.

Définition 3.1.3 1) Soit xn une suite convergente vers α avec un ordre p et une constante
asymptotique d’erreur C et yn une suite convergente vers α avec un ordre q et une
constante asymptotique D. Alors si (p > q) ou et (p = q et C < D), on dit que la
suite xn converge pus vite que yn .
2) La convergence des méthodes pour la détermination des racines d’une équation non li-
néaire dépend en générale de la donnée initiale x0 . Le plus souvent, on ne sait établir
que des résultats de convergence locale, c’est à dire valable seulement pour une valeur x0
appartenant à un certain voisinage de la racine α pour tout choix de x0 ∈ I sont dites
globalement convergentes vers α.

3.2 Méthode de dichotomie (la bissection)

La méthode de dichotomie est basée sur le théorème des valeurs intermédaires.

Définition 3.2.1 (Théorème des valeurs intermédaires) Soit f une fonction continue sur
I = [a, b], telle que f (a)f (b) < 0. Alors il existe α ∈ [a, b] tel que f (α) = 0.

La condition f (a)f (b) ≤ 0 signifie que f (a) et f (b) sont de signes opposés (où que l’un des
deux est nul). L’hypothèse de continuité est essentielle !

Ce théorème affirme qu’il existe au moins une solution de l’équation (f (x) = 0) dans l’inter-
valle [a, b]. Pour le rendre effectif est trouver une solution (approchée) de l’équation (f (x) = 0), il
s’agit maintenant de l’appliquer sur un intervalle suffisamment petit. On va voir que cela permet
d’obtenir un solution de l’équation (f (x) = 0) comme la limite d’une suite.
Étant donné une fonction continue

f : I = [a, b] → R.
Cette méthode consiste à construire des intervalles emboités In = [an , bn ], tels que In+1 ⊂ In ⊂
In−1 ⊂ · · · ⊂I où la longueur de l’intervalle In+1 est la moitié de celle de l’intervalle In en
concervant la propriété f (an )f (bn ) ≤ 0.
Voici comment construire une suite d’intervalles emboîtés, dont la longueur tend vers 0, et
contenant chacun une solution de l’équation (f (x) = 0).
On part d’une fonction f : [a, b] → R continue, avec a < b, et f (a)f (b) ≤ 0. Voici la première
étape de la construction : on regarde le signe de la valeur de la fonction f appliquée au point
milieu a+b
2
16 Analyse Numerique

• Si f (a)f ( a+b a+b

2 ) ≤ 0, alors il existe c ∈ [a, 2 ] tel que f (c) = 0.
• Si f (a)f ( a+b a+b a+b
2 ) > 0, cela implique que f ( 2 )f (b) ≤ 0, donc il existe c ∈ [ 2 , b] tel que
f (c) = 0.

Nous avons obtenu un intervalle de longueur moitié dans lequel l’équation (f (x) = 0)
admet une solution. On itère alors le procédé pour diviser de nouveau l’intervalle en
deux. Voici le processus complet :
• Au rang 0 :On pose a0 = a, b0 = b. Il existe une solution x0 de l’équation (f (x) = 0)
dans l’intervalle [a0 , b0 ].
• Au rang 1 :
- Si f (a0 )f ( a0 +b
2 ) ≤ 0, alors on pose a1 = a0 et b1 = x1 =
0 a0 +b0
2 ,
a0 +b0
- sinon on pose a1 = x1 = 2 et b1 = b.
- Dans les deux cas, il existe une solution x1 de l’équation (f (x) = 0) dans l’intervalle
[a1 , b1 ].
• ···
b−a
• Au rang n : supposons construit un intervalle [an , bn ], de longueur 2n , et contenant une
solution xn de l’équation (f (x) = 0). Alors :
- Si f (an )f ( an +b
2 ) ≤ 0, alors on pose an+1 = an et bn+1 = xn =
n an +bn
2 ,
an +bn
- sinon on pose an+1 = xn = 2 et bn+1 = bn .
- Dans les deux cas, il existe une solution xn+1 de l’équation (f (x) = 0) dans l’intervalle
[an+1 , bn+1 ].

Exemple 3.2.2 Montrer que la suite xn est convergente vers α la racine de l’équation f (x) = 0.

Preuve 3.2.3 Les suites an , bn et xn sont construites de façon que

[an , bn ] ⊂ [an−1 , bn−1 ] ⊂ · · · ⊂ [a0 , b0 ]

bn−1 − an−1
bn − an = tel que f (an )f (bn ) ≤, ∀n ≥ 1
2
et
bn + an
xn = , ∀n ≥ 1
2
T. Moulahi & I. Mahfoudhi 17

Il est clair que an et bn sont respectivement croissante et décroissante et on a

1
|bn − an | = |bn−1 − an−1 | = 2−n |b − a| → 0, quand n → +∞.
2
Donc, on a
l = lim an = lim bn = lim xn .
n→+∞ n→+∞ n→+∞

Or comme f (an )f (bn ) ≤ 0, par passage à la limite et en utilisant la continuité de la fonction f ,

on obtient
f (l)2 ≤ 0 ⇒ f (l) = 0 ⇒ l = α.

Algorithme Méthode de dichotomie :

— I0 = [a0 , b0 ] et x0 = a0 +b
2 . Pour n ≥ 0 on choisit le sous-intervalle
0

— In+1 = [an+1 , bn+1 ] de l’intervalle In = [an , bn ] de la façon suivante :

— Soit xn = an +b 2 .
n

— Si f (xn ) = 0 alors α = xn et la méthode termine ;

— Si f (an )f (xn ) < 0 on pose an+1 = an et bn+1 = xn
— Si non an+1 = xn et bn+1 = bn
— on définit In = [an , bn ] ; on augmente k de 1 et on recommence.
La méthode de dichotomie est toujours convergente, mais elle est lente. En effet, pour obtenir
une approximation d’une solution α avec une erreur absolue inférieur à ε, le nombre d’itérations
nécessaires n est donné par la rélation suivante :

|en | = |xn − α| ≤ |bn − an | ≤ 2−n |b0 − a0 |

donc pour avoir |en | ≤ ε, il suffit que

|b0 − a0 |
2n ≥
ε
soit alors
|b0 −a0 |

ln ε
n≥ .
ln 2

3.3 Méthode du point fixe (approximations successives)

Définition 3.3.1 (Point fixe) Soit f une fonction de R −→ R. On dit que x0 est un point fixe
de f si et seulement si f (x0 ) = x0 .

Proposition 3.3.2 Soit f une fonction de R −→ R et x0 est un zéro de f si et seulement si x0

est point fixe de g(x) = f (x) + x.

Exemple 3.3.3 Trouver les équivalences entre les points fixes et les zéros des fonctions sui-
vantes :
— f1 (x) = x2 − x − 3
— f2 (x) = x3 − 3x
9 −x
— f3 (x) = 10 e
— f4 (x) = sin(x) − x
18 Analyse Numerique

Proposition 3.3.4 Soit f : [a, b] → R une fonction continue telle que f ([a, b]) ⊂ [a, b]. Alors la
fonction f admet au moins un point fixe dans [a, b].

Preuve 3.3.5 Soit g(x) = f (x) − x pour tout x ∈ I = [a, b].

La fonction g est continue sur I et on a

g(a) = f (a) − a ≥ 0 et g(b) = f (b) − b ≤ 0 ⇒ g(a)g(b) ≤ 0.

D’après le théorème des valeurs intermédiaires, il existe α ∈ I, tel que g(α) = 0. Ainsi, on a
démontré qu’il existe α ∈ I tel que f (α) = α.

Principe de la méthode Cette methode consiste à faire d’abord des opérations algébriques sur
l’équation f (x) = 0 afin de l’écrire sous la forme g(x) = x où g est une fonction à déterminer. La
recherche d’une solution de l’ équation f (x) = 0 est équivalent alors à la déterminer d’un point
fixe de la fonction g.

Exemple 3.3.6 Soit f (x) = x3 + x − 1, on peut choisir la fonction g définie par g(x) = 1 − x3 .

Définition 3.3.7 On dit que la fonction f est contractante (où f est une contraction) s’il existe
k ∈ [0, 1[ tel que
|f (x) − f (y)| ≤ k|x − y|, ∀x, y ∈ [a, b].
Le réel k est appelé rapport de contraction

Théorème 3.3.8 (Fonction k-lipschitzienne) Soit f : [a, b] −→ R est une fonction diffé-
rentiable sur [a, b] inclu dans R. Si sup |f 0 (x)| ≤ k pour tout x dans [a, b], alors f est k-
x∈[a,b]
lipschitzienne sur [a, b].

Théorème 3.3.9 (Théorème du point fixe) Soit f : [a, b] −→ R est une fonction contractante
telle que f ([a, b]) ⊂ [a, b]. Alors f admet un unique point fixe α ∈ [a, b]. De plus, pour tout point
initial x0 ∈ [a, b] la suite (xn )n≥0 définie par xn+1 = f (xn ) converge vers α ∈ [a, b].

Preuve 3.3.10 (i) Existence du point fixe : La fonction f est contractante donc elle est
Lipshitizienne. f est alors continue. En utilisant le fait que f ([a, b]) ⊂ [a, b], on démontre
que f admet au moins un point fixe dans [a, b] (voir la démonstration du proposition
3.3.4).
(ii) Unicité du point fixe : Supposons qu’il existe deux point fixes différents α et β de f
et notons par k ∈ [0, 1[ le rapport de contraction de f . Ainsi, on a

|f (α) − f (β)| = |α − β| ≤ k|α − β|.

Comme 0 ≤ k < 1 alors on a une contradiction (α 6= β et k < 1), d’où α = β.

(iii) Convergence de la suite (xn ) :

|xn − xn−1 | = |f (xn−1 ) − f (xn−2 )| ≤ k|xn−1 − xn−2 | ≤ · · · ≤ k n−1 |x1 − x0 |,

donc pour tout n, m ∈ N tels que n ≥ m, on a :

1 − k n−m
|xn − xm | ≤ (k n−1 + k n−2 + k n−3 + · · · + k m )|x1 − x0 | = k m |x1 − x0 |,
1−k
T. Moulahi & I. Mahfoudhi 19

Puisque 0 ≤ k < 1, on a
lim |xn − xm | = 0.
n,m→∞

On en déduit que la suite (xn ) est de cauchy dans [a, b] donc elle est convergente. Notons
par l la limite de la suite (xn ). En utilisant la continuité de la fonction f et par passage
à la limite dans l’identité xn+1 = f (xn ), on obtient f (l) = l. Donc α = l.

Corollaire 3.3.11 Le résultat du Théorème 3.3.9 reste valable si on remplace l’hypothèse "f est
contractante " par : f de classe C 1 sur [a, b] et supa≤x≤b |f 0 (x)| < 1.

Corollaire 3.3.12 Soit f une fonction réelle admettant un point fixe α. Supposons que f est
continûment différentialle sur un voisinage de α. Alors
(i) Si |f 0 (α)| < 1, la méthode du point fixe est localement convergente, i.e., il existe un
voisinage V de α tel que, pour tout choix de x0 ∈ V, la suite (xn ) définie par xn+1 = f (xn )
converge vers α.
(ii) Si |f 0 (α)| > 1, la méthode du point fixe est divergente pour tout choix de x0 .

Remarque 3.3.13 Le cas |f 0 (α)| = 1, est le plus délicat car on peut avoir les deux cas : Conver-
gente et divergente.

Définition 3.3.14 (L’ordre de la méthode) Une méthode du point fixe est d’ordre p ssi
xn+1 − α
lim =C
n→∞ (xn − α)p
— Si p = 1 on parle de convergence linéaire,
— Si p = 2 on parle de convergence quadratique.

Proposition 3.3.15 Supposons que la méthode du point fixe converge et que f est de classe C2 ,
alors xn+1 − α = f 0 (α)(xn − α) + O(||xn − α||) en particulier, en dimension 1 d’espace, si xn 6= α
xn+1 − α
lim = f 0 (α)
n→∞ (xn − α)

En général, la méthode du point fixe, quand elle converge, est une méthode d’ordre 1. C’est à
dire que, en gros, à chaque itération l’erreur est multipliée par un coefficient(plus petit que un).
Algorithme du point fixe
D’où l’algorithme de la méthode du point fixe :
Etant donné une fonction f vérifiant les hypothèses (H1) et (H2)sur un intervalle [a, b], et un
nombre positif ε :
f : [a, b] → R
(H1) f est continue et dérivable sur [a, b].
0
(H2) ∃K ∈]0, 1[: ∀x ∈ [a, b] |f (x)| ≤ K
Algorithme Méthode du point fixe :
— On choisit x0 ∈ [a, b], ε > 0 et K.
log(ε) − log |b − a|

— On calcule n0 = E +1
log K
— Pour n de 1 à n0 , on calcule xn = f (xn−1 ).
Une valeur approchée à ε près de la racine c est xn0 .
20 Analyse Numerique

3.4 Méthode de Newton

Ètant donné une fonction f de classe C 2 , pour déterminer la racine de l’équation f (x) = 0,
la méthode de Newton consiste à constriuire à aprtir de x0 une suite (xn ) définie par

f (xn )
xn+1 = xn − .
f 0 (xn )

Interpretation géometrique : xn+1 est l’intersection de la tangente à la courbe Cf de la

fonction f au point (xn , f (xn )) avec l’axe des abscisses. En fait, l’équation de la tangente T à
Cf en (xn , f (xn )) est donnée par T : y = f 0 (xn )(x − xn ) + f (xn ).
L’intersection de la tangente T avec l’axe des abscisses est déterminée par

f (xn )
y = 0 ⇒ x = xn − .
f 0 (xn )

Remarque 3.4.1 Il faut que f 0 (xn ) 6= 0.

La méthode de Newton est une méthode de point fixe pour la fonction

f (x)
ψ(x) = x − f 0 (x) si f 0 (x) 6= 0
(3.2)
xn+1 = xn − ff0(x n)
(xn )

Alors on a : f (α) = 0 si et seulement si α est un point fixe de ψ. Si de plus f 0 (α) 6= 0 alors

ψ 0 (α) = 0

Théorème 3.4.2 (Théorème de Newton) Si f ∈ C2 , f (α) = 0 et f 0 (α) 6= 0 alors il existe δ

telle que, si |x0 − α| ≤ δ la suite définie dans (3.2) converge vers α. De plus, la convergence est
xn+1 − α f 00 (α)
quadratique : lim =
n→∞ (xn − α)2 2f 0 (α)

Remarque 3.4.3 — Si f 0 (α) 6= 0 alors ψ 0 (α) = 0,la convergence est quadratique.

0
— Si f (α) = 0, la convergence est linéaire. On considère alors la méthode de Newton mo-
difiée : xn+1 = xn − p ff0(x n)
(xn ) n ≥ 0 avec p la multiplicité de α.

Algorithme Méthode de Newton :



 x0 , ε > 0 et Nmax données initiale.


 k = 0;
2
  ||x
k+1 − xk ||2

 
 Tant que ≥ ε && k < Nmax Faire


||xk+1 ||22


f (xk )


k+1 = xk − 0 ;
 x




 f (xk )
k = k + 1;

Chapitre 4

Approximation polynômiale 1

4.1 Interpolation
Le but de cet chapitre est de trouver une approximation " polynômiale" d’une fonction f .
Soient f ∈ C 0 ([a, b]) et x0 , x1 , . . . , xn ∈ [a, b] n + 1 des points distincts. On cherche un polynôme
p de degré n tel que

Théorème 4.1.1 (Méthode classique) Le problème d’interpolation p(xi ) = f (xi ), 0 ≤ i ≤ n,

admet une solution et une seule, donnée par la formule (4.1). On peut aussi voir les choses
différemment. Si p(x) = a0 + a1 x + · · · + an xn , les coefficients de p sont solutions de

. . . xn0
    
1 x0 a0 f (x0 )
 1 x1 . . . xn1   a1   f (x1 ) 
=
    
 .. ..   .. .. 
 . .  .   . 
1 xn . . . xnn an f (xn )

Mal conditionné :
— Y
La matrice de ce système linéaire est une matrice de Vandermonde de déterminant
(xi − xj ) 6= 0 car les points xi sont distincts.
i<j

— Le système de Vandermonde appartient à la catégorie des systèmes linéaires mal condi-

tionnés.

Définition 4.1.2 (Système mal conditionné) On appelle un système mal conditionné si pour
une petite erreur sur les coefficients ou le second membre entraéne une erreur importante sur la
solution du système. Autrement le conditionnement d’une matrice inversible A est :
cond(A) = ||A|| × ||A−1 || = λλmax
min
où ||.|| est une norme matricielle.
1. Ce chapitre est le contenu du document [?, ?, ?, ?, ?]

21
22 Analyse Numerique

4.1.1 Méthode de Lagrange

Soit P un polynôme de degré n tel que coïncide avec la fonction f en n + 1 points
P (xi ) = f (xi ), 0 ≤ i ≤ n.
On considère les polynômes Li , i = 0, . . . , n de degré n tels que Li (xj ) = δij = 1 si i = j et
0 si non. Explicitement on a :
n
Y (x − xj )
Li (x) = , 0≤i≤n
(xi − xj )
j=0,i6=j

Alors le polynôme d’interpolation de f aux points x0 , x1 . . . . xn s’écrit sous cette forme :

n
X
Pn (x) = f (xi )Li (x), 0≤i≤n (4.1)
i=0

1
Exercice 4.1.3 Soient x0 = 0, x1 = 21 , x2 = 1 et f (x) = .
1+x
1) Construire les polynômes de Lagrange Li , i = 0, 1, 2.
2) Construire le polynôme P2 qui interpole f aux points xi pour i = 0, 1, 2.
Algorithme Méthode de Lagrange :
Donner deux vecteurs X = (xi )1≤i≤n , Y = (yi )1≤i≤n et t
— P = 0;
— Pour i = 1 à n faire
— L = 1;
— Pour j = 1 à i − 1
(t−x )
— L = L (xi −xjj ) ;
— Pour j = i + 1 à n
(t−x )
— L = L (xi −xjj ) ;
— P = P + y(i)L;

4.1.2 Méthode des différences divisées

Soit pk le polynôme d’interpolation par la méthode de différence divisée de f aux points
x0 , x1 , . . . , xk .
On désigne par f [x0 , x1 , . . . , xk ] le coefficient du monôme de plus haut degré de pk . Alors

p0 (x) = f (x0 ) On définit les pk

pk (x) − pk−1 (x) = f [x0 , x1 , . . . , xk ](x − x0 ) . . . (x − xk−1 ).
Théorème 4.1.4 (Méthode de Newton) Il existe un polynôme pn d’interpolation unique de
degré inférieur ou égal à n définit comme suit :
n
X
pn (x) = f (x0 ) + f [x0 , x1 , . . . , xk ](x − x0 ) . . . (x − xk−1 ).
k=1
f [x1 ,...,xk ]−f [x0 ,...,xk−1 ]
Avec f [x0 , x1 , . . . , xk ] = (xk −x0 )
T. Moulahi & I. Mahfoudhi 23

1
Exercice 4.1.5 Soient x0 = 0, x1 = 12 , x2 = 1 et f (x) = .
1+x
1) Construire les coefficients f [x0 , . . . , xi ], i = 0, 1, 2.
2) Construire le polynôme P2 qui interpole f aux points xi pour i = 0, 1, 2.

Algorithme Méthode de Newton :

Donner deux vecteurs X = (xi )1≤i≤n , Y = (yi )1≤i≤n et t
— Pour i = 1 à n faire
— D(i, i) = yi ;
— Pour i = 2 à n faire
— Pour j = i à n faire
— D(j − i, j) = D(j−i+1,j)−D(j−i,j−1)
xj −xj−i ;
P = D(1, 1)
ϕ = (t − x1 );
— Pour i = 1 à n faire
— P = P + D(1, i)ϕ;
— ϕ = ϕ × (t − xi );

4.2 Formule d’erreur

Théorème 4.2.1 (Méthode de Newton) Soient x0 , x1 , . . . , xn , n+1 points distincts dans [a, b]
et soit f ∈ C n+1 ([a, b]). Alors pour tout x ∈ [a, b]
1
f (x) − pn (x) = πn+1 (x)f (n+1) (ξ)
(n + 1)!
n
Y
où πn+1 = (x − xi ), avec ξ ∈ [a, b].
i=0

En prenant la borne supérieure de la valeur absolue des deux membres dans la formule d’erreur,
on obtient en particulier :
1
||f − pn || ≤ ||πn+1 ||||f (n+1) ||
(n + 1)!

Remarque 4.2.2 L’erreur d’interpolation f (x)−pn (x) dépend à la fois de la quantité ||f (n+1) ||,
qui peut être grande si f oscille trop vite, et de la quantité πn+1 , qui est liée à la répartition des
points xi dans l’intervalle [a, b]. Dans le cas particulier où les noeuds sont équirepartis

1  (b − a) n+1
||f − pn || ≤ ||f (n+1) ||
4(n + 1) n
1
Exemple 4.2.3 On définit la fonction f (x) = 1+x 2

— Calculer les polynômes de lagrange pi pour xi = −5 + 10 ni , i = 1, . . . , n

— Calculer l’erreur de l’interpolation de Lagrange, ainsi que leur limite.