Les limites des ordinateurs dans la résolution des problèmes numériques

LES LIMITES DE L'ORDINATEUR DANS LA RESOLUTION D'UN PROBLEME NUMERIQUE

Par NGOIE MPOY Ruffin Benoît^1(*)

ABSTRACT

The goal of this article is to show to the user that computer, fast and powerful computational tool, cannot be used without precautions to deal with mathematical problems.

In calculations, numbers handled by the computer are represented in memory with a restricted number of figures. This limitation inherent in the structure of the machine is sometimes generating errors which can make lose any significance with a result.

The examples are given in PASCAL language, but certain results were produced by a programmable calculator of mark Texas Instrument TI 86

INTRODUCTION

Le but de cet article est de montrer à l'utilisateur que l'ordinateur, outil de calcul rapide et puissant, ne peut pas être utilisé sans précautions pour traiter les problèmes mathématiques.

Dans les calculs, les nombres manipulés par l'ordinateur sont représentés en mémoire avec un nombre restreint des chiffres. Cette limitation inhérente à la structure de la machine est parfois génératrice d'erreurs qui peuvent faire perdre toute signification à un résultat.

Les exemples sont donnés en langage PASCAL, mais certains résultats ont été produits par une calculette programmable de marque Texas Instrument TI 86

1. Notation

Nous supposerons que le lecteur s'est familiarisé avec les propriétés élémentaires des ensembles IN, Z, Q et IR où :

IN =

Z =

Q =

IR = Q U I où I = (Mubenga, K., 1984)

2. Quelques rappels des notions mathématiques

2.1. Théorème de Rolle

Soit une fonction continue dans. Si admet une dérivée pour tout de et si, il existe au moins un nombre tel que . (Chambadal, L., 1968)

Démonstration

Par hypothèse, il existe sur une courbe d'équation au moins un point d'abscisse où la tangente est parallèle à OX (). Soit cette tangente, puisque est parallèle à OX, son équation est de la forme. Il est clair que son coefficient angulaire qui est est nul. D'où.

2.2. Formules des accroissements finis

Soit une fonction continue dans. Si admet une dérivée pour tout de et si, il existe au moins un nombre tel que :

Démonstration

En effet, il suffit d'appliquer le théorème de Rolle à la fonction puisque est continue dans et que, il existe un nombretel que or .

D'où et

(Lorent, R et Lorent, S., 1990)

2.3. Formule de Taylor

2.3.1. Introduction

Considérons le polynôme et ses dérivées successives. On a :

...

D'où et (2.3.1)

Nous nous proposons d'étendre la formule des accroissements finis en introduisant les dérivées successives de  : On obtient la formule de Taylor.

La formule (2.3.1) qui est valable pour un polynôme de degré n sera généralisée. Cette formule est dite de Mac Laurin. Notons que la formule de Mac Laurin est un cas particulier de la formule de Taylor.

2.3.2. Formule de Taylor

Soit une fonction continue dans qui admet des dérivées 1^ère, 2^ème, ..., n^ième continues dans et qui, de plus, admet une dérivée (n+1)^ième fini dans

Posons

Remarquons que

(2.3.2)

Considérons la fonction, nous avons en vertu des relations (2.3.2),

Remarquons que est continue dans et qu'elle admet une dérivée dans ; il en est de même de

Comme, il existe, en vertu du théorème de Rolle une valeur telle que :

avec. Dès lors, comme, il existe une valeur telle que avec Et ainsi de suite jusque : avec . D'où, puisque  :

avec

Or en dérivant successivement et en remarquant que, on obtient :

D'où avecet

avec

En remplaçant par sa valeur, on obtient la formule de Taylor :

(2.3.2 bis) où

avec s'appelle le reste de la formule de Taylor.

La formule (2.3.2 bis) dite formule de Taylor est encore valable si

Remarque

Si on pose et , on obtient une autre forme de la formule de Taylor :

où avec

3. Limites de l'ordinateur

Représentation des nombres réels en mémoire

Dans un ordinateur, tout nombre réel peut s'écrireavec . Pour un ordinateur donné, il existe deux entiers et tels que les nombres réels manipulés par cet ordinateur soient ceux pour lesquels le développement binaire de est de la forme avec (et donc ) et . Ces nombres sont rangés en mémoire sur un nombre fixe d'octets. Il est à remarquer que tous ces nombres sont des rationnels.

Dans un ordinateur, chaque nombre est placé dans un mot de la mémoire. Un mot est formé d'un nombre fini de cases, chacune ne pouvant contenir qu'un seul chiffre. Dans la première, on va placer le signe de , puis les chiffres successifs de la mantisse de , ensuite le signe de son exposant. Chaque mot de la mémoire d'un ordinateur ne peut donc contenir, comme nous l'avons précédemment dit, qu'un nombre fini des chiffres. En particulier, nous appellerons le nombre de chiffres décimaux de la mantisse des mots de l'ordinateur (en général, on aura =7 ou 8 en simple précision, 15 ou 16 en double précision). Par conséquent, seuls seront représentés de façon exacte les nombres dont la mantisse ne dépasse pas chiffres. Le problème qui se pose à nous maintenant est simple : comment représenter un nombre réel ayant une mantisse avec un nombre de chiffres supérieur à à l'aide d'un mot de la mémoire qui ne peut en contenir que  ? Il y a deux possibilités.

· La troncature qui consiste à couper (à tronquer) la mantisse de après son -ième chiffre,

· L'arrondi qui consiste à tenir compte du ()-ième chiffre. Si celui-ci est inférieur à 5, on tronque tandis que, s'il est supérieur ou égal à 5, on ajoute une unité au -ième chiffre avant de tronquer. Il y a quatre sortes d'arrondi : supérieur, inférieur, vers zéro et au plus proche. Nous venons de décrire celui au plus proche tandis que la troncature correspond à l'arrondi vers zéro.

Presque la totalité des ordinateurs travaille actuellement par arrondi. Dans les deux cas, le nombre réel est donc représenté dans l'ordinateur par un nombre (dit nombre machine) qui, en général, en est une approximation. Nous l'appellerons, que l'ordinateur travaille par troncature ou par arrondi. L'erreur ainsi commise s'appelle erreur d'affectation parce qu'au nombre réel on affecte un mot contenant le nombre . On a le théorème suivant :

Théorème

« L'erreur d'affectation vérifie où K= 5 si l'ordinateur travaille par arrondi et 10 s'il travaille par troncature »

Démonstration

Donnons la démonstration dans le cas de la troncature. On a :

Donnons une borne supérieure de ce rapport en majorant son numérateur et en minorant son dénominateur. Le numérateur est majoré par 0.99999... = 1 et le dénominateur est minoré par 0.100... puisque Par conséquent . (Brezinski, C. et Redivo-Zaglia, M., 2005) 

Il est évident que, pour l'arrondi, l'erreur est deux fois plus faible et correspond donc à K = 5.

Remarquons que l'on peut également écrire l'inégalité donnée dans ce théorème sous forme d'égalité avec

Erreur d'arrondi

Nous venons de voir que la taille de la place réservée en mémoire pour ranger un nombre est fixée. Il en résulte que si les nombres manipulés ont une écriture nécessitant pour plus de chiffres en base 2, ils devront être nécessairement rangés sous forme tronquée donc approchée. Ceci conduit à une erreur sur le nombre appelée erreur d'arrondi. Cette erreur est très faible et peu significative si l'on considère le nombre individuellement (elle ne dépasse pas 2^-k-1 en valeur relative)

Opérations arithmétiques

Voyons maintenant comment un ordinateur s'y prend pour effectuer les quatre opérations arithmétiques élémentaires +, -, x, /.

Addition

Soit à calculer A = B + C. Cette opération, comme les trois autres d'ailleurs, ne s'effectue pas dans la mémoire centrale mais dans ce que l'on appelle l'accumulateur. Cette accumulateur est un ensemble de trois mots dont la particularité est d'avoir les mantisses avec chiffres au lieu de . C'est pour cela que l'on parle souvent d'accumulateur en double précision (même si, dans la pratique, chiffres ne pas nécessaires mais seulement pour l'addition et la soustraction et pour la multiplication.

Pour effectuer l'opération A = B + C, l'ordinateur commence par recopier sans modification dans l'accumulateur celui des deux opérandes qui est le plus grand en valeur absolue. Comme, dans l'accumulateur, la mantisse doit avoir chiffres, il la complète à droite par des zéros. Puis il recopie l'autre opérande dans l'accumulateur en faisant en sorte que son exposant soit le même que celui du premier opérande. Pour cela, on rajoute éventuellement des zéros à gauche de la mantisse (c'est-à-dire avant ). Pour fixer les idées, donnons un exemple avec . Supposons B = 0.23487757 x 10³ et que C = 0.56799442. Dans l'accumulateur on recopie B tel quel, c'est-à-dire que l'on aura B=0.2348775700000000x10³. pour que C ait le même exposant que B, il faut le multiplier par 10³.

Mais il faut, bien sûr, le diviser aussi par 10³ pour que sa valeur ne change pas, c'est-à-dire que C = (0.56799442/10³ )x10³ et, dans l'accumulateur, on aura C = 0.000567994420000x10³

Finalement, cela montre que l'ordinateur procède comme quand nous effectuons une addition avec un papier et un crayon : nous plaçons les uns en dessous des autres les chiffres correspondants aux puissances identiques de 10. Maintenant, l'addition peut s'effectuer dans l'accumulateur et l'on trouve B + C = 0.2354455644200000 x 10³. On voit que, dans l'accumulateur, l'addition s'est effectuée sans aucune erreur ( au moins sur cet exemple ; on verra plus loin d'autres exemples où le résultat obtenu dans l'accumulateur présente une erreur). Enfin, notre résultat doit être renvoyé dans un mot de la mémoire de l'ordinateur. Or ces mots ont des mantisses qui ne possèdent que (8 dans notre exemple) chiffres. Nous allons donc faire une erreur qui est celle que l'on commet lorsque l'on place un nombre ayant une mantisse de plus de chiffres dans un mot qui n'en accepte que  : C'est une erreur d'affectation telle qu'elle est donnée par le théorème précédent. Il est évident que les choses se passent de la même façon pour une soustraction. Dans l'exemple précédent, on obtiendra donc A = 0.23544556 x 10³ que l'ordinateur procède par arrondi ou par troncature.

Multiplication

Dans le cas d'une multiplication, le produit de deux mantisses de longueur donne un résultat de longueur et les exposants s'ajoutent. Le résultat d'une multiplication est donc exact dans l'accumulateur et la seule erreur que l'on commet est, de nouveau, une erreur d'affectation en revenant de l'accumulateur dans la mémoire.

Division

Pour une division enfin, il est évident que, dans l'accumulateur, le résultat n'est pas toujours exact (par exemple, lorsque l'on divise 1 par 3, le résultat possède une infinité de 3). L'erreur, dans l'accumulateur, se situe au niveau du -ième chiffre, c'est-à-dire une erreur supérieure. Comme le résultat du Théorème de l'erreur d'affectation fournit une borne supérieure de l'erreur, il est donc toujours valable. Nous avons démontré que, pour toute opération arithmétique, l'erreur est donnée par le Théorème de l'erreur d'affectation et nous avons finalement le Théorème suivant :

Théorème

« L'erreur sur une opération arithmétique satisfait avec K=5 dans le cas de l'arrondi, K=10 dans celui de la troncature et où * est l'une des opérations +, -, x, / » (Cottet-Emard, F et Goetgheluck, F., 1993) 

Exemples

a. Exemple 1

Nous pouvons vérifier rapidement sur un ordinateur qu'on peut trouver r suffisamment grand tel que :

Opérations	Résultat par Ordinateur	Résultat par Calculette TI 86 (r = 500)
1 + 10^-r	1	1
1 + 10^-r- 1	0	0
1 - 1 + 10^-r	10^-r	10^-r
	0 (au lieu de 1)	0

Ces résultats s'expliquent en remarquant que :

· Les opérations sont effectuées de la gauche vers la droite

· Quand on effectue 1 + 10^-r, l'opération de décalage et de troncature sur 10^-r transforme ce nombre en 0.

b. Exemple 2

L'exécution des instructions suivantes :

PROGRAM Calcul1 (INPUT, OUTPUT);

VAR

n : INTEGER ;

s : REAL ;

BEGIN

s := 0 ;

FOR n := 1 TO 10000 DO s := s + 1.0 E-10 ;

s:= s+1;

WRITE (s) 

END.

et l'exécution de :

PROGRAM Calcul2 (INPUT, OUTPUT);

VAR

n : INTEGER ;

s : REAL ;

BEGIN

s := 1 ;

FOR n := 1 TO 10000 DO s := s + 1.0 E-10 ;

WRITE (s)

END.

peuvent afficher des valeurs différentes à l'écran. En effet, s donne 1.0000010000 E+00 pour Calcul1 et 1.0000010004 E+00 pour Calcul2.

Ceci nous suggère le principe suivant :

« Dans une somme, il sera toujours préférable d'additionner d'abord les termes les plus petits en valeur absolue pour leur cumul ne soit pas négligé face aux termes les plus grands »

c. Exemple 3

L'affichage est fait en base 10 avec un nombre fixé de chiffres. Les nombres sont le plus souvent fournis à l'ordinateur sous forme décimale. Nous avons vu qu'ils sont transformés et manipulés sous forme binaire avec les erreurs que cela comporte. Une fois le calcul terminé, ils sont reconvertis en base 10, ce qui introduit une nouvelle erreur. L'affichage sur l'écran ne fournit donc pas nécessairement la valeur exacte contenue en mémoire.

Opération	Résultat affiché
	1

Sur une calculette de marque Texas instrument TI 86 x = 10^-14

· La première opération donne un résultat apparemment exact. Si ce résultat était rigoureusement exact, on devrait avoir 0 comme résultat de la seconde opération. Pour comprendre ce qui s'est passé, travaillons en base 2 :

Un calcul simple montre qu'alors, est représenté en mémoire en base 2 par 0.1111111... (t+1 chiffres 1) nombre qui vaut 1 - 2^-t et qui est arrondi à 1 pour être affiché en base 10 avec un maximum de précision. En revanche dans la seconde opération, c'est 2^-t qui sera affiché.

d. Exemple 4

· · On a . Par le théorème des accroissements finis, on a aussi :

Donc, pour x positif :

On pourra vérifier par un calcul sur ordinateur que pour x suffisamment grand, les formules donnant fournissent des résultats acceptables contrairement à la formule qui donne t.

Testés sur une calculette Texas Instrument TI 86, les résultats obtenus sont pour x=E+100 (soit 10¹⁰⁰) :

e. Exemple 5

Une erreur répétée un grand nombre de fois ou multipliée par un grand nombre peut conduire à une erreur globale non négligeable.

L'exécution des instructions suivantes affectera à ERREUR une valeur non nulle alors que d'un point de vue strictement mathématique on devrait avoir ERREUR = 0.

PROGRAM Calcul3 (INPUT, OUTPUT);

VAR

I : INTEGER ;

S, ERREUR, a : REAL ;

BEGIN

a := 1/3 ;

S:=0;

FOR I:= 1 TO 30000 DO s := s + a ;

ERREUR:= S-10000;

WRITE (ERREUR)

END.

Remarquons que 1/3 est représenté en mémoire par une valeur par défaut. Par ailleurs au fur et à mesure que S augmente, 1/3 est de plus en plus décalé et tronqué pour additionner S et a. Il en résulte une petite erreur par défaut. Testé sur ordinateur, ce code revoie la valeur -2,5331974030 E-06 au lieu de 0. 

f. Exemple 6

La récursivité donne la possibilité de faire figurer dans la définition d'un objet une référence à ce même objet.

Une procédure ou une fonction récursive est un sous - programme qui s'appelle lui-même, et qui intègre une variable de contrôle permettant d'arrêter le processus d'appel.

On considère les suites () et () définies par :

Les programmes récursifs de calcul des termes de ces suites sont :

PROGRAM Calcul4 (INPUT, OUTPUT);

VAR

I, n : INTEGER ;

FUNCTION terme(val:INTEGER):REAL;

BEGIN

IF val = 0

THEN terme:=1/3

ELSE terme:=4*terme(val-1)-1

END ;

BEGIN

WRITELN(`Saisir un nombre entier');

READLN(n) ;

WRITE(`Le terme qui correspond à ce nombre est',terme(n)) 

END.

Et

PROGRAM Calcul5 (INPUT, OUTPUT);

VAR

I, n : INTEGER ;

FUNCTION terme(val:INTEGER):REAL;

BEGIN

IF val = 0

THEN terme:=4/3

ELSE terme:=terme(val-1)/4+1

END ;

BEGIN

WRITELN(`Saisir un nombre entier');

READLN(n) ;

WRITE(`Le terme qui correspond à ce nombre est',terme(n)) 

END.

Calculés à la main, les termes successifs de ces deux suites sont égaux à 1/3 pour () et 4/3 pour (). Les deux suites sont donc constantes (Thiel, E., 2004)

* ¹ Assistant au Département de Mathématique à l'ISP/Mbanza-Ngungu