Résolution d’un système triangulaire

Considérons un système inversible \(3 \times 3\) triangulaire inférieur :

\[\left[\begin{array}{lll} l_{11} & 0 & 0 \\ l_{21} & l_{22} & 0 \\ l_{31} & l_{32} & l_{33} \end{array}\right] \quad\left[\begin{array}{l} x_1 \\ x_2 \\ x_3 \end{array}\right]=\left[\begin{array}{l} b_1 \\ b_2 \\ b_3 \end{array}\right] .\]

La matrice étant inversible, ses termes diagonaux \(l_{i i}, i=1,2,3\) sont non nuls. On peut donc déterminer successivement les valeurs inconnues \(x_i\) pour \(i=1,2,3\) :

\[\begin{aligned} & x_1=b_1 / l_{11}, \\ & x_2=\left(b_2-l_{21} x_1\right) / l_{22}, \\ & x_3=\left(b_3-l_{31} x_1-l_{32} x_2\right) / l_{33} . \end{aligned}\]

Cet algorithme peut être étendu aux systèmes \(n \times n\). On l’appelle substitution directe.

1. Substitution directe et rétrograde

Substitution directe

Dans le cas d’un système \(\mathbf{L x}=\mathbf{b}\), où \(\mathbf{L}\) est une matrice inversible triangulaire inférieure d’ordre \(n(n \geq 2)\), la méthode de substitution directe s’écrit

\[\begin{aligned} x_1 & =\frac{b_1}{l_{11}} \\ x_i & =\frac{1}{l_{i i}}\left(b_i-\sum_{j=1}^{i-1} l_{i j} x_j\right), \quad i=2, \ldots, n \end{aligned}\]

On appelle ces relations formules de "descente".
L’algorithme effectue \(n(n+1) / 2\) multiplications et divisions et \(n(n-1) / 2\) additions et soustractions.
Le nombre global d’opérations pour Substitution directe est donc \(n^2\) flops
Si la matrice est diagonale il faut que \(n\) flops.

On traite de manière analogue

Substitution rétrograde

un système linéaire \(U \mathbf{x}=\mathbf{b}\), où \(U\) est une matrice inversible triangulaire supérieure d’ordre \(n(n \geq 2)\). Dans ce cas l’algorithme s’appelle substitution rétrograde et s’écrit dans le cas général

\[\begin{aligned} x_n & =\frac{b_n}{u_{n n}}, \\ x_i & =\frac{1}{u_{i i}}\left(b_i-\sum_{j=i+1}^n u_{i j} x_j\right), \quad i=n-1, \ldots, 1 \end{aligned}\]

On appelle ces relations formules de "remontée".
Son coût est également de \(n^2\) flops.

2. Exemples

2.1. Résolution d’un système à l’aide d’une matrice triangulaire inférieure

Considérons le système d’équations suivant :

\[\begin{aligned} 2x_1 &= 4 \\ 3x_1 + 5x_2 &= 1 \\ x_1 + 2x_2 + 4x_3 &= 2 \end{aligned}\]

Ce système peut être représenté sous la forme matricielle \(Ax = b\) où

\[A = \left[\begin{array}{lll} 2 & 0 & 0 \\ 3 & 5 & 0 \\ 1 & 2 & 4 \end{array}\right]\]

\[b = \left[\begin{array}{l} 4 \\ 1 \\ 2 \end{array}\right]\]

Pour résoudre ce système avec une matrice triangulaire inférieure, nous utiliserions les formules de descente.

\[\begin{aligned} x_1 &= \frac{4}{2} = 2 \\ x_2 &= \frac{1 - 3(2)}{5} = -1 \\ x_3 &= \frac{2 - 1(2) + 2(1)}{4} = 0.5 \end{aligned}\]

2.2. Exemple pratique en Python :

Vous pouvez utiliser la bibliothèque numpy pour résoudre ce système :

import numpy as np

def forward_substitution(L, b):
    n = len(b)
    x = np.zeros(n)

    for i in range(n):
        x[i] = b[i]

        for j in range(i):
            x[i] -= L[i, j] * x[j]

        x[i] /= L[i, i]

    return x

# Définir la matrice L (triangulaire inférieure) et le vecteur b
L = np.array([[2, 0, 0], [3, 5, 0], [1, 2, 4]])
b = np.array([4, 1, 2])

x = forward_substitution(L, b)
print(x)
print("A x close to b ? ", np.allclose(np.dot(L, x), b) )

Results

[ 2.  -1.   0.5]
A x close to b ?  True

Substitution rétrograde (backward substitution) :

Pour résoudre des systèmes d’équations avec des matrices triangulaires supérieures, utilisez la méthode suivante :

import numpy as np

def backward_substitution(U, b):
    n = len(b)
    x = np.zeros(n)

    for i in range(n-1, -1, -1):
        x[i] = b[i]

        for j in range(i+1, n):
            x[i] -= U[i, j] * x[j]

        x[i] /= U[i, i]

    return x

# Définir la matrice U (triangulaire supérieure) et le vecteur b
U = np.array([[2, 3, 1], [0, 5, 2], [0, 0, 4]])
b = np.array([4, 1, 2])

x = backward_substitution(U, b)
print(x)
print("A x close to b ? ", np.allclose(np.dot(U, x), b) )

Results

[1.75 0.   0.5 ]
A x close to b ?  True