Horner's Method

ALGORITHM:

1. START
2. Given non-linear equation f(x) = a₀xⁿ + a₁x^n-1 + …….. + a_n-1x +a_n
3. Take initial guess as x0.
4. Use synthetic division to find f(x0) where deflated equation g(x) = b₀x^n-1 + b₁x^n-2 + …….. + b_n-1 and f(x0) = b_n-1
5. Again, divide g(x) synthetically by x0 to find f'(x0) where h(x) = c₀x^n-2 + c₁x^n-3 + …….. + c_n-3x + c_n-2 and f'(x0) = c_n-3
6. Use N-R formula to find next value x1 = x0 - f(x0)/f'(x0).
7. If |x1-x0| < accuracy, root = x1, Else set x0=x1 and go to step 4.
8. STOP.

PROGRAM in C:

// for polynomial x^2 - 5x + 6 = 0 correct up to 3 decimal places

#include<stdio.h>

#include<conio.h>

#include<math.h>

void main()

{

    float a[10],b[10],c[10],x0,x1=0,tmp,acc=0.001,f,g;

    int n,i;

    printf("Enter degree (n) of polynomial: ");

    scanf("%d",&n);

    for(i=n;i>=0;i--)

    {

        printf("Enter coefficient x[%d]: ",i);

        scanf("%f",&a[i]);

    }

    printf("Enter intial guess: ");

    scanf("%f",&x0);

    do

    {

        tmp=x1;

        for(i=n;i>=0;i--)

        {

            if(i==n)

            {

                b[i]=a[i];

                c[i]=b[i];

            }

            else

            {

                b[i]=a[i]+x0*b[i+1];

                c[i]=b[i]+x0*c[i+1];

                if(i==0)

                    f=b[i];

                if(i==1)

                    g=c[i];

            }

        }

        x1=x0-f/g;

        x0=x1;

    }while(fabs(tmp-x1)>=acc);

    printf("One of the roots is %0.4f",x1);

    getch();

}

Example:
For the equation X² – 5X + 6 = 0,