Lernzettel: Résolution efficace des systèmes linéaires

📋 Plan du Cours

1. Définition et formulation des systèmes linéaires
2. Décomposition LU et méthodes directes associées
3. Décomposition de Choleski et algorithme associé
4. Introduction aux commandes et calculs matriciels avec Matlab
5. Méthodes itératives pour la résolution des systèmes linéaires et critères de convergence
6. Méthode de Jacobi et formulation matricielle associée
7. Méthode de Gauss–Seidel et méthode de relaxation
8. Méthode du gradient conjugué pour la résolution itérative des systèmes linéaires

📖 1. Définition et formulation des systèmes linéaires

🔑 Notions clés & Définitions

• Systèmes linéaires : En notation matricielle, les équations sont écrites comme : 𝑎11 𝑎12 ⋯ 𝑎1𝑛 𝑎21 𝑎22 ⋯ 𝑎21 ⋮ ⋮ ⋱ ⋮ 𝑎𝑛1 𝑎𝑛2 ⋯ 𝑎𝑛𝑛 𝑥1 𝑥2 ⋮ 𝑥𝑛
• Équations et de systèmes : Relations mathématiques exprimant une égalité entre une combinaison linéaire des inconnues et une constante, formant un système à résoudre.
• Système linéaire : Un exemple On veut résoudre le système linéaire suivant : 2𝑥1 − 𝑥2 = 0 −𝑥1 + 2𝑥2 = 3 de solution 𝑥1 = 1, 𝑥2 = 2.

📝 Points essentiels

• Chaque équation du système correspond à une combinaison linéaire des inconnues pondérée par les coefficients de la matrice A.
• Les coefficients a_ij et les constantes b_i sont connus, les inconnues x_j sont à déterminer.
• La résolution numérique des systèmes linéaires est fondamentale en analyse numérique et intervient dans de nombreux domaines.
• La notation matricielle permet de représenter simultanément toutes les équations du système de manière compacte.

💡 À retenir

Comprendre la structure fondamentale et la représentation matricielle des systèmes linéaires est la base indispensable pour toute méthode de résolution.

📖 2. Décomposition LU et méthodes directes associées

🔑 Notions clés & Définitions

• 𝐿𝑈 : 5𝑥3 /3 = −2, 𝑥1 = 11 + 2𝑥2 − 𝑥3 /4
• Phase d'élimination : Étape de la méthode d'élimination de Gauss consistant à transformer la matrice initiale en une matrice triangulaire supérieure en éliminant les coefficients sous la diagonale.
• Décomposition LU : Méthode Forme initiale Forme finale Elimination de Gauss 𝐴 Ԧ𝑥 = 𝑏 𝑈 Ԧ𝑥

📝 Points essentiels

• Toute matrice carrée A peut être factorisée en produit LU avec L triangulaire inférieure et U triangulaire supérieure.
• La méthode d'élimination de Gauss transforme la matrice A en une forme triangulaire supérieure U par élimination des coefficients sous la diagonale.
• La substitution directe permet de résoudre L y = b puis U x = y pour obtenir la solution x.
• Les décompositions LU de Doolittle et Crout imposent respectivement L ou U avec des diagonales unitaires.
• Méthodes directes Solution : On résout d'abord les équations 𝐿 Ԧ𝑦 = 𝑏 par substitution directe : ቐ 2𝑦1 = 28, 𝑦1 = 28/2 = 14 −𝑦 + 2𝑦2 = −40, 𝑦2 = (−40 + 𝑦1)/2 = −13 𝑦1 − 𝑦2 + 𝑦3 = 3, 𝑦3 = 33 − 𝑦1 + 𝑦2 = 6 La solution Ԧ𝑥 est alors obtenue à partir de 𝑈 Ԧ𝑥 = Ԧ𝑦 : ൞ 2𝑥3 = 𝑦3, 𝑥3 = 𝑦3/2 = 3 4𝑥2 − 3𝑥3 = 𝑦2, 𝑥2 = (𝑦2 + 3𝑥3)/4 = −1 4𝑥1 − 3𝑥2 + 𝑥3 = 𝑦1 𝑥1 = (𝑦1 + 3𝑥2 − 𝑥3)/4 = 6 Ԧ𝑥 = 3 −1 6 Méthodes directes Méthode d'élimination de Gauss - Algorithme Supposons que les 𝑘 premières lignes de 𝐴 aient déjà été transformées en forme triangulaire supérieure.
• Il existe trois décomposition LU décompositions couramment utilisées : L'avantage de la décomposition 𝐿𝑈 par rapport à la méthode d'élimination de Gauss est qu'une fois la matrice 𝐴 est décomposée, nous pouvons résoudre 𝐴 Ԧ𝑥 = 𝑏 pour autant de vecteurs constants 𝑏 que nous le souhaitons.

💡 À retenir

Toute matrice carrée A peut être factorisée en produit LU avec L triangulaire inférieure et U triangulaire supérieure.

📖 3. Décomposition de Choleski et algorithme associé

🔑 Notions clés & Définitions

• 𝐿𝐿𝑇 : 5𝑦2 = 18 𝑈 Ԧ𝑥 = Ԧ𝑦 → 𝑈 𝑦 = 1 4 1 0 2 −2 0 0 −9 7 6 18 → ቐ 𝑥3 = −2, 𝑥2 = (6 + 2𝑥3)/2 = 1, 𝑥1 = 7 − 4𝑥2
• Décomposition de Choleski : Méthode de factorisation d'une matrice symétrique définie positive A en un produit A = L L^T, où L est une matrice triangulaire inférieure.
• Méthode de décomposition 𝐿𝑈 : 5𝑦2 = 18 𝑈 Ԧ𝑥 = Ԧ𝑦 → 𝑈 𝑦 = 1 4 1 0 2 −2 0 0 −9 7 6 18 → ቐ 𝑥3 = −2, 𝑥2 = (6 + 2𝑥3)/2 = 1, 𝑥1 = 7 − 4𝑥2

📝 Points essentiels

• La condition nécessaire et suffisante pour appliquer la décomposition de Choleski est que A soit symétrique et définie positive.
• La décomposition de Choleski est plus efficace que la décomposition LU classique pour les matrices symétriques définies positives.
• Les éléments diagonaux de 𝐿 ne doivent pas être stockés.

💡 À retenir

La décomposition de Choleski exploite la symétrie et la positivité définie pour simplifier et accélérer la résolution des systèmes linéaires.

📖 4. Introduction aux commandes et calculs matriciels avec Matlab

🔑 Notions clés & Définitions

• Exemples : Cas concrets illustrant l'utilisation des opérations numériques et fonctions dans Matlab pour faciliter la compréhension et l'application.

📝 Points essentiels

• Les opérations numériques de base dans Matlab incluent +, -, *, /, ^ pour addition, soustraction, produit, division et puissance.
• Les fonctions mathématiques usuelles disponibles sont sqrt, cos, sin, tan, exp, log, log10, etc.
• La déclaration de variables s'effectue par affectation avec le signe =, par exemple x = 2.

💡 À retenir

Maîtriser les commandes de base et fonctions mathématiques dans Matlab est essentiel pour manipuler efficacement les matrices et résoudre des systèmes linéaires.

📖 5. Méthodes itératives pour la résolution des systèmes linéaires et critères de convergence

🔑 Notions clés & Définitions

• Méthodes itératives : Techniques de résolution approchée de systèmes linéaires qui commencent par une estimation initiale de la solution et l'améliorent par approximations successives jusqu'à ce que le changement devienne négligeable.
• 𝑁 Ԧ𝑥 0 + 𝑏 : Remarquons que si on choisit pour Ԧ𝑥 0 la solution exacte du système, alors on a 𝑀 Ԧ𝑥 1
• Rayon spectral : On appelle rayon spectral de 𝐴 (𝜌(𝐴)) la plus grande valeur propre en module, i.e.

📝 Points essentiels

• Les méthodes itératives commencent par une estimation initiale et améliorent la solution par itérations successives.
• Elles sont avantageuses pour les grandes matrices peu denses, permettant de stocker uniquement les éléments non nuls.
• Les méthodes sont autocorrectives, corrigeant les erreurs d'arrondi au fil des itérations.
• : exp, log, log10
• Exemples : 𝑒, 𝑒2, ln 2 , log 100 Règle d’or : consulter l’aide en ligne de Matlab via la commande help Présentation de l’environnement de calcul Matlab 25 Décomposition LU avec Matlab 26 Décomposition LU avec Matlab 27 Résolution d’équations et de systèmes linéaires−méthodes itératives Méthodes itératives Les méthodes itératives ou indirectes commencent par une estimation initiale de la solution 𝑥, puis améliorent à plusieurs reprises la solution jusqu'à ce que le changement de 𝑥 devienne négligeable.
• • Les procédures itératives sont autocorrectives, ce qui signifie que les erreurs d'arrondi (ou même les erreurs arithmétiques) dans un cycle itératif sont corrigées dans les cycles suivants.

💡 À retenir

Les méthodes itératives commencent par une estimation initiale et améliorent la solution par itérations successives.

📖 6. Méthode de Jacobi et formulation matricielle associée

🔑 Notions clés & Définitions

• Méthode de Jacobi : Procédé itératif pour résoudre un système linéaire qui repose sur la décomposition de la matrice A en une somme D + L + U, où chaque nouvelle approximation des inconnues est calculée simultanément à partir des valeurs de l'itération précédente.
• Matrice triangulaire : Matrice carrée dont tous les éléments situés soit au-dessus, soit en dessous de la diagonale principale sont nuls.

📝 Points essentiels

• La matrice A se décompose en A = D + L + U où D est diagonale, L triangulaire inférieure, U triangulaire supérieure.
• Où :
  • 𝑈 représente une matrice triangulaire supérieure, 𝑈 = 𝑈11 𝑈12 𝑈13 0 𝑈22 𝑈23 0 0 𝑈33
  • 𝐿 est une matrice triangulaire inférieure, 𝐿 = 𝐿11 0 0 𝐿21 𝐿22 0 𝐿31 𝐿32 𝐿33
  • 𝐼 désigne la matrice identité.

💡 À retenir

La méthode de Jacobi repose sur une décomposition simple de la matrice et une mise à jour simultanée des inconnues à partir des valeurs précédentes.

📖 7. Méthode de Gauss–Seidel et méthode de relaxation

🔑 Notions clés & Définitions

• Méthode de Gauss–Seidel : Méthode itérative pour résoudre un système linéaire où chaque composante de la solution est mise à jour en utilisant les valeurs les plus récentes calculées dans la même itération pour les indices inférieurs, améliorant ainsi la convergence.

📝 Points essentiels

• La méthode de Gauss–Seidel est un cas particulier de la méthode de relaxation pour ω = 1.
• La méthode de Gauss–Seidel converge généralement plus vite et dans plus de cas que la méthode de Jacobi.

💡 À retenir

La méthode de Gauss–Seidel améliore la convergence en utilisant les dernières valeurs calculées, et la relaxation affine cette approche par un paramètre de contrôle.

📖 8. Méthode du gradient conjugué pour la résolution itérative des systèmes linéaires

🔑 Notions clés & Définitions

• Ԧ𝑟 𝑘 : Vecteur résidu représentant la différence entre b et le produit de A par la solution approximative x_k, utilisé pour guider la convergence.
• Ԧ𝑥 𝑘+1 : On définit la norme : Ԧ𝑥 ≔ ෍ 𝑖

📝 Points essentiels

• La méthode du gradient conjugué minimise la fonction f(x) = 1/2 x^T A x - b^T x où A est symétrique définie positive.
• La direction de recherche s_k est choisie conjuguée par rapport à A, assurant l'orthogonalité des directions successives.
• Le pas α_k est calculé pour minimiser f(x) le long de la direction s_k selon α_k = (s_k^T r_k) / (s_k^T A s_k).

💡 À retenir

La méthode du gradient conjugué combine optimisation quadratique et directions conjuguées pour une convergence rapide sur les matrices symétriques définies positives.

📊 Tableaux de Synthèse

Comparaison des méthodes de résolution de systèmes linéaires

Méthode	Type	Avantages	Inconvénients
LU	Méthode directe	Rapide pour matrices petites	Peut être coûteuse pour grandes matrices
Choleski	Méthode directe	Efficace pour matrices symétriques positives	Ne s'applique pas aux matrices non symétriques
Jacobi	Méthode itérative	Simple à implémenter	Convergence lente ou non assurée
Gauss–Seidel	Méthode itérative	Convergence plus rapide que Jacobi	Peut diverger si la matrice n'est pas diagonale dominante
Gradient conjugué	Méthode itérative	Convergence rapide pour matrices symétriques positives	Nécessite que la matrice soit définie positive

⚠️ Pièges & Confusions Fréquentes

1. Confondre décomposition LU avec décomposition de Choleski, qui est spécifique aux matrices symétriques positives.
2. Utiliser la méthode de Jacobi sans vérifier la diagonale dominante, ce qui peut empêcher la convergence.
3. Appliquer la décomposition de Choleski à une matrice non symétrique ou non définie positive, menant à des erreurs.
4. Oublier que la méthode de relaxation nécessite un paramètre ω optimal pour assurer la convergence.
5. Confondre la convergence de la méthode de gradient conjugué avec celle de méthodes non adaptées, comme Jacobi ou Gauss–Seidel.
6. Négliger la nécessité de vérifier la condition de convergence pour les méthodes itératives.
7. Utiliser Matlab sans connaître les fonctions spécifiques pour chaque méthode, entraînant des erreurs de syntaxe ou de logique.

✅ Checklist Examen

1. Vérifier si la matrice est carrée avant de choisir la méthode de décomposition.
2. Confirmer la propriété de symétrie et de positivité pour la décomposition de Choleski.
3. Choisir la méthode appropriée selon la taille et la densité du système.
4. Vérifier la diagonale dominante pour la convergence de Jacobi et Gauss–Seidel.
5. Utiliser la méthode du gradient conjugué pour matrices symétriques définies positives.
6. Tester la convergence en utilisant le rayon spectral ou d'autres critères.
7. Utiliser Matlab pour automatiser les calculs et vérifier les résultats.
8. Comparer les performances des méthodes directes et itératives selon le contexte.
9. S'assurer que la matrice est stockée efficacement pour les grandes dimensions.
10. Interpréter correctement les résultats obtenus par chaque méthode.
11. Vérifier la stabilité numérique des opérations effectuées.