448 pages analyse.pdf

~ 17 nalyse J numrique

pour ingnieurs

Andr Fortin

EDITIONS DE L ECOLE POLYTEC~QUE DE MONTREAL

A vaut-propos

Ce manuel reflte mon exprience comme professeur et comme coordon-nateur du wurs d'analyse numrique 215 offert aux tudiants de l'cole Polytechnique de MontraL Chaque anne, environ 500 tudiants suivent ce cours qui propc un survol des principales mthodes numriques lmen-tai res et couvre plus particulirement les sujets sui\-ants;

analyse d'erreurs;

racines d'une quation algbrique;

systmes d'quations linaires et non linaires;

interpola tion, diffrentiation et intgration numriques;

quations diffrentielles ordinaires.

La premire tche du coordonnateur consiste trou\er un livre qui convienne parfaitement la matire fixe par les exigences du programme d'eJJscigne-mcnt. On trouve sur le march de nombreux livres qui trai tent de l'analyse numrique. Cette branche des mathmatiques appliques conn ait en effet un essor considrable depuis plusieurs annes et peu prs toutes les facults de gnie offrent au moins un COilTS d'introduction l'analyse numrique, ~uivi trs souvent d'un second cours plus avanc. On peut mettre la main sur nombre de bons manuels conus aux tats-Unis et donc publis en anglais. Du ct qubcois, comme on peut s'y attendre, la production est mince en raison de l'troitesse du march. Enfin, les ouvrages en provenance d'Europe ne conviennent pas nos besoins en raison de leur contenu mathmatique trop avanc.

Cet tat de fa.i t m 'aconduit tenter l'exprience de rassembler mes notes de cours et de publier ce manuel. Le lecteur y trouvera une introduction l'analyse numrique lmentaire motive pa.r les applications en ingnierie.

VI Avant-propos

n m'a paru intressant d'aborder du mme coup un domaine en pleine ex-pansion que j'ai eu l'occasion d'explorer pendant mes actiVits de recherche, savoir les systmes dynamiques. ll ne s'agit ici que d'illustrer la contribu-tiOn des mthodes numriques au dveloppement de ce champ d'activits. J'attire tout au plus l'attentiOn sur quelques comportements des systmes dynamiques qui peuvent tre observs l'aide de mthodes numriques l-mentaires.

L'approche pdagogique de ce manuel repose sur une comprhension pro-fonde des mthodes plutt que sur l'aspect calculatoire. Cela signifie que les exemples choisis cherchent avant tout illustrer diffrents aspects des m-thodes et souligner leurs avantages et leurs inconvnients. Cette approche est justifie en partie par le fait que de plus en plus d'ingnieurs utilisent des outils logiciels commerciaux. L'objectif de ce manuel est donc de faire des tudiants des utilisateurs intelligents, en ce sens qu'ils sauront exactement quoi s'attendre de chaque mthode et qu'ils seront en mesure de valider leurs rsultats.

En terminant, j'aimerais remercier toutes les personnes qui ont contribu la rahsatwn de ce manuel. En particulier, Mme Carole Burney-Vincent et M. Gilles Savard du dpartement de mathmatiques et de gnie industriel ont patiemment lu et comment plusieurs chapitres. M. Robert Roy a accept de se servir d'une version prliminaire pour le cours d'analyse numrique donn pendant l't de 1994; ses remarques et ses suggestiOns ont t trs utiles. J'a1 galement pu compter sur la collaboration de toute l'quipe professorale du cours d'analyse numrique. ll me faut galement souligner la participation du Serv1ce Pdagogique de l'cole Polytechnique de Montral.

Enfin, je ne peux passer sous silence l'appui inconditionnel de mon pouse Marie et de mes fils Michel et Jean-Philippe qui ont d, entre autres choses, subir mes absences frquentes lors de la rdaction et de la mise en pages finale de cet ouvrage. Je tiens de plus souhgner que la page couverture de ce manuel est inspire des dessins de Michel et Jean-Philippe.

Veuillez tous trouver in l'expression de ma plus profonde reconnaissance.

Table des matires

1 Analyse d'erreurs 1.1 Introduction ..

1 1

1.2 Erreurs de modlisation . . . . . . . . . 5 1.3 Reprsentation des nombres sur ordinateur 9

1.3.1 Reprsentation des entiers signs 9 1.3.2 Reprsentation des nombres rels 13

1.4 Erreurs dues la reprsentation 18 1.5 Arithmtique flottante . . . . 23

1.5.1 Oprations lmentaires 24 1.5.2 Oprations risques . . . . 27 1.5.3 valuation des polynmes 32

1.6 Erreurs de troncature . . . . . 33 1.6.1 Dveloppement de Taylor en une variable 34 1.6.2 Dveloppement de Taylor en plusieurs variables 41 1.6.3 Propagation d'erreurs dans le cas gnral 43

1.7 Exercices

2 quations non linaires 2.1 Introduction . . . . . 2.2 Mthode de la bissection . 2.3 Mthodes des points fixes

2.3.1 Convergence de la mthode des points fixes 2.3.2 Interprtation gomtrique 2.3.3 Extrapolation d'Aitken

2.4 Mthode de Newton ..... 2.4.1 Interprtation gomtrique 2.4.2 Analyse de convergence 2.4.3 Cas des racines multiples

47

53 53 54 61 64 70 72 75 77 78 80

VIII Table des matires

2.5 Mthode de la scante . . . . . . . . . . 2.6 Applications ............... .

2.7

2.6.1 Modes de vibration d'une poutre 2.6.2 Premier modle de viscosit Exercices

3 Systmes d'quations algbriques 3.1 Introduction ........... . 3.2 Systmes linaires . . . . . . . . 3.3 Oprations lmentaires sur les lignes .

3.3.1 Multiplication d'une ligne par un scalaire 3.3.2 Permutation de deux lignes 3.3.3 Opration(~+-~+ >..lj) .

3.4 limination de Gauss . . . . . . 3.5 Dcomposition LU . . . . . . .

3.5.1 Principe de la mthode 3.5.2 Dcomposition de Crout 3.5.3 Dcomposition LU et permutation de lignes 3.5.4 Calcul de la matrice inverse A-1

3.6 Effets de l'arithmtique flottante . . . . . . 3.7 Conditionnement d'une matrice ...... .

3.7.1 Bornes d'erreurs et conditionnement 3.8 Systmes non linaires . . . . . . . . . . . 3.9 Applications . . . . . . . . . . . . . . . . .

3.9.1 Calcul des tensions dans une ferme 3.9.2 Deuxime modle de viscosit

3.10 Exercices

4 Systmes dynamiques discrets 4.1 Introduction ......... . 4.2 Application quadratique . . . 4.3 Mthodes de points fixes: cas complexe . 4.4 Mthodes de points fixes en dimension n

4.4.1 Attracteur d'Hnon ....... . 4.5 Mthodes itratives pour les systmes linaires

4.5.1 Mthode de Jacobi .... 4.5.2 Mthode de Gauss-Seidel

4.6 Exercices

85 88 88 91 95

101 101 102 107 109 110 111 113 118 118 119 127 132 135 142 150 155 162 162 166 169

177 177 177 188 192 201 205 207 214 218

Table des matires

5 Interpolation 5.1 Introduction . 5.2 Matrice de Vandermonde 5.3 Interpolation de Lagrange 5.4 Polynme de Newton . 5.5 Erreur d'interpolation 5.6 Splines cubiques 5. 7 Krigeage . . . . . . . .

5.7.1 Effet ppite .. 5. 7.2 Courbes paramtres . 5. 7.3 Cas multidimensionnel

5.8 Application: courbe des puissances classes 5.9 Exercices ................. .

6 Diffrentiation et intgration numriques 6.1 Introduction ....... .

IX

221 221 223 224 230 240 251 262 273 277 282 284 287

293 293

6.2 Diffrentiation numrique . . . . 294 6.2.1 Drives d'ordre 1 . . . . 294 6.2.2 Drives d'ordre suprieur 301

6.3 Extrapolation de Richardson . . 306 6.4 Intgration numrique . . . . . . . 309

6.4.1 Formules de Newton-Cotes simples et composes 310 6.4.2 Mthode de Romberg . . . . . 327 6.4.3 Quadratures de Gauss . . . . . 331 6.4.4 Intgration l'aide des splines 340

6.5 Applications . . . . . . . . . . . . . . . 343 6.5.1 Courbe des puissances classes 343 6.5.2 Puissance lectrique d'un ordinateur 344

6.6 Exercices ...... .

7 quations diffrentielles 7.1 Introduction .... . 7.2 Mthode d'Euler .. . 7.3 Mthodes de Taylor 7.4 Mthodes de Runge-Kutta .

7.4.1 Mthodes de Runge-Kutta d'ordre 2 7.4.2 Mthode de Runge-Kutta d'ordre 4.

7.5 Mthodes pas multiples ..... 7.6 Systmes d'quations diffrentielles .....

346

351 351 355 361 368 368 372 376 385

x

7.7 quations d'ordre suprieur 7.8 Mthode de tir . . . . . . . 7.9 Mthodes des diffrences finies 7.10 Applications .......... .

7.10.1 Problme du pendule .. 7.10.2 Systmes de masses et de ressorts. 7.10.3 Attracteur trange de Lorenz

7.11 Exercices ............ . Rponses aux exercices du chapitre 1 . Rponses aux exercices du chapitre 2 . Rponses aux exercices du chapitre 3 . Rponses aux exercices du chapitre 4 . Rponses aux exercices du chapitre 5 . Rponses aux exercices du chapitre 6 . Rponses aux exercices du chapitre 7 .

Table des matires

388 391 400 403 403 406 410 415 419 422 424 429 431 436 438

Chapitre 1

Analyse d'erreurs

1.1 Introduction

Les cours traditionnels de mathmatiques nous familiarisent avec des thories et des mthodes qui permettent de rsoudre de faon analytique un certain nombre de problmes. C'est le cas notamment des techniques d'intgration et de rsolution d'quations algbriques ou diffrentielles. Bien qu'on puisse proposer plusieurs mthodes pour rsoudre un problme donn, celles-ci conduisent un mme rsultat, prcis et unique.

C'est ici que l'analyse numrique se distingue des autres champs plus classiques des mathmatiques. En effet, pour un problme donn, il est pos-sible d'utiliser plusieurs techniques de rsolution qui rsultent en diffrents algorithmes. Ces algorithmes dpendent de certains paramtres qui influent sur la prcision du rsultat. De plus, on utilise en cours de calcul des ap-proximations plus ou moins prcises. Par exemple, on peut remplacer une drive par une diffrence finie de faon transformer une quation diffren-tielle en une quation algbrique. Le rsultat final et son degr de prcision dpendent des choix que l'on fait.

Une partie importante de l'analyse numrique consiste donc contenir les effets des erreurs ainsi introduites, qui proviennent de trois sources prin-cipales:

les erreurs de modlisation;

les erreurs de reprsentation sur ordinateur;

les erreurs de troncature.

2 Chapitre 1

Les erreurs de modlisation, comme leur nom l'indique, proviennent de l'tape de mathmatisation du phnomne physique auquel on s'intresse. Cette tape consiste faire ressortir les causes les plus dterminantes du phnomne observ et les mettre sous forme d'quations (diffrentielles le plus souvent). Si le phnomne observ est trs complexe, il faut simplifier et ngliger ses composantes qui paraissent moins importantes ou qui rendent la rsolution numrique trop difficile. C'est ce que l'on appelle les erreurs de modlisation.

La seconde catgorie d'erreurs est lie l'utilisation de l'ordinateur. En effet, la reprsentation sur ordinateur (gnralement binaire) des nombres introduit souvent des erreurs. Mme infimes au dpart, ces erreurs peu-vent s'accumuler lorsqu'on effectue un trs grand nombre d'oprations. Par exemple, la fraction 1/3 n'a pas de reprsentation binaire exacte, car elle ne possde pas de reprsentation dcimale finie. Ces erreurs se propagent au fil des calculs et peuvent compromettre la prcision des rsultats.

Enfin, les erreurs de troncature proviennent principalement de l'utilisa-tion du dveloppement de Taylor, qui permet par exemple de remplacer une quation diffrentielle par une quation algbrique. Le dveloppement de Taylor est le principal outil mathmatique du numricien. ll est donc primordial d'en matriser l'nonc et ses consquences.

Ce chapitre traite donc principalement d'erreurs numriques, et non des invitables erreurs de programmation qui font, hlas, partie du quotidien du numricien. Il devrait permettre au lecteur de mieux grer les erreurs au sein des processus numriques afin d'tre en mesure de mieux interprter les rsultats.

Tout d'abord, un peu de terminologie est ncessaire pour ventuellement quantifier les erreurs.

Dfinition 1.1 Soit x, un nombre, et x*, une approximation de ce nombre. L'erreur absolue est dfinie par:

~x=lx-x*l (1.1)

Analyse d'erreurs

Dfinition 1.2 Soit x, un nombre, et x*, une approximation de ce nombre. L'erreur relative est dfinie par:

E ( ) = lx- x*l = l~xl r x lxi Jxl (1.2)

De plus, en multipliant par 100%, on obtient l'erreur relative en pour-centage.

3

En pratique, il est difficile d'valuer les erreurs absolue et relative, car on ne connat gnralement pas la valeur exacte de x et on n'a que x*. Dans le cas de quantits mesures dont on ne connat que la valeur approximative, il est impossible de calculer l'erreur absolue; on dispose en revanche d'une borne suprieure pour cette erreur qui dpend de la prcision des instruments de mesure utiliss. Cette borne est quand mme appele erreur absolue, alors qu'en fait on a:

lx- x*l ~~x ce qui peut galement s'crire:

x* - ~x ~ x ~ x* + ~x (1.3) et que l'on note parfois x = x* ~x. On peut interprter ce rsultat en disant que l'on a estim la valeur exacte x partir de x* avec une incertitude de

~x de part et d'autre. L'erreur absolue donne une mesure quantitative de l'erreur commise et

l'erreur relative en mesure l'importance. Par exemple, si on fait usage d'un chronomtre dont la prcision est de l'ordre du dixime de seconde, l'erreur absolue est borne par 0,1 s. Mais est-ce une erreur importante? Dans le contexte d'un marathon d'une dure de 2 h 20 min, l'erreur relative lie au chronomtrage est trs faible:

0'

1 = 0 000 0119 2 x 60 x 60 + 20 x 60 '

et ne devrait pas avoir de consquence sur le classement des coureurs. Par contre, s'il s'agit d'une course de 100 m d'une dure d'environ 10 s, l'erreur relative est beaucoup plus importante:

0,1 10 0 = 0,01

'

4 Chapitre 1

soit 1% du temps de course. Avec une telle erreur, on ne pourra vraisem-blablement pas faire la diffrence entre le premier et le dernier coureur.

Cela nous amne parler de prcision et de chiffres significatifs au sens de la dfinition suivante.

Dfinition 1.3 Si l'erreur absolue vrifie

alors le chiffre correspondant la me puissance de 10 est dit significatif et tous ceux sa gauche (correspondant aux puissances de 10 suprieures m) le sont aussi.

Exemple 1.1 On obtient une approximation de 1r (x= 1r) au moyen de la quantit 22/7 (x*= 22/7 = 3,142 857 ). On en conclut que:

22 ~x= l1r- 71 = 0,00126

Puisque l'erreur absolue est plus petite que 0,5 x 10-2 , le chiffre des cen-times est significatif et on a en tout 3 chiffres significatifs (3,14) .

Exemple 1.2 Si on retient 3,1416 comme approximation de 1r, on a:

~x= l1r- 3,14161 ~ 0,73 x 10-5

et l'erreur absolue est infrieure 0,5 x 10-4 . Le chiffre correspondant cette puissance de 10 ( 6) est significatif au sens de la dfinition, ainsi que tous les chiffres situs sa gauche. ll est remarquer que le chiffre 6 dans 3,1416 est significatif mme si la quatrime dcimale de 1r est un 5 (3,14159 ).

Analyse d'erreurs 5

L'approximation 3,1416 possde donc 5 chiffres significatifs .

Remarque 1.1 Inversement, si un nombre est donn avec n chiffres significatifs, cela signifie que l'erreur absolue est infrieure 0,5 fois la puissance de 10 correspondant au dernier chiffre significatif. 0

Exemple 1.3 On a mesur le poids d'une personne et trouv 90,567 kg. On vous assure que l'appareil utilis est suffisamment prcis pour que tous les chiffres fournis soient significatifs. D'aprs la dfinition, puisque le dernier chiffre significatif correspond aux millimes (milligrammes), cela signifie que:

~x :=:; 0,5 x 10-3 kg En pratique, on conclut que:

~x= 0,5 x 10-3 kg

1.2 Erreurs de modlisation La premire tape de la rsolution d'un problme, et peut-tre la plus dli-

cate, consiste modliser le phnomne observ. n s'agit en gros d'identifier tous les facteurs internes et externes qui influent (ou que l'on souponne d'influer) sur les rsultats. Dans le cas d'un phnomne physique, on fait l'inventaire des forces en prsence: gravitationnelle, de friction, lectrique, etc. On a par la suite recours aux lois de conservation de la masse, de l'ner-gie, de la quantit de mouvement et d'autres principes mathmatiques pour traduire l'influence de ces diffrents facteurs sous forme d'quations. Le plus souvent, on obtient des quations diffrentielles ou aux drives partielles.

L'effort de modlisation produit en gnral des systmes d'quations com-plexes qui comprennent un grand nombre de variables inconnues. Pour rus-sir les rsoudre, il faut simplifier certaines composantes et ngliger les moins importantes. On fait alors une premire erreur de modlisation.

6 Chapitre 1

m

Figure 1.1: Problme du pendule

De plus, mme bien dcompos, un phnomne physique peut tre difficile mettre sous forme d'quations. On introduit alors un modle qui dcrit au mieux son influence, mais qui demeure une approximation de la ralit. On commet alors une deuxime erreur de modlisation. illustrons cette dmarche l'aide d'un exemple.

Exemple 1.4 Le problme du pendule est connu depuis trs longtemps (voir par exemple Simmons, rf. (20]). Une masse m est suspendue une corde de longueur l (voir la figure 1.1). Au temps t = 0, on suppose que l'angle 0(0) entre la corde et la verticale est 00 et que sa vitesse angulaire 0'(0) est 0~. Les forces en prsence sont la gravit agissant sur la masse et la corde, d'une part, et la friction de l'air agissant sur tout le systme, d'autre part.

Suivant la deuxime loi de Newton, la force due l'acclration tangen-tielle mlO"(t) est quilibre par la composante tangentielle de l'acclration gravitationnelle mg sin(O(t)) et par la force de friction Ff qui s'oppose au mouvement. On a alors:

mlO"(t) = -mgsin(O(t))- FJ

Analyse d'erreurs 7

Pour connatre comment se comporte la force de friction Ff en fonction de O(t), il faut recourir des mesures exprimentales, qui dmontrent que la friction est peu prs proportionnelle la vitesse ZO'(t) avec un coefficient de proportionnalit Cf. ll est important de remarquer que cette loi est ap-proximative et que le coefficient Cf est obtenu avec une prcision limite. Tout cela entrane des erreurs de modlisation.

On obtient une quation diffrentielle du second ordre:

O"(t) 0(0)

O'(O) Oo O' 0

c10'(t) gsin(O(t)) m l (1.4)

(1.5) (1.6)

L'quation diffrentielle 1.4 est non linaire et on dmontre qu'elle ne possde pas de solution analytique simple.

Une brve analyse montre qu'il est raisonnable de ngliger la friction de l'air, car les vitesses de mouvement sont faibles. ll s'agit encore d'une erreur de modlisation, qui parat acceptable cette tape de l'analyse. Si les rsultats s'avrent insatisfaisants, il faudra revenir en arrire et identifier, parmi les forces ngliges, celle qui tait la plus importante. Une analyse adimensionnelle est souvent ncessaire pour y arriver.

Mme en ngligeant la friction, ce qui revient poser Cf = 0, l'quation rsultante ne possde toujours pas de solution simple. En effet, sa rsolution fait intervenir les intgrales elliptiques (Simmons, rf. [20]) qui ne peuvent s'exprimer en fonctions lmentaires. Puisque tel est le but, on doit encore simplifier le problme. On peut par exemple supposer que les angles sont petits et que:

sin( 0( t)) ~ 0( t) n en rsulte le problme simplifi suivant:

O"(t) 0(0)

O'(O)

g O(t) ---

Oo O' 0

l

L'quation 1.7 possde la solution priodique classique:

O(t) = Acos(wt) + B sin(wt)

(1.7) (1.8) (1.9)

(1.10) o w2 = gjl et les constantes A et B sont dtermines par les conditions initiales (A= 00 , B = 0~/w).

8 Chapitre 1

0,10

0,08

0,06

e(tJ 0,04 0,02

0 .... -- --- ---

-0,02

-0,04

-0,06

-0,08

10 15 20 Temps (s)

Friction non nglige

0,10

0,08 (\ r 1\ /~ (\ 1\

9(t) 0,06 0,04

0,02

0 --- -- ...... ....

-0,02

-0,04

-0,06

-0,08

-0,10 v v v v

0 10 15 20 Temps (s)

Friction nglige

Figure 1.2: Deux solutions au problme du pendule

La figure 1.2 permet la comparaison entre les solutions des quations diffrentielles 1.4 et 1.7 dans le cas o 00 = 0,1 et 0~ = O. L'quation 1.10 est la solution analytique de l'quation diffrentielle 1.7, alors que l'quation diffrentielle 1.4 ne possde qu'une solution numrique (nous la reverrons au chapitre 7). On remarque immdiatement que la solution numrique (o la friction n'est pas nglige) prvoit l'amortissement du mouvement avec le temps, tandis que la solution analytique reste parfaitement priodique. La solution numrique est de toute vidence plus prs de ce que l'on observe pour un pendule.

Analyse d'erreurs 9

Remarque 1.2 Les erreurs de modlisation, quoique trs importantes, ne font pas partie de la matire de ce livre. Nous faisons l'hypothse que les problmes tudis sont bien modliss, bien que ce ne soit pas toujours le cas en pratique. 0

1.3 Reprsentation des nombres sur ordinateur Un ordinateur ne peut traiter les nombres de la mme manire que l'tre

humain. n doit d'abord les reprsenter dans un systme qui permette l'ex-cution efficace des diverses oprations. Cela peut entraner des erreurs de reprsentation sur ordinateur, qui sont invitables et dont il est souhaitable de comprendre l'origine afin de mieux en matriser les effets. Cette section prsente les principaux lments d'un modle de reprsentation des nombres sur ordinateur. Ce modle s'avre utile pour comprendre le fonctionnement type des ordinateurs; il ne peut bien entendu tenir compte des caractris-tiques sans cesse changeantes des ordinateurs modernes.

La structure interne de la plupart des ordinateurs s'appuie sur le systme binaire. L'unit d'information ou bit prend la valeur 0 ou 1. videmment, trs peu d'information peut tre accumule au moyen d'un seul bit. On regroupe alors les bits en mots de longueur variable (les longueurs de 8, de 16, de 32 ou de 64 bits sont les plus courantes). Les nombres, entiers et rels, sont reprsents de cette manire, bien que leur mode prcis de reprsentation dpende du fabricant.

1.3.1 Reprsentation des entiers signs

Nous traitons de trois formes parmi les plus courantes de reprsentation des entiers sur ordinateur. Plusieurs autres variantes existent, et il importe de connatre celle qui est utilise par l'ordinateur afin de pouvoir s'y retrouver.

Pour transformer un entier positif N dans sa reprsentation binaire habi-tuelle, il faut dterminer les ai tels que:

ou encore

10 Chapitre 1

11 1 11 1 1 1 1 1 111 1 11 1 111 1 1 olol

Figure 1.3: Reprsentation signe et grandeur sur 16 bits d'un entier

Dans ce qui prcde, le sous-indice indique la base utilise. On obtient la valeur des ai en suivant la dmarche suivante: en divisant N par 2, on obtient a0 (le reste de la division) plus un entier; on refait le mme raisonnement avec la partie entire de N /2 (en ngligeant la partie fractionnaire ou reste) pour obtenir a1 ; on continue ainsi jusqu' ce que la partie entire soit nulle.

Exemple 1.5 Si N = (1000)10, on a:

1000/2 500 reste 0 c.--d. ao = 0 500/2 250 reste 0 c.--d. a1 = 0 250/2 125 reste 0 c.--d. a2 = 0 125/2 62 reste 1 c.--d. a3 = 1 62/2 31 reste 0 c.--d. a4 = 0 31/2 15 reste 1 c.--d. a5 = 1 15/2 7 reste 1 c.--d. as= 1 7/2 3 reste 1 c.--d. a7 = 1 3/2 1 reste 1 c.--d. a8 = 1 1/2 0 reste 1 c.--d. lZ9 = 1

Ainsi, l'entier dcimal 1000 s'crit 111110 1000 en base 2 .

Voyons maintenant quelques variantes de reprsentation binaire des en-

tiers signs: la reprsentation signe et grandeur, la reprsentation en complment 2 et la reprsentation par excs. Ces variantes prsentent toutes un certain nombre d'avantages et d'inconvnients au regard de l'ex-cution des oprations arithmtiques lmentaires.

Reprsentation signe et grandeur

Pour illustrer la reprsentation signe et grandeur, il suffit de prendre un exemple. Considrons un mot de 16 bits tel qu'illustr la figure 1.3. Dans

Analyse d'erreurs

cette reprsentation, un bit (le premier) est consacr au signe: 0 pour un entier positif 1 pour un entier ngatif

11

Les autres bits peuvent alors servir la reprsentation de l'entier lui-mme. Ainsi:

01011100 1010 0100 =

+ ( 1 x 214 + 0 x 213 + 1 x 212 + ... + 1 x 22 + 0 x 21 + 0 x 2) est la reprsentation binaire du nombre dcimal 23 716. Le premier bit (0) indique un entier positif. Le plus grand entier reprsentable dans ce cas est bien sr 0111111111111111 qui reprsente 32 767, c'est--dire 215 - 1 en base 10. ll est remarquer que le nombre 0 peut tre reprsent de deux faons, savoir:

+0 = 0000 0000 0000 0000 -0 = 1000 0000 0000 0000

Un mot de 16 bits permet d'exprimer tous les entiers compris entre -32 767 et +32 767. Si un calcul sur des nombres entiers rsulte en un entier su-prieur 32 767, le compilateur enverra un message d'erreur indiquant un dbordement ( overftow). Remarque 1.3 Dans la reprsentation signe et grandeur et galement dans les reprsenta-tions qui suivent, nous utilisons la convention que le premier bit est celui situ le plus gauche. En informatique, on utilise plus souvent une numro-tation des bits allant de 0 jusqu' n- 1 en commenant par le bit le plus droite dit le moins significatif. D

Reprsentation en complment 2

La reprsentation en complment 2 est trs frquemment utilise. Si on dispose de n bits pour exprimer l'entier N, on pose:

ll faut remarquer le signe ngatif devant le terme an-l On constate facile-ment que tous les entiers positifs vrifient:

12 Chapitre 1

Les entiers positifs sont donc reprsents par 0 suivi de leur expression binaire habituelle en ( n -1) bits. Pour obtenir la reprsentation d'un nombre ngatif, il suffit de lui ajouter 2n-l et de transformer le rsultat en forme binaire.

Exemple 1.6 La reprsentation sur 4 bits de 0101 vaut:

soit 5 en forme dcimale. Par contre, 1101 vaut:

c'est--dire -8 + 5 = -3. Inversement, la reprsentation binaire de -6 sera 1 suivi de la reprsentation sur 3 bits de:

-6 + 23 = 2

qui est 010. On aura donc ( -6)10 = (1010)2 dans la reprsentation en com-plment 2.

Reprsentation par excs

illustrons la reprsentation par excs en prenant pour exemple un mot de 4 bits ( n = 4 ). On peut alors reprsenter au plus 24 (2n dans le cas gnral) entiers diffrents, y compris les entiers ngatifs. Si on veut exprimer un entier dcimal N, il suffit de lui ajouter un excs d et de donner le rsultat sous forme binaire. Inversement, si on a la reprsentation binaire par excs d'un entier, il suffit de calculer sa valeur en base 10 et de soustraire d pour obtenir l'entier recherch.

La reprsentation par excs a l'avantage d'ordonner la reprsentation binaire en assignant 0000 le plus petit entier dcimal reprsentable, savoir -d. En gnral, la valeur de d est 2n-l (23 sur 4 bits). Ainsi, avec 4 bits et d 23 , on obtient:

Analyse d'erreurs 13

Forme binaire Forme dcimale 0000 -8 0001 -7

1110 +6 1111 +7

Pour obtenir ce tableau, il suffit de remarquer que, par exemple, 1111 vaut 15 en dcimal, auquel on soustrait 23 pour obtenir 7.

Exemple 1.7 Soit un mot de 8 bits et un excs d = 27 = 128. Pour reprsenter ( -100)10, il suffit de lui ajouter 128, ce qui donne 28, et d'exprimer le rsultat sur 8 bits, soit 00011100.

Remarque 1.4 n existe d'autres reprsentations des entiers signs, comme la reprsentation en complment 1. Notre but n'tant pas d'en donner une liste exhaustive, nous nous limitons celles qui ont dj t prsentes. D

1.3.2 Reprsentation des nombres rels La tche de reprsentation est plus complexe dans le cas des nombres rels.

En effet, dans le systme dcimal, nous avons l'habitude de reprsenter un nombre x sous la forme:

x= mx 101

o m est la mantisse, l est l'exposant et 10 est la base. De faon gnrale, selon une base b quelconque, on peut crire:

La forme gnrale de la mantisse est la suivante:

14

ce qui signifie que:

m = d1 X b-1 + d2 X b-2 + d3 X b-3 + + dn X b-n

o n est le nombre de chiffres de la mantisse. Les di vrifient:

:S:(b-1) :S:(b-1) pour i=2,3,,n

Chapitre 1

(1.11) (1.12)

La premire ingalit signifie que la mantisse est normalise, c'est--dire que son premier chiffre est toujours diffrent de O. La normalisation permet d'assurer l'unicit de la reprsentation et d'viter les ambiguts entre:

0,1020 X 102 et 0,0102 x 103

pour reprsenter 10,2. La dernire expression n'est jamais retenue. Dans cet exemple, on a utilis la base b = 10 et n = 4 chiffres dans la mantisse. Ainsi, la mantisse satisfait toujours:

1 - < m < 1 b-

car la plus petite mantisse possible est 0,1000, qui vaut 1/b. Ces considrations servent de lignes directrices pour la reprsentation

d'un nombre rel sur ordinateur. Dans le cas qui nous intresse, la base sera gnralement 2 (b = 2). li faut donc trouver un moyen de reprsenter la mantisse (une fraction), l'exposant (un entier sign) et le signe de ce nombre. Remarque 1.5 Les calculatrices de poche se distinguent des ordinateurs principalement par le fait qu'elles utilisent la base 10 (b = 10) et une mantisse d'une longueur d'environ 10 ( n = 10). L'exposant l varie gnralement entre -100 et 100.0

Considrons titre d'exemple un mot de 8 bits tel que l'illustre la fi-gure 1.4. li est entendu qu'en pratique les mots sont beaucoup plus grands. Le premier bit donne le signe du nombre. Il reste donc 7 bits pour reprsen-ter la mantisse et l'exposant. On retient 3 bits pour l'exposant et les 4 bits suivants pour la mantisse. Il est noter que cette dernire est normalise et que son premier bit est toujours 1. Il faut ensuite dterminer quelle est la re-prsentation utilise pour l'exposant. Par exemple, si l'exposant est exprim suivant la reprsentation signe et grandeur, alors 01011011 se dcompose de la faon suivante:


0 1 0 1 1 0 1 1

1 1

+ 21 20 '

2-1 2-2 2-3 2-4

Exposant Mantisse

Figure 1.4: Reprsentation signe et grandeur sur 8 bits d'un rel

Exposant 101

Ce nombre est donc positif. L'exposant est ngatif et vaut:

et la mantisse est:

1 x T 1 + 0 x T 2 + 1 x T 3 + 1 x 2-4 = 0,6875

Ainsi, 0101 1011 reprsente le nombre dcimal:

0,6875 x 2-1 = 0,343 75

Par contre, si l'exposant est exprim suivant la reprsentation en compl-ment 2, la valeur binaire 101 qui reprsente l'exposant signifie alors -3 et (01011011)2 vaut 0,085 9375 en base 10.

Conversion d'une fraction dcimale en valeur binaire

La mthode de conversion d'une fraction dcimale en valeur binaire est similaire celle que l'on utilise dans le cas des entiers. Soit J, une fraction dcimale comprise entre 0 et 1. n faut donc trouver les di tels que:

ou encore

f = d1 x T 1 + d2 x T 2 + d3 x 2-3 + Si on multiplie f par 2, on obtient d1 plus une fraction. En appliquant

le mme raisonnement (2f- di), on obtient d2 On poursuit ainsi jusqu' ce que la partie fractionnaire soit nulle ou que l'on ait atteint le nombre maximal de chiffres de la mantisse.

16

Exemple 1.8 Si f = 0,0625, on a:

0,0625 x 2 0,1250 x 2 0,2500 x 2 0,5000 x 2

0,1250 c.--d. 0,2500 c.--d. 0,5000 c.--d. 1,0000 c.--d.

ce qui signifie que (0,0625)10 = (0,0001)2 .

Exemple 1.9 Si f = 1/3, on a:

1/3 x 2 2/3 x 2 1/3 x 2 2/3 x 2

0 + 2/3 c.--d. 1 + 1/3 c.--d. 0 + 2/3 c.--d. 1 + 1/3 c.--d.

dl= 0 d2 = 0 d3 = 0 d4 = 1

dl= 0 d2 = 1 d3 = 0 d4 = 1

On peut poursuivre la conversion l'infini et dmontrer que:

1 - = (0,010 101 .. )2 3

Chapitre 1

En pratique, puisqu'on n'utilise qu'un nombre fini de chiffres dans la man-tisse, il faudra s'arrter aprs n bits .

Norme IEEE

L'Institute for Electrical and Electronic Engineers (IEEE) s'efforce de rendre aussi uniformes que possible les reprsentations sur ordinateur. ll propose une reprsentation des nombres rels en simple prcision sur 32 bits et en double prcision sur 64 bits (convention IEEE-754 ). Les reprsentations


en simple et double prcision sont construites comme suit. Le premier bit tmoigne du signe du nombre, les 8 bits suivants (11 en double prcision) dterminent l'exposant avec un excs de 127 ou 28- 1 - 1 (1023 ou 211- 1 - 1 en double prcision) et les 23 derniers bits (52 en double prcision) sont pour la mantisse normalise. Puisque l'on normalise la mantisse, le premier bit est toujours 1 et il n'est pas ncessaire de le garder en mmoire. La mantisse normalise peut donc commencer par un 0 tout en conservant la mme prcision qu'avec 24 bits (53 en double prcision).

Ainsi, suivant la notation de Cheney et Kincaid (rf. [5]), les 32 bits de la reprsentation en simple prcision IEEE:

dsignent le nombre dcimal:

(-1)d1 x 2(d2 d3 d9 )2 x 2-127 x (1,d10d11d32h

On remarque immdiatement les diffrentes composantes: le bit de signe, l'exposant avec un excs de 127 et la mantisse normalise par l'ajout du 1 manquant.

Remarque 1.6 La norme IEEE traite le nombre rel 0 de faon particulire. D

Exemple 1.10 Les 32 bits suivants (en simple prcision IEEE):

1100 00011110 0000 0000 0000 0000 0000

se dcomposent en:

( -1)1 x 2(10000011)2 x 2-127 x (1,11)2

-16 x 1,75 = -28

On obtient la reprsentation du nombre dcimal (30,0625)10 en simple pr-cision au moyen de l'opration inverse. Tout d'abord, la partie entire (30)10

18 Chapitre 1

devient (11110)2 en forme binaire et la partie fractionnaire (0,0625)10 est tout simplement (0,0001)2. Ainsi, on a:

(30,0625)10 = (11110,0001)2 = 1,111000 01 x 24

Dans la dernire expression, la mantisse est normalise et le bit 1 la gauche de la virgule n'est pas conserv en mmoire. L'exposant 4 est dcal de 127 pour devenir 131. La reprsentation de 131 sur 8 bits est (1000 0011)2. Puisque le nombre (30,0625)10 est positif, sa reprsentation en simple prci-sion IEEE sera:

0 1000 0011 1110 00010000 0000 0000 000

1.4 Erreurs dues la reprsentation Le fait d'utiliser un nombre limit de bits pour reprsenter un nombre

rel a des consquences importantes sur la propagation des erreurs. On peut par exemple rechercher quel est le plus petit nombre positif reprsentable sur 8 bits (voir la figure 1.4 ). En choisissant la reprsentation signe et grandeur pour l'exposant, on constate que le nombre doit tre positif (0), que son exposant doit tre ngatif (1), que sa valeur doit tre la plus petite possible compte tenu du signe (11) et, enfin, que la mantisse doit tre la plus petite possible compte tenu de la normalisation (1000). On obtient:

qui vaut 0,0625. Consquemment, on ne peut pas reprsenter tout nombre rel positif plus petit que 0,0625 dans ce systme 8 bits. Un calcul rsultant en un nombre plus petit que 0,0625 donnerait lieu un sous-dpassement ( underflow).

On peut se demander quel serait le nombre suivant. Il s'agit bien sr de 01111001, dont la valeur dcimale est 0,070 3125. Il n'est donc pas possible de reprsenter exactement sur 8 bits les nombres entre 0,0625 et 0,070 3125. Si on cherche par exemple reprsenter le nombre rel 0,07, l'ordinateur choisira soit 01111000 (c'est--dire (0,0625)10), soit 01111001 (c'est--dire (0,070 3125)10) Le choix dpend de l'utilisation de la troncature ( chopping), qui consiste choisir systmatiquement la borne infrieure, ou de l'arrondi


( rounding), qui consiste choisir la borne infrieure seulement si le nombre que l'on souhaite reprsenter est plus petit que:

0,0625 + 0,070 3125 2

Par ailleurs, le plus grand nombre reprsentable sur 8 bits est 0011 1111, qui vaut 7,5. Tout calcul rsultant en un nombre plus grand que 7,5 donnerait lieu un dbordement.

Cet exemple sur 8 bits exagre grandement les effets de la reprsenta-tion des nombres rels sur ordinateur. Personne ne songe faire des calculs numriques avec seulement 8 bits. Si on travaille avec plus de bits, le plus petit nombre reprsentable devient de plus en plus petit et l'cart entre les nombres reprsentables diminue galement. Les conclusions qui suivent restent cependant vraies.

Quel que soit le nombre de bits utiliss, il existe un plus petit et un plus grand nombre positifs reprsentables (de mme pour les nombres ngatifs). TI existe donc un intervalle fini l'extrieur duquel on se heurte invitablement un dbordement ou un sous-dpassement.

l'intrieur de cet intervalle fini, seulement un nombre fini de nombres sont reprsentables exactement, et on doit recourir la troncature ou l'arrondi pour reprsenter les autres rels.

La reprsentation en point flottant induit une erreur relative qui d-pend du nombre de bits de la mantisse, de l'utilisation de la troncature ou de l'arrondi ainsi que du nombre x que l'on veut reprsenter. En effet, nous avons vu l'importance sur la prcision du nombre de bits de la mantisse et nous avons galement constat qu'un nombre fini seulement de rels peuvent tre reprsents exactement. L'intervalle entre les nombres reprsentables varie en longueur selon l'exposant devant la mantisse.

Dfinition 1.4 La prcision machine E est la plus grande erreur relative que l'on puisse commettre en reprsentant un nombre rel sur ordinateur en utilisant la troncature.

20 Chapitre 1

Remarque 1.7 La prcision machine dpend bien sr de l'appareil utilis et du nombre de bits de la mantisse. De plus, si on utilise l'arrondi, la prcision machine est tout simplement E/2.0

Thorme 1.1 La prcision machine vrifie:

(1.13) o b est la base utilise et n le nombre de bits de la mantisse.

Dmonstration: Soit x, un nombre quelconque. Sa reprsentation exacte en base b est donc de la forme:

ce qui entrane que l'erreur absolue commise par troncature est:

< O,(b- 1)(b- 1)(b- 1) X bl-n en vertu de l'quation 1.12. L'erreur relative satisfait donc:

Er(x) = l~xl lxi <

<

<

O,(b- 1)(b- 1)(b- 1) X bl-n O,d1 d2d3 dndn+l dn+2 X b1

O,(b-1)(b-1)(b-1) X bl-n 0,100 000 ... x bl

On note alors que b1-n est une borne suprieure pour la prcision machine. Dans ce qui suit, on ne fera plus la distinction entre la prcision machine E et sa borne suprieure b1-n, bien que ces deux quantits soient lgrement diffrentes. 0


n est facile de montrer que cette borne est presque atteinte pour tous les nombres x de dveloppement en base b de la forme:

x = 0,100 000 O(b- 1)(b- 1) .x b1 (1.14)

c'est--dire dont le 1 est suivi de ( n - 1) zros et ensuite d'une infinit de chiffres valant (b-1). L'erreur relative est alors:

O,(b- 1)(b- 1) X b1-n Er(x) = 1 0,100 000 O(b- 1)(b- 1) x b

qui est trs prs de b1-n.

Exemple 1.11 Suivant la norme IEEE, la mantisse d'un rel contient 23 bits en simple prcision (52 bits en double prcision), mais avec une prcision de 24 bits (53 en double prcision) puisque, aprs la normalisation, le premier 1 n'est pas gard en mmoire. La prcision machine vaut alors:

21 - 24 = 0,119 x 10-6

en simple prcision et 21- 53 = 0,222 x 10-15

en double prcision.

Ce rsultat peut tre vrifi directement sur ordinateur au moyen de l'al-

gorithme qui suit (voir Chapra et Canale, rf. [4]). Cet algorithme permet de construire une suite de nombres de forme similaire celle de l'quation 1.14.

Algorithme 1.1: Prcision machine

1. E = 1

2. Lorsque 1 + E > 1, effectuer E = t:/2

3. E = 2 x E et arrt

4. Prcision machine = E D

22 Chapitre 1

Dans l'algorithme prcdent, le nombre (1 + E) prend successivement les valeurs suivantes:

Forme dcimale Forme binaire 2 0,1 x 2-.: 1,5 0,11 x 21 1,25 0,101 x 21 1,125 0,1001 x 21 1,0625 0,100 01 x 21

Cette suite continue jusqu' ce que le nombre de zros intercals dans la reprsentation binaire soit trop grand et dpasse la longueur de la mantisse. On aura alors 1 + E = 1 et l'algorithme s'arrtera. TI est noter que la reprsentation binaire de 1 + E est de forme similaire celle de la relation 1.14. Sur un IBM RISC 6000, la concordance entre le rsultat de cet algorithme et l'quation 1.13 est parfaite.

Terminons cette section par deux exemples illustrant les effets parfois tonnants de la reprsentation binaire.

Exemple 1.12 Si on convertit la fraction dcimale 0,1 en sa valeur binaire, on a:

0,1 x 2 0,2 c.--d. dl= 0 0,2 x 2 0,4 c.--d. d2 = 0 0,4 x 2 0,8 c.--d. d3 = 0 0,8 x 2 1,6 c.--d. d4 1 0,6 x 2 1,2 c.--d. d5 = 1 0,2 x 2 0,4 c.--d. d6 = 0

ou encore

(0,1)10 = (0,00011001100)2 Ainsi, une fraction ayant un dveloppement dcimal fini peut avoir un dve-loppement binaire illimit.


Lorsqu'on utilise un nombre fini de bits dans la mantisse pour reprsenter (0,1)10, l'importance de l'erreur commise dpend du nombre de bits utiliss.

Exemple 1.13 Le problme consiste sommer 10 000 fois le nombre (1,0)10 , qui possde un dveloppement binaire fini, et le nombre (0,1)10, qui n'a pas de reprsentation exacte sur un nombre fini de bits. On obtient, sur un IBM RISC 6000, les rsultats suivants:

10 000,000 00 et 999,902 8931

en simple prcision et:

10 000,000 000 000 0000 et 1000,000 014 90116119

en double prcision. Cela dmontre l'effet des erreurs de reprsentation sur ordinateur. Des oprations en apparence identiques donnent, dans un cas, un rsultat exact et, dans l'autre, un rsultat erron dont la prcision augmente avec le nombre de bits de la mantisse .

1.5 Arithmtique flottante Les erreurs ont tendance se propager et quelques fois s'amplifier au fil

des calculs. Dans cette section, nous suivons l'volution des erreurs au fil des oprations lmentaires. Afin de simplifier l'expos, nous utilisons le systme dcimal, mais les effets dcrits valent galement pour les autres bases.

Tout nombre rel x s'crit sous la forme:

Dfinition 1.5 Soit x, un nombre rel. On note fi( x) sa reprsentation en notation flot-tante n chiffres dfinie par:

24 Chapitre 1

Remarque 1.8 La notation flottante d'un nombre dpend du nombre n de chiffres dans la mantisse, mais aussi du procd retenu pour liminer les derniers chiffres. Ainsi, la troncature consiste retrancher les chiffres partir de la position n + 1. Avec l'arrondi, on ajoute 5 au ( n + 1 )e chiffre de la mantisse avant d'effectuer la troncature. La troncature est dite biaise, car on a toujours, pour des nombres positifs, fi( x) ~ x. Par contre, l'arrondi est non biais, car on a tour tour x ~ fl(x) ou x 2:: fl(x). Nous utilisons l'arrondi dans les exemples qui suivent. 0

Remarque 1.9 La norme IEEE recommande l'utilisation de l'arrondi dans la reprsentation binaire des nombres rels. 0

Exemple 1.14 Si on choisit n = 4, alors on a:

fl(1/3) fl(7r) fl(12,4551)

0,3333 x 10 0,3142 x 101 0,1246 x 102

1.5.1 Oprations lmentaires

Les oprations lmentaires sont l'addition, la soustraction, la multiplica-tion et la division. Soit x et y, deux nombres rels. On effectue ces oprations en arithmtique flottante de la faon suivante:

x+y x y x-7-y xx y

--+

--+

--+

--+

fl(fl(x) + fl(y)) fi( fi( x) - fl(y)) fl(fl( x) -7- fl(y)) fi( fi( x) x fl(y))


En un mot, on doit d'abord reprsenter les deux oprandes en notation flottante, effectuer l'opration de la faon habituelle et exprimer le rsultat en notation flottante.

Exemple 1.15 Si on prend n = 4, alors on a:

1/3 x 3 --+ fl(fl(1/3) x fl(3)) fl((0,3333 x 10) x (0,3000 x 101 )) fl(0,099 990 00 x 101 ) 0,9999 x 10

On remarque une lgre perte de prcision par rapport la valeur exacte de cette opration qui est 1.

La multiplication et la division sont particulirement simples en arith-

mtique flottante cause de la loi des exposants.

Exemple 1.16 Toujours avec n = 4, eff-ectuer les oprations suivantes:

a) (0,4035 x 106 ) x (0,1978 x 10-1 )

fl(0,4035 x 106 x 0,1978 x 10-1 ) fl(0,079 8123 x 105) fl(0,798123 x 104 ) 0,7981 x 104

b) (0,567 89 x 104 ) 7 (0,123 4321 x 10-3 )

fl(0,5679 x 104 7 0,1234 x 10-3 ) fi( 4,602106 969 x 107 ) fl(0,460 210 6969 x 108 ) 0,4602 x 108

26 Chapitre 1

Par contre, il faut tre plus prudent avec l'addition et la soustraction. On ajoute d'abord des zros la mantisse du nombre ayant le plus petit exposant de telle sorte que les deux exposants soient gaux. On effectue ensuite l'opration habituelle et on met le rsultat en notation flottante.

Exemple 1.17 Toujours avec n = 4, effectuer les oprations suivantes:

a) (0,4035 x 106 ) + (0,1978 x 104 ) fl(0,4035 x 106 + 0,1978 x 104 ) fl(0,4035 x 106 + 0,001 978 x 106 ) fl(0,405 4 78 x 106 ) 0,4055 x 106

b) (0,567 89 x 104)- (0,123 4321 x 106 )

fl(0,5679 x 104 - 0,1234 x 106) fl(0,005 679 x 106 - 0,1234 x 106 ) -fl(O,l17 72 x 106 ) -0,1177 x 106

On constate qu'il est primordial de dcaler la mantisse avant d'effectuer l'addition ou la soustraction.

Remarque 1.10 TI faut bien remarquer que des oprations mathmatiquement quivalentes ne le sont pas forcment en arithmtique flottante. L'ordre des oprations est trs important. En voici un exemple. 0

Exemple 1.18 La proprit de distributivit de la multiplication sur l'addition n'est pas tou-jours respecte en arithmtique flottante. En effet, en arithmtique exacte:

122 x (333 + 695) = (122 x 333) + (122 x 695) = 125 416

Analyse d'erreurs

En arithmtique flottante avec n = 3, on obtient d'une part:

122 x (333 + 695)

et d'autre part:

fi[(0,122 x 103 ) x fi(0,333 x 103 + 0,695 x 103 )] fi[(0,122 x 103 ) x fi(1,028 x 103 )] fi[(0,122 x 103 ) x (0,103 x 104 )] fi(0,012 566 x 107 ) 0,126 x 106

(122 x 333) + (122 x 695) fl[fl((0,122 x 103 ) x (0,333 x 103 ))

27

+ fi((0,122 x 103 ) x (0,695 x 103 ))] fi[fi(0,040 626 x 106 ) + fi(0,084 79 x 106)] fi[(0,406 x 105 ) + (0,848 x 105 )] fi(1,254 x 105 ) 0,125 x 106

On constate donc une lgre diffrence entre les deux rsultats, ce qui indique que les deux faons d'effectuer les oprations ne sont pas quivalentes en arithmtique flottante.

1.5.2 Oprations risques

Un certain nombre de calculs sont particulirement sensibles aux erreurs d'arrondi. Nous prsentons quelques exemples d'oprations viter.

Exemple 1.19 Additionner deux nombres dont les ordres de grandeur sont trs diffrents:

(0,4000 x 104 ) + (0,1000 x 10-2 ) fi(0,4000 x 104 + 0,1000 x 10-2 ) fi(0,4000 x 104 + 0,000 0001 x 104 ) fi(0,400 0001 x 104 ) 0,4000 x 104

La loi des exposants et l'arrondi font en sorte que le petit nombre disparat compltement devant le plus grand. Ce comportement est encore plus en vidence dans l'exemple suivant .

28 Chapitre 1

Exemple 1.20 Calculer une somme de termes positifs:

n 1 Sn=1+L~+.

i=l z z

On peut valuer analytiquement cette srie en utilisant les fractions par-tielles. En effet:

n 1 Sn = 1 + L -.2-.

i=l z + z n (1 1 ) 1+2:: -:---.-

i=l z z + 1

1 1 1 1 1 1 + (1--) + (---) + ... + (-- -) 2 2 3 n n+1 1 2---

n+1 On peut calculer cette somme tout d'abord directement:

1 1 1 St n = 1 + - + - + + --

' 2 6 n 2 + n

et ensuite rebours: 1 1 1 s2 n = + ... + - + - + 1

' n 2 + n 6 2

Les rsultats calculs sur IBM RISC 6000 sont rsums dans le tableau ci-dessous pour diffrentes valeurs de n.

n sl n S2,n Valeur exacte de Sn 99 1,989 999 890 1,990 000 010 1,99

999 1,999 001026 1,999 000 072 1,999 9999 1,999 791 980 1,999 899 983 1,9999

On remarque que S2,n est plus prcis que St,n Cela est d au fait que lors-qu'on somme S1 non accumule dans S1 n les sommes intermdiaires. Cons-

' ' quemment, St,n devient de plus en plus grand par rapport P~i et on finit


par additionner un trs grand et un trs petit nombre (ce type d'opration est viter). Inversement, lorsqu'on somme S2,m les sommes intermdiaires augmentent, mais les termes qui s'ajoutent au fil de la sommation croissent galement et le phnomne prcdent ne se produit pas .

Exemple 1.21 Soustraire deux nombres presque identiques:

(0,5678 x 106)- (0,5677 x 106 )

fi(0,5678 x 106 - 0,5677 x 106 ) fl(0,0001 x 106 ) 0,1000 x 103

La soustraction de ces 2 nombres de valeur trs proche fait apparatre trois 0 non significatifs dans la mantisse du rsultat. On appelle ce phnomne l'limination par soustraction des chiffres significatifs. L'exemple suivant en illustre les consquences possibles .

Exemple 1.22 (Chapra et Canale, rf. [4]) Calculer les racines de:

ax2 + bx + c

qui sont bien sr:

-b + y'b2 - 4ac -b - v'b2 - 4ac r1 = et r2 = ------2a 2a

On considre le cas o a = 1, b = 3000,001 et c = 3. Les racines exactes sont r 1 = -0,001 et r 2 = -3000. Un calcul en simple prcision (norme IEEE) donne r 1 = -0,000 988 28133 et r 2 = -3000,0000, dont l'erreur relative est respectivement de 1,17% et de 0,0 %. Le calcul de r 2 ne pose aucune difficult particulire. L'erreur relative lie r 1 provient de l'addition de ( -b ), qui vaut -3000,000 977, et de v'b2 - 4ac, qui vaut 2999,999 023. Cette

30 Chapitre 1

opration revient soustraire des nombres trs voisins. Pour viter cela, on peut multiplier r1 par son conjugu et calculer:

r1

= ( -b + y'b2- 4ac) ( -b- y'b2 - 4ac) 2a -b - y'b2 - 4ac

-2c b+ v'b2 - 4ac

On obtient de cette manire:

r1 = -0,001000000047

et une erreur relative extrmement faible .

Exemple 1.23 valuer une srie de nombres de signes alterns (Chapra et Canale, rf [4]).

Nous verrons un peu plus loin que le dveloppement de Taylor de la fonction e-x autour de 0 est:

(1.15)

On remarque que les termes de la srie changent constamment de signe. Dans l'expression 1.15, Sn dsigne la somme des ( n + 1) premiers termes de la srie. Le tableau ci-dessous prsente quelques rsultats intermdiaires obtenus lors de l'valuation de e-10 , qui consiste poser tout simplement x = 10 dans l'quation 1.15.


n xnjn! Somme partielle Sn 0 + 1,000 000 00 +1,000 000 000 1 -10,000 0000 -9,000 000 000 2 +50,000 0000 +41 ,000 000 00 3 -166,666 718 -125,666 6718 4 +416,666 687 +291,000 0000 5 -833,333 374 -542,333 37 40 10 +2755,73217 +1342,587 402 20 +41,103 1875 +13,396 75140 30 +0,376 998 9125 x 10-2 +0,852 284 9530 x 10-3 31 -0,121612 5558 x 10-2 -0,363 840 6051 x 10-3 32 +0,380 039 2442 x 10-3 +0,161986 3906 x 10-4 33 -0,115 163 4060 x 10-3 -0,989 647 6690 x 10-4 34 +0,338 715 9086 x 10-4 -0,650 931 7609 x 10-4 35 -0,967 759 7518 x 10-5 -0,747 707 7452 x 10-4 40 +0,122 5618007 x 10-7 -0,726 567 8660 x 10-4 41 -0,298 931 2131 x 10-8 -0,726 576 6908 x 10-4 42 +0,7117409990x 10-9 -0,726 569 5604 x 10-4 43 -0,165 5211662 x 10-9 -0,726 5712338 x 10-4 44 +0,376 184 4655 x 10-lO -0,726 570 8700 x 10-4 45 -0,835 965 4982 x 10-11 -0,726 570 9428 x 10-4

Voil un exemple parfait de calcul instable. On remarque immdiate-ment que le rsultat final est faux, car on obtient une valeur ngative pour l'exponentielle dont la valeur exacte est 0,453 9993 x 10-4 On voit aussi qu'il est inutile de continuer pour des valeurs de n plus grandes que 45, car la valeur de xn / n! est trop petite pour modifier substantiellement le rsul-tat. Cela revient additionner un trs grand et un trs petit nombre. On constate enfin que le phnomne d'limination par soustraction des chiffres significatifs se produit de faon systmatique en raison de l'alternance des signes.

On peut contourner ces difficults en valuant la srie de manire diff-rente. Une possibilit consiste utiliser l'algorithme de Horner pour l'va-luation des polynmes.

1.5.3 valuation des polynmes n est trs frquent d'avoir valuer des polynmes de degr lev en

analyse numrique. n est donc important de pouvoir les valuer rapidement et de la faon la plus stable possible du point de vue de l'arithmtique flottante. C'est ce que permet l'algorithme de Horner appel aussi algorithme de multiplication imbrique. Pour valuer un polynme de la forme:

en un point x quelconque, il suffit de regrouper judicieusement les termes de la faon suivante:

p(x) = ao +x( al+ x(a2 + x(a3 + + x(an-l + anx) )))

Voyons l'valuation d'un polynme l'exemple suivant.

Exemple 1.24 Soit le polynme:

p( x) = 2 + 4x + 5x2 + 3x3

(1.16)

qui ncessite 6 multiplications et 3 additions. En suivant le mode de regrou-pement de l'quation 1.16, on obtient:

p(x) = 2 + x(4 + x(5 + 3x))

qui ncessite seulement 3 multiplications et 3 additions (et aucune lvation de puissance). On rduit donc substantiellement le nombre d'oprations n-cessaires et, de plus, cette nouvelle expression est moins sensible aux effets de l'arithmtique flottante.

La mthode de Horner est facile programmer grce l'algorithme sui-

vant.

Algorithme 1.2: Mthode de Horner

1. tant donn les coefficients ai d'un polynme de degr n 2. tant donn une abscisse x


3. tant donn la variable Pn qui contiendra la valeur du polynme en x 4. Pn =an

5. Pour i = n, n- 1, n- 2, , 2, 1:

Pn =ai-l+ PnX

6. crire x, p(x) = Pn D

Exemple 1.25 La mthode de Horner peut servir reprendre le calcul e-10 par la srie alterne 1.15. Les coefficients du polynme sont:

( -1)i a;=-.-,-

z.

Pour le polynme de degr n = 45, on obtient la valeur approximative 0,453 999 X 10-4 , qui est trs prs de la valeur exacte et qui ne change plus pour les valeurs suivantes de n .

1.6 Erreurs de troncature

Les erreurs de troncature constituent la principale catgorie d'erreurs. Tout au long de ce manuel, nous abordons des mthodes de rsolution qui comportent des erreurs de troncature plus ou moins importantes. L'ordre d'une mthode dpend du nombre de termes utiliss dans les dveloppements de Taylor appropris. li est donc essentiel de revoir en dtaille dveloppe-ment de Taylor, car il constitue l'outil fondamental de l'analyse numrique.

Remarque 1.11 li est important de ne pas confondre les erreurs de troncature traites dans cette section et la troncature utilise pour la reprsentation des nombres sur ordinateur. D

34

\ \

' ' ' '

xo

f(x) P2(x) P1(x) P0(x)

1 1

1 1

1

1

1 1

1

1 1

1

1 1

1 1

1

Chapitre 1

Figure 1.5: Approximation de f( x) au voisinage de xo

1.6.1 Dveloppement de Taylor en une variable

li existe plusieurs faons d'introduire le dveloppement de Taylor. Une faon trs simple consiste le prsenter formellement comme un problme d'approximation au voisinage d'un point x0 On se demande alors quel est le polynme de degr 0 (not Po( x)) qui donne la meilleure approximation d'une fonction f(x) donne dans le voisinage du point xo.

Selon la figure 1.5, ce polynme est:

Po( x)= f(xo)

On peut pousser plus loin l'analyse et chercher le meilleur polynme de degr 1 de la forme:

Pt(x) = ao + at(x- xo) ( 1.17) On pourrait tout aussi bien chercher un polynme de forme plus classique:

Ces deux expressions sont quivalentes et aboutissent au mme rsultat. La forme 1.17 est plus pratique et plus naturelle puisqu'elle s'articule autour du point xo.

On doit introduire deux conditions pour dterminer les deux constantes. Intuitivement, la meilleure droite (polynme de degr 1) est celle qui passe


par ( xo, f( xo)) et dont la pente est celle de la fonction f( x) en x0 , ce qui entrane que:

ou encore

f(xo) !'(xo)

ao f(xo) a1 !'(xo)

li en rsulte l'expression suivante:

P1(x) = f(xo) + f'(xo) (x- xo)

(1.18) (1.19)

On peut bien sr poursuivre ce raisonnement condition que la fonction f( x) soit suffisamment drivable. Dans le cas d'un polynme de degr 2, on imposerait:

pour obtenir facilement:

P2(xo) ~(xo) ~'(xo)

f(xo) J'( xo) !"(xo)

J"(x ) (x x )2 P2(x)=f(xo)+f'(xo)(x-xo)+ 0 2

-

0

(1.20) (1.21) (1.22)

En poursuivant ce raisonnement jusqu' l'ordre n, c'est--dire en imposant l'galit des drives jusqu' l'ordre n, on obtient le polynme de Taylor de degr n de la fonction f( x) autour de x0

Dfinition 1.6 Le polynme de Taylor de degr n de la fonction f( x) autour de xo est dfini par:

Pn(x) f(xo) + f'(xo) (x- xo) + f"(xo) ~~- xo) 2 (1.23)

f"'(xo) (x- xo? f(n)(xo) (x- xo)n + 3! + .. + ----'-----'--n...:.!----'--

o f(n)(xo) dsigne la drive d'ordre n de f(x) en xo.

36 Chapitre 1

Ce polynme donne une approximation de la fonction f( x) au voisinage de x 0 li n'y a cependant pas galit en ce sens que si on utilise l'quation 1.23 pour estimer f( x) on commettra une erreur. Remarque 1.12 On choisit gnralement le point x 0 o on dveloppe le polynme de Taylor de faon ce que l'on puisse facilement valuer la fonction f( x) ainsi que ses drives. 0

Le rsultat suivant quantifie l'erreur commise lorsqu'on utilise le poly-nme de Taylor (Thomas et Finney, rf. [22]).

Thorme 1.2 Soit f( x), une fonction dont les drives jusqu ' l'ordre ( n + 1) existent au voisinage du point x 0 On a l'galit suivante:

f(x) = Pn(x) + Rn(x) (1.24) o Pn(x) est le polynme de Taylor 1.23 et Rn(x) est l'erreur commise, qui est donne par:

f(n+l)((x)) (x- xo)(n+l) Rn( x)= (n + 1)! (1.25)

pour un certain (x) compris entre x0 et x. 0

Remarque 1.13

1. L'quation 1.24 est une galit et ne devient une approximation que lorsque le terme d'erreur est nglig.

2. Le terme d'erreur de l'quation 1.25 devient de plus en plus grand lorsque x s'loigne de xo en vertu du terme (x - x0 )(n+I) (voir la figure 1.5).

3. Inversement, pour une valeur de x prs de x 0 , le terme d'erreur de l'quation 1.25 est de plus en plus petit lorsque n augmente.

4. On sait que le point ( x) existe et qu'il varie avec x, mais on ne connat pas sa valeur exacte. li n'est donc pas possible d'valuer le terme d'erreur exactement. On peut tout au plus lui trouver une borne su-prieure dans la plupart des cas.


5. On commet une erreur de troncature chaque fois que l'on utilise le dveloppement de Taylor et que l'on nglige le terme d'erreur de l'qua-tion 1.25. 0

Un cas particulier important du thorme prcdent est le premier tho-rme de la moyenne, qui quivaut poser n = 0 dans le dveloppement de Taylor.

Corollaire 1.1 Soit f(x), une fonction drivable dans l'intervalle [xo, x]. Alors il existe dans [x0 ,x] tel que:

f(x) = f(xo) + J'()(x- xo) qui s'crit galement sous la forme:

f(x)- f(xo) = J'()(x- xo) 0 (1.26)

On cre une forme plus pratique du dveloppement de Taylor en remplaant x par x0 + h ou encore l'expression x - x0 par h. On obtient ainsi:

f(xo + h) = Pn(h) + Rn(h) (1.27) o

f(xo) + f'(xo) h + !"(~~) h2 (1.28)

et j(n+l)((h)) h(n+l) Rn(h) = (n + 1)! (1.29)

pour (h) compris entre xo et x0 + h.

Exemple 1.26 On considre la fonction f( x) = ex au voisinage de x0 = O. Puisque toutes les drives de ex sont gales ex et valent 1 en x 0 = 0, le dveloppement

38 Chapitre 1

de Taylor de degr n devient:

h2 h3 hn exo+h =eh~ P, (h) = 1 + h +-+- + ... +-

n 2! 3! n! et l'expression du terme d'erreur de l'quation 1.29 est:

e(h) hn+l Rn(h) = (n + 1)!

o (h) E [0, h]. On peut mme dterminer une borne suprieure pour le terme d'erreur. La fonction exponentielle tant croissante, on a:

dans l'intervalle [0, h] et on conclut que: ehhn+l

Rn ( h) ~ ( n + 1)! (1.30) On peut utiliser ce dveloppement pour estimer la valeur de e0 ' 1 en pre-

nant h = 0,1.

n Pn(0,1) Erreur absolue Nombre de chiffres Borne pour le significatifs terme d'erreur

0 1,000 0000 0,105 X lQU 1 0,111 x 10 1 1,100 0000 0,517 x 10-2 2 0,552 x 10-2 2 1,105 0000 0,171 x 10-3 4 0 184 x 10-3

' 3 1,1051667 0,420 x 10-5 6 0,460 x 10-5

On obtient l'erreur absolue simplement en comparant le rsultat avec la valeur exacte 1,105 170 918, tandis que la borne suprieure de l'erreur pro-vient de l'quation 1.30 avec h = 0,1. Enfin, si on prend h = 0,05 et n = 3 pour estimer e0 ,05 , on obtient:

P3(0,05) = 1,051 270 833 et une erreur absolue d'environ 0,263 x 10-6 . On remarque de plus que le rapport des erreurs absolues lies P3 ( h) est:

IP3(0,1)- e0 ' 1 1 IP3(0,05)- eo,o51

0,4245 x 10-5 = 16 14 0,263 x 10-6 '


La valeur de ce rapport n'est pas fortuite. La dfinition suivante permet de comprendre d'o provient cette valeur (Bourdeau et Glinas, rf. [1]) .

Dfinition 1. 7 Une fonction f(h) est un grand ordre dehn au voisinage de 0 (not f(x) = O(hn)) s'il existe une constante positive C telle que:

au voisinage de O.

Bien qu'imprcise, cette dfinition exprime assez bien les caractristiques d'une fonction de type O(hn). Lorsque h est assez petit, la fonction O(hn) dcrot comme Chn. Plus n est grand, plus la dcroissance est rapide. Ainsi, une fonction O(h3 ) dcrot plus vite qu'une fonction O(h2), qui elle-mme dcrot plus vite qu'une fonction 0( h ). Pour avoir une ide du comportement d'une fonction de type 0( hn ), il suffit de remarquer que, lorsque h est divis par 2, la fonction 0( hn) diminue selon un facteur approximatif de 2n. En effet, si on remplace h par h/2 dans Chn, on obtient:

Remarque 1.14 Le terme d'erreur du polynme de Taylor de degr n est gnralement de type O(hn+l ). Cela explique le rapport de 16,14 obtenu dans l'exemple prcdent. En effet, on y trouve un polynme de Taylor de degr 3 dont le terme d'erreur est de type O(h4 ). En passant de h = 0,1 h = 0,05, on divise h par un facteur de 2, d'o une diminution selon un facteur de 24 = 16 de l'erreur. Bien sr, le facteur de 16 est approximatif et n'est atteint qu' des valeurs de h trs petites. Dans le cas gnral, on note:

40 Chapitre 1

Dfinition 1.8 Une approximation dont le terme d'erreur est un grand ordre de hn (O(hn)) est dite d'ordre n.

Remarque 1.15 Suivant cette dfinition, le polynme de Taylor de degr n est gnralement (mais pas toujours) une approximation d'ordre ( n + 1) de f( x). Par exemple, le dveloppement de Taylor de degr n de ex autour de x = 0 est d'ordre (n+1).D

Remarque 1.16 Dans certains manuels, il y a confusion entre le degr et l'ordre du polynme de Taylor. ll faut s'assurer de bien distinguer ces deux notions. o

Exemple 1.27 Calculer le dveloppement de Taylor d'ordre 5 de la fonction sin x autour de xo = O. Les drives de la fonction sont respectivement:

f(x) sin x, f(O) 0 !'(x) cos x, f'(O) 1 !"(x) -sin x, J"(O) 0 !"'(x) -cos x, f"'(O) -1 !""(x) sin x, f""(O) 0 !""'(x) cos x

Le dveloppement de Taylor est donc:

. ( h) . (h) h h3 cos((h))h5 sm x0 + = sm = - 1 + 1 3. 5.


il suffit de calculer le polynme de Taylor de degr 3 (P3(h)) pour obtenir une approximation d'ordre 5 de la fonction sin h. Puisque la fonction cos x est borne en valeur absolue par 1, on note immdiatement que:

Si on prend maintenant h = 0,1, on peut obtenir l'approximation:

. (0,1? sm(0,1) ~ 0,1-----:31 = 0,099833333

soit une erreur absolue de 0,8332 x 10-7 . il est noter que la borne suprieure de l'erreur vaut 0,8333 x 10-7 , ce qui est trs prs de la valeur exacte. Si on prend h = 0,2, on trouve:

. (0,2? sm(0,2) ~ 0,2 - --1 - 0,198 666 6667 3.

et une erreur absolue de 0,2664 x 10-5 . On remarque de plus que le rapport entre les deux erreurs absolues est:

0,2664 x 10-5 - 1 0 8332 x 10-7 - 3 '97 '

ce qui confirme que cette approximation est bien d'ordre 5. En prenant une valeur de h deux fois plus grande, on trouve une erreur peu prs 25 = 32 fois plus grande. Cet exemple montre que le polynme de Taylor de degr 3 de la fonction f( x) = sin x est d'ordre 5 .

1.6.2 Dveloppement de Taylor en plusieurs variables On peut reprendre, dans le cas de plusieurs variables, le raisonnement

qui a men au dveloppement de Taylor d'une variable. Nous nous limitons, pour les fins de l'expos, trois variables, le cas gnral tant similaire.

42 Chapitre 1

Thorme 1.3 Soit f(xt, x2, x3), une fonction de trois variables, que l'on suppose suffisam-ment diffrentiable. On a alors:

+ Les termes suivants (dsigns par les pointills) font intervenir les diffrentes drives partielles d'ordre 3, 4, 5 de la fonction f(xt, x 2 , X3). On voit bien la similitude avec le cas d'une variable. En pratique, on utilise principalement le dveloppement de degr 1, qui ne fait intervenir que les drives partielles d'ordre 1. D

Exemple 1.28 Soit la fonction de deux variables:

f(xt, Xz) =xi+ Xt sin Xz que l'on dveloppe autour de (x~, x 2 ) = (1, 0). On a alors /(1, 0) = 1. De plus, les drives partielles du premier ordre de f sont:

f(x~, xz) . = 2x1 +sm x2

Xt

et celles du deuxime ordre sont:

82 f(xt, xz) = 2 xi

Analyse d'erreurs

Au point (1, 0), ces drives partielles valent:

et

8/(1' 0) = 2 8x1

8f(1' 0) = 1 8xz

8Zj(1,0)=2 8zf(1;0)=0 8zf(1,0)=1 8xi 8xz 8x18xz

43

Le dveloppement de Taylor de degr 2 de cette fonction de deux variables autour du point (1 , 0) est donc:

c'est--dire /(1 + h1,hz) ~ 1 + 2ht +hz+ hi+ hthz

En choisissant par exemple h1 = hz = 0,1, on obtient l'approximation sui-vante:

!(1,1' 0,1) ~ 1,32 qui est proche de la valeur exacte 1,319 816 758 avec une erreur absolue d'environ 0,000 183. Si on prend maintenant h1 = hz = 0,05, on obtient une approximation de /(1,05, 0,05) qui vaut 1,155. L'erreur absolue dans ce dernier cas est d'environ 0,000 021825, qui est environ 8,4 fois plus petite qu'avec h1 =hz= 0,1. Ce facteur de 8 s'explique par le choix d'un dvelop-pement de degr 2 (et d'ordre 3) et par la division des valeurs de h1 et hz par 2.

1.6.3 Propagation d'erreurs dans le cas gnral Nous approfondissons dans cette section plusieurs notions vues plus haut.

Que peut-on dire, par exemple, de la prcision des rsultats obtenus lorsqu'on additionne ou qu'on multiplie des valeurs connues avec une prcision limite? Plus gnralement, si on a:

x x* ~x y y* ~y

quelle sera la prcision de la fonction d'une variable f( x*) ou de la fonction de deux variables g(x*, y*)? Ici encore, le dveloppement de Taylor apporte

44 Chapitre 1

une solution. Considrons d'abord le cas d'une variable. Une quantit x inconnue est approche par une valeur approximative x* avec une erreur absolue ~x. On estime la valeur inconnue f( x) par l'approximation f( x*). L'erreur absolue lie ce rsultat est:

~~ = lf(x)- f(x*)l On a de plus:

f(x) = f(x* ~x)= f(x*) J'( x*) ~x+ O((~x)2 ) En ngligeant les termes d'ordre plus grand ou gal 2, on obtient:

~~ c:::: lf'(x*)l ~x que l'on peut galement crire:

f(x) = f(x*) 1/'(x*)l~x (1.31)

Exemple 1.29 On a mesur la longueur d'un ct d'une bote cubique et obtenu l* = 10,2 cm avec une prcision de l'ordre du millimtre (~l = 0,1 cm). On cherche le volume v de cette bote. Dans ce cas, f(l) = l3 = v et l'erreur lie au volume est:

~v= lf'(l*)l ~~ = 3 (10,2)2 x 0,1 = 31,212::; 0,5 x 102 La valeur approximative du volume est (10,2)3 = 1061,2 cm3 , dont seuls les deux premiers chiffres sont significatifs .

On traite les fonctions de plusieurs variables en faisant appel au dve-

loppement de Taylor en plusieurs variables. Nous donnons le rsultat en dimension 3 seulement, car le cas gnral ne pose aucune difficult suppl-mentaire.


Thorme 1.4 Soit f( x, y, z), une fonction de trois variables x, y et z dont on estime la valeur par x*, y* et z* avec une prcision de ~x, de ~y et de ~z respectivement. L'erreur absolue ~~ est donne par:

~~ = 1 f(x~:*, z*) 1 ~x + 1 f(x~:*, z*) 1 ~y (1.32)

+ lf(x~:*,z*)l ~z D

Exemple 1.30 Un signal lectrique est donn par:

V= A sin(wt- cf;) o V est la tension, A est l'amplitude du signal (A* = 100 V), w est la frquence (w* = 3 rad/s), cp est le dphasage (cp* = 0,55 rad) et t est le temps ( t* = 0,001 s ). En supposant que A et w sont connus exactement (A= A*, w = w*) et que cp* et t* possdent respectivement 2 et 1 chiffres significatifs, il s'agit d'valuer l'erreur absolue lie V ainsi que le nombre de chiffres significatifs.

Puisque A et w sont connus exactement, on sait immdiatement que ~A et ~w sont nuls et qu'ils n'ont aucune contribution l'erreur lie V. Par ailleurs:

~t 0,5 x 10-3 ~cp 0,5 x 10-2

et l'erreur totale est:

c'est--dire

~V= IA*w*cos(w*t*- cj;*)lx(0,5x10-3 )+1-A*cos(w*t*- cj;*)lx(0,5x10-2)

46 Chapitre 1

ce qui donne:

~v 256,22666235 x (0,5 x 10-3 ) + 1-85,40887451 x (0,5 x 10-2) = 0,555157 684

La tension approximative V* est bien sr:

V* =A* sin(w*t*- cp*)= -52,012 730 71 et puisque ~V ::::; 0,5 x 101 , ce nombre n'a qu'un seul chiffre significatif .

Quelques cas particuliers mritent de l'attention. De l'quation 1.32, on

peut dduire la faon dont se propagent les erreurs dans les oprations l-mentaires. En effet, en prenant par exemple f(x, y)= xjy, on trouve:

ou encore A( ..!... ) = IYI~x + ixi~Y ux.y 2 y

On obtient ainsi le tableau suivant partir de l'quation 1.32.

~(x+ y) - ~x+~y -

~(x- y) - ~x+~y -

~(x x y) - IYI~x + lxi~Y - (1.33)

~(x+ y) - IYI~x + ixi~Y - y2

On remarque que les erreurs absolues pour la soustraction s'additionnent. Le tableau montre galement la similitude entre la propagation d'erreurs et la diffrentiation d'une somme, d'une diffrence, d'un produit et d'un quotient de deux fonctions.


1. 7 Exercices

1. Tous les chiffres des nombres suivants sont significatifs. Donner une borne suprieure de l'erreur absolue et estimer l'erreur relative.

a) 0,1234 b) 8, 760 c) 3,14156 d) 0,112 35 x 10-3 e) 8,000 f) 0,223 56 x 108

2. Exprimer les nombres dcimaux suivants en reprsentation binaire clas-sique.

a) 32 b) 125 c) 1231 d) 876 e) 999 f) 12345

3. Exprimer les entiers signs 125, -125, 0, 175 et -100 dans une forme binaire sur 8 bits en utilisant:

a) la reprsentation signe et grandeur. b) le complment 2. c) la reprsentation par excs ( d = 27 ).

4. Traduire les nombres binaires 0000 0011, 1000 0001 et 11111111 dans la forme dcimale selon que la reprsentation utilise est:

a) la reprsentation binaire classique. b) la reprsentation signe et grandeur. c) le complment 2. d) la reprsentation par excs ( d = 27 ).

5. Pour reprsenter les nombres rels, considrer un mot de 16 bits dont 1 exprime le signe du nombre, 5, l'exposant et 10, la mantisse. a) Reprsenter le plus petit et le plus grand nombre positifs en utilisant le complment 2 pour l'exposant. b) Dterminer la prcision machine.

6. Convertir en forme binaire les fractions dcimales suivantes.

a) 0,5 b) 0,2 c) 0,9 d) 1/3 e) 0,25 f) 3/8

48 Chapitre 1

7. Un ordinateur fictif reprsente les nombres rels sur 32 bits dans l'ordre suivant: 1 bit pour le signe du nombre (0 = positif, 1 = ngatif); 7 bits pour l'exposant en reprsentation signe et grandeur; 24 bits pour la mantisse (normalise). a) Que reprsentent (en base 10) les 32 bits:

1000 10111010 1000 0010 0000 0000 0000

b) Donner une borne suprieure de l'erreur relative lie cette repr-sentation (on suppose que l'ordinateur utilise la troncature). c) Donner l'expression binaire sur 32 bits du plus petit nombre rel positif reprsentable et donner sa valeur en base 10.

8. Convertir les nombres suivants en simple prcision IEEE.

a) -52,234375 b)7112,0 c)16,2 Vrifier les rponses en les retransformant en nombres dcimaux. va-luer l'erreur de reprsentation commise en c).

9. Donner la reprsentation en notation flottante en base 10 des nombres suivants (arrondir en conservant 4 chiffres dans la mantisse).

a) e b) 1/6 c) 2/3 d) 12,487 x 105 e) 213 456 f) 2000,1

10. Montrer que la loi d'associativit de l'addition n'est pas toujours res-pecte en arithmtique flottante. Utiliser l'arithmtique flottante 3 chiffres et les nombres suivants: x = 0,854 x 103 , y= 0,251 x 103 et z = 0,852 x 103

11. Effectuer les oprations suivantes en arithmtique flottante 3 chiffres. a) 1r(1j1r) b) 2136 (9993 + 0,004 567) c) (1,235)4 d) 10 200 + 341 e) (10200+ 341)- 9800 f) (125 x 25) + (10 x 2,5)


12. Combien de nombres diffrents peut-on reprsenter en arithmtique flottante 3 chiffres (base 10) si l'exposant l est compris entre -9 et 9?

13. Est-ce que (x . y) est quivalent (x x (1 flottante?

y)) en arithmtique

14. On doit effectuer l'opration 1 - cosx pour des valeurs de x voisines de O. Expliquer ce qui risque de se produire du point de vue de l'arith-mtique flottante et proposer une solution de rechange.

15. Donner une faon d'valuer les expressions suivantes qui permette d'viter le plus possible les erreurs dues l'arithmtique flottante. a) cos2 e- sin2 e pour des valeurs de e autour de 7r /4 b) p(2), o p(x) = 1- 2x + 3x2 - 4x3

100 1 c) L-=2

i=l z

16. La srie divergente: 00 1 2:-

n=l n

devient convergente en arithmtique flottante. Expliquer brivement pourquoi.

17. Dmontrer que l'erreur relative lie la multiplication et la division de deux nombres est la somme des erreurs relatives lies chacun des nombres.

18. Effectuer les dveloppements de Taylor suivants l'ordre demand. Utiliser la forme de l'quation 1.28. Donner l'expression analytique du terme d'erreur. Donner galement une borne suprieure de l'erreur lorsque c'est possible.

a) cos(x) autour de xo = 0 (ordre 8) b) sin( x) autour de xo = 0 (ordre 9) c) arctan( x) autour de x0 = 0 (ordre 5) d) cos( x) autour de xo = 1r /2 (ordre 7) e) sin( x) autour de xo = 1r /2 (ordre 8)

50 Chapitre 1

19. valuer les erreurs commises dans l'valuation des fonctions suivantes. Tous les chiffres fournis sont significatifs. Indiquer le nombre de chiffres significatifs du rsultat. a) ln(x) en x*= 2,01 b) arctan(x) en x*= 1,0100 c) x8 en x*= 1,123 d) (sin(x))2 en x*= 0,11

20. valuer les erreurs commises dans l'valuation des fonctions de plu-sieurs variables suivantes. Tous les chiffres fournis sont significatifs. Indiquer le nombre de chiffres significatifs du rsultat. a) x 2y3 en x*= 12,1, y*= 3,721 b) -xyz en x* = 1,260, y* = 0.5 x 10-3 , z* = 12,93

21. l'aide d'une mthode numrique, on a valu la drive d'une fonc-tion pour deux valeurs de h.

h J'( xo) Erreur absolue 0,1 25,3121 0,0004

0,05 25,312 475 0,000 025

a) Donner le nombre de chiffres significatifs de chaque approximation et arrondir au dernier chiffre significatif. b) Quel est l'ordre de la mthode de diffrentiation numrique utilise.

22. a) Calculer le dveloppement de Taylor d'ordre 5, c'est--dire dont le terme d'erreur est de type O(h5 ), de la fonction f(x) = ln(x) autour de x 0 = 1. Donner l'expression analytique du terme d'erreur. b) l'aide de ce dveloppement, donner une approximation de ln(1,1). Par comparaison avec la valeur exacte (ln 1,1 = 0,095 310 179 8), don-ner le nombre de chiffres significatifs de l'approximation. c) Par quel facteur approximatif l'erreur obtenue en b) serait-elle r-duite si on valuait ln(1,025) au moyen du dveloppement de Taylor obtenu en a)? (Ne pas faire les calculs.)

23. En se servant d'un dveloppement de Taylor de la fonction arctan x autour de xo = 0, on a obtenu les rsultats suivants:

arctan(0,4) = 0,380 714 667 (erreur absolue = 0,208 29 x 10-3 ) arctan(0,1) = 0,099 668 667 (erreur absolue = 0,1418 x 10-7 )


Quel tait l'ordre du dveloppement de Taylor utilis? 24. a) Obtenir le dveloppement de Taylor autour de x0 = 0 de la fonction:

1 f(x) = -1 --x b) Poser x = -t2 dans le dveloppement en a) et obtenir le dvelop-pement de Taylor de:

1 g(t) = 1 + t2

c) Intgrer l'expression obtenue en b) et obtenir le dveloppement de Taylor d 'arctan t. d) Utiliser l'expression obtenue en a) et obtenir le dveloppement de Taylor de ln(l +x). (Remplacer x par -x en premier lieu.)

25. La fonction d'erreur f( x) est dfinie par: 2 rx 2 f(x)= .Jii}o e-t dt

Pour en obtenir le dveloppement de Taylor, on peut suivre les tapes suivantes: a) Obtenir le dveloppement de Taylor de e-x. (Limiter le dveloppe-ment aux 6 premiers termes.) b) Dduire de a) le dveloppement de Taylor de e-t2 c) Dduire de b) le dveloppement de Taylor de f( x). d) Donner une approximation de f(l) en utilisant les 4 premiers termes de son dveloppement de Taylor. e) Quel est l'ordre de l'approximation obtenue end)? f) Donner le nombre de chiffres significatifs de l'approximation obtenue en d) en la comparant avec la valeur exacte f( 1) = 0,842 701.

Chapitre 2 ,

Equations non linaires

2.1 Introduction Le numricien est souvent confront la rsolution d'quations alg-

briques de la forme: f(x)=O (2.1)

et ce dans toutes sortes de contextes. Introduisons ds maintenant la termi-nologie qui nous sera utile pour traiter ce problme.

Dfinition 2.1 Une valeur de x solution de f( x) = 0 est appele une racine ou un zro de la fonction f( x) et est note r.

Nous avons tous appris au secondaire comment rsoudre l'quation du second degr:

dont les deux racines sont:

ax2 + bx + c = 0

-b v'b2 - 4ac 2a

Certains ont galement vu comment calculer les racines d'une quation du troisime ordre et se souviennent que la formule est beaucoup plus com-plexe. On peut aussi obtenir une formule gnrale pour le quatrime degr. Par contre, la plupart des tudiants ignorent qu'il n'existe pas de formule permettant de trouver les racines des polynmes de degr plus grand ou gal

54 Chapitre 2

5. Non pas que les mathmaticiens ne l'aient pas encore trouve, mais Galois1 a dmontr que cette formule n'existe pas.

Puisqu'il n'existe pas de formule gnrale pour des fonctions aussi simples que des polynmes, il est peu probable que l'on puisse rsoudre analytique-ment l'quation 2.1 dans tous les cas qui nous intressent. n faudra donc recourir aux mthodes numriques. Dans ce qui suit, nous prsentons plu-sieurs techniques de rsolution, chacune ayant ses avantages et ses inconv-nients. Nous tcherons de mettre en vidence ces avantages et inconvnients de faon tirer le meilleur parti de chacune des mthodes proposes.

n faudra galement se souvenir des enseignements du chapitre prcdent pour viter de dvelopper des algorithmes numriquement instables.

2.2 Mthode de la bissection La mthode de la bissection repose sur une ide toute simple, savoir

qu'en gnral, de part et d'autre d'une solution de l'quation 2.1, une fonction continue f( x) change de signe et passe du positif au ngatif ou vice versa (voir la figure 2.1 ). De toute vidence, ce n'est pas toujours le cas puisque la fonction f( x) peut aussi tre tangente l'axe des x (voir la figure 2.2).

Supposons pour l'instant qu'il y ait effectivement un changement de signe autour d'une raciner de f(x). Nous nous occuperons des cas pathologiques un peu plus tard. Soit [xi. x2], un intervalle ayant un changement de signe, c'est--dire:

On pose alors: Xm =

Xl+ Xz

2

(2.2)

qui est bien sr le point milieu de l'intervalle. n suffit alors de dterminer, entre les intervalles [xi. Xm] et [xm, xz], celui qui possde encore un chan-gement de signe. La racine se trouvera forcment dans cet intervalle. la premire itration de la figure 2.1, ce serait l'intervalle [xw, x2], tandis qu' la deuxime itration ce serait [xi. xml Cela nous amne l'algorithme suivant.

1 Le mathmaticien variste Galois (1811-1832) fut tu dans un duel l'ge de 21 ans, non sans avoir eu le temps d'apporter une contribution considrable la tho-rie des groupes.

quations non linaires

10

-2~--~--~----~--~--~--~--~~~ -2 -1.5 -1 x,

0.5

~0.5

-1

0.2 0,4 0.6 0.8 l 12 1.4 1.6 1.8 2 Xl Xm Xz

0,8

0.4

0,2

-0,2

-0.4

-0,6

-0.8

x, 0,1 0,2 0.3

0,2

0.1

~0,1

-0.2

-0.3

~0.4

-0.5

-0,6

-0,7 0.5 x,

0,4 0,5 0,6 xm

0.55 0.6 0,65

0.7 0,8 0,9 Xz

0,7 0,75 0,8 0,85 0,9 xm

Figure 2.1: Mthode de la bissection: f( x) = e-x - x

55

0,95 1 Xz

56 Chapitre 2

Algorithme 2.1: Algorithme de la bissection

1. tant donn un intervalle [xt, x2] pour lequel f( x) possde un change-ment de signe

2. tant donnE, le critre d'arrt, et N, le nombre maximal d'itrations 3. Poser:

Xm =

S. lx2- x1l 4. 1 1 1 < E: 2 Xm convergence atteinte crire la racine x m crire f (x m ) arrt

5. crire x1, x2, Xm, f(x!), f(x2), f(xm) 6. Si f(xl) X f(xm) < 0, alors X2 = Xm 7. Si f(xm) X f(x2) < 0, alors X1 = Xm 8. Si le nombre maximal d'itrations N est atteint:

convergence non atteinte en N itrations arrt

9. Retour l'tape 3 D

L'expression: lx2- x1l

2lxml est une approximation de l'erreur relative. En effet, l'tape 3 de l'algorithme de la bissection, la racine recherche est soit dans l'intervalle [xt, Xm] ou dans l'intervalle [xm, x 2], qui sont tous deux de longueur:

quations non linaires 57

ce qui constitue une borne suprieure de l'erreur absolue. En divisant par Xm, on obtient une approximation assez fiable de l'erreur relative.

Remarque 2.1 Dans l'algorithme prcdent, il faut prendre garde au cas o la racine re-cherche est O. ll y a alors risque de division par 0 au cours de l'valuation de l'erreur relative. Ce cas est toutefois rare en pratique. 0

Remarque 2.2 ll est parfois utile d'introduire un test d'arrt sur la valeur de f(x), qui doit tendre galement vers O. 0

Exemple 2.1 La fonction f( x) = x3 + x 2 3x - 3 possde un zro dans l'intervalle [1, 2). En effet:

!(1) x !(2) = -4,0 x 3,0 = -12,0 < 0 On a alors Xm = 1,5 et !(1,5) = -1,875. L'intervalle [1,5, 2) possde encore un changement de signe, ce qui n'est pas le cas pour l'intervalle [1, 1,5). Le nouvel intervalle de travail est donc [1,5, 2], dont le point milieu est Xm = 1,75. Puisque f(1,75) = 0,17187, on prendra l'intervalle [1,5, 1,75) et ainsi de suite. Le tableau suivant rsume les rsultats.

Xl Xz Xm f(xl) f(xz) f(xm) Erreur absolue lie Xm

1,0 2,0 1,5 -4,0 3,0 -1,875 0,5 1,5 2,0 1,75 -1,875 3,0 +0,17187 0,25 1,5 1,75 1,625 -1,875 0,17187 -0,943 35 0,125

1,625 1,75 1,6875 -0,94335 0,17187 -0,40942 0,0625 1,6875 1,75 1,718 75 -0,40942 0,17187 -0,124 78 0,03125

On remarque aisment que la longueur de l'intervalle entourant la racine

est divise par deux chaque itration. Cette constatation permet de dter-miner l'avance le nombre d'itrations ncessaires pour obtenir une certaine

58 Chapitre 2

erreur absolue ~r sur la raciner. Soit L = x2 -Xt, la longueur de l'intervalle de dpart. Aprs une itration, le nouvel intervalle est de longueur L/2 et aprs n itrations la longueur de l'intervalle est:

Si on veut connatre la valeur de n ncessaire pour avoir:

il suffit de rsoudre cette quation en fonction de n et on trouve la condition:

n > ln(ir) ln 2

(2.3)

n est clair que, sur le plan pratique, on doit prendre pour valeur de n le plus petit entier vrifiant cette condition.

Exemple 2.2 Dans l'exemple prcdent, L = 2,0- 1,0. Si on veut une erreur absolue plus petite que 0,5 x 10-2, ce qui revient s'assurer que le chiffre des centimes est significatif, il faut effectuer au moins:

1 ( 1,0 ) n o,sxlo 2 = 7 64 itrations

ln2 '

On fera donc 8 itrations pour s'assurer de cette prcision. On peut aisment vrifier qu'aprs 8 itrations l'erreur maximale lie Xm est de 0,003 906 25 et que la vritable erreur est 0,001 582 .

Exemple 2.3 On souhaite calculer v'2 avec une calculatrice dote seulement des 4 opra-tions lmentaires. Cela revient rsoudre:


Cette fonction prsente un changement de signe dans l'intervalle [1, 2]. L'algorithme de la bissection donne les rsultats suivants avec f = 10-3 .

Xl X2 Xm !(xl) f(x2) f(xm) (xmh 1,0 2,0 1,5 -1,0 2,0 +0,25 1,1 1,0 1,5 1,25 -1,0 0,25 -0,4375 1,01 1,25 1,5 1,375 -0,4375 0,25 -0,1094 1,011 1,375 1,5 1,4375 -0,1094 0,25 +0,06641 1,0111 1,375 1,4375 1,4062 -0,1094 0,06641 -0,02246 1,011 01 1,4062 1,4375 1,4219 -0,022 46 0,06641 +0,021 73 1,011011 1,4062 1,4219 1,4141 -0,02246 0,02173 -0,00043 1,0110101

1,4141 1,4219 1,4180 -0,00043 0,021 73 +0,010 64 1,4141 1,4180 1,4160 -0,00043 0,01064 +0,00510 1,4141 1,4160 1,4150 -0,00043 0,00510 +0,002 33 1,4141 1,4150 1,4146 -0,00043 0,002 33 +0,00095 1,4141 1,4146 1,4143 -0,00043 0,000 95 +0,00026

On a arrondi 5 chiffres les rsultats de ce tableau. La racine trouve est alors 1,414184 57, ce qui se rapproche de la valeur exacte ( 10 chiffres significatifs) 1,414 213 562. Cet exemple est particulirement intressant du point de vue de la reprsentation binaire. En effet, l'intervalle de dpart tant [1, 2] et puisque les nombres 1 et 2 possdent des reprsentations binaires exactes, chaque itration de la mthode de la bissection permet de fixer 1 bit de la reprsentation binaire de la racine. la ( n + 1 )e itration, on est assur que les n premiers bits de la mantisse de Xm sont exacts. On peut constater ce phnomne la dernire colonne du tableau, qui contient la reprsentation binaire de Xm.

Remarque 2.3 La convergence de la mthode de la bissection n'est pas trs rapide, mais elle est sre partir du moment o on a un intervalle avec changement de signe. On parle alors de mthode ferme, car on travaille dans un intervalle ferm. C'est galement le cas de la mthode de la fausse position (voir les exercices de fin de chapitre). Les mthodes des sections qui suivent sont dites ouvertes en ce sens qu'il n'y a pas d'intervalle dterminer ayant un changement de signe. Au contraire des mthodes fermes, les mthodes ouvertes ne garantissent nullement la convergence, mais elles possdent d'autres avantages. D

60 Chapitre 2

Figure 2.2: Cas pathologiques pour la mthode de la bissection


Remarque 2.4 TI existe des cas o la mthode de la bissection achoppe. La figure 2.2 illustre certains de ces cas. La premire situation critique est celle o la fonction f( x) est tangente l'axe des x et ne prsente donc pas de changement de signe. La bissection ne peut alors s'appliquer. TI y a aussi celle o deux racines (ou un nombre pair de racines) sont prsentes dans l'intervalle de dpart; en ce cas, il n'y a toujours pas de changement de signe. Enfin, si l'intervalle de dpart contient un nombre impair de racines, f( x) change de signe mais l'algorithme peut avoir des difficults choisir parmi ces racines. On peut assez facilement viter ces cueils en illustrant graphiquement la fonction f( x) dans l'intervalle d'intrt. D

2.3 Mthodes des points fixes Avant d'aborder les mthodes des points fixes, il importe de dfinir ce

qu'est un point fixe d'une fonction.

Dfinition 2.2 Un point fixe d'une fonction g(x) est une valeur de x qui reste invariante pour cette fonction, c'est--dire toute solution de:

x= g(x) (2.4) est un point fixe de la fonction g( x).

n existe un algorithme trs simple permettant de dterminer des points fixes. n suffit en effet d'effectuer les itrations de la faon suivante:

{ xo

Xn+l

donn g(xn) (2.5)

partir d'une valeur estime initiale x 0 L'intrt de cet algorithme rside dans sa gnralit et dans la relative facilit avec laquelle on peut en faire l'analyse de convergence. TI en rsulte l'algorithme plus complet suivant.

62 Chapitre 2

Algorithme 2.2: Algorithme des points fixes

1. tant donn t:, un critre d'arrt 2. tant donn N, le nombre maximal d'itrations 3. tant donn x 0 , une valeur estime initiale du point fixe 4. Effectuer Xn+l = g(xn)

S. lxn+l - Xnl 5. 1 1 1 < f: Xn+l

convergence atteinte crire la solution Xn+l arrt

6. Si le nombre maximal d'itrations N est atteint:

convergence non atteinte en N itrations arrt

7. Retour l'tape 4 D

On peut rsoudre des quations

Documents

448 pages analyse.pdf