UniversitdOrlansFacultdesSciencesLicencedephysique3meanneANALYSE NUMRIQUET.DudokdeWitUniversitdOrlansSeptembre2011Table des matires1 Introduction 41.1 Un exemple : le calcul de

x . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 Interpolation et extrapolation 52.1 Linterpolation polynomiale. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82.2 Autres fonctions dinterpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.3 Extrapolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122.4 Interpolation en plusieurs dimensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 Diffrentiation numrique 133.1 Estimation de la drive premire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133.2 Estimation de la drive seconde. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153.3 Driver dans la pratique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163.3.1 Sif (x) est donne par un tableau de valeurs . . . . . . . . . . . . . . . . . . . . . . . . 163.3.2 Sif (x) est donne par son expression analytique . . . . . . . . . . . . . . . . . . . . . 163.3.3 Impact du bruit sur la drivation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174 Intgration numrique 194.1 Mthodes simples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204.2 Mthodes composes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214.3 Autres mthodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224.4 Lintgration dans la pratique. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225 Recherche des racines dune fonction 255.1 Mthode de la bisection ou de la dichotomie. . . . . . . . . . . . . . . . . . . . . . . . . . . . 255.2 Mthode de la Regula falsi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275.3 Mthode de la scante . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295.4 Mthode de Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305.5 La recherche de racines dans la pratique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326 Intgration dquations diffrentielles 336.1 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 336.2 Les mthodes dEuler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 356.3 Stabilit des mthodes dEuler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366.4 Mthodes de Runge-Kutta. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 376.5 Lintgration dans la pratique. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 396.6 Intgrer lorsque lordre >1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 406.7 Intgrer en prsence de conditions de bord . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 412Ce fascicule est unsupport au cours danalyse numrique Il aborde : linterpo-lation, la drivation et lintgration numriques, la recherche de racines dunefonction et lintgration dquations diffrentielles. Deux autres chapitres delanalyse numrique (algbre linaire et optimisation) seront abords dans lecours de Nathalie Brun-Huret.Les applications se feront avec le logiciel Scilab (unclone gratuit de matlab),dontladocumentationetlessourcespeuventtretlchargesladressehttp://www.scilab.orgQuelques rfrences utiles disponibles la BU sont :J.-Ph. Grivet, Mthodes numriques appliques, EDPSciences, 2009 (trsproche du programme du cours, mais avec un contenu plus riche).A. Fortin, Analysenumrique, PressesInternationalesPolytechniques(bonne introduction, proche des applications).C. Guilpin,Manuel de calcul numrique appliqu, EDP Sciences, 1999(plus complet et plus thorique que le prcdent).W. Presset al., Numerical RecipesinC, CambridgeUniversityPress,3me d., 2007 (LA rfrence sur les outils numriques).Des rfrences sur le logiciel ScilabLe site de Scilab : http://www.scilab.orgB. Pinon, Une introduction Scilab :http://www.iecn.u-nancy.fr/~pincon/scilab/docA4.pdfB. Ycart, Dmarrer en Scilab :http://ljk.imag.fr/membres/Bernard.Ycart/polys/demarre_scilab/P. Depondt, Cours de physique numrique, (excellent cours enligne, mais le niveau est plus proche dun cours de master)http://physp6www.cicrp.jussieu.fr/PF/Accueil/PhysNum.htmPour me contacter : Thierry Dudok de Witemail ddwit@cnrs-orleans.frhttp://lpc2e.cnrs-orleans.fr/~ddwit/enseignement.html31 IntroductionLordinateur est aujourdhui un outil incontournable pour simuler et modliser les sys-tmes,maisilfautencoresavoirexprimernosproblmesenlangageformalisdesmathmatiques pures. Nous sommes habitus rsoudre les problmes de faon ana-lytique, alors que lordinateur ne travaille que sur des suites de nombres. On verra dslors quil existe souvent plusieurs approches pour rsoudre un mme problme, ce quiconduit des algorithmes1diffrents. Un des objectifs de ce cours est de fournir desbases rigoureuses pour dvelopper quelques algorithmes utiles dans la rsolution deproblmes en physique.Un algorithme, pour tre utile, doit satisfaire un certain nombre de conditions. Il doittre :rapide: le nombre doprations de calcul pour arriver au rsultat escompt doittre aussi rduit que possible.prcis:lalgorithmedoitsavoircontenirleseffetsdeserreursquisontinh-rentes tout calcul numrique. Ces erreurs peuvent tre dues la modlisation, la reprsentation sur ordinateur ou encore la troncature.souple : lalgorithme doit tre facilement transposable des problmes diff-rents.1.1 Un exemple : le calcul de

xSurordinateur, ladditiondedeuxentierspeutsefairedefaonexactemaisnonlecalcul duneracinecarre.Onprocdealorsparapproximationssuccessivesjusquconverger vers la solution souhaite. Il existe pour cela divers algorithmes. Le suivantest connu depuis lantiquit (mais ce nest pas celui que les ordinateurs utilisent).Soitxunnombrerelpositifdontoncherchelaracinecarre.Dsignonspara0lapremire estimation de cette racine, et par 0 lerreur associe.

x =a0+0Cherchons une approximation de 0. Nous avonsx =(a0+0)2=a20+2a00+20Supposons que lerreur soit petite face a0, ce qui permet de ngliger le terme en 20x a20+2a00Remplaons lerreur 0 par un 0, qui en est une approximation, de telle sorte quex =a20+2a001. LemotalgorithmevientdumathmaticienarabeAl-Khwarizmi(VIIIsicle)quifutlundespremiersutiliser une squence de calculs simples pour rsoudre certaines quations quadratiques. Il est un des pionniersde lal-jabr (algbre).4On en dduit que0=(x/a0a0)/2Le termea1=a0+0=12_xa0+a0_constitueunemeilleureapproximationdelaracinequea0,sousrservequeled-veloppement soit convergent.Dans ce dernier cas, rien ne nousempche de recom-mencer les calculs avec a1, puis a2, etc., jusqu ce que la prcision de la machine nepermette plus de distinguer le rsultat nal de la vritable solution. On peut donc d-nir une suite, qui partir dune estimation initialea0devrait en principe convergervers la solution recherche. Cette suite est :ak+1=12_xak+ak_, a0>0Lalgorithme du calcul de la racine carre devient donc1. Dmarrer avec une premire approximation a0>0 de

x2. A chaque itration k, calculer la nouvelle approximation ak+1=(x/ak+ak)/23. Calculer lerreur associe k+1=(x/ak+1ak+1)/24. Tant que lerreur est suprieure un seuil x, recommencer en 2.Le tableauci-dessous illustre quelques itrations de cet algorithme pour le cas o x =4.i aii0 4 -1.51 2.5 -0.452 2.05 -0.04943 2.00061 -0.0006104 2.00000009 -0.000000093etcNous voyons que lalgorithme converge trs rapidement, et permet donc destimer laracinecarredunnombremoyennantunnombrelimitdoprationslmentaires(additions,soustractions, divisions,multiplications).Il reste encore savoir si cet al-gorithmeconvergetoujourset dterminerlarapiditdesaconvergence.Lanalysenumrique est une discipline proche des mathmatiques appliques, qui a pour ob-jectif de rpondre ces questions de faon rigoureuse.2 Interpolation et extrapolationProblme: Une fonctionf (x) nest connue que par quelques-uns de ses points decolocation :_x0, f (x0)_,_x1, f (x1)_, . . . ,_xn, f (xn)_. Comment fait-on pour valuer cettefonctionf en un x donn, proche des points de colocation?5Danstouteslesexpriencesoonestamenvaluerunefonctionf (x)pourdif-frentesvaleurs dex(parexemple lapressionp(T)en fonctiondelatemprature Tdans une machine thermique) il est fastidieux voire impossible dvaluer une fonctionf (x) pour un grand nombre de valeurs de x. Linterpolation devient ncessaire chaquefois que lon veut estimerf (x) pour une valeur de xautre que celles dont on dispose.Comme nous le verrons plus bas, linterpolation se trouve aussi la base de nombreuxalgorithmes.Exemple :Lorsdunbalayagedefrquence, larponseenamplitudedunltrepasse-hautatmesurequelquesfrquencesdiffrentes(cf.tableau ci-dessous).Estimez la frquence decoupuredece ltre, sachant que lafonctionde transfert dultre varie rgulirement avec la frquence. Il faut donc interpoler les donnes et d-terminer quelle frquence correspond le gain de -3 [dB]. La gure 1 suggre que cettefrquence de coupure vaut environfc=6500 Hz.gain [dB] xk-0.39 -1.39 -1.73 -4.01 -3frquence [Hz] f (xk) 2000 4000 4800 7500 ?0 2000 4000 6000 8000 1000065432101?frequence [Hz]gain [dB]FIGURE 1 Les trois mesures ainsi que lemplacement approximatif de la frquence de coupure du ltre,pour un gain de -3 dBAvant dinterpoler ces donnes, il convient dabord dechanger les units : les frquences sont exprimes ici en Hz, mais il est plus com-modedelesconvertirenkHzdesortenepasavoirgrerdesvaleursquiscartent trop de lunit.changer de reprsentation. Notre objectif est en effet dvaluer la frquence pourungaindonn. Il est donc prfrable de traiter la frquence comme une fonctiondu gain ( f = f (g)) plutt que linverse (g =g( f )).6Si onpossde unmodle analytique exact de la fonctionde transfert, il vaut mieux utili-ser celui-ci pour faire unajustement aux donnes et endduire des valeurs interpoles.En labsencedemodleanalytique, leplussimpleconsisteajuster despolynmes.Les polynmes ont en effet lavantage de se calculer aisment et de possder des pro-prits mathmatiques intressantes (dont celle dtre aisment diffrentiables). Nousavons deux options :1. Soit on ajuste un seul polynme lensemble des points de colocation. Ce poly-nme ne pourra pas forcment passer par tous les points. Ce cas est illustr danslagure2(a) ci-dessous.Lepolynmededegr1 (unedroite)nepassepas partous les points et approxime relativement mal les mesures. Le polynme de de-gr2(uneparabole)nepasseluinonpluspartouslespointsmaisdonnedesrsultats visuellement meilleurs. Le polynme de degr 3 passe exactement partous les points.2. Soit on ajuste des polynmes diffrents aux diffrents intervalles, de faon pas-ser par tous les points. Le plus simple consiste relier les mesures par des poly-nmes de degr 1 (= des segments de droite). Linterpolation spline, qui est cou-rammentutilisedanslapratique,consisterelierlespointspardesboutsdepolynmededegr3.Onobtientainsiunefrquencedecoupuredefc = 7196Hz.6 4 2 00246810frequence [kHz]gain [dB](a) mesuresdroiteparabolecubique6 4 2 00246810frequence [kHz]gain [dB](b) mesuresordre 1splineFIGURE2 A gauche : interpolation des donnes par un polynme unique. A droite : interpolation enutilisant des polynmes diffrents pour chaque intervalle.Il reste maintenant savoir si le polynme dinterpolation utilis constitue une bonneapproximationde lafonctionf (x) (dont,rappelons-le,on ne connatque quatre va-leurs), ou sil est possible de faire mieux.Sans perte de gnralit, trions les valeurs des abscisses xide telle sorte que x0 x1. . . xn. Si la valeur de x qui nous intresse se situe dans lintervalle [x1, xn], on parleradinterpolation. Sinon, cestdextrapolationquilsagira.Lextrapolationdunefonc-tion est un tache gnralement beaucoup plus dlicate que linterpolation.7Il nest pas ncessaire que les pivots xisoient quidistants, mme si cela permet davoirdes algorithmes plus rapides.2.1 Linterpolation polynomialeSolution: une des solutions les plus simples consiste faire passer par les points decolocation_xi, f (xi)_ un polynme de degr kpk(x) =a0+a1x +a2x2+. . . +akxktel quepk(xi) = f (xi) i =1, . . . npuis valuer ensuite ce polynme en x. Si ce polynme approxime bien la fonctionf , on peut esprer quef (x) pk(x). Un thorme important dit ici queThorme: Par n +1 pointsdecolocation_xi, f (xi)_, dabscissesdiffrentes(xi =xj i = j ), on ne peut faire passer quun et un seul polynme de degr n.0 1 2 3 4 52101234xf(x) mesuresp4(x)splinelog(x)FIGURE3 Exemple dajustement dune fonctionf (x) =log(x) par un polynme de degr quatre p4(x)et par une fonction spline cubique s(x). La fonctionf (x) nest connue que par cinq points de colocation.Linterpolation est satisfaisante, quelle que soit la fonction choisie. En revanche, lextrapolation scartetrs vite de la valeur exacte, et ce pour tous les polynmes.Par deux points ne passe donc quune seule droite. Par trois points une seule parabole,etc. Il existe diffrentes approches pour construire ces polynmes. Toutes donnent for-mellement le mme rsultat, mais leur utilit pratique varie considrablement (tempsdecalcul,sensibilitauxerreursdarrondi,. . . ).LamthodedeLagrangeestunm-thodesimpleetsystmatiquepourconstruiredespolynmesdedegrquelconque.8Elle nest cependant gure utilise aujourdhui en raison de son cot en temps de cal-cul.Pour une fonction dnie par deux points de colocation uniquement (n =2), lepolynme de Lagrange est de degr 1 et scritp1(x) = f (x0)x x1x0x1+ f (x1)x x0x1x0Onvrie que ce polynme passe bienpar les deux points de colocationpuisquep(x =x0) = f (x0) et p(x =x1) = f (x1).Pourunefonctiondniepartroispointsdecolocation, lepolynmedeLa-grange est une parabole dquationp2(x) = f (x0)(x x1)(x x2)(x0x1)(x0x2)+ f (x1)(x x0)(x x2)(x1x0)(x1x2)+ f (x2)(x x0)(x x1)(x2x0)(x2x1)Pour une fonction dnie par n +1 points de colocation, lexpression gnraledu polynme de Lagrange de degr n scritpn(x) =n

k=0f (xk)Lk(x)o Lk(x) dsigne le polynme de degr nLk(x) =(x x0)(x x1) (x xk1)(x xk+1) (x xn)(xkx0)(xkx1) (xkxk1)(xkxk+1) (xkxn)On vrie que Lk(x) satisfait toujours la conditionLk(xl) =_0 si l =k1 si l =kErreur dinterpolation: linterpolationpolynomialepeutaismentgnrerdesvaleurs absurdes, si elle nest pas effectue correctement. Il est donc essentiel de quan-tier lerreur dinterpolation pour interprter les rsultats.En analyse numrique , il est gnralement impossible de connatre exactement lerreur.En effet, si tel tait le cas, alors la solution exacte serait elle aussi connue. En revanche,il est souvent possible destimer lordre de grandeur de lerreur et de savoir comme cettedernire se comporte dans diffrentes conditions. Cette information est ncessaire (maisnon sufsante) pour valuer la abilit dune mthode.Appelons n(x) lcart ou erreur dnie parf (x) =pn(x) +n(x)Tout le problme consiste estimer lerreur sans disposer de la valeur def (x) en toutx. On supposera dans ce qui suit que les valeurs des points de colocation sont connues9exactement,cequinestpastoujoursvraidanslapratique.Lethormesuivantestalors utileThorme : Soit un ensemble de n + 1 points de colocation {_x0, f (x0)_,_x1, f (x1)_, . . . ,_xn, f (xn)_}. On suppose que la fonctionf (x) est dnie dans lintervalle[x0, xn] et quelle est (n +1)-foisdrivable dans lintervalle]x0, xn[. Il existe alors uneabscisse [x0, xn] telle quen(x) =f(n+1)()(n+1)!(x x0)(x x1) (x xn)o lexpressionf(n+1)() dsigne la drive (n +1)-ime def (x), value en une abs-cisse inconnue.Ce thorme nous apprend quelerreur n(x) est dautant plus petite que la fonctionf (x) est "lisse" (ses drivessuprieures restent petites).lerreur n(x) diminue quand x est proche dun des points de colocation. Elle estnaturellement nulle aux points de colocation : n(xi) =0,i =0, . . . , npour un degr n lev, le polynme dans lexpression de lerreur tend osciller,ce qui peut affecter linterpolation.0 2 4 6051015xf(x) mesuresp10(x)FIGURE 4 Exemple dinterpolation avec un polynme de degr 10. Plus le degr est lev, plus le poly-nme a tendance osciller.Lagure4illustrecequisepassequandoninterpoleavecdespolynmesdedegrlev. Non seulement le calcul de ces polynmes de degr lev prsente des instabili-ts numriques, mais en plus on voit apparatre des oscillations indsirables. Augmen-ter le degr du polynme ne fait quamplier ces oscillations. Do la rgle gnrale10Linterpolation polynomiale est dautant plus risque que le degr du po-lynme est lev. En pratique, on ne dpasse rarement le degr trois.Linterpolationest dautant meilleureque lafonction ajuster est rgu-lire (continment drivable).La gure 5 illustre linterpolation dune fonction qui nest pas continment drivable.La discontinuit augmente considrablement lerreur dinterpolation.2 4 6 82024681012xf(x) mesuresp5(x)splinesol. exacteFIGURE 5 Exemple dajustement dune fonction discontinue par un polynme de degr quatre p5(x) etpar une fonction spline cubique s(x). La fonctionf (x) nest connue que par six points de colocation.2.2 Autres fonctions dinterpolationIl existe de nombreuses autres mthodes dinterpolation ainsi que divers algorithmespour le calcul des coefcients des polynmes dinterpolation. Le cas o les pivots sontquidistants se prte videmment le mieux un calcul rapide.Le choix dune mthode est gnralement motiv par un ou plusieurs critres- la simplicit de la programmation- la rapidit de lalgorithme de calcul- la capacit de la fonction dcriref (x)- le proprits analytiques intressantes-lagnralisationplusdedimensions:commentinterpolerunefonctiondeplu-sieurs variables ? . . .Citonsici lesfonctionssplinecubiques, qui sont devenuestrspopulaires. Aulieudefairepasserununiquepolynmededegrlevpartouslespointsdecoloca-tion, onchoisit defairepasserunecubiquediffrenteparchaquepairedepoints11(x0, x1), (x1, x2), . . . , (xn1, xn). Le problme est a priori sous-dtermin, car il existe uneinnit de cubiques pouvant passer par deux points. Toutefois, si onimpose enchaquexila continuit def (x) ainsi que la continuit de la drive premiref (x), la solutiondevient unique. Le rsultat est souvent plus satisfaisant quavec un polynmede La-grange, comme le montrent les gures 3 et 4. Il existe en outre des algorithmes rapidespour le calcul des coefcients des splines.2.3 ExtrapolationLextrapolationest une tche encore bienplus dlicate que linterpolation, car la rapidedivergence des fonctions polynmiales tend rapidement donner des valeurs qui sonttotalementdnuesdesens.Contrairementlinterpolation, ilestindispensablededisposer dun modle analytiquede la fonction tudier si on veut extrapoler celle-ci.Sans un tel modle, lextrapolation sera peu crdible.1800 1900 2000 21000510152025anneeeffectif [milliard] mesuresp5(x)splineexponentielleFIGURE 6 Extrapolation de leffectif de la population mondiale jusquen 2100.Exemple :Letableauci-dessousdonnequelquesvaleursdelapopu-lationmondiale. Diffrenteshypothsesdefconditdonnentdesextra-polationsfort diffrentes. Selonlescnariomalthusien(tauxdenatalitconstant), la concentration devrait continuer de crotre de faon exponen-tielle n(t) =n0et /. Ce cas est illustr par la courbe en traitill dans la gure6. Une rduction progressive de ce taux permettrait au contraire de stabili-ser leffectif. Les extrapolation polynomiales dans la gure 6 ne sappuientsur aucun modle et nont donc aucune valeur, mme si le hasard veut quele modle spline soit en bon accord avec le modle mathusien pour le sicle venir.12anne t 1804 1927 1960 1974 1987 1999effectif n(t) [milliard] 1 2 3 4 5 62.4 Interpolation en plusieurs dimensionsDe nombreuses applications sont de grosses consommatrices dinterpolations plu-sieurs dimensions : les programmes faisant appel des lments nis, la CAO, les lo-giciels utiliss pour gnrer des effets spciaux dans les lms, . . . La plupart des outils(et en particulier les fonctionsspline)peuvent tre gnres plusieursdimensions,au prix dune plus grande complexit.3 Diffrentiation numriqueUne fonctionf (x) continment drivable est connue par quelques-uns de ses pointsdecolocation.Comment fait-on pourvaluer ladrivepremiref (x)et/ou lesd-rivesdordresuprieur ?Cebesoindediffrentiationnumriquesexprimedansdenombreux domaines.Exemple :Latensionauxbornesduncondensateurqui sedchargeest mesure des intervalles rguliers, donnant une suite de valeurs{U0,U1,U2, . . . ,Un}. Pour estimer le courant de dcharge I =CU, il faut dri-ver une fonction dont on ne connat que les points de colocation. Commentprocder ?La solution consiste ici faire passer par les points de colocation un polynme dinter-polation, puis driver celui-ci le nombre de fois ncessaire. On peut ainsi estimer ladrive aux points de colocation ou entre deux.3.1 Estimation de la drive premireLe cas le plus simple est celui o il ny a que deux points de colocation :_x0, f (x0)_ et_x1, f (x1)_. Par ces points passe la droite dquationp1(x) =f (x1) f (x0)x1x0(x x0) + f (x0)Lestimation de la drive premire quivaut donc au coefcient directeur de la droitef (x) p1(x) =f (x1) f (x0)x1x0, x [x0, x1]Notons quelle prend la mme valeur en tout point de lintervalle [x0, x1]. Par ailleurs,la drive seconde et toutes les drives suprieures sont nulles.13Estimationde lerreur : Poursavoirquelleconanceaccorderlexpressionci-dessus, il faut connatre lerreur. Du chapitre prcdent, nous tironsf (x) =pn(x) +n(x) f (x) =pn(x) +n(x)Supposons dornavant que les abscisses des points de colocation sont rgulirementrparties, et appelons h = xi +1xilcartement ou pas entre deux abscisses voisines.On peut alors montrer quen(x) =(1)n f(n+1)()(n+1)!hn, [x0, xn]Lerreurvariedonccomme n(x) hn.Ondiraquelleest dordrenetoncrirafr-quemment de faon abrge n(x) O(hn)Avecdeuxpointsdecolocation, lexpressiondeladrivepremiredordre1peutscrirede deux faonsdiffrentes.Soit on estime la pente dela droitequi passe parlepointdecolocationsuivant(diffrenceavant),soitonprendlapentedeladroitepassant par le point qui prcde (diffrence arrire).f (xk) =f (xk+1) f (xk)h+O(h) diffrence avant dordre 1f (xk) =f (xk) f (xk1)h+O(h) diffrence arrire dordre 1Avec troispointsde colocation,le polynmedinterpolationdevient une parabole.Apartir de cette dernire, on peut valuer la drive premire en chacun des trois pointsf (xk1) =f (xk+1) +4f (xk) 3f (xk1)2h+O(h2) diffrence avant dordre 2f (xk) =f (xk+1) f (xk1)2h+O(h2) diffrence centre dordre 2f (xk+1) =3f (xk+1) 4f (xk) + f (xk1)2h+O(h2) diffrence arrire dordre 2Pourlesdiffrencesdordre2,lerreurvarieasymptotiquementcommeh2alorsquepour les diffrences dordre un, elle varie comme h. Pour une fonctionf sufsammentlisse et pour un petit pas hdonn, la diffrence dordre 2 donnera gnralement uneerreur plus petite.Trois raisons nous poussent prfrer la diffrence centre dordre 2 :1. Dabord, son terme derreur est en O(h2) et non en O(h)2. Un calcul plus dtaill montre ensuite que parmi les trois estimateurs dordre 2,cest la diffrence centre qui possde en moyenne lerreur la plus petite.3. Enn,etcestlunpointcrucial: ladiffrencecentredordre2nencessiteque la connaissance de deux points de colocation. En effet, la valeur du point enlequel onestime la drive nentre pas enjeu. Le cot encalcul est donc identique celui dune diffrence dordre 1, pour un rsultat meilleur.14x0 x1 x2f(x0)f(x1)f(x2)diff. avantdiff. centreediff. arriereFIGURE 7 Illustration des drives avant et arrire dordre 1, et de la drive centre dordre 2 au pointdabscisse x =x1.Exemple: Lestimation de la drive def (x) =1/x en x =2 par diffrentesmthodes donne les rsultats ci-dessous. On constate que pour h sufsam-mentpetit,rduirelepasdunfacteur10revientdiminuerlerreurdunfacteur 10 pourla mthode dordre1 et dun facteur 100pour lamthodede dordre 2. En revanche, pour des grands pas h, la mthode dordre 1 estplus proche de la ralit. La diffrence centre dordre 2 est donc plus int-ressante, condition que le pas soit sufsamment petit, et pour autant quela fonctionf driver soit sufsamment continue.pas diffrence centre diffrence avantdordre 2 dordre 1h f (x =2) || f (x =2) ||1.50000000 -0.57142857 0.32142857 -0.14285714 0.107142861.00000000 -0.33333333 0.08333333 -0.16666667 0.083333330.10000000 -0.25062657 0.00062657 -0.23809524 0.011904760.01000000 -0.25000625 0.00000625 -0.24875622 0.001243780.00100000 -0.25000006 0.00000006 -0.24987506 0.000124940.00010000 -0.25000000 0.00000000 -0.24998750 0.000012500.00001000 -0.25000000 0.00000000 -0.24999875 0.000001253.2 Estimation de la drive secondeLaprocdurerestelammepourlesdrivessecondes,saufquelepolynmedin-terpolation doit tre driv deux fois. Comme ce polynme doit tre au minimum dedegr 2 (sinon sa drive seconde est nulle), on en dduit quil faut au minimum troispoints de colocation.15Pour trois points de colocation, on obtient les expressionsf (xk1) =f (xk+1) 2f (xk) + f (xk1)h2+O(h2) diffrence avant dordre 2f (xk) =f (xk+1) 2f (xk) + f (xk1)h2+O(h2) diffrence centre dordre 2f (xk+1) =f (xk+1) 2f (xk) + f (xk1)h2+O(h2) diffrence arrire dordre 2A titre de comparaison, la diffrence centre dordre 4 scritf (xk) =f (xk2) +16(xk1) 30f (xk) +16f (xk+1) f (xk+2)h4+ O(h4)3.3 Driver dans la pratique3.3.1 Sif (x) est donne par un tableau de valeursSi lafonctiondriverestspciepar unensembledepointsdecolocation(=sonexpressionanalytiquenestpasconnue)alorslepasestimpos.Leseuldegrdeli-bert dont on dispose reste le degr du polynme dinterpolation utilis pour valuerla drive.Augmenter le degrdu polynmepeut sembler intressant, mais nousavonsvu queles polynmes dinterpolation de degr suprieur 3 sont rarement recommandables.Par ailleurs, un telcalcul ncessitera davantage doprations de calcul.3.3.2 Sif (x) est donne par son expressionanalytiqueLa situations est fort diffrente lorsque lexpression analytique de la fonction driverest connue. En effet les points de colocation peuvent alors tre choisis librement et onpeut prendre un pas h aussi petit que souhait.Onpourrait penser quil vaut mieux choisir unpas h trs petit pour augmenter la prci-sion du calcul. Cest souvent vrai. Toutefois, lorsque h devient trop petit, le rsultat estentach par des erreurs darrondi. En effet, suivant le type de fonction driver, il arri-vera un moment o lcartf (x +h) f (x) sera infrieur la prcision du calculateur.Le rsultat sera alors erron.Il existe donc une valeur optimale du pas qui dpendrade la fonctionf (x) driveretdelaprcisionducalculateur.Pourunecalculettedepoche,lavaleurrelativedupas se situera typiquement entre h/x = 102et h/x = 106. Pour un calcul en doubleprcision, le pas relatif pourra parfois descendre jusqu h/x =1012.163.3.3 Impact du bruit sur la drivationLa diffrentiationnumrique est une procdurequi amplie fortement le bruit dansun signal. La gure 8 illustre le cas de la drivation de la fonctionf (x) =sin(x) lorsquecette dernire est affecte par du bruit additif de faible amplitude.0 2 4 6 810.500.51xf(x)f(x)=sin(x) sans bruit0 2 4 6 810.500.51xf(x)=sin(x) avec bruit0 2 4 6 810.500.51xf(x)f(x) sans bruit0 2 4 6 810.500.51xf(x) avec bruitFIGURE8Drivationdelafonctionf (x) =sin(x)avecunlgerbruitadditif(droite)etsansbruitadditif ( gauche). La range de haut reprsente la fonctionf (x) avec ses points de colocation. La rangedebasreprsentelafonctiondiffrencie,avecladriveavantdordre1(traitill),ladrivearriredordre 1 (trait n) et la drive centre dordre 2 (trait pais).Pour rsumer, il est conseill de17Pour les drives dordre 1 et 2, les expressions les plus intressantes sontles diffrences centres dordre 2f (xk) =f (xk+1) f (xk1)2h+O(h2)f (xk) =f (xk+1) 2f (xk) + f (xk1)h2+O(h2)En gnral, plus le terme derreur O(hp) est dordre lev, plus le rsultattendra tre prcis. Mais ceci nest pas toujours vrai lorsque les donnessont affectes de bruit. De fait, les drives dordre suprieur et les expres-sions dordre suprieur 2 sont rarement utilises.A titre dexemple, un programme de calcul simpli de la drive par diffrence cen-tre scrit en Scilab1 function [dydx] = derivee (y,h)23 // y : vecteur de valeurs a deriver4 // h : pas de derivation5 // dydx : difference centree de y(x) (vecteur colonne )67 y = y(:);8 n = length(y);9 dydx = zeros(n ,1);10 dydx(1) = y(2)-y(1);11 dydx(n) = y(n)-y(n-1);12 dydx(2:n-1) = (y(3:n)-y(1:n -2)) / 2;13 dydx = dydx / h;14 endfunctiono y est un vecteur dordonnesobtenuespour des abscisses espaces de h. Voici lamme fonction, crite sous une forme plus compacte1 function [dydx] = derivee (y,h)23 // y : vecteur de valeurs a deriver4 // h : pas de derivation5 // dydx : difference centree de y(x) (vecteur colonne )67 y = y(:); // met y en vecteur colonne8 dydx = [y(2)-y(1); (y(3:$)-y(1:$ -2))/2; y($)-y($ -1)]/h;9 endfunctionSi lexpression analytique de la fonctionf (x) est connue, alors on peut procder diff-remment :181 function [dfdx] = derivee (f,x)23 // f : nom de la fonction a deriver4 // x : vecteur dabscisses ou il faut evaluer la derivee5 // dfdx : valeur de la derivee (vecteur colonne )67 x = x(:); // met x en vecteur colonne8 dx = [x(2)-x(1); (x(3:$)-x(1:$ -2))/2; x($)-x($ -1)]; // le pas9 y = f(x); // evalue en x la fonction dont le nom est dans f10 dfdx = [y(2)-y(1); (y(3:$)-y(1:$ -2))/2; y($)-y($-1)] ./ dx;11 endfunctionIl faut ensuite dnir la fonction driver. Par exemple pourf (x) =xexnous aurionsfunction f = mafonction(x)// definit la fonction dont il faut evaluer la deriveef = exp(-x).*x;endfunctionEt le rsultat sobtient en excutant dans la consolez = derivee(mafonction,x);4 Intgration numriqueLeproblmedelintgrationnumrique(ouquadrature)peutseprsenterdedeuxfaons diffrentes :Problme 1 : Unefonctionf (x)estconnueparquelques-unsdesespointsdecolocation {_xi, f (xi)_}ni =0(qui sont rgulirement espacs ou non). Comment fait-onpour estimer la valeur de lintgrale_xnx0f (x) dx, alorsque lexpression analytique def (x) nest pas connue ?Un exemple : la dcharge dun courant I (t) dans une bobine dinductance Lest tudie en mesurant le courant des intervalles de temps rguliers. Celadonne une suite {I0, I1, . . . , In}. Comment estimer lnergie W =12L_I2dt ?Problme2: On cherche la valeur de lintgralednie_baf (x) dxlorsque lex-pression analytique de lintgrandf (x) est connue, mais non sa primitive.Un exemple : calculer_baex2dx19Solution :Ces deux problmes, pourtant trs diffrents, peuvent tre rsolus avec lesmmes outils. Comme dans le chapitre prcdent, nous interpolons la fonction f (x) ouses points de colocation avec un polynme, puis nous intgrons explicitement ce po-lynme. Nous supposerons dans ce qui suit que la distance entre points de colocationadjacents est constante et vaut h (le pas).4.1 Mthodes simplesCommenons par le cas le plus simple : estimer lintgrale dnie par seulement deuxpoints de colocation (n =1). Par ces deux points passe le polynme de degr 1p1(x) =f (x1) f (x0)x1x0(x x0) + f (x0)Or nous avons_x1x0f (x) dx =_x1x0p1(x) dx +_x1x01(x) dxce qui donne_x1x0f (x) dx =h2_f (x0) + f (x1)_+O(h3)Cette mthode est dite mthode des trapzes puisque laire est approxime par un tra-pze (cf. gure 9).0 2 4 601234xf(x)n=10 2 4 601234xn=2FIGURE 9 Exemple dintgration dune fonction par interpolation avec un polynme du premier et dusecond degr. La valeur de lintgrale correspond laire de la gure en gris.En ajoutant un point de colocation entre les deux premiers, nous pouvons amliorer lersultat et interpoler par une parabole. Cela donne la mthode de Simpson_x2x0f (x) dx =h3_f (x0) +4f (x1) + f (x2)_+O(h5)20Notonsquepourunpashsufsammentpetit, lamthodedeSimpsondonneuneerreurconsidrablementpluspetitequecelledelamthodedestrapzes. Onpeutsupposer que le rsultat samliore davantage en approximant lintgrale avec quatrepoints. Toutefois, pour les raisons voques plushaut, il nest gure recommandderecourir des polynmes de degr plus lev.Commentfaut-il alorsprocderpourintgrerdesfonctionsdonnesparungrandnombre de points de colocation? Au lieu daugmenter le degr du polynme, il suftdappliquersparmentlamthodedestrapzesouseSimpsonchacundesinter-valles. Cela donne les formules dites composes.0 2 4 601234xf(x)trapezes n=60 2 4 601234xSimpson n=6FIGURE10 Exemple dintgration dune fonction avec une mthode compose: la mthode des tra-pzes ( gauche) et celle de Simpson ( droite).4.2 Mthodes composesPour intgrer aveclamthodedes trapzes unefonctiondont les abscisses sont{x0, x1, . . . , xn},ilsuftdappliquersparmentlamthodedestrapzeschaque in-tervalle. Cela donne_xnx0f (x) dx =h2_f (x0) + f (x1)_+h2_f (x1) + f (x2)_+ +h2_f (xn1) + f (xn)_+O(nh3)= h_12f (x0) + f (x1) + f (x2) + + f (xn1) +12f (xn)_+O(nh3)Dans la pratique, les bornes dintgration x0 et xnsont gnralement xes, mais nonle nombre ndintervalles. Cest donc sur ce dernier quil faut jouer pour amliorer laprcision des rsultats. Comment varie le terme derreur en fonction de n ? Nous avonsnh3=n_xnx0n_31n2Lerreur dintgration varie donc comme n2et nous noterons O(n2). Contrairement la drivation, ole paramtre-cl est le pas h, ici nous travaillons plutt sur le nombredintervalles n.21Avec la mthode de Simpson (en prenant des intervalles qui ne se chevauchent pas),on obtient la formule de Simpson compose. Comme chaque intervalle ncessite troispointsdecolocation, lenombrendintervallesdoitobligatoirement trepair. Celadonne_xnx0f (x) dx =h3_f (x0) +4f (x1) +2f (x2) +4f (x3) + +4f (xn1) + f (xn)_+O(n4)4.3 Autres mthodesOnutiliseaujourdhui plus couramment des mthodes adaptatives qui, pour unnombre dintervalles n donn, offrent une erreur plus petite ou bien qui permettent deslectionner le meilleur nombredintervalles (pour une prcision donne) en proc-dant par itrations. La mthode de Rombergconsiste combiner astucieusement uneinterpolation par des polynmes de diffrents degrs pour rduire davantage le termederreur.LesmthodesdequadraturedeGausscherchentminimiserlerreurdin-tgration en choisissant convenablement les abscisses xi(qui ne sont plus forcmentrparties uniformment). Enn, il existe des mthodes spcialement adaptes lint-gration de fonctions qui prsentent des singularits, comme par exemplef (x) =x1/2.4.4 Lintgration dans la pratiqueLesproblmesdintgrationnumriquesontcomparables ceux rencontrsdansladiffrentiationnumrique. Augmenterlenombrendintervalles(lorsquecestpos-sible) amliore gnralement les rsultats. Toutefois, lorsque ndevient trop grand, letemps de calcul devient prohibitif et le rsultat est corrompu par les erreurs darrondi.Suivantletypedefonction,npeutvarierden = 100 106ouplus.Ilexistedesm-thodes qui permettent de dterminer le nombre n optimal de faon rcursive.Exemple de calcul avec un intgrand connuOn cherche la valeur de lintgrale I =_10exdx donnemthode des trapzes mthode de Simpsonn I I 2 0.6452351 -0.0131 0.6323336 -0.0002134 0.6354094 -0.00328 0.6321341 -0.000013610 0.6326472 -0.000526 0.6321209 -0.000000351100 0.6321258 -0.00000526 0.6321209 -0.00000000003511000 0.6321206 -0.0000000526 0.6321209 -0.0000000000000035122On saperoit quen dcuplant le nombre dintervalles, lerreur chute dun facteur 102pour la mthode des trapzes (qui est dordre O(n2)), et dun facteur 104pour la m-thode de Simpson, dordre O(n4). Ceci est illustr dans la gure 11. A prcision com-parable,lamthodedeSimpsonncessitedoncmoinsdeoprationsarithmtiques.Attention:ceciestvraiuniquementpourunnombredintervallesn 1.Quandcenombreestfaible(typiquementn < 10),ilpeutarriverquelamthodedestrapzesoffre un meilleur rsultat.Exemple de calcul avec une suite de points de colocationQuelle est la distance parcourue par un objet dont les mesures de vitesse ont donn ?t [s] 5 6 7 8 9 10 11 12 13v [m/s] 20 19 17 13 8 5 2 1 0On trouve respectivementMthode ordre rsultatMthode des rectangles n185.00 mMthode de trapzes n275.00 mMthode de Simpson n475.33 mDans cet exemple, le rsultat exact nest pas connu car lexpression analytique def (x)ne lest pas non plus.10010210410610151010105100n(n) epsTrapezesSimpsonFIGURE 11 Evolution de lerreur dintgration en fonction du nombre dintervalles n, pour la mthodedestrapzesetcelledeSimpson. Lafonctionintgreestici_0sinxdx.Notezquelerreurcesseduchuter lorsque sa valeur devient comparable la prcision machine. Inutile daugmenter n dans ce cas !23Avant dintgrer une fonction, il faut la visualiser au pralable, an dtermi-nersielleseprtebienuneintgrationnumrique(rgularit,disconti-nuits, singularits,. . . ) et pour estimer le pas.Le pas doit toujours tre choisi h T, o Test lchelle caractristique surlaquelle la fonctionf (x) varie. Pour une fonction priodique, par exemple,Tsera la priode.Les mthodes dintgration classiques sont la mthode des trapzes et cellede Simpson. La seconde offre, temps de calcul quivalent, un rsultat g-nralement meilleur._xnx0f (x) dx =h_12f (x0) + f (x1) + f (x2) + + f (xn1) +12f (xn)_+O(n2)_xnx0f (x) dx =h3_f (x0)+4f (x1)+2f (x2)+4f (x3)+ +4f (xn1)+f (xn)_+O(n4)Un programme de calcul simpli de lintgrale par la mthode des trapzes, lorsquelexpressionanalytiquedelintgrandest connue,estdonnci-dessous.Onpourraitaussi passer le nom de lintgrand comme argument.1 function [y] = trapezes (f,a,b,n)23 // f : nom de la fonction a integrer4 // a : borne inferieure5 // b : borne superieure6 // n : nombre d intervalles7 // y : integrale89 x = linspace (a,b,n+1);10 y = f(x); // evalue en x la fonction dont le nom est dans f11 h = x(2)-x(1); // le pas12 I = (sum(y) - 0.5*(y(1)+y($)))*h;13 endfunctionLa mme fonction, base sur la mthode de Simpson, donne1 function [I] = simpson (f,a,b,n)23 // f : nom de la fonction a integrer4 // a : borne inferieure5 // b : borne superieure6 // n : nombre d intervalles (pair)7 // I : integrale89 n = 2*int(n/2); // garantit que n soit pair10 x = linspace (a,b,n+1);11 y = f(x); // evalue en x la fonction dont le nom est dans f12 h = x(2)-x(1); // le pas13 I = y(1)+y($) + 4* sum(y(2:2:$-1)) + 2*sum(y(3:2:$ -2));2414 I = I*h/3;15 endfunctionPar intgrer, il fait leur fournir lenomdelafonctionqui dnit lintgrand. Parexemple, pour calculer_10ex2dx avec la mthode des trapzes enprenant 400 noeuds,on commence par dnir lintgrandfunction f = integrand(x)// definit lintegrandpour le calcul dintegralef = exp(-x.*x);endfunctionou encore dnir dans la console une fonction avec la commande deffdeff([y]=integrand(x),y=exp(-x.*x))puis dans la console on excute la commandeI = trapezes(integrand,0,1,400)5 Recherche des racines dune fonctionProblme: Une fonctionf (x) connue en chacun de ses points possde une ou plu-sieurs racines (ou zros) { xi| f ( xi) =0}. Comment fait-on pour dterminer ces racines ?Il existe de nombreuses mthodes de recherche de racines. Toutes sont itratives : par-tant dune ou de plusieurs estimations de la racine, ces mthodes convergent en prin-cipeparitrationssuccessives.Leproblmeconsistetrouveruncompromisentrela vitesse (il faut limiter le nombre doprations de calcul) et la abilit (il faut que lamthode converge srement vers la valeur souhaite).Dans la pratique, onest souvent amen alterner diffrentes mthodes enfonctiondescaractristiques de la fonction. Notons aussi que le problme courant de la recherchede zros en plusieurs dimensions {( xi, yi, . . .) | f ( xi, yi, . . .) =0} est nettement plus com-plexe et fait aujourdhui encore lobjet dintenses recherches.5.1 Mthode de la bisection ou de la dichotomieSupposonsquelintervalledanslequelsesituelaracinesoitconnu.Lamthodedelabisectionoffreuneconvergencelentemaissreverslaracine.Cettemthodeestrecommande lorsque la fonction prsente des discontinuits ou des singularits.25Procdure suivre : Laracinesetrouveinitialementdanslintervalledere-cherche [xk, xk+1]. On a doncf (xk) f (xk+1) 0. Lalgorithme devient1. choisir comme nouvelle abscisse xk+2 = (xk+xk+1)/2, le point milieu de linter-valle :2. sif (xk) f (xk+2) 0, la solution se trouve dans lintervalle [xk, xk+2], qui devientalors le nouvel intervalle de recherche3. aucontraire, si f (xk) f (xk+2) 0, lenouvel intervallederecherchedevient[xk+2, xk+1]4. revenir au point 1. jusqu ce quil y ait convergence.0 0.5 1 1.5 2 2.5 3420246xf(x)x0x1x2x3x4 xFIGURE 12 Reprsentation des premires itrations avec la mthode de la bisection pourf (x) =x24.On peut montrer que cette mthode possde une convergence linaire : si k=| x xk|est lcart la k-ime itration entre xket la racine x, alors en moyenne k+1= c k,o 0