Méthodes itératives pour résoudre Ax =b – Méthode de Jacobi

La méthode itérative la plus simple pour résoudre Ax=b est peut-être la méthode de Jacobi. Notez que la simplicité de cette méthode est à la fois bonne et mauvaise: bonne, car elle est relativement facile à comprendre et constitue donc un bon avant-goût des méthodes itératives; mauvaise, car elle n’est généralement pas utilisée dans la pratique (bien que son utilité potentielle ait été reconsidérée avec l’avènement du calcul parallèle). Pourtant, c’est un bon point de départ pour apprendre des méthodes itératives plus utiles, mais plus compliquées.

Étant donné une approximation actuelle

x(k) =(x1(k), x2(k), x3(k), …, xn(k))

pour x, la stratégie de la méthode de Jacobi consiste à utiliser la première équation et les valeurs actuelles de x2 (k), x3(k), …, xn(k) pour trouver une nouvelle valeur x1(k +1), et de manière similaire à trouvez une nouvelle valeur xi(k) en utilisant la i th équation et les anciennes valeurs des autres variables. Autrement dit, étant donné les valeurs actuelles x(k) =(x1(k), x2(k), …, xn(k)), trouvez de nouvelles valeurs en résolvant pour

x(k +1) =(x1(k +1), x2(k +1), …, xn(k+1))

en

Ce système peut également être écrit comme

Pour être clair, l’indice i signifie que xi(k) est le i th élément du vecteur

x(k) =(x1(k), x2(k), …, xi(k), …, xn(k)),

et l’exposant k correspond à l’itération particulière (pas à la k power puissance de xi).

Si nous écrivons D, L et U pour la diagonale, le triangulaire inférieur strict et le triangulaire supérieur strict et les parties de A, respectivement,

ensuite, la méthode de Jacobi peut être écrite en notation vectorielle matricielle comme suit

Exemple 1

Appliquons la méthode de Jacobi au système

.

À chaque étape, étant donné les valeurs actuelles x1 (k), x2 (k), x3 (k), nous résolvons pour x1 (k + 1), x2 (k + 1) et x3 (k +1) dans

.

Donc, si notre estimation initiale x(0) =(x1(0), x2(0), x3(0)) est le vecteur zéro 0 =(0,0,0) — une estimation initiale commune à moins que nous ayons des informations supplémentaires qui nous amènent à en choisir une autre — alors nous trouvons x(1) =(x1(1), x2(1), x3(1)) en résolvant

Donc x(1) = (x1(1), x2(1), x3(1)) = (3/4, 9/6, -6/7) ≈ (0.750, 1.500, -0.857). Nous itérons ce processus pour trouver une suite d’approximations de plus en plus meilleures x(0), x(1), x(2), …. Nous montrons les résultats dans le tableau ci-dessous, avec toutes les valeurs arrondies à 3 décimales.

Nous nous intéressons à l’erreur e à chaque itération entre la vraie solution x et l’approximation x(k) : e(k) = x−x(k). Évidemment, nous ne connaissons généralement pas la vraie solution x. Cependant, pour mieux comprendre le comportement d’une méthode itérative, il est instructif d’utiliser la méthode pour résoudre un système Ax = b pour lequel nous connaissons la vraie solution et analysons la rapidité avec laquelle les approximations convergent vers la vraie solution. Pour cet exemple, la vraie solution est x =(1, 2, -1).

La norme d’un vecteur // x // nous indique la taille du vecteur dans son ensemble (par opposition à la taille de chaque élément du vecteur). La norme vectorielle la plus couramment utilisée en algèbre linéaire est la norme l2:

Par exemple, si x =(1, 2, -1), alors

Dans ce module, nous utiliserons toujours la norme l2 (y compris pour les normes matricielles dans les tutoriels suivants), de sorte que //// signifie toujours || ||2 .

Pour nos besoins, nous observons que // x // sera petit exactement lorsque chacun des éléments x1, x2, …, xn dans x =(x1, x2| …, xn) est petit. Dans le tableau suivant, la norme de l’erreur devient progressivement plus petite à mesure que l’erreur dans chacun des trois éléments x1, x2, x3 devient plus petite, ou en d’autres termes, à mesure que les approximations deviennent progressivement meilleures.