Horners algoritm

Horners algoritm, Horners metod eller Horners schema är en regel för att beräkna värdet av ett polynom. Den används med fördel för polynom av hög grad. Den är uppkallad efter den brittiska matematikern William George Horner.

Regeln innebär att polynomet

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

skrivs om på den rekursiva formen

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

Den senare formen har fördelen att endast n additioner samt n multiplikationer måste utföras, jämfört med (n²+n)/2 multiplikationer för originalformen. Uträkningen kan därmed utföras snabbare, och blir dessutom numeriskt stabilare (det vill säga avrundningsfelet blir mindre).

${\displaystyle x^{6}-4x^{5}+13x^{4}+7x^{3}-x^{2}-x+12=0}$

skrivs om till

${\displaystyle ((((x-4)x+13)x+7)x-1)x-1)x+12=0}$

${\displaystyle -14y^{4}-13y^{3}+9y^{2}+1=0}$

skrivs om till

${\displaystyle (((-14y)-13)y+9)y^{2}+1=0}$

• Syntetisk division