Test d'arrêt pour méthode itérative convergente

[invited9162c0f]

Bonjour a tous. En programmant une méthode itérative linéaire, il m'est venu un doute quant à la validité du test d'arrêt usuellement employé. Pourriez-vous m'aider ?

Soit Ax=b est un système linéaire, dont on suppose qu'il y a existence et unicité de la solution x. En construisant une méthode itérative linéaire convergente (c'est à dire une suite de vecteurs x^k qui tend vers la solution x, et ce qu'elle que soit le vecteur initial de la suite), on utilise couramment le test d'arrêt suivant : on fixe un réel très petit E, et on teste à chaque itération k si la norme ||Ax^k-b||<= E. Si c'est le cas, on considère que x^k est solution approchée. Or en y réfléchissant bien, imposer ||Ax^k-b|| très petit ne revient pas à imposer ||x^k-x|| très petit également, avec x la solution...du moins ce n'est pas une implication.

D'où mon incompréhension d'utiliser en ingénierie ce test d'arrêt pour les méthodes itératives, étant donnée qu'on peut se retrouver avec des solutions approchée très éloignée de la solution réelle avec ce test là, même si E est très petit... Qu'en pensez-vous ? Est-ce qu'une propriété que je n'ai pas prise en compte implique en fait qu'on a vraiment ||x^k-x|| majorée par un terme en ||Ax^k-b| ? Ou bien fait-on réellement l'erreur faute de mieux ?

Merci d'avance pour votre aide.
-----

[iFly]

Bonjour,

x est solution de ax-b=0 si et seulement si quelque soit E>0, |ax-b|<E. Donc si x_k vérifie pour un E petit |ax_k-b|<=E, on peut bien en déduire que x_k est une solution approchée. Tout est lié ici à l'équivalence : x est solution de ax-b=0 si et seulement si quelque soit E>0, |ax-b|<E. Le x_k sera même d'autant plus proche que E est petit, puisqu'il vérifiera |ax-b|<E pour plus de E.

Après je ne suis qu'élève de CPGE mais j'espère que cela peut t'apporter quelques éclaircissements.

Bonne soirée.

[invite9bc98748]

Salut,
Si cela peut t'aider j'ai quelques explications:
Par ton itération tu as ce qui équivaut à en remplacant b par Ax (x la solution exacte si elle existe). De l'algèbre linéaire tu sais que Ax = b a une solution unique si et seulement si le déterminant est différent de 0.
- Si il est égale à zéro cela veut dire que le noyau de A est non nul et que tu as donc une infinité de solution. Comme les vecteurs appartenant à ce noyaux vérifient Ax = 0, il se pourrait que le vecteur appartienne aussi à ce noyau vérifiant l'inégalité .
- Si le det(A) est différent de zéro, cela veut dire que le noyau est nul que l'unique solution Ax = 0 est x = 0 ce qui veut dire que si tu as alors le vecteur est proche de zéro.
En gros si det(A) est différent de zero alors la solution que tu trouves par ton itération devrait se rapprocher de la solution unique que tu cherches, si det(A) = 0 tu as une infinité de solution à ton problème.
J'espère que j'ai pu t'aider un peu dans ton problème.
Ciao