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

Calcul Scientifique Cours, exercices corrigés et illustrations en Matlab et Algorithmes de résolution Etude de la convergence Résolution Méthode de dichotomie : Critère de convergence Méthode de dichotomie : Première variante

1 7 Exercices de l'humour, dans un fichier pdf `a télécharger absolument Pour améliorer l'algorithme précédent, on va se contenter dans un premier temps (par dichotomie dans la liste triée des si), et le dernier n correspond `a la taille

[PDF] Calcul Scientifique: Cours, exercices corrigés et illustrations en

(ou Octave) en regard de la ligne où elle apparaît pour la première fois Le symbole mais quand elles s'accumulent au cours d'algorithmes longs et complexes, elles La méthode de dichotomie est implémentée dans le Programme 2 1 :

[PDF] EXAMEN 1 - Corrigé

4) Nous ne répondrons à aucune question concernant ces exercices, sauf si nous 5) L'examen est noté sur 100 points et compte pour 40 de la note finale (iii) [5 pts] Pour quels vecteurs initiaux ne peut-on pas démarrer l'algorithme?

[PDF] Calcul Scientifique: Cours, exercices corrigés et - Ceremade

lisés pour implémenter les divers algorithmes présentés, ce qui permet de vérifier (ou Octave) en regard de la ligne où elle apparaît pour la première fois Le symbole La méthode de dichotomie est implémentée dans le Programme 2 1 :

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

[PDF] Exercices corrigés - u-psudfr

Les exercices suivants sont fournis à titre d'exemples et de modèles Ils sont soit simples, soit Écrivez une boucle while pour déterminer si cet entier est premier S'il ne l'est pas, la boucle Écrire l'algorithme du calcul de : m3 = m1−m2

[PDF] Cours danalyse 1 Licence 1er semestre

1 5 Exercices Un entier est premier s'il n'est divisible que par 1 et lui-même proc`ede par dichotomie, c'est-`a-dire que l'on va couper l'intervalle [a, b] en

[PDF] Introduction à lalgorithmique - Cours, examens et exercices gratuits

Ce texte est en premier lieu un support du cours d'algorithmique ou de structures Écrire le pseudo code, itératif ou récursif, de la recherche dichotomique

[PDF] Optimisation

des différentielles D'autres exemples sont dans la séance d'exercices Voir les exercices pour des exemples g3 g2 FIG 3 2 – Premières étapes de la méthode du gradient Définir un algorithme qui procède par dichotomie directe

[PDF] Analyse Numérique : SMA-SMI S4 Cours, exercices et examens

ii) Si on adopte la stratégie du pivot partiel qui consiste à mettre en première Si x(0) est le vecteur initial donné, l'algorithme de Jacobi est de la forme : La méthode de dichotomie consiste à approcher θ par encadrement, en réduisant à

Chapitre 3 : Résolution Numérique des

Equations

H. Sadok

Cours d"Analyse Numérique, Chapitre 3 : Résolution Numérique des Equations

IntroductionCas scalaire p=1Plan

1Introduction

Bibliographie

Introduction

2Cas scalairep=1Algorithmes de résolution

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 Equations IntroductionCas scalaire p=1BibliographieIntroduction

Bibliographie

Quarteroni, Alfio, Saleri, Fausto

Calcul Scientifique Cours, exercices corrigés et illustrations en Matlab et Octave

2006, XII, 319 p., Broché

ISBN: 978-88-470-0487-0S. Guerre-Delabrière et M. Postel, "Méthodes d"approximation, Equations différentielles, Applications

Scilab», Ellipses, Paris, 2004.

Cours d"Analyse Numérique, Chapitre 3 : Résolution Numérique des Equations IntroductionCas scalaire p=1BibliographieIntroduction

Position du problème

Le problème

Etant donnéf:Rp!Rp;

On cherche un vecteurx2Rnsolution def(x) =0:(1)Nous allons d"abord traiter le cas scalaire. La fin de ce chapitre

sera consacrée au cas vectoriel. Cours d"Analyse Numérique, Chapitre 3 : Résolution Numérique des Equations IntroductionCas scalaire p=1Algorithmes de résolutionEtude de la con vergence

Résolution numérique des équations

Résoudre numériquement l"équationf(x) =0, revient à chercherxtel quejf(x)j , avectrès petit. On va supposer dans la suite que la racinexest séparable, c"est à dire qu"il existe un intervalle[a;b]tel quexest la seule racine dans cet intervalle.

On rappelle le théorème des valeures intermédiaires :théorème des valeures intermédiaires

Soitfune fonction continue dans[a;b], et soit

y2[min(f(a);f(b));max(f(a);f(b))], alors il existex2[a;b]tel quef(x) =y.supposons qu"il existe un intervalle[a;b]tel quef(a)f(b)<0, donc d"apr `s le thérème des valeurs intermédiaires, il existe un point xtel quef(x) =0.Cours d"Analyse Numérique, Chapitre 3 : Résolution Numérique des Equations IntroductionCas scalaire p=1Algorithmes de résolutionEtude de la con vergence

Méthode de dichotomie

Hypothèse :xest séparable dans[a;b]. Supposons de plus quef(a)f(b)<0. On définit l"algorithme suivant :algorithme de la bissection Initialisation:a0=a;b0=bavecf(a)f(b)<0Iterations: Pourk=0;1;2;:::c k=ak+bk2 ,Sif(ak)f(ck)<0alorsak+1=aketbk+1=cksinonak+1=cketbk+1=bkfin du si fin du pour Cours d"Analyse Numérique, Chapitre 3 : Résolution Numérique des Equations IntroductionCas scalaire p=1Algorithmes de résolutionEtude de la con vergence

Méthode de dichotomie : Exemple

f(x) = (5x)ex5=0, aveca=1 etb=611.522.533.544.55-10 0 10 20 30
40

50Cours d"Analyse Numérique, Chapitre 3 : Résolution Numérique des Equations

IntroductionCas scalaire p=1Algorithmes de résolutionEtude de la con vergence Méthode de dichotomie : Critère de convergence

Il est évident que

b nan=ba2 n:Donc sijbnanj alors 2nba

Et doncnlog2ba

Si par exemplea=1,b=2 et=104, alorsn14. Ce qui

montre que 14 itérations sont suffisante pour avoir une erreur inférieure à 10 4.

Comme approximation on propose

an+bn2 . La convergence de la méthode de dichotomie est linéaire. Cette méthode nécessite une seule évaluation de fonctions par itération. Nous allons voir dans ce qui suit une variante. Cours d"Analyse Numérique, Chapitre 3 : Résolution Numérique des Equations IntroductionCas scalaire p=1Algorithmes de résolutionEtude de la con vergence

Méthode de dichotomie : Première variante

Au lieu de prendrecnégal au milieu de[an;bn], nous allons tout d"abord tracer la droite passant par les deux points(an;f(an)) et(bn;f(bn)). Le nouveau pointcnsera donc l"intersection de cette droite avec l"axe Ox.a b c f(a) f(b) Cours d"Analyse Numérique, Chapitre 3 : Résolution Numérique des Equations IntroductionCas scalaire p=1Algorithmes de résolutionEtude de la con vergence

Méthode de dichotomie : Première variante

La droite passant par les points(an;f(an))et(bn;f(bn))a pour

équation

y=f(an) + (xan)f(bn)f(an)b nan:

On en déduit donc quecnest donné par

c n=anf(bn)bnf(an)f(bn)f(an): En modifiant l"algorithme précédent on obtient : Cours d"Analyse Numérique, Chapitre 3 : Résolution Numérique des Equations IntroductionCas scalaire p=1Algorithmes de résolutionEtude de la con vergence

Méthode de Regula-Falsi

Hypothèse :xest séparable dans[a;b]. Supposons de plus quef(a)f(b)<0. On définit l"algorithme suivant :algorithme de la fausse position (Regula-Falsi) Initialisation:a0=a;b0=bavecf(a)f(b)<0Iterations: Pourk=0;1;2;:::c k=akf(bk)bkf(ak)f(bk)f(ak),Sif(ak)f(ck)<0alorsak+1=aketbk+1=cksinonak+1=cketbk+1=bkfin du si fin du pour Cours d"Analyse Numérique, Chapitre 3 : Résolution Numérique des Equations IntroductionCas scalaire p=1Algorithmes de résolutionEtude de la con vergence Interprétation de la Méthode de Regula-Falsi Le principal inconvénient de cette méthode réside dans le fait que l"on peut avoir une stagnation de l"un des des points, comme le montre le graphe suivant : Cours d"Analyse Numérique, Chapitre 3 : Résolution Numérique des Equations IntroductionCas scalaire p=1Algorithmes de résolutionEtude de la con vergence Interprétation de la Méthode de Regula-Falsi Modifiée Nous allons remédier à ce petit problème, en changeant l"ordonnée (on va le diviser par deux) du point qui cause la stagnation. Si on reprend la figure précédente on obtient maintenant : Cours d"Analyse Numérique, Chapitre 3 : Résolution Numérique des Equations IntroductionCas scalaire p=1Algorithmes de résolutionEtude de la con vergence

Méthode de dichotomie (Seconde variante) :

l"algorithmeProgramme matlab function [w,ier,N]=quest(f,a,b,xeps,feps,itermax) fa=f(a); fb=f(b); w=a; fw=fa; a0=a; b0=b; for N=1 : itermax if(abs(a-b) < xeps) ier=0; return end if ( abs(fw) <= feps) ier = 1; return end w = (fa*b-fb*a)/(fa-fb); fwp=fw; fw=f(w); Cours d"Analyse Numérique, Chapitre 3 : Résolution Numérique des Equations IntroductionCas scalaire p=1Algorithmes de résolutionEtude de la con vergence

Méthode de dichotomie (Seconde variante) :

l"algorithme (suite)Programme matlab (suite) if fa*fw > 0 a=w; fa=fw; if( fw*fwp >0 ) fb = fb/2; end else b=w; fb=fw; if( fw*fwp > 0) fa = fa/2; end end end ier = 2; Cours d"Analyse Numérique, Chapitre 3 : Résolution Numérique des Equations IntroductionCas scalaire p=1Algorithmes de résolutionEtude de la con vergence Méthode de dichotomie (Seconde variante) : Exemple f(x) = (5x)ex5=0, aveca=1 etb=611.522.533.544.55-10 0 10 20 30
40

50Cours d"Analyse Numérique, Chapitre 3 : Résolution Numérique des Equations

IntroductionCas scalaire p=1Algorithmes de résolutionEtude de la con vergence

Méthode de Newton

La méthode de Newton est basée sur le développement de Taylor. Soitxune solution de l"´quation non linéairef(x) =0. Nous savons d"après la formule des rectangles à gauche que : f(x)f(xk) =Z x x kf0(t)dt= (xxk)f0(xk) +(xxk)22 f00(k): En notant quef(x) =0 et en négligeant l"erreur de quadrature numérique on obtient la méthode de Newton: x k+1=xkf(xk)f

0(xk):Cours d"Analyse Numérique, Chapitre 3 : Résolution Numérique des Equations

IntroductionCas scalaire p=1Algorithmes de résolutionEtude de la con vergence

Programmation de la méthode de Newton

Les paramètres d"entrée sont

0: approximation initiale,": tolérance souhaitée,itemax: nombre maximal d"it´rationsAlgorithme

Etant donnés un point initialx0et une tolérance",Tant quejf(xk)j> "etkitemax,faire x k+1=xkf(xk)f

0(xk);Fait

Cours d"Analyse Numérique, Chapitre 3 : Résolution Numérique des Equations IntroductionCas scalaire p=1Algorithmes de résolutionEtude de la con vergence Interprétation géométrique de la méthode de Newton

Prenons

f(x) =arctan(x); qui a pour solution exactex=0. L"itération de Newton pour cette fonction s"écrit sous la forme suivante: x k+1=xk(1+x2k)arctan(xk):

En prenantx0=1, on obtient :-1.510.500.511.5

1 0.8 0.6 0.4 0.2 0 0.2 0.4 0.6 0.8 1 x atan(x) x 0 x 1 x 3 x

Figure :

Méthode de Ne wtonpour la f onctionarctan.

Cours d"Analyse Numérique, Chapitre 3 : Résolution Numérique des Equations IntroductionCas scalaire p=1Algorithmes de résolutionEtude de la con vergence

Méthode de Newton : Remarques

la fonctionfdoit être dérivable.x k+1peut ne pas être calculable sif0(xk) =0 ou sixkn"est

pas dans le domaine de définition def.chaque itération nécessite une évaluation defet une

évaluation def0.cette méthode est souvent appelée aussi méthode de Newton-Raphsonla méthode de Newton est une méthode de point fixe puisquexk+1peut s"écrire sous la formexk+1=g(xk)avecg(x) =xf(x)f

0(x):Cours d"Analyse Numérique, Chapitre 3 : Résolution Numérique des Equations

IntroductionCas scalaire p=1Algorithmes de résolutionEtude de la con vergence

Méthode de Newton : Exemple1

Soitaun nombre positif, pour calculera1, nous allons appliquer la méthode de Newton à la fonctionf(x) =1x a:L"itération de Newton pour cette fonction s"écrit sous la forme suivante:x k+1=2xkax2k:En prenantx02]0;1a

[, on a les propriétés suivantes :Cours d"Analyse Numérique, Chapitre 3 : Résolution Numérique des Equations

IntroductionCas scalaire p=1Algorithmes de résolutionEtude de la con vergence Méthode de Newton ( Exemple1 ) : propriétés

La suitefxkgest bien définie puisquexk2]0;1a

[fxkgest une suite croissante majorée par1a , elle est donc convergente vers 1a fxkgest une suite de point fixe avec x k+1=2xkax2k=g(xk).Notonsekl"erreur de la méthode i.e.ek=xk1a , il est facile de voir queConvergence Quadratique e k+1e

2k=a:Cours d"Analyse Numérique, Chapitre 3 : Résolution Numérique des Equations

IntroductionCas scalaire p=1Algorithmes de résolutionEtude de la con vergence

Méthode de Newton : Exemple2

SoitAun nombre positif, pour calculerpA, nous allons

appliquer la méthode de Newton à la fonctionf(x) =x2A:L"itération de Newton pour cette fonction s"écrit sous la forme

suivante:x k+1=12 x k+Ax

kEn prenantx02]pA;1[, on a les propriétés suivantes :Cours d"Analyse Numérique, Chapitre 3 : Résolution Numérique des Equations

IntroductionCas scalaire p=1Algorithmes de résolutionEtude de la con vergence Méthode de Newton ( Exemple2 ) : propriétés

La suitefxkgest bien définie puisquexk2]pA;1[fxkgest une suite décroissante minorée parpA, elle est

donc convergente.fxkgest une suite de point fixe avecxk+1=12 x k+Ax k qui converge verspA.Notonsekl"erreur de la méthode i.e.ek=xkpA, il est facile de voir queConvergence Quadratique e k+1e

2k=12xket limk!1e

k+1e 2k=12 pA Cours d"Analyse Numérique, Chapitre 3 : Résolution Numérique des Equations IntroductionCas scalaire p=1Algorithmes de résolutionEtude de la con vergence

Méthode de la sécante : introduction

Bien que la méthode de Newton est très utilisée dans la pratique, son principal inconvénient vient du fait de l"utilisation à chaque itération de la dérivée. Quand la fonctionfn"est pas définie explicitement, on n" pas toujours accés à sa dérivée. C"est pourquoi nous allons voir maintanant la méthode de la sécante qui n"utilise pas la dérivée def. L"idée de cette méthode est d"approcher la dérivdef0(xk)par une différence dévisée f

0(xk)[xk1;xk] =f(xk)f(xk1)x

kxk1:Cours d"Analyse Numérique, Chapitre 3 : Résolution Numérique des Equations IntroductionCas scalaire p=1Algorithmes de résolutionEtude de la con vergence

Méthode de la sécante

L"itération de la méthode de la sécante s"écrit donc x

k+1=xkf(xk)(xkxk1)f(xk)f(xk1):Figure :Inter prétationgéométr iquede la méthode de la sécante .

Cours d"Analyse Numérique, Chapitre 3 : Résolution Numérique des Equations IntroductionCas scalaire p=1Algorithmes de résolutionEtude de la con vergence

Méthode de la sécante : Exemple

Appliquons la méthode de la sécante et la méthode de Newton pour trouver la racine def(x) =arctan(x). Nous partons des itérésx0=1 etx1=3 pour la méthode de la sécante etx0=1 pour la méthode de Newton.012345 25
20 15 10 5 0 Plot of error with respect to iteration, f(x)=atan

Nonlinear iterations

Relative residual

Secant

NewtonCours d"Analyse Numérique, Chapitre 3 : Résolution Numérique des Equations IntroductionCas scalaire p=1Algorithmes de résolutionEtude de la con vergence

Méthode de la sécante : Exemple1

f(x) =1x a:L"itération de la sécante pour cette fonction s"écrit sous la forme suivante:x k+1=xk+xk1axkxk1:En prenantx0etx1dans]0;1a [, on a les propriétés suivantes :La suitefxkgest bien définie puisquexk2]0;1a [Notonsekl"erreur de la méthode i.e.ek=xk1a , il est facile de voir queConvergence Super-linéaire e k+1e kek1=a:Cours d"Analyse Numérique, Chapitre 3 : Résolution Numérique des Equations IntroductionCas scalaire p=1Algorithmes de résolutionEtude de la con vergence

Méthode de Newton : Exemple2

f(x) =x2A:L"itération de la sécante pour cette fonction s"écrit sous la forme suivante:x k+1=xkxk1+Ax k+xk1Notonsekl"erreur de la méthode i.e.ek=xkpA, il est facile de voir queConvergence Super-linéaire e k+1e kek1=12xket limk!1e k+1e kek1=12 pA Cours d"Analyse Numérique, Chapitre 3 : Résolution Numérique des Equations IntroductionCas scalaire p=1Algorithmes de résolutionEtude de la con vergence

Définition

Soitx2Rn,xk2Rn,k=1;2;:::. S"il existe une constante c2[0;1)et un entierk00 tels que pour toutkk0, kek+1kckekk alors la suitefxkgconverge linéairementversx. Si pour une suitefckgqui tend vers 0, kek+1kckkekk; pour toutk, alors la suitefxkgconvergesuper-linéairement versx. S"il existe des constantesp>1,c0, etk00 telles quefxkgconverge versxpour toutkk0, kek+1kckekkp; alors la suitefxkgconverge versxavecau moins un ordrep. Sip=2 oup=3, alors la convergence est dite respectivement

quadratiqueoucubique.Cours d"Analyse Numérique, Chapitre 3 : Résolution Numérique des Equations

IntroductionCas scalaire p=1Algorithmes de résolutionEtude de la con vergence Etude de la convergence de la méthode de Newton théoreme

Soitf:D !R, pour un ouvertDdans lequel

kf0(y)f0(z)kKkyzk:. Supposons qu"il existe >0 tel quejf0(x)j> pour toutx2 D. Sif(x) =0 a une solution x

2 D, alors il existe une constante >0 telle que: si

jx0xj< , alors la suitefxkggénérée par x k+1=xkf(xk)f

0(xk);k=0;1;2;:::

existe et converge versx. En outre, pourk=0;1;:::; jxk+1xj K2jxkxj2:Cours d"Analyse Numérique, Chapitre 3 : Résolution Numérique des Equations IntroductionCas scalaire p=1Algorithmes de résolutionEtude de la con vergence Etude de la convergence de la méthode de la sécante théoreme La méthode de la sécante a une convergence d"ordre r=(1+p5)2 . En d"autres termes, nous avons jxk+1xj Cjxkxjr:Cours d"Analyse Numérique, Chapitre 3 : Résolution Numérique des Equationsquotesdbs_dbs45.pdfusesText_45

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

Chapitre 3 : Résolution Numérique des

Equations

H. Sadok

IntroductionCas scalaire p=1Plan

1Introduction

Bibliographie

Introduction

2Cas scalairep=1Algorithmes de résolution

Méthode de dichotomie

Méthode de Newton

Méthode de la sécante

Etude de la convergence

Bibliographie

Quarteroni, Alfio, Saleri, Fausto

2006, XII, 319 p., Broché

Scilab», Ellipses, Paris, 2004.

Position du problème

Le problème

Etant donnéf:Rp!Rp;

Résolution numérique des équations

Soitfune fonction continue dans[a;b], et soit

Méthode de dichotomie

Méthode de dichotomie : Exemple

50Cours d"Analyse Numérique, Chapitre 3 : Résolution Numérique des Equations

Il est évident que

Et doncnlog2ba

Si par exemplea=1,b=2 et=104, alorsn14. Ce qui

Comme approximation on propose

Méthode de dichotomie : Première variante

Méthode de dichotomie : Première variante

équation

On en déduit donc quecnest donné par

Méthode de Regula-Falsi

Méthode de dichotomie (Seconde variante) :

Méthode de dichotomie (Seconde variante) :

50Cours d"Analyse Numérique, Chapitre 3 : Résolution Numérique des Equations

Méthode de Newton

0(xk):Cours d"Analyse Numérique, Chapitre 3 : Résolution Numérique des Equations

Programmation de la méthode de Newton

Les paramètres d"entrée sont

0: approximation initiale,": tolérance souhaitée,itemax: nombre maximal d"it´rationsAlgorithme

0(xk);Fait

Prenons

En prenantx0=1, on obtient :-1.510.500.511.5

Figure :

Méthode de Ne wtonpour la f onctionarctan.

Méthode de Newton : Remarques

0(x):Cours d"Analyse Numérique, Chapitre 3 : Résolution Numérique des Equations

Méthode de Newton : Exemple1

La suitefxkgest bien définie puisquexk2]0;1a

2k=a:Cours d"Analyse Numérique, Chapitre 3 : Résolution Numérique des Equations

Méthode de Newton : Exemple2

2k=12xket limk!1e

Méthode de la sécante : introduction

0(xk)[xk1;xk] =f(xk)f(xk1)x

Méthode de la sécante

Méthode de la sécante : Exemple

Nonlinear iterations

Relative residual

Secant

Méthode de la sécante : Exemple1

Méthode de Newton : Exemple2

Définition

Soitf:D !R, pour un ouvertDdans lequel

2 D, alors il existe une constante >0 telle que: si

0(xk);k=0;1;2;:::