Ce fascicule de travaux dirigés est destiné aux étudiants de deuxième année de licence MI2E à l'Université Paris-Dauphine. Il regroupe des exercices d'application portant sur les méthodes numériques fondamentales, essentielles pour la résolution de systèmes linéaires complexes.
Le document couvre les notions suivantes :
- Méthodes de résolution directe : élimination de Gauss et factorisations LU, Cholesky et QR ;
- Méthodes itératives : algorithmes de Jacobi, Gauss-Seidel et Richardson ;
- Analyse de convergence et étude des normes matricielles ;
- Introduction à la résolution d'équations non linéaires.
Méthode d'élimination de Gauss
Cette section présente des exercices pratiques sur la résolution de systèmes linéaires en utilisant l'algorithme d'élimination de Gauss et ses variantes comme Gauss-Jordan.
Exercice 1 : Application directe de l'élimination de Gauss
L'objectif est de résoudre le système Ax = b en détaillant toutes les étapes de calcul, notamment les matrices intermédiaires et les vecteurs du second membre.
Premier système (4x4) :
- Matrice A : [2, -1, 4, 0 ; 4, -1, 5, 1 ; -2, 2, -2, 3 ; 0, 3, -9, 4]
- Vecteur b : [8, 16, 3, 3]
Second système (3x3) :
- Matrice A : [5, 2, 1 ; 5, -6, 2 ; -4, 2, 1]
- Vecteur b : [1, 2, 1]
Exercice 2 : Pivotage et permutations
On considère un système Ax = b où la matrice A présente des zéros sur sa diagonale au cours du processus d'élimination.
1. Analyser s'il est possible d'utiliser la méthode de Gauss sans échange de lignes (pivotage).
2. Rechercher une permutation des lignes (matrice P) et des colonnes (matrice Q) pour obtenir une forme P A Q permettant d'effectuer l'élimination de manière stable.
Exercice 3 : Calcul d'inverse par Gauss-Jordan
Soit la matrice triangulaire supérieure U d'ordre 4. Calculez son inverse U⁻¹ en résolvant le système matriciel UX = I₄, où I₄ est la matrice identité, en utilisant la méthode d'élimination de Gauss-Jordan.
Exercice 4 : Forme échelonnée
Proposer une formulation matricielle complète, exprimée comme un produit de matrices élémentaires, pour transformer une matrice A de dimension 4x6 en sa forme échelonnée réduite.
Exercice 5 : Analyse structurelle d'une matrice
À partir d'un système (S) Ax = b, réalisez les étapes suivantes :
- Déterminer la forme échelonnée réduite par Gauss-Jordan.
- Calculer le rang de la matrice A et la dimension de son noyau (Ker A).
- Déterminer une base pour l'espace image (Im A) et pour le noyau.
- Établir les conditions de compatibilité sur le vecteur b pour que le système admette au moins une solution.
Méthodes de factorisation pour systèmes linéaires
La factorisation consiste à décomposer une matrice complexe en un produit de matrices plus simples (triangulaires ou orthogonales) pour faciliter la résolution de systèmes.
Exercice 1 : Factorisation LU
Pour une matrice A donnée, calculez la décomposition LU (Lower-Upper). Utilisez ensuite cette décomposition pour résoudre Ax = b et calculer le déterminant de A en utilisant la propriété det(A) = det(L) × det(U).
Exercice 2 : Cas de matrices spécifiques
Déterminer les factorisations LU pour différentes structures de matrices (3x3, 4x4 et matrices symboliques avec des coefficients a, b, c, d). Il est important de préciser les matrices élémentaires de transition à chaque étape.
Exercice 3 : Matrices bandes
Une matrice bande possède des éléments non nuls uniquement sur une bande étroite autour de la diagonale principale. Démontrez que la factorisation LU préserve cette structure : si A est une matrice bande, alors L et U conservent la même largeur de bande.
Exercice 4 : Matrices tridiagonales
Pour une matrice tridiagonale (éléments non nuls uniquement sur la diagonale et les deux sous-diagonales), établissez les formules récursives permettant de calculer les coefficients de L et U de manière efficace. Évaluez le nombre d'opérations nécessaires (complexité algorithmique).
Exercice 5 : Matrices à diagonale dominante
Démontrez qu'une matrice à diagonale strictement dominante par lignes est toujours inversible et admet une factorisation LU. Utilisez un raisonnement par récurrence et des calculs par blocs pour valider cette propriété.
Exercice 6 : Factorisation de Cholesky
La factorisation de Cholesky s'applique aux matrices symétriques définies positives (A = BBᵀ).
- Prouvez l'unicité de cette factorisation lorsque les éléments diagonaux de B sont positifs.
- Élaborez l'algorithme de calcul des coefficients de B.
- Comparez la complexité de Cholesky par rapport à l'élimination de Gauss classique.
Exercice 7 : Paramètre et définition positive
Soit une matrice A dépendant d'un paramètre ε. Déterminez les valeurs de ε pour lesquelles A est symétrique définie positive. Appliquez ensuite la méthode de Cholesky pour résoudre le système associé.
Exercice 8 : Factorisation QR
Démontrez que toute matrice réelle inversible A peut se décomposer en un produit QR, où Q est une matrice orthogonale et R une matrice triangulaire supérieure. Faites le lien avec le procédé d'orthonormalisation de Gram-Schmidt.
Méthodes itératives pour systèmes linéaires
Contrairement aux méthodes directes, les méthodes itératives construisent une suite de vecteurs convergeant vers la solution exacte.
Exercice 1 : Normes matricielles et rayon spectral
Rappels sur les propriétés des normes matricielles subordonnées (norme 1, norme 2 et norme infinie). Démontrez que la norme d'une matrice est toujours supérieure ou égale à son rayon spectral ρ(A).
Exercice 2 : Convergence et série de Neumann
Étudiez la condition de convergence des suites matricielles. Montrez que la série de terme général Aᵏ converge vers (I - A)⁻¹ si et seulement si le rayon spectral de A est strictement inférieur à 1.
Exercice 3 : Jacobi et Gauss-Seidel
Démontrez que si une matrice est à diagonale strictement dominante, les méthodes de Jacobi et de Gauss-Seidel convergent vers la solution du système pour n'importe quel vecteur initial.
Exercice 4 : Comparaison de convergence
Pour une matrice 3x3 donnée, calculez les rayons spectraux des matrices d'itération de Jacobi et Gauss-Seidel. Identifiez laquelle des deux méthodes est la plus rapide en fonction de la petitesse du rayon spectral.
Exercice 5 : Méthode de relaxation
Étude d'une méthode de relaxation dépendant d'un paramètre ω. Déterminez les conditions sur ω pour garantir la convergence et retrouvez le cas particulier de la méthode de Gauss-Seidel (ω = 1).
Exercice 6 : Méthode de Richardson (Gradient à pas fixe)
La méthode de Richardson utilise un paramètre α pour mettre à jour la solution : x(k+1) = x(k) + α(b - Ax(k)). Analysez les conditions sur α pour assurer la convergence, notamment lorsque la matrice A est symétrique définie positive.
Résolution d'équations non linéaires
Exercice 1 : Méthode de la fausse position
La méthode de la fausse position (ou regula falsi) est une variante de la dichotomie. Au lieu de diviser l'intervalle en son milieu, on utilise l'intersection de la sécante avec l'axe des abscisses pour estimer la racine de la fonction f(x) = 0.
Foire Aux Questions (FAQ)
Quelle est la différence entre une méthode directe et une méthode itérative ?
Les méthodes directes (comme Gauss ou LU) calculent la solution exacte en un nombre fini d'étapes (en faisant abstraction des erreurs d'arrondi). Les méthodes itératives (comme Jacobi) génèrent une suite de solutions approchées qui convergent vers la solution exacte, ce qui est souvent plus efficace pour les très grandes matrices creuses.
Pourquoi vérifier si une matrice est à diagonale dominante ?
C'est une condition suffisante cruciale. Si une matrice est à diagonale strictement dominante, on a la garantie qu'elle est inversible et que les méthodes itératives classiques comme Jacobi et Gauss-Seidel convergeront à coup sûr.
Quand utiliser la factorisation de Cholesky plutôt que LU ?
La factorisation de Cholesky est préférable dès que la matrice est symétrique définie positive. Elle est environ deux fois plus rapide que la factorisation LU et plus stable numériquement, car elle exploite la symétrie de la matrice.