I1 — Calcul numérique

Objectif du chapitre. Apprendre à résoudre numériquement des équations (dichotomie, Newton), à intégrer une fonction par rectangles et trapèzes (Simpson en complément) et à résoudre une équation différentielle par la méthode d'Euler. Ce chapitre applique les bases Python du chapitre I1 — Bases Python et représentation des nombres et la complexité du chapitre I1 — Algorithmes et complexité.

Notions

1. Résolution d'équation : dichotomie

Pour résoudre $f(x) = 0$ avec une fonction continue strictement monotone sur $[a, b]$ (avec $f(a)\,f(b) < 0$, c'est-à-dire un changement de signe), la dichotomie divise l'intervalle en deux ; on garde la moitié où le produit des signes est négatif ; on itére jusqu'à ce que l'intervalle soit suffisamment petit ; la complexité est $O(\log \frac{b-a}{\varepsilon})$ (convergence linéaire).

Exemple (dichotomie). Pour résoudre $f(x) = x^2 - 2 = 0$ sur $[1, 2]$ ($f(1) = -1$, $f(2) = 2$) : $x_0 = 1{,}5$, $f(1{,}5) = 0{,}25 > 0$ ; on garde $[1, 1{,}5]$ ; $x_1 = 1{,}25$, $f(1{,}25) = -0{,}4375 < 0$ ; on garde $[1{,}25, 1{,}5]$ ; ... la suite converge vers $\sqrt{2} \approx 1{,}414$ ; la complexité est $O(\log \frac{1}{\varepsilon})$.

def dichotomie(f, a, b, eps=1e-9):
    while b - a > eps:
        m = (a + b) / 2
        if f(a) * f(m) <= 0:
            b = m
        else:
            a = m
    return (a + b) / 2

2. Résolution d'équation : Newton

La méthode de Newton part d'une valeur initiale $x_0$ et itére : $x_{n+1} = x_n - \dfrac{f(x_n)}{f'(x_n)}$ ; la convergence est quadratique (le nombre de chiffres corrects double à chaque itération) si $x_0$ est suffisamment proche de la racine ; elle échoue si $f'(x_n) \approx 0$ ou si $x_0$ est trop loin.

def newton(f, fp, x0, eps=1e-12, maxit=100):
    x = x0
    for _ in range(maxit):
        x1 = x - f(x) / fp(x)
        if abs(x1 - x) < eps:
            return x1
        x = x1
    return x

3. Intégration numérique

L'intégration par rectangles approxime $\int_a^b f(x)\,dx$ par $\sum_{i=0}^{n-1} f(x_i)\,\Delta x$ (complexité $O(n)$, erreur $O(\Delta x)$) ; l'intégration par trapèzes approxime par $\dfrac{\Delta x}{2}\left(f(x_0) + 2\sum_{i=1}^{n-1} f(x_i) + f(x_n)\right)$ (erreur $O(\Delta x^2)$) ; l'intégration de Simpson (paraboles, complément) a une erreur $O(\Delta x^4)$ (plus précise).

def trapèzes(f, a, b, n):
    h = (b - a) / n
    s = (f(a) + f(b)) / 2
    for i in range(1, n):
        s += f(a + i * h)
    return s * h

4. Équations différentielles : Euler

La méthode d'Euler résout numériquement $y' = f(t, y)$, $y(t_0) = y_0$ ; elle itére : $y_{n+1} = y_n + h\,f(t_n, y_n)$, $t_{n+1} = t_n + h$ ; la précision dépend du pas $h$ (erreur $O(h)$) ; des méthodes plus précises (Runge-Kutta, complément) réduisent l'erreur ($O(h^4)$ pour RK4).

def euler(f, t0, y0, tf, h):
    t, y = t0, y0
    while t < tf:
        y = y + h * f(t, y)
        t = t + h
    return y

Lien avec M4

La méthode d'Euler est la version numérique de la résolution des équations différentielles du chapitre M4 — Techniques fondamentales de calcul en analyse : quand la solution exacte n'est pas accessible, on approxime la courbe intégrale par petits pas.

Capacités exigibles

Ce chapitre met en œuvre les capacités de l'IPT : on évalue la complexité des algorithmes numériques (I1.complexite-algorithme) et on implémente la dichotomie (I1.dichotomie) pour la résolution d'équation. Les deux capacités sont traitées en détail dans le chapitre I1 — Algorithmes et complexité.

Ce qui tombe en colle et en DS

• Résoudre $f(x) = 0$ par dichotomie (condition de changement de signe, nombre d'itérations).
• Comparer dichotomie et Newton (vitesse de convergence, conditions de succès).
• Approximer une intégrale par trapèzes et estimer l'erreur.

Pièges classiques

• Newton : convergence : la méthode de Newton converge quadratiquement seulement si $x_0$ est suffisamment proche de la racine ; il ne faut pas supposer qu'elle converge toujours ; elle échoue si $f'(x_n) \approx 0$ (division par zéro) ou si $x_0$ est trop loin ; il faut ajouter un critère d'arrêt (tolérance sur $|f(x_n)|$ ou nombre max d'itérations).
• Dichotomie : condition de départ : la dichotomie exige $f(a)\,f(b) < 0$ (changement de signe) ; si $f(a)$ et $f(b)$ ont le même signe, l'algorithme n'est pas garanti (il peut converger vers une racine hors de $[a, b]$ ou diverger) ; il faut choisir un intervalle qui encadre la racine.
• Euler : pas h : la précision de Euler dépend du pas $h$ ; un pas trop grand donne une approximation mauvaise (et peut diverger) ; il faut choisir $h$ assez petit (mais pas trop petit : l'erreur d'arrondi s'accumule et le temps de calcul augmente).

Pour aller plus loin

Annales utilisables sur ce chapitre : voir la page générale Ressources, exercices et annales pour les manuels recommandés et les banques d'exercices gratuites.