176
Analyse numérique M33 USTV L2 2012/2013 Recueil d’exercices corrigés et aide-mémoire G. FACCANONI Dernière mise-à-jour Jeudi 31 janvier 2013

2012_2013_M33_L2

Embed Size (px)

Citation preview

  • Anal

    yse

    num

    riq

    ueM

    33

    USTV

    L22012/2013

    Recueil dexercices corrigset aide-mmoire

    G. FACCA

    NONI

    Dernire

    mise--jo

    ur

    Jeudi 31

    janvier 2

    013

  • Ce fascicule est un support au cours danalyse numrique. Il aborde : la recherche de racines dune fonction, linterpo-lation, lintgration numriques, lintgration dquations diffrentielles, le fitting de donnes et la rsolution de systmeslinaires. Les applications se feront avec le langage Python dont la documentation et les sources peuvent tre tlcharges ladresse http://www.python.org.

    Avertissement : ces notes sont rgulirement mises jour et corriges, ne vous tonnez pas si vous dcouvrez des erreurs.Merci de me les communiquer. Toutes les remarques ou questions permettant den amliorer la rdaction peuvent treenvoyes ladresse [email protected]

    Gloria FACCANONI

    IMATH Btiment U-318 T 0033 (0)4 94 14 23 81Universit du Sud Toulon-VarAvenue de luniversit B [email protected] LA GARDE - FRANCE i http://faccanoni.univ-tln.fr

    2

  • Table des matires

    Notations 5

    Introduction au calcul scientifique 7

    1. Rsolution dquations non linaires 91.1. tape : localisation des zros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91.2. tape : construction dune suite convergente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

    1.2.1. Mthodes de dichotomie (ou bissection), de LAGRANGE (ou Regula falsi) et de la scante . . . . . . . . 101.2.2. Mthodes de point fixe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

    2. Interpolation 472.1. Position du problme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 472.2. Interpolation de LAGRANGE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 482.3. Polynme dHERMITE ou polynme osculateur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 512.4. Splines : interpolation par morceaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

    2.4.1. Interpolation linaire composite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 542.5. Approximation de drives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

    3. Quadrature 733.1. Principes gnraux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 733.2. Exemples de formules de quadrature interpolatoires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

    4. quations diffrentielles ordinaires 994.1. Schmas numriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1014.2. Stabilit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102

    5. Meilleur approximation au sens des moindres carrs. 1235.1. Fitting par une relation affine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1235.2. Fitting par un polynme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125

    6. Systmes linaires 1316.1. Systmes mal conditionns . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1316.2. Mthode (directe) dlimination de Gauss et factorisation LU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1326.3. Mthodes itratives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137

    A. Python : guide de survie pour les TP 159A.1. Obtenir Python et son diteur IDLE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159

    A.1.1. Utilisation de base dIDLE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159A.2. Notions de base de Python . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162A.3. Fonctions et Modules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168

    A.3.1. Fonctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168A.3.2. Modules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170

    A.4. Structure conditionnelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172A.5. Boucles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173

    3

  • NotationsEnsembles usuels en mathmatiques

    On dsigne gnralement les ensemble les plus usuels par une lettre double barre :

    N lensemble des entiers naturels

    N lensemble des entiers strictement positifsZ lensemble des entiers relatifs (positifs, ngatifs ou nuls)

    Z lensemble des entiers 6= 0Q lensemble des nombres rationnels

    (pq , p Z, q Z

    )R lensemble des rels

    R lensemble des rels autres que 0C lensemble des nombres complexes

    IntervallesIngalit Ensemble Reprsentation graphique

    a x b [a,b] a b

    a < x < b ]a,b[ a b

    a x < b [a,b[ a b

    a < x b ]a,b] a b

    x a [a,+[ a

    x > a ]a,+[ a

    x b ],b] b

    x < b ],b[ b

    |x| a avec a 0 [a, a] a a

    |x| < a avec a 0 ]a, a[ a a

    |x| a avec a 0 ],a] [a,+[ a a

    |x| > a avec a 0 ],a[]a,+[ a ax R ],+[

    Symboles utiliss dans le document

    dfinition

    thorme, corollaire, proposition

    proprit(s)

    astuce

    attention

    remarque

    mthode, algorithme, cas particulier

    exercice de base

    exercice

    exemple

    5

  • Notations Jeudi 31 janvier 2013

    curiosit

    gal par dfinition> strictement suprieur< strictement infrieur suprieur ou gal infrieur ou gal6= diffrent{ } ensemble

    ; ensemble vide| tel que appartient6 nappartient pas pour tout (quantificateur universel) il existe (quantificateur universel)6 il nexiste pas! il existe un et un seul est sous-ensemble (est contenu) union densembles intersection densembles= si . . . alors si et seulement sissi si et seulement si

    ln logarithme de base e

    loga logarithme de base a

    infinisymbole dintgralen

    i=0 ai somme par rapport lindice i , quivaut a0+a1+ +anni=0 ai produit par rapport lindice i , quivaut a0a1 an

    n! n factoriel, quivaut 12 ng f g compos ff , d fd x symboles de drive

    Conventions pour la prsentation du codePour lcriture du code, on utilise deux prsentations :? les instructions prcdes de chevrons dans une boite grise sont saisir dans une session interactive

    1 >>> 1 + 12 2

    ? les instructions sans chevrons dans une boite grise sont des bouts de code crire dans un fichier

    1 print Coucou!

    6 G. Faccanoni

  • Introduction au calcul scientifiqueOn peut dfinir le CALCUL SCIENTIFIQUE comme la discipline qui permet de reproduire sur un ordinateur un phnomne

    ou un processus dcrit par un modle mathmatique.

    PHNOMNE PHYSIQUE, CO-NOMIQUE, BIOLOGIQUE. . .

    Observation exprimentaleModle conceptuel

    MODLE MATHMATIQUE

    Mise en quations :quations diffrentielles, int-grales, stochastiques. . .

    ANALYSE MATHMATIQUE

    Bien posBien conditionnProprits de la solutionSolutions analytiques

    ANALYSE NUMRIQUE

    Mthodes de discrtisationAnalyse des algorithmes (rapi-dit, prcision, souplesse)Estimation des erreurs

    PROGRAMMATION

    Langage de programmation (C,C++, Fortran, Java, Python, Mat-lab, Scilab, Octave. . .)Structure des donnesImplmentation de lalgorithmeOptimisation

    CALCULS

    POSTPROCESSING

    VisualisationAnalyse des rsultats

    CALCUL SCIENTIFIQUE

    Lordinateur est aujourdhui un outil incontournable pour simuler et modliser des systmes complexes, mais il fautencore savoir exprimer nos problmes (physiques, conomiques, biologiques. . .) en langage formalis des mathmatiquespures sous la forme dquations mathmatiques (diffrentielles, intgrales. . .). Nous sommes habitus rsoudre les pro-blmes de faon analytique, alors que lordinateur ne travaille que sur des suites de nombres. On verra quil existe souventplusieurs approches pour rsoudre un mme problme, ce qui conduit des algorithmes diffrents. Un des objectifs de cecours est de fournir des bases rigoureuses pour dvelopper quelques algorithmes utiles dans la rsolution de problmes enmathmatique, conomie, physique. . .

    Un algorithme, pour tre utile, doit satisfaire un certain nombre de conditions. Il doit tre :

    rapide : le nombre doprations de calcul pour arriver au rsultat escompt doit tre aussi rduit que possible ;prcis : lalgorithme doit savoir contenir les effets des erreurs qui sont inhrentes tout calcul numrique (ces erreurs

    peuvent tre dues la modlisation, la reprsentation sur ordinateur ou encore la troncature) ;

    souple : lalgorithme doit tre facilement transposable des problmes diffrents.Le choix et loptimisation des algorithmes numriques mis en pratique sont absolument cruciaux tant pour les calculs

    de type industriel souvent trs rptitifs et devant donc pouvoir tre excuts en un temps trs court, que pour les cal-culs de rfrence pour lesquels la seule limite est la patience de celui qui les fait. Par exemple, en fluidodynamique, enlaissant tourner une station de travail pendant quelques jours, les numriciens rsolvent des systmes frisant le milliarddinconnues. Lexprience montre quentre une approche numrique standard et une approche soigneusement rflchie

    7

  • Introduction au calcul scientifique Jeudi 31 janvier 2013

    et optimise un gain de temps de calcul dun facteur 100, voire davantage, est souvent observ. Il est clair quon peut pas-ser ainsi, grce cet effort, dun calcul totalement draisonnable un calcul parfaitement banal : tout lenjeu de lanalysenumriques est l ! Cest dire limportance pour tous scientifique de bien connatre ces mthodes, leurs avantages et leurslimites.

    Exemple Calcul dep

    ASur ordinateur, laddition de deux entiers peut se faire de faon exacte mais non le calcul dune racine carre. On procde alors par

    approximations successives jusqu converger vers la solution souhaite. Il existe pour cela divers algorithmes. Le suivant est connudepuis lantiquit (mais ce nest pas celui que les ordinateurs utilisent).Soit A un nombre rel positif dont on cherche la racine carre. Dsignons par x0 la premire estimation de cette racine (gnralementle plus grand entier dont le carr est infrieur A ; par exemple, si A = 178, alors x0 = 13 car 132 = 169< 178 et 142 = 196> 178) et par0 lerreur associe : p

    A = x0+0.Cherchons une approximation de 0. On a

    A = (x0+0)2 = x20 +2x00+20.Supposons que lerreur soit petite face x0, ce qui permet de ngliger le terme en

    20 :

    A ' x20 +2x00.

    Remplaons lerreur 0 par un 0, qui en est une approximation, de telle sorte que

    A = x20 +2x00.

    On en dduit que

    0 =Ax20

    2x0donc

    x1 = x0+0 =1

    2

    (A

    x0+x0

    )constitue une meilleure approximation de la racine que x0 (sous rserve que le dveloppement soit convergent). De plus, rien ne nousempche de recommencer les calculs avec x1, puis x2, etc., jusqu ce que la prcision de la machine ne permette plus de distinguerle rsultat final de la vritable solution. On peut donc dfinir une suite, qui partir dune estimation initiale x0 devrait en principeconverger vers la solution recherche. Cette suite est

    xk+1 =1

    2

    (A

    xk+xk

    ), x0 > 0.

    Lalgorithme du calcul de la racine carre devient donc1. Dmarrer avec une premire approximation x0 > 0 de

    pA.

    2. chaque itration k, calculer la nouvelle approximation xk+1 = 12(

    Axk+xk

    ).

    3. Calculer lerreur associe k+1 =Ax2k+12xk+1 .

    4. Tant que lerreur est suprieure un seuil fix, recommencer au point 2Le tableau ci-dessous illustre quelques itrations de cet algorithme pour le cas o A = 5 :

    k xk k

    0 2.0000000000 0.23606797751 2.2500000000 0.01393202252 2.2361111111 0.00004313363 2.2360679779 0.00000000044 2.2360679775 0.0000000000

    On voit que lalgorithme converge trs rapidement et permet donc destimer la racine carre dun nombre moyennant un nombre li-

    mit doprations lmentaires (additions, soustractions, divisions, multiplications). Il reste encore savoir si cet algorithme converge

    toujours et dterminer la rapidit de sa convergence. Lanalyse numrique est une discipline proche des mathmatiques appliques,

    qui a pour objectif de rpondre ces questions de faon rigoureuse.

    Dans la plupart des domaines scientifiques, tout calcul passe par lexploitation de techniques de reprsentation desfonctions et des algorithmes de localisation de zros, de recherche dlments propres de matrices, de calcul dintgrales,de rsolution dquations diffrentielles, aux drives partielles et/ou intgrales. . . Une partie de ces diffrents problmesest trait dans ce polycopi ; noter la prsence dexercices corrigs en fin de chaque chapitre permettant de vrifier ou deconsolider lassimilation des notions introduites.

    8 G. Faccanoni

  • 1. Rsolution dquations non linaires

    Recherche de la solution de lquation non linaire f (x)= 0 o f est une fonction donne

    Soit f : RR une fonction continue donne dont on veut chercher numriquement un ou plusieurs zros x, cest--diref (x)= 0. Les mthodes numriques pour approcher x consistent : localiser grossirement le (ou les) zro(s) de f en procdant des valuation qui sont souvent de type graphique ; on

    note x0 cette solution grossire ;

    construire, partir de x0, une suite x1, x2, x3, . . . telle que limk xk = x o f (x)= 0. On dit alors que la mthode estconvergente.

    Dfinition Mthode itrative deux niveauxOn appelle mthode itrative deux niveaux un procd de calcul de la forme

    xk+1 =G(xk ), k = 0,1,2, . . .

    dans lequel on part dune valeur donne x0 pour calculer x1, puis laide de x1 on calcul x2 etc. La formule mme estdite formule de rcurrence. Le procd est appel convergent si xk tend vers un nombre fini lorsque k tend vers +. Ilest bien vident quune mthode itrative nest utile que sil y a convergence vers les valeurs cherches.

    On peut parfaitement envisager des mthodes itratives multiniveaux, comme par exemples les schmas trois niveauxdans lesquels on part de deux valeurs donnes x0 et x1 pour calculer x2, puis laide de x1 et x2 on calcule x3 etc.

    Dfinition Ordre de convergenceSoit p un entier positif. On dit quune mthode ( deux niveaux) convergente est dordre p sil existe une constante Ctelle que

    |xxk+1| C |xxk |p .Si p = 1 (et C < 1) on parle de convergence linaire, si p = 2 on parle de convergence quadratique.

    1.1. tape : localisation des zrosPour localiser grossirement le (ou les) zro(s) de f on va faire dabord une tude de la fonction f , puis on va utiliser les

    thormes suivants afin de trouver un intervalle qui contient un et un seul zro.

    Thorme Thorme des valeurs intermdiairesFormulation 1 Limage dun intervalle de R par une fonction continue est un intervalle de R.Formulation 2 Soit f une fonction continue sur un intervalle I = [a;b] de R. Alors f atteint toutes les valeurs interm-

    diaires entre f (a) et f (b). Autrement dit :? si f (a) f (b) alors pour tout d [ f (a), f (b)] il existe c [a;b] tel que f (c)= d ;? si f (a) f (b) alors pour tout d [ f (b), f (a)] il existe c [a;b] tel que f (c)= d .

    Ce thorme donne alors le corollaire immdiat suivant.Corollaire Thorme de BOLZANO ou des zros dune fonction continueSoit une fonction continue f : [a,b]R, si f (a) f (b)< 0, alors il existe (au moins un) x ]a,b[ tel que f (x)= 0.

    Ce thorme garantit juste lexistence dun zro. Pour lunicit on essayera dappliquer le thorme de la bijection dontlnonc est rappel ci-dessous.

    Thorme Thorme de la bijectionSoit f une fonction continue et strictement monotone sur un intervalle I de R, alors f induit une bijection de I dansf (I ). De plus, sa bijection rciproque est continue sur I , monotone sur I et de mme sens de variation que f .

    9

  • 1. Rsolution dquations non linaires Jeudi 31 janvier 2013

    1.2. tape : construction dune suite convergenteAyant encadr les zros de f , la construction de suites qui convergent vers ces zros peut se faire laide de plusieurs

    mthodes numriques. Ci-dessous on dcrit les mthodes les plus connues et on tudie leurs proprits (convergencelocale vs globale, vitesse de convergence, etc.).

    1.2.1. Mthodes de dichotomie (ou bissection), de Lagrange (ou Regula falsi) et de lascante

    Dans les mthodes de dichotomie et de LAGRANGE, chaque pas ditration on divise en deux un intervalle donn et onchoisit le sous-intervalle o f change de signe. Concrtement, soit une fonction numrique strictement monotone sur unintervalle [a,b]. On suppose que lquation f (x)= 0 na quune et une seule solution dans cet intervalle. On se propose dedterminer cette valeur avec une prcision donne. Soit [a0,b0] un intervalle dans lequel f (a0) f (b0)< 0 et soit c0 ]a0,b0[.Si f (a0) f (c0) < 0, alors la racine appartient lintervalle [a0,c0] et on reprend le procd avec a1 = a0 et b1 = c0. Sinon,cest--dire si f (a0) f (c0) > 0 on pose a1 = c0 et b1 = b0. On construit ainsi une suite dintervalles embots [ak ,bk ]. Lessuites ak et bk sont adjacentes et convergent vers x.

    Dfinition Mthodes de dichotomie et de LAGRANGESoit deux points a0 et b0 (avec a0 < b0) dimages par f de signe contraire (i.e. f (a0) f (b0)< 0). En partant de I0 = [a0,b0],les mthodes de dichotomie et de LAGRANGE (appele aussi Regula falsi) produisent une suite de sous-intervalles Ik =[ak ,bk ], k 0, avec Ik Ik1 pour k 1 et tels que f (ak ) f (bk )< 0.

    ? Dans la mthode de dichotomie, on dcoupe lintervalle [ak ;bk ] en deux intervalles de mme longueur, i.e. on divise[ak ;bk ] en [ak ;ck ] et [ck ;bk ] o ck est

    ck =ak +bk

    2.

    ? Dans la mthode de Lagrange, plutt que de diviser lintervalle [ak ;bk ] en deux intervalles de mme longueur, ondcoupe [ak ;bk ] en [ak ;ck ] et [ck ;bk ] o ck est labscisse du point dintersection de la droite passant par (ak , f (ak ))et (bk , f (bk )) et laxe des abscisses, i.e. est solution de lquation

    f (bk ) f (ak )bk ak

    (cak )+ f (ak )= 0

    qui est

    ck = ak bk ak

    f (bk ) f (ak )f (ak )=

    ak f (bk )bk f (ak )f (bk ) f (ak )

    .

    Dans les deux cas, pour litration suivante, on pose soit [ak+1;bk+1]= [ak ;ck ] soit [ak+1;bk+1]= [ck ;bk ] de sorte ce quef (ak+1) f (bk+1)< 0. La suite (ck )kN converge vers x puisque la longueur de ces intervalles tend vers 0 quand k tend vers+. Les algorithmes scrivent alors comme suit :

    DICHOTOMIE :

    Require: a, b > a, , f : [a,b]Rk 0ak abk bxk

    ak +bk2

    while bk ak > or | f (xk )| > doif f (ak ) f (xk )< 0 then

    ak+1 akbk+1 xk

    elseak+1 xkbk+1 bk

    end if

    xk+1 ak+1+bk+1

    2k k+1

    end while

    LAGRANGE :

    Require: a, b > a, , f : [a,b]Rk 0ak abk bxk ak

    bk akf (bk ) f (ak )

    f (ak )

    while bk ak > or | f (xk )| > doif f (ak ) f (xk )< 0 then

    ak+1 akbk+1 xk

    elseak+1 xkbk+1 bk

    end if

    xk+1 ak+1bk+1ak+1

    f (bk+1) f (ak+1)f (ak+1)

    k k+1end while

    10 G. Faccanoni

  • Jeudi 31 janvier 2013 1. Rsolution dquations non linaires

    ExempleSoit f (x)=3943x+39x25x3. On cherche a estimer x [1;5] tel que f (x)= 0.

    DICHOTOMIE

    f (x)=39+ (43+ (395x)x)x

    x

    y

    1

    f (1)=1

    5

    f (5)= 2

    3

    f (3)= 1

    2

    f (2)=0.1875 2.5

    f (2.5)= 0.3984375

    I0 = [1;5]I1 = [1;3]I2 = [2;3]

    I3 = [2;2.5]LAGRANGE

    f (x)=39+ (43+ (395x)x)x

    x

    y

    1

    f (1)=1

    5

    f (5)= 2

    2.3

    f (2.3)= 0.197530824 2.11f (2.11)=0.06002

    I0 = [1;5]I1 = [1;2.3]I2 = [2.11;2.3]

    RemarqueAvec la mthode de la dichotomie, les itrations sachvent la m-me tape quand |xm x| |Im | < , o est unetolrance fixe et |Im | dsigne la longueur de lintervalle Im . Clairement Ik = ba2k , donc pour avoir une erreur |xm x| < ,on doit prendre le plus petit m qui vrifie

    m log2ba

    .

    Notons que cette ingalit est gnrale : elle ne dpend pas du choix de la fonction f .

    Exemple Fond dinvestissementLe client dune banque dpose au dbut dune anne v euros dans un fonds dinvestissement et en retire, la fin de la n-me anne,

    un capital de M > v euros. Nous voulons calculer le taux dintrt annuel moyen T de cet investissement.Le capital final M est reli aux taux dintrt annuel moyen T par la relation

    M = vn

    k=1(1+T )k = v (1+T )

    n 1(1+T )1 = v

    1+TT

    ((1+T )n 1) .

    On en dduit que T est racine de lquation algbrique non linaire f (T )= 0 o

    f (T )= v 1+TT

    ((1+T )n 1)M .

    tudions la fonction f :? f (T )> 0 pour tout T > 0,? limT0+ f (T )= nv M < (n1)v , limT+ f (T )=+,? f (T )= v

    T 2(1+ (1+T )n (T n1))> 0 pour tout T > 0 (comparer le graphe de 1/(1+T )n et de nT 1)

    G. Faccanoni 11

  • 1. Rsolution dquations non linaires Jeudi 31 janvier 2013

    En tudiant la fonction f on voit que, comme nv < M ds que n > 1, elle admet un unique zro dans lintervalle ]0,+[ (on peutmme prouver que elle admet un unique zro dans lintervalle ]0, M [).

    Supposons que v = 1000 et quaprs 5 ans M est gal 6000. En tudiant la fonction f on voit quelle admet un unique zrodans lintervalle ]0.01,0.1[. Si on applique la mthode de la dichotomie avec = 1012, aprs 36 itrations la mthode converge vers0.06140241153618. On conclut ainsi que le taux dintrt T est approximativement gal 6.14%.

    La mthode de dichotomie est simple mais elle ne garantit pas une rduction monotone de lerreur dune itration lautre : tout ce dont on est assur, cest que la longueur de lintervalle de recherche est divise par deux chaque tape. Parconsquent, si le seul critre darrt est le contrle de la longueur de Ik , on risque de rejeter de bonnes approximations dex. En fait, cette mthode ne prend pas suffisamment en compte le comportement rel de f . Il est par exemple frappant quela mthode ne converge pas en une seule itration quand f est linaire ( moins que le zro x ne soit le milieu de lintervallede recherche initial).

    Dfinition Mthode de la ScanteIl sagit dune mthode trois niveaux : approcher les zros de f se ramne calculer la limite de la la suite rcurrente

    x0 donn,

    x1 donn,

    xk+1 = xk xk xk1

    f (xk ) f (xk1)f (xk ),

    Cette mthode a ordre 1+p

    52 .

    Remarque Interprtation gomtrique de la mthode de la scanteSoit f : RR une fonction continue et soit x [a,b] un zro de f . Pour calculer xk+1 on prend lintersection de laxe desabscisses avec la droite passant par les points (xk , f (xk )) et (xk1, f (xk1)), i.e. on cherche x solution du systme linaire{

    y = f (xk ) f (xk1)xkxk1 (xxk )+ f (xk ),y = 0,

    ce qui donne

    x = xk xk xk1

    f (xk ) f (xk1)f (xk ).

    On reconnat la mthode de la scante.

    1.2.2. Mthodes de point fixeEn samusant avec une calculatrice de poche ou avec le code python ci-dessous

    1 import math2 x = 13 for i in range (1,100):4 x = math.cos(x)5 print x_, i, =, x

    on peut vrifier quen partant de la valeur 1 et en appuyant plusieurs fois de suite sur la touche cosinus, on obtient cettesuite de valeurs :

    x0 = 1,x1 = cos(x0)= 0.540302305868,x2 = cos(x1)= 0.857553215846,x3 = cos(x2)= 0.654289790498,

    ...

    x55 = 0.739085133171,...

    x100 = 0.739085133215

    qui tend vers la valeur 0.73908513. . . . En effet, on a par construction xk+1 = cos(xk ) pour k = 0,1, . . . (avec x0 = 1). Si cettesuite converge, sa limite ` satisfait lquation cos(`)= `. Pour cette raison, ` est appel point fixe de la fonction cosinus.

    12 G. Faccanoni

  • Jeudi 31 janvier 2013 1. Rsolution dquations non linaires

    f

    y

    xa

    a

    b

    bx0

    x1

    x1

    x2

    x2

    x3

    x3

    x4

    x4

    x5

    x5

    x6

    ([a;b]) [a;b]0(x)< 1convergence

    f

    y

    xa

    a

    b

    bx0

    x1

    x1

    x2

    x2

    x3

    x3

    x4

    x4

    x5

    x5

    x6

    x6

    x7

    ([a;b]) [a;b]1 do

    xk+1 (xk )k k+1

    end whileNaturellement toute mthode de point fixe nest pas forcement convergente. Par contre, si elle converge, cest--dire si lasuite xk a une limite que nous notons x, et si est continue, alors cette limite est ncessairement un point fixe de puisque

    x = limk

    xk+1 = limk

    (xk )=(

    limk

    xk

    )=(x).

    On a le rsultat suivant :Thorme Convergence (globale) des itrations de point fixeConsidrons une fonction : [a;b] R. On se donne x0 [a;b] et on considre la suite xk+1 = (xk ) pour k 0. Si lesdeux conditions suivantes sont satisfaites :condition de stabilit : (x) [a,b] pour tout x [a,b]condition de contraction stricte : il existe K < 1 tel que |(x)(y)| K |x y | pour tout x, y [a,b]alors est continue, a un et un seul point fixe x dans [a,b] et la suite xk+1 =(xk ) converge vers x pour tout choix de x0dans [a,b].

    Dmonstration.

    G. Faccanoni 13

  • 1. Rsolution dquations non linaires Jeudi 31 janvier 2013

    Continuit La condition de contraction stricte implique que est continue puisque, si on prend une suite (yk )k [a,b]qui converge vers un lment x de [a,b], alors nous avons |(x)(yn)| K |x yn | et par suite limk(yk )=(x).

    Existence Commenons par prouver lexistence dun point fixe de . La fonction g (x)=(x) x est continue dans [a,b]et, grce la condition de stabilit, on a g (a) = (a) a 0 et g (b) = (b)b 0. En appliquant le thorme desvaleurs intermdiaires, on en dduit que g a au moins un zro dans [a,b], i.e. a au moins un point fixe dans [a,b].

    Unicit Lunicit du point fixe dcoule de la condition de contraction stricte. En effet, si on avait deux points fixes distinctsx1 et x2, alors

    |x1 x2| = |(x1)(x2)| K |x1 x2| < |x1 x2|ce qui est impossible.

    Convergence Prouvons prsent que la suite xk converge vers lunique point fixe x quand k tend vers + pour toutedonne initiale x0 [a;b]. On a

    0 |xk+1 x| = |(xk )(x)| K |xk x|o K < 1 est la constante de contraction. En itrant k+1 fois cette relation on obtient

    |xk+1 x| K k+1|x0 x|,

    i.e., pour tout k 0|xk+1 x||x0 x|

    K k+1.

    En passant la limite quand k tend vers + on obtient |xk+1 x| tend vers zro.

    RemarqueSi est de classe C 1([a,b]) et si |(x)| < 1 pour tout x [a,b], alors la condition de contraction stricte est satisfaite. Deplus, on a

    limk

    xk+1 xxk x

    =(x).

    Ce thorme assure la convergence, avec un ordre 1, de la suite (xk )kN vers le point fixe x pour tout choix dune valeurinitiale x0 [a;b]. Il constitue donc un exemple de rsultat de convergence globale. Mais en pratique, il est souvent difficilede dterminer a priori lintervalle [a;b] ; dans ce cas, le rsultat de convergence locale suivant peut tre utile.

    Thorme dOSTROWSKI ou de convergence (locale) des itrations de point fixeSoit x un point fixe dune fonction continue et diffrentiable dans un intervalle [a;b] contenant x. Si |(x)| < 1, alorsil existe un intervalle [c;d ] [a;b] tel que la suite (xk )k converge vers x pour tout x0 [c;d ]. De plus,? si 0 1 la suite diverge de faon monotone, tandis que pour(x)

  • Jeudi 31 janvier 2013 1. Rsolution dquations non linaires

    En gnral, la mthode de point fixe ne converge pas pour des valeurs arbitraires de x0, mais seulement pour des valeurssuffisamment proches de x, cest--dire appartenant un certain voisinage de x. Au premier abord, cette condition sembleinutilisable : elle signifie en effet que pour calculer x (qui est inconnu), on devrait partir dune valeur assez proche de x !En pratique, on peut obtenir une valeur initiale x0 en effectuant quelques itrations de la mthode de dichotomie ou enexaminant le graphe de f . Si x0 est convenablement choisi alors la mthode de point fixe converge.

    Proposition Calcul de lordre de convergence dune mthode de point fixeSoit x un point fixe dune fonction C p+1 pour un entier p 1 dans un intervalle [a;b] contenant x. Si(i )(x)= 0 pour1 i p et (p+1)(x) 6= 0, alors la mthode de point fixe associe la fonction ditration est dordre p+1.

    Mthodes de point fixe particulirement connuesSoit f : [a,b] R une fonction continue (continment drivable pour la mthode de la corde 2 et la mthode de NEW-TON) et soit x un zro de f . Supposons que lon connaisse une valeur x0 proche de x. Approcher les zros de f se ramneau problme de la dtermination des points fixes de la fonction , ce qui se fait en construisant la suite rcurrente{

    xk+1 =(xk ),x0 donn.

    Considrons les fonctions suivantes qui dfinissent des mthodes clbres :

    Mthode de la Corde 1 : (xk )= xk ba

    f (b) f (a) f (xk ) ordre : 1

    Mthode de la Corde 2 : (xk )= xk f (xk )

    f (x0)ordre : 1

    Mthode de Newton : (xk )= xk f (xk )

    f (xk )ordre :

    {2 si x est une racine simple

    1 sinon

    Preuve de lordre de convergence de la mthode de NewtonSoit la mthode de Newton pour le calcul de ` zro de f . Cette mthode peut tre mise sous la forme dune itration depoint fixe un+1 =(un) en posant

    (x)= x f (x)f (x)

    .

    ? Si f (`) 6= 0 (i.e. si ` est racine simple), on trouve

    (x)= 1 ( f(x))2 f (x) f (x)

    ( f (x))2= f (x) f

    (x)( f (x))2

    , (`)= 0,

    (x)= f(x)

    f (x)+ f (x) f

    (x)( f (x))2

    2 f (x)( f(x))2

    ( f (x))3, (`)= f

    (`)f (`)

    .

    La mthode de Newton est donc dordre 2.? Si la racine ` est de multiplicit m > 1, alors la mthode nest plus du second ordre. En effet, f (x)= (x`)mh(x) o h

    est une fonction telle que h(`) 6= 0. On a alors

    (x)= 1 f (x)f (x)

    = 1 (x`)h(x)mh(x)+ (x`)h(x) ,

    (x)= h(x)(m(m1)h(x)+2(x`)h(x)+ (x`)2h(x))(

    mh(x)+ (x`)h(x))2 , (`)= 1 1m .Si la valeur de m est connue a priori, on peut retrouver la convergence quadratique en modifiant la mthode de New-ton comme suit :

    (x)= xm f (x)f (x)

    .

    Remarque Interprtation gomtrique de la mthode de NEWTON et des mthodes de la cordeSoit f : RR une fonction continment drivable et soit x un zro simple de f , cest--dire f (x)= 0 et f (x) 6= 0. Suppo-sons que lon connaisse une valeur xk proche de x. Pour calculer xk+1 on prend lintersection de laxe des abscisses avec

    G. Faccanoni 15

  • 1. Rsolution dquations non linaires Jeudi 31 janvier 2013

    la droite tangente au graphe de f passant par le point (xk , f (xk )), i.e. on cherche x solution du systme linaire{y = f (xk )(xxk )+ f (xk ),y = 0.

    On obtient

    x = xk f (xk )

    f (xk )ce qui correspond la mthode de NEWTON.

    x

    yf

    y = f (x0)(xx0)+ f (x0)

    y = f (x1)(xx1)+ f (x1)

    xx0x1x2

    Soit f : RR une fonction continue et soit x [a,b] un zro de f . Cette fois-ci, pour calculer xk+1 on prend lintersectionde laxe des abscisses avec la droite passant par le point (xk , f (xk )) et parallle la droite passant par les points (a, f (a))et (b, f (b)), i.e. on cherche x solution du systme linaire{

    y = f (b) f (a)ba (xxk )+ f (xk ),y = 0,

    ce qui donne

    x = xk ba

    f (b) f (a) f (xk ).

    Il sagit de la mthode de la corde 1. Cette mthode permet dviter qu chaque itration on ait valuer f (xk ) car onremplace f (xk ) par

    f (b) f (a)ba .

    x

    y

    f

    a b

    y = f (b) f (a)ba (xx0)+ f (x0)

    y = f (b) f (a)ba (xx1)+ f (x1)

    xx0

    x1x2

    16 G. Faccanoni

  • Jeudi 31 janvier 2013 1. Rsolution dquations non linaires

    Une variante de la mthode de la corde consiste calculer xk+1 comme lintersection entre laxe des abscisses et la droitepassant par le point (xk , f (xk )) et parallle la droite tangente au graphe de f passant par le point (x0, f (x0)), i.e. oncherche x solution du systme linaire {

    y = f (x0)(xxk )+ f (xk ),y = 0,

    ce qui donne

    x = xk f (xk )

    f (x0)

    Dans cette variante on remplace f (xk ) par f (x0).

    x

    y

    f

    y = f (x0)(xx0)+ f (x0)

    y = f (x0)(xx1)+ f (x1)

    xx0x1x2

    ExempleOn se trouve en possession dune calculatrice qui ne sait effectuer que les oprations addition, soustraction et multiplication. Lorsquea > 0 est donn, on veut calculer sa valeur rciproque 1/a. Le problme peut tre ramen rsoudre lquation x = 1/a ce qui quivaut chercher le zro de la fonction

    f : R+ R

    x 7 1xa

    Selon la formule de NEWTON on axk+1 = (1+a)xk +x2k ,

    une rcurrence qui ne requiert pas de divisions. Pour a = 7 et partant de x0 = 0.2 par exemple, on trouve x1 = 0,12, x2 = 0,1392,x3 =0,1427635200, x4 = 0,1428570815, etc. Cette suite converge vers 1/7' 0,142857142857.

    Exemple Comparaison des mthodes de Newton pour diffrentes formulation de la fonction initialeDans R+ on veut rsoudre lquation

    x = e1/x . (1.1)En transformant lquation donne de diffrentes manires, on arrive diffrentes formules de rcurrence :

    1. Lquation (1.1) quivaut chercher le zro de la fonction

    f : R+Rx 7 xe1/x

    En utilisant la mthode de Newton on trouve la formule itrative

    xk+1 = xk f (xk )

    f (xk )= xk

    xk e1/xk1+ e1/xk

    x2k

    = xk x2kxk e1/xkx2k +e1/xk

    .

    2. Si on pose y = 1/x, alors on a lquivalencex = e1/x y = ey ,

    G. Faccanoni 17

  • 1. Rsolution dquations non linaires Jeudi 31 janvier 2013

    donc la solution x de lquation (1.1) est la rciproque du zro de la fonction

    g : R+Ry 7 1 ye y

    En utilisant la mthode de Newton on trouve la formule itrative

    yk+1 = yk g (yk )

    g (yk )= yk

    1 yk e yk(1+ yk )e yk

    = yk +eyk yk

    1+ yket xk = 1/yk .

    3. Lquation (1.1) est encore quivalente chercher le zro de la fonction

    h : R+Rx 7 1x ln(x)

    En utilisant la mthode de Newton on trouve la formule itrative

    xk+1 = xk h(xk )

    h(xk )= xk +

    1xk ln(xk )1+ ln(xk )

    = 1+xk1+ ln(xk )

    .

    La reprsentation graphique de f montre quil nexiste quune seule racine. Comme f (1.7) f (1.9) < 0, elle se trouve dans lintervalle[1.7;1.9]. En partant de x0 = 1.8 on trouve les suites suivantes :

    Formule 1 Formule 2 Formule 3x1 = 1,7628781412 1.7418849724 1.7634610883x2 = 1.7632228030 1.7751466845 1.7632228446x3 = 1.7632228344 1.7564077294 1.7632228344

    La solution est x ' 1,76322283435.Attention noter que mme si la mthode de NEWTON permet en gnral dobtenir une convergence quadratique, un mauvaischoix de la valeur initiale peut provoquer la divergence de cette mthode (notamment si la courbe reprsentative de fprsente au point dabscisse x0 un tangente peu prs horizontale). Do limportance dune tude pralable soigne dela fonction f (cette tude est dailleurs ncessaire pour toute mthode de point fixe).

    Critres darrtSupposons que (xn)n soit une suite qui converge vers x zro de la fonction f . Nous avons le choix entre deux types decritres darrt pour interrompre le processus itratif dapproximation de x : ceux bass sur le rsidu et ceux bass surlincrment. Nous dsignerons par une tolrance fixe pour le calcul approch de x et par en = x xn lerreur absolue.Nous supposerons de plus f continment diffrentiable dans un voisinage de la racine.Contrle du rsidu : les itrations sachvent ds que | f (xn)| < . Il y a des situations pour lesquelles ce test

    savre trop restrictif ou, au contraire, trop optimiste.? si | f (x)| ' 1 alors |en | ' : le test donne donc une indication satisfaisante de lerreur ;? si | f (x)| 1, le test nest pas bien adapt car |en | peut tre assez grand par rapport ;? si enfin | f (x)| 1 alors |en | et le test est trop restrictif.Dans lexemple prcdent f (x)= 2p2 1 : le test est trop restrictif (comparer la colonne | f (xn)| la colonne |xxn |).

    Contrle de lincrment : les itrations sachvent ds que |xn+1xn | < . Soit (xn)n la suite produite par la m-thode de point fixe xn+1 = (xn). Comme x = (x) et xn+1 = (xn), on obtient par un dveloppement au premierordre

    en+1 = xxn+1 =(x)(xn)=(n)(xxn)=(n)en , n I x,xnI x,xn tant lintervalle dextrmits x et xk . En utilisant lidentit

    en = (xxn+1)+ (xn+1xn)= en+1+ (xn+1xn)=(n)en + (xn+1xn),

    on en dduit que

    en = xn+1xn1(n)

    .

    Par consquent, ce critre fournit un estimateur derreur satisfaisant si (x) ' 0 dans un voisinage de x. Cest lecas notamment des mthodes dordre 2, dont la mthode de Newton. Cette estimation devient dautant moinsbonne que sapproche de 1.

    18 G. Faccanoni

  • Jeudi 31 janvier 2013 1. Rsolution dquations non linaires

    x

    y

    f

    f (xk )

    xk

    ek

    xx

    y

    f

    f (xk )xk

    ek

    x

    FIGURE 1.2.: Deux situations pour lesquelles le rsidu ek = xk x est un mauvais estimateur derreur : | f (x)| >> 1 (gauche), | f (x)|

  • 1. Rsolution dquations non linaires Jeudi 31 janvier 2013

    TTTTTTTTTTTTT Codes Python TTTTTTTTTTTTdichotomie, lagrange, newton et point_fix sont quatre fonctions (informatiques) qui renvoient la valeur approche

    du zro dune fonction (mathmatique) f . En paramtre elles reoivent f, la fonction dont on cherche la racine, a et b sontles extrmits de lintervalle de recherche pour les mthodes de dichotomie et de LAGRANGE, x_init est la donne initialepour les mthodes de NEWTON et de point fixe, maxITER est le nombre maximal ditrations et tol est la tolrance. Ellesrenvoient

    Mthodes numriques.

    1 #!/usr/bin/python2 #-*- coding: Utf-8 -*-3

    4 import math, sys5

    6 def dichotomie(f,a,b,tol,maxITER):7 fa = f(a)8 if abs(fa)tol)) and (k

  • Jeudi 31 janvier 2013 1. Rsolution dquations non linaires

    57 x = x_init58 fx = f(x)59 h = tol60 dfx = (f(x+h)-fx)/h # calcul approche de f(x)61 while ( (abs(fx)>tol) and (ktol) and (k

  • 1. Rsolution dquations non linaires Jeudi 31 janvier 2013

    115 x_init = 0.116 print "E) Zero calcule par la methode de Newton a partir du point x_0 =",x_init," : ", newton(f,x_init,tol

    ,maxITER)117 print "F) Zero calcule par la methode de point fix a partir du point x_0 =",x_init," : ", point_fix(phi,

    x_init,tol,maxITER)118

    119 x_init = 1.120 print "G) Zero calcule par la methode de Newton a partir du point x_0 =",x_init," : ", newton(f,x_init,tol

    ,maxITER)121 print "H) Zero calcule par la methode de point fix a partir du point x_0 =",x_init," : ", point_fix(phi,

    x_init,tol,maxITER)122

    123

    124 # Dans python il existe un module qui implement deja ces methodes, comparons nos resultats avec ceux dumodule:

    125 from scipy.optimize import fsolve126 x_init = 0.127 print "** Zero calcule par le module scipy.optimize a partir du point x_0 =",x_init," : ", fsolve(f,x_init

    )128 x_init = 1.129 print "** Zero calcule par le module scipy.optimize a partir du point x_0 =",x_init," : ", fsolve(f,x_init

    )

    22 G. Faccanoni

  • Jeudi 31 janvier 2013 1. Rsolution dquations non linaires

    .............. Exercices .............Exercice 1.1Dcrire les mthodes de la dichotomie et de LAGRANGE et les utiliser pour calculer le zro de la fonction

    f (x)= x34x8.95

    dans lintervalle [2;3] avec une prcision de 102.

    CORRECTION. En partant de I0 = [a,b], les mthodes de la dichotomie et de LAGRANGE produisent une suite de sous-intervalles Ik = [ak ,bk ], k 0, avec Ik Ik1, k 1, et tels que f (ak ) f (bk )< 0. Dans notre cas on a

    k 0ak 2bk 3while |bk ak | > 0.01 do

    xk g (ak ,bk )k k+1if (a3k 4ak 8.95)(x3k 4xk 8.95)< 0 then

    ak+1 akbk+1 xk

    elseak+1 xkbk+1 bk

    end ifend while

    avec

    g (ak ,bk )={ ak+bk

    2 pour la mthode de la dichotomie,ak f (bk )bk f (ak )

    f (bk ) f (ak ) pour la mthode de la LAGRANGE.

    Dichotomiek ak xk bk signe de f (ak ) signe de f (xk ) signe de f (bk )0 2.000000 2.5000000 3.00000 +1 2.500000 2.7500000 3.00000 + +2 2.500000 2.6250000 2.75000 +3 2.625000 2.6875000 2.75000 +4 2.687500 2.7187500 2.75000 + +5 2.687500 2.7031250 2.71875 +6 2.703125 2.7109375 2.71875 + +

    LAGRANGEk ak xk bk signe de f (ak ) signe de f (xk ) signe de f (bk )0 2.000000 2.596666667 3.00000 +1 2.596666667 2.690262642 3.00000 +2 2.690262642 2.702092263 3.00000 +3 2.702092263 2.703541518 3.00000 +4 2.703541518 2.703718378 3.00000 +5 2.703718378 2.703739951 3.00000 +6 2.703739951 2.703742582 3.00000 +

    Exercice 1.2Dterminer la suite des premiers 3 itrs des mthodes de dichotomie dans lintervalle [1,3] et de Newton avec x0 = 2pour lapproximation du zro de la fonction f (x) = x22. Combien de pas de dichotomie doit-on effectuer pour am-liorer dun ordre de grandeur la prcision de lapproximation de la racine ?

    CORRECTION. On cherche les zros de la fonction f (x)= x22 :? Mthode de la dichotomie : en partant de I0 = [a,b], la mthode de la dichotomie produit une suite de sous-intervalles

    Ik = [ak ,bk ] avec Ik+1 Ik et tels que f (ak ) f (bk )< 0. Plus prcisment? on pose a0 = a, b0 = b, x0 = a0+b02 ,

    G. Faccanoni 23

  • 1. Rsolution dquations non linaires Jeudi 31 janvier 2013

    f (x)

    x

    y

    1

    1

    3

    7

    2

    2

    32

    14

    54

    716

    I0I1

    I2I3I4

    (a) Mthode de la dichotomie.

    f (x)

    x

    y

    232

    1712

    (b) Mthode de Newton.

    FIGURE 1.3.: Approximation du zro de la fonction f (x)= x22.

    ? pour k 0? si f (ak ) f (xk )< 0 on pose ak+1 = ak , bk+1 = xk sinon on pose ak+1 = xk , bk+1 = bk? et on pose xk+1 = ak+1+bk+12 .

    Voir la figure 1.3a.? Mthode de Newton :

    xk+1 = xk f (xk )

    f (xk )= xk

    x2k 22xk

    = 12

    xk +1

    xk.

    Voir la figure 1.3b.Donc on a le tableau suivant

    x0 x1 x2 x3

    Dichotomie 2 32 = 1,5 54 = 1,25 118 = 1,375Newton 2 32 = 1,5 1712 = 1,416 1724 + 1217 ' 1,4142156

    On rappelle quavec la mthode de la dichotomie, les itration sachvent la m-me tape quand |xm x| |Im | < , o est une tolrance fixe et |Im | dsigne la longueur de lintervalle Im . Clairement Ik = ba2k , donc pour avoir |xm x| < ondoit prendre

    m log2ba

    .

    Amliorer dun ordre de grandeur la prcision de lapproximation de la racine signifie avoir

    |xk x| =|x j x|

    10

    donc on doit effectuer k j = log2(10)' 3,3 itrations de dichotomie.

    Exercice 1.3

    1. Donner la suite dfinissant la mthode de Newton pour la recherche dun zro de fonction. Justifier lexpressionde la suite.

    2. crire lalgorithme pour une convergence 106 prs.3. Dterminer lordre de convergence minimale de cette suite.

    24 G. Faccanoni

  • Jeudi 31 janvier 2013 1. Rsolution dquations non linaires

    CORRECTION.1. Supposons f C 1 et f (x) 6= 0 (cest--dire x est une racine simple de f ). La mthode de Newton revient calculer le

    zro de f en remplaant localement f par sa tangente : en partant de lquation de la tangente la courbe (x, f (x))au point xk

    y(x)= f (xk )+ f (x)(xxk )et en faisant comme si xk+1 vrifiait y(xk+1)= 0, on obtient

    xk+1 = xk f (xk )

    f (xk ).

    tant donn une valeur initiale x(0), cette formule permet de construire une suite xk .2. Algorithmes pour une convergence = 106 :

    Require: x0, x 7 f (x)while |xk+1xk | > 106 do

    xk+1 xk f (xk )f (xk )end while

    3. La relation prcdent peut tre mise sous la forme dune itration de point fixe xk+1 = g (xk ) avec

    g (x)= x f (x)f (x)

    .

    Si x est racine simple, cest--dire si f (x) 6= 0, on trouve g (x) = 0 et g (x) = f (x)f (x) : la mthode de Newton est doncdordre 2. Si la racine x est de multiplicit m > 1, alors g (x) = 1 1m et la mthode nest que dordre 1. Si la valeurde m est connue priori, on peut retrouver la convergence quadratique de la mthode de Newton en modifiant lamthode comme suit :

    xk+1 = xk mf (xk )

    f (xk ).

    Exercice 1.4On veut calculer le zro de la fonction

    f (x)= x22dans lintervalle [0;2].

    1. On applique la mthode de LAGRANGE : crire lalgorithme et lutiliser pour remplir le tableau (on sarrtera auplus petit k qui vrifie | f (xk )| < 104).

    k ak xk bk signe de f (ak ) f (xk ) signe de f (bk ) |xk p

    2|0 0.00000 1.00000 2.00000 -1.00000 + 0.414211...

    2. On applique la mthode de NEWTON : crire lalgorithme et lutiliser pour remplir le tableau (on sarrtera au pluspetit k qui vrifie | f (xk )| < 104). Le point de dpart x0 est donn.

    k xk f (xk ) |xk p

    2|0 1.000001...

    CORRECTION.

    1. En partant de I0 = [a,b], la mthode de LAGRANGE produit une suite de sous-intervalles Ik = [ak ,bk ], k 0, avecIk Ik1, k 1, et tels que f (ak ) f (bk )< 0. Dans notre cas on a

    k 0ak 0bk 2xk akwhile |x2k 2| > 0.0001 do

    xk ak bk+2ak+bkif (a2k 2)(x2k 2)< 0 then

    ak+1 ak

    G. Faccanoni 25

  • 1. Rsolution dquations non linaires Jeudi 31 janvier 2013

    bk+1 xkelse

    ak+1 xkbk+1 bk

    end ifk k+1

    end whilek ak xk bk signe de f (ak ) | f (xk )| signe de f (bk ) |xk

    p2|

    0 0.00000 1.00000 2.00000 |-1.00000|>0.0001 + 0.414211 1.00000 1.33333 2.00000 |-0.22222|>0.0001 + 0.080882 1.33333 1.40000 2.00000 |-0.04000|>0.0001 + 0.014213 1.40000 1.41176 2.00000 |-0.00692|>0.0001 + 0.002454 1.41176 1.41379 2.00000 |-0.00119|>0.0001 + 0.000425 1.41379 1.41414 2.00000 |-0.00020|>0.0001 + 0.000076 1.41414 1.41420 2.00000 |-0.00004| 104 do

    xk+1 xk2 + 1xkk k+1

    end while

    k xk | f (xk )| |xk p

    2|0 1.00000 |-1.00000|>0.0001 0.414211 1.50000 |0.25000|>0.0001 0.085792 1.41667 |0.00695|>0.0001 0.002463 1.41422 |0.00002|

  • Jeudi 31 janvier 2013 1. Rsolution dquations non linaires

    ? si |i (`)| = 1, on ne peut en gnral tirer aucune conclusion : selon le problme considr, il peut y avoir convergenceou divergence.

    ? Enfin, si ( j )i (`)= 0 pour 1 j p et (p+1)i (`) 6= 0, alors la mthode de point fixe associe la fonction ditration i

    est dordre p+1.Calculons donc i (`) pour i = 1,2,3,4 :

    1. 1(x)=3x2+2x7 et 1(1)=8 : la suite diverge en oscillant (colonne C) ;2. 2(x)= 3x

    3(8x)+(8x3)(8x)2 et

    2(1)= 1449 : la suite converge de faon oscillante (colonne D) ;

    3. 3(x)= 310 x2+1

    5x+ 1

    5et 3(1)= 410 : la suite converge de faon monotone (colonne A ou B) ;

    4. 4(x)= (6x22x)(3x22x+8)(2x3x2+8)(6x2)

    (3x22x+8)2 et 4(1)= 0 : la suite converge lordre au moins 2 (colonne B).

    Exercice 1.6Entre deux murs (verticaux) parallles, on place deux chelles en les croisant. La premire fait 3m de long, la seconde2m. On constate quelles se croisent une hauteur de 1m. Quelle est la distance entre les deux murs ?

    CORRECTION. Avec un peu de trigonomtrie, on obtient une mise en quation de cette distance d sous la forme : d =2sin()= 3sin() et 12cos() + 13cos() = 1. Il reste rsoudre 1p4d 2 +

    1p9d 2 = 1.

    Exercice 1.7Soit la fonction f(x) = cosh(x)+ cos(x). Pour = 1,2,3 trouver (graphiquement) un intervalle qui contient le zrode f. Calculer ce dernier par la mthode de dichotomie avec une tolrance de 1010. Utiliser ensuite la mthode deNewton. Pourquoi cette mthode nest-elle pas prcise quand = 2 ?

    CORRECTION.

    tude de f. On se rappelle que cosh(x)= ex+ex2 et sinh(x)= exex

    2 donc? limx f(x)=+? f (x)= sinh(x) sin(x) et f (x)= 0 si et seulement si x = 0 (comparer les graphes de sinh et sin et se rappeler que

    pour x > 0 on a sinh(x)> x > sin(x) et pour x < 0 on a sinh(x)< x < sin(x))? f (x)= cosh(x)cos(x)> 0 pour tout x 6= 0.par consquent? pour = 1, la fonction na pas de zro rel,? pour = 2 il ny a que le zro x = 0 et il est de multiplicit quatre (cest--dire f2(x)= f 2a(x)= f 2 (x)= f 2 (x)= 0 et

    f (IV )2 (x) 6= 0),? pour = 3, f3 admet deux zros distincts, un dans lintervalle ]3,1[ et lautre dans ]1,3[.

    x

    y

    y = f1(x)

    y = f2(x)

    y = f3(x)

    Mthode de la dichotomie. Dans le cas = 2, la mthode de dichotomie ne peut pas tre utilise car il est impossiblede trouver un intervalle ]a,b[ sur lequel f2(a) f2(b) < 0. Pour = 3, en partant de [a,b] = [3,1], la mthode dedichotomie converge en 34 itrations vers la valeur x = 1.85792082914850 avec f3(x) ' 3.61012. De mme, enprenant [a,b]= [1,3], la mthode de dichotomie converge en 34 itrations vers la valeur x = 1.85792082914850 avecf3(x)'3.68771012.

    Mthode de Newton. Considrons le cas o = 2. En partant de la donne initiale x0 = 1, la mthode de NEWTONconverge vers la valeur x = 1.4961104 en 31 itrations avec = 1010 tandis que la racine exacte de f2 est 0. Cetcart est d au fait que f2 est quasiment constante au voisinage de sa racine, donc le problme de recherche du zroest mal conditionn. La mthode converge vers la mme solution et avec le mme nombre ditrations mme si onprend gal au zro machine. Considrons le cas = 3. La mthode de Newton avec gal au zro machine convergevers 1.85792082915020 aprs 9 itrations en partant de x0 = 1, alors que si x0 = 1, elle converge aprs 9 itrationsvers 1.85792082915020.

    G. Faccanoni 27

  • 1. Rsolution dquations non linaires Jeudi 31 janvier 2013

    Voici les instructions :

    130 def f(x):131 return math.cosh(x)+math.cos(x)-gamma132

    133 maxITER = 100134

    135 gamma = 3136 tol = 1.0e-15137 a = -3.138 b = -1.139 x_init = -1.140 print "Zero calcule par la methode de dichotomie dans lintervalle [", a, ",", b,"] : ", dichotomie(f,a,b,

    tol,maxITER)141 print "Zero calcule par la methode de Newton a partir du point x_0 =",x_init," : ", newton(f,x_init,tol,

    maxITER)142 a = 1.143 b = 3.144 x_init = 1.145 print "Zero calcule par la methode de dichotomie dans lintervalle [", a, ",", b,"] : ", dichotomie(f,a,b,

    tol,maxITER)146 print "Zero calcule par la methode de Newton a partir du point x_0 =",x_init," : ", newton(f,x_init,tol,

    maxITER)147

    148 gamma = 2149 tol = 1.0e-10150 x_init = -1.151 print "Zero calcule par la methode de Newton a partir du point x_0 =",x_init," : ", newton(f,x_init,tol,

    maxITER)152 x_init = 1.153 print "Zero calcule par la methode de Newton a partir du point x_0 =",x_init," : ", newton(f,x_init,tol,

    maxITER)

    Exercice 1.8 quation dtat dun gazNous voulons dterminer le volume V occup par un gaz dont la temprature est T et dont la pression est p. Lquationdtat (i.e. lquation liant p, V et T ) selon le modle de VAN DER WAALS est donne par(

    p+a(

    N

    V

    )2)(V N b)= kN T,

    o a et b sont deux coefficients qui dpendent du gaz considr, N est le nombre de molcules contenues dans le volumeV et k est la constante de Boltzmann. Nous devons donc rsoudre une quation non linaire dont la racine est V .Pour le dioxyde de carbone CO2, les coefficients a et b dans prennent les valeurs suivantes : a = 0.401Pam3 etb = 42.7106 m3. Trouver le volume occup par 1000 molcules de CO2 la temprature T = 300K et la pres-sion p = 3.5107 Pa par la mthode de dichotomie, avec une tolrance de 1012 (la constante de Boltzmann vautk = 1.38065031023 JK1).

    CORRECTION. On doit calculer les zros de la fonction f (V )= pV +aN 2/V abN 3/V 2pN bkN T , o N est le nombrede molcules. On a

    ? limV0+ f (V )= et limV+ f (V )=+? f (V )= paN 2/V 2+2abN 3/V 3 = p+aN 2(2bN /V 1)/V 2? f (V )= 0 si et seulement si p

    aN 2V 3V =2bN donc pour aucun V > 0.

    En traant le graphe de f , on voit que cette fonction na quun zro simple dans lintervalle ]0.01,0.06[ avec f (0.01) < 0 etf (0.06)> 0. On peut calculer ce zro en utilisant la mthode de dichotomie comme suit :

    154 def f(V):155 a = 0.401156 b = 42.7e-6157 N = 1000.158 T = 300.159 p = 3.5e7160 k = 1.3806503e-23161 return p*V+a*N**2/V-a*b*N**3/V**2-p*N*b-k*N*T

    28 G. Faccanoni

  • Jeudi 31 janvier 2013 1. Rsolution dquations non linaires

    162

    163 tol = 1.0e-12164 left = 0.01165 right = 0.06166

    167 print "Zero calcule par la methode de dichotomie dans lintervalle [", left, ",", right,"] : ", dichotomie(f,left,right,tol,maxITER)

    ce qui donne V = 0.0426999999999m3.

    Exercice 1.9Soit A est un nombre positif donn et considrons lalgorithme suivant : tant donn une valeur x0, on calcule

    xk+1 = xk +Ax2k

    2, k = 0,1,2, . . .

    1. Montrer que si la suite xk converge, alors sa limite est soitp

    A soit pA.2. On considre le cas o A ]0,4[. Montrer quil existe > 0 tel que, si |x0

    pA| alors la suite xk converge versp

    A.

    3. Vrifier graphiquement que si x0 est proche de p

    A mais diffrent de pA, alors la suite xk ne converge pas verspA.

    4. Vrifier que si x0 = 1, alors lalgorithme concide avec la mthode de la corde 2 pour rsoudre x2 A = 0.5. Proposer un algorithme plus efficace pour calculer la racine carre dun nombre positif A.

    CORRECTION.

    1. Supposons que xk converge vers `. En passant la limite dans la formule de rcurrence on obtient

    `= `+ A`2

    2,

    cest--dire `2 = A et donc `=pA.2. La mthode peut scrire sous la forme dune mthode de point fixe o la fonction est dfinie par

    (x)= x+ Ax2

    2.

    Si A ]0,4[ et `=pA, puisque (x)= 1 x, alors |(`)| = |1pA| < 1 : on peut appliquer le thorme dOSTROWSKIdonc il existe > 0 tel que, si |x0

    pA| alors la suite xk converge vers

    pA.

    3. On a reprsent dans la figure ci-dessous le graphe de la fonction lorsque A = 1/2. Si on choisit x0 < p

    A alorsla suite diverge vers ; si pA < x0 2+

    pA alors la suite diverge vers .

    y = xy

    x

    pA

    pA

    pA

    pA 2+pAx0

    x1

    x1

    x2

    x2 x3x3

    x4

    x4

    x5

    4. Soit f la fonction dfinie par f (x)= x2 A. La mthode de la corde 2 pour rsoudre f (x)= 0 scrit dans ce cas

    xk+1 = xk f (xk )

    f (x0)= xk

    x2k A2x0

    , k = 0,1,2, . . . .

    G. Faccanoni 29

  • 1. Rsolution dquations non linaires Jeudi 31 janvier 2013

    Si on choisit x0 = 1, cette mthode scrit donc

    xk+1 = xk f (xk )

    f (x0)= xk

    x2k A2

    , k = 0,1,2, . . . .

    Ainsi on conclut que la mthode donne concide avec la mthode de la corde 2 pour rsoudre x2 A = 0 lorsquex0 = 1 comme point de dpart.

    5. Si on choisit la mthode de Newton pour rsoudre f (x)= 0 avec f (x)= x2 A, on a

    xk+1 = xk f (xk )

    f (xk )= xk

    x2k A2xk

    , k = 0,1,2, . . . .

    Cette mthode est plus efficace que la prcdente car elle converge lordre 2 pour tout x0 > 0.

    Exercice 1.10Soit f : RR la fonction dfinie par f (x)= x32. On veut approcher le zro de f par la mthode de point fixe suivante :{

    x0 donn,

    xk+1 = g(xk ) pour tout k 0,(1.2)

    avec g : RR la fonction dfinie par g(x)= (1)x3+(1 3

    )x+2(1)+ 2

    3x2, R.

    1. Pour quelles valeurs du paramtre la mthode de point fixe (1.2) est-elle consistante (i.e. est un point fixe deg) ?

    2. Pour quelles valeurs du paramtre la mthode de point fixe (1.2) est-elle dordre 2 ?

    3. Existe-t-il des valeurs du paramtre pour lesquelles la mthode de point fixe (1.2) est-elle dordre 3 ?

    CORRECTION. Comme est le zro de f , on a 3 = 2.1. La mthode de point fixe (1.2) est consistante pour tout R car

    g()= (1)3+(1

    3

    )+2(1)+ 2

    32= (1)(32)+

    (1

    3

    )+ 2

    32=

    3+ 2

    32= (

    32)32

    =.

    2. La mthode de point fixe (1.2) est au moins dordre 2 si g ()= 0. On a

    g ()= 3(1)2+1

    3 4

    33= 3(1)2+1= (1)(32+1)

    donc la mthode de point fixe (1.2) est au moins dordre 2 si = 1.3. Pour que la mthode de point fixe (1.2) soit dordre 3 il faudrait g ()= g ()= 0. Puisque g ()= 0 si et seulement si

    = 1 et g 1 ()= 44 6= 0, il nest pas possible davoir une convergence dordre suprieur 2.

    Exercice 1.11On considre le problme du calcul de ` [0,pi] tel que `= 1 14 cos(`).

    1. Montrer quon peut utiliser la mthode de la dichotomie pour approcher `. Que vaut lapproximation de ` aprs 3itrations ? Quel est lerreur maximale quon obtient aprs 3 itrations ?

    k 0 1 2 3[ak ,bk ] [0,pi]`k

    pi2

    2. On considre la mthode de point fixe suivante :{x0 [0,pi],xk+1 = g (xk ) pour tout k 0,

    (1.3)

    avec g : [0,pi]R la fonction dfinie par g (x)= 1 14 cos(x).2.1. tudier graphiquement la convergence de cette mthode.

    2.2. Montrer rigoureusement que la mthode converge pour tout x0 [0,pi].2.3. Montrer que lerreur satisfait lingalit |xk `| C k |x0 `|. Donner une estimation de la constante C et

    lutiliser pour minorer le nombre ditrations ncessaires pour approcher ` 103 prs.

    30 G. Faccanoni

  • Jeudi 31 janvier 2013 1. Rsolution dquations non linaires

    2.4. Montrer que si on utilise le critre darrt |xk+1xk | alors |xk+1`| 1C . Quelle valeur de faut-il choisirpour approcher ` 103 prs ?

    CORRECTION.

    1. Soit f : [0,pi]R la fonction dfinie par f (x)= 1 14 cos(x)x. Elle est de classeC, f (0)= 3/4> 0 et f (pi)= 5/4pi `.

    g

    y

    x

    pi

    pix0 x1x2 x0x1x2

    5434

    2.2. g ([0,pi])= [3/4,5/4] [0,pi] et |g (x)| 1/4< 1 : la mthode de point fixe converge vers ` pour tout x0 [0,pi].2.3. Pour tout k N il existe k compris entre ` et xk tel que |xk`| = |g (xk1)g (`)| |g (k )||xk1`| 14k |x0`|

    pi4k

    . Donc, pour approcher ` 103 prs, il faut prendre le plus petit k N qui vrifie k log4(103pi) 5.9, i.e.k = 6.

    2.4. Pour tout k N on a |xk `| |xk+1xk | |xk+1xk +xk `| = |xk+1`| C |xk `| avec C = 1/4 do

    |xk+1`| 1

    1C |xk+1xk |

    1C .

    Pour que lerreur soit infrieur 103 il faut alors choisir (1C )103.

    Exercice 1.12On considre le problme du calcul de ` [0,pi] tel que `= 1+ 12 sin(`).

    1. Montrer quon peut utiliser la mthode de la dichotomie pour approcher `. Que vaut lapproximation de ` aprs 3itrations ?

    2. On considre la mthode de point fixe suivante :{x0 [0,pi],xk+1 = g (xk ) pour tout k 0,

    (1.4)

    avec g : [0,pi]R la fonction dfinie par g (x)= 1+ 12 sin(x).2.1. tudier graphiquement la convergence de cette mthode.

    2.2. Montrer rigoureusement que la mthode converge pour tout x0 [0,pi].2.3. Montrer que lerreur satisfait lingalit |xk `| C k |x0 `|. Donner une estimation de la constante C et

    lutiliser pour minorer le nombre ditrations ncessaires pour approcher ` 103 prs.2.4. Montrer que si on utilise le critre darrt |xk+1xk | alors |xk+1`| 1C . Quelle valeur de faut-il choisir

    pour approcher ` 103 prs ? (Rappel : |a c| |cb| |ab| |a c|+ |cb| pour tout a,b,c R)CORRECTION.

    1. Soit f : [0,pi]R la fonction dfinie par f (x)= 1+ 12 sin(x)x. Elle est de classeC, f (0)= 1> 0 et f (pi)= 1pi< 0, lethorme des valeurs intermdiaires permet de conclure quil existe au moins un ` [0,pi] tel que f (`)= 0. De plus,comme f (x)= 12 cos(x)1< 0, ce zro est unique. On peut alors utiliser la mthode de la dichotomie pour approcher` et lon a

    G. Faccanoni 31

  • 1. Rsolution dquations non linaires Jeudi 31 janvier 2013

    k 0 1 2 3[ak ,bk ] [0,pi]

    [0, pi2] [

    pi4 ,

    pi2

    ] [ 3pi8 ,

    pi2

    ]`k

    pi2

    pi4

    3pi8

    7pi16

    2. On considre la mthode de point fixe de fonction ditration g .

    2.1. tude graphique de la convergence :

    g est de classe C, g (0) = g (pi) = 1, g (x) = 12 cos(x) [1/2,1/2], g est croissante sur [0, pi2 ], dcroissante sur [pi2 ,pi]et g (pi/2)= 3/2 0 fix).

    1. Faire ltude complte de la fonction g .

    2. Comparer g lidentit.

    3. Soit la suite (xn)nN dfinie parxn+1 = g (xn), x0 > 0.

    laide des graphe de g et de lidentit sur R+, dessiner la suite (xn)nN sur laxe des abscisses. Observer graphi-quement la convergence.

    4. Justifier mathmatiquement la convergence observe graphiquement. En particulier, montrer que cette suite estdcroissante partir du rang 1.

    5. Calculer lordre de convergence de la suite.

    6. crire lalgorithme dfini par la suite (xn)nN qui permet de dterminer 3p

    a une prcision de 106.7. Expliciter la mthode de Newton pour la recherche du zro de la fonction f dfinie par f (x) = x3 a. Que

    remarque-t-on ?

    CORRECTION.

    1. tude de la fonction g : R+R dfinie par g (x)= 23 x+ 13 ax2 :? g (x)> 0 pour tout x R+ ;? lim

    x0+g (x)= lim

    x+g (x)=+ ;lim

    x+g (x)

    x = 23 et limx+g (x)23 x = 0 donc y = 23 x est un asymptote et lon a g (x)> 23 x pour tout x > 0 ;

    ? g (x)= 23(1 a

    x3

    );

    ? g est croissante sur [ 3p

    a,+[, dcroissante sur [0, 3pa] ;? x = 3pa est un minimum absolu et g ( 3pa)= 3pa,? g (x)= 2a

    x4> 0 : g est convexe sur R+.

    32 G. Faccanoni

  • Jeudi 31 janvier 2013 1. Rsolution dquations non linaires

    y = 23 xg (x)

    x

    y

    i (x)

    3p

    a

    3p

    a

    (a) Graphe de g compar au graphe de i (x)= x.

    g (x)

    x

    y

    i (x)

    3p

    a

    3p

    a

    x0 x1x2x3x4

    (b) tude graphique de la convergence de la m-thode de point fixe.

    FIGURE 1.4.: Exercice 1.13

    x 0 3p

    a +

    g (x) +

    g (x)+

    3p

    a

    +

    2. Graphe de g compar au graphe de i (x) = x : voir la figure 1.4a. On vrifie analytiquement quil existe une et uneseule intersection entre la courbe dquation y = g (x) et la droite dquation y = x :

    g (x)= x 23

    x+ 13

    a

    x2= x x3 = a.

    3. tude graphique de la convergence de la mthode de point fixe : voir la figure 1.4a.

    4. On en dduit que pour tout x > 0 on a g (x) 3pa. Donc, pour tout k > 0, xk = g (xk1) 3p

    a. Vrifions les hypothsesdu thorme de point fixe qui fournit une condition suffisante de convergence de la suite :

    4.1. pour tout x dans [ 3p

    a,+[ on a g (x)> 3pa donc g ([ 3pa,+[) [ 3pa,+[ (i.e. lintervalle 3pa,+[ est stable) ;4.2. g C 1([ 3pa,+[) ;4.3. pour tout x dans [ 3

    pa,+[ on a

    |g (x)| =23(1 a

    x3

    )< 1donc g est contractante.

    Alors la mthode converge vers x point fixe de g . De plus, pour tout x [ 3pa,+[ on a x = g (x) x = 3pa : lamthode permet donc de calculer de faon itrative la racine cubique de a.

    5. tant donn que

    g (x)= 0, g (x)= 2ax4

    6= 0la mthode de point fixe converge lordre 2.

    6. Algorithme de point fixe :

    Require: x0 > 0while |xk+1xk | > 106 do

    xk+1 g (xk )end while

    Quelques remarques propos du critre darrt bas sur le contrle de lincrment. Les itrations sachvent ds que|xk+1xk | < ; on se demande si cela garantt-t-il que lerreur absolue ek+1 est elle aussi infrieur . Lerreur absolue litration (k+1) peut tre value par un dveloppement de Taylor au premier ordre

    ek+1 = |g (x) g (xk )| = |g (zk )ek |

    G. Faccanoni 33

  • 1. Rsolution dquations non linaires Jeudi 31 janvier 2013

    avec zk compris entre x et xk . Donc

    |xk+1xk | = |ek+1ek | = |g (zk )1|ek ' |g (x)1|ek .Puisque g (x)= 0, on a bien |xk+1xk | ' ek .

    7. La mthode de Newton est une mthode de point fixe avec g (x)= x f (x)f (x) . Ici elle scrit

    xk+1 = xk f (xk )

    f (xk )= xk

    x3k a3x2k

    = xk 1

    3xk +

    a

    3x2k= 2

    3xk +

    a

    3x2k

    autrement dit la mthode de point fixe assigne est la mthode de Newton (quon sait tre dordre de convergencegale 2 lorsque la racine est simple).

    Exercice 1.14On veut rsoudre lquation ex = x avec 0 0. De plus, comme g (1) = e < 1, on peut conclure que` ]0;1[.

    Mthode 2 : La fonction f : x 7 exx est continue monotone dcroissante, limx exx =+ et limx+ exx = ; par le thorme des valeurs intermdiaires on conclut quil existe un et un seul ` R telque f (`) = 0. Comme f (0) > 0, on peut appliquer nouveau le thorme des valeurs intermdiaires lintervalle [0;[ et en dduire que ` > 0. De plus, comme f (1) < e11 < 0, on peut conclure que` ]0;1[.

    2. Le graphe de la fonction g est celui en figure 1.14. On en dduit que? la suite (un)n converge pour tout u0 R ;? g (R)=]0;+[ et g (]0;+[)=]0;1[ ainsi u1 ]0;+[ et un ]0;1[ pour tout n > 1 ;? la convergence nest pas monotone : la sous-suite des termes dindice pair est monotone croissante tandis que

    la sous-suite des termes dindice impair est monotone dcroissante (ce qui veut dire dune part quon ne pourrapas utiliser les thormes du type monotone+borne=convergente pour prouver la convergence, dautre parton voit aussi que ni lintervalle [`;+[ ni lintervalle [0;`] sont stables) ;

    ? |g (x)| nest pas borne pour tout x R (croissance exponentielle ). Plus particulirement, |g (x)| < 1 ssiex > ssi x > ln()/. Comme 0

  • Jeudi 31 janvier 2013 1. Rsolution dquations non linaires

    g (x)x

    y i (x)

    `

    `

    0 1

    (a) Graphe de g compar au graphe de i (x)= x.

    g (x)x

    y i (x)

    `

    `

    x0 x1x2 x3

    (b) tude graphique de la convergence de la mthode de pointfixe.

    FIGURE 1.5.: Exercice 1.14

    Exercice 1.15Soit f une application de R dans R dfinie par f (x)= exp(x2)4x2. On se propose de trouver les racines relles de f .

    1. Situer les 4 racines de f (i.e. indiquer 4 intervalles disjoints qui contiennent chacun une et une seule racine).

    2. Montrer quil y a une racine x comprise entre 0 et 1.

    3. Soit la mthode de point fixe {xk+1 =(xk ),x0 ]0,1[,

    (1.7)

    avec lapplication de R dans R dfinie par (x) =p

    exp(x2)2 . Examiner la convergence de cette mthode et en

    prciser lordre de convergence.

    4. crire la mthode de Newton pour la recherche des zros de la fonction f .

    5. Entre la mthode de Newton et la mthode de point fixe (1.7), quelle est la plus efficace ? Justifier la rponse.

    CORRECTION. On cherche les zros de la fonction f (x)= exp(x2)4x2.1. On remarque que f (x)= f (x) : la fonction est paire. On fait donc une brve tude sur [0,+[ :

    ? f (0)= 1 et limx+ f (x)=+,

    ? f (x) = 0 pour x = 0 et x =pln4 et on a f (0) = 1 et f (pln4) = 4(1 ln4) < 0 ; f est croissante pour x >pln4 etdcroissante pour 0< x 0 et f (1)= e4< 0, pour le thorme des valeurs intermdiaires il existe au moins un x ]0,1[ telque f (x) = 0. Puisque f (x) = 2x exp(x2)8x = 2x(exp(x2)22) < 2x(e 4) < 0 pour tout x ]0,1[, ce x est unique.Voir la figure 1.6b.

    3. tude de la convergence de la mthode (1.7) :

    3.1. pour tout x dans ]0,1[ on a

    0 0 pour tout n N donc ` 0,? si x0 < 0 alors xn < 0 pour tout n N donc ` 0.

    Comme x0 = 1> 0, alors xn > 0 pour tout n N et ` {

    0,p

    5}.

    2. Soit la fonction g dfinie sur [1;p

    5] par g (x)= 10xx2+5 . On tudie la fonction g :

    ? g (x)> 0 pour tout x [1;p5] ;? g (1)= 53 , g (

    p5)=p5 ;

    ? g (x)=10 x25(x2+5)2 ;

    ? g est croissante sur [1;p

    5[ et g (p

    5)= 0.Graphe de g compar au graphe de i (x) = x : voir la figure 1.8a. On vrifie analytiquement quil existe une et uneseule intersection entre la courbe dquation y = g (x) et la droite dquation y = x dans [1;p5] :

    g (x)= x 10xx2+5 = x x

    2 = 5.

    3. On a g (x) [5/3;p5] pour tout x [1;p5] et on a vu au point prcdent que g est croissante et g (p5)=p5.De plus, g (x) x car

    g (x)= 10xx2+5

    10x

    (p

    5)2+5 = x,

    par consquent la suite xk+1 = g (xk ) xk est croissante.Comme g (x) (p5)=p5 alors la suite xk+1 = g (xk )

    p5 est borne. On a ainsi une suite croissante et born, ce qui

    implique quelle converge. Comme au premier point on a montr que si elle converge vers ` alors ` {0,p5}, onconclut que xn

    n+p

    5. Pour ltude graphique de la convergence de la mthode de point fixe voir la figure 1.8b.

    Dans ce cas, on ne peut pas utiliser le thorme de point fixe pour prouver la convergence de la suite sur lintervalle[1;p

    5]. En effet

    ? g est au moins de classe C 1([1;p

    5])? g ([1;

    p5])= [5/3;p5] [1;p5]

    ? mais 0 g (x)< 1 ssi x [10+5p5;p5] (et on a

    10+5p5> 1).

    G. Faccanoni 37

  • 1. Rsolution dquations non linaires Jeudi 31 janvier 2013

    En revanche, on peut utiliser le thorme de point fixe pour prouver la convergence de la suite sur lintervalle [5/3;p

    5]car

    ? g est au moins de classe C 1([5/3;p

    5])? g ([5/3;

    p5]) [5/3;p5]

    ? 0 g (x)< 1 pour tout x [5/3;p5].4. Comme g (

    p5)= 0 et g (p5) 6= 0, la mthode de point fixe associe la fonction ditration g est dordre 2.

    Exercice 1.17Lobjectif de cet exercice est de dterminer le zro dune fonction C 2(R,R) vrifiant 2 < f (x) < 1 sur R. On dfinit lasuite {xn}nN de R par la rcurrence suivante

    xn+1 = g (xn)= xn + f (xn),

    o > 0 et x0 R sont donns.1. Montrer que lim

    x f (x)=+ et limx+ f (x)=.2. En dduire quil existe un unique ` lment de R tel que f (`)= 0.3. Montrer que si 0

  • Jeudi 31 janvier 2013 1. Rsolution dquations non linaires

    4.1. On vrifie dabord que, si la suite converge vers un point fixe de g , ce point est bien un zro de f (ici le rciproqueest vrai aussi) : soit ` R, alors

    `= g (`) `= `+ f (`) 0= f (`) f (`)= 0;4.2. vrifions maintenant que la suite converge vers un point fixe de g (et donc, grce ce quon a vu au point

    prcdant, elle converge vers lunique zro de f ) :4.2.1. on a videmment que g : RR ;4.2.2. on a dj remarqu que g C 1(R,R) ;4.2.3. pour tout x dans R on a prouv que |g (x)| < 1, i.e. que g est contractante.

    Alors la suite xn+1 = g (xn) converge vers ` point fixe de g et zro de f .5. Si = 1f (`) alors

    xn+1 = g (xn)= xn f (xn)f (`)

    ,

    qui converge car 2< f (`)

  • 1. Rsolution dquations non linaires Jeudi 31 janvier 2013

    2. g est de classe C 2(R,R). Puisque 1< f (x)< 2 et 0

  • Jeudi 31 janvier 2013 1. Rsolution dquations non linaires

    y = 23 x 49g (x)

    x

    y i (x)

    m

    m

    (a) Graphe de g compar au graphe de i .

    g (x)

    x

    y

    i (x)

    x0 x1x2x3x4

    (b) tude graphique de la convergence de la mthode de pointfixe.

    FIGURE 1.9.

    ? g est croissante sur [m,+[, dcroissante sur [0,m] o m 1,36 ;? x =m est un minimum absolu et g (m)=m.

    x 0 m +

    g (x) +

    g (x)+

    m

    +

    2. Graphe de g compar au graphe de i (x) = x : voir la figure 1.9a. On vrifie analytiquement quil existe une et uneseule intersection entre la courbe dquation y = g (x) et la droite dquation y = x :

    g (x)= x 2x3+4x2+103x2+8x = x x

    3+4x210= 0 x =m f (x)= 0.

    3. Pour ltude graphique de la convergence de la mthode de point fixe voir la figure 1.9b.

    4. On en dduit que pour tout x > 0 on a g (x)m. Donc, pour tout k > 0, xk = g (xk1)m. Pour tudier la convergencede la mthode vrifions si on peut appliquer le thorme de point fixe :

    4.1. pour tout x dans [m,+[ on a g (x)>m donc g ([m,+[) [m,+[ ;4.2. g C 1([m,+[) ;4.3. pour tout x dans [m,+[, on a |g (x)| =

    (6x2+8x)g (x)(6x+8)3x2+8x < 1 alors g est contractante.Si les conditions prcdentes sont vrifies alors la mthode converge vers m point fixe de g . De plus, pour tout [m,+[ : = g () =m donc le point fixe de g est racine de f .

    5. Algorithme de point fixe :

    Require: x0 > 0Require: g : x 7 g (x)

    while |xk+1xk | > doxk+1 g (xk )

    end while

    6. La mthode de Newton est une mthode de point fixe avec g (x)= x f (x)f (x) . Ici donc elle scrit

    xk+1 = xk f (xk )

    f (xk )= xk

    x3k +4x2k 103x2k +8xk

    = g (xk )

    G. Faccanoni 41

  • 1. Rsolution dquations non linaires Jeudi 31 janvier 2013

    autrement dit la mthode de point fixe assigne est la mthode de Newton.

    7. tant donn que la mthode de point fixe donne est la mthode de Newton et que la racine m de f est simple, elleconverge lordre 2.

    Quelques remarques propos du critre darrt bas sur le contrle de lincrment. Les itrations sachvent ds que |xk+1xk | < ; on se demande si cela garantt-t-il que lerreur absolue ek+1 est elle aussi infrieur . Lerreur absolue litration(k+1) peut tre value par un dveloppement de Taylor au premier ordre

    ek+1 = |g (x) g (xk )| = |g (zk )ek |avec zk compris entre m et xk . Donc

    |xk+1xk | = |ek+1ek | = |g (zk )1|ek ' |g (m)1|ek .Puisque g (x)= 2 3x+4

    x2(3x+8)2 f (x), alors g(m)= 0 donc on a bien |xk+1xk | ' ek .

    Exercice 1.20

    On se propose de calculer 4

    13 en trouvant les racines relles de lapplication f de R dans R dfinie par f (x)= x4 13 .

    1. Situer les 2 racines de f (i.e. indiquer 2 intervalles disjoints qui contiennent chacun une et une seule racine). Enparticulier, montrer quil y a une racine x comprise entre 0 et 1.

    2. Soit g la fonction dfinie sur [0;1] par

    g (x)= x(9x4+5)

    3(5x4+1) .

    2.1. Faire ltude complte de la fonction g et la comparer lidentit.

    2.2. Soit la suite (xn)nN dfinie parxn+1 = g (xn), x0 ]0;1[.

    laide des graphe de g et de lidentit sur [0;1], dessiner la suite (xn)nN sur laxe des abscisses. Observergraphiquement la convergence.

    2.3. Justifier mathmatiquement la convergence observe graphiquement.

    2.4. Calculer lordre de convergence de la suite.

    2.5. crire lalgorithme dfini par la suite (xn)nN qui permet de dterminer 4

    13 une prcision de .

    3. Expliciter la mthode de Newton pour la recherche du zro de la fonction f .

    4. Entre la mthode de Newton et la mthode de point fixe xk+1 = g (xk ), quelle est la plus efficace ? Justifier la rponse.

    CORRECTION.

    1. f est paire ; comme f (x) = 4x3, f est croissante pour x > 0 et dcroissante pour x < 0 ; puisque f (0) < 0 et f (1) =f (1)> 0, on conclut que il ny a que deux racines relles distinctes : x ]0;1[ et x ]1;0[.

    2. On tudie la fonction g (x)= x(9x4+5)3(5x4+1) pour x 0.

    2.1. ? g (x) 0 pour tout x 0 et g (x)= 0 ssi x = 0 ;? g (x)= 5(9x86x4+1)

    3(5x4+1)2 = 53(

    3x415x4+1

    )2donc g (x) 0 pour tout x ]0;1[ et g (x)= 0 ssi x = 4

    13 . De plus, g

    (4

    13

    )=

    4

    13 .

    ? Enfin, g (x) = 103 3x41

    5x4+132x3

    (5x4+1)2 =

    203 g

    (x) 32x3

    (5x4+1)2 =320x3(3x41)

    (5x4+1)3 donc g(x) = 0 ssi x = 0 ou x = 4

    13 , g est

    concave pour x ]

    0; 4

    13

    [, convexe pour x > 4

    13 .

    ? Pour le graphe de g compar au graphe de i (x)= x pour x [0;1] voir la figure 1.10a.? On vrifie analytiquement quil existe une et une seule intersection entre la courbe dquation y = g (x) et

    la droite dquation y = x :

    g (x)= x x(9x4+5)

    3(5x4+1) = x 9x4+5= 3(5x4+1) x4 = 1

    3 f (x)= 0.

    2.2. Pour ltude graphique de la convergence de la mthode de point fixe voir la figure 1.10b.

    2.3. tudions la convergence de la mthode. On remarque que

    xk+1xk

    = 9x4k +5

    3(5x4k +1)> 1 xk < 4

    1

    3

    42 G. Faccanoni

  • Jeudi 31 janvier 2013 1. Rsolution dquations non linaires

    y = 35 x

    g (x)

    x

    y

    i (x)

    14

    13

    4

    13

    (a) Graphe de g compar au graphe de i .

    g (x)

    x

    y

    i (x)

    14

    13

    4

    13

    x0 x1 x2 x3 x4

    (b) tude graphique de la convergence de la mthode de point fixe.

    FIGURE 1.10.

    donc la suite rcurrente {x0

    ]0; 4

    13

    [xk+1 = g (xk )

    est monotone croissante et majore par 4

    13 : elle est donc convergente vers ` 4

    13 . Comme ` = g (`) ssi ` =

    4

    13 , on conclut quelle converge vers

    4

    13 . De mme, la suite rcurrente{

    x0 ]

    4

    13 ;0[

    xk+1 = g (xk )

    est monotone dcroissante et minor par 4

    13 : elle est donc convergente vers ` 4

    13 . Comme ` = g (`) ssi

    `= 4

    13 , on conclut quelle converge vers

    4

    13 .

    Par consquent, quelque soit le point initiale, la mthode de point fixe donne converge vers 4

    13 point fixe de

    g (et racine de f ).

    Soulignons quon ne peut pas utiliser le thorme de point fixe pour prouver la convergence de la mthode carg nest pas contractante sur [0;1]. En effet, dans [0;1] on a

    |g (x)| < 1 g (x)< 1 5(3x41)2 < 3(5x4+1)2 15x8+30x41> 0 x4 >1+

    16

    15]0;1[.

    2.4. Si on pose x = 4

    13 alors g (x) = x, g (x) = 0, g (x) = 0 et g (x) = 320x2 25x

    822x4+1(5x4+1)4 = 15

    p3

    2 : on conclut que lasuite converge lordre 3.

    2.5. Algorithme de point fixe :

    Require: x0 > 0Require: g : x 7 g (x)

    while |xk+1xk | > doxk+1 g (xk )

    end while

    3. Entre la mthode de Newton et la mthode de point fixe xk+1 = g (xk ), la plus efficace est la mthode de point fixexk+1 = g (xk ) car elle est dordre 3 tandis que celle de Newton nest que dordre 2.

    Exercice 1.21Comparer les mthodes de la dichotomie, de Lagrange et de Newton pour approcher la racine x ' 0.5149332646611294de la fonction f (x) = cos2(2x) x2 sur lintervalle ]0,1.5[ avec une prcision de 1016. Pour la mthode de Newton onprendra x0 = 0.75.

    G. Faccanoni 43

  • 1. Rsolution dquations non linaires Jeudi 31 janvier 2013

    CORRECTION. On modifie les fonctions donnes la page 20 pour que les mthodes sarrtent lorsque le nombre ditra-tions est gal maxITER :

    1 import math, sys2

    3 def dichotomie(f,a,b,tol,maxITER):4 fa = f(a)5 if abs(fa)tol) and (ktol) and (k

  • Jeudi 31 janvier 2013 1. Rsolution dquations non linaires

    63 k += 164 return x

    Ensuite on construit une matrice dont la premire colonne contient le nombre ditrations, la deuxime colonne lerreurabsolue obtenue par la mthode de la dichotomie avec le nombre ditrations indiqu dans la premire colonne, la troi-sime colonne lerreur absolue obtenue par la mthode de LAGRANGE et la dernire par la mthode de NEWTON.

    65 def f(x):66 return (math.cos(2.*x))**2-x**267 def df(x):68 return -4.*math.cos(2.*x)*math.sin(2.*x)-2.*x69

    70 exact = 0.514933264661129471

    72 nITER = 1073 tol = sys.float_info.epsilon74 a = 0.75 b = 1.576 x_init = 0.7577

    78

    79 XXX = []80 Dic = []81 Lag = []82 New = []83

    84 for i in range(nITER):85 maxITER = i86 XXX.append(maxITER)87 Dic.append(abs(exact-dichotomie(f,a,b,tol,maxITER)))88 Lag.append(abs(exact-lagrange(f,a,b,tol,maxITER)))89 New.append(abs(exact-newton(f,x_init,tol,maxITER)))90 print "%2.g %15.17f %15.17f %15.17f" % (XXX[i], Dic[i], Lag[i], New[i])

    On obtient ainsi le tableau

    maxITER Dichotomie LAGRANGE NEWTON0 0.23506673533887057 0.14588447288050665 0.235066735338870571 0.13993326466112943 0.03464350570111258 0.077739757197412502 0.04756673533887057 0.00260088757041255 0.000230796768012083 0.04618326466112943 0.00002318596617201 0.000000016700200674 0.00069173533887057 0.00000020304484416 0.000000000000000115 0.02274576466112943 0.00000000177782544 0.000000000000000006 0.01102701466112943 0.00000000001556633 0.000000000000000007 0.00516763966112943 0.00000000000013634 0.000000000000000008 0.00223795216112943 0.00000000000000122 0.000000000000000009 0.00077310841112943 0.00000000000000000 0.00000000000000000

    On affiche enfin les erreurs absolues |x xmaxITER| en fonction du nombre ditrations pour chaque mthode avec unechelle logarithmique pour laxe des ordonnes.

    91 from matplotlib.pylab import *92 xlabel(Iterations)93 ylabel(Absolute error)94 axis([0.,nITER,0.,0.1])95 semilogy(XXX,Dic,"r-o",XXX,Lag,"g-o",XXX,New,"y-o")96 legend([Dichotomie,Lagrange,Newton])97 show()

    Le rsultat est le suivant

    G. Faccanoni 45

  • 1. Rsolution dquations non linaires Jeudi 31 janvier 2013

    On remarque tout dabord que la dcroissance de lerreur avec la mthode de la dichotomie nest pas monotone. De plus,on voit que la mthode de NEWTON est dordre 2 tandis que la mthode de LAGRANGE est dordre 1.

    46 G. Faccanoni

  • 2. Interpolation

    tant donn n+1 points { (xi , yi )}ni=0, trouver un polynme p = p(x) tel que p(xi )= yitant donn n+1 couples (xi , yi ), le problme consiste trouver une fonction =(x) telle que (xi )= yi ; on dit alors

    que interpole {yi } aux nuds {xi }. Les quantits yi peuvent, par exemple, reprsenter les valeurs aux nuds xi dunefonction f connue analytiquement ou des donnes exprimentales. Dans le premier cas, lapproximation a pour but deremplacer f par une fonction plus simple en vue dun calcul numrique dintgrale ou de drive. Dans lautre cas, lebut est davoir une reprsentation synthtique de donnes exprimentales dont le nombre peut tre trs lev. On parledinterpolation polynomiale quand est un polynme, dapproximation trigonomtrique quand est un polynme trigo-nomtrique et dinterpolation polynomiale par morceaux (ou dinterpolation par fonctions splines) si est polynomialepar morceaux.

    2.1. Position du problmeNotons Rm[x] lespace vectoriel form par tous les polynmes de degr infrieur ou gale m. Il est bien connu que

    Rm[x] a dimension m+1 et que sa base canonique est donne par{

    1, x, x2, . . . , xm}.

    Supposons que lon veuille chercher un polynme Pm de degr m 0 qui, pour des valeurs x0, x1, x2, . . . , xm distinctesdonnes (appels nuds dinterpolation), prenne les valeurs y0, y1, y2, . . . , ym respectivement, cest--dire

    Pm(xi )= yi pour 0 i m. (2.1)

    Si un tel polynme existe, il est appel polynme dinterpolation ou polynme interpolant.Une manire apparemment simple de rsoudre ce problme est dcrire le polynme dans la base canonique de Rm[x] :

    Pm(x)= a0+a1x+a2x2+ +am xm ,

    o a0, a1, a2, . . . , am sont des coefficients qui devront tre dtermins. Les (m+1) relations (2.1) scrivent alorsa0+a1x0+ . . . an xm0 = y0a0+a1x1+ . . . an xm1 = y1. . .

    an +a1xm + . . . am xmm = ymPuisque les valeurs xi et yi sont connues, ces relations forment un systme linaire de (m + 1) quations en les (m + 1)inconnues a0, a1, a2, . . . , am quon peut mettre sous la forme matricielle 1

    1 x0 . . . xm01 x1 . . . xm1...

    ......

    1 xm . . . xmm

    a0a1...

    am

    =

    y0y1...

    ym

    . (2.2)Ainsi, le problme consistant chercher le polynme Pm satisfaisant (2.1) peut se rduire rsoudre le systme linaire (2.2).Cependant, rsoudre une systme linaire de (m + 1) quations (m + 1) inconnues nest pas une tache triviale. Cettemthode pour trouver le polynme Pm nest donc pas une bonne mthode en pratique. Dans la suite on va tudier unemthode plus astucieuse pour construire le polynme Pm .

    1. La matrice

    1 x0 ... x

    m0

    1 x1 ... xm1

    ......

    ...1 xm ... xmm

    sappelle matrice de VANDERMONDE.

    47

  • 2. Interpolation Jeudi 31 janvier 2013

    2.2. Interpolation de LAGRANGEQuand on crit le polynme Pm dans la base canonique de Rm[x], le problme est de dterminer les (m+1) coefficients

    a0, a1, a2, . . . , am tels quePm(x)= a0+a1x+a2x2+ +am xm .

    On se demande sil existe une autre base { L0,L1,L2, . . . ,Lm } de Rm[x] telle que le polynme Pm scrit

    Pm(x)= y0L0(x)+ y1L1(x)+ y2L2(x)+ + ymLm(x).

    Les (m+1) relations (2.1) imposent la condition :

    Li (x j )

    {1 si i = j0 sinon

    pour 0 i , j m,

    ce qui donne

    Li (x)=n

    j=0j 6=i

    xx jxi x j

    = (xx0)(xx1) (xxi1)(xxi+1) (xxm)(xi x0)(xi x1) (xi xi1)(xi xi+1) (xi xm)

    .

    Clairement, le numrateur de Li (x) est un produit de m termes (x x j ) avec i 6= j et est donc un polynme de degr m. Lednominateur est une constante et il est facile de vrifier que

    ? Li (x) Rm[x],? Li (x j )= 0 si i 6= j , 0 i m,? Li (xi )= 1.

    De plus, les polynmes L0,L1,L2, . . . ,Lm sont linairement indpendants car si lquationm

    i=0i Li (x) = 0 doit tre satis-faite pour tout x R alorsmi=0i Li (x j )= 0 doit tre vraie pour tout j = 0,1, . . . ,m et puisquemi=0i Li (x j )= j , on conclutque tous les j sont nuls. Par consquent, la famille { L0,L1,L2, . . . ,Lm } forme une base de Rm[x].

    Il est important de remarquer que nous avons construit explicitement une solution du problme (2.1) et ceci pour nim-porte quelles valeurs y0, y1, y2, . . . , ym donnes. Ceci montre que le systme linaire (2.2) a toujours une unique solution.

    Dfinition Interpolation de Lagrangetant donn m+1 points distincts x0, . . . , xm et m+1 valeurs correspondantes y0, . . . , ym , il existe un unique polynmePm Rm[x] tel que Pm(xi )= yi , pour i = 0, . . .m quon peut crire sous la forme

    Pm(x)=m

    i=0yi Li (x) Rm[x] o Li (x)=

    mj=0j 6=i

    xx jxi x j

    .

    Cette relation est appele formule dinterpolation de LAGRANGE et les polynmes Li sont les polynmes caractristiques(de LAGRANGE).

    ExemplePour m = 2 le polynme de Lagrange scrit

    P (x)= y0(xx1)(xx2)

    (x0x1)(x0x2)+ y1

    (xx0)(xx2)(x1x0)(x1x2)

    + y2(xx0)(xx1)

    (x2x0)(x2x1)

    ExempleOn cherche le polynme dinterpolation de LAGRANGE qui en 1 vaut 8, en 0 vaut 3 et en 1 vaut 6. On a

    P (x)= y0(xx1)(xx2)

    (x0x1)(x0x2)+ y1

    (xx0)(xx2)(x1x0)(x1x2)

    + y2(xx0)(xx1)

    (x2x0)(x2x1)= 8 x(x1)

    2+3 (x+1)(x1)1 +6

    (x+1)x2

    = 4x2x+3.

    RemarqueSi m est petit il est souvent plus simple de calculer directement les coefficients a0, a1, . . ., am en rsolvant le systmelinaire (2.2).

    48 G. Faccanoni

  • Jeudi 31 janvier 2013 2. Interpolation

    Soit f : RRune fonction continue donne et soit x0, x1, x2, . . . , xm , (m+1) points distincts donns. Interpoler la fonctionf aux points xi , 0 i m signifie chercher un polynme Pm de degr m tel que

    Pm(xi )= f (xi ) pour 0 i m. (2.3)La solution de ce problme est donc donne par

    Pm(x)=m

    i=0f (xi )Li (x) Rm[x] o Li (x)=

    mj=0j 6=i

    xx jxi x j

    et le polynme Pm est appele interpolant de f de degr m aux points x0, x1, x2, . . . , xm .

    ExempleSoit f : RR la fonction dfinie par f (x)= ex . On cherche linterpolant de f aux points 1, 0, 1. On a

    P (x)= f (x0)(xx1)(xx2)

    (x0x1)(x0x2)+ f (x1)

    (xx0)(xx2)(x1x0)(x1x2)

    + f (x2)(xx0)(xx1)

    (x2x0)(x2x1)= 1

    e

    x(x1)2

    + (x+1)(x1)1 +e(x+1)x

    2=(

    1

    2e1 e

    2

    )x2+

    (e

    2 1

    2e

    )x+1.

    La figure ci-dessous montre le graphe de la fonction f et de son interpolant aux points 1, 0, 1.

    x

    y

    1 0 1

    1e

    1

    e

    fP2

    Proposition ErreurSi yi = f (xi ) pour i = 0,1, . . . ,n, f : I R tant une fonction donne de classe C n+1(I ) o I est le plus petit intervallecontenant les nuds { xi }ni=0, lerreur dinterpolation au point x I est donn par

    En(x) f (x)Pn(x)= f(n+1)()

    (n+1)! n+1(x)

    o I et n+1(x)n

    i=0(xx j ).

    videmment, En(xi ) = 0 pour i = 0,1, . . . ,n. De plus, dans le cas dune distribution uniforme de nuds, i.e. quand xi =xi1+h avec i = 1,1, . . . ,n et h > 0 et x0 donns,

    maxxI

    |En(x)| maxxI | f(n+1)(x)|

    4(n+1) hn+1.

    Attention priori on pourrait penser que cette erreur tend vers 0 quand n + puisque

    limn+

    hn+1

    4(n+1) = 0.

    En ralit il existe des fonctions f pour lesquelles maxxI |En(x)| n+ +. Ce rsultat frappant indique quen aug-

    mentant le degr n du polynme dinterpolation, on nobtient pas ncessairement une meilleure reconstruction de f .

    G. Faccanoni 49

  • 2. Interpolation Jeudi 31 janvier 2013

    Exemple RUNGECe phnomne est bien illustr par la fonction de RUNGE : soit la fonction f : [5,5] R dfinie par f (x) = 1

    1+x2 . La fonction fest infiniment drivable sur [5,5] et | f (n)(5)| devient trs rapidement grand lorsque n tend vers linfini. Si on considre une dis-tribution uniforme des nuds on voit que lerreur tend vers linfini quand n tend vers linfini. Ceci est li au fait que la quantit

    maxx[5,5]| f (n+1)(x)| tend plus vite vers linfini que hn+1

    4(n+1) tend vers zro. La figure 2.1a montre ses polynmes interpolants de de-grs 3, 5 et 10 pour une distribution quirepartie des nuds. Cette absence de convergence est galement mise en vidence par lesfortes oscillations observes sur le graphe du polynme dinterpolation (absentes sur le graphe de f ), particulirement au voisinagedes extrmits de lintervalle. Ce comportement est connu sous le nom de phnomne de RUNGE. On peut viter le phnomne deRUNGE en choisissant correctement la distribution des nuds dinterpolation. Sur un intervalle [a,b], on peut par exemple considrerles nuds de CHEBYSHEV-GAUSS-LOBATTO (voir figure 2.1b)

    xi =a+b

    2 ba

    2cos(pi

    ni)

    , pour i = 0, . . . ,n

    Pour cette distribution par