SMP3 : ANALYSE NUMÉRIQUE ET ALGORITHMIQUE PDF

TP2 : f(x)=0

On recommence ensuite la procédure sur l'intervalle o`u f change de signe et ainsi de suite. Exercice 2. On souhaite utiliser la méthode de dichotomie pour

Analyse Numérique

Exercice 4.6 Calculer. ∫ +∞. 0.5 e. −t3 dt avec 4 décimales exactes. Page 92. 92 ... méthode de Givens et on note M (i µ) le nombre de paires consécutives de ...

Analyse Numérique - Corrigé du TD 5

méthode de dichotomie produit une suite de sous-intervalles In = [anbn]

Corrige de l exercice sur la dichotomie

Corrigé exercice Dichotomie. Corrigé exercice 2 Méthode de dichotomie pour la résolution d'une équation. 0. = )x(f. Théorème : Soit f est une fonction continue

DICHOTOMIE

On a représenté ci-dessous la fonction f définie par ( ) = − 7 . L'objectif est de déterminer sur l'intervalle [2 ; 4]

1 Algorithme de dichotomie

méthode par balayage. (Détailler les étapes). 2 Suites récurrentes. Exercice 3. On considère la suite (un) définie par u0 = 1 et pour tout entier naturel n ...

SMP3 : ANALYSE NUMÉRIQUE ET ALGORITHMIQUE

Exercice 1 : La méthode de la Dichotomie : Recherche de la racine x de l'équation f(x)=0 dans l'intervalle [a b] (x est la seule racine dans [a

Retour sur le TD Exercice 2 - Recherche de racine par dichotomie

1. Nous considérons la fonction f qui à x ∈ [05] associe x2 -1. Tracer cette fonction. 2. Implémenter la méthode

Méthodes numériques

2.5 Corrigés des exercices Figure 1 : Principe de la méthode de Dichotomie. 1.3.1.2 Convergence et estimation de l'erreur. Pour montrer que la méthode de ...

Chapitre 1: Résolution déquations à laide de méthodes

La méthode de dichotomie consiste à construire une suite d'intervalles Exercice 1.8 Quelles sont les valeurs fournies par la méthode de Newton pour la.

Analyse Numérique

Rappeler la méthode de dichotomie qui permet d'approcher ce zéro de f. Par suite d'apr`es l'exercice 1

USTV 2011/2012

10?/05?/2012 Recueil d'exercices corrigés ... les méthodes de dichotomie et de LAGRANGE (appelée aussi Regula falsi) produisent une suite de ...

Analyse Numérique

1.5 Exercices du chapitre 1 . 2.2.2.1 Méthode de dichotomie (ou bisection) . . . . . . . . . . 18 ... 4.4.2.5 Méthode des trapèzes corrigés .

TP2 : f(x)=0

Les exercices de cette séance de travaux pratiques seront résolus `a l'aide La méthode de dichotomie pour trouver la solution d'une équation f(x) = 0 ...

1 Algorithme de dichotomie

TP INFO n° 2 : Algorithme de dichotomie et Suites. TS. 1 Algorithme de dichotomie. Exercice 1. Etude d'une fonction auxiliaire f et de solutions approchées

Résolution déquations non linéaires £ ¢ ¡ Exercice 4.1 Correction

et on pose xk+1 = ak + bk. 2 . Figure 3 – Étude graphique de la convergence (méthode de dichotomie). • Méthode de Newton xk+1 = xk ?.

SMP3 : ANALYSE NUMÉRIQUE ET ALGORITHMIQUE

Exercice 1 : La méthode de la Dichotomie : Recherche de la racine x de l'équation f(x)=0 dans l'intervalle [a b] (x est la seule racine dans [a

Fiche 2 : Les fonctions

Fiche Exercices. Calculer des limites. Méthode : Encadrer une solution d'une équation du type f (x ) = 0par dichotomie. Méthode :.

Chapitre 1: Résolution déquations à laide de méthodes

La méthode de dichotomie consiste à construire une suite d'intervalles Exercice 1.2 1) Montrer que chaque équation suivante n'admet qu'une solution.

Zéros de fonctions

Le principe de dichotomie repose sur la version suivante du théorème des valeurs La méthode de dichotomie a l'énorme avantage de fournir un encadrement ...

Analyse Num´erique Corrig´e du TD 5 - Côte d'Azur University

La m´ethode de dichotomie est bas´ee sur le th´eor`eme suivant : Th´eor`eme 2 1 Soit [ab] un intervalle ferm´e de R et f : [ab] ? R une fonction continue Si f(a)f(b) < 0 alors ?? ?]ab[ tel que f(?) = 0 On se donne un intervalle I 0 = [ab] contenant le z´ero ? que l’on veut approcher La m´ethode de dichotomie produit

Méthode de la dichotomie Exercice 1 - e-monsite

Méthode de la dichotomie Exercice 1 On va utiliser la recherche d’une valeur approchée d’une solution d’une équation par la méthode de dichotomie : On souhaite par exemple trouver une valeur approchée de la solution de l’équation xex ? 1 = 0 Justifier que l’équation précédente admet une unique solution sur [0; 1]

Zéros des fonctions - e Math

En?n voici la version récursive de l’algorithme de dichotomie Code 4 (dichotomie py (4)) def dichotomie(abprec): if b-a

Méthodesnumériques:optimisation L32016–2017—2 semestre

La méthode de dichotomie est la suivante : par récurrence on pose c n = 1 2 (a n + b n) le point milieuetondé?nitensuite: (a n+1;b n+1) = (a n;c n) sif0(c n) >0 (c n;b ) sif0(c )

SMP3 : ANALYSENUMÉRIQUE ETALGORITHMIQUE

---------------SÉRIEN01---SOLUTIONS--------2017 - 2018

Exercice 1 :La méthode de la Dichotomie:

Recherche de la racinexde l"équationf(x) = 0dans l"intervalle[a;b](xest la seule racine dans[a;b])

avec une précision".

Initialisation :a0=a,b0=b

Tant quejbkakj> "(test d"arrêt)!faire#(une boucle de calcul à refaire tant que la condition est

vérifiée) :

Calculerxk=ak+bk2

et :

Sif(ak)f(xk)<0Alorsak+1:=aketbk+1:=xk

Sinonak:=xketbk+1:=bk

Sijbnanj "!Fin.

Conclusion :xn=an+bn2

est une valeur approchée dexavec une précision". Méthode de Lagrange(utilisant la droite qui passe par(ak;f(ak))et(bk;f(bk))au lieu du centre de l"intervalle[ak;bk]) :

Recherche de la racinexde l"équationf(x) = 0dans l"intervalle[a;b](xest la seule racine dans[a;b])

avec une précision".

La méthode est une généralisation de la méthode de dichotomie : la valeur dexkest déterminée comme

intersection de la droite qui passe par les deux points(ak;f(ak))et(bk;f(bk))et l"axe des abscisses.

La méthode est à différencier avec les autres méthodes utilisant une sécante notamment la variante de

la méthode de Newton qui consiste à remplacerf0(xk+1)parf(xk)f(xk1)x kxk+1ou, autrement dit, on rem- place la tangente par la sécante.

Initialisation :a0=a,b0=b

Tant quejbkakj> "(test d"arrêt)!faire#(une boucle de calcul à refaire tant que la condition est

vérifiée) : Calculerxk=akbkakf(bk)f(ak)f(ak) =akf(bk)bkf(ak)f(bk)f(ak)et :

Sif(ak)f(xk)<0Alorsak+1:=aketbk+1:=xk

Sinonak:=xketbk+1:=bk

Sijbnanj "!Fin.

Conclusion :xn=anbnanf(bn)f(an)f(an) =anf(bn)bnf(an)f(bn)f(an)est une valeur approchée dexavec une

précision".

Les tests d"arrêt peuvent être différents d"une méthode à l"autre et suivant la précision cherchée,

généralement, nous pouvons distinguer trois type de conditions d"arrêt : 1)

Majoration de l"erreur absolue par une quantité qui ne dépends pas de la racine recherchée xni

dexk, par exemple, dans les méthodes de Dichotomie et de la Lagrange on a : jxkxj jbkakj Il st suffisant de choisirjbkakj "pour obtenir la précision recherchée 2)

T estbasé sur le résidu : jf(xk)j "

T estbasé sur l"incrément : jxk+1xkj "

Suivant la situation et les conditions initiales, chaque test peut être considéré comme satisfaisant

ou trop restrictif. 1 2 Application:x3+ 2x2+ 10x20,a= 1,b= 2et"= 102= 0:01:

1)Localisation de la racine: On af(1) =7,f(2) = 16et :f0(x) = 3x2+ 4x+ 10>0pour tout

x2[1;2]. En résumé :8< :fest continue surR(polynôme) f(1):f(2)<0 fest croissante sur[1;2] D"après le théorème des valeurs intermédiaires, il existex2[1;2]unique tel quef(x) = 0. Initialisation(Méthode de Dichotomie) :a0= 1,b0= 2et"= 102= 0:01 - On a :jb0a0j=j32j= 1>0:01donc :8< :x

0=2+32

= 1:5 f(x0) =f(1:5) = 2;875 f(a0):f(x0)<0)a1= 00= 1 b

1=x0= 1;5

Le reste des calculs est dans le tableau suivant (les deux dernières colonnes ne sont pas obligatoires et

sont utilisées juste pour comparer les différents tests d"arrêt) :- On a :jb7a7j=j1;3751;3671875j= 0;0078125<0:01donc : FIN, et :

7=1;375+1;36718752

= 1;37109375est une valeur approchée dexà102près en utilisant le test basé sur la majoration de l"erreur parjbkakj.

Remarque :

Nous pouv onsdéterminer le nombre d"itérations a vantde f aireles calculs et en utilisant la préci-

sion demandée : e nba2 n=12 n0:01) nln(2)ln(0:01))n ln(0:01)ln(2) '6:64

Doncn= 7etx7est l"approximation cherchée.

Si on utilise les autres tests, le nombre d"itérations n"est pas forcément ég alà 7mais peut aug-

menter ou diminuer suivant les cas (voir les deux dernières colonnes du tableau) :

Test basé sur le résidu : 8 itérations

Test basé sur l"incrément : 6 itérations. Initialisation (Méthode de Lagrange):a0= 1,b0= 2et"= 102= 0:01- On a :jb0a0j= j32j= 1>0:01donc :8>< :x

0=1f(2)2f(1)f(2)f(1)= 1;304347826

f(x0) =f(1;304347826) =1;334757952 f(a0):f(x0)>0)a1=x0= 1;304347826 b

1=b0= 2

Le reste des calculs est dans le tableau suivant :- On remarque que la quantitéjbkakjvarie très lentement et après quelques itérations, elle a une

valeur stationnaire approximativement égale à0;63. On en déduit que pour cette exemple, on ne peut

pas utiliser le test d"arrêt basé sur la majoration de l"erreur parjbkakj. Par contre, nous pouvons

utiliser les deux autres tests : Test basé sur le résidu : 3 itérations et une valeur approchée égale à1;36850 Test basé sur l"incrément : 2 itérations et une valeur approchée égale à1;36698.

REMARQUES:

Nous ne pouvons pas utiliser la majorationenba2

npour déterminer en avance le nombre d"itérations.

La determination préalable du nombre d"itérations nécessite d"établir une majoration du typeenMn

propre à cette méthode. Exercice 2 :Soitf: [1;2]!Rune fonction continue strictement croissante telle quef(1) =1et f(2) = 1:

Les conditions de l"application du théorème des valeurs intermédiaires sont vérifiées, nous pouvons

en déduire qu"il existe une seule racine (x= 1:6555) dans l"intervalle[1;2]. 1. Méthode de la dichotomie dans l"inter valle[1;2] On applique successivement les étapes de la méthode de Dichotomie en remarquons quef(x)<0 sur[1;1:6555[etf(x)>0sur]1:6555;2]. a

0= 1,b0= 2,x0= 1:5,f(x0)<0,f(a0)f(x0)>0, donca1=x0= 1;5etb1=b0= 2et ainsi

de suite :ka kx kb ksigne def(ak)signe def(xk)signe def(bk)011,52--+

11,51,752-++

21,51,6251,75--+

31,6251,68751,75-++

41,6251,656251,6875-++

Combien d"itérations f aut-ilef fectuerpour approcher le zéro de fà210près? à25près?

jxnxj ba2 n=12 n1010) nln(2) 10ln(10))n10ln(10)ln(2) '33;2)n= 34 jxnxj ba2 n=12 n105) nln(2) 5ln(10))n5ln(10)ln(2) '16;6)n= 17

Exercice 3 :1.Donner la suite définissant la méthode de Ne wtonpour la recherche d"un zéro de

fonction. Justifier l"expression de la suite : On a :(x

0donnée

x n+1=xnf(xn)f 0(xn)

Pour déterminerxk+1, la méthode consiste à remplacer localement la courbe de la fonction par la

tangente qui passe pasxket d"équation :Tk:y=f0(xk)(xxk) +f(xk) 4 La valeurxk+1est l"abscisse du point d"intersection de la droiteTkavec l"axe des abscisses (l"in- tersection n"existe que sif0(xk)6= 0), on a :

0 =f0(xk)(xk+1xk) +f(xk) =xk+1f0(xk)xkf0(xk) +f(xk))xk+1=xkf(xk)f

0(xk) carf0(xk)6= 0. 2. Écrire l"algorithme pour une con vergenceà 106près;x0donnée,x1=x0f(x0)f 0(x0) Tant quejxk+1xkj>106(ou tant quejf(xk)j>106)#Faire (une boucle de calcul) : x k+1=xkf(xk)f 0(xk) Le dernier terme de la suite est une approximation dexà106près. Conditions suffisantes de convergence de la suitexnvers la racinex:

1)fest de classeC2sur[a;b]

2)f(a)f(b)<0

3)f0(x)6= 0sur[a;b]

4)f00(x)6= 0sur[a;b]

5)f(x0)f00(x)>0sur[a;b](f(x0)est de même signe quef00(x)sur l"intervalle)

REMARQUES:

1) Sif(x0)f00(x)<0on calculex1et sif(x1)f00(x)>0etx12[a;b]nous avons aussi la conver-

gence. 2. Déterminer l"ordre de con vergenceminimale de cette suite : Si la racine xest telle quef0(x)6= 0 et si la suitexn!xest la convergence est au moins quadratique (p= 2). En effet : x n+1x=xnf(xn)f

0(xn)x

Ou encore (en rappelant quef(x) = 0) :

(1)xn+1x=(xnx)f0(xn)f(xn) +f(x)f 0(xn) D"autre part, par application de la formule de Taylor-Lagrange, à l"ordre 2, il existencomprise entrexnetxtel que : f(x) =f(xn)+(xxn)f0(xn)+(xxn)2f00(n)2 )f(x)f(xn) = (xxn)f0(xn)+(xxn)2f00(n)2

En replaçant dans(1), on obtient :

x n+1x=f00(n)f

0(xn)(xxn)22

)en+1=f00(n)f

0(xn)e2n

On en déduit (on peut supposer quef0(x)>0) :

lim n!+1jen+1jjenj2=jf00(x)j2jf0(x)j>0finie

En effet, on a :

x n!xquotesdbs_dbs7.pdfusesText_5

[PDF] SMP3 : ANALYSE NUMÉRIQUE ET ALGORITHMIQUE

SMP3 : ANALYSENUMÉRIQUE ETALGORITHMIQUE

Exercice 1 :La méthode de la Dichotomie:

Initialisation :a0=a,b0=b

Calculerxk=ak+bk2

Sif(ak)f(xk)<0Alorsak+1:=aketbk+1:=xk

Sinonak:=xketbk+1:=bk

Sijbnanj "!Fin.

Conclusion :xn=an+bn2

Initialisation :a0=a,b0=b

Sif(ak)f(xk)<0Alorsak+1:=aketbk+1:=xk

Sinonak:=xketbk+1:=bk

Sijbnanj "!Fin.

T estbasé sur le résidu : jf(xk)j "

T estbasé sur l"incrément : jxk+1xkj "

1)Localisation de la racine: On af(1) =7,f(2) = 16et :f0(x) = 3x2+ 4x+ 10>0pour tout

0=2+32

1=x0= 1;5

7=1;375+1;36718752

Remarque :

Doncn= 7etx7est l"approximation cherchée.

Test basé sur le résidu : 8 itérations

0=1f(2)2f(1)f(2)f(1)= 1;304347826

1=b0= 2

REMARQUES:

Nous ne pouvons pas utiliser la majorationenba2

0= 1,b0= 2,x0= 1:5,f(x0)<0,f(a0)f(x0)>0, donca1=x0= 1;5etb1=b0= 2et ainsi

11,51,752-++

21,51,6251,75--+

31,6251,68751,75-++

41,6251,656251,6875-++

0donnée

0 =f0(xk)(xk+1xk) +f(xk) =xk+1f0(xk)xkf0(xk) +f(xk))xk+1=xkf(xk)f

1)fest de classeC2sur[a;b]

2)f(a)f(b)<0

3)f0(x)6= 0sur[a;b]

4)f00(x)6= 0sur[a;b]

5)f(x0)f00(x)>0sur[a;b](f(x0)est de même signe quef00(x)sur l"intervalle)

REMARQUES:

1) Sif(x0)f00(x)<0on calculex1et sif(x1)f00(x)>0etx12[a;b]nous avons aussi la conver-

0(xn)x

Ou encore (en rappelant quef(x) = 0) :

En replaçant dans(1), on obtient :

0(xn)(xxn)22

0(xn)e2n

On en déduit (on peut supposer quef0(x)>0) :

En effet, on a :