cmathconvergencebisection

Parameter of convergence of bisection method. C code


I stuck with one formula in my code. Changed it many times in different ways but all the time my teacher say that it is not correct. I gave up and have no idea what else I can do. I think I just don't understand the formula correctly that's why I do it wrong. Could you please help me to find the solution. Thank you!

It is a very simple bisection method where I have to solve the equation. Besides this I have to find the Parameter of convergence (I am not sure if I use the right term for this. The task is in Russian) using the formula α = |Xn+1 - Xn| / |Xn - Xn-1|, where n - Order of convergence (again here I am not sure if this is correct term. I used Google translator).

Please take a look at the end of the code where I calculate this value and give me please an advise what do I do wrong? I use the root ξ as an Xn, a and b as Xn-1 and Xn+1 accordingly. Teacher's comment was "The convergence parameter is still incorrect. With this approach will always be obtained 1. As I wrote, use the formula from the task".

#include<stdio.h>
#include<math.h>
#include<time.h>

double f(double x); //Function
int res(int i, double a, double b, double ξ, double ε1, double ε2); //Print result
double Bisection(double a, double b, double ε1, double ε2); //Bisection method

int main()
{
    double a=-10, b=0, ξ, h=0.5, α, x1, x2, ε1, ε2;
    int i=0;

    printf("\nf(x) = 2^x - 2 * cos(x)");
    printf("\nStart of the interval a = %.0lf", a);
    printf("\nEnd of the interval b = %.0lf", b);
    printf("\nEnter error ε1 for function = ");
    scanf("%lf", &ε1);
    printf("Enter error ε2 for argument = ");
    scanf("%lf", &ε2);
    printf("\n\nSOLUTION:");

    //selection of roots
    x1=a;
    x2=x1+h;
    while (x2<=b)
    {
        if ((f(x1)*f(x2))<0) 
        {
            i++;
            printf("\n\n%d) %d root of the function is in the interval [%.1f, %.1f]\n",i, i, x1, x2);
            printf("\nn\t     a\t\t   b\t\t ξ\t     f(ξ)\t     ε1\t\t    ε2\n");
            Bisection(x1,x2,ε1,ε2); //Bisection method
        }
        x1=x2;
        x2=x1+h;
    }
    return 0;
}

//Function
double f(double x) 
{
   double y;
   y=pow(2,x)-2*cos(x);
   return y;
}

//Print result
int res(int i, double a, double b, double ξ, double ε1, double ε2) 
{
   printf("%d\t%10.7f    %10.7f    %10.7f    %10.7f    %e    %e\n", i, a, b, ξ, f(ξ), ε1, ε2);
   return 0;
}

//Bisection method
double Bisection(double a, double b, double ε1, double ε2)
{
    double ξ=(a+b)/2; //Middle of the interval
    double α;
    int i=0;
    if (f(ξ)==0) 
    {
        printf("Root: %f \n\n", ξ);
    }
    else 
    {
        while ((fabs(f(ξ))>ε1) && ((fabs(b-a)/2)>ε2)) //The accuracy of the definition of the root
        {
            if ((f(a)*f(ξ))<0) 
            {
                b=ξ;
            }
            else 
            {
                a=ξ;
            }
            ξ=(a+b)/2;
            res(i+1, a, b, ξ, ε1, ε2); //Print results
            i++;
        }
        α = fabs(ξ-b)/fabs(ξ-a); //Parameter of convergence
        printf("\nParameter of convergence: α=%.1f\n", α);
        printf("Root ξ=%.7f found after %d iterations\n", ξ, i);
        printf("Function f(ξ)=%.10f found after %d iterations\n", f(ξ), i);
    }
    return 0;
}

Program execution result


Solution

  • To my understanding

    the formula α = |Xn+1 - Xn| / |Xn - Xn-1|

    Refers to the calculated roots (X) at every iteration (n), so that in the first iteration

    |Xn - Xn-1| = fabs(b - a)
    |Xn+1 - Xn| = fabs(ξ - a) = fabs(b - ξ) 
                = fabs(b - a) / 2             given that ξ=(a+b)/2  (ignoring numerical errors)
    

    At every successive iteration of the bisection method the range [a, b] is halved, meaning that α will always be 1/2.

    Due to the limited precision and range of floating-point types, the expression ξ=(a+b)/2 (or ξ = a + (b - a)/2) will eventually generate a value numerically equivalent to one of the extremes, resulting in α = 0.