[PDF] SMP3 : ANALYSE NUMÉRIQUE ET ALGORITHMIQUE

View - Download SMP3 : ANALYSE NUMÉRIQUE ET ALGORITHMIQUE

Previous PDF

Next PDF

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 "

3)

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 :

x

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 :

1)

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.

2)

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

3

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-++

2.

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!x nest comprise entrexnetx)n!x f

0etf00sont continues (fde classeC2) alors :f00(n)!f00(x)etf0(xn)!f0(x).

5 4. Application :1) f(x) =x33x2+ 2xsur[0;5;0;7]etx0= 0;4puisx0= 0;5 fest définie et de classeC2. D"autre part, on a :f0(x) = 3x26x+2, étudiant le signe def0(x): = 3624 = 12a=6p12 6 = 1p3 3 '0;42b=6 +p12 6 = 1 +p3 3 '1;58

Donc :

f0(x)>0; x2] 1;a[[]b;+1[; f

0(x)<0; x2]a;b[.

et on a :f00(x) = 6x6 = 6(x1)Étude de signe def00(x):f00(x)>0; x >1; f

00(x)<0; x <1.

Etude sur l"intervalle[1;0;4]:

Localisation de la racine :fcontinue et strictement croissante sur[1;0;4]donc l"équation f(x) = 0admet une seule solution dans cet intervalle.

Utilisation de la méthode de Newton :

Pourx0=0;3on af(0;3)' 0;8970<0,f00(x)<0etf0(x)>0sur l"intervalle et comme

fest de classeC2, on déduit que les conditions suffisantes de convergence sont vérifiées et la suite

(xn)définie par la méthode de Newton converge vers la solutionxet permet le calcul d"une valeur

approchée de la solution en utilisant soit le test basé sur le résidu soit le test basé sur l"incrément.

Le schéma numérique peut être écrite :(x

0valeur initiale bien choisie

x n+1=xnf(xn)f

0(xn)=xkx3k3x2k+2xk3x2k6xk+2=2x3k3x2k3x2k6xk+2

Un exemple des calculs est donné dans le tableau suivant :Pourx0= 0;3on af(0;3)'0;3570>0de signe contraire à celui def00(x)sur l"intervalle, on

en déduit que trois conditions suffisantes de convergence sont vérifiées mais la quatrième n"est pas

vérifiée (f(x0)f00(x)>0sur l"intervalle). Dans ce cas, nous pouvons calculerx1et si sa valeur vérifiée la condition on la considère comme valeur initiale pour obtenir la convergence!

On a :

x

1=x0f(x0)f

0(x0)' 0;4596etf(x1)' 1;6498<0

On déduit que le schéma de Newton converge dans ce cas aussi. Les calculs des premières itéra-

tions sont dans le tableau suivant : 6

Etude sur l"intervalle[0;45;1;2]:

L"application de la méthode de Newton avec les trois valeurs initiales donne la situation suivante :Malgré que les valeurs prises parx0sont très proches (0,5 puis 0,54 et 0,555), on constate que les

suites définies par la méthode de Newton semblent converger vers des valeurs différentes (2 puis

0 et 1). Cet exemple montre l"instabilité de la méthode de Newton dans certains cas et la nécessité

de vérifier les conditions de convergence avant de pouvoir l"utiliser. Ici, les conditions ne sont pas

vérifiées carf00change de signe dans l"intervalle et admet un point d"inflection au point d"abscisse

1. Notons que nous pouvons résoudre directement l"équationf(x) = 0et elle admet trois racines

0, 1 et 2. En effet :

f(x) = 0)x(x1)(x2) = 0)x= 0; x= 1; x= 2 Exercice 4 :On veut calculer le zéro de la fonctionf(x) = 3x2dans l"intervalle[1;2]: 1.

Déterminer la suite des premiers 3itérés de la méthode de dichotomie dans l"intervalle[1;2]. On

pourra utiliser le tableau ci-dessous :Combien de pas (ou d"étapes) de dichotomie doit-on effectuer pour améliorer d"un ordre de gran-

deur la précision de l"approximation de la racine? Si la premiere precision"est obtenue après

jitérations et on cherche à ajouterkitérations pour améliorer la precision d"un rang (obtenir la

précision"0="10 ou passage de10nà10(n+1)) alors : jxj+kxj jxjxj2 k"10

Commejxjxj ", il suffit de prendre

1

2k110)kln(10)ln(2)'3;32

7 et par conséquent, il faut ajouter au moins4itérations. 2.

On applique la méthode de Lagrange : Écrire l"algorithme et l"utiliser pour remplir le tableau (on

s"arrêtera au plus petitkqui vérifiejf(xk)j<104):Les pointsa0etb0sont donnés. On pourra

utiliser le tableau ci-dessous :En utilisant le test précisé dans la question, nous obtenons la valeur approchée1;73203.

3.

On applique la méthode de Ne wton: Écrire l"algorithme et l"utilise rpour remplir le tableau (on

s"arrêtera au plus petitkqui vérifiejf(xk)j<104):Le point de départx0= 1;8est donné. On pourra utiliser le tableau ci-dessous :

On a :

f(x) = 3x2f0(x) =2x <0sur[1;2]f00(x) =2<0etf(x0) =f(1;8)' 0;24 Les conditions de convergence sont vérifiées

La méthode :x0donnée

Tant que quejf(xk)j>104!faire#(une boucle de calcul à refaire tant que la condition est vérifiée) : x k+1=xk3x2k2xk=x2k32xk=xk2

32xkEn utilisant le test précisé dans la question, nous obtenons la valeur approchée1;73205après deux

itérations Exercice 5 :Soit(E)l"équation suivante :(E)ex24x2= 0 1. Utiliser la représentation graphique, ci-jointe, de la fonction f(x) =ex24x2pour localiser les quatres racines de(E)dans quatre intervalles d"amplitude 1 chacun et qui contient une seule racine; 8 La lecture graphique permet de localiser les racines (changement de la position de la courbe par rapport à l"axe des abscisses) dans les intervalles :[2;1],[1;0],[0;1]et[1;2]. 2. Montrer qu"il y a une seule racine xde(E)dans[0;1]; On a : f(0) = 1etf(1) =e4<0doncf(0)f(1)<0 fest continue (fonction exponentielle et polynôme sont continues)fest strictement croissante : f

0(x) = 2xex28x= 2x(ex24)<0car0< x <1et la fonction exponentielle est croissante

impliquent :0< x2<1)1< ex2< e <4.

On en déduit, avec le théorème des valeurs intermédiaires, que l"équationf(x) = 0admet une

seule solution dans[0;1] 3. T ransformerl"équation(E)enproblèmesderecherchedepointsfixes,souslesformessuivantes: (PF1) :g1(x) =xtel queg1est une fonction définie par une racine carrée et la fonction excep- tionnelle, f(x) = 0)ex24x2= 0)x2=ex24 )x=pe x22 et comme la racine recherchée est positive, nous choisissons : x=pe x22 =g1(x) (PF2) :g2(x) =xtel queg2est une fonction définie par la fonction exponentielle et un polynôme de degré 2, f(x) = 0)f(x)+x=x)ex24x2+x=x)g2(x) =ex24x2+x=x(PF3) :g3(x) =x tel queg3une autre fonction à déterminer; f(x) = 0)ex24x2= 0)ex2= 4x2)x2= ln(4x2))x=g3(x) =pln(4x2)pour x > 12 4. Écrire les schémas numériques pour calculer xen utilisant(PF1)puis(PF2). Exécuter les calculs des quatres premières itérations de chacun des deux schémas; (PF1)(x

0donnée

x k+1=g1(xk) =pe x2k2 (PF2)x0donnée x k+1=g2(xk) =ex2k4x2k+xk 9 5.

Étudier la con vergencedes deux schémas relatifs à (PF1)et à(PF2). Évaluer l"erreur commise

lorsque le schéma converge; Conditions suffisantes de convergence d"un schéma point fixe de fonctiongdéfinie sur[a;b]: gest contractante; g([a;b])[a;b]

On ag1(x) =pe

x22 et

0x1)0x21)1ex2e)12

g1(x)pe 2 '0;82

Donc :

g

1([0;1])[0;1]

Noter qu"il faut montrer que0f(x)1pour toutx2[0;1]et il ne suffit pas de montrer que f(0)>0etf(1)<1.

D"autre part :g01(x) =xex22

pe x2=xpe x22 et

0x1)1ex2e)12

pe x22 pe 2 )0g01(x)pe 2 '0;82

On en déduit que :

jg01(c)j sup x2[0;1]jg01(x)j pe 2 En utilisant le théorème des accroissements finies pourxetydans[0;1], il existec2]0;1[telle que : jg1(x)ga(y)j=jg01(c)jjxyj pe 2 jxyj etg1estpe 2 contractante.

On déduit que la méthode de point fixe converge vers la solutionxde l"équation telle queg1(x) =x

Concernant le méthode point fixe avecg2(x) =ex24x2+xon ag2(0;3)'1;03>1(ou g

2(1) =e3<0) doncg2([0;1])n"est pas incluse dans[0;1], les conditions suffisantes de

convergence ne sont pas vérifiées et ne pouvons rien déduire dans ce cas. 6.

Écrire la méthode de Ne wtonpour déter minerla racine xde(E). Quel est son ordre? Quel est le

meilleur choix parmi les deux méthodes? Justifier la réponse. Utilisant la méthode de Newton pour trouver une solution approchée de l"equationf(x) =ex2

4x2= 0dans l"intervalle[0;1](une seule racine telle que localiser dans une question précédente).

La méthode de Newton définie une suite(xn)ntelle que :8< :x

0bien choisie

x k+1=xkf(xk)f

0(xk)=xkex2k4x2k2xkex2k8xk=xkex2k4x2k2xk(ex2k4)

On af0(x) = 2x(ex24)<0sur]0;1]donc la méthode de Newton est d"ordre deux tandis que

la méthode de point fixe est d"ordre un. La méthode de Newton, lorsqu"elle vérifiée les conditions

de convergence, est le meilleur choix pour cet exemple. 10

Exercice 6 :SoientX= 211etY= 81.

quotesdbs_dbs13.pdfusesText_19

[PDF] méthode de dichotomie pdf

[PDF] méthode de dichotomie python

[PDF] Methode de dissertation

[PDF] Méthode de dissertation HELP

[PDF] Méthode de factorisation

[PDF] methode de factorisation d'un polynome

[PDF] methode de gauss (systeme lineaire)

[PDF] méthode de gauss jordan exercices corrigés

[PDF] méthode de gauss matrice

[PDF] méthode de gauss matrice pdf

[PDF] methode de gauss resolution systeme

[PDF] méthode de gestion du temps pdf

[PDF] methode de horner

[PDF] methode de l'anthropologie

[PDF] méthode de la sécante exercice corrigé