Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Méthode de Jacobi
Résumé
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 qui converge vers un point fixe x, solution du système d'équations linéaires.
On cherche à construire, pour x donné, la suite x = F(x) avec .
où est une matrice inversible.
où F est une fonction affine. La matrice B = MN 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).
Si x est solution de alors il vérifie
Soit e le vecteur erreur
ce qui donne
L'algorithme converge si (c-à-d. Bk tend vers la matrice nulle).
On décompose la matrice A de la façon suivante : avec D la matrice diagonale de A, la matrice triangulaire inférieure de A de diagonale nulle et la matrice triangulaire supérieure de diagonale nulle. Dans la méthode de Jacobi, on choisit et (dans la méthode de Gauss-Seidel, et ).
avec
pour la ligne i de D(E+F) :
Soit le vecteur résidu. On peut écrire avec r que l'on calcule de la manière suivante :
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 ε :
Cette méthode a un coût de l'ordre de par itération. Elle converge moins vite que la méthode de Gauss-Seidel, mais est très facilement parallélisable.
En 1932, l'ingénieur américain Hardy Cross a publié un article 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. Au mois de novembre 1936, Cross étendit son application à la résolution des réseaux d'adduction d'eau et des circuits électriques.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.