Terminologie

Nous vous invitons maintenant à revoir la terminologie concernant les matrices triangulaires.
Nous appelerons 'décomposition LU' de A toute écriture de A sous la forme d'un produit A=LU où:
Essayons maintenant de voir l'intérêt d'une telle décomposition dans le cas où A est la matrice d'un système de Cramer.
Les systèmes triangulaires se résolvent instantanément. Supposons maintenant A ainsi décomposée.
Le système AX=B s'écrit LUX=B
Posons UX=Y
Alors on a LY=B, donc Y est solution d'un système triangulaire inférieur.
Y étant connu X est solution d'un système triangulaire supérieur dont Y est second membre.
La résolution de AX=B se ramène donc à la résolution de deux systèmes triangulaires successifs.
La factorisation de type LU est donc une méthode de résolution. Elle semble a priori plus complexe que la méthode du pivot de Gauss, mais elle a cependant un intérêt indéniable.
Dans la méthode de Gauss, si on change le second membre B, tous les calculs sont à refaire. Si A est décomposée, la méthode de résolution ne dépend plus de B (mais les résultats en dépendent...).
On préfèrera donc une méthode par décomposition, chaque fois qu'on a à résoudre plusieurs systèmes avec la même matrice et des seconds membres distincts.
Il existe plusieurs algorithmes de décomposition LU.
La résolution est encore facilitée quand une des deux matrices triangulaires possède uniquement des 1 sur la diagonale.
Nous présenterons ici la méthode dite 'de Crout', pour laquelle les éléments diagonaux de U sont tous égaux à 1.
Posons:
A= (αi,j) 1 ≤ i,j ≤ n
L= (li,j) 1 ≤ i,j ≤ n
U= (ui,j) 1 ≤ i,j ≤ n
Posant A=LU en égalant les coefficients, il vient des relations de récurrence:
k-1
li,ki,k - Σ li,huh,k
h=0

pour i ≥ k
n-1
Σ lk,huh,j
h=0
uk,j= αk,j -   _______
lk,k

pour j>k
Le principal problème vient du fait que les calculs sont impossibles si on est dans le cas où lk,k = 0. Il faut alors procéder à un 'pivotage', c'est à dire effectuer une même transposition sur les lignes de L et les lignes de A de façon à amener en première position une ligne de L avec lk,k ≠ 0. Il est facile de vérifier que si A est inversible on peut toujours trouver un tel pivot. Cette fois encore on peut optimiser en choisissant le meilleur parmi les possibles.
Il existe d'autres méthodes en particulier celle dite 'de Doolittle' pour laquelle ce sont les éléments diagonaux de L qui sont égaux à 1. Nous ne jugeons pas utile de développer cet algorithme ici, les manipulations sur les lignes étant simplement remplacées par des manipulations sur les colonnes.
Voici maintenant une appliquette qui vous permettra de visualiser des factorisations LU pour des matrices d'ordre 4 à coefficients réels.
Appuyer seulement sur le bouton "Go!".

Applet réalisée avec la bibliothèque Jama du groupe Mathworks.

Café Python

Voici un programme calculant une factorisation 'exacte' par la méthode de Crout avec pivotage. L'utilisation du module psyco ne sert qu'à améliorer les performances.

Voici le résultat d'une exécution:

(0,0,4,6,6,7,0)

(7,3,6,8,3,1,3)

(5,0,3,6,8,8,8)

(6,4,8,3,0,3,9)

(7,9,8,3,7,3,0)

(2,6,5,7,3,0,8)

(0,6,5,2,2,2,6)

----------------

(7,0,0,0,0,0,0)

(5,-15/7,0,0,0,0,0)

(0,0,4,0,0,0,0)

(6,10/7,2,-20/3,0,0,0)

(7,6,-8/5,-9/5,93/4,0,0)

(2,36/7,1/5,51/10,117/8,6619/1550,0)

(0,6,7/5,7/10,129/8,2709/775,-14790/6619)

----------------

(1,3/7,6/7,8/7,3/7,1/7,3/7)

(0,1,3/5,-2/15,-41/15,-17/5,-41/15)

(0,0,1,3/2,3/2,7/4,0)

(0,0,0,1,1/4,-21/40,-31/20)

(0,0,0,0,1,1617/1550,1061/2325)

(0,0,0,0,0,1,34768/6619)

(0,0,0,0,0,0,1)

----------------

(7,3,6,8,3,1,3)

(5,0,3,6,8,8,8)

(0,0,4,6,6,7,0)

(6,4,8,3,0,3,9)

(7,9,8,3,7,3,0)

(2,6,5,7,3,0,8)

(0,6,5,2,2,2,6)

----------------

(0,1,0,0,0,0,0)

(0,0,1,0,0,0,0)

(1,0,0,0,0,0,0)

(0,0,0,1,0,0,0)

(0,0,0,0,1,0,0)

(0,0,0,0,0,1,0)

(0,0,0,0,0,0,1)

----------------

(0,0,4,6,6,7,0)

(7,3,6,8,3,1,3)

(5,0,3,6,8,8,8)

(6,4,8,3,0,3,9)

(7,9,8,3,7,3,0)

(2,6,5,7,3,0,8)

(0,6,5,2,2,2,6)

Voici maintenant un programme utilisant la bibliothèque scipy.linalg:

Voici le résultat de l'exécution:

(array([[ 1., 1., 1.],

[ 1., 1., -1.],

[ 0., 0., 3.]]), array([0, 1, 2]))

Il faut naturellement interpréter ce résultat:
L est:
1 0 0
1 1 0
0 0 3
U est:
1 1 1
0 1 -1
0 0 1
Et enfin les numéros des lignes pivot sont 0,1,2 (pas de pivotage).