Module : Analyse Numériques & Algorithmique

Filière SMP : S3
Mohammed MOUSSA

Université Ibn Tofail

19 octobre 2015
 Introduction
Méthodes directes
Méthodes Itératives

Programme

Programme
1 Chapitre 1 : Systèmes linéaires
2 Chapitre 2 Zéros de fonctions non-linéaires.
3 Chapitre 3 Approximation polynômiale.
4 Chapitre 4 Intégration numérique.

M. MOUSSA An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives

Introduction

Système Linéaire
On appelle système linéaire d'ordre n (n entier positif), une expression de
la forme
Ax = b;
où A = (aij ), 1 ≤ i; j ≤ n, désigne une matrice de taille n × n de
nombres réels ou complexes, b = (bi ),1 ≤ i ≤ n, un vecteur colonne réel
ou complexe et x = (xi ),1 ≤ i ≤ n, est le vecteur des inconnues du
système. La relation précédente équivaut aux équations
n
X
aij xj = bi; i = 1; . . . ; n
j=1

M. MOUSSA An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives

Introduction
Système Linéaire
La matrice A est dite régulière (ou non singulière) si detA 6= 0 ; on a
existence et unicité de la solution x (pour n'importe quel vecteur b donné)
si et seulement si la matrice associée au système linéaire est régulière.
Théoriquement, si A est non singulière, la solution est donnée par la
formule de Cramer :
det(Ai)
xi = ; i = 1; . . . ; n,
detA
où Ai est la matrice obtenue en replaçant la i-ème colonne de A par le
vecteur b. Cependant l'application de cette formule est inacceptable pour
la résolution pratique des systèmes, car son coût est de l'ordre de (n + 1)!
"oating-point operations" (ops).

M. MOUSSA An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives

Méthodes directes

Méthode A = LU
Pour résoudre Ax = b, on cherche à écrire A = LU où
1 L est une matrice triangulaire inférieure avec des 1 sur la diagonale,
2 U est une matrice triangulaire supérieure.
La résolution de Ax = b est alors ramenée aux résolutions successives des
systèmes échelonnés Ly = b et U x = y .

M. MOUSSA An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives

Méthodes directes

Résolution des systèmes triangulaires.

Dénition 2.1
Une matrice A = (aij ) est triangulaire supérieure si

aij = 0, ∀i, j tel que 1 ≤ j < i ≤ n

et triangulaire inférieure si

aij = 0, ∀i, j tel que 1 ≤ i < j ≤ n

Suivant ces cas, le système à résoudre est dit système triangulaire

supérieur ou inférieur.

M. MOUSSA An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives

Méthodes directes
Résolution des systèmes triangulaires.
Si la matrice
QnA est régulière et triangulaire alors, comme
det(A) = i=1 aii , on en déduit que aii 6= 0, pour tout i = 1, . . . , n.
Si A est triangulaire inférieure on a
x1 = b1 /a11 ;

et pour i = 2, 3, . . . , n
 
i−1
1  X
xi = bi − aij xj 
aii j=1

Cet algorithme est appelé méthode de descente.

M. MOUSSA An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives

Méthodes directes
Résolution des systèmes triangulaires.
Si A est triangulaire supérieure on a
xn = bn /ann ;

et pour i = n − 1, n − 2, . . . , 2, 1
 
n
1  X
xi = bi − aij xj 
aii j=i+1

Cet algorithme est appelé méthode de remontée.

Le nombre de multiplications et de divisions nécessaires dans cet
algorithme est de n(n + 1)/2 et le nombre d'additions et de soustraction
est de n(n − 1)/2, donc l'algorithme nécessite de n2 ops.

M. MOUSSA An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives

Méthodes directes

Factorisation LU.
C'est la méthode la plus préférée pour la résolution de systèmes linéaires
comportant une matrice A dense, sans structure et sans quantication
particulière.
On vient de voir qu'il est très simple de résoudre des systèmes
triangulaires. La transformation du système original en un système
triangulaire se fait en choisissant des combinaisons linéaires appropriées
des équations du système.

M. MOUSSA An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives

Méthodes directes
Factorisation LU.
Exemple 1 Soit le système

3x1 + 5x2 = 9
6x1 + 7x2 = 4

si l'on multiplie la première équation par 2 et que l'on la soustrait de la

deuxième on obtient

3x1 + 5x2 = 9
− 3x2 = −14

Cette procédure s'appelle élimination de Gauss . Dans la suite on

donnera à ce procédé une formulation matricielle, notamment en termes
de factorisation d'une matrice. On présentera un algorithme qui factorise
une matrice donnée A en une matrice triangulaire inférieure L et une
matrice triangulaire supérieure U , tel que A = LU .
M. MOUSSA An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives

Méthodes directes
Méthode d'élimination de Gauss et décomposition LU.
Exemple 2 Pour la matrice A correspondant à l'exemple précédent la
factorisation A = LU est :
    
3 5 1 0 3 5
=
6 7 2 1 0 −3

La solution du système original Ax = b est alors obtenue en résolvant

deux systèmes triangulaires successivement. On remplace A par sa
factorisation
Ax = LU x = Ly = b
et l'on cherche la solution y à partir du système triangulaire inférieur
Ly = b, puis la solution de x à partir du système triangulaire supérieur
U x = y.

M. MOUSSA An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives

Méthodes directes

Formalisation de l'élimination de Gauss.

il s'agit de formaliser une procédure qui transforme une matrice en une
matrice triangulaire supérieure en éliminant, colonne après colonne, les
éléments non nuls en dessous de la diagonale comme illustré dans
l'exemple suivant. Soit la matrice
 
1 4 7
A= 2 5 8 
3 6 10

que l'on veut transformer en une matrice triangulaire supérieure. On

obtient cette forme en deux étapes.

M. MOUSSA An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives

Méthodes directes

Formalisation de l'élimination de Gauss.

Lors de la première étape on soustrait 2 fois la première ligne de la
deuxième ligne et 3 fois la première ligne de la troisième ligne, ce qui
peut être
 obtenu, en  multipliant la matrice donnée par la matrice
1 0 0
L1 =  −2 1 0  pour obtenir
−3 0 1
    
1 0 0 1 4 7 1 4 7
 −2 1 0  2 5 8 = 0 −3 −6 
−3 0 1 3 6 10 0 −6 −11

M. MOUSSA An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives

Méthodes directes

Formalisation de l'élimination de Gauss.

Lors de la deuxième étape on transforme cette nouvelle matrice en
soustrayant 2 fois la deuxième ligne de la troisième ligne ce qui peut être
obtenu,
 en multipliant
 la matrice donnée par la matrice
1 0 0
L2  0 1 0  pour obtenir
0 −2 1
    
1 0 0 1 4 7 1 4 7
 0 1 0  0 −3 −6  =  0 −3 −6 
0 −2 1 0 −6 −11 0 0 1

M. MOUSSA An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives

Méthodes directes

Formalisation de l'élimination de Gauss.

Procédés LU
Nous pouvons résumé le procédé de factorisation comme suit,
     
1 0 0 1 0 0 1 4 7 1 4 7
 0 1 0   −2 1 0  2 5 8 = 0 −3 −6 
0 −2 1 −3 0 1 3 6 10 0 0 1

On a alors
L2 L1 A = U ⇒ A = (L2 L1 )−1 U = L−1 −1
1 L2 U = LU

M. MOUSSA An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives

Méthodes directes
Formalisation de l'élimination de Gauss.
Procédés LU
Or    
1 0 0 1 0 0
L1 =  −2 1 0  ⇒ L−1
1 =
 2 1 0 
−3 0 1 3 0 1
et    
1 0 0 1 0 0
L2 =  0 1 0  ⇒ L−1
2 =  0 1 0 
0 −2 1 0 2 1
En eet ;
    
1 0 0 1 0 0 1 0 0
 −2 1 0  2 1 0 = 0 1 0 
−3 0 1 3 0 1 0 0 1

M. MOUSSA An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives

Méthodes directes

Formalisation de l'élimination de Gauss.

Procédés LU
De plus,
    
1 0 0 1 0 0 1 0 0
L = L−1 −1
1 L2 = 2 1 0  0 1 0 = 2 1 0 
3 0 1 0 2 1 3 2 1

Nous avons donc factoriser A en LU par

    
1 4 7 1 0 0 1 4 7
A= 2 5 8 = 2 1 0  0 −3 −6 
3 6 10 3 2 1 0 0 1

M. MOUSSA An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives

Méthodes directes

Résolution du système
 
1
Résolvons maintenant le système Ax =  3 . On commence par
  6
1
résoudre le système Ly =  3 . Comme L est triangulaire inférieur,
6
on utilise la méthode de la descente, ainsi,
 
 y1 = 1  y1 = 1
y2 = 3 − 2y1 ⇒ y2 = 1
y3 = 6 − 3y1 − 2y2 y3 = 1
 

M. MOUSSA An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives

Méthodes directes
Résolution du système
 
1
nous terminerons par résoudre le système U x =  1 . Comme U est
1
triangulaire supérieur, on utilise la méthode de la remonté, ainsi,

x3 = 1
 10
 x1 = 3
 

 1 7 
x2 = (1 + 6x3 ) = − ⇒ 7
−3 3 x2 = −
 x = 1 − 7x − 4x = 10 3

 


1 3 2
3 x3 = 1

On a bien,  10 
   
1 4 7  3  1
 2 5 8  7 = 3 
 − 
3 6 10 3 6
1
M. MOUSSA An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives

Méthodes directes
Exemple 1. n=4.
 
−2 1 −1 1
 2 0 4 −3 
Soit la matrice A = 
 −4
, alors on a
−1 −12 9 
−2 1 1 −4

1 0 0 0
 1 1 0 0
successivement, L1 =  ,

 −2 0 1 0 
−1 0 0 1
   
−2 1 −1 1 1 0 0 0
 0 1 3 −2  0
 , L2 = 
 1 0 0 
,
A(1) = L1 A =  0 −3 −10 7   0 3 1 0 
0 0 2 −5 0 0 0 1
 
−2 1 −1 1
 0 1 3 −2 
A(2) = L2 A(1) = L2 L1 A =  
 0 0 −1 1 
0 0
M. MOUSSA
2 −5
An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives

Méthodes directes
Exemple 1. n=4.
 
1 0 0 0
 0 1 0 0 
Finalement L3 = 
 0
, par suite
0 1 0 
0 0 2 1 
−2 1 −1 1
 0 1 3 −2 
, et
U = M3 A(2) = L3 L2 L1 A = 
 0 0 1 1 
0 0 0 −3
 
1 0 0 0
 −1 1 0 0 
L= .
 2 −3 1 0 
1 0 −2 1

M. MOUSSA An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives

Méthodes directes

Exemple 1. n=4.
C'est à dire
  
1 0 0 0 −2 1 −1 1
 −1 1 0 0   0 1 3 −2 
A = LU =   
 2 −3 1 0  0 0 1 1 
1 0 −2 1 0 0 0 −3

M. MOUSSA An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives

Méthodes directes

Méthode d'élimination de Gauss et décomposition LU.

Le coût de cette méthode de factorisation est de l'ordre de 2n3 /3 ops.
En fait, pour passer de A(k) à A(k + 1) on modie tous les éléments de
A(k) sauf les premières k lignes et les premières k colonnes, qui ne
changent pas ; pour chaque élément de A(k+1) il faut faire une
multiplication et une soustraction ; on a donc 2(n − k)2 opérations à
faire. Au total, pour fabriquer A(n) il faut
n−1 n−1
X X n(n + 1)(2n + 1) 2n3
2(n − k)2 = 2j 2 = 2 ∼
6 3
k=1 k=1

M. MOUSSA An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives

Condition D'existence
Proposition 2.1
La factorisation LU de la matrice carrée A de taille n par la méthode de
Gauss existe si et seulement si les sous-matrices principales Ai = (ahk ),
h, k = 1, . . . , i sont non-singulières. Cette propriété est satisfaite en
particulier dans les cas qui suivent :
1 A est une matrice symétrique dénie positive ;
2 A est une matrice à diagonale dominante stricte par lignes,
c'est-à-dire pour tout i = 1, . . . , n
n
X
|aii | > |aij |
j=1,j6=i

3 A est une matrice à diagonale dominante stricte par colonnes,

c'est-à-dire pour tout i = 1, . . . , n
n
X
|ajj | > |aij |
M. MOUSSA An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives

Méthodes directes : Décomposition de Cholesky

Décomposition de Choleski RRT .

Soit A une matrice qui admet une décomposition en LU , si en plus, A
est symétrique, c'est à dire A = AT et uii > 0, pour tout 1 ≤ i ≤ n, on
peut écrire la matrice A sous la forme A = LDDT M où D est la matrice
diagonale avec d2ii = uii et M est la matrice triangulaire supérieure dont
les mii = 1 et mij = uij , pour j 6= i. On a alors décomposer A sous la
forme a = RRT car dans ce cas M T = L avec R = LD

M. MOUSSA An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives

Méthodes directes : Décomposition de Cholesky

Décomposition de Choleski : Algorithme.
Étudions l'exemple suivant,
 
1 2 3
A= 2 5 10 
3 10 26

Comme A = RRT , on a alors

  
r11 0 0 r11 r21 r31
A =  r21 r22 0  0 r22 r32 
r31 r32 r33 0 0 r33
2
 
r11 r11 r21 r11 r31
2 2
A =  r11 r21 r11 + r22 r21 r31 + r22 r32 
2 2 2
r11 r31 r21 r31 + r22 r32 r31 + r32 + r33

M. MOUSSA An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives

Méthodes directes : Décomposition de Cholesky

Décomposition de Choleski : Algorithme.
On obtient alors le système échelonné suivant,
 2 

 r11 = 1 
 r11 = 1
r11 r21 = 2 r21 = 2

 


 

r11 r31 = 3 r31 = 3
 
2 2 ⇒

 r21 + r22 = 5 
 r22 = 1
r21 r31 + r22 r32 = 10 r32 = 4

 


 

 2 2 2
r31 + r22 + r33 = 26 r33 = 1


Finalement on a bien,
    
1 2 3 1 2 3 1 0 0
A= 2 5 10  =  0 1 4  2 1 0 
3 10 26 0 0 1 3 4 1

M. MOUSSA An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives

Méthodes Itératives : Méthode de Jacobi

Exemple.
Pour résoudre le système Ax = b, parfois on préfère utiliser des méthodes
itératives (d'approximation) qui consistent à approcher la solution et non
pas de trouver la solution exacte, pour cela on écrit la matrice de la
manière suivante : A = G − H avec G inversible. Le système devient
alors, Ax = b ⇔ Gx = Hx + b ⇔ x = M x + b0 où M = G−1 H et
b0 = G−1 b on est ramené à un problème de point xe. On dénit alors la
suite récurrente xk+1 = M xk + b0 avec x0 choisi de façon arbitraire. Si la
suite converge, la limite est la solution du système.
Dans la pratique, il faudra décomposer A = G − H de façon que la suite
soit convergente et que G−1 se déduisent facilement de G ou plus
simplement que le système Gxk+1 = Hxk + b se résolve simplement. On
choisira pour G une matrice diagonale (Jacobi) ou triangulaire inférieure
Gauss-Seidel

M. MOUSSA An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives

Méthodes Itératives : Méthode de Jacobi

Algorithme de Jacobi
On écrit A = D − E − F où D est la partie diagonale de A, E (resp. F )
la partie triangulaire inférieure (resp. supérieure) de A. On suppose que
tous les aii sont non nuls, donc D est inversible, on choisit G = D et
H = E + F . On a alors alors
M = D−1 (E + F ) = D−1 (D − A) = I − D−1 A. Le calcul eectif se fait
en résolvant directement le système
Dxk+1 = (E + F )xk + b

Soit,
j=n
X
bi − aij xkj
j=1, j6=i
xk+1
i =
aii

M. MOUSSA An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives

Méthodes itératives : Méthode de Jacobi

Exemple.
Soit à résoudre le système suivant,

 3x1 + x2 − x3 = 2
x1 + 5x2 + 2x3 = 17
2x1 − x2 − 6x3 = −18


La matrice est à diagonale strictement dominante donc, la méthode de

Jacobi converge vers la solution du système. Suivant la formule décrite
précédemment, la méthode de Jacobi s'écrit dans ce cas pour la première
itération à partir d'un vecteur x(0) = (0, 0, 0)T : Première itération
donne :
1 2


 x11 = (2 − 0 + 0) =

 3 3
1 17

x12 = (17 − 0 − 0) =
 5 5


 x13 1
= − (−18 − 0 + 0) = 3

6
M. MOUSSA An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives

Méthodes itératives : Méthode de Jacobi

Exemple
La deuxième itération donne :
1 8

2 − 17



 x21 = 5 +3 =

 3 15
1 31

17 − 23 − 2 × 3


x22 = =
 5 15
 1 239
− −18 − 2 × 23 + 17


 x23

= =
6 5 90

M. MOUSSA An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives

Exemple Suite .....

On continue à itérer jusqu'à l'estimation souhaité, par exemple si on
demande à s'arrêter une fois |x −x | < 10−2 on s'arrêtera à la 10 ème
k+1 k

itération (voir tableau ci-dessous) : la solution exacte est (1, 2, 3)

k xk1 xk2 xk3
0 0 0 0
1 0.66667 3.40000 3.00000
2 0.53333 2.06667 2.65556
3 0.86296 2.23111 2.83333
4 0.86741 2.09407 2.91580
5 0.94057 2.06020 2.94012
6 0.95997 2.03583 2.97016
7 0.97811 2.01994 2.98069
8 0.98691 2.01210 2.98938
9 0.99242 2.00686 2.99362
10 0.99558 2.00407 2.99633

M. MOUSSA An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives

Méthodes Itératives : Méthode de Gauss-Seidel

Algorithme de Gauss-Seidel
On écrit A = D + E − F où D est la partie diagonale de A, E (resp. F )
la partie triangulaire inférieure (resp. supérieure) de A. On suppose que
D + E est inversible, on choisit G = D + E et H = F . On a alors alors.
Le calcul eectif se fait en résolvant directement le système
(D + E)xk+1 = F xk + b

Soit, X X
bi − aij xk+1
j − aij xkj
1≤j≤k k+1≤j≤n
xk+1
i =
aii

M. MOUSSA An-Num-S3