Résolution approchée déquations ordinaires (EO): f(x)=0 Contents PDF

CHAPITRE 2

5 Méthode de la sécante. 12. 5.1 Convergence . Exemple 2.1 On cherche une racine de la fonction f (x) = x2 + x ? 6 = 0 sur. [1 2].

Méthode de la sécante

Méthode de la sécante. • La méthode de Newton nécessite le calcul de et on obtient la méthode de la sécante ... Exemple: (choix de g).

Analyse Numérique

20 0 615468502. Cet exemple confirme les remarques générales. La méthode de Newton est la plus rapide. Ici

EILCO : Analyse Numérique Chapitre 3 : Résolution Numérique des

Méthode de la sécante. Etude de la convergence Méthode de dichotomie : Exemple ... Si par exemple a = 1 b = 2 et ? = 10?4

Résolution dune équation méthodes de la sécante et de type point

2.3 Méthode de la sécante ou regula falsi (facultatif) démarrage (dans l'exemple on effectue 5 pas en partant de l'intervalle initial [2; 3].

1 Convergence 2 Critère darrêt

Exercice 4 : Faire un dessin illustrant la méthode de Newton pour la fonction y = xe?x avec x(0) = 0.5 puis x(0) = 2. Exemple 1 : considérons la fonction y =

Méthodes Numériques : Optimisation

arrive par exemple lorsque F est déjà le résultat d'un calcul complexe. Lemme 2.14 : Vitesse de convergence de la méthode de la sécante.

La méthode de la corde

La méthode de la corde. Groupe algorithmique de l'IREM d'Aix-Marseille. Henri ROLAND 2010-2011. 1) Position du problème. Soit f une fonction dérivable et

Résolution approchée déquations ordinaires (EO): f(x)=0 Contents

Admettez le résultat de convergence sur la méthode de sécante et essayez de Exemple 1.2.1 (Equations nonlinéaires dans les schémas numériques pour EDO).

L2EcoMaths/InfoMaths/Maths

Math209Analyse & Simulations

Universit

´e Paris-Sud Ann´ee20182019©Jean-Baptiste APOUNG KAMGA R

´esolution approch´ee d"´equations ordinaires (EO):f(x) = 0Vous trouverez ici le support du cours 5. Le contenu peut avoir

´et´e long pour les deux s´eances dedi´ees. Aussi il est fourni ici pour vous permettre d"acc ´eder aux d´etails des commentaires fournis en s´eances. Dans sa lecture, munissez-v ousde la fiche de tra vauxpratiques qui lui est associ

´ee et´eventuellement

de vos notes de cours. Insistez sur les remarques qui sont fournies et mises en

´evidence par lacouleur bleu .

Essayez les e xercicesqui sont fournis, certains v ouspermettront de mieux comprendre les remarques.

Admettez le r

´esultat de convergence sur la m´ethode de s´ecante et essayez de comprendre son in- terpr ´etation donn´ee dans la remarque qui la suit.Note 0.0.1(Guide pour´etudiants).Contents 1 G ´en´eralit´es, d´efinitions et exemples 3 1.1 D

´efinitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3

1.2 Exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.3 Remarque . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.4 Quelques notions sur les suites: vitesse de convergence, ordre et valeur ajout

´ee par une it´eration . . . .4

2 Position correcte du probl

`eme (Eq) 6

2.1 Notion de conditionnement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 Construction de sch

´emas num´eriques pour (Eq) 9

3.1 G

´en´eralit´es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .9

3.2 M

´ethode de dichotomie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .9

3.2.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.2.2 Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.2.3 Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.2.4 Analyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11 3.3 M

´ethode de fausse position . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .11

3.3.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .11

3.3.2 Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.3.3 Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.3.4 Analyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13 3.4 M

´ethode d"it´eration (ou du point fixe) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .13

3.4.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.4.2 Interpr

´etation g´eom´etrique: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .13

3.4.3 Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.4.4 Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.4.5 Analyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15 3.5 M

´ethode de Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .16

3.5.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.5.2 Interpr

´etation g´eom´etrique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .16

3.5.3 Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.5.4 Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.5.5 Analyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

18 3.6 M

´ethode de la s´ecante . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .20

3.6.1 principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.6.2 Interpr

´etation g´eom´etrique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .20

3.6.3 Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.6.4 Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.6.5 Analyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

22
2 1 G ´en´eralit´es, d´efinitions et exemples

Soitm >0un entier etIun domaine ferm´e born´e deRm. Soitf:I!Rmcontinue. On consid`ere le probl`eme :

(Eq)Chercherx2Itel que : f(x) = 0(1)1.1 D´efinitions•Le probl

`eme (1) est appel´e´equation lin´eairepos´e dansIlorsquefest affine. Dans le cas contraire il

est dit

´equation non-lin´eaire.

T outx2Isolution (1) est diteracineouz´erodefdansI. Si fest de classeCrsurIavecr1etxune racine defdansI, alors -xest diteracine simplesif0(x)6= 0, -xest diteracine de multiplicit´ep < r, sif(k)(x) = 0; k= 0;:::;p1;etf(p)(x)6= 0 -Lorsquem= 1c"est-`a-diref:IR!R, l"´equation est ditescalaire.D

´efinition 1.1.1.1.2 Exemples

L"une des utilisations importantes est la r

´esolution num´erique des´equations diff´erentielles ordinaires.

Nous avons vu au chapitre pr

´ec´edent que les m´ethodes implicites pour la r´esolution des EDOs avaient un certain avantage, sur les m ´ethodes explicites. Pour s"en convaincre, consid´erons le probl`eme _

L(t) =LL(t)t2]0;T[;avecL(0) =L0(2)

Un sch

´emas d"Euler explicite appliqu´e`a la r´esolution de cette´equation conduit`a la suite L n+1= (1 +Lt)Ln;n= 0;:::;N1

Alors qu"un sch

´ema d"Euler implicite conduirait`a la suite:

L n+1=Ln+LtLn+1;n= 0;:::;N1 La d

´etermination deLn+1se ram`ene ici`a la r´esolution de l"´equationx=Ln+xLtqui s"´ecrit aussi

xLnxLt= 0 On a vu que pourL0= 10;L=0:5;t= 3;T= 180, le sch´ema d"Euler explicite est incapable

d"approcher la solution exacteL(t) =L0etLalors que le sch´ema d"Euler implicite se comporte beaucoup

mieux. Ce pendant on ne pourra pas toujours r ´esoudre explicitement le probl`eme non-lin´eaire pos´e par les sch ´emas`a un pas implicites. C"est le cas par exemple de l"´equation _u(t) =eu(t)t2]0;T[;avecu(0) =u0:(3)

Ici le sch

´ema d"Euler implicite s"´ecrit

u n+1=un+ teun+1; n= 0;:::;N1:

Pour toutn= 0;:::;N1, cette´equation ne pourraˆetre r´esoluble que de mani`ere approch´ee

(num

´eriquement). Sachant queNpeutˆetre tr`es grand en pratique, cette r´esolution devraˆetre efficace: rapide

(pascoˆuteuse) et pr´ecise (afin de ne pas accroˆıtre l"erreur locale de la m´ethode`a un pas implicite).Exemple 1.2.1(Equations nonlin´eaires dans les sch´emas num´eriques pour EDO).3

Dans un probl

`eme de tir`a canon, on est souvent amen´e`a d´eterminer l"angle vertical d"orientation du canon

afin d"atteindre une cible pr

´ecise.

En une dimension le probl

`eme peut se mettre sous la forme (4) o`ufest une certaine fonction donn´ee:

Chercherx0(0)o`u8<

00(t) =f(t;x(t));t2]0;T[;

x(0) =x0; x(T) =xT(4)

On obtient ici un probl

`eme aux limites et non un probl`eme de Cauchy pour une´equation diff´erentielle! Si l"on dispose d"un bon solveur d"Edo, on peut en faire usage. On peut en effet transformer ce probl `eme en un probl

`eme de Cauchy (en une edo), en introduisant une inconnue n´ecessaire pour d´efinir une condition

initiale :

En effet, si pourv2Ron consid`ere le probl`eme :

8< :z

00(t) =f(t;z(t));t2]0;T[;

z(0) =x0; z

0(0) =v(5)

On a alors un probl

`eme de Cauchy pour une Edo. Si l"on pose alorsg(t;v)la solution de cette Edo, en l" ´evaluant`at=Ton d´efinit une fonctiong(T;v)de la seule variablev.

Le probl

`eme de d´etermination de la vitesse initiale revient alors`a r´esoudre l"´equation d"inconnuev:G(v) =

0, avecG(v) =g(T;v)xTExemple 1.2.2(M´ethode de tir pour les probl`emes aux limites du second ordre).Il appara

ˆıt donc que dans certaines´equations non lin´eaires, l"expression de la fonction dont on cherche une racine peut

etre biencomplexe: ici une´evaluation de la fonctionGn´ecessite une r´esolution d"Edo. Il est donc n´ecessaire de chercher

des m

´ethodes num´eriques de r´esolution d"´equations non-lin´eaires qui soient efficaces et si possible sans recours au calcul

des d

´eriv´ees.

1.3 Remarque

Il appara

ˆıt`a travers ces exemples que :•la r

´esolution analytique des´equations non-lin´eaires n"est pas toujours possible, mˆeme lorsqu"on sait

qu"il en existe des solutions. D"o `u la n´ecessit´e de recourir`a des algorithmes efficaces (en terme de pr

´ecision et coˆut) permettant d"en d´eterminer des solutions approch´ees. C"est-`a-dire`a lar´esolution

num

´erique efficacede ces´equations.

La plupart des

´equations non-lin´eaires sont donn´ees sous la formex=g(x). On dit que l"´equation non-lin ´eaire est pos´ee sous forme derecherche de point fixe.Remarque 1.3.1.

1.4 Quelques notions sur les suites: vitesse de convergence, ordre et valeur ajout

´ee par une

´eration

Comme nous le verrons, la recherche de solution approch ´ee conduira`a la construction de suites qui convergent vers la solution du probl `eme. Il est donc n´ecessaire de quantifier cette convergence. Pour cela un rappel sur l"ordre de convergence des suites est n

´ecessaire.

Soitxnune suite r´eelle qui converge versx

Si K1= limnxxn+1xxnexiste et siK12]1;1[nf0g, on dit que la suitexnconvergelin´eairement versx. On parle aussi de convergenced"ordre 1.

Si K1= 0et siK2= limnxxn+1(xxn)2existe et n"est pas´egale`a z´ero, on dit que la suitexnconverge

quadratiquementversx. On parle aussi de convergenced"ordre 2. Si K1= 0;K2= 0et siK2= limnxxn+1(xxn)3existe et n"est pas´egale`a z´ero, on dit que la conver- gence estcubiqueou encored"ordre 3.D

´efinition 1.4.1.On g

´en´eralise de mani`ere´evidente cette d´efinition`a des convergences d"ordres sup´erieures. Remarquons qu"il n"est pas

´ecessaire en pratique de calculer la limite pour conclure car cette limite peut ne pas exister. On utilise alors la d´efinition

suivanteLa convergence de la suitexnversxest d"ordrersi9Ntel que8n > N

0< Ajxn+1xjjxnxjrB <1

o `uA;Bsont deux constantes ind´ependantes den. La convergence est d"ordreau moinsrsi seule l"in´egalit´e avecBa lieu.D ´efinition 1.4.2.Signalons cependant qu"il faut passer par la d ´efinition avec la limite pour d"acc´eder`a l"estimation du nombre de chiffres exactes ajout ´es par it´eration. En effet, si la suite est convergente d"ordrerdans le sens o`u K r= limnjxxn+1jjxxnjrexiste et est non nul (Krest appel´econstante asymtotiquede l"erreur), alors d

n=log10jxnxjmesure le nombre de chiffres d´ecimaux dexnet dexqui co¨ıncident(`a une constante

additive pr `es ne d´ependant pas den) et on a d n+1rdnlog10(Kr):

Ce qui montre qu"

`a une constante additive pr`es, le nombre de chiffres exactes est multipli´e parr`a chaque it

´eration.

En effet on adn+1+ log10(Kr)=(1r) =r(dn+ log10(Kr)=(1r)).

Onpeutdoncestimerlenombred"it

´erationsn´ecessairespourgagnerunchiffreexacte. Enparticulier, lorsque la convergence est lin ´eaire, comme ce sera le cas pour la plupart des m´ethodes que nous verrons, mˆeme celles d"ordre

´elev´ee lorsqu"elles seront confront´ees`a des situations particuli`eres comme celles de recherche des

racines multiples.Remarque 1.4.1.

Soitxnune suite qui converge lin´eairement avec une constante asymptotique d"erreur´egale`aK. Alors le

nombre d"it

´erations n´ecessaires pour gagner un chiffre exacte est le plus petit entier sup´erieur`a1log10(K).Proposition 1.4.1((importance de la constante asymptotique d"erreur dans une convergence lin´eaire).5

la formule de r ´ecurrence du nombre de chiffres exactes par it´eration est donn´ee ici pardn+1=dn log

10(K). Ainsi apr`es m it´erations`a partir de l"it´erationn, on adn+m=dnmlog10(K). Par cons´equent,

d n+m=dn+ 1si et seulement sim=1log10(K)(arrondi`a l"entier sup´erieur).D

´emonstration.Quelques fois il est suffisant d"estimer l"ordre de convergence au moyen de comparaisons:

Soientxn,yndeux suites qui convergent respectivement versx,y. On dit quexnconverge plus vite que y nsilimn!1xnxyquotesdbs_dbs47.pdfusesText_47

[PDF] Résolution approchée déquations ordinaires (EO): f(x)=0 Contents

L2EcoMaths/InfoMaths/Maths

Math209Analyse & Simulations

Universit

´ee et´eventuellement

´evidence par lacouleur bleu .

Admettez le r

1.2 Exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.3 Remarque . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.4 Quelques notions sur les suites: vitesse de convergence, ordre et valeur ajout

´ee par une it´eration . . . .4

2 Position correcte du probl

2.1 Notion de conditionnement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 Construction de sch

´emas num´eriques pour (Eq) 9

3.2.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.2.2 Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.2.3 Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.2.4 Analyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.3.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .11

3.3.2 Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.3.3 Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.3.4 Analyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.4.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.4.2 Interpr

3.4.3 Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.4.4 Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.4.5 Analyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.5.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.5.2 Interpr

3.5.3 Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.5.4 Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.5.5 Analyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.6.1 principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.6.2 Interpr

3.6.3 Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.6.4 Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.6.5 Analyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

´equation non-lin´eaire.

´efinition 1.1.1.1.2 Exemples

L"une des utilisations importantes est la r

Nous avons vu au chapitre pr

L(t) =LL(t)t2]0;T[;avecL(0) =L0(2)

Un sch

Alors qu"un sch

´ema d"Euler implicite conduirait`a la suite:

Ici le sch

´ema d"Euler implicite s"´ecrit

Dans un probl

´ecise.

En une dimension le probl

Chercherx0(0)o`u8<

00(t) =f(t;x(t));t2]0;T[;

On obtient ici un probl

En effet, si pourv2Ron consid`ere le probl`eme :

00(t) =f(t;z(t));t2]0;T[;

0(0) =v(5)

On a alors un probl

Le probl

0, avecG(v) =g(T;v)xTExemple 1.2.2(M´ethode de tir pour les probl`emes aux limites du second ordre).Il appara

´eriv´ees.

1.3 Remarque

Il appara

ˆıt`a travers ces exemples que :•la r

´erique efficacede ces´equations.

La plupart des

1.4 Quelques notions sur les suites: vitesse de convergence, ordre et valeur ajout

´ee par une

´eration

´ecessaire.

Soitxnune suite r´eelle qui converge versx

´efinition 1.4.1.On g

0< Ajxn+1xjjxnxjrB <1

Ce qui montre qu"

´eration.

Onpeutdoncestimerlenombred"it

10(K). Ainsi apr`es m it´erations`a partir de l"it´erationn, on adn+m=dnmlog10(K). Par cons´equent,