Newton-Raphson Method (C code for finding a real root of an equation)

This article is about Newton's method for finding roots.

In numerical analysis, Newton's method (also known as the Newton–Raphson method), named after Isaac Newton and Joseph Raphson, is a method for finding successively better approximations to the roots (or zeroes) of a real-valued function.

The Newton-Raphson method in one variable is implemented as follows:
Given a function ƒ defined over the reals x, and its derivative ƒ ', we begin with a first guess x₀ for a root of the function f. Provided the function satisfies all the assumptions made in the derivation of the formula, a better approximation x₁ is

Geometrically, (x₁, 0) is the intersection with the x-axis of a line tangent to f at (x₀, f (x₀)).
The process is repeated as

until a sufficiently accurate value is reached.
This algorithm is first in the class of Householder's methods, succeeded by Halley's method. The method can also be extended to complex functions and to systems of equations.

C code for finding a real root of  the equationf(x)= x*x*x-2*x-5 using Newton-Raphson Method

#include
//#include
#include
int main(){
    //clrscr();
    int i;
    float x,fx,fdx,t;
    printf("Enter x0: ");
    scanf("%f",&x);
    //freopen("file.txt","w",stdout);
    for(;;)
    {
        t=x;
        fx=pow(x,3)-(2*x)-5;
        fdx=3*pow(x,2)-2;
        x=t-(fx/fdx);
        printf("\nthe value of x is::%f\n",x);
        if(fabs(x-t)<=0.0001)
        {
            printf("The root is: %f",x);
            break;
        }
    }
    //fclose(stdout);
    getch();
    return 0;
}

sample output:

Enter x0: 2

the value of x is::2.100000

the value of x is::2.094568

the value of x is::2.094552
The root is: 2.094552

Implementation of Iterative Method

In computational mathematics, an iterative method is a mathematical procedure that generates a sequence of improving approximate solutions for a class of problems. A specific implementation of an iterative method, including the termination criteria, is an algorithm of the iterative method. An iterative method is called convergent if the corresponding sequence converges for given initial approximations. A mathematically rigorous convergence analysis of an iterative method is usually performed; however, heuristic-based iterative methods are also common.
In the problems of finding the root of an equation (or a solution of a system of equations), an iterative method uses an initial guess to generate successive approximations to a solution. In contrast, direct methods attempt to solve the problem by a finite sequence of operations. In the absence of rounding errors, direct methods would deliver an exact solution (like solving a linear system of equations Ax = b by Gaussian elimination). Iterative methods are often the only choice for nonlinear equations. However, iterative methods are often useful even for linear problems involving a large number of variables (sometimes of the order of millions), where direct methods would be prohibitively expensive (and in some cases impossible) even with the best available computing power.

C code to find a real root of the equation 2x=cosx+3 using Iterative method:

  /***********************************************************
* You can use all the programs on  www.engineercse.blogspot.com
* for personal and learning purposes.
* contact azam.ruet10@gmail.com
* To find more C programs, do visit www.engineercse.blogspot.com
* and browse!
*
*                            Coding is poetry!!!
***********************************************************/
#include
#include
#include
#include

int main(){
    int i;
    float f,a,b,x,t;
    scanf("%f",&x);
    //x=(a+b)/2;
    if((sin(x)/2)<1 br="">        for(i=0;i<2000 br="" i="">            t=f;
            //x=0;
            //f=0;
            f=(cos(x)+3)/2;
            printf("%f\n",x);
            //t=f;

            x=f;
            if(fabs(f-t)<=0.0001)
                break;
            //t=f;
        }
        printf("\nThe Root is: %f",x);
    }
    else
        printf("\nThe Method cannot be applied..");

    getch();
}

sample output: 90

90.000000
1.275963
1.645290
1.462788
1.553900
1.508448
1.531154
1.519816
1.525479
1.522651
1.524063
1.523358
1.523710
1.523534

The Root is: 1.523622

Implementing Bisection Method[Numerical Methods]

The method is applicable when we wish to solve the equation f(x) = 0 for the real variable x, where f is a continuous function defined on an interval [a, b] and f(a) and f(b) have opposite signs. In this case a and b are said to bracket a root since, by the intermediate value theorem, the f must have at least one root in the interval (a, b).
At each step the method divides the interval in two by computing the midpoint c = (a+b) / 2 of the interval and the value of the function f(c) at that point. Unless c is itself a root (which is very unlikely, but possible) there are now two possibilities: either f(a) and f(c) have opposite signs and bracket a root, or f(c) and f(b) have opposite signs and bracket a root. The method selects the subinterval that is a bracket as a new interval to be used in the next step. In this way the interval that contains a zero of f is reduced in width by 50% at each step. The process is continued until the interval is sufficiently small.
Explicitly, if f(a) and f(c) are opposite signs, then the method sets c as the new value for b, and if f(b) and f(c) are opposite signs then the method sets c as the new a. (If f(c)=0 then c may be taken as the solution and the process stops.) In both cases, the new f(a) and f(b) have opposite signs, so the method is applicable to this smaller interval.^[4]

C code implementing bisection method for the equation x*x*x-2*x-5
#include
#include
double f(double x)
{
    return (x*x*x-2*x-5);
}
int main()
{
    double a,b,x;
    scanf("%lf %lf",&a,&b);
    if((f(a)>=0 && f(b)>=0) || (f(a)<0 amp="" b="" br="" f="">    printf("possible\n");
    else
    {
       while(1)
       {
           x=(a+b)/2;
           printf("%lf\n",x);
           if(fabs(f(x)-0)<=0.001)
           {
               printf("%lf\n",x);
               break;
           }
           if((f(a)>=0 && f(x)>=0) || (f(a)<0 amp="" br="" f="" x="">              a=x;
           else
              b=x;
       }
    }
    getch();
    return 0;
}

sample o/p:
2 3
2.500000
2.250000
2.125000
2.062500
2.093750
2.109375
2.101563
2.097656
2.095703
2.094727
2.094238
2.094482
2.094482

Analysis :  

The method is guaranteed to converge to a root of f if f is a continuous function on the interval [a, b] and f(a) and f(b) have opposite signs. The absolute error is halved at each step so the method converges linearly, which is comparatively slow.

Specifically, if c₁ = (a+b)/2 is the midpoint of the initial interval, and c_n is the midpoint of the interval in the nth step, then the difference between c_n and a solution c is bounded by

This formula can be used to determine in advance the number of iterations that the bisection method would need to converge to a root to within a certain tolerance. The number of iterations needed, n, to achieve a given error (or tolerance), ε, is given by:
where
Therefore, the linear convergence is expressed by