[PDF] Analyse Numérique 0 0 On suppose que la matrice

View - Download Analyse Numérique 0 0

Previous PDF

Next PDF

Universit´e de Nice Sophia-AntipolisLicence L3 Math´ematiques Ann´ee 2008/2009

Analyse Num´eriqueCorrig´e du TD 6

EXERCICE 1

Matrices diagonales, triangulaires

1.1 Matrices diagonales

SoitD= (dii)i=1,...,nune matrice diagonale d"ordren >0. Donner une condition n´ecessaire et suffisante pour queDsoit inversible. On peut repr´esenterDsous forme du tableau suivant : (d 11 ...0 d ii0 d nn))))))))

Commedet D=n?

i=1d ii, on a

Dinversible??det D?= 0??dii?= 0,?i= 1,...,n.

1.2 Matrices triangulaires inf´erieures

SoitL= (lij)i,j=1,...,nune matrice triangulaire inf´erieure d"ordren >0. a. Sous quelle condition n´ecessaire et suffisanteLest-elle inversible?

La matriceLpeut se mettre sous la forme suivant :

(l 11 l

21l22......

l

1ilijlii0

.ln-1n-1 l n1lnj···lnn-1lnn)))))))))))))) d"o`u la matrice triangulaire inf´erieureLpeut ˆetre caract´eris´ee par : 1 Universit´e de Nice Sophia-AntipolisLicence L3 Math´ematiques Ann´ee 2008/2009 lij= 0 sii < j,?i,j= 1,...,n.

Puisquedet L=n?

i=1l ii, on a

Linversible??det L?= 0??lii?= 0,?i= 1,...,n.

b. On suppose que la matrice triangulaire inf´erieureLest inversible. Soitb un vecteur colonne ayantncomposantes. Donner un algorithme qui permet de r´esoudre l"´equation d"inconnuey:

Ly=b.(1.1)

Commelii?= 0,?i= 1,...,n, la r´esolution du syst`eme (1.1) s"´ecrit y1=b1l11, y i=1 lii? b i-i-1? j=1l ijyj? ,?i= 2,...,n. (1.2) Quel est le coˆut de cet algorithme en termes d"op´erations ´el´ementaires (addi- tions, multiplications, divisions) ? Le calcul dey1demande 1 division (div) dans l"algorithme (1.2). Pourifix´e dans{1,...,n}, le calcul deyipar l"algorithme (1.2) requiert 1 division (div), i-1 additions (add) eti-1 multiplications (mult).

Au total le coˆutCLde l"algorithme (1.2) est

C

L= 1 div +n?

i=2? (i-1) add + (i-1) mult + 1 div? = 1 div + n? i=21 div +n-1? k=1kadd +n-1? k=1kmult (n-1)n

2add +(n-1)n2mult +ndiv.

Le nombre d"op´erations ´el´ementairesCLest de l"ordre den2,i.e.CL=O(n2). 2 Universit´e de Nice Sophia-AntipolisLicence L3 Math´ematiques Ann´ee 2008/2009

1.3 Matrices triangulaires sup´erieures

On consid`ere une matrice triangulaire sup´erieureUd"ordren >0 . a. Donner une condition n´ecessaire et suffisante pour queUsoit inversible.

La matriceUpeut se mettre sous la forme suivant :

(u

11u12···u1ju1n-1u1n

u

22u2n-1u2n......

u iiuijuin 0 u n-1n-1un-1n u nn)))))))))))))) d"o`u la matrice triangulaire inf´erieureUpeut ˆetre caract´eris´ee par : u ij= 0 sii > j,?i,j= 1,...,n.

Commedet U=n?

i=1u ii, on a

Uinversible??det U?= 0??uii?= 0,?i= 1,...,n.

b. On suppose que la matrice triangulaire sup´erieureUest inversible. Soity un vecteur colonne donn´e ayantncomposantes. Ecrire un algorithme qui permet de r´esoudre l"´equation d"inconnuex:

U x=y .(1.3)

Lesuii´etant non nuls, l"inconnuexsolution du syst`eme lin´eaire (1.3) est donn´ee par xn=ynunn, x i=1 uii? y i-n? j=i+1u ijyj? ,?i= 1,...,n-1. (1.4)

Donner la complexit´e de cet algorithme.

Le calcul dexnrequiert 1 multiplication (mult) dans l"algorithme (1.4). Pourifix´e dans{1,...,n}, le calcul dexipar l"algorithme (1.4) demande 1 division (div), n-iadditions (add) etn-imultiplications. 3 Universit´e de Nice Sophia-AntipolisLicence L3 Math´ematiques Ann´ee 2008/2009

Par suite le coˆutCUde l"algorithme (1.4) est

C

U= 1 div +n-1?

i=1? (n-i) add + (n-i) mult + 1 div? n-1? k=1kadd +n-1? k=1kmult + 1 div +n-1? i=11 div (n-1)n

2add +(n-1)n2mult +ndiv.

Le nombre d"op´erations ´el´ementairesCUest de l"ordre den2,i.e.CU=O(n2)..

Vocabulaire

L"algorithme (1.2) pour inverser les syst`emes triangulaires inf´erieurs est ditdescente ousubstitution directe. L"algorithme (1.4) pour r´esoudre les syst`emes triangulaires sup´erieurs est ditremont´eeousubstitution r´etrograde.

EXERCICE 2

M´ethode d"´elimination de Gauss

2.1 Des exemples

Effectuer une ´elimination de Gauss sur les syst`eme lin´eaires suivants (2 4 41 3 11 5 6)) (x 1 x 2 x 3)) =((21 -6)) (1 0 6 28 0-2-2

2 9 1 3

2 1-3 10))))

(x 1 x 2 x 3 x 4)))) =((((6 -2 -8 -4))))

Premier exemple

Nous ´ecrivons le premier syst`eme sous la forme du tableau (2 4 4 21 3 1 11 5 6-6)) L 1 L 2 L 3 •On effectue l"´elimination de Gauss. On a successivement (2 4 4 20 1-1 0

0 3 4-7))

L2←L2-0.5L1

L

3←L3-0.5L1(2.1)

4 Universit´e de Nice Sophia-AntipolisLicence L3 Math´ematiques Ann´ee 2008/2009 (2 4 4 20 1-1 0

0 0 7-7))

L

3←L3-3L2

On obtient alors le syst`eme triangulaire suivant

?2x1+ 4x2+ 4x3= 2 x

2-x3= 0

7x3=-7

En utilisant l"algorithme de remont´ee (1.2) on a successivement x

3=-1,x2=-1,x1= 5.

L"´elimination de Gauss ci-dessus est ditesans permutation. •On peut par exemple `a l"´etape (2.1) ci-dessus, remplacer le pivot 1 par le coefficient 3 dex2de la derni`ere ligne, parce que 3>1 donne plus de stabilit´e num´erique. Dans ce cas on dit que l"on fait une ´elimination de Gauss avecpivot partiel. Dans ce contexte on obtient (2 4 4 20 3 4-7

0 1-1 0))

L3←→L2

(2 4 4 20 3 4-7 0 0-7

373)))

L

3←L3-13×L2

D"o`u on obtient le syst`eme triangulaire sup´erieur suivant ?2x1+ 4x2+ 4x3= 2

3x2+ 4x3=-7

7

3x3=73

En appliquant l"algorithme de remont´ee `a ce syst`eme on obtient x

3=-1,x2=-1,x1= 5.

•On peut enfin par exemple `a l"´etape (2.1) ci-dessus, remplacer le pivot 1 par le coefficient

le plus grand en module dans la sous-matrice 1-1 3 4 Ceci rend la m´ethode plus stable num´eriquement. Ici on trouve 4 comme nouveau pivot. Dans ce cas on dit que l"on fait une ´elimination de Gauss avecpivot partiel. Dans ce 5 Universit´e de Nice Sophia-AntipolisLicence L3 Math´ematiques Ann´ee 2008/2009 contexte on obtient((2 4 4 20 3 4-7

0 1-1 0))

L2←→L3

(2 4 4 20 4 3-7

0-1 1 0))

c2←→c3 (2 4 4 20 4 3-7 0 0 7

4-74)))

L

3←-L3+14L2

Cette derni`ere transformation donne le syst`eme lin´eaire suivant ?2x1+ 4x3+ 4x2= 2 + 4x3+ 3x2=-7 7

4x2=-74

Par application de l"algorithme de remont´ee au syst`eme triangulaire ci-dessus on obtient : x

2=-1,x3=-1,x1= 5.

Deuxi`eme exemple

On met le deuxi`eme exemple sous forme du tableau suivant (1 0 6 2 68 0-2-2-2

2 9 1 3-8

2 1-3 10-4))))

L 1 L 2 L 3 L 4 puis on effectue (1 0 6 2 60 0-50-18-50

0 9-11-1-20

0 1-15 6-16))))

L

2←L2-8L1

L

3←L3-2L1

L

4←L4-2L1(2.2)

La matrice obtenue apr`es la 1

i`ere´etape d"´elimination (2.2) a pour pivot 0. Pour continuer

la m´ethode de Gauss, on peut soit utiliser la strat´egie de pivot partiel ou soit celle de pivot

total. •Pivot partiel: on prend comme pivot le plus grand ´el´ement de la colonne (091)) 6 Universit´e de Nice Sophia-AntipolisLicence L3 Math´ematiques Ann´ee 2008/2009 Cela revient `a ´echanger la 2i`emeet la 3i`emelignes. On obtient (1 0 6 2 60 9-11-1-20

0 0-50-18-50

0 1-15 6-16))))

L

2←→L3

On continue l"´elimination :

(1 0 6 2 60 9-11-1-20

0 0-50-18-50

0 0-124

9559-1249)))))

L

4←L4-19L2

(1 0 6 2 60 9-11-1-20

0 0-50-18-50

0 0 0 2491

2250)))))

L

4←L4-1501249L3

On d´eduit le syst`eme triangulaire sup´erieur suivant ?x

1+ 6x3+ 2x4= 6

9x2-11x3-x4=-20

-50x3-18x4=-50 2491

225x4= 0

D"o`u par la formule de remont´ee on trouve

x

4= 0,x3= 1,x2=-1,x1= 0.

•Pivot total: On part de l"´etape (2.2) de l"´elimination de Gauss. Le plus grand ´el´ement

en module de la sous-matrice

0-50-18

9-11-1

1-15 6

est-50, qui se trouve `a la 2i`emeligne et `a la 3i`emecolonne de la matrice de d´epart. On positionne-50 en pivot, en ´echangeant la 2i`emecolonne et la 3i`emecolonne : (1 6 0 2 60-50 0-18-50

0-11 9-1-20

0-15 1 6-16))))

c

2←→c3

7 Universit´e de Nice Sophia-AntipolisLicence L3 Math´ematiques Ann´ee 2008/2009

On continue l"´elimination :

(1 6 0 2 60-50 0-18-50 0 0 9 74
25-9
0 0 1 285

25-1)))))))

L

3←→L3-11

50L2
L

4←→L4-15

50L2
(1 6 0 2 60-50 0-18-50 0 0 9 74
25-9
0 0 0 2491

2250)))))))

L4←→L4-19L3

Ce qui conduit au syst`eme lin´eaire suivant

?x

1+ 6x3+ 2x4= 6

-50x3-18x4=-50

9x2+74

25x4=-9

2491

225x4= 0

dont la solution est x

4= 0,x2=-1,x3= 1,x1= 0.

2.2 Cas g´en´eral

On consid`ere maintenant le cas g´en´eral d"un syst`eme lin´eaireAx=b. a. ´Ecrire un algorithme de r´esolution de ce syst`eme par la m´ethode de

Gauss.

On ´ecrit l"algorithme dans le cas avec pivot partiel. En modifiant l"´etape de la recherche de pivot, on obtient soit l"algorithme de pivot total ou soitl"´elimination de Gauss sans permutation. 8 Universit´e de Nice Sophia-AntipolisLicence L3 Math´ematiques Ann´ee 2008/2009 //Triangulation pouriallant de1`an-1faire //Recherche du pivot partiel numlignepiv=i pourkallant dei`anfaire si|A(k,i)|>|A(numlignepiv,i)|alors numlignepiv=k finsi //On met le pivot `a sa place sinumlignepiv?=ialors //On ´echange les lignes numlignepiv et i pourjallant dei`anfaire tampon=A(numlignepiv,j)

A(numlignepiv,j) =A(i,j)

A(i,j) =tampon

finpour finsi finpour //Elimination pivot=A(i,i) pourkallant dei+ 1`anfaire factpivot=A(k,i) pivot pourjallant dei`anfaire

A(k,j) =A(k,j)-factpivot?A(i,j)

finpour b(k) =b(k)-factpivot?b(i) finpour 9 Universit´e de Nice Sophia-AntipolisLicence L3 Math´ematiques Ann´ee 2008/2009 //R´esolution par la remont´ee

X(n) =b(n)

A(n,n)

pouriallant den-1`a1par pas de-1faire pourjallant dei+ 1`anfaire b(i) =b(i)-A(i,j)?X(j) finpour

X(i) =b(i)

A(i,i)

finpour b. Donner la complexit´e de cet algorithme. Le coˆut des op´erations calcul´e ici ne tient pas compte de la recherche du pivot.

On s"int´eresse `a la partie "´elimination" de l"algorithme ci-dessus. Consid´erons la i`eme

´etape de l"´elimination,i? {1,...,n}. Pour chaque lignekallant dei+ 1 `anon fait les op´erations suivantes : - une division (div) afin de calculer une fois pour toute le coefficient permettant d"ob- tenir des z´eros sous le pivot; - une adddition (add) et une multiplication (mult) permettant de mettre `a jour chaque coefficient de la lignek, ce qui correspond `a toutes les colonnes de num´erosjvariant dei`an; - une addition (add) et une multiplication (mult) permettant de mettre `a jour le second membre de la lignek,i.e.b(k). Le nombre d"op´erations pour l"´elimination de Gauss avec prise en compte du second membre s"´ecrit donc C

E=n-1?

i=1n k=i+1?

1 div +?

n? j=i(1 add + 1 mult)? + 1 add + 1 mult? n-1? i=1n k=i+1?

1 div + (n-i+ 1) add + (n-i+ 1) mult?

n-1? i=1? (n-i)div + (n-i)(n-i+ 1) add + (n-i)(n-i+ 1) mult? 10 Universit´e de Nice Sophia-AntipolisLicence L3 Math´ematiques Ann´ee 2008/2009

CE=n-1?

i=1(n-i) div +n-1? i=1(n-i)(n-i+ 1)add +n-1? i=1(n-i)(n-i+ 1) mult n-1? i=1(n-i) div +? n-1? i=1(n-i) +n-1? i=1(n-i)2? add +? n-1? i=1(n-i) +n-1? i=1(n-i)2? n-1? l=1ldiv +? n-1? l=1l+n-1? l=1l 2? add +? n-1? l=1l+n-1? l=1l 2? mult (n-1)n

2div +(n-1)n2add +n(n-1)(2n-1)6add

(n-1)n

2mult +n(n-1)(2n-1)6mult.

Il vient le nombre d"op´erations de la partie ´elimination de l"algorithme de Gauss est de l"ordren3:CE=O(n3). Or dans l"exercice 3 on a montr´e que l"algorithme de remont´ee est de l"ordre den2,CU=

0(n2). Au total l"algorithme d"´elimination de Gauss avec r´esolution du syst`eme lin´eaire

Ax=best de l"ordre den3,i.e.O(n3) o`u la matrice carr´eeAest d"ordren.

EXERCICE 3

Factorisation LU

3.1 Un exemple

On revient sur la premi`ere matrice donn´ee dans l"exercice2 : (2 4 41 3 11 5 6)) Effectuer une factorisationLUde cette matrice o`uLest une matrice triangu- laire inf´erieure ayant des1sur sa diagonale etUest une matrice triangulaire sup´erieure. 11 Universit´e de Nice Sophia-AntipolisLicence L3 Math´ematiques Ann´ee 2008/2009

D´ecompositionLU

Les mineurs principaux de la matrice propos´ee sont

2??= 2?= 0,????2 41 3????

= 2?= 0,??????2 4 41 3 11 5 6?????? = 14?= 0, Donc on peut la factoriser sous la formeLUo`uLest une matrice triangulaire inf´erieure ayant des 1 sur sa diagonale etUest une matrice triangulaire sup´erieure. Identification directeComme la matrice propos´ee est d"ordre 3, on peut´ecrire compl`etementquotesdbs_dbs46.pdfusesText_46

[PDF] algorithme racine carrée dichotomie PDF Cours,Exercices ,Examens

[PDF] algorithme recherche chaine caractere PDF Cours,Exercices ,Examens

[PDF] algorithme rendu de monnaie PDF Cours,Exercices ,Examens

[PDF] algorithme rendu de monnaie c# PDF Cours,Exercices ,Examens

[PDF] algorithme rendu de monnaie python PDF Cours,Exercices ,Examens

[PDF] algorithme résolution équation second degré complexe PDF Cours,Exercices ,Examens

[PDF] algorithme robot suiveur de ligne PDF Cours,Exercices ,Examens

[PDF] algorithme schéma de bernoulli PDF Cours,Exercices ,Examens

[PDF] algorithme scratch college PDF Cours,Exercices ,Examens

[PDF] Algorithme seconde 2nde Mathématiques

[PDF] algorithme seconde algobox PDF Cours,Exercices ,Examens

[PDF] Algorithme Seconde Boites de conserves 3ème Mathématiques

[PDF] algorithme seconde boucle pour PDF Cours,Exercices ,Examens

[PDF] algorithme seconde calculatrice PDF Cours,Exercices ,Examens

[PDF] algorithme seconde calculatrice casio PDF Cours,Exercices ,Examens