Math 15 Minutes - Devenir fort en Maths pour intégrer une prépa scientifique

Algorithme de factorisation LU d’une matrice

Dans cet article nous allons découvrir un algorithme simple de factorisation LU d’une matrice.

 

factorisation lu matrice

 

Position du problème

Parfois, on doit résoudre des problèmes de la forme Ax = b1, Ax = b2, … Où A est une matrice et x un vecteur. Dans ce cas il est plus pratique de remplacer A par un produit de matrices LU où L est une matrice triangulaire inférieure unipotente et U une matrice échelonnée.

On cherche donc A = LU

 

Quelques définitions

Matrice triangulaire inférieure unipotente

Une matrice triangulaire inférieure unipotente est une matrice triangulaire (donc n x n) inférieure dont la diagonale n’est constituée que de 1.

Elle est inversible.

matrice triangulaire inferieure unipotente

Matrice échelonnée

Une matrice échelonnée est souvent le résultat de la méthode du pivot de Gauss. C’est une matrice dont :

  • toutes les lignes non nulles sont au-dessus des lignes nulles
  • le coefficient principal de chaque ligne se trouve dans une colonne située à droite de celle du coefficient principal de la ligne au-dessus d’elle
  • tous les coefficients situés dans une colonne en dessous d’un coefficient principal sont nuls.

Elle est échelonnée réduite si :

  • le coefficient principal de toute ligne est égal à 1
  • les coefficients principaux sont les seuls éléments non nuls de leur colonne.

matrice echelonnee

 

Factorisation LU

Soit A une matrice m x n. Nous allons chercher :

  • L matrice n x n triangulaire inférieure unipotente
  • U matrice m x n échelonnée

telles que :

  • A = LU

Remarque : le choix de la lettre L vient de « Left ». Et U de « Upper ».

 

Utilité de la factorisation LU

Si A = LU, Ax = b est équivalent à L(Ux) = b. En posant y = Ux, chercher Ax = b c’est résoudre :

  • Ly = b
  • Ux = y

On résout la première, puis la seconde. Ce qui est facilité car ces matrices sont triangulaires.

C’est utile quand on a plusieurs équations Ax = b à résoudre.

 

Algorithme de factorisation LU

On supposera que l’on peut transformer A en une matrice échelonnée sans avoir à échanger des lignes.

L’algorithme est à peu près le suivant :

  • on transforme A en une matrice échelonnée
  • on utilise les coefficients de la matrice échelonnée en divisant par la valeur du pivot de Gauss la colonne pour remplir la matrice L.

Cela sera plus clair avec un exemple !

 

L’exemple suivant est tiré de l’excellent livre Algèbre Linéaire et applications.

Soit donc la matrice :

factorisation-LU-exemple-1

 

On applique la méthode du Pivot de Gauss sans permutation de lignes.

Première colonne de L

Le premier pivot est le 2 du haut de la première colonne. La première colonne de L sera donc (1, -2, 1, -3), colonne obtenue en divisant la première colonne de A par le pivot 2.

 

Deuxième colonne de L

Après la première passe de la méthode du pivot de Gauss, la matrice est équivalente à :

factorisation-LU-exemple-2

La deuxième colonne de L va donc être (0, 1, -3, 4). Attention, on part du pivot. Le premier coefficient est donc 0.

 

Troisième colonne de L

On passe à l’étape suivante avec le pivot de Gauss. La matrice équivalente est :

factorisation-LU-exemple-3

 

ATTENTION : ici, la 3ème colonne n’est pas pivot ! On se rappellera que L est une matrice 4 x 4 alors que A est une matrice 4 x 5. Il faut donc « perdre des colonnes » ! La 3ème colonne de L sera donc prise sur la colonne pivot suivante : la 4ème. On obtient (0, 0, 1, 2).

Quatrième colonne de L

La dernière étape du pivot de Gauss donne :

factorisation-LU-exemple-4

La dernière colonne de L est donc (0, 0, 0, 1).

 

Résultat de la factorisation LU

On obtient donc :

factorisation LU resultat

 

Algorithme de factorisation LU : le résumé

Voici une image qui résume l’algorithme.

 

algorithme de factorisation lu matrice resume

 

Photo: Alexas_Fotos

Leave a reply

Your email address will not be published.

You may use these HTML tags and attributes:

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>