Résolution d'équations non linéaires

11.1 Introduction et Ordre de Convergence

Dans ce chapitre, nous nous intéressons à l'approximation des zéros d'une fonction réelle d'une variable réelle. Étant donné un intervalle $I\subset \mathbb{R}$ et une application continue $f:I\to \mathbb{R}$, on cherche à calculer une valeur approchée de $c\in I$ telle que $f(c)=0$.

Toutes les méthodes de résolution présentées sont des méthodes itératives. Elles consistent à construire une suite de valeurs $(x_n{)}_{n\in \mathbb{N}}$ qui converge vers la racine $c$. La vitesse de convergence de la suite détermine la qualité et la performance pratique de l'algorithme.

Lien avec la précision décimale

Si ${\delta }_n=-{\log }_{10}(e_n)$ désigne le nombre de décimales exactes à l'étape $n$, alors pour $n$ assez grand :

$${\delta }_{n+1}\approx r{\delta }_n-{\log }_{10}(\mu )$$

• Convergence linéaire ($r=1$) : ${\delta }_{n+1}\approx {\delta }_n-{\log }_{10}(\mu )$. Le nombre de décimales augmente de façon additive. Pour la dichotomie ($\mu =1/2$), on gagne $-{\log }_{10}(1/2)\approx 0.301$ décimale par itération (soit 1 décimale toutes les 3 itérations).
• Convergence quadratique ($r=2$) : ${\delta }_{n+1}\approx 2{\delta }_n-{\log }_{10}(\mu )$. Le nombre de décimales exactes est doublé à chaque étape (la précision passe par exemple de 4 à 8 puis 16 décimales).

Critères d'Arrêt

En pratique, on doit arrêter le processus itératif lorsque l'approximation est jugée satisfaisante. On utilise principalement trois critères :

• Nombre maximal d'itérations : évite les boucles infinies en cas de divergence.
• Tolérance sur l'incrément : $|x_{n+1}-x_n|\le \epsilon$.
• Tolérance sur le résidu : $|f(x_n)|\le \epsilon$.

11.2 Méthode de la Fausse Position (Regula Falsi)

La méthode de la fausse position est une alternative à la dichotomie. Plutôt que de diviser l'intervalle $[u_n,v_n]$ systématiquement par son milieu, on calcule l'intersection de la droite sécante reliant $(u_n,f(u_n))$ et $(v_n,f(v_n))$ avec l'axe des abscisses.

L'abscisse de cette intersection $x_n$ s'écrit :

$$x_n=\frac{u_{n}f(v_n)-v_{n}f(u_n)}{f(v_n)-f(u_n)}$$

L'algorithme de recherche itère alors les bornes $(u_n,v_n)$ en posant $u_0=a$, $v_0=b$ et :

$$(u_{n+1},v_{n+1})=\{\begin{array}{ll}(u_n,x_n)& \text{si }f(u_n)f(x_n)\le 0\\ (x_n,v_n)& \text{sinon}\end{array}$$

Contrairement à la dichotomie, la largeur de l'intervalle $v_n-u_n$ ne tend pas nécessairement vers 0. C'est le cas par exemple si la fonction est strictement convexe : l'une des bornes reste fixe (stationnaire) tandis que l'autre converge vers la racine $c$.

def regula_falsi(f, a, b, epsilon=1e-12, maxiter=100):
    """
    Methode de la fausse position.
    """
    if f(a) * f(b) > 0:
        raise ValueError("f(a) et f(b) doivent être de signes opposés")

    u, v = a, b
    for n in range(maxiter):
        # Calcul du point d'intersection
        x = (u * f(v) - v * f(u)) / (f(v) - f(u))

        if abs(f(x)) < epsilon or abs(v - u) < epsilon:
            return x

        if f(u) * f(x) <= 0:
            v = x
        else:
            u = x

    raise RuntimeError(f"Non convergence après {maxiter} itérations")

11.3 Méthode de Newton-Raphson

La méthode de Newton-Raphson s'affranchit de la contrainte d'encadrement en procédant par approximations successives basées sur la tangente locale à la courbe.

11.3.1 Principe de l'Algorithme

À l'étape $x_n$, on modélise la fonction par son approximation affine tangente :

$${\phi }_n(x)=f(x_n)+f^{\prime }(x_n)(x-x_n)=0$$

L'intersection avec l'axe $y=0$ donne la valeur suivante $x_{n+1}$ :

La suite de Newton-Raphson est définie par la relation de récurrence :

$$x_{n+1}=x_n-\frac{f(x_n)}{f^{\prime }(x_n)}$$

11.3.2 Théorème de Convergence Quadratique

11.3.3 Application : Méthode de Héron (Racine Carrée)

Calculer la racine carrée $\sqrt{\alpha }$ d'un nombre réel $\alpha >0$ revient à chercher la racine positive de $f(x)=x^2-\alpha =0$. La suite de Newton associée s'écrit :

$$x_{n+1}=\frac{1}{2}\left(x_n+\frac{\alpha }{x_n}\right)$$

def heron(alpha, x0=None, tol=1e-12, maxiter=100):
    """
    Calcule sqrt(alpha) par la methode de Heron (Newton pour x**2 - alpha = 0).
    """
    if x0 is None:
        x0 = alpha if alpha >= 1 else 1.0

    x = x0
    for n in range(maxiter):
        x_new = 0.5 * (x + alpha / x)
        if abs(x_new - x) < tol:
            return x_new
        x = x_new

    raise RuntimeError(f"Non convergence après {maxiter} itérations")

# Exemple
print(heron(2))   # 1.414213562373095
print(heron(10))  # 3.1622776601683795

11.3.4 Dangers et Limites de Newton

• Convergence uniquement locale : Si $x_0$ est trop éloigné, une divergence est possible.
• Dérivée nulle : Si $f^{\prime }(c)=0$ (racine de multiplicité $m\ge 2$), la convergence de Newton devient simplement linéaire. On peut restaurer l'ordre quadratique en modifiant la formule :

$$x_{n+1}=x_n-m\frac{f(x_n)}{f^{\prime }(x_n)}$$

• Cycle : Pour certaines fonctions, la méthode de Newton peut osciller indéfiniment sans converger.

11.4 Dérivée Numérique et Choix du Pas

Pour appliquer Newton-Raphson sans connaître analytiquement la dérivée $f^{\prime }$, on l'approxime par un taux de variation avec un pas $h$ petit.

11.4.1 Différences Finies

11.4.2 Le Choix Optimal du Pas $h$

Intuitivement, on pourrait penser qu'il faut choisir le pas $h$ le plus petit possible. En informatique binaire, c'est faux en raison du compromis entre :

• L'erreur de troncature (mathématique) : due aux termes négligés dans le développement de Taylor.
• L'erreur d'arrondi (machine) : due à la soustraction de deux valeurs proches (cancellation), de l'ordre de $\frac{2\epsilon |f(x)|}{h}$ où $\epsilon \approx 2.22\cdot 10^{-16}$.

Pour la différence en avant, l'erreur totale est $E(h)\approx \frac{2\epsilon |f(x)|}{h}+\frac{h}{2}|f^{\prime \prime }(x)|$. L'étude des variations montre que cette erreur est minimale pour :

$$h_{opt}\approx \sqrt{\epsilon }\approx 10^{-8}$$

Pour la différence centrée, l'erreur totale est $E(h)\approx \frac{2\epsilon |f(x)|}{h}+\frac{h^2}{6}|f^{\prime \prime \prime }(x)|$, avec un optimum :

$$h_{opt}\approx \sqrt[3]{\epsilon }\approx 10^{-5}$$

def derivee_centree(f, x, h=1e-5):
    """Approximation de la dérivée par différence centrée."""
    return (f(x + h) - f(x - h)) / (2 * h)

11.5 Méthode de la Sécante

La méthode de la sécante évite d'avoir à évaluer la dérivée $f^{\prime }(x_n)$ en la remplaçant par la pente de la corde reliant les deux points précédents $(x_{n-1},f(x_{n-1}))$ et $(x_n,f(x_n))$.

La suite est définie par la formule de récurrence :

$$x_{n+1}=x_n-\frac{x_n-x_{n-1}}{f(x_n)-f(x_{n-1})}f(x_n)$$

Cette méthode requiert deux points initiaux $x_0$ et $x_1$.