Ce support pédagogique est destiné aux étudiants de troisième année de licence de mathématiques (L3) à l'Université de Rouen. Il s'agit d'une fiche de travaux dirigés dédiée à l'analyse numérique, spécifiquement axée sur l'étude des méthodes itératives pour la résolution de systèmes linéaires. À travers divers exercices théoriques et appliqués, ce document permet d'approfondir les critères de convergence et la manipulation des rayons spectraux des matrices d'itération.
Il couvre les notions suivantes :
- Les méthodes classiques de Jacobi et de Gauss-Seidel
- La technique de relaxation (SOR)
- L'analyse de la convergence et des propriétés spectrales
- L'optimisation des paramètres de relaxation
Méthodes itératives pour la résolution de systèmes linéaires
En analyse numérique, la résolution de systèmes linéaires de la forme Ax = b est fondamentale. Lorsque la matrice A est de grande taille ou creuse, les méthodes directes deviennent inefficaces. On a alors recours aux méthodes itératives qui consistent à générer une suite de vecteurs convergeant vers la solution exacte.
Principe général de décomposition
Les méthodes itératives reposent sur la décomposition de la matrice A (appartenant aux matrices réelles d'ordre n) sous la forme A = M - N, où M est une matrice inversible. Le système se transforme en un problème de point fixe : Mx = Nx + b. Le processus itératif est défini par :
x(k+1) = M⁻¹Nx(k) + M⁻¹b, pour un vecteur initial x(0) choisi arbitrairement.
Définition des méthodes classiques
Pour une matrice A = D - E - F, où D représente la diagonale, -E la partie triangulaire inférieure stricte et -F la partie triangulaire supérieure stricte, on définit les méthodes suivantes :
- Méthode de Jacobi : M = D et N = E + F.
- Méthode de Gauss-Seidel : M = D - E et N = F.
- Méthode de Relaxation (SOR) : M = (D/ω) - E, avec un paramètre ω appartenant à l'intervalle ]0, 2[.
Exercice 1 : Propriétés de la matrice d'itération
Soit la méthode itérative Mxn+1 = Nxn + c. Si la matrice d'itération B = M⁻¹N possède un rayon spectral nul, cela signifie que toutes ses valeurs propres sont égales à zéro. Dans ce cas, la matrice est nilpotente.
Il existe alors un entier p tel que (M⁻¹N)ᵖ = 0. On peut en déduire que la solution exacte du système est obtenue en un nombre fini d'itérations (au plus p itérations). La méthode itérative se comporte alors comme une méthode directe.
Exercice 2 : Convergence des méthodes de Jacobi et Gauss-Seidel
On considère la matrice paramétrée par le réel α :
Aα = [[2, α, 0], [α, 2, α], [0, α, 2]]
1. Analyse de la méthode de Jacobi
La matrice de Jacobi J est obtenue en isolant la diagonale. Pour que la méthode de Jacobi converge, le rayon spectral de J doit être strictement inférieur à 1. Il convient de calculer les valeurs propres de J en fonction de α pour déterminer l'intervalle de convergence.
2. Analyse de la méthode de Gauss-Seidel
La matrice d'itération de Gauss-Seidel L₁ est construite à partir de la partie triangulaire inférieure. La convergence est également liée au rayon spectral. En général, si A est une matrice à diagonale dominante, la convergence est assurée.
Exercice 3 : Étude d'une suite de vecteurs
On résout le système avec A = [[4, 1], [0, -1]] et b = [5, -1]. En posant A = B - I (où I est la matrice identité), on étudie la suite xk+1 = Bxk - b.
Si le vecteur initial est proche de la solution exacte x = [1, 1], on observe le comportement de l'erreur. Si la matrice B a un rayon spectral supérieur à 1, la suite diverge, ce qui illustre l'importance du choix de la décomposition M-N.
Exercice 4 : Matrices à diagonale strictement dominante
Une matrice est dite à diagonale strictement dominante si, pour chaque ligne, la valeur absolue de l'élément diagonal est strictement supérieure à la somme des valeurs absolues des autres éléments de la ligne.
Théorème : Si A est à diagonale strictement dominante, alors :
- La méthode de Jacobi converge vers la solution du système.
- La méthode de Gauss-Seidel converge également vers la solution.
Exercice 5 : Comparaison des vitesses de convergence
Il est important de noter qu'on ne peut pas affirmer qu'une méthode est systématiquement meilleure qu'une autre. Cet exercice présente deux cas de figure :
- Une matrice où le rayon spectral de Jacobi est inférieur à celui de Gauss-Seidel (Jacobi est plus rapide).
- Une matrice où le rayon spectral de Gauss-Seidel est inférieur à celui de Jacobi (Gauss-Seidel est plus rapide).
Exercice 6 : Optimisation par la méthode de Jacobi relaxée
Pour une matrice A symétrique, définie positive et tridiagonale, la version relaxée de la méthode de Jacobi introduit un paramètre ω. L'étude montre que :
- Il existe une relation directe entre les valeurs propres de la matrice relaxée et celles de la matrice de Jacobi classique.
- La convergence est garantie pour ω appartenant à un intervalle spécifique.
- Il existe une valeur optimale ω_opt qui minimise le rayon spectral et maximise ainsi la vitesse de convergence.
FAQ : Questions fréquemment posées
Qu'est-ce que le rayon spectral d'une matrice ?
Le rayon spectral, noté ρ(M), est la plus grande valeur absolue des valeurs propres de la matrice M. C'est l'indicateur principal de la convergence des méthodes itératives : la convergence est assurée si et seulement si ρ(M) < 1.
Quelle est la différence entre Jacobi et Gauss-Seidel ?
Dans la méthode de Jacobi, on utilise les composantes du vecteur de l'itération précédente pour calculer toutes les nouvelles composantes. Dans la méthode de Gauss-Seidel, on utilise les nouvelles composantes dès qu'elles sont calculées, ce qui accélère généralement la convergence.
Pourquoi utiliser un paramètre de relaxation (ω) ?
Le paramètre de relaxation permet de modifier les propriétés spectrales de la matrice d'itération. Si ω > 1 (sur-relaxation), on cherche à accélérer la convergence. Si ω < 1 (sous-relaxation), on cherche parfois à stabiliser une méthode qui divergerait autrement.