[PDF] 1 Convergence 2 Critère darrêt PDF NonLinEqs.pdf

Par exemple si on considère la suite obtenue par l'algorithme de point fixe ( section Principe de la méthode de la sécante : On part de deux valeurs x(0) et x(1)

Si, par exemple, on souhaite obtenir une approximation de l à 10−N près, comme on L'idée de la méthode de la sécante est très simple : pour une fonction f

[PDF] Résolution dune équation, méthodes de la sécante et de type point

La méthode de la sécante consiste à enchaîner des pas consécutifs à partir d'un intervalle de démarrage (dans l'exemple, on effectue 5 pas en partant de

[PDF] Méthode de la sécante - Angelfire

La méthode de Newton nécessite le calcul de la dérivée de la et on obtient la méthode de la sécante n n n n n f x f x Exemple: (choix de g) Résoudre x3

[PDF] Analyse Numérique

20 0, 615468502 Cet exemple confirme les remarques générales La méthode de Newton est la plus rapide Ici, la méthode de la sécante l'est presque autant

[PDF] CHAPITRE 2 - Cours

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] Intervalle initial : [a,b] = [1, 2]

[PDF] EILCO : Analyse Numérique Chapitre 3 : Résolution - LMPA

Méthode de Newton Méthode de la sécante Méthode de dichotomie : Exemple f(x)=(5 − x)ex Si par exemple a = 1, b = 2 et ϵ = 10−4, alors n ≥ 14 Ce qui

[PDF] 1 Convergence 2 Critère darrêt

Par exemple si on considère la suite obtenue par l'algorithme de point fixe ( section Principe de la méthode de la sécante : On part de deux valeurs x(0) et x(1)

[PDF] Ift 2421 Chapitre 2 Résolution déquations non linéaires

Méthode de la sécante Exemple : fonction considérée: -3 + x (-3 + x (1 + x)) ou - 3 - 3 x + x 2 + x 3 Estimations initiales: x1 = 1 x2 = 2 Tolérance sur x:0 0005

[PDF] Résolution déquations non linéaires 1 Méthode de dichotomie

On peut poser par exemple g(x) = x + f(x), mais on prendra La méthode de la sécante consiste `a construire une suite (xn) qui converge vers α de la mani`ere

[PDF] 3 Méthodes de résolution de léquation f(x)=0 - LMPT

En effet, l'ordre pourrait être intermédiaire entre 1 et 2 (cf plus loin la méthode de la sécante par exemple) 3 4 Méthode de Newton Afin de s'assurer

Sup"GaliléeAnnée 2018/2019

MACS1

Equations 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

(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 25
30
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. 2

Critè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èmes

La 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))f

0(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)f

0(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 Newton

Il 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)=x

Exemple 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

(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écante

Convergence:

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.

1. : [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.

Pour montrer l"unicité, on raisonne par l"absurde : on suppose que l"on a deux points fixes1et2. Alors,

j12j=j(1)(2)jcar(i) =i

Lj12jcarest lipschitzienne

La convergence de l"algorithme provient de jx(n+1)j=j()(x(n))jcar() =etx(n+1)= (x(n))

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.10<=g"(x)<1FIGURE6 - Iterations de point fixe dans quatre situations différentes La convergence est en général linéaire, du fait que l"erreure(n)=jx(n)jvérifie e (n+1)Le(n): Propriété 6.4.Si2 Cp+1(J)pour un certain voisinageJdeet un entierp0, et si(i)() = 0pour0ipet (p+1)()6= 0, alors la méthode de point fixe est d"ordrep+ 1et lim n!1x (n+1)(x(n))p+1=(p+1)()(p+ 1)!; p0 6

Exercice 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 pas

dans 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

log

10(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 off

d"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"ordrep1si

9C >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);8nn0

Ainsi, 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_dbs47.pdfusesText_47

[PDF] [PDF] 1 Convergence 2 Critère darrêt

Sup"GaliléeAnnée 2018/2019

1Convergence

9C >0 :je(n+1)j Cje(n)jp;8nn0(1)

2Critère d"arrêt

2.1Contrôle de l"incrément

Les itérations s"achèvent dès que :

Si0((n))est très proche de0(), alors

1/(1-Φ′(α))FIGURE1 - Comportement de110()en fonction de0()

2.2Contrôle du résidu

Les itérations s"achèvent dès que :

Ainsi,

2.3Nombre d"itérations maximal

3Méthode de dichotomie (bissection)

Critère d"arrêt:

Exercice 2 : a) Montrer queje(n)j (ba)2

4Méthode de Newton.

Supposons quefest dérivable sur[a;b].

0(x(n)); n0:Exercice 4 : Faire un dessin illustrant la méthode de Newton pour la fonction

0(x). Pour résoudre cette

On obtient (en Matlab/Octave) :

5Méthode de la sécante.

Convergence:

6Méthode de point fixe (ou des approximations successives).

Le choix den"est pas unique.

1. : [a;b]![a;b]continue,

2.lipschitzienne sur[a;b], de constante de lipschitzL <1

Lj12jcarest lipschitzienne

Ljx(n)jcarest Lipschitzienne;

7Calcul de l"erreur en pratique

10(eee)en fonction den,1nnit. Pour cela on peut utiliser la fonctionsemilogyde Matlab :

9C >0 :je(n+1)j Cje(n)jp;8nn0

Références