MENUCours D'introduction à l'analyse numérique

Lorsque l'on met en place une méthode numérique pour résoudre un problème scientifique il importe d'avoir une approche critique des résultats. Notamment, si l’on recherche de la précision, il n’est pas inutile d’avoir une idée de l’erreur que produit la méthode numérique utilisée. Cette erreur est essentiellement de deux types : l’erreur d'arrondi et l'erreur d'approximation.

Erreur d’arrondi

Dans un programme numérique, les réels sont représentés par des nombres à virgule flottante en binaire. Ce codage s'effectue sur un nombre fini de bits ce qui limite la précision machine \(\varepsilon_{m}\). En simple précision, les réels sont codés sur 32 bits et peuvent s’étendre de ± 1,1754944E−38 à ± 3,4028235E38 avec sept chiffres significatifsDans la norme IEEE 754, 1 bit est réservé au signe, 8 bits à l'exposant et 23 bits pour la mantisse. Ainsi la plus petite valeur de la mantisse correspond à 2^-23=1,2E-7. ce qui correspond à une précision \(\varepsilon_{m}\simeq 10^{-7}\). En double précision, les réels sont codés sur 64 bits ce qui donne une précision \(\varepsilon_{m}\simeq10^{-15}\).

On pourrait croire que de telles précisions sont largement suffisantes dans les situations courantes, mais ce serait oublier le caractère itératif des méthodes numériques entraînant une propagation et une accumulation des erreurs d’arrondi. Par exemple, lorsque que l’on calcule un nombre \(X\) en effectuant \(N\) multiplications, on montre que l’erreur relative \(\delta X/X\) varie comme \(\sqrt{N}\varepsilon_{m}\).

De plus, il est facile de constater que deux suites d’opérations mathématiques donnant le même résultat théorique ne donneront pas nécessairement le même résultat numérique. C’est pourquoi, lors de la phase de programmation, il est judicieux de respecter les règles suivantes :

Erreur d'approximation

Les méthodes numériques reposent en général sur des schémas approximatifs ce qui produit des erreurs indépendamment de la précision machine.

Erreur de troncature

Ce type d'erreur désigne l'erreur d'approximation suite à la troncature d'un développement en série ou d'un processus. Par exemple, on détermine la limite d'une suite en calculant sa valeur après un grand nombre d'itérations \(N\), la limite quand \(N\to \infty\) étant inaccessible. De même, dans les méthodes de différences finies, les dérivées sont approchées par des taux de variation ; par exemple \[ f'(x)\simeq\frac{f(x+h)-f(x)}{h} \] Il importe de pouvoir estimer cette erreur sans quoi les résultats numériques n'ont aucune valeur. N'oublions pas qu'une méthode numérique donne toujours un résultat et que c'est la confiance qu'on lui accorde qui doit être interrogée.

Illustrons ces idées sur les solveurs d'équations différentielles. Pour estimer l'erreur d'une méthode de résolution des équations différentielles, on peut calculer l’écart entre la solution exacte \(y(T)\) à l'instant \(T\) et la solution approchée \(y_{N}\) après \(N\) itérations (de pas \(h\)) : \[ \varepsilon_{\text{T}}=\left|y(T)-y_{N}\right| \] On dira qu’une méthode est d’ordre \(p\) si \(\varepsilon_{\text{T}}\) varie comme \(1/N^{p}\). Par exemple, on sait que la méthode d’Euler produit une erreur de l’ordre de \(h^{2}\) à chaque étape[1] ce qui finalement donnera une erreur totale \(\varepsilon_{\text{T}}\simeq Nh^{2}=\frac{T^{2}}{N}\) : la méthode d’Euler est d’ordre un. Par contre, la méthode de Runge-Kutta d’ordre 4 est, comme son nom l’indique, d’ordre 4 puisque chaque étape s’accompagne d’une erreur de troncature en \(h^{5}\).

Pour réduire l'erreur de troncature il faut diminuer le pas de discrétisation mais pas trop, car cela revient à augmenter le nombre d'itérations et à accumuler des erreurs d'arrondi. Aussi, il est impossible de minimiser, en même temps, l’erreur d’arrondi et l’erreur de troncature, ce qui oblige à trouver un compromis acceptable pour minimiser et l’erreur totale et le temps de calcul.

Pour illustrer notre propos, nous avons tracé sur la figure ci-dessus, l’erreur \(\varepsilon_{\rm{T}}\) produite par deux méthodes d'intégration des équations différentielles (Euler et RK4), appliquées à l’équation différentielle \(\mathrm{d}v/\mathrm{d}t+v=1\). On constate que pour la méthode d’Euler, l’erreur est essentiellement gouvernée par les problèmes de troncature pour \(N<10^{5}\) et qu’elle varie, comme attendu, en \(1/N\). En revanche, pour la méthode RK4, ce qui frappe immédiatement c’est la précision importante même pour un petit nombre de pas avec une décroissance rapide en \(1/N^{4}\). Si l’on désire une précision de \(10^{-5}\), 10 points suffisent ! Cependant, très rapidement, les erreurs d’arrondi entrent en compétition avec les erreurs de troncature. Ici, le calcul est effectué en simple précision ce qui impose une précision optimale de l’ordre de \(10^{-7}\).

Cas des méthodes de Monte Carlo

On désigne par ce terme les méthodes qui reposent sur la génération de nombres aléatoires pour effectuer des calculs. En effet, certains problèmes peuvent se ramener au calcul de l'espérance mathématique d'une variable aléatoire. Le calcul intégral, la résolution de certaines équations aux dérivées partielles, la détermination des propriétés thermodynamiques d'un système à l'équilibre, en sont quelques exemples.

Suivant le problème considéré, une méthode de Monte Carlo produit des erreurs plus ou moins importantes, mais dans tous les cas il y a au moins deux raisons qui limitent la précision de la méthode :

1. D'une part, le générateur de nombres aléatoires singe le hasard sans vraiment produire du hasard pur : on parle de nombres pseudo-aléatoires. Notamment, lorsque l'on demande à un générateur de fournir une série aléatoire, on s'aperçoit qu'au bout d'un certain nombre de tirages la liste se répète. C'est pourquoi, du fait de cette périodicité, deux séries aléatoires peuvent présenter des corrélations ce qui induit des estimations biaisées.
2. D'autre part, la méthode repose sur l'estimation d'une espérance que l'on approche par la moyenne arithmétique laquelle fluctue à chaque expérience numérique.

En général, un bon moyen d'estimer l'erreur d'une méthode de Monte Carlo consiste à répéter \(n\) fois l'algorithme ce qui produit \(n\) mesures numériques entachées d'erreurs pseudo-aléatoires. À partir de ces \(n\) résultats -que nous noterons \(x_i\)- on calcule la moyenne \[ m=\frac{\sum_{i=1}^n x_i}{n} \] Cette quantité aléatoire présente un écart-type donné par \[ \sigma_m=\frac{\sigma}{\sqrt n} \] avec \(\sigma\) l'écart-type d'une mesure. Soit on connait théoriquement \(\sigma\) (c'est rarement le cas) soit on estime \(\sigma\) à partir de la liste des mesures via l'estimateur non biaisé \[ \sigma^2\simeq \frac{1}{n-1} \sum_{i=1}^n (x_i-m)^2 \] Finalement on mettra le résultat sous la forme \[ \text{résultat}=m\pm \sigma_m \] ce qui définit un intervalle de confiance de 68%.

En général, les méthodes de Monte Carlo convergent assez lentement et sont assez gourmandes en temps de calcul. Elles sont surtout utilisées en physique statistique et en physique théorique.

Comment contrôler l'erreur d'une méthode numérique ?

Face à un problème sans solution analytique, l’évaluation de l’erreur est problématique. Heureusement, il existe plusieurs moyens pour la contrôler.

• On peut calculer numériquement — quand le problème en possède — une grandeur conservativePar exemple, dans un système conservatif ou hamiltonien, l’énergie mécanique est une constante du mouvement.. Ainsi toute variation des valeurs numériques de cette grandeur permet d’estimer la précision de la méthode.
• Pour les méthodes qui reposent sur une discrétisation de l'espace et/ou du temps, on peut voir l'influence d'une diminution du pas. Si les solutions sont proches, on peut penser que la méthode est fiable ; l’écart entre les deux solutions donne alors un ordre de grandeur de l’erreur produite. À l’inverse, si une diminution du pas donne une solution radicalement différente de la précédente il est hautement probable que l’on se trouve dans une “région d’instabilité”.
• En ce qui concerne les méthodes de Monte Carlo il est bon de tester deux générateurs de nombres pseudo-aléatoires pour vérifier que le biais induit par le caractère imparfait du générateur est bien négligeable devant les erreurs statistiques.

Dans tous les cas, il ne faut pas négliger une analyse critique des erreurs numériques. Celle-ci est d'ailleurs d’autant plus facile qu’on possède une bonne intuition du phénomène étudié.