Bombelli's algorithm

Pour approcher √13, on commence par 3, car 3² = 9 et il manque 4 pour atteindre 13. Ce reste est placé au numérateur d'une fraction. Son premier dénominateur vaut deux fois 3, soit 6 : on obtient 3 + 4/6 = 11/3, environ 3,667.

La méthode réutilise ensuite l'approximation précédente dans le dénominateur. Elle produit 18/5, puis 119/33, de plus en plus proches de √13. Chaque étape ne manipule que des nombres rationnels, alors que la valeur visée est irrationnelle.

L'algorithme de Bombelli est un procédé d'approximation d'une racine carrée par des fractions. Pour un entier positif N qui n'est pas un carré parfait, on note a la partie entière de √N et r le reste positif N − a². La factorisation N − a² = (√N − a)(√N + a) donne l'identité :

On remplace d'abord la racine encore présente au dénominateur par a, puis par l'approximation obtenue à l'étape précédente. Si x₀ désigne a, les approximations suivantes sont définies par :
Chaque x_n est rationnel. Les troncatures successives développent la fraction continue généralisée :

Pour N = 2, on a a = 1 et r = 1 ; en posant x = √2, l'identité devient x = 1 + 1/(1 + x). La méthode est attribuée au mathématicien italien de la Renaissance Rafael Bombelli. Bombelli la décrit lui-même à travers l'approximation de √13, où a = 3 et r = 4 : les fractions obtenues sont les réduites de cette fraction continue généralisée.

Soit N un entier positif. On choisit l'entier a tel que a² ≤ N < (a + 1)², puis on calcule le reste r = N − a². Si r = 0, la racine vaut exactement a et le calcul s'arrête.

Sinon, on part de x₀ = a et l'on répète la règle $x_{n+1}=a+\frac{r}{a+x_n}x\_\{n+1\}=a+\backslash frac\{r\}\{a+x\_n\}$. On arrête lorsque deux valeurs successives donnent la précision voulue ; chacune reste une fraction exacte tant qu'aucun arrondi décimal n'est effectué.

La procédure décrite ici s'applique à la racine carrée positive d'un entier N positif. Elle exige de connaître a, la partie entière de √N, puis le reste r = N − a². Avec ce choix, r est nul ou strictement positif, et tous les dénominateurs a + x_n sont positifs.

Deux contrôles sont vérifiables : a² ≤ N < (a + 1)² et chaque nouvelle fraction respecte la même récurrence. Si N est un carré parfait, par exemple N = 9, le reste vaut 0 : il ne faut pas poursuivre une fraction imbriquée, puisque √9 = 3 est déjà exact. Pour une entrée négative dans les nombres réels, cette procédure ne s'applique pas ; il faut changer de cadre numérique.

On cherche une approximation rationnelle de √13. Les données sont N = 13, a = 3 puisque 3² = 9 < 13 < 16 = 4², et r = 13 − 9 = 4. On pose x₀ = 3.

1. La première fraction vaut $x_1=3+\frac{4}{3+3}=\frac{11}{3}\approx \mathrm{3,6667}x\_1=3+\backslash frac\{4\}\{3+3\}=\backslash frac\{11\}\{3\}\backslash approx3\{,\}6667$.
2. On réinjecte 11/3 : $x_2=3+\frac{4}{3+11\mathrm{/}3}=\frac{18}{5}=\mathrm{3,6}x\_2=3+\backslash frac\{4\}\{3+11/3\}=\backslash frac\{18\}\{5\}=3\{,\}6$.

3. On réinjecte 18/5 : $x_3=3+\frac{4}{3+18\mathrm{/}5}=\frac{119}{33}\approx \mathrm{3,60606}x\_3=3+\backslash frac\{4\}\{3+18/5\}=\backslash frac\{119\}\{33\}\backslash approx3\{,\}60606$.
4. Les approximations passent alternativement sous et au-dessus de √13. Le schéma associé rend visible ce resserrement.

Le contrôle ne dépend pas d'une valeur décimale de √13 : (18/5)² = 324/25 = 12,96 < 13, tandis que (119/33)² = 14 161/1 089 > 13. Ainsi . Les deux dernières fractions encadrent la racine avec un intervalle de largeur 1/165.

Pour un calcul à la main, la méthode fournit des fractions que l'on peut conserver sans arrondir. On choisit l'entier inférieur, on calcule le reste, puis on applique la même récurrence jusqu'à obtenir un encadrement assez serré. Si seule une valeur décimale immédiate est recherchée, une calculatrice est plus directe ; Bombelli est préférable lorsqu'on veut suivre la construction rationnelle.

Pour contrôler une approximation de √13, on élève la fraction au carré et on compare le résultat à 13. Cette vérification indique de quel côté de la racine se trouve la valeur. Deux approximations consécutives placées de part et d'autre donnent en plus un intervalle exact, utile lorsque la précision doit être justifiée plutôt que simplement affichée.

Fraction continue généralisée et fraction continue simple. Dans le développement de Bombelli pour √13, le nombre 4 est le numérateur partiel répété dans les fractions imbriquées, pas une fraction à lui seul. Pour √2, le reste vaut 1 et l'écriture prend la forme simple 1 + 1/(2 + 1/(2 + …)).

Fraction exacte et approximation de la racine. Le nombre 119/33 est une fraction exacte, mais il n'est pas égal à √13. Son écriture décimale 3,60606 est elle-même arrondie. Le test par les carrés tranche : 119²/33² est strictement supérieur à 13.

Un carré parfait arrête immédiatement la procédure. Pour N = 9, le choix a = 3 donne r = 0. La fraction ajoutée est nulle et √9 = 3 ; poursuivre les substitutions ne produit aucune information nouvelle.

Les approximations ne progressent pas dans un seul sens. Pour √13, 11/3 est au-dessus de la racine, 18/5 est en dessous et 119/33 repasse au-dessus. Le symptôme n'est pas une erreur de calcul : on contrôle la précision par l'encadrement ou par l'écart, pas en exigeant une suite croissante.

Un arrondi précoce dégrade le caractère exact. Réinjecter 3,67 à la place de 11/3 modifie les étapes suivantes. Il faut conserver les numérateurs et dénominateurs entiers jusqu'au résultat final, puis seulement convertir en décimal si le besoin l'exige.

Le choix initial doit encadrer la racine. Pour N = 13, a vaut 3 parce que 9 ≤ 13 < 16. Partir de 4 contredit cette condition et ne correspond plus à la procédure énoncée ; il faut d'abord corriger la partie entière.

La fiche Fraction continue précise le vocabulaire des développements, des troncatures et des réduites mobilisé par l'algorithme.

L'article Les fractions continues, prolonge l'étude de ces écritures et de leurs approximations rationnelles.