Cet ouvrage et des milliers d'autres font partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour les lire en ligne
En savoir plus

Partagez cette publication

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