Tuesday, 4 June 2013

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 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.
            Hence,
            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. 

No comments:

Post a Comment

Was this post helpful? Ask any questions you have, I will try to answer them for you.

Follow by Email