Prepa Help
Prepa Help › Cours › Informatique, 1re année

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.

Les nombres sont ceux du chapitre complet ; chaque filière voit la partie qui correspond à son programme.

Pour résoudre f(x)=0f(x) = 0 quand aucune formule ne donne la solution, la dichotomie part d'un intervalle [a,b][a, b] où ff change de signe, le coupe en deux au milieu et garde la moitié où ff change encore de signe : après ⌈log⁡2b−aε⌉\left\lceil \log_2 \frac{b - a}{\varepsilon} \right\rceil tours, le milieu est à au plus ε2\frac{\varepsilon}{2} d'un zéro. La méthode de Newton suit la tangente, xn+1=xn−f(xn)f′(xn)x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} : 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 f(x)=0f(x) = 0 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 :

L'essentiel : Poser le problème Extrait gratuit

Un extrait de la fiche « L'essentiel » du chapitre. Les démonstrations sont dans le cours détaillé.

À retenir Avant toute méthode
  • Mettre l'équation sous la forme f(x)=0f(x) = 0, tout du même côté.
  • Existence : ff continue sur [a,b][a, b] et f(a) f(b)≤0f(a)\,f(b) \le 0 ; unicité : ff strictement monotone.
  • Localiser : tracer ff, ou balayer [a,b][a, b] à pas fixe ; un balayage ne voit ni deux zéros proches ni un zéro double.
  • On cherche xx à ε\varepsilon près, pas un xx où f(x)f(x) est petit.

Une méthode du chapitre Extrait gratuit

Un exercice corrigé Extrait gratuit

Dans le chapitre complet

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 offres

Plan du cours

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.

  1. Mettre une équation sous la forme f(x)=0f(x) = 0 et justifier l'existence d'une solution
  2. Choisir un intervalle de départ
  3. Écrire une dichotomie juste
  4. Prouver la terminaison et compter les tours
  5. Prouver la correction par l'invariant de changement de signe
  6. Choisir ε\varepsilon et le test d'arrêt d'une dichotomie
  7. Écrire la méthode de Newton avec un plafond d'itérations
  8. Dérouler Newton à la main et lire la tangente
  9. Choisir et justifier le test d'arrêt de Newton
  10. Remplacer la dérivée par une dérivée approchée et choisir hh
  11. Diagnostiquer un échec de Newton et y remédier
  12. Mesurer une vitesse de convergence
  13. Comparer la dichotomie et Newton
  14. Utiliser bisect et newton de scipy.optimize
  15. Résoudre une équation qui dépend d'un paramètre
  16. Chercher un minimum ou un maximum comme zéro de la dérivée
  17. Traduire une méthode donnée par l'énoncé et contrôler qu'elle s'arrête
  18. 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)

Entraînement (14)

Approfondissement (5)

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.

Questions fréquentes

Comment écrire la méthode de dichotomie en Python ?

On part de a<ba < b avec f(a)f(b)≤0f(a) f(b) \le 0. 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 [a,m][a, m] 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 ε2\frac{\varepsilon}{2} 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 tt tours, la longueur de l'intervalle vaut b−a2t\frac{b - a}{2^t}. La boucle while b - a > eps fait donc exactement ⌈log⁡2b−aε⌉\left\lceil \log_2 \frac{b - a}{\varepsilon} \right\rceil tours si b−a>εb - a > \varepsilon : 20 tours pour un intervalle de longueur 1 et ε=10−6\varepsilon = 10^{-6}, 40 tours pour 10−1210^{-12}. Un chiffre décimal coûte environ 3,32 tours, et diviser ε\varepsilon 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 xn+1=xn−f(xn)f′(xn)x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} depuis x0x_0 et l'on s'arrête dès que ∣xn−xn−1∣≤ε\lvert x_n - x_{n-1}\rvert \le \varepsilon, 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 f(x+h)−f(x−h)2h\frac{f(x + h) - f(x - h)}{2h}, avec un pas hh voisin de 10−510^{-5}, qui ne dépend pas de ε\varepsilon.

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 xx. On n'arrête jamais sur f(m) == 0 seul, qui n'est presque jamais vrai en flottants, ni sur ∣f(m)∣\lvert f(m)\rvert, 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 ff change de signe entre x−εx - \varepsilon et x+εx + \varepsilon. La précision ε\varepsilon 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 ff 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 f(a)f(a) et f(b)f(b) 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.

Toute ta prépa au même endroit

Pour chaque chapitre : le cours, l'essentiel, les méthodes, les pièges, les exercices corrigés, les problèmes de concours, et un assistant qui répond à tes questions. Programmes du Maroc et de France. Avec la plateforme vidéo YOUNESS SCHOOL offerte, dès 600 DH (60 $) par mois, sans engagement.

Prépas scientifiques : voir l'offrePrépas ECS et ECT : voir l'offreTu hésites encore ? Essaie gratuitement Prepa Help.

← Images : matrices de pixels, opérations, convolution