Introduction à l'analyse numérique
Notion de base - Stockage des valeurs numériques dans l'ordinateur
Les valeurs sont d'abord converties en binaire, représentées par les 0 et 1 dans la machine. Pour la représentation d'une valeur, on utilise un nombre de bit déterminé. Dans les machine d'aujourd'hui, on utilise au moins 32 bits pour représenter une valeur numérique. C'est aussi la longueur d'un mot de machine.
Représentation des entiers
Si on utilise 8 bits pour représenter une valeur entière, on peut avoir le schéma de représentation simple comme suit:
1 bit pour représenter le signe (positif ou négatif), et 7 autres bits pour la valeur. Dans ce schéma, on peut représenter des valeurs entières dans [-(27-1), (27-1)]. Si on utilise 16 bits, les valeurs représentées sont alors [-(215-1), (215-1)].
Pour la représentation de valeurs négatives, on utilise le complément de 2L où L est le nombre de bits utilisés. Ainsi, le complément d'une valeur v dans une représentation à 8 bits sera 28-v. Soit v la valeur 5. Elle est représentée par "00000101". La valeur -5 est donc représentée par son complément de 28, soit "11111011". Cette manière de représenter les valeurs négatives permet de considérer la soustraction exactement comme une addition, en utilisant le débordement (overflow).
Pour les machines d'aujourd'hui, on utilise 32 bit pour représenter un int, et 64 bits pour un long.
Représentation des réels
Il y a 2 principes de représentation: à point fixe et à point flottant.
Point fixe
Cette méthode fixe une position pour le point décimal. La partie à gauche du point est utilisée pour représenter la partie entière, et la partie droite est utilisée pour la partie décimale. Par exemple si on utilise 15 bits pour la partie entière et 16 bits pour la partie décimale, et un autre bit pour le signe, nous aurons le schéma suivant:
|1|2 16|17 32|
Les valeurs qu'il peut représenter sont donc dans l'intervalle ±[2-16, 215). Par exemple, la valeur de 1.5 sera représentée comme "0000000000000001.1000000000000000". Cette intervalle est très limitée.
Point flottant
Ce schéma consiste à représenter une valeur réelle comme ±M * 2E où 1≤M<2 est la mantisse, et E l'exposant. Par exemple, la valeur 5.5 sera transformée en 1.011 * 210 en code binaire. Dans un schéma de représentation à point flottant, on fixe la longueur de M et de E selon le standard IEEE qui sont comme suit (où a1a2… est l'exposant et b1b2 … est la mantisse):
Précision simple (32 bits) |
| ± |a1a2… a8|b1b2 … b23| |
Précision double (64 bits) |
| ± |a1a2… a11|b1b2 … b52| |
Précision étendue (96 bits) |
| ± |a1a2… a15|b1b2 … b64| |
Remarques:
1. Selon ce standard, la mantisse doit être sous forme 1.b1b2…. Ainsi, la valeur 1 devant le point décimal n'est pas représentée explicitement. On représente seulement les chiffres après le point décimal (a1a2…).
2. Dans le cas où le signe est 0 et l'exposant est aussi 0, on tomber dans le cas "sous-normal" (subnormal). Dans ce cas particulier, la mantisse est de forme 0.b1b2 …
Problème de précision
Quelque soit le schéma de représentation, il peut toujours y avoir un problème de précision. La différence minimale entre deux valeurs représentables dépend de la longueur de mantisse et de l'exposant. La table suivante donne l'écart minimal dans différents schémas:
Précision simple (32 bits) |
e = 2-23 * 2-8 |
Précision double (64 bits) |
e = 2-52 * 2-11 |
Précision étendue (96 bits) |
e = 2-64 * 2-15 |
Quand la valeur de l'exposant augmente, cet écart augmente aussi. Par exemple, dans le cas ou l'exposant=0, l'écart minimal dans le représentation à précision simple est 2-23. Entre ces valeurs représentables, il y a donc beaucoup de valeurs non représentables dans un schéma donné.
Erreur dans les représentations et les calcules
Il y a deux notions d'erreur: erreur absolue et erreur relative.
L'erreur absolue est l'écart entre la valeur précise et sa représentation. Soit Q la valeur précise, et Q* sa représentation. L'erreur absolue est E = D Q = |Q-Q*|.
L'erreur relative est l'erreur absolue par rapport à la valeur précise: Er = D Q / |Q| £ D Q /(|Q*| - D Q)
L'erreur est souvent due à l'arrondissage. La règle d'arrondissage est: si le premier chiffre à arrondir est >= 5, ajouter 1 dans le chiffre devant.
Exemples:
Q |
Q* |
erreur absolue |
316.872 |
316.9 |
£ 0.5 * 10-1 |
4.167500 |
4.168 |
£ 0.5 * 10-3 |
0.00111118 |
0.001112 |
£ 0.5 * 10-6 |
436276 |
4.363*105 |
£ 0.5 * 102 |
R1: L'erreur absolue engendrée par un arrondissage est donc £ 0.5 * 10P où P est la position de l'arrondissage.
Chiffre significatif exact
Un chiffre dans un nombre approximatif est exact si l'erreur absolue de ce nombre est < 1/2 * l'unité du rang du chiffre en question.
Exemple1: le n-ième chiffre décimal est exact si l'erreur absolue < 0.5 * 10-n.
Exemple 2: si on représente 2/3 par 0.6667, le troisième 6 est exacte parce que |2/3 - 0.6667| < 0.5*10-3, et le chiffre 7 est aussi exact parce que |2/3 - 0.6667| < 0.5*10-4.
Afin de minimiser la perte de précision, voici les règles générale sur l'arrondissage:
Erreur relative v.s. chiffre significatif exact
Théorème 1:
Si un nombre approximatif possède n chiffres significatifs exacts, alors l'erreur relative est < 5*10-n (sauf pour les nombres sous forme d'un 1 suivi par n-1 zéros).Par exemple, soit Q* = 34.152, et on sait que les 5 chiffres sont significatifs exacts. L'erreur relative dans ce nombre est donc < 5*10-5. Cela peut être vérifié comme suit:
L'erreur absolue est au maximum 0.5*10-3 selon R1.
L'erreur relative est £ D Q /(|Q*| - D Q) £ 0.5*10-3 / (34.152 - 0.5*10-3) = 1/68303 < 5*10-5.
Ainsi, cet exemple vérifie le théorème.
Dans le cas de 1 suivi de n-1 zéro, le théorème n'est plus valide. Voyons quelques exemples:
n |
Q* |
erreur relative |
selon théorème 1 |
1 |
1 |
0.5/(1-0.5) = 1 |
5*10-1 |
2 |
10 |
0.5/(10-0.5) = 1/19 |
5*10-2 |
3 |
100 |
0.5/(100-0.5) = 1/199 |
5*10-3 |
4 |
1000 |
0.5/(1000-0.5) = 1/1999 |
5*10-4 |
On voit que l'erreur prédite par le théorème est plus petite que l'erreur réelle. Donc, le théorème n'est pas valide dans ces cas.
Théorème 2: Soit Q* une approximation de Q. Si l'erreur relative dans Q* est £ 0.5*10-n, alors Q* possède au moins n chiffres significatifs exacts.
Donc, si on sait que l'erreur relative dans 345.24 est £ 0.5*10-4, on peut conclure qu'au moins les chiffres 3, 4, 5, et 2 sont exacts. Le chiffre 4 reste incertain.
Propagation des erreurs dans les opérations arithmétiques
Soit u et v deux nombres qui sont représentés par u* et v*. Les erreurs absolues dans u* et v* sont respectivement D u et D v. On a alors:
Opération |
erreur absolue |
erreur relative |
u* + v* |
D u + D v |
(D u + D v) / |u* + v*| |
u* - v* |
D u + D v |
(D u + D v) / |u* - v*| |
u* * v* |
|u*| D u + |v*| D v |
D u/|u*|+ D v/|v*| |
u* / v* |
|(|u*| D u - |v*| D v) | /(v*)2 |
D u/|u*|+ D v/|v*| |
Si on examine les erreurs relatives associées aux opérations, on voit que l'opération la plus dangereuse est la soustraction. Si u* et v* sont rapprochées, l'erreur relative après la soustraction peut être très grande.
Voyons un exemple pour voir comment l'erreur relative peut être amplifiée. Soit u*=754.8 et v*=37.68151, et on suppose que tous les chiffres sont exacts. Les erreurs relatives de u* et v* sont respectivement <5 * 10-4 et <5*10-7 selon le théorème 1.
Après la soustraction, l'erreur absolue dans u*-v* est D (u-v) £ D u + D v = 0.5*10-1 + 0.5*10-5 = 0.50005. L'erreur relative dans u*-v* est donc £ (D (u-v) / | u*-v*| - D (u -v) £ 0.50005/(717.11849 - 0.50005) » 0.00007 < 0.5*10-3.
Par rapport aux erreurs relative de u*, cette nouvelle erreur relative est légèrement amplifiée. Ce n'est pas un cas critique parce que u* et v* sont des valeurs très différentes.
Exemple 2: Soit u*=67815 et v*=67814, et tous les chiffres sont exacts.
Les erreurs relatives de ces deux nombres sont < 5*10-5 selon le théorème 1.
L'erreur absolue dans u*-v* est D (u-v) £ 0.5 + 0.5 = 1. L'erreur relative de u*-v* est £ D (u-v) / (|(u*-v*)| - D (u-v)) = 1/0 ® ¥ . On voit que l'erreur relative dans u*-v* peut être très grande.
Il peut sembler curieux que la division n'amplifie pas l'erreur relative. L'erreur relative après la division est comparable aux erreurs d'avant la division. Pour vous convaincre, faites l'exercice de calcule de l'erreur relative d'une division. Déterminez d'abord les erreurs absolues. Ensuite, vous allez pouvoir calculer une borne supérieure pour l'erreur relative et obtenir la formule du tableau précédent.
Condition et instabilité d'une formule
On vient de voir qu'il faut se méfier de la soustraction. Si une formule contient une opération de soustraction entre deux nombres rapprochées, il y a la danger d'amplification d'erreur relative, et le résultat obtenu peut être peu précis. Afin de déterminer si une formule de calcule peut engendrer une grande perte de précision, on utilise la notion de condition.
Condition: La condition d'une formule détermine si le résultat de la formule est sensible à un petit changement dans la valeur d'une variable. Elle est calculée comme suit:
Condition(f, x) = changement relatif de f(x) / changement relatif de x
= max{[|f(x) - f(x*)| / |f(x)|] / [|x-x*| / |x|]}
où |x-x*| est un petit changement sur x, (|x-x*| / |x|) un changement relatif sur x.
Il est possible d'utiliser le dérivé f'(x) pour représenter [f(x)-f(x*)]/(x-x*). La formule ci-dessus peut donc être transformée en la suivante:
Condition(f,x) = |f'(x)*x / f(x)|
Si la valeur de Condition(f,x) est élevée, la fonction est mal formulée, et elle peut générer une très grande erreur relative.
Exemple 1: Soit la fonction f(x) = x1/2. F'(x) = 1/(2x1/2). On a donc:
Condition(f,x) = | 1/(2x1/2)x / x1/2 | = 1/2.
Cette valeur est petite. Cela signifie que le calcule de cette fonction ne va pas amplifier l'erreur relative de x. La fonction est donc bien formulée.
Exemple 2: Soit f(x) = 10/(1-x2). On a f'(x) = 20x / (1-x2)2.
Condition(f,x) = | (20x / (1-x2)2)x / (1-x2) | = 2x2 / |1-x2|.
Si x® 1, la condition ® ¥ . Donc, la fonction est mal formulée quand x® 1 (ou -1).
Instabilité: L'instabilité d'une formule signifie la sensibilité de la fonction aux erreurs d'arrondissage durant le calcule. L'examen de l'instabilité d'une formule consiste à décomposer la formule étape par étape, et examiner si chaque étape est bien conditionnée. Si une des étapes est mal conditionnée (a une condition élevée), la formule est alors instable.
Si une fonction est mal conditionnée, alors elle est aussi instable. Par contre, si une formule est instable, il ne signifie pas nécessairement que la fonction est mal conditionnée. Il se peut que la formule choisie est instable (i.e. une des étapes impliquées est mal conditionnées). Il est possible qu'on trouve une formule équivalente pour la remplacer et que cette nouvelle formule devient stable.
Par exemple, soit f(x) = (1+x)1/2 - x1/2
La condition de cette fonction est bonne quand x est très grande: Condition(f,x) = 1/[2(x+1)1/2x1/2] » 1/2
Cependant, si on examine les étapes de calcules, on peut voir que la formule est instable.
Décomposons cette formule comme suit:
Soit la valeur de x = x0.
f1(x0) = x0 + 1 = x1
f2(x1) = x11/2 = x2
f3(x0) = x01/2 = x3
f4(x3) = x2 - x3
Si on calcule la condition de f1, f2, f3, on peut voir que ces fonctions sont bien conditionnées. Cependant, f4(x3) ne l'est pas si x3® x2 (ou si la valeur de x0 est très grande). Dans ce cas, Condition(f4, x3) = |x3 / (x2 - x3)| qui tend vers ¥ quand x3® x2. Cette étape est donc mal conditionnée. La formule globale est donc instable.
Cependant, pour cette formule, il est possible de trouver une autre formule équivalente qui est stable, parce que la condition de la fonction globale est bien conditionnée. La formule équivalente qu'on peut utiliser est:
f(x) = 1/[(x+1)1/2 + x1/2].
Vous pouvez vérifier que cette formule est stable quand x est très grande.