AlgèbreMéthode · Glossaire
méthode de Jacobi
La méthode de Jacobi désigne deux algorithmes d’algèbre linéaire numérique. Pour résoudre un système linéaire dont tous les coefficients diagonaux sont non nuls, elle recalcule simultanément chaque inconnue à partir des valeurs précédentes ; cette itération simple ne converge que sous des conditions supplémentaires. Pour une matrice symétrique réelle, elle applique des rotations planes afin d’annuler progressivement les coefficients hors diagonale et de faire apparaître les valeurs propres sur la diagonale.
Sommaire
Ce que vous allez apprendre
- Distinguer les deux algorithmes appelés méthode de Jacobi.
- Appliquer les mises à jour simultanées à un système linéaire de deux équations.
- Identifier les hypothèses et les critères qui conditionnent la convergence.
- Relier les rotations de Jacobi à la diagonalisation d’une matrice symétrique réelle.
En clair
Imaginez deux nombres inconnus, chacun dépendant de l’autre. On part d’une estimation, puis on recalcule les deux nombres en même temps avec les anciennes valeurs. On recommence jusqu’à ce que les corrections deviennent négligeables : c’est la méthode de Jacobi pour un système linéaire.
Le même nom désigne aussi un autre geste. Pour une matrice symétrique réelle, de petites rotations effacent peu à peu les nombres placés hors de la diagonale. La diagonale finit alors par révéler les valeurs propres.
Définition
Pour résoudre un système linéaire, on écrit la matrice carrée A comme la somme de sa diagonale D, de sa partie strictement inférieure L et de sa partie strictement supérieure U. Le vecteur b contient les seconds membres, et le vecteur x(k) est l’approximation obtenue après k itérations. Si chaque terme diagonal utilisé est non nul, la mise à jour de Jacobi est :
Toutes les composantes de x(k+1) sont donc calculées avec x(k), sans réutiliser une valeur fraîchement mise à jour. La convergence dépend de A ; une diagonale strictement dominante suffit, mais n’est pas nécessaire. Plus exactement, elle a lieu pour tout point de départ lorsque le rayon spectral de la matrice d’itération −D−1(L + U) est inférieur à 1.
Pour les valeurs propres, A est une matrice symétrique réelle. Chaque rotation orthogonale Q agit dans un plan de coordonnées et choisit un coefficient hors diagonale à annuler. La transformation suivante conserve les valeurs propres : . En répétant ces rotations selon une stratégie qui traite les coefficients hors diagonale, la matrice tend vers une forme diagonale dont les termes sont les valeurs propres, à l’ordre près.
Le principe
Pour le système Ax = b, le nombre aij est le coefficient de la ligne i et de la colonne j. Isolez la diagonale D de A, choisissez une approximation initiale, puis appliquez simultanément pour chaque indice i. Arrêtez lorsque le résidu Ax(k) − b respecte la tolérance fixée.
Pour une matrice symétrique réelle, choisissez un coefficient hors diagonale, construisez une rotation plane qui l’annule, puis appliquez la rotation des deux côtés de la matrice. Répétez jusqu’à ce que la taille des coefficients hors diagonale soit inférieure à la tolérance ; lisez alors les valeurs propres sur la diagonale.
Quand l'utiliser
Pour la résolution, A doit être carrée et les coefficients diagonaux servant de diviseurs doivent être non nuls, éventuellement après permutation des équations. Cette condition rend l’itération définie, mais ne garantit pas sa convergence. Une diagonale strictement dominante est un critère suffisant facile à vérifier. Si un coefficient diagonal reste nul, la formule bloque ; il faut réordonner le système ou employer une autre méthode.
Pour le calcul spectral décrit ici, la matrice doit être réelle et symétrique. Les rotations sont alors orthogonales, les valeurs propres sont réelles et une diagonalisation orthogonale existe. Sur une matrice réelle non symétrique, annuler successivement les coefficients par cette procédure n’offre pas la même garantie ; une méthode adaptée, telle que l’algorithme QR, est préférable.
Un exemple, pas à pas
Résolvons un système de deux équations. Les données sont les coefficients 10 et −1, les deux seconds membres égaux à 9, et l’approximation initiale x(0) = 0, y(0) = 0.
1. Avec les deux anciennes valeurs nulles, on obtient x(1) = 0,9 et y(1) = 0,9.
2. Avec 0,9 dans les deux formules, x(2) = y(2) = 0,99.
3. Une nouvelle mise à jour donne x(3) = y(3) = 0,999.
2. Avec 0,9 dans les deux formules, x(2) = y(2) = 0,99.
3. Une nouvelle mise à jour donne x(3) = y(3) = 0,999.
L’erreur sur chaque inconnue est divisée exactement par 10 à chaque étape de cet exemple ; la figure rend cette progression visible sans changer d’échelle en cours de route.
La solution exacte est x = y = 1. Le contrôle est immédiat : 10 × 1 − 1 = 9 dans chaque équation. Après trois itérations, le résidu vaut −0,009 pour chacune des deux lignes, car 10 × 0,999 − 0,999 − 9 = −0,009.
En pratique
Pour un grand système creux, une itération de Jacobi demande surtout des produits locaux et se parallélise facilement. Sur une matrice dense de taille modeste, une factorisation directe est souvent préférable lorsque l’on veut une précision prévisible en un nombre fini d’étapes.
Jacobi est aussi utile comme brique de préconditionnement ou de lissage dans des méthodes plus élaborées. Face à Gauss-Seidel, on le choisit lorsque les mises à jour simultanées et le calcul parallèle priment ; Gauss-Seidel réemploie aussitôt les nouvelles valeurs et peut converger plus vite.
Pour obtenir tout le spectre d’une matrice symétrique réelle, les rotations de Jacobi ont l’avantage de conserver la symétrie et de produire aussi des vecteurs propres en accumulant les rotations. Si seule la valeur propre dominante est recherchée, la méthode de la puissance demande généralement moins de travail.
À ne pas confondre
La méthode itérative de Jacobi n’est pas Gauss-Seidel. Le test est l’origine des valeurs employées pendant une itération : Jacobi utilise uniquement l’itération précédente, tandis que Gauss-Seidel réutilise immédiatement les composantes déjà recalculées.
La méthode de Jacobi ne désigne pas la matrice jacobienne d’une fonction. La première est un algorithme d’algèbre linéaire ; la seconde rassemble des dérivées partielles. Calculer les dérivées d’une application à plusieurs variables tranche donc sans ambiguïté.
Enfin, les deux algorithmes portant le nom de Jacobi ne sont pas deux étapes d’une même procédure. L’un cherche un vecteur solution de Ax = b ; l’autre diagonalise progressivement une matrice symétrique pour en extraire les valeurs propres.
Limites et pièges
Des coefficients diagonaux non nuls ne suffisent pas à assurer la convergence. Pour la matrice de diagonale (1, 1) et de coefficients hors diagonale égaux à 2, la matrice d’itération a un rayon spectral égal à 2 : certaines erreurs doublent à chaque pas. Il faut vérifier un critère de convergence ou changer de méthode.
Deux itérations successives très proches ne prouvent pas, à elles seules, que l’équation est bien satisfaite. Le symptôme décisif est un résidu Ax − b encore trop grand. Le test d’arrêt doit donc contrôler ce résidu avec une tolérance adaptée aux données.
Dans la méthode spectrale, l’annulation est numérique : on s’arrête lorsque les coefficients hors diagonale passent sous un seuil, pas lorsqu’ils deviennent tous exactement nuls. Un seuil trop large dégrade les valeurs propres ; un seuil inférieur aux effets d’arrondi gaspille des rotations.
Avec une valeur propre multiple, les valeurs diagonales peuvent converger correctement alors que la base de vecteurs propres n’est pas unique dans le sous-espace correspondant. Il faut interpréter le sous-espace propre plutôt que chercher un vecteur propre canonique.
Pour aller plus loin
Deux idées prolongent naturellement cette fiche. Le rayon spectral explique pourquoi l’erreur de l’itération linéaire décroît ou s’amplifie. Pour le calcul des valeurs propres, l’accumulation des rotations orthogonales montre comment obtenir, en plus de la diagonale, une base de vecteurs propres.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres