Upload
redouan-hije
View
241
Download
0
Embed Size (px)
Citation preview
7/30/2019 Transfert de chaleur - Conduction
1/60
1EMI - M. TAHA JANAN
Position du problme
=+++
=+++
=+++
mmmn22n11n
2mm2222112
1mm1221111
bxaxaxa
.
.
.
bxaxaxa
bxa......xaxa
Rsoudre le systme suivant :
RESOLUTION NUMERIQUES DE
SYSTEMS LINEAIRES D'EQUATIONS
www.almohandiss.com
7/30/2019 Transfert de chaleur - Conduction
2/60
2EMI - M. TAHA JANAN
Ecriture matricielle
Rsoudre le systme suivant bxA =.
A : matrice (non forcment carre)
)(
......
.....
......
.....
......
.......
......
321
321
33333231
22232221
11131211
ij
nmnjnnn
imijiii
mj
mj
mj
a
aaaaa
aaaaa
aaaaa
aaaaa
aaaaa
A =
=
b : vecteur
colonne secondmembre
x : vecteur
colonne desinconnues
=
mx
xx
x
x
.
.
3
2
1
=
nb
bb
b
b
.
.
3
2
1
Le systme est linaire lorsque la matrice A
ne dpend pas des composantes xi du vecteur
des variables
www.almohandiss.com
7/30/2019 Transfert de chaleur - Conduction
3/60
3EMI - M. TAHA JANAN
On distingue 3 cas :
Systme surdtermin (n>m)
Systme de Cramer (n=m)
Systme sous dtermin (n
7/30/2019 Transfert de chaleur - Conduction
4/60
4EMI - M. TAHA JANAN
A.1. Mthode de Cramer : )(Adt=
Si 0 : solution unique
= iix i = 1 n
Si 0= : deux cas
Tous les i sont nuls : une infinit de solutions
Au moins un des nest pas nul : pas de solutioni
Mthode utilisable lorsque le nombre dquations est petit
Inconvnients majeurs :
- mthode difficile programmer
- temps dexcution trs lev
A- Mthodes directes
www.almohandiss.com
7/30/2019 Transfert de chaleur - Conduction
5/60
5EMI - M. TAHA JANAN
Nombre doprations :
On a (n + 1) dterminants calculer et n divisions.
Pour chaque dterminant on a :
n! n multiplications et n! 1 additions.
Nombre doprations ncessaires :(n + 1) n! n multiplications.
(n + 1) (n! 1) additions
n divisions
soit au total TC = (n + 1)2 n! 1 oprations.
Pour n = 5 TC = 4319 oprations
Pour n = 10 TC = 439 084 799 ~ 4. 108 oprations
www.almohandiss.com
7/30/2019 Transfert de chaleur - Conduction
6/60
6EMI - M. TAHA JANAN
A.2. Mthode de rsolution par inversion de A :
tC
AA
)det(
11 =
o C t est la matrice des cofacteurs.
Nombre doprations de la mthode :
T2 = n! (n2 + n + 1) + 3 n2 n.
Pour n = 5 TC = 3790 oprations
Pour n = 10 TC = 402 797 090 ~ 4 108 oprations
La mthode a les mmes inconvnients de celle de Cramer
bAxbxA .. 1==
www.almohandiss.com
l h di
7/30/2019 Transfert de chaleur - Conduction
7/60
7EMI - M. TAHA JANAN
A.3. Mthode de Gauss :
Prambule : Rsolution des systmes triangulaires.
Systme triangulaire suprieur.
=
=+
=++
=+++
nnnn
nn1)-n(1)-n(1)-n(1)-n(
2nn2222
1nn1221111
bxa
xaxa
0
bxa......xa
bxa......xaxa
La matrice associ A est triangulaire suprieure
www.almohandiss.com
l h di
7/30/2019 Transfert de chaleur - Conduction
8/60
8EMI - M. TAHA JANAN
Systme triangulaire infrieur.
=+++
=+
=
nnnn22n11n
2222112
1111
bxa......xaxa.
.
.
bxaxa
bxa
La matrice associ A est triangulaire infrieure
www.almohandiss.com
www almohandiss com
7/30/2019 Transfert de chaleur - Conduction
9/60
9EMI - M. TAHA JANAN
La rsolution des deux systmes se fait de proche en proche.
Pour le deuxime systme on a :
11
1
1
abx = i = 2,. . ., n.
Nombre doprations :
n divisions
1 + 2 + 3 + + ( n 1 ) =
2
)1n(n multiplications
1 + 2 + 3 + + ( n 1 ) =2
)1n(n additions
Soit au total Tt = n2.
ii
j
1i
1j
iji
ia
xab
x
=
=
www.almohandiss.com
www almohandiss com
7/30/2019 Transfert de chaleur - Conduction
10/60
10EMI - M. TAHA JANAN
Mthode de Gauss, principe :
A laide dun dun algorithme dlimination convenable, cette mthode
transforme le systme en une suite de systmes quivalents (ont mmessolutions) dont le dernier est triangulaire.
la procdure de rsolution se fait alors en deux tapes :
triangularisation par limination.
rsolution du systme triagulaire quivalent.
www.almohandiss.com
www almohandiss com
7/30/2019 Transfert de chaleur - Conduction
11/60
11EMI - M. TAHA JANAN
Premire tape : triangularisation par limination.
1re limination : Supposons que a11
0, sinon on permute les lignes.
11
i1
i1
a
ag = a11 est appel le pivot et la ligne l1, ligne de pivot de
la premire limination.
Pour i = 2, 3, , n, remplaons la ligne li par li gi1.l1
Le systme devient :
=+++
=+++
=+++
)2(
nn
)2(
nn2
)2(
2n
)2(
2n
)2(
n22
)2(
22
1n
n1221111
bxa......xa0
.
.
.
bxa......xa0
bxa......xaxaAvec
j11iji
2)(
ji agaa =
i , j = 2, . . ., n
11ij
2)(
i gb bb =
www.almohandiss.com
www.almohandiss.com
7/30/2019 Transfert de chaleur - Conduction
12/60
12EMI - M. TAHA JANAN
2ime limination
On applique le procd au systme form des (n 1) dernireslignes : a22pivot et l2 ligne de pivot.
Les xi ninterviennent pas dans les liminations. On considre
alors la matrice n x ( n + 1 )
Remarque
== b)(A,A
~
+
+
+
)1n(n
)1n(2
)1n(1
nnn2n1
2n2221
1n1211
a
a
a
a..aa
.
.
.
a..aa
a..aa
www.a o a d ss.co
www.almohandiss.com
7/30/2019 Transfert de chaleur - Conduction
13/60
13EMI - M. TAHA JANAN
Algorithme de la mthode de Gauss ( kime limination )
++=+==
+===+
+
1,...,1,...,1
1,...,1,...,11
1
nkjnkiagaa
njkiaak
jkki
k
ji
k
ji
k
ji
k
ji
O)k(
k
)k(
ki
ki
aag
k
= i = k + 1, . . ., n. Les autres lments sont nuls.
2
ime
tape : Rsolution du systme triangulaire
Nombre doprations de la mthode de Gauss :6
794 23 nnnTG
+=
n = 5 TG = 115 ; n = 10 TG = 805
Pour des raisons de stabilit, on a intrt chaque tape de llimination
bien choisir le pivot tel que soit le plus grand possible.)( k
kka
www.almohandiss.com
7/30/2019 Transfert de chaleur - Conduction
14/60
14EMI - M. TAHA JANAN
Exemple 1 :
On se propose de dterminer la solution du systme suivant par lamthode de Gauss :
=+
=+
=
13
32
232
zyx
zx
zy
Matrice augmente
1311
3102
2320
On remarquera tout de suite que le premier pivot est nul :
Il faudra changer la ligne 1 avec une autre, soit la troisime
www.almohandiss.com
7/30/2019 Transfert de chaleur - Conduction
15/60
15EMI - M. TAHA JANAN
2320
3102
1311
l2-2l1
2320
1520
1311
l2/2
2320
2/12/510
1311
l3-2l2
1200
2/12/510
1311
l3/2
2/1100
2/12/510
1311
z = 1/2 y = 7/4 x=5/4
www.almohandiss.com
7/30/2019 Transfert de chaleur - Conduction
16/60
16EMI - M. TAHA JANAN
Exemple 2 :
Soit infiniment petit ( par exemple = 10-6 )
=+
=+
2yx
1yx
=
211
11A~ )1(
Pivot a11 =
= 1-1-
)2(
-2-10
11
A~
1
1
1
2
6
6
101
102
Ce qui donne y = = 1 ; x =
y1 = 0.
Or
1
0nest pas solution du systme.
=
www.almohandiss.com
7/30/2019 Transfert de chaleur - Conduction
17/60
17EMI - M. TAHA JANAN
=+
=+
1yx
2yx
= 11
211
A
~ )1(
Pivot a11 = 1
=
2-1-10211A~ )2(
1
21
6
6
101
1021
Ce qui donne y = = = 1 ; x = 2 - y = 1
11 est bien une solution prs.
www.almohandiss.com
7/30/2019 Transfert de chaleur - Conduction
18/60
18EMI - M. TAHA JANAN
Exercices dapplication :
1) Rsoudre le systme linaire :
=++
=++
=++
25322
37532
10
zyx
zyx
zyx
)k(
kka { }n.,..k,ia )k(
ki=
)k(
kka { }n.,..k,,ia )k(
ji=j
Pour le choix du pivot deux stratgies sont possibles
La mthode du pivot partiel : = max
La mthode du pivot total :
= max
www.almohandiss.com
7/30/2019 Transfert de chaleur - Conduction
19/60
19EMI - M. TAHA JANAN
=
25322
37532
10111
~ )1(A
Pivot a11
= 1. g21
= g31
=
1
2= 2.
=
5100
17310
10111~ )2(A
z = 5 ; y = 17 - 3 z = 2 et x = 10 y - z = 3.
La solution du systme est
5
2
3
www.almohandiss.com
7/30/2019 Transfert de chaleur - Conduction
20/60
20EMI - M. TAHA JANAN
2) Rsoudre le systme linaire :
=++
=++
=++
203772142
270235
72
zyx
zyx
zyx
www.almohandiss.com
7/30/2019 Transfert de chaleur - Conduction
21/60
21EMI - M. TAHA JANAN
=
203772142
270235
72111~ )1(A
1
5
1
42Pivot a11 = 1. g21 = = 5 ; g31 = = 42.
=
3024203735210
360270320
72111
~ )2(A
=
98735210
90320
72111
)2(
22a
2
21Pivot = - 2. g
32=
+
=
22190987
2633500
90320
72111~ )2(A
=
422700
90320
72111
7
84
2
390 zz = = 12 ; y = = 27 et x = 72 y z = 33.
www.almohandiss.com
7/30/2019 Transfert de chaleur - Conduction
22/60
22EMI - M. TAHA JANAN
A.4. Mthode de Gauss-Jordan
Principe :
Diagonaliser la matrice
A du systme par
limination.
=
+
+
+
)1n(n
)1n(2
)1n(1
nnn2n1
2n2221
1n1211
)1(
a
aa
a...aa
.
.
.
a...aaa...aa
A~
1re tape
Normalisation : on
divise l1par a11.
+
+
+
)1n(n
)1n(2
11
)1n(1
nnn2n1
2n2221
11
1n
11
12
)'1(
a
a
a
a
a..aa
.
.
.
a..aa
a
a..a
a1
~A
www.almohandiss.com
7/30/2019 Transfert de chaleur - Conduction
23/60
23EMI - M. TAHA JANAN
Rduction : on remplace lipar li - ai1 li pour i > 2.
=
+
+
+
)2(
)1n(n
)2(
)1n(2
11
)1n(1
)2(
nn
)2(
n2
)2(
2n
)2(
22
11
1n
11
12
)2(
a
a
a
a
a..a0
.
.
.
a..a0
a
a
..a
a
1
~A
www.almohandiss.com
7/30/2019 Transfert de chaleur - Conduction
24/60
24EMI - M. TAHA JANAN
2me tape
)2(
22a
)2(
i2a
Normalisation : on divise l2par
Rdution :
on remplace lipar li - l2
=
+
+
)3()1n(n
)3()1n(2
)3(1n
)3(nn
)3(2n
)3(1n
)3(
a
a
a
a..00
.
.
.
a..10
a..01
A
A la nime limination le
systme quivalent est
diagonal.
=
+
+
+
)n(
)1n(n
)n(
)1n(2
)n(
)1n(1
)(
a1
a
a
0
01
1
~ nA
pour tout i
2.
Do les solutions :)n(
)1n(ii ax += pour i = 1, 2, . . . , n.
www.almohandiss.com
7/30/2019 Transfert de chaleur - Conduction
25/60
25EMI - M. TAHA JANAN
Lalgorithme de Gauss Jordan est :
1n,...k,jn1,...,k1,k,...1,iaga )k(jkki
)k(
ji
)1k(
ji+=+==+a
Exercices dapplication :
1) Rsoudre le systme linaire :
=++
=+=++
11633
2220331
zyx
yxzyx
=
11633
2022
0331~ )1(A
www.almohandiss.com
7/30/2019 Transfert de chaleur - Conduction
26/60
26EMI - M. TAHA JANAN
Normalisation Rduction
l1 :
11633
2022
0331
11360
2640
0331
113602
1
2
310
0331
86002
1
2
310
2
3
2
301
l2
3
4100
2
1
2
310
2
3
2
301
3
4100
2
5010
2
7001
l3
2
7
2
5
3
4La solution est x = ; y = - ; z =
www.almohandiss.com
7/30/2019 Transfert de chaleur - Conduction
27/60
27EMI - M. TAHA JANAN
2) Rsoudre le systme linaire :
=
=++
=+
10232
1023
52
zyx
zyx
zyx
=
10232
10123
5211
~ )1(A
www.almohandiss.com
7/30/2019 Transfert de chaleur - Conduction
28/60
28EMI - M. TAHA JANAN
Normalisation Rduction
10232
10123
5211
20610
5550
5211
20610
1110
5211
21700
1110
4101
3100
1110
4101
3100
2010
1001
l1
l2
l3
La solution est ( 1 , 2 , 3 )t.
www.almohandiss.com
7/30/2019 Transfert de chaleur - Conduction
29/60
29EMI - M. TAHA JANAN
3) Rsoudre le systme linaire :
=++
=++
=++
1122
21432
2865
zyx
zyx
zyx
=1122121432
28651~ )1(A
www.almohandiss.com
7/30/2019 Transfert de chaleur - Conduction
30/60
30EMI - M. TAHA JANAN
Normalisation Rduction
11221
21432
28651
17430
35270
28651
l1
17430
57
810
28651
2
7
400
57
810
37201
l2
l3
2
7100
57
810
37
201
2
7
100
1010
2001
La solution est ( 1 , 2 , )t.2
7
www.almohandiss.com
7/30/2019 Transfert de chaleur - Conduction
31/60
31EMI - M. TAHA JANAN
=++
=+
=++
522
1
3
zyx
zyx
zyx
=++
=+
=++
922
2
6
zyx
zyx
zyx
=
9
2
6
5122
1111
3111
~ )1(A
www.almohandiss.com
7/30/2019 Transfert de chaleur - Conduction
32/60
32EMI - M. TAHA JANAN
9
26
5122
11113111
5
4
6
3140
2020
3111
5
2
6
3140
1010
3111
3
24
1100
10102101
3
2
4
1100
1010
2101
3
2
1
1100
1010
1001
l1
l2
l3
Les solution sont ( 1 , 1 , 1 )t et ( 1 , 2 , 3 )t respectivement.
A li i I i d i
www.almohandiss.com
7/30/2019 Transfert de chaleur - Conduction
33/60
33EMI - M. TAHA JANAN
Application : Inversion dune matrice
Linversion dune matrice peut tre recherche en posant :
bIxA .. = bAxI .. 1=
Matrice augmente :
10000
0000
0000100
0000010
0000001
......
...
......
...
.....
......
......
321
321
33333231
22232221
11131211
nnnjnnn
inijiii
nj
nj
nj
aaaaa
aaaaa
aaaaa
aaaaa
aaaaa
Processus de Gauss-Jordan :
A I I A-1
i d li i
www.almohandiss.com
7/30/2019 Transfert de chaleur - Conduction
34/60
34EMI - M. TAHA JANAN
Exercice dapplication
Calculer la matrice inverse de A = 43
12
( A , In ) =
1043
0112
1043
02
1
2
11
1
2
3
2
50
02
1
2
11
L1 :
5
2
5
310
02
1
2
11
5
2
5
310
5
1
5
401
L2 :
5
1
23
14Do A -1 =
www.almohandiss.com
7/30/2019 Transfert de chaleur - Conduction
35/60
35EMI - M. TAHA JANAN
A5 Factorisation
Principe :
Dcomposer la matrice A en facteurs faciles inverser : matrices triangulaires
Factorisations LU
U : Matrice triangulaire suprieure
L : matrice triangulaire infrieureOn pose A=L.U
A d d i i L i l i i i l
www.almohandiss.com
7/30/2019 Transfert de chaleur - Conduction
36/60
36EMI - M. TAHA JANAN
A admet une dcomposition L U ssi les mineurs principaux sont non nuls
det( A ) = det( L ) det( U ) 0 ( car A est inversible ).
donc L et U sont inversibles
L et U sont uniques.
Rsolution : A x = b quivalent L U x = b
Nous sommes emmen rsoudre 2 systmes triangulaires :
=
=
yxU
byLL.y = b systme triangulaire infrieur
U.x = y systme triangulaire suprieur
Nombre doprations : TLU = (n3/3 - n/3) + n2 .
www.almohandiss.com
7/30/2019 Transfert de chaleur - Conduction
37/60
37EMI - M. TAHA JANAN
A.5.1. Mthode de Crout :
Les uii sont gaux 1
A titre dexercice :
Dterminer les expressions de L et U.
=
nnnjnnn
ijiii
lllll
llll
lll
ll
l
L
......
.....0......
.....
0...0...
0....0...0
0...0...00
321
321
333231
2221
11
=
1...0...000
.....
......000
.....
......100
.......10
......1
33
2223
111312
inij
nj
nj
nj
uu
uu
uuu
uuuu
U
A 5 1 Mthode de Crout : formules de calcul
www.almohandiss.com
7/30/2019 Transfert de chaleur - Conduction
38/60
38EMI - M. TAHA JANAN
A.5.1. Mthode de Crout : formules de calcul
=
1...0...000
.....
......000.....
......100
.......10
......1
......
.....
0......
.....
0...0...
0....0...0
0...0...00
.
33
2223
111312
321
321
333231
2221
11
inij
nj
nj
nj
nnnjnnn
ijiii uu
uu
uuu
uuuu
lllll
llll
lll
ll
l
UL
li1= ai1
n,2,jj,il
ulau
n,1,ii,julal
ii
1i
1k
kjikij
ij
1j
1k
kjikijij
K
K
=
=
==
=
=
On dtermine la colonne des l et puis la ligne correspondantes des u
www.almohandiss.com
7/30/2019 Transfert de chaleur - Conduction
39/60
39EMI - M. TAHA JANAN
Exemple
=
100110
3/23/11
13/4203/71
003
122321
213
A 5 2 M h d d D li l
www.almohandiss.com
7/30/2019 Transfert de chaleur - Conduction
40/60
40EMI - M. TAHA JANAN
A.5.2 Mthode de Doolittle
Identique celle de Crout mais avec ici lii = 1.
=
1......
.....
0...1...
.....
0...0...1
0....0...01
0...0...001
321
321
3231
21
njnnn
iii
llll
lll
ll
l
L
=
nn
in
nj
nj
nj
u
u
uuu
uuuu
uuuuu
U
...0...000
.....
......000
.....
......00
.......0
......
3333
222322
11131211
Nombre doprations : TD = 2n3/3+2n2
A 5 2 M h d d D li l f l d l l
www.almohandiss.com
7/30/2019 Transfert de chaleur - Conduction
41/60
41EMI - M. TAHA JANAN
A.5.2 Mthode de Doolittle formules de calcul :
www.almohandiss.com
7/30/2019 Transfert de chaleur - Conduction
42/60
42EMI - M. TAHA JANAN
Pour k = 1 n
pour j = k n :
=
=1
1
k
r
rjkrkjkj ulau
pour i = k +1 n
=
=
1
1
1 k
rrkirik
kkik ulaul
On dtermine dabord la kime ligne de U, puis la kime colonne de L
www.almohandiss.com
7/30/2019 Transfert de chaleur - Conduction
43/60
43EMI - M. TAHA JANAN
A.5.3. Dcomposition de Cholesky
Dfinition : Matrice dfinie positive :
Une matrice A est dfinie positive lorsque pour tout vecteur x non nul de
Rn on a xt.A.x > 0.
PripritA dfinie positive ssi Tous les mineurs diagonaux > 0.
Mthode de Cholesky :
Une matrice symtrique dfinie positive peut tre dcompose comme suit :
tLLA =
L : matrice infrieure
Lt : transpose de L
Nombre doprations : TCh = n3/3 + n2 +8n /3-2 ~ moiti LU
Exercice : Etablir les expressions des lments de L.
www.almohandiss.com
7/30/2019 Transfert de chaleur - Conduction
44/60
44EMI - M. TAHA JANAN
A.5.3. Dcomposition de Cholesky dtermination des lij
Pour i = 1 n
=
=1
1
2i
k
kiiiii lal
pour j = i +1 n
=
=
1
1
1 i
k
kikjij
ii
ij llal
l
B Mthodes itratives
www.almohandiss.com
7/30/2019 Transfert de chaleur - Conduction
45/60
45EMI - M. TAHA JANAN
Mthode itrative :
Pour rsoudre un systme Ax=b o A est une matrice (n,n) et b ,
on construit des suites
qui vrifient la relation:
nIR
{ (p) np IN
x dans IR
(p+1) (p)x = Mx + c
M matrice (n,n) et c tant dfinis partir de A et b.nIR
Dans la suite, A est suppose relle et rgulire.
B- Mthodes itratives
Description des mthodes usuelles
www.almohandiss.com
7/30/2019 Transfert de chaleur - Conduction
46/60
46EMI - M. TAHA JANAN
Description des mthodes usuelles
A partir d un vecteur x(0) quelconquepris dans , on construit la suite de
vecteurs x(p) dans suivant les formules:nIR
nIR
n(p+1) (p)
i iji jii j 1
j in
(p+1) (p) (p)i iji i j
ii j 1
1(1) i 1.....n x (b a x )
a
1(2) i 1.....n x x (b a x )
a
=
=
= =
= = +
1. Mthode de Jacobi
a) par points
Remarque: La mthode ne peut tre mise en uvre que si
iia 0, pour i=1 n
b) bl
www.almohandiss.com
7/30/2019 Transfert de chaleur - Conduction
47/60
47EMI - M. TAHA JANAN
b) par blocs
Le systme Ax=b est crit sous la forme par blocs suivante
11 12 1j 1r1 1
21 22 2 j 2r 2 2
i ii1 i2 ij ir
r rr1 r2 rj rr
A A A A X B
A A A A X B
X BA A A A
X BA A A A
=
L L
L L
M MM M M M
L L
M MM M M M
L L
Pour i=1 r ,Aii sont des matrices carres (mi,mi) supposes inversibles. On a
donci im m
i iX IR et B IR .
www.almohandiss.com
7/30/2019 Transfert de chaleur - Conduction
48/60
48EMI - M. TAHA JANAN
La formule par points (1) stend en une formule par blocs de la faon
suivante
r1
ii i iji j
j 1j i
(3) i=1,.....,r X A (B A X )
=
= (p)(p+1)
Si mi=1, pour i=1 r, les matrices Aii se rduisent des scalaires et la
mthode par blocs concide avec la mthode par points.
2. Mthode de Gauss-Seidel
www.almohandiss.com
7/30/2019 Transfert de chaleur - Conduction
49/60
49EMI - M. TAHA JANAN
a) par points
Au lieu dattendre une itration entire comme il est fait dans la mthode de
Jacobi, on corrige au fur et mesure.
11 1 12 2 1n n 1
i1 1 ii 1 i 1 ii i ii 1 i 1 in n i
n1 1
.....
.......................
..........................
.......
a x a x a x b
a x a x a x a x
...................
. a........
....
x b
a x .
+ +
+ + + =
+ + + + =
+
(p) (p)
(p) (p)
(p+1)
(p+1) (p+1) (p+1)
(p+1)
M
M
nn 1 n 1 nn n na x a x. b
+ + =
(p+1) (p+1)
On tire de lquation ni, les valeurs des autres composantes tant fixes pour ji.
ix(p+1)
jx(p+1)
jx(p)
On obtient alors les formules:
www.almohandiss.com
7/30/2019 Transfert de chaleur - Conduction
50/60
50EMI - M. TAHA JANAN
Comme pour Jacobi, la mthode ne peut tre mise en uvre que si
iia 0, pour i=1 n
On obtient alors les formules:
i 1 n
i ij iji j jii j 1 j i 1
i 1 n
i ij iji i j jii j 1 j i
1(4) i 1.....n x (b a x a x )a
1(5) i 1.....n x x (b a x a x )a
= = +
= =
= =
= = +
(p+1) (p+ (1)
(p+1)
p)
(p) (p)(p+1)
b) par blocs
www.almohandiss.com
7/30/2019 Transfert de chaleur - Conduction
51/60
51EMI - M. TAHA JANAN
b) par blocs
On reprend la dcomposition par blocs introduite pour la mthode de Jacobi.
La formule par points (4) stend en une formule par blocs de la faon
suivante
i 1 r1ii i ij iji j j
j 1 j i 1
(6) i=1,.....,r X A (B A X ) A X )
= = +
= (p)(p+1) (p+1)
I-3 mthode S.O.R. par points
www.almohandiss.com
7/30/2019 Transfert de chaleur - Conduction
52/60
52EMI - M. TAHA JANAN
En vue dacclrer la convergence de la mthode de Gauss-Seidel, on introduitun paramtre rel
i 1 n
i ij iji i j jii j 1 j i 1
i 1 n
i ij iji i j j
ii j 1 j i
(7) i 1...n x (1 )x (b a x a x )a
(8) i 1...n x x (b a x a x )a
= = +
= =
= = +
= = +
(p) (p)
(p) (p)
(p+1) (p+1)
(p+1) (p+1)
: pondration
Si =1 "S.O.R.=Gauss-Seidel"
R
www.almohandiss.com
7/30/2019 Transfert de chaleur - Conduction
53/60
53EMI - M. TAHA JANAN
Remarques:
a) la mthode ne peut tre mise en uvre que si
iia 0, pour i=1 n
b) On peut aussi dfinir une mthode S.O.R. par blocs.
c) En pratique, doit tre pris dans . Cest une condition
ncessaire de convergence.
] [0,2
I-4 Test d arrt
www.almohandiss.com
7/30/2019 Transfert de chaleur - Conduction
54/60
54EMI - M. TAHA JANAN
I 4 Test d arrt
Les mthodes directes le sont au sens o elles fournissent la solution dusystme en un nombre fini doprations lmentaires.
Par contre, Jacobi,Gauss-Seidel et S.O.R. sont des mthodes itratives .
Pour dterminer quand on arrte litration, il faut introduire un test darrt
bas sur un critre permettant destimer si on est proche de la solution.
Par exemple, le plus simple est un test sur le rsidu.
(p)Ax - b
est une norme sur et un rel positif petit choisir en fonction
du problme
nIR
Ecritures matricielles
www.almohandiss.com
7/30/2019 Transfert de chaleur - Conduction
55/60
55EMI - M. TAHA JANAN
A=D-E-F D : partie diagonale de AE : oppos de la partie infrieure de A
F : oppos de la partie supieure de A
(p 1) (p)
x x bavec (
)
+
= ++ =
-1
--1 1EDJ D(9)
J = AF I - DJacobi
(p+1) (p) -1x = x + ( ) b
avec
-1
D
D
- E(10)
= ( - )E F
1
1
L
L
Gauss-Seidel
(p+1) (p) -1x = x + (D - E) b
avec [(1- + ]
-1ED D
(11)= ( - ) F
L
L )
S.O.R
Convergence des mthodes itratives
www.almohandiss.com
7/30/2019 Transfert de chaleur - Conduction
56/60
56EMI - M. TAHA JANAN
Dfinition :
Soit A une matrice(n,n) valeurs relles ou complexes.
On dit que A est diagonale strictement dominante si
n
ii ij
j=1j i
a > a i = 1 n
Lemme de Hadamard:A diagonale strictement dominante A rgulire
Convergence des mthodes itratives
Thorme 3
www.almohandiss.com
7/30/2019 Transfert de chaleur - Conduction
57/60
57EMI - M. TAHA JANAN
Thorme 4 (Kahan)La matrice ditration de S.O.R. par points ou par
blocs vrifie La mthode S.O.R. n est
donc pas convergente si .
( ) 1 . L
] [0,2
Thorme 3
Les mthodes de Jacobi et Gauss-Seidel par points pourrsoudre un systme de matrice diagonale strictement
dominante sont des itrations linaires convergentes.
Lw= (D-E)-1[(1-)D+F]
Exemple :
www.almohandiss.com
7/30/2019 Transfert de chaleur - Conduction
58/60
58EMI - M. TAHA JANAN
Soit rsoudre le systme suivant :
=+
=++
=+
31123
1972
34
zyx
zyx
zyx
( )( )
( )
+=
=
+=
+
+
+
12/331
7/219
4/3
)()()1(
)()()1(
)()()1(
ppp
ppp
ppp
yxz
zxy
zyxJacobi :
0000
zyxitration
www.almohandiss.com
7/30/2019 Transfert de chaleur - Conduction
59/60
59EMI - M. TAHA JANAN
Avec (x,y,z)(0)= (0,0,0,)
32117
32116
32,000000021,0000000115
3,000000011,999999990,9999999414
2,999999842,00000011,0000001113
2,999999761,99999930,9999997812
2,9999991221,0000028911
3,000006891,999995310,9999965510
3,000016482,000030281,000008179
3,000054222,000021550,999866898
2,999707982,00024041,000070597
2,999000421,998718060,999658376
2,996683531,998050041,006145045
3,011647891,987067741,001000924
3,05629962,052295921,01711313
3,199404762,130952380,71726192
2,583333332,714285710,751
( )( )
+=++
+
7/219
4/3
)()1()1(
)()()1(
ppp
ppp zyx
G S id l
www.almohandiss.com
7/30/2019 Transfert de chaleur - Conduction
60/60
60EMI - M. TAHA JANAN
( )
( )
+=
=
+++
++
12/331
7/219
)1()1()1(
)()1()1(
ppp
ppp
yxz
zxyGauss-Seidel :
3219
321,0000000028
2,9999999961,9999999871,0000000147
3,0000000672,0000000130,9999992366
3,0000014382,0000044950,9999962265
2,9999760861,9999911821,0002605184
2,9995406911,9984986181,0010075643
3,0084945442,0044642860,9114583332
3,1458333332,50,751
0000
zyxItration