Bairstow's Method

/*      The following C program implements Bairstow’s method for determining the complex root of a polynomial equation, by extracting a quadratic factor of the  form x² + Px + Q from a polynomial equation. The polynomial and the initial approximations to P and Q are read as input.         */

Source Code:

 #include<stdio.h>

#include<math.h>

#define max 10

#define min 0.0005

void main()

{

 float a[max], b[max], bc[max], bd[max], p, q, r, s, error, errorp, errorq, rq, sq, rp, sp;

 int i, degree, j=0;

/* accepting the polynomial equation in the following form,

            xⁿ + a₀x^n-1 + a₁x^n-2 +……….+ a_n-2x + a_n-1 = 0      */

 printf("\n Enter degree of polynomial?  ");

 scanf("%d",&degree);

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

 {

  printf("\n Enter coefficient of x^%d:  ",i);

  if(i<degree)

  {

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

             a[degree-1-i]/=a[degree];

  }

  else

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

  }

  a[degree]=1;

  printf("\n X^2 + PX + Q \n Enter guesses for P and Q:  ");

  scanf("%f %f",&p,&q);

  error=1;

  while(error>=min)

  {

/* Beginning of Lin's method */

            for(i=0;i<=degree-3;i++)

             if(i==0)

                         b[i]=a[i]-p;

             else if(i==1)

                         b[i]=a[i]-p*b[i-1]-q;

             else

                         b[i]=a[i]-p*b[i-1]-q*b[i-2];

             /* Modification of Lin's to Bairstow's method */

             r = a[degree-2] - p*b[degree-3] - q*b[degree-4];

             s = a[degree-1] - q*b[degree-3];

             for(i=0; i<=degree-3; i++)

              if(i==0)

                          bc[i]=-1;

              else if(i==1)

                          bc[i]=-b[0]+p;

              else

                          bc[i]=b[i-1]-p*bc[i-1]-q*bc[i-2];

              rp=-b[degree-3]-p*bc[degree-3]-q*bc[degree-4];

              sp=-q*bc[degree-3];

             for(i=0;i<=degree-3;i++)

              if(i==0)

                          bd[i]=0;

              else if(i==1)

                          bd[i]=-1;

              else

                          bd[i]=-b[i-2]-p*bd[i-1]-q*bd[i-2];

              rq=-b[degree-4]-p*bd[degree-3]-q*bd[degree-4];

              sq=-b[degree-3]-q*bd[degree-3];

              errorp = (s*rq - r*sq)/(rp*sq - sp*rq);

              p+=errorp;

              errorq = (r*sp - s*rp)/(rp*sq - sp*rq);

              q+=errorq;

              errorp = fabs(errorp);

              errorq = fabs(errorq);

                                                                                                                                  

if(errorp>errorq)

                         error=errorp;

              else

                         error=errorq;

              j++;                                                                            /* iteration no. */

  }

  printf("\n\n X^2 + %f*X + %f",p,q);

  printf("\n\n ---> Total iterations = %d",j);

  }

SAMPLE OUTPUT:

Extracting a quadratic factor x² + Px + Q from the following polynomial equation by Lin’s method to determine the complex root of the following polynomial equation:

 x⁴ + x³ + 3x² + 4x + 6 = 0

Ø      Initial approximations:           P = 2.1,           Q = 1.9

                      

Ø      Initial approximations:           P = -2.1,          Q = -1.9

Note:               x⁴ + x³ + 3x² + 4x + 6 = (x² + 2x + 2)( x² - x + 3)

                      For the same initial approximations of P=2.1 and Q=1.9,

      Total iterations for Lin’s method (=24) > Total iterations for Bairstow’s method (=3)