LG

Soit le système linéaire $AX=b$ avec $A$ matrice carrée $N \times N$ et $b$ et $X$ vecteurs de $\mathbb R^N$

Peut se résoudre si $det A \neq 0$.

Soit on détermine $A^{-1}$, on obtient $X = A^{-1}b$.

$$A^{-1}=\frac 1 {\det A} \,^{t}\!{\rm {com} A}$$

Dans la pratique, cette méthode est trop longue et inappliquée.

$$A = LU$$

• $L$ matrice triangulaire inférieure,
• $U$ matrice triangulaire supérieure avec des 1 sur la diagonale.

On détermine $LY=b$ puis $UX=Y$.

Lorsque L est déterminée, on ne peut calculer $y_i$ que si les $y_i$ inférieurs sont calculés :

$$y_i = \frac{b_i - \sum_{j=1}^{i-1}l_{i,j}y_j}{l_{ii}}$$ [1] §2.1 La factorisation de Gauss.

Complexité : $N^2/2$ multiplications et additions, $N$ divisions.

Puis on applique le même principe avec la matrice supérieure $U$ pour déterminer le vecteur $x$.

Valable pour une matrice carrée définie positive.

Étape 1 : $$ \begin{align*} &j = 1 \\ &i = 1 \quad &l_{jj} &= a_{jj} \\ &\forall i \in [2,N] \quad &u_{ji} &= \frac{a_{ji}}{l_{jj}} \end{align*} $$ Étape 2 : $$ \begin{align} \forall j &\in [2,N-1] : \\ i &= 1 \quad & l_{ji} &= a_{ji} \\ \forall &i \in [2, j] \quad & l_{ji} &= a_{ji} - \sum_{k=1}^{i-1}l_{jk}u_{ki} \\ \forall &i \in [j+1, N] \quad & u_{ji} &= \frac{a_{ji} - \sum_{k=1}^{j-1}l_{jk}u_{ki}}{l_{jj}} \end{align} $$ Étape 3: $$ \begin{align} \forall i &\in [1,N] : \\ j &= N \\ l_{ji} &= a_{ji} - \sum_{k=1}^{i-1}l_{jk}u_{ki} \\ \end{align} $$ Complexité : $\frac{N^3}{3}$ multiplications, $N$ divisions.

[1] §2.2 L'algorithme de Gauss.

À propos des méthodes de décomposition de type GAUSS Archive 14/​10/​2018

Si l'un des $l_{jj}$ vaut 0, il faut appliquer un pivot.

Résolution de systèmes linéaires par des méthodes directes : Gauss, LU Archive 14/10/2018

Exemple :

Université Laval avec une matrice $4*4$ Archive 14/10/2018

Valable pour une matrice carrée symétrique définie positive.

$$A = C D {}^t C$$

• $C$ matrice triangulaire inférieure ayant des 1 sur la diagonale.
• $D$ matrice diagonale

Soit $\forall i \in [1,N]$ $$ d_i = a_{ii} - \sum_{j=1}^{i-1} l_{ij}^2 d_j \\ \forall j \in [i+1,N]\\ l_{ji} = (a_{ji} - \sum_{k=1}^{i-1} l_{jk} l_{ik} d_k)/d_i $$

Exemple : Résolution de systèmes linéaires par des méthodes directes : LDL’ et Choleski en page 14 Archive 14/10/2018

Valable pour une matrice carrée symétrique définie positive.

$$A = H {}^t H$$

• $H$ matrice triangulaire inférieure.

Méthode :

The Cholesky algorithm Archive 17/10/2018

Soit $$A^i= \begin{pmatrix} I_{i-1} & 0 & 0 \\ 0 & a_{i,i} & b_i^T \\ 0 & b_i & B^i \end{pmatrix}$$

$$L_i:= \begin{pmatrix} I_{i-1} & 0 & 0 \\ 0 & \sqrt{a_{i,i}} & 0 \\ 0 & \frac{b_i}{\sqrt{a_{i,i}}} & I_{n-i} \end{pmatrix}$$

$$ A^{i+1}= \begin{pmatrix} I_{i-1} & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & B^i - \frac{b_i b_i^T}{a_{i,i}} \end{pmatrix} $$

Exemple :

$$ A = A^1= \begin{pmatrix} 4 & 12 & -16 \\ 12 & 37 & -43 \\ -16 & -43 & 98 \end{pmatrix} $$

$$ L_1= \begin{pmatrix} \sqrt4 & 0 & 0 \\ \frac{12}{\sqrt4} & 1 & 0 \\ \frac{-16}{\sqrt4} & 0 & 1 \end{pmatrix}= \begin{pmatrix} 2 & 0 & 0 \\ 6 & 1 & 0 \\ -8 & 0 & 1 \end{pmatrix} $$

$$ A^2= \begin{pmatrix} 1 & 0 & 0 \\ 0 & B^1 - \frac{b_1 b_1^T}{a_{1,1}} & \cdots \\ 0 & \vdots & \ddots \end{pmatrix} \quad B^1= \begin{pmatrix} 37 & -43 \\ -43 & 98 \end{pmatrix} \quad b_1=\begin{pmatrix} 12 \\ -16 \end{pmatrix} \quad A^2= \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 5 \\ 0 & 5 & 34 \end{pmatrix} $$

$$ L_2= \begin{pmatrix} 1 & 0 & 0 \\ 0 & \sqrt1 & 0 \\ 0 & \frac{5}{\sqrt1} & 1 \end{pmatrix}= \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 5 & 1 \end{pmatrix} $$

$$ A^3= \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & B^2 - b_2 b_2^T \end{pmatrix} \quad B^2= \begin{matrix} 34 \end{matrix} \quad b_2=\begin{matrix} 5 \end{matrix} \quad A^3= \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 9 \end{pmatrix} $$

$$ L_3= \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & \sqrt9 \end{pmatrix}= \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 3 \end{pmatrix}$$

$$ L = L_1 L_2 L_3 = \begin{pmatrix} 2 & 0 & 0 \\ 6 & 1 & 0 \\ -8 & 5 & 3 \end{pmatrix} $$

$$ \begin{align*} \forall i &\in [1,N] \\ j &= i \quad & L_{j,j} &= \sqrt{ A_{j,j} - \sum_{k=1}^{j-1} L_{j,k}^2 } \\ \forall j &\in [1,i-1] \quad & L_{i,j} &= \frac{1}{L_{j,j}} \left( A_{i,j} - \sum_{k=1}^{j-1} L_{i,k} L_{j,k} \right) \end{align*} $$

Exemple :

$A = \begin{pmatrix} 4 & 12 & -16 \\ 12 & 37 & -43 \\ -16 & -43 & 98 \end{pmatrix}$

$L = \begin{pmatrix} \sqrt 4 = 2 & 0 & 0 \\ \frac{12}{2} = 6 & \sqrt{37-6^2} = 1 & 0 \\ \frac{-16}{2} = -8 & \frac{-43-(-8)*6}{1} = 5 & \sqrt{98-8^2-5^2} = 3 \end{pmatrix}$

[1] : DESTUYNDER, Philippe. Méthodes numériques pour l'ingénieur. Lavoisier, 2010, 248 pages.

[2] : Timothy, Vismor. Matrix Algorithms. January 30, 2015, 69 pages. Archive 11/11/2018