La suite de Héron, étude mathématique et implémentation en python

La suite de Héron, étude mathématique et implémentation en python

La suite de Héron est une suite permettant de trouver une valeur approchée d’une racine carrée.

Elle tire son nom du mathématicien Héron d’Alexandrie.

suite de héron
Héron d’Alexandrie

Suite de Héron: étude mathématique

On considère la suite \((u_n)_{n\in\mathbb{N}}\) définie par son premier terme \(u_0 > 0\) et par la relation de récurrence suivante :$$\forall n\in\mathbb{N},\quad u_{n+1}=\frac{1}{2}\left(u_n+\frac{a}{u_n}\right)$$où \(a\) est un réel strictement plus grand que 1 (le cas où il est égal à 0 ne nous importe peu car la suite devient géométrique de raison \(\frac{1}{2}\) et converge donc vers 0).

Cette suite est appelée une suite de Héron de paramètre a.

Fonction associée à la suite de Héron

Immédiatement, on peut constater que \(u_{n+1} = f(u_n)\), avec:$$f(x)=\frac{1}{2}\left(x+\frac{a}{x}\right)$$que l’on peut définir sur \(]0;+\infty[\).

Sa dérivée est alors:$$f'(x)=\frac{1}{2}\left(1-\frac{a}{x^2}\right)$$que l’on peut aussi écrire:$$f'(x)=\frac{x^2-a}{2x^2}.$$

L’expression \(x^2-a\) s’annule pour \(x=-\sqrt{a}\) et pour \(x=\sqrt{a}\). On a alors le tableau de variations suivant :

tableau de variations de la fonction associée à la suite de héron
Tableau de variations de la fonction associée à la suite de Héron de paramètre a

f admet donc un minimum pour \(x=\sqrt{a}\) qui vaut \(\sqrt{a}\).

Pour tout réel x > 0, \(f(x) \geqslant \sqrt{a}\).

Tous les termes de la suite sont positifs

Ce résultat est presque immédiat. En effet, $$u_0>0$$ donc $$\frac{1}{2}\left(u_0 + \frac{a}{u_0}\right)>0$$donc:$$u_1>0.$$

De plus, si on suppose que pour un entier k fixé, \(u_k>0\),$$\frac{1}{2}\left(u_k + \frac{a}{u_k}\right)>0$$donc:$$u_{k+1}>0.$$

D’après le principe de récurrence, on peut conclure que pour tout entier naturel n, \(u_n>0\).

La suite de Héron est minorée par \(\sqrt{a}\)

Nous venons en effet de démontrer que tous les termes de la suite sont strictement positifs donc pour tout entier naturel n, \(f(u_n) \geqslant \sqrt{a}\) d’après les variations de la fonction f.

La suite est décroissante

En effet, on a:$$\begin{align}u_{n+1}-u_n & = \frac{1}{2}\left(u_n+\frac{a}{u_n}\right)-u_n\\&=\frac{1}{2}\left(u_n+\frac{a}{u_n}\right)-\frac{1}{2}\times2u_n\\&=\frac{1}{2}\left(u_n+\frac{a}{u_n}-2u_n\right) \\&=\frac{1}{2}\left(\frac{a-u_n^2}{u_n}\right)\end{align}$$

Or, nous avons vu précédemment que pour tout entier naturel n, \(u_n\geqslant\sqrt{a}\), donc que \(u_n^2 \geqslant a\), ce qui nous assure que \(u_{n+1}-u_n \leqslant 0\).

La suite de Héron est donc décroissante.

La suite est convergente

La suite est minorée et décroissante. D’après le théorème de convergence des suites monotones, elle converge donc. Notons \(\ell\) sa limite.

Comme f est une fonction continue, on peut écrire : $$u_{n+1} = f(u_n) \Rightarrow \lim\limits_{n\to+\infty} u_{n+1} = f\left(\lim\limits_{n\to+\infty} u_n\right),$$c’est-à-dire:$$\ell = f(\ell).$$On doit donc résoudre cette dernière équation pour déterminer la valeur de la limite de la suite.

$$\begin{align}\ell = f(\ell) & \iff \ell = \frac{1}{2}\left(\ell + \frac{a}{\ell}\right)\\&\iff 2\ell = \ell + \frac{a}{\ell}\\&\iff \ell = \frac{a}{\ell}\\&\iff \ell^2=a\\&\iff \ell=-\sqrt{a}\text{ ou }\ell = \sqrt{a} \end{align}$$

Or, tous les \(u_n\) sont positifs donc \(\ell\) ne peut pas être égale à \(\sqrt{a}\). Par conséquent,$$\lim\limits_{n\to+\infty} u_n=\sqrt{a}.$$

Vitesse de convergence de la suite de Héron

Effectuons le calcul suivant:$$\begin{align}u_{n+1}-\sqrt{a} & = \frac{1}{2}\left( u_n + \frac{a}{u_n} \right) – \sqrt{a} \\ & = \frac{1}{2}\left( u_n + \frac{a}{u_n} \right) – \frac{1}{2}\times2\sqrt{a}\\&=\frac{1}{2}\left( u_n + \frac{a}{u_n} – 2\sqrt{a}\right)\\&=\frac{1}{2}\left( \frac{u_n^2 + a – 2\sqrt{a} }{u_n} \right) \\& = \frac{1}{2}\times\frac{\left(u_n-\sqrt{a}\right)^2}{u_n} \end{align}$$

Considérons maintenant la suite \((d_n)\) définie par son premier terme \(d_0=1\) et par la relation de récurrence :$$d_{n+1}=\frac{1}{2}d_n^2.$$On choisit \(u_0\) de sorte que \(u_0-\sqrt{a} \leqslant 1\). Démontrons par récurrence que pour tout entier naturel n, et pour a > 1, \( u_n-\sqrt{a} \leqslant d_n\).

  • Initialisation : c’est ce que nous avons supposé, à savoir que \(u_0-\sqrt{a} \leqslant 1\).
  • Hérédité : supposons que pour un entier k fixé, \( u_k-\sqrt{a} \leqslant d_k\). Alors:$$\begin{align}u_k-\sqrt{a} \leqslant d_k & \Rightarrow (u_k-\sqrt{a})^2 \leqslant d_k^2\\&\Rightarrow \underbrace{\frac{1}{2u_k}(u_k-\sqrt{a})^2}_{=u_{k+1}-\sqrt{a}} \leqslant \frac{1}{2u_k}d_k^2 \\& \Rightarrow u_{k+1}-\sqrt{a} \leqslant \underbrace{\frac{1}{2}d_k^2}_{=d_{k+1}}\times\frac{1}{u_k} \leqslant d_{k+1}\end{align}$$La dernière inégalité vient du fait que \(\frac{1}{u_k}<1\).

Ainsi, comme la suite \((d_n)\) converge vers 0, il suffit que \(d_n \leqslant 10^{-p}\) pour que \(u_n-\sqrt{a} \leqslant 10^{-p}\).

On peut facilement montrer que pour tout entier naturel n,$$d_n=\frac{1}{2^{v_n}}$$où la suite \((v_n)\) vérifie : $$v_0=0,\qquad v_{n+1}=2v_n+1.$$On en déduit alors que:$$v_n=2^n-1$$et donc que:$$d_n=\frac{1}{2^{2^n-1}}.$$Ainsi, si on veut une valeur approchée de \(\sqrt{a}\) à \(10^{-p}\), il faut que:$$\begin{align}\frac{1}{2^{2^n-1}}\leqslant 10^{-p} \\ & \iff 2^{2^n-1} \geqslant 10^p\\& \iff n \geqslant \log_2\left( \log_2(10^p)+1 \right) \end{align}$$

Ainsi, pour une valeur approchée à \(10^{-9}\), il faut que:$$n\geqslant4,949$$donc 5 termes suffisent… Rapide la convergence non ?

Suite de Héron: du côté de Python

from math import log, ceil
def heron(a,p):
    u = 3 # premier terme
    N = ceil( log( log( 10**p , 2) + 1 , 2) )
    for n in range(N):
        u = 0.5 * (u + a/u)
        
    return u,N

print( heron(11,10) )

J’ai ici implémenté une fonction heron(a,p) qui admet deux arguments : “a” est le nombre dont on cherche une valeur approchée à \(10^{-p}\).

Ainsi, dans cet exemple, on affiche une valeur approchée de \(\sqrt{11}\) à \(10^{-10}\).

Il est a noter toutefois qu’il est inutile de mettre de trop grandes valeurs de p car Python est assez limité dans les décimales.

Ce programme affiche :

(3.3166247903554, 6)

Cela signifie que 6 termes ont suffit pour trouver la valeur approchée.

Stéphane Pasquet
Stéphane Pasquet

1 réflexion au sujet de « La suite de Héron, étude mathématique et implémentation en python »

Modérand SODOHOUEPublié le  12:26 - Jan 7, 2021

Merci bien très intéressant

Ahmed BakariPublié le  11:34 - Jan 27, 2021

Bonjour/bonsoir s’il vous plaît besoin du Bord le point Tc

Laissez votre message