Algorithme de Horner

Au temps jadis, les physiciens et les astronomes devaient faire tous leurs calculs à la main, et ces calculs pouvaient être très compliqués. Il fallait souvent évaluer des quantités polynomiales, par exemple $5x^4 -4x^3 +3x^2 -2x+1$ pour $x=8$. La façon naïve d'arriver au résultat est de calculer $x$, $x^2$, $x^3$ et $x^4$ pour la valeur choisie $x=8$, ce qui représente $3$ multiplications, puis $5x^4$, $4x^3$, $3x^2$ et $2x$, ce qui représente $4$ multiplications supplémentaires. En ajoutant les sommes à la liste des opérations nécessaires, on obtient en tout $7$ multiplications et $4$ additions. La tradition attribue au mathématicien anglais William George Horner (1786-1837) la description en 1819 d'une méthode efficace pour économiser des opérations, méthode encore utilisée de nos jours par les ordinateurs. Remplaçons en effet $5x^4 -4x^3 +3x^2 -2x+1$ par l'expression équivalente

$$x(x(x(x\times 5-4)+3)-2)+1,$$

puis calculons successivement $a=5$, $b=xa-4$, $c=xb+3$, $d=xc-2$, et enfin $e=xd+1$. Alors $e$ est le résultat cherché, obtenu après $4$ multiplications et $4$ additions. On économise donc des multiplications, qui sont des opérations longues à réaliser. De plus, on n'a été obligé de stocker en mémoire (ou dans son cerveau, si on n'est pas en silicium) que deux valeurs : $x$ et $a$, puis $x$ et $b$, puis $x$ et $c$, etc.

La tradition a retenu cette méthode sous le nom d'algorithme de Horner à cause de l'article de 1819 cité plus haut. Il se trouve que cet article ne contient pas ladite méthode ! Horner la décrit bien, mais dans un autre article, publié en 1830 seulement. Et entre temps, en 1820, un fabricant de montres londonien nommé Theophilus Holdred avait, lui, effectivement publié la méthode.

Alors, Horner plagiaire ? Quoi qu'il en soit, on sait maintenant que la méthode de Horner était en fait déjà connue d'Isaac Newton en 1669, et avant lui, du mathématicien chinois Ch'in Chiu-Shao (ou Chu Shih-Chieh, ou Zhu Shijie, on s'y perd !) au XIII^e siècle. Elle peut être vue comme un cas particulier d'une règle due au mathématicien italien Paolo Ruffini (1765-1822), règle qui permet de calculer le quotient et le reste de la division euclidienne d'un polynôme $P$ par un monôme $X-a$. Signalons enfin que des versions de cet algorithme permettent aussi d'évaluer des polynômes de matrices, situation où le gain de temps de calcul réalisé est encore plus important.