Methodes iteratives pour la resolution d'equations

De
Publié par

CHAPITRE XVII Methodes iteratives pour la resolution d'equations To explain all nature is too difficult a task for any one man or even for any one age. ‘Tis much better to do a little with certainty, and leave the rest for others that come after you, than to explain all things. Isaac Newton (1642-1727) Objectif. Les methodes iteratives figurent parmi les methodes numeriques les plus courantes et le plus puissantes. L'idee est de partir d'une valeur approchee (souvent grossiere) de la solution, puis d'augmenter la precision par l'application iteree d'un algorithme bien choisi. Dans ce chapitre nous discutons deux methodes iteratives classiques : la methode du point fixe pour resoudre une equation du type f (x) = x ou f est une fonction contractante, puis son raffinement, la methode de Newton pour resoudre f (x) = 0 ou f est une fonction derivable. Pour des complements voir le livre de J.-P. Demailly, Analyse numerique et equations differentielles, EDP Sciences, 1996. Sommaire 1. La methode du point fixe. 1.1. Dynamique autour d'un point fixe. 1.2. Espaces metriques. 1.3. Fonctions contractantes. 1.4. Le theoreme du point fixe. 1.5. Quelques applications. 2. La methode de Newton. 2.1. Vitesse de convergence. 2.2. Iteration de Newton.

  • equation de recurrence xn

  • solutions reelles de l'equation exp

  • precision par l'application iteree

  • convergence

  • espace metrique

  • point fixe

  • methode de point fixe

  • unique point


Publié le : mardi 19 juin 2012
Lecture(s) : 106
Source : www-fourier.ujf-grenoble.fr
Nombre de pages : 16
Voir plus Voir moins
To explain all nature is too difcult a task for any one man or even for any one age. `Tis much better to do a little with certainty, and leave the rest for others that come after you, than to explain all things. Isaac Newton (1642-1727)
CHAPITRE XVII
M´ethodesite´rativespourlar´esolutiond'e´quations
Objectif. Lesm´ethodesite´rativesgurentparmilesm´ethodesnume´riqueslespluscourantesetleplus puissantes.L'id´eeestdepartird'unevaleurapproche´e(souventgrossiere)delasolution,puisd'augmenter lapr´ecisionparl'applicationit´ere´ed'unalgorithmebienchoisi. Danscechapitrenousdiscutonsdeuxm´ethodesite´rativesclassiques:lame´thodedupointxepour r´esoudreune´equationdutype f ( x ) = x ou f est une fonction contractante, puis son rafnement, la me´thode deNewtonpourr´esoudre f ( x ) = 0ou f est une fonction de´rivable. Pour des comple´ments voir le livre de J.-P. Demailly, Analysenume´riqueet´equationsdiffe´rentielles , EDP Sciences, 1996. Sommaire 1.Lam´ethodedupointxe. 1.1. Dynamique autour d'un point xe. 1.2. Espaces me´triques. 1.3.Fonctionscontractantes.1.4.Lethe´oremedupointxe.1.5.Quelquesapplications. 2. La me´thode de Newton. 2.1.Vitessedeconvergence.2.2.It´erationdeNewton.2.3.Exemples. 2.4. Bassin d'attraction. 2.5. Version quantitative. 2.6. Criteres pratiques. 3. Application aux polynoˆmes complexes. 3.1.Leth´eoremedeGauss-d'Alembert.3.2.Relation entre racines et coefcients. 3.3. Instabilite´ des racines mal conditionne´es. Retour sur la me´thode dichotomique Commenc¸ons par la me´thode « par tˆatonnement » que l'on appelle plus savamment « la me´thode di-chotomique » .Cetteme´thodealem´erited'ˆetre´ele´mentaire,maiselleadeuxinconv´enients:d'abordelle neconvergequelentement,puisimple´mente´ena¨vementa(vecdesarrondisale´atoires)ellepeutˆetreinuti-lisableacausedesphe´nomenesdebruit,de´jadiscsuta´euchapitreXV, § 5.6. Exemple 0.1. Le programme dichotomie.cc r´esoutleproblemedebruitparuncalculablebase´sur l'arithm´etiqued'intervalles.(Lelirepuisletester.)Ladifcult´eprincipaleestd'imple´mentersoigneuse-mentlafonctiondonn´ee f : R R selon l'arithmetique d'intervalles arrondie en une fonct ion ´ Interval f( const Interval& x ) . D'une part il faut garantir l'encadrement de l'image exacte , et d'autre part cet encadrement doit ˆetre assez precis, c'est-a-dire on veut e´viter des sur-encadrements grossiers. Discuter l'importance de ces pre´requis ´ pourlacorrectionetl'efcacite´delam´ethodedichotomique.Puisanalyserbrievementcommentsatisfaire ces exigences pour un polyn ˆome comme f ( x ) = x 6 9 x 5 + 30 x 4 40 x 3 + 48 x 32. Exemple 0.2. Lam´ethodedichotomiqueseg´ene´raliseducasunidimensionnel f : R R aux fonctions f : R m R n , disons avec m = n = 2pourxerlesid´ees.Sicelavousint´eresse,vouspouvezregarderle lm www-sop.inria.fr/coprin/logiciels/ALIAS/Movie/movie_undergraduate.mpg puis ana-lyserlam´ethodepropos´ee.Essayezd'abordded´ecrirel'algorithmeplusend´etail:commeavantlaprin-´ cipaledifcult´eestdebienimple´menter f selonl'arithm´etiqued'intervallesarrondie.Etantdonn´eeune telleimpl´ementationde f , formulez l'algorithme dichotomique puis prouver sa corre ction. (Si vous ˆetes zl'il´ementerenpartantduprogramme dichotomie.cc .) courageux, vous pouve mp Danscechapitrenouschercheronsaobtenirdesm´ethodesti´erativesquiconvergentplusrapidement etquiserontplusfacilesaimpl´ementerquelame´thodedichotomique.Nousd´evelopponsl'essentieldela the´orie,leth´eoremedupointxeetlame´thodedeNewto,nsousuneformeprˆeteaprogrammer.Parcontre, laprobl´ematiquedescalculsablessera(temporairement)ne´glig´eandenepasencombrerlapremiere pr´esentation.Ceciestpartiellementjusti´eparlefaitqu'unefonctioncontractantesoitnum´eriquement stable,etlorsdesit´erationsleserreursaccumul´eesrestentborn´ees(etonesperemˆemen´egligeables). 311
312
ChapitreXVII—Me´thodesite´rativespourlar´esolutiond'e´quations
1.Lam´ethodedupointxe 1.1. Dynamique autour d'un point xe. Nous allons nous inte´resser aux ite´rations d'une fonctio n f : E E ,ou ( E d ) estunespacem´etrique.Typiquement E est une partie de R m et d : E × E R est la erees distance euclidienne d ( x y ) = å i ( x i y i ) 2 . La fonction f peut ˆetre complique´e, d'autant plus ses it´ ´ f 2 = f f , f 3 = f f f , f 4 = f f f f ,...Nousnecalculonsjamaiscesit´ere´estoutesentierse.Nous supposonsseulementqu'ilestfacilea´evaluer f en un point donne´, et nous allons suivre sa trajectoire : ´ ive ( ) N De´nition 1.1. Etant donne´e f : E E et une valeur initiale x 0 nous construisons la suite ite´rat x n n partant de x 0 parl'applicationit´er´eedelafonction f , de sorte que x n + 1 = f ( x n ) pour tout n N . Le cas trivial est celui d'un point xe de f , c'est-a-dire d'un point a E tel que f ( a ) = a . Par contre, le comportement de f dans un voisinage d'un point xe a peut nous donner des renseignements utiles : Exemple 1.2. L'exemple le plus simple est une fonction line´aire f : R R , f ( x ) = kx avec une constante k R . Elle admet a = 0 pour point xe. Pour x 0 6 = 0deuxph´enomenespeuventseproduire: 1 (1) Si | k | < 1, par exemple k = alors les images successives x n = f n ( x 0 ) s'approchent de a , car 2 , | f n ( x 0 ) a | = | k | n  | x 0 a | → 0. On dit que a est un point xe attractif (ou stable ). (2) Si | k | > 1, par exemple k = 2, alors les images successives x n = f n ( x 0 ) s'e´loignent de a , car | f n ( x 0 ) a | = | k | n  | x 0 a | → υ . On dit que a est un point xe re´pulsif (ou instable ). Exemple 1.3. Plus ge´ne´ralement, e´tudions une fonction f : R R que l'on suppose contin ˆument de´rivable. Comme avant nous supposons qu'elle admet un point xe a = f ( a ) . (1) Supposons que | f ( a ) | < 1. Dans ce cas on peut choisir n'importe quelle constante k telle que | f ( a ) | < k < 1,etlacontinuit´ede f nous assure l'existence d'un voisinage V = [ a Α a + Α ] tel que | f ( Π ) | ≤ k pour tout Π V . Pour tout x V nous pouvons ainsi majorer les accroissements : il existe Π entre a et x tel que f ( x ) f ( a ) = f ( Π )( x a ) ,etparcons´equent | f ( x ) a | = | f ( x ) f ( a ) | = | f ( Π )( x a ) | ≤ k | x a | Ainsi les images ite´re´es de x V sont de plus en plus proches de a ,pluspre´cis´ement: | f n ( x ) a | ≤ k n | x a | pour tout n N . Autrement dit, a est un point xe attractif . (2)Re´ciproquementl'ine´galit´e | f ( a ) | > 1 implique que | f | ≥ k > 1 dans un voisinage V de a : toute valeur initiale x V r { a } s'´eloignede a , dans le sens que | f ( x ) a | ≥ k | x a | . Autrement dit, a est un point xe r´epulsif . + Astuce. — Dans ce cas on peut inverser f , au moins localement : la restriction f | V : V U er e est une bijection de V sur U = f ( V ) ; son inverse g = f | V 1 est une fonction contin ˆument d´ ivabl avec g ( a ) = a et g ( a ) = f 1 ( a ) . (Le prouver.) On peut ainsi se ramener au premier cas. (3) Dans le cas douteux | f ( a ) | = 1, une analyse plus ne s'impose. Pour x 7→ x x 3 le point xe a = 0 est attractif, pour x 7→ x + x 3 ilestr´epulsif.(Lede´tailler.)Pour x 7→ x + x 2 il est attractif a gauchemaisr´epulsifadroite,pour x 7→ x x 2 c'estl'inverse.(Led´etailler.) Remarque 1.4. En dimension 2 la situation peut ˆetre plus complexe. Conside´rons une application line´aire ( xy ) 7→ l 0 0 m ( xy ) . Si | l | | m | < 1, le point xe a = 0 est attractif. Si | l | | m | > 1,ilestr´epulsif. Si | l | < 1 < | m | , il existe une direction stable et une direction instable. ´ ´e un ensemble E et une suite ( ) N dans E ,commentd´enirla 1.2.Espacesm´etriques. Etant donn x n n notiondeconvergence?Lafa¸conlapluscommodeseraitdedisposerd'unenotiondedistance d ( x y ) entre deux points x y E , c'est-a-dire une application d : E × E R . Pour que la distance se comporte comme onlesouhaite,nousexigeonslestroisproprie´t´essuivantes: Positivit´e: d ( x y ) 0 pour tout x y E , avec d ( x y ) = 0 si et seulement si x = y . Sym´etrie: d ( x y ) = d ( y x ) pour tout x y E . Ine´galite´ triangulaire: d ( x z ) d ( x y ) + d ( y z ) pour tout x y z E . MAE 22 juin 2009
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.