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 :

Avec l'élimination de Gauss standard, chaque résolution coûte opérations. Pour systèmes, le coût total serait .

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

• Factorisation (une seule fois) :
• Chaque résolution :

Pour systèmes, le coût devient , une économie considérable !

Principe de la décomposition

L'idée fondamentale

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

où :

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

Lien avec l'élimination de Gauss

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

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

Formules de calcul (méthode de Doolittle)

Calcul des éléments

En développant le produit , on obtient les formules suivantes :

Pour les éléments de U (ligne , colonne avec ) :

Pour les éléments de L (ligne , colonne avec ) :

Ordre des calculs

L'algorithme procède colonne par colonne :

1. Pour chaque colonne :
   • D'abord calculer (éléments de U dans la colonne j)
   • Puis calculer (éléments de L sous la diagonale)

Exemple détaillé

Factorisons la matrice :

Colonne 1

Éléments de U :

Éléments de L :

Colonne 2

Éléments de U :

Éléments de L :

Colonne 3

Éléments de U :

Résultat

Vérification

Algorithme de factorisation LU

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 ?

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

Pour une matrice 3×3 :

• Mineur d'ordre 1 :
• Mineur d'ordre 2 :
• Mineur d'ordre 3 :

Généralisation : Pour une matrice , il faut vérifier que les mineurs principaux sont non nuls :

Explicitement :

Autrement dit, toutes les sous-matrices principales doivent être inversibles.

Que faire si un mineur est nul ?

Si un mineur principal est nul, la factorisation LU standard échoue. Solutions :

1. Utiliser le pivotage : où est une matrice de permutation
2. 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)

• a des 1 sur la diagonale
• est quelconque

Méthode de Crout

• est quelconque
• a des 1 sur la diagonale

Factorisation de Cholesky

Pour les matrices symétriques définies positives :

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 :

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

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.