1

Chapitre 1 Chapitre 1 Chapitre 1 Chapitre 1 IntroductionIntroductionIntroductionIntroduction au calcul numriqueau calcul numriqueau calcul numriqueau calcul numrique

I.I.I.I. IntroductionIntroductionIntroductionIntroduction Les mthodes numriques permettent de rsoudre par des calculs numriques des problmes danalyse mathmatique (optimisation, calcul diffrentiel ou intgral, algbre linaire). Ces mthodes numriques sont bases sur le dveloppement dalgorithmes1 dvelopps sur des ordinateurs et des calculateurs. Les rsultats fournis par un ordinateur aussi sophistiqu soit-il, sont des solutions approches. Les approximations utilises par les machines dpendent la fois des contraintes physiques de la machine (espace mmoire, vitesse de lhorloge, ...)2 et du choix des mthodes utilises par le concepteur du programme Dans la pratique, les types de problmes abords sont du ressort des mathmatiques continues (variable relle ou complexe). . La rsolution dun problme par un ordinateur est discrte. En effet, dans le systme numrique dun ordinateur la prcision dun chiffre (le nombre significatif de dcimales dun chiffre) ne peut excder la longueur maximale des mots permise par lordinateur. Il en dcoule donc que tous les calculs sont entachs derreurs darrondi. La difficult omniprsent rencontr en analyse numrique est don celui du contrle de la propagation des erreurs qui seront invitablement engendres par les machines durant lexcution des calculs. En gnral la rsolution dun problme mathmatique donn se fera suivant les tapes suivantes :

1.1.1.1. MMMModlisation du problmeodlisation du problmeodlisation du problmeodlisation du problme Le problme pratique (ingnierie, sciences physiques, ) est formul sous la forme dun modle mathmatique (intgrale, systme dquations linaires, quations diffrentielles ou quations aux drives partielles.

2.2.2.2. Choix dune mthode numrique et des paramtres de la mthodeChoix dune mthode numrique et des paramtres de la mthodeChoix dune mthode numrique et des paramtres de la mthodeChoix dune mthode numrique et des paramtres de la mthode

Cette tape pourrait comporter une estimation prliminaire derreurs.

1 On appelle algorithme toute mthode de rsolution dun problme donn. Linterface dun algorithme prsente les donnes (paramtres dentre ou INPUT) et les rsultats (paramtres de sortie ou OUTPUT) du problme. Elle dcrit galement une succession doprations lmentaires qui constituent les tapes de rsolution du problme (telles que prconises par la mthode numrique choisie). 2 Pour en savoir plus sur le fonctionnement dun ordinateur, consulter www.commentcamarche.com

2

3.3.3.3. ProgrammationProgrammationProgrammationProgrammation

La mthode numrique choisie pour la rsolution du problme mathmatique est prsente sous la forme dun algorithme qui sera utilis pour crire un programme en langage informatique (Mathematica, Maple, Matlab, Fortran, C, C++, ). La programmation dans un langage donn requiert le choix de routines adaptes. Un algorithme doit tre simple, peu complexe et efficace (au sens o une erreur gnre ne croit pas trop durant le calcul).Dans le cadre de ce cours le logiciel libre scilab sera utilis (scilab Version 5.3.0)Version 5.3.0)Version 5.3.0)Version 5.3.0) est : http://www.scilab.org/products/scilab/download

4.4.4.4. Excution des calculsExcution des calculsExcution des calculsExcution des calculs

5.5.5.5. Interprtation des rsultatsInterprtation des rsultatsInterprtation des rsultatsInterprtation des rsultats / Rexcution des calcul/ Rexcution des calcul/ Rexcution des calcul/ Rexcution des calculssss Les rsultats des calculs doivent tre interprts en des termes physiques. On pourrait galement dcider dexcuter nouveau le programme de calcul, de rviser lalgorithme conu pour le rendre plus efficace ou de reformuler le problme mathmatique.

II.II.II.II. Type dalgorithmeType dalgorithmeType dalgorithmeType dalgorithmessss

1.1.1.1. Mthodes directesMthodes directesMthodes directesMthodes directes Elles mnent la solution exactes du problme mathmatiques aprs lapplication dun nombre finis doprations lmentaires (exemples : limination de Gauss, algorithme du simplexe). Cependant, il n ya pas de mthodes directes connues pour tous les types de problmes et il faut parfois se contenter dune solution approche. Par ailleurs, mme lorsquune mthode directe existe, lutilisation d autres mthodes peut tre prfrable.

2.2.2.2. Mthodes itrativesMthodes itrativesMthodes itrativesMthodes itratives Elles reposent sur lapplication dun algorithme itratif qui permet de gnrer une suite de solutions approches du problme considr. Sous certaines conditions, cette suite converge vers la solution. Les mthodes itratives sont dites autocorrectives car elles permettent la correction des erreurs chaque itration. On peut les prfrer mme quand une mthode directe existe car elles sont plus stables et plus efficaces.

3

Plusieurs mthodes itratives seront tudies dans le cadre de cours (mthode de Newton, de Lagrange, .)

3.3.3.3. DiscrtisationDiscrtisationDiscrtisationDiscrtisation

Lapplication de ces mthodes de rsolution numrique exige que lon remplace le problme mathmatique continu par un problme discret : en fait elles adoptent le mme mode de fonctionnement que les ordinateurs. La solution du problme, souvent une fonction (exemple rsolution dune quation diffrentielle), est alors reprsente par un nombre fini de valeurs dtermin sur un nombre fini de points du domaines de dfinition de la fonction. Il existe plusieurs types de mthode de discrtisation : diffrences divises, lments finis, diffrences finies et volumes finis.

III.III.III.III. Reprsentation des nombres en machinesReprsentation des nombres en machinesReprsentation des nombres en machinesReprsentation des nombres en machines

1.1.1.1. Le stockage des nombresLe stockage des nombresLe stockage des nombresLe stockage des nombres La mmoire dun ordinateurs est compose de millions ( Mo) voir de milliards (Go)doctets situs dans des emplacements prcis appels des octets. Les nombres stocks qui y sont reprsents sous la forme dentiers relatifs ou de rels.

a)a)a)a) les entiersles entiersles entiersles entiers Pour les entiers, le calcul se fait dans une arithmtique modulo2n o n est le nombre de bits des mots machines. En gnral, n prend les valeurs 16, 32 ou 64 bits et dfinit la prcision du nombre. Les entier ngatifs tant pris en compte les nombres donc sont pris entre -2n-1 et 2n-1 - 1. Soit, pour n=16 bits, sur l'intervalle [-32768, 32767].

b)b)b)b) les reles reles reles relslslsls Dans le systme dcimal, un rel peut tre reprsent avec un nombre fini ou infini de dcimales. Dans un ordinateur, deux formes de reprsentations sont possibles :

i.i.i.i. NNNNotation fixeotation fixeotation fixeotation fixe :::: Tous les nombres sont reprsents avec un nombre fini de dcimales (exemples : 72.457 ; 0.023 ; -2.000). Cependant, cette notation nest pas efficace pour le calcul scientifique.

4

ii.ii.ii.ii. NNNNotation flotanteotation flotanteotation flotanteotation flotante La notation flottante est celle utilise par les ordinateurs. Elle sert reprsenter des valeurs relles impossibles obtenir en notation fixe. Un nombre flottant est du type :

0.6427. 103 ; 0.1825 10-26 ; -0.2000 10-1 ou 6.427. 102 ; 1.825 10-27 ; -2.000 10-2 (1)(1)(1)(1) On remarque que quen notation flottante, le nombre de dcimales significatives est fixe tandis que la virgule est dite flottante . Un nombre flottant tient souvent sur le mme nombre de bits n qu'un nombre entier. Deux prcisions sont retenues dans la reprsentation flottante : la prcision simple (32 bits) et la prcision double (64 bits). Ces prcisions dterminent le nombre maximal de dcimales significatives qui pourront tre reprsentes dans la notation flottante dun rel. Les nombres flottants sont donc une approximation des nombres rels. Lexemple ci-dessus ((((1)1)1)1) montre quil y a plusieurs formats de reprsentation dun nombre rel en notation flottante. Pour rendre portable lcriture flottante, un format standard a t dfini : la norme IEEE 754norme IEEE 754norme IEEE 754norme IEEE 754. Ce format est commun tous les ordinateurs. Etant donn un rel a, lcriture flottante de a note fl(a) est telle que :

ffffl(a) = l(a) = l(a) = l(a) = Km.10m.10m.10m.10rrrr avec avec avec avec m =0.d1 d2.dsm =0.d1 d2.dsm =0.d1 d2.dsm =0.d1 d2.ds et d1 et d1 et d1 et d1 0;0;0;0; - m est la mantisse. Les di sont appels les digits. Ce sont des entiers naturels compris

entre 0 et 9 - r est lexposant. r est un entier relatif compris entre -37 et +38 (en prcision

simple) -307 et +308 (en prcision double).

ExempleExempleExempleExemple 2222: avec une prcision 10-4 prs (on dit aussi 4 digits significatifs) on a : fl(98.17) = 0.9817 102 ; fl(10) =0.1000 102; fl(0.0057869) = 0.5787 10-6, fl(-13600) = -0.1360 105 RemarqueRemarqueRemarqueRemarquessss : : : : 1. Les nombres flottants sont une approximation des nombres rels, car le nombre de chiffres significatifs de la mantisse est dtermin par la prcisons (simple ou double) utilise par la machine. Dans la norme IEE 754, si s dsigne la prcision souhaite, la mantisse est alors une valeur arrondie 10-s prs (Exemple : 10-4 prs, fl(-100.987) = -0.1001 10)

Norme IEEE 754Norme IEEE 754Norme IEEE 754Norme IEEE 754 Digits significatifs Digits significatifs Digits significatifs Digits significatifs ExposantExposantExposantExposant Simple Prcision (32 bits) s = 7 10-37 10n 10+38 Double prcision (64 bits) s= 16 10-307 10n 10+308

5

2. Lorsque lexposant r est en dessous de la norme IEEE (r < -307), O est affich : on dit quil ya underflow (dpassement de capacit vers le bas)

3. Lorsque lexposant r est au dessus de la norme IEEE (r > +308) : on dit quil y a overflow (dpassement de capacit vers le haut). Les calculs sont arrts et un message derreur est affich. En cas doverflow, Excel affiche #NOMBRE).

4. La norme IEEE fixe aussi des valeurs spciales: K, NaN (Not A Number) permettant dcrire des programme lorsque pour des fonctions discontinues

2. 2. 2. 2. Rgles de larithmtique flottanteRgles de larithmtique flottanteRgles de larithmtique flottanteRgles de larithmtique flottante

Si T dsigne une des 4 oprations lmentaires, on a pour tous rels x et y : xxxx T y = fl ( fl(x)y = fl ( fl(x)y = fl ( fl(x)y = fl ( fl(x)Ufl(y)).fl(y)).fl(y)).fl(y)).

Plus prcisment AdditionAdditionAdditionAddition : x: x: x: x V y = fly = fly = fly = fl ( fl(x)+fl(y))( fl(x)+fl(y))( fl(x)+fl(y))( fl(x)+fl(y)) SoustractionSoustractionSoustractionSoustraction : x : x : x : x W y = fl (y = fl (y = fl (y = fl (fl(x)fl(x)fl(x)fl(x) fl(y)fl(y)fl(y)fl(y))))) MultiplicationMultiplicationMultiplicationMultiplication : x: x: x: x Y y = fly = fly = fly = fl ( fl(x)( fl(x)( fl(x)( fl(x)Zfl(y))fl(y))fl(y))fl(y)) Division : x Division : x Division : x Division : x [ y = fly = fly = fly = fl (fl(x)(fl(x)(fl(x)(fl(x)\fl(y))fl(y))fl(y))fl(y))

Au vu de ces rgles, il ressort que :

a)a)a)a) laddition flottante laddition flottante laddition flottante laddition flottante V nest pas nest pas nest pas nest pas associativeassociativeassociativeassociative : : : : x V (y V z) peut tre diffrent de (x V y) V z

ExempleExempleExempleExemple 3333 : avec une prcision de 4 digits, on a :

1 V (0.0005 V 0.0005) =1.0010 Par ailleurs,

(1 V 0.0005) V 0.0005 =1.0000 car (1 V 0.0005) = 0.1* 10 + 0.5*10-3

= 0.1*10 + 0.00005*10 = 0.1*10 + 0.0000*10 (avec une prcision de 4 digits) = 0.1*10

RemarqueRemarqueRemarqueRemarque : si y est trs petit par rapport _ ( y ` _) alors lordre des nombre influe sur le rsultat de laddition flottante et on a : ab(_) + ab(c) = ab(_)

6

b) la distributivit de la distributivit de la distributivit de la distributivit de la multiplication (la multiplication (la multiplication (la multiplication (Y) par rapport laddition () par rapport laddition () par rapport laddition () par rapport laddition (V ) nest pas nest pas nest pas nest pas distributive :distributive :distributive :distributive : x Y (y V z) peut tre diffrent de (x Yy) V (x Y z)

ExempleExempleExempleExemple 4444 : avec une prcision 3 digits

150 Y (222 V 767) = abd ab(150) Z ab(1089)e = ab( 0.150 *103 Z 0.109 *104) = ab(163500) = 0.164 *106

(150 Y 222) V (150 Y 767) = abd ab(33300) + ab(115050)e = ab( 0.333 f 10g + 0.115 f 10h) = ab( 148300) = 0.148*106

On remarque que dans IR, on a : 150Z (222 + 767) =(150 Z 222) + (150 Z 767)=163500. La premire expression 150 Y (222 V 767) donne donc une meilleure approximation du rsultat. Dans la seconde expression, il y a plus doprations lmentaires (3 au lieu 2dans la premire) et le rsultat obtenu est assez loign de la vraie valeur. RemarqueRemarqueRemarqueRemarque En arithmtique flottante :

1. chaque opration intermdiaire introduit une nouvelle erreur dans le calcul 2. Deux expressions algbriques quivalentes peuvent fournir des rsultats

diffrents et lordre des oprations peuvent changer les rsultats. IV IV IV IV Etude derreuEtude derreuEtude derreuEtude derreurrrrssss 1111....OriginesOriginesOriginesOrigines derreurs derreurs derreurs derreurs

a)a)a)a) Erreurs darrondiErreurs darrondiErreurs darrondiErreurs darrondi

Il est impossible dafficher toutes les dcimales dun nombre rel. Un rel sera donc soit arrondi3 , soit tronqu. 3 Dans ce cas la rgle observe pour le dernier chiffre reprsentatif est : arrondir ce chiffre lentier suprieur si la

dcimale qui vient aprs est suprieur ou gal 5 ou sinon reporter le chiffre en ltat.

7

ExempleExempleExempleExemple 5555 :::: Soit i = jjg = 0.6666666 666 Avec une prcision de 5 digits, la reprsentation flottante de a est :

forme tronque : ijk = 0.66666 10-1

forme arrondie : ilk= 0.66667 10-1

Quelle forme donne est la meilleure reprsentation a? Un ordinateur fournit une approximation du nombre sous forme darrondi lentier suprieur. Tout calcul numrique est donc toujours entach derreur

b)b)b)b) Erreurs de troncature Erreurs de troncature Erreurs de troncature Erreurs de troncature On entend par erreurs de troncature les erreurs rsultant, par exemple, des troncatures faites remplaant une sommation infinie par une somme finie (exemple remplacer 1 srie de Taylor dune fonction par ses premiers termes). Ce type derreur se rencontre souvent lors de lapplication des algorithmes itratifs. voir TD

c)c)c)c) Erreurs exprimentalesErreurs exprimentalesErreurs exprimentalesErreurs exprimentales (ou de mesure(ou de mesure(ou de mesure(ou de mesure)))) Elles dcoulent dune erreur de quantification dans les applications pratiques.

d)d)d)d) EEEErreurs de discrtisationrreurs de discrtisationrreurs de discrtisationrreurs de discrtisation Dans ce cas, la solution du problme discret ne concide pas de la solution du problme

3.3.3.3. EstimationEstimationEstimationEstimation derreurderreurderreurderreur Cest le principe de base de toute mthode numrique. Soit iq la valeur approche de a. On donne les dfinitions suivantes.

a)a)a)a) EEEErreur absoluerreur absoluerreur absoluerreur absolue On appelle erreur et on note r la valeur dfinie par :

r = i s iq Autrement dit, Erreur (r )= vraie valeur valeur approche. Lerreur ainsi dfinie est galement appele erreur absolue RemarRemarRemarRemarqqqquuuueeee : les expressions |i s iq| ou peuvent galement tre utilises pour dfinir lerreur absolue.

8

b)b)b)b) EEEErreur relativerreur relativerreur relativerreur relative On appelle erreur relative et note ru = vwvqv =

xv

Lerreur relative est donc gale yuuyzu v{|}~zyuvy v~yzu : cest le taux derreur. RemarqueRemarqueRemarqueRemarquessss ::::

1 Dans la pratique, est inconnue mais on peut obtenir une borne suprieur de lerreur note . est alors un rel positif tel que : || . est galement appele borne de lerreur . (On procde de faon analogue pour lerreur relative).

2 Souvent la vraie valeur a est inconnue, ce qui rend lerreur relative impossible. Si lerreur absolue est trs faible par rapport la valeur approche autrement dit si ` i , on prend ru xv.

c)c)c)c) Exemple Exemple Exemple Exemple de calcul derreurde calcul derreurde calcul derreurde calcul derreur Exemple Exemple Exemple Exemple 6666 : reprenons lexemple 5 Soit le rel i = jjg = 0.6666666 666 Calculons, les bornes suprieures des erreurs absolues commises dans les deux reprsentations de a.

FFFForme tronqueorme tronqueorme tronqueorme tronque :

|j| = |i s ijk| = jjg s 0.66666 10wj 0.000 000 666 666 6... Soit avec une prcision de 5 digits, |j| = |i s ijk| 0.66667 10-11

FFFForme arrondieorme arrondieorme arrondieorme arrondie : : : :

|l| = |i s ilk| = jjg s 0.66667 10wj 0.000 000 333 334 4... Soit avec une prcision de 5 digits, |l| = |i s ilk| 0.33333 10-11

9

On remarque lerreur commise sur la forme tronque est environ deux fois lerreur de la forme darrondi et par consquent la forme arrondie donne une meilleure approximation de la vraie valeur. On peut gnraliser ce rsultat. (faire la dmonstration en exercice). RemarqueRemarqueRemarqueRemarque :::: Soit une reprsentation tronque dun rel a. On note Y la mantisse de cette reprsentation. On note m la mantisse de fl(a). Alors

i s ab(i)i s

12 10

jw

4.4.4.4. Notion de meilleure approximationNotion de meilleure approximationNotion de meilleure approximationNotion de meilleure approximation Proposition 1 Proposition 1 Proposition 1 Proposition 1 Soient ijk et ilk deux approximations dun mme rel a. On note j = i s ijk l = i s ilk les erreurs absolues. On dira que ilk est une meilleure approximation de a que ijk si et seulement si |l| |j| RemarqueRemarqueRemarqueRemarque : Dans labsolu, une estimation sera considre comme bonne lorsque que le terme derreur est trs petit par rapport la valeur approche

5555 Propagation des erreursPropagation des erreursPropagation des erreursPropagation des erreurs ThormeThormeThormeThorme 1 1 1 1 1. Dans une addition ou une soustraction, la borne de lerreur absolue du rsultat est gale la somme des bornes des erreurs. 2. Dans une multiplication ou une division, la borne de lerreur relative du rsultat est approximativement gale la somme des bornes des erreurs relatives. PreuvePreuvePreuvePreuve :::: 1. Soit x et y deux rels. On note _ et c leurs approximations respectives. On a :

_ = _ + j avec | j| j et c = c + l avec | l| l

o j ldsignent les termes derreurs absolues . Soit lerreur commise dans lestimation de la diffrence de x et y. Puisque quune valeur approche de _ s c est _ s c, on a :

10

|| = |(_ s c) s ( _ s c) | =|(_ s _) (c s c)| = | j s l| | j| + | l| j + l

2. Soit u lerreur relative commise dans lestimation du produit xy |u| = w =

w(w)(w ) =

w

Comme jl est trs petit (jl 0), on a |u| +

=

+

+

ju + lu

ju lu dsignent les bornes suprieurs des erreurs relatives commises dans lestimation de x et y respectivement.

6666 Perte de digits significatifsPerte de digits significatifsPerte de digits significatifsPerte de digits significatifs DfinitionDfinitionDfinitionDfinition 2222 Lorsque le rsultat obtenu lissue dune opration a moins de dcimales significatives que les nombres partir desquels il a t calcul, on dit quil y a perte de digits significatifs (on dit aussi perte de significativit ou perte de prcision). Exemple 7Exemple 7Exemple 7Exemple 7 Trouver les racines de x - 40x +2 = 0 de deux manires diffrentes 10-4 prs Soit lquation quadratique (E) : a x + b x + c = 0 avec a 0 et b-4ac > 0. On sait que les 2 solutions exactes de (E) sont de la forme w{K{wvlv . (*). Dautre part comme x1.x2 = c/a, on a : x2 = v (**) 1111rererere mthodemthodemthodemthode Daprs (*), on obtient _j =

wZll = 20+19.95 = 39.95 = 0.3995 *10

_l = w wZl

l = 20 19.95 = 0.05 soit _l = 0.5000*10-1 avec une prcision 4 digits. On remarque que ce rsultat (x2) entraine une perte en digits significatifs. 2222memememe mthodemthodemthodemthode Comme prcdemment, on obtient daprs (*), on obtient : _j =

wZll = 20+19.95 = 39.95 = 0.3995 *10

En utilisant daprs (**), x2 = l.g = 0.05006 = 0.5006*10-1

La deuxime mthode donne une meilleure approximation de x2.

11

RemarqueRemarqueRemarqueRemarque : : : : Pour une meilleure approximation des racines dune quation quadratique (E), il est recommand dutiliser la mthode 2 en observant la rgle suivante :

- On calcule la plus grande racine de (E) avec (*) - puis, on utilise (**) pour dterminer la racine la plus petite.

VVVV ConditionnementConditionnementConditionnementConditionnement et stabilit numrique dun algorithet stabilit numrique dun algorithet stabilit numrique dun algorithet stabilit numrique dun algorithmmmmeeee Les mthodes numriques sont formules sous forme dalgorithme (voir section I). Un algorithme est une procdure agences suivant des tapes successives qui traduit une mthode numrique dans un langage de programmation ( Scilab, Matlab, C, C++, Fortran, ) comprhensible par un ordinateur. Linterface dun algorithme prsente les donnes (paramtres dentre ou INPUT) et les rsultats (paramtres de sortie ou OUTPUT) du problme. Elle dcrit galement une succession doprations lmentaires qui constituent les tapes de rsolution du problme telles que prconises par la mthode. En plus dtre clair et le moins complexe possible, un algorithme doit, pour tre efficace, vrifier certaines conditions fondamentales en analyse numrique :

1. Stabilit numriqueStabilit numriqueStabilit numriqueStabilit numrique Un algorithme est dit stable lorsquune erreur une fois gnre naugmente pas trop durant lexcution des tapes de calcul suivantes. Autrement dit, la propagation des erreurs est lente. La stabilit est une condition ncessaire et suffisante en calcul numrique.

2. Conditionnement Conditionnement Conditionnement Conditionnement Un problme est bien conditionn si de petites variations (erreurs de mesure ou darrondi) sur les donnes initiales du problme nentranent que de petites perturbations sur les rsultats finaux. Dans le cas o de petites variations entrainent une variation importante des rsultats, on dit que le problme est mal conditionn. Le conditionnement est en fait une stabilit mathmatique . Cest une condition ncessaire lefficacit dun algorithme. ATTENTION! un bon conditionnement ne garantit pas la stabilit numrique dun algorithme RRRReeeemmmmaaaarrrrqqqquuuueeee 1. Ne pas confondre la notion de problme bien conditionn et celle de problme bien

pos Un problme est dit bien pos sil admet une solution unique et si cette solution ne dpend pas continment des donnes initiales