[PDF] Searches related to nombre d+itération dichotomie PDF

Agr´egation interneUFR MATH´EMATIQUES

R´esolution d"´equations non lin´eaires

On consid`ere une fonction r´eellefd´efinie sur un intervalle [a,b],aveca < b, et continue sur cet intervalle et on suppose quefadmet une unique racine surI=]a,b[, c"est-`a-dire qu"il existe un uniqueα?Itel quef(α) = 0.

1. M´ethode de dichotomie

On consid`ere un intervalle [a,b] et une fonctionfcontinue de [a,b] dansR.On suppose quef(a)f(b)<0 et que l"´equationf(x) = 0 admet une unique solutionαsur l"intervalle [a,b]. La m´ethode de dichotomie consiste `a construire une suite (xn) qui converge versαde la mani`ere suivante : y=f(x) a

• •b.x0x1.x2.x3.

DichotomieInitialisation : on prend pourx0le milieu de [a,b].La racine se trouve alors dans l"un des deux intervalles ]a,x0[ ou ]x0,b[ ou bien elle est ´egale `ax0.

•sif(a)f(x0)<0, alorsα?]a,x0[.On

posea1=a,b1=x0.

•sif(a)f(x0) = 0, alorsα=x0.

•sif(a)f(x0)>0, alorsα?]x0,b[.On

posea1=x0,b1=b.

On prend alors pourx1le milieu de [a1,b1].

On construit ainsi une suitex0= (a+b)/2,

x

1= (a1+b1)/2,...,xn= (an+bn)/2

Etant donn´e une pr´ecisionε, cette m´ethode permet d"approcherαen un nombre pr´evisible

d"it´erations. Les principes de construction suivants consistent `a transformer l"´equationf(x) = 0 en une ´equation ´equivalenteg(x) =x. On peut poser par exempleg(x) =x+f(x), mais on prendra plus g´en´eralementg(x) =x+u(x)f(x) o`uuest une fonction non nulle sur l"intervalle I.Il reste `a choisirupour que la suite d´efinie parx0?Iet la relation de r´ecurrence x n+1=xn+u(xn)f(xn) soit bien d´efinie et converge vers la racineαdef. G´eom´etriquement, on a remplac´e la recherche de l"intersection du graphe de la fonctionf avec l"axeOx, par la recherche de l"intersection de la droite d"´equationy=xavec la courbe d"´equationy=g(x). y=f(x) a

• •bα•

Racine def

y=g(x)y=x a

• •bα•

Point fixe deg

Pr´eparation`a l"agr´egation interne UFR maths, Universit´e de Rennes I Le choix d"une m´ethode est conditionn´e par les r´eponses aux questions suivantes :

1) la suite (xn) converge-t-elle?

2) si la suite converge, sa limite est-elleα?

3) si on veut la solution `aεpr`es, comment arrˆeter les it´erations d`es que cette condition est

remplie?

4) comme dans tout calcul, on d´esire obtenir rapidement le r´esultat approch´e, il faudra donc

estimer la mani`ere dont ´evolue l"erreure=xn-αau cours des it´erations. Les deux premi`eres questions sont purement math´ematiques. Les deux derni`eres sont num´eriques, car on ne peut effectuer qu"un nombre fini d"it´erations pour le calcul.

La continuit´e des fonctions consid´er´ees permet de r´epondre `a la question 2 : si la suite converge,

elle converge vers une racine de l"´equation; si, de plus,xn?I, pour toutn, alors par unicit´e de la racine dansI, la suite converge versα.

2. Th´eor`eme du point fixe

D´efinition 1 -On dit que l"applicationg: [a,b]→Rest strictement contractante si Proposition 2 -Soitgune application de classeC1de l"intervalle [a,b] deRdansR.On suppose queg?v´erifie alors l"applicationgest strictement contractante dans l"intervalle [a,b]. Th´eor`eme 3 -Sigest une application d´efinie sur l"intervalle [a,b]`a valeurs dans[a,b], alors la suite (xn) d´efinie parx0?[a,b] et la relation de r´ecurrencexn+1=g(xn) converge vers l"unique solutionαde l"´equationx=g(x) avecα?[a,b].

D´emonstration : la suite

(xn)est bien d´efinie carg([a,b])?[a,b]. Montrons, par l"absurde, que l"´equationx=g(x)a au plus une solution. Supposons qu"il y ait deux solutionsα1etα2, alors orL <1donc n´ecessairementα1=α2.

Montrons que la suite(xn)est convergente. On a

et par r´ecurrence

On en d´eduit que

Cette suite v´erifie le crit`ere de Cauchy; elle est donc convergente versα?[a,b], or l"applicationgest continue donc la limiteαv´erifieg(α) =α. On a aussi une ´evaluation de l"erreur en faisant tendrepvers l"infini, on obtient

1-L·

On constate que, pournfix´e, l"erreur est d"autant plus petite queLest proche de 0.

3. M´ethode de la s´ecante

- 2 -

R´esolution d"´equations non lin´eaires

3.1. Description de la m´ethode

Cette m´ethode est ´egalement appel´ee m´ethode de Lagrange, m´ethode des parties propor-

tionnelles ou encore regula falsi... On consid´ere un intervalle [a,b] et une fonctionfde classeC2de [a,b] dansR.On suppose quef(a)f(b)<0 et quef?ne s"annule pas sur [a,b], alors l"´equationf(x) = 0 admet une unique solution sur l"intervalle [a,b]. Remarque -L"hypoth`ese "fd´erivable" suffirait, mais demanderait une r´edaction un peu plus fine des d´emonstrations. La m´ethode de la s´ecante consiste `a construire une suite (xn) qui converge versαde la mani`ere suivante : soit Δ

0la droite passant par (a,f(a)) et (b,f(b)), elle coupe l"axeOx

en un point d"abscissex0?]a,b[.On approche donc la fonctionfpar un polynˆomePde degr´e 1 et on r´esoutP(x) = 0. y=f(x)Δ 0 a

••bα••x0x

1• f(x0)• ?a,f(a)?•• ?b,f(b)? M´ethode de la s´ecanteEnsuite, suivant la posi-tion deαpar rapport `a x

0, on consid`ere la droite

passant par (a,f(a)) et (x0,f(x0)) si f(x0)f(a)<0 ou celle passant par (x0,f(x0)) et (b,f(b)) sif(x0)f(b)<0.

On appellex1l"abscisse

du point d"intersection de cette droite avec l"axeOx.

On r´eit`ereensuite le proc´ed´e.

Plaons-nous dans le cas o`uf?>0 est d´erivable etfest convexe (i.e.f??≥0), alors la suite (xn) est d´efinie par???x 0=a x n+1=bf(xn)-xnf(b) f(xn)-f(b) En effet, sifest convexe, on remplace l"intervalle [xn,b] par l"intervalle [xn+1,b].L"´equation d"une droite passant par?c,f(c)?et?b,f(b)?avecc?=besty-f(b) =f(b)-f(c) b-c(x-b). On cherche son intersection avec l"axeOxdonc on prendy= 0 et on obtient la formule donn´ee plus haut. Remarque -sifest convexe, alors sa repr´esentation graphique est au dessus des tangentes et en dessous des cordes.

On poseg(x) =bf(x)-xf(b)

f(x)-f(b)=x-b-xf(b)-f(x)f(x) d"o`uxn+1=g(xn).

Montrons que cette suite (xn) est d´efinie.

Pour cela, il suffit de montrer queg([a,b])?[a,b].V´erifions d"abord quegest de classe C

1sur [a,b].Elle l"est de mani`ere ´evidente sur [a,b[.L"applicationgest continue enbet

g(b) =b-f(b)/f?(b).On a, pour toutx?[a,b[ g ?(x) = 1-f?(x)b-x =f(b)f(b)-f(x)-(b-x)f?(x) ?f(b)-f(x)?2· On en d´eduit queg?est continue enbetg?(b) =f(b)f??(b)/?2f?(b)2?.De plus, l"application fest convexe, doncf(b)-f(x)-(b-x)f?(x)≥0. On a ´egalementf(b)>0 - 3 - Pr´eparation`a l"agr´egation interne UFR maths, Universit´e de Rennes I carfcroissante etf(a)f(b)<0.La fonctiongest donc croissante sur [a,b].On a alorsg([a,b])?[g(a),g(b)].De plus,g(a) =a-f(a)(b-a) f(b)-f(a), orf(a)<0 et (b-a) f(b)-f(a)≥0 par croissance def; doncg(a)≥a.De mˆemeg(b) =b-f(b)f?(b), or f La croissance degmontre que la suite (xn) est croissante carx1=g(a)≥a=x0, or elle est dans l"intervalle [a,b], donc elle converge versl?[a,b] tel que, par continuit´e deg, Soitx?]a,b[ tel quef(x) = 0, alors il est imm´ediat queg(x) =x.R´eciproquement, soit x?]a,b[ tel queg(x) =x, alorsb-x f(b)-f(x)f(x) = 0, orx?=betf(x)?=f(b) carfest strictement croissante etx?]a,b[.On en d´eduit quef(x) = 0.Il y a unicit´e de la racine def, doncl=αet la suite (xn) converge versα.

3.2. Rapidit´e de convergence de la m´ethode de la s´ecante

On axn-α=g?(ξ)(xn-1-α).On en d´eduit, par continuit´e deg?enα, que lim n→+∞|xn-α| |xn-1-α|=|g?(α)|=g?(α).

4. M´ethode de Newton

On cherche les points fixes de la fonctiong(x) =x+u(x)f(x), et on a vu que lim n→+∞|xn-α| |xn-1-α|=|g?(α)|=g?(α). Pour obtenir une convergence plus rapide, on peut chercherutel queg?(α) = 0. On a, si les fonctions ont les r´egularit´es n´ecessaires,g?(x) = 1 +u?(x)f(x) +u(x)f?(x) et on en d´eduit queg?(α) = 0 siu(α) =-1/f?(α).Si la fonctionf?ne s"annule pas, on peut donc choisiru(x) =-1/f?(x).On obtient alors la m´ethode de Newton.

4.1. Description de la m´ethode

On consid`ere une fonction r´eelle d´efinie sur un intervalleI= [a,b] de classeC2telle que f(a)f(b)<0; on suppose que les fonctionsf?etf??ne s"annulent pas et gardent chacune un signe constant surI.On pose g(x) =x-f(x) f?(x)· Sif?f??est positive (respectivement n´egative) sur [a,b], on posex0=b(respectivementa). On d´efinit alors la suite (xn) par la donn´ee dex0et la relation de r´ecurrencexn+1=g(xn). Th´eor`eme 4 -La suite (xn) converge versαl"unique racine defsur [a,b]. D´emonstration : pour simplifier la r´edaction, on va supposer quef?est strictement positive etf??est strictement n´egative surI.Les autres cas se traitent de mani`ere similaire. Ces hypoth`eses assurent l"existence et l"unicit´e deα?Itel quef(α) = 0. On va montrer que la suite(xn)est croissante et major´ee parα.On ax0=a, donc x f?(xn)et que la fonctionf? - 4 -

R´esolution d"´equations non lin´eaires

est positive, doncfest croissante, on en d´eduit imm´ediatement quexn+1≥xnet la suite (xn)est croissante. De plus,xn+1-α=g(xn)-g(α) =g?(ξ)(xn-α)avecξ?]xn,α[.

Org?(x) =f(x)f??(x)

La suite(xn)est croissante et major´ee; elle est donc convergente. Notons?sa limite. La continuit´e degpermet d"´ecrire que?=g(?)et doncf(?) = 0d"o`u?=α.

4.2. Interpr´etation graphique

La m´ethode de Newton consiste `a remplacer la courbe par sa tangente en une de ses deux extr´emit´es. Le pointx1est l"intersection de cette tangente avec l"axeOx.

Pour faire le dessin, on va se placer dans le cas ´etudi´e pourla m´ethode de la s´ecante, i.e.

f ?>0 etf??<0.On prend alorsx0=b. y=f(x)a

••bα• •x1f(x1)•

a,f(a)?•? b,f(b)?• M´ethode de NewtonTraons la tangente `a la courberepr´esentative defpassant par?b,f(b)?.L"´equation de cette tangente esty=f?(b)(x- b) +f(b).Son intersection avec l"axeOxa une ordonn´ee nulle et son abscisse vaut x

1=b-f(b)

f?(b).On trace en- suite la tangente `a la courbe au point?x1,f(x1)?.Le r´eel x

2est l"abscisse de l"intersec-

tion de cette deuxi`eme tan- gente avec l"axeOxet on r´eit`ere ce proc´ed´e. Remarque -Si on prenait la tangente `a la courbe en?a,f(a)?, son intersection avec l"axe Oxne serait pas, sur ce dessin, dans l"intervalle [a,b].

4.3. Rapidit´e de convergence de la m´ethode de Newton

On suppose que la fonctionfest de classeC3surI= [a,b], que l"on af(a)f(b)<0 et que les fonctionsf?etf??sont toutes deux strictement positives sur [a,b]. Ceci nous garantit l"existence et l"unicit´e d"une racine simpleαdefsur [a,b]. On a doncf(α) = 0 etf?(α)?= 0.

On poseg(x) =x-f(x)

f?(x)et on d´efinit la suite (xn) parx0=bet la relation de r´ecurrence x n+1=g(xn). Th´eor`eme 5 -On a alors limn→+∞|xn+1-α| |xn-α|= 0 et limn→+∞|xn+1-α||xn-α|2=12f (2)(α)f?(α)·

D´emonstration : puisquefest de classeC3,gest de classeC2; on ag?(α) =f(α)f??(α)(f?(α)2)=

0carαest racine simple def.

La formule de Taylor `a l"ordre 1 s"´ecritxn-α=g(xn)-g(α) = (xn-α)g?(ξ)org?est continue sur[a,b], donclimn→+∞|xn+1-α| |xn-α|=g?(α) = 0.

La formule de Taylor `a l"ordre 2 s"´ecrit

x n-α=g(xn)-g(α) = (xn-α)g?(α) +1

2(xn-α)2g??(ξ) =12(xn-α)2g(2)(ξ)

org?(2)est continue sur[a,b], donc lim n→+∞|xn+1-α| |xn-α|2=g(2)(α) =12f (2)(α)f?(α)· - 5 - Pr´eparation`a l"agr´egation interne UFR maths, Universit´e de Rennes I Remarque -Le r´esultat est encore vrai si on suppose quefest de classeC2.La d´emonstration est plus difficile... Remarque -On peut utiliser la m´ethode de Newton avec un point de d´epart dans ]a,b[, mais la convergence de la suite n"est pas garantie. En pratique, on utilise souvent la m´ethode de dichotomie pour trouver unx0assez proche de la racine.

5. Ordre de convergence

La convergence de la suite ne suffit pas num´eriquement, on aimerait avoir une estimation de la rapidit´e de convergence. On poseen=xn-α. enest l"erreur absolue au pasn.L"erreur relative vauten/α. D´efinition 6 -La m´ethode d´efinie parxn+1=g(xn) est dite d"ordrepsi|en+1| |en|pa une

limite non nulle en +∞.La m´ethode de la s´ecante est donc d"ordre 1 sig?(α)?= 0, tandis

que la m´ethode de Newton est d"ordre 2 sig(2)(α)?= 0. D´efinition 7 -Lorsque la m´ethode est d"ordre 1 (respectivement 2), on ditque la convergence est lin´eaire (respectivement quadratique). - 6 -

APPROXIMATION D"UNE SOLUTION

D"UNE´EQUATION NON LIN´EAIRE

1. M´ethode de dichotomie . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . 1

2. Th´eor`eme du point fixe . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . 2

3. M´ethode de la s´ecante . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . 2

3.1. Description de la m´ethode . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . 2

3.2. Rapidit´e de convergence de la m´ethode de la s´ecante .. . . . . . . . . . . . . . . . . . 4

4. M´ethode de Newton. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 4

4.1. Description de la m´ethode . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . 4

4.2. Interpr´etation graphique . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . 5

4.3. Rapidit´e de convergence de la m´ethode de Newton . . . . .. . . . . . . . . . . . . . . . 5

5. Ordre de convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . 6

- i -quotesdbs_dbs27.pdfusesText_33

[PDF] composition d'un journal

[PDF] avantage questionnaire anonyme

[PDF] la première page dun journal sappelle

[PDF] premiere page de journal personnalisé

[PDF] exemple questionnaire contraception

[PDF] les différentes parties d'un journal

[PDF] comment sont organisées les informations dans un journal

[PDF] premiere page d'un journal en anglais

[PDF] quiz littérature difficile

[PDF] culture générale littérature française

[PDF] quiz littéraire

[PDF] option grec au lycée

[PDF] option grec au collège

[PDF] consommation collaborative : perceptions

[PDF] option grec en 3ème