Analyse Numerique

Embed Size (px)

Citation preview

Universite Louis Pasteur L2MathematiquesU.F.R. de Mathematique et InformatiqueAnalyse NumeriqueS.Salmon2005-20062Tabledesmati`eres0.1 Quest-ce que lanalyse numerique ? . . . . . . . . . . . . . . . . . . . . . . . . 70.2 Pourquoi un ordinateur fait-il des calculs faux? . . . . . . . . . . . . . . . . . 70.2.1 Ecriture en baseb . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70.2.2 Representation des nombres en machine . . . . . . . . . . . . . . . . . 90.2.3 Erreurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90.3 Quest-ce quun bon algorithme ? . . . . . . . . . . . . . . . . . . . . . . . . . 100.4 A quoi sert lanalyse numerique ? . . . . . . . . . . . . . . . . . . . . . . . . . 100.5 Plan du cours . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100.6 Bibliographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 Resolutiondes equationsnonlineaires 131.1 Position du probl`eme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131.2 Localisation des zeros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131.3 Methode des approximations successives ou methode du point xe . . . . . . 141.3.1 Une methode classique. . . . . . . . . . . . . . . . . . . . . . . . . . . 151.3.2 Methode du point xe . . . . . . . . . . . . . . . . . . . . . . . . . . . 161.3.3 Ordre dune methode . . . . . . . . . . . . . . . . . . . . . . . . . . . 191.4 Methode de Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201.4.1 Convergence de la methode de Newton . . . . . . . . . . . . . . . . . . 211.4.2 Zeros de multiplicitem . . . . . . . . . . . . . . . . . . . . . . . . . . 231.4.3 Test darret des iterations . . . . . . . . . . . . . . . . . . . . . . . . . 231.5 Cas particulier : recherche des racines dun polyn ome . . . . . . . . . . . . . . 241.5.1 Suite de Sturm : localisation des racines . . . . . . . . . . . . . . . . . 241.5.2 Approximation de la plus grande racine . . . . . . . . . . . . . . . . . 241.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262 Normesmatriciellesetconditionnement 272.1 Rappel sur le produit scalaire . . . . . . . . . . . . . . . . . . . . . . . . . . . 272.2 Rappel sur les normes vectorielles . . . . . . . . . . . . . . . . . . . . . . . . . 272.3 Normes matricielles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292.4 Conditionnement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303 Resolutiondesyst`emeslineaires 333.1 Position du probl`eme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333.2 Cas des matrices triangulaires. . . . . . . . . . . . . . . . . . . . . . . . . . . 333.3 Methode de Gauss . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343.4 Strategie de pivot . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3934 TABLEDESMATI`ERES3.5 Co ut de la methode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393.6 Existence de la factorisationLU . . . . . . . . . . . . . . . . . . . . . . . . . 403.7 Cas particulier des matrices symetriques denies positives . . . . . . . . . . . 404 Interpolationpolynomiale 434.1 Position du probl`eme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434.2 Polyn omes de Lagrange . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434.2.1 Decompte doperations . . . . . . . . . . . . . . . . . . . . . . . . . . . 464.3 Dierences divisees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 464.3.1 Cas particulier : points equitablement repartis . . . . . . . . . . . . . 484.4 Estimation de lerreur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 504.5 Interpolation dHermite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 524.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 534.7 La methode des splines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 544.7.1 Interpolation cubique de Hermite. . . . . . . . . . . . . . . . . . . . . 544.7.2 Interpolation spline cubique. . . . . . . . . . . . . . . . . . . . . . . . 545 Integrationnumerique 555.1 Position du probl`eme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 555.2 Formules de Newton-Cotes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 555.2.1 Formules de quadrature de type interpolation. . . . . . . . . . . . . . 555.2.2 Construction des formules de Newton-Cotes . . . . . . . . . . . . . . . 575.2.3 Formules composites . . . . . . . . . . . . . . . . . . . . . . . . . . . . 635.3 Formules de Gauss . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 645.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 676 Derivationnumerique 696.1 Position du probl`eme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 696.2 Approximation de la derivee premi`ere . . . . . . . . . . . . . . . . . . . . . . 696.2.1 Formules `a deux points . . . . . . . . . . . . . . . . . . . . . . . . . . 696.2.2 Formules `a trois points . . . . . . . . . . . . . . . . . . . . . . . . . . . 716.3 Approximation de la derivee seconde . . . . . . . . . . . . . . . . . . . . . . . 716.4 Approximation des derivees dordre superieur . . . . . . . . . . . . . . . . . . 726.5 Methode des dierences nies . . . . . . . . . . . . . . . . . . . . . . . . . . . 726.5.1 Exemples de mecanique . . . . . . . . . . . . . . . . . . . . . . . . . . 726.5.2 Principe de la methode . . . . . . . . . . . . . . . . . . . . . . . . . . 74AResolutionnumeriquedes equationsdierentielles 77A.1 Position du probl`eme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77A.2 Resolution numerique : methode dEuler . . . . . . . . . . . . . . . . . . . . . 78A.3 Methodes `a un pas generique . . . . . . . . . . . . . . . . . . . . . . . . . . . 80A.4 Methodes `a pas multiples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83BAnnee2002-2003 85CAnnee2003-2004 115DAnnee2004-2005 147TABLEDESMATI`ERES 5E Annee2005-2006 1796 TABLEDESMATI`ERESIntroduction0.1 Quest-cequelanalysenumerique ?Les calculatrices et les ordinateurs nous permettent de faire beaucoup doperations et cetr`esrapidement.Maispour quelesmachinessoientcapablesdefairecescalculs, ilfautlesprogrammer ! ...et donc ecrire les programmes. Cest lobjet essentiel de lanalyse numeriquequi sest developpeeaveclapparition des ordinateurs (et qui est alors une specialiterecentedes mathematiques).Mais faire beaucoup doperations ne veut pas dire faire nimporte quoi : les methodes ontun co ut,lie dune part au temps de calcul, ieau nombre doperations elementaires(addi-tions,soustractions,multiplicationsetdivisions)` a faire,etdautrepart ` a lespacememoirenecessaire pour stocker les donnees et les resultats.Par ailleurs, lordinateur ne fait pas de calculs exacts (` a cause du mode de representationdes reels 2 = 1.4142136). Ceci constitue un inconvenient car cela provoque des erreurs dar-rondis et de troncature.Lobjectif de lanalyse numerique est de developper des algorithmes, de les comparer entreeux (cest-`a-diredestimer leurs performances a priori ) et de les etudier an de selectionnerles bons algorithmes.0.2 Pourquoi unordinateurfait-il descalculsfaux ?Tout simplement parce quil ne connat quun nombre ni de nombres ! Par exemple ceuxqui poss`edent un nombre ni donne de chires non nuls apr`es la virgule, or ce nest pas le casde13ou de 2 qui ont un nombre inni de chires non nuls apr`es la virgule.0.2.1 EcritureenbasebLa representationdes nombresquenous utilisonsquotidiennementestlarepresentationen base 10 mais les ordinateurs travaillent en base 2 (representation binaire) ou en base 8 ouencore en base 16.Denition1Ecriture en basebSoitb un entier strictement superieur ` a 1. Pour tout entiern superieur ou egal ` a 1, il existe78 TABLEDESMATI`ERESun unique entierp et des entiersdi(0 i p) compris entre 0 etb 1 avecdp = 0 tels que :n =p

i=0dibinote=dpdp1. . . d0bExemple : En base 10 :234 = 2 102+ 3 10 + 4 100 En base 2 :234 = 2 117= 2 (2 58 + 1)= 2 (2 2 29 + 1)= 2 (2 2 (2 14 + 1) + 1)= 2 (2 2 (2 2 7 + 1) + 1)= 2 (2 2 (2 2 (2 3 + 1) + 1) + 1)= 2 (2 2 (2 2 (2 (2 1 + 1) + 1) + 1) + 1)= 27+ 26+ 25+ 23+ 2.Donc 234 = 111010102. En base 8 :234 = 8 29 + 2= 8 (8 3 + 5) + 2= 3 82+ 5 8 + 2Donc 234 = 3528. En base 16 (on utilise les symboles de 0 ` a 9 plus les lettres A, B, C, D, E, F ) :234 = 16 14 + 10Donc 234 = EA16.On generalise cette ecriture aux nombres reels. Mais attention le nombre de chires apr`esla virgule etant inni la somme va de `ap :Denition2Ecriture en basebSoitb un entier strictement superieur ` a 1. Pour tout reel x non nul, il existe un unique entierp et des entiersdi(i p) compris entre 0 etb 1 avecdp = 0 tels que :x =p

i=dibinote=dpdp1. . . d0, d1. . . dq . . .b0.2. POURQUOIUNORDINATEURFAIT-ILDESCALCULSFAUX? 9Exemple : En base 10 :0.625 = 0 100+ 6 110 + 2 1102+ 5 1103 En base 2 :0.625 = 0.500 + 0.125= 1 12 + 0 122+ 1 123Donc 0.625 = 0.1012.0.2.2 RepresentationdesnombresenmachineDans un ordinateur, les nombres sont representes en virguleottante :Denition3Representationen virgule ottanteSoitx un reel non nul, en virgule ottantex secrit :x = 0.a1. . . aN.bE,avecb Nla base,a = 0.a1. . . aNque lon appelle la mantisse, 0 ai< b, a1 = 0,E Zlexposantcomprisentredeuxentiers met M(m E M)et N Nlenombredechiressignicatifs.N.B:Si E< mouE>M, lereel considerenepeutpas etrerepresenteenvirguleot-tante dans ce syst`eme, lordinateur ne connat alors pas ce nombre, on parle dunderow(siE< m) ou doverow(siE> M).Denition4ArrondiSoitxunreel dontlarepresentationenvirguleottanteest x = 0.a1. . . aNaN+1.bE,silamachine consideree na queNchires signicatifs, il faut denirAr(x) larrondidex :siaN+1 b/2, alorsAr(x) = 0.a1. . . aN.bE+ 0. 0 . . . 0. .N11.bE,siaN+1< b/2, alorsAr(x) = 0.a1. . . aN.bE.N.B : Le casaN+1 = b/2 est arbitraire !Lerreur relative faite est alors :|x Ar(x)||x|b2bN. .precisionmachine0.2.3 ErreursLa premi`ere source derreurs dans les calculs faits par un ordinateur provient donc daborddeserreursdarrondisur lesdonnees. Puisdesoperationseectueessurlesreelsenvirguleottante. Nous ne nous etendrons pas sur ce sujet (voir TAN licence) mais il faut etre conscient10 TABLEDESMATI`ERESquecertainesoperations, telleslasoustractiondedeuxreelsvoisinsparexemple, peut etreune source derreurs non negligeables !ExempleSoitx = 0, 124322.104ety = 0, 123171.104. Le calculdex ysur une machine ` a 4 chiressignicatifs donne Ar(x) Ar(y) = 0, 1243.1040, 1231.104= 0, 11.102, il ne reste alors plusque deux chires signicatifs ! (cest ce que lon appelle lextinctiondechires).0.3 Quest-cequunbonalgorithme ?An de choisir le meilleur algorithme possible, il faut pouvoir les comparer. Un bon algo-rithme est alors un algorithme :1. le moins co uteux possible en place memoire,2. lemoins co uteuxpossibleentemps decalcul : cest-` a-dire qui minimiselenombredoperations necessaires. Cest ce quon appelle un probl`eme de complexite.Un exemple : Calcul dun determinant dune matriceN N.LamethodemathematiquedeCramernecessiteN N! operationselementaires(N!additions et (N1)N! multiplications). Prenons N= 50, sachant que 5050! 15.1055,et quunordinateurpeutfaireenviron20GFlops (ie 20milliards doperations `alaseconde), il faudrait quand meme environ 1050ans pour faire ce calcul.3. le plus stable possible, ie le moins sensibleauxerreurs darrondi quenous venonsdevoquer,4. leplusprecispossible: lasolutionquejobtiensestunesolutionapprochee, jeveuxsavoirsijesuispr`esouloindelasolutionexacte. Cestcequonappellelestimationderreur.0.4 Aquoisertlanalysenumerique ?Lanalyse numerique est donc letude dalgorithmes qui permettront de simuler des probl`emesphysiques sur un ordinateur. Un probl`eme mod`ele est le probl`eme suivant. On se donne unecorde de tension T > 0 attachee `a ses deux extremites et sur laquelle on tire avec une forcefvers le haut. On cherche ` a calculer le deplacement verticalu de la corde. Les physiciens nousdonnent lequation que verieu :___T u

(x) = f(x) x ]0, 1[u(0) = 0.u(1) = 0.A nous de la resoudre !0.5 Planducours1. Resolution des equations non lineaires2. Normes matricielles et conditionnement3. Resolution de syst`emes dequations lineaires4. Interpolation polynomiale et splines0.6. BIBLIOGRAPHIE 115. Integration et derivation numeriques6. Dierences nies0.6 Bibliographie1. Cours de licence de Techniques dAnalyse Numerique de Bopeng Rao (Universite LouisPasteur, Strasbourg).2. Cours de licence de Techniques dAnalyse Numerique de Reinhard Schaefke (UniversiteLouis Pasteur, Strasbourg).3. CoursdanalysenumeriquematricielledeMichel Sala un(ConservatoireNational desArts et Metiers, Paris).4. Initiation ` a lAnalyse Numerique.Auteur : Theodor, Editeur : Masson (epuise mais disponible ` a la librairie du CNAM ouen biblioth`eque).5. Analyse numerique pour ingenieurs (Deuxi`eme edition). Auteur : Andre Fortin, Editeur :Presses internationales Polytechnique.6. Introduction ` a lanalyse numerique, Applications sous Matlab. Auteur : Jerome Bastien,Jean-Noel Martin, Editeur : Dunod.12 TABLEDESMATI`ERESChapitre1Resolutiondesequationsnonlineaires1.1 Positionduprobl`emeSoitunefonctionf : R Rcontinue. Onchercheleszeros(encoreditslesracines)def ie lespoints x Rtelsquef(x)=0. Ceprobl`emeestimportantenparticulierenoptimisationo` uloncherche` a minimiser(oumaximiser)une fonction,caroncherchealorsles points o` u la derivee sannule.Sil existeun intervalle[a, b]telquef(a).f(b)< 0,alors par le theor`emedes valeurs in-termediaires, il existe au moins un zero de f dans lintervalle [a, b]. Si de plus, f est strictementmonotone alorsfest une bijection et ce zero est unique dans [a, b].1.2 LocalisationdeszerosQuellequesoitlamethodeutilisee, il estpreferableavantdechercher leszeros dunefonction, davoir une idee de leur localisation. Une methode simple et ecace pour cela est ladichotomie.On suppose quil existe un intervalle [a, b] tel quef(a).f(b) < 0.Oncalcule alors f_a +b2_et ondeterminelenouvel intervalle contenant laracinesoit_a, a +b2_, soit_a +b2, b_, en regardant le signe des produits f_a +b2_f(a) et f_a +b2_f(b).Onrecommencealorsleprocessussurlintervalledeuxfoispluspetitetainsi desuite. Aubout den iterations de cette procedure la longueur de lintervalle obtenue estb a2n.Apartirdemaintenant, onsupposequef neposs`edequunseul zero(notel)dans[a, b].1314 CHAPITRE1. RESOLUTIONDESEQUATIONSNONLINEAIRES1.3 MethodedesapproximationssuccessivesoumethodedupointxeMis` apartquelquescassimplescommeles equationsduseconddegre, ilestimpossibledexprimer directement les solutions def(x) = 0.Principe de la methode des approximations successivesOn remplace lequationf(x) = 0 par une equation equivalentex = g(x) et on construit lasuite recurrente denie par :_x0xe dans [a, b]xn+1= g(xn),avec lespoir que la suite (xn) converge vers la solution l du probl`eme. Cette methode est diteiterative (par opposition aux methodes dites directes).Interpretation geometrique :Chercherl tel quef(l)=0revient` achercherlintersectiondugraphedefaveclaxedesabscisses.Chercher l tel que g(l) = l revient ` a chercher lintersection du graphe de g avec la droite y = xcest-`a-dire ` a trouver le pointxe deg, do` u le nom de la methode.lCfIntersection du graphe de f et de l`axe des abscisses lCgy=xIntersection du graphe de g et de la droite y=xExemples :On peut remplacer lequationf(x) = 0 par lequationx = x f(x) = g(x) ou parx = x f(x)= g(x), = 0.Questions :1. La suite (xn) converge-t-elle ?1.3. METHODE DES APPROXIMATIONS SUCCESSIVES OUMETHODE DU POINT FIXE152. Si oui, converge-t-elleversl solution du probl`eme ?3. Question danalyse numerique : sil y a convergenceversl, ` a quelle vitesse converge-t-on ? Peut-on estimer lerreur commise sur lapproximation del ?La reponse `a la question 2 est immediate : La reponse `a la question 2 est oui.Sil y a convergence de la suite (xn) denie par :_x0xe dans [a, b]xn+1= g(xn),et quexn [a, b],n N alorsxn tend versl tel queg(l) = l quandn tend vers linni.preuveSoitx = limnxn. Alors :xn+1= g(xn) x = g(x)carg est continue. Donc la limite de (xn) veriex = g(x) et six [a, b] alorsx = l. Donc pour que (xn) converge versl, il sut que (xn) converge et quexn [a, b],n N.1.3.1 UnemethodeclassiqueMethode de la corde(ou methode de Lagrange1)On remplace la courbe par une droite passant par deux points donnes et on approche le pointdintersection de la courbe avec laxe des abscisses par le point dintersection de la droite aveclaxedesabscisses.Onrecommenceaveclenouveaupointcalculeetundes deux pointsdedepart de lalgorithme.Equation de la droite (AB) :y f(a)x a=f(b) f(a)b ax1= a f(a)b af(b) f(a)x2= a f(a)x1af(x1) f(a)soitxn+1= a f(a)xnaf(xn) f(a). .g(xn)ouxn+1= b f(b)xnbf(xn) f(b). .e g(xn)1Joseph-LouisLagrange,francais( ?)neenItalie,1736-181316 CHAPITRE1. RESOLUTIONDESEQUATIONSNONLINEAIRES ABab x1x2Mthode des parties proportionnelles1.3.2 MethodedupointxeSoit la suite recurrente suivante :_x0xe dans [a, b]xn+1= g(xn),(1.1)On suppose queg est une fonction continue, quel [a, b] et quel = g(l) f(l) = 0.Theor`eme1Condition susante de convergence de la methodedu point xe.Si(1) g(x) est strictement contractantei.e 0 L < 1, (x, y) [a, b] |g(x) g(y)| L |x y|.et si(2) x [a, b] =g(x) [a, b]Alors quel que soit x0 [a, b], la suite (xn)nN denie par (1.1) converge vers l unique solutionde lequationl = g(l) dans [a, b].preuveSi x0 [a, b], alorsparlhypoth`ese(2), x1=g(x0) [a, b], x2=g(x1) [a, b], . . . Doncxn [a, b], n N et si la suite converge, elle converge versl = limnxn [a, b], solutiondel = g(l).Si lasuite(xn)nNconverge, alorsl estunique. Eneet, soientl1etl2, limitesde(xn),dapr`es lhypoth`ese (1) :|l1l2| = |g(l1) g(l2)| L |l1l2| avecL < 1,donc|l1l2|(1 L) 0,1.3. METHODE DES APPROXIMATIONS SUCCESSIVES OUMETHODE DU POINT FIXE17soitl1 = l2. Montrons que la suite converge :|xn+1xn| = |g(xn) g(xn1)| L |xnxn1| L2|xn1xn2| . . . Ln|x1x0|Donc en particulier :|xn+pxn| = |xn+pxn+p1 +xn+p1xn+p2 + +xn+1xn| |xn+pxn+p1| + |xn+p1xn+p2| + + |xn+1xn| (Ln+p1+Ln+p2+ +Ln) |x1x0| Ln1 Lp1 L|x1x0| or 0 < 1 Lp 1|xn+pxn| Ln1 L |x1x0|Comme 0 L < 1, limnLn= 0 et limn |xn+p xn| = 0, p N. La suite (xn)nNverie le crit`ere de Cauchy2donc converge. Remarque1 Strictement contractanteimplique continue.Dans lapratique, il faut daborddeterminer lintervallesur lequel lafonctiong estcontractante(si elle lest !) puis eventuellement le reduire pour queg([a, b]) [a, b].Faisons tendrep vers linni dans linegalite de la preuve precedente :|xn+pxn| Ln1 L |x1x0|,on obtient que|l xn| Ln1 L |x1x0|,etqueLn1 Lestuneestimationdelerreurentrelasolutionletlen-i`eme iteredelasuitexn. Donc plusL est proche de 0, plusl est prochedexn.Proposition1Soitgderivable sur [a, b]. Sig

verie maxx[a,b] |g

(x)| = L < 1, alorsgestune applicationstrictement contractantedans [a, b].preuveOn utilise la formule des accroissements nis :g(x) g(y) = g

()(x y) avec ]x, y[,|g(x) g(y)| = |g

()||x y| maxt[a,b]|g

(t)||x y| = L |x y|,o` u 0 L < 1. Remarque2 Cette proposition est bien utile car il est beaucoup plus facile de regarderle max deg

que de verier quegest contractante.2AugustinLouisCauchy,francais,1789-185718 CHAPITRE1. RESOLUTIONDESEQUATIONSNONLINEAIRESAttention:soitlafonctiong(x)=x + 1/xpourx 1.Onag

(x) = 1 1/x2donc|g

(x)| < 1 mais supx1 |g

(x)| = 1 et|g(x) g(y)| < |x y|.Pourtantgna pas de point xe, en eetx = g(x) 1/x = 0 !Proposition2(Admise) Conditionsusante de non interet de la methode du point xeSi g

est continueauvoisinagede l tel que g(l) =l et si |g

(l)| >1, alors quel quesoitx0 [a, b],dierentdel,soitlasuite(xn)nNdeniepar(1.1)neconvergepasversl,soitelle est stationnaireenl`a partir dun certain rang.N.B : On dit alors del quil est un point xe repulsif.Methodologie :Apr`es avoir localise les zeros delafonctionde f dans unintervalledelongueur donnee,onetudielafonctiong. Si gnestpasderivable, oncherche` asavoir directementsi gestcontractanteou non dans lintervalle. Sigest derivable, on etudie sa deriveeg

et on estimeg

(l) :Si |g

(l)|< 1, la methode converge.Il faut alors trouver un intervalle [a, b] dans lequelmaxx[a,b] |g

(x)|< 1 etg([a, b]) [a, b] (il en existe forcementun aussi petit soit-il, cfproposition suivante).Proposition3(Admise)Si |g

(l)| < 1,alorsil existeunintervalle[a, b] contenant lpour lequel la suite denie parx0 [a, b] etxn+1 = g(xn) converge versl.x0x1x2Fig. 1.1 0 g

(l) < 1Si |g

(l)| > 1, on elimine la methode, cf Proposition 2 et Fig. 1.3.Exemples1.3. METHODE DES APPROXIMATIONS SUCCESSIVES OUMETHODE DU POINT FIXE19x0x1x2Fig. 1.2 1 < g

(l) 0 g(x) = x f(x). La condition |g

(l)| < 1 devient |1 f

(l)| < 1. g(x) = xf(x)/. La condition |g

(l)| < 1 devient |1f

(l)/| < 1. Donc il faut choisir proche def

(l).N.B: Lechoix=f

(x)donnelamethodedeNewtonquenousetudieronsparti-culi`erement. g(x) =af(x) xf(a)f(x) f(a)(Lagrange).g

(l) =f(a) + (l a)f

(l)f(a),orf(a) = f(l) + (a l)f

(l) + (a l)22f

(c) pourc ]a, l[. La condition devient donc(a l)2f

(c)2f(a)< 1.1.3.3 OrdredunemethodeDenition5La methode denie parxn+1 = g(xn) est dordrep si |xn+1l||xnl|p= |en+1||en|pa unelimite dans R+quandn tend vers linni.Remarque3Le termeen = |xnl| est lerreur ` aletapen.Dans le cas o` ug estp fois derivable, on a :en+1 = xn+1l = g(xn)g(l) = (xnl)g

(l)+(xnl)22g

(l)+ +(xnl)pp!g(p)(l)+(xnl)pn(xnl)20 CHAPITRE1. RESOLUTIONDESEQUATIONSNONLINEAIRESx0x1x2Fig. 1.3 g

(l) > 1avec limnn = 0, soit,en+1 = eng

(l) +e2n2g

(l) + +epnp!g(p)(l) +epnn(en).Lamethodeest ditedordre psi et seulement si g

(l) =g

(l) = =g(p1)(l) =0etg(p)(l) = 0.En particulier, sig

(l) = 0, la methodeest dordre 1 et ona une convergencedite lineaire.Ce qui est le cas general des methodes daproximations successives.Le rapport |en+1||en| |g

(l)| sappelle le coecient de reduction asymptotique de lerreur.Plus ce rapport est petit, plus vite lerreur decrot.1.4 MethodedeNewton Methode de Newton3On remplace la courbe par la tangente ` a la courbe en un point donne et on approche le pointdintersectionde la courbe avec laxe des abscisses par le point dintersection de la tangenteavec laxe des abscisses. On recommence avec le nouveau point calcule.Equation de la tangente ` a la courbe enA :y f(a)x a= f

(a)3SirIsaacNewton,anglais, 1643-17271.4. METHODEDENEWTON 21 Aa=x0x 1Mthode de NewtonFig. 1.4 Methode de Newtonx1= a f(a)f

(a)x2= x1f(x1)f

(x1)soitxn+1= xnf(xn)f

(xn). .g(xn)Attention :f

(xn) = 0, n N.Soit donc la methode de Newton :___x0xe dans [a, b]xn+1= g(xn) = xnf(xn)f

(xn).(1.2)1.4.1 ConvergencedelamethodedeNewtonTheor`eme2ConvergenceglobaledelamethodedeNewtonSif C2([a, b]) et est telle que1. f(a)f(b) < 02. x [a, b], f

(x) = 0 (stricte monotonie)3. x [a, b], f

(x) = 0 (convexite dans le meme sens sur lintervalle [a, b]),alors x0 [a, b] tel quef(x0)f

(x0)>0, lasuite(xn)nNdeniepar(1.2)convergeverslunique solutionl def(x) = 0 dans [a, b].preuve22 CHAPITRE1. RESOLUTIONDESEQUATIONSNONLINEAIRESLes hypoth`eses (1) et (2) assurent lexistence et lunicite del dans [a, b].xn+1l = xnl f(xn)f

(xn)= xnl +f(l) f(xn)f

(xn)= xnl + (l xn)f

(xn) + (l xn)2f

(n)/2f

(xn)avecn ]xn, l[= (xnl)_1 f

(xn) + (l xn)f

(n)/2f

(xn)_= (xnl)2f

(n)2f

(xn)Si f

(x) et f

(x) ont meme signe sur [a, b], alors quel que soit n 0, xn+1l > 0. Doncla suite (xn)nNest minoree parl.Si f

(x) et f

(x) sont de signe contraire sur [a, b], alors quel que soit n 0, xn+1l < 0.Donc la suite (xn)nNest majoree parl.f

(x) > 0 x0 [a, b] doncf(x0) > 0 par hypoth`ese.f

(x) > 0l < x1 = x0f(x0)f

(x0)< x0donc n N, l < xn.Commef(xn) est du meme signe quef(x0)> 0 (carfne sannule quenl etxn> l),alorsxn+1 = xnf(xn)f

(xn)< xn,donc la suite est decroissante et minoree parl donc convergente.f

(x) < 0l > x1 = x0f(x0)f

(x0)> x0donc n N, l > xn.Commef(xn) est du meme signe quef(x0) > 0, alorsxn+1 = xnf(xn)f

(xn)> xn,donc la suite est croissante et majoree parl donc convergente.f

(x) < 0 x0 [a, b] doncf(x0) < 0 par hypoth`ese.Memes arguments que dans le 1er cas. N.B : Pour une racine multiple, les hypoth`eses de ce theor`eme ne peuvent etre veriees !1.4. METHODEDENEWTON 23Theor`eme3Silest un zero simple, la methode de Newton est dordre2 au moins.preuveOn a que g

(x) =f(x)f

(x)(f

(x))2(si f

existe) donc comme f(l) = 0, on a g

(l) = 0 et la methodeest dordre 2 au moins.g

(x) =[f

(x)f

(x) +f(x)f

(x)](f

(x))22f

(x)f

(x)2f(x)(f

(x))4do` u g

(l) =f

(l)f

(l)(deni carf

(l) = 0 si l est un zero simple). Donc si f

(l) = 0, la methodede Newton est dordre 2 et sif

(l) = 0, la methode de Newton est dordre superieur `a 2. Remarque4Si la methode est dordre2, la convergence est dite quadratique. On a :en+1 = e2ng

(l)2+e2n(en)soit log10 |en+1| = 2 log10 |en| c o` uc = log10 |g

(l)2|, ce qui signie que la pente de lerreurenfonctiondunombrediterationsest de2et qu`achaqueiteration, onmultipliepar2lenombre de chires exacts apr`es la virgule !1.4.2 ZerosdemultiplicitemProposition4Silest un zero defde multiplicitem, la methode iterative___x0xe dans [a, b]xn+1= g(xn) = xnm f(xn)f

(xn).est dordresuperieur ou egal ` a 2.preuveOn resout |f(x)|1/m= 0 qui admetl comme zero simple.g(x) = x f1/m(x)(f1/m(x))

= x f1/m(x)(1/m)f1/m1(x)f

(x)= x m f(x)f

(x).

1.4.3 TestdarretdesiterationsQuelle que soit la methode iterative utilisee, un des points importants de la programmationde ces methodes est le choix du test darret des iterations. Deux solutions :1. |xn+1xn| avec la precision desiree. Mais attention, il peut arriver que |xn+1xn|soit petit sans quil y ait solution au probl`eme de point xe.2. |f(xn)| avec valeur xee. Mais commef(xn) = f(xn) f(l) (xnl)f

(l), cettevaleur depend de |f

(l)| !24 CHAPITRE1. RESOLUTIONDESEQUATIONSNONLINEAIRES1.5 Casparticulier:recherchedesracinesdunpolyn omeDans le cas des polyn omes, on est amene `a se poser deux questions dierentes en fonctiondu probl`eme :1. localiser et trouver toutes les racines dun polyn ome,2. trouver laplusgrandeenmodule.1.5.1 SuitedeSturm:localisationdesracinesOn construit une suite de Sturm4`a laide de lalgorithme dEuclide5pour trouver le PGCDde deux polyn omes. Soit `a trouver les racines du polyn omePn(x).On posef0(x) = Pn(x) etf1(x) = P

n(x), alorsf2(x) = R(x) o` uf0(x) = Qf1(x) +R(x), degR nAlors pour toute valeur initiale x0> 1, la suite de Newton (xn)nN est strictement decroissanteet converge vers1.4JacquesCharlesFrancoisSturm,suisse,1803-18555EuclidedAlexandrie,325-265avantJC( ?)1.5. CASPARTICULIER:RECHERCHEDESRACINESDUNPOLYNOME 25preuveSupposons quePsoitstrictementpositifpourx>1.Dapr`esletheor`emedeRolle6, P

admet (n 1) racines telles que :i+1< i< i, 1 i n 1doncP

> 0 pourx > 1. Dapr`es le theor`eme de Rolle,P

admet (n 2) racines telles que :i+2< i+1< i< i< 1, 1 i n 2doncP

> 0 pourx > 1.x1 = x0P(x0)P

(x0)= x0P(x0) P(1)P

(x0),orP(1) P(x0) = (1x0)P

(x0) + (1x0)2P

(), ]1, x0[. Ce qui donne :x1 = 1 + (1x0)2 P

()P

(x0),or, par hypoth`esex0> 1et>1, doncP

()> 0 etP

(x0)> 0 do` ux1> 1. Et commedautrepart, x0>x1, onpeutmontrerparrecurrenceque(xn)nNdecrotetquelleestminoreepar1doncconvergente. Sa limitenepeut etrequelunique solutiondeP(x) = 0dans [1, x0] (dapr`es le theor`eme (2)) cest-`a-dire1.1P 0 + P

+ P

+ Si lon suppose que Pest strictement negatif pour x > 1, les arguments restent les memes.1P 0 P

P

N.BSoit___x0xexn+1= g(xn) = xnP(xn)P

(xn).Une fois trouvee1, la plus grande racine, on poseP1(x) =P(x)x 1, alorsP

1(x) =P

(x)x 1P(x)(x 1)2, et pour trouver2, on utilise la methode suivante :___x0xexn+1= g(xn) = xnP(xn)P

(xn) P(xn)/(xn1).6MichelRolle,francais, 1652-171926 CHAPITRE1. RESOLUTIONDESEQUATIONSNONLINEAIRESUne fois1, . . . , jtrouvees, on poseP1(x) =P(x)(x 1) . . . (x j), alorsP

1(x) =P

(x)(x 1) . . . (x j) P(x)(x 1) . . . (x j)j

i=11x i, et pour trouver j+1, on utilisela methode suivante :___x0xexn+1= g(xn) = xnP(xn)P

(xn) P(xn)

ji=1 1/(x i).1.6 ConclusionLavantage de la methode du point xe est que si elle converge, elle convergera quelle quesoit la valeur initiale choisie dans lintervalle de convergence. Son inconvenient principal est salenteur de convergence, on peut neanmoins laccelerer (cf TD et TP). La methode de Newtonest plus rapide car la vitesse de convergence est dordre au moins 2 ; la diculte reside dansle choix de la valeur initiale !Les dierentes methodes proposees ont leurs avantages et leurs inconvenients, on choisiracellequi convientlemieuxauprobl`emepose ! Onvoitquil estdoncnecessairedetudiercorrectementlesalgorithmesavantdeselancerdanslaprogrammation !Cestlademarcheobligatoire en analyse numerique.Chapitre2Normesmatriciellesetconditionnement2.1 Rappel surleproduitscalaireSoitE un espace vectoriel sur R. On appelle produit scalaire sur E toute forme bilineairesymetrique, denie positive cest-`a-dire : E E R telle que1. x, y, z E, , R, (x +y, z) = (x, z) +(y, z)x, y, z E, , R, (z, x +y) = (z, x) +(z, y)2. x, y E, (x, y) = (y, x)3. x E, (x, x) 0 et(x, x) = 0 x = 0.2.2 Rappel surlesnormesvectoriellesUne norme vectorielle est une application de: RNR+ telle que1. x = 0 x = 02. R, x RN, x = ||x3. x, y RN, x +y x +y (inegalitetriangulaire).ExemplesPour 1 p < , on denit la normep par :RN x xp = (N

i=1|xi|p)1/p.On retrouve la norme euclidienne pourp = 2.Proposition5Inegalite de Cauchy-Schwarz1x, y RN, |(x, y)| _(x, x)_(y, y) = xy1HermannAmandusSchwarz,allemand,1843-19212728 CHAPITRE2. NORMESMATRICIELLESETCONDITIONNEMENTpreuvePour tout R, on a :0 (x + y, x + y) = (x, x) + 2(x, y) + 2(y, y).Or un trin ome estde signe constantsi et seulement silna aucune racine reellecest-`a-diresi et seulement si son discriminant reduit est negatif, soit :

= (x, y)2(x, x)(y, y) 0.Et cest la relation demandee.Legalitenest possible que six ety sont lies. CorollaireCetteinegalitepermetdedemontrerquepourtoutproduitscalaire, onpeutdenirunenorme : x =_(x, x).preuve1. x = 0 (x, x) = 0 x = 0.2. R, x RN, x =_(x, x) =_2(x, x) = ||x3. x, y RN, x + y2=(x + y, x + y)=(x, x) + 2(x, y) + (y, y) (x, x) +2_(x, x)_(y, y) + (y, y) (_(x, x) +_(y, y))2= (x +y)2

CorollaireSoitA une matrice carree dordreN, symetrique (A =TA) et deniepositive (x RN\ {0} , (Ax/x) > 0) alors xA =_(Ax/x) est une norme.preuve CommeA est denie positive, Aexiste et est `a valeurs positives. Dapr`es le corollaire precedent, il sut de demontrer que lapplication_ : RNRN R(x, y) (Ax/y)denit un produit scalaire.Cest une forme bilineaire, puisque cest le produit scalaire de deux vecteurs de RN.(Ax/y) =TyAx(x/Ay) =T(Ay)x =TyTAx, donc siA est symetrique (x/Ay) =TyAx = (Ax/y).(x, x) = (Ax/x) 0 carA est semi-denie positive et(x, x) = (Ax/x) = 0 x = 0 carA est denie positive.

N.B(x/y) =Tyx =N

i=1xiyi(Ax/y) =TyAx(x/Ay) =T(Ay)x =TyTAx, donc siA est symetrique (x/Ay) =TyAx = (Ax/y).2.3. NORMESMATRICIELLES 29Theor`eme6(Admis)Dans un espace vectoriel de dimension nie toutes les normes sont equivalentesie, R/ x RN, xi xj xi.2.3 NormesmatriciellesDenition6Une norme matricielle est une application, qui ` a une matrice associe un nombrereel positif ou nul, telle que1. A = 0 A = 02. R, A RNN, A = ||A3. A, B RNN, A +B A +B (inegalite triangulaire).4. A, B RNN, A.B AB.Denition7Une norme matricielle Met une norme vectorielle Vsont dites com-patibles si et seulement si :A RNN,x RN,AxV AMxV .Proposition6A partir de toute norme vectorielle V , on peut denir une norme matri-cielle Mcompatible, dite la norme matricielle subordonnee `a la norme vectorielleparAM= supxRN\{0}AxVxV.preuveA(x)VxV= ||AxV||xV= AxVxVx = 0,doncsupxRN\{0}AxVxV= supxV =1AxVxV.Or la sph`ere unite est un ensemble ferme borne et la norme est une fonction continue. Doncle supremum existe et est atteint sur la sph`ere, donc cette norme Mest bien denie.A, B RNN, A.B = supxRN\{0}ABxVxV= supxRN\{0}A(Bx)VBxVBxVxV supyRN\{0}AyVyVsupxRN\{0}BxVxV AB La compatibilite est evidente. Remarque5Pour toute norme matricielle subordonnee M: IM= 1.30 CHAPITRE2. NORMESMATRICIELLESETCONDITIONNEMENTExemples Norme de Frobenius2A =_n

i=1m

j=1a2ij =_tr(TAA)N.B : I =n (doncnest pas subordonnee `a une norme vectorielle). Normes matricielles subordonnees aux normes vectorielles :A1 = sup1jmn

i=1|aij|A =sup1inm

j=1|aij|A2 = supx=0Ax2x2=_(TAA)o` u est le rayon spectral deA ie(A) = maxi |i| o` ui est valeur propre de A.2.4 ConditionnementOn consid`ere le syst`emeAx = b o` uA est inversible. Dans la pratique,b peut etre entachederreur (erreur de mesures, erreurs darrondi. . . ) et le syst`eme `a resoudre devient :Ay = b + b avecy = x + xLe but estde mesurer lerreur relativecommise surx, i.exxen fonctiondes donnees duprobl`eme : bb .A(x + x) = b + bAx +Ax = b + b orAx = bAx = bx = A1bx = A1b A1bxx A1

bxCommeAx = b, b A x, on obtient :xx A1A. .=Cond(A)bbLe conditionnement deA, note Cond(A), donne une estimationde lamplicationde ler-reur commise surx par rapport ` a lerreur sur les donneesb.2FerdinandGeorgFrobenius,allemand,1849-19172.4. CONDITIONNEMENT 31Si Cond(A) est petit, on dit que la matrice est bien conditionnee et lerreur commise sur xest du meme ordre de grandeur que celle commise sur les donnees b. Inversement, si Cond(A)estgrand,onditquelamatriceestmal conditionneeetlerreurcommisesurxestplusgrande que lerreur commise sur les donneesb.Proprietes :1. Cond(A) = Cond(A1)2. Cond(A) = Cond(A), R3. La matrice identite est la matrice la mieux conditionnee :A1A = I = 1.4. 1 = I = A1A A1 A = Cond(A).32 CHAPITRE2. NORMESMATRICIELLESETCONDITIONNEMENTChapitre3Resolutiondesyst`emeslineaires3.1 Positionduprobl`emeOn cherche ` a resoudre un syst`eme lineaire dequations, ie on cherche le vecteur x RNtelqueAx = b o` uA RNNest une matrice carree, supposee inversible (detA = 0) etb RNun vecteur donne.Ce probl`eme est un des plus importants de lanalyse numerique, nous allons voir une methodepour le resoudre mais il en existe beaucoup dautres.3.2 CasdesmatricestriangulairesSoit le syst`eme suivant `a resoudre :___a11x1= b1a21x1+ a22x2= b2.........an1x1+ an2x2+ + annxn= bnCe syst`eme equivaut ` a trouverx vecteur de RNtel queAx = b avec :Ax =_____a11a21a22......an1an2. . . ann__________x1x2...xn_____=_____b1b2...bn_____Comme la matrice est triangulaire inferieure, detA = ni=1aii, cette matrice est inversiblesi et seulement si aii = 0, i 1, 2, . . . , n. Le vecteur x sobtient facilement par une descente :___x1= b1/a11x2= (b2a21x1)/a22...xi= (bi

i1j=1aijxj)/aii...xn= (bn

n1j=1aijxj)/ann3334 CHAPITRE3. RESOLUTIONDESYST`EMESLINEAIRESComptons le nombre doperations necessaires `a une descente :pour le calcul dexi : (i 1), (i 2) + 1, 1/, donc au totaln

i=12(i 1) +n = 2n1

i=0i +n = n(n 1) +n n2operations.Soit maintenant le syst`eme suivant `a resoudre :___a11x1+ a12x2+ + a1nxn= b1a22x2+ + a2nxn= b2.........annxn= bnCe syst`eme equivaut ` a trouverx vecteur de RNtel queAx = b avec :Ax =_____a11a12. . . a1na22. . . a2n......ann__________x1x2...xn_____=_____b1b2...bn_____Commelamatriceesttriangulairesuperieure, detA=ni=1aii, cettematriceestinver-siblesietseulementsi aii = 0, i 1, 2, . . . , n.Levecteurxsobtientfacilementparuneremontee :___x1= (b1

nj=2aijxj)/a11x2= (b2

nj=3aijxj)/a22...xi= (bi

nj=i+1aijxj)/aii...xn= bn/annComptons le nombre doperations necessaires `a une remontee :pour le calcul dexi :n (i + 1) + 1 = (n i), (n i), 1/, donc au totaln

i=12(n i) +n = 2n

i=1n n

i=1i +n = 2n2n(n + 1) +n n2operations.3.3 MethodedeGauss(Gauss1)Commelessyst`emestriangulairessontfacileseteconomiques ` aresoudre, lobjectif estdetransformer tout syst`eme lineaire en syst`eme triangulaire equivalent.1JohannCarlFriedrichGauss,allemand,1777-18553.3. METHODEDEGAUSS 35Soit ` a resoudre le syst`emeAx = b, on suppose quea11 = 0 :___a11x1 +a12x2 + +a1nxn= b1a21x1 +a22x2 + +a2nxn= b2......an1x1 +an2x2 + +annxn= bnL1 L1L2 L2a21a11L1...Ln Lnan1a11L1___a11x1+ a12x2 + +a1nxn= b1a(2)22 x2 + +a(2)2nxn= b(2)2......a(2)n2x2 + +a(2)nnxn= b(2)no` u pour 2 i n :a(2)ij= aijai1a11a1j,b(2)i= b(1)iai1a11b1,Interpretation matricielleSoit la matriceL(1)telle que :L(1)=___________1 0 . . . 0a21a111a31a110............ 0an1a110 . . . 0 1___________alors le calcul deL(1)b etL(1)A donne :L(1)b =_____________b1a21a11b1 +b2...ai1a11b1 +bi...an1a11b1 +bn_____________= b(2)L(1)A =__________a11a12. . . a1n0 a22a21a11a12. . . a2na21a11a1n0 a32a31a11a12. . . a3na31a11a1n.........0 an2an1a11a12. . . annan1a11a1n__________= A(2)36 CHAPITRE3. RESOLUTIONDESYST`EMESLINEAIRESDonc on a :Ax = b L(1)Ax = L(1)b A(2)x = b(2).A letape (r)On a eliminex1des equations 2 `an,x2des equations 3 `an etxr1 des equationsr `an. Onsuppose quea(r)rr , que lon appelle le pivot, est non nul.___a(1)11 x1 +a(1)12 x2+ . . . + a(1)1nxn= b(1)1... =...a(r1)r1r1xr1+ a(r1)r1r xr +. . . + a(r1)r1nxn= b(r1)r1a(r)rr xr +. . . + a(r)rnxn= b(r)ra(r)r+1rxr +. . . + a(r)r+1nxn=...... =...a(r)nrxr +. . . + a(r)nnxn= b(r)nL1 L1...Lr1 Lr1Lr LrLr+1 Lr+1a(r)r+1ra(r)rrLr...Ln Lna(r)nra(r)rrLrOnobtient alorslamatrice A(r+1)etlevecteur b(r+1)tels que: pour r + 1 i netr + 1 j n :a(r+1)ij= a(r)ija(r)ira(r)rra(r)rj,b(r+1)i= b(r)ia(r)ira(r)rrb(r)r,Interpretation matricielleSoit la matriceL(r)telle que :L(r)=___________________1 0 . . . . . . . . . 00 1 . . . . . ....... 0... . . .......... 1 . . .......... a(r)r+1ra(r)rr. . ............. . . .......... . . .... 00 0 a(r)nra(r)rr. . . 0 1___________________3.3. METHODEDEGAUSS 37alors le calcul deL(r)b(r)etL(r)A(r)donne :L(r)b(r)=________________b(1)1b(2)2...b(r1)ra(r)r+1ra(r)rrb(r)r+b(r)r+1...a(r)nra(r)rrb(r)r+b(r)n________________= b(r+1)L(r)A(r)=___a(1)11a(1)12. . . . . . . . . . . . . . . a(1)1n0 a(2)22. . . . . . . . . . . . . . . a(2)2n0 0 a(3)33. . . . . . . . . . . . a(3)3n...... 0... . . . . . . . . .......... . . . 0 a(r)rra(r)rr+1. . . a(r)rn...... . . .... 0 a(r+1)r+1r+1. . . a(r+1)r+1n...... . . .......... . . . a(r+1)r+2n...... . . .......... . . ....0 0 0 0 0 a(r+1)nr+1. . . a(r)+1nn____________________= A(r+1)Donc on a :Ax = b L(r)A(r)x = L(r)b(r)A(r+1)x = b(r+1).Au bout de (n 1) etapes,lesyst`eme est triangulaire superieur. Deplus, lamatriceest inversible(donclesyst`emesoluble)si etseulementsi det(A(n)) =ni=1a(i)ii=0ie si aucundespivots nestnul ! Lamethode de Gauss est donc possible si aucun des pivots rencontres nest nul.On a alors queAx = b A(n)x = b(n)L(n1)A(n1)x = L(n1)b(n) L(n1)L(n2). . . L(1)Ax = L(n1)L(n2). . . L(1)b.Notons U(pourupper) lamatrice A(n)puisquelleesttriangulairesuperieureet L(pourlower)lamatriceL(n1)L(n2). . . L(1)puisquelleesttriangulaireinferieurecommeproduitde matrices elles-memes triangulaires inferieures, on a alors :Ux = LbComme, quel que soit r, detL(r)= 1, les matrices L(r)sont toutes inversibles donc leur produitaussi. NotonsL = L1= L(1)1L(2)1. . . L(n1)1qui est aussi triangulaire inferieure.Ax = b LUx = b.38 CHAPITRE3. RESOLUTIONDESYST`EMESLINEAIRESOn a donc factorise la matriceA en un produit dune matrice triangulaire inferieure et dunematricetriangulairesuperieure. Do` ulautrenom de la methodede Gauss :la factorisationLU. Pour resoudre le syst`eme, il sut maintenant de faire une descente pour resoudre Ly = bpuis une remontee pour resoudreUx = y.Proposition7Linverse dune matriceL(r)est donnee par :___________________1 0 . . . . . . . . . 00 1 . . . . . ....... 0... . . .......... 1 . . ..........a(r)r+1ra(r)rr. . ............. . . .......... . . .... 00 0a(r)nra(r)rr. . . 0 1___________________Proposition8Le produit dune matriceL(r)1par une matriceL(r+1)1est donne par :_____________________1 0 . . . . . . . . . 00 1 . . . . . ....... 0... . . .......... 1 . . ..........a(r)r+1ra(r)rr1 . . .............a(r+1)r+2r+1a(r+1)r+1r+1. . .......... . . . . . .... 00 0a(r)nra(r)rra(r+1)nr+1a(r+1)r+1r+1. . . 0 1_____________________Corollaire1La matriceL est donnee par :______________________1 0 . . . . . . . . . . . . 0a(1)21a(1)111 0 . . . . . . . . ....a(1)31a(1)11a(2)32a(2)22... . . . . . . . . .......... 1 0 . . ..........a(r)r+1ra(r)rr1 0............a(r+1)r+2r+1a(r+1)r+1r+1............ . . . . . .... 0a(1)n1a(1)11a(2)n2a(2)22a(r)nra(r)rra(r+1)nr+1a(r+1)r+1r+1. . .a(n1)nn1a(n1)n1n11______________________3.4. STRATEGIEDEPIVOT 393.4 StrategiedepivotLa methode suppose qu` a chaque etape, lepivot est non nul. Que se passe-t-illorsquonrencontre un pivot nul ?Supposonsquea(r)rr=0, commeAestinversible, onpeuttoujourstrouverdanslasous-colonne r un terme a(r)ir(i > r) non nul. Dans ce cas on permute les lignes i et r de la matrice(attention de ne pas oublier de faire la meme manipulation sur le second membre pour garderlequivalence des syst`emes).Erreurs darrondiSoit ` a resoudre le syst`eme :_ 11 1__x1x2_=_12_La solution est donnee parx1 =11 etx2 =1 21 , ce qui donne pour = 0,x1 = x2 = 1.Or en resolvantce syst`eme par la methode de Gauss avec = 109o` u 109est la precisionde la machine, on obtient :_10910 1 109__x1x2_=_12 109_,or, 1 109 109et 2 109 109sur la machine do` u la solutionx2= 1 etx1= 0 quinest pas la solution !Si par contre, on permute les lignes 1 et 2, on obtient :_1 10 1 109__x1x2_=_21 2 109_,or, 1 109 1 et 1 2 109 1 sur la machine do` u la solutionx2 = 1 etx1 = 1 qui estla solution du syst`eme !Conclusionil nefautpas utiliser des pivots troppetits car les erreursdarrondi peuventdonnerdessolutionsfausses. Oncherchealorsdanslasous-colonner, leplusgrandpivotajr = maxrin |air| et on permute les lignesj etr. Cest ce quon appelle une strategie depivotpartiel. La methode de Gauss nest jamais programmeesans au moins une strategiede pivot partiel.Remarque6 Lespivotspetitsnedisparaissent pas, ilssont justerejetes` alandelalgorithmeo` u leur inuence est moins grande.Si on cherche le plus grand pivot dans la sous-matricer i n etr j n et quonpermute alors ` a la fois les lignes et les colonnes, cest une strategiedepivottotal.3.5 Co utdelamethodeCo ut de letaper :pouri = r + 1 ` an etj = r + 1 ` an,a(r+1)ij= a(r)ijmira(r)rj, r + 1 j n.40 CHAPITRE3. RESOLUTIONDESYST`EMESLINEAIRESsoit (n r)/ et (n r)2fois (1, 1) pour le calcul dea(r+1)ijetpouri = r + 1 ` an,b(r+1)i= b(r)imirb(r)r.soit (n r) fois (1, 1) pour le calcul deb(r+1)i, soit au totaln1

r=1(n r) =n1

r=1r =n(n 1)2divisions,2n1

r=1[(nr)2+(nr)] = 2n(n 1)(2n 1)6+2n(n 1)2= 2n(n21)3additions et multiplications,soitautotal delordrede2n33operations. Il fautrajouterleco utdunedescenteetduneremontee ie2n2qui devient vite negligeable d`es quen est grand.3.6 ExistencedelafactorisationLUTheor`eme7SoitA une matrice carree dordren ayant toutes ses sous-matrices principales

Ak=(aij)1i,jkreguli`eres ( ieinversibles). Alors lamatrice Aadmet uneuniquefacto-risationLUo` uLest triangulaireinferieureavecdes1surladiagonaleet Utriangulairesuperieure.preuveUnicite SoitA = L1U1 = L2U2do` u U1U12. .triangulaire superieure= L11L2. .triangulaire inferieure= D.CommeD a des 1 sur la diagonale,D = I, doncU1 = U2etL1 = L2.Existence il sut de montrer que a(r)rr= 0 pour 1 r n1. On le demontre par recurrence.Lepremierpivotestforcement nonnul carcestlasous-matrice A1qui estreguli`ereparhypoth`ese.Sia(r)rr= 0 pour 1 r k 1, ona alorsA =L(1)1L(2)1. . . L(k1)1A(k)soit par blocs :

Ak = LkA(k)k, or dune part par hypoth`ese det

Akest dierent de 0 et dautre part det

Ak =a(1)11 a(2)22. . . a(k1)k1k1a(k)kk .Par hypoth`esede recurrencea(r)rr= 0 pour 1 r k 1,donca(k)kkest aussi dierent de 0 Remarque7Cest lavaleursurladiagonaledeLqui donnelunicite. Cettevaleurdoitdonc toujours etre xee.3.7 Cas particulier des matrices symetriques denies positivesRappel Soit Aune matrice symetrique (A =TA) reelle denie positive (x RN\ {0} , (Ax/x) >0) alorsA est inversible et toutes ses valeurs propres sont reelles et strictement positives.preuveSoitx Ker(A),Ax = 0 donc (Ax/x) = 0 x = 0 soitA inversible.Soitx Cnvecteur propre deA associe `a la valeur propre C, alorsAx = x etAx = Ax = x.3.7. CASPARTICULIERDESMATRICESSYMETRIQUESDEFINIESPOSITIVES 41On fait le produit scalaire de la premi`ere egalite parx et de la deuxi`eme parx, on obtient :(Ax/x) = (x/x) = x2et (Ax/x) = (x/x) = x2.Comme (Ax/x) = (Ax/x) carA est symetrique, on a :x2= x2, soit est reel.Enn,0 < (Ax/x) = (x/x) = x2.

Theor`eme8Toute matrice symetrique denie positive admet une unique factorisationLU.preuveSoit Ak, sous-matrice principale dordrek deA. Alors Akest denie positive car(x1x2. . . xk)

AkT(x1x2. . . xk) = (x1x2. . . xk0 . . . 0)AT(x1x2. . . xk0 . . . 0) 0.Donc Ak est inversible et dapr`es le theor`eme (7),A poss`ede une factorisationLUunique. Factorisation de Cholesky2CommeA est symetrique, on aLU=T(LU) =TUTL soitTU1L. .triangulaireinferieure=TLU1. .triangulairesuperieure=_____1/u110 00 1/u22.........0 . . . 1/unn_____.PosonsD=_____u110u22.........0 . . .unn_____ (cequi estpossiblecarAestdeniepositiveetquelesuii> 0).AlorsTLU1=D2, do` uDTL =DD2U=D1U, etdoncA =LD.D1U=LD.DTL =LTL avec L = LD.Corollaire2Toute matrice symetrique denie positive admet une unique factorisationLTL,appelee factorisationde Cholesky.Factorisation de Crout3CommeA = LTL = LD.DD1T(LD) = LD.DD1TDTL = LD.DD1DTL = LD2TL.Corollaire3Toute matrice symetrique denie positive admet une unique factorisation LDTL,appelee factorisationde Crout.Remarque8Pourdesraisonsnumeriques,onpref`ereutiliserlafactorisationdeCrout ` acelle de Cholesky car il ny a pas dextractionde racines carrees.2AndreLouisCholesky,francais, 1875-19183PrescottDurand( ?)Crout,americain( ?)42 CHAPITRE3. RESOLUTIONDESYST`EMESLINEAIRESChapitre4Interpolationpolynomiale4.1 Positionduprobl`emeSoient(xi, yi), i=0, . . . , n, n + 1couplesdevaleursreelles. Lebutdetoutprobl`emedinterpolation est de determiner une fonctiong simple, telle que :g(xi) = yi, i = 0, . . . , n.Les points (xi, yi) sont appeles les points dinterpolation. Linterpolation polynomiale consiste`a chercher la fonctiong sous la forme dun polyn ome.Exemple dutilisationEn physique, on mesure experimentalementla temperature dun objet qui refroidit au coursdu temps. On obtient une suite de valeurs ` a dierents tempsti. On cherche alors ` a tracer lacourbe derefroidissementla plus prochepossible des pointsmesures,etainsi`a estimerdesvaleurs de la fonction en des points non mesures (cf Fig 4.1).Exemple le plus simple : interpolation lineaireOn remplace la courbe defpar la droite passant par (xi, f(xi)) et (xi+1, f(xi+1)) :p(x) = f(xi) +f(xi+1) f(xi)xi+1xi(x xi)Voici lecalcul parinterpolationlineairedesnotes depresenceauxTPsMaple: 0si pasdabsence, 20 si presence `a toutes les seancessauf 1 cest-`a-dire` a 11 seances.On peut alorsfacilement obtenir la note de presence dun etudiant venu ` a 5 seances, cest environ 9 (cf Fig4.2).4.2 Polyn omesdeLagrangeSoient(xi, yi), i = 0, . . . , n, n + 1pointsdinterpolation.Existe-t-il unpolyn omePtelqueP(xi) = yi, i = 0, . . . , n?Theor`eme9Si lesxisont tous distincts alors il existe un unique polyn omePnde degre auplusn tel quePn(xi) = yi, i = 0, . . . , n.4344 CHAPITRE4. INTERPOLATIONPOLYNOMIALE00.20.40.60.812 4 6 8 10Fig. 4.1 Les points mesures (croix), la fonction (en pointilles) et le polyn ome dinterpolation(en trait plein).preuveUnicite : SoientPnetQn deux polyn omes de degre inferieur ou egal `an tels que :Pn(xi) = Qn(xi) = yi, i = 0, . . . , n.NotonsRn =Pn Qn, ce polyn ome est de degre inferieur ou egal`an, et poss`ede au moinsn + 1 racines (lesxi, i = 0, . . . , n), ce qui signie queRn ne peut etre que le polyn ome nul.Existence (demonstration constructive)On commence par chercher des polyn omesLkde degren tels queLk(xi) = ik =_1 sii = k0 sinon, i = 0, . . . , n.AlorsLksannule enx0, x1, . . . , xk1, xk+1, . . . , xn doncLi secrit :Lk(x) = (x x0)(x x1) . . . (x xk1)(x xk+1) . . . (x xn)(N.B :Lkest bien de degren).Reste `a trouver. Pour cela, on utilise le fait queLk(xk) doit etre egal `a 1 :Lk(xk) = 1 = (xkx0)(xkx1) . . . (xkxk1)(xkxk+1) . . . (xkxn),soit =1(xkx0)(xkx1) . . . (xkxk1)(xkxk+1) . . . (xkxn).4.2. POLYNOMESDELAGRANGE 4501234567891011121314151617181920y1 2 3 4 5 6 7 8 9 10 11 12xFig. 4.2 Calcul de la note de presence aux TP Maple par interpolation lineaire.DoncLk(x) =(x x0)(x x1) . . . (x xk1)(x xk+1) . . . (x xn)(xkx0)(xkx1) . . . (xkxk1)(xkxk+1) . . . (xkxn)=ni=0i=k(x xi)ni=0i=k(xkxi).On pose alorsPn(x) =n

i=0yiLi(x). CommePn(xk) =n

i=0yiLi(xk) =n

i=0yiik = yk, k = 0, . . . , npar unicite, le polynomePnest le polyn ome cherche. Remarque9 Proposition9LesLk, k = 0, . . . , n formentune base de lespacevec-toriel des polynomesde degre au plusn.preuveIls forment une famille maximale libre car sin

i=0iLi(x) = 0 x R46 CHAPITRE4. INTERPOLATIONPOLYNOMIALEalors,n

i=0iLi(xk) =n

i=0iik = k = 0, k = 0, . . . , n.

Proposition10n

i=0Li = 1.preuvePardenition, lepolyn omeP= ni=0Liestlepolyn omedinterpolationdedegreauplusn tel queP(xi) = 1, i = 0, . . . , n. DoncP 1 est un polyn ome de degre au plusnqui sannule en tous lesxi, i = 0, . . . , n, donc qui poss`eden + 1 racines, ce qui signiequeP 1 ne peut etre que le polyn omenul. 4.2.1 DecomptedoperationsLe calcul dun des polyn omes de Lagrange1de degren necessite :2(n 1) multiplications,2n additions,1 divisionDonc pour calculerPn, les operations necessaires sont :(n + 1) polyn omes de Lagrange(n + 1) multiplications,n additions.ie (2n1)(n+1) multiplications, 2n(n+1) +n additions et (n+1) divisions, soit de lordrede 4n2operations. Ce qui est relativement cher.Onpeutdiminuerdemoitiececo utenre-ecrivant plusastucieusement lespolynomesdeLagrange mais il reste une diculte majeure avec cette methode.Si on veut rajouter un point dinterpolation et chercher le polyn ome de degren+1 qui passepar lesn + 2 points dinterpolation que lon sest donnes, il faut recalculer les polyn omes deLagrangequi ontalorschange ! Do` ulideedecontruirelespolynomesdinterpolationparrecurrence an de minimiser le nombre de calculs si on rajoute ou retire un point.4.3 DierencesdiviseesOn se donne une fonctionfque lon cherche ` a interpoler etn + 1 points dinterpolation(xi, f(xi)), i = 0, . . . , n. On noteyi = f(xi), i = 0, . . . , n.Soit Pn(x) lepolyn omededegre ntel que Pn(xi) =yi, i =0, . . . , net soit Pn1(x) lepolyn ome de degren 1 tel quePn1(xi) = yi, i = 0, . . . , n 1.AlorsPn(x) = Pn1(x) +C(x). DoncC(x) = Pn(x) Pn1(x) est un polyn ome de degre au1Joseph-LouisLagrange,francais( ?)neenItalie,1736-18134.3. DIFFERENCESDIVISEES 47plusn qui sannule enxi, i = 0, . . . , n 1.DoncC(x) = an(x x0)(x x1) . . . (x xn1) do` uPn(x) = Pn1(x) +an(x x0)(x x1) . . . (x xn1).Reste `a calculeran le coecient dominant deC(x).Comme Pn1 est de degre au plus n1, an est le coecient dominant de Pn(x) =n

k=0ykLk(x).Comme chaqueLkest de degre au plusn, cherchons le terme dominant deLk:Lk(x) =(x x0)(x x1) . . . (x xk1)(x xk+1) . . . (x xn)(xkx0)(xkx1) . . . (xkxk1)(xkxk+1) . . . (xkxn)=1(xkx0)(xkx1) . . . (xkxk1)(xkxk+1) . . . (xkxn)xn+. . .Doncan=n

k=0yk(xkx0)(xkx1) . . . (xkxk1)(xkxk+1) . . . (xkxn)=n

k=0f(xk)(xkx0)(xkx1) . . . (xkxk1)(xkxk+1) . . . (xkxn)=n

k=0f(xk)ni=0i=k(xkxi)siyk = f(xk).Ce coecient an est note f[x0, x1, . . . , xn] et est appele la dierence divisee dordre n de f.On denit alors la forme de Newton2progressivedu polyn ome dinterpolation defpar :_P0(x) = f[x0] = y0Pn(x) = Pn1(x) + (x x0)(x x1) . . . (x xn1)f[x0, x1, . . . , xn]et la formedeNewtonregressivedupolyn omedinterpolationdefpar :_P0(x) = f[xn] = ynPn(x) = Pn1(x) + (x xn)(x xn1) . . . (x x1)f[x0, x1, . . . , xn]Proposition11k 1, f[x0, x1, . . . , xk] =f[x1, x2, . . . , xk] f[x0, x1, . . . , xk1]xkx0preuveOn note Pk1(x) le polyn ome de degrek 1 tel que Pk1(xi) =yi, i = 1, . . . , k,Pk1(x) lepolyn omededegrek 1tel quePk1(xi)=yi, i=0, . . . , k 1, etPk(x)lepolyn omededegrek tel quePk(xi) = yi, i = 0, . . . , k.On poseQ(x) =(x x0)Pk1(x) (x xk)Pk1(x)xkx02SirIsaacNewton,anglais, 1643-172748 CHAPITRE4. INTERPOLATIONPOLYNOMIALELe polyn omeQ est de degre au plusk et verie :___Q(xi) =(xix0)Pk1(xi) (xixk)Pk1(xi)x0xk= (xix0)yi(xixk)yixkx0= yi, i = 1, . . . , k 1Q(xk) =(xkx0)Pk1(xk)xkx0= ykQ(x0) =(x0xk)Pk1(x0)xkx0= y0.DoncQ(x) = Pk(x) carPk(x) est unique.OrPk1(x) = Pk2(x) + (x x0)(x x1) . . . (x xk2)f[x0, x1, . . . , xk1]et Pk1(x) = Pk2(x) + (x x1) . . . (x xk1)f[x1, x2, . . . , xk].En identiant les termes de plus haut degre de Q_f[x1, x2, . . . , xk] f[x0, x1, . . . , xk1]xkx0_etdePk(f[x0, x1, . . . , xk]), on obtient exactement la relation cherchee. Exemple dapplication :x0 = 1 y0 = 0x1 = 2 y1 = 3x2 = 3 y2 = 23 02 1= 3 = f[x0, x1]2 33 2 = 1 = f[x1, x2]1 33 2= 2 = f[x0, x1, x2]Formeprogressive :___P0(x) = f[x0] = y0 = 0P1(x) = P0(x) +f[x0, x1](x x0) = 0 + 3(x 1)P2(x) = P1(x) +f[x0, x1, x2](x x0)(x x1) = 3(x 1) 2(x 1)(x 2) = 2x2+ 9x 7Formeregressive :___P0(x) = f[x2] = y2 = 2P1(x) = P0(x) +f[x1, x2](x x2) = 2 (x 3) = x + 5P2(x) = P1(x) +f[x0, x1, x2](x x2)(x x1) = x + 5 2(x 3)(x 2) = 2x2+ 9x 74.3.1 Casparticulier:pointsequitablementrepartisSoientxi = x0 +i h, i = 0, . . . , n etyi, i = 0, . . . , n, n+1 points dinterpolation. Quandon construit la table des dierences divisees, on remarque que les denominateurs sont toujourslesmemes.Ondecidealorsde ne plus faire lesdivisions dans la table,onobtientalorsunetabledesdierencesprogressives-regressives.4.3. DIFFERENCESDIVISEES 49Table des dierences diviseesx0y0x0 +h y1x0 + 2h y2x0 + 3h y3y1y0hy2y1hy3y2hy22y1 +y02h2y32y2 +y12h2y33y2 + 3y1y06h3Table des dierences progressives-regressivesx0y0x0 +h y1x0 + 2h y2x0 + 3h y3y1y0y2y1y3y2y22y1 +y0y32y2 +y1y33y2 + 3y1y0On note loperateur de dierence croissante deni par y0 = y1y0 et loperateurdedierencedecroissante deni par y3 = y3y2. Alors :2y0= y0 = (y1y0) = y1y0 = (y2y1) (y1y0) = y22y1 +y0,3y0= 2y0 = (y22y1 +y0) = y22y1 +y0 = y33y2 + 3y1y0,2y3= y3 = (y3y2) = y3y2 = (y3y2) (y2y1) = y32y2 +y1,3y3= 2y3 = (y32y2 +y1) = y32y2 +y1 = y33y2 + 3y1y0.Do` u lecriture de la table des dierences progressives-regressives :x0y0x0 +h y1x0 + 2h y2x0 + 3h y3y0y2y1y32y02y33y0 = 3y3On denit alors les polyn omes dinterpolation par recurrence sous leur formeprogressive :___P0(x) = f[x0] = y0Pn(x) = Pn1(x) + ny0n!hn (x x0)(x x1) . . . (xxn1)soitPn(x) = y0 + y0h(x x0) + 2y02!h2 (x x0)(x x1) + + ny0n!hn (x x0)(x x1) . . . (x xn1)50 CHAPITRE4. INTERPOLATIONPOLYNOMIALEet sous leur formeregressive :___P0(x) = f[xn] = ynPn(x) = Pn1(x) + (x xn)(x xn1) . . . (x x1)nynn!hnsoitPn(x) = yn + ynh(x xn) + 2yn2!h2(x xn)(x xn1) + + nynn!hn (x xn)(x xn1) . . . (x x1)Exemple dapplication :x0 = 1 y0 = 0x1 = 2 y1 = 3x2 = 3 y2 = 23 0 = 3 = y02 3 = 1 = y21 3 = 4 = 2y0 = 2y2Formeprogressive :___P0(x) = y0 = 0P1(x) = P0(x) + y0h(x x0) = 0 + 3(x 1)P2(x) = P1(x) + 2y02!h2 (x x0)(x x1) = 3(x 1) 2(x 1)(x 2) = 2x2+ 9x 7Formeregressive :___P0(x) = y2 = 2P1(x) = P0(x) + y2h(x x2) = (x 3)P2(x) = P1(x) + 2y22!h2 (x x2)(x x1) = (x 3) 2(x 3)(x 2) = 2x2+ 9x 74.4 EstimationdelerreurSoit une fonctionf: [a, b] R et soientx0, x1, x2, . . . xn [a, b]. SoitPnle polyn omedinterpolation de ftel quePn(xi) = f(xi), i = 0, . . . , n. Que peut-on dire def(x) Pn(x) ?Theor`eme10Soit f Cn([a, b]),derivable(n + 1)foissur]a, b[.Si a x0 0 et comme

ni=0 ni Q(xi) = 0,la formule est fausse pour ce polyn ome de degre 2n + 2.Theor`eme17(Admis) La formule de quadrature ` a (n+1) points est exacte sur IP2n+1si etseulementsilespointsxi, i = 0 . . . n,sonttelsquelepolyn omev(x) = ni=0(x xi)verieuneconditiondorthogonalite `a savoir :_baxqv(x) dx = 0 0 q n.On appelle formule de type Gauss les formules de quadrature :_baf(x) dx =n

i=0(n)if(xi) o` ulesxi sont les zeros dun polyn ome de degren + 1 qui verie la condition dorthogonalite.Theor`eme18Pourf C2n+2([a, b]), lerreur des formules de type Gauss est donnee par:R(f) =_bav2n(x) dx(2n + 2)!f2n+2(), [a, b]preuveOn construit le polyn ome dinterpolation de HermiteP2n+1deni surx0, x1, . . . , xn alors :f(x)P2n+1(x) =(x x0)2(x x1)2. . . (x xn)2(2n + 2)!f2n+2(), a min(x, x0) < < max(x, xn) b.66 CHAPITRE5. INTEGRATIONNUMERIQUEAlors_baf(x) dx _baP2n+1(x) dx =_bav2n(x)(2n + 2)!f2n+2() dx_baf(x) dx n

i=0(n)iP2n+1(xi) =_bav2n(x)(2n + 2)!f2n+2() dx_baf(x) dx n

i=0(n)if(xi) =_bav2n(x)(2n + 2)!f2n+2() dxcarlaformuledequadratureestexactepourlespolyn omesdedegre2n + 1. Onutiliseletheor`eme des valeurs intermediaires comme dans la demonstration de lerreur pour la formuledes trap`ezes, carv2n(x) est de signe constant sur [a, b] et quef2n+2est continue sur [a, b], onobtient donc quil existe [a, b] tel que :R(f) =_bav2n(x) dx(2n + 2)!f2n+2().

Theor`eme19(Admis)LesformulesdetypeGausssontstablesetconvergentespourtoutefonction continue.Remarque15 Convergente signie limnn

i=0(n)if(xi) =_baf(x) dx.LesformulesdetypeGausssont souvent utilespourlesintegralesimpropres conver-gentes.Il existedesformulesdetypeGausso` ulesextremitesdelintervallesont despointsdintegration: formules de Gauss-Radauet Gauss-Lobatto4.Exemple Gauss-Radau ` a 2 points_11f(x) dx = A0f(1) +A1f(x1) +R(f)f 1, R(f) = 0 _111 dx = 2 = A0 +A1.f x, R(f) = 0 _11xdx = 0 = A0 +x1A1.f x2, R(f) = 0 _11x2dx = 2/3 = A0 +x21A1.N.B : Ce syst`eme nest pas un syst`eme lineaire !On obtientA0 = 1/2, A1 = 3/2, x1 = 1/3. La formule (exacte pour le degre 2) est donc_11f(x) dx =12_f(1) + 3f_13__+R(f)4RehuelLobatto,neerlandais,1797-18665.4. CONCLUSION 67Notez la dierence avec_11f(x) dx = A0f(x1) +A1f(x2) +R(f)o` u il y a 4 inconnues !Les 4 equations sont les suivantes :f 1, R(f) = 0 _111 dx = 2 = A0 +A1.f x, R(f) = 0 _11xdx = 0 = A0x1 +A1x2.f x2, R(f) = 0 _11x2dx = 2/3 = A0x21 +A1x22.f x3, R(f) = 0 _11x3dx = 0 = A0x31 +A1x31.do` u :A0x1 = A1x2A1x2(x22x21) = 0De la derni`ere equation on tire : soitA1 = 0,A0 = 2 etx1 = 0 ce qui est impossible puisque23= A0x21 +A1x22,soitx2 = 0,A0 = 0 oux1 = 0 ce qui est impossible,soitx2 = x1.On obtient alors queA0 = A1 = 1 et quex21 = 13.Do` u la formule :_11f(x) dx = f_13_+f_13_+R(f)Les formules de Gauss-Lobatto de degre de precision 3 et 5 sont :_11f(x) dx =13f(1) + 43f(0) + 13f(1) +R(f)_11f(x) dx =16f(1) + 56f_15_+ 56f_15_+ 16f(1) +R(f)5.4 ConclusionLes formules des trap`ezes et de Simpson sont les plus utilisees et souvent sous leur formecomposite. Les formules deGauss sont neanmoins beaucoupplus precises et peuvent delamemefaconetrecomposees. Lintegrationnumeriqueest aussi tr`es utilepour calculernumeriquement des integrales doubles :_11_11f(x, y) dxdy.68 CHAPITRE5. INTEGRATIONNUMERIQUEChapitre6DerivationnumeriqueApplication : methode des dierencesnies6.1 Positionduprobl`emeComme pour lintegrale,on voudrait etre en mesure devaluer numeriquement la deriveedunefonctionqui nest connuequepar ses valeurs enuncertainnombredepoints. Ceprobl`emedederivationnumeriqueesttr`escommuneningenierieetenanalysenumerique(cest la base des methodes de dierences nies).6.2 Approximationdeladeriveepremi`ereSupposons donnee une fonction f susamment derivable sur un intervalle [a, b] de R seule-ment connue de fa con discr`ete iepar ses valeurs en des pointsxi, i = 0, . . . , n.Unedesmethodeslesplusanciennesutilisees pourobtenirdesformulesdederivationnumerique consiste `a construire des quotients dierentiels `a laide de la formule de Taylor.6.2.1 Formules`adeuxpointsOnsupposequelesxisontreguli`erementespaces: xi=x0 + ihetonchercheuneap-proximation def

(x0). Ecrivons un premier developpement de Taylor1dordre 1 defautourdex0:f(x0 +h) = f(x0) +hf

(x0) +h22f

(1), 1 [x0, x0 +h]On obtient :___f

h+(x0) =f(x0 +h) f(x0)happroximation de la derivee premi`ere enx0E = h2f

(1), 1 [x0, x0 +h] erreur commise1BrookTaylor,anglais, 1685-17316970 CHAPITRE6. DERIVATIONNUMERIQUEEcrivons un autre developpement de Taylor dordre 1 defautour dex1:f(x1h) = f(x1) hf

(x1) +h22f

(2), 2 [x1h, x1]On obtient alors :___f

h(x1) =f(x1) f(x1h)happroximation de la derivee premi`ere enx1E =h2f

(2), 1 [x1h, x1] erreur commiseLes formules obtenues sont donc deux approximations de la derivee premi`ere en un pointdonne ie deux discretisations de f

(xi) et lerreur commise ` a chaque fois tend vers 0 commeh. On parle dapproximation dordre 1.Augmentons lordre du developpement de Taylor defautour dex1 :f(x1 +h) = f(x1) +hf

(x1) +h22f

(x1) +h36f(3)(1), 1 [x1, x1 +h]f(x1h) = f(x1) hf

(x1) +h22f

(x1) h36f(3)(2), 2 [x1h, x1]En soustrayant membre `a membre, on obtient :f(x1 +h) f(x1h) = 2hf

(x1) +h36 (f(3)(1) +f(3)(2)).Ce qui donne :___f

hc(x1) =f(x1 +h) f(x1h)2happroximation de la derivee premi`ere enx1E = h212(f(3)(1) +f(3)(2)), 1 [x1, x1 +h], 2 [x1h, x1] erreur commiseLestimation de lerreur se simplie : [x1h, x1 +h]/h212(f(3)(1) +f(3)(2)) = h26f(3)().Laformulecentreeestuneformuledordre2etdoncplusprecisequelesdeuxpremi`eresformules, memesi ellenecessitelaconnaissancedef aumemenombredepoints. Il fautcependant noter que les points utilisessont disposes symetriquementpar rapport ` a celui o` ulon calcule la derivee.Remarque16 SoientP+,PetPcles polyn omesdinterpolationdefcontruitsrespecti-vement sur les pointsx1, x1 +h,x1h, x1etx1h, x1 +h, alors:f

h+(x1) = P

+(x1)f

h(x1) = P

(x1)f

hc(x1) = P

c(x1)6.3. APPROXIMATIONDELADERIVEESECONDE 71Commepourlintegrationnumerique, leprincipeutiliseestderemplacerlafonctionf parson polyn omedinterpolationet de deriver ce dernier.En eet :x1f(x1)x1 +h f(x1 +h)f(x1 +h) f(x1)hDoncP(x) = f(x1) +f(x1 +h) f(x1)h(x x1)OnadoncqueP

(x) =f(x1 +h) f(x1)hetonposef

(x1) P

(x1) =f(x1 +h) f(x1)h.Onpeutverierquelaformulecentreecorrespondaussi ` af

hc(x1)=P

2(x1)o` uP2estlepolyn omededegre2quiinterpolefauxpointsx1 h, x1, x1 + h.Cestdoncenfaituneformule ` a trois points donc une meilleure approximation.6.2.2 Formules`atroispointsIl est possible de developper dautres formules, pour cela il sut decrire un developpementde Taylor defautour dex0avec un pas 2h par exemple :f(x0 + 2h) = f(x0) + 2hf

(x0) + 2h2f

(x0) + 4h33f(3)(1), 1 [x0, x0 + 2h]f(x0 +h) = f(x0) +hf

(x0) +h22f

(x0) +h36f(3)(2), 2 [x0, x0 +h]En combinant ces deux equations de fa con `a faire disparatre la derivee seconde, on obtient :___f

hd(x0) =4f(x0 +h) 3f(x0) f(x0 + 2h)2happroximation de la derivee premi`ere enx0E =h23 (2f(3)(1) f(3)(2)), 1 [x0, x0 + 2h], 2 [x0, x0 +h] erreur commiseOn peut demontrer en utilisant un polyn ome dinterpolation (cf TD) que dans ce cas, lerreurpeut se mettre sous la forme suivante :E =h23f(3)(), [x0, x0 + 2h].6.3 ApproximationdeladeriveesecondePour obtenir une approximation de la derivee seconde, nous procedons de la meme facon,mais `a partir de developpements de Taylor dordre 4 :f(x1 +h) = f(x1) +hf

(x1) +h22f

(x1) +h36f(3)(x1) +h424f(4)(1), 1 [x1, x1 +h]f(x1h) = f(x1) hf

(x1) +h22f

(x1) h36f(3)(x1) +h424f(4)(2), 2 [x1h, x1]72 CHAPITRE6. DERIVATIONNUMERIQUEf(x)dxu(y)0 y1Fig.6.1 Elastiquede tensionxe`a sesdeux extremitesetsoumis `a une forceverticalef(x) donneeApr`es addition, on obtient :___f

hc(x1) =f(x1 +h) 2f(x1) +f(x1h)h2approximation de la derivee seconde enx1E = h224(f(4)(1) +f(4)(2)), 1 [x1, x1 +h], 2 [x1h, x1] erreur commiseLe terme derreur peut se simplier de la meme facon que precedemment : [x1h, x1 +h]/h224(f(4)(1) +f(4)(2)) = h212f(4)().Cetteformuleestdoncdordre2(letermederreurtendvers0commeh2)etesttr`esimportante dans la pratique.6.4 ApproximationdesderiveesdordresuperieurOnpeutevidemmentgeneraliser cetteapprocheetdeterminerdesapproximationsdesderivees dordresuperieur. Maisattention, laderivationnumeriqueestuneoperationtr`esinstable, ietr`es sensible aux erreurs darrondi.6.5 Methodedesdierencesnies6.5.1 ExemplesdemecaniqueOnsupposequunelastiquedelongueur 1et detension >0est xe`ases deuxextremites et est soumis `a une force verticale donneef(x)dx au pointx :On cherche alors le deplacement verticalu(x) au pointx.La theorie de lelasticite (linearisee) nous apprend qualors la fonction u : [0, 1]x u(x) R verie lequation dierentielle suivante :u

(x) = f(x) x [0, 1]6.5. METHODEDESDIFFERENCESFINIES 73et les conditionslimiteshomog`enes :u(0) = u(1) = 0.Le probl`eme que verie la fonctionu(x) est donc un probl`emeauxlimites :___u

(x) = f(x) x =]0, 1[u(0) = 0u(1) = 0(6.1)Remarque17Si u est une solution correspondant ` a une tension , u/2 est alors une solutioncorrespondant`a une tension 2.Les questions que lon se pose ` a partir de ce probl`eme sont les suivantes :1. Existe-t-il unesolutionie unefonctionu: [0, 1] xu(x)Rqui verieceprobl`eme ?2. Si oui, est-elle unique ?3. Que peut-on dire de lapplicationf u?4. Peut-on expliciteru(x) ?Theor`eme20Si f C0([0, 1]), leprobl`eme (6.1) admet unesolutionet uneseule u C2([0, 1]).Lapplicationf u est lineaire.preuveExistence SoitG(x, ) =_x(1 ) 0 x 1(1 x) 0 x 1Alors la fonctionu(x) =_10G(x, )f() dx, 0 x 1 est une fonction C2([0, 1]), solution de(6.1).UniciteSoientu1etu2deux solutions C2([0, 1])de (6.1).Alorsu =u1 u2est C2([0, 1])etest telle que :___u

(x) = 0 x =]0, 1[u(0) = 0u(1) = 0Alorsu(x) = ax +b, a, b R constantes. Mais les conditions aux limites donnenta = b = 0.Doncu1 = u2.LineariteSoientu1etu2deux solutions C2([0, 1])de (6.1)avecrespectivementpour secondmembre f1 etf2. Alors u1 +u2 est solution de (6.1) avec pour second membre f1 +f2. Memeraisonnement avecu, R. Avec ce theor`eme, nous avons repondu ` a 3 questions sur 4 (analyse mathematique du probl`eme).La reponse `a la derni`ere question est NON :on ne pourra pas trouver une formule explicite de la fonction solutionu, on va donc en cher-cheruneapproximationieune approximationdesvaleursdeu(xi)endespointsxidonnes(analyse numerique : choisir la methode dapproximation et faire lanalyse a priori, program-mer la methode et etudier les resultats - analyse a posteriori - ).74 CHAPITRE6. DERIVATIONNUMERIQUE0 Lx x+dxSh(T!Te )Fig. 6.2 Ailette de refroidissementOnetudieladissipationdelachaleurdansunelementderadiateur(ouailette). Onsuppose que lailette, de longueur L, est susamment mince pour considerer que le probl`emeest unidimensionnel (ieque la temperatureTne depend que dex). Lequationdierentielleque verie alorsTest la suivante :kT

(x) +hc(x)pS(T Te) = 0 x =]0, L[o` u k est la conductivite thermique (W/(mKelvin)), hc(x) le coecient surfacique de transfertthermique (W/(m2Kelvin)), p le perim`etre de la surface S (pdx represente la surface laterale)etTe la temperature ambiante.Ennotantu(x) =T(x) Teetenrajoutantlesconditionslimites` asavoirquelailetteestchauee aux deux extremites `a une temperatureT0, le probl`eme secrit :___u

(x) +c(x)u(x) = 0 x =]0, L[u(0) = T0u(L) = T0Ce probl`eme est donc du type suivant qui nous servira de mod`ele :___u

(x) +c(x)u(x) = f(x) x =]0, 1[u(0) = u(1) = (6.2)6.5.2 PrincipedelamethodeOnsuposequedansleprobl`ememod`ele(6.2)f, csontdesfonctionsdonneescontinuesdans [0, 1] avecc(x) 0 x [0, 1]. On cherche ` a trouveru(x), x [0, 1], solution de (6.2).Theor`eme21(Admis) Sous les hypoth`eses donnees, le probl`eme (6.2) a une solution et uneseuleu C2([0, 1]).On subdivise de fa con reguli`ere lintervalle [0, 1]. On appellexi = ih, i = 0 . . . N + 1 lespointsdelasubdivision. Lasubdivisionestappelleemaillageuniformede[0, 1], xi, i=6.5. METHODEDESDIFFERENCESFINIES 750 . . . N + 1 les noeuds du maillageeth =1N + 1le pas du maillage.Le nombre de noeudsdu maillage (N + 2) est destine `a tendre vers linni et donch est amene `a tendre vers 0.Notonsui = u(xi), alorsu0 = etuN+1 = permet de verier les conditions limites. Ilreste `a trouverui, i = 1 . . . N. Ecrivons lequation dierentielle du probl`eme enxi :u

(xi) +c(xi)u(xi) = f(xi) i = 0, . . . NComme les fonctionsc etfsont donnees, on peut calculerc(xi)note=cietf(xi)note=fi.Or on a vu ` a la section precedente que lon pouvait approcher la derivee seconde dune fonctionen un point donne `a laide de la formule :___u

(xi) =u(xi +h) 2u(xi) +u(xih)h2h212u(4)(), [xih, xi +h].u

(xi) =ui+12ui +ui1h2h212u(4)(), [xi1, xi+1].On a alors facilement que :max1iNu

(xi) _ui+1 + 2uiui1h2_h212supx[0,1]|u(4)(x)|.Le membre de droite dans linegaliteprecedente sappelle lerreurdeconsistance.Donc on obtient quil existei [xi1, xi+1], i = 1, . . . , Ntels que :u2 + 2u1u0h2+c1u1= f1h212u(4)(1)u3 + 2u2u1h2+c2u2= f2h212u(4)(2). . .ui+1 + 2uiui1h2+ciui= fih212u(4)(i). . .uN+1 + 2uN uN1h2+cNuN= fN h212u(4)(N)Ce qui donne le syst`eme suivant `a resoudre :1h2____________2 +c1h21 0 0 . . . 01 2 +c2h21 0...0 1 2 +c3h21......... 0 1...... 0............ 10 . . . . . . 0 1 2 +cNh2_______________________u1u2.........uN___________=___________f1 +h2f2.........fN +h2___________h212___________12.........N___________soit un syst`eme de la forme AhU= B+Eh o` u Ah est une matrice tridiagonale symetriqueetEh un vecteur tel que :Eh

h212supx[0,1]|u(4)(x)|,donc qui tend vers 0 commeh2.76 CHAPITRE6. DERIVATIONNUMERIQUETheor`eme22Sic(x) 0 x [0, 1], la matriceAhest denie positive (donc inversible !).preuveOn a que x RN:(Ahx/x) =1h2(N

i=1(2+cih2)x2i2N1

i=1xixi+1) =1h2(x21+N1

i=1(xixi+1)2+x2N+h2N

i=1cix2i) 0.(Ahx/x) = 0 ___x1 = 0xN= 0xi = xi+1, i = 1, . . . , N 1x = 0.

Notons () le syst`eme lineaire suivant :AhUh = B, ()et appelons Uh = (uh(xi))1iN lunique vecteur solution. On peut alors demontrer le theor`emede convergence suivant :Theor`eme23Si u C4([0, 1])estsolutionde(6.2)et uhsolutiondusyst`emelineaire()alors :u uh

=max1iN|u(xi) uh(xi)| h296supx[0,1]|u(4)(x)|.Donc plus h est petit (plus il y a de points dans le maillage), meilleure est lapproximationde la solution exacte du probl`eme si celle-ci est reguli`ere.Remarque18Siu C3([0, 1])alors :u uh

= O(h)Siu C2([0, 1])alors:u uh

h00AnnexeAResolutionnumeriquedesequationsdierentiellesA.1 Positionduprobl`emeOnappelleequationdierentielleuneequationreliant unefonctionetses deriveessuccessives. Si lequationne fait intervenir que la fontion et sa derivee, on parle dequationdupremierordre.Soit un ouvert de RRN. Etant donnesf: RRNRNqui ` a un couple (t, u) associef(t, u)continue, unpointquelconquet0 R, unpointquelconqueU0 RN, nouscherchonsunefontionu : I RN,o` uIestunvoisinagedet0dans R,qui` at Iassocieu(t), contin ument derivable, telle queu verie le probl`emedeCauchy suivant :_u

(t) = f(t, u(t))u(t0) = U0conditioninitialeouconditiondeCauchy(A.1)On dit quil y a unicite au probl`eme de Cauchy en (t0, U0) sil existe au moins une solution`a ce probl`eme et si pour toutes solutions : I RNet : J RN, les fonctions etconcident surI J.Letude mathematique de lexistence et de lunicite dune solutionu est delicate et consti-tueunebrancheenti`eredesmathematiques. Nousnouscontenteronsdedonnerunecondi-tionsusant `a lexistenceetlunicitedune solutionauprobl`emede Cauchy.Nous ne nousinteresserons ensuite qu`a la resolution numerique de ces equations dierentielles.Theor`eme24Theor`eme de Cauchy-Lipschitz (Admis)Si f est continuedans et si f est localement lipschitziennepar rapport ` asadeuxi`emevariable, ie sipour tout (t0, u0) , il existe un voisinageVde (t0, u0) etL > 0 tels que :(t, u), (t, v) V,|f(t, u) f(t, v)| L|u v|,alors pour tout (t0, u0) , il existe I voisinage de t0 dans R et une application u, contin umentderivable, deIdans RNsolution unique de :_u

(t) = f(t, u(t))u(t0) = U07778 ANNEXEA. RESOLUTIONNUMERIQUEDESEQUATIONSDIFFERENTIELLESRemarque19Si f estdeclasse C1alorsfestlocalement lipschitzienneparrapport ` asadeuxi`eme variable, et le theor`eme de Cauchy-Lipschitz sapplique.Exemples_u

(t) = u(t) tu(0) = 0La fontionu(t) = exp (t) +t + 1, t 0 est solution.___u

(t) =u(t)t ln t+1ln t, t [e, 5]u(e) = eLa fontionu(t) =tln test solution unique car :|f(t, u) f(t, v)| =v ut ln tv ue=1e|v u|.A.2 Resolutionnumerique:methodedEulerOn suppose que les hypoth`eses du theor`eme (24) sont veriees. Nous cherchons `a approcherles valeurs de la solutionu de lequation (A.1) pour dierentes valeurs det I = [0, T].Soith la longueur du pas, on denittj = jh, j = 0, 1, 2, . . . , n :_tj+1tju

(t) dt =_tj+1tjf(t, u(t)) dtu(tj+1) u(tj) =_tj+1tjf(t, u(t)) dt. .integrationnumeriqueOn noteuj = u(tj) etuj+1 = u(tj+1).En utilisant la formule des rectangles ` a gauche, on obtient :uj+1uj= (tj+1tj)f(tj, u(tj))uj+1= uj + (tj+1tj)f(tj, uj)On obtient le schema dEuler explicite (explicite car on a directement uj+1 en fonction deuj) :_uj+1= uj +hf(tj, uj)u(0) = U0A.2. RESOLUTION NUMERIQUE:METHODEDEULER 79En utilisant la formule des rectangles ` a droite, on obtient :uj+1uj= (tj+1tj)f(tj+1, u(tj+1))uj+1= uj + (tj+1tj)f(tj+1, uj+1)On obtient le schema dEuler implicite (implicite car uj+1 est des deux cotes de lequation) :_uj+1= uj +hf(tj+1, uj+1)u(0) = U0Remarque20Le schema dEuler explicite est plus simple ` a utiliser mais moinsprecis quele schema dEuler implicite. De plus, le schema dEuler implicite est plus stable que le schemadEuler explicite.ExempleSoit > 0 et lequation :u

(t) = u(t)u(0) = 1La fonctionu(t) = exp (t) est solution.Par le schema dEuler explicite :uj+1 = (1 h)uj uj = (1 h)nDonc commeu(t) tend vers0 quandt tend vers linni, |1 h|< 1, soitlaconditiondestabiliteh < 2/.Par le schema dEuler implicite :(1 + h)uj+1 = uj uj =1(1 + h)nAlorsujtend vers 0 pour touth > 0. Il ny a pas de conditiondestabilite.Interpretation graphique du schema dEuler expliciteCommeu

(0)=f(0, u(0)), onconfondlacourbedef: t f(t, u(t))etlatangenteen0pour trouver le point suivant, A1. Puis on construit la tangente ` a la courbe au nouveau pointet on trouve un pointA2, etcLe-schemaEn combinant les schemas dEuler explicite et implicite, on obtient le-schema :_uj+1= uj +h[f(tj+1, uj+1) + (1 )f(tj, uj)], 0 1u(0) = U0.On retrouve le schema dEuler explicite pour = 0, et limplicite pour = 1.Pour = 1/2, on retrouve la formule des trap`ezes.Remarque21Pourlesschemasimplicites, lavaleurdedepart estengeneral donneeparun schema explicite. Les schemas implicites sont ` a considerercomme des equations de pointxe.80 ANNEXEA. RESOLUTIONNUMERIQUEDESEQUATIONSDIFFERENTIELLESA10t1Tt2A2u0CfLe schema de Heunuj+1= uj +hf(tj, uj)uj+1= uj +h/2[f(tj+1, uj+1) +f(tj, uj)]uj+1= uj +h/2[f(tj+1, uj +hf(tj, uj)) +f(tj, uj)]u(0) = U0.Le schema dEuler modieuj+1/2= uj +h/2f(tj, uj)uj+1= uj +hf(tj+1/2, uj+1/2)u(0) = U0.A.3 Methodes`aunpasgeneriqueLes methodes `aunpas secrivent_uj+1= uj +h(tj, uj, h)u0= u(0),avec continue par rapport aux trois variables.Choisir une methode revient ` a choisir la fonction! Quelles conditions imposer ` a pour quela methode fonctionne ?A.3. METHODES`AUNPASGENERIQUE 81ExemplesSchema dEuler(t, u, h) = f(t, u).Schema de Heun(t, u, h) = 1/2[f(t +h, u +hf(t, u)) +f(t, u)].On poseej(h) = u(tj) uj, j = 0, 1, . . . , n : lerreur ` a letapej.Objectif 1 : Quand h tend vers 0,u(tj) doit tendre versujieon a convergence de la solutionapprochee trouveeujvers la solution exacte au pointtj,u(tj).Denition11Unemethode`aunpasestditeconvergentesur[0, T]siquellequesoitU0condition initiale :limh0max0jn|ej(h)| = 0limh0max0jn|u(tj) uj| = 0.Objectif 2 : Il faut que la methode approche bien lequation dierentielle.Denition12Unemethode`aunpasestditeconsistantesipourtout usolutiondeu

=f(t, u) :limh0max0jn11h (u(tj+1) u(tj)) (tj, u(tj), h)= 0Objectif 3 : connatre et controler la repercussion des erreurs darrondi.Denition13Une methode`a un pas est dite stable si :il existeKindependantdeh tel que, pour tousU0, U0etuj+1 = uj +h(tj, u(tj), h), uj+1 = uj +h(tj, u(tj), h) + jverient |uj uj| K(|U0

U0| +j1

i=0|i|) 0 j n.Ces trois notions sont liees pour les schemas `a un pas. En eet :Proposition12Pour une methode`a un pas, la convergence implique la consistance.Theor`eme25Si une methode `a un pas est consistante et stable alors elle est convergente.preuveSoit u solution de lequation dierentielle, la consistance donne : u(tj+1) = u(tj)+h(tj, u(tj), h)+navec limh0 maxn |n| = 0.Or la methode est aussi stable, doncmaxj|u(tj) uj| K(|u(0) U0| +hN..=Tmaxn|n|)maxj|u(tj) uj| K(|u(0) U0| +T maxn|n|. .0).Donc maxj |u(tj) uj| 0. 82 ANNEXEA. RESOLUTIONNUMERIQUEDESEQUATIONSDIFFERENTIELLESProposition13Uneconditionnecessaireetsusantepourquunemethode`aunpassoitconsistante est(t, u, 0) = f(t, u),t [0, T],u RN.Justicationlimh0u(t +h) u(t)h= u

(t) = f(t, u(t)).Comme est continue,limh0(t, u(t), h) = (t, u(t), 0),soit(t, u(t), 0) = f(t, u(t)).Proposition14Si est localement lipschitzienne par rapport ` a sa deuxi`eme variable, alorsla methodeest stable.Theor`eme26Le schema dEuler et le schema de Heun sont explicites et convergents.preuvePour le schema dEuler, cest evident car(t, u, h) = f(t, u) est localement lipschitzienne parrapport ` a la deuxi`eme variable, par hypoth`ese du theor`eme de Cauchy-Lipschitz.Pour le schema de Heun,(t, u, h) = 1/2[f(t +h, u +hf(t, u)) +f(t, u)]. Or|(t, u, h) (t, v, h)| 1/2|f(t, u) f(t, v)| + 1/2|f(t +h, u +hf(t, u) f(t +h, v +hf(t, v))| L/2|u v| +L/2|u v +h(f(t, u) f(t, v))| L(1 +hl/2)|u v|.

Denition14On dit quune methodeest dordrep simaxj|1/h(u(tj+1) u(tj)) (tj, u(tj), h)| = O(hp).Methode dordre 4 : methode de Runge-KuttaOn pose(t, u, h) = 1/6(k1 + 2k2 + 2k3 +k4)aveck1= f(t, u)k2= f(t +h/2, u + (h/2)k1)k3= f(t +h/2, u + (h/2)k2)k4= f(t +h, u +hk3).Cette methode est dordre 4 et donne dexcellentsresultats.Son defaut est quelle demandelevaluation defquatre fois.A.4. METHODES`APASMULTIPLES 83A.4 Methodes`apasmultiplesOn appelle methode`akpas une methode denie par :kuj+k + k1uj+k1 + + 0uj = h(kfj+k + + 0fj), k = 0o` u on a posefj = f(tj, uj).Sik = 0, la methode est explicite et implicite sinon.Pour denir ces methodes `a pas multiples, on utilise les formules dintegration numeriqueou de dierentiationou dinterpolation (cf TDs).Exemples_tj+1tj1u

(t) dt =_tj+1tj1f(t, u(t)) dtu(tj+1) u(tj1) = 2hfj..formule du point milieuOn obtient alors le schemasaute-mouton (leap-frog en anglais) :_uj+1= uj1 + 2hfju0= u(0)._tj+2tju

(t) dt =_tj+2tjf(t, u(t)) dtu(tj+2) u(tj) = 2h/6(fj+2 + 4fj+1 +fj). .formule de SimpsonSoit :_uj+2= uj +h/3(fj+2 + 4fj+1 +fj)u0= u(0).Remarque22Comment programmerun schema implicite ?Soienty0, y1donnes.Pouri = 1 `an faire (etape de prediction, formule explicite) :y0i+1 = yi + 3h/2f(xi, yi) h/2f(xi1, yi1)Pourk = 0, 1 jusqu` a convergence faire (etape de correction):yk+1i+1= yi +h/2[f(xi, yi) +f(xi+1, yki+1)]y1donne par Runge-Kutta de meme ordreque le schema pour conserver la precision.On peut montrerque si la prediction est bien choisie, une iteration de correctionsut.84 ANNEXEA. RESOLUTIONNUMERIQUEDESEQUATIONSDIFFERENTIELLESAnnexeBAnnee2002-20038586 ANNEXEB. ANNEE2002-2003DEUG MIAS 2 AnalysenumeriqueAnnee 2002-2003 Feuille 1Exercice1PolynomesdeLagrange(Joseph-Louis Lagrange, franco-italien, 1736-1813)Soient les points dinterpolation suivants : (1, 0), (1, 0), (2, 3) et (3, 2). Trouvez le polyn omedinterpolation de degre 3 passant par ces points :a) par une methode didentication,b) par une methode de mise en facteurs,c) `a laide des polyn omes de Lagrange.Exercice2MatricedeVandermonde(Alexandre Vandermonde, fran cais, 1735-1796)a)Ecrirelesyst`emelineairequi denitlepolyn omedinterpolationdedegre3passantpar les points de coordonnees (x0, y0), (x1, y1), (x2, y2), (x3, y3).b) CalculerledeterminantdelamatriceV decesyst`emelineaire(onpourraeectuerdes manipultations delignes et decolonnes). Lamatrice V est appeleematricedeVandermonde.c) Calculer dans le cas general (i.e. en dimension quelconque) le determinant dune matricede Vandermonde.Exercice3AlgorithmedeNeville-Aitken(EricHaroldNeville, anglais, 1889-1961etAlexander Aitken, neo-zelandais,1895-1967)Pour deux suites de nombres x1, x2, . . . , xr et y1, y2, . . . , yr, on denit la suite de polyn omes :Pk,0 = ykpourk = 0, 1, . . . , r etPk,j+1(x) =(xkx)Pj,j(x) (xj x)Pk,j(x)xkxjpourk = j + 1, . . . , r etj = 0, . . . ,k 1.a) ConstruireP3,3avec(x0, y0) = (1, 0),(x1, y1) = (1, 0),(x2, y2) = (2, 3)et (x3, y3) =(3, 2).b) Montrez par recurrence que Pk,j avec k j est le polyn ome dinterpolation de Lagrangepour les pointsx0,x1,. . . ,xj1,xk.c) Quen concluez-vous pourPk,k?Exercice4Dierencesdiviseesa) Retrouvezpar la methodedes dierencesdivisees le polynome dinterpolationde La-grange de degre 3 aux points (1, 0), (1, 0), (2, 3) et (3, 2) (polyn ome dej` a obtenu).b) Reecrire larbre des dierences divisees lorsque les points x0, x1, x2, x3 sont reguli`erementrepartis (formule de Newton : Sir Isaac Newton, anglais, 1643-1727).87DEUG MIAS 2 AnalysenumeriqueAnnee 2002-2003 Feuille 2Exercice1On consid`ere la table suivante :x f(x)2.8 16.44463.0 20.08553.2 24.53253.4 29.96413.6 36.59823.8 44.70124.0 54.59821.) Calculerf(3.3)par interpolationpolynomiale` a partir desdonnees3, 3.2, 3.4, 3.6,enecrivant le polyn ome sous la forme de Newton utilisant les dierences progressives.2.) Donner unemajorationdelerreur theoriquedinterpolationsachantquef(x) =ex.Comparer ` a lerreur reelle.3.) Combien de points aurait-il fallu prendre, en theorie, pour avoir une erreur inferieure`a 5.105? On admettra que :n

i=0(x xi) hn+1(n + 1)! o` uxi = x0 +ih etx0 x xn.4.) Resoudre f(x) = 30 par interpolation inverse, ` a la precision de votre choix. Comparer`a la solution exacte.Exercice2Soit la fonction denie parf(x) =1 +x.1.) Determiner le polyn ome dinterpolation de NewtonPveriant :P(0) = f(0), P_12_= f_12_, P(1) = f(1).CalculerP(0.1) etP(0.9). Comparer aux valeurs exactes.Evaluerf(x) P(x) pour ces deux valeurs en vous servant dun theor`eme du cours.2.) DeterminerQ polyn ome dinterpolation dHermite veriant :Q(0) = f(0), Q_12_= f_12_, Q(1) = f(1).Q

(0) = f

(0), Q

_12_= f

_12_, Q

(1) = f

(1).CalculerQ(0.1) etQ(0.9). Comparer aux valeurs exactes.88 ANNEXEB. ANNEE2002-2003Exercice3Soit la fonction denie parf(x) =3 x.1. Construire la table des dierences divisees `a partir des donnees(xi, f(xi)),i = 0 ` a 4, avecx0 = 0, x1 = 1, x2 = 8, x3 = 27, x4 = 64.2. Ecrirelepolyn omedinterpolationdef, noteP4, construitsurlesdonneesdu1, enutilisant la formule de Newton et les dierences divisees, cest-`a-dire :P0(x) = f(x0)Pk(x) = Pk1(x) + (x x0)(x x1) . . . (x xk1)f[x0, x1, . . . , xk]CalculerPi(20) pouri = 1 ` a 4 et comparer `af(20).3. Ecrire lerreur dinterpolationE4(x) = f(x) P4(x).Peut-on majorerE4(20) sur lintervalle considere ? Expliquer les resultats du (2).4. Pour ameliorer les resultats, on interpole f sur les donnees (xi, f(xi)) i = 1 ` a 4. Ecrirele polyn ome dinterpolation ainsi obtenu ` a laide de (1). On le note Q3. Calculer Qi(20)pouri = 1, 2, 3 et donner une majoration deE3(20) = f(20) Q3(20).5. Onveutmaintenantresoudre3x=avec =2.71441761659, parinterpolationinverse. Pour cela :a. Construire la table des dierences progressives-regressives (yi = yiyi1) pour lesdonnees permutees, cest-`a-dire pour (f(xi), xi)i = 0 ` a 4.b. Ecrirelepolyn omedinterpolationR4, construit` alaidedelaformuledeNewtonregressive :Rk(x) = Rk1(x) + (x xn)(x xn1) . . . (x xn(k1))kf(xn)k!hkR0(x) = f(xn)Calculerles Ri()pouri =1 ` a 4. Queconstate-t-on ?Evaluerunemajorationde2() = f1() R2(). Comparer ` aR3() R2().89DEUG MIAS 2 AnalysenumeriqueAnnee 2002-2003 Feuille 3TD de preparation au premier TP Maple.Probl`eme1Etude des polyn omes de Tchebyche (Pafnuty Lvovich Chebyshev, russe, 1821-1894)On appelle fonction polynomiale de Tchebyche de degren, lapplicationTn : [1, +1] Rx cos(narccos(x)).1) Montrezen posant cos() =x que pour toutentiern positif, Tnestun polyn ome dedegren en x.2) Montrez que pour toutn 2, on aTn+1(x) = 2xTn(x) Tn1(x).3) Calculez les 5 premiers polynomes de Tchebyche.4) Determinez en fonction den le coecient du terme enxndeTn.5) On poseXk = cos(2k 12n) pourk = 1, . . . , n.Montrez que Tn poss`ede n zeros simples. Ces zeros sont appeles les points de Tchebychedordren.6) Si fest une fonction de classe Cn+1[1, 1] , on rappelle que lon a lestimation derreur|f(x) P(x)| maxx[1,+1]f(n+1)(x)(n + 1)!maxx[1,+1]|(x x0) . . . (x xn)|o` u Pest le polyn ome dinterpolation de Lagrange en les points x0, . . . , xn. On admettrale resultat suivantmaxx[1,+1]|(x x0) . . . (x xn)| maxx[1,+1]|(x X0) . . . (x Xn)| .Expliquez pourquoi les points de Tchebyche sont de bons points dinterpolation.7) Quels points dinterpolation faut-il choisir si lintervalle dinterpolation est le segment[a, b] ?90 ANNEXEB. ANNEE2002-2003DEUG MIAS 2 AnalysenumeriqueAnnee 2002-2003 Feuille 4On poseTn(x) = cos(narccos(x)) etX = arccos(x) pourx [1; 1].Exercice1Lespolyn omesdeChebyshev1. Demontrez la formule de recurrence des polynomes de Chebyshev `a laide de MAPLE.(Indice : developper cos((n + 2)x) puis cos((n + 1)x).)2. Acher les 10 premiers polyn omes de Chebyshev `a laide dune boucle for. Que vaut lecoecient de plus haut degre ?3. Tracer leurs graphes.4. Verier que les cos_(2k1)12_ sont les zeros dun des polyn omes precedents (Lequel ?).Exercice2Linterpolationpolynomiale1. Consultez laide en ligne de MAPLE pour linterpolation.2. Construire (` a laide de MAPLE!) le polyn ome dinterpolation de Lagrange de la fonctionfdenie parf(x) = exp(x2) avec :6 points : -5, -3, -1, 1, 3, 5.11 points : -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5.21 points : -5,-4.5,-4,-3.5,-3,-2.5,-2,-1.5,-1,-0.5,0,0.5,1, 1.5,2,2.5,3,3.5,4,4.5, 5.3. Tracerfet son polyn ome dinterpolation sur un meme graphe. Que constatez-vous ?Exercice3Interpolationpolynomialeetpolyn omesdeChebyshev1. Quel sont les polyn omes de Chebyshev qui poss`edent 6, 11 et 21 zeros ?2. Construire (` a laide de MAPLE!) le polyn ome dinterpolation de Lagrange de la fonctionfdenie par f(x) = exp(x2) avec 6, 11 puis 21 points dinterpolation qui seront les 6,11 puis 21, zeros dun polyn ome de Chebyshev.3. Tracerfet ce nouveau poyln ome dinterpolation sur un meme graphe. Que constatez-vous ?4. Reprendre les trois derni`eres questions avec la fonctionf(x) =11 +x2.91DEUG MIAS 1 AnalysenumeriqueAnnee 2002-2003 Feuille TP1Exercice1SoitI =_+0ex2dx etIn =_n0ex2dx. On a alorsIn = In1 +_nn1ex2dx. Une tablede valeurs donneI2 = 0.88208139076242.a) Considerons la formule dintegration suivante :_10f(x)dx = f(0) + f_13_+ f_23_+ f(1).Trouvez , , , , tels que cette formule soit exacte sur lespace vectoriel des polyn omesde degre le plus eleve possible. Par un changement de variables, donnez la formule surlintervalle quelconque [a, b] .b) Calculez_32ex2dx et_43ex2dx par la formule precedente. En deduireI3 etI4.c) On pose f_1n_= In. On a alors limn+In = f(0) = I. Interpolez fpar le polyn ome Psur les donnees_12, f_12__,_13, f_13__,_14, f_14__et calculezP(0).Exercice2a) DeterminezA0,A1,A2tels que la relation :_20f(x)xdx = (2h)1/2(A0f(0) +A1f(h) +A2f(2h)) +R(f)soitexacte(i.e. R(f) = 0)sur lespacevectoriel des polyn omesdedegreleplus elevepossible. On precisera ce degre.b) Calculez exactement_10ln(1 +x)xdx, en integrant dabord par partie, puis par chan-gement devariable. Calculezapproximativement cetteintegrale parlamethodequiprec`ede.Comparer ce resultat ` a celui que lon obtient par la methode de Simpson (oncalculeralimx0ln(1 +x)x).c) Expliquez pourquoi le resultat obtenu par la methode de Simpson est mauvais (ThomasSimpson, anglais, 1710-1761).92 ANNEXEB. ANNEE2002-2003Exercice3On veut evaluer I =_10ln(x)x21dx par une formule dintegration numerique du type

Aif(xi)o` uf(x) =ln(x)x21.a) Montrez quexi = 1 est une valeur possible mais pasxi = 0.b) Construire la formule de quadrature suivante, de type interpolation :_10f(x)dx = af_12_+bf(1) +R(f).DeterminezR(f). Appliquez cette formule ` aI.c) On rappelle la formule de Gauss-Legendre ` a deux points :_11f(x)dx = f_13_+f_13_+1135f(4)()pour [1, 1] . En deduire lapproximation de_10f(x)dx et lappliquer ` aI.(Johann Carl Friedrich Gauss, allemand, 1777-1855 et Adrien-Marie Legendre, fran cais,1752-1833)d) Comparez les resultats precedents `a la valeur exacte28.Exercice4On veut evaluerI =_+11ex2(1 +x2)dx.a) Calculez une approximation deIpar la methode des trap`ezes `a 3 points.b) Construire une methode dapproximation du type :_+11f(x)(1 +x2)dx = A1f(x1) +A2f(x2) +R(f)o` u x1, x2 et A1, A2 sont des nombres distincts non nuls. En supposant R(f) = Kf(4)(), [1, 1] . DeterminezK`a laide def(x) = x4.93DEUG MIAS 2 AnalysenumeriqueAnnee 2002-2003 Feuille 5Exercice1Ecrire la methode des trap`ezes composite `an + 1 points. Que pouvez-vous dire de lerreur ?Probl`eme1On denit une fonction poids (x) = exet les polyn omes de Laguerre Ln(x) = exdndxn(xnex).Ces derniers verient :_0exLn(x)Lp(x) dx = 0, n = p,_0exLn(x)2dx = (n!)2.On construit alors la formule dintegration suivante :_0exf(x) dx =n

k=0Ankf(xk) +R(f).On vous fournit la table suivante.Abscisses et poids pour lintegrationde Gauss-Laguerre :n = 2 xii0.585786437627 0.8535533905933.414213562373 0.146446609407n = 3 xii0.415774556783 0.7110930099292.294280360279 0.2785177335696.289945062937 0.0103892565016On veut calculer numeriquementI =_/20ln(sin(x)) dx.1. Expliquer pourquoi on ne peut appliquer ni la methode des trap`ezes, ni celle de Simpson.On coupe alorsIen deux integrales :I1 =_a0ln(sin(x)) dx etI2 =_/2aln(sin(x)) dx2. On determine daborda de sorte que |I1| .a) Sachant que sin(x) 2x, x _0;2, montrer que|I1| a_1 ln(2a )_.94 ANNEXEB. ANNEE2002-2003b) Verier quea = 103convient pour = 1.5102.3. On prend maintenanta = 103et = 1.5102.Ecrire la methode des trap`ezes composite `a n+1 points appliquee `a I2 ainsi que lerreur.Combien de points doit-on prendre pour avoir une erreur inferieure `a ?4. Utiliser la transformation ln(sin(x)) = ln(x) +ln_sin(x)x_pour calculer une estimationdeIpar la methode de Simpson simple.5. Dan