Introduction Cas scalaire p = 1 EILCO : Analyse Numérique Chapitre 3 : Résoluti

Introduction Cas scalaire p = 1 EILCO : Analyse Numérique Chapitre 3 : Résolution Numérique des Equations H. Sadok Cours d’Analyse Numérique, Chapitre 3 : Résolution Numérique Introduction Cas scalaire p = 1 Plan 1 Introduction Bibliographie Introduction 2 Cas scalaire p = 1 Algorithmes 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 Introduction Cas scalaire p = 1 Bibliographie Introduction 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-0 S. 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 Introduction Cas scalaire p = 1 Bibliographie Introduction Position du problème Le problème Etant donné f : Rp →Rp, On cherche un vecteur x ∈Rn solution de f(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 Introduction Cas scalaire p = 1 Algorithmes de résolution Etude de la convergence Résolution numérique des équations Résoudre numériquement l’équation f(x) = 0, revient à chercher x∗tel que |f(x∗)| ≤ϵ, avec ϵ très petit. On va supposer dans la suite que la racine x∗est séparable, c’est à dire qu’il existe un intervalle [a, b] tel que x∗est la seule racine dans cet intervalle. On rappelle le théorème des valeures intermédiaires : théorème des valeures intermédiaires Soit f une fonction continue dans [a, b], et soit y ∈[min(f(a), f(b)), max(f(a), f(b))], alors il existe x ∈[a, b] tel que f(x) = y. supposons qu’il existe un intervalle [a, b] tel que f(a)f(b) < 0, donc d’apr` s le thérème des valeurs intermédiaires, il existe un point ¯ x tel que f(¯ x) = 0. Cours d’Analyse Numérique, Chapitre 3 : Résolution Numérique Introduction Cas scalaire p = 1 Algorithmes de résolution Etude de la convergence Méthode de dichotomie Hypothèse : x∗est séparable dans [a, b]. Supposons de plus que f(a)f(b) < 0. On définit l’algorithme suivant : algorithme de la bissection Initialisation: a0 = a, b0 = b avec f(a)f(b) < 0 Iterations: Pour k = 0, 1, 2, . . . ck = ak+bk 2 , Si f(ak)f(ck) < 0 alors ak+1 = ak et bk+1 = ck sinon ak+1 = ck et bk+1 = bk fin du si fin du pour Cours d’Analyse Numérique, Chapitre 3 : Résolution Numérique Introduction Cas scalaire p = 1 Algorithmes de résolution Etude de la convergence Méthode de dichotomie : Exemple f(x) = (5 −x)ex −5 = 0, avec a = 1 et b = 6 1 1.5 2 2.5 3 3.5 4 4.5 5 −10 0 10 20 30 40 50 Cours d’Analyse Numérique, Chapitre 3 : Résolution Numérique Introduction Cas scalaire p = 1 Algorithmes de résolution Etude de la convergence Méthode de dichotomie : Critère de convergence Il est évident que bn −an = b −a 2n . Donc si |bn −an| ≤ϵ alors 2n ≥b−a ϵ . Et donc n ≥log2 b−a ϵ  . Si par exemple a = 1, b = 2 et ϵ = 10−4, alors n ≥14. Ce qui montre que 14 itérations sont suffisante pour avoir une erreur inférieure à 10−4. Comme approximation on propose an+bn 2 . 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 Introduction Cas scalaire p = 1 Algorithmes de résolution Etude de la convergence Méthode de dichotomie : Première variante Au lieu de prendre cn é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 point cn sera 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 Introduction Cas scalaire p = 1 Algorithmes de résolution Etude de la convergence 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) + (x −an)f(bn) −f(an) bn −an . On en déduit donc que cn est donné par cn = 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 Introduction Cas scalaire p = 1 Algorithmes de résolution Etude de la convergence Méthode de Regula-Falsi Hypothèse : x∗est séparable dans [a, b]. Supposons de plus que f(a)f(b) < 0. On définit l’algorithme suivant : algorithme de la fausse position (Regula-Falsi) Initialisation: a0 = a, b0 = b avec f(a)f(b) < 0 Iterations: Pour k = 0, 1, 2, . . . ck = akf(bk)−bkf(ak) f(bk)−f(ak) , Si f(ak)f(ck) < 0 alors ak+1 = ak et bk+1 = ck sinon ak+1 = ck et bk+1 = bk fin du si fin du pour Cours d’Analyse Numérique, Chapitre 3 : Résolution Numérique Introduction Cas scalaire p = 1 Algorithmes de résolution Etude de la convergence 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 Introduction Cas scalaire p = 1 Algorithmes de résolution Etude de la convergence 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 Introduction Cas scalaire p = 1 Algorithmes de résolution Etude de la convergence Méthode de dichotomie (Seconde variante) : l’algorithme Programme 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 Introduction Cas scalaire p = 1 Algorithmes de résolution Etude de la convergence 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 Introduction Cas scalaire p = 1 Algorithmes de résolution Etude de la convergence Méthode de dichotomie (Seconde variante) : Exemple f(x) = (5 −x)ex −5 = 0, avec a = 1 et b = 6 1 1.5 2 2.5 3 3.5 4 4.5 5 −10 0 10 20 30 40 50 Cours d’Analyse Numérique, Chapitre 3 : Résolution Numérique Introduction Cas scalaire p = 1 Algorithmes de résolution Etude de la convergence Méthode de Newton La méthode de Newton est basée sur le développement de Taylor. Soit x∗une solution de l’´ quation non linéaire f(x) = 0. Nous savons d’après la formule des rectangles à gauche que : f(x∗)−f(xk) = Z x∗ xk f ′(t)dt = (x∗−xk) f ′(xk) + (x∗−xk)2 2 f ′′(ηk). En notant que f(x∗) = 0 et en négligeant l’erreur de quadrature numérique on obtient la méthode de Newton: xk+1 = xk −f(xk) f ′(xk). Cours d’Analyse Numérique, Chapitre 3 : Résolution Numérique Introduction Cas scalaire p = 1 Algorithmes de résolution Etude de la convergence Programmation de la méthode de Newton Les paramètres d’entrée sont x0 : approximation initiale, ε : tolérance souhaitée, itemax : nombre maximal d’it´ rations Algorithme Etant donnés un point initial x0 et une tolérance ε, Tant que |f(xk)| > ε et k ≤itemax , faire xk+1 = xk −f(xk) f ′(xk), Fait Cours d’Analyse Numérique, Chapitre 3 : Résolution Numérique Introduction Cas scalaire p = 1 Algorithmes de résolution Etude de la convergence Interprétation géométrique de la méthode de Newton Prenons f(x) = arctan(x), qui a pour solution exacte x∗= 0. L ’itération de Newton pour cette fonction s’écrit sous la forme suivante: xk+1 = xk −(1 + x2 k ) arctan(xk). En prenant x0 = 1, on obtient : −1.5 −1 −0.5 0 0.5 1 1.5 −1 −0.8 −0.6 −0.4 −0.2 0 0.2 0.4 0.6 0.8 1 x atan(x) x0 x1 x3 x* Cours d’Analyse Numérique, Chapitre 3 : Résolution Numérique Introduction Cas scalaire p = 1 Algorithmes de résolution Etude de la convergence Méthode de Newton : Remarques la fonction f doit être dérivable. xk+1 peut ne pas être calculable si f ′(xk) = 0 ou si xk n’est pas dans le domaine de définition de f. chaque itération nécessite une évaluation de f et une évaluation de f ′. cette méthode est souvent appelée aussi méthode de Newton-Raphson la méthode de Newton est une méthode de point fixe puisque xk+1 peut s’écrire sous la forme xk+1 = g(xk) avec g(x) uploads/Management/ cours-3 3 .pdf

  • 21
  • 0
  • 0
Afficher les détails des licences
Licence et utilisation
Gratuit pour un usage personnel Attribution requise
Partager
  • Détails
  • Publié le Mar 30, 2022
  • Catégorie Management
  • Langue French
  • Taille du fichier 0.2336MB