MATHÉMATIQUES, INFORMATIQUE et GÉOMATIQUE

FILIÈRE GÉNIE INDUSTRIELLE

================================

MATHÉMATIQUES APPLIQUÉES 1

ANALYSE NUMÉRIQUE 1
T

Pr. Hassan EL AMRI

AF

École Normale Supérieure de Casablanca

Route d’El Jadida, Casablanca, Maroc.
DR

[email protected]

Année universitaire : 2020-2021

 DR

ii
AF
T
Table des matières

1 Arithmétique de l’ordinateur erreurs numériques, Sources d’erreurs 1

1.1 Erreur de modélisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Erreur de données . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.3 Erreur de troncature ou d’itération . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.4 Erreur d’arrondi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.5 Erreur humaines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

2 Méthodes Numériques de résolution des Systèmes linéaires 3

2.1 Méthodes directes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.1.1 Méthode des éliminations de Gauss . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.1.2 Méthodes des différences finies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.1.3 Méthode de Cholesky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Rappel sur les matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
sa
2.2.1 Valeurs et vecteurs propres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
Ca

2.3 Méthodes itératives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

NS

2.3.1 Exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
-E

2.3.2 Cadre général . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

ri

2.3.3 Méthode de Jacobi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

Am

2.3.4 Méthode de Gauss Seidel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

El

2.3.5 Relaxation, SOR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

H.

2.3.6 Convergence des méthodes de Jacobi, Gauss-Seidel et SOR . . . . . . . . . . . . . . . . 20

2.4 Notions sur les éléments finis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.4.1 Éléments finis P1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.5 Méthodes Numériques de résolution des systèmes non linaires . . . . . . . . . . . . . . . . . . 27
2.5.1 Rappels et notations de calcul différentiel . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.5.2 Méthodes du point fixe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.5.3 Méthode de Newton en dimension 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.5.4 Point fixe de monotonie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.6 Interpolation et Approximation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

iv
∂u
(x, t) − ∆u(x, t) = f
∂t

sa
Ca
NS
-E
ri
Am
El
H.

v
 H.
El
Am
ri

vi
-E
NS
Ca
sa
Chapitre 1

Arithmétique de l’ordinateur erreurs numériques,

Sources d’erreurs

1.1 Erreur de modélisation

On se déplace d’une ville A à une ville B avec une vitesse constante V . Le temps T qu’il faudra pour arriver
à B vérifie
d = V T.
La route étant pleine de barrage, de virage et d’embouteillages, la vitesse ne peut pas être constante, elle
dépend du temps. Alors le temps qu’il faudra vérifie l’équation
sa
Z T
Ca

d= v(t)dt.
NS

0
-E

1.2 Erreur de données

ri
Am

Erreurs de lecture, instruments de mesures, Nombre de chiffres significatifs fini (π = 3.14 par exemple)
El
H.

1000 ∗ 3.14 = 3140 − 1000 ∗ π = −1, 59.

1.3 Erreur de troncature ou d’itération

f (x) = 0
Newton
f (x)
g(x) = x −
f 0 (x)
x0 , quelconque xn+1 = g(xn )
f (x) = x2 − 2
On fait ce type d’erreur lorsque :
— On prend un nombre fini de termes dans une série (Taylor par exemple) La suite x0 donné, xn+1 = x2n + x2n
√
converge vers 2. Mais en général on s’arrête après un nombre fini d’itérations. On commet donc une
"petite" erreur :
x0 = 1, x1 = 1.5000, x2 = 1.4167, x3 = 1.4142, x4 = 1.4142

x0 = 10, x1 = 5.1000, x2 = 2.7461, x3 = 1.7372,

x4 = 1.4442, x5 = 1.4145, x6 = 1.4142

1
 — On approche une dérivée par un quotient aux différences finies

 u00 (x) + a(x)u0 (x) + b(x)u(x) = f (x), dans [0, 1]
 u(0) = α, u(1) = β

•0 x•
i−1 x•i x•
i+1
•1
1
Figure 1.1 – xi = ih, h = N +1
.

u(xi+1 ) − u(xi ) u(xi ) − u(xi−1 ) u(xi+1 ) − u(xi−1 )

u0 (xi ) ' ' '
h h 2h
u(xi+1 ) − 2u(xi ) + u(xi−1 )
u00 (xi ) '
h2

u1 , u2 , ....., un

AU = F
sa
1.4 Erreur d’arrondi
Ca
NS

Les nombres ne sont pas stockés de facon exacte sur un ordinateur. Il en est de même pour les opérations qui
-E

introduisent des erreurs supplémentaires. Par exemple, 34 sera stocké sur la machine avec la valeur 1.333333
ri

qui ne comporte que 7 chiffres significatifs corrects alors que la valeur exacte comporte une décimale infinie.
Am
El

1.5 Erreur humaines

H.

Elles sont infinies ! !

2
Chapitre 2

Méthodes Numériques de résolution des

Systèmes linéaires

2.1 Méthodes directes

2.1.1 Méthode des éliminations de Gauss
La descente :

On considère un système linéaire

sa
Ca

Ax = b
NS
-E
ri
Am



 a11 x1 +a12 x2 +... +a1j xj +... +a1N xN = b1 : eq1
a21 x1 +a22 x2 +... +a2j xj +... +a2N xN = b2 : eq2
El





.....
H.





....

(2.1)

 ai1 x1 +ai2 x2 +... +aij xj +... +aiN xN = bi : eqi
....




....




aN 1 x 1 +aN 2 x2 +... +aN j xj +... +aN N xN = bN : eqN


On suppose que a11 6= 0.

ai1
Pour i = 2, ..., N on multiplie la première équation par − , on l’ajoute à la ième ligne.
a11
  
ai1
a11 x1 +a12 x2 +... +a1j xj +... +a1N xN = b1 : eq1 ∗ −


a11




a21 x1 +a22 x2 +... +a2j xj +... +a2N xN = b2 : eq2




 .....


.... (2.2)
ai1 x1 +ai2 x2 +... +aij xj +... +aiN xN = bi : eqi




....




....




aN 1 x 1 +aN 2 x2 +... +aN j xj +... +aN N xN = bN : eqN


Le système dévient

3
 

 a11 x1 +a12 x2 +... +a1j xj +... +a1N xN = b1 : eq1
a122 x2 +... +a12j xj +... +a12N xN = b12 : eq21




a132 x2 +... +a13j xj +... +a13N xN = b13 : eq31





.....



.... (2.3)
a1i2 x2 +... +a1ij xj +... +a1iN xN = b1i : eqi1







 ....



 ....
a1N 2 x2 +... +a1N j xj +... +a1N N xN = b1N : eqN
1



où
ai1
a1ij = aij − a1j , i, j = 2, ..., N
a11
et
ai1
b1i = bi − b1 , i = 2, ..., N
a11

On suppose que a122 6= 0.

a1i2
Pour i = 3, ..., N on multiplie la deuxième équation par − on l’ajoute à la ième ligne.
a122


 a11 x1 +a12 x2 +... +a1j xj +... +a1N xN = b1 : eq1
 1 
a


sa
a122 x2 +... +a12j xj +... +a12N xN = b12 : eq21 ∗ − 1i2


Ca




 a22
a132 x2 +... +a13j xj +... +a13N xN = b13 : eq31

NS





.....
-E


(2.4)
....
ri



Am

a1i2 x2 +... +a1ij xj +... +a1iN xN = b1i : eqi1






 ....
El




 ....
H.



a1N 2 x2 +... +a1N j xj +... +a1N N xN = b1N : eqN
1



Le système dévient


 a11 x1 +a12 x2 + ... +a1j xj +... +a1N xN = b1 : eq1
a122 x2 + ... +a12j xj +... +a12N xN = b12 : eq21




a233 x3 +... +a23j xj +... +a23N xN = b23 : eq32





....



.... (2.5)
a2i3 x2 +... +a2ij xj +... +a2iN xN = b2i : eqi2







 ....



 ....
a2N 3 x2 +... +a2N j xj +... +a2N N xN = b2N : eqN
2



où
a1i2
a2ij = a1ij − a1j , i, j = 3, ..., N
a122
et
a1i2 1
b2i = b1i − b , i = 3, ..., N
a122 2
Ainsi de suite, on obtient un système linéaire du type :

4
 

 a11 x1 +a12 x2 + ... +a1j xj +... +a1N xN = b1
1
a x + ... +a12j xj +... +a12N xN = b12

22 2



a233 x3 +... +a23j xj +... +a23N xN = b23





 ...

 ai−1
ii xi
i−1
+... +aiN xN = bi−1
i
....




−2 N −2 N −2
aN

N −1,N −1 xN −1 +aN −1,N xN = bN −1



 −1 −1
aN
N N xN = bN

N

où en notant a0ij = aij



 P our i = 1, ..., N
 P our k = 1, ..., i − 1

descente P our j = k, ..., N

 ak−1 k−1 k−1
aik
ak = ak−1 − ik k−1 a , bki = bk−1 − bk−1


ij ij akk kj i ak−1 k
kk

ak−1
On pose µkj = ak−1
kj , mik = ik
µkk
, yk = bkk−1

 P our i = 1, ..., N
 P our k = 1, ..., i − 1



bki = bk−1 − mik yk
sa
i
Ca




 P our j = k, ..., N
NS

akij = ak−1 − mik µkj


ij
-E
ri

On part donc d’un système à matrice carrée pleine, et on arrive à un système à matrice triangulaire supérieure.
Am
El

Ux = c
H.

 
a11 a12 ... a1j ... a1N
 . a122 ... a12j ... a12N 
 
 . 2 2 2
 . a33 ... a 3j ..a 
3N 
 . ... . . . 
U =
 
i−1 i−1 
 . . . .aii ... aiN 
 . . . . . .... 
 
−2 N −2 
aN

 . . . . N −1,N −1 aN −1,N 
−1
. . . . . aNNN

On la note  
u11 u12 ... u1j ... u1N
 . u22 ... u2j ... u2N 
 
 . . u33 ... u3j ..u3N 
 
 . ... . . . 
U =
 .

 . . .uii ... uiN  
 . . . . . .... 
 
 . . . . uN −1,N −1 uN −1,N 
−1
. . . . . uNNN

Théorème 2.1.1. Une matrice triangulaire supérieure U est inversible si et seulement si les éléments de sa
6 ∀i = 1, ..., N.
diagonale sont tous non nuls : uii =

5
Pour une matrice triangulaire supérieure de termes (uij ) la résolution du système linéaire U x = c se fait selon
l’organigramme suivant.
i = N, N − 1, ..., 1 f aire




 XN
ci − uij xj

 j=i+1
 xi =

uii
Le nombre d’opérations dans le processus de la descente est :
 3
N −N

 additions,
3







 3
N −N
multiplications


 3



 N (N − 1) divisions



2

Le nombre d’opérations dans le processus de la remontée est :

N (N − 1)


 additions,
2






N (N − 1)
sa
 multiplications
Ca



 2

NS




N divisions
-E
ri

Le nombre total d’opérations est de l’ordre de :

Am

 3
N
El


 additions,
H.

3







 3
N
multiplications


 3


 2
 N


divisions

2

Le nombre total d’opérations dans la méthode de Cramer est :


 (N + 1)! additions,
(N + 2)! multiplications
N divisions


Pour N = 10 on a 
Gauss 700 opérations
Cramer 400.000.000 opérations


a11 x1 + a12 x2 = b1
a21 x1 + a22 x2 = b2
 
a11 a12
∆ = det
a21 a22

6
  
b a
∆1 = det 1 12
b2 a22
 
a b
∆2 = det 11 1
a21 b2

∆1 ∆2
x1 = , x2 =
∆ ∆

∆ ==== 2mult + 1add

Total 6 multi 2 divisions et 3 additions.

Le choix du pivot est très important.

10−4 x1 + x2 = 1

eq1
x1 + x2 =2 eq2

1
La solution exacte (1 − 0.0001)x1 = 1, x1 = 0.9999 = 1, 00010
x2 = 2 − 1.00010 = 0.99990
x1 = 1.00010, x2 = 0.99990

Par Gauss : 104 ∗ eq1 + eq2

sa
Ca

10−4 x1 +x2

=1 eq1
NS

−99990x2 = −99990 −104 ∗ eq1 + eq2

-E
ri

On en déduit que x2 = 1 et donc x1 = 0 dans l’équation eq1

Am
El

Exercice 2.1.2. Écrire le programme (la descente et la montée) pour le cas où la matrice du système linèaire
H.

est tridiagonale ie
 
a11 a12 ... ...0.... ..0. ... 0
a21 a22 a23 0.... ...0... ... 0 
 
 0 a32 a33 a 34 0.. ... 0 
 
 . ... . . . 
A=  
 0.. ..0.. ..0.. a i,i−1 a ii a i,i+1 0 

 . . . . . .... 
 
 . . . . aN −1,N −1 aN −1,N 
. . . . . aN N

C’est à dire aij = 0 pour |i − j| > 1.

Théorème 2.1.3. Si la matrice A est tridiagonale alors U est tridiagonale.

 
u11 u12 ... ...0.... ..0. ... 0
 0 u22 u23 0.... ...0... ... 0 
 
 0 0 u33 u34 0.. ... 0 
 
 . ... . . . 
U =
 0.. ..0.. ..0..

 0 uii ui,i+1 0  
 . . . . . .... 
 
 . . . . 0 uN −1,N −1 uN −1,N 
. . . . . 0 uN N

7
2.1.2 Méthodes des différences finies

 −u00(x) + a(x)u0(x) + b(x)u(x) = f (x), dans [0, 1]
 u(0) = 0, u(1) = 0

•0 x•
i−1 x•i x•
i+1
•1
1
Figure 2.1 – xi = ih, h = N +1
.

h2 00 h3 h4
u(xi+1 ) = u(xi + h) = u(xi ) + hu0 (xi ) + u (xi ) + u000 (xi ) + u0000 (ξi )
2 6 24

h2 00 h3 h4
u(xi−1 ) = u(xi − h) = u(xi ) − hu0 (xi ) + u (xi ) − u000 (xi ) + u0000 (ξi0 )
2 6 24

h4 0000 h4
u(xi+1 ) + u(xi−1 ) = 2u(xi ) + h2 u00 (xi ) + u (ξi ) + u0000 (ξi0 )
24 24
sa

h4 u0000 (ξi ) + u0000 (ξi0 )

Ca

u(xi+1 ) + u(xi−1 ) − 2u(xi ) = h2 u00 (xi ) +

NS

12 2
-E

h4 0000
u(xi+1 ) + u(xi−1 ) − 2u(xi ) = h2 u00 (xi ) + u (ηi )
ri
Am

12
El

u(xi+1 ) − 2u(xi ) + u(xi−1 ) h2 0000

u00 (xi ) = − u (ηi )
H.

h2 12
On suppose pour simplifier que a(x) = b(x) = 0
h2 0000
On néglige le terme en u (ηi ) et le problème devient :
12
u00 (xi ) = f (xi ), i = 1, ...., N

ui−1 − 2ui + ui+1

= f (xi ) = ci , i = 0, ..., N
h2
u0 − 2u1 + u2
i = 1, = f (x1 ) = c1
h2
Comme u0 = 0 il reste :

−2u1 + u2
= f (x1 ) = c1
h2
Pour i = 2
u1 − 2u2 + u3
= f (x2 ) = c2
h2
−ui−1 + 2ui − ui+1
= −f (xi ) = Ci , i = 1, ..., N
h2

8
  
2 −1 0 0 ... 0 0 0 0
−1 2 −1 0 0 .... 0 0 0
 
1  0 −1 2 −1 . 

h2 
 . 

 
0 . 0 .. 0 .. 0 −1 2

On sait montrer que :

|ui − u(xi )| ≤ C h.

2.1.3 Méthode de Cholesky

Ax = b1 , Ax = b2 , ....., Ax = bk
 
2 3
A=
4 5
   
1 0 1 0
E1 = , E1−1 =
sa
2 1 −2 1
Ca
NS

    
1 0 2 3 2 3
E1−1 A
-E

= = =U
−2 1 4 5 0 −1
ri
Am

A = E1 U
El

Le passage de la matrice
H.

 
a11 a12 ... a1j ... a1N
 a21 a22 ... a2j ... a2N 
 
 ..... 
 
 .... 
A=
 ai1 ai2
 (2.6)
 ... aij ... aiN 
 .... 
 
 .... 
aN 1 aN 2 ... aN j ... aN N

à la marice  
a11 a12 ... a1j ... a1N

 a122 ... +a12j ... a12N


 a132 ... a13j ... a13N

.....
 
 
A1 =  .... (2.7)
 

a1i2 ... a1ij 1 
+... +aiN 


 
 .... 
 
 .... 
a1N 2 ... a1N j 1
... aN N

On multiplie la première équation par E1−1

9
  
1 0 ... 0 ... 0
 l21 1 0 .. . 0 
 
 l31 0 1 .. . 0 
 
 l41 0 ..... 
 
 . ....
E1 =  (2.8)


 li1 0 ... 0 .. . 0
 
 . .... 
 
 . .... 1 0
lN 1 0 ... 0 .. . 1
avec
ai1
li1 =
aii
−1
E1−1 E2−1 ....EN A=U
c’est à dire
A = EN ....E1 U = LU

akik
lkk = 1, et lik = , i = k + 1, ..., n
akkk

Ax = b ⇐⇒ LU x = b ⇐⇒ Ly = b, U x = y
sa
On fait la descente et la remontée de Gauss une seule fois et on résout des systèmes linéaires à matrices
Ca

triangulaire inférieur et supérieure.

NS

Théorème 2.1.4. Soit A = (aij ) une matrice carrée d’ordre n telle que les sous matrices diagonales
-E
ri

 
a11 . . a1k
Am

 . . . . 
∆k = 
 . . . .  , k = 1, ...n
El


H.

ak1 . . akk

soient inversibles.
Alors il existe une matrice triangulaire inférieure L = (lij ) avec lii = 1, 1 ≤ i ≤ n et une matrice triangulaire
supérieure U telles que
A = LU.
De plus une telle factorisation est unique.

Remarque 2.1.5. Si la matrice A est symétrique définie positive, alors les conditions du théorème 2.1.4 sont
vérifiées.

Remarque 2.1.6. Si la condition du théorème 2.1.4 n’est pas satisfaite on peut toujours s’y ramener après
des permutations préalables des lignes de la matrice.

Exercice 2.1.7. 1. Montrer que la matrice

 
2 2 1
A = 1 1 1
3 2 1
est inversible.
2. Montrer que A ne peut pas être écrite sous la forme d’un produit d’une matrice triangulaire inférieure et
d’une matrice triangulaire supérieure.

10
 1. Calculer le déterminant
2. On suppose que LU = A
    
1 0 0 u11 u12 u13 2 2 1
l21 1 0  0 u22 u23  = 1 1 1
l31 l32 1 0 0 u33 3 2 1
La première ligne de L fois les trois colonnes de U :

u11 = 2, u12 = 2, u13 = 1

La deuxième ligne de L fois les trois colonnes de U :

l21 u11 = 1, l21 u12 + u22 = 1, l21 u13 + u23 = 1

ou encore
2l21 = 1, 2l21 + u22 = 1, l21 + u23 = 1
c’est à dire
1 1
l21 = , u22 = 0, u23 =
2 2
La troisième ligne de L fois les trois colonnes de U :

l31 u11 = 3, l31 u12 + l32 u22 = 2, l31 u13 + l32 u23 + u33 = 1
ou encore
sa
Ca

1
NS

2l31 = 3, l31 u12 = 2, l31 + l32 + u33 = 1

2
-E

3 4 1 1
ri

l31 = , u12 = , l32 + u33 = −

Am

2 3 2 2
El

On tombe sur une absurdité :

4
H.

u12 = 2 et u12 =
3

On permute la deuxième et la troisième ligne

    
1 0 0 u11 u12 u13 2 2 1
l21 1 0  0 u22 u23  = 3 2 1
l31 l32 1 0 0 u33 1 1 1

devient
    
1 0 0 2 2 1 2 2 1
l21 1 0 0 u22 u23  = 3 2 1
l31 l32 1 0 0 u33 1 1 1
Puis
    
1 0 0 2 2 1 2 2 1
3

2
1 0 0 u22 u23  = 3 2 1
l31 l32 1 0 0 u33 1 1 1
3
3 + u22 = 2, + u23 = 1
2
1
u22 = −1, u23 = −
2

11
     
1 0 0 2 2 1 2 2 1
3 1 0 0 −1 − 12  = 3 2 1
2
l31 l32 1 0 0 u33 1 1 1
1
2l31 = 1, 2l31 − l32 = 1, l31 − l32 + u33 = 1
2
1 1
l31 = , l32 = 0, u33 =
2 2
    
1 0 0 2 2 1 2 2 1
 32 1 0 0 0 −1 = 3 2 1
1
2
0 1 0 0 21 1 1 1

2.2 Rappel sur les matrices

On définit sur Rn les trois normes (équivalentes) suivantes

n
! 21 n
X X
||x||2 = x2i , ||x||1 = |xi | , ||x||∞ = max |xi |
i=1,...,n
i=1 i=1

Soit Mn×n (R) l’espace des matrices carrées d’ordre n. On définit sur Mn×n (R) les trois normes associées aux
trois normes de Rn par :
||Ax||
sa
||A|| = sup
Ca

x6=0 ||x||
NS

Définition 2.2.1. Une norme de Mn×n (R) est dite subordonnée si elle provient d’une norme de Rn .
-E
ri

Proposition 2.2.2. Si une norme ||.|| est subordonnée alors

Am
El

||I|| = 1
H.

où I est l’identité de Rn : Ix = x, ∀x ∈ Rn .

Remarque 2.2.3. Il existe des normes non subordonnées, par exemple la norme naturelle de Mn×n (R) définie
pour n > 1 par :
n
! 12
X
||A|| = a2ij
i,j=1
√
||I|| = n
2
C’est la norme euclidienne de Rn .

2.2.1 Valeurs et vecteurs propres

Définition 2.2.4. 1. Soit A ∈ Mn×n (R) on dit qu’un scalaire λ ∈ C est valeur propre de A, s’il existe un
vecteur non nul v ∈ Rn tel que
Av = λv.
2. On note σ(A) l’ensemble des valeurs propres de A
3. On appelle rayon spectral de la matrice A le réel

ρ(A) = max {|λ| , λ ∈ σ(A)}

12
Proposition 2.2.5. 1. Soient A ∈ Mn×n (R) et ||.|| une norme quelconque de A ∈ Mn×n (R). Alors
ρ(A) ≤ ||A|| .

2. Pour toute matrice A et tout ε > 0 il existe une norme subordonnée telle que
ρ(A) ≤ ||A|| ≤ ρ(A) + ε.
Démonstration. Soit λ ∈ σ(A), ∃v ∈ Rn , v 6= 0 tel que Av = λv.

||Av|| = |λ| ||v||

||Av||
|λ| = ≤ ||A||
||v||
on en déduit que
ρ(A) ≤ ||A|| .

Proposition 2.2.6. (Exercice) Soit ||.|| une norme subordonnée. Soit B une matrice telle que
||B|| < 1
alors la matrice I + B est inversible et on a
(I + B)−1  ≤
  1
1 − ||B||
sa
Exo :
Ca

1 1
≤
1 − |x|
NS

1+x
-E

(I + B)−1 (I + B) = I
ri
Am

Théorème 2.2.7. Soi B une matrice carrée. Les conditions suivantes sont équivalentes :
El

1. lim B k = 0, ie : ∀i, j bkij → 0

H.

k→∞
2. lim B k v = 0, ∀v ∈ Rn
k→∞
3. ρ(B) < 1
4. ||B|| < 1 pour une certaine norme matricielle subordonnée ||.|| .
De plus
  1
ρ(B) = lim B k  k ,
k→∞
n×n
pour n’importe quelle norme de M (R).
 
0 0 0 ε
1 0 0 0
 
0 1 0 0 
 

 0 1 0 0 

A(ε) =  . . .  ∈ Mn×n (R)
 

 . . . 


 . . . 

 0 1 0 0
0 1 0
La matrice A(0) a pour valeur propre 0 de multiplicité n.
Par contre det(A(ε)) = εn

13
2.3 Méthodes itératives
2.3.1 Exemples
    
a11 a12 x1 b
Ax = 1 = 1 =b
a21 a22 x2 b2

a11 x1 + a12 x2 = b1
a21 x1 + a22 x2 = b2
 0
0 x1
x = donné :
x02

a11 x11 + a12 x02 = b1
a21 x01 + a22 x12 = b2

 a11 x11 = b1 − a12 x02 = b1 + 0x01 − a12 x02
(2.9)
a22 x12 = b2 − a21 x01 = b2 − a21 x01 + 0x02


On calcule pour i = 0, ...

 a11 xi+1

1 = b1 − a12 xi2 = b1 + 0xi1 − a12 xi2
(2.10)
a22 xi+1 = b2 − a21 xi1 = b2 − a21 xi1 + 0xi2

2
Pour i = 0 on aura
sa
Ca


1 1
 x1 = (b1 − a12 x02 )
NS

a11

-E

 x1 = 1
(b2 − a21 x01 )

ri

2 a22
Am

Et on pose
ei1 = xi+1 − xi1 , ei2 = xi+1 − xi2
El

1 2
H.

  xi+1  
a11 0 i+1 0 −a12
x =b+ xi
0 a22 −a21 0

Dxi+1 = b + Exi + F xi
On arrête le processus lorsque    
max ei1  , ei2  ≤ ε assez petit
(2.10) s’écrit sous forme matricielle
 i+1    i
i+1 x1 0 a12 x1
Dx = D i+1 = b −
x2 a21 0 xi2
qu’on peut écrire
Dxi+1 = b + (E + F )xi
où        
b a11 0 0 0 0 −a12
b= 1 D= E= , F =
b2 0 a22 −a12 0 0 0

xi+1 = D−1 b + D−1 (E + F )xi

On remarque que
A=D−E−F

14
 =====================================
    
a11 a12 a13 x1 b1
Ax = a121 a22 a23  x2  = b2  = b
a131 a32 a33 x3 b3

 a11 x1 + a12 x2 + a13 x3 = b1
a21 x1 + a22 x2 + a23 x3 = b2
a31 x1 + a32 x2 + a33 x3 = b3

 0
x1
0
x = x02  donné : On calcule xi+1 pour i = 0, ...

x03

a11 xi+1 = b1 − a12 xi2 − a13 xi3



 1



a22 xi+1
2 = b2 − a21 xi1 − a23 xi3 (2.11)




a33 xi+1 = b3 − a31 xi1 − a32 xi2

3

‘  0
0 x1
Etape 0 : x = donné :
x02
Etape 1 
2x11 + 3x02 = 1
sa

x01 − 3x12 = 2
Ca
NS

2x11 = 1 − 3x02 , x11 = 12 (1 − 3x02 )


-E

x01 − 3x12 = 2
ri
Am

2x11 = 1 − 3x02 , x11 = 12 (1 − 3x02 )



x11 − 3x12 = 2
El
H.

15
2.3.2 Cadre général
On écrit la la matrice A sous la forme A = M − N avec M inversible.

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

x = F (x)

C’est à dire que x est un point fixe de l’application F . On lance alors une itération de point fixe. On donne x0
quelconque et on calcule
xk+1 = M −1 b + M −1 N xk = B + Gxk = F (xk )

x0

= donnée quelconque,
k+1 (2.12)
x = B + Gxk , k = 0, 1, ...
avec
B = M −1 b et G = M −1 N

La solution exacte x̄ vérifie Ax̄ = b et donc

x̄ = B + Gx̄ (2.13)

(2.12) et (2.13) donnent

xk+1 − x̄ = G(xk − x̄)

sa
Ca

c’est à dire
NS

xk+1 − x̄ = G2 (xk−1 − x̄)

-E
ri
Am

et encore
xk − x̄ = Gk (x0 − x̄)
El
H.

 k     
x − x̄ ≤ Gk  x0 − x̄

On choisit G (et donc M et N ) de sorte que la suite (xj )j converge vers la solution exacte x̄.

G  ≤ ||G||k
 k 

x − x̄ ≤ ||G||k x0 − x̄
 k   

Théorème 2.3.1. Les énoncés suivants sont équivalents :

1. la méthode itérative (2.12) converge pour tous les x0 ∈ Rn
2. le rayon spectral de G est strictement inférieur à 1, i.e. ρ(G) < 1,
3. pour au moins une norme matricielle subordonnée, on a ||G|| < 1.

ρ(G) = max {|λ| , λ valeur propre de G}

16
2.3.3 Méthode de Jacobi
Définition 2.3.2. La méthode de Jacobi correspond à la décomposition

A = D − (E + F ),

c’est dire M = D et N = E + F . où :
 
−F
A= D =D−E−F
−E

G = J = D−1 (E + F )

x0

= donné quelconque,
k+1 (2.14)
x = B + J xk , k = 0, 1, ...

Définition 2.3.3. Une matrice carrée d’ordre n, A = (aij )ij est dite à diagonale dominante si
X
|aii | > |aij | ∀i = 1, ..., n
j6=i

ou X
|aii | > |aji | ∀i = 1, ..., n
sa
Ca

j6=i
NS

Exemple 2.3.4.
-E

 
a11 a12 a13
ri

A = a21
 a22 a23 
Am

a31 a32 a33

El

     
a11 0 0 0 0 0 0 −a12 −a13
H.

D=  0 a22 0 , E = −a21
  0 0  , F = 0 0 −a23 
0 0 a33 −a31 −a32 0 0 0 0

Théorème 2.3.5. Si une matrice est à diagonale dominante alors la méthode de Jacobi converge pour tout
x0 ∈ R n .

La méthode de Jacobi se programme comme suit :

 0

 x donné quelconque, k = 0, 1, ..
X
aij xkj

bi − (2.15)
j6=i
 xk+1


i = , i = 1, ..., n
aii

17
2.3.4 Méthode de Gauss Seidel
Si on écrit la matrice du système sous la forme A = (D − E) − F = M − N alors on obtient
 0
x = donné quelconque,
k+1 (2.16)
x = B + L1 xk , k = 0, 1, ...
avec
B = (D − E)−1 b , L1 = (D − E)−1 F
qui est la méthode de Gauss-Seidel. Elle s’écrit
 0

 x donné quelconque, k = 0, 1, ...
X X
aij xk+1 aij xkj

bi − j − (2.17)
j<i j>i
 xk+1


i = , i = 1, ..., n
aii

2.3.5 Relaxation, SOR

Pour tout ω > 0 on décompose la matrice A comme suit :
   
D 1−ω
A= −E − F + D
ω ω sa
 −1  −1  
D D 1−ω
Ca

B= −E b, Lω = −E F+ D
ω ω ω
NS
-E

 0
x = donné quelconque,
k+1 (2.18)
= B + Lω xk , k = 0, 1, ...
ri

x
Am
El

 0
x donné quelconque, 
k = 0, 1, 2, ...
H.


 

X X
k+1


k+1 k ω 
xi = (1 − ω)xi + aii bi − aij xj − aij xkj  , i = 1, ..., n

j<i j>i
(2.19)

Résumé :
Nom de la
méthode A=M −N M −1 N description
Jacobi A = D − (E + F ) J = D−1 (E + F ) Dxk+1 = (E + F )xk + b
Gauss-
Seidel A = (D − E) − F L1 = (D − E)−1 F (D − E)xk+1 = F xk + b
A= D


ω
− E
−
−1
F + 1−ω D 1−ω D 1−ω




Relaxation ω
D Lω = ω
−E ω
D +F ω
− F xk+1 = ω
D + F xk + b

18
Amusez vous en faisant des mathématiques :
Pour se débarrasser d’un importun qui vient de l’aborder,
une femme le prévient :
Je suis mariée et mère de quatre enfants...
L’homme répondit étrangement :
Quels sont le produit et la somme de leurs âges ?
Interloquée, après un rapide calcul mental, la femme répondit :
126 et la somme est justement le numéro de la maison en face !
L’homme réfléchit un instant avant de répondre :
Je ne trouve pas leurs âges.
La femme, prise au jeu : sa
Le plus petit ne parle pas encore.
Ca
NS

L’homme :
-E
ri

Maintenant, je sais.
Am
El

Question : Dire comment il a su et donner les âges des

H.

quatre enfants.
a1 1 1 1 1 1 1 1 1 1 1 2
a2 1 1 1 1 1 1 2 2 3 3 3
a3 1 2 3 6 7 9 3 7 3 6 3
a4 126 63 42 21 18 14 21 9 14 7 7
S 129 67 47 29 27 25 27 19 21 17 15

19
2.3.6 Convergence des méthodes de Jacobi, Gauss-Seidel et SOR
On rappelle le résultat important suivant :
Théorème 2.3.6. Soit A ∈ Mn×n (R) symétrique, et soit A = M − N une décomposition de
A telle que M est inversible.
Si la matrice symétrique M ∗ + N est définie positive, alors

ρ(M −1 N ) < 1.

Démonstration. M ∗ + N est symétrique :

(M ∗ + N )∗ = ((A + N )∗ + N )∗ = (A∗ + N ∗ + N )∗ = A∗ + N ∗ + N = M ∗ + N

On considère la norme suivante (c’est une norme puisque la matrice A est définie positive,
exercice)
p
||x||A = (x, Ax), ∀x ∈ Rn norme ?

 −1   −1
M N  = M (M − A) = I − M −1 A = sup (I − M −1 A)x
    
A
||x||A =1
sa
Ca

Posons M −1 Ax = y, on évalue ||x − y||A . Montrer que (exercice)

NS
-E

||x − y||2A = 1 − (y, (M ∗ + N )y)

ri
Am

et donc
El

||x − y||2A < 1

H.

B matrice définie positive

(Bx, x) > 0, ∀x 6= 0
x ∈ SA (0, 1) −→ (I − M −1 A)x
 
A
est continue, sur un compact, elle atteint sa borne supérieure. On en déduit donc que
 −1 
M N  < 1
A

et que
ρ(M −1 N ) < 1.

Théorème 2.3.7. Si la matrice A est symétrique définie positive, la méthode de relaxation

converge si 0 < ω < 2. (Condition suffisante).
Démonstration.
E ∗ = F, F ∗ = E
aii > 0, ∀i = 1, ..., n

20
 (Aei , ei ) = aii > 0.
D
− E − F + 1−ω . A étant symétrique alors E ∗ = F .



A=M −N = ω ω D
   
∗ D 1−ω 2−ω
M +N = −F + F + D = D.
ω ω ω
— La matrice D est définie positive :
(Aei , ei ) = aii > 0.
— M ∗ + N est définie positive si et seulement si ω ∈ ]0, 2[.
ω ∈ ]0, 2[ =⇒ M ∗ + N Déf-Pos =⇒ ρ(Lω ) < 1 =⇒ la méthode de relaxation converge.
On en déduit que la méthode de Gauss-Seidel converge puisqu’elle correspond au cas ω = 1.
Théorème 2.3.8. ρ(Lω ) ≥ |ω − 1| ω 6= 0.
La méthode de relaxation ne peut converger que pour ω ∈ ]0, 2[.
1
Démonstration. Si B det(AB) = det(A) det(B). Si B est inversible, det(B −1 ) = .
det(B)
 −1  
D 1−ω
Lω = −E D+F
ω ω
sa
Ca

Alors
NS

det 1−ω 1−ω

D + F det D
-E

det(Lω ) = ω
D

= ω

D
= (1 − ω)n
det ω − E det ω
ri
Am

D’autre part le déterminant d’une matrice est égal au produit des ses valeurs propres :
El
H.

Y
λi (Lω ) = (1 − ω)n .
i=1,n

D’où
|1 − ω|n ≤ ρ (Lω )n
C’est à dire
|1 − ω| ≤ ρ (Lω )
Si, donc |1 − ω| ≥ 1, c’est à dire :

1 − ω ≤ −1 ⇐⇒ 2 ≤ ω

ou

1 − ω ≥ 1 ⇐⇒ ω ≤ 0
ρ (Lω ) ≥ 1 et la méthode sera donc divergence.
SOR converge si et seulement si 0 < ω < 2.
Pour la méthode de Jacobi on sait que

21
Exercice 2.3.9. Soit A une matrice tridiagonale :
 
a1 c1
b a c 
 2 2 2 

 b3 a3 c3 


 b 4 a4 a4 

A= . . .  ∈ Mn×n (R)
 
. . .
 
 
. . .
 
 
 
 bn−1 an−1 cn−1 
bn an

Pour µ 6= 0 on pose
 
a1 µ−1 c1
µb −1
 2 a2 µ c2


−1

 µb3 a3 µ c3 

−1
µb4 a4 µ c 4
 
 
A(µ) =  . . .
 

. . .
 
sa
 
Ca

 
 . . . 
NS

µbn−1 an−1 µ−1 cn−1 

 

-E

µbn an
ri
Am

On pose
El
H.

 
µ

 µ2 


 µ3 

µ4
 
 
Q(µ) =  .
 

.
 
 
 
 . 
µn−1
 
 
µn
1. Montrer que
A(µ) = Q(µ)A(1) (Q(µ))−1
2. En déduire que
det A(µ) = det A(1), ∀µ 6= 0 (2.20)
3. Les valeurs propres de la matrice de Jacobi J = D−1 (E + F ) sont les zéros du polynôme

pJ (λ) = det(D−1 (E + F ) − λI)

22
 montrer que ce sont aussi les zéros du polynôme

qJ (λ) = det(λD − E − F ) = det(−D)pJ (λ)

4. Les valeurs propres de L1 = (D − E)−1 F de la méthode de Gauss-Seidel sont les zéros du

polynôme
pL1 (λ) = det((D − E)−1 F − λI)
Montrer que ce sont aussi les zéros du polynôme

qL1 (λ) = det(λD − λE − F ) = det(E − D)pL1 (λ)

5. En utilisant (2.20) avec µ = λ, montrer que

qL1 (λ2 ) = det(λ2 D − λE − λF ) = λn qJ (λ)

6. Montrer que
sa
ρ(L1 ) = ρ(J )2
Ca
NS
-E

En déduire que la méthode de Jacobi et la méthode de Gauss-Seidel convergent ou divergent en

ri

même temps. Et que, si elles convergent, Gauss-Seidel est plus rapide.

Am
El
H.

Théorème 2.3.10. Soit A une matrice tridiagonale telle que toutes les valeurs propres de
la matrice de Jacobi J soient réelles.
Alors la méthode de Jacobi, et la méthode de relaxation convergent ou divergent simultanément ;
lorsqu’elles convergent, la fonction ω ∈ ]0, 2[ −→ ρ(Lω ) a l’allure de la figure 2.2.
Démonstration. Voir Ciarlet [1], pages 106-109.

23
 Figure 2.2 – Allure de ρ(Lω ) sa
2.4 Notions sur les éléments finis
Ca
NS
-E

−u00 (x) = f (x) dans ]0, 1[


ri

(2.21)
Am

u(0) = u(1) = 0
El

− u00 (x)v(x) = f (x)v(x) dans ]0, 1[

H.

(2.22)

Z 1 Z 1
00
− u (x)v(x)dx = f (x)v(x)dx, ∀v ∈ C 1 (I) (2.23)
0 0
Une intégration par parties en imposant que v(0) = v(1) = 0 :
Trouver une fonction u vérifiant :
Z 1 Z 1
0 0
u (x)v (x)dx = f (x)v(x)dx, ∀v ∈ C 1 (I). (2.24)
0 0

0 = x0 < x1 < ....xi < .... < xn+1 = 1, Ki = [xi , xi+1 ], i = 0, ..., n.
On construit une suite de sous-espace Vh de dimension finies tels que lim Vh = V (Vh1 ⊂ Vh2
h→0
pour h2 ≤ h1 ). On cherche alors uh ∈ Vh telle que
Z 1 Z 1
u0h (x)vh0 (x)dx = f (x)vh (x)dx, ∀vh ∈ Vh . (2.25)
0 0
en espérant que lorsque h tend vers 0, uh ’tend’ vers u. C’est la méthode de Galerkin.

24
2.4.1 Éléments finis P1

Vh = v ∈ C 0 (I), v|Ki ∈ P1 (Ki ), i = 0, ..., n, v(0) = v(1) = 0



1. Montrer que Vh est un espace de dimension finie (dim Vh = n).

La famille (φi )i=1,n engendre un sous espace de C 1 (I) de dimension n + 2.
On définit les fonction φi de la manière suivante
 x − xn+1 si x ∈ K

 −x + x1 si x ∈ K

0 n
φ0 (x) = x1 , φn+1 (x) = xn+1 − xn
0 ailleurs 0 ailleurs
et pour i = 1, ..., n 
x − xi−1
si x ∈ Ki−1


 xi − xi−1


φi (x) = −x + xi+1
si x ∈ Ki



 x i+1 − x i
0 ailleurs
sa
φ0 φ1 φi−1 φi φi+1 φn φn+1
Ca
NS

1
-E
ri
Am
El
H.

x0 = 0 xi−2 xi−1 xi xi+1 xi+2 xn xn+1 = 1

Figure 2.3 – Supp(φi ) ∩ Supp(φi+1 ) = Ki Supp(φi ) ∩ Supp(φi−1 ) = Ki−1 ,

φ1 , ..., φn ∈ Vh

X
uh (x) = ui φi (x)
i=1,n
Z 1 X Z 1
ui φ0i vh0 dx = f vh dx, ∀vh ∈ Vh . (2.26)
0 i=1,n 0

25
 X Z 1 Z 1
ui φ0i vh0 dx = f vh dx, ∀vh ∈ Vh . (2.27)
i=1,n 0 0

vh = φj , j = 1, ..., n
X Z 1 Z 1
ui φ0i φ0j dx = f φj dx, ∀j = 1, ..., n. (2.28)
i=1,n 0 0

On pose
Z 1 Z xj
aij = φ0i φ0j dx, bj = f φj dx, pour i, j = 1, ..., n
0 xj−1
X
aij ui = bj , ∀j = 1, ..., n. (2.29)
i=1,n

i = 1, ..., n
x − xi−1


 si x ∈ Ki−1
h

sa

φi (x) = −x + xi+1
Ca

si x ∈ Ki
 h
NS



0 ailleurs

-E

i = 1, ..., n
ri
Am

1

 dans Ki−1
El


 h

H.

φ0i (x) = 1
− dans Ki
h



0 ailleurs


donc

2 1
, ai,i+1 = − = ai−1,i , aij = 0 ailleurs
aii =
h h
Et donc le système à résoudre est
    
2 −1 u1 b1
−1 2 −1  u   b 
  2   2 

 −1 2 −1  u   b 
 3   3 
−1 2 −1 u4   b4 
    
1  
. . .   ..  =  .. 
   
h

. . .   ..   .. 
   

. . .   ..   .. 
    

−1 2 −1 un−1  bn−1 
    

−1 2 un bn

26
2.5 Méthodes Numériques de résolution des systèmes non linaires
On se donne g ∈ C(Rn , Rn ) et on cherche x ∈ Rn solution de :

x ∈ Rn , g(x) = 0 (2.30)
Lorsque f (x) = Ax−b, avec A ∈ Mn×n (R), le problème revient à résoudre un système linéaire.

2.5.1 Rappels et notations de calcul différentiel

Définition 2.5.1. (Application différentiable). Soient E et F des espaces vectoriels normés,
f une application de E dans F et x ∈ E. On rappelle que f est différentiable en x s’il existe
T x ∈ L(E, F ) (où L(E, F ) est l’ensemble des applications linéaires de E dans F ) telle que
f (x + h) = f (x) + T x(h) + ||h||E ε(h) avec ε(h) → 0quandh → 0. (2.31)
L’application T x est alors unique et on note Df (x) = T x ∈ L(E, F ) la différentielle de f
au point x. Si f est différentiable en tout point de E, alors on appelle différentielle de f
l’application Df : E → L(E, F ) qui à x ∈ E associe l’application linéaire Df (x) de E dans
F .
sa
Ca

Remarquons que si f est une application linéaire de E dans F alors, f est différentiable et
NS

Df = f .
-E

En dimension 1 (E = F = R), si f est différentiable alors Df (x) = f 0 (x).

ri
Am

Pour E =  R3 , F
= R
2
El
H.

x1  2 3

3 x 1 + x2 + x 3
Pour x = x2  ∈ R on associe f (x) = ∈ R2
3x1 + x2
x3
 
h1
alors pour h = h2  ∈ R3
h
3
(x1 + h1 )2 + (x2 + h2 ) + (x3 + h3 )3 2x1 h1 + h2 + 3x23 h3
  
f (x + h) = ' f (x) +
3(x1 + h1 ) + x2 + h2 3h1 + h2
 
 2
 h1
2x1 1 3x3  
f (x + h) − f (x) ' h2
3 1 0
h3
2x1 1 3x23
 
Df (x) = Jf (x) = ∈ M2×3 (R)
3 1 0
Matrice à 2 lignes (dim F ) et 3 colonnes (dim E).
Pour E = Rn et F = R
 
∂f ∂f ∂f
Jf (x) = ∂x 1 ∂x 2
.. .. ∂xn ∈ M1×n (R)

27
On note le gradient de f en un point x ∈ Rn par :
∇f (x) = Jf (x)t
alors
X ∂f (x)
Jf (x)h = ∇f (x).h = hi
i=1,n
∂x i

Si E = F = Rn
  
x1 f1 (x)
 x2   f2 (x) 
 ∈ Rn −→  ..  ∈ Rn
   
f :x= ..
   
 ..   .. 
xn fn (x)
alors  
∂f1 ∂f1 ∂f1
∂x1 ∂x2 .. .. ∂xn
 ∂f2 ∂f2 ∂f2 

 ∂x1 ∂x2 .. .. 
∂xn 
Jf (x) =   ∈ M(R)n×n .
 .. .. .. .. 
 .. .. .. .. 
 
∂fn ∂fn ∂fn
.. ..
sa
∂x1 ∂x2 ∂xn
Ca
NS

2.5.2 Méthodes du point fixe

-E
ri

Résoudre g(x) = 0 revient à résoudre x − g(x) = x, c’est à dire que la solution x̄ de l’équation
Am

g(x) = 0 est le point fixe de la fonction f (x) = x − g(x).

El
H.

Théorème 2.5.2. (Point fixe). Soit (E, d) un espace métrique complet, et f : E → E une
fonction strictement contractante, c’est–à–dire :
∃k ∈]0, 1[ , d(f (x), f (y)) ≤ kd(x, y), ∀x, y ∈ E.
Alors il existe un unique point fixe x̄ ∈ E qui vérifie f (x̄) = x̄. De plus si x0 ∈ E, et
xk+1 = f (xk ) , ∀k ≥ 0, alors xk → x̄ quand k → ∞.
Démonstration.
d(xn+1 , xn ) = d(f (xn ), f (xn−1 )) ≤ kd(xn , xn−1 ) ≤ .... ≤ k n d(x1 , x0 )
Pour p ≥ 1 l’inégalité triangulaire donne :
p−1
X p−1
X
d(xn+p, xn) ≤ d(xn+p−i, xn+p−i−1) ≤ k n+p−i−1d(x1, x0)
i=0
i=0
= k n k p−1 + k p−2 + ... + k + 1 d(x1, x0)
p
n1 − k
=k d(x1, x0)
1−k
28
La suite (xn )n est donc de Cauchy. Comme l’espace est complet elle converge. Soit x̄ sa limite.
On a
xn+1 = f (xn ), ∀n ∈ N
Donc à la limite et puisque f est continue on aura
f (x̄) = x̄
d(f (x̄), f (ȳ)) ≤ kd(x̄, ȳ),

d(x̄, ȳ) ≤ kd(x̄, ȳ)

n’est possible que si x̄ = ȳ car k < 1.

Exercice 2.5.3. Soit (E, d) un espace métrique complet, et f : E → E. Montrer que s’il
existe K ∈ N tel que f K = f of of o...of soit contracte alors f admet un point fixe.
| {z }
K f ois

Exercice 2.5.4. (Point fixe de contraction avec relaxation)

Soit g : Rn → Rn telle que
1. g est lipschitzienne, c’est à dire, ∃M > 0 tel que :
sa

|g(x) − g(y)| ≤ M |x − y| , ∀x, y ∈ Rn

Ca
NS

2. Il existe ∃α > 0 tel que :

-E

(g(x) − g(y), x − y) ≥ α |x − y|2 , ∀x, y ∈ Rn

ri
Am

 
2α
El

Montrer que pour tout ω ∈ 0, 2 , la fonction fω (x) = x − ωg(x) est strictement contrac-
M
H.

tante.
g(x) = Ax − b
|g(x) − g(y)| = |A(x − y)| ≤ ||A|| |x − y|

(Ax − Ay, x − y) ≥ α |x − y|2

(Az, z) ≥ α |z|2 ∀z ∈ Rn
Conclure.
Pour résoudre g(x) = 0 on pose f (x) = x − g(x), le procédé s’écrit alors
 0
x quelconque
(2.32)
xk+1 = xk − ωg(xk ), k = 0, 1, ....
Qui est équivalent à (exercice) :
 0
x quelconque
k+1
y = f (xk ) (2.33)
 k+1
x = ωy k+1 + (1 − ω)xk , k = 0, 1, ....

29
2.5.3 Méthode de Newton en dimension 1

g(x) = 0

x0 quelconque
0 g(x1 ) − g(x0 )
0
g (x ) '
x1 − x0

1 g(x1 ) − g(x0 )
0
x −x '
g 0 (x0 )

1 g(x1 ) − g(x0 )
0
x 'x +
g 0 (x0 )

1 g(x0 )
0
x =x − 0 0
g (x )

0 n+1 g(xn )
x qque , x n
= x − 0 n = f (xn )
sa

g (x )
Ca
NS

g(x)
-E

f (x) = x −
g 0 (x)
ri
Am

Convergence :
El
H.

0 g 0 (x)2 − g(x)g 00 (x) g(x)g 00 (x)

f (x) = 1 − =
g 0 (x)2 g 0 (x)2
Au point fixe x̄
0 g(x̄)g 00 (x̄)
f (x̄) = =0
g 0 (x̄)2
f 0 étant continue il existe un intervalle fermé autour de x̄, I dans lequel

|f 0 (x)| < 1

sup |f 0 (x)| = k < 1

x∈I

Dans I
|f (x) − f (y)| = |f 0 (θxy )(x − y)| ≤ k |x − y|

f est contractante dans I.

30
2.5.4 Point fixe de monotonie
L’approximation de nombreux problèmes naturels (physique, biologique, économique, bioma-
thématique ...) se ramènent à la résolution de problèmes non linéaires du genre : Ax = R(x)
où A est une matrice carrée d’ordre n inversible, et R ∈ C(Rn , Rn ).
On peut les écrire sous la forme x = A−1 R(x) et appliquer l’algorithme de point fixe sur la
fonction f : x −→ A−1 R(x), ce qui donne comme itération :

x0 quelconque, xk+1 = A−1 R(xk ).

Si on pratique un point fixe avec relaxation, dont le paramètre de relaxation ω > 0, alors
l’itération s’écrit :  0
x quelconque
x̃ k+1
= A−1 R(xk ), (2.34)
 k+1
x = ωx̃k+1 + (1 − ω)xk .
Si la matrice A possède une propriété dite “de monotonie”, on peut montrer la convergence de
l’algorithme du point fixe :
Théorème 2.5.5. (Point fixe de monotonie). Soient A ∈ Mn (R) et R ∈ C(Rn , Rn ). On
suppose que :
sa
Ca

1. la matrice A est une matrice d’inverse positive, ou IP –matrice voir exercice 8), c.à.d. que
A est inversible et tous les coefficients de A−1 sont positifs ou nuls, ce qui est équivalent
NS
-E

à dire que :
ri

Ax ≥ 0 =⇒ x ≥ 0,
Am

au sens composante par composante, c’est-à-dire :

El
H.

(Ax)i ≥ 0, ∀i = 1, ..., n =⇒ xi ≥ 0, ∀i = 1, ..., n.

2. R est monotone, c.à.d. que si x ≥ y (composante par composante) alors R(x) ≥ R(y)
(composante par composante).
3. 0 est une sous-solution du problème, c’est-à-dire que 0 ≤ R(0) et il existe x̃ ∈ Rn ; x̃ ≥ 0
tel que x̃ est une sur-solution du problème, c’est-à-dire que Ax̃ ≥ R(x̃).
On pose x0 = 0 et Axk+1 = R(xk ). On a alors :
1. 0 ≤ xk ≤ x̃, ∀k ∈ N,
2. xk+1 ≥ xk , ∀k ∈ N,
3. xk −→ x̃ quand k −→ +∞ et Ax̃ = R(x̃).

31
2.6 Interpolation et Approximation

sa
Ca
NS
-E
ri
Am
El
H.

32
Bibliographie

[1] P. G. CIARLET, Introduction à l’analyse numérique matricielle et à l’optimisation. Col-

lection mathématiques appliquées pour la maîtrise, Masso, 1982.

sa
Ca
NS
-E
ri
Am
El
H.

33