Résoudre f(x) = 0 en Python, dichotomie et méthode de Newton : cours et exercices corrigés d'informatique de prépa (MPSI, PCSI, TSI, Maroc)
Encadrer une solution, méthode de dichotomie et sa terminaison, coût en nombre d'itérations, méthode de Newton, critères d'arrêt, comparaison des vitesses de convergence et cas d'échec.
- 18méthodes
- 32exercices corrigés
- 3problèmes
- 16pièges
- 46figures
Pour résoudre quand aucune formule ne donne la solution, la dichotomie part d'un intervalle où change de signe, le coupe en deux au milieu et garde la moitié où change encore de signe : après tours, le milieu est à au plus d'un zéro. La méthode de Newton suit la tangente, : près d'un zéro simple, le nombre de chiffres exacts double à chaque pas, mais elle peut échouer. Ce chapitre suit la ligne « Résolution des équations f(x) = 0 » de la section « Ingénierie numérique » du programme marocain d'informatique de première année, la même en MPSI, en PCSI et en TSI ; il n'est pas ouvert aux classes françaises. Il apprend à mettre une équation sous la forme et à localiser une solution, à écrire une dichotomie juste, à prouver qu'elle s'arrête et à compter ses tours, à choisir un test d'arrêt qui a un sens avec des flottants, à écrire Newton avec un nombre maximal d'itérations et une dérivée approchée, à mesurer une vitesse de convergence, à comparer les deux méthodes et à utiliser bisect et newton de scipy.optimize. Tu y trouves des méthodes pas à pas, des exercices corrigés, dont plusieurs tirés de sujets du CNC, de CCINP, de Centrale-Supélec, de Mines-Ponts et de la Banque PT, et trois problèmes du CNC.
Ce que tu sauras faire
Beaucoup d'équations de la physique, de la chimie ou des sciences de l'ingénieur n'ont pas de solution donnée par une formule : on ne sait pas isoler l'inconnue. On cherche alors une valeur approchée de la solution, pas à pas, avec une précision choisie d'avance. Ce chapitre présente les deux méthodes du programme, la dichotomie et la méthode de Newton, et apprend à les comparer. À la fin de ce chapitre, tu dois savoir :
- mettre une équation sous la forme , justifier qu'elle a une solution et trouver un intervalle qui la contient ;
- écrire une dichotomie juste, prouver qu'elle s'arrête, compter ses tours et prouver son résultat par un invariant ;
- choisir un test d'arrêt et une précision qui ont un sens avec des flottants ;
- écrire la méthode de Newton avec un nombre maximal d'itérations, la dérouler à la main et l'interpréter par la tangente ;
- remplacer la dérivée par une dérivée approchée et choisir le pas ;
- mesurer une vitesse de convergence, reconnaître une convergence quadratique et les cas où Newton échoue ;
- comparer les deux méthodes et utiliser
bisectetnewtondu modulescipy.optimize.
L'essentiel : Poser le problème Extrait gratuit
- Mettre l'équation sous la forme , tout du même côté.
- Existence : continue sur et ; unicité : strictement monotone.
- Localiser : tracer , ou balayer à pas fixe ; un balayage ne voit ni deux zéros proches ni un zéro double.
- On cherche à près, pas un où est petit.
Une méthode du chapitre Extrait gratuit
On demande les premiers itérés à la main, ou d'expliquer la formule, ou de justifier une récurrence donnée par l'énoncé.
La tangente en a pour équation ; elle coupe l'axe en .
- Calculer et simplifier la formule de l'itération si possible.
- Dresser un tableau : , , , , .
- Calculer avec assez de chiffres (au moins deux de plus que la précision cherchée).
- Interpréter : écart entre itérés, nombre de chiffres stables.
« La tangente à la courbe de en a pour équation ; comme , elle coupe l'axe des abscisses au point d'ordonnée nulle, . »
, zéro de , depuis 2 : la formule se simplifie en .
| 0 | 2 | 4 | 2,25 | |
| 1 | 2,25 | 0,0625 | 4,5 | 2,2361111 |
| 2 | 2,2361111 | 4,4722222 | 2,2360680 |
Le premier pas : . Après trois pas, l'erreur vaut : le tableau, arrondi à sept décimales, donne .
- Oublier le signe : éloigne du zéro.
- Arrondir trop tôt : les chiffres gagnés par un pas sont perdus.
Exercices 5 et 7.
Un exercice corrigé Extrait gratuit
Un objet de masse , suspendu à un ressort de raideur et freiné par une force d'amortissement de coefficient , a une position (comptée depuis l'équilibre, vers le haut) qui vérifie . On prend , , et ; on a tiré l'objet vers le bas et on l'a lâché sans vitesse : (valeur lue sur la figure du sujet) et . Les positions sont calculées toutes les s, de à s, et rangées dans une liste P : P[i] est la position à l'instant .
Question Q.4. Écrire la fonction racines(P), qui reçoit la liste P des positions et affiche les valeurs des zéros de la fonction : les valeurs des tels que , ou avec la précision . Le sujet donne l'exemple : 0.589, 1.684, 2.78, 3.875, 4.971, 6.067, 7.162.
Dans le sujet, la liste P vient d'un schéma numérique écrit aux questions précédentes ; ici, elle est fabriquée par la solution exacte de l'équation, avec , , et .
Question A. (Question ajoutée.) Un élève lit l'énoncé à la lettre et affiche les tels que . Combien de valeurs obtient-il ? Quelle lecture faut-il retenir ?
- Méthode 2 : entre deux échantillons consécutifs, s'annule si leurs signes sont contraires ; c'est un balayage d'une liste.
- On affiche l'instant arrondi au millième :
round(t, 3).
On ne dispose pas de la fonction , seulement de ses valeurs tous les millièmes de seconde : on ne peut pas faire de dichotomie, mais on peut repérer les changements de signe, comme le balayage du cours. Un zéro est entre deux échantillons de signes contraires ; on le situe à près en donnant l'instant du second.
On fabrique d'abord la liste P.
b, k, m = 1, 12.5, 1.5
lam = b / (2 * m)
w = math.sqrt(k / m - lam**2)
A = -0.3
B = lam * A / w
P = []
for i in range(8001):
t = i * 1e-3
c = A * math.cos(w * t) + B * math.sin(w * t)
P.append(math.exp(-lam * t) * c)
Question Q.4.
def racines(P):
# P : positions toutes les 1e-3 s depuis t = 0
# affiche les instants, arrondis au millième,
# où y s'annule ou change de signe
R = []
for i in range(len(P) - 1):
if P[i] == 0:
R.append(round(i * 1e-3, 3))
elif P[i] * P[i + 1] < 0:
R.append(round((i + 1) * 1e-3, 3))
print(R)
racines(P)
Le programme affiche :
[0.589, 1.684, 2.78, 3.875, 4.971, 6.067, 7.162]
On retrouve exactement les sept valeurs du sujet. Un zéro est entre deux instants consécutifs, donc localisé à près.
Question A.
L = []
for i in range(len(P)):
if abs(P[i]) <= 1e-3:
L.append(round(i * 1e-3, 3))
print(len(L), L[0], L[1], L[2])
Le programme affiche :
76 0.587 0.588 0.589
L'élève obtient 76 valeurs : la courbe passe lentement près de 0 (sa pente est faible quand l'amortissement a réduit les oscillations), et plusieurs échantillons consécutifs vérifient autour de chaque zéro. L'exemple du sujet, sept valeurs, montre que l'énoncé veut un instant par passage par zéro : on retient la lecture par changement de signe. La précision est celle de l'instant, pas celle de .
Sur des valeurs échantillonnées, un zéro se repère par un changement de signe entre deux échantillons voisins ; un test en donne plusieurs par passage. Voir la méthode 2.
Le cours détaillé, toute la fiche « L'essentiel », 18 méthodes, 16 pièges corrigés, la carte mentale, 32 exercices corrigés, 3 problèmes de concours, les fiches à mémoriser et l'assistant qui répond à tes questions. Les trois premiers chapitres de chaque matière sont offerts avec un compte d’essai gratuit.
Ouvrir l'essai gratuitVoir les offresPlan du cours
- 1. Le problème
- 1.1 Des équations sans formule
- 1.2 Se ramener à
- 2. Localiser une solution
- 2.1 Tracer
- 2.2 Balayer
- 3. La dichotomie
- 3.1 L'idée
- 3.2 Le programme
- 3.3 Terminaison et nombre de tours
- 3.4 Correction : un invariant
- 3.5 Cas limites
- 3.6 Deux voisines à ne pas confondre
- 4. La dichotomie face aux flottants
- 4.1 Le test
f(m) == 0n'est pas un test d'arrêt - 4.2 Une précision plus fine que les flottants
- 4.3 Le produit qui s'annule
- 4.4 Choisir d'après l'ordre de grandeur du zéro
- 4.5 Arrêter sur trompe
- 4.1 Le test
- 5. La méthode de Newton
- 5.1 L'idée de la tangente
- 5.2 Dérouler à la main
- 5.3 Le programme
- 5.4 Le test d'arrêt
- 5.5 Terminaison non garantie
- 5.6 La méthode de Héron
- 6. Quand la dérivée n'est pas connue
- 6.1 Une dérivée approchée
- 6.2 Newton à dérivée approchée
- 7. La vitesse de convergence
- 7.1 Dichotomie : un bit par tour
- 7.2 Newton : les chiffres doublent
- 7.3 Le résultat
- 7.4 Le cas du zéro double
- 7.5 Newton comme point fixe
- 8. Quand Newton échoue
- 8.1 Cinq façons d'échouer
- 8.2 Les remèdes
- 9. Comparer les deux méthodes
- 10. Les fonctions de
scipy.optimize- 10.1
bisect - 10.2
newton - 10.3
brentqetfsolve
- 10.1
- 11. Les méthodes définies par les sujets du CNC
- 11.1 La sécante
- 11.2 La fausse position
- 11.3 Les méthodes de Brent et de Dekker
- 12. Ce que le sujet fournit
- 13. Histoire et suite
- 13.1 Deux mille ans de racines
- 13.2 Ce qui vient ensuite
Les méthodes du chapitre
Chaque méthode est une fiche : quand l'utiliser, le rappel de cours, les étapes, la rédaction attendue sur la copie, un exemple traité, les erreurs à éviter.
- Mettre une équation sous la forme et justifier l'existence d'une solution
- Choisir un intervalle de départ
- Écrire une dichotomie juste
- Prouver la terminaison et compter les tours
- Prouver la correction par l'invariant de changement de signe
- Choisir et le test d'arrêt d'une dichotomie
- Écrire la méthode de Newton avec un plafond d'itérations
- Dérouler Newton à la main et lire la tangente
- Choisir et justifier le test d'arrêt de Newton
- Remplacer la dérivée par une dérivée approchée et choisir
- Diagnostiquer un échec de Newton et y remédier
- Mesurer une vitesse de convergence
- Comparer la dichotomie et Newton
- Utiliser
bisectetnewtondescipy.optimize - Résoudre une équation qui dépend d'un paramètre
- Chercher un minimum ou un maximum comme zéro de la dérivée
- Traduire une méthode donnée par l'énoncé et contrôler qu'elle s'arrête
- Programmer la recherche du point fixe d'une fonction contractante et majorer l'erreur
Les exercices corrigés
Chaque exercice a ses indications, sa correction rédigée et ce qu'il faut en retenir.
Application directe (13)
- Dérouler une dichotomie
- Écrire la dichotomie, trouver π
- Combien de tours ?
- L'équation tan x = x
- Newton à la main
- Newton avec un plafond
- La méthode de Héron
- Les pulsations de coupure d'une résonance
- bisect et newton de scipy
- La température d'une goutte qui s'évapore
- Trouver l'erreur d'une dichotomie
- Le premier zéro de la tache d'Airy
- Les instants où un ressort repasse par l'équilibre
Entraînement (14)
- L'aimantation d'un matériau
- La profondeur du chenal sonore
- Le pH de la solution du béton
- Les vitesses extrêmes du moteur d'un drone
- Arrêter sur la valeur de f ou sur l'écart ?
- Quand les flottants arrêtent la dichotomie
- Trois échecs de Newton
- Mesurer les vitesses
- L'équation de Kepler
- Le pH d'un acide faible
- Un minimum par la méthode de Newton
- Les pôles d'une pompe d'assistance cardiaque
- Les pulsations propres d'un profilé
- Le point fixe d'une fonction contractante
Approfondissement (5)
- La méthode de Brent
- Pourquoi Newton double les chiffres
- Newton sur une racine double
- Le sinus de 1° d'al-Kashi
- Test absolu ou relatif
Les problèmes de concours
Des extraits de sujets réels, corrigés en entier, avec la durée conseillée et les méthodes mobilisées.
- La racine n-ième par la méthode de Newton
- La sécante et la regula falsi
- La méthode de Dekker
Questions fréquentes
Comment écrire la méthode de dichotomie en Python ?
On part de avec . On garde fa = f(a) en mémoire, puis, tant que b - a > eps, on calcule le milieu m = (a + b) / 2 et fm = f(m) : si fa * fm <= 0, un zéro est dans et l'on pose b = m ; sinon on pose a = m et fa = fm. On renvoie le milieu (a + b) / 2, qui est à au plus d'un zéro. Le test au sens large garde un zéro tombé exactement sur un milieu, et une seule borne change à chaque tour.
Combien de tours fait une dichotomie pour une précision donnée ?
Après tours, la longueur de l'intervalle vaut . La boucle while b - a > eps fait donc exactement tours si : 20 tours pour un intervalle de longueur 1 et , 40 tours pour . Un chiffre décimal coûte environ 3,32 tours, et diviser par 1000 n'ajoute qu'une dizaine de tours. C'est le logarithme en base 2, pas le logarithme décimal.
Comment écrire la méthode de Newton en Python ?
On itère depuis et l'on s'arrête dès que , en renvoyant le dernier itéré. Rien ne garantit la convergence : la boucle compte ses tours et s'arrête par assert n < nmax au-delà d'un plafond, et la dérivée est testée avant la division (assert d != 0). Si la dérivée n'est pas connue, on la remplace par la différence centrée , avec un pas voisin de , qui ne dépend pas de .
Quel test d'arrêt choisir pour la dichotomie et pour Newton ?
Pour la dichotomie, on arrête sur la longueur de l'intervalle, while b - a > eps, ce qui garantit la précision sur . On n'arrête jamais sur f(m) == 0 seul, qui n'est presque jamais vrai en flottants, ni sur , qui ne dit rien de la distance au zéro. Pour Newton, on arrête sur l'écart entre deux itérés successifs ; c'est sûr en pratique près d'un zéro simple, pas près d'un zéro double. Pour une garantie, on vérifie que change de signe entre et . La précision doit rester plus grande que l'écart entre deux flottants voisins du zéro.
Quelle différence entre la dichotomie et la méthode de Newton ?
La dichotomie demande seulement une fonction continue et un intervalle où elle change de signe ; elle converge toujours, mais lentement, de façon linéaire, avec une erreur majorée divisée par 2 à chaque tour et une évaluation de par tour. Newton demande la dérivée et un départ proche du zéro ; près d'un zéro simple, sa convergence est quadratique, mais elle peut échouer : dérivée nulle, cycle, divergence, sortie du domaine, convergence vers un autre zéro. On résume : sûre et lente contre rapide et capricieuse. La méthode mixte fait quelques tours de dichotomie, puis Newton.
Comment utiliser bisect et newton de scipy.optimize ?
Après from scipy import optimize, optimize.bisect(f, a, b) fait une dichotomie et lève ValueError si et ont le même signe. optimize.newton(f, x0, fprime=df) fait la méthode de Newton et lève RuntimeError si elle ne converge pas en 50 itérations ; sans l'argument fprime, elle fait une méthode de la sécante. On passe la fonction elle-même, sans parenthèses. Ces deux fonctions sont au programme marocain de première année ; brentq et fsolve sont fournies par l'énoncé quand il s'en sert.
Comment y accéder
Ce chapitre fait partie de l'accès complet. Les trois premiers chapitres de chaque matière (deux par bloc en économie et droit, en management et gestion) sont offerts avec un compte d'essai gratuit. Créer un compte d'essai ou se connecter. Pour l'accès complet et les tarifs, vois les offres.