Ce document, conçu spécifiquement pour les étudiants universitaires des filières scientifiques SM4 et SMP4, présente le corrigé du Travaux Dirigés n°2 portant sur la résolution numérique des systèmes linéaires par méthodes directes. Il vise à approfondir la compréhension des techniques fondamentales et leur application pratique dans ce domaine essentiel.
Il couvre les notions suivantes:
- L'étude de la décomposition LU (existence, unicité et calcul).
- La résolution de systèmes linéaires via la méthode de Gauss et la méthode de remontée.
- La décomposition de Cholesky pour les matrices définies positives.
- La décomposition QR utilisant le procédé d'orthonormalisation de Gram-Schmidt.
TD n°2 : Résolution Numérique des Systèmes Linéaires par Méthodes Directes
Exercice 1 : Décomposition LU et Résolution de Système Linéaire
1. **Condition d'existence et unicité de la décomposition LU**
Une condition suffisante pour qu'une matrice carrée `A` admette une décomposition LU (où `L` est une matrice triangulaire inférieure et `U` une matrice triangulaire supérieure) est que tous ses mineurs principaux non nuls soient inversibles. En d'autres termes, les déterminants principaux de la matrice `A` doivent être non nuls. Cela implique que tous les pivots rencontrés lors de l'élimination de Gauss sont non nuls.
Si la décomposition LU existe et que la matrice `U` a des 1 sur sa diagonale (ou `L` a des 1 sur sa diagonale, cas Doolittle ou Crout respectivement), alors cette décomposition est unique. La preuve de l'unicité peut être faite en supposant deux décompositions `A = L₁U₁ = L₂U₂`. Si `L₁` et `L₂` sont des matrices triangulaires inférieures unitaires (diagonale de 1) et `U₁` et `U₂` des matrices triangulaires supérieures, alors on a `L₂⁻¹L₁ = U₂U₁⁻¹`. Le membre de gauche est une matrice triangulaire inférieure unitaire, et le membre de droite est une matrice triangulaire supérieure. La seule matrice qui est à la fois triangulaire inférieure unitaire et triangulaire supérieure est la matrice identité (`Id`). Ainsi, `L₂⁻¹L₁ = Id`, ce qui implique `L₁ = L₂`, et par conséquent `U₁ = U₂`.
2. **Détermination de l'inverse et résolution par la méthode de Gauss**
Pour déterminer l'inverse d'une matrice triangulaire `A`, on peut utiliser la méthode de remontée (ou descente/remontée). Si `A` est une matrice triangulaire inférieure, pour trouver l'inverse `X` telle que `AX = I`, on peut résoudre `n` systèmes linéaires `Ax_j = e_j` où `x_j` est la `j`-ième colonne de `X` et `e_j` est la `j`-ième colonne de la matrice identité. La méthode de remontée (ou substitution avant/arrière) est utilisée pour résoudre efficacement ces systèmes.
Exemple de matrice triangulaire `A`:
`A = [[1, 0, 0, 0], [2, 1, 0, 0], [4, 2, 1, 0], [8, 4, 2, 1]]`
Pour résoudre un système linéaire `(S)` de la forme `Ax=b` en utilisant la méthode de Gauss, l'objectif est de transformer la matrice `A` en une matrice triangulaire supérieure `U` à l'aide d'opérations élémentaires sur les lignes. Le système `Ax=b` est alors équivalent à un nouveau système `Ux=c` qui est facile à résoudre par substitution arrière (remontée).
Un exemple de système triangulaire obtenu après application de la méthode de Gauss est :
`x₁ + 2x₂ + 4x₃ = 8`
`x₂ + 2x₃ = 4`
`x₃ = 2`
(Note : Les caractères étranges dans l'entrée ` 42002420 41284321 321321 xxxxxx xxx` ont été interprétés et reformulés comme un système linéaire standard).
Exercice 2 : (Non présent dans le texte original, mais peut être inclus pour la structure)
Cet exercice n'était pas détaillé dans le document fourni. Nous passerons directement à l'exercice 3.
Exercice 3 : Calcul de la Décomposition LU
Soit A une matrice carrée donnée.
1. **Vérification de l'existence de la décomposition LU de A**
Pour qu'une décomposition LU existe, les mineurs principaux de la matrice `A` doivent être non nuls. Si tous les sous-déterminants principaux sont non nuls, alors la décomposition LU existe et est unique (sous certaines conventions, comme L unitaire ou U unitaire).
2. **Calcul de la décomposition LU de A**
La décomposition LU d'une matrice `A` est obtenue en appliquant la méthode d'élimination de Gauss à `A`. Les multiplicateurs utilisés lors des étapes d'élimination forment les éléments non diagonaux de la matrice `L` (matrice triangulaire inférieure avec des 1 sur la diagonale), tandis que la matrice résultante après l'élimination est `U` (matrice triangulaire supérieure).
Exercice 4 : Décompositions de Cholesky et QR
1. **Vérification qu'une matrice est définie positive et calcul de sa décomposition de Cholesky**
Pour vérifier qu'une matrice est définie positive, on peut calculer ses valeurs propres. Si toutes les valeurs propres sont positives (strictement supérieures à zéro), alors la matrice est définie positive. Une autre méthode consiste à vérifier que tous ses mineurs principaux sont strictement positifs.
Si une matrice `A` est symétrique et définie positive, elle admet une décomposition de Cholesky unique `A = LLᵀ` (ou `A = RᵀR`), où `L` est une matrice triangulaire inférieure avec des éléments diagonaux positifs (et `R` est une matrice triangulaire supérieure). Les valeurs propres de `A` (0.5858, 2.0000 et 3.4142) étant positives confirment qu'elle est définie positive. La décomposition de Cholesky `L` est alors calculable par des formules spécifiques (vue en cours), par exemple :
`L = [[1.4142, 0, 0], [0.7071, 1.2247, 0], [0, 0.8165, 1.1547]]`
2. **Calcul de la décomposition QR de Gram-Schmidt**
La décomposition QR d'une matrice `A` exprime `A` comme le produit d'une matrice `Q` orthogonale (ses colonnes sont des vecteurs orthonormés) et d'une matrice `R` triangulaire supérieure. Le procédé d'orthonormalisation de Gram-Schmidt est une méthode courante pour obtenir cette décomposition.
Si `A = [a₁, a₂, a₃]` (où `a₁, a₂, a₃` sont les colonnes de `A`), le procédé de Gram-Schmidt construit les vecteurs `q₁, q₂, q₃` orthonormés :
- `q₁ = a₁ / ||a₁||`
- `v₂ = a₂ - proj_{q₁}a₂ = a₂ - (a₂ ⋅ q₁)q₁`
- `q₂ = v₂ / ||v₂||`
- `v₃ = a₃ - proj_{q₁}a₃ - proj_{q₂}a₃ = a₃ - (a₃ ⋅ q₁)q₁ - (a₃ ⋅ q₂)q₂`
- `q₃ = v₃ / ||v₃||`
Ceci donne la matrice `Q = [q₁, q₂, q₃]`. La matrice `R` est ensuite donnée par `R = QᵀA`.
FAQ sur la Résolution Numérique des Systèmes Linéaires
Qu'est-ce qu'une décomposition LU et à quoi sert-elle ?
La décomposition LU (Lower-Upper) est une méthode de factorisation d'une matrice carrée `A` en un produit de deux matrices triangulaires : une matrice `L` (inférieure) et une matrice `U` (supérieure). Elle est principalement utilisée pour résoudre efficacement des systèmes d'équations linéaires `Ax=b` à plusieurs reprises avec la même matrice `A` mais différents vecteurs `b`, ainsi que pour calculer des déterminants ou des inverses de matrices.
Dans quels cas la décomposition de Cholesky est-elle applicable ?
La décomposition de Cholesky est une factorisation matricielle spécifique qui s'applique uniquement aux matrices symétriques et définies positives. Une matrice est symétrique si elle est égale à sa transposée, et définie positive si toutes ses valeurs propres sont strictement positives ou si `xᵀAx > 0` pour tout vecteur `x` non nul.
Quelle est la différence principale entre la décomposition LU et la décomposition QR ?
La décomposition LU factorise une matrice `A` en un produit de matrices triangulaires `L` (inférieure) et `U` (supérieure), utilisée principalement pour la résolution de systèmes linéaires. La décomposition QR, quant à elle, factorise `A` en une matrice `Q` orthogonale et une matrice `R` triangulaire supérieure. La décomposition QR est particulièrement utile pour la résolution de problèmes de moindres carrés, le calcul de valeurs propres et la détermination de bases orthonormées.