Chap 1 : Résolution d'équations non-linéaires

1 Universit SavoieMont-BlancL3 MASSChap1:R solutiond' quationsnon-lin airesBut:Recherchedessolutionsdel' quationnonlin airef(x) = 0o festunefonctiondonn e Lesm tho desnum riquesp ourappro cherunesolutionconsistent lo calisergrossi rementunz rodefenpro c dantleplussouventpardesconsi-d rationsgraphiques;lasolutiongrossi reestnot x0. construire partirdex0unesuitex1, x2, x3, ..tellequelimn xn= xo xv ri ef( x) = ,lo calisationdessolutionsOnsedonneuneapplic ationfcontinued'unouvertIdeRdansRetonche rche appro chernum riquementunesolutiondusyst mef(x) = 0. est-cequ'untelxexiste ?ExemplesFonctionsp olyn mialesdedegr < ,applicationslin nitionsD :I R,onapp ellez rodeftout x Iquisatisfaitf( x) = ellep oint xedeftout xquisatisfaitf( x) = terminerlesz rosdel'applicationf(x) =x2 5x+ terminerlespoints xesdel'applicationg(x) =x2 4x+ duireuneinterpr tationgraphiqued'unz roetd'unpoint xed' :Si xestunz rodefalors xestunp oint xedeg:x7 f(x) + sultatsth oriquesTh or me1(Th or medesvaleursinterm diaires)SoitfunefonctioncontinuesurI= [a,b].

2 Alorsfatteinttouteslesvaleursentref(a)et f(b) d [f(a),f(b)]ilexistec Itelquef(c) = :I= [a,b] Runeapplicationcontinuetel lequef(a)f(b)<0c'est- -direquef(a)etf(b)sontnonnulsetdesignesoppos x ]a,b[telquef( x) = ,alors : unefonctionp olyn miale co e cientsr elsdedegr impairadmetaumoinsunz rosurR. l' quationx(1 + 2x) =exadmetuneuniquesolutiondansl'intervalle]0,1[.Corollaire2(Th or medep oint xe)Soitg: [a,b] [a,b]continuesur[a,b].Alorsgadmetunpoint xe xdansl'interval le[a,b]. osonsparl'absurdequegn'admetpasdep oint xesur[a,b].Alorsenparticulier{g(a)> ag(b)< bPosonsf(x) =g(x) x,festcontinuepuisquegl' {f(a)>0f(b)< 'existenced'unz rodefdans[a,b], x,quiestdoncpard nitiondefunp oint ch esD ellem thodeit rativeunpro c d decalculdelaformexn+1=F(xn), n= 0,1,2,..quipartd'unevaleurdonn ex0p ourcalculerx1,puis l'aidedex1oncalculex2, +1estditeformuleder c d estditconvergentsixntendversunnombre nilorsquentendversl'in 'unem tho deconvergenteestd'ordreps'ilexisteunecon stanteCtellequesi x= limnxn| x xn+1| C| x xn|pouencorelimn | x xn+1|| x xn|p= 1onparledeconvergencelin aire,sip= :Danslecaso p= 1,ilestn cessairequeC <1p ourque(xn)convergevers tho desdeladichotomieetdeLagrangePrincip edesdeuxm tho tho dess'appuientsurleth or medesvaleursinter-m relafonctionfcontinuesur[a,b] valeursdansRavecf(a)f(b)< 'ilexisteunz rodefdansI0= ]a,b[qu'onnote caliser xonvacalculer chaqueit rationunsous-intervalleIn= [an,bn]deIn 1danslequel xestlo calis.}}

3 Tho dededichotomieconsiste d coup erl'intervalleInendeuxintervallesdem tement,supp osonsparexemplequef(an)<0,f(bn)>0etnotonsxn=an+ tudielesignedef(xn) sif(xn) = 0alors x=xn sif(xn)<0,d'apr sdeTVI,ilexisteunz rodefsurl'intervalle]xn,bn[.Onp osedoncan+1=xnetbn+1=bn. sif(xn)>0,d'apr sdeTVI,ilexisteunz rodefsurl'intervalle]an,xn[.Onp osedoncan+1=anetbn+1= oursuitalorslaconstructionjusqu' obtenirlapr cisionsouhait tho dededichotomieconsistedonc construiredeuxsuitesadjacentes(an)et(bn) (quisontlesextr mit sdesintervallessuccessifsdanslesquels xestlo calis )convergeantvers or me2 Soienta,b R,a < b,f: [a,b]7 Runeapplicationcontinueposs dantununiquez ronot x ]a,b[.Onsupposedeplusquef(a)f(b)< (an)et(bn)convergentvers xetonalesmajorationsd'erreursuivantes n 0,0 x an b a2n,0 bn x b (an)et(bn) cis ment,onvamontrerparr currencesurnque n 1, an 1 an, bn bn 1, bn an=b a2n(oubienan=bn= x).(1)Rapp el:(an)et(bn)sontditesadjacentessil'unee stcroissante,l'autred croissanteet|an bn| 0quandn.

4 R sultat:si(an)et(bn)sontadjacentesalorsce sdeuxsuitessontconvergentesetontlam melimitel R, n,an l bn. (x0)estdusignedef(a)alorsa1=x0=a0+b02etb 1=b0= ri equea0 a+b2=a1 b1=b0b1 a1=b a+b2=b (x0)f(a)<0. H r dit .Onsupp oselapropri t (1) tudielesignedef(xn) =f(an+bn2).Sif(xn)f(a)>0(l'opp os setraitantdemani recompl tementana-logue),alorsan+1=xnan an+bn2=an+1etparhyp oth seder currenceonobtientbn+1 an+1=bn an+bn2=bn an2=12b a2n=b a2n+1,cequiach velad monstrationde(1).Onaainsimontr que(an)et(bn)sontadjacentes, ndeconclurelad monstrationduth or me,ilreste montrerquel= (l) = {f(an)f(a) 0f(bn)f(b) 0cequidonneenpassant lalimiteparcontinuit def{f(l)f(a) 0f(l)f(b) 04 Commeparailleursonasupp os queaetb taientnonnulsetdesignesopp os sonan cessairement{f(l) 0f(l) 0= f(l) = nendisantque0 x an bn an b a2n0 bn xn bn an b :Commeonl'adit,lesit rationss'ach vent lam-i me tap equand| x xm| |Im|< o estunetol rance x |Im|=b a2mdoncp ouravoiruneerreurinf rieure ,ondoitprendreleplusp etitmtelquem log(b a )log(2)= log2(b a ).}}}

5 Lam tho dededichotomienegarantitpaslar ductionmonotonedel'erreurabsolued'uneit ration l'autre,c'est- -direqu'onn'apas| x xn+1| Cn| x xn|p ourtoutn 0avecCn< tho dededichotomien'estpasunem tho ded' :Avantage:Facile impl menter,unefoisunz roisol onaconvergence coups nients:Convergencelente,m tho depasg n ralisableendimensionsup rieure,nes'appliquepasparexemplep ourchercherlesextrema, ourx7 tquedecoup erl'intervalleendeuxintervallesdem melongueur,ond coup eIn=[an,bn]en[an,xn]et[xn,bn]o xnestlep ointd'intersectiondeladroitepassantpar(an,f(an))et(bn,f(bn))etl' quationssuivantesf(bn) f(an)bn an(xn bn) +f(bn) = 0,ouencorexn=anf(bn) bnf(an)f(bn) f(an).Onestalorsramen commepr c demment tudierlesignedef(xn).5 Prop osition1 Sif(r guli resur[a,b])avecf designeconstantsur[a,b](c dfconvexeouconcavesur[a,b])alorssoitilexisteunntelquef(xn) = 0,soitxnestbiend nipourtoutnetxnconverge l'ordre1vers xo xestl'uniquez rodefdans[a,b]. osonsquef(a)<0etf(b)>0avecfconvexe(f 0). fadmetununiquez rosur[a,b].

6 Danslasuiteonsupp osequ'iln'existepasd'indicep ourlequelxn= +1=xn,bn+1=bavec(xn) currence,onsaitquexn> an=xn 1carf(an)< [an,bn]doncs' critcommebarycentredesp ointsanetbnxn= nan+ (1 n)bno n=xn bnan bnl'in galit deconvexit nousdonnealorsf(xn) =f( nan+ (1 n)bn) nf(an) + (1 n)f(bn) = 'onp oseaurangsuivantan+1=xn. xn x:d'apr scequipr c de,lasuite(xn)estcroissante,ma jor 'estdoncunesuiteconvergente, montrerdoncquel= , crivonslaformuleder currencedonnantlasuite(xn)xn+1=xn b xnf(b) f(xn)f(xn).(2)Enmultipliantlesdeuxmembre sdel' quationparf(b) f(xn)etenpassant lalimiten onobtient(b l)f(l) = 0.(3)Parailleursl'in galit xn< x < bimpliquequ' lalimite:l x < l' quation(3)onend duitquef(l) = 0doncquel= x. laconvergenceestlin aire:onutilisantlaformuleder currence(2)on crit x xn+1= x xn+b xnf(b) f(xn)f(xn)puis x xn+1=( x xn)(1 +b xnf(b) f(xn)f(xn) x xn)=( x xn)(1 b xnf(b) f(xn)f( x) f(xn) x xn)Passons lalimiten danscettederni re quationp ourab outir limn x xn+1 x xn= 1 b xf(b) f( x)f ( x) =C(4)6 Ilnousfautdoncmontrerque0 C < 'estlaconvexit defquip etellenousp ermetd' crirelesin galit ssuivantes{f(b) f( x) +f ( x)(b x)f(a) f( x) +f ( x)(b x)ouencoreenutilisantquea < x < betf( x) = 0{f ( x) f(b)b x= C 0f ( x) f(a)a x= C <1 Remarque:Lecrit red'arr t|Im|< estp euadapt enpratiquep ourl' f reutiliserplut tl'undesdeuxcrit ressuivant(voircompl menten ndechapitre) contr ledur sidu:ons'arr te|f(xn)|<.}}

7 Contr ledesincr ments:ons'arr tequand|xn+1 xn|< .Exercice2D crirelesm thodesdedichotomieetdeLagrangeetlesutili serpourcalculerlez rodelafonctionf(x) = 2x3 x 5dansl'interval le[1,2]avecunepr cisionde10 tho desdep oints xeTh or me3(Th or medep oint xecontractant)SoientIuninterval leferm nonvidedeRetg:I Iuneapplicationstrictementcontractantec dqu'ilexisteuneconstante0< k <1tel leque (x,y) I2|g(x) g(y)|< k|x y|.Alorsilexisteununique x Itelqueg( x) = xlasuited niepar{x0 I n Nxn+1=g(xn)convergevers ,onalamajorationd'erreur|xn x| kn|x0 x| n :Ip eut tredelaformeI=R,I=] ,a],[a,+ [ouI= [a,b]. I= [a,b].7 existenced'unpoint xe:okparlecorollaire2(onremarquerap ourcelaquelappt dek-contractivit entra nelacontinuit deg). unicit dupoint xe:soient xet xdeuxp oints | x x|=|g( x) g( x)| k| x x|.Laconditionk <1imp osedonc| x x|= 0c d x= x. convergenceetmajorationd'erreur:Onvad montrerparr currencesurnque|xn x| kn|x0 x|. initialisation:onabien|x0 x| k0|x0 x|.}

8 H r dit :onsupp osel'in galit v ri + 1ona|xn+1 x|=|g(xn+1) g( x)| k|xn x| kn+1|x0 x|.L'in galit estbiensatisfaiteaurangn+ 1cequiconclutlapreuveparr <1,onakn 0etcettein galit p ermetainsidemontrerlaconvergencedexnvers n ralo Iestunferm deR,l'existencede xetlaconvergencedelasuites'obtiennentsimultan mentenmontrantque(xn) etcommegestk-contractanteonp eut crirep ourn 1|xn+1 xn|=|g(xn) g(xn 1)| k|xn xn 1| kn|x1 x0|Soitmaintenantp > n 0,onap j=n+1(xj xj 1) =xp xnetl'in galit pr c dentedonne|xp xn| p j=n+1kj 1|x1 x0|=p (n+1) j=0kn+j|x1 x0|=kn|x1 x0|p (n+1) j=0kj kn|x1 x0|+ j=0kj=kn|x1 x0|1 k n,p (xn)estdoncunesuitedeCauchydansIquiestun ferm ,onnotellalimite ;parcontinuit deg,enpassant lalimitedansl' galit xn+1=g(xn),onobtientl=g(l).L'unicit sed montredelam memani requep ourlecasd' :R RdeclasseC1etsoit xunpoint |g ( x)|<1,alorsilexiste >0telquesix0satisfait| x x0| ,alorslasuitedonn eparxn+1=g(xn)convergevers xlorsquentendversl'in nitionSoit xunp oint xed'uneapplicationg,onditque xestunp oint xe attractifsi|g (x)|<1 r pulsifsi|g ( x)|>1 Lecorollaire3nousdonnedonclaconvergencel o caleautourdesp oint sultatsuivantdonnelanon-convergencep ourlesp oints xesr pulsifsProp osition2 Soientg:I RuneapplicationdeclasseC1et xunpoint xer (xn)lasuited nieparl'approximationdepoint xexn+1=g(xn).

9 Alorssoitlasuite(xn)eststationnaire, gale x partird'uncertainrang,soit(xn)neconverge pasvers estcontinuesurI,ilexiste >0telque x I,| x x|< = |g (x)|> osonsparl'absurdequelasuite(xn)convergev ers (quid p endde )telque n N0,|xn x| etdonc n N0,|g (xn)|> 'apr sleth or medesaccroissements nisilexistecnentrexnet xtelqueg(xn) g( x) =g(cn)(xn x).Doncp ourtoutn N0ona|xn+1 x|=|g(xn) g( x)|=|g (cn)||xn x|>|xn x|.Sip ourtoutn N0onaxn6= x,l'in galit pr c denteentreencontradictionaveclaconvergen cedes(xn)vers relasuited'it r sxn+1=gi(xn),x0 [0,1].Diredanslesdeuxcassuivantssilasuit econverge(donnerlanaturedespoints xes ventuelsdegi) (x) =12x(1 x) (x) =12x(1 +x) Peut-on tendreler sulatduth or meaucask= 1?Exercice5 Onconsid relasuited'it r sxn+1=g(xn),x0 [0,1]avecg(x) =x+x3puisg(x) =x (donnerlanaturedespoints xes ventuelsdeg).Exercice6 Oncherche d terminerlez rodelafonctionf:R Rd nieparf(x) = 1 3e rosurRnot xdirectement partirdel' quationsatisfaitepar tho deit rativederelaxation:L' quationf(x) = 0est quivalente 6= 0x=x+ f(x)Sionposeg(x) =x+ f(x)onestdoncramen trouver pourquelasuited nieparxn+1=g(xn)converge.

10 (a)On xex0dans[1,2].Trouver pourquelasuiteconvergeetjusti erlechoixdex0.(b)Quepeut-ondiredelavites sedeconvergencedelasuite ? tho dedeNewtonSoitfunefonctiond niesurunintervalle[a,b],contin mentd rivablesur[a,b]( [a,b]).Soit xunz rodefque[a,b]telquef ( x)6= tho dederelaxationintro duitedansl'exercicepr c dent{f( x) = 0} { 6= 0, x=g ( x)}g (x) =x+ f(x).Alorslemeilleurchoixdeconstante estceluip ourlequellam tho deestd'ordre2,soitceluip ourlequelg ( x) = 0 = 1f ( x).Enpratiqueiln'estpasp ossible(saufcasparticulier)decalculerf ( x)puisqu'onneconna tpas approximer chaqueit rationf ( x)parf (xn).C'estlam or me4(Th or medeconvergenceglobale)Onreprendleshypot h sespr c dentesetonsupposedeplusquefestdeclasseC2 surIetquef etf nes' Itelquef(x0)soitdum mesignequef (onsupposequ'ilexisteaumoinsuntelx0).Alo rslasuited nieparlam thodedeNewton{x0donn xn+1=xn f(xn)f (xn)=g(xn)estbiend nieetconvergedemani remonotonevers xuniquez ( x) = estdesigneconstantsurI,feststrictementmo notonesurIetl' quationf(x) = oint xestdoncl'uniquez ' galit g ( x) = 0d couledirectementdelad nitiondelam tho dedeNewton(onachoisi danslam tho dederelaxationp ouravoircette galit ).}