Algoritme de Horner

En el camp matemàtic del anàlisis numèric, el Algoritme de Horner, cridat aixina per William George Horner, és un algoritme per a evaluar de forma eficient funciones polinòmiques d'una forma monomial.

Donat el polinomi

$p(x)=a_0+a_{1}x+a_2{x}^2+a_3{x}^3+\cdots +a_n{x}^n,$

a on $a_0,\dots ,a_n$ són número real, volem evaluar el polinomi a un valor específic de $x$, digam $x_0$.

Per a portar a terme el procediment, definim una nova seqüència de constants com es mostra a continuació:

$b_n$	$:=$	$a_n$
$b_{n-1}$	$:=$	$a_{n-1}+b_n{x}_0$
	$⋮$
$b_0$	$:=$	$a_0+b_1{x}_0$

Llavors $b_0$ és el valor de $p(x_0)$.

Per a vore cóm funciona açò, note's que el polinomi pot escriure's de la forma

$p(x)=a_0+x(a_1+x(a_2+\cdots +x(a_{n-1}+a_{n}x)\cdots ))$

Despuix, substituint iterativamente la $b_i$ en l'expressió,

$p(x_0)$	$=$	$a_0+x_0(a_1+x_0(a_2+\cdots +x_0(a_{n-1}+b_n{x}_0)\dots ))$
	$=$	$a_0+x_0(a_1+x_0(a_2+\cdots +x_0(b_{n-1})\dots ))$
	$⋮$
	$=$	$a_0+x_0(b_1)$
	$=$	$b_0$

Aplicació

L'algoritme de Horner s'usa a sovint per a convertir entre distints sistemes numèrics posicionals — en que el seu case x és la base del sistema numèric, i els coeficients a_i són els dígits de la representació del número donat en la base x — i pot usar-se també si x és una matriu, en el cas de la qual la càrrega computacional es reduïx encara més.

Eficiència

l'evaluació usant la forma monomial del polinomi de grau-n requerix a lo manco n sumes i (n²+n)/2 multiplicacions, si les potències es calculen per mig de la repetició de multiplicacions. L'algoritme de Horner només requerix n sumes i n multiplicacions. (Minimisar el número de multiplicacions és lo més desijable perque necessiten molta càrrega computacional i són inestables comparades en la suma).

S'ha demostrat que l'algoritme de Horner és òptim, de modo que qualsevol algoritme que s'use per a evaluar un polinomi requerirà com a mínim el mateix número d'operacions. El fet de que el número d'operacions requerides és mínim va ser demostrat per Alexander Ostrowski en 1954, i que el número de multiplicacions és mínim per Victor Pa en 1966. Quan x és una matriu, l'algoritme de Horner no és òptim.

Vore també

• Regla de Ruffini
• Algoritme de Clenshaw per a evaluar polinomis de la forma de Chebyshov
• Algoritme de De Casteljau per a evaluar polinomis de la forma de Bézier

Referències

• William George Horner. A new method of solving numerical equations of all orders, by continuous approximation. En Philosophical Transactions of the Royal Society of London, pp. 308-335, juliol de 1819.
• Donald Knuth. The Art of Computer Programming, Volum 2: Seminumerical Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89684-2. Pàgines 486–488 en la secció 4.6.4.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest i Clifford Stein. Introduction to Algorithms, Segona Edició. MIT Press i McGraw-Hill, 2001. ISBN 0-262-03293-7. Problema 2-3 (pág 39) i pág 823, secció 30.1: Representation of polynomials.
• Jesús María Sanz Serna. Dèu Lliçons de Càlcul Numèric, Segona Edició Revisada i Ampliada. Universitat de Valladolit, Secretariat de Publicacions i Intercanvi Editorial, 2010. ISBN 978-84-8448-552-0. Capítul 1, pág 20-22. Método de Horner.