Numerical Analysis

Dr Syed Muhammad Ghufran

August 11, 2020

ii
Contents

1 The Numerical Solution of Non-Linear Equations 1

1.1 Finding Roots of Equations . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.1.1 Classification of Equations . . . . . . . . . . . . . . . . . . . . . . . 2

1.2 Numerical Iterative methods . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.2.1 Bisection Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.2.2 The Newton-Raphson Method:- . . . . . . . . . . . . . . . . . . . . 23

1.3 Error term of Newtion Raphson Method . . . . . . . . . . . . . . . . . . . 25

1.3.1 The Secant Method (1st Derivation) . . . . . . . . . . . . . . . . . 44

1.4 Error term of Secant Method . . . . . . . . . . . . . . . . . . . . . . . . . 45

1.4.1 Regula Falsi Method . . . . . . . . . . . . . . . . . . . . . . . . . . 50

2 Solution Non-Linear Function 55

2.1 Direct Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

2.2 Iterative Method or Indirect Method of Solution . . . . . . . . . . . . . . . 55

2.3 Termination of an Iterative Procedure . . . . . . . . . . . . . . . . . . . . . 55

2.4 Solution of Non-linear Equation . . . . . . . . . . . . . . . . . . . . . . . . 56

2.5 Numerical methods of solving Non-Linear equations . . . . . . . . . . . . 57

2.6 Newton-Raphson Method . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

2.7 Order of Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

iii
iv CONTENTS

2.8 Simple or First order Iteration . . . . . . . . . . . . . . . . . . . . . . . . . 61

2.9 Second order iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

2.10 Simple Iterative Procedure or Fixed Point Method . . . . . . . . . . . . . . 63

2.11 Convergence of Simple Iterative Procedure . . . . . . . . . . . . . . . . . . 63

2.12 Error Analysis of Simple Iterative Method . . . . . . . . . . . . . . . . . . 71

2.13 Acceleration of Convergence: Aitken’s ∆2 process or Aitken’s Method . . . 72

2.14 The Secant Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

2.15 The Bisection Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

Chapter 1

The Numerical Solution of

Non-Linear Equations

Introduction

One of the most frequently occurring problems in scientific work is to find the roots of an
equation of the form
f (x) = 0 (1.1)

The function f (x) may be given explicitly as, for example, a polynomial or a
transcendental function. Frequently, however, f (x) may be known only implicitly in that
only a rule for evaluating it on any argument is known. In rare cases it may be possible
to obtain the exact roots such as in the case of a factorizable polynomial. In general,
however, we can hope to obtain only approximate values of the roots, relying on some
computational techniques to produce the approximation. In this lecture, we will
introduce some elementary iterative methods for finding a root of equation (2.1), in
other words, a zero of f (x).

1.1 Finding Roots of Equations

• We are examining equations with one independent variable.

• Equations may be linear or Non-linear.

• Non-linear equations may be polynomials or generally non-linear equations.

• A root of the equation is simply a value of the independent variable that satisfies
the equation.

1
2 CHAPTER 1. THE NUMERICAL SOLUTION OF NON-LINEAR EQUATIONS

1.1.1 Classification of Equations

• Linear:- Independent variable appears to the first power only, either alone or
multiplied by a constant.

• Non-linear:-

– Polynomial:- independent variable appears raised to powers of positive

integers only.
– General non-linear:- all other equations.

1.2 Numerical Iterative methods

1.2.1 Bisection Method

Definition. The Bisection method in mathematics is a root finding method which

repeatedly bisects an interval and then selects a subinterval in which a root must lie for
further processing.

• It is a very simple and robust method, but it is also relatively slow.

• The method is also called ”The interval Halving Method.”

Suppose a continuous function f (x) defined on the interval [a, b] is given with
f (a) and f (b) of opposite sign. Then by intermediate value theorem there exists r,
a < r < b for which f (r) = 0. Although the procedure will work for the case when f (a)
and f (b) has opposite signs and there is more than one root in [a, b] but it will be
assumed for simplicity that the root in [a, b] is unique. The method calls for a repeated
halving (dividing into two equal parts) subintervals of [a, b], and at each step locating
the half containing r.
To begin let a1 = a, b1 = b and m1 be the mid point of [a, b] i.e. m1 = a+b 2 . If
f (m1 ) = 0 then r = m1 but if not , then f (m1 ) has the same sign as either f (a) or f (b).

If f (m1 ).f (a1 ) < 0, then r ∈ (a1 , m1 ). We get the new interval (a2 , b2 ), where
a2 = a1 and b2 = m1 .

If f (m1 ).f (b1 ) < 0, then r ∈ (m1 , b1 ) and we get the new interval (a2 , b2 ) where
a2 = m1 , b2 = b1 where
b1 − a 1
b2 − a2 =
2
b1 − a 1
= 2−1
2
1.2. NUMERICAL ITERATIVE METHODS 3

Repeating the process n − times we obtain the Bisection method.

a n + bn
mn = , where n = 1, 2, 3, ...
2

Where 
(a
n−1 , mn−1 ) if f (an−1 ).f (mn−1 < 0),
(an , bn ) =
(m
n−1 , bn−1 ) if f (mn−1 ).f (bn−1 ) < 0.

and
b1 − a1
bn − a n =
2n−1
b−a
= n−1 .
2
We have the mid point of the last interval as approximation to the root.

Figure 1.1: Bisection Method

• Bisection method steps:-

Step1. Find points a and b such that a < b and f (a).f (b) < 0.
a+b
Step2. Take the interval [a, b] and find next value x1 = 2
Step3. If f (x1 ) = 0 then x1 is an exact root,
– else if f (a).f (x1 ) < 0 then b = x1 ,
– else if f (x1 ).f (b) < 0 then a = x1 ,
Step4. Repeat steps 2 and 3 until f (xi ) = 0 or |f (xi )| ≤ accuracy
Theorem. If f (x) is continuous on [a, b] and f (a) and f (b) have oposite signs
i.e.(f (a)f (b) < 0), then f (x) vanishes at least once in (a, b).

This follows from the indeterminate value theorem. Graphically we see it quite clearly. If
at a the curve lies above x − axis and at b it lies below x − axis, then it must cross the
x − axis at least once.
4 CHAPTER 1. THE NUMERICAL SOLUTION OF NON-LINEAR EQUATIONS

Algorithm for Bisection Method

Given a continuous function f (x) on [a, b]

1. Find points a and b such that f (a)f (b) < 0

2. Take the interval [a, b] and find its midpoint x1

3. If f (x1 = 0 then x1 is an exact root, else if f (x1 )f (b) < 0 then let a = x1 , else if
f (a)f (x1 ) < 0 then let b = x1

4. Repeat steps 2 and 3 until f (xi ) = 0 or |f (xi )| <= DOA, where DOA stands for
degree of accuracy.

Example. Find the solution of

x2 = ln x + 3

with a = 1, b = 2 using Bisection method (5-iterations).

Solution 1. Given that

f (x) = x2 − ln x − 3

and [a, b] = [1, 2].


f (1) = 12 − ln 1 − 3 = 1 − 3 = −2 < 0, (−ve)
f (2) = 22 − ln 2 − 3 = 1 − ln 2 = 0.307 > 0. (+ve)

Hence the roots of the given function lies in (1, 2).

• 1st iteration:- (1, 2)

1+2
– Since f (1) < 0, and f (2) > 0, x1 = 2 = 1.5

f (x1 ) = f (1.5) = (1.5)2 − ln(1.5) − 3 = −1.1555 < 0

∴ f (1.5) < 0, and f (2) > 0.

So the root of the given function lies between (1.5, 2).

• 2nd iteration:- (1.5, 2)

1.5+2
– Since f (1.5) < 0, and f (2) > 0 then x2 = 2 = 1.75

f (x2 ) = f (1.75) = (1.75)2 − ln(1.75) − 3 = −0.4971 < 0

∴ f (1.75) < 0, and f (2) > 0.

So the root of the given function lies between (1.75, 2).

1.2. NUMERICAL ITERATIVE METHODS 5

• 3rd iteration:- (1.75, 2)

1.75+2
– Since f (1.75) < 0, and f (2) > 0 then x3 = 2 = 1.875

f (x3 ) = f (1.875) = (1.875)2 − ln(1.875) − 3 = −0.1129 < 0

∴ f (1.875) < 0, and f (2) > 0.

So the root of the given function lies between (1.875, 2).

• 4th iteration:- (1.875, 2)

1.875+2
– Since f (1.875) < 0, and f (2) > 0 then x4 = 2 = 1.9375

f (x4 ) = f (1.9375) = (1.9375)2 − ln(1.9375) − 3 = 0.0925 > 0

∴ f (1.875) < 0, and f (1.9375) > 0.

So the root of the given function lies between (1.875, 1.9375).

• 5th iteration:- (1.875, 1.9375)

1.875+1.9375
– Since f (1.875) < 0, and f (1.9375) > 0 then x5 = 2 = 1.9063

f (x5 ) = f (1.9063) = (1.9063)2 − ln(1.9063) − 3 = −0.01118 < 0

∴ f (1.9063) < 0, and f (1.9375) < 0.

So the root of the given function lies between (1.9063, 1.9375).

Remark. If an error tolerance ε is prescribed then the approximate number of the iterations
required may be determined from the relation.

[log(b − a) − log ε]
n≥ .
log 2

Theorem. Let f (x) be a contiuous function on [a, b] and suppose f (a).f (b) < 0. The
Bisection method generates a sequence xn approximating r with the property

b−a
|xn − r| ≤ , n≥1
2n

Note:-
bn − a n
|xn − r| ≤ ,
22
1/2(b − a)
≤ ,
2n−1
b−a b−a
≤ n−1+1 = n .
2 2
6 CHAPTER 1. THE NUMERICAL SOLUTION OF NON-LINEAR EQUATIONS

Example. Determine approximately how many iterations (step) are necessary to solve

f (x) = x6 − x − 1

with an accuracy of ǫ = 10−3 for [a, b] = [1, 2].

Solution 2. It is required to find an integer n that will satisfy

b1 − a1
|xn − r| ≤ < ǫ = 10−3 ,
2n
b1 − a1 2−1
n
< 10−3 ⇒ < 10−3 ,
2 2n
2−n < 10−3 ⇒ log 2−n ≤ log 10−3
− n log(2) ≤ −3 log(10),
3
n log(2) ≥ 3 log(10), ⇒ n ≥ = 9.969.
log(2)

Therefore, n ≥ 10 i.e. 10 iterations are required to obtain an approximation accuracy 10−3 .

Similarly we can obtain by the formula

log(b − a) − log ǫ
n≥ .
log 2

Example. Use the Bisection method to find the approximate zero accurate to with in
10−2 for x3 − x − 1 on [1, 2].
Solution 3. Given that f (x) = x3 − x − 1 and [a, b] = [1, 2].

Since we know that

log(b − a) − log ǫ
n≥ ,
log 2
log(2 − 1) − log 10−2
≥ ,
log 2
log 1 − (−2) log 10 2 log 10
≥ = ,
log 2 log 2
n ≥ 6.64 = 7.

Hence the approximate no of iterations required in 7. Now the sequence of iteration using
Bisection method are obtained as follows.

f (1) = 13 − 1 − 1 = −1 < 0, (−ve)
f (2) = 23 − 2 − 1 = 5 > 0. (+ve)

Hence the roots of the given function lies in (1, 2).

• 1st iteration:- (1, 2)

1.2. NUMERICAL ITERATIVE METHODS 7

1+2
– Since f (1) < 0, and f (2) > 0, x1 = 2 = 1.5

f (x1 ) = f (1.5) = (1.5)3 − 1.5 − 1 = 0.875 > 0

∴ f (1) < 0, and f (1.5) > 0.

So the root of the given function lies between (1, 1.5).

• 2nd iteration:- (1, 1.5)

1+1.5
– Since f (1) < 0, and f (1.5) > 0 then x2 = 2 = 1.25

f (x2 ) = f (1.25) = (1.25)3 − (1.25) − 1 = −0.2969 < 0

∴ f (1.25) < 0, and f (1.5) > 0.

So the root of the given function lies between (1.25, 1.5).

• 3rd iteration:- (1.25, 1.5)

1.25+1.5
– Since f (1.25) < 0, and f (1.5) > 0 then x3 = 2 = 1.375

f (x3 ) = f (1.375) = (1.375)3 − 1.375 − 1 = 0.2246 > 0

∴ f (1.25) < 0, and f (1.375) > 0.

So the root of the given function lies between (1.25, 1.375).

• 4th iteration:- (1.25, 1.375)

1.25+1.375
– Since f (1.25) < 0, and f (1.375) > 0 then x4 = 2 = 1.3125

f (x4 ) = f (1.3125) = (1.30125)3 − 1.33125 − 1 = −0.0515 < 0

∴ f (1.3125) < 0, and f (1.375) > 0.

So the root of the given function lies between (1.3125, 1.375).

• 5th iteration:- (1.3125, 1.375)

1.3125+1.375
– Since f (1.3125) < 0, and f (1.375) > 0 then x5 = 2 = 1.34375

f (x5 ) = f (1.34375) = (1.34375)3 − 1.34375 − 1 = 0.0826 > 0

∴ f (1.3125) < 0, and f (1.34375) > 0.

So the root of the given function lies between (1.3125, 1.34375).

• 6th iteration:- (1.3125, 1.34375)

8 CHAPTER 1. THE NUMERICAL SOLUTION OF NON-LINEAR EQUATIONS

1.3125+1.34375
– Since f (1.3125) < 0, and f (1.34375) > 0 then x6 = 2 = 1.328125

f (x6 ) = f (1.328125) = (1.328125)3 − 1.328125 − 1 = 0.01458 > 0

∴ f (1.3125) < 0, and f (1.328125) > 0.

So the root of the given function lies between (1.3125, 1.328125).

• 7th iteration:- (1.3125, 1.328125)

– Since f (1.3125) < 0, and f (1.328125) > 0 then

x7 = 1.3125+1.328125
2 = 1.3203125

f (x7 ) = f (1.3203125) = (1.3203125)3 − 1.3203125 − 1 = −0.0187 < 0

∴ f (1.3203125) < 0, and f (1.328125) > 0.

n an bn xn f (xn )
1 1 2 1.5 f (1.5) > o
2 1 1.5 1.25 f (1.25) < o
3 1.375 1.5 1.375 f (1.375) > o
4 1.25 1.375 1.3125 f (1.3125) < o
5 1.3125 1.375 1.34375 f (1.34375) > o
6 1.3125 1.34375 1.328125 f (1.328125) > o
7 1.3125 1.328125 1.320313 f (1.320313) < o

Table 1.1: Bisection Method

After the 7th iteration we find that the root lies in the interval
(1.3125, 1.328125). and is equal to 1.3203125. Hence the approximate zero
accurate to within 10−2 for x3 − x − 1 = 0 on [1, 2] is 1.3203125.

Check:-

b−a
|xn − r| ≤ ,
2n
a = 1, b = 2, xn = 1.328125, r = 1.320313,
2−1
|1.328125 − 1.320313| ≤ ,
27
1
0.007812 ≤ ,
128
0.007812 ≤ 0.0078125
√
3
Example. Find the approximation to 25 correct to 3 significant digits using Bisection
method in (2, 3).
1.2. NUMERICAL ITERATIVE METHODS 9

Solution 4. Let
√ 1
25 = 25( 3 ) ,
3
x=
x3 = 25,
x3 − 25 = 0.

Given that
f (x) = x3 − 25

and (a, b) = (2, 3).

Now the sequence of iteration using Bisection method are obtained as follows.

f (2) = 23 − 25 = −17 < 0, (−ve)
f (3) = 33 − 25 = 2 > 0. (+ve)

Hence the roots of the given function lies in (2, 3). The sequence of iterates using Bisection
Method is obtained as. Therefore, after the 11th iteration we get the root 2.924 which is

n an bn xn f (xn )
1 3 3 2.5 f (2.5) < o
2 2.5 3 2.75 f (2.75) < o
3 2.75 3 2.875 f (2.875) < o
4 2.875 3 2.9375 f (2.9375) > o
5 2.875 2.9375 2.9063 f (2.9063) < o
6 2.9063 2.9375 2.9219 f (2.9219) < o
7 2.9219 2.9375 2.9297 f (2.9297) > o
8 2.9219 2.9297 2.9258 f (2.9258) > o
9 2.9219 2.9258 2.9238 f (2.9238) < o
10 2.9238 2.9258 2.9248 f (2.9248) > o
11 2.9238 2.9248 2.9243 f (2.9243) > o

Table 1.2: Bisection Method

correct to 3-decimal places.

Check:-

b−a
|xn − r| ≤ ,
2n
a = 2, b = 3, xn = 2.924, r = 2.9248,
3−2
|2.9248 − 2.9243| ≤ 1 ,
2 1
1
|0.0005| ≤ ,
2048
0.0005 ≤ 0.0004
10 CHAPTER 1. THE NUMERICAL SOLUTION OF NON-LINEAR EQUATIONS

Example. Find the interval in which the smallest +ve root of the following equation lies
x3 − x − 4 = 0.
Determine two roots correct to three decimal places, using Bisection method.
Solution 5. Let
f (x) = x3 − x − 4.

x = 1, f (1) = 13 − 1 − 4 = −4 < 0, (−ve)
x = 2, f (2) = 23 − 2 − 4 = 2 > 0. (+ve)

Therefore, the root lies between 1 and 2. So the (a, b) = (1, 2). The sequence od iterates
using Bisection method is obtained as.

n an bn xn f (xn )
1 1 2 1.5 f (1.5) = −2.125 < o
2 1.5 2 1.75 f (1.75) = −0.390 < o
3 1.75 2 1.875 f (1.875) = 0.716 > o
4 1.75 1.875 1.8125 f (1.8125) = 0.1418 > o
5 1.75 1.8125 1.78125 f (1.78125) = −0.1296 < o
6 1.78125 1.8125 1.7968 f (1.7968) = 0.004 > o
7 1.78125 1.7968 1.7890 f (1.7890) = −0.0632 < o
8 1.7890 1.7968 1.793 f (1.793) = −0.028 < o
9 1.793 1.7968 1.795 f (1.795) − −0.0114 < o

Table 1.3: Bisection Method

Therefore, after the 9th iteration we get the root 1.79 which is correct to 2-decimal
places.

Check:-

b−a
|xn − r| ≤ ,
2n
a = 1, b = 2, xn = 1.793, r = 1.795,
2−1 1
|1.793 − 1.795| ≤ 9
, =⇒ |0.002| ≤ ,
2 512
0.002 ≤ 0.001

The Bisection Method:- This method requires two starting values x0 and x1 for the
solution of non-linear equation f (x) = 0, such that f (x0 )f (x1 ) < 0, i.e; root lies between
x0 and x1 . The method start as follows.

1. Find x2 using
x0 + x1
x2 =
2
(mid-point of x0 and x1 ) and find f (x2 ).
1.2. NUMERICAL ITERATIVE METHODS 11

2. If f (x2 ) = 0, the x2 is a root of f (x) = 0. If f (x2 ) 6= 0, two things are possible.

(a) If f (x0 )f (x2 ) < 0, compute new iterate x3 as

x0 + x2
x3 =
2

and evaluate f (x3 ).

(b) If f (x1 )f (x2 ) < 0, compute new iterate x3 as

x2 + x1
x3 =
2

and evaluate f (x3 ).

The process is then repeated with new points until the desired accuracy obtained.
Note:- This method is very simple but is very slow to converge. However, the
convergence is guaranteed. For this reason, the method is often used for solving
Non-linear equation. This method is particularly useful when we have to find the roots
using a computer programme.
Example. Write the equation x2 − N = 0 in the form x = g(x) in the ways and form
√
sequence which converges to N .

Solution. Since
x2 − N = 0,

x2 = N

N
(i) x = x = g(x).
x2 −N
(ii) x − 2 = g(x).
x2 −N
(iii) x − 2x = g(x).

Consider

x2 − N
g(x) = x − ,
2x
1 N
=x− x+ ,
2 2x
1 N
xi+1 = x+ .
2 2x
√
Now , N is a fixed point of g(x) = 12 x + N
2x .

Since
√ 1√ N
g( N ) = N+ √ ,
2 2 N
12 CHAPTER 1. THE NUMERICAL SOLUTION OF NON-LINEAR EQUATIONS

√ 1√ 1√
g( N ) = N+ N,
2 2
√ √
g( N ) = N .

Also,
′ 1 N
− 2
g (x) =
2 2x
′ √ 1 N
|g ( N )| = | − √ 2 |
2 2 N
′ √ 1 1
|g ( N )| = | − | = 0 < 1.
2 2
√
=⇒ N is point of attraction for g(x).
√
∴⇒ xi+1 = g(x) converges to N.
Example. Consider the eq ex − 9x2 = 0 it has a root r1 between −1 and 0 and other
between 5 and 6.

xi /2
Solution. Let x1 = 0 and xi+1 = − e 3

(i) Show that the sequence {xi } converges to r1 (−1 < r1 < 0) .

(ii) Take x1 = 5, does sequence converges to r2 .

(iii) Find an iteration for g(x) show that the sequence xi+1 = g(xi ) may converge to r2 .
(with x1 = 5)

(i) xi
e2
g(x) = −
3
xi
′ e2
g (x) = − , ⇒ xi ǫ(−1, 0).
6
Now xi
′ e2 e0 1
|g (x)| = | − | ⇒ = <1
6 6 6

⇒ iteration will converge tor1 .

′
⇒ |g (x)| < 1, ri ǫ(−1, 0)

⇒ r1 is point of attraction for g(x)

∴ sequence xi+1 −→ r1 .

(ii)
exi /2
xi+1 = −
3
1.2. NUMERICAL ITERATIVE METHODS 13

exi /2
xi+1 = − ,
3
let x1 = 5
e5/2
x2 = − = −4.0608,
3
−4.0608
e 2
x3 = − = −0.0438,
3
x4 = −0.3261,
x5 = −0.2831,
x6 = −0.2893,
x7 = −0.2884,
x8 = −0.2885,
x9 = −0.2885,
x10 = −0.2885.

Therefore, sequence converges to r1 . So taking x1 = 5, it does not converges to r2 .

(iii)

exi /2
xi+1 = − ,
3
ex = 9x2 ,
x = ln(9x2 ) = g(x),
′ 1
g (x) = 2 18x.
9x

x
for xǫ(5, 6), is max. at x = 5
2
.
′ x 2
|g (x)| = | | ≤ < 1
2 5
′
∴ for r2 ǫ(5, 6), |g (x)| < 1.

∴ r2 is point of attraction for g(x).

14 CHAPTER 1. THE NUMERICAL SOLUTION OF NON-LINEAR EQUATIONS

∴ xi+1 = ln(9x2 ) converges to r2 .

xi+1 = ln[(9)x2 ],
let x1 = 5
x2 = ln(952 ) = 5.416,
x3 = 5.575,
x4 = 5.634,
x5 = 5.654,
x6 = 5.662,
x7 = 5.664,
x8 = 5.665,
x9 = 5.666,
x10 = 5.666,
x11 = 5.666.

Therefore, sequence converges to r2 = 5.666

Example. The eq. x6 = x4 + x3 + 1 has a root between 1 and 2. Find a root to 4-dp.

Solution.
f (x) = x6 − x4 − x3 − 1
′
f (x) = 6x5 − 4x3 − 3x2

f (1) = 16 − 14 − 13 − 1 = −2 < 0, (−ve)
f (2) = 26 − 24 − 23 − 1 = 39 > 0. (+ve)
1.2. NUMERICAL ITERATIVE METHODS 15

By Newton’s method

f (xi )
xi+1 = xi − ′ ,
f (xi )
x6 − x4 − x3 − 1
xi+1 = xi − i 5 i 3 i 2 , (1.2)
6xi − 4xi − 3xi
Let x1 = 1,
x61 − x41 − x31 − 1
x2 = x1 − ,
6x51 − 4x31 − 3x21
(1)6 − (1)4 − (1)3 − 1
x2 = 1 − ,
6(1)5 − 4(1)3 − 3(1)2
1−1−1−1
=1− ,
6−4−3
2
x2 = 1 + = −1,
−1
x2 = −1 .

x62 − x42 − x32 − 1

x3 = x2 − ,
6x52 − 4x32 − 3x22
(−1)6 − (−1)4 − (−1)3 − 1
x3 = −1 − ,
6(−1)5 − 4(−1)3 − 3(−1)2
1−1+1−1
= −1 − ,
−6 + 4 − 3
0
x3 = −1 + = −1,
−5
x3 = −1 .

x62 − x42 − x32 − 1

x4 = x2 − ,
6x52 − 4x32 − 3x22
(−1)6 − (−1)4 − (−1)3 − 1
x4 = −1 − ,
6(−1)5 − 4(−1)3 − 3(−1)2
1−1+1−1
= −1 − ,
−6 + 4 − 3
0
x4 = −1 + = −1,
−5
x4 = −1 .

Therefore, root of eq. is −1. But −1 6∈ [1, 2].

16 CHAPTER 1. THE NUMERICAL SOLUTION OF NON-LINEAR EQUATIONS

Let x1 = 2, i = 1,
x61 − x41 − x31 − 1
x2 = x1 − ,
6x51 − 4x31 − 3x21
(2)6 − (2)4 − (2)3 − 1 64 − 16 − 8 − 1
x2 = 2 − =2− ,
6(2)5 − 4(2)3 − 3(2)2 192 − 32 − 12
39
x2 = 2 − = 1.7365,
148
x2 = 1.7365 .

Now x2 = 1.7365,
x62 − x42 − x32 − 1
x3 = x2 − ,
6x52 − 4x32 − 3x22
(1.7365)6 − (1.7365)4 − (1.7365)3 − 1
x3 = 1.7365 − ,
6(1.7365)5 − 4(1.7365)3 − 3(1.7365)2
12.0897
= 1.7365 − ,
64.7467
x3 = 1.7365 − 0.1867 = 1.5498,
x3 = 1.5498 .

Now x3 = 1.5498,
x63 − x43 − x33 − 1
x4 = x3 − ,
6x53 − 4x33 − 3x23
x4 = 1.4431,
x4 = 1.4431 .

Now x4 = 1.4431,
x64 − x44 − x34 − 1
x5 = x4 − ,
6x54 − 4x34 − 3x24
x5 = 1.4073,
x6 = 1.4036,
x7 = 1.4036,
x8 = 1.4036.

Therefore, root of the eq. is 1.4036.

Note. We can proceed from x1 = 1.5.

Example. Find the smallest +ve root of tan(x) + tanh(x) = 0 upto 4-dp.
1.2. NUMERICAL ITERATIVE METHODS 17

Solution.
f (x) = tan(x) + tanh(x)
′
f (x) = sec2 xi + sech2 xi



 f (2) = tan(2) + tanh(2) = −2.18504 + 0.96403,


f (2) = −1.2210 < 0, (−ve),




 f (3) = tan(3) + tanh(3) = −0.14255 + 0.99505,


f (3) = 0.8525 > 0. (+ve)


By Newton’s method

f (xi )
xi+1 = xi − ,
f ′ (xi )
tan xi + tanh xi
xi+1 = xi − , (1.3)
sec2 xi + sech2 xi
Let x1 = 2, i = 1.
tan x1 + tanh x1
x2 = x1 − ,
sec2 x1 + sech2 x1
tan(2) + tanh(2)
x2 = 2 − ,
sec2 (2) + sech2 (2)
(−2.1850 + 0.9640)
x2 = 2 − ,
(5.7744 + 0.0707)
x2 = 2.2089,
x3 = 2.3388,
x4 = 2.3643,
x5 = 2.3650,
x2 = 2.3650.

Example. Find the iteration between the curves

y = ex−2 (1.4)

y = ln(x + 2) (1.5)

upto 4-dp, x > 0.

Solution. From eq(2.4) put in eq(2.5)

ex−2 = ln(x + 2)

f (x) = ex−2 − ln(x + 2)

′ 1
f (x) = ex−2 −
x+2
18 CHAPTER 1. THE NUMERICAL SOLUTION OF NON-LINEAR EQUATIONS



 f (−1) = e−1−2 − ln(−1 + 2) = 0.0498 − 0,


f (−1) = 0.0498 > 0, (+ve),




 f (0) = e−2 − ln(2) = 0.135335 − 0.693147,


f (0)

= −0.557812 < 0. (−ve)

By Newton’s method

f (xi )
xi+1 = xi − ,
f ′ (xi )
(exi −2 − ln(xi + 2))
xi+1 = xi − x −2 ,
(e i − 1/(xi + 2))
Take x1 = −1, i = 1,
(ex1 −2 − ln(x1 + 2)) (e−1−2 − ln(−1 + 2))
x2 = x1 − x
= −1 − ,
(e 1 − 1/(x1 + 2))
−2 (e−1−2 − 1/(−1 + 2))
(e−3 − ln(1)) 0.04979 − 0)
= −1 − −3 = −1 − ,
(e − 1/(1)) 0.04979 − 1
x2 = −1 + 0.0524 = −0.9476,
x3 = −0.9460,
x4 = −0.9460.

Therefore, root is x = −0.9460, putting in eq(2.4) or eq(2.5).

from eq(2.4) we have y = ex−2 = e−0.4960−2 = e−2.9460 = 0.0526.

from eq(2.5) we have y = ln(x + 2) = ln(−0.4960 + 2) = ln(1.054) = 0.0526.

Therefore, point of intersection is (-0.9460, 0.0526).

Example. Show that if α is the double root of f (x) = 0, then the iteration

f (xi
xi+1 = xi −
f ′ (xi )

converges to α not quadratically but geometrically.

Solution. Since α is the double root of

′
f (x) = 0, f (α) = 0, and f (α) = 0.

We have

f (xi )
xi+1 = xi − ′ ,
f (xi )
f (xi − α + α)
xi+1 − α = xi − α − ′ .
f (xi − α + α)
1.2. NUMERICAL ITERATIVE METHODS 19

We define
ǫi+1 = xi+1 − α.

(error between actual value α and computed value xi+1 ).

f (α + ǫi )
ǫi+1 = ǫi − ,
f ′ (α + ǫi )
Apply Taylor’s theorem,
′ ′′
f (α) + ǫi f (α) + (1/2)ǫ2i f (α) + ....
ǫi+1 = ǫi − ′ ,
f (α) + ǫi f (α) + (1/2)ǫ2i f (α) + ....
′′ ′′′

′′
0 + 0 + (1/2)ǫ2i f (α) + ....
ǫi+1 = ǫi − ′′ ,
0 + ǫi f (α) + ....
′′
(1/2)ǫ2i f (α) + ....
ǫi+1 = ǫi − ,
ǫi f ′′ (α) + ...

neglecting O(ǫi ) from the denominator,

′′ ′′′
(1/2)ǫ2i f (α) + (1/3!)ǫ3i f (α)....
ǫi+1 = ǫi − ,
ǫi f ′′ (α)
′′ ′′′
1/2ǫ2i f (α) (1/6)ǫ3i f (α)
ǫi+1 = ǫi − + ,
ǫi f ′′ (α) ǫi f ′′ (α)
′′′
ǫi (1/6)ǫ2i f (α)
= ǫi − − ,
2 f ′′ (α)
′′′
ǫi (1/6)ǫ2i f (α)
= − ′′ ,
2 f (α)
ǫi
ǫi+1 = − Kǫ2i ,
2
′′′
1 f (α)
where, K = .
6 f ′′ (α)

f (xi )
xi+1 = xi − → α not quadratically.
f ′ (xi )
ǫi
Since term 2 is also involved.

Example. Show that if α is the double root of f (x) = 0, then iteration

f (xi )
xi+1 = xi − 2
f ′ (xi )

converges to α quadratically.

Solution. Since α is the double root of

′
f (x) = 0, f (α) = 0, and f (α) = 0.
20 CHAPTER 1. THE NUMERICAL SOLUTION OF NON-LINEAR EQUATIONS

We have

f (xi )
xi+1 = xi − 2 ,
f ′ (xi )
f (xi − α + α)
xi+1 − α = xi − α − 2 ′ .
f (xi − α + α)

We define
ǫi+1 = xi+1 − α.

(error between actual value α and computed value xi+1 ).

f (ǫi + α)
ǫi+1 = ǫi − 2 ,
f ′ (ǫi + α)
Apply Taylor’s theorem,
′ ′′
f (α) + ǫi f (α) + (1/2)ǫ2i f (α) + ....
ǫi+1 = ǫi − 2 ′ ,
f (α) + ǫi f ′′ (α) + (1/2)ǫ2i f ′′′ (α) + ....
′′
0 + 0 + (1/2)ǫ2i f (α) + ....
ǫi+1 = ǫi − 2 ,
0 + ǫi f ′′ (α) + ....
′′ ′′′
2[(1/2)ǫ2i f (α) + (1/3!)ǫ3i f (α)....]
ǫi+1 = ǫi − ,
ǫi f ′′ (α) + ...

neglecting O(ǫi ) from the denominator,

′′ ′′′
2(1/2)ǫ2i f (α) + 2(1/6)ǫ3i f (α)....
ǫi+1 = ǫi − ,
ǫi f ′′ (α)
′′ ′′′
ǫ2 f (α) (1/3)ǫ3i f (α)
ǫi+1 = ǫi − i ′′ + ′′ ,
ǫi f (α) ǫi f (α)
′′′
(1/3)ǫ2i f (α)
= ǫi − ǫi − ,
f ′′ (α)
′′′
(1/3)ǫ2i f (α)
=− ,
f ′′ (α)

ǫi+1 = Kǫ2i ,
′′′
1 f (α)
where, K=− .
3 f ′′ (α)

f (xi )
=⇒ xi+1 = xi − 2 → α quadratically.
f ′ (xi )

Example. Generalise the results if α be zero of order m of f (x) = 0, then iteration

f (xi )
xi+1 = xi − m
f ′ (xi )

converges to α quadratically.
1.2. NUMERICAL ITERATIVE METHODS 21

′ ′′
Solution. Let α be zero of order 3. i.e. f (α) = 0, f (α) = 0, f (α) = 0. We have

f (xi )
xi+1 = xi − 3 ,
f ′ (xi )
f (xi − α + α)
xi+1 − α = xi − α − 3 ′ .
f (xi − α + α)

We define
ǫi+1 = xi+1 − α.

(error between actual value α and computed value xi+1 .

f (ǫi + α)
ǫi+1 = ǫi − 3 ′ ,
f (ǫi + α)
Apply Taylor’s theorem,
′ ′′ ′′′
f (α) + ǫi f (α) + (1/2!)ǫ2i f (α) + (1/3!)ǫ3i f (α) + ....
ǫi+1 = ǫi − 3 ,
f ′ (α) + ǫi f ′′ (α) + (1/2!)ǫ2i f ′′′ (α) + ....
′′′ ′′′′
0 + 0 + 0 + (1/3!)ǫ3i f (α) + (1/4!)ǫ4i f (α) + ....
ǫi+1 = ǫi − 3 ,
0 + 0 + (1/2!)ǫ2i f ′′′ (α) + ....
′′′ ′′′′
(1/3!)ǫ3i f (α) + (1/4!)ǫ4i f (α) + ....
ǫi+1 = ǫi − 3 ,
(1/2!)ǫ2i f (α) + ...
′′′

neglecting O(ǫi ),
′′′ ′′′′
[(1/3!)ǫ3i f (α) + (1/4!)ǫ4i f (α)]
ǫi+1 = ǫi − 3 ,
(1/2!)ǫ2i f ′′′ (α)
′′′ ′′′′
(1/3)ǫ3i f (α) ǫ4i f (α)
ǫi+1 = ǫi − (3/2) − (3/2)(1/12) ,
(1/2)ǫ2i f ′′′ (α) (1/2)ǫ2i f ′′′ (α)
′′′′
ǫ2i f (α)
ǫi+1 = ǫi − ǫi − (1/4) ,
f ′′′ (α)
′′′′
(1/4)ǫ2i f (α)
=− ,
f ′′′ (α)
′′′′
f (α)
ǫi+1 = Kǫ2i , where, K = −(1/4) .
f ′′′ (α)

f (xi )
∴ xi+1 = xi − 3 → α quadratically.
f ′ (xi )
Generally, Let α be zero of order m.
22 CHAPTER 1. THE NUMERICAL SOLUTION OF NON-LINEAR EQUATIONS

′ ′′
∴, f (α) = 0, f (α) = 0, f (α) = 0, . . . . f (m−1) (α) = 0,

(m+1) (m+1)
[(1/m!)ǫm
i f
(m) (α) + 1/(m + 1)!ǫ
i f (α)]
ǫi+1 = ǫi − m (m−1) (m)
,
1/(m − 1)!ǫi f (α)
(m) (m) (m+1) (m+1)
[(1/m(m − 1)!)ǫi f (α) + (1/(m + 1)m(m − 1)!)ǫi f (α)]
ǫi+1 = ǫi − m (m−1) (m)
,
(1/(m − 1)!)ǫi f (α)
(m) (m) (m+1) (m+1)
(m/m(m − 1)!)ǫi f (α) (m/(m + 1)m(m − 1)!)ǫi f (α)
ǫi+1 = ǫi − [ (m−1) (m)
+ (m−1) (m)
],
(1/(m − 1)!)ǫi f (α) (1/(m − 1)!)ǫi f (α)

(m−m+1) 1 ǫ2i f (m+1) (α)

ǫi+1 = ǫi − [ǫi + ],
(m + 1) f (m) (α)
1 ǫ2i f (m+1) (α)
ǫi+1 = ǫi − ǫi − ],
(m + 1) f (m) (α)
1 ǫ2i f (m+1) (α)
ǫi+1 = − ],
(m + 1) f (m) (α)
1 ǫ2i f (m+1) (α) 1 f (m+1) (α)
ǫi+1 = − = Kǫ2i , where, K=− .
(m + 1) f (m) (α) (m + 1) f (m) (α)

f (xi )
∴ xi+1 = xi − m → α quadratically.
f ′ (xi )

Exercise 1

1. The function f (x) = x3 + 4x2 − 10, has a root in [a, b] = [1, 2]. Approximate the
root correct to 3-dp by Bisection method.

2. The function f (x) = x2 − 3, has a root in [a, b] = [1, 2].

3. The function f (x) = exp−x (3.2sinx − 0.5cosx), has a root in [a, b] = [3, 4], by using
the Bisection Method.

4. Find a root of the function f (x) = x3 + x + 1, by using the Bisection Method on the
interval [a, b] = [0, 1].

5. Find a root of the function f (x) = x6 − x − 1, by using the Bisection Method on the
interval [a, b] = [1, 2]. ǫ = 0.001.

6. Determine the number of iterations necessary to solve f (x) = x3 + 4x2 − 10 with

accuracy 10−3 using a = 1 and b = 2.

7. Find x4 to approximate positive square root of 3 using Bisection method.

8. Find the root of the function f (x) = x4 + 10x2 − 6, by using Bisection method.
1.2. NUMERICAL ITERATIVE METHODS 23

9. Solve the transidental equation

f (x) = e−x − sin x,

to find a positive real root by Bisection method. By inspection method the initial
values are x0 = 0 and x1 = 1. Ans. x = 0.445313

10. Solve the equation

f (x) = x3 − x2 − 2x + 1

by Bisection method to evaluate a positive root. By inspection method the initial

values are x0 = 0 and x1 = 1. Ans. x = 0.4454

11. Find a positive real root of

x
f (x) = sin x −
2
π 77π
with x0 = 2 and x1 = π, using Bisection method. Ans. x = 128 .

12. Find the root of the function f (x) = ex − 5x2 , by using Bisection method.

13. Find a +ve root using Bisection method of the function f (x) = x2 − 2x − 3.

1.2.2 The Newton-Raphson Method:-

In the Newton-Raphson method, the root is not bracketed. In fact, only one initial guess
of the root is needed to get the iterative process started to find the root of an equation.
The method hence falls in the category of open methods. Convergence in open methods
is not guaranteed but if the method does converge, it does so much faster than the
bracketing methods.

• Derivation:- Start by choosing an initial value for x that’s fairly close to the root.
We will call it x0 . Draw a tangent to the curve at that x- value. The point where
the tangent touches the curve is (x0 , f (x0 )) and the gradient of the line segment is
′
f (x0 ). The equation of the tangent is

y − y1 = m(x − x1 ),
′ (1.6)
y − f (x0 ) = f (x0 )(x − x0 ).

If we can find the x-coordinate of the point where the tangent crosses the x-axis,
let’s call it x1 then that will bring us closer to the actual root, α. The tangent line
crosses at some point say (x1 , 0) so we substitute y = 0, and x = x1 into the
equation (2.2) of the tangent

′
0 − f (x0 ) = f (x0 )(x1 − x0 ).
24 CHAPTER 1. THE NUMERICAL SOLUTION OF NON-LINEAR EQUATIONS

Now rearrage this to get x1 .

′ ′ ′
f (x0 )x1 = f (x0 )x0 − f (x0 ),
f (x0 ) ′
x1 = x0 − ′ , f (x0 ) 6= 0. (1.7)
f (x0 )

Usually x1 will be closer to α than x0 . The next improved appriximation x2 can be

simply apply eq(2.3) with x1 in place of x0 and x2 in place of x1 this yeilds

f (x1 ) ′
x2 = x1 − , f (x1 ) 6= 0.
f ′ (x1 )

The process is repeated as until a sufficiently accurate value is reached. More

generaly
f (xn )
xn+1 = xn − ′ , n = 0, 1, 2, .... (1.8)
f (xn )
Eq(2.4) is called Newton-Raphson Method.

• How to find an initial guess x0 fot the solution

Suppose f (x) = 0 is a given non-linear equation. If x0 is not given, we can obtaine
it by variuos methods such as

1. Draw the graph of y = f (x), x0 is that value which crosses the x-axis or ( x0 is
the value which is close to the point where the curve crosses x-axis)
2. We rearrange f (x) as f (x) = f1 (x) + f2 (x) and draw f1 (x) and f2 (x) x0 will
be the point of intersection of these curves (or point close to the point of
intersection).
3. We construct a table of values of x and f (x) for different values of x. x0 is
taken near that value where the sign of f (x) changes.
Here f (x1 ) < 0, f (x2 ) > 0 therefore the root lies between x1 and x2 .

Newtion Raphson Method (Derivation)

′
Take a point (a, f (a)) on the curve such that a lies close to α, slope at a, is f (a).
Equation of the tangent
y − f (a) ′
= f (a)
x−a
y − f (x1 ) ′
= f (x1 )
x − x1
the point where it intersects x − axis is (x2 , 0)

0 − f (x1 ) ′
= f (a)
x2 − x1
1.3. ERROR TERM OF NEWTION RAPHSON METHOD 25

f (x1 )
x2 = x1 − ′
f (x1 )
..
.
f (xi )
xi+1 = xi − , i = 0, 1, 2, 3. . .
f ′ (xi )

1.3 Error term of Newtion Raphson Method

′
Let α be a simple root of f (x) = 0, i.e. f (α) = 0, f (α) 6= 0. We have

f (xi )
xi+1 = xi − ,
f ′ (xi )
f (α + xi − α)
xi+1 − α = xi − α − ′ .
f (α + xi − α)

Define xi+1 − α = ǫi+1 , (error between actual value α and computed value xi+1 ).

f (α + ǫi )
ǫi+1 = ǫi − ,
f ′ (α + ǫi )
Apply Taylor’s theorem,
′ ′′
f (α) + ǫi f (α) + (1/2)ǫ2i f (α) + ....
ǫi+1 = ǫi − ′ ,
f (α) + ǫi f ′′ (α) + (1/2)ǫ2i f ′′′ (α) + ....
′ ′′
0 + ǫi f (α) + (1/2)ǫ2i f (α) + ....
ǫi+1 = ǫi − ′ ,
f (α) + ǫi f ′′ (α) + (1/2)ǫ2i f ′′′ (α) + ....
′ ′′
ǫi f (α) + (1/2)ǫ2i f (α) + ....
ǫi+1 = ǫi − ′ ,
f (α) + ǫi f ′′ (α) + (1/2)ǫ2i f ′′′ (α) + ....

neglecting O(ǫi ) from the denominator,

′ ′ ′′
ǫi f (α) − ǫi f (α) − (1/2)ǫ2i f (α)
ǫi+1 = ,
f ′ (α)
′′ ′′
1 f (α) 1 f (α)
ǫi+1 = − ǫ2i ′ = Kǫ2i , ⇒ where, K=− .
2 f (α) 2 f ′ (α)

For this reaseon we say that Newton’s method converges quadratically.

Example. Solve the following equation correct to 4 significant figures using

Newton-Raphson method.
x3 − 5x2 − 29 = 0.

Here
f (x) = x3 − 5x2 − 29,
′
f (x) = 3x2 − 10x.
26 CHAPTER 1. THE NUMERICAL SOLUTION OF NON-LINEAR EQUATIONS

x 0 1 2 3 4 5 6
f (x) −29 −33 −41 −47 −45 −29 7

The root lies between (5, 6). Let x0 = 6,

f (xn )
xn+1 = xn − ′ , n = 0, 1, 2, ...,
f (xn )
f (x0 )
for n = 0, x1 = x0 − ′ ,
f (x0 )
f (6) 7
=6− ′ = 6 − , ⇒ x1 = 5.8542 ,
f (6) 48
f (x1 )
for n = 1, x2 = x1 − ′ ,
f (x1 )
f (5.8542)
= 5.8542 − ′ ,
f (5.5842)
[(5.5842)3 − 5(5.5842)2 − 29]
x2 = 5.5842 − , ⇒ x2 = 5.84799
3(5.5842)2 − 10(5.5842)
f (x2 )
for n = 2, x3 = x2 − ′ ,
f (x2 )
f (5.84799)
= 5.84799 − ′ ,
f (5.84799)
[(5.84799)3 − 5(5.84799)2 − 29]
x3 = 5.84799 − , ⇒ x3 = 5.84798 .
3(5.84799)2 − 10(5.84799)

Thus x3 = 5.84798 converges to 4-dp.

Example. Find the iterative method based on the Newton-Raphson method for finding
sqaure root of N , where N is a +ve real number. Apply the method to

1. N = 18 to obtain the result correct to two decimal place.

2. N = 3 to obtain the result correct to six decimel places.

Solution 6. Let
√ 1
x= N = (N ) 2 ,
x2 = N,
we have, f (x) = x2 − N,
′
f (x) = 2x.
1.3. ERROR TERM OF NEWTION RAPHSON METHOD 27

Using Newton-Raphson method

f (xn )
xn+1 = xn − , n = 0, 1, 2, ...,
f ′ (xn )
(x2 − N )
xn+1 = xn − n ,
2xn
xn N
= xn − ( − ),
2 2xn
xn N
= xn − + ,
2 2xn
xn N
= + ,
2 2xn
1 N
xn+1 = (xn + ), n = 0, 1, 2, 3, ....
2 xn

Next for N = 18, then f (x) = x2 − 18

x 0 1 2 3 4 5
f (x) −18 −17 −14 −9 −2 6

The root lies between (4, 5). Let us take x0 = 4, and N = 18,

1 N 1 18
for n = 0, x1 = (x0 + ) = (4 + ),
2 x0 2 4
x1 = 4.25 ,
1 N 1 18
for n = 1, x2 = (x1 + ) = (4.25 + ),
2 x1 2 4.25
x2 = 4.2426 ,
1 N 1 18
for n = 2, x3 = (x2 + ) = (4.2426 + ) = x3 = 4.2426 .
2 x2 2 4.2426

The root correct to 2-dp is 4.24.

1
Example. Find the iterative method based on the Newton-Raphson method for N,
where N is a +ve real number. Apply the method to N = 18.
Let
1
x=
N
1
f (x) = − N
x
′ 1
f (x) = − 2 , x =6= 0,
x
Using Newton-Raphson method to obtain the iterative scheme

f (xn )
xn+1 = xn −
f ′ (xn )
28 CHAPTER 1. THE NUMERICAL SOLUTION OF NON-LINEAR EQUATIONS

(1/xn − N )
xn+1 = xn −
−1/x2n
xn+1 = xn + (xn − N x2n )

xn+1 = xn + xn − N x2n

xn+1 = 2xn − N x2n

xn+1 = xn (2 − N xn )

For N = 18, take x0 = 0.1

xn+1 = xn (2 − 18xn )

continue to solve
Example. Find the iterative method based on the Newton-Raphson method for cube
root of N , where N is a +ve real number. Apply the method to N = 18.
Let
x = N 1/3

f (x) = x3 − N
′
f (x) = 3x2
Example. Find the root of x6 − x − 1 = 0 in (1, 2) by using Newton-Raphson method.
Home-work
Example. Use Newton-Raphson method find to 4-dp the root near 0.5 of the equation
e−x − sinx = 0
Solution 7. Here take x0 = 0.5.

f (x) = e−x − sin x,

′
f (x) = −e−x − cos x,
′
f (x) = −(e−x + cos x).

Apply Newton-Raphson method.

f (xn ) ′
xn+1 = xn − , f (xn ) 6= 0, n = 0, 1, 2, ...
f ′ (xn )

(e−xn − sin xn )
xn+1 = xn + ,
(e−xn + cos xn )
for n = 0,
(e−x0 − sin x0 )
x1 = x0 + ,
(e−x0 + cos x0 )
(e−0.5 − sin(0.5))
x1 = 0.5 + ,
(e−0.5 + cos(0.5))
x1 = 0.58564.
1.3. ERROR TERM OF NEWTION RAPHSON METHOD 29

for n = 1,
(e−x1 − sin x1 )
x2 = x1 + ,
(e−x1 + cos x1 )
(e−0.58564 − sin(0.58564))
x2 = 0.58564 + −0.58564 ,
(e + cos(0.58564))
x2 = 0.58853.

for n = 2,
(e−x2 − sin x2 )
x3 = x2 + ,
(e−x2 + cos x2 )
(e−0.58853 − sin(0.58853))
x3 = 0.58853 + −0.58853 ,
(e + cos(0.58853))
x3 = 0.58853

Hence the required root to 4-dp is x = 0.5885

Example. Find the root of x3 − 3x − 3 = 0 to 4-dp using Newton-Raphson method, that

lie near x = 2.
′
Solution 8. Here, f (x) = x3 − 3x − 3, f (x) = 3x2 − 3, x0 = 2.

Apply Newton-Raphson method.

f (xn ) ′
xn+1 = xn − ′ , f (xn ) 6= 0, n = 0, 1, 2, ....,
f (xn )

(x3n − 3xn − 3)
xn+1 = xn − ,
(3x2n − 3)
for n = 0,
(x30 − 3x0 − 3)
x1 = x0 − ,
(3x20 − 3)
(23 − 3(2) − 3)
x1 = 2 − ,
(3(22 ) − 3)
x1 = 2.11111 .

for n = 1,
(x31 − 3x1 − 3)
x2 = x1 − ,
(3x21 − 3)
((2.1111)3 − 3(2.11111) − 3)
x2 = 2.11111 − ,
(3(2.11111)2 − 3)
x2 = 2.10384 .

for n = 2,
(x32 − 3x2 − 3)
x3 = x2 − ,
(3x22 − 3)
((2.10384)3 − 3(2.10384) − 3)
x3 = 2.10384 − ,
(3(2.10384)2 − 3)
x3 = 2.10380 .
30 CHAPTER 1. THE NUMERICAL SOLUTION OF NON-LINEAR EQUATIONS

for n = 3,
(x33 − 3x3 − 3)
x4 = x3 − ,
(3x23 − 3)
((2.10380)3 − 3(2.10380) − 3)
x4 = 2.10380 − ,
(3(2.10380)2 − 3)
x4 = 2.10380 .

Hence the required root to 4-dp is x = 2.1038

Example. Using the Newton-Raphson method evaluate to 2-dp the root of the equation
which lie between 0 and 1 the equation is

f (x) = ex − 3x.

Solution 9. Here
f (x) = ex − 3x,
′
f (x) = ex − 3,
Apply Newton-Raphson method and let take x0 = 0.

f (xn ) ′
xn+1 = xn − ′ , f (xn ) 6= 0, n = 0, 1, 2, ...,
f (xn )
(exn − 3xn )
xn+1 = xn − .
(exn − 3)

for n = 0,
(ex0 − 3x0 )
x1 = x0 − ,
(ex0 − 3)
(e0 − 3(0))
=0− ,
(e0 − 3)
x1 = 0.5

for n = 1,
(ex1 − 3x1 )
x2 = x1 − ,
(ex1 − 3)
(e0.5 − 3(0.5))
= 0.5 − ,
(e0.5 − 3)
x2 = 0.61006.

for n = 2,
(ex2 − 3x2 )
x3 = x2 − ,
(ex2 − 3)
(e0.61006 − 3(0.61006))
= 0.0.61006 − ,
(e0.61006 − 3)
x3 = 0.61900.
1.3. ERROR TERM OF NEWTION RAPHSON METHOD 31

for n = 3,
(ex3 − 3x3 )
x4 = x3 − ,
(ex3 − 3)
(e0.61900 − 3(0.61900))
= 0.0.61900 − ,
(e0.61900 − 3)
x4 = 0.61906.

for n = 4,
(ex4 − 3x4 )
x5 = x4 − .
(ex4 − 3)
(e0.61906 − 3(0.61906))
= 0.0.61906 − ,
(e0.61906 − 3)
x5 = 0.61906.

Hence the required root to 4-dp is x = 0.6191

Note. We can also take x0 = 1 then

(ex0 − 3x0 ) (e1 − 3(1))

for n = 0, x1 = x0 − =1− = 0,
(ex0 − 3) (e1 − 3)
(ex1 − 3x1 ) (e0 − 3(0))
for n = 1, x2 = x1 − =0− = 0.5,
(ex1 − 3) (e0 − 3)
x2 = 0.5.

Similarly follow the above same procedure. We have x3 = 0.61006, x4 = 0.61900,

x5 = 0.61906 and x6 = 0.61906.

Example. Determine the positive real root of the equation 4sinx = ex up-to 4-dp using
Newton-Raphson method in the interval (0, 0.5).

Solution 10. Here

f (x) = 4 sin x − ex ,
′
f (x) = 4 cos x − ex .

Apply Newton-Raphson method and take x0 = 0.

f (xn ) ′
xn+1 = xn − ′ , f (xn ) 6= 0, n = 0, 1, 2, ....,
f (xn )
(4 sin xn − exn )
xn+1 = xn − .
4 cos xn − exn )
32 CHAPTER 1. THE NUMERICAL SOLUTION OF NON-LINEAR EQUATIONS

for n = 0,
(4 sin x0 − ex0 )
x1 = x0 − ,
4 cos x0 − ex0 )
(4 sin(0) − e0 )
x1 = 0 − ,
4 cos(0) − e0 )
x1 = 0.33333,

for n = 1,
(4 sin x1 − ex1 )
x2 = x1 − ,
4 cos x1 − ex1 )
(4 sin(0.33333) − e0.33333 )
x2 = 0.33333 − ,
4 cos(0.33333) − e0.33333 )
x2 = 0.36975 .
for n = 2,
(4 sin x2 − ex2 )
x3 = x2 − ,
4 cos x2 − ex2 )
(4 sin(0.36975) − e0.36975 )
x3 = 0.36975 − ,
4 cos(0.36975) − e0.36975 )
x + 3 = 0.37056 .
for n = 3,
(4 sin x3 − ex3 )
x4 = x3 − ,
4 cos x3 − ex3 )
(4 sin(0.37056) − e0.37056 )
x4 = 0.37056 − ,
4 cos(0.37056) − e0.37056 )
x4 = 0.37056.

Hence the required root to 4-dp is x = 0.3706

Note. Do the above question by taking x0 = 0.5.

Example. Find the smallest positive root to the equation
Z x
2
10 e−x dt = 1
0

with six correct decimals by Newton-Raphson method.

Solution 11. Here Z x
2
10 e−x dt = 1
0
Z x
−x2
10e dt = 1
0
2
10e−x [t]x0 dt = 1
2
10e−x [x − 0] = 1
2
10e−x x − 1 = 0
1.3. ERROR TERM OF NEWTION RAPHSON METHOD 33

Let

2
f (x) = 10e−x x − 1,
′ 2
f (x) = 10e−x (1 − 2x2 ).

when x = 0, then f (0) = 0 − 1 = −1 = −ve < 0,

when x = 1, then f (1) = 10e−1 1 − 1 = +ve > 0.

Since f (x) changes the sign between 0 and 1.

Apply Newton-Raphson method.

f (xn ) ′
xn+1 = xn − , f (xn ) 6= 0, n = 0, 1, 2, ....,
f ′ (xn )
2
(10xn e−xn − 1)
xn+1 = xn −
10e−x2n (1 − 2x2n )

Follow the procedure as in previous example and complete the question correct to 3-dp.

Example. The equation f (x) = 0 where

x2 x3 x4 x5
f (x) = 0.1 − x + − + − + ...
(2!)2 (3!)2 (4!)2 (5!)2

has one root correct to 5-dp using Newton-Raphson method.

Solution 12. We use Newton-Raphson method as

f (xn ) ′
xn+1 = xn − ′ , f (xn ) 6= 0, n = 0, 1, 2, ....,
f (xn )

x2 x3 x4 x5
f (x) = 0.1 − x + − + − + ...,
(2!)2 (3!)2 (4!)2 (5!)2
2x 3x2 4x3 5x4
f ′ (x) = 0 − 1 + − + − + ...,
4 36 576 14400
x x2 x3 x4
f ′ (x) = −1 + − + − + ....
2 12 144 2880

when x = 0, then f (0) = +ve > 0,

when x = 1, then f (1) = −ve < 0.

Since f (x) changes the sign between 0 and 1.

Note: Here we use Bisection method to have better start for x0 .

Let us take x0 = 0.2

34 CHAPTER 1. THE NUMERICAL SOLUTION OF NON-LINEAR EQUATIONS

for n = 0,
f (x0 )
x1 = x0 − ,
f ′ (x0 )
f (0.2)
x1 = 0.2 − ′ ,
f (0.2)
(0.2)2 3
(0.1 − 0.2 + (2!)2
− (0.2)
(3!)2
+ ....)
x1 = 0.2 − (0.2) (0.2)2 (0.2)3 (0.2)4
,
(−1 + 2 − 12 + 144 − 2880 ....)
x1 = 0.100120.

for n = 1,
f (x1 )
x2 = x1 − ,
f ′ (x1 )
f (0.100120)
x2 = 0.100120 − ′ ,
f (0.100120)
x2 = 0.102600.

for n = 2,
f (x2 )
x3 = x2 − ,
f ′ (x2 )
f (0.102600)
x3 = 0.102600 − ′ ,
f (0.102600)
x3 = 0.102602.

Hence the root correct to 5-dp is 0.102600

Example. Find all the roots of cos x − x2 − x = 0 correct to 5-dp.

Solution 13. Let f (x) = cos x − x2 − x. We have

• f (0) = 1 > 0, • f (−1) = 0.5403 > 0,

f (1) = −1.4597 < 0, f (−2) = −2.4161 < 0,
f (2) = −5.416 < 0, f (−3) = −6.99 < 0,

Since f (x) changes the sign between 0 and 1, also between −1 and −2. Hence
f (x) has root in the intervals (0, 1) and another root in the interval (−2, −1).
Note: Here we use Bisection method to have better start for x0 .

n an bn xn f (xn )
1 0 1 0.5 f (0.5) >0
2 0.5 1 0.75 f (0.75) <0
3 0.5 0.75 0.625 f (0.625) <0

Table 1.4: Bisection Method for interval (0, 1)

1.3. ERROR TERM OF NEWTION RAPHSON METHOD 35

n an bn xn f (xn )
1 −2 −1 0.5 f (0.5) <0
2 −1.5 −1 0.75 f (0.75) >0
3 −1.25 −1 0.625 f (0.625) >0

Table 1.5: Bisection Method for interval (−2, −1)

So take better initial guess for interval (0, 1), is x0 = 0.5 while for the interval
(−2, −1) is x0 = −1.5.

f (x) = cos x − x2 − x,
f ′ (x) = − sin x − 2x − 1,
f ′ (x) = −(sin x + 2x + 1).

Apply Newton-Raphson method.

f (xn )
xn+1 = xn − , where f ′ (xn ) 6= 0, n = 0, 1, 2, ....,
f ′ (xn )
(cos xn − x2n − xn )
xn+1 = xn − ,
−(sin xn + 2xn + 1)
(cos xn − x2n − xn )
xn+1 = xn + .
(sin xn + 2xn + 1)

Let us take x0 = −1.5

for n = 0,
(cos x0 − x20 − x0 )
x1 = x0 + ,
(sin x0 + 2x0 + 1)
(cos(−1.5) − (−1.5)2 − (−1.5))
x1 = −1.5 + ,
(sin(−1.5) + 2(−1.5) + 1)
(0.07074 − 2.25 + 1.5)
x1 = −1.5 + ,
(−0.99749 − 3 + 1)
x1 = −1.2734

for n = 1,
(cos x1 − x21 − x1 )
x2 = x1 + ,
(sin x1 + 2x1 + 1)
(cos(−1.2734) − (−1.2734)2 − (−1.2734))
x2 = −1.2734 + ,
(sin(−1.2734) + 2(−1.2734) + 1)
(0.2930 − 1.6215 + 1.2734)
x2 = −1.2734 + ,
(−0.9561 − 2.5468 + 1)
x2 = −1.2514
36 CHAPTER 1. THE NUMERICAL SOLUTION OF NON-LINEAR EQUATIONS

for n = 2,
(cos x2 − x22 − x2 )
x3 = x2 + ,
(sin x2 + 2x2 + 1)
(cos(−1.2514) − (−1.2514)2 − (−1.2514))
x3 = −1.2514 + ,
(sin(−1.2514) + 2(−1.2514) + 1)
(0.31399 − 1.5660 + 1.2514)
x3 = −1.2514 + ,
(−0.9494 − 2.5028 + 1)
x3 = −1.2512
Hence the root correct to 3-dp is x = −1.251.
Let us take x0 = 0.5
for n = 0,
(cos x0 − x20 − x0 )
x1 = x0 + ,
(sin x0 + 2x0 + 1)
(cos(0.5) − (0.5)2 − (0.5))
x1 = 0.5 + ,
(sin(0.5) + 2(0.5) + 1)
(0.8776 − 0.25 − 0.5)
x1 = 0.5 + ,
(0.4794 + 1.0 + 1)
x1 = 0.551

for n = 1,
(cos x1 − x21 − x1 )
x2 = x1 + ,
(sin x1 + 2x1 + 1)
(cos(0.551) − (0.551)2 − (0.551))
x2 = 0.551 + ,
(sin(0.551) + 2(0.551) + 1)
(0.8520 − 0.3036 − 0.551)
x2 = 0.551 + ,
(0.5235 + 1.102 + 1)
x2 = 0.550

for n = 2,
(cos x2 − x22 − x2 )
x3 = x2 + ,
(sin x2 + 2x2 + 1)
(cos(0.55) − (0.55)2 − (0.55))
x3 = 0.55 + ,
(sin(0.55) + 2(0.55) + 1)
(0.8525 − 0.3025 − 0.55)
x3 = 0.55 + ,
(0.5227 + 1.1 + 1)
x1 = 0.550

Hence the root correct to 3-dp is x = 0.550.

Example. Find the two roots near x = 2 of the equation x4 − 5x3 − 12x2 + 76x − 79 = 0

Solution 14. Here

f (x) = x4 − 5x3 − 12x2 + 76x − 79,

f ′ (x) = 4x3 − 15x2 − 24x + 76.
1.3. ERROR TERM OF NEWTION RAPHSON METHOD 37

x 0 1 2 3
f (x) −79 −19 1 −13

Since f (x) changes the sign between 1 and 2, root lies between 1 and 2.
Apply Newton-Raphson method.

f (xn )
xn+1 = xn − , where f ′ (xn ) 6= 0, n = 0, 1, 2, ....,
f ′ (xn )
(x4 − 5x3 − 12x2n + 76xn − 79)
xn+1 = xn − n 3 n .
(4xn − 15x2n − 24xn + 76)

To find first root. Take x0 = 1.

for n = 0,
(x40 − 5x30 − 12x20 + 76x0 − 79)
x1 = x0 − ,
(4x30 − 15x20 − 24x0 + 76)
((1)4 − 5(1)3 − 12(1)2 + 76(1) − 79)
x1 = 1 −
(4(1)3 − 15(1)2 − 24(1) + 76)
(1 − 5 − 12 + 76 − 79)
x1 = 1 − ,
(4 − 15 − 24 + 76)
x1 = 1.46341 .

for n = 1, · · · · · · x2 = 1.67775 ,
for n = 2, · · · · · · x3 = 1.77506 ,
for n = 3, · · · · · · x4 = 1.76801 ,
for n = 4, · · · · · · x5 = 1.76839 ,
for n = 5, · · · · · · x6 = 1.76839 .

Hence one root near x = 2 is 1.76839 to 4-dp.

To find the 2nd root.
Since f (x) changes the sign between 2 and 3, therefore root lies between 2 and 3.
So we take x0 = 3.
for n = 0,
(x4 − 5x3 − 12x20 + 76x0 − 79)
x1 = x0 − 0 3 0 ,
(4x0 − 15x20 − 24x0 + 76)
((3)4 − 5(3)3 − 12(3)2 + 76(3) − 79)
x1 = 3 −
(4(3)3 − 15(3)2 − 24(3) + 76)
(81 − 135 − 108 + 228 − 79)
x1 = 3 − ,
(108 − 135 − 72 + 76)
x1 = 2.43478 .
38 CHAPTER 1. THE NUMERICAL SOLUTION OF NON-LINEAR EQUATIONS

for n = 1, · · · · · · x2 = 2.27913 ,
for n = 2, · · · · · · x3 = 2.24337 ,
for n = 3, · · · · · · x4 = 2.24100 ,
for n = 4, · · · · · · x5 = 2.24099 ,
for n = 5, · · · · · · x6 = 2.24099 .
Hence one root near x = 2 is 2.2409 to 4-dp.

Example. Find all the roots (have three roots) of the equation

2x3 − 13x2 − 22x + 3 = 0.

Solution 15. Here

f (x) = 2x3 − 13x2 − 22x + 3,

f ′ (x) = 6x2 − 26x − 22.

x −2 −1 0 1 2 3 4 5 6 7 8
f (x) −21 10 3 −30 −77 −126 −165 −182 −165 −102 19

Apply Newton-Raphson method.

f (xn )
xn+1 = xn − , where f ′ (xn ) 6= 0, n = 0, 1, 2, ....,
f ′ (xn )
(2x3n − 13x2n − 22xn + 3)
xn+1 = xn − .
(6x2n − 26xn − 22)

To find first root.

Since f (x) changes the sign between −2 and −1, therefore root lies between −2
and −1.
Take x0 = −2.

for n = 0,
(2x30 − 13x20 − 22x0 + 3)
x1 = x0 − ,
(6x20 − 26x0 − 22)
(2(−2)3 − 13(−2)2 − 22(−2) + 3)
x1 = −2 − ,
(6(−2)2 − 26(−2) − 22)
(−16 − 54 + 44 + 3)
x1 = −2 − ,
(24 + 52 − 22)
x1 = −1.5741 .
1.3. ERROR TERM OF NEWTION RAPHSON METHOD 39

for n = 1,

(2x31 − 13x21 − 22x1 + 3)

x2 = x1 − ,
(6x21 − 26x1 − 22)
(2(−1.5741)3 − 13(−1.5741)2 − 22(−1.5741) + 3)
x2 = −1.5741 − ,
(6(−1.5741)2 − 26(−1.5741) − 22)
(−7.80058 − 32.21128 + 34.6302 + 3)
x2 = −1.5741 − ,
(14.86674 + 40.9266 − 22)
x2 = −1.5036 .

for n = 2, · · · · · · x3 = −1.50004 ,
for n = 3, · · · · · · x4 = −1.50000 ,
for n = 4, · · · · · · x5 = −1.50000 .

Therefore first root is −1.50.

To find 2nd root.

Since f (x) changes the sign between 0 and 1, therefore take x0 = 0.
for n = 0,
(2x30 − 13x20 − 22x0 + 3)
x1 = x0 − ,
(6x20 − 26x0 − 22)
(2(0)3 − 13(0)2 − 22(0) + 3) 3
x1 = 0 − =− ,
(6(0)2 − 26(0) − 22) −22
x1 = 0.1364 .
for n = 1,
(2x31 − 13x21 − 22x1 + 3)
x2 = x1 − ,
(6x21 − 26x1 − 22)
(2(0.1364)3 − 13(0.1364)2 − 22(0.1364) + 3)
x2 = 0.1364 − ,
(6(0.1364)2 − 26(0.1364) − 22)
x2 = 0.12706 .

for n = 2, · · · · · · x3 = 0.12702 ,
for n = 3, · · · · · · x4 = 0.12702 .

Hence 2nd root is 0.12702.

To find 3rd root.
Since f (x) changes the sign between 7 and 8, therefore take x0 = 7.
for n = 0,
(2x30 − 13x20 − 22x0 + 3)
x1 = x0 − ,
(6x20 − 26x0 − 22)
(2(7)3 − 13(7)2 − 22(7) + 3)
x1 = 7 − ,
(6(7)2 − 26(7) − 22)
x1 = 8.13333 .
40 CHAPTER 1. THE NUMERICAL SOLUTION OF NON-LINEAR EQUATIONS

for n = 1,

(2x31 − 13x21 − 22x1 + 3)

x2 = x1 − ,
(6x21 − 26x1 − 22)
(2(8.13333)3 − 13(8.13333)2 − 22(8.13333) + 3)
x2 = 8.13333 − ,
(6(8.13333)2 − 26(8.13333) − 22)
(1076.0568 − 859.9637 − 178.9333 + 3)
x2 = 8.13333 − ,
(396.9063 − 211.4666 − 22)
x2 = 7.88761 .

for n = 2, · · · · · · x3 = 7.87303 ,
for n = 3, · · · · · · x4 = 7.87298 ,
for n = 4, · · · · · · x5 = 7.87298 .

Hence 3rd root is 7.87298.

Example. By taking logrithms, find the solution of xx = 10 correct to 4-dp by

Newton-Raphson method.

Solution 16. Here

f (x) = xx − 10,
dxx
f ′ (x) = .
dx

• xx = 10, ln y = ln(xx ),
f (x) = xx − 10,, ln y = x ln x,
dxx 1 dy 1
f ′ (x) = . y dx = x x + ln x,
dx
dy
• Let y = xx , = xx (1 + ln x).
dx

f ′ (x) = xx (1 + ln x).

x 1 2 3
f (x) −9 −6 17

Since f (x) changes the sign between 2 and 3, root lies between 2 and 3. Therefore
take x0 = 2.
1.3. ERROR TERM OF NEWTION RAPHSON METHOD 41

Apply Newton-Raphson method.

f (xn )
xn+1 = xn − , where f ′ (xn ) 6= 0, n = 0, 1, 2, ....,
f ′ (xn )
((xn )xn − 10)
xn+1 = xn − .
(xn )xn (1 + ln xn )

for n = 0,
((x0 )x0 − 10)
xn+1 = x0 − ,
(x0 )x0 (1 + ln x0 )
(22 − 10)
=2− 2 ,
2 (1 + ln 2)
x1 = 2.885924 .

for n = 1, · · · · · · x2 = 2.628389 ,
for n = 2, · · · · · · x3 = 2.520914 ,
for n = 3, · · · · · · x4 = 2.506413 ,
for n = 4, · · · · · · x5 = 2.506184 ,
for n = 5, · · · · · · x6 = 2.506184 .

Hence the required root is x = 2.506184 to 4-dp.

Example. Find to 4-dp to two roots of x = log10 x + 2, using Newton-Raphson method.

Solution. Here

f (x) = x − log10 x − 2,
1
f ′ (x) = 1 − .
x ln 10

x 0.01 1 2 3
f (x) 0.01 −1 −0.3 0.5

Apply Newton-Raphson method.

f (xn )
xn+1 = xn − , where f ′ (xn ) 6= 0, n = 0, 1, 2, ....,
f ′ (xn )
(xn − log10 xn − 2)
xn+1 = xn − 1 .
(1 − xn ln 10 )

To find first root.

Since f (x) changes the sign between 0.01 and 1, root lies between 0.01 and 1.
Therefore take x0 = 0.01.
42 CHAPTER 1. THE NUMERICAL SOLUTION OF NON-LINEAR EQUATIONS

for n = 0,
(x0 − log10 x0 − 2)
xn+1 = x0 − 1 ,
(1 − x0 ln 10 )
(0.01 − log10 (0.01) − 2)
= 0.01 − ,
(1 − (0.01)1 ln 10 )
x1 = 0.010236 .

for n = 1, · · · · · · x2 = 0.010239 ,
for n = 2, · · · · · · x3 = 0.010239 ,

Hence the 1st root correct to 4-dp is x = 0.0102.

To find 2nd root.

Since f (x) changes the sign between 2 and 3, root lies between 2 and 3.
Therefore take x0 = 2.

for n = 0,
(x0 − log10 x0 − 2)
x1 = x0 − 1 ,
(1 − x0 ln 10 )
(2 − log10 (2) − 2)
=2− 1 ,
(1 − (2) ln 10 )

x1 = 2.38453 .

for n = 1, · · · · · · x2 = 2.375816 ,
for n = 2, · · · · · · x3 = 2.375812 ,
for n = 2, · · · · · · x4 = 2.375812 .

Hence the 2nd root correct to 4-dp is x = 2.3758.

Exercise 2

1. Find the iterative formula based on the Newton-Raphson method for function
√
x = 3 N , where N is a +ve real number. Apply the method to

(a) N = 35 (d) N = 20
(b) N = 15 (e) N = 3
(c) N = 12 (f) N = 5

2. Find the iterative formula based on the Newton-Raphson method for function
x = N1 , where N is a +ve real number. Apply the formula to N = 18 and take
initial value x0 = 0.
OR
1.3. ERROR TERM OF NEWTION RAPHSON METHOD 43

Show that the iterative formula for the equation x − N1 = 0, is

xn+1 = xn (2 − N xn ), a special case of Newton-Raphson method.

3. Determine the positive real root of the following equation upto 4-dp using
Newton-Raphson method.

(a) ex sin x = 12 x, in the interval (0, π).

Note. If we take x0 = 0 then x1 = 0, x2 = 0, x3 = 0,.... Hence we can not take
x0 = 0, so take x0 = π
(b) 2 sinh x = cosh x, in the interval (0, 1).
Note.Do the above question by taking x0 = 1.

1
4. Use the Newton-Raphson process to find the indicated root of ln x − 1 − x2 =0
upto 4-dp. Taking x0 = 3

5. Use the Newton-Raphson method to evaluate a root of the equation ex − 3x2 = 0

near x = −0.5 upto 6-dp.

6. Find the positive real root of xex = 1, using the Newton-Raphson method use
x = 1 upto 6-dp.

7. Find a positive real root of the equation x3 + 2x2 + 10x − 20 = 0, by

Newton-Raphson method starting value is x = 1 compute upto x3 .

8. Find the positive root of the equation x4 − x − 10 = 0. upto 3-dp

9. Find the positive root of the equation f (x) = 2x − log x − 6. upto 3-dp

10. Find the positive root of 4x4 = x + 8. correct to 4 significant figure.

Ans. x5 = 1.2326 4-dp.

11. Find the diameter D of the pipe which satisfies the flow equation
8820D 5 − 231D − 0.6465 correct to 3-dp.
Ans. x12 = 0.163 3-dp.

12. Find the root of x6 − x − 1 = 0 in (1, 2) by using Newton-Raphson method.

Ans. x5 = 1.1347 4-dp.

13. Evaluate the positive real root of the equation

x4 + 0.5x3 + 0.84x2 − 1.66x − 132 = 0 by Newton-Raphson method
Ans. x4 = 1.10000 = 1.1.

14. Use the Newton-Raphson process to evaluate x4 of f (x) = x1 . Taking x0 = 1

15. Find the positive root of the equation x4 + 10x2 − 6 = 0. upto 4-dp

16. Find the root of f (x) = x2 − 2 in [1, 2] by using Newton-Raphson method.

44 CHAPTER 1. THE NUMERICAL SOLUTION OF NON-LINEAR EQUATIONS

17. Find the real root of f (x) = x2 − 2x − 2 correct to 3-dp, by using Newton’s
Raphson’s Method.

18. Find a +ve real root of f (x) = x2 − 2x − 3 correct to 3-dp, by using Newton’s
Raphson’s Method.

1.3.1 The Secant Method (1st Derivation)

The secant method is a modified form of Newton-Raphson method.

f (xn )
xn+1 = xn − , where f ′ (xn ) 6= 0, n = 0, 1, 2, ..... (1.9)
f ′ (xn )

We replace the derivative f ′ (x) by the difference ratio i.e;

f (xn ) − f (xn−1 )
f ′ (x) ∼
=
xn − xn−1

f (xn )(xn − xn−1 )

xn+1 = xn − ,
f (xn ) − f (xn−1 )
xn f (xn ) − xn f (xn−1 ) − xn f (xn ) + xn−1 f (xn )
= ,
f (nn ) − f (xn−1 )
−xn f (xn−1 ) + xn−1 f (xn )
= ,
f (nn ) − f (xn−1 )
xn−1 f (xn ) − xn f (xn−1 )
xn+1 = . (1.10)
f (nn ) − f (xn−1 )
Where, n = 1, 2, 3, ..., provided that f (xn ) 6= f (xn−1 ). The secant method requires two
starting points x0 and x1 values of f (x0 ) and f (x1 ) are calculated, which gives two
points on the graph of the function. The new point x2 is obtained using eq(2.6).

Remark. 1. The Secant method requires two starting values x0 and x1 but we do not
demand that f (x0 ).f (x1 ) < 0 as with the rule of False Position method.

√
2. The order of the convergence of Secant method is equal to 1+2 5 = 10618 which shows
that this method has the oredr of convergence slightly inferior to that of
Newton-Raphson method.e.g; 2.

3. The Secant method avoids the evaluation of f ′ (x) and is well adapted for computer
usage.

4. Each error is proportional to the product of the previous two errors.

1.4. ERROR TERM OF SECANT METHOD 45

The Secant Method (2nd Derivation)

In this method we choose c at the midpoint where the segment AB (or the secant line
joining A and B) intersect the x − axis.

f (b) − f (a)
Slop = .
b−a

Equation of line
y − y1 x − x1
= ,
y2 − y1 x2 − x1
y − f (a) x−a
= ,
f (b) − f (a) b−a
y − f (a) f (b) − f (a)
= ,
x−a b−a
At point C, y = 0, then

0 − f (a) f (b) − f (a)

= ,
C−a b−a
b−a
C = a − f (a) ,
f (b) − f (a)
af (b) − af (a) − bf (a) + af (a)
C= ,
f (b) − f (a)
af (b) − bf (a)
C= ,
f (b) − f (a)

Now take a = x0 , b = x1 and C = x2 such that f (x1 )f (x2 ) < 0.

x0 f (x1 ) − x1 f (x0 )
x2 = ,
f (x1 ) − f (x0 )
x1 f (x2 ) − x2 f (x1 )
x3 = ,
f (x2 ) − f (x1 )
..
.
xn−1 f (xn ) − xn f (xn−1 )
xn+1 = .
f (xn ) − f (xn−1 )

1.4 Error term of Secant Method

Here we have
xi−1 f (xi ) − xi f (xi−1 )
xi+1 = .
f (xi ) − f (xi−1 )
α be a simple root of f (x) = 0, i.e. f (α) = 0, f (α) 6= 0.

xi−1 f (xi ) − xi f (xi−1 )

xi+1 − α = − α.
f (xi ) − f (xi−1 )
46 CHAPTER 1. THE NUMERICAL SOLUTION OF NON-LINEAR EQUATIONS

xi−1 f (xi ) − xi f (xi−1 ) − αf (xi ) + αf (xi−1 )

xi+1 − α = .
f (xi ) − f (xi−1 )
(xi−1 − α)f (xi ) − (xi − α)f (xi−1 )
xi+1 − α = .
f (xi ) − f (xi−1 )
Define 
ǫ = xi+1 − α,
i+1
f (x ) = f (x − α + α) = f (ǫ + α).
i i i

similarly
f (xi−1 ) = f (xi−1 − α + α) = f (ǫi−1 + α).
ǫi−1 f (α + ǫi ) − ǫf (α + ǫi−1 )
ǫi+1 = .
f (α + ǫi ) − f (α + ǫi−1 )

ǫi−1 [f (α) + ǫi f (α) + 12 ǫ2i f (α) + ....] − ǫi [f (α) + ǫi−1 f (α) + ...]
′ ′′ ′

ǫi+1 = .
[f (α) + ǫi f ′ (α) + 2!1 ǫ2i f ′′ (α) + ...] − [f (α) + ǫi−1 f ′ (α) + 2!
1 2
ǫi−1 f ′′ (α)...]

since f (α) = 0,

ǫi−1 [0 + ǫi f (α) + 12 ǫ2i f (α) + ....] − ǫi [0 + ǫi−1 f (α) + ...]

′ ′′ ′

ǫi+1 = .
[0 + ǫi f ′ (α) + 2!1 ǫ2i f ′′ (α) + ...] − [0 + ǫi−1 f ′ (α) + 2!
1 2
ǫi−1 f ′′ (α)...]

ǫi−1 ǫi f (α) + 21 ǫi−1 ǫ2i f (α) + .... − ǫi ǫi−1 f (α) − ǫi ǫ2i−1 f (α) − ...
′ ′′ ′ ′′

ǫi+1 = 1 2 ′′ .
ǫi f ′ (α) + 2! ǫi f (α) + ... − ǫi−1 f ′ (α) − 2!1 ǫ2i−1 f ′′ (α) − ...

1 2 ′′ − 12 ǫi ǫ2i−1 f (α)
′′
2 ǫi−1 ǫi f (α)
ǫi+1 = .
ǫi f (α) − ǫi−1 f ′ (α)
′

1 ′′
2 ǫi−1 ǫi f (α)(ǫi − ǫi−1 )
ǫi+1 = ′ .
(ǫi − ǫi−1 )f (α)

′′
1 f (α)
ǫi+1 = ǫi−1 ǫi ′ = Kǫi−1 ǫi . (1.11)
2 f (α)
′′
1 f (α)
where, K =
2 f ′ (α)
We have ǫi+1 = Kǫi−1 ǫi . Hence error is proportional to the product of errors
Let us assume
ǫi+1 = Aǫm
i . (1.12)
1.4. ERROR TERM OF SECANT METHOD 47

Where A and m are to be found. Therefore,

ǫi
ǫi = Aǫm m
i−1 , =⇒ ǫi−1 = ,
A
ǫi
ǫi−1 = ( )1/m . (1.13)
A

Substitute in eq(2.7) from eq(2.8) and eq(2.9)

ǫi 1/m K
Aǫm
i = Kǫi ( ) , =⇒ Aǫm
i =
A A1/m
Hence m should be choosen so that

1
m=1+ , =⇒ m2 = m + 1,
m
√
2 1± 1+4
m − m − 1 = 0, =⇒ m =
2
√ √
1± 5 1+ 5
m= , =⇒ m = = 1.6180.
2 2
A should be choosen so that

K
A= , =⇒ A1+1/m = K
A1/m
K = Am

Example. Use the Secant method to find correct to 4-dp the root between 0.4 and 0.6 of
the equation
sin x = 5x − 2

In order to apply Secant method we need two starting values. Let x0 = 0.4 and x1 = 0.6.
Apply Secant method
xn−1 f (xn ) − xn f (xn−1 )
xn+1 = .
f (xn ) − f (xn−1 )
for n = 1,
x0 f (x1 ) − x1 f (x0 )
x2 = .
f (x1 ) − f (x0 )

f (x0 ) = sin x0 − 5x0 + 2,

= sin(0.4) − 5(0.4) + 2,
f (x0 ) = 0.38942.
f (x1 ) = sin x1 − 5x1 + 2,
= sin(0.6) − 5(0.6) + 2,
f (x1 ) = −0.43536,
(0.4)(−0.43536) − (0.6)(0.38942)
x2 = .
(−0.43536) − (0.38942)
48 CHAPTER 1. THE NUMERICAL SOLUTION OF NON-LINEAR EQUATIONS

x2 = 0.4944 .

for n = 2,
x1 f (x2 ) − x2 f (x1 )
x3 = .
f (x2 ) − f (x1 )

f (x2 ) = sin x2 − 5x2 + 2,

= sin(0.4944) − 5(0.4944) + 2,
f (x2 ) = 0.0025.

(0.6)(0.0025) − (0.4944)(−0.43536)
x3 = ,
(0.0025) − (−0.43536)
x3 = 0.4950 .

for n = 3,
x2 f (x3 ) − x3 f (x2 )
x4 = .
f (x3 ) − f (x2 )

f (x3 ) = sin x3 − 5x3 + 2,

= sin(0.4950) − 5(0.4950) + 2,
f (x2 ) = 0.00003.

(0.4944)(0.00003) − (0.4950)(0.0025)
x4 = ,
(0.00003) − (0.0025)
x3 = 0.4950 .
Hence the required root to 4-dp is x = 0.4950.
1.4. ERROR TERM OF SECANT METHOD 49

Exercise 3

1. Using the Secant method to evaluate to 4-dp the root of the equation

(a) ex − 3x = 0 starting values are x0 = 0.4 and x1 = 0.9.

(b) f (x) = ex − 5x2 , starting values are x0 = 0 and x1 = 1.

2. Given the following equations:

(a) x4 − x − 10 = 0,
(b) x − e−x = 0
determine the initial approximations for finding the smallest positive root.
Use these to find the correct to 3-dp with the Secant method.
2
3. The equation f (x) = x + e−Bx cos x,using Secant method. As one choice initial
guesses, use x0 = −1, x1 = 0. B = 1, 5, 10, 25, 50.

4. Find the root of the equation x3 − 8x − 5 using Secant method. The initial
approximations be x0 = 3, and x1 = 3.5.

5. Determine a root of the equation sin x + 3 cos x − 2 = 0 using the Secant method.
The initial approximations are x0 = 0, and x1 = 1.5.

6. Find the root of the equation x3 − 8x − 5 = 0 using Secant method. The initial
approximations be x0 = −2, and x1 = −1.5.

7. Find the root of the equation x6 − x − 1 = 0 using Secant method. The initial
approximations be x0 = 2, and x1 = 1.0.

8. Find the root of the equation x3 − 75 = 0 using Secant method. The initial
approximations be x0 = 4, and x1 = 5.

9. Find the root of the equation tan x − tanh x = 0 using Secant method. The initial
approximations be x0 = 7, and x1 = 7.5.

10. Find the root of the equation cos x cosh x − 1 = 0 using Secant method. The initial
approximations be x0 = 4.5, and x1 = 5.0.

11. Find the root of the equation sin x − 0.1x = 0 using Secant method. The initial
approximations be x0 = 2, and x1 = 3.

12. Find the root of the equation f (x) = e−x − x using Secant method. The initial
approximations be x0 = 0, and x1 = 1.5.
√
13. Find the root of the equation f (x) = sin( x) − x using Secant method. The initial
approximations be x0 = 3, and x1 = 4.
50 CHAPTER 1. THE NUMERICAL SOLUTION OF NON-LINEAR EQUATIONS

14. Use the Secant to find a solution to f (x) = cos x − x with x0 = 0.5 and x1 = π4 .

15. Find the root of the equation f (x) = tan x − x − 1 using Secant method. The initial
approximations be x0 = 0, and x1 = 1.

1.4.1 Regula Falsi Method

Let f (x) = 0 be a non-linear equation. Suppose α is the real root of this equation which
lies in the small interval (xL , xR ).
Since the root lies in the interval (xL , xR ), the curve y = f (x) must cross
x − axis between xL and xR therefore f (xL )f (xR ) < 0, i.e, f (xl ) and f (xR ) have
opposite sign. Join points A and B so that the line AB crosses x − axis at point xi .
Equation of line AB is

y − y1 x − x2
= ,
y2 − y1 x2 − x1
y − f (xL ) x − xL
= .
f (xR ) − f (xL ) xR − xL

At point xi , y = 0, x = xi .

0 − f (xL ) xi − xL
= ,
f (xR ) − f (xL ) xR − xL
xR − xL
(xi − xL ) = −f (xL ) ,
f (xR ) − f (xL )
f (xL )(xR − xL )
xi = xL − .
f (xR ) − f (xL )

Which gives the approximation.

1. αǫ(xL , xi ). If xL < α < xi then

f (xL )f (xi ) < 0

and xi becomes the new xR for the next iteration.

2. αǫ(xi , xR ). If xi < α < xR then

f (xR )f (xi ) < 0

and xi becomes the new xL for the next iteration.

Note. • Regula falsi is a Latin name which means false position. The fact that
replacement of the curve by a straight line gives a false position of the root is the
origin of the
1.4. ERROR TERM OF SECANT METHOD 51

• This method required two initial approximations xL and xR so that f (xL f (xR )) < 0.

• The Secant method converges comparatively faster as compare to Regula False

method. It is a slow method.

•
f (xL )(xR − xL ))
xi = xL −
f (xR ) − f (xL )
xL f (xR ) − xL f (xL ) − xR f (xL ) + xL f (xL )
xi =
f (xR ) − f (xL )
xL f (xR ) − xR f (xL )
xi =
f (xR ) − f (xL )
Example. Solve f (x) = e−x − sin( πx
2 ), using the method of false position to find a
positive real root.
Here
πx
f (x) = e−x − sin( ).
2

x 0 1
f (x) 1 −0.632121

Since f (x) changes the sign between 0 and 1. Therefore xL = 0 and xR = 1.

πxL π(0)
f (xL ) = e−xL − sin( ), ⇒ f (0) = e0 − sin( ) = 1,
2 2
πxR π1
f (xR ) = e−xR − sin( ), ⇒ f (0) = e1 − sin( ) = −0.632121.
2 2
since f (xL )f (xR ) < 0
Applying Regula Falsi method
xL f (xR ) − xR f (xL )
xi =
f (xR ) − f (xL )
(0)(−0.632121) − 1(1)
for i=1, x1 = = 0.612700
−0.632121 − 1
x1 = 0.612700
f (x1 ) = f (0.612700) = e−0.6127 − sin((0.6127π)/2) = −0.278695
since f (xL )f (x1 ) < 0,
xR (= x1 ) = 0.612700 ⇒ f (xR )(= f (x1 )) = 0.278695
xL f (xR ) − xR f (xL )
xi =
f (xR ) − f (xL )
(0)(−0.278695) − (0.6127)(1)
for i=2, x2 = = 0.479160
−0.278695 − 1
x2 = 0.479160
f (x2 ) = f (0.479160) = e−0.479160 − sin((0.479160π)/2) = −0.064281
52 CHAPTER 1. THE NUMERICAL SOLUTION OF NON-LINEAR EQUATIONS

since f (xL )f (x2 ) < 0,

xR (= x2 ) = 0.479160 ⇒ f (xR )(= f (x2 )) = −0.064281
xL f (xR ) − xR f (xL )
for i=3, xi =
f (xR ) − f (xL )
(0)f (xR ) − (0.479160)(1)
x3 = = 0.450219
−0.0648281 − 1
x3 = 0.450219
f (x3 ) = f (0.450219) = e−0.450219 − sin((0.450219π)/2) = −0.012221
since f (xL )f (x3 ) < 0,
xR (= x3 ) = 0.450219 ⇒ f (xR )(= f (x3 )) = −0.012221
xL f (xR ) − xR f (xL )
for i=4, xi =
f (xR ) − f (xL )
(0)f (xR ) − (0.450219)(1)
x4 = = 0.450219
−0.012221 − 1
x4 = 0.444183
f (x4 ) = f (0.444183) = e−0.444183 − sin((0.444183π)/2) = −0.002232
since f (xL )f (x4 ) < 0,
xR (= x4 ) = 0.444183 ⇒ f (xR )(= f (x4 )) = −0.002232
xL f (xR ) − xR f (xL )
for i=5, xi =
f (xR ) − f (xL )
(0)f (xR ) − (0.444783)(1)
x5 = = 0.445192
−0.002232 − 1
x5 = 0.443792
f (x5 ) = f (0.443792) = e−0.443792 − sin((0.443792π)/2) = −0.003201
since f (xL )f (x4 ) < 0,
xR (= x4 ) = 0.444183 ⇒ f (xR )(= f (x4 )) = −0.002232
xL f (xR ) − xR f (xL )
for i=5, xi =
f (xR ) − f (xL )
(0)f (xR ) − (0.444783)(1)
x5 = = 0.445192
−0.002232 − 1
continue till x7 .
1.4. ERROR TERM OF SECANT METHOD 53

Example. Solve f (x) = x3 + x2 − 3x − 3 using method of false position to a positive real

root.
Here
f (x) = x3 + x2 − 3x − 3.

x 0 1 2
f (x) −3 −4 3

Since f (x) changes the sign between 1 and 2. Therefore xL = 1 and xR = 2.

f (x = xL ) = x3L + x2L − 3xL − 3, ⇒ f (1) = 13 + 12 − 3(1) − 3 = −4,

f (x = xR ) = x3R + x2R − 3xR − 3, ⇒ f (2) = (2)3 + (2)2 − 3(2) − 3 = 3
since f (xL )f (xR ) < 0
Applying Regula Falsi method
xL f (xR ) − xR f (xL )
xi =
f (xR ) − f (xL )
(1)(3) − 2(−4)
for i=1, x1 = = 1.571429
3 − (−4)
x1 = 1.571429
f (xL = x1 ) = f (1.571429) = (1.571429)3 + (1.571429)2 − 3(1.571429) − 3
f (x1 ) = −1.364428
since f (xR )f (x1 ) < 0,
∴ xL (= x1 ) = 1.571429 ⇒ f (xL )(= f (x1 )) = −1.364428
xL f (xR ) − xR f (xL )
xi =
f (xR ) − f (xL )
(1.571429)(3) − 2(−1.364428)
for i=2, x2 = = 1.705411
3 − (−1.364428)
x2 = 1.705411
f (xL = x2 ) = f (1.705411) = (1.705411)3 + (1.705411)2 − 3(1.705411) − 3
f (x2 ) = −0.247743
since f (xR )f (x2 ) < 0,
∴ xL (= x2 ) = 1.705411 ⇒ f (xL )(= f (x2 )) = −0.247743
xL f (xR ) − xR f (xL )
xi =
f (xR ) − f (xL )
(1.705411)(3) − 2(−0.247743)
for i=3, x3 = = 1.727883
3 − (−0.247743)
x3 = 1.727883
f (xL = x3 ) = f (1.727883) = (1.727883)3 + (1.727883)2 − 3(1.727883) − 3 = −0.030418
54 CHAPTER 1. THE NUMERICAL SOLUTION OF NON-LINEAR EQUATIONS

since f (xR )f (x3 ) < 0.

∴ xL (= x3 ) = 1.727883 ⇒ f (xL )(= x3 ) = −0.030418
xL f (xR ) − xR f (xL )
xi =
f (xR ) − f (xL )
(1.727883)(3) − 2(−0.030418)
for i=4, x3 = = 1.730614
3 − (−0.030418)
x4 = 1.730614
f (xL = x4 ) = f (1.730614) = (1.730614)3 + (1.730614)2 − 3(1.730614) − 3 = −0.013585
since f (xR )f (x4 ) < 0.
∴ xL (= x4 ) = 1.730614 ⇒ f (xL )(= x4 ) = −0.013585
xL f (xR ) − xR f (xL )
xi =
f (xR ) − f (xL )
(1.730614)(3) − 2(−0.013585)
for i=5, x3 = = 1.731828
3 − (−0.013585)
x5 = 1.731828
f (xL = x5 ) = f (1.731828) = (1.731828)3 + (1.731828)2 − 3(1.731828) − 3 = −0.002108
since f (xR )f (x5 ) < 0.
∴ xL (= x5 ) = 1.731828 ⇒ f (xL )(= x5 ) = −0.002108
xL f (xR ) − xR f (xL )
xi =
f (xR ) − f (xL )
(1.731828)(3) − 2(−0.002108)
for i=6, x3 = = 1.732016
3 − (−0.002108)
x5 = 1.732016
Hence the required root correct to 3dp is x = 1.732.
Chapter 2

Solution Non-Linear Function

[Fazle Haq]

2.1 Direct Method

A method which calculate the required solution without any initial or intermediate
approximations in a finite number of stages.

2.2 Iterative Method or Indirect Method of Solution

An indirect method starts with an initial approximation and proceeds by calculating a

sequence of further approximations which eventually gives the solution as accurately as
desired.

2.3 Termination of an Iterative Procedure

An iterative procedure may converges or diverges. If the divergence occurs the

procedure should be terminated because there may not be any solution. We may start
the procedure by changing the initial approximation if necessary. In case of convergence,
one of the following criteria for stopping computations may be used.

• Continue the computation for a fixed number of iterations say n and then
terminate the process. The final value of xn may then be accepted as the value of
the root.

55
56 CHAPTER 2. SOLUTION NON-LINEAR FUNCTION

• Continue the computations till absolute difference between two successive values
xn and xn−1 is less than a pre-assigned accuracy say E (tolerance) say

|xn − xn−1 | < ǫ, where ǫ > 0

• A better criteria for stopping the process is to use the following result.

xn − xn−1
< ǫ, provided that xn 6= 0and ǫ > 0.
xn

In considering whether an iterate converges or not, it may be necessary to ignore the

first few iterations since the procedure may appears to diverge initially, even though it
ultimately converges.

1. Linear equation: The equation ax + b = 0 is called linear equation.

2. Non-linear Equation: There are two types of non-linear equations.

(a) Algebraic Equations:

an xn + an−1 xn−1 + an−2 xn−2 + ... + a0 = 0

If n ≥ 5 the solution can not be obtained easily by direct method

(b) Transcendental Equations: A transcendental equation is that which involves
trigonometric, hyperbolic, exponential and logarithmic function etc. e.g.

tan x − x + 1 = 0, log x + ex − 1 = 0

ex = cos x + x2 .

2.4 Solution of Non-linear Equation

There are two types of methods for solution of non-linear equations.

• Direct or Graphical method

• Numerical (iterative) methods

There are many non-linear equations which can not be solved easily by analytically. For
example
x3 − x − 10 = 0
2.5. NUMERICAL METHODS OF SOLVING NON-LINEAR EQUATIONS 57

,
e2x + 2x + 9

and hence there is a need for numerical methods to find their roots.
An algebraic equation of degree n has n (real and / or complex) roots. For
equations of degree 4 or less the roots maybe obtained by analytical methods. A
transcendental equation may has no root, a finite or an infinite number of (real and / or
complex) roots.

2.5 Numerical methods of solving Non-Linear equations

We will consider the following methods for finding the real roots of algebraic and
transcendental equations.

2.6 Newton-Raphson Method

If xn is an approximation to an exact real root α of the equation f (x) = 0 than a better

approximation is given by

f (xn )
xn+1 = xn − , where f / (xn ) 6= 0, n = 0, 1, 2, . . .
f / (xn )

Suppose α is the exact root of the nonlinear equation

f (x) = 0 (2.1)

Let x0 be the initial approximation to α and suppose the 2nd approximation is

x1 = x0 + h, (2.2)

where h is very very small number.

58 CHAPTER 2. SOLUTION NON-LINEAR FUNCTION

Since x1 is an approximate root of eq(6.1), it will satisfy eq(6.1)

f (x1 ) = 0,
f (x0 + h) = 0,
Apply Taylor’s theorem
h2 //
f (a + h) = f (a) + hf / (a) + f (a) + ...,
2!
h2
f (x0 + h) = f (x0 ) + hf / (x0 ) + f // (x0 ) + ...,
2!
h2 //
f (x0 ) + hf / (x0 ) +
f (x0 ) + ..., = 0,
2!
since h2 and higher power of h are negligible.
f (x0 ) + hf / (x0 ) = 0,
hf / (x0 ) = −f (x0 ),
f (x0 )
h = − / , if f / (x0 ) 6= 0
f (x0 )
eq(6.2) becomes,
f (x0 )
x1 = x0 − / , provided f / (x0 ) 6= 0
f (x0 )

Similarly if x2 = x1 + h is the next approximation, we have

f (x1 )
x2 = x1 − , provided f / (x1 ) 6= 0
f / (x1 )

Hence if x0 , x1 , x2 , x3 , ... is a sequence of approximations to the exact root α of eq(6.1),

we get
f (xn )
xn+1 = xn − / ,
f (xn )
provided f / (xn ) 6= 0, n = 0, 1, 2, . .

Remark. • The Newton-Raphson method is one the most powerful and well known
method used for finding a root of f (x) = 0.

• In N-R formula initial approximation x0 is called approximate zero of f (x).

• The term
f (xn )
f / (xn
in N-R method is called correction term.

• In N-R method each error is proportional to the square of the previous

error(quadratically convergent method or 2nd order method). This means that the
number of accurate figure is approximately doubled with each iteration. For example,
if we start with one correct digit for an approximation, then after one iteration we
2.6. NEWTON-RAPHSON METHOD 59

should have two correct digits, after three iterations, eight correct digits etc. Thus we
need only 4 or five iterates if the method is convergent.

• N-R method is self correcting for minor errors.

• N-R method does not always yield or convergent sequence. The method fails if f / (x) is
zero for any xn in the sequence. This problem can be overcome by choosing a different
value of x0 . Generally x0 must be chosen very close to the root for convergence to the
result.

• The evaluation of the derivatives f / (x) at each step makes the method unpopular
computationally. It is sometimes very laborious to calculate f / (x). This is a major
difficulty in this method.

• If |f / (x)| is very small compared to |f (x)|, there could be slow convergence or even
divergence.

• If the root is very near to the maximum or minimum values of the function at that
point, N-R method fails.

• If two or more roots are nearly equal then the method is not fastly convergent.
Despite some of the difficulties metioned alone, N-R method is the most popular
method for finding a root of the non-linear equation. The attraction of this method is
that it converges very rapidly.
Example. Using N-R method to calculate the square root of 3 upto 6dp.
√
Let, x = 3,
squaring both sides,
x2 = 3,
x2 − 3 = 0,
Here f (x) = x2 − x,
f / (x) = 2x,

Since f (x) changes the sign between 1 and 2, root lies between 1 and 2.

x 0 1 2
f (x) −3 −2 1

Apply Newton-Raphson method.

f (xn )
xn+1 = xn − , where f ′ (xn ) 6= 0, n = 0, 1, 2, ....,
f ′ (xn )
(x2 − 3)
xn+1 = xn − n .
2xn )
60 CHAPTER 2. SOLUTION NON-LINEAR FUNCTION

for n = 0,
(x20 − 3)
x1 = x0 + ,
2x0
(12 − 3)
x1 = 1 − ,
2(1)
x1 = 2.000000.

for n = 1,
(x21 − 3)
x2 = x1 − ,
2x1
(22 − 3)
x2 = 2 − ,
2(2)
x2 = 1.750000

for n = 2,
(x22 − 3)
x3 = x2 − ,
2x2
((1.75)2 − 3)
x3 = 1.75 − ,
2(1.75)
x3 = 1.7321429

for n = 3,
(x23 − 3)
x4 = x3 − ,
2x3
((1.7321429)2 − 3)
x4 = 1.7321429 − ,
2(1.7321429)
x4 = 1.7320508

for n = 4,
(x24 − 3)
x5 = x4 − ,
2x4
((1.7320508)2 − 3)
x5 = 1.7320508 − ,
2(1.7320508)
x5 = 1.7320508

Hence the square root of 3 upto 6dp is x = x = 1.7320508

2.7 Order of Convergence

Suppose xn is nth approximation to an exact root α of the equation f (x) = 0. If ǫn is the

error in the nth approximation then

ǫ n = xn − α
2.8. SIMPLE OR FIRST ORDER ITERATION 61

ǫn+1 = xn+1 − α

2.8 Simple or First order Iteration

if

ǫn+1 = kǫn ,
ǫn ∝ ǫn .

i.e. each error is proportional to the previous error then the method is called linearly
convergent method or 1st order iteration or linearly convergent process.

2.9 Second order iteration

if

ǫn+1 = kǫ2n ,
ǫn ∝ ǫ2n .

i.e. each error is proportional to the square of previous error, then the method is called
quadratically convergent method or second order process.

Definition. Let x0 , x1 , x2 , ...xp be a sequence of approximations which converges to the

exact root α of f (x) = 0.
ǫn+1 = kǫ2n
If lim = k,
x→∞ ǫpn
then p is called the order of convergence of the sequence and k is called the asymptotic
error constant.

Theorem. Prove that Newton-Raphson method is quadratically convergent or is a second

order method.

Proof. Suppose xn is nth approximation to an exact root α of the equation

f (x) = 0. (2.3)
62 CHAPTER 2. SOLUTION NON-LINEAR FUNCTION

If ǫn is the error in the nth approximation then

ǫn = approximate value − True value,

ǫn = xn − α,
xn = α + ǫ n ,
xn+1 = α + ǫn+1 ,
Apply Newton-Raphson method
f (xn )
xn+1 = xn − ,
f ′ (xn )
f (α + xn − α)
xn+1 − α = xn − α − ′ .
f (α + xn − α)

f (α + ǫn )
ǫn+1 = ǫn − ,
f ′ (α + ǫn )
Apply Taylor’s theorem,
′ ′′
f (α) + ǫn f (α) + (1/2)ǫ2n f (α) + ....
ǫn+1 = ǫn − ′ ,
f (α) + ǫn f ′′ (α) + (1/2)ǫ2n f ′′′ (α) + ....

Since α is a root of eq(6.3), therefore f (α) = 0,

′ ′′
0 + ǫn f (α) + (1/2)ǫ2n f (α) + ....
ǫn+1 = ǫn − ′ ,
f (α) + ǫn f ′′ (α) + (1/2)ǫ2n f n′′′ (α) + ....

neglecting O(ǫn ), because ǫn is small,

′ ′′
ǫn f (α) + (1/2)ǫ2n f (α)
ǫn+1 = ǫn − ,
f ′ (α) + ǫn f ′′ (α)
′′
ǫn f (α)[1 + (1/2)ǫn ff ′ (α)
(α)
′
]
ǫn+1 = ǫn − ′′ ,
f (α)[1 + ǫn ff ′ (α)
(α)
′
]
′′
ǫn [1 + (1/2)ǫn ff ′ (α)
(α)
]
ǫn+1 = ǫn − ′′ ,
[1 + ǫn ff ′ (α)
(α)
]
′′ ′′
f (α) f (α) −1
ǫn+1 = ǫn − ǫn [1 + (1/2)ǫn ][1 + ǫn ′ ] ,
f ′ (α) f (α)
′′ ′′
f (α) f (α)
ǫn+1 = ǫn − ǫn [1 + (1/2)ǫn ′ ][1 − ǫn ′ ],
f (α) f (α)
′′ ′′ ′′
f (α) f (α) ǫ2n (f (α))
ǫn+1 = ǫn − ǫn [1 + (1/2)ǫn − ǫn ′ − ],
′
f (α) f (α) 2 (f ′ (α))2
′′
f (α)
ǫn+1 = ǫn − ǫn [1 − (1/2)ǫn ′ ],
f (α)
2.10. SIMPLE ITERATIVE PROCEDURE OR FIXED POINT METHOD 63

′′
f (α)
ǫn+1 = ǫn − ǫn + (1/2)ǫ2n ],
f ′ (α)
′′
1 f (α)
ǫn+1 = ǫ2n ′ ,
2 f (α)
′′
f (α)
Since 2f ′ (α)
, is a constant quantity,
therefore, we put
′′
1 f (α)
K=
2 f ′ (α)
,
ǫn+1 = Kǫ2n ,
ǫn+1 ∝ ǫ2n ,
Each error is proportional to the square of the previous error. Therefore, for this reason
we say that Newton’s method is quadratically convergent method i.e it is 2nd order
method

2.10 Simple Iterative Procedure or Fixed Point Method

Suppose that the equation f (x) = 0 is arranged in the form

x = φ(x)

Finding the value of x for which x = φ(x) is thus equivalent to finding a solution of the
equation f (x) = 0. To find a root of f (x) = 0, we use an iterative method of the form

xn+1 = φ(xn ), n = 0, 1, 2, ...

where x0 is the initial approximation. This method is called simple iterative procedure or
simple iteration (also called Fixed point method).

2.11 Convergence of Simple Iterative Procedure

Let I be an interval containing the exact root α of equation f (x) = 0 or x = φ(x), if

′
|φ (x)| < 1 for all x in I, the sequence of iterates x0 , x1 , x2 , ..., xn converges to the root α,
′
provided that the initial approximation is chosen in I. In practice we check φ (x0 ), if
′
|φ (x0 )| < 1 then the sequence x0 , x1 , x2 , ., ., . will tend to be α
64 CHAPTER 2. SOLUTION NON-LINEAR FUNCTION

Example. Solve the equation by simple iterative method

x + log x = 0

when the root lies between 0.5 and 0.6.

we first find whether or not the iterative method is applicable.

f (x) = x − ln x,
x = − ln x,
x = φ(x),
on comparing,
φ(x) = − ln x,
′ 1
φ (x) = − ,
x
′ 1 1
|φ (x)| = | − | = > 1, if x ∈ (0.5, 0.6).
x x

Therefore, for this arrangement the iterative method is not applicable.

Consider again

x + ln x = 0,
−x = ln x,
e−x = x,
x = e−x ,
on comparing,
φ(x) = e−x ,
′
φ (x) = −e−x ,
′ 1
|φ (x)| = | − e−x | = x < 1, if x ∈ (0.5, 0.6).
e

Therefore, for this arrangement the iterative method is applicable. Take x0 = 0.5.

Applying Simple Iterative procedure

xn+1 = φ(xn ),
xn+1 = e−xn , n = 0, 1, 2, ...
2.11. CONVERGENCE OF SIMPLE ITERATIVE PROCEDURE 65

for n = 0,
x1 = e−x0 = e−0.5000 = 0.6065,
⇒ x1 = 0.6065 ,

for n = 1,
x2 = e−x1 = e−0.6065 = 0.5452,
⇒ x2 = 0.5452

for n = 2,
x3 = e−x2 = e−0.5452 = 0.5797,
⇒ x3 = 0.5797

for n = 3,
x4 = e−x3 = e−0.5797 = 0.5601,
⇒ x4 = 0.5601

for n = 4,
x5 = e−x4 = e−0.5601 = 0.5712,
⇒ x5 = 0.5712

for n = 5,
x6 = e−x5 = e−0.5712 = 0.5649,
⇒ x6 = 0.5649

for n = 6,
x7 = e−x6 = e−0.5649 = 0.5684,
⇒ x7 = 0.5684

for n = 7,
x8 = e−x7 = e−0.5684 = 0.5664,
⇒ x8 = 0.5664

for n = 8,
x9 = e−x8 = e−0.5664 = 0.5676,
⇒ x9 = 0.5676

for n = 9,
x10 = e−x9 = e−0.5676 = 0.5669,
⇒ x10 = 0.5669

for n = 10,
x11 = e−x10 = e−0.5669 = 0.5673,
⇒ x11 = 0.5673

for n = 11,
x12 = e−x11 = e−0.5673 = 0.5671,
⇒ x12 = 0.5671
66 CHAPTER 2. SOLUTION NON-LINEAR FUNCTION

for n = 12,
x13 = e−x12 = e−0.5671 = 0.5672,
⇒ x13 = 0.5672

for n = 13,
x14 = e−x13 = e−0.5672 = 0.5671,
⇒ x14 = 0.5671

Hence the required root to 3-dp is x = 0.567

Example. Find the root of x3 − 4x2 + x − 10 = 0 correct to 4-dp by Simple iteration

method.

Here x3 − 4x2 + x − 10 = 0 =⇒ f (x) = x3 − 4x2 + x − 10

x 0 1 2 3 4 5
f (x) −10 −12 −16 −16 −6 20

Since f (x) changes the sign between 4 and 5, root lies between 4 and 5. ∴ take
x0 = 4. We first find whether or not the iterative method is applicable.

x3 − 4x2 + x − 10 = 0,
x = 10 + 4x2 − x3 , since x = φ(x),
on comparing the above we have
′
φ(x) = 10 + 4x2 − x3 , ⇒ φ (x) = 8x − 3x2 ,
′ ′
|φ (x)| = |8x − 3x2 |, ⇒ |φ (4)| = |8(4) − 3(4)2 | = 16 > 1,
Therefore, for this arrangement of f(x)=0, the iterative method is not applicable.

Consider again
x3 − 4x2 + x − 10 = 0,
4x2 = x3 + x − 10,
1p 3
x= x + x − 10, since x = φ(x),
2
on comparing the above we have
1p 3
φ(x) = x + x − 10,
2
′ (3x2 + 1) ′ (3x2 + 1)
φ (x) = √ , ⇒ |φ (x)| = | √ |,
2.2 x3 + x − 10 4 x3 + x − 10
′ (3(4)2 + 1) 49
|φ (4)| = | p |= > 1,
4 (4)3 + 4 − 10 30.4631
2.11. CONVERGENCE OF SIMPLE ITERATIVE PROCEDURE 67

Therefore, for this arrangement of f (x) = 0, the iterative method is not applicable.

Consider again, x3 − 4x2 + x − 10 = 0,

x3 = 4x2 − x + 10,
x.x2 = 4x2 − x + 10,
4x2 − x + 10
x= ,
x2
x = φ(x),
on comparing the above we have
4x2 x 10
φ(x) = 2
− 2 + 2,
x x x
1 10
φ(x) = 4 − + 2 ,
x x
′ 1 20
φ (x) = 2 − 3 ,
x x
′ 1 20
|φ (x)| = | 2 − 3 |,
x x
′ 1 20 1 20
|φ (4)| = | 2 − 3 | = | − |
4 4 16 64
′
|φ (4)| = | − 0.25| = 0.25 < 1.
Therefore, for this arrangement of f(x)=0, the iterative method is applicable.

Applying Simple Iteration method

xn+1 = φ(x), for n = 0, 1, 2, ...

4x2n − xn + 10
xn+1 = ,
x2n
4x20 − x0 + 10 4(4)2 − 4 + 10
for n=0, x1 = , ⇒ x 1 = = 4.3750,
x20 42
4x21 − x1 + 10 4(4.3750) 2 − 4.3750 + 10
for n=1, x2 = , ⇒ x 2 = = 4.2939,
x21 (4.3750)2
4x22 − x2 + 10 4(4.2939) 2 − 4.2939 + 10
for n=2, x3 = , ⇒ x 3 = = 4.3095,
x22 (4.2939)2
4x23 − x3 + 10 4(4.3095) 2 − 4.3095 + 10
for n=3, x4 = , ⇒ x 4 = = 4.3064,
x23 (4.3095)2
4x24 − x4 + 10 4(4.3064) 2 − 4.3064 + 10
for n=4, x5 = , ⇒ x 5 = = 4.3070,
x24 (4.3064)2
4x25 − x5 + 10 4(4.3070) 2 − 4.3070 + 10
for n=5, x6 = , ⇒ x 6 = = 4.3069,
x25 (4.3070)2
4x26 − x6 + 10 4(4.3069) 2 − 4.3069 + 10
for n=6, x7 = , ⇒ x 7 = = 4.3069,
x26 (4.3069)2
Hence the required root correct to 3-dp is x = 4.307 .
68 CHAPTER 2. SOLUTION NON-LINEAR FUNCTION

Example. Find the root of x3 − 5x2 − 29 = 0 correct to 3dp by Simple Iteration method.

Here x3 − 5x2 − 29 = 0 =⇒ f (x) = x3 − 5x2 − 29.

x 0 1 2 3 4 5 6
f (x) −29 −33 −41 −47 −45 −29 7

Since the sign of f (x) changes between 5 and 6, ∴ take x0 = 5. We first find
whether or not the iterative method is applicable.

x3 − 5x2 − 29 = 0, =⇒ x3 = 5x2 + 29
5x2 + 29
x.x2 = 5x2 + 29, =⇒ x =
x2
5x2 29 29
x = 2 + 2 , =⇒ x = 5 + 2
x x x
since x = φ(x)
29 ′ 29 × 2
φ(x) = 5 + 2 , =⇒ φ (x) = −
x x3
′ 58
|φ (5)| = | − |<1
125
Therefore, the iteration method will converge.

Applying Simple Iteration method

xn+1 = φ(x), for n = 0, 1, 2, ...

5x2n + 29
xn+1 = ,
x2n
5x20 + 29 5(5)2 + 29
for n=0, x1 = , ⇒ x 1 = = 6.16,
x20 52
5x21 + 29 5(6.16)2 + 29
for n=1, x2 = , ⇒ x 2 = = 5.7643,
x21 (6.16)2
5x22 + 29 5(5.7643) 2 + 29
for n=2, x3 = , ⇒ x 3 = = 5.8728,
x22 (5.7643) 2
5x23 + 29 5(5.8728) 2 + 29
for n=3, x4 = , ⇒ x 4 = = 5.8408,
x23 (5.8728) 2
5x24 + 29 5(5.8408) 2 + 29
for n=4, x5 = , ⇒ x 5 = = 5.8501,
x24 (5.8408) 2
5x25 + 29 5(5.8501) 2 + 29
for n=5, x6 = , ⇒ x 6 = = 5.8474,
x25 (5.8501) 2
5x26 + 29 5(5.8474) 2 + 29
for n=6, x7 = , ⇒ x 7 = = 5.8482,
x26 (5.8474) 2
2.11. CONVERGENCE OF SIMPLE ITERATIVE PROCEDURE 69

5x27 + 29 5(5.8482) 2 + 29
for n=7, x8 = , ⇒ x7 = = 5.8479,
x27 (5.8482) 2
5x28 + 29 5(5.8479) 2 + 29
for n=8, x9 = , ⇒ x 7 = = 5.8480,
x28 (5.8479) 2
5x29 + 29 5(5.8480) 2 + 29
for n=9, x10 = , ⇒ x 7 = = 5.8480,
x29 (5.8480) 2
Hence the required root correct to 3-dp is x = 5.848 .

Remark. • xn+1 = φ(xn ) x0 is initial approximation n = 0, 1, 2, ....

• xn = φ(xn−1 ) x0 is initial approximation n = 1, 2, ....

Example. Find the root of x + log x = 0 correct to 3dp by Simple Iteration method.

Here
x + log x = 0, =⇒ x = − log x

xn = − log(xn−1 ) = φ(xn−1 ).

Take x0 = 0.55.

φ(x) = − log(x),
′ 1
φ (x) = −
x
′ 1
|φ (0.55)| = | − | = 1.8182 > 1
0.55
Therefore, the iteration method will diverge.
xn = e−xn−1 = φ(xn−1 )
φ(x) = e−x
′
φ (x) = −e−x
′ 1
|φ (0.55)| = | − 0.55 | = 0.5769 < 1
e
Therefore, the iteration method will converge.
(xn−1 + e−xn−1 )
xn = = φ(xn−1 )
2
(x + e−x )
φ(x) =
2
′ (1 − e−x )
φ (x) =
2
′ (1 − e−0.55 )
|φ (0.55)| = | |
2
1 1
= [1 − 0.55 ] = 0.21151 < 1,
2 e
Therefore, the iteration method will converge.
70 CHAPTER 2. SOLUTION NON-LINEAR FUNCTION

Example. The cubic polynomial equation x3 − 3x + 2 has roots x = 1 (a double) and

x = −2. Starting with x0 = 0.9, find x1 , x2 , etc using iteration

(xn − 1)(xn + 2)
xn = xn −
3(xn + 1)

(xn−1 − 1)(xn−1 + 2)
xn = xn−1 −
3(xn−1 + 1)

(x0 − 1)(x0 + 2) (0.9 − 1)(0.9 + 2)

for n=1, x1 = x0 − , ⇒ x1 = 0.9 − = 0.9509,
3(x0 + 1) 3(0.9 + 1)
(x1 − 1)(x1 + 2) (0.9509 − 1)(0.9509 + 2)
for n=2, x1 = x1 − , ⇒ x2 = 0.9509 − = 0.9756,
3(x1 + 1) 3(0.9509 + 1)

for n = 3, · · · · · · x3 = 0.9879 ,
for n = 4, · · · · · · x4 = 0.9939 ,
for n = 5, · · · · · · x5 = 0.9970 ,
for n = 6, · · · · · · x6 = 0.9985 ,
for n = 7, · · · · · · x7 = 0.9985 ,
for n = 8, · · · · · · x8 = 0.9985 ,
for n = 9, · · · · · · x9 = 0.9985 ,
for n = 10, · · · · · · x10 = 0.9985 ,

Hence the required root is x = 0.9985 = 1.

Example. Find by simple iteration to 5dp the root near x = 0.5 of the equation
sin x = 5x − 2. We first find whether or not the iterative method is applicable.

sin x = 5x − 2 =⇒ x = sin−1 (5x − 2)

′ 5
φ(x) = sin−1 (5x − 2), =⇒ φ (x) = p
1 − (5x − 2)2
′ 5
|φ (x)| = | p | = 5.8 > 1
1 − (5(0.5) − 2)2
Therefore, the iteration method will diverge.
Consider again sin(x) = 5x − 2
sin(x) + 2
x=
5
sin(x) + 2 ′ cos(x)
φ(x) = =⇒ φ (x) =
5 5
′ cos(0.5)
|φ (0.5)| = | | = 0.18 < 1.
5
2.12. ERROR ANALYSIS OF SIMPLE ITERATIVE METHOD 71

Therefore, the simple iteration method is applicable.

Applying simple iterative procedure.

xn+1 = φ(xn ), n = 0, 1, 2, 3, ...

sin(xn ) + 2
xn+1 =
5
sin(x0 ) + 2 sin(0.500000) + 2
for n=0, x1 = = = 0.495885,
5 5
sin(x1 ) + 2 sin(0.495885) + 2
for n=1, x2 = = = 0.495162
5 5
sin(x2 ) + 2 sin(0.495162) + 2
for n=2, x3 = = = 0.495035
5 5
sin(x3 ) + 2 sin(0.495035) + 2
for n=3, x4 = = = 0.495012
5 5
sin(x4 ) + 2 sin(0.495012) + 2
for n=4, x5 = = = 0.495009
5 5
sin(x5 ) + 2 sin(0.495009) + 2
for n=5, x6 = = = 0.495008
5 5
sin(x6 ) + 2 sin(0.495008) + 2
for n=6, x7 = = = 0.495008
5 5
Hence the root near 0.5 is x = 0.49501 .

2.12 Error Analysis of Simple Iterative Method

Let xn be an approximation to the real root α of the equation

f (x) = 0 (2.4)

If ǫn is error then
ǫn = xn − α, =⇒ xn = ǫn + α

We rearrange eq(6.4) in the form

x = φ(x)

By simple iterative method

xn+1 = φ(xn ), n = 0, 1, 2, ...

ǫn+1 + α = φ(α + ǫn ),
Applying Taylor’s theorem
′ 1 ′′ 1 ′′′
ǫn+1 + α = φ(α) + ǫn φ (α) + ǫ2n φ (α) + ǫ3n φ (α) + ...
2! 3!
since α is a root of the equation x = φ(x), therefore, α = φ(α)weget,
′ 1 ′′ 1 ′′′
ǫn+1 + α = α + ǫn φ (α) + ǫ2n φ (α) + ǫ3n φ (α) + ....
2 6
72 CHAPTER 2. SOLUTION NON-LINEAR FUNCTION

′ 1 ′′ 1 ′′′
ǫn+1 = ǫn φ (α) + ǫ2n φ (α) + ǫ3n φ (α) + ....
2 6
′
If φ (α) 6= 0, neglecting squares and higher powers of ǫn , ∵ ǫn is very small.
′
ǫn+1 = ǫn φ (α), (Ist order iteration)
′
Now if |φ (α)| < 1
′
Then ǫn+1 = ǫn φ (α) < ǫn i.e ǫn+1 < ǫn i.e. every error is less than the previous error.
Then the sequence x0 , x1 , x3 , ..., will converge to α.

Since we don’t , in general know that what the value of α is, we usually replace α in
′
|φ (α)| < 1 by x0 . Hence the practical criterion for simple iteration to get a root is

′
|φ (x0 )| < 1.

Note (i).
′
ǫn+1 = φ (x0 )ǫn

ǫn+1 = Kǫn

where K is proportional.
ǫn+1 ∝ ǫn

each error is a proportional to the previous error . i.e. the method is first order iteration or
linearly convergent method.

Note (ii). If each error is proportional to the square of the previous error then it is called
second order iteration method or Quadratically method.

Note (iii). If each error is proportional to the cube of the previous error then it is called
cubic order iterative method and so on.

Note (iv).
′
ǫn+1 = φ (x0 )ǫn
′
If φ (x0 ) is closer to zero =⇒ ǫn+1 is closer to zero. =⇒ x0 , x1 , x3 , . . . will converge more
quickly to the exact root α.

2.13 Acceleration of Convergence: Aitken’s ∆2 process or

Aitken’s Method

We can accelerate the slow rate of convergence of the first order iterative process for
equation f (x) = 0 by using Aitken’s ∆2 process. Let xn−1 , xn , xn+1 be the three
successive approximations to the desired root x of the equation x = φ(x). Therefore,

ǫn−1 = x − xn−1 , ǫn = x − xn , ǫn+1 = x − xn+1 .

2.13. ACCELERATION OF CONVERGENCE: AITKEN’S ∆2 PROCESS OR AITKEN’S METHOD73

Since simple iteration is a first order process,

′
ǫn+1 = φ (x)ǫn
ǫn+1 = Kǫn ,
ǫn+1 ′
=⇒ = K, where K = φ (x). (2.5)
ǫn
ǫn = Kǫn−1 ,
ǫn
=⇒ =K (2.6)
ǫn−1
from eq(6.5) and eq(6.6),
ǫn+1 ǫn
= .
ǫn ǫn−1
ǫn−1 ǫn+1 = ǫ2n it means error in G.P

(x − xn−1 )(x − xn+1 ) = (x − xn )2

x2 − xxn+1 − xxn−1 + xn−1 xn+1 = x2 − 2xxn + x2n

−xxn+1 − xxn−1 + 2xxn = x2n − xn−1 xn+1

−x(xn+1 + xn−1 − 2xn ) = x2n − xn−1 xn+1

x2n − xn−1 xn+1

x=−
(xn+1 + xn−1 − 2xn )
x2n − xn−1 xn+1
x = xn+1 − − xn+1
(xn+1 + xn−1 − 2xn )
x2n − xn−1 xn+1 + x2n+1 + xn−1 xn+1 − 2xn xn+1
x = xn+1 −
(xn+1 + xn−1 − 2xn )
x2n + x2n+1 − 2xn xn+1
x = xn+1 −
(xn+1 + xn−1 − 2xn )
(xn+1 − xn )2
x = xn+1 − . (2.7)
(xn+1 + xn−1 − 2xn )
We introduce finite difference.
∆xn = xn+1 − xn
∆2 xn−1 = ∆(∆xn−1 )
= ∆(xn − xn−1 )
= ∆xn − ∆xn−1
= (xn+1 − xn ) − (xn − xn−1 )
2
∆ xn−1 = xn+1 − xn − xn + xn−1
∆2 xn−1 = xn+1 + xn−1 − 2xn
eq(6.7) becomes
(∆xn )2
x = xn+1 − , n ≥ 0. (2.8)
(∆2 xn+1 )
74 CHAPTER 2. SOLUTION NON-LINEAR FUNCTION

Which is the required ∆2 process. The name Aitken’s ∆2 process is given because it
contains ∆2 .

Note. Aitken’s method can not be applied to second or higher order process. It can only be
used to accelerate the convergence of any sequence that is linearly convergent.

Example. Calculate a positive real root of f (x) = x2 − 2x − 3 using Aikten’s process and
the formula x = φ(x). At x = 3 the f (x) have no sign. Since f (x) changes the sign

x 0 1 2 3 4
f (x) −3 −4 −3 0 5

between 2 and 4, therefore take x0 = 4.

x2 − 2x − 3 = 0
x2 = 2x + 3
√ ′ 2 1
x= 2x + 3 = φ(x) =⇒ φ (x) = √ =√
2 2x + 3 2x + 3
′ 1
|φ (x)| = | √ |<1
2x + 3
∴ the method is convergent.
By Simple iteration method
xn+1 = φ(xn ), n = 0, 1, 2, ....
1
xn+1 = √
2xn + 3
1 1
for n=0, x1 = √ =p = 3.3166
2x0 + 3 2(4) + 3
1 1
for n=1, x2 = √ =p = 3.1037
2x1 + 3 2(3.3166) + 3

x ∆ ∆2
x0 = 4.0000
−0.6834
x1 = 3.3166 0.4705
−0.2129
x2 = 3.1037

Applying Aitken’s ∆2 process

(∆xn )2
x = xn+1 −
∆2 (xn−1 )
2.14. THE SECANT METHOD 75

(∆x1 )2
for n=1, x = x2 −
∆2 (x0 )
(−0.2129)2
x = 3.1037 −
0.4705
x = 3.0074.

Note. The Aitken’s process can be iterated up to the desired degree of accuracy.

2.14 The Secant Method

Theorem.

xn−1 f (xn ) − xn f (xn−1 )

xn+1 = , providedf (xn ) 6= f (xn−1 ),
f (xn ) − f (xn−1 )

provided f (xn ) 6= f (xn−1 ). where xn and xn−1 are two approximation of the root of the
equation f (x) = 0.

Proof. The Secant method is a modified form of Newton-Raphson method.

f (xn
xn+1 = xn − . (2.9)
f ′ (xn )

We know that,
′ f (x0 ) − f (x)
f (x0 ) = lim ,
x→x0 x0 − x
′ f (x0 ) − f (xn−1 )
⇒ f (x0 ) = lim ,
xn−1 →x0 x0 − xn−1
′ f (xn ) − f (xn−1 )
⇒ f (xn ) = lim ,
xn−1 →xn xn − xn−1
′ f (xn ) − f (xn−1 )
f (xn ) ≈ ,
xn − xn−1

Eq(6.9) becomes

f (xn
xn+1 = xn − f (xn )−f (xn−1 )
xn −xn−1
f (xn (xn − xn−1 )
xn+1 = xn −
f (xn ) − f (xn−1 )
xn f (xn ) − xn f (xn−1 ) − xn f (xn ) + xn−1 f (xn )
xn+1 =
f (xn ) − f (xn−1 )
xn−1 f (xn ) − xn f (xn−1 )
xn+1 = .
f (xn ) − f (xn−1 )
76 CHAPTER 2. SOLUTION NON-LINEAR FUNCTION

Note. • The Secant method requires two starting values x0 and x1 .

√
• The order of convergence of Secant method is equal to 1+2 5 = 1.618. Which shows
that this method has the order of convergence slightly inferior to that of
Newton-Raphson method.
′
• The Secant method avoids the evaluation of f (x) and is well adapted for computer
usage.

• Each error is proportional to the product of the previous two errors.

2.15 The Bisection Method

This method is also known as Binary search method or Bolsano method. This method
requires two starting values x0 and x1 for the solution of non-linear equation f (x) = 0
such that f (x0 )f (x1 ) < 0 i.e. root lies between x0 and x1 .
The method start as follows.

x0 +x1
1. Find x2 using x2 = 2 (mid-point of x0 and x1 ) and find f (x2 ).

2. If f (x2 ) = 0 then x2 is a root of f (x) = 0.

If f (x2 ) 6= 0, two things are possible.

• If f (x0 )f (x2 ) < 0, compute new iterate x3 as

x0 + x2
x3 =
2

and evaluate f (x3 ).

• If f (x1 )f (x2 ) < 0, compute new iterate x3 as

x1 + x2
x3 =
2

and evaluate f (x3 ).

The process is then repeated with new points until the desired accuracy obtained.

Note. This method is very simple but is very slow to converge. However, the convergence is
guarented. For this reasons, this method is often used for solving non-linear equations. This
method is particularly useful when we have to find the roots using a computer program.
Most commercial root finding programmes use a combination of the Newton-Raphson and
the Bisection methods. If one fails to converges then switch to the other to obtain a new
estimate of the root.
2.15. THE BISECTION METHOD 77

Example. Solve the transcedental equation

πx
f (x) = e−x − sin( )
2

to find a positive real root by Bisection method. Here, f (x) = e−x − sin( πx
2 ) Since f (x)

x 0 1
f (x) 1 −0.63212

changes the sign between 0 and 0. Therefore root lies between 0 and 1.

take x0 = 0 and x1 = 1
π(0)
f (x0 ) = f (0) = e0 − sin( )=1
2
π(1)
f (x1 ) = f (1) = e1 − sin( ) = 0.63212
2
f (x0 )f (x1 ) < 0
By Bisection method
x0 + x1 0+1
x2 = = = 0.5
2 2
π(0.5)
f (x2 ) = f (0.5) = e0.5 − sin( ) = −0.1005761
2
f (x0 )f (x2 ) < 0
x0 + x2 0 + 0.5
x3 = = = 0.25
2 2
π(0.25)
f (x3 ) = f (0.25) = e0.25 − sin( ) = 0.396117
2
f (x2 )f (x3 ) < 0
x2 + x3 0.5 + 0.25
x4 = = = 0.375
2 2
π(0.375)
f (x4 ) = f (0.375) = e0.375 − sin( ) = 0.131719
2
f (x2 )f (x4 ) < 0
x2 + x4 0.5 + 0.375
x5 = = = 0.4375
2 2
π(0.4375)
f (x5 ) = f (0.4375) = e0.4375 − sin( ) = 0.011255
2
f (x2 )f (x5 ) < 0
x2 + x5 0.5 + 0.4375 π(0.46875)
x6 = = = 0.46875.f (x6 ) = f (0.46875) = e0.46875 − sin( ) = −0.045775
2 2 2
f (x5 )f (x6 ) < 0
x5 + x6 0.4375 + 0.46875
x7 = = = 0.453125
2 2
π(0.453125)
f (x7 ) = f (0.453125) = e0.453125 − sin( ) = −0.017534
2
78 CHAPTER 2. SOLUTION NON-LINEAR FUNCTION

f (x5 )f (x7 ) < 0

x5 + x7 0.4375 + 0.453125
x8 = = = 0.445313
2 2
π(0.445313)
f (x8 ) = f (0.445313) = e0.445313 − sin( ) = −0.003208
2
Hence the root of the equation upto 7 iterations is
x = 0.445313

Example. Solve the following equation by Bisection method to evaluate a positive root

x3 − x2 − 2x + 1 = 0.

Here
f (x) = x3 − x2 − 2x + 1.

Since f (x) changes the sign between 0 and 1. Therefore, root lies between 0 and 1.

x 0 1
f (x) 1 −1

take x0 = 0 and x1 = 1
f (x0 ) = f (0) = 03 − 02 − 2(0) + 1 = 1
f (x1 ) = f (1) = 13 − 12 − 2(1) + 1 = −1
f (x0 )f (x1 ) < 0
By Bisection method
x0 + x1 0+1
x2 = = = 0.5
2 2
f (x2 ) = f (0.5) = (0.5)3 − (0.5)2 − 2(0.5) + 1 = −0.125
f (x0 )f (x2 ) < 0
x0 + x2 0 + 0.5
x3 = = = 0.25
2 2
f (x3 ) = f (0.25) = (0.25)3 − (0.25)2 − 2(0.25) + 1 = 0.4531
f (x2 )f (x3 ) < 0
x2 + x3 0.5 + 0.25
x4 = = = 0.375
2 2
f (x4 ) = f (0.375) = (0.375)3 − (0.375)2 − 2(0.375) + 1 = 0.621
f (x2 )f (x4 ) < 0
x2 + x4 0.5 + 0.375
x5 = = = 0.4375
2 2
f (x5 ) = f (0.4375) = (0.4375)3 − (0.4375)2 − 2(0.4375) + 1 = 0.0173
f (x2 )f (x5 ) < 0.
2.15. THE BISECTION METHOD 79

x2 + x5 0.5 + 0.4375
x6 = = = 0.46875.
2 2
f (x6 ) = f (0.46875) = (0.46875)3 − (0.46875)2 − 2(0.46875) + 1 = −0.0543
f (x5 )f (x6 ) < 0
x5 + x6 0.4375 + 0.46875
x7 = = = 0.453125
2 2
f (x7 ) = f (0.453125) = (0.453125)3 − (0.453125)2 − 2(0.453125) + 1 = 0.0187
f (x5 )f (x7 ) < 0
x5 + x7 0.4375 + 0.453125
x8 = = = 0.4534375
2 2
Hence after 7th iterations the root is x = 0.4534 .

x π
Example. Find a positive real root of f (x) = sin(x) − 2 with x0 = 2 and x1 = π using
Bisection method.

x
f (x) = sin(x) −
2
π
take x0 = and x1 = π
2
x0 π/2 π
f (x0 ) = sin(x0 ) − = sin(π/2) − = 1 − = 0.2146
2 2 4
x1 π π
f (x1 ) = sin(x1 ) − = sin(π) − = 0 − = −1.5708
2 2 2
f (x0 )f (x1 ) < 0Therefore, By Bisection method
x0 + x1 (π/2) + π 3π
x2 = = =
2 2 4
x2 3π/4
f (x2 ) = sin(x2 ) − = sin(3π/4) − = −0.4710
2 2
f (x0 )f (x2 ) < 0
x0 + x2 1 π 3π 5π
x3 = = ( + )=
2 2 2 4 8
5π
f (x3 ) = f ( ) = −0.0579
8
f (x0 )f (x3 ) < 0
x0 + x3 1 π 5π 9π
x4 = = ( + )=
2 2 2 8 16
9π
f (x4 ) = f ( ) = 0.0972
16
f (x3 )f (x4 ) < 0
x3 + x4 1 5π 9π 19π
x5 = = ( + )=
2 2 8 16 32
19π
f (x5 ) = f ( ) = 0.0243
32
f (x3 )f (x5 ) < 0.
x3 + x5 1 5π 19π 39π
x6 = = ( + )= .
2 2 8 32 64
80 CHAPTER 2. SOLUTION NON-LINEAR FUNCTION

39π
f (x6 ) = f ( ) = −0.0157
64
f (x5 )f (x6 ) < 0
x5 + x6 1 19π 39π 77π
x7 = = ( + )=
2 2 32 64 128
Hence after 6th iterations the root is
77π
x= .
128