Validité d'un test d'arrêt - méthode convergente

[dmat]

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 xk 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 ||Axk-b||<= E. Si c'est le cas, on considère que xk est solution approchée. Or en y réfléchissant bien, imposer ||Axk-b|| très petit ne revient pas à imposer ||xk-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ées très éloignées 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 ||xk-x|| majorée par un terme en ||Axk-b| ? Ou bien fait-on réellement l'erreur faute de mieux ?

Merci d'avance pour votre aide.

[L.A.]

Bonjour.

Il est tout a fait normal de d'évaluer ||Axk-b|| plutôt que ||xk-x|| précisément parce que on ne connait pas x, contrairement à A,xk et b.
Ensuite si ||Axk-b|| est petit, alors ||xk-x|| est lui aussi nécessairement petit, du moins en dimension finie : en effet si A est une matrice, d'inverse B, alors la quantité notée
|||B||| = sup {||Bx|| | x app. R^n et ||x||=1}
est finie, et pour tout x dans R^n on a ||Bx|| < |||B|||.||x||
donc si ||Axk-b||<e alors
||xk-x||=||B(Axk-b)|| < |||B|||.||Axk-b||<|||B|||.e
qui est de l'ordre de e.

[Dlzlogic]

Bonjour,
J'ai fait beaucoup de tests d'arrêt d'itération, et à chaque fois, je me suis reposé le problème. Pour ma part, j'ai toujours essayé de procéder par encadrement. Là au moins, je suis sûr que le résultat obtenu s'écarte de moins de la valeur petite servant d'arrêt.
La méthode par dichotomie est intéressante.
Je vais prendre un exemple simple, soit à calculer l'intersection de 2 droites. Supposons que l'angle des deux droites est très faible. On va trouver un point dont la distance à chaque droite est plus faible que E, mais on sera loin de l'intersection. Alors qu'une méthode par encadrement où le test consiste à mesurer la variation par rapport à la valeur précédente est beaucoup plus sûre.

[L.A.]

En effet tout dépend des données éventuellement catastrophiques et de la méthode ou de l'idée du raisonnement. En tout cas pour ce qui est d'évaluer la solution de Ax=b, la méthode est vraiment efficace, en plus on peut majorer |||B||| par la formule de la comatrice et l'inégalité d'Hadamard, voire des méthodes plus brutales en petite dimension par exemple. Ce qui fait qu'on a une idée très précise de ||xk-x|| à partir de ||Axk-b||.

[L.A.]

Par contre le plus difficile de trouver la méthode de construction de xk dans ce cas, mais il existe des méthodes (Gauss-Seidel,etc...) qui se basent sur le point fixe.
Pour les méthode de dichotomie (recherche d'un zéro d'une fonction R->R) la majoration de l'erreur est directement calculable à partir de l'intervalle de départ et du nombre d'itérations.
Pour l'intersection de deux droites de faible angles, la méthode que tu propose n'est peut être pas la meilleure, je n'ai jamais réfléchi au problème, cela dépend de la forme des données (sous forme d'équations cartésienne, on en revient à l'inversion d'une matrice). "Petit" en maths ne voulant rien dire (on peut toujours trouver plus "petit") il suffit de restreindre encore l'erreur possible sur les distances pour obtenir une précision suffisante de la position de la solution.

[Dlzlogic]

Par contre le plus difficile de trouver la méthode de construction de xk dans ce cas, mais il existe des méthodes (Gauss-Seidel,etc...) qui se basent sur le point fixe.
Pour les méthode de dichotomie (recherche d'un zéro d'une fonction R->R) la majoration de l'erreur est directement calculable à partir de l'intervalle de départ et du nombre d'itérations.

Je ne vois pas le problème sous cet aspect. La majoration de l'écart est une donnée de base, disons la précision du résultat. Ce sera par exemple le millimètre.

Pour l'intersection de deux droites de faible angles, la méthode que tu propose n'est peut être pas la meilleure, je n'ai jamais réfléchi au problème, cela dépend de la forme des données (sous forme d'équations cartésienne, on en revient à l'inversion d'une matrice).

Ceci était un exemple, je ne calcule pas l'intersection de deux droites de cette façon. Mes droites sont en général connues par 2 points, ce sont d'ailleurs presque toujours des segments, mes arcs de cercles sont connus par le centre et les extrémités, les arcs de parabole, à peu près pareil. A propos de l'intersection de deux droites, c'est une fonction très difficile. Naturellement, je ne parle pas de la formule elle même, mais du résultat recherché, par exemple, les extrémités font-elles partie du segment ? la formule utilisée dépend de la direction des droites, pour des questions de précision. Comme c'est une fonction très utilisée, elle doit être hyper-optimisée.

"Petit" en maths ne voulant rien dire (on peut toujours trouver plus "petit") il suffit de restreindre encore l'erreur possible sur les distances pour obtenir une précision suffisante de la position de la solution.

Encre une fois, j'ai employé un mot qui ne veut rien dire : "petit". On est en informatique et non en mathématique, comme je travaille avec des "long", "petit" ne peut pas être plus petit que l'unité.