Newton-Raphson Method – Algorithm, Implementation in C With Solved Examples


Numerical Methods & Algorithms / Friday, October 12th, 2018

To solve non-linear function of the real variable x we have already learned Bisection method and Iteration method, in this article we are going to learn Newton-Raphson method to solve the same.

Newton-Raphson Method or Method of Tangent

Let x0 be an approximate root of the equation f(x) = 0. Suppose x1 =x0 + h be the exact root of the equation, where h is the correction of the root. Then f(x1) =0.

Using Taylor’s series, f(x1) = f(x0 + h) is expanded in the following form
\[f\left( {{x}_{0}} \right)+hf’\left( {{x}_{0}} \right)+\frac{{{h}^{2}}}{2!}f”\left( {{x}_{0}} \right)+….=0\]
Neglecting the second and higher order derivatives the above equation reduces to
\[f\left( {{x}_{0}} \right)+hf’\left( {{x}_{0}} \right)=0\Rightarrow h=-\frac{f\left( {{x}_{0}} \right)}{f’\left( {{x}_{0}} \right)}\]
\[Hence,{{x}_{1}}={{x}_{0}}+h={{x}_{0}}-\frac{f\left( {{x}_{0}} \right)}{f’\left( {{x}_{0}} \right)}\]
To compute the value of h, the second and higher powers of h are neglected so the value of
\[h=-\frac{f\left( {{x}_{0}} \right)}{f’\left( {{x}_{0}} \right)}\]
is not exact, it is an approximate value. So, x1 obtained is not a root of the equation, but it is a better approximation of x than x0.

In general,
\[{{x}_{n+1}}={{x}_{n}}-\frac{f\left( {{x}_{n}} \right)}{f’\left( {{x}_{n}} \right)}…………(1)\]

This expression generates a sequence of approximate values x1, x2, ….,xn,… each successive tern of which is closer to the exact value of the root x than its predecessor. The method will terminate when |xn+1 – xn| becomes very small. In Newton-Raphson method the arc of the curve y = f(x) is replaced by a tangent to the curve, hence this method is sometimes called the method of tangents.

Algorithm of Newton-Raphson method

Step 1. Start the program.
Step 2. Define the function f(x), f’(x)
Step 3. Enter the initial guess of the root , say x0
Step 4. Calculate xn+1 = xn – [f(xn)/ f’(xn)], n = 0, 1, 2, …
Step 5. If |xn+1 – xn| < ϵ, ϵ being prescribed accuracy then go to step 7.
Step 6. Set xn = xn+1 and go to step 4.
Step 7. Print the value of xn.
Step 8. Stop the program.

Implementation of Newton-Raphson method in C

/* Program Newton-Raphson
   Program to find a root of the equation x*x*x - 3x + 1 =0 by
   Newton-Raphson method. f(x) and its derivative fd(x) are to
   be supplies.*/

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

void main()
{
	int k=0; //counts number of iterations
	float x1,x0; //x0 is the initial guess
	float eps=1e-5; //error tolerance
	float f(float x);
	float fd(float x);
	printf("\nEnter the initial guess x0 : ");
	scanf("%f",&x0);
	x1=x0;
	do
	{
		k++;
		x0=x1;
		x1=x0-f(x0)/fd(x0);
	}while(fabs(x1-x0)>eps);
	printf("One root is %8.5f obtained at %dth iteration",x1,k);
}

//definition of the function f(x)
float f(float x)
{
	return(x*x*x-3*x+1);
}

//definition of the function fd(x)
float fd(float x)
{
	return(3*x*x-3);
}

Output
Enter the initial guess x0 : 1.1
One root is 1.53209 obtained at 7 th iteration

 

 Example 01

Find a real root of the equation x2 + 2x = 2 correct to three significant figures by Newton-Raphson method.

Solution:

Let f(x) = x2 + 2x -2
Therefore f’(x) = 2x + 2
\[\text{So the iteration formula}~{{x}_{n+1}}={{x}_{n}}-\frac{f\left( {{x}_{n}} \right)}{f’\left( {{x}_{n}} \right)},~\text{gives}\]
\[{{x}_{n+1}}={{x}_{n}}-\frac{{{x}_{n}}^{2}+2{{x}_{n}}-2}{2{{x}_{n}}+2}=\frac{{{x}_{n}}^{2}+2}{2{{x}_{n}}+2}\left( n=0,1,2,… \right)\]
\[\text{Now }f\left( 0 \right)\text{ }=\text{ }-\text{2 }<0,\text{ }f\left( \text{1} \right)\text{ }=\text{ 1}>0\]
So a real root lies between 0 and 1. But for quick convergence we take x0 = 0.5. Then we have
\[{{x}_{1}}=\frac{{{x}_{0}}^{2}+2}{2{{x}_{0}}+2}=0.75\]
and similarly we get
\[{{x}_{2}}=0.7321,{{x}_{3}}=0.7320,{{x}_{4}}=0.7320\]
Thus the required real root is 0.732, correct to three significant figures.

 

 Example 02

Use Newton-Raphson method to find a positive root of the equation ex – 3x = 0, correct to four decimal places.

Solution:

Let f(x) = ex – 3x
Therefore f’(x) = ex – 3
So the iteration formula for Newton-Raphson method
\[{{x}_{n+1}}={{x}_{n}}-\frac{f\left( {{x}_{n}} \right)}{f’\left( {{x}_{n}} \right)},~\text{gives}\]
\[{{x}_{n+1}}={{x}_{n}}-\frac{{{e}^{{{x}_{n}}}}-3{{x}_{n}}}{{{e}^{{{x}_{n}}}}-3}=\frac{\left( {{x}_{n}}-1 \right){{e}^{{{x}_{n}}}}}{{{e}^{{{x}_{n}}}}-3}\left( n=0,1,2,… \right)\]
\[\text{Now }f\left( 1 \right)\text{ }=\text{ }-0.2817\text{ }<0,\text{ }f\left( 2 \right)\text{ }=\text{ 1}\text{.3890}>0\]
So a real root lies between 1 and 2. Taking x0 = 2, we have
\[{{x}_{1}}=\frac{\left( 2-1 \right){{e}^{2}}}{{{e}^{2}}-3}=1.68352\]
\[{{x}_{2}}=\frac{\left( 1.68352-1 \right){{e}^{1.68352}}}{{{e}^{1.68352}}-3}=1.54348\]
and similarly we get
\[{{x}_{3}}=1.51349,{{x}_{4}}=1.51214,{{x}_{5}}=1.51213\]
Hence a positive real root of the given equation correct to four decimal places is 1.5121

 

 Example 03

Using Newton-Raphson method, find the value of
\[\sqrt[4]{12}\]

Solution:
\[\text{Let}~x=\sqrt[4]{12}\Rightarrow {{x}^{4}}=12\]
\[\text{So let}~~f(x)={{x}^{4}}-12\Rightarrow f'(x)=4{{x}^{3}}\]
So the iteration formula for Newton-Raphson method
\[{{x}_{n+1}}={{x}_{n}}-\frac{f\left( {{x}_{n}} \right)}{f’\left( {{x}_{n}} \right)},~\text{gives}\]
\[{{x}_{n+1}}={{x}_{n}}-\frac{{{x}_{n}}^{4}-12}{4{{x}_{n}}^{3}}=\frac{3{{x}_{n}}^{4}+12}{4{{x}_{n}}^{3}}\left( n=0,1,2,… \right)\]
\[\text{Now }f\left( 0 \right)\text{ }=\text{ }-12\text{ }<0,\text{ }f\left( 1 \right)\text{ }=\text{ }-\text{110, }f\left( 2 \right)\text{ }=4>0\]
So a real root lies between 1 and 2. Taking x0 = 1.5, we have
\[{{x}_{1}}=\frac{3{{x}_{0}}^{4}+12}{4{{x}_{0}}^{3}}=2.0138\]
and similarly we get
\[{{x}_{2}}=1.8777,{{x}_{3}}=1.8614,{{x}_{4}}=1.8612\]
\[\text{Hence }\sqrt[4]{12}=1.861,~\text{correct to four significant figures}.\]

 

<< Previous     Next>>

;

Leave a Reply

Your email address will not be published. Required fields are marked *