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 Modèle:Math. Pour cela, on utilise une suite Modèle:Math qui converge vers un point fixe Modèle:Mvar, solution du système d'équations linéaires.
Principe de construction
On cherche à construire<ref name="Ciarlet"/>, pour Modèle:Math donné, la suite Modèle:Math avec <math>k \in \N</math>.
Modèle:Formule où Modèle:Formule est une matrice inversible.
- <math>\begin{matrix}
Ax=b \Leftrightarrow Mx=Nx+b \Leftrightarrow & x &=& M^{-1}Nx+M^{-1}b \\ & &=& F(x)\end{matrix} </math> où Modèle:Mvar est une fonction affine. La matrice Modèle:Math est alors appelée matrice de Jacobi.
Cependant, l'algorithme qui suit n'est valable que si la matrice Modèle:Mvar est à diagonale strictement dominante sur les lignes (si la matrice Modèle:Mvar est diagonale, sinon se référer à la section convergence).
Algorithme
<math> \left\{ \begin{array}{l} x^{(0)} \; \mbox{connu}\\ x^{(k+1)} = Bx^{(k)}+M^{-1}b \end{array} \right. </math>
Erreur et convergence
Si Modèle:Mvar est solution de Modèle:Formule alors il vérifie
- <math>x = Bx+M^{-1}b</math> .
Soit Modèle:Math le vecteur erreur
- <math>e^{(k+1)}=x^{(k+2)}-x^{(k+1)}=B(x^{(k+1)}-x^{(k)}) =Be^{(k)}</math>
ce qui donne
- <math>e^{(k+1)}=Be^{(k)}=B^{k+1}e^{(0)}</math>.
L'algorithme converge si <math>\lim_{k \to \infty} \| e^{(k)} \| = 0 \Longleftrightarrow \lim_{k \to \infty} \| B^k \| = 0</math> (c-à-d. Modèle:Mvar tend vers la matrice nulle). Modèle:Théorème Modèle:Théorème
Méthode de Jacobi
On décompose la matrice Modèle:Mvar de la façon suivante : Modèle:Formule avec Modèle:Mvar la matrice diagonale de Modèle:Mvar, Modèle:Formule la matrice triangulaire inférieure de Modèle:Mvar de diagonale nulle et Modèle:Formule la matrice triangulaire supérieure de diagonale nulle. Dans la méthode de Jacobi, on choisit Modèle:Formule et Modèle:Formule (dans la méthode de Gauss-Seidel<ref name="Ciarlet"/>, Modèle:Formule et Modèle:Formule).
- <math>x^{(k+1)}=D^{-1}(E+F) x^{(k)}+D^{-1}b</math>
- <math>x^{(k+1)}_i=\cdots x^{(k)}_i+\frac{b_i}{a_{ii}}</math> avec
pour la ligne i de Modèle:Math : <math>-\left(\frac{a_{i,1}}{a_{i,i}},\cdots, \frac{a_{i,i-1}}{a_{i,i}},0,\frac{a_{i,i+1}}{a_{i,i}},\cdots, \frac{a_{i,n}}{a_{i,i}}\right)</math>
- <math>x^{(k+1)}_i= -\frac{1}{a_{ii}} \sum_{j=1 \atop j \ne i}^n a_{ij}x^{(k)}_j + \frac{b_i}{a_{ii}}</math>
Vecteur résidu
Soit <math>r^{(k)}=D e^{(k)}</math> le vecteur résidu. On peut écrire <math>x_i^{(k+1)}=\frac{r_i^{(k)}}{a_{i,i}} + x_i^{(k)}</math> avec Modèle:Math que l'on calcule de la manière suivante :
- <math>r_l^{(k+1)}=-\sum_{j=1 \atop j \ne l}^n a_{l,j} \frac{r_j^{(k)}}{a_{l,l}}</math>.
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 Modèle:Mvar :
- <math>\frac{\|r^{(k)} \|}{\|b\|} < \varepsilon </math>
Coût
Cette méthode a un coût de l'ordre de Modèle:Formule 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<ref>Modèle:Article</ref> 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<ref name="Zaytzeff">Modèle:Ouvrage</ref>,<ref name = "MDM">Modèle:Article</ref>. Au mois de novembre 1936, Cross étendit son application à la résolution des réseaux d'adduction d'eau et des circuits électriques<ref name="HCross">Modèle:Article.</ref>. 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
Liens externes
- {{#invoke:Langue|indicationDeLangue}} Méthode de Jacobi
