Numerical methods of any function

# Numerical methods of any function ## Objectifs et prérequis Ce chapitre vise à fournir aux élèves de Upper Sixth (Pure Mathematics with Mechanics) une compréhension approfondie des méthodes numériques pour approximer les solutions des équations de la forme $f(x) = 0$, où $f$ est une fonction réelle continue. Les méthodes étudiées permettent de localiser et d’approcher numériquement les racines lorsque des solutions analytiques ne sont pas disponibles ou trop complexes à obtenir. À l’issue de ce chapitre, l’élève sera capable de : - Comprendre la nécessité et les limites des méthodes numériques en mathématiques appliquées. - Localiser une racine d’une fonction continue sur un intervalle donné en utilisant le théorème des valeurs intermédiaires. - Appliquer la méthode de dichotomie (bisection) avec rigueur pour encadrer une racine. - Mettre en œuvre la méthode de Newton–Raphson pour obtenir une convergence rapide vers une racine simple. - Évaluer la précision d’une approximation numérique, estimer l’erreur et discuter des conditions de convergence. - Appliquer ces méthodes à des problèmes concrets issus de la mécanique ou d’autres domaines scientifiques. **Prérequis** : - Maîtrise du calcul différentiel et intégral (dérivées, continuité, théorème des valeurs intermédiaires). - Notions de suites et de leur convergence. - Familiarité avec la notation fonctionnelle et la résolution d’équations algébriques de base. - Capacité à effectuer des calculs numériques avec précision (arrondi, signification des chiffres). --- ## I. Introduction to numerical methods Les méthodes numériques sont des procédés algorithmiques permettant d’approcher des solutions à des problèmes mathématiques qui ne peuvent pas être résolus exactement par des méthodes analytiques (c’est-à-dire par des formules fermées). En particulier, résoudre $f(x) = 0$ pour une fonction $f$ donnée peut s’avérer impossible lorsque $f$ est transcendante (comme $f(x) = e^x - x - 2$) ou lorsqu’elle résulte d’un modèle physique complexe. Contrairement aux méthodes analytiques qui donnent une solution exacte sous forme d’expression, les méthodes numériques produisent une suite d’approximations qui convergent vers la solution recherchée. Leur efficacité dépend de la vitesse de convergence, de la stabilité numérique et du coût computationnel. > **À retenir** : Une méthode numérique est un procédé itératif qui génère une suite $(x_n)$ telle que $\lim_{n \to \infty} x_n = x^*$, où $x^*$ est la solution exacte de $f(x) = 0$. Les méthodes étudiées ici appartiennent à la classe des méthodes de recherche de zéros (root-finding methods). Elles nécessitent généralement : - Une fonction $f$ continue sur un intervalle d’intérêt. - Des informations initiales (comme un intervalle contenant une racine ou une approximation initiale). - Un critère d’arrêt basé sur la précision désirée (par exemple, $|x_{n+1} - x_n| < \epsilon$ ou $|f(x_n)| < \epsilon$). Les erreurs en méthodes numériques proviennent de deux sources principales : - L’erreur de troncature : due à l’approximation du problème mathématique par un algorithme fini. - L’erreur d’arrondi : due à la représentation finie des nombres dans l’ordinateur (non traitée ici en détail, mais à garder à l’esprit). Dans ce chapitre, nous nous concentrons sur deux méthodes fondamentales : la dichotomie (robuste mais lente) et Newton–Raphson (rapide mais conditionnelle). --- ## II. Location of roots of functions Avant d’appliquer une méthode numérique, il est essentiel de localiser approximativement une racine, c’est-à-dire de déterminer un intervalle $[a, b]$ où l’on sait qu’une racine existe. Cela permet de garantir la convergence de certaines méthodes (comme la dichotomie) et d’éviter les échecs dus à de mauvaises valeurs initiales. Le théorème clé utilisé est le **théorème des valeurs intermédiaires** (Intermediate Value Theorem, IVT). > **À retenir** : Si $f$ est continue sur l’intervalle fermé $[a, b]$ et si $f(a)$ et $f(b)$ sont de signes opposés (c’est-à-dire $f(a) \cdot f(b) < 0$), alors il existe au moins un $c \in (a, b)$ tel que $f(c) = 0$. Ce théorème ne garantit pas l’unicité de la racine, mais assure son existence. Pour isoler une racine unique, on peut restreindre l’intervalle jusqu’à ce que la fonction soit strictement monotone dessus (ce qui implique que $f'$ ne change pas de signe). ### Exemple 1 : Localisation d’une racine de $f(x) = x^3 - x - 2$ On veut montrer qu’il existe une racine dans l’intervalle $[1, 2]$. - $f(1) = 1^3 - 1 - 2 = -2 < 0$ - $f(2) = 8 - 2 - 2 = 4 > 0$ - Puisque $f$ est un polynôme, elle est continue sur $\mathbb{R}$, donc sur $[1, 2]$. - Comme $f(1) \cdot f(2) = (-2)(4) = -8 < 0$, d’après le théorème des valeurs intermédiaires, il existe au moins un $c \in (1, 2)$ tel que $f(c) = 0$. On peut affiner : essayer $x = 1.5$ : $f(1.5) = (1.5)^3 - 1.5 - 2 = 3.375 - 3.5 = -0.125 < 0$ Donc $f(1.5) < 0$ et $f(2) > 0$ → racine dans $[1.5, 2]$. Essayer $x = 1.75$ : $f(1.75) = (1.75)^3 - 1.75 - 2 = 5.359375 - 3.75 = 1.609375 > 0$ Donc racine dans $[1.5, 1.75]$. On poursuit ainsi pour encadrer la racine avec la précision désirée. ### Exercice 1 : Localisation de racines **a)** Montrer que l’équation $f(x) = e^{-x} - x = 0$ admet une racine unique dans l’intervalle $[0, 1]$. **b)** Trouver un intervalle de longueur $0,5$ contenant une racine de $g(x) = \ln(x) + x - 2$. **Corrigé :** **a)** - $f(x) = e^{-x} - x$ est continue sur $[0, 1]$ (différentiable donc continue). - $f(0) = e^{0} - 0 = 1 > 0$ - $f(1) = e^{-1} - 1 \approx 0,3679 - 1 = -0,6321 < 0$ - Donc $f(0) \cdot f(1) < 0$ → par IVT, il existe au moins un $c \in (0, 1)$ tel que $f(c) = 0$. - Pour l’unicité : $f'(x) = -e^{-x} - 1 < 0$ pour tout $x \in \mathbb{R}$ → $f$ est strictement décroissante → au plus une racine. - Donc une racine unique dans $(0, 1)$. **b)** - $g(x) = \ln(x) + x - 2$ est définie et continue sur $(0, +\infty)$. - Essayer $x = 1$ : $g(1) = \ln(1) + 1 - 2 = 0 + 1 - 2 = -1 < 0$ - Essayer $x = 2$ : $g(2) = \ln(2) + 2 - 2 \approx 0,693 > 0$ - Donc $g(1) < 0$, $g(2) > 0$ → racine dans $[1, 2]$. - Pour un intervalle de longueur $0,5$ : essayer $x = 1,5$ $g(1,5) = \ln(1,5) + 1,5 - 2 \approx 0,4055 - 0,5 = -0,0945 < 0$ Donc $g(1,5) < 0$, $g(2) > 0$ → racine dans $[1,5, 2]$ (longueur $0,5$). On peut aussi prendre $[1, 1,5]$ si on veut, mais $g(1) < 0$, $g(1,5) < 0$ → pas de changement de signe. Donc l’intervalle de longueur $0,5$ contenant une racine est $[1,5, 2]$. --- ## III. Bisection method La méthode de dichotomie (ou bisection) est une méthode numérique robuste pour approcher une racine de $f(x) = 0$ lorsque l’on connaît un intervalle $[a, b]$ où $f$ est continue et où $f(a)$ et $f(b)$ sont de signes opposés. Elle repose sur la division répétée de l’intervalle en deux et la sélection du sous-intervalle où le changement de signe de $f$ persiste. ### Algorithme de la méthode de dichotomie 1. Choisir un intervalle initial $[a_0, b_0]$ tel que $f(a_0) \cdot f(b_0) < 0$ et $f$ continue sur $[a_0, b_0]$. 2. Pour $n = 0, 1, 2, \dots$ : - Calculer le milieu : $c_n = \frac{a_n + b_n}{2}$ - Évaluer $f(c_n)$ - Si $f(c_n) = 0$ → racine exacte trouvée (rare en pratique) - Sinon : - Si $f(a_n) \cdot f(c_n) < 0$ → la racine est dans $[a_n, c_n]$ → on pose $a_{n+1} = a_n$, $b_{n+1} = c_n$ - Sinon ($f(c_n) \cdot f(b_n) < 0$) → la racine est dans $[c_n, b_n]$ → on pose $a_{n+1} = c_n$, $b_{n+1} = b_n$ 3. Répéter jusqu’à ce que la longueur de l’intervalle $b_n - a_n$ soit inférieure à une tolérance $\epsilon > 0$, ou que $|f(c_n)| < \epsilon$. À l’étape $n$, on prend souvent $x_n = \frac{a_n + b_n}{2}$ comme approximation de la racine. > **À retenir** : Après $n$ itérations, la longueur de l’intervalle contenant la racine est $\frac{b_0 - a_0}{2^n}$. Donc l’erreur maximale sur l’approximation $x_n$ est vérifiée par : > $$|x_n - x^*| \leq \frac{b_0 - a_0}{2^{n+1}}$$ Cette borne permet de déterminer à l’avance le nombre d’itérations nécessaires pour atteindre une précision donnée. ### Exemple 2 : Application de la dichotomie à $f(x) = x^3 - x - 2$ sur $[1, 2]$ On sait qu’il existe une racine dans $[1, 2]$ (voir Exemple 1). On veut l’approximer avec une erreur inférieure à $0,001$. - $a_0 = 1$, $b_0 = 2$, $b_0 - a_0 = 1$ - On cherche $n$ tel que $\frac{1}{2^{n+1}} < 0,001$ → $2^{n+1} > 1000$ → $n+1 > \log_2(1000) \approx 9,96$ → $n \geq 9$ On effectue les itérations : | $n$ | $a_n$ | $b_n$ | $c_n = \frac{a_n+b_n}{2}$ | $f(c_n)$ | Nouveau sous-intervalle | |-----|--------|--------|-----------------------------|-----------|--------------------------| | 0 | 1,0 | 2,0 | 1,5 | $-0,125$ | $[1,5, 2,0]$ | | 1 | 1,5 | 2,0 | 1,75 | $1,6094$ | $[1,5, 1,75]$ | | 2 | 1,5 | 1,75 | 1,625 | $0,6660$ | $[1,5, 1,625]$ | | 3 | 1,5 | 1,625 | 1,5625 | $0,2513$ | $[1,5, 1,5625]$ | | 4 | 1,5 | 1,5625 | 1,53125 | $0,0569$ | $[1,5, 1,53125]$ | | 5 | 1,5 | 1,53125| 1,515625 | $-0,0348$ | $[1,515625, 1,53125]$ | | 6 | 1,515625| 1,53125| 1,5234375 | $0,0109$ | $[1,515625, 1,5234375]$ | | 7 | 1,515625| 1,5234375| 1,51953125 | $-0,0120$ | $[1,51953125, 1,5234375]$| | 8 | 1,51953125| 1,5234375| 1,521484375 | $-0,0006$ | $[1,521484375, 1,5234375]$| | 9 | 1,521484375| 1,5234375| 1,5224609375 | $0,0051$ | $[1,521484375, 1,5224609375]$| À l’itération $n=9$, l’intervalle est $[1,521484375, 1,5224609375]$, longueur $= 0,0009765625 < 0,001$. On prend $x_9 = \frac{1,521484375 + 1,5224609375}{2} = 1,52197265625$ comme approximation. L’erreur maximale est inférieure à $\frac{0,0009765625}{2} = 0,000488 < 0,001$. On peut vérifier : $f(1,52197) \approx (1,52197)^3 - 1,52197 - 2 \approx 3,521 - 3,52197 \approx -0,00097$ → proche de zéro. ### Exercice 2 : Méthode de dichotomie **a)** Utiliser la méthode de dichotomie pour approcher la racine de $f(x) = \cos(x) - x$ dans l’intervalle $[0, 1]$ avec une précision de $0,01$. **b)** Combien d’itérations sont nécessaires au minimum pour garantir une erreur inférieure à $10^{-4}$ si l’on part de l’intervalle $[0, 1]$ ? **Corrigé :** **a)** - $f(x) = \cos(x) - x$ est continue sur $[0,1]$. - $f(0) = \cos(0) - 0 = 1 > 0$ - $f(1) = \cos(1) - 1 \approx 0,5403 - 1 = -0,4597 < 0$ → racine dans $[0,1]$ - On veut $|x_n - x^*| < 0,01$ → $\frac{1-0}{2^{n+1}} < 0,01$ → $2^{n+1} > 100$ → $n+1 > \log_2(100) \approx 6,64$ → $n \geq 6$ Itérations : | $n$ | $a_n$ | $b_n$ | $c_n$ | $f(c_n)$ | Nouvel intervalle | |-----|--------|--------|--------|-----------|-------------------| | 0 | 0,0 | 1,0 | 0,5 | $\cos(0,5)-0,5 \approx 0,8776-0,5=0,3776>0$ | $[0,5, 1,0]$ | | 1 | 0,5 | 1,0 | 0,75 | $\cos(0,75)-0,75 \approx 0,7317-0,75=-0,0183<0$ | $[0,5, 0,75]$ | | 2 | 0,5 | 0,75 | 0,625 | $\cos(0,625)-0,625 \approx 0,8109-0,625=0,1859>0$ | $[0,625, 0,75]$ | | 3 | 0,625 | 0,75 | 0,6875 | $\cos(0,6875)-0,6875 \approx 0,7730-0,6875=0,0855>0$ | $[0,6875, 0,75]$ | | 4 | 0,6875 | 0,75 | 0,71875| $\cos(0,71875)-0,71875 \approx 0,7523-0,71875=0,03355>0$ | $[0,71875, 0,75]$ | | 5 | 0,71875| 0,75 | 0,734375| $\cos(0,734375)-0,734375 \approx 0,7417-0,734375=0,0073>0$ | $[0,734375, 0,75]$ | | 6 | 0,734375| 0,75 | 0,7421875| $\cos(0,7421875)-0,7421875 \approx 0,7370-0,7421875=-0,0052<0$ | $[0,734375, 0,7421875]$ | À $n=6$, intervalle $[0,734375, 0,7421875]$, longueur $= 0,0078125 < 0,01$ Approximation : $x_6 = \frac{0,734375 + 0,7421875}{2} = 0,73828125$ Vérification : $f(0,73828) \approx \cos(0,73828) - 0,73828 \approx 0,7395 - 0,73828 = 0,00122$ → acceptable pour précision $0,01$. **b)** On veut $\frac{1}{2^{n+1}} < 10^{-4}$ → $2^{n+1} > 10^4 = 10000$ $\log_2(10000) = \frac{\ln(10000)}{\ln(2)} \approx \frac{9,2103}{0,6931} \approx 13,29$ Donc $n+1 > 13,29$ → $n \geq 13$ → **Au moins 13 itérations** sont nécessaires. ---