Méthode de Horner
Pour calculer la valeur prise par une fonction polynôme en un point \(x\) de \(K\), il y a plusieurs méthodes.
Une méthode très "performante" est la méthode de Horner.
Elle consiste à calculer \(\tilde{P}(x)\), avec \(P(X)=\displaystyle{\sum_{k=0}^{k=n}a_k X^k}\), en utilisant la forme suivante :
\(\tilde{P}(x)=(\ldots((a_nx+a_{n-1})x+a_{n-2})x+\ldots+a_1)x+a_0\)
ce qui nécessite n multiplications et n additions, nombre d'opérations très inférieur à celui obtenu en faisant les calculs comme ils se présentent.
Pour s'en convaincre, on peut considérer l'exemple suivant :
Soit l'élément \(P(X)=2X^3+4X^2-3X+5\) de \(R[X]\) et \(x\) un nombre réel.
On écrit \(\tilde{P(x)}\) sous la forme : \(\tilde{P}(x)=((2x+4)x-3)x+5\).
Pour calculer \(\tilde{P}(x)\), avec \(x\) élément de \(R\), on a donc besoin de 3 multiplications et de 3 additions par la méthode de Hörner, mais de 5 multiplications et de 3 additions en calculant directement.
De plus, cette méthode est très facilement programmable.