Horner's Method

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 P_n(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 P_n(z) of the polynomial P at x = z as the sequence of steps starting with the leading coefficient a_n using:

	bk = z·bk+1 + ak
	ck = z·ck+1 + bk

                The next value of the x_n in the iterative step is found by,

                x_k+1 = x_k – (b₀/c₁), where b₀ = P_n(x_k) = b₀ and c₁ = P’_n(x_k) in shortcut.

Generally, the iteration is continued until the required amount of precision is obtained.

Example: Solve the equation x³+9x²-18 using Horner’s Method where z= x₀ = 1.5.

            Here, a₀=-18, a₁=0, a₂=9, and a₃=1.

            Starting from a₃, b₃=c₃=a₃=1.

            Hence,

            b₂ = 9+1x1.5 = 10.5                          c₂ = 10.5+1x1.5 = 12

            b₁ = 0+10.5x1.5 = 15.75                  c₁ = 15.75+12x1.5 = 33.75

            b₀ = -18+15.75x1.5 = 5.625                 

            So, x₁ = x₀ – (b₀/c₁) = 1.5 – (5.625/33.75) = 1.333

            Þ x₁ = z = 1.333

            

            Now, for the new value of z,

            b₂ = 9 + 1x1.333 = 10.333                               c₁ = 28.881

            b₁ = 0+10.333x1.333 = 13.774

            b₀ = -18 + 13.774x1.333 = 0.361

            So, x₂ = x₁ – (b₀/c₁) = 1.333 – (0.361/28.881) = 1.320

            Þ x₂ = z = 1.320

            Again, for new value of z,

            b₀ = -0.018           c₁ = 28.987

            So, x₃ = x₂ – (b₀/c₁) = 1.320 – (-0.018/28.987) = 1.320

Therefore, Approximate Root = 1.320 correct to 3 decimal places.