Example of Horner's Scheme

To find a root of p(x) = 4x⁴-2x²+3x+1, we apply Newton's method with initial guess x₀ = -2.

x1 = (-2) - p(-2) p¢(-2)

So we need to compute p(-2) and p¢(-2).

Horner's scheme

p(x) = 1+ x(3+x(-2+x( 0+x(4)))).

Note: p(x) does not have a cubic term but we still need that in the nested multiplication form.

The coefficients for p(x) are:

a4 = 4, a3 = 0, a2 = -2, a1 = 3, a0 = 1

Applying Horner's scheme with x = -2:

b4 = a4 = 4 b3 = a3+ x b4 = 0+ (-2)(4) = -8 b2 = a2+ x b3 = -2+(-2)(-8) = 14 b1 = 3+(-2)(14) = -25 b0 = 1+(-2)(-25) = 51

Hence

p(-2) = b0 = 51

Remark :

p(x) = (x- (-2)) Q(x) + p(-2)

with

Q(x) = b4x3+b3x2+b2x+b1 = 4x3-8x2+14x-25

Note: Q(x) is not the derivative of p(x). Only that the value of Q(-2) matches the value of p¢(-2).

To evaluate p¢(-2), write Q(x) in nested multiplication form:

Q(x) = -25+x(14+x(-8+x(4))).

Applying Horner's scheme now to Q(x) with x = -2:

c3 = b4 = 4 c2 = b3+ x c3 = -8+ (-2)(4) = -16 c1 = b2+ x c2 = 14+(-2)(-16) = 46 c0 = -25 +(-2)(46) = -117

Hence

p¢(-2) = Q(-2) = c0 = -117

Thus the next guess in the Newton's method is

x1 = -2 - 51 -117 = - 61 39 = -1.564102564