Horners algoritm

Från Wikipedia
Hoppa till: navigering, sök

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.

Regeln innebär att polynomet

p(x) = a_0 + a_1x + a_2x^2 + a_3x^3 + \cdots + a_nx^n.

skrivs om på den rekursiva formen

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 (n2+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).

Exempel[redigera | redigera wikitext]

1[redigera | redigera wikitext]

x^6 - 4x^5 + 13x^4 + 7x^3 - x^2 -x + 12 = 0

skrivs om till

((((x-4)x+13)x+7)x-1)x-1)x+12=0

2[redigera | redigera wikitext]

-14y^4-13y^3+9y^2+1=0

skrivs om till

(((-14y)y-13)y+9)y+1=0

Se även[redigera | redigera wikitext]