Newton-Raphson Method

The Newton-Raphson method helps us locate an approximate real root of the given equation and improves its accuracy by a flow process.

Numerical Methods: Numerical Methods provide various techniques to find an approximate solution to a difficult problem using various operations. Numerical methods are easily adoptable to solving problems using computers as they involve sequential steps.

Here we are calculating

       a.    The numerical solution of algebraic and non-algebraic equations, and
       b.    The exact and numerical solution of a system of linear algebraic equations.

Numerical solution of Algebraic and Transcendental Equations: Given an equation f(x) = 0, it is generally not possible to find the roots such that f(x) becomes exactly zero. This topic deals with numerical methods of obtaining approximate roots of the given equation.

Equations involving algebraic quantities like x, x2 , x3,…etc are called algebraic equations.

Example : $x^{3} - 2x^{2}$ + x – 2 = 0, $x^{5} - x^{6}$ = 20
   
Equations that involves non-algebraic quantities like, ex , log |x| , sin x, tan x, …etc are called transcendental equations.

Example : $e^{x}$ – x = 0,  x ln |x| - 2 = 0, sin 2x = 5x

The Numerical methods of finding approximate roots of the given equation are a repetitive process known as the iteration process. In every step, the result of the previous step is used, and the process is carried out until we get the result to its desired accuracy. All the numerical methods are only approximate techniques for the solution of any problem and computers play a great role in various numerical methods for obtaining the result to the highest degree of accuracy.

    If (x) = 0 is a real valued continuous function of the real variable x, we get the following fundamental property:

    When there exist two values a, b such that f(x) has an opposite sign, say f(a)<0, f(b)>0 equivalently f(a), f(b) < 0 then there always exists at least one real root in the interval (a,b).

    Geometrically the property means that the graph of y = f(x) intersects the x-axis at least at one point, x0 that lies between a and b which is a real root of f(x) = 0.

This property is useful  in locating an initial approximation for a real root of f(x) = 0.

It is important to note that if the values of a, b of x lie near each other, then the numerical iterative methods will give the real root to the desired accuracy more quickly. In some methods, we have to locate an approximate root x = x0 for starting the iterative process. In which case, if the magnitude, say f(a), is nearer to zero compared to f(b), we prefer to take x = x0 = a as the initial approximation.

The two different iterative methods are

1.    The Newton-Raphson method
2.    The Regular - falsi method

Newton-Raphson Method Example

Example:
Show that the equation $x^{3}$ - 2x - 1 = 0 has a root between 1 and 2. Find the root correct to two decimal places using the Newton-Raphson method.

Solution:
Given f(x) = $x^{3}$ - 2x - 1

differentiate with respect to x
f'(x)=3$x^{2}$ - 2

Initial value x0=1
f(1) = $1^{3}$ - 2(1) - 1 = -2
f'(1)= 3$(1)^{2}$ - 2 = 1

x1= x0- $\frac{f(x0)}{f'(x0)}$

x1 = 1 - $(\frac{-2}{1})$

x1 = 3

f(3) = $3^{3}$ - 2(3) - 1 = 20
f'(3)= 3$(3)^{2}$ - 2 = 25

x2 = x1 - $\frac{f(x1)}{f'(x1)}$

x2 = 3 - $\frac{20}{25}$

x2 = 2.2

f(2.2)= $(2.2)^{3}$ - 2(2.2) -1 = 5.248
f'(2.2)= 3$(2.2)^{2}$ - 2 = 12.51

x3 = x2 - $\frac{f(x2)}{f'(x2)}$

x3 = 2.2 - $\frac{5.248}{12.51}$

x3 = 1.78

and continue until you get two numbers that are less than a predetermined limit.
x = 1.00000000, -2.0000000000
x = 3.00000000, 20.0000000000
x = 2.20000000, 5.2480000000
x = 1.78083067, 1.0859900367
x = 1.63630320, 0.1085760658
x = 1.61830458, 0.0015844130
x = 1.61803405, 3.553 e-70000

Hence root = 1.68


Example:
Equation f(x)= 5 sin 3x  ,where $\frac{p}{4}$ = x = $\frac{p}{2}$ ( p = pi ) .Use newton raphson to find approximate value at which f(x)=0.

Solution:
Xo= $\frac{\frac{p}{4} + \frac{p}{2}}{2}$ = $\frac{0.7854 + 1.5708}{2}$ = 1.1781

since, f(x)= 5 sin 3x
f'(x) = 15 cos 3x

Newton Raphson  formula: Xn+1 = Xn - $\frac{f(xn)}{f'(xn)}$

for n=0,
f(1.1781)=5 sin 3(1.1781)= -1.91
f'(1.1781) = 15 cos (3( 1.1781))=-13.86

X1 = X0 - $\frac{f(x0)}{f'(x0)}$

X1 = 1.1781-( -1.91)/(-13.86)=1.0402

Now n=1,
f(1.0402)=5 sin (3(1.0402))= 0.104956
f'(1.0402) = 15 cos (3( 1.0402))=-14.9967
 
X2 = X1 - $\frac{sin3(X1)}{3 \ cos3(X1)}$

X2 = 1.0402 - $\frac{0.104956}{-14.9967}$

X2 =1.04719

Now n=2,
f(1.04719) = 5 sin (3(1.04719)) = 0.0001132
f'(1.04719) = 15 cos (3(1.04719)) = -14.99999

X3 = X2  - $\frac{sin3 \ (X2)}{3 \ cos3(X2)}$

X3 = 1.04719  -  $\frac{0.0001132}{-14.99999}$

X3 = 1.04719

Hence the root=1.04719

Newton-Raphson Algorithm

Let f(x) = 0, be the given equation and x0 be an approximate root of the equation. If h is a small correction applied to the root, then x0 + h is the exact root and we try to find h such that f (x0 + h) = 0.

Using Taylor’s expansion of f(x0 + h) , we have,

f(x0) + h f ' (x0) +   f '' (x0) + …………………. = 0

Since h is a small quantity, h2 , h3 ,…………….. being even smaller can be neglected.

Hence we have, f(x0 ) + h f ' (x0 ) = 0

⇒      h = - $\frac{f(x_{0})}{f'(x_{0})}$

The first approximation  to the root x0 is given by, x1 = x0 + h

(i.e)               x1 = x0$\frac{f(x_{0})}{f'(x_{0})}$ , provided $f'(x_{0})$ $\neq$ 0

The second approximation is obtained by replacing x0  by x1.

(i.e)              x2 = x1$\frac{f(x_{1})}{f'(x_{1})}$


In general, xn+1 = xn$\frac{f(x_{n})}{f'(x_{n})}$


This is called the Newton-Raphson iterative formula.

Newton Raphson Practice


Question :
Show that f(x) = (x^4+2)/5 - x has 2 positive roots. Use Newton-Raphson Method to find these roots, correct to 3 decimal points. 

Question :
How to use Newton-Raphson method to fi nd the solution of x-e^-x=0.
 

Practice Problems

Question 1: Use three iteration of the Newton-Raphson method to estimate a root of the equation f(x) = 0 starting at the indicated value of x1 = 5
f(x) = $x^{2}$ - 24.
Question 2: Show that f(x) = $\frac{x^{4} + 2}{5} $ - x has 2 positive roots. Use Newton-Raphson Method to find these roots, correct to 3 decimal points.