Analyse numérique avec Python - normale sup

1 Analyse num rique avec PythonPTSI Lyc e Eiffel22 mai 2014 Retour au Python pour ce dernier gros chapitre de l ann e (untout petit chapitre final seras rement consacr aux rudiments de Scilab), o nous allons tudier ensemble (et programmer enPython) quelques algorithmes classiques d Analyse num rique. Le but est de r soudre des probl mesmath matiques fr quemment rencontr s en mod lisation (donc dans les autres sciences, par exempledes quations diff rentielles), en ne cherchant surtout pas comprendre les math matiques quisontcach es derri re, mais en tentant de trouver une m thode efficace pour d terminer une solutionutilisable en pratique (mais approch e) au probl me donn .On essaiera donc d insister sur le c t num rique de la r solution, en tentant d valuer l efficacit des algorithmes (complexit , pr cision desr sultat obtenus), et les limites des mod les pr sent s (probl mes d arrondis, de validit de certainstests, instabilit num rique).

2 1 R solution approch e d quations du typef(x) = :Quantit de probl mes en mod lisation se ram nent la r solution d quations uneinconnue r elle. Pour en donner un tout fait ordinaire maisfondamentale en physique, on lanceun projectile soumis uniquement la force de gravitation avec une vitesse initiale et une hauteurinitiale donn es, et on souhaite savoir la distance qu il parcourt avant de toucher le sol. Dans samod lisation la plus simple, ce probl me se ram ne la r solution d une quation du second degr .Plus g n ralement, on se placera dans la situation o on dispose des donn es suivantes : une fonctionfcontinue et un intervalle sur lequel elle s annule au moins une fois. une valeur initialex0(qui peut simplement tre une borne de l intervalle). une pr cision souhait e pour la valeur approch e de la R solution m thodes ne nous concernent pas dans ce cours, elles sontplut t du ressort de votre professeurde math matiques.

3 Il faut tout de m me tre conscient que : on ne sait r soudre de fa on exacte que tr s tr s peu d quations (en gros tout ce qui se ram ne une quation du premier ou du second degr ). m me quand on sait le faire, on est confront s des probl mesnum riques. Pour l quationdu second degr , on a besoin de calculer , mais comment effectue-t-on un tel calcul num -riquement ? Ce sera certainement de fa on approch e, et il faut un algorithme pour effectuerle calcul (cf plus bas). m thode a d j t vue dans le chapitre 2. Rappelons qu elle consiste construire deuxsuites(an)et(bn)en partant dea0=aetb0=b(aetb tant les bornes de l intervalle d tude), eten divisant l intervalle en deux chaque tape. Citons simplement le r sultat suivant :Th or me notant une solution de l quationf(x) = 0, par la m thode de dichotomie, onaura toujours|an |6|b a| peut donc ma triser facilement la pr cision de l appriximation lorsqu on utilise la m thode dedichotomie.

4 Le seul inconv nient est que la m thode est relativement peu efficace. Pour obtenirune pr cision de10chiffres apr s la virgule en partant d un intervalle de largeur1, il faut unebonne trentaine d tapes. On gagne en gros trois chiffres significatifs toutes les10 tapes, puisque1210 11000. Les seuls limites num riques que peut rencontrer cet algorithme sont dues aux nombreuxtests de signe effectu s (un chaque tape), qui peuvent devenir impr cis quand la fonctionfprenddes valeurs tr s proches M thode de principe de la m thode de Newton est le suivant : sous des hypoth ses plus ou moins fortessur la fonctionf(en premi re approximation, on aura besoin quefsoit d rivable sur l intervalled tude), on part d un pointx0, et on construit une suite r currente convergeant vers la solutionde l quation en prenant pourxn+1l abscisse du point d intersection de l axe des abscisses et de latangente la courbe defen son point d abscissexn.

5 La tangente tant proche de la courbe,il parait raisonnable d imaginer que ce point sera relativement proche du point d intersection de lacourbe elle-m me avec l axe des abscisses. Un petit dessin pour illustrer tout a :1201 1 Sur cette figure (qui correspond la fonctionf(x) =x2 2reprise en exemple ci-dessous), on estpartis dex0= 1, et on trouve une bonne approximation de la racine apr s seulement deux g n ralement, la convergence de la m thode de Newton est tr s rapide :Th or me notant la racine recherch e, par la m thode de Newton, on auralog|xn |62nlog(K|x0 a|) log(K), o Kest une constante d pendant defd finie parK=maxI|f |2 minI|f |,I tant l intervalle d dit, l cart entrexnet sera en gros de l ordre de122n, ce qui est gigantesque. chaque tape, la pr cision est doubl e ! Il ne faut que quelques tapes ( peine cinq en g n ral) pour obtenirdes valeurs approch es 10 10pr s l aide de la m thode de Newton.

6 Quels peuvent alors tre lesinconv nients de la m thode de Newton ? Il y en a quelques-uns: Il faut connaitre la d riv ef de la fonctionfpour calculer les termes de la suite r , il faudra approher la valeur def (xn)(on peut calculer une d riv e approch e en cal-culant la pente de la droite reliant deux points de la courbe proches de celui d abscissexn), cequi augmente largement les impr cisions de calcul. La majoration de l cart est beaucoup moins pratique, et constitue un crit re d arr t de l algo-rithme peu performant en pratique (il devient rapidement plus faible que les erreurs d arrondi !).Il vaut mieux prendre un crit re du genre|xn+1 xn|< comme condition d arr t, mais l erreurcommise peut alors tre difficile Surtout, Newton va marcher tr s mal sur des fonctions qui ne sont pas suffisamment r guli resou sur des intervalles trop grands. Notamment, si la d riv edefs annule un endroit, onest en gros danger (ou m me si elle devient trop petite, on risque de sortir de l intervalle).

7 En pratique, Newton marche tr s bien sur une fonction convexe (ou concave) sur un intervalledonn .Exemple pratique : calcul approch de obtenir une valeur approch e de 2, il suffitd appliquer la m thode de Newton la fonctionf:x7 x2 2, en partant d une valeur positive dex0,par exemplex0= 1. L quation de la tangente enxn la courbe def tanty=f (xn)(x xn)+f(xn),on auraxn+1=xn f(xn)f (xn)(la condition revient posery= 0dans l quation pr c dente). Ici,f (x) = 2x, et on obtient simplementxn+1=xn x2n 22xn=xn2+1xn. Un programme Python tr ssimple appliquant la m thode de Newton dans ce cas est le suivant (on donne comme argument lavaleur initiale et le nombre d it rations souhait ) :> def Newton(x,n) :>a=x>for i in range(n) :>a=a/2+1/a>return aTerminons avec un petit tableau r capitulatif des performances de nos deux algorithmes. gauche,la dichotomie a t effectu e partir dea0= 1etb0= 2, droite Newton a t effctu en partantdex0= les d cimales affich es pour Newton quandn= 4sont d j exactes, elle ne bougent M thode de la s canteIl existe des m thodes plus ou moins proches de la m thode de Newton, vitant de devoir connaitrela d riv e pour calculer la valeur approch e de la racine.

8 Parmi celles-ci, la m thode de la s canteconsiste partir de deux points, tracer la droite reliant les deux points correspondants sur la courbedef, et remplacer le premier des deux points (plus g n ralement l avant-dernier point calcul ) parl abscisse du point d intersection de cette droite avec l axe des abscisses. Cette m thode est moinsbonne que Newton, mais pas D j disponible en PythonComme pour tous les algorithmes de ce chapitre, nous ne ferons que r impl menter des fonctionsd j existantes en Python . Sans faire une description de ce qui existe d j , je vous donnerai chaque fois les modules Python contenant les fonctions utiles, et libre vous d aller en regarder lesfonctionnalit s pr cises de plus pr s, puisque tous les modules sont document s en ligne. Bien s r,cette documentation est en anglais, et pas toujours tr s claire, mais elle indique pour chaque fonctionles arguments et options disponibles, et il faut que vous vous entrainiez utiliser cette les m thodes de r solution approch e d quations, tout se trouve dans le ,qui est lui-m me un sous-module du (gros) module d Analyse num rique scipy.

9 Il contient entre autresles fonctions suivantes :Fonctions utiles du module brentq(f,a,b): d termine une racine de la fonctionfdans l intervalle[a, b]par lam thode de Brent (pas tudi e dans ce cours !). bisect(f,a,b): d termine une racine defdans[a, b]en effectuant une dichotomie. newton(f,x0): d termine une racine par la m thode de Newton ou approch enpartantde x0 (si on donne la d riv e en argument suppl mentaire, c est la m thode de Newtonque nous avons vue qui sera utilis e ; on peut galement donner la d riv e seconde pourqu une m thode encore plus efficace soit mise en oeuvre ; en l absence de d riv e, c estune m thode du type s cante qui sera utilis e). root(fun,x0): d termine une racine de la fonction fun, qui peut ici tre une fonctionde plusieurs variables (des options suppl mentaires permettent de choisir une m thodeparticuli re, mais celles-ci ne sont pas notre programme).2 Int gration num cette section, nous nous int resserons aux algorithmes permettant le calcul num riqued int grales.

10 Il s agit bien s r de faire nouveau du calculapproch , et donc de ne pas utiliser decalcul de primitive, m me si aujourd hui beaucoup de logiciels de calcul formel (et de calculatrices)sont capables de faire de l int gration exacte. Comme dans le cas des quations, il faut de toute fa onavoir conscience qu on ne sait calculer exactement que tr speu d int grales, m me quand elle fontintervenir des fonctions usuelles. Ainsi, la fonctionx7 e x2, d une importance fondamentale enprobabilit s, n admet pas de primitive exprimable l aidedes fonctions usuelles (oui, oui, ce genrede r sultat se d montre !). Le principe g n ral commun aux trois m thodes que nous allons pr senterest simple : d couper l intervalle d int gration en petitsmorceaux, et approcher sur chacun de cespetits intervalles la courbe repr sentative de la fonctionfpar une courbe tr s simple pour laquellele calcul d aire est M thode des de plus simple comme fonction qu une fonction constante ?