Module : Analyse Numériques & Algorithmique

Filière SMP : S3
M. H. EL ALJ

Université Ibn Tofail

12 novembre 2016
 Introduction
Méthodes directes
Méthodes Itératives
Méthodes Itératives
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. H. EL ALJ An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives
Méthodes Itératives
Méthodes Itératives

Introduction
Système Linéaire
On appelle système linéaire d'ordre n (n > 0), l'expression Ax = b; où

 
a11 ... a1j ... ... a1n
.
.
 
 a12 . a2j ... ... a2n 
 
 . . . 
. . . 
. ...

. . 
A = (aij ) = 

 matrice d'ordre n
.
1≤i;j≤n .
 
 ai1 ... aij . ... ain 
 
 . . . . 
. . . . 
 . . . .

an1 ... anj ... ... ann

b = (bi ) , un vecteur colonne et x = (xi ) est le vecteur des inconnues du

1≤i≤n 1≤i≤n
système. La relation précédente équivaut aux équations

n
X
aij xj = bi; i = 1; . . . ; n
j=1M. H. EL ALJ An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives
Méthodes Itératives
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 per seconds" (ops).

M. H. EL ALJ An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives
Méthodes Itératives
Méthodes Itératives

Méthodes directes
Résolution des systèmes triangulaires.

Dénition 1.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. H. EL ALJ An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives
Méthodes Itératives
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. H. EL ALJ An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives
Méthodes Itératives
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. H. EL ALJ An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives
Méthodes Itératives
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. H. EL ALJ An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives
Méthodes Itératives
Méthodes Itératives

Méthodes directes
Résolution du système Lx = y .
on commence par résoudre le système Ly = b
 
1 0 ... ... ... 0    
.. .. y1 b1
. .
 
 l21 1   y2   b2 
.. .. .. ..
  ..   .. 
    
. . . .
 .   . 

 0
Ly =    yi  = 
..
..
   
bi 
. .

li1 ... lii−1 1   ..   .. 
    
.. .. ..  .   . 

. . .

 0 
yn bn
ln1 ... ... ... lnn−1 1

ligne 1 ⇒ y1 = b1 ; X
i−1
ligne i ⇒ yi = (bi − lij yj ) i = 2, . . . , n − 1, n
j=1

Cet algorithme est appelé méthode de descente..

M. H. EL ALJ An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives
Méthodes Itératives
Méthodes Itératives

Méthodes directes
Résolution du système U y = b.
La détermination de y nous permet de résoudre le système U x = y
 
u11 ... u1i ... u1n−1 u1n    
.. .. x1 y1
. . .. ..
 
 0
. .
   
 .. ..
    
 . . uii . . .
   
... uin  x i
 
= y i

 .. .. .. .. .. ..
  
 . . . . . .
   
   
 . ..
    
 ..
  xn−1   yn−1
. un−1n−1 un−1n


xn yn
0 ... ... ... 0 unn

ligne n ⇒ xn = yn /unn ;

ligne i ⇒ xi = u yi − Pnj=i+1 uij xj

1  
i = n − 1, n − 2, . . . , 2, 1
ii
Cet algorithme est appelé méthode de remontée..
M. H. EL ALJ An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives
Méthodes Itératives
Méthodes Itératives

Factorisation LU
Cette méthode est basée sur le procédé de triangularisation de Gauss. A
l'étape 1 : on determine d'abord L1 et on calcul A1 par le produit
matriciel L1 A = A1
  
1 0 ... ... ... 0 a11 ... a1j ... ... a1n
.. ..
. .
  
 −l21 1 0   a21 a2j 
 .. .. .. ..
  .. .. ..
  
 . . . .
 . . .

0 
L1 A =  .. .. ..
.. ..
 
. . . . .
  
 −li1 1   ai1 aij 
 . .. .. ..  . .. ..
  
 .. . . . 0   .. . .


−ln1 0 ... ... 0 1 an1 ... anj ... ... ann
ai1
oú li1 = i = 2, . . . , n de sorte que tous les éléments de la première
a11
colonne en dessous du premier pivot a11 de la matrice A1 soient tous nuls
M. H. EL ALJ An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives
Méthodes Itératives
Méthodes Itératives

Factorisation LU
On construit ainsi les matrices Li et Ai pour i = 1, . . . , k − 1
A l'étape k : on détermine la matrice Lk et on calcule la matrice AK par
le produit matriciel Lk Ak−1 = Ak
  
1 0 ... ... ... 0 a11 ... a1j ... ... a1n
.. .. .. ..
. . . .
  
 0 0  0 
.. ..   ..
..
  
. .  .
. ak−1 ak−1
 
 1 kk ... ... kn

..   ..
..
  
.  .
. ak−1 ak−1
 
 −lk+1k 1 k+1k ... ... k+1n

.. ..  . .. ..
  
. . 0   .. . .
 
 
0 −lnk 1 0 ak−1
nk ... ... ak−1
nn

ak−1
oú lik = ik
i = k + 1, . . . , n de sorte que tous les éléments de la k me
ak−1
kk
colonne en dessous du pivot ak−1 kk de la matrice A soient tous nuls
k

M. H. EL ALJ An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives
Méthodes Itératives
Méthodes Itératives

Factorisation LU
au bout de la n − 1me étape, on trouve la matrice U = An−1
oú U = Ln−1 Ln−2 . . . L2 L1 A
 
a11 ... a1k ... ... a1n
.. ..
. .
 
 0 
 .. ..
 
 . . ak−1 ak−1


U = kk kn
 ..

 .

0 akk+1k+1 akk+1n 
 . .. .. ..
 
 .. . . .


0 ... ... ... 0 an−1
nn

c'est une matrice triangulaire supérieure

M. H. EL ALJ An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives
Méthodes Itératives
Méthodes Itératives

Factorisation LU
de même on détermine la matrice
−1
L = (Ln−1 Ln−2 . . . L2 L1 ) = L−1 −1 −1 −1
1 L2 . . . Ln−2 Ln−1

par  
1 0 ... ... ... 0
.. ..
. .
 
 l21 0 
 .. .. .. ..
 
 . . . .

1 
L= ..

.
 
 lk+11 lk+1k 1 
 . .. ..
 
 .. . .

0 
ln1 ... lnk ... lnn−1 1
oú L est une matrice triangulaire inférieure telle que
ak−1
lik = ik
pour k = 1, . . . , n − 1 et i = k + 1, . . . , n
ak−1
kk
M. H. EL ALJ An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives
Méthodes Itératives
Méthodes Itératives

Méthodes directes
Elimination de Gauss
La procédure d'élimination de Gauss consiste à passer directement d'un
système 0quelconque de la forme Ax = b à un système triangulaire de la
forme A x = b oú A est unematrice  triangulaire supérieure.
0 0

La matrice augmentée Finale A |b est obtenu à partir de la matrice

0 0

augmentée initiale (A|b) par la transformation

 0 0

A |b = (Ln−1 Ln−2 . . . L2 L1 ) (A|b)

ce qui s'écrit également de la forme suivante :

0
A = (Ln−1 Ln−2 . . . L2 L1 ) A = An−1 = U

et 0
b = (Ln−1 Ln−2 . . . L2 L1 ) b
M. H. EL ALJ An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives
Méthodes Itératives
Méthodes Itératives

Méthodes directes
Elimination de Gauss.
Exemple 1 Soit le système

(l1 ) 3x1 + 5x2 = 9
(l2 ) 6x1 + 7x2 = 4

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

deuxième : l2 ← l2 − 2l1 et on obtient

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

la solution est donnée par

14

x2 = 3
1 −43
x1 = 3 (9 − 5x2 ) = 9

M. H. EL ALJ An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives
Méthodes Itératives
Méthodes Itératives

Méthodes directes
Méthode d'élimination de Gauss et décomposition LU.
Cette procédure décrite plus haut s'appelle élimination de Gauss .
La factorisation A = LU de l'exemple précédent est :
    
3 5 1 0 3 5
A= = = LU
6 7 2 1 0 −3

en eet :

avec l21 = aa21 et

   
1 0 1 0
L1 = =
−l21 1 −2 1 11
    
1 0 3 5 3 5
A1 = L1 A = = =U
−2 1 6 7 0 −3

puisque
     
1 0 1 0 1 0 1 0
L = L−1
1 = 2 1 2 1 −2 1 0 1
M. H. EL ALJ An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives
Méthodes Itératives
Méthodes Itératives

Méthodes directes
Décomposition LU.
La solution du système original Ax = b est alors obtenue en résolvant
successivement les deux systèmes triangulaires.
On remplace A par sa factorisation LU
Ax = LU x = Ly = b

et l'on cherche tout d'abord y à partir du système triangulaire inférieur

Ly = b, qui s'écrit :

soit
     
1 0 y1 9 y1 + = 9
=
2 1 y2 4 2y1 + y2 = 4

qui admet pour solution


y1 = 9
y2 = (4 − 2y1 ) = −14
M. H. EL ALJ An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives
Méthodes Itératives
Méthodes Itératives

Méthodes directes
Décomposition LU.
Après de détermination de y , on cherche la solution de x à partir du
système triangulaire supérieur U x = y qui s'écrit :

soit
     
3 5 x1 y1 3x1 + 5x2 = 9
=
0 −3 x2 y2 − 3x2 = −14

qui admet pour solution

 
 x2 14
=

3 
1 −43 
 x1
 = (9 − 5y2 ) =
3 9
et on vérie que
−43
 
   
3 5  9  9
Ax =  14  =
6 7 4
M. H. EL ALJ 3An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives
Méthodes Itératives
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. H. EL ALJ An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives
Méthodes Itératives
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
On pose L1 =  −2 1 0  de sorte que
−3 0 1
    
1 0 0 1 4 7 1 4 7
L1 A =  −2 1 0   2 5 8 = 0 −3 −6  = A1
−3 0 1 3 6 10 0 −6 −11

et que dans la matrice A1 = L1 A, transformée de A par le produit

matriciel à gauche par L1 , dispose de zéros sous son 1er pivot a111 = 1

M. H. EL ALJ An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives
Méthodes Itératives
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 que l'on
obtient, en multipliant la matrice A1 par la matrice
 
1 0 0
L2  0 1 0  , ainsi
0 −2 1
    
1 0 0 1 4 7 1 4 7
L 2 A1 =  0 1 0   0 −3 −6  =  0 −3 −6 
0 −2 1 0 −6 −11 0 0 1
de sorte que la matrice A2 = L2 A1 dispose d'un zéro sous son pivot
a222 = −3

M. H. EL ALJ An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives
Méthodes Itératives
Méthodes Itératives

Méthodes directes
Factorisation LU.
Procédés LU
Le procédé de factorisation se résume 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
U = A2 = L2 A1 = L2 L1 A
d'oú
A = (L2 L1 )−1 U = L−1 −1
1 L2 U = LU

M. H. EL ALJ An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives
Méthodes Itératives
Méthodes Itératives

Méthodes directes
Matrices inverses des Li .
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
L1 L−1
1 =  −2 1 0  2 1 0 = 0 1 0  = Id3
−3 0 1 3 0 1 0 0 1

de même ; L2 L2−1 = L−1

2 L2 = Id3
M. H. EL ALJ An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives
Méthodes Itératives
Méthodes Itératives

Méthodes directes
Explicitation de L et de U .
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  = LU
3 6 10 3 2 1 0 0 1

M. H. EL ALJ An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives
Méthodes Itératives
Méthodes Itératives

Méthodes directes
Résolution du système
Application
 pour la résolution
 du système
  Ax = b soit
1 4 7 x1 1
Ax =  2 5 8   x2  =  3 . On commence par le système
3 6 10 x3 6
    
1 0 0 y1 1
Ly =  2 1 0   y2  =  3 . Comme L est triangulaire
3 2 1 y3 6
inférieure, 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. H. EL ALJ An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives
Méthodes Itératives
Méthodes Itératives

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

Vérication : On a bien,
   10   
1 4 7 3 1
Ax =  2 5 8   − 73  =  3  = b
3 6 10 1 6
M. H. EL ALJ An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives
Méthodes Itératives
Méthodes Itératives

Méthodes directes
Exemple 1. n=4.
 
−2 1 −1 1
 2 0 4 −3 
Soit la matrice A = 
 −4 −1 −12
,on a successivement,
9 
−2 1 1 −4
   
1 0 0 0 −2 1 −1 1
 1 1 0 0  1  0 1 3 −2 
 −2 0 1 0 , A = L1 A =  0 −3 −10
L1 =    ,
7 
−1 0 0 1 0 0 2 −5
   
1 0 0 0 −2 1 −1 1
 0 1 0 0   0 1 3 −2 
 0 3 1 0 , A = L2 A =  0 0 −1
2 1
L2 =    
1 
0 0 0 1 0 0 2 −5

M. H. EL ALJ An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives
Méthodes Itératives
Méthodes Itératives

Méthodes directes
Exemple 1. n=4.
Finalement
   
1 0 0 0 −2 1 −1 1
 0 1 0 0   0 1
, et U =  3 −2 
 = L3 A2 ,
L3 = 
 0 0 1 0   0 0 −1 1 
0 0 2 1 0 0 0 −3

par suite U = L3 A2 = L3 L2 A1 = L3 L2 L1 A
 
1 0 0 0
 −1 1 0 0 
et L = (L3 L2 L1 )−1 = L−1 −1 −1
1 L2 L3 = .
 2 −3 1 0 
1 0 −2 1

M. H. EL ALJ An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives
Méthodes Itératives
Méthodes Itératives

Méthodes directes

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

  
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. H. EL ALJ An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives
Méthodes Itératives
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. H. EL ALJ An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives
Méthodes Itératives
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 ,
n
X
c'est à dire ∀i = 1, . . . , n |aii | > |aij |
j=1,j6=i

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

n
X
c'est à dire ∀j = 1, . . . , n |ajj | > |aij |
i=1,i6=j
M. H. EL ALJ An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives
Méthodes Itératives
Méthodes Itératives

Méthodes directes : Décomposition de Choleski

Décomposition de Choleski RRT .

Proposition 2.2
Soit A est une matrice symétrique, A = AT et dénie positive
< xT , Ax >> 0 pour tout x 6= 0 alors il existe une matrice triangulaire
inférieure R telle que A = RRT

On calcule R par identication A = RRT . Donc,

i
X
aij = RiT Rj = rik rjk , i≤j
k=1

ce qui donne les rij en fonction des aij

M. H. EL ALJ An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives
Méthodes Itératives
Méthodes Itératives

Méthodes directes
Le produit A = RRt de la décomposition de Cholesky s'écrit :
  
r11 0 ... ... 0 r11 ... ri1 ... rl1 ... rn1
.. . . ..   .. .. .. .. 
. . .  . . . . 

  0
..
  
 ri1 . . . rii
.
 
.. .. . . rii ... rli ... rni 
 
. . . .. .. .. 
  
. . . 
 
..
 
.
  
 rl1 . . . rli ... rll  rll ... rnl 
.. .. .. . . .. .. .. 
  
. . . . . . . 
 
 0 
rn1 . . . rni ... rnl ... rnn 0 ... ... 0 rnn

Notons que l'élément ali de la matrice A correspondant au produit de la

l ème ligne de R avec la i ème colonne de Rt pour l > i s'écrit :
i
et
X
ali = rlk rik ∀l = 1, . . . , n ∀i = 1, . . . , l
k=1 M. H. EL ALJ An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives
Méthodes Itératives
Méthodes Itératives

Méthodes directes : Décomposition de Choleski

Décomposition de Choleski : Algorithme.
Étape 1 : On détermine la ligne 1 de R :

2 √
 a11 = r11 r11 = r11
 ⇒ r11 = a11
al1
 al1 = rl1 r11
 ⇒ rl1 = ∀l = 2, . . . , n
r11

Étape i : On connaît les colonnes


1 à i − 1 de R :

r11 0
.. ..
. .
 

 0 

 ri−1,1 . . . ri−1,i−1
Ri−1

=
 ri,1

... ri,i−1 
.. ..
 
. .
 
 ... 
rn,1 ... rn,i−1
M. H. EL ALJ An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives
Méthodes Itératives
Méthodes Itératives

Méthodes directes : Décomposition de Choleski

Décomposition de Choleski : Algorithme.
On écrit, i X
2 2 2 2
aii = rik = ri1 + ri2 + . . . + rii ∀i = 2, . . . , n
k=1

Or tous les ri,k sont connus pour k = 1, . . . , i − 1. on en déduit que

v
i−1
X
u
u i−1
X
2
aii = rik + rii2 ⇒ rii = taii − 2
rik ∀i = 2, . . . , n
k=1 k=1

par ailleurs, pour i xé et pour tout l = i + 1, . . . , n, on a

i i−1
!
X 1 X
ali = rlk rik ⇒ rli = ali − rlk rik
rii
k=1 k=1

M. H. EL ALJ An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives
Méthodes Itératives
Méthodes Itératives

Méthodes directes : Décomposition de Choleski

Exemple.
Résoudre le système suivant Ax = b suivant,
   
2 1 0 0 x1 1
 1 2 1 0   x2   0 
  = 
 0 1 2 1   x3   0 
0 0 1 2 x4 −1

A est dénie positive, elle est dons factorisable en RRT

    
2 1 0 0 r11 0 0 0 r11 r21 r31 r41
 1 2 1 0   r21 r22 0 0   0 r22 r32 r42 
 =  
 0 1 2 1   r31 r32 r33 0  0 0 r33 r43 
0 0 1 2 r41 r42 r43 r44 0 0 0 r44

M. H. EL ALJ An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives
Méthodes Itératives
Méthodes Itératives

Méthodes directes : Décomposition de Choleski

Exemple.
Pour i = 1, on a √ √
r11 = 2a11 =
a21 1
r21 = =√
r11 2
a31
r31 = =0
r
a11
41
r41 = =0
r11
Pour i = 2, on a r r
√ 1 3
r22 = a22−r21
2 = 2− =
2r 2
1 2
r32 = (a32 − r31 r21 ) =
r22 3
1
r42 = (a42 − r41 r21 ) = 0
r22
M. H. EL ALJ An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives
Méthodes Itératives
Méthodes Itératives

Méthodes directes : Décomposition de Choleski

Exemple.
Pour i = 3, on a
r
p
2 − r2 = 2 2
r33 = a33 − r31 32 2−0− = √
3
√ 3 √
1 3 3
r43 = (a43 − r41 r31 − r42 r32 ) = (1 − 0 − 0) =
r33 2 2
et nalement pour i = 4, on a
r √
3 5
q
r44 = a44 − 2
r41 − 2
r42 − 2
r43 = 2−0−0− =
4 2
on peut commencer à résoudre le 1er système Ry = b qui s'écrit

M. H. EL ALJ An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives
Méthodes Itératives
Méthodes Itératives

Méthodes directes : Décomposition de Choleski

Exemple.
 √ 
2 q0 0 0    
y1 1
√1 3
0 0   y2  
 
 2 q2 0 
Ry =    y3  = 
   =b

0 2 √2 0  0 
 3 √3
3
√
5
y4 −1
0 0 2 2
 √

 2y1 q = 1
 √1 y1 + 3 y2

= 0

soit : q2
2 2
2

3 y2 +√ 3 y3 = 0

 √
 √3


5
2 y3 + 2 y4 = −1

M. H. EL ALJ An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives
Méthodes Itératives
Méthodes Itératives

Méthodes directes : Décomposition de Choleski

Exemple.
ce qui entraine successivement en descendant,
b1 1
y1 = =√
r11 2
1 1
0− √ √
b2 − r21 y1 1
y2 = = r2 2 = −√
r22 3 6
2√ r  !
b3 − r31 y1 − r32 y2 3 2 1 1
y3 = = 0−0− −√ = √
r33 2 3 6 2 3
√
3 1 √
−1 − 0 − 0 − √
b4 − r41 y1 − r42 y2 − r43 y3 2 2 3 5
y4 = = √ =−
r44 5 2
2
M. H. EL ALJ An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives
Méthodes Itératives
Méthodes Itératives

Méthodes directes : Décomposition de Choleski

Exemple.
La troisième étape consiste à résoudre l'équation RT x = y qui s'écrit :
√

1 1

 2x1 + √ x2 = y1 = √
r2 2



 r

 3 2 1
x2 + x3 = y2 = −√



2 √3 6
2 3 1
√ x3 + √


 x4 = y3 =



 √ 3 2 2 √3
 5 x4 5


 = y4 = −
2 2
donc, facilement et comme précédemment, on aura successivement en
remontant x4 = −1, x3 = 1, x2 = −1 et x1 = 1

M. H. EL ALJ An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives
Méthodes Itératives
Méthodes Itératives

Méthodes directes : Décomposition de Choleski

Exemple.
On a bien,    
2 1 0 0 1 1
 1 2 1 0   −1   0 
  = 
 0 1 2 1  1   0 
0 0 1 2 −1 −1

M. H. EL ALJ An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives
Méthodes Itératives
Méthodes Itératives

Méthodes directes
Décomposition de Cholesky à partir de la décomposition LU n=4.
 
2 1 0 0
 1 2 1 0 
Soit la matrice A = 
 0 1 2 1 ,on a successivement,


0 0 1 2
   
1 0 0 0 2 1 0 0
 −1 1 0 0  1 3
, A = L1 A =  0 2 1 0 ,
 
L1 =  2
 0 0 1 0   0 1 2 1 
0 0 0 1 0 0 1 2
   
1 0 0 0 2 1 0 0
 0 1 0 0   0 3 1 0 
 0 − 2 1 0 , A = L2 A =  0 0 4 1 
2 1 2
L2 =    
3 3
0 0 0 1 0 0 1 2

M. H. EL ALJ An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives
Méthodes Itératives
Méthodes Itératives

Méthodes directes
Décomposition de Cholesky à partir de la décomposition LU n=4.
Finalement
   
1 0 0 0 2 1 0 0
 0 3
1 0 0   0
, et U =  2 1 0 
 = L3 A2 ,
L3 = 
 0 4
0 1 0   0 0 3 1 
0 0 − 34 1 0 0 0 5
4

par suite U = L3 A2 = L3 L2 A1 = L3 L2 L1 A
 
1 0 0 0
1
1 0 0 
et L = (L3 L2 L1 )−1 = L−1 −1 −1 .

2
1 L2 L3 = 
 2
0 3 1 0 
3
0 0 4 1

M. H. EL ALJ An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives
Méthodes Itératives
Méthodes Itératives

Méthodes directes
Décomposition de Cholesky à partir de la décomposition LU n=4.
C'est à dire
    
1 0 0 0 2 1 0 0 2 1 0 0
 1 1 0 0   0 3
1 0   0 3
1 0 
LU =  2  2 = 2 =A
 0 2 4
3 1 0  0 0 3 1   0 1 2 1 
3 5
0 0 4 1 0 0 0 4 0 0 1 2

On pose D = diag( (uii )) alors

p

 √
√1
  
2 0 0 0
q0 0 0 2 q
3 2
   
0 0 0
et D −1 0 0 0 
 2
 
D=  = 3 √ =
 0 0 √2 0   3 
 3 √
  0 0 2 0 
0 0 0 5 0 0 0 √2
2 5

M. H. EL ALJ An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives
Méthodes Itératives
Méthodes Itératives

Méthodes directes
Et on a LD = R
 √   √ 
2 2 q0 0 0
q1 0 0
 
1 0 0 0
 1 3 √1 3
0 0 
   
 2 1 0 0 

 0 2 1 0  
= 2 q2 
2
 0
3 1 0   0 0 √2 1  
0 2 √2 0 

3 √ 3
3 √3
  
0 0 1 √
5
4 0 0 0 2 0 0 3 5
2 2

on a de même D−1 U = Rt
 √
√1 √1
  
1 0 0   2 0 0
2 q 2 1 0 0 q2 q
2 3 3 2
   
0 1 0  = 0 0 
  0 1 0   2 3
 3 √  2 √ 
 0 4

0 0 3
1  0 3 1  
 0 0 √2 3 
 2 5 3 2 
√
0 0 0 2
√ 0 0 0 4 5
5 0 0 0 2

M. H. EL ALJ An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives
Méthodes Itératives
Méthodes Itératives

Méthodes Itératives : Formalisme général

Décomposition canonique
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. La matrice A s'écrit sous la forme
 
a11 a12 ... ... a1n
.. .. ..
. . .
 
 a21 
A =  ... .. .. ..
 
. . . =D−E−F
 
aii
 . .. ..
 
 .. . .

an−1n 
an1 ... ... ann−1 ann
où D : diagonale de A
E : triangulaire inférieure avec des 0 sur la diagonale
F : triangulaire supérieure avec des 0 sur la diagonale
M. H. EL ALJ An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives
Méthodes Itératives
Méthodes Itératives

Méthodes Itératives : Formalisme général

 
a11 0 ... ... 0
.. .. ..
. . .
 
 0 
D =  ... .. .
. aii . .
..
 
.
 

 . .. ..
 
 .. . .

0 
0 ... ... 0 ann
   
0 ... ... ... 0 0 −a12 ... ... −a1n
.. ..  .. .. .. ..
. .  . . . .
  
 −a21  
E =  ... ..
.. ..  .. .. .. ..
et
   
. . . F = . . . .
  
 
 . .. .. ..  . ..
   
 .. . . .  .. . −an−1n
 
 
−an1 ... . . . −ann−1 0 0 ... ... ... 0

M. H. EL ALJ An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives
Méthodes Itératives
Méthodes Itératives

Méthodes Itératives : Formalisme général

Principe
Le Principe consiste consiste a écrire la matrice A sous la forme
A = G − H avec G inversible et la résolution du système Ax = b se
ramène à un problème de point xe x = M x + b dont la solution est la
0

limite de la suite dénie par :


x0 donné 0
xn+1 = M xn + b
en Eet, on les équivalences suivantes
Ax = b ⇔ Gx = Hx + b
⇔ x = G−1 (Hx + b)
⇔ x = G−1 (Hx + b)
0
⇔ x = Mx + b
oú M = G−1 H et b = G−1 b
0

M. H. EL ALJ An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives
Méthodes Itératives
Méthodes Itératives

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

Algorithme de Jacobi
On écrit A = D − (E + F )
On suppose que tous les aii sont non nuls, donc D est inversible, on pose

G = D
H = E+F alors
La matrice d'itération de la méthode de Jacobi associée à Ax = b est
donnée par
MJ = D−1 (E + F ) = D−1 (D − A) = I − D−1 A

Et L'itération de la méthode de Jacobi s'écrit :

x0 : donné


xk+1 = MJ xk + bJ avec bJ = D−1 b

M. H. EL ALJ An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives
Méthodes Itératives
Méthodes Itératives

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

En eet le système xk+1 = MJ xk + bJ soit Dxk+1 = (E + F )xk + b
s'écrit
 

a11 xk+1
 0 −a12 ... ... −a1n xk1
 
b1

..
1
.. .. ..   .. 
  . .

. −a21 . 
  . 

  
 =  .. .. .. ..
  
  
. .

 aii xk+1 xki 
  . . + bi 
  
i
.. ..  .. 

  .
 
.. ..

.   . .   . 
 
. . .

−an−1n
 
ann xk+1
n −an1 ... ... −ann−1 0 xkn bn
 
n
1 
(1)
X
xk+1
i = bi − aij xkj  , i = 1, . . . , n
aii
j=1,j6=i

L'algorithme de Jacobi nécessite le stockage des deux vecteurs xki et xk+1

i

M. H. EL ALJ An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives
Méthodes Itératives
Méthodes Itératives

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

Algorithme de Gauss Seidel
Méthode de Gauss-Seidel
On écrit A = (D − E) − F
On suppose D − E est inversible, ce qui est assuré lorsque la matrice A
est à diagonale dominante, on pose

G = D−E
H = F alors
La matrice d'itération de la méthode de Jacobi associée à Ax = b est
donnée par
MG = (D − E)−1 (F ) = I − (D − E)−1 A

Et L'itération de la méthode de Gauss Seidel s'écrit :

x0 donné

:
xk+1 = M G x k + bG avec bg = (D − E)−1 b
M. H. EL ALJ An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives
Méthodes Itératives
Méthodes Itératives

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

Algorithme de Gauss Seidel
Et L'itération de la méthode de Gauss-Seidel s'écrit également :
(D − E)xk+1 = F xk + b

oú Dxk+1 = Exk+1 + F xk + b
et pour une donnée x0 choisie on calcule xk+1 par
 
i−1 n
1 
(2)
X X
xk+1
i = bi − aij xk+1
j − aij xkj  , i = 1, . . . , n
aii j=1 j=i+1

L'algorithme de Gauss-Seidel ne nécessite qu'un vecteur de stockage xki

et il est en général plus rapide.

M. H. EL ALJ An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives
Méthodes Itératives
Méthodes Itératives

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

Exemple.
On cherche à résoudre le système Ax = b suivant :
    
3 1 −1 x1 2
Ax =  1 5 2   x2  = b =  17  (3)
2 −1 −6 x3 −18

alors la décomposition A = D − E − F de la matrice A est donnée par

     
3 0 0 0 0 0 0 −1 1
D= 0 5 0  E =  −1 0 0  et F =  0 0 −2 
0 0 −6 −2 1 0 0 0 0

M. H. EL ALJ An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives
Méthodes Itératives
Méthodes Itératives

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

Exemple.
et l'itération de Jacobi du système (3) s'écrit :
3xk+1
    k   
1 0 −1 1 x1 2
Dxk+1 =  5xk+1
2
 =  −1 0 −2   xk2  +  17 
−6xk+1
3
−2 1 0 xk3 −18

ce qui conduit pour x0 = (x01 , x03 , x03 )t donné, aux formules suivantes :
 1
 xk+1
1 = ( 2 −xk2 +xk3 )
3






 k+1 1
x2 = ( 17 −xk1 −2xk3 ) (4)
 5

1


 xk+1 =

− ( −18 −2xk1 +xk2 )
 3

6
M. H. EL ALJ An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives
Méthodes Itératives
Méthodes Itératives

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

La première itération avec x(0) = (0, 0, 0)t donne :
1 2


 x11 = (2 − 0 + 0) = = 0.6666667


 3 3
1 17

x12 = (17 − 0 − 2 × 0) = = 3.4

 5 5
1


 x1

= − (−18 − 2 × 0 + 0) = 3
3
6
et La deuxième itération donne :
1 8

2 − 17


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


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


 x2

= = 2.655556
3 5
6 90
M. H. EL ALJ An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives
Méthodes Itératives
Méthodes Itératives

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

L'application des formules (5) donnent les résultats numériques suivants :
pour x0 = (0, 0, 0)t on a

et pour x0 = (1, 1, 1)t on a

M. H. EL ALJ An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives
Méthodes Itératives
Méthodes Itératives

Méthodes itératives : Méthode de Gauss Seidel

et l'itération de Gauss Seidel du système (3) s'écrit :
(D − E)xk+1 = F xk + b
soit :
   k+1    k   
3 0 0 x1 0 −1 1 x1 2
 1 5 0   xk+1
2
= 0 0 −2   xk2 + 17 
2 −1 −6 xk+1
3
0 0 0 xk3 −18

ce qui conduit pour x0 = (x01 , x03 , x03 )t donné, aux formules suivantes :

1

 xk+1
1 = ( 2 −xk2 +xk3 )
3





1 (5)
xk+1
2 = ( 17 −xk+1
1 −2xk3 )


 5

 xk+1 1
−2xk+1 +xk+1


3 = − ( −18 1 2 )
6
M. H. EL ALJ An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives
Méthodes Itératives
Méthodes Itératives

Méthodes itératives : Méthode de Gauss Seidel

Les deux premières itérations pour x(0) = (0, 0, 0)t donnent :
1 2


 x11 = (2 − 0 + 0) = = 0.666667


 3 3
1 49

2


x12 = 17 − 3 −2×0 = = 3.266667

 5 15
1 241


2 49
 x1

= − −18 − 2 × + = = 2.6677778

3 3 15
6 90
et La deuxième itération donne :
1 127

49 241



 x21 = 2− 15 + 90 = = 0.4037707


 3 90
1 3017

127 241


x22 = 17 − 270 −2× 90 = = 2.2348148

 5 1350
1 21537


127 3017 17
 x2

= − −18 − 2 × + + = = 2.7843209

3 90 1350 5
6 8100
M. H. EL ALJ An-Num-S3
 Introduction
Méthodes directes
Méthodes Itératives
Méthodes Itératives
Méthodes Itératives

Méthodes itératives : Méthode de Gauss Seidel

L'application des formules (5) donnent les résultats numériques suivants :
pour x0 = (0, 0, 0)t on a

et pour x0 = (1, 1, 1)t on a

M. H. EL ALJ An-Num-S3