Archives

Publié par Anthony Le Cazals

La génération et la propagation des erreurs

L’étude des erreurs forme une partie importante de l’analyse numérique. Les erreurs introduites dans la solution d’un problème ont plusieurs origines. Les erreurs d’arrondis surviennent car il est impossible de représenter en pratique tous les nombres réels exactement sur une machine à états finis (ce que sont en fin de compte tous les ordinateurs numériques). Les erreurs de troncature sont commises par exemple quand une méthode itérative est terminée et que la solution approchée obtenue diffère de la solution exacte. De façon similaire, la discrétisation (en) d’un problème (aussi appelée quantification dans les applications pratiques de calcul numérique) induit une erreur de discrétisation (en) (erreur de quantification dans les applications pratiques) car la solution du problème discret ne coïncide pas exactement avec la solution du problème continu.

Une fois que l’erreur est générée, elle se propagera généralement tout au long du calcul. Cela conduit à la notion de stabilité numérique1 : un algorithme est numériquement stable si une erreur, une fois générée, ne croît pas trop durant le calcul (dans une méthode de calcul itératif, une erreur trop grande peut dans certains cas faire diverger l’algorithme qui ne parviendra pas à approcher la solution). Cela n’est possible que si le problème est bien conditionné, ce qui signifie que la solution ne change que d'une faible quantité si les données du problème sont changées d'un montant faible. Ainsi, si un problème est mal conditionné, alors la moindre erreur dans les données provoquera une erreur très importante dans la solution trouvée.

Cependant, un algorithme qui résout un problème bien conditionné peut être ou ne pas être numériquement stable. Tout l’art de l’analyse numérique consiste à trouver un algorithme stable pour résoudre un problème mathématique bien posé. Un art apparenté est de trouver des algorithmes stables permettant de résoudre des problèmes mal posés, ce qui requiert généralement la recherche d'un problème bien posé dont la solution est proche de celle du problème mal posé, puis de résoudre à la place ce second problème bien posé.

Article Analyse numérique, sur Wikipéda

Méthode de Newton oui approximation par itération

Sous sa forme moderne, l'algorithme de Newton peut être présenté brièvement comme suit : à chaque itération, la fonction dont on cherche un zéro est linéarisée en l'itéré (ou point) courant et l'itéré suivant est pris égal au zéro de la fonction linéarisée. Cette description sommaire indique qu'au moins deux conditions sont requises pour la bonne marche de l'algorithme : la fonction doit être différentiable aux points visités (pour pouvoir y linéariser la fonction) et les dérivées ne doivent pas s'y annuler (pour que la fonction linéarisée ait un zéro) ; s'ajoute à ces conditions la contrainte forte de devoir prendre le premier itéré assez proche d'un zéro régulier de la fonction (i.e., en lequel la dérivée de la fonction ne s'annule pas), pour que la convergence du processus soit assurée.

L'intérêt principal de l'algorithme de Newton est sa convergence quadratique locale. En termes imagés mais peu précis, cela signifie que le nombre de chiffres significatifs corrects des itérés double à chaque itération, asymptotiquement. Comme le nombre de chiffres significatifs représentables par un ordinateur est limité (environ 15 chiffres décimaux sur un ordinateur avec un processeur 32-bits), on peut simplifier grossièrement les propriétés de convergence de l'algorithme de Newton en disant que, soit il converge en moins de 10 itérations, soit il diverge. En effet, si l'itéré initial n'est pas pris suffisamment proche d'un zéro, la suite des itérés générée par l'algorithme a un comportement erratique, dont la convergence éventuelle ne peut être que le fruit du hasard (un des itérés est par chance proche d'un zéro).

Article Méthode de Newton, sur Wikipéda

Pour être informé des derniers articles, inscrivez vous :

Commenter cet article