Analyse numérique : méthode de factorisation de Gauss

Résumé du document

Cours d'analyse numérique traitant à la fois de la méthode de Gauss et de la Factorisation LU. Cette présentation de 50 diapositives vous permettra de bien comprendre et assimiler ces aspects.

Extraits

[...] X triang. sup. Supposons A=L1U1=L2U2 U1 triang. sup. triang. sup. L1 triang. inf.à diag. unité X triang. [...]

[...] < number > I-3 Programmation de la factorisation LU aucun calcul pour effectuer le produit de matrices . k élément qui n'est plus utilisé après le traitement complet de la ligne < number > Algorithme de factorisation -12 Simulation sur un exemple où algorithme de factorisation k=1 r=12/2=6 -12 - k=2 < number > III Matrices à structure particulière III-1 Matrice symétrique Proposition 4 Soit A une matrice régulière et symétrique. Si la phase d'élimination de Gauss s'effectue sans permutation de lignes alors toutes les matrices k=1 à n sont symétriques. [...]

[...] Démonstration: Soit A=LU . On introduit la matrice diagonale U régulière D régulière On pose L1=LD et U1=D-1U A=L1U1 A=At Unicité de la factorisation soit A=LDLt Remarque dans le cas où A est s.d.p. : A=LDLt avec dii>0 i=1 à n On pose d'où A=LD1/2D1/2Lt avec B=LD1/2, on obtient A=BBt dite factorisation de Cholesky < number > III-2 Matrice à structure bande Définition 2 On dit qu'une matrice est de structure bande avec une demi-largeur de bande m si m est le plus petit entier tel que i-j aij=0 n-m n-m m+1 m+1 Une matrice tridiagonale a une demi-largeur de bande égale à 1. [...]

[...] En pratique, on ne retient qu'une estimation asymptotique lorsque , suffisante pour les systèmes de grande taille. Pour la méthode de Gauss, on obtient: Ses estimations s'obtiennent à partir de l'algorithme en utilisant les formules: < number > Illustration numérique montrant l'importance du choix d'une méthode de résolution: Formules de Cramer donnant la solution d'un système Dj est le déterminant d'une matrice Le calcul du déterminant par une méthode de développement par ligne conduit à un coût de résolution supérieur à inférieur à 1/100 seconde par Gauss de l'ordre de 10185 l 'age de l'Univers par méthode de Cramer Temps de résolution sur un système (100,100) sur un calculateur à 100 Mflops: < number > I-4 Un résultat théorique admis Ak désigne les sous-matrices principales de A définies par Théorème 1 Si det(Ak) 0 pour k=1 à alors la phase d'élimination est faisable sans permutation de lignes et les éléments diagonaux de la matrice triangulaire supérieure U ainsi obtenue sont données par Conséquences: Sur une matrice s.d.p. [...]

[...] det(A(k+1))=det(M(k)A(k)) =det(M(k))det(A(k)) det(A(k+1))=det(A(k)) k=1 à n-1 det(A)=det(U) A inversible inversible pour k=1 à n L'élimination de xk n'est possible que si Dans ce cas est dit pivot de l'étape k. Sinon le processus d'élimination doit être modifié. 2ème cas: L'élimination de xk est donc déjà faite La phase d'élimination peut donc toujours être menée jusqu'à la fin. On poursuit l'élimination avec comme pivot de l'étape k . 1er cas: On permute l'équation k avec l'équation nouveau système Remarques: det(U) où p est le nombre de permutations d'équations effectuées dans la phase d'élimination. det(A)=0 det(U)=0 La phase de remontée complète n'est possible que si A est inversible (régulière). [...]