Horner's method is an efficient way of evaluating polynomials and their derivatives at a given point. It is also used for a compact presentation of the long division of a polynomial by a linear polynomial.
A polynomial Pn(x) can be written in the descending order of the powers of x:
Pn(x) = anxn + an-1xn-1 + ... + a1x + a0
or in the ascending order of the exponents:
Pn(x) = a0 + a1x + ... + an-1xn-1 + anxn.
The Horner scheme computes the value Pn(z) of the polynomial P at x = z as the sequence of steps starting with the leading coefficient an using:
bk = z·bk+1 + ak
ck = z·ck+1 + bk
The next value of the xn in the iterative step is found by,
xk+1 = xk – (b0/c1), where b0 = Pn(xk) = b0 and c1 = P’n(xk) in shortcut.
Generally, the iteration is continued until the required amount of precision is obtained.
Example: Solve the equation x3+9x2-18 using Horner’s Method where z= x0 = 1.5.
Here, a0=-18, a1=0, a2=9, and a3=1.
Starting from a3, b3=c3=a3=1.
b2 = 9+1x1.5 = 10.5 c2 = 10.5+1x1.5 = 12
b1 = 0+10.5x1.5 = 15.75 c1 = 15.75+12x1.5 = 33.75
b0 = -18+15.75x1.5 = 5.625
So, x1 = x0 – (b0/c1) = 1.5 – (5.625/33.75) = 1.333
Þ x1 = z = 1.333
Now, for the new value of z,
b2 = 9 + 1x1.333 = 10.333 c1 = 28.881
b1 = 0+10.333x1.333 = 13.774
b0 = -18 + 13.774x1.333 = 0.361
So, x2 = x1 – (b0/c1) = 1.333 – (0.361/28.881) = 1.320
Þ x2 = z = 1.320
Again, for new value of z,
b0 = -0.018 c1 = 28.987
So, x3 = x2 – (b0/c1) = 1.320 – (-0.018/28.987) = 1.320
Therefore, Approximate Root = 1.320 correct to 3 decimal places.