Algoritmo de Horner

En el campo matemático del análisis numérico, el Algoritmo de Horner, llamado así por William George Horner, es un algoritmo para evaluar de forma eficiente funciones polinómicas de una forma monomial.

Dado el polinomio

${\displaystyle p(x)=a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\cdots +a_{n}x^{n},}$

donde ${\displaystyle a_{0},\ldots ,a_{n}}$ son números reales, queremos evaluar el polinomio a un valor específico de ${\displaystyle x\,\!}$, digamos ${\displaystyle x_{0}\,\!}$.

Para llevar a cabo el procedimiento, definimos una nueva secuencia de constantes como se muestra a continuación:

${\displaystyle b_{n}\,\!}$	${\displaystyle$ :=\,\!}	${\displaystyle a_{n}\,\!}$
${\displaystyle b_{n-1}\,\!}$	${\displaystyle$ :=\,\!}	${\displaystyle a_{n-1}+b_{n}x_{0}\,\!}$
	${\displaystyle \vdots }$
${\displaystyle b_{0}\,\!}$	${\displaystyle$ :=\,\!}	${\displaystyle a_{0}+b_{1}x_{0}\,\!}$

Entonces ${\displaystyle b_{0}\,\!}$ es el valor de ${\displaystyle p(x_{0})\,\!}$.

Para ver como funciona esto, nótese que el polinomio puede escribirse de la forma

${\displaystyle p(x)=a_{0}+x(a_{1}+x(a_{2}+\cdots +x(a_{n-1}+a_{n}x)\cdots ))}$

Después, sustituyendo iterativamente la ${\displaystyle b_{i}}$ en la expresión,

${\displaystyle p(x_{0})\,\!}$	${\displaystyle =\,\!}$	${\displaystyle a_{0}+x_{0}(a_{1}+x_{0}(a_{2}+\cdots +x_{0}(a_{n-1}+b_{n}x_{0})\dots ))}$
	${\displaystyle =\,\!}$	${\displaystyle a_{0}+x_{0}(a_{1}+x_{0}(a_{2}+\cdots +x_{0}(b_{n-1})\dots ))}$
	${\displaystyle \vdots }$
	${\displaystyle =\,\!}$	${\displaystyle a_{0}+x_{0}(b_{1})\,\!}$
	${\displaystyle =\,\!}$	${\displaystyle b_{0}\,\!}$