Aller au contenu
ELECTRONICS ENGINEERINGelectronics-engineering.com
Analyse numérique

Recherche de racines : dichotomie, Newton, sécante et point fixe

La dichotomie, la méthode de Newton avec démonstration de la convergence quadratique, la méthode de la sécante, itération de point fixe, Newton pour les systèmes et SPICE.

https://www.electronics-engineering.com/fr/recherche-de-racines-dichotomie-newton/

Pas encore de vote : soyez le premier à noter cette page.

Trouver où une fonction s’annule est l’un des problèmes les plus fréquents : le point de fonctionnement d’une diode dans un circuit (là où l’équation exponentielle de la diode rencontre la droite de charge), la fréquence à laquelle un filtre atténue de 3 dB, l’angle de tir pour atteindre une cible. Pour presque toute équation non linéaire il n’existe pas de formule, donc on procède par itération : on part d’une estimation et on l’améliore jusqu’à ce qu’elle soit assez précise.

La méthode de dichotomie

Si f est continue sur [a, b] et que f(a) et f(b) ont des signes opposés, par le théorème des valeurs intermédiaires de l’Analyse 1 il existe au moins une racine. La dichotomie divise l’intervalle par deux à chaque pas :

  1. calculer le milieu c = (a + b)/2 ;
  2. si f(a) et f(c) ont des signes opposés la racine est dans [a, c], sinon dans [c, b] ;
  3. répéter jusqu’à ce que l’intervalle soit plus petit que la tolérance.

Après n pas l’intervalle a une largeur (b - a)/2^n. Passer d’un intervalle de 1 à une tolérance de 10^{-6} demande 20 pas (2^{20} \approx 10^6). La méthode est lente mais elle converge toujours, et la borne d’erreur est garantie. Elle gagne un chiffre décimal tous les 3.3 pas environ.

La méthode de Newton

L’idée est de remplacer la fonction par sa tangente et de prendre comme nouvelle estimation le point où la tangente coupe l’axe :

    \[ x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)} \]

Les premières itérations de la méthode de Newton avec des tangentes qui s'approchent de la racine
En partant de x_0, la tangente au graphe en x_0 coupe l’axe en x_1 ; la tangente en x_1 donne x_2, et ainsi de suite. Les estimations s’approchent très vite de la racine α.

Exemple : la racine carrée. Avec f(x) = x^2 - a la formule devient x_{k+1} = \frac12\left(x_k + \frac{a}{x_k}\right), la méthode de Babylone. Pour \sqrt2 en partant de x_0 = 3 (comme sur la figure) : 1.8333 ; 1.4621 ; 1.41500 ; 1.4142138 ; 1.41421356237311. Les chiffres décimaux corrects vont 0, 1, 3, 6, 13 : ils doublent à peu près à chaque pas.

Démonstration de la convergence quadratique

Soit \alpha la racine et e_k = x_k - \alpha l’erreur. En développant f avec Taylor autour de x_k, évaluée en \alpha :

    \[ 0 = f(\alpha) = f(x_k) - f'(x_k)\,e_k + \tfrac12 f''(\xi)\,e_k^2 \]

En divisant par f'(x_k) et en utilisant la définition de l’itération, x_k - \frac{f(x_k)}{f'(x_k)} - \alpha = e_{k+1} :

    \[ e_{k+1} = \frac{f''(\xi)}{2f'(x_k)}\,e_k^2 \]

La nouvelle erreur est proportionnelle au carré de l’ancienne : si e_k = 10^{-4}, e_{k+1} est de l’ordre de 10^{-8}. C’est la convergence quadratique, bien plus rapide que la dichotomie, qui est linéaire.

Les limites de Newton

  • Elle demande la dérivée, qui n’est pas toujours disponible.
  • La convergence n’est garantie que si l’on part assez près de la racine. Loin, les tangentes peuvent envoyer l’estimation n’importe où ou la faire osciller : avec f(x) = \arctan x et x_0 = 2 les estimations divergent.
  • Si f'(\alpha) = 0 (une racine double) la convergence devient seulement linéaire.

En pratique on combine les deux méthodes : dichotomie jusqu’à ce que l’intervalle soit petit, puis Newton pour finir en quelques pas. C’est ce que font des fonctions comme fzero de MATLAB ou brentq de SciPy.

La méthode de la sécante

Quand la dérivée n’est pas disponible, on l’approche par le taux d’accroissement des deux dernières estimations :

    \[ x_{k+1} = x_k - f(x_k)\,\frac{x_k - x_{k-1}}{f(x_k) - f(x_{k-1})} \]

La convergence est superlinéaire, d’ordre \frac{1 + \sqrt5}{2} \approx 1.618 (le nombre d’or), et chaque pas ne demande qu’une évaluation de f : elle est souvent plus efficace que Newton.

L’itération de point fixe

Toute équation f(x) = 0 peut se réécrire x = g(x), et un point fixe se cherche avec x_{k+1} = g(x_k). Elle converge si |g'(x)| \lt 1 près de la solution : l’erreur est multipliée par environ |g'(\alpha)| à chaque pas.

Exemple. x = \cos x : en partant d’une valeur quelconque et en appuyant de façon répétée sur la touche cosinus d’une calculatrice (en radians) on arrive à 0.739085…, parce que |g'| = |\sin x| \lt 1 près de la solution. Newton lui-même est une itération de point fixe avec g(x) = x - f/f', qui a g'(\alpha) = 0 : c’est pourquoi elle converge plus vite.

Les systèmes non linéaires

Pour un système \mathbf F(\mathbf x) = \mathbf 0 de n équations à n inconnues, Newton se généralise avec la matrice jacobienne de l’Analyse 2 :

    \[ J(\mathbf x_k)\,\boldsymbol\Delta_k = -\mathbf F(\mathbf x_k),\qquad \mathbf x_{k+1} = \mathbf x_k + \boldsymbol\Delta_k \]

à chaque pas on résout un système linéaire. C’est le cœur de SPICE : pour un circuit avec diodes et transistors, le simulateur linéarise les composants autour de l’estimation courante et résout le système linéaire, en répétant jusqu’à ce que les tensions ne changent plus. Quand une simulation « ne converge pas », c’est Newton qui n’arrive pas à trouver la solution à partir de l’estimation initiale.

Les critères d’arrêt

On s’arrête quand la différence entre deux estimations successives est inférieure à une tolérance, |x_{k+1} - x_k| \lt \text{tol}, ou quand le résidu |f(x_k)| est assez petit, et dans tous les cas après un nombre maximal d’itérations, pour ne pas rester bloqué si la méthode ne converge pas. Un petit résidu seul ne suffit pas : si la fonction est très plate près de la racine, |f| peut être minuscule même loin de la solution.

S’abonner
Notifier de
guest
1 commentaire
Le plus ancien
Plus récent Les plus votés
1
0
Vous avez apprécié cet article ? Merci de laisser un commentaire.x