NEWTON-RAPHSON METHOD OF SOLVING A

NONLINEAR EQUATION
ABDULBASIT R SEIF

107-063061-01122
Department of Computer science
2010

Abstract
This paper presents the idea of Newton-Raphson method
for solving non linear equation. The paper starts with ALGORITHM
derivation of the Newton-Raphson method formula, and The steps of the Newton-Raphson method to find the
then develops the algorithm of the Newton-Raphson root of an equation f ( x ) = 0 are
method, pointing out the computational time of the
1. Evaluate f ′( x ) symbolically
algorithm then use the Newton-Raphson method to solve
a nonlinear equation, and discuss the drawbacks of the 2. Use an initial guess of the root, xi , to
Newton-Raphson method. estimate the new value of the root, x i +1 , as
Keywords f ( xi )
Newton-Raphson, tolerance, absolute relative xi +1 = xi −
approximate error, converge, diverge. f ′( xi )
Introduction 3. Find the absolute relative approximate error
In the Newton-Raphson method, only one initial guess ∈a as
of the root is needed to get the iterative process started
to find the root of an equation. The method hence falls xi +1 − x i
∈a = ×10 0
in the category of open methods. xi +1
Derivation
4. Compare the absolute relative approximate
The Newton-Raphson method is based on the principle
error with the pre-specified relative error
that if the initial guess of the root of f ( x ) = 0 is at x i
tolerance, ∈s . If ∈ a >∈ s , then go to
, then if one draws the tangent to the curve at f ( xi ) , Step 2, else stop the algorithm. Also, check
the point x i +1 where the tangent crosses the x -axis is if the number of iterations has exceeded the
an improved estimate of the root . maximum number of iterations allowed. If
Using the definition of the slope of a function, at x = xi so, one needs to terminate the algorithm and
f ′( xi ) = tan θ notify the user.

f ( xi ) − 0 ALGORITHM DEVELOPMENT
= ,
xi − xi + 1
Algorithm: Newton-Raphson
which gives
f ( xi ) INPUT: f, , tolerance
xi +1 = xi −
f ′( xi ) OUTPUT:
Find the value of x that maximizes f(x)
Equation is called the Newton-Raphson formula for METHOD
solving nonlinear equations of the form f ( x ) = 0 . So
starting with an initial guess, x i , one can find the next {
guess, x i +1 , by using Equation . One can repeat this
process until finds the root within a desirable tolerance. While
 {
2
do Iteration 1
2 n+1 The estimate of the root is
c1 = 2c 0 − c 02 a
= 2(0.5) −(0.5) 2 ( 2.5)
9n (n+1)
= 0.375
1 n The absolute relative approximate error ∈a at the end
of Iteration 1 is
c − c0
∈a = 1 ×100
} c1
0.375 −0.5
} = ×100
0.375
= 33.333%
The number of significant digits at least correct is 0, as
you need an absolute relative approximate error of less
ALGORITHM ANALYSIS
than 5% for one significant digit to be correct in your
Computational time
T = 2+2(n+1)n + 9(n+1)n + n result.
T = 9n2 + 12n + 4
T(n) = 9n2 +12n + 4
Iteration 2
T ≈ O(n2)
The estimate of the root is
TABLE c 2 = 2c1 − c12 a
= 2(0.375 ) −(0.375 ) 2 ( 2.5)
T(n) 1 2 3 4 5 = 0.39844
n2 1 4 9 16 25
The absolute relative approximate error ∈ a at the end
Graph of Iteration 2 is
c − c1
∈a = 2 ×100
c2
0.39844 −0.375
= ×100
0.39844
= 5.8824 %
The number of significant digits at least correct is 0.

Iteration 3
The estimate of the root is
c3 = 2c 2 − c 22 a
a , given the equation = 2(0.3984 ) − (0.3984 ) 2 ( 2.5)
To find the inverse of a number
1 = 0.39999
f (c ) = a − = 0 The absolute relative approximate error ∈ at the end
c a

where c is the inverse of a . of Iteration 3 is

0.39999 − 0.39844
∈a = ×100
Let us take the initial guess of the root of f ( c ) = 0 0.39999
as c 0 = 0.5 . = 0.38911 %
Hence the number of significant digits at least correct is
given by the largest value of m for which
∈a ≤ 0.5 ×10 2 −m AN INTRODUCTION TO NUMERICAL ANALYSIS
0.38911 ≤ 0.5 ×10 2−m Endre Suli and David F. Mayers
0.77821 ≤ 10 2 −m http://www.ma.man.ac.uk/higham
log ( 0.77821 ) ≤ 2 − m
m ≤ 2 − log ( 0.77821 ) = 2.1089 http://www.rit.edu/vwlsps/uncertainties
So
m=2 http://numericalmethods.eng.usf.edu
The number of significant digits at least correct in the
estimated root 0.39999 is 2.

Drawbacks of the Newton-Raphson Method

Divergence at inflection points
If the selection of the initial guess or an iterated value of
the root turns out to be close to the inflection point (see
the definition in the appendix of this chapter) of the
function f ( x ) in the equation f ( x ) = 0 , Newton-
Raphson method may start diverging away from the
root. It may then start converging back to the root.

Oscillations near local maximum and minimum

Results obtained from the Newton-Raphson method may
oscillate about the local maximum or minimum without
converging on a root but converging on the local
maximum or minimum. Eventually, it may lead to
division by a number close to zero and may diverge.
Root jumping
In some case where the function f ( x ) is oscillating
and has a number of roots, one may choose an initial
guess close to a root. However, the guesses may jump
and converge to some other root.
Conclusion
It can be clearly seen that in the algorithm method
is particularly well suited for computer application
because the repetitive calculations and decision
making steps are easy and quick for a computer to
make.

REFERENCES

MATHEMATICS FOR COMPUTER SCIENTISTS,

Gareth J. Janacek & Mark Lemmon Close

NUMERICAL METHODS
THIRD EDITION
Doug Faires and Dick Burden