Résolution numérique d'équations non-linéaires

28 Sep 2019, 07:20

cours / ananum / python

L’objectif que nous nous fixons ici est de présenter quelques méthodes numériques pour la recherche des zéros d’une fonction non-linéaire \(f\).

Par exemple, dans la figure suivante nous représentons graphiquement une fonction non-linéaire ainsi que ses zéros trouvés de manière numérique.

Pour formaliser les notations, on considère la définition suivante des zéros d’une fonction.

Définition

Soit \(f : \mathbb{\Omega} \subset \mathbb{R}^N \to \mathbb{R}^N\) avec \(\Omega\) un domaine de \(\mathbb{R}^N\). On dit que \(\alpha \in \Omega\) est un zéro de \(f\) si \(f(\alpha) = 0_{\mathbb{R}^N}\).

Il est naturel de se poser la question de l’existence des zéros:

un ou plusieurs zéros?
comment déterminer les zéros d’une fonction en sachant qu’un calcul exact il est rarement possible?

En général, on approche les zéros des fonctions non-linéaires à l’aide des méthodes itératives. Plus précisément, soit \(f : I \to \mathbb{R}\), \(I\) un intervalle de \(\mathbb{R}\) et supposons que \(f\) admet au moins un zéro \(\alpha \in I\). Calculer une valeur approchée de \(\alpha\) par une méthode itérative consiste à construire une suite récurrente \((x_n)_n\) de \(I\) convergeant vers \(\alpha\).

Plusieurs critères d’arrêt existent :

\begin{equation} \color{blue}{|f(x_{n + 1})| < \varepsilon} \text{ ou } \color{blue}{|x_{n + 1} - x_{n}| < \varepsilon} \text{ ou } \color{blue}{\dfrac{|x_{n + 1} - x_{n}|}{|x_{n + 1}|} < \varepsilon}, \end{equation}

pour un \(\varepsilon > 0\) donné. Plus exactement, on construit des termes de la suite \((x_n)_n\) jusqu’à un de ces critères d’arrêt est validé.

Une fois qu’on sait que la suite \(x_n\) converge vers le zéro \(\alpha\) de \(f\), il est pertinent de quantifier la vitesse de convergence de la suite et, donc, de la méthode d’approximation.

Définition

Soit \((x_n)_{n \in \mathbb{N}}\) une suite convergeant vers \(\alpha\) tel que \(f(\alpha) = 0\). Soit \(p \in \mathbb{N}^*\). S’il existe \(C > 0\) et \(n_0 \in \mathbb{N}\) tels que \[\forall n \ge n_0, \quad |x_{n + 1} - \alpha| \le C |x_n - \alpha|^p,\] on dit que la convergence est d’ordre au moins \(p\).

Si \(p = 1\) on dit que la convergence est linéaire et si \(p = 2\) la convergence et quadratique:

\(p = 1\) : convergence linéaire \[\forall n \ge 0, \quad |x_{n + 1} - \alpha| \le C |x_n - \alpha|\]
\(p = 2\) : convergence quadratique \[\forall n \ge 0, \quad |x_{n + 1} - \alpha| \le C |x_n - \alpha|^2.\]

Si la limite

\begin{equation} \lim\limits_{n \to \infty} \dfrac{|x_{n+1} - \alpha|}{|x_n - \alpha|^p} \end{equation}

existe et elle est finie, alors la convergence est d’ordre au moins \(p\).

Définition

S’il existe une suite \((c_n)\) qui converge à 0 telle que \[\forall n \ge n_0, \quad |x_{n + 1} - \alpha| \le c_n |x_n - \alpha|\] on dit que la convergence est surlinéaire.

Il existe plusieurs méthodes classique d’approximation des zéros. Nous allons présenter les méthodes suivantes:

méthode de la dichotomie
méthode de la fausse position
méthode de point fixe
méthode de Newton.

Méthode de la dichotomie

On rappel d’abord un très connu résultat donnant l’existence d’un zéro pour les fonctions continues changeant de signe: le théorème des valeurs intermédiaires.

Théorème

Soit \(f : [a, b] \to \mathbb{R}\), une fonction continue sur \([a, b]\). Supposons \(f(a)f(b) < 0\).

Alors il existe \(\alpha \in ]a, b[\) tel que \(f(\alpha) = 0\).

La méthode de la dichotomie permet d’approcher un zéro d’une fonction vérifiant les hypothèses du théorème des valeurs intermédiaires. Voici une illustration graphique de cette méthode.

L’idée de la méthode peut être résumé par:

on prend \(c = \dfrac{a + b}{2}\)
si \(f( c)f(a) < 0\) \[\color{red}{b = c}\]
si \(f( c)f(b) < 0\) alors le zéro \(\alpha\) de \(f\) est à chercher dans \(]c, b[\) \[\color{red}{a = c}.\]
aller au point 1. si on n’a pas convergé.

Plus précisément, nous allons construire trois suites récurrentes \((a_n)_{n \ge 0}\), \((b_n)_{n \ge 0}\) et \((c_n)_{n \ge 0}\) définies comme suit:

\(a_0 = a\), \(b_0 = b\)
Pour tout \(n \ge 0\):
- \(c_n = \dfrac{a_n + b_n}{2}\)
- si \(f(c_n) = 0\) alors \(a_{n + 1} = a_n\), \(b_{n + 1} = b_n\)
- si \(f(c_n)f(a_n) < 0\) alors \(a_{n+1} = a_n\), \(b_{n + 1} = c_n\)
- si \(f(c_n)f(b_n) < 0\) alors \(a_{n+1} = c_n\), \(b_{n + 1} = b_n\).

Théorème

Soit \(f : [a, b] \to \mathbb{R}\), une fonction continue sur \([a, b]\) telle que \(f(a)f(b) < 0\). Alors la suite \((c_n)_n\) définie par la méthode de la dichotomie converge vers un zéro \(\alpha \in ]a, b[\) de \(f\).

L’idée de la preuve est de montrer que les suites \((a_n)_n\) et \((b_n)_n\) sont adjacentes. Elles convergent donc vers la même limite, notée \(\beta\). En utilisant le théorème d’encadrement, on a \[\lim_{n \to \infty} c_n = \beta.\] finalement, on obtient \(f(\beta) = 0\) en passant à la limite pour la suite \((f(a_n)f(b_n))_n\).

De point de vue algorithmique, la méthode de la dichotomie peut être synthétisée comme suit:

Données : \(f\), \(a\), \(b\), \(\epsilon\), nmax
\(c = (a + b) / 2\)
\(n = 1\)
tant que \(|f( c)| \ge \epsilon\) et \(n \le\) nmax:
\(\qquad\) si \(f(a)f( c) < 0\) :
\(\qquad\qquad\) \(b = c\)
\(\qquad\) sinon:
\(\qquad\qquad\) \(a = c\)
\(\qquad\) \(n = n + 1\)
\(\qquad\) \(c = (a + b) / 2\)
si \(|f( c)| < \epsilon\) :
\(\qquad\) donner \(c\)
sinon:
\(\qquad\) afficher “Non convergence en nmax itérations”

Remarquer que pour la construction de la suite \((c_n)\) seuls les signes de \(f(a_n)\) et \(f(b_n)\) sont utilisés (et pas les valeurs de \(f(a_n)\) et \(f(b_n)\)). La méthode de la dichotomie est inapplicable pour chercher un zéro sans changement de signe de \(f\). De plus, si on sait que dans \([a,b]\) il n’existe qu’un zéro \(\alpha\) de \(f\), on a un contrôle de l’erreur : \[\forall n \in \mathbb{N}, \quad |c_n - \alpha| < \frac{1}{2^{n + 1}}(b-a).\] Cela donne une convergence de la méthode de la dichotomie plutôt “lente”.

Méthode de la fausse position

Comme la méthode de la dichotomie, la méthode de la fausse position construit une suite récurrente pour approcher un zéro d’une fonction continue qui change de signe sur un intervalle. Voici une illustration graphique de la méthode :

Le principe de la méthode peut être résumé par:

\(w = a - f(a) \dfrac{b - a}{f(b) - f(a)}\)
si \(f(w)f(a) < 0\) alors \(\alpha \in ]a, w[\) \[\color{red}{b = w}.\]
si \(f(w)f(b) < 0\) alors \(\alpha \in ]w, b[\) \[\color{red}{a = w}.\]
aller au point 1. si on n’a pas convergé.

Plus précisément, nous allons construire trois suites récurrentes \((a_n)_{n \ge 0}\), \((b_n)_{n \ge 0}\) et \((w_n)_{n \ge 0}\) définies comme suit:

\(a_0 = a\), \(b_0 = b\)
Pour tout \(n \ge 0\):
- \(w_n = a_n - f(a_n) \dfrac{b_n - a_n}{f(b_n) - f(a_n)}\)
- si \(f(w_n) = 0\) alors \(a_{n + 1} = a_n\), \(b_{n + 1} = b_n\)
- si \(f(w_n)f(a_n) < 0\) alors \(a_{n+1} = a_n\), \(b_{n + 1} = w_n\)
- si \(f(w_n)f(b_n) < 0\) alors \(a_{n+1} = w_n\), \(b_{n + 1} = b_n\).

Nous pouvons démontrer le résultat de convergence suivant:

Théorème

Soit \(f \in C^2([a, b], \mathbb{R})\), telle que \(f(a)f(b) < 0\). Supposons que \(f^″\) est de signe constant sur \([a, b]\).

Alors la suite \((w_n)_{n \in \mathbb{N}}\) définie par la méthode de la fausse position converge vers l’unique zéro \(\alpha \in ]a, b[\) de \(f\).

Méthode de point fixe

L’idée de la méthode de point fixe est d’écrire le problème de recherche d’un zéro de \(f\) comme un problème de recherche d’un point fixe d’une autre fonction \(g\).

Exemple

On peut choisir la fonction \(g\) de différentes manières. Voici le deux choix les plus fréquentes:

\(g(x) = x - f(x)\)
\(g(x) = x - \lambda f(x)\) avec \(\lambda \neq 0\).

Le principe de la méthode de point fixe est de construire une suite itérative \((x_n)_{n \in \mathbb{N}}\) de la manière suivante:

\begin{equation} \left\{ \begin{array}{l} x_0 \in \mathbb{R} \\ x_{n + 1} = g(x_n), \quad \forall n \in \mathbb{N} \end{array} \right. \end{equation}

Il est facile à voire que si \(g\) est continue et si \(\lim x_n = \alpha\) alors \(\alpha = g(\alpha)\). Il faudra, donc, donner des conditions (les moins restrictives possible) pour que la suite \((x_n)_{n \in \mathbb{N}}\) converge.

Exemple : On peut mettre en évidence plusieurs comportements différents de la méthode de point fixe en fonction des valeurs de la dérivée de \(g\) (si \(g\) est dérivable).

Si \(\boldsymbol{0 < g’(x) < 1}\) pour tout \(x \in I\) la suite \((x_n)\) donnée par la méthode de point fixe a un comportement similaire à celui illustré dans la figure suivante:
Si \(\boldsymbol{1 < g’(x)}\) pour tout \(x \in I\) la suite \((x_n)\) donnée par la méthode de point fixe a un comportement similaire à celui illustré dans la figure suivante:
Si \(\boldsymbol{-1 < g’(x) < 0}\) pour tout \(x \in I\) la suite \((x_n)\) donnée par la méthode de point fixe a un comportement similaire à celui illustré dans la figure suivante:
Si \(\boldsymbol{g’(x) < -1}\) pour tout \(x \in I\) la suite \((x_n)\) donnée par la méthode de point fixe a un comportement similaire à celui illustré dans la figure suivante:

Une notion qui couvrira les deux cas précédents (\(|g’(x)| < 1\)) pour lesquels on a la convergence de la méthode de point fixe est la notion d’application contractante.

Définition

Soit \(g : I \subset \mathbb{R} \to \mathbb{R}\).

On dit que \(g\) est une application contractante sur \(I\) s’il existe \(0 \le K < 1\) tel que

\begin{equation} \forall x, y \in I \quad |g(x) - g(y)| \le K |x- y|. \end{equation}

Il est facile à démontrer que si \(g\) est contractante alors \(g\) est continue. De plus, en utilisant le théorème de accroissements finis on peut démontrer que si \(g\) est une fonction de classe \(C^1\) sur l’ensemble fermé, borné et non-vide \(I\) et s’il existe \(0 \le K < 1\) tel que \[|g’(x)| \le K \qquad \forall x \in I\] alors \(g\) est contractante. Une propriété remarquable des fonctions contractantes invariant un ensemble fermé et non-vide et le théorème de Banach de point fixe.

Théorème de Banach de point fixe

Soit \(g : I \subset \mathbb{R} \to \mathbb{R}\). On suppose :

\(I\) est un fermé non-vide,
\(g(I) \subset I\), \((\forall x \in I,\ g(x) \in I)\),
\(g\) est contractante sur \(I\). Il existe donc \(0 \le K < 1\) telle que pour tout \(x,\ y \in I\) on a \[|g(x) - g(y)| \le K |x - y|.\]

Alors, \(g\) admet un unique point fixe \(\alpha \in I\).

Démonstration. Démontrons d’abord l’unicité du point fixe. Supposons qu’il existe deux points fixes distincts \(\alpha, \beta \in I\): \[\left\{ \begin{array}{l} g(\alpha) = \alpha \\ g(\beta) = \beta \end{array}\right. \qquad \alpha \ne \beta.\]

Montrons maintenant l’existence d’un point fixe. Pour cela nous allons construire une suite \((x_n)_{n \ge 0}\) définie par \[\left\{ \begin{array}{l}x_0 \in I\\ x_{n + 1} = g(x_n), \qquad n \ge 0. \end{array}\right.\] Nous allons montrer que la suite \((x_n)_{n \ge 0}\) est une suite de Cauchy. Pour tout \(n \ge 0\), on a

\begin{align*} |x_{n + 1} - x_n| & = |g(x_n) - g(x_{n - 1})| \le K |x_n - x_{n - 1}| \\ & = K |g(x_{n-1}) - g(x_{n - 2})| \le K^2 |x_{n-1} - x_{n - 2}| \\ & = \ \dots \\ & = K^{n - 1} |g(x_{1}) - g(x_{0})| \le K^n |x_1 - x_0|. \end{align*}

De plus, pour tout \(n \ge 0\) et \(p \ge 1\) nous avons

\begin{align*} |x_{n + p} - x_n| & = \left| \sum_{i = 0}^{p-1} (x_{n + p - i} - x_{n + p - i - 1}) \right| \\ & \le \sum_{i = 0}^{p-1} |x_{n + p - i} - x_{n + p - i - 1}| \\ & \le \sum_{i = 0}^{p-1} K^{n + p - i - 1} |x_1 - x_0| \\ & = K^n |x_1 - x_0| \sum_{i = 0}^{p - 1} K^i = \frac{1 - K^p}{1 - K} K^n |x_1 - x_0| \\ & \le \frac{K^n}{1 - K} |x_1 - x_0| \to 0 \text{ quand } n \to +\infty. \end{align*}

Alors, la suite \((x_n)_{n \ge 0}\) est une suite de Cauchy de nombres réels, donc \((x_n)_{n \ge 0}\) converge. Soit \(\alpha\) sa limite. Comme \(g(I) \subset I\), tous les termes de la suite \((x_n)_{n \ge 0}\) restent dans I. En rappelant l’hypothèse que \(I\) est fermé, il suit que \(\alpha \in I\). Mais \(g\) est continue (car contractante). En passant à la limite dans la relation de récurrence qui définit la suite \((x_n)_{n \ge 0}\) on déduit que \(g(\alpha) = \alpha\), c’est-à-dire \(\alpha\) et un point fixe de \(g\).

Remarque

Les outils employés pour la preuve du théorème précédent ne sont pas spécifiques au fait que la fonction \(g\) est une fonction définie sur un ensemble \(I \subset \mathbb{R}\). Le résultat reste vrai si \(I\) est un fermé de \(\mathbb{R}^N\) en remplaçant les valeurs absolues par des normes. En fait, le résultat reste vrai dans tout espace vectoriel normé qui a la propriété que les suites de Cauchy convergent. On appelle un tel espace un espace de Banach. Ces espaces doivent leur nom au mathématicien polonais Stefan Banach.

Le résultat suivant est une conséquence directe du théorème de point fixe de Banach.

Théorème (convergence globale)

Soit \(g : I \subset \mathbb{R} \to \mathbb{R}\). On suppose :

\(I\) est un fermé non-vide de \(\mathbb{R}\),
\(g(I) \subset I\): \((\forall x \in I, \ g(x) \in I)\),
\(g\) est contractante sur \(I\) de constante de contraction \(0 \le K < 1\).

Alors, la suite \((x_n)_{n \in \mathbb{N}}\) définie par \(x_{n + 1} = g(x_n)\) et \(x_0 \in I\) donné converge vers l’unique point fixe \(\alpha \in I\) de \(g\). De plus,

\begin{align} \forall n \in \mathbb{N}, \quad |x_n - \alpha| \le \frac{K^{n}}{1 - K} |x_1 - x_0|, \\ \forall n \in \mathbb{N}, \quad |x_{n + 1} - \alpha| \le \frac{K}{1 - K} |x_{n + 1} - x_n|. \end{align}

Démonstration. Le fait que la suite \((x_n)_{n \ge 0}\) converge vers l’unique point fixe de \(g\) est exactement le théorème de point fixe de Banach. Il reste donc à démontrer les deux estimations d’erreur.

Commençons par la première estimation.

\begin{align*} |x_{n} - \alpha| & = |g(x_{n-1}) - g(\alpha)| \le K |x_{n-1} - \alpha| \\ & = K |g(x_{n - 2}) - g(\alpha)| \le K^2 |x_{n - 2} - \alpha| \\ & \dots \\ & = K^{n - 1} |g(x_0) - g(\alpha)| \le K^n |x_0 - \alpha|. \end{align*}

Mais

\begin{align*} |x_0 - \alpha| & = |x_0 - x_1 + x_1 - \alpha| \\ & \le |x_0 - x_1| + |x_1 - \alpha | = |x_0 - x_1| + |g(x_0) - g(\alpha)| \\ & \le |x_0 - x_1| + K |x_0 - x_\alpha|, \end{align*}

d’où \((1 - K)|x_0 - \alpha| \le |x_0 - x_1|\). Il suit donc que \[ |x_0 - \alpha| \le \frac{1}{1 - K} |x_0 - x_1| \] et, donc, \[ |x_n - \alpha| \le \frac{K^n}{1 - K} |x_0 - x_1|. \]

Pour la deuxième partie de la preuve on commence par évaluer \(|x_{n+1} - \alpha|\):

\begin{align*} |x_{n+1} - \alpha| & = |g(x_n) - g(\alpha)| \\ & \le K |x_n - \alpha| = K |x_n - x_{n+1} + x_{n+1} - \alpha| \\ & \le K |x_{n + 1} - x_n| + K |x_{n + 1} - \alpha|. \end{align*}

On obtient immédiatement que \[(1 - K) |x_{n + 1} - \alpha| \le K |x_{n+1} - x_n|,\] et, en prenant en compte que \(1 - K >0\), la preuve est finie.

Nous démontrons le résultat suivant de convergence locale pour la méthode de point fixe.

Théorème (convergence locale)

Soit \(g : I \subset \mathbb{R} \to \mathbb{R}\). On suppose :

\(g\) de classe \(C^1\) sur \(I\),
\(g\) possède un point fixe \(\alpha\) situé à l’intérieur de \(I\),
\(|g’(\alpha)| < 1\).

Alors, il existe \(\rho > 0\) tel que la suite \((x_n)_{n \in \mathbb{N}}\) définie par \(x_{n + 1} = g(x_n)\) et \(x_0 \in [\alpha - \rho, \alpha + \rho]\) est bien définie, reste dans \([\alpha - \rho, \alpha + \rho]\) et converge vers \(\alpha\).

Démonstration.

La première étape de la preuve est de montrer qu’il existe \(\rho > 0\) tel que \(g\) soit une contraction sur l’intervalle fermé \([\alpha - \rho, \alpha + \rho]\). Comme \(g’\) est continue sur \(I\) (car de classe \(C^1\)) et \(|g’(\alpha)| < 1\), alors il existe \(\rho > 0\) tel que \(|g’(x)| < 1\) pour tout \(x \in [\alpha - \rho, \alpha + \rho]\). Soient \(x, y \in [\alpha - \rho, \alpha + \rho]\) distincts. La fonction \(g\) vérifie les hypothèses du théorème des accroissements finis. Il existe donc \(\xi_{x,y}\) compris entre \(x\) et \(y\) tel que

\[ \frac{g(x) - g(y)}{x - y} = g’(\xi_{x,y}). \]

Alors

\[ |g(x) - g(y)| = |g’(\xi_{x,y})| |x - y| \le \max_{\xi \in [\alpha - \rho, \alpha + \rho]} |g’(\xi)| |x - y|.\]

Mais \[ K = \max_{\xi \in [\alpha - \rho, \alpha + \rho]} |g’(\xi)| < 1, \]

donc \(g\) est une contraction de constante \(K\). De plus, \(g([\alpha - \rho, \alpha + \rho]) \subset [\alpha - \rho, \alpha + \rho]\). Effectivement, soit \(x \in [\alpha - \rho, \alpha + \rho]\). Alors \(|x - \alpha| \le \rho\) et donc \[ |g(x) - \alpha| = |g(x) - g(\alpha)| \le K|x - \alpha| \le K \rho < \rho,\] ce qui n’est rien d’autre que \(g(x) \in [x - \rho, x + \rho]\).

La fonction \(g\) est donc une fonction contractante sur l’intervalle fermé \([\alpha - \rho, \alpha + \rho]\). De plus, \(g([\alpha - \rho, \alpha + \rho]) \subset [\alpha - \rho, \alpha + \rho]\). On peut alors appliquer le théorème de point fixe de Banach pour obtenir la convergence de la suite \((x_n)_{n \ge 0}\) vers le point fixe \(\alpha\).

Pour le théorème de convergence globale il faut que \(g\) soit contractante sur l’intégralité de \(I\). On obtient alors que la méthode de point fixe converge convergence pour tout \(x_0\) dans \(I\). Le résultat de convergence locale se réduit finalement au fait que \(g\) est contractante au voisinage de \(\alpha\). Alors, dans ce cas la convergence a lieu pour \(x_0\) proche de \(\alpha\). Dans les deux cas, on a

\begin{equation} \forall n \in \mathbb{N}, \quad |x_{n + 1} - \alpha| \le K|x_n - \alpha|, \end{equation}

donc on a au moins une convergence linéaire.

Cas particulier:

Soit \(g \in C^2(I, \mathbb{R})\) tel que \(g’(\alpha) = 0\) avec \(\alpha\) un point fixe.

A l’aide du théorème de Taylor-Lagrange on a:

\begin{equation} g(x_n) = g(\alpha) + g’(\alpha)(x_n - \alpha) + g^{\prime\prime}(\xi_n) \frac{(x_n - \alpha)^2}{2} \end{equation}

et donc la convergence de la méthode de point fixe et au moins quadratique.

Méthode de Newton

Le principe de la méthode de Newton est illustré graphiquement dans la figure suivante.

La méthode de Newton pour approcher un zéro de la fonction dérivable \(f\) consiste en construire une suite récurrente \((x_n)_{n \in \mathbb{N}}\) définie par

\begin{equation} \left\{ \begin{array}{l} x_0 \text{ donné, proche du zéro à approcher} \\ x_{n + 1} = x_n - \dfrac{f(x_n)}{f’(x_n)}, \quad \forall n \in \mathbb{N} \end{array} \right. \end{equation}

Autrement dit, on définit \(x_{n+1}\) à partir de \(x_n\) comme l’intersection de la droite tangente au graphique de la fonction \(f\) au point \((x_n, f(x_n))\) avec l’axe \(Ox\).

On démontre le théorème suivant de convergence locale.

Théorème

Soit \(f \in \mathcal{C}^2([a, b], \mathbb{R})\) et \(\overline x \in [a, b]\) un zéro de \(f\) tel que \(f’(\overline x) \ne 0\). Alors il existe \(\delta > 0\) tel que pour tout \(x_0 \in [\overline x - \delta, \overline x + \delta]\) la suite \((x_n)_{n \in \mathbb{N}}\) donnée par la méthode de Newton est bien définie et converge vers \(\overline x \in [a, b]\). En outre, il existe une constante \(C > 0\) telle que

\begin{equation} |x_{n+1} - \overline x| < C |x_n - \overline x|^2. \end{equation}

Démonstration.

Comme \(f \in \mathcal{C}^2([a, b], \mathbb{R})\) la fonction \(f’\) est continue sur \([a, b]\). Du fait que \(f’(\overline{x}) \ne 0\) et de la continuité de \(f’\) il suit qu’il existe \(\eta > 0\) telle que pour tout \(x \in [\overline{x} - \eta, \overline{x} + \eta]\) on a \(f’(x) \ne 0\).

Soit \(L\) et \(M\) définis par

\begin{align*} L = \inf_{x \in [\overline{x} - \eta, \overline{x} + \eta]} |f’(x)| \\ M = \sup_{x \in [\overline{x} - \eta, \overline{x} + \eta]} |f^{\prime\prime}(x)|. \end{align*}

Vue le choix de \(\eta\), \(|f’(x)| > 0\) pour tout \(x \in [\overline{x} - \eta, \overline{x} + \eta]\). De plus \(f’\) est continue sur l’intervalle fermé \([\overline{x} - \eta, \overline{x} + \eta]\), donc elle atteint son \(\inf\). Alors \(L > 0\). On a également \(M > 0\). Le cas \(M = 0\) ce réduit au fait que \(f\) est linéaire sur \([\overline{x} - \eta, \overline{x} + \eta]\) et donc la méthode de Newton converge de manière exacte dès la première itération.

Alors \[\frac{1}{f’(x)} \le \frac{1}{L} \qquad \forall x \in [\overline{x} - \eta, \overline{x} + \eta].\] Soit \(\delta = \min\{\eta, \frac{L}{M}\}\). Alors, \(\frac{M\delta}{2L} \le \frac{1}{2} < 1\) et pour tout \(x \in [\overline{x} - \delta, \overline{x} + \delta]\)

\begin{align*} \frac{1}{f’(x)} \le \frac{1}{L} \\ |f^{\prime\prime}(x)| \le M. \end{align*}

Soit \(x_0 \in [\overline{x} - \delta, \overline{x} + \delta]\). Alors par la formule de Taylor-Lagrange il existe \(\eta_0 \in [\overline{x} - \delta, \overline{x} + \delta]\) tel que

\begin{equation} 0 = f(\overline x) = f(x_0) + (\overline x - x_0) f’(x_0) + \frac{(\overline x - x_0)^2}{2!} f^{\prime\prime}(\eta_0). \end{equation}

En rappelant que \(f’\) ne s’annule pas sur \([\overline{x} - \delta, \overline{x} + \delta]\), de la relation précédente on en déduit

\begin{equation} 0 = \frac{f(x_0)}{f’(x_0)} + \overline x - x_0 + \frac{(\overline x - x_0)^2}{2!} \frac{f^{\prime\prime}(\eta_0)}{f’(x_0)}. \end{equation}

La définition de la suite \((x_n)_{n \ge 0}\) par la méthode de Newton combinée à la relation précédente, donne \[x_1 = \overline x + \frac{(\overline x - x_0)^2}{2!} \frac{f^{\prime\prime}(\eta_0)}{f’(x_0)}.\] Alors, \[ |x_1 - \overline x| \le \frac{1}{2} \frac{|f^{\prime\prime}(\eta_0)|}{|f’(x_0)|} |\overline x - x_0|^2 \le \frac{M}{2L} \delta^2 \le \delta.\]

Donc \(|x_1 \in [\overline{x} - \delta, \overline{x} + \delta]|\) et \(f’(x_1) \ne 0\). En procédant par récurrence la suite \((x_n)_{n \ge 0}\) et bien définie et, de plus, \(\displaystyle |x_{k + 1} - \overline x| \le \frac{M}{2L} |x_k - \overline x|^2\).

Notons \(\displaystyle e_k = \frac{M}{2L} |x_k - \overline x|\). La relation précédente donne \[ e_{k + 1} \le (e_k)^2 \] et donc \[ e_k \le (e_0)^{2^k} \le \left( \frac{M\delta}{2L}\right)^{2^k} \to 0 \] quand \(k \to \infty\). Alors \(x_k \to \overline{x}\) quand \(k \to \infty\). De plus la convergence et quadratique.

Remarquer que la méthode de Newton donne seulement la convergence locale. La combinaison de plusieurs méthodes peut être nécessaire pour la recherche rapide des zéros d’une fonction.

Remarque

La méthode de point fixe et la méthode de Newton peuvent être utilisés pour la recherche des zéro des fonctions \(f : D \subset \mathbb{R}^N \to \mathbb{R}^N\).

Ainsi la méthode de point fixe revient à construire une suite \((\boldsymbol{x}_n)_{n}\) définie par \[\boldsymbol{x}_{n + 1} = g(\boldsymbol{x}_n)\] avec \(g(\boldsymbol{x}) = \boldsymbol{x} + f(\boldsymbol{x})\) par exemple.

Dans ce cadre la méthode de Newton s’écrit par \[ \boldsymbol{x}_{n + 1} = \boldsymbol{x}_{n} - (\nabla f(\boldsymbol{x}_n))^{-1} f(\boldsymbol{x}_n), \] où \(\nabla f(\boldsymbol{x}_n) \in M_n(\mathbb{R})\) et la matrice Jacobienne de \(f\) évaluée en \(\boldsymbol{x}_n\).

Biblio

Filbet, Francis. Analyse numérique-Algorithme et étude mathématique-2e édition: Cours et exercices corrigés. Dunod, 2013.