Factorisation LU — Principes

Objectifs d'apprentissage

À la fin de cette leçon, vous serez en mesure de :

Comprendre le principe de la décomposition LU
Calculer manuellement une factorisation LU pour une matrice 3×3
Identifier les formules pour les éléments de L et U
Connaître l'ordre des calculs dans l'algorithme
Comprendre les conditions d'existence de la factorisation

Prérequis

Élimination de Gauss
Multiplication de matrices

Motivation : pourquoi factoriser ?

Dans de nombreuses applications, on doit résoudre plusieurs systèmes linéaires avec la même matrice mais des seconds membres différents :

A \cdot x^{(1)} = b^{(1)}, \quad A \cdot x^{(2)} = b^{(2)}, \quad \ldots, \quad A \cdot x^{(k)} = b^{(k)}

💡

Exemples d'applications

Simulation temporelle : résolution à chaque pas de temps avec une matrice constante
Analyse de sensibilité : étude de l'effet de différentes conditions aux limites
Méthodes itératives : résolution répétée dans des algorithmes d'optimisation

Avec l'élimination de Gauss standard, chaque résolution coûte $O(n^3/3)$ opérations. Pour $k$ systèmes, le coût total serait $O(k \cdot n^3/3)$ .

La factorisation LU permet de « mémoriser » le travail d'élimination :

Factorisation (une seule fois) : $O(n^3/3)$
Chaque résolution : $O(n^2)$

Pour $k$ systèmes, le coût devient $O(n^3/3 + k \cdot n^2)$ , une économie considérable !

Principe de la décomposition

L'idée fondamentale

La factorisation LU consiste à décomposer une matrice $A$ en un produit de deux matrices triangulaires :

A = L \cdot U

où :

$L$ est une matrice triangulaire inférieure (Lower) avec des 1 sur la diagonale
$U$ est une matrice triangulaire supérieure (Upper)

\begin{pmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{pmatrix} = \begin{pmatrix} 1 & 0 & 0 \\ l_{21} & 1 & 0 \\ l_{31} & l_{32} & 1 \end{pmatrix} \cdot \begin{pmatrix} u_{11} & u_{12} & u_{13} \\ 0 & u_{22} & u_{23} \\ 0 & 0 & u_{33} \end{pmatrix}

Lien avec l'élimination de Gauss

La matrice $U$ est exactement la matrice triangulaire supérieure obtenue après l'élimination de Gauss !

La matrice $L$ contient les multiplicateurs utilisés pendant l'élimination :

l_{ij} = m_{ij} = \frac{a_{ij}^{(j)}}{a_{jj}^{(j)}} \quad \text{pour } i > j

Formules de calcul (méthode de Doolittle)

Calcul des éléments

En développant le produit $L \cdot U = A$ , on obtient les formules suivantes :

Pour les éléments de U (ligne $i$ , colonne $j$ avec $j \geq i$ ) :

u_{ij} = a_{ij} - \sum_{k=1}^{i-1} l_{ik} \cdot u_{kj}

Pour les éléments de L (ligne $i$ , colonne $j$ avec $i > j$ ) :

l_{ij} = \frac{1}{u_{jj}} \left( a_{ij} - \sum_{k=1}^{j-1} l_{ik} \cdot u_{kj} \right)

Ordre des calculs

L'algorithme procède colonne par colonne :

Pour chaque colonne $j = 1, 2, \ldots, n$ :
- D'abord calculer $u_{1j}, u_{2j}, \ldots, u_{jj}$ (éléments de U dans la colonne j)
- Puis calculer $l_{j+1,j}, l_{j+2,j}, \ldots, l_{nj}$ (éléments de L sous la diagonale)

⚠️

Ordre important !

Les calculs doivent être effectués dans le bon ordre car chaque élément dépend des éléments précédemment calculés.

Exemple détaillé

Factorisons la matrice :

A = \begin{pmatrix} 2 & 1 & 1 \\ 4 & 3 & 3 \\ 8 & 7 & 9 \end{pmatrix}

Colonne 1

Éléments de U :

$u_{11} = a_{11} = 2$

Éléments de L :

$l_{21} = a_{21}/u_{11} = 4/2 = 2$
$l_{31} = a_{31}/u_{11} = 8/2 = 4$

Colonne 2

Éléments de U :

$u_{12} = a_{12} = 1$
$u_{22} = a_{22} - l_{21} \cdot u_{12} = 3 - 2 \cdot 1 = 1$

Éléments de L :

$l_{32} = (a_{32} - l_{31} \cdot u_{12})/u_{22} = (7 - 4 \cdot 1)/1 = 3$

Colonne 3

Éléments de U :

$u_{13} = a_{13} = 1$
$u_{23} = a_{23} - l_{21} \cdot u_{13} = 3 - 2 \cdot 1 = 1$
$u_{33} = a_{33} - l_{31} \cdot u_{13} - l_{32} \cdot u_{23} = 9 - 4 \cdot 1 - 3 \cdot 1 = 2$

Résultat

L = \begin{pmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 4 & 3 & 1 \end{pmatrix}, \quad U = \begin{pmatrix} 2 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 2 \end{pmatrix}

Vérification

L \cdot U = \begin{pmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 4 & 3 & 1 \end{pmatrix} \cdot \begin{pmatrix} 2 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 2 \end{pmatrix} = \begin{pmatrix} 2 & 1 & 1 \\ 4 & 3 & 3 \\ 8 & 7 & 9 \end{pmatrix} = A \quad \checkmark

Algorithme de factorisation LU

factorisation_lu.pypython

import numpy as np

def factorisation_lu(A):
  """
  Factorisation LU sans pivotage (méthode de Doolittle).

  Paramètres:
      A : matrice carrée (n x n)

  Retourne:
      L : matrice triangulaire inférieure avec 1 sur la diagonale
      U : matrice triangulaire supérieure
  """
  n = len(A)
  L = np.eye(n)  # Matrice identité (1 sur la diagonale)
  U = np.zeros((n, n))

  for j in range(n):  # Pour chaque colonne
      # Calcul des éléments de U (ligne i <= j)
      for i in range(j + 1):
          somme = sum(L[i, k] * U[k, j] for k in range(i))
          U[i, j] = A[i, j] - somme

      # Calcul des éléments de L (ligne i > j)
      for i in range(j + 1, n):
          somme = sum(L[i, k] * U[k, j] for k in range(j))
          L[i, j] = (A[i, j] - somme) / U[j, j]

  return L, U

# Exemple d'utilisation
A = np.array([[2, 1, 1],
            [4, 3, 3],
            [8, 7, 9]], dtype=float)

L, U = factorisation_lu(A)
print("L =")
print(L)
print("\nU =")
print(U)
print("\nVérification L·U =")
print(L @ U)

Conditions d'existence

Quand la factorisation LU existe-t-elle ?

🚨

Condition suffisante

La factorisation LU (sans pivotage) existe et est unique dès que les $n-1$ premiers mineurs principaux de A sont non nuls.

Un mineur principal d'ordre $k$ est le déterminant de la sous-matrice formée par les $k$ premières lignes et colonnes.

Pour une matrice 3×3 :

Mineur d'ordre 1 : $a_{11}$
Mineur d'ordre 2 : $\det\begin{pmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{pmatrix}$
Mineur d'ordre 3 : $\det(A)$

Généralisation : Pour une matrice $n \times n$ , il suffit de vérifier que les $n-1$ premiers mineurs principaux sont non nuls (pour une matrice 3×3, seuls les mineurs d'ordre 1 et 2 sont concernés) :

M_k = \det(A_{1:k, 1:k}) \neq 0 \quad \text{pour } k = 1, 2, \ldots, n-1

Explicitement :

M_1 = a_{11}, \quad M_2 = \det\begin{pmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{pmatrix}, \quad M_3 = \det\begin{pmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{pmatrix}, \quad \ldots, \quad M_{n-1} = \det(A_{1:n-1,\, 1:n-1})

Autrement dit, il suffit que les sous-matrices principales $A_{1:k, 1:k}$ soient inversibles pour $k \leq n-1$ ; le dernier mineur $M_n = \det(A)$ n'intervient pas, une matrice singulière pouvant très bien admettre une factorisation LU.

Que faire si un mineur est nul ?

Si l'un des $n-1$ premiers mineurs principaux est nul, la factorisation LU standard n'est plus garantie : l'algorithme peut buter sur un pivot $u_{jj}$ nul. Solutions :

Utiliser le pivotage : $P \cdot A = L \cdot U$ où $P$ est une matrice de permutation
Vérifier si la matrice est singulière (pas de solution unique au système)

Variantes de la factorisation

Méthode de Doolittle (utilisée ici)

$L$ a des 1 sur la diagonale
$U$ est quelconque

Méthode de Crout

$L$ est quelconque
$U$ a des 1 sur la diagonale

Factorisation de Cholesky

Pour les matrices symétriques définies positives :

A = L \cdot L^T

Cette factorisation est plus efficace (environ 2× moins d'opérations) et garantit la stabilité numérique.

Résumé

La factorisation LU décompose une matrice en un produit $A = L \cdot U$ :

L : triangulaire inférieure avec des 1 sur la diagonale (contient les multiplicateurs)
U : triangulaire supérieure (résultat de l'élimination de Gauss)

Aspect	Détail
Coût de factorisation	$O(n^3/3)$ opérations
Coût par résolution	$O(n^2)$ opérations
Condition d'existence	$n-1$ premiers mineurs principaux non nuls (suffisant)
Lien avec Gauss	U = matrice après élimination, L = multiplicateurs

Pour aller plus loin

La prochaine leçon expliquera comment utiliser la factorisation LU pour résoudre des systèmes linéaires, ainsi que les techniques de stockage compact et le pivotage.