Université Hassan 1er Année universitaire 2022 - 2023 Faculté des Sciences et T

Université Hassan 1er Année universitaire 2022 - 2023 Faculté des Sciences et Techniques Parcours GE-GM Département de Mathématiques et Informatique Analyse Numérique – Chapitre 1: Résolution numérique des équations et systèmes non linéaires – 1 Résolution numérique des équations 1.1 Position du problème Soit f : R − →R une fonction donnée. On désire trouver une ou plusieurs solutions de l’équation f(x) = 0. L’application f est en outre supposée continue et dérivable autant de fois qu’il est nécéssaire sur l’intervalle où sont recherchées les racines réelles de l’équation f(x) = 0. 1.2 Séparation des racines Définition 1 Une racine s est dite séparée dans un intervalle si cet intervalle contient uniquement cette racine s. Figure 1: Exemple de séparation dans [a, b] des racines d’une fonction Pour procéder à la séparation des racines, il existe essentiellement deux types de méthodes : les méthodes graphiques et les méthodes algébriques. • Méthode graphique : Nous pouvons localiser assez sommairement les racines de l’équation f(x) = 0 en considérant le graphe de y = f(x). exemple: Figure 1 • Méthode algébrique : La condition f(a) · f(b) < 0 implique que l’équation f(x) = 0 a au moins une racine dans ]a, b[ (théorème des valeurs intermédiaires), cette racine étant unique si f ′(x) ̸= 0 dans [a, b]. Nous pouvons utiliser l’algorithme suivant qui permet une séparation plus précise (localisation). 1.3 Algorithme de Dichotomie Considérons l’équation f(x) = 0 où la fonction est telle que : f(a) · f(b) < 0 et f ′(x) ̸= 0 dans [a, b] ce qui assure l’existence d’une racine unique dans l’intervalle ]a, b[. Désignons par x0 le milieu du segment [a, b], x0 = a + b 2 . Alors : • ou bien f (x0) = 0 et x0 est racine de l’équation; • ou bien f (x0) ̸= 0. Dans ce dernier cas, la racine est dans l’un des intervalles [a, x0] et [x0, b]. Pour savoir dans lequel des deux, formons les produits f(a) · f (x0) et f (x0) · f(b); l’un de ces produits est négatif, par exemple le premier. La racine se trouve donc séparéee dans l’intervalle [a, x0], moitié de l’intervalle initial [a, b]. L’intervalle [a, x0] est maintenant designé par [a1, b1]. Divisons à nouveau le segment [a1, b1] en deux et reprenons le raisonnement précédent. En poursuivant ainsi la dichotomie, nous obtenons ainsi, soit une racine exacte, soit une suite infinie de segments emboités [a1, b1] , [a2, b2] , · · · , [an, bn] , · · · tels que        f (an) · f (bn) < 0 bn −an = b −a 2n (1) Notons que : • Les extrémités a1, a2, · · · , an, · · · forment une suite croissante majorée par b. • Les extrémités b1, b2, . . . . . . .., bn, . . .. forment une suite décroissante minorée par a. Les deux suites sont dons adjacentes. Elles ont donc une limite commune : s = lim n− →∞an = lim n− →∞bn En passant à la limite dans l’inégalité (1), la continuité de la fonction f entraine  f(s)2 ≤0. Il s’ensuit que s est une racine de l’équation f(x) = 0 et de plus s −an ≤b −a 2n La méthode de dichotomie consiste à construire une suite (xn) qui converge vers α de la manière suivante : • Initialisation : on prend pour x0 le milieu de [a, b]. La racine se trouve alors dans l’un des deux intervalles ]a, x0[ ou ]x0, b[ ou bien elle est égale à x0. • si f(a)f (x0) < 0, alors s ∈] a, x0[. On pose a1 = a, b1 = x0. • si f(a)f (x0) = 0, alors α = x0. • si f(a)f (x0) > 0, alors α ∈] x0, b[. On pose a1 = x0, b1 = b. • On prend alors pour x1 le milieu de [a1, b1]. On construit ainsi une suite x0 = (a + b)/2, x1 = (a1 + b1) /2, . . . xn = (an + bn) /2 telle que |s −xn| ≤(b −a)/2n Pour que |x −xn| ≤ε il suffit de prendre : b −a 2n ≤ε soit n ≥ log b −a ε ! log 2 Etant donné une précision ε, cette méthode permet d’approcher s en un nombre prévisible d’itérations. Exemple 1 f(x) = x2 −1 [a, b] = [0, 3] 1.4 La méthode des approximations successives Dans ce paragraphe, l’équation f(x) = 0 est supposée mise sous la forme x −F(x) = 0. Ceci peut toujours se faire en posant F(x) = x + f(x), mais quelque fois aussi de plusieurs autres manières : par exemple, l’équation x3−x−1 = 0 peut s’écrire x = x3−1 ou x = 1 x2 −1 , ou x = (x + 1) 1 3. Théorème du point fixe : Soit F une fonction définie sur un intervalle I = [a, b] fermé borné telle que i) F est continue sur I. ii) ∀x ∈I, F(x) ∈I. Alors, il existe s ∈I tel que s = F(s)s est dit point fixe de F. Démontration 1 Soit g la fonction définie sur [a, b] par g(x) = x −F(x). • g est continue sur [a, b]. • g(a) = a −F(a) ≤0 car F(a) ∈[a, b]. • g(b) = b −F(b) ≥0 car F(b) ∈[a, b]. Donc g(a) · g(b) ≤0. Alors, il existe un s ∈[a, b] tq g(s) = 0, c’est à dire s = F(s). Définition 2 On dit que F est L-lipschitziènne sur I s’il existe une constante L ≥0 telle que ∀x1, x2 ∈I, |F (x1) −F (x2)| ≤L |x1 −x2| . Théorème 1 Si F est L-lipschitziènne avec 0 ≤L < 1 sur l’intervalle I, alors F admet au plus un point fixe dans I. Démontration 2 Supposons s1 et s2 deux points fixes, alors : |s1 −s2| = |F (s1) −F (s2)| ≤L |s1 −s2| avec L < 1 d’où |s1 −s2| (1 −L) ≤0 comme L < 1, on obtient donc s1 = s2 Proposition 1 Si F est dérivable sur I et si |F ′(x)| ≤L ∀x ∈I, alors F est L- lipschitziènne sur I. Démontration 3 Utilisons la formule des accroissements finis : F(x)−F(y) = F ′(ξ)(x− y) avec ξ ∈] x, y[ |F(x) −F(y)| = |F ′(ξ)| |x −y| ≤L|x −y| 1.5 L’algorithme des approximations successives : La méthode des approximations successives consiste à construire la suite (xn) définie de la façon suivante :    x0 ∈I, arbitraire xn = F (xn−1) n ≥1 (2) La méthode des approximations successives s’interprète géomètriquement très simplement par Théorème 2 Soit I un intervalle fermé et soit F une fonction définie sur I telle que : Figure 2: Interpretation géomètrique de la méthode des approximations successives i) ∀x ∈I, F(x) ∈I. ii) F est L-lipschitziènne sur I avec 0 < L < 1. Alors F a un unique point fixe s et toute suite (xn) définie par x0 ∈I, xn = F (xn−1) converge vers s. De plus:        |xn −s| ≤ Ln 1 −L |x1 −x0| |xn −s| ≤Ln |x0 −s| (3) Démontration 4 Montrons que la suite (xn) converge. On a |xn+1 −xn| = |F (xn) −F (xn−1)| ≤L |xn −xn−1| donc |xn+1 −xn| ≤Ln |x1 −x0| or |xn+p −xn| = |(xn+p −xn+p−1) + (xn+p−1 −xn+p−2) + · · · + (xn+1 −xn)| ≤|xn+p −xn+p−1| + |xn+p−1 −xn+p−2| + · · · + |xn+1 −xn| donc |xn+p −xn| ≤|x1 −x0|  Ln+p−1 + Ln+p−2 + · · · + Ln Ce qui implique |xn+p −xn| ≤Ln |x1 −x0| 1 −Lp 1 −L ≤|x1 −x0| Ln 1 −L or limn→∞Ln = 0, donc lim n→∞|xn+p −xn| = 0 ∀p ∈N. Cette suite vérifie le critère de Cauchy, donc converge vers une limite s, et comme F est une fonction continue, car L-lipschitziènne, cette limite vérifie F(s) = s. Ceci prouve l’existence d’un point fixe s; l’unicité d’un point fixe de F a déjà été annoncé dans le théorème 2. En faisant tendre p vers l’infini dans l’inégalité |xn+p −xn| ≤|x1 −x0| Ln 1−L, on obtient la première majoration de (3). La seconde découle de |xn −s| = |F (xn−1) −F(s)| ≤L |xn−1 −s| (n ≥1). Algorithme du point fixe But : trouver une solution de g(x) = x. Entrées : une approximation initiale s0. ε (la précision désirée). N0 (le nombre maximal d’itérations). Sortie : la valeur approchée de α ou un message d’échec. Etape 1 : Poser N = 1 Etape 2 : Tant que N ≤N0 Faire les étapes 3 à 6. Etape 3 : Poser s = g (s0). Etape 4 : Si |s −s0| ≤ε Alors imprimer α, aller à l’étape 8. Etape 5 : Poser N = N + 1. Etape 6 : Poser s0 = s. Etape 7 : Imprimer la méthode a échoué après N0 uploads/Geographie/ chapitre-1-1-analyse-numerique.pdf

Tags
Administrationetape méthode suite alors racine
Documents similaires
  • 14
  • 0
  • 0
Afficher les détails des licences
Licence et utilisation
Gratuit pour un usage personnel Attribution requise
Partager