Analyse Numérique 0 0 PDF la méthode de Gauss

MAT 1200: Introduction à lalgèbre linéaire

Factorisation LU d'une matrice. Matrice de permutation. Exemples-Exercices. méthode de Gauss en une forme échelonnée U ? Mmn

1 Méthode de Gauss et factorisation LU

C'est cette méthode que l'on généralisera ci-dessous dans l'exercice 2

Chapitre 2 Résolution des Systèmes Linéaires Ax=b Méthodes

II.1 Principe de la factorisation (décomposition). La matrice des coefficients A est factorisée sous la forme d'un produit de deux matrices A = L.U (où L

Cours 4 : Gauss et LU

Résolution de systèmes linéaires par des méthodes directes : Gauss LU

Analyse Numérique 0 0

la méthode de Gauss on peut soit utiliser la stratégie de pivot partiel Effectuer une factorisation LU de cette matrice o`u L est une matrice triangu-.

Décompositions matricielles

Décomposition LU. Méthode : On fait comme un pivot de Gauss mais on effectue les opérations de pivot sous forme de produits de matrices. Vincent Nozick.

Factorisation LU Résolution de Ax = b

diagonales par blocs creuses

3. Factorisation LU - Sections 2.6 et 2.7

inverses des matrices d'élimination. Cette matrice est triangulaire inférieure. Ceci est une factorisation (ou décomposition) LU de la matrice A.

Chapitre III: Factorisation LU

Soit A ? Mn(R) une matrice inversible. On cherche `a construire une factorisation LU de A définie par les matrices triangulaires.

Résolution de systèmes linéaires Factorisation LU

méthode numérique et par la même occasion servira de template pour ceux qui veulent faire du latex ! 1.1 Factorisation LU d'une matrice tridiagonale .

Méthode de Gauss et factorisation LU

1 Méthode de Gauss et factorisation LU Exercice1:unexemple Soient ; ; PR Onconsidèrelesystèmelinéairesuivantd’inconnuesx 1;x 2;x 3: $ & x 1 2 2 3 3 2x 1 6x 2 5x 3 x 1 2x 2 7x 3 (1) 1 Écrirelesystème(1) souslaformeAx bavecA PM 3pRqxPR3;etbPR3quel’onexplicitera 2 Est-cequelesystème(1) admetuneuniquesolutionpourtout ; ; PR?

Algèbre linéaire - MATLAB & Simulink - MathWorks France

Les méthodes de factorisation Rappelons que : Factoriser signifie : transformer une somme en un produit Comment reconnaître une somme ou un produit ? Une somme est le résultat de l’addition de deux ou plusieurs termes Exemples: (1) a b+ + 3 est une somme de 3 termes : a b et 3 (2) x y z w? + ? est une somme de 4 termes : x ?y z

Méthode de la décomposition LU

Utilité de la détermination LU Calcul de déterminant Grâce à la factorisation LUon eutp alculerc le déterminant d'une matrice arrceé avec O(2 3 n3) opérations vu que det(A) = det(L)×det(U) = det(U) = Yn k=1 u kk Résolution : Supposons qu'on veut ésoudrre le système AX= b Déompcosons Asous forme LU alors AX= bdevient (LU)X= bou

3 Factorisation LU - GERAD

Factorisation PA = LU Quand A?1 existe si un 0 apparaˆ?t `a la place d’un pivot alors on peut obtenir un pivot non-nul en interchangeant deux lignes `a l’aide d’une matrice de permutation L’ensemble des permutations n´ecessaires `a l’´elimination peut ˆetre rassembl´e en une matrice de permutation P

Searches related to méthode de factorisation lu PDF

L’ef?cacité algorithmique de la factorisation A = LU repose sur la connaissance préa- lable de L et de U L’algorithme présenté dans la Section 3 suivante montre qu’en détermi- nant une forme échelonnée U de A on détermine du même coup la factorisation A = LU

Qu'est-ce que la factorisation LU ?

La factorisation LU, ou élimination de Gauss-Jordan, exprime toute matrice carrée A comme le produit d’une permutation d’une matrice triangulaire inférieure et d’une matrice triangulaire supérieure

Quels sont les trois méthodes de factorisation?

Les trois méthodes de factorisation qu’il faut connaître sont : la mise en évidence, les produits (identités) remarquables et le groupement de termes. A. La mise en évidence Rappelons la propriété de distributivité de la multiplication par rapport à l’addition et à la soustraction :

Comment calculer la factorisation ?

Pour obtenir la factorisation complète, un algorithme itératif possible consiste à appliquer la factorisation partiellement successivement sur les compléments de Schur S k, k : A = L ( 0) U ( 0) = … = L ( k) U ( k) = … = L ( N ? 1) U ( N ? 1). où les matrices L ( k) et U ( k) sont obtenues à la k eme itération.

Qu'est-ce que la factorisation en mathématiques ?

La factorisation est une opération importante en mathématiques car elle permet, quand elle est possible, de résoudre simplement certaines équations. Souvent un problème où il faut trouver une quantité inconnue x, se transforme en une équation de la forme ax 2 + bx + c = 0. ax 2 + bx + c s'appelle un trinôme en x.

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......

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

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 :

11u12···u1ju1n-1u1n

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

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

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))

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)))

3←L3-13×L2

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

3x2+ 4x3=-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)))

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))))

2←L2-8L1

3←L3-2L1

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))))

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)))))

4←L4-19L2

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

0 0-50-18-50

0 0 0 2491

2250)))))

4←L4-1501249L3

quotesdbs_dbs33.pdfusesText_39

[PDF] echelle de mesure qualité de vie

[PDF] methode de gauss wikipedia

[PDF] questionnaire qualite de vie

[PDF] échelle qualité de vie psychiatrie

[PDF] questionnaire qualité de vie sf 36

[PDF] algorithme de horner matlab

[PDF] algorithme de horner en c

[PDF] module 1 rencontres 1ére année

[PDF] exposé sur le film intouchable

[PDF] texte au hasard d une rencontre 1ére année

[PDF] objet et methode de lanthropologie

[PDF] analyse anthropologique définition

[PDF] intouchables résumé

[PDF] démarche anthropologique définition

[PDF] enquête de terrain anthropologie

[PDF] Analyse Numérique 0 0 la méthode de Gauss

Qu'est-ce que la factorisation LU ?

Quels sont les trois méthodes de factorisation?

Comment calculer la factorisation ?

Qu'est-ce que la factorisation en mathématiques ?

Analyse Num´eriqueCorrig´e du TD 6

EXERCICE 1

Matrices diagonales, triangulaires

1.1 Matrices diagonales

Commedet D=n?

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

1.2 Matrices triangulaires inf´erieures

La matriceLpeut se mettre sous la forme suivant :

21l22......

1ilijlii0

Puisquedet L=n?

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

Ly=b.(1.1)

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

L= 1 div +n?

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

1.3 Matrices triangulaires sup´erieures

La matriceUpeut se mettre sous la forme suivant :

11u12···u1ju1n-1u1n

22u2n-1u2n......

Commedet U=n?

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

U x=y .(1.3)

Donner la complexit´e de cet algorithme.

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

U= 1 div +n-1?

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

Vocabulaire

EXERCICE 2

M´ethode d"´elimination de Gauss

2.1 Des exemples

2 9 1 3

2 1-3 10))))

Premier exemple

0 3 4-7))

L2←L2-0.5L1

3←L3-0.5L1(2.1)

0 0 7-7))

3←L3-3L2

On obtient alors le syst`eme triangulaire suivant

2-x3= 0

7x3=-7

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

0 1-1 0))

L3←→L2

373)))

3←L3-13×L2

3x2+ 4x3=-7

3x3=73

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

0 1-1 0))

L2←→L3

0-1 1 0))

4-74)))

3←-L3+14L2

4x2=-74

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

Deuxi`eme exemple

2 9 1 3-8

2 1-3 10-4))))

0 9-11-1-20

0 1-15 6-16))))

2←L2-8L1

3←L3-2L1

4←L4-2L1(2.2)

La matrice obtenue apr`es la 1

0 0-50-18-50

0 1-15 6-16))))

2←→L3

On continue l"´elimination :

0 0-50-18-50

0 0-124

9559-1249)))))

4←L4-19L2

0 0-50-18-50