analyse numerique berriri .pdf



Nom original: analyse-numerique-berriri.pdfTitre: Chapitre I Résolution des systèmes algébriques linéairesAuteur: Kamel BERRIRI

Ce document au format PDF 1.5 a été généré par TeX / pdfTeX, et a été envoyé sur fichier-pdf.fr le 11/03/2011 à 17:06, depuis l'adresse IP 41.229.x.x. La présente page de téléchargement du fichier a été vue 3337 fois.
Taille du document: 940 Ko (105 pages).
Confidentialité: fichier public


Aperçu du document


Chapitre I
Résolution des systèmes algébriques
linéaires
Kamel BERRIRI
Université de Sousse

11 mars 2011

K. BERRIRI (Université de Sousse)

Analyse numérique

1 / 47

Plan
1

Méthodes de résolution directes
Généralités
Elimination de Gauss
Elimination de Gauss-Jordan
Méthode de Factorisation
Introduction
Décomposition LU à partir de méthode de Gauss
Factorisation LU Générale

Factorisation de Choleski
2

Méthodes itératives
Méthodes de Jacobi
Méthodes de Gauss-Seidel

K. BERRIRI (Université de Sousse)

Analyse numérique

2 / 47

Un système d’équations linéaires est un système de n équations
linéaires à n inconnues

a11 x1 + a12 x2 + a13 x3 + . . . + a1n xn = b1







 a21 x1 + a22 x2 + a23 x3 + . . . + a2n xn = b2









..
.

=

..
.

an1 x1 + an2 x2 + an3 x3 + . . . + ann xn = bn

où aij et bj sont connus pour i, j = 1, ..., n.

K. BERRIRI (Université de Sousse)

Analyse numérique

3 / 47

Un système d’équations linéaires est un système de n équations
linéaires à n inconnues

a11 x1 + a12 x2 + a13 x3 + . . . + a1n xn = b1







 a21 x1 + a22 x2 + a23 x3 + . . . + a2n xn = b2









..
.

=

..
.

an1 x1 + an2 x2 + an3 x3 + . . . + ann xn = bn

où aij et bj sont connus pour i, j = 1, ..., n.

Exemple : Trouver x1 , x2 , x3 solution de

 2x1 + 3x2 − x3 = 5
4x1 + 4x2 − 3x3 = 3

−2x1 + 3x2 − x3 = 1
K. BERRIRI (Université de Sousse)

Analyse numérique

3 / 47

Écriture matricielle :
AX = b
où A dénote la matrice carrée d’ordre n des coefficients du
système linéaire et b le vecteur du second membre.





b1
a11 ... a1i ... a1n
 .. 

. . . ..
. . . .. 
 ..
 . 

.
. 
 .





bi 

A =  ai1 ... aii ... ain 
b=
x
=
 . 

 .




. . ..
. . .. 
.
 ..
. .
. .
 . 

an1 ... ani ... ann
bn

K. BERRIRI (Université de Sousse)

Analyse numérique


x1
.. 
. 

xi 
.. 
. 

xn

4 / 47

Écriture matricielle :
AX = b
où A dénote la matrice carrée d’ordre n des coefficients du
système linéaire et b le vecteur du second membre.





b1
a11 ... a1i ... a1n
 .. 

. . ..
. . .. 
 ..
 . 

. .
. . 
 .





b


b= i 
x=
A =  ai1 ... aii ... ain 

 .
 ... 

. . . ..
. . . .. 
 ..




.
.
an1 ... ani ... ann
bn


x1
.. 
. 

xi 
.. 
. 

xn

Exemple : Trouver x1 , x2 , x3 solution de

 2x1 + 3x2 − x3 = 5
4x1 + 4x2 − 3x3 = 3

−2x1 + 3x2 − x3 = 1
K. BERRIRI (Université de Sousse)

Analyse numérique

4 / 47

Écriture matricielle :
AX = b
où A dénote la matrice carrée d’ordre n des coefficients du
système linéaire et b le vecteur du second membre.





b1
a11 ... a1i ... a1n
 .. 

. . . ..
. . . .. 
 ..
 . 

.
. 
 .





b


A =  ai1 ... aii ... ain 
b= i 
x=

 .
 ... 

. . ..
. . .. 
 ..

. .
. .



an1 ... ani ... ann
bn


x1
.. 
. 

xi 
.. 
. 

xn

Exemple : Trouver X ∈ R3 solution de



  
2
3 −1
x1
5
 4




4 −3
x2
3 
=
−2 3 −1
x3
1
K. BERRIRI (Université de Sousse)

Analyse numérique

4 / 47

Méthode de Cramer
Trois énoncés équivalents :
Le système AX = b admet une solution unique si et
seulement si la matrice A est de rang maximal (autant
d’inconnues que d’équations et pas d’équation qui se
répète).
Le système AX = b admet une solution unique si et
seulement si det A 6= 0
Le système AX = b admet une solution unique si et
seulement si A est inversible.
Dans ce cas la solution est fournie par
X = A−1 b
det Aj
La formule de Cramer : xj =
det A
où Aj est la matrice A dont la colonne j est remplacée par b.
K. BERRIRI (Université de Sousse)

Analyse numérique

5 / 47

Exemple
Calculer le temps nécessaire pour résoudre à l’aide de méthode
de Cramer un système linéaire de 20 équations en disposant
d’un ordinateur 1 GHZ (qui calcul à peu près 109
opérations/seconde).

K. BERRIRI (Université de Sousse)

Analyse numérique

6 / 47

Exemple
Calculer le temps nécessaire pour résoudre à l’aide de méthode
de Cramer un système linéaire de 20 équations en disposant
d’un ordinateur 1 GHZ (qui calcul à peu près 109
opérations/seconde).
Réponse :
Nombre d’opération : 9.7316 × 1020
Temps requis en secondes : 9.7316 × 1011
Temps rquis en années ≈ 31287.

K. BERRIRI (Université de Sousse)

Analyse numérique

6 / 47

Exemple
Calculer le temps nécessaire pour résoudre à l’aide de méthode
de Cramer un système linéaire de 20 équations en disposant
d’un ordinateur 1 GHZ (qui calcul à peu près 109
opérations/seconde).
Réponse :
Nombre d’opération : 9.7316 × 1020
Temps requis en secondes : 9.7316 × 1011
Temps rquis en années ≈ 31287.
La méthode de Cramer est impuissante ou inefficace pour
résoudre des système d’ordre (n ≥ 4).

K. BERRIRI (Université de Sousse)

Analyse numérique

6 / 47

Exemple
Calculer le temps nécessaire pour résoudre à l’aide de méthode
de Cramer un système linéaire de 20 équations en disposant
d’un ordinateur 1 GHZ (qui calcul à peu près 109
opérations/seconde).
Réponse :
Nombre d’opération : 9.7316 × 1020
Temps requis en secondes : 9.7316 × 1011
Temps rquis en années ≈ 31287.
La méthode de Cramer est impuissante ou inefficace pour
résoudre des système d’ordre (n ≥ 4).
Comment résoudre efficacement des systèmes linéaires ?

K. BERRIRI (Université de Sousse)

Analyse numérique

6 / 47

Méthodes de résolution
Une méthode directes est essentiellement une méthode
basée sur la remontée (descente). Pour de telle méthode
on peut faire un estimé a priori du nombre d’opérations en
virgule flottante et du temps de calcul (une remontée ou une
descente exige ≈ n2 opérations élémentaires). La plupart
du temps la limitation dans l’utilisation de méthodes directes
vient de l’espace mémoire requis pour la résolution.
À l’opposée de ces méthodes on trouve les méthodes
itératives. Ces méthodes ne garantissent pas la
convergence et ne peuvent garantir un nombre fixe
d’opérations pour l’obtention d’une solution. Cependant la
plupart des méthodes itératives exigent moins d’espace
mémoire.

K. BERRIRI (Université de Sousse)

Analyse numérique

7 / 47

Principe de la méthodes
La méthode d’élimination de Gauss consiste à utiliser les
opérations élémentaires afin de réduire le système sous la
forme triangulaire supérieure.

K. BERRIRI (Université de Sousse)

Analyse numérique

8 / 47

Dans l’application de la méthode de Gauss on procède par
élimination des termes sous la diagonale en utilisant la notion
de matrice augmentée.

K. BERRIRI (Université de Sousse)

Analyse numérique

9 / 47

Dans l’application de la méthode de Gauss on procède par
élimination des termes sous la diagonale en utilisant la notion
de matrice augmentée.

Définition
La matrice augmentée du système AX = b est la matrice de
dimension n × (n + 1) obtenu en ajoutant le membre de droite b
à la matrice A :


a11 ... a1i ... a1n b1
. . ..
. . ..
 ..

. .
. .
 .



 ai1 ... aii ... ain bi 
 .

. . . ..
. . . ..
 ..

.
.
an1 ... ani ... ann bn

K. BERRIRI (Université de Sousse)

Analyse numérique

9 / 47

Dans l’application de la méthode de Gauss on procède par
élimination des termes sous la diagonale en utilisant la notion
de matrice augmentée.

Définition
La matrice augmentée du système AX = b est la matrice de
dimension n × (n + 1) obtenu en ajoutant le membre de droite b
à la matrice A :


a11 ... a1i ... a1n b1
. . ..
. . ..
 ..

. .
. .
 .



 ai1 ... aii ... ain bi 
 .

. . . ..
. . . ..
 ..

.
.
an1 ... ani ... ann bn
Cette notation est très utile puisque les opérations élémentaires
doivent être faites sur la matrice A et sur b simultanément.
K. BERRIRI (Université de Sousse)

Analyse numérique

9 / 47

On considère la matrice augmentée à l’étape 0 (Initialisation) :
 (0)
 (0)
(0)
(0)
(0)
a11 ... a1i ... a1n b1
L1
 ..

.
.
.
.. .
.. .
 .
 ..
. .
. .


e(0) :=  a(0) ... a(0) ... a(0) b(0)  L(0)
A
ii
i
in
 i1
 i
 ..
 ..
..
..
.
.
.
.
 .
 .
. .
. .
(0)

an1

K. BERRIRI (Université de Sousse)

...

(0)

ani

...

Analyse numérique

(0)

ann

(0)

bn

(0)

Ln

10 / 47

Etape 1 (Itération k = 1)
(0)

On suppose que le pivot de Gauss a11 6= 0. Pour éliminer
l’inconnue x1 des lignes Li pour 2 ≤ i ≤ n , on effectue cette
transformation (étape 1 de l’algorithme de Gauss) :



e(1)
A





=




(1)
a11

..
.

(1)
a12
(1)
a22

0
..
.

..
.
..
.

0

an2

(1)

K. BERRIRI (Université de Sousse)

...
..
.
..
.
..
.

(1)
a1i

...

ani

..
.

(1)
a1n

...
.. ..
. .

(1)

(1)

bi
..
.

(1)

bn

(1)

...
..
.

(1)

... ann

aii
..
.

(1)
b1

ain
..
.

Analyse numérique

(1)

 L(1) = L(0)
1
1
..
 .


 L(1) = L(0) −
 i
i

 ..
 .
(1)

(0)

Ln = Ln −

(0)

ai1

(0)
a11

(0)

an1

(0)

a11

(0)

L1

(0)

L1

11 / 47

Etape 1 (Itération k = 1)
(0)

On suppose que le pivot de Gauss a11 6= 0. Pour éliminer
l’inconnue x1 des lignes Li pour 2 ≤ i ≤ n , on effectue cette
transformation (étape 1 de l’algorithme de Gauss) :



e(1)
A





=




(1)
a11

..
.

(1)
a12
(1)
a22

0
..
.

..
.
..
.

0

an2

(1)

K. BERRIRI (Université de Sousse)

...
..
.
..
.
..
.

(1)
a1i

...

ani

..
.

(1)
a1n

...
.. ..
. .

(1)

(1)

bi
..
.

(1)

bn

(1)

...
..
.

(1)

... ann

aii
..
.

(1)
b1

ain
..
.

Analyse numérique

(1)

 L(1) = L(0)
1
1
..
 .


 L(1) = L(0) −
 i
i

 ..
 .
(1)

(0)

Ln = Ln −

(0)

ai1

(0)
a11

(0)

an1

(0)

a11

(0)

L1

(0)

L1

11 / 47

Etape 1 (Itération k = 2)
(1)

si maintenant a22 6= 0, on peut réitérer le procédé en éliminant
(2)
cette fois l’inconnue x2 des lignes Li pour 3 ≤ i ≤ n, on obtient :

(2)


e(2)
A




=




(2)
a11

(2)
a21
(2)
a22

(2)
a1i

0
0
..
.

0
..
.

...
. . ..
. .
(2)
... aii
..
..
.
.

0

0

...

K. BERRIRI (Université de Sousse)

(2)

ani

(2)
a1n

(2)
b1

...
. . ..
. .
(2)
(2)
... ain bi
..
.
...

(2)

ann

Analyse numérique

(2)

bn

(1)

 L1 = L1
..
 .

 (2)
 Li = Li(1) −

 .
 ..
(2)

(1)

Ln = Ln −

(1)

ai2

(1)

a22

(1)

an2

(1)

a22

(1)

L2

(1)

L2

12 / 47

Etape 1 (Itération k = 2)
(1)

si maintenant a22 6= 0, on peut réitérer le procédé en éliminant
(2)
cette fois l’inconnue x2 des lignes Li pour 3 ≤ i ≤ n, on obtient :

(2)


e(2)
A




=




(2)
a11

(2)
a21
(2)
a22

(2)
a1i

0
0
..
.

0
..
.

...
. . ..
. .
(2)
... aii
..
..
.
.

0

0

...

K. BERRIRI (Université de Sousse)

(2)

ani

(2)
a1n

(2)
b1

...
. . ..
. .
(2)
(2)
... ain bi
..
.
...

(2)

ann

Analyse numérique

(2)

bn

(1)

 L1 = L1
..
 .

 (2)
 Li = Li(1) −

 .
 ..
(2)

(1)

Ln = Ln −

(1)

ai2

(1)

a22

(1)

an2

(1)

a22

(1)

L2

(1)

L2

12 / 47

Etape n-1 (Itération k = n − 1)
Après n − 1 itérations (ou étapes) de cet algorithme (en
supposant que touts les pivots de Gauss sont non nuls) on
construit un système linéaire triangulaire supérieur
A(n−1) X = b(n−1) équivalent au système initial A(0) X = b :

K. BERRIRI (Université de Sousse)

Analyse numérique

13 / 47



Etape n-1 (Itération k = n − 1)
Après n − 1 itérations (ou étapes) de cet algorithme (en
supposant que touts les pivots de Gauss sont non nuls) on
construit un système linéaire triangulaire supérieur
A(n−1) X = b(n−1) équivalent au système initial A(0) X = b :

(n−1)

a11


 0


 0


 0
0

(n−1)

a12

(n−1)

a22
0
0
0

(n−1)

...
..
.

a1n
..
.

(n−1)

...
..
.

ain
..
.

0

ann

... a1i
.
... ..
... aii
..
. 0
... 0

K. BERRIRI (Université de Sousse)

(n−1)

(n−1)

(n−1)

(n−1)



(n−1)

(0)

L
= L1
. 1
 ..

(n−1) 
 ..
bi
.
..

.
 (n−1) (n−2) a(n−2)
(n−2)
n,n−1
= Ln − (n−2)
L
(n−1) Ln
bn
an−1,n−1 n−1
b1
..
.

Analyse numérique

13 / 47

Algorithme de la remontée Triangulaire
Matrice triangulaire supérieure : remontée triangulaire (on
commence à n on fini à 1 ”en haut”).
!
n
(n−1)
X
bn
1
(n−1)
(n−1)
xn = (n−1) , xi = (n−1) bi

aik xk , i = n−1, n−2, ..., 1
ann
aii
k=i+1

K. BERRIRI (Université de Sousse)

Analyse numérique

14 / 47

Exemple de remontée triangulaire
Soit à résoudre le système


 

3 1 3
x1
0
 0 2 2   x2  =  30 
0 0 1
x3
15

b3


x3 =


a33



3

X
30 − 2x3

1
x2 = a22 b2 −
a2k xk =
2

k=3


3

X
0 − 1x2 − 3x3


1

x
=
b

a1k xk =

1
a11
 1
3
k=2

K. BERRIRI (Université de Sousse)

Analyse numérique

15 / 47

Exemple de remontée triangulaire
Soit à résoudre le système


 

3 1 3
x1
0
 0 2 2   x2  =  30 
0 0 1
x3
15

b3


x3 =
= 15


a33



3

X
30 − 2x3

1
x2 = a22 b2 −
a2k xk =
2

k=3


3

X
0 − 1x2 − 3x3


1

x
=
b

a1k xk =

1
a11
 1
3
k=2

K. BERRIRI (Université de Sousse)

Analyse numérique

15 / 47

Exemple de remontée triangulaire
Soit à résoudre le système


 

3 1 3
x1
0
 0 2 2   x2  =  30 
0 0 1
x3
15

b3


x3 =
= 15


a33



3

X
30 − 2x3

1
= 0
x2 = a22 b2 −
a2k xk =
2

k=3


3

X
0 − 1x2 − 3x3


1

a1k xk =

 x1 = a11 b1 −
3
k=2

K. BERRIRI (Université de Sousse)

Analyse numérique

15 / 47

Exemple de remontée triangulaire
Soit à résoudre le système


 

3 1 3
x1
0
 0 2 2   x2  =  30 
0 0 1
x3
15

b3


x3 =
= 15


a33



3

X
30 − 2x3

1
= 0
x2 = a22 b2 −
a2k xk =
2

k=3


3

X
0 − 1x2 − 3x3


1

a1k xk =
= −15

 x1 = a11 b1 −
3
k=2

K. BERRIRI (Université de Sousse)

Analyse numérique

15 / 47

Exemple de remontée triangulaire
Soit à résoudre le système


 

3 1 3
x1
0
 0 2 2   x2  =  30 
0 0 1
x3
15

b3


x3 =
= 15


a33



3

X
30 − 2x3

1
= 0
x2 = a22 b2 −
a2k xk =
2

k=3


3

X
0 − 1x2 − 3x3


1

a1k xk =
= −15

 x1 = a11 b1 −
3
k=2
La solution est le vecteur suivanté : X = (−15, 0, 15)T
K. BERRIRI (Université de Sousse)

Analyse numérique

15 / 47

Algorithme d’élimination
On considère de nouveau la matrice augmentée :
 (0)

(0)
(0)
(0)
a11 ... a1i ... a1n b1
 ..

. . . ..
. . . ..
 .

.
.
 (0)

(0)
(0)
(0)
(0)

e :=  a
A
 i1 ... aii ... ain bi 
 ..

. . ..
. . ..
 .

. .
. .
(0)
(0)
(0)
(0)
an1 ... ani ... ann bn

(0)

L1
..
.

(0)

Li
..
.

(0)

Ln

(0)

On suppose que le pivot a11 6= 0.

K. BERRIRI (Université de Sousse)

Analyse numérique

16 / 47

Etape 1 (Itération k = 1)
1

On commence à diviser la première ligne L1 de la matrice
(0)
A(0) par a11 pour avoir 1 à la position (1, 1)

K. BERRIRI (Université de Sousse)

Analyse numérique

17 / 47

Etape 1 (Itération k = 1)
1

On commence à diviser la première ligne L1 de la matrice
(0)
A(0) par a11 pour avoir 1 à la position (1, 1)











K. BERRIRI (Université de Sousse)

(0)

(0)

1

a12

(0)
a21

..

(0)

a11

.
..
.
...
..
...
.
(0)
an1 ...

...
..
.

...
..

(0)

aii

(0)
ai1

..
.
(0)
ani

a1n

(0)

a11

.
. ..

(0)

a

(0)

b1

(0)

a11

(0)

in
bi
...
(0)
ai1
. . . ..
.
(0)
(0)
... ann bn

Analyse numérique












17 / 47

Etape 1 (Itération k = 1)
1

On commence à diviser la première ligne L1 de la matrice
(0)
A(0) par a11 pour avoir 1 à la position (1, 1)











2

(0)

(0)

1

a12

(0)
a21

..

(0)

a11

.
..
.
...
..
...
.
(0)
an1 ...

...
..
.

...
..

(0)

aii

(0)
ai1

..
.
(0)
ani

a1n

(0)

a11

.
. ..

(0)

a

(0)

b1



(0)

a11

(0)

in
bi
...
(0)
ai1
. . . ..
.
(0)
(0)
... ann bn











Eliminer l’inconnue x1 des lignes Li pour i 6= 1, en faisant
ces transformations :

K. BERRIRI (Université de Sousse)

Analyse numérique

17 / 47

Etape 1 (Itération k = 1)

2

Eliminer l’inconnue x1 des lignes Li pour i 6= 1, en faisant
ces transformations :


(0)
(0)
(0)
a1n
a12
b1
(1)
(0)
1
L1 = (0)
L
...
...
1
(0)
(0)
(0)

a11 1
a11
a11
a11 
 (0) .

. . ..
 a

. . ...
. .
 21

 ..

(0)
(0)
(0)
 .

...
a
...
a
b
ii
in
i


 ..

. . . ..
. . . ..
.
.
 .

(0)
(0)
(0)
(0)
an1 ... ani ... ann bn

K. BERRIRI (Université de Sousse)

Analyse numérique

17 / 47

Etape 1 (Itération k = 1)

2

Eliminer l’inconnue x1 des lignes Li pour i 6= 1, en faisant
ces transformations :

 (1)
(0)
(1)
(1)
(1)
1
L1
L1 = (0)
1
a12 ... ... a1n b1
a
11
 (0) .

. . . ..
. . ...
 a

.
 21

 ..
(0)
(0)
(0) 
 .

...
a
...
a
b
ii
in
i


.
.
.
 .

..
.. .
. ..
. .
 .

(0)
(0)
(0)
(0)
an1 ... ani ... ann bn

K. BERRIRI (Université de Sousse)

Analyse numérique

17 / 47

Etape 1 (Itération k = 1)

2

Eliminer l’inconnue x1 des lignes Li pour i 6= 1, en faisant
ces transformations :

 (1)
(0)
(1)
(1)
(1)
1
L1
L1 = (0)
1
a12 ... ... a1n b1
a
11


. . . ..
. . . ..
 0

.
.


 ..
(0)
(0)
(0) 
 .

...
a
...
a
b
ii
in
i


.
.
.
 .

..
.. .
. ..
. .
 .

(0)
(0)
(0)
(0)
an1 ... ani ... ann bn

K. BERRIRI (Université de Sousse)

Analyse numérique

17 / 47

Etape 1 (Itération k = 1)

2

Eliminer l’inconnue x1 des lignes Li pour i 6= 1, en faisant
ces transformations :

 (1)
(0)
1
(1)
(1)
(1)
L1 = (0)
L
1
a12 ... ... a1n b1
a11 1


. . . ..
. . . ..
 0

.
.


(1)
(1)
(1) 
 0
...
a
...
a
b
ii
in
i


 ..

..
..
.
.
.
.
 .

. .
. .
(0)
(0)
(0)
(0)
an1 ... ani ... ann bn

K. BERRIRI (Université de Sousse)

Analyse numérique

17 / 47

Etape 1 (Itération k = 1)

2

Eliminer l’inconnue x1 des lignes Li pour i 6= 1, en faisant
ces transformations :

 (1)
(0)
1
(1)
(1)
(1)
L1 = (0)
L
1
a12 ... ... a1n b1
a11 1

 .
. . . ..
. . . ..
 0
 ..
.
.


(1)
(1)
(1) 
 0
(1)
(0)
(0) (1)
...
a
...
a
b
ii
in
i

 Li = Li − ai1 L1
 ..

.
..
. . ..
 .

. ..
. .
(0)
(0)
(0)
(0)
an1 ... ani ... ann bn

K. BERRIRI (Université de Sousse)

Analyse numérique

17 / 47

Etape 1 (Itération k = 1)

2

Eliminer l’inconnue x1 des lignes Li pour i 6= 1, en faisant
ces transformations :

 (1)
(0)
1
(1)
(1)
(1)
L1 = (0)
L
1
a12 ... ... a1n b1
a11 1

 .
. . . ..
. . . ..
 0
 ..
.
.


(1)
(1)
(1) 
 0
(1)
(0)
(0) (1)
...
a
...
a
b
ii
in
i

 Li = Li − ai1 L1
 ..
 .
.
..
. . ..
 .
 ..
. ..
. .
(1)
(1)
(1)
(1)
(0)
(0) (1)
0
... ani ... ann bn
Ln = Ln − an1 L1

K. BERRIRI (Université de Sousse)

Analyse numérique

17 / 47

Etape 1 (Itération k = 1)

2

Eliminer l’inconnue x1 des lignes Li pour i 6= 1, en faisant
ces transformations :

 (1)
(0)
1
(1)
(1)
(1)
L1 = (0)
L
1
a12 ... ... a1n b1
a11 1

 .
. . . ..
. . . ..
 0
 ..
.
.


(1)
(1)
(1) 
 0
(1)
(0)
(0) (1)
...
a
...
a
b
ii
in
i

 Li = Li − ai1 L1
 ..
 .
.
..
. . ..
 .
 ..
. ..
. .
(1)
(1)
(1)
(1)
(0)
(0) (1)
0
... ani ... ann bn
Ln = Ln − an1 L1

K. BERRIRI (Université de Sousse)

Analyse numérique

17 / 47

Etape 1 (Itération k = 1)

2

Eliminer l’inconnue x1 des lignes Li pour i 6= 1, en faisant
ces transformations :

 (1)
(0)
1
(1)
(1)
(1)
L1 = (0)
L
1
a12 ... ... a1n b1
a11 1

 .
. . . ..
. . . ..
 0
 ..
.
.


(1)
(1)
(1) 
e(1) =  0
(1)
(0)
(0) (1)
A
...
a
...
a
b
ii
in
i

 Li = Li − ai1 L1
 ..
 .
.
..
. . ..
 .
 ..
. ..
. .
(1)
(1)
(1)
(1)
(0)
(0) (1)
0
... ani ... ann bn
Ln = Ln − an1 L1

K. BERRIRI (Université de Sousse)

Analyse numérique

17 / 47

Etape 2 (Itération k = 2)
(1)

si maintenant a22 6= 0, on peut réitérer le procédé en éliminant
(2)
cette fois l’inconnue x2 des lignes Li pour i 6= 2, on obtient :


e(2)
A

(2)

1 0 a13

 0 1 ...

=
 0 0 ...
 .. .. ..
 . . .
0 0 ...

K. BERRIRI (Université de Sousse)

...
..
.
(2)

aii
...

(2)

ani

(2)

(2)

a1n b1
. . ..
. .
(2)
(2)
... ain bi
..
.
...

(2)

ann

(2)










bn

Analyse numérique

18 / 47

Etape 2 (Itération k = 2)
(1)

si maintenant a22 6= 0, on peut réitérer le procédé en éliminant
(2)
cette fois l’inconnue x2 des lignes Li pour i 6= 2, on obtient :


e(2)
A

(2)

1 0 a13

 0 1 ...

=
 0 0 ...
 .. .. ..
 . . .
0 0 ...

K. BERRIRI (Université de Sousse)

...
..
.
(2)

aii
...

(2)

ani

(2)

(2)

a1n b1
. . ..
. .
(2)
(2)
... ain bi
..
.
...

(2)

ann

(2)



(2)

(2)

(1) (2)

L1 = L1 − a12 L2









bn

Analyse numérique

18 / 47

Etape 2 (Itération k = 2)
(1)

si maintenant a22 6= 0, on peut réitérer le procédé en éliminant
(2)
cette fois l’inconnue x2 des lignes Li pour i 6= 2, on obtient :


e(2)
A

(2)

1 0 a13

 0 1 ...

=
 0 0 ...
 .. .. ..
 . . .
0 0 ...

K. BERRIRI (Université de Sousse)

...
..
.
(2)

aii
...

(2)

ani

(2)

(2)

a1n b1
. . ..
. .
(2)
(2)
... ain bi
..
.
...

(2)

ann

(2)



(2)

(2)

(1) (2)

L1 = L1 − a12 L2
 L(2) = 1 L(1)
 2
(1)
a22 2






bn

Analyse numérique

18 / 47

Etape 2 (Itération k = 2)
(1)

si maintenant a22 6= 0, on peut réitérer le procédé en éliminant
(2)
cette fois l’inconnue x2 des lignes Li pour i 6= 2, on obtient :


e(2)
A

(2)

1 0 a13

 0 1 ...

=
 0 0 ...
 .. .. ..
 . . .
0 0 ...

K. BERRIRI (Université de Sousse)

...
..
.
(2)

aii
...

(2)

ani

(2)

(2)

a1n b1
. . ..
. .
(2)
(2)
... ain bi
..
.
...

(2)

ann

(2)



(2)

(2)

(1) (2)

L1 = L1 − a12 L2
 L(2) = 1 L(1)
 2
(1) 2
 (2) a22(1)
 L = L − a(1) L(2)
 i
i
i1 i



bn

Analyse numérique

18 / 47

Etape 2 (Itération k = 2)
(1)

si maintenant a22 6= 0, on peut réitérer le procédé en éliminant
(2)
cette fois l’inconnue x2 des lignes Li pour i 6= 2, on obtient :


e(2)
A

(2)

1 0 a13

 0 1 ...

=
 0 0 ...
 .. .. ..
 . . .
0 0 ...

K. BERRIRI (Université de Sousse)

...
..
.
(2)

aii
...

(2)

ani

(2)

(2)

a1n b1
. . ..
. .
(2)
(2)
... ain bi
..
.
...

(2)

ann

(2)

bn

Analyse numérique



(2)

(2)

(1) (2)

L1 = L1 − a12 L2
 L(2) = 1 L(1)
 2
(1) 2
 (2) a22(1)
 L = L − a(1) L(2)
 i
i
i1 i
 ..
 .
(2)
(1)
(1) (2)
Ln = Ln − an1 Ln

18 / 47

Etape finale (Itération k = n)
Après n itérations (ou étapes) de cet algorithme (en supposant
que touts les pivots de Gauss sont non nuls) on obtient une
équation de type A(n) X = b(n) avec A(n) = Id équivalent au
système initial A(0) X = b :


(n)
1 0 ... 0 ... 0 b1


. . . .
 0 1 ... .. .. .. ..



(n)
(n)
e =  0 0 0 1 ... 0 b 
A
i




.. .. ..
 0 0 0 0 . . .

(n)
0 0 0 0 0 1 bn

Solution
(n)

(n)

La solution n’est autre que le vecteur X = b(n) = (b1 , ..., bn )T
K. BERRIRI (Université de Sousse)

Analyse numérique

19 / 47

Etape finale (Itération k = n)
Après n itérations (ou étapes) de cet algorithme (en supposant
que touts les pivots de Gauss sont non nuls) on obtient une
équation de type A(n) X = b(n) avec A(n) = Id équivalent au
système initial A(0) X = b :


(n)
1 0 ... 0 ... 0 b1


. . . .
 0 1 ... .. .. .. ..



(n)
(n)
e =  0 0 0 1 ... 0 b 
A
i




.. .. ..
 0 0 0 0 . . .

(n)
0 0 0 0 0 1 bn

Solution
(n)

(n)

La solution n’est autre que le vecteur X = b(n) = (b1 , ..., bn )T
K. BERRIRI (Université de Sousse)

Analyse numérique

19 / 47

Et si je veux changer b ?
Trois options :
1
Je recommence le processus avec la nouvelle valeur de b
car je dois transformer A et b simultanément dans la
méthode de Gauss
2

j’attend d’avoir TOUT les b que je veux et je fais Gauss sur
la matrice augmentée de tout les b.

3

J’essaie de garder l’information ayant servi à la
transformation de la matrice lors de la première résolution
pour résoudre avec les autres b

K. BERRIRI (Université de Sousse)

Analyse numérique

20 / 47


Aperçu du document analyse-numerique-berriri.pdf - page 1/105

 
analyse-numerique-berriri.pdf - page 3/105
analyse-numerique-berriri.pdf - page 4/105
analyse-numerique-berriri.pdf - page 5/105
analyse-numerique-berriri.pdf - page 6/105
 




Télécharger le fichier (PDF)


Télécharger
Formats alternatifs: ZIP Texte



Documents similaires


analyse numerique berriri
chap5 math5
notesdecours
anamat
methodes numeriques outils
rapport tp

Sur le même sujet..




🚀  Page générée en 0.026s