Sunday 17 March 2013

C Program for Birge-Vieta Method

Basic Theory:
The Birge-Vieta method investigates the real root of a polynomial, say xr, by assuming that (x-xr) is a factor of that polynomial. Starting with an initial value or approximation x0 to xr, we use some iterative method to improve the value of the approximation such that R(xr)®0. It makes the use of the Newton-Raphson method for iteration in order to improve the value of xr.
xn+1=xn – [f(xn)/f ’(xn)]

We deploy the Synthetic Division method in order to find out R(xr) in this method. The remainder of first division gives the functional value while the remainder second division gives the value of derivative. We continue the iteration until the result of desired precision is obtained.

Example:  Solve the equation x3+x2-3x-3 using Birge-Vieta Method where x0 = 2.
Using the synthetic division,
2|1         1              -3            -3
  |           2              6              6
  |1         3              3              3¬f(x0)
  |           2              10
  |1         5              13¬f ’(x0)

Now, x1 = 2 – 3/13 = 1.7692
1.7692|1              1              -3            -3
           |                 1.7692   4.8992   3.3602
           |1              2.7692   1.8992   0.3602¬f(x1)
           |                 1.7692   8.0292
           |1              4.5384   9.9285¬f ’(x1)
Now, x2 = 1.7692 – 0.3602/9.9285 = 1.7329
1.7329|1              1              -3            -3
           |                 1.7329   4.7358   3.0079
           |1              2.7329   1.7358   0.0079¬f(x2)
           |                 1.7329   7.7387
           |1              4.4658   9.4745¬f ’(x2)
Now, x3 = 1.7329 – 0.0079/9.4745 = 1.7320
Therefore, Approximate Root = 1.732 correct to 3 decimal places.

Program:
#include<stdio.h>
#include<conio.h>
#include<math.h>

float p[6], ply[6],q[6];

float synth(int m, float r){
                int i;
                q[0] = p[0];
                for(i=1;i<=m;i++){
                                q[i] = (q[i-1]*r)+p[i];
                }

                printf("\n");
                for(i=0;i<m;i++){
                                printf("\t%f",q[i]);
                }
                printf("\t%f",q[m]);
                return(q[m]);
}

void main(){
                clrscr();
                int m,i,flag=0;
                float r, x,x1, fx, fdx;
                printf("\t\tBIRGE-VIETA METHOD");
                printf("\n Enter the highest degree of the equation (max 5): ");
                scanf("%d",&m);
                                for(i=0;i<=m;i++){
                                printf("\n Coefficient x[%d] = ",m-i);
                                scanf("%f",&p[i]);
                                ply[i] = p[i];
                                }
                printf("\n Enter the initial value x0 : ");
                scanf("%f",&r);
                x = r;

                do{
                   printf("\n%f\n",x);
                   fx = synth(m,x);
                                for(i=0;i<=m;i++){
                                                p[i]=q[i];
                                }
                   fdx = synth(m-1,x);
                   x1 = x - (fx/fdx);

                                if(fabs(x1-x) <= 0.0009){
                                                flag = 1;
                                 }
                   x = x1;

                                for(i=0;i<=5;i++){
                                                p[i]=ply[i];
                                }

                }while(flag!=1);

                printf("\nApproximate root = %f", x1);
getch();

}


Sample Output:

                        BIRGE-VIETA METHOD
Enter the highest degree of the equation (max 5): 3
Coefficient x[3] = 1
Coefficient x[2] = 1
Coefficient x[1] = -3
Coefficient x[0] = -3
Enter the initial value x0 : 2
2.000000
              1.000000   3.000000   3.000000   3.000000
              1.000000   5.000000   13.000000
1.769231
              1.000000   2.769231   1.899408   0.360492
              1.000000   4.538462   9.928994
1.732924
              1.000000   2.732924   1.735948   0.008266
              1.000000   4.465847   9.474921
Approximate root = 1.732051



©Dixit Bhatta 2013

6 comments:

  1. Replies
    1. I am happy that it helped you Abhishek :)

      Delete
  2. i cant understand can you tell me this in step by step

    ReplyDelete
    Replies
    1. I have provided the explanation and an example above. The program behaves exactly the way it is outlined in the example. I am not sure if I can explain it all in comments when the entire post is my best effort to make you understand.

      Delete
  3. try to small programs sir ji

    ReplyDelete
  4. If your devc++ got the error "undenifed reference to clrsrc()" remove the #include, getch() and clrsrc()

    ReplyDelete

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