Cours de mathématiques - Exo7
Plus précisément nous allons voir trois méthodes afin de trouver des L'idée de la méthode de la sécante est très simple : pour une fonction f continue ...
Méthode de la sécante
Méthode de la sécante. • La méthode de Newton nécessite le calcul de la dérivée de la fonction f(x). • Cette dérivée peut être difficile à calculer (par.
CHAPITRE 2
4 Méthode de Newton. 10. 4.1 Racines multiples d'ordre m . . . . . . . . . . . . . . . . . . . . . . . 11. 5 Méthode de la sécante. 12. 5.1 Convergence .
Analyse Numérique
.ECKHA 2.1 Méthode de la sécante f (x) par la sécante AB et xn+1 est l'intersection de AB avec la droite (Ox) . Comme le montre le dessin xn+1 semble plus
Résolution dune équation méthodes de la sécante et de type point
La méthode de la sécante est donnée dans Formulaires et tables. Pour une fonction f définie sur un intervalle [a b] et telle que f(a)·f(b) < 0
Méthode de la sécante
Le but de la méthode de la sécante est d'approximer f1 par une corde. Insérez un dessin ici ! Soit f de classe C2 a un zéro de f et tel que f1paq ‰ 0. On pose
Analyse numérique en Python Résolution numérique déquations
Par ailleurs la méthode de la sécante ne nécessite pas d'avoir un encadrement d'une racine sous la forme de deux valeurs de x pour lesquels les signes de f (x)
1 Convergence 2 Critère darrêt
constante C est appelée facteur de convergence de la méthode. Principe de la méthode de la sécante : On part de deux valeurs x(0) et x(1) dans [a ...
Méthodes Numériques : Optimisation
La méthode de la sécante est la meilleure méthode unidimensionelle! Avec 1 appel à la fonction par itération et une convergence à l'ordre ? ? 1.618 elle est
EILCO : Analyse Numérique Chapitre 3 : Résolution Numérique des
Méthode de dichotomie. Méthode de Newton. Méthode de la sécante. Etude de la convergence. Cours d'Analyse Numérique Chapitre 3 : Résolution Numérique des
Méthode de la sécante — Wikipédia
FIGURE 5 – Méthode de la sécante Convergence: Theorem 5 1 Supposons que fest C2 dans un voisinage J=] ; + [; >0 de la racine et que f0ne s’annule pas dans ce voisinage Alors si x(0) et x(1) (choisies dans J) sont assez proche de la suite (x(n)) n 0 dé?nie par la méthode de la sécante converge vers avec un ordre p= (1 + p 5)=2
Zéros des fonctions - e Math
LA MÉTHODE DE LA SÉCANTE 5 c = (a+b)/2 if f(a)*f(c)
Chapitre 3 Résolution numérique des équations non linéaires
La méthode de dichotomie converge toujours mais la convergence est linéaire : l’erreur à chaque pas est divisée par 2 Nous allons introduire une méthode plus rapide 3 2 Méthodes itératives pour la résolution de F(x)=x Nous présentons ici la méthode des approximations successives Elle consiste à partir d’un
Qu'est-ce que la méthode de la sécante ?
En analyse numérique, la méthode de la sécante est un algorithme de recherche d'un zéro d'une fonction f . La méthode de la sécante est une méthode comparable à celle de Newton, où l'on remplace par On obtient la relation de récurrence : L'initialisation nécessite deux points x0 et x1, proches, si possible, de la solution recherchée.
Comment calculer l’équation d’une sécante?
Déterminer l’équation y = ax+ b d’une sécante à une courbe repré- sentant la fonction f. Déterminer l’équation y = ax+ b de la sécante à la courbe repré- sentant f(x) = 3x2- 6x - 2 aux points d’abscisses: 1 0 et 3.
Quelle est la différence entre la méthode de la sécante et de Muller ?
La méthode de la sécante évalue la racine de la fonction f en l'approximant par interpolation linéaire. La méthode de Muller évalue la racine par interpolation quadratique à l'aide des trois derniers points calculés. Elle converge plus rapidement que la méthode de la sécante (ordre de convergence de 1,84).
Comment calculer l'abscisse de la sécante ?
xi est l'abscisse du point d'intersection de la sécante (Mi?2Mi?1) avec l'axe des abscisses pour i ? 2. On pose x0 = ?1 et x1 = 0 (abscisses respectives de M0 et M1 ). On obtient alors la formule de récurrence suivante : xn+1 = xn ? f (xn)?f (xn?1)xn ?xn?1 f (xn) . xn ?xn?1f (xn)?f (xn?1) .
Sup"GaliléeAnnée 2018/2019
MACS1Equations non linéaires - Notes de coursSoitfune fonction continue sur un intervalle[a;b]deR. Nous cherchons2[a;b]tel que
f() = 0:En général,ne peut pas être calculé explicitement et on doit utiliser les ordinateurs pour calculer une valeur approchée de.
Les méthodes pour approcher une racinedefsont en général itératives : elles consistent à construire une suite(x(n))n0
telle que lim n!1x(n)=:1Convergence
Definition 1.1.On définit l"erreur absolue à l"étapenpar e (n)=x(n); n0: La convergence des itérations est caractérisée par :Definition 1.2.On dit qu"une suite(x(n))n0construite par une méthode numérique converge versavec un ordrep1si
9C >0 :je(n+1)j Cje(n)jp;8nn0(1)
oùn00est un entier. Dans ce cas, on dit que la méthode est d"ordrep. Sip= 1, il est nécessaire queC <1dans (1) pour que
x(n)converge vers. On dit que la convergence estlinéairesip= 1(C <1),quadratiquesip= 2, etcubiquesip= 3. La
constanteCest appelée facteur de convergence de la méthode.En général, la convergence dépend du choix de la donnée initialex(0): le plus souvent on ne sait montrer la convergence que
localement, c"est-à-dire seulement pour unx(0)"suffisamment proche" de la racine. Les méthodes qui convergent vers
pour toutx(0)2[a;b]sont ditesglobalement convergentesvers.2Critère d"arrêt
Soit(x(n))n0une suite qui converge vers un zérodef. Soittolune tolérance fixée. En général on utilise soit un critère
basé sur l"incrément, soit un critère basé sur le résidu.2.1Contrôle de l"incrément
Les itérations s"achèvent dès que :
jx(n+1)x(n)j< toloujx(n+1)x(n)jjx(n+1)j< tol;(2)selon que l"on regarde la difference absolue ou relative de deux itérés successifs. Une question fondamentale est de se demander
si les erreurs correspondantesjx(n+1)joujx(n+1)j=jjsont petites. Ce n"est pas le cas si la convergence est très
lente. Par exemple si on considère la suite obtenue par l"algorithme de point fixe (section 6),x(n+1)= (x(n)), alors, comme
() =, l"erreure(n+1)=x(n+1)vérifie e (n+1)= (x(n))() = 0((n))e(n); avec(n)2]x(n);[:On a donc x (n+1)x(n)=x(n+1)+x(n)=e(n+1)e(n)= (10((n)))e(n):Si0((n))est très proche de0(), alors
e (n)'110()(x(n+1)x(n)): Ainsi, comme on peut l"observer sur la figure 1, le critère d"arrêt sur l"incrément est optimal p ourles métho destelles que 0() = 0comme la méthode de Newton, est satisfai santsi 1<0()<0, n"est pas satisfaisant si 0()proche de 1. 1 -1-0.8-0.6-0.4-0.200.20.40.60.810 5 10 15 20 2530
35
40
45
50
1/(1-Φ′(α))FIGURE1 - Comportement de110()en fonction de0()
2.2Contrôle du résidu
Les itérations s"achèvent dès que :
jf(x(n))j< tol(3) On peut montrer (voir [3]) que siest une racine simple, alors je(n)j.1jf0()jjf(x(n))j:Ainsi,
si jf0()j '1, alorsje(n)j 'tolet le critère d"arrêt sur le résidu est satisfaisant,si jf0()j 1, le critère d"arrêt sur le résidu n"est pas adapté carje(n)jpeut être grand par rapport à la tolérancetol,
si jf0()j 1, le critère est trop restrictif carje(n)j toldans ce cas.2.3Nombre d"itérations maximal
Il est nécessaire, en plus d"un test de type (2) ou (3), d"imposer un nombre d"itérations maximal (au cas où le test portant
sur l"incrément ou le résidu ne serait pas vérifié), c"est-à-dire : n < n max(4) oùnmaxest le nombre d"itérations maximal que l"on se fixe.3Méthode de dichotomie (bissection)
Cette méthode est basée sur le théorème des valeurs intermédiaires : Soitf: [a;b]!Rune fonction continue, alorsf
prend toute les valeurs intermédiaires entref(a)etf(b). En particulier, sifest telle quef(a)f(b)<0, alors il existe2]a;b[
tel quef() = 0.Pour trouver un zéro def, la méthode de dichotomie consiste à calculer le point milieumde l"intervalle et à regarder la valeur
def(m). Selon le signe, on sait dans quel sous-intervalle[a;m]ou[m;b]se trouve le zéro. Ensuite on réitère le procédé dans
le sous-intervalle correspondant. Ce qui conduit à l"algorithme suivant : Algorithme: On posea(0)=a; b(0)=b; x(0)= (a(0)+b(0))=2. Alors pourn0: si f(a(n))f(x(n))>0on posea(n+1)=x(n),b(n+1)=b(n) si f(a(n))f(x(n))<0on posea(n+1)=a(n),b(n+1)=x(n) puis on posex(n+1)= (a(n+1)+b(n+1))=2. 2Critère d"arrêt:
Exercice 1 : Montrer qu"un test d"arrêt du type (2) est équivalent à un test d"arrêt portant sur la longueur des sous-intervalles jb(n)a(n)j tol; oùtolest une tolérance fixée. On aura alorsjx(n)j jb(n)a(n)j tol.Convergence:Exercice 2 : a) Montrer queje(n)j (ba)2
n+1; n0et en déduire que la méthode de dichotomie converge. b) Montrer qu"avec le choix du critère d"arrêt ci-dessus, si on veut avoire(n) on doit prendrenln((ba)=)ln(2)1.-1-0.8-0.6-0.4-0.200.20.40.60.810 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 x -5-4-3-2-1012345-10 -8 -6 -4 -2 0 2 4 6 8 10 xFIGURE2 - Cas où la méthode de dichotomie a des problèmesLa figure 2 montre deux cas où la méthode de dichotomie ne marche pas : lorsque la fonction a le même signe des deux
côtés du zéro, ou dans le cas d"un pôle (dans ce cas la méthode indiquerait un zéro). La lente convergence de la méthode
de dichotomie suggère de n"utiliser celle-ci que pour localiser la racine et s"en approcher. En effectuant quelques itérations
de dichotomie, on obtient une approximation dequ"on peut utiliser comme point de départ pour une méthode d"ordre
supérieur qui convergera plus vite vers la racine avec une précision donnée. Etudions deux méthodes d"ordre supérieur.
4Méthode de Newton.
Supposons quefest dérivable sur[a;b].
Principe de la méthode de Newton :On part d"une valeurx(0)2[a;b]donnée. Soitla courbe représentative def. On
construit le nouvel itéréx(1)de sorte que le point(x(1);0)soit le point d"intersection entre l"axe desxet la tangente àpas-
sant par le point(x(0);f(x(0))). On itère ce processus : Connaissantx(n); n0, on construit le nouvel itéréx(n+1)de sorte
que le point(x(n+1);0)soit le point d"intersection entre l"axe desxet la tangente àpassant par le point(x(n);f(x(n))).
(voir la figure 3). On définit ainsi la suitex(n)de la façon suivante :x(0)2[a;b]donné, x (n+1)=x(n)f(x(n))f0(x(n)); n0:Exercice 4 : Faire un dessin illustrant la méthode de Newton pour la fonction
y=xex, avecx(0)= 0:5puisx(0)= 2.Exemple 1: considérons la fonctiony=arctan(x). Le zéro de cette fonction estx= 0. En traçant la fonction on observe qu"il
existe un pointxoù l"algorithme de Newton va osciller, c"est-à-direg(x) =xoùg(x) =xf(x)f0(x). Pour résoudre cette
équation, qui se réecrit sous la forme(1 +x2)arctan(x)2x= 0, on peut utiliser par exemple la méthode de dichotomie.
On obtient (en Matlab/Octave) :
>> x=Dichotomie("g",1,2) x = 1.3917 3 fx x x0x1x2aFIGURE3 - Construction géométrique de la méthode de NewtonIl est important de noter que cette boucle où l"on oscille entrexetxa lieu théoriquement. Numériquement, on peut
sortir de cette boucle (et converger ou diverger) à cause des erreurs d"arrondi. L"algorithme va converger dans le cas oùx0
est plus petit (en valeur absolue) quex, et diverger dans l"autre cas (voir la figure 4). fx x xsaFIGURE4 - Méthode de Newton dans le cas oùf(x) = arctan(x)etx(0)=xExemple 2: considérons la fonctiony=x3. la convergence est linéaire. Ceci provient du fait que 0 est un zéro multiple, et
la méthode de Newton "perd" la convergence quadratique dans ce cas : x n+1=xnx3n3x2n=23 xn; n0:La méthode de Newton étant une méthode de point fixe, l"étude théorique de la convergence sera effectué ci-dessous.
L"utilisation de la méthode de Newton nécessite le calcul de la dérivée defen chaque point de l"itération, ce qui peut être
coûteux. C"est pourquoi on remplace souvent dans les calculs la tangente par la sécante.5Méthode de la sécante.
Principe de la méthode de la sécante :On part de deux valeursx(0)etx(1)dans[a;b]données et on trace la droite passant
par les points(x(0);f(x(0)))et(x(1);f(x(1))). Elle coupe l"axe desxenx(2). On itère ce processus : Connaissantx(n1)et
x(n); n1, on construit le nouvel itéréx(n+1)de sorte que le point(x(n+1);0)soit le point d"intersection entre l"axe desx
et la sécante passant par les points(x(n1);f(x(n1)))et(x(n);f(x(n)))(voir la figure 5). 4 On définit ainsi la suitex(n)de la façon suivante :x(0); x(1)2[a;b]donnés, x (n+1)=x(n)x(n)x(n1)f(x(n))f(x(n1))f(x(n)); n1:fx x x0x2ax1x3FIGURE5 - Méthode de la sécanteConvergence:
Theorem 5.1.Supposons quefestC2dans un voisinageJ=];+[; >0de la racine, et quef0ne s"annule pas dans
ce voisinage. Alors six(0)etx(1)(choisies dansJ) sont assez proche de, la suite(x(n))n0définie par la méthode de la sécante
converge versavec un ordrep= (1 +p5)=21:618. On dit que la convergence est superlinéaire.6Méthode de point fixe (ou des approximations successives).
Il s"agit d"un procédé plus général pour trouver les racines d"une équation non linéaire. La méthode est fondée sur le fait
que pourf: [a;b]!R, on peut toujours transformer le problèmef(x) = 0en un problème équivalent
(x) =x;où la fonction auxiliaire : [a;b]!Ra été choisie de sorte que() =quandf() = 0. Approcher les zéros defrevient
ainsi à chercher les points fixes de, ce qui se fait en utilisant l"algorithme suivant : étant donnéx(0), on pose
x (n+1)= (x(n)); n0:Le choix den"est pas unique.
Definition 6.1.Soitfune fonction continue sur[a;b]. On dit quefest lipschitzienne sur[a;b], de constante de LipschitzL0si
jf(x)f(y)j Ljxyj;8x;y2[a;b]Theorem 6.2(convergence des itérations de point fixe).On se donnex(0)et on considère la suitex(n+1)= (x(n)), pourn0.
Si1. : [a;b]![a;b]continue,
2.lipschitzienne sur[a;b], de constante de lipschitzL <1
alorsa un unique point fixedans[a;b]et la suite(x(n))converge verspour tout choix dex(0)2[a;b].Démonstration.On remarque que si(a) =aou si(b) =balors on a l"existence d"un point fixe. On suppose que(a)> aet
(b)< b. La fonctionhdéfinie parh(x) = (x)xvérifie alorsh(a)>0eth(b)<0; commehest continue, par le théorème
des valeurs intermédiaires, il existe2[a;b]tel queh() = 0, c"est-à-dire tel que() =et donc il existe un point fixe.
5Pour montrer l"unicité, on raisonne par l"absurde : on suppose que l"on a deux points fixes1et2. Alors,
j12j=j(1)(2)jcar(i) =iLj12jcarest lipschitzienne
Ljx(n)jcarest Lipschitzienne;
et par récurrence surnon en déduit que jx(n)j Lnjx(0)j;8n2N:CommeL <1on aLn!0lorsquen! 1et l"algorithme converge vers le point fixe.Lemma 6.3.Siest dérivable sur[a;b]et si sa dérivée est bornée parLsur[a;b], alorsest lipschitzienne sur[a;b], de constante
de lipschitzL.La figure 6 illustre dans quatre situations différentes, deux cas oùj0(x)j<1et où l"algorithme converge, et deux cas où
j0(x)j>1sur[a;b]et où l"algorithme diverge.1Exercice 5 : Interpréter la méthode de Newton comme un méthode de point fixe et en déduire le théorème 6.5 ci-dessous.
Theorem 6.5.Supposons quefestC2dans un voisinageJ=];+[; >0de la racine, et quef0ne s"annule pasdans ce voisinage. Alors il existe < tel que sijx(0)j< , la suite(x(n))n0définie par la méthode de Newton converge
quadratiquement vers.7Calcul de l"erreur en pratique
Le calcul numérique de l"erreur peut servir d"une part à vérifier les estimations théoriques, et d"autre part à comparer - en
vitesse de convergence- différentes méthodes pour approcher une racinedef. Ainsi, en plus du calcul d"une approximation
de, on souhaite calculerje(n)j=jx(n)j; n0. Le problème est que l"on ne connait pasen général, et même siest
connu, sa valeur risque d"être approchée sur un ordinateur (par exemple si=). Aussi on calculera en pratique un vecteur
e eede(n+ 1)ièmecomposanteen+1=jx(n)aj;0nnit, oùnitnmaxest le nombre d"itérations, et -avautsiest connu, sinon asera une valeur approchée deaussi précise que possible.Représentation de l"erreur en pratique (en Matlab/Octave): pour visualiser l"erreur on utilisera deux types de graphes :
d"une part le tracé du vecteureee(en échelle logarithmique) en fonction du nombre d"itérations, c"est-à-dire le tracé de
log10(eee)en fonction den,1nnit. Pour cela on peut utiliser la fonctionsemilogyde Matlab :
>> semilogy(e)En particulier, on utilisera cette représentation de l"erreur pour observer et comparer les vitesses de convergence des diffé-
rentes méthodes. Par exemple sieDeDeDest le vecteur erreur correspondant à l"algorithme de dichotomie, eteNeNeNcelui correspondant
à l"algorithme de Newton, on utilisera la représentation suivante : >> semilogy(e_D) >> hold on >> semilogy(e_N) >> hold offd"autre part, le tracé deen+1en fonction deen,1nnit1, de façon à trouver l"ordre de la méthode. Rappelons qu"une
méthode est d"ordrep1si9C >0 :je(n+1)j Cje(n)jp;8nn0
oùn00est un entier. En pratique on aura alors je(n+1)j Cje(n)jp;8nn0 soit encore ln(je(n+1)j)ln(C) +pln(je(n)j);8nn0Ainsi, les points(ln(je(n)j);ln(je(n+1)j))sont sur une droite de pentep, pournn0. Donc pour trouver l"ordre de la
méthode, il faut tracer cette droite et regarder sa pente. Pour cela, on introduit les vecteursyyyetxxxdéfinis par :
y n=ln(en+1)etxn=ln(en);1nnit1;et on traceyyyen fonction dexxx. Sauf éventuellement sur les premières itérations (nn0) la courbe que l"on obtient est une
droite de pentep. On peut tracer sur la même figure (en rouge) la droitey=px: >> y=log(e(2:length(e))); >> x=log(e(1:length(e)-1)); >> plot(x,y,"b",x,p *x,"r")Références
[1] J. P .Demailly .Analyse Numérique et Equations Différentielles, PUG, 1994. [2] M.J. Gander and W. Gander. Scientific Computing. An introduction using MAPLE and MATLAB, to appear. [3]A. Qua rteroni,R. Sacco and F. Saleri. Méthodes numériques pour le calcul scientifique. Programmes en MATLAB, Springer,
2000.[4] J. Rappaz and M. Picasso. Introduction à l"analyse numérique, PPUR, 1997. 7quotesdbs_dbs26.pdfusesText_32
[PDF] methode de newton pdf
[PDF] méthode de héron dm
[PDF] developpement decimal
[PDF] développement décimal d un réel
[PDF] loi de poisson exemple
[PDF] approximation dans un calcul synonyme
[PDF] approximation linéaire excel
[PDF] approximation affine d'une fonction
[PDF] approximation affine d'une fonction au voisinage de a
[PDF] approximation linéaire fonction deux variables
[PDF] formule d'approximation
[PDF] english synonyms list pdf
[PDF] paces
[PDF] extraction et séparation d'espèces chimiques exercices