Méthode de Jacobi

La méthode de Jacobi, due au mathématicien allemand Karl Jacobi, est une méthode itérative de résolution d'un système matriciel de la forme Ax = b. Pour cela, on utilise une suite x(k) qui converge vers un point fixe x, solution du système d'équations linéaires.

Principe de construction

On cherche à construire[1], pour x(0) donné, la suite x(k + 1) = F(x(k)) avec .

A=MNM est une matrice inversible.

F est une fonction affine. La matrice B = M–1N est alors appelée matrice de Jacobi.

Cependant, l'algorithme qui suit n'est valable que si la matrice A est à diagonale strictement dominante sur les lignes (si la matrice M est diagonale, sinon se référer à la section convergence).

Algorithme

Erreur et convergence

Si x est solution de Ax=b alors il vérifie

.

Soit e(k) le vecteur erreur

ce qui donne

.

L'algorithme converge si (c-à-d. Bk tend vers la matrice nulle).

Théorème  Une condition nécessaire et suffisante pour que est[1] que le rayon spectral (plus grande valeur propre en module) de B soit strictement inférieur à 1.

Théorème  La méthode converge quel que soit x(0) pour les systèmes linéaires dont la matrice est à diagonale strictement dominante[2].

Méthode de Jacobi

On décompose la matrice A de la façon suivante : A=DEF avec D la matrice diagonale de A, E la matrice triangulaire inférieure de A de diagonale nulle et F la matrice triangulaire supérieure de diagonale nulle. Dans la méthode de Jacobi, on choisit M=D et N=E+F (dans la méthode de Gauss-Seidel[1], M=DE et N=F).

avec


pour la ligne i de D–1(E+F) :

Vecteur résidu

Soit le vecteur résidu. On peut écrire avec r(k)
i
que l'on calcule de la manière suivante :

.

Test d'arrêt

Pour le test d'arrêt, on utilise l'erreur relative sur le vecteur résidu, ce qui donne, pour une précision donnée ε :

Coût

Cette méthode a un coût de l'ordre de 3n2+2n par itération. Elle converge moins vite que la méthode de Gauss-Seidel, mais est très facilement parallélisable.

Applications

En 1932, l'ingénieur américain Hardy Cross a publié un article[3] décrivant une méthode itérative de calcul des efforts dans les charpentes, qu'il appela « méthode de redistribution des moments », et qui est essentiellement une application de la méthode de Jacobi aux matrices de raideur de la résistance des matériaux. Par son interprétation mécanique intuitive, elle exerça une profonde influence à l'époque où se construisaient les gratte-ciels[4],[5]. Au mois de novembre 1936, Cross étendit son application à la résolution des réseaux d'adduction d'eau et des circuits électriques[6]. L'avènement des calculateurs électroniques a relégué cette technique au rang de curiosité académique, de même que la méthode de relaxation de Southwell, qui en est une généralisation ; elle conserve néanmoins un intérêt didactique pour l'étude de la statique.

Voir aussi

Articles connexes

Notes

  1. Philippe Ciarlet, Introduction à l’analyse numérique matricielle et à l’optimisation, Masson, coll. « Math. Appl. pour la Maîtrise », (réimpr. 2001) (ISBN 2-225-68893-1), « 5. Méthodes de Jacobi, de Gauss-Seidel, de relaxation, théor. 5.1.1 »
  2. Patrick Lascaux et Raymond Théodor, Analyse numérique matricielle appliquée à l'art de l'ingénieur, vol. 2 : Méthodes itératives, p. 346
  3. (en) « Analysis of Continuous Frames by Distributing Fixed-End Moments », Transactions of the American Society of Civil Engineers, vol. 96, no 1, (DOI 10.1061/TACEAT.0004333)
  4. Serge Zaytzeff, Calcul des constructions hyperstatiques par les méthodes de relaxation, Paris, Dunod, (réimpr. 1953, 1957), 330 p., « V. Cas des portiques étagés soumis aux déplacements latéraux », p. 63
  5. (en) Leonard K. Eaton, « Hardy Cross and "The Moment Distribution Method" », Nexus Network Journal, (lire en ligne)
  6. (en) Hardy Cross, « Analysis of flow in networks of conduits or conductors », University of Illinois Bulletin, (lire en ligne).

Liens externes

  • Portail de l'analyse
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.