AP-BAlgorithmes d’approximation

Méthode de Newton (tangente)

Idée directrice

L'énoncé donne une fonction $f$ dérivable et demande d'approcher une racine par la méthode de Newton : à partir d'un point $x_0$ , on suit la tangente jusqu'à l'axe des abscisses pour obtenir $x_1$ , et ainsi de suite. La suite de récurrence est $x_{n+1} = x_n - \dfrac{f(x_n)}{f'(x_n)}$ . L'arrêt se fait quand $|x_{n+1} - x_n| < \varepsilon$ (ou $|f(x_n)| < \varepsilon$ ). La convergence est quadratique — bien plus rapide que la dichotomie — mais exige $f'(x_n) \neq 0$ .

Ce qui aide à reconnaître la démarche

« Écrire un algorithme utilisant la méthode de Newton pour approcher la solution de $f(x)=0$ » ; « Donner la formule de récurrence $x_{n+1}$ en fonction de $x_n$ » ; « Quel est le critère d'arrêt de l'algorithme ? » ; « Donner la trace pour les trois premières itérations » ; « Comparer la convergence de Newton et de la dichotomie »

Besoin d’un point de départ ? Voir la méthode

Calculer $f'(x)$ explicitement avant d'écrire l'algorithme — la formule de récurrence en dépend.
Critère d'arrêt le plus courant au bac : $|x_{n+1} - x_n| < \varepsilon$ . Parfois $|f(x_n)| < \varepsilon$ .
Toujours vérifier $f'(x_n) \neq 0$ pour éviter la division par zéro (signaler dans l'algorithme).
Newton converge en $O(\log \log(1/\varepsilon))$ itérations (quadratique), dichotomie en $O(\log(1/\varepsilon))$ .
Si l'énoncé parle de tangente, c'est Newton ; si de bissection ou couper en deux, c'est la dichotomie.

Les pièges à vérifier dans ta démarche

Pièges fréquents : (1) Oublier de simplifier la formule de récurrence (écrire $x_{n+1} = x_n - f(x_n)/f'(x_n)$ sans substituer $f$ et $f'$ ). (2) Utiliser $f(x) = 0$ comme critère d'arrêt au lieu de $|x_{n+1}-x_n| < \varepsilon$ : en virgule flottante, $f(x)$ n'atteint jamais exactement 0. (3) Mauvais choix de $x_0$ qui fait diverger la suite (ex. $x_0$ loin de la racine sur une fonction non monotone).

Sujet principal

Exercice — dans l'esprit des sujets du bac

4 questionsCorrigé masqué

On veut approcher $\sqrt{3}$ en cherchant la racine positive de $f(x) = x^2 - 3$ sur $[1, 2]$ .

Rappeler la formule de récurrence de la méthode de Newton appliquée à cette fonction. Simplifier l'expression de $x_{n+1}$ en fonction de $x_n$ .
Écrire l'algorithme de Newton permettant de calculer une valeur approchée de $\sqrt{3}$ avec une précision $\varepsilon > 0$ donnée.
1. Identifier les données d'entrée et de sortie.
2. Quel risque existe-t-il si $f'(x_n) = 0$ ? Comment s'en prémunir ?
Donner la trace de l'algorithme pour $x_0 = 2$ et $\varepsilon = 10^{-4}$ (3 premières itérations). Compléter le tableau ( $n$ , $x_n$ , $f(x_n)$ , $x_{n+1}$ ).
Comparer la rapidité de convergence de Newton et de la dichotomie. Quel inconvénient majeur présente Newton ?

Voir la correction commentéeAprès avoir posé votre démarche

1. Formule de Newton pour $f(x)=x^2-3$ sur $[1,2]$ , racine positive $\sqrt{3}$ .

$f'(x)=2x$ , donc $x_{n+1}=x_n-\dfrac{x_n^2-3}{2x_n}=\dfrac{x_n}{2}+\dfrac{3}{2x_n}=\dfrac{x_n+3/x_n}{2}$ (moyenne arithmético-harmonique, aussi méthode de Héron).

2. Algorithme. TDOL — objets locaux :

x, xnew : réel — itéré courant et suivant
x0, eps : réel — donnée initiale et précision (Type/Nature : paramètres d'entrée)

DEF PROC Newton(x0, eps : réel)
Variables x, xnew : réel
Début
  x ← x0
  xnew ← (x + 3/x) / 2
  TantQue ABS(xnew - x) > eps faire
    x ← xnew
    xnew ← (x + 3/x) / 2
  FinTantQue
  Écrire(xnew)
Fin

3. Trace d'exécution ( $x_0=2$ , $\varepsilon=10^{-4}$ ) :

$n$	$x_n$	$f(x_n)=x_n^2-3$	$x_{n+1}$	$\lvert x_{n+1}-x_n\rvert$
0	2	1	1,75	0,25
1	1,75	0,0625	1,732143	0,0179
2	1,732143	0,000319	1,732051	$9{,}2\times10^{-5}<\varepsilon$ → arrêt

On retourne $x_3\approx1{,}732051$ , soit $\sqrt3$ à $10^{-4}$ près en trois itérations (valeur exacte 1,7320508…).

Contrainte : $x\neq 0$ (division par $f'(x)$ ) ; eps dans ]0 ; 1]. Critère d'arrêt : $|x_{n+1}-x_n|<\varepsilon$ , pas $f(x)=0$ exact.

Équivalent Python (extrait).

def newton(x0, eps):
    x = x0
    xnew = (x + 3/x) / 2
    while abs(xnew - x) > eps:
        x = xnew
        xnew = (x + 3/x) / 2
    return xnew
print(newton(2.0, 1e-4))

4. Newton contre dichotomie. La dichotomie divise l'intervalle par 2 à chaque étape : pour passer d'une largeur 1 à $10^{-4}$ il lui faut $\lceil\log_2 10^4\rceil=14$ itérations, et elle converge toujours dès que $f$ change de signe. Newton double environ le nombre de décimales exactes à chaque itération (convergence quadratique) : trois itérations ici. Son inconvénient majeur : il exige la dérivée et un bon point de départ ; si $f'(x_n)$ est nul ou très petit, la tangente est presque horizontale et l'itéré suivant part très loin — l'algorithme peut diverger, ce que la dichotomie ne fait jamais.

Changer d’énoncé, garder le raisonnement

Choisis un seul transfert après le sujet principal. Qu’est-ce qui change ? Quel résultat ou quelle méthode peux-tu réutiliser ? Les autres exercices restent disponibles pour une prochaine séance.

Variantes rencontrées : Newton appliqué à $f(x) = x^2 - a$ donne la méthode de Héron pour $\sqrt{a}$ (voir AP-D). Parfois l'énoncé demande de montrer la convergence en calculant $|x_{n+1} - \alpha|$ en fonction de $|x_n - \alpha|^2$ . On rencontre aussi $f(x) = e^x - 2$ ou $f(x) = \ln(x) - 1$ .

Exercices d'entraînement — une nuance à la fois

1 Drill AP-B.1 — méthode de Newton

Entraînement 01 / 04

Drill AP-B.1 — méthode de Newton

1 questionCorrigé masqué

Donner la formule d'itération de la méthode de Newton pour approcher une racine de f.

Voir la correction commentéeAprès avoir posé votre démarche

$x_{n+1}=x_n-f(x_n)/f'(x_n)$ si $f'\neq 0$ . TDOL : x réel. Type/Nature : itéré.

DEF FN IterNewton(x : réel) : réel
Début
  Retourner x - f(x)/f'(x)
Fin

On retourne le nouvel itéré ; convergence quadratique près de la racine.

2 Transfert — Newton sans garde-fou : reconnaître la moyenne de Héron, détecter un cycle

Entraînement 02 / 04

Transfert — Newton sans garde-fou : reconnaître la moyenne de Héron, détecter un cycle

4 questionsCorrigé masquéEn cours de relecture

La méthode de Newton approche un zéro (une racine) de $f$ en remplaçant, à chaque itération, la courbe par sa tangente : $x_{n+1} = x_n - \dfrac{f(x_n)}{f'(x_n)}$ . Une fonction Newton(x0, eps) proposée par un élève répète ce calcul « jusqu'à $|x_{n+1} - x_n| < eps$ » et retourne le dernier terme, sans autre test.

Pour $f(x) = x^2 - a$ ( $a > 0$ ), montrer que la formule de Newton s'écrit $x_{n+1} = \dfrac{1}{2}\left(x_n + \dfrac{a}{x_n}\right)$ : la tangente redonne la moyenne de $x_n$ et de $a/x_n$ . Donner la trace pour $a = 3$ , $x_0 = 2$ , $eps = 10^{-4}$ (colonnes $n$ , $x_n$ , $|x_n - x_{n-1}|$ ) jusqu'à l'arrêt.
Pour $g(x) = x^3 - 2x + 2$ et $x_0 = 0$ , calculer $x_1$ puis $x_2$ . Que fait la fonction de l'élève sur cet exemple ? Quel second danger, indépendant de celui-ci, guette le calcul de $x_{n+1}$ ?
Écrire l'algorithme d'une fonction NewtonSur(x0, eps, nmax : …) : … qui retourne la valeur approchée trouvée et signale l'échec par une valeur sentinelle, en se protégeant des deux dangers. On dispose des fonctions F(x) et DF(x) déjà écrites. Donner son TDOL.
Traduire NewtonSur en Python (les fonctions F et DF étant définies), puis indiquer ce que retournent les appels correspondant à $f$ avec $x_0 = 2$ et à $g$ avec $x_0 = 0$ , $nmax = 50$ .

Cet exercice et sa correction sont en cours de relecture. Tu peux les consulter ; l’exercice n’est pas encore proposé en séance.

Voir la correction commentéeAprès avoir posé votre démarche

1. Idée : appliquer la formule générale à $f(x) = x^2 - a$ , $f'(x) = 2x$ .

$x_{n+1} = x_n - \dfrac{x_n^2 - a}{2x_n} = \dfrac{2x_n^2 - x_n^2 + a}{2x_n} = \dfrac{x_n^2 + a}{2x_n} = \dfrac{1}{2}\left(x_n + \dfrac{a}{x_n}\right)$ . La tangente à la parabole redonne exactement la moyenne de Héron : si $x_n > \sqrt a$ alors $a/x_n < \sqrt a$ , et la moyenne resserre l'encadrement.

Trace pour $a = 3$ , $x_0 = 2$ :

$n$	$x_n$	$\lvert x_n - x_{n-1}\rvert$
0	2	—
1	1,75	0,25
2	1,732143	0,0179
3	1,7320508	$9{,}2\times10^{-5}$

À $n = 3$ , l'écart $9{,}2\times10^{-5} < 10^{-4}$ : arrêt, la fonction retourne $\boxed{x_3 \approx 1{,}7320508}$ ( $\sqrt3 = 1{,}7320508\ldots$ , sept décimales exactes en trois itérations).

2. Idée : dérouler deux itérations et regarder où l'on retombe.

$g(0) = 2$ , $g'(x) = 3x^2 - 2$ , $g'(0) = -2$ : $x_1 = 0 - \dfrac{2}{-2} = 1$ . Puis $g(1) = 1 - 2 + 2 = 1$ , $g'(1) = 1$ : $x_2 = 1 - 1 = 0$ . La suite revient à son point de départ : $0, 1, 0, 1, \ldots$ L'écart $|x_{n+1} - x_n|$ vaut toujours $1$ : la condition d'arrêt $< eps$ n'est jamais vraie et la fonction de l'élève boucle indéfiniment, bien que $g$ ait une racine réelle (voisine de $-1{,}769$ , atteinte par exemple depuis $x_0 = -1$ ). Second danger, indépendant du cycle : si $f'(x_n) = 0$ (tangente horizontale), le calcul de $x_{n+1}$ divise par zéro ; pour $f(x) = x^2 - a$ c'est le cas dès $x_0 = 0$ .

3. Idée : deux gardes, un compteur d'itérations et un test de dérivée nulle, et une sentinelle pour l'échec.

0) DEF FN NewtonSur (x0, eps : réel ; nmax : entier) : réel
1) x ← x0 ; n ← 0 ; fini ← faux
2) Répéter
     n ← n + 1
     d ← DF(x)
     Si d = 0 alors
        fini ← vrai ; x ← -1
     Sinon
        x1 ← x - F(x) / d
        Si abs(x1 - x) < eps alors fini ← vrai FinSi
        x ← x1
     FinSi
   Jusqu'à fini ou (n = nmax)
3) Si non fini alors x ← -1 FinSi
4) NewtonSur ← x
5) Fin NewtonSur

La sentinelle

-1

signale l'échec (dérivée nulle ou

nmax

itérations sans convergence) ; elle convient ici parce que les racines cherchées sont positives, sinon on retournerait un booléen en paramètre var.

TDOL

Objet	Type / Nature	Rôle
x	réel	terme courant $x_n$
x1	réel	terme suivant $x_{n+1}$
d	réel	valeur de $f'(x_n)$ , testée avant division
n	entier	compteur d'itérations
fini	booléen	vrai dès qu'un critère d'arrêt est atteint
F, DF	fonctions	$f$ et $f'$

4. Idée : même structure en Python, la boucle for borne d'elle-même le nombre d'itérations.

def newton_sur(x0, eps, nmax):
    x = x0
    for n in range(1, nmax + 1):
        d = DF(x)
        if d == 0:
            return -1
        x1 = x - F(x) / d
        if abs(x1 - x) < eps:
            return x1
        x = x1
    return -1

Avec F = lambda x: x*x - 3, DF = lambda x: 2*x : print(newton_sur(2, 1e-4, 50)) affiche

1{,}7320508\ldots

(trois itérations, comme la trace). Avec F = lambda x: x**3 - 2*x + 2, DF = lambda x: 3*x*x - 2 : newton_sur(0, 1e-4, 50) effectue 50 itérations du cycle

0 \to 1 \to 0

et retourne

\boxed{-1}

: l'échec est signalé au lieu de bloquer le programme. Le même appel avec

x_0 = -1

retourne

-1{,}7692923\ldots

, racine réelle de

g

: Newton dépend du point de départ, et une valeur approchée n'est valable que si la fonction a réellement convergé.

3 Transfert — Dichotomie : le changement de signe est une hypothèse, pas une conclusion

Entraînement 03 / 04

Transfert — Dichotomie : le changement de signe est une hypothèse, pas une conclusion

4 questionsCorrigé masquéEn cours de relecture

La dichotomie approche un zéro d'une fonction continue en coupant en deux un intervalle $[a, b]$ sur lequel la fonction change de signe : à chaque itération on garde la moitié qui contient encore ce changement de signe, et la largeur est divisée par deux. C'est la méthode d'approximation la plus robuste — elle ne demande ni dérivée ni bon point de départ — mais elle exige son hypothèse de départ. On travaille avec $f(x) = x^3 + x - 1$ et $g(x) = x^2 - 1$ , continues sur $\R$ ; une fonction F(x) qui calcule $f(x)$ est déjà écrite.

Calculer $f(0)$ , $f(1)$ et le produit $f(0) \times f(1)$ . Qu'autorise le signe de ce produit à affirmer sur $[0, 1]$ ? Donner ensuite la trace de la dichotomie sur $[0, 1]$ pendant 4 itérations (colonnes $n$ , $a$ , $b$ , $m = \dfrac{a+b}{2}$ , $f(m)$ , moitié conservée), puis l'encadrement obtenu du zéro et sa largeur.
On lance le même traitement sur $g$ et l'intervalle $[-2, 2]$ : calculer $g(-2) \times g(2)$ . Un élève en déduit « $g$ ne s'annule pas sur $[-2, 2]$ ». Réfuter cette déduction par un calcul, dire ce que la méthode a réellement le droit d'annoncer ici, et indiquer comment relancer le calcul sur la même fonction pour obtenir un zéro.
Écrire l'algorithme du module Dicho qui reçoit $a$ , $b$ et la précision $eps$ et qui rend deux informations : la valeur approchée du zéro et un booléen disant si le calcul a pu être mené. Le module refuse de calculer lorsque $a \geq b$ ou lorsque $F(a) \times F(b) > 0$ . Donner le TDOL.
Le module s'arrête quand la largeur de l'intervalle courant est $\leq eps$ et rend son milieu. Quelle erreur maximale est alors garantie sur le zéro rendu ? Cette garantie fait-elle intervenir la dérivée de $f$ , contrairement à la méthode de Newton ?

Cet exercice et sa correction sont en cours de relecture. Tu peux les consulter ; l’exercice n’est pas encore proposé en séance.

Voir la correction commentéeAprès avoir posé votre démarche

1. Idée : pour une fonction continue, un changement de signe garantit l'existence d'un zéro — c'est l'hypothèse qui fait démarrer la méthode.

$f(0) = 0 + 0 - 1 = -1$ et $f(1) = 1 + 1 - 1 = 1$ , donc $f(0) \times f(1) = -1 < 0$ . Comme $f$ est continue sur $[0, 1]$ , elle s'annule au moins une fois dans $]0 ; 1[$ ; ici $f'(x) = 3x^2 + 1 > 0$ , la fonction est strictement croissante et le zéro $\alpha$ est unique.

$n$	$a$	$b$	$m$	$f(m)$	moitié conservée
1	0	1	0,5	$-0{,}375$	$[0{,}5 ; 1]$
2	0,5	1	0,75	$+0{,}171875$	$[0{,}5 ; 0{,}75]$
3	0,5	0,75	0,625	$-0{,}130859375$	$[0{,}625 ; 0{,}75]$
4	0,625	0,75	0,6875	$+0{,}012451171875$	$[0{,}625 ; 0{,}6875]$

Après 4 itérations : $\boxed{0{,}625 < \alpha < 0{,}6875}$ , largeur $0{,}0625 = \dfrac{1}{2^4}$ — la largeur initiale $1$ divisée par $2$ quatre fois. (Valeur exacte : $\alpha = 0{,}6823278\ldots$ , bien dans l'encadrement.)

2. Idée : le test de signe est une condition suffisante d'existence ; ne pas la vérifier n'est pas une conclusion.

$g(-2) = 4 - 1 = 3$ et $g(2) = 4 - 1 = 3$ , donc $g(-2) \times g(2) = 9 > 0$ . Pourtant $g(-1) = 0$ et $g(1) = 0$ : il y a deux zéros dans $[-2, 2]$ . Les deux changements de signe se compensent aux extrémités, et le produit redevient positif : l'information « même signe aux deux bornes » ne distingue pas « aucun zéro » de « un nombre pair de zéros ».

Le module n'a donc le droit d'annoncer qu'une chose : sur cet intervalle je ne peux pas démarrer. Pour obtenir un zéro de $g$ , on coupe l'intervalle et on relance là où le signe change : $g(-2) \times g(0) = 3 \times (-1) = -3 < 0$ , la dichotomie sur $[-2, 0]$ converge vers $-1$ ; de même sur $[0, 2]$ elle converge vers $+1$ .

3. Idée : un refus est une information, il se transmet par un booléen — pas par une valeur numérique qui aurait l'air d'un résultat.

0) DEF PROC Dicho (a, b, eps : réel ; var x : réel ; var possible : booléen)
1) Si (a ≥ b) ou (F(a) * F(b) > 0) alors
      possible ← faux
      x ← 0
   Sinon
      possible ← vrai
      inf ← a
      sup ← b
      Répéter
         m ← (inf + sup) / 2
         Si F(inf) * F(m) ≤ 0 alors
            sup ← m
         Sinon
            inf ← m
         FinSi
      Jusqu'à (sup - inf) ≤ eps
      x ← (inf + sup) / 2
   FinSi
2) Fin Dicho

TDOL

Objet	Type / Nature	Rôle
inf	réel	borne gauche courante
sup	réel	borne droite courante
m	réel	milieu de $[inf ; sup]$
F	fonction	calculer $f$ en un point

Deux détails qui coûtent des points : les bornes de travail inf et sup sont des objets locaux (on ne modifie pas les données reçues, et le nom ne rentre pas en conflit avec la fonction $g$ de l'énoncé), et le test s'écrit $F(inf) \times F(m) \leq 0$ — avec $\leq$ , le cas $F(m) = 0$ (on est tombé exactement sur le zéro) garde le bon côté au lieu de le rejeter.

4. Idée : ce que la dichotomie garantit se lit sur la largeur de l'intervalle, jamais sur la valeur de la fonction.

À la sortie de la boucle, $sup - inf \leq eps$ et le zéro $\alpha$ appartient toujours à $[inf ; sup]$ ; le milieu rendu est donc à une distance au plus $\dfrac{sup-inf}{2}$ de $\alpha$ : l'erreur est $\boxed{\leq \dfrac{eps}{2}}$ . C'est une majoration prouvée, pas une estimation : elle ne dépend que de la continuité et de l'encadrement maintenu à chaque étape.

Aucune dérivée n'intervient : le module n'évalue que des signes. La méthode de Newton, elle, calcule $\dfrac{f(x_n)}{f'(x_n)}$ et exige $f'(x_n) \neq 0$ ; elle ne tient pas le zéro entre deux bornes, donc son test d'arrêt $|x_{n+1} - x_n| \leq eps$ n'est qu'un indice de proximité. Le prix de la garantie : la dichotomie ne divise l'erreur que par $2$ à chaque itération.

4 Transfert — Budget d'itérations : la dichotomie se compte d'avance, Newton se compte après coup

Entraînement 04 / 04

Transfert — Budget d'itérations : la dichotomie se compte d'avance, Newton se compte après coup

4 questionsCorrigé masquéEn cours de relecture

On cherche $\sqrt[3]{5}$ , c'est-à-dire le zéro de $h(x) = x^3 - 5$ , avec la précision $eps = 10^{-6}$ . Deux méthodes d'approximation sont en concurrence : la dichotomie sur $[1, 2]$ , qui s'arrête quand la largeur de l'intervalle devient $\leq eps$ , et la méthode de Newton partie de $x_0 = 2$ , qui s'arrête quand $|x_{n+1} - x_n| \leq eps$ . On suppose qu'évaluer $h$ ou $h'$ coûte le même temps.

Montrer que la largeur de l'intervalle après $n$ itérations de dichotomie vaut $\dfrac{1}{2^n}$ , puis déterminer le plus petit $n$ tel que cette largeur soit $\leq 10^{-6}$ . Ce nombre dépend-il de $h$ ?
Écrire la formule de récurrence de Newton pour $h$ , simplifiée en fonction de $x_n$ , puis donner la trace jusqu'à l'arrêt (colonnes $n$ , $x_n$ , $|x_n - x_{n-1}|$ ). Combien d'itérations ?
Comparer les deux méthodes en nombre d'évaluations de fonction (la dichotomie évalue $h$ une fois par itération si l'on mémorise le signe de la borne gauche ; Newton évalue $h$ et $h'$ à chaque itération). Puis choisir sous contrainte : le zéro d'une grandeur relevée par un capteur, dont aucune expression de la dérivée n'est disponible, doit être approché à $10^{-3}$ sur $[1, 2]$ — quelle méthode, et combien d'itérations annonce-t-on au chef de projet ?
Écrire l'algorithme d'une fonction NbIter (a, b, eps : réel) : entier qui rend le nombre d'itérations que la dichotomie effectuera sans exécuter la dichotomie, et donner son TDOL. Expliquer pourquoi la fonction équivalente est impossible à écrire pour Newton.

Cet exercice et sa correction sont en cours de relecture. Tu peux les consulter ; l’exercice n’est pas encore proposé en séance.

Voir la correction commentéeAprès avoir posé votre démarche

1. Idée : une largeur qui est divisée par deux à chaque pas se compte avant d'avoir calculé quoi que ce soit.

La largeur initiale vaut $b - a = 1$ et chaque itération la divise par $2$ : après $n$ itérations elle vaut $\dfrac{b-a}{2^n} = \dfrac{1}{2^n}$ . On cherche le plus petit $n$ tel que $\dfrac{1}{2^n} \leq 10^{-6}$ , c'est-à-dire $2^n \geq 10^6$ , soit $n \geq \log_2(10^6) = 6\log_2 10 \approx 19{,}93$ .

$\dfrac{1}{2^{19}} = 1{,}907\times10^{-6} > 10^{-6}$ et $\dfrac{1}{2^{20}} = 9{,}537\times10^{-7} \leq 10^{-6}$ : il faut $\boxed{n = 20}$ itérations. Ce nombre ne dépend que de $b - a$ et de $eps$ — pas de $h$ : la même borne vaut pour une fonction compliquée comme pour $x^3 - 5$ .

2. Idée : Newton remplace la courbe par sa tangente, ce qui double le nombre de décimales exactes à chaque pas.

$x_{n+1} = x_n - \dfrac{h(x_n)}{h'(x_n)} = x_n - \dfrac{x_n^3 - 5}{3x_n^2} = \dfrac{2x_n^3 + 5}{3x_n^2}$ .

$n$	$x_n$	$\lvert x_n - x_{n-1}\rvert$
0	2	—
1	1,750000000000	$2{,}50\times10^{-1}$
2	1,710884353741	$3{,}91\times10^{-2}$
3	1,709976428917	$9{,}08\times10^{-4}$
4	1,709975946677	$4{,}82\times10^{-7}$

À la 4ᵉ itération l'écart passe sous $10^{-6}$ : $\boxed{4 \text{ itérations}}$ , pour $x_4 = 1{,}709975946677$ — la valeur exacte $\sqrt[3]{5} = 1{,}709975946677$ est déjà atteinte à $10^{-12}$ près, bien au-delà de ce qui était demandé.

3. Idée : compter les itérations flatte Newton ; compter les évaluations rétablit le vrai coût, et une contrainte sur la dérivée peut renverser le choix.

Dichotomie : $20$ itérations $\times$ 1 évaluation $= 20$ évaluations. Newton : $4$ itérations $\times$ 2 évaluations ( $h$ et $h'$ ) $= 8$ évaluations. Newton reste $2{,}5$ fois moins cher malgré son itération deux fois plus chère — mais son compteur n'était connu qu'après coup.

Avec un capteur, $h'$ n'a pas d'expression : Newton ne peut pas être appliqué tel quel (le remplacer par une dérivée approchée ajoute une évaluation et une erreur supplémentaire). La dichotomie ne demande que le signe de la grandeur mesurée. Pour $eps = 10^{-3}$ sur $[1, 2]$ : $\dfrac{1}{2^9} = 1{,}95\times10^{-3} > 10^{-3}$ et $\dfrac{1}{2^{10}} = 9{,}77\times10^{-4} \leq 10^{-3}$ , donc on annonce $\boxed{10 \text{ itérations}}$ , donc 10 mesures — un chiffre ferme, donné avant de lancer la campagne.

4. Idée : le nombre d'itérations de la dichotomie est une fonction de $(a, b, eps)$ seuls ; celui de Newton dépend de la fonction et du point de départ.

0) DEF FN NbIter (a, b, eps : réel) : entier
1) L ← b - a
   n ← 0
   Tant que L > eps faire
      L ← L / 2
      n ← n + 1
   Fin tant que
2) NbIter ← n
3) Fin NbIter

TDOL

Objet	Type / Nature	Rôle
L	réel	largeur courante de l'intervalle
n	entier	nombre d'itérations comptées

On est tenté d'écrire directement $n = \left\lfloor \dfrac{\ln((b-a)/eps)}{\ln 2} \right\rfloor + 1$ ; la formule tombe juste presque partout, mais elle se trompe d'une unité quand $\dfrac{b-a}{eps}$ est exactement une puissance de $2$ : pour $b - a = 1$ et $eps = 0{,}0625$ elle annonce $5$ alors que $4$ divisions suffisent ( $1/2^4 = eps$ ). La version par divisions successives n'a pas ce défaut.

Pour Newton, rien de tel : avec le même $h$ et le même $eps = 10^{-6}$ , le départ $x_0 = 2$ demande 4 itérations et le départ $x_0 = 100$ en demande 15. Le compteur dépend de la fonction et du point initial, et pour certains couples la suite ne converge même pas — il n'existe donc pas de fonction de $(a, b, eps)$ qui le rende.

Limite machine, vérifiée par exécution : avec $eps = 10^{-20}$ , NbIter annonce 67 itérations, mais la dichotomie réelle ne s'arrête jamais — dès que les deux bornes sont deux réels machine voisins (écart $\approx 2{,}2\times10^{-16}$ autour de $1{,}7$ ), leur milieu est arrondi sur l'une d'elles et la largeur cesse de diminuer. Newton n'est pas mieux loti : écrit $x_{n+1} = \dfrac{2x_n^3 + 5}{3x_n^2}$ , il oscille indéfiniment entre deux réels machine voisins ; écrit $x_{n+1} = x_n - \dfrac{h(x_n)}{h'(x_n)}$ , il tombe par chance sur un écart exactement nul à la 6ᵉ itération et s'arrête. Une précision demandée plus fine que le pas machine n'est rendue par aucun des deux, et c'est pourquoi un compteur maximal d'itérations accompagne toujours ces boucles.

Relier ce raisonnement au bac

Choisis une filière pour voir les sujets qui étayent ce scénario.

Tu écris. Tu continues.

Où veux-tu aller ?

Méthode de Newton (tangente)

Exercice — dans l'esprit des sujets du bac

Changer d’énoncé, garder le raisonnement

Exercices d'entraînement — une nuance à la fois

Drill AP-B.1 — méthode de Newton

Transfert — Newton sans garde-fou : reconnaître la moyenne de Héron, détecter un cycle

Transfert — Dichotomie : le changement de signe est une hypothèse, pas une conclusion

Transfert — Budget d'itérations : la dichotomie se compte d'avance, Newton se compte après coup

Relier ce raisonnement au bac