🔢Méthodes numériques : Newton et dichotomie

Beaucoup d'équations $f(x) = 0$ n'ont pas de solution exacte simple (par exemple $x^2 = 2$, ou $x^3 + x - 1 = 0$). On en cherche alors une valeur approchée avec un algorithme.

Idée clé (théorème des valeurs intermédiaires) : si $f$ est continue et que $f(a)$ et $f(b)$ sont de signes contraires, alors il existe une solution entre $a$ et $b$. On va resserrer cet encadrement.

On exécutera un nombre d'itérations fixé et on renverra une valeur arrondie avec round(x, k) : ainsi le résultat est toujours le même, ce qui rend les tests fiables.

⭐ Pour les curieux — pourquoi ça marche ? Imagine que tu traces la courbe de $f$ sans lever le crayon (c'est ça, « continue ») entre $a$ et $b$. Si $f(a) < 0$, tu démarres sous l'axe des abscisses ; si $f(b) > 0$, tu finis au-dessus. Pour passer du dessous au dessus sans décoller le crayon, tu es bien obligé de traverser l'axe au moins une fois : ce point de traversée, c'est une solution de $f(x) = 0$. C'est tout le théorème des valeurs intermédiaires, et c'est précisément la continuité qui interdit de « sauter » par-dessus l'axe.

Pour repérer un encadrement : calcule f(a) et f(b). Si f(a) * f(b) < 0, les signes sont opposés → une solution est piégée entre a et b.

Pour $f(x) = x^2 - 2$ : $f(1) = -1 < 0$ et $f(2) = 2 > 0$. La solution $\sqrt 2 \approx 1{,}41$ est bien entre 1 et 2.

round(x, 4) arrondit à 4 décimales : round(1.41421356, 4) donne 1.4142. C'est ce qu'on renvoie pour comparer à une valeur attendue.

On part d'un intervalle $[a, b]$ qui encadre la solution ($f(a)$ et $f(b)$ de signes contraires). À chaque étape :

1. On calcule le milieu $m = (a + b)/2$.
2. On regarde le signe de $f(m)$ pour savoir dans quelle moitié se trouve la solution.
3. On remplace $a$ ou $b$ par $m$ : l'intervalle est deux fois plus petit.

def dicho(a, b, n):
    for _ in range(n):
        m = (a + b) / 2
        if (m * m - 2) * (a * a - 2) <= 0:  # f(m) et f(a) signes opposés
            b = m        # la racine est dans [a, m]
        else:
            a = m        # la racine est dans [m, b]
    return round((a + b) / 2, 4)

Ici $f(x) = x^2 - 2$. Après n étapes, l'intervalle a été divisé par $2^n$ : on s'approche très vite de la solution.

⭐ Pour les curieux — pourquoi ça marche ? À chaque étape on garde la moitié de l'intervalle où $f$ change encore de signe (la racine y reste donc emprisonnée), et cette moitié a exactement la moitié de la largeur précédente. En partant d'une largeur $L_0 = b - a$, on obtient $L_1 = \dfrac{L_0}{2}$, puis $L_2 = \dfrac{L_0}{4}$, et ainsi de suite : c'est une suite géométrique de raison $\frac{1}{2}$, donc après $n$ étapes la largeur vaut $L_n = \dfrac{L_0}{2^n}$. Ce $2^n$ au dénominateur explose vite : 10 étapes divisent déjà l'intervalle par plus de 1000 ($2^{10} = 1024$), ce qui garantit qu'on approche la racine d'aussi près qu'on veut.

Pour programmer une dichotomie sur $f(x) = 0$ :

1. Boucle for _ in range(n): (nombre d'itérations imposé).
2. Milieu m = (a + b) / 2.
3. Compare les signes : if f(m) * f(a) <= 0: → la racine est à gauche, donc b = m ; sinon a = m.
4. Renvoie round((a + b) / 2, k) (le milieu final, meilleure estimation).

Pour $f(x) = x^2 - 2$ sur $[1, 2]$ avec n = 1 : $m = 1{,}5$, $f(1{,}5) = 0{,}25 > 0$ (même signe que $f(2)$), donc on garde $[1 ; 1{,}5]$. Milieu final : round(1.25, 4) = 1.25.

Comparer les signes avec un produit f(m) * f(a) <= 0 évite d'écrire plein de if. Si le produit est négatif ou nul, les signes sont opposés (racine entre a et m).

La méthode de Newton approche une racine de $f$ en suivant la tangente à la courbe. À partir d'un point de départ $x_0$, on itère :

$x_{n+1} = x_n - \dfrac{f(x_n)}{f'(x_n)}.$

Géométriquement, $x_{n+1}$ est l'endroit où la tangente en $x_n$ coupe l'axe des abscisses. Quand ça converge, c'est beaucoup plus rapide que la dichotomie.

def newton(x0, n):
    x = x0
    for _ in range(n):
        x = x - (x * x - 2) / (2 * x)   # f(x)=x^2-2, f'(x)=2x
    return round(x, 4)

Pour $f(x) = x^2 - 2$, on a $f'(x) = 2x$. En partant de $x_0 = 2$, on converge vers $\sqrt 2 \approx 1{,}4142$ en très peu d'étapes.

⭐ Pour les curieux — pourquoi ça marche ? La formule de Newton n'est pas magique : elle tombe de l'équation de la tangente, déjà connue en Tle. La tangente à la courbe au point $x_n$ a pour équation $y = f(x_n) + f'(x_n)\,(x - x_n)$. On cherche où cette droite coupe l'axe des abscisses, c'est-à-dire où $y = 0$ : on résout $f(x_n) + f'(x_n)\,(x - x_n) = 0$, ce qui donne $x = x_n - \dfrac{f(x_n)}{f'(x_n)}$. C'est exactement $x_{n+1}$ : on glisse le long de la tangente jusqu'à l'axe, et on recommence. On comprend du coup pourquoi $f'(x_n) = 0$ casse tout : une tangente horizontale ne croise jamais l'axe !

Pour programmer Newton :

1. Initialise x = x0.
2. Boucle for _ in range(n):.
3. À chaque tour : x = x - f(x) / fprime(x) (remplace f et fprime par leurs expressions).
4. Renvoie round(x, k).

Newton pour $\sqrt 2$, départ $x_0 = 2$ :

• $x_1 = 2 - (4-2)/4 = 1{,}5$
• $x_2 = 1{,}5 - (2{,}25-2)/3 = 1{,}41666\dots$

newton(2, 2) renvoie donc round(1.41666..., 4) = 1.4167.

Newton converge en peu d'étapes mais il faut un bon point de départ et $f'(x) \ne 0$. Sinon on divise par zéro ! La dichotomie, elle, est plus lente mais toujours sûre dès qu'on a un bon encadrement de départ.

Une méthode approchée donne un nombre avec beaucoup de décimales (1.4142135623730951). Pour pouvoir comparer à une valeur attendue, on arrondit avec round(x, k) :

round(1.4142135623730951, 4)   # -> 1.4142
round(1.41666666, 4)           # -> 1.4167

Le deuxième argument k est le nombre de décimales gardées. On choisit k (souvent 3 ou 4) et on l'indique dans l'énoncé pour que tout le monde obtienne la même réponse.

Renvoie toujours round(resultat, k) à la fin d'une méthode approchée. Fais bien tes calculs sans arrondir dans la boucle, et arrondis seulement à la fin : sinon tu accumules des erreurs.

round(2.5, 0) peut surprendre : Python utilise l'arrondi « au pair le plus proche » et renvoie 2.0. En pratique, avec k ≥ 3, ce détail n'a aucun impact sur nos exercices.

Arrondis uniquement la valeur renvoyée, pas les valeurs intermédiaires : tu gardes ainsi toute la précision pendant les itérations.

Les deux méthodes résolvent $f(x) = 0$, mais différemment :

En pratique : la dichotomie est robuste et facile à écrire ; Newton est ultra-rapide quand on connaît $f'$ et qu'on part assez près de la solution.

Choisis la dichotomie quand tu as un encadrement sûr et que tu veux un résultat garanti. Choisis Newton quand tu connais $f'(x)$ et que tu veux peu d'itérations.

Pour $\sqrt 2$ à $10^{-4}$ près : la dichotomie depuis $[1, 2]$ demande une quinzaine d'étapes ; Newton depuis $x_0 = 2$ y arrive en 4 étapes.

Newton qui « part en vrille » (diverge) est souvent dû à un mauvais point de départ ou à $f'(x)$ proche de 0. Dans le doute, encadre d'abord avec quelques dichotomies, puis affine avec Newton.