Décomposition LU

En algèbre linéaire, la décomposition LU est une méthode de décomposition d'une matrice comme produit d'une matrice triangulaire inférieure (comme lower, inférieure en anglais) par une matrice triangulaire supérieure (comme upper, supérieure). Cette décomposition est utilisée en analyse numérique pour résoudre des systèmes d'équations linéaires. Soit une matrice carrée. On dit que admet une décomposition LU s'il existe une matrice triangulaire inférieure formée de 1 sur la diagonale, notée , et une matrice triangulaire supérieure, notée , qui vérifient l'égalité Il n'est pas toujours vrai qu'une matrice admette une décomposition LU. Cependant dans certains cas, en permutant des lignes de , la décomposition devient possible. On obtient alors une décomposition de la forme où est une matrice de permutation. Bien que les décompositions LU et PLU conduisent à des formules distinctes, généralement quand on parle de la décomposition LU, on fait référence à l'une ou l'autre de ces décompositions. La matrice symétrique se factorise de la façon suivante : Cette factorisation matricielle permet de résoudre des systèmes d'équations linéaires où les coefficients des inconnues sont les mêmes, mais avec plusieurs seconds membres différents. Soit à déterminer le vecteur d'inconnues associé au second membre : Ce problème est donc équivalent à la résolution de que l'on peut mettre, en posant , sous la forme : On trouve les composantes de par des substitutions élémentaires, puisque d'abord donc , puis , donc , etc. Cette étape est appelée descente, puisqu'on résout le système en descendant de à . Il reste à calculer les composantes du vecteur en résolvant le système triangulaire supérieur : ce qui se fait de manière similaire, mais en calculant d'abord : etc. en remontant (étape dite de remontée). Remarque. - Les matrices triangulaires et auraient pu être inversées aisément en utilisant l'élimination de Gauss-Jordan.