Computer Arithmetic

and Solution of
Non-linear Equations
UNIT 2 SOLUTION OF NON-LINEAR
EQUATIONS
Structure Page Nos.
2.0 Introduction 24
2.1 Objectives 25
2.2 Iterative Methods for Locating Roots 25
2.2.1 Bisection Method
2.2.2 Fixed-point Method
2.3 Chord Methods For Finding Roots 34
2.3.1 Regula-falsi Method
2.3.2 Newton-Raphson Method
2.3.3 Secant Method
2.4 Iterative Methods and Convergence Criteria 39
2.4.1 Order of Convergence of Iterative Methods
2.4.2 Convergence of Fixed-point Method
2.4.3 Convergence of Newton’s Method
2.4.4 Rate of Convergence of Secant Method
2.5 Summary 45
2.6 Solutions/Answers 45

2.0 INTRODUCTION
In this unit we will discuss one of the most basic problems in numerical analysis. The
problem is called a root-finding problem and consists of finding values of the variable
x (real) that satisfy the equation f(x) = 0, for a given function f. Let f be a real-value
function of a real variable. Any real number α for which f(α) = 0 is called a root of
that equation or a zero of f. We shall confine our discussion to locating only the real
roots of f(x), that is, locating non-real complex roots of f(x) = 0 will not be discussed.
This is one of the oldest numerical approximation problems. The procedures we will
discuss range from the classical Newton-Raphson method developed primarily by
Isaac Newton over 300 years ago to methods that were established in the recent past.

Myriads of methods are available for locating zeros of functions and in first section
we discuss bisection methods and fixed point method. In the second section, Chord
Method for finding roots will be discussed. More specifically, we will take up regula-
falsi method (or method of false position), Newton-Raphson method, and secant
method. In section 3, we will discuss error analysis for iterative methods or
convergence analysis of iterative method.

We shall consider the problem of numerical computation of the real roots of a given
equation
f(x) = 0

which may be algebraic or transcendental. It will be assumed that the function f(x) is
continuously differentiable a sufficient number of times. Mostly, we shall confine to
simple roots and indicate the iteration function for multiple roots in case of Newton
Raphson method.

All the methods for numerical solution of equations discussed here will consist of two
steps. First step is about the location of the roots, that is, rough approximate value of
the roots are obtained as initial approximation to a root. Second step consists of
methods, which improve the rough value of each root.
A method for improvement of the value of a root at a second step usually involves a

24
process of successive approximation of iteration. In such a process of successive Solution of Non-Linear
Equations
approximation a sequence {Xn} n = 0, 1, 2, … is generated by the method used
starting with the initial approximation xo of the root α obtained in the first step such
that the sequence {Xn} converges to α as n → ∞. This xn is called the nth
approximation of nth iterate and it gives a sufficiently accurate value of the root α.

For the first step we need the following theorem:

Theorem 1: If f(x) is continuous in the closed internal [a, b] and f(a) are of opposite
signs, then there is at least one real root α of the equation f(x) = 0 such that a < α < b.

If further f(x) is differentiable in the open interval (a, b) and either f’(x) < 0 or
f’(x) > 0 in (a, b) then f(x) is strictly monotonic in [a, b] and the root α is unique.

We shall not discuss the case of complex roots, roots of simultaneous equations nor
shall we take up cases when all roots are targeted at the same time, in this unit.

2.1 OBJECTIVES
After going through this unit, you should be able to:

• find an approximate real root of the equation f(x) = 0 by various methods;

• know the conditions under which the particular iterative process converges;
• define ‘order of convergence’ of an iterative method; and
• know how fast an iterative method converges.

2.2 ITERATIVE METHODS FOR LOCATING

ROOTS
One of the most frequently occurring problem in scientific work is to find the roots of
equations of the form:
f(x) = 0

In other words, we want to locate zeros of the function f(x). The function f(x) may be
a polynomial in x or a transcendental function. Rarely it may be possible to obtain the
exact roots of f(x) = 0. In general, we aim to obtain only approximate solutions using
some computational techniques. However, it should be borne in mind that the roots
can be computed as close to the exact roots as we wish through these methods. We
say x* satisfies f(x) = 0 approximately when f(x*) is small or a point x* which is
close to a solution of f(x) = 0 in some sense like x* – α < ε where α is a root of
f(x) = 0.

To find an initial approximation of the root, we use tabulation method or graphical

method which gives an interval containing the root. In this section, we discuss two
iterative methods (i) bisection method and (ii) fixed-point method. In a later section
we shall discuss about the rate of convergence of these methods.

2.2.1 Bisection Method

Suppose a continuous function f, defined on the interval [a, b], is given, with f(a) and
f(b) of opposite signs, i.e. f(a) f(b) < 0, then by Intermediate Value Theorem stated
below, there exists a number α on the real line such that a < α < b, for which f(α) = 0.

25
Computer Arithmetic Theorem 2 (Intermediate-value Theorem): If the function f is continuous on the
and Solution of closed interval [a, b], and if f(a) ≤ y ≤ f(a), then there exists a point c such that
Non-linear Equations
a ≤ c ≤ b and f(c) = y.

The method calls for a repeated halving of subintervals of [a, b] and, at each step,
locating the “half” containing α. To start with, a1 = a and b1 = b, and let α1 be the mid
1
point of [a, b], that is α1 = (a1 + b1). If f(α1) = 0, then α = α1. If not, then f(α1)
2
has the same sign as either f(a1) or f(b1). If f(a1) f(α1) < 0, then root lies in (a1, α1).
Otherwise the root lies in (α1, b1). In the first case we set a2 = a1 and b2 = α1 and in
the later case we set a2 = α1 and b2 = b1. Now we reapply the process to the interval
(a2, b2). Repeat the procedure until the interval width is as small as we desire. At
each step, bisection halves the length of the preceding interval. After n steps, the
1
original interval length will be reduced by a factor enclosing the root.
2n

Figure 1: Bisection Method

We now mention some stopping procedures that could be applied to terminate the
algorithm. Select a tolerance ε > 0 and generate α1, α2, … αn until one of the
following conditions is met:
(i) αn – αn–1 < ε, (2.2.1)
α n − α n −1
(ii) < ε, αn ≠ 0, or (2.2.2)
αn
(iii) f(αn) < ε (2.2.3)

While applying bisection method we repeatedly apply a fixed sequence of steps. Such
a method is called an Iteration method.

However, it is pertinent to mention that difficulties can arise using any of these
stopping criteria. For example, there exist sequence {αn} with the property that the
differences αn – αn–1 converge to zero while the sequence itself diverges. Also it is
possible for f(αn) to be close to zero while αn differs significantly from α. The criteria
given by (2.2.2) is the best stopping criterion to apply since it tests relative error.

Though bisection algorithm is conceptually clear, it has significant drawbacks. It is

very slow in converging. But, the method will always converge to a solution and for
this reason it is often used to obtain a first approximation for more efficient methods
that are going to the discussed.

26
Theorem 3: Let f ∈ C [a, b] and suppose f(a).f(b) < 0. The bisection procedure Solution of Non-Linear
Equations
generates a sequence {αn} approximating α with the property,

b−a
αn – α ≤ , n ≥ 1.
2n

Now we illustrate the procedure with the help of an example.

Example 1

Find the least positive root of equation.

f(x) = x3 + 4x2 – 10 = 0

Check that f(x) has only one root in the interval in which this least positive root lies.
Find α4 by bisection algorithm.

Solution

Consider the following tables of values.

X 0 1 2
f(x) –10 –5 14

Take a1 = 1, b1 = 2, since f(a1) f(b1) < 0.

We give the four iterations in the following tabular form.

N an bn αn f(αn)
1 1 2 1.5 2.375
2 1 1.5 1.25 – 1.79687
3 1.25 1.5 1.375 0.16211
4 1.25 1.375 1.3125 – 0.84839
5 1.3125 1.375 1.34375 – 0.35098

After four iterations, we have α4 = 1.3125 approximating the root α with an error
α – α4≤ 1.375 – 1.325 = .050 and since 1.3125 < α.

α − α4 b5 − a 5 .050 .5 1 1
< < ≤ = 10–1 = 101–2
α a5 1.3125 10 2 2

That is, the approximation is correct to at least 2 significant digits.

Remarks 1: Generally the first stage methods for location of the roots of f(x) = 0 are
(i) Tabulation method and (ii) Graphical method. The method of tabulation is very
crude and labourious and we have used it in the above example to some extent in
locating the least positive root of f(x) = 0. In graphical method we plot the graph of
the curve y = f(x) on the graph paper and the points where the curve crosses the x-axis
gives approximate values of the roots.

2.2.2 Fixed-point Method (or Method of Interation)

This method is also known as Method of Successive Approximations or Method of
Iteration. In this method, we write the equation f(x) = 0.

For example x3 – x – 1 = 0 can be written as,

27
Computer Arithmetic 1
and Solution of x = (1 + x) 3
Non-linear Equations
1+ x
or x=
x2
1+ x
or x=
x

Now solving f(x) = 0 is equivalent to solving x = g(x).

Each such g(x) given above is called an iteration function. In fact, these are infinite
number of ways in which the original equation f(x) = 0 can be written as x = g(x).
Out of all these functions where one is to be selected, will be discussed in the
following analysis.

Definition 1: A number ξ is called a fixed point of g(x) if g(ξ) = ξ and g is called the
iteration function.

Our problem is now to find out fixed point(s) of g(x). Graphically x = g(x) is
equivalent to solving y = x and y = g(x).

Figure 2: Fixed Point Method

Once an iteration function is chosen, to solve x = g(x), we start with some suitable
value x0 close to the root (how to choose this will be explained) and calculate
x1 = g(x0) (the first approximation), then x2 = g(x1) (second approximation) and so on.

In general

xn+1 = g(xn), n = 0, 1, 2 …

The sequence {xn} converges (under some suitable conditions on g) to a number ξ

(say). If g is continuous then this gives ξ = g(ξ), that is, ξ is a fixed point of g(x).

Concerning the existence, uniqueness of a fixed point and convergence of the

sequence, we state a theorem below:

Theorem 4 (Fixed Point Theorem): Let iteration function g(x) be defined and
continuous on a closed interval I = [a, b]. suppose further that g(x) satisfies the
following:
(i) g(x) ∈ I for all ∈ I
(ii) g(x) is differentiable on I = [a, b]
and there exists a non-negative number k < 1 such that for all x ∈ I, g′(x) ≤ k < 1.

28
Then Solution of Non-Linear
Equations
(a) g(x) has a fixed point ξ,
(b) the fixed point is unique, and
(c) the sequence {x1} generated from the rule xn+1 = g(xn) converges to ξ, the
fixed point of g(x), when x0 ∈ [a, b]

Proof: (a) Existence: Suppose g(a) = a or g(b) = b, then there is nothing to be

proved. So, suppose g(a) ≠ a and g(b) ≠ b. Then g(a) > a and g(b) < b since g(x) ∈ I
for all x ∈ I.

Consider h(x) = g(x) – x

Then h(a) = g(a) – a > 0 and

h(b) = g(b) – b < 0

Also h(x) is continuous on I since g(x) is so. Hence by Intermediate Value Theorem,
there exists a number ξ, a < ξ < b such that h(ξ) = 0 ⇒

g(ξ) – ξ = 0, i.e., g(ξ) = ξ

Hence g(x) has a fixed point in I.

(b) Uniqueness: From (2.2.4)

h′(x) = g′(x) – 1, but g′(x) ≤ k < 1

Hence h′(x) < 0.

Therefore, h(x) is a decreasing function and it crosses x-axis only once, i.e. h(x)
vanishes only once in I.

Therefore g(x) – x = 0 only for unique value of x in (a, b). Hence uniqueness.

(c) Convergence: Let ξ be the fixed point of g(x). We have

ξ = g(ξ) and xn+1 = g(xn).

Let en+1 = ξ – xn+1 = g(ξ) – g(xn) = g′(ηn) (ξ – xn), where ηn lies between xn and ξ, that
is, en+1 = g′(ηn)en.

Thus, we have en+1 ≤ k en. Using this repeatedly

en≤ kn e0
lim en= 0 since k < 1,
m →∞

i.e. lim ξ – xn = 0 ⇒ {xn} → ξ

m →∞

(The sequence {xn} converges to the number ξ)

Hence proved.
Thus, it may be noted that the iterative scheme xn+1 = g(xn) converges under the
condition g′(x) < 1, x ∈ [a, b].

Example 2
For x3 – x – 1 = 0, find a positive root by the fixed point method. Find minimum
number of iterations so that nth approximate xn is correct to 4 decimal places.

29
Computer Arithmetic Solution
and Solution of
Non-linear Equations 1
Write x = (1 + x) 3 = g(x).

The root lies between 1 and 2 since f(1) = –1 and f(2) = 3.

1
Also g(1) – 1 = 2 3 – 1 = +ve
1
g(2) – 2 = 3 3 – 2 = –ve
I = [a, b] = [1, 2]
1
g′(x) = 2
is decreasing function and
3(1 + x) 3

1
max g′(x)= g′(1) = 2
= k < 1.
x∈I
3× 2 3

Since g′(x) = +ve, therefore g(x) is increasing.

1
max g(x) = g(2) = 3 3 = 1.442 < 2
x∈I

1
min g(x) = g(1) = 2 3 > 1.
x∈I

Hence, g(x) ε I for all x ∈ I.

1
Therefore, xn+1 = (1 + x n generates a sequence of numbers which converges to a
)3
fixed point of g(x), (starting with xo ∈ I).
1
We have k = 2
< 1 and
3× 2 3

en ≤ kn en and eo< 1. Hence for the desired accuracy we have
n
 
 1  1
en ≤  2
 < 10–4 ⇒ n = 7.
  2
 3× 2 3 

Remark 2: In the following figures we observe the importance of g′(x) in the

neighbourhood of a fixed point ξ.

Figure 3

30
In the neighbourhood of ξ,g′(x)>1 (the sequences converge in these cases Fig. 3). Solution of Non-Linear
Equations
In the neighbourhood of ξ, g′(x) < 1 (the sequences converge in these two cases
Fig. 4).

Figure 4

Remark 3: In numerical problems, one may follow the following procedure to find an
interval [a, b].

In order to use this method one needs only to see if g′(x)<1 at a point in the
neighbourhood of the root. Therefore, determining an interval I is not necessary.

Choose an interval [a, b] by some trial and check for the following:
(i) a – g(a) and b – g(b) must be of opposite sign (with b – g(b) > 0).
(ii) g′(x) ≤ k < 1 for x ∈ [a, b]
(iii) g′(x) is continuous on [a, b].

If above conditions are not satisfied try for a smaller interval and so on.

Example 3

Find the smallest positive root of e–x – cos x = 0 by the fixed point method.

Solution

To locate the smallest positive root, we draw the figures of

y = e–x and y = cos x

Figure 5 Figure 6

π π
Figure shows that the desired root lies between 0 and i.e. in (0, ).
2 2
31
Computer Arithmetic Now let us try x = cos–1 (e–x) = g(x)
and Solution of 1
Non-linear Equations g' (x) =
2x
e −1
To make this less than 1, we must choose e2x – 1 > 1, that is, e2x > 2. This gives
1
x> ln2 This suggest that we should take the suggested interval
2
1 π π
( ln2, ), but to take a closed interval, we consider I = [ln2, ].
2 2 2

Derivative of g(x) implies that g(x) is an increasing function.

–1 –ln2
max g(x) = g(ln2) = cos (e )
x ∈I

1 π 22
= cos–1   = = > ln2
2 3 21
π
π − π
max g(x) = g( ) = cos–1 ( e 2 ) <
x∈I 2 2
π
−
since e 2 is positive. Hence g(x) ∈ I for all x ∈ I.
1 1 1
max  g' (x)  = = = = k <1
x∈I 3
e 2ln2 − 1
4
e ln − 1
since g' (x) is a decreasing function.

Hence all the sufficient conditions of the Theorem 4 are satisfied.

Now further, suppose that we want to find minimum number of iteration required to
get 4 decimal place accuracy. Let n be the minimum number of iterations required
for the desired accuracy.
1
en ≤ k n eo ≤ 10 −4
2
π
eo ≤ − ln2 ≤ 1. Thus the given condition is satisfied if
2
n
 1  1
  ≤ 10 − 4 . That is,
  2
 3
– n log 10 3 ≤ −4 − log 10 2 i.e.
4.301
n≥ = 18.07 i.e., n =19
0.238

Example 4: Find the iteration function and interval I = [a, b] which satisfy the
conditions of the theorem of fixed point to find the smallest positive root of
x = tan x.

Solution:

We rewrite the equation x = tan x as x = nπ + tan −1 x, n = 0,±1,±2, ..

π π
We know that − < tan −1 x < , so for desired root we take n = 1, that is,
2 2
−1
We consider x = π + tan x = g(x) and
 π 3π 
consider I =  , 
2 2 

 π 3π  π π π 3π
For x ∈  ,  , we have − < tan −1 x < , hence < g(x) <
2 2  2 2 2 2

32
 1 1 4 Solution of Non-Linear
Also max. g' (x) = max. 2
= 2
= 2
<1 Equations
x∈I x∈I 1+ x π 4+π
1+
4
(Since g' (x) is a decreasing function).
 π 3π 
Hence for any xo ∈ I =  ,  , the sequence generated by the fixed-point iteration
2 2 
method will converge.

Remark 5: If ξ is a fixed point of g(x) lying in the open interval (c, d) on which
φ' (x) then the sequence {xn}generated with g(x) as iteration function will not
converge to ξ , however close xo to ξ is taken except accidentally. (Consider the
root ξ = 2 of f(x) = x 2 − x − 2 = 0 with g(x) = x 2 − 2 ).

Remark 6: If ξ is a fixed point of g(x) such that g' (ξξ = 1, then the iteration
function with g(x) may or may not converge to ξ . However, if g' (ξξ < 1, in some
deleted neighbourhood of ξ , then it will converge to ξ , with xo taken sufficiently
close to ξ . If g' (ξξ ) > 1, in some deleted neighbourhood of ξ , then sequence will
not converge to ξ .

Remark 7: The conditions mentioned in fixed-point theorem are sufficient but not
necessary.

Now we discuss one example, which is very simple but conveys the fact that if a
function f(x) has more zeros i.e. f(x) = 0 has more than one real root, then we may
have to consider different g(x) for different roots.

Example 5: Find the iteration function g(x) and corresponding interval to get the two
roots 1 and 2 by fixed point iteration method for the equations
x2 – 3x + 2 = 0

Solution:

(a) For the root x = 1 if we consider x = 3x−2 = g(x), then

3
g′(x) = and
2 3x−2
x2 + 2 1 5
g′(1) = 1. Hence we choose g(x) = , I1=  , 
3 2 4
2x 5
g′(x) = > 0 for x ∈ I1. Hence g(x) is increasing. Also max. g'(x) = < 1.
3 x∈I 1 6
25
+2
57 5
max. g(x) = 16 = <
x∈I 1 3 48 4
1
+2
3 1
max. g(x) = 4 = <
x∈I 1 3 2 2
Hence all the conditions of the theorem are satisfied.

(b) Now for the other root 2, consider

x2 + 2 4
If g(x) = , then g′(2) = > 1. Hence we choose g(x) = 3x−2 with
3 3
3 5
I2 =  , 
2 2
33
Computer Arithmetic 3
and Solution of g′(x) = > 0 for all x ∈ I2, so g(x) is increasing.
Non-linear Equations 2 3x−2
11 5
max. g(x) = <
x∈I 2 2 2
5 3
min g(x) = > so g(x) : maps I 2 into itself.
x∈I 2 2 2

3 3
Also max. g1(x)= = < 1 (since g′(x) is a decreasing function).
x∈I 2 9 10
2 −2
2

Hence all the conditions for the fixed point theorem are satisfied.

In the following two examples, we use the corollary to the fixed point theorem
(Theorem 4).

Example 6: The equation f(x) = x4 – x – 10 = 0 has a root in the interval [1, 2].
Derive a suitable iteration function ϕ(x) such that the sequence of iterates obtained
from the method xk+1 = ϕ (xk), k = 0, 1, 2, ... converges to the root of f(x)=0. Using
this method and the initial approximation x0 = 1.8, iterate thrice.

1
Solution: Choose ϕ (x) = (x+10) 4 , I = [1, 2].

1 3
Then ϕ′(x) = (x +10)−4 = 1 ⋅ 1
3
4 4
(x +10) 4
1 1
max. ϕ′(x) = ⋅ 3
x ∈I2 4
(11)4
i.e., ϕ′(x) < 1 for x ∈ [1, 2]

Given x0 = 1.8
x1 = (1.8+ 10)1/ 4 = 1.8534 = 1.86
x2 = (1.8+ 10)1/ 4 = 1.8534 = 1.86
x3 = (1.8+ 10)1/ 4 = 1.8534 = 1.86

Example 7: The equation f(x) = x3 – 5x +1 = 0 has a root in the interval [0, 1].
Derive a suitable iteration function ϕ(x), such that the sequence of iterates obtained
from the formula xk+1 = ϕ(xk), k = 0, 1, 2, ... converge to the root of f(x)=0. Using
this formula and the initial approximation x0 = 0.5, iterate thrice.

x3 +1 3x2 max
Solution: ϕ (x) = is chosen since ϕ′(x) = and ϕ′(x) < 1.
5 5 0 ∈x ∈I
With x0 = 0.5, x1 = 0.225 = 0.23, x2 = 0.202.
1
What about choosing ϕ(x) = (5x−1)3 ?
What is max ϕ′(x) in this case?
0 ∈x ∈I

2.3 CHORD METHODS FOR FINDING ROOTS

In the previous section we have introduced you to two iterative methods for finding
the roots of an equation f(x) = 0, namely bisection method and fixed point method. In
34
this section we shall discuss three iterative methods: regula-falsi, Newton-Raphson, Solution of Non-Linear
Equations
and Secant methods. In the next section we shall discuss the efficiency of these
methods.

2.3.1 Regula-falsi Method

This method attempts to speed up bisection method retaining its guaranteed
convergence. Suppose we want to find a root of the equation f(x) = 0 where f(x) is a
continuous function. We start this procedure also by locating two points xo and x1
such that f(xo)f(x1) < 0.

Let us consider the line joining (xo, f(xo)) and (x1, f(x1)). This line cuts the x-axis at
some point, say x2. We find f(x2). If f(x2)f(x0) < 0, then we replace x1 by x2 and
draw a straight line connecting (x2, f(x2)) and {xo, f(xo)}. If f(x2) and f(xo) are such
that f(x2)f(x0) > 0, then x0 is replaced by x2 and draw a straight line connecting (x1,
f(x1)) and (x2, f(x2)). Where the straight line crosses x – axis. that print gives x3. In
both the cases, the new interval obtained is smaller then the initial interval. We
repeat the above procedure. Ultimately the sequence is guaranteed to converge to the
desired root.

Figure 7

f(x1 ) − f(x o )
The equation of the chord PQ is y – f(x0) = (x − x o )
x1 − x o
This cuts x-axis at the point x2 given by
f(x1 ) − f(x o )
0 – f(xo) = (x 2 − x o )
x1 − x o
x o f(x1 ) − x 1 f(x o )
i.e. x2 = .
f(x1 ) − f(x o )
x r −1 f(x r ) − x r f(x r −1 )
In general, xr+1 = , r = 1, 2, 3,....
f(x r ) − f(x r −1 )

If f(x2) = 0, then x2 is the required root. If f(x2) ≠ 0 and f(xo)f(x2) < 0, then the next
approximation lies in (xo, x2). Otherwise it lies in (x2, x1). Repeat the process till
x i +1 − x i < ε .

Example 8: The equation 2x3 + 5x2 + 5x + 3 = 0 has a root in the interval [–2, –1].
Starting with xo = –2.0 and x1 = –1.0 as initial approximations, perform three iteration
of the Regula-falsi method.

Solution:
f(–2) = –16 + 20 – 10 + 3 = –3
f(–1) = –2 + 5 – 5 + 3 = 1, and f(–2) f(–1) < 0

35
Computer Arithmetic x o f(x1 ) − x 1 f(x o ) −2 × 1 − ( −1)( −3) −5
and Solution of x2 = = = , i.e.,
f(x1 ) − f(x o ) 1 − ( −3) 4
Non-linear Equations
x2 = –1.25 (First iteration)
−125 25 −5 21
f(x2) = + 5× + 5× +3 =
32 16 4 32

The root lies in (xo, x2)

x3 = –1.384 or 1.39 (Second iteration) since
21  5 
− 2× −  −  × ( −3) − 42 − 5 − 42 − 120
32  4 
x3 = = 32 4 = 32
21 21 21 + 96
− ( −3) +3
32 32 32
−162
= = −1.384 ≈ −1.39.
117

For next iteration find f(x3) and proceed in similar fashion.

2.3.2 Newton-Raphson Method

Newton-Raphson method or N–R method in short.

It can be introduced by basing it on the Taylor’s expansion as explained below. Let xo

be an initial approximation and assume that xo is close to the exact root α and
f’(xo) ≠ 0. Let α = xo + h where h is a small quantity in magnitude. Let f(x) satisfy
all the conditions of Taylor’s theorem. Then
f(xo+ h) = f(xo) + h f’(xo) + .....

The method is derived by assuming that the term involving h2 is negligible and that
f(xo) + h f′(xo) = 0 i.e. f(xo) + (α - xo)f′(xo) = 0
f ( xo )
i.e. α ≈ xo -
f ' ( xo )
f ( xo )
i.e. x1 = xo -
f ' ( xo )
Geometrically the next approximation, x1, is the abscissa of the point of intersection
of the tangent PT and the x-axis in Figure 8.

The iteration scheme is

f(x n )
. xn+1 = xn – n = 0, 1, 2, ....
f' (x n )

Figure 8 : Newton – Raphson Method

36
N-R method is an extremely powerful technique, but it has a major difficulty – the Solution of Non-Linear
Equations
need to know the value of the derivative of f at each approximation or iteration.
derivative evaluation, we discuss a slight variation, known as Secant Method next.

Example 9: Newton-Raphson method is used to find the pth root of a positive real
number R. Set up the iteration scheme. Perform three iterations of the method for
R=16.0, p =3, starting with the initial approximation 2.0.

Solution: Let us denote pth root of R by x i.e.

x = R 1/p or xp ─ R = 0.
f′ (x) = pxp─1.

Newton-Raphson Iteration scheme is

f (x k )
xk+1 = x k − ,
f ' (x k )
x kp − R
= xk − ,
px kp −1
 1 R
On simiplification we get xk+1 =  1 −  xk + , k = 0, 1, 2, .....
 p  p x kp −1
8 91
For R = 16, p = 3, xo = 2, we get x1 = = 2.67, x2 = = 2.53,
3 36

Remark 8: If a root is repeated m times, the N─R method is modified as

f (x k )
x k +1 = x k − in
f ′(x k )

Example 10 : The quadric equation x4 – 4x2 + 4 = 0 has a double root. Starting with
xo = 1.5, compute two iterations by Newton-Raphson method.

Solution: For m-repeated root of f(x) = 0, the iteration scheme in case of Newton-
Raphson method is given by:
f (x k )
xk+1 = x k − m , k = 0, 1, 2, ...
f' (x k )
In this case, we have
xk+1 = x k −
(
2 x k4 − 4x k2 + 4 ) , (since m =2 and f(x) = x 4 − 4x 2 + 4 )
4x k3 − 8x k
With xo = 1.5, we have
1
2×
3 16 = 17 = 1.41
x1 = −
2 3 12
2

Example 11: Perform two iterations of the Newton-Raphson method to find an

1
approximate value of starting with the initial approximation xo = 0.02
15
Solution: Suppose we want to find the reciprocal of the number N.
1
Let f(x) = –N
x

37
Computer Arithmetic 1
and Solution of Then f’(x) = and the iteration scheme is
Non-linear Equations
x2
1
−N
xk
xk+1 = xk − = 2xk – Nx k2 , k = 0, 1, 2...
−1
x k2

In this case we xk+1 = 2xk – 15 x 2k , k = 0, 1,2. This gives x1 = 0.034, x2 = 0.051,

x3 = 0.063, etc.

2.3.3 Secant Method

This method is a modification of the regula-falsi method and retains the use of secants
throughout, but dispenses with the bracketing of the root. Given a function f(x) and
two given points xo and x1,

We compute,
f (x o ) x f (x1 ) − x1 f (x o )
x2 = x o − = o .
f (x1 ) − f (x o ) f (x1 ) − f (x o )
x1 − x o

Figure 9

Above figure illustrates how xn+1 is obtained.

Example 12: Apply the Secant method to find a root of the equation

2x3 + 3x2 + 3x + 1 = 0. Take the initial approximations as xo = –0.2 and x1 = –0.4.

Solutions:

Let f(x) = 2x3 + 3x2 + 3x + 1

f(–0.2) = 0.504
f(–0.4) = 0.152
x o f (x1 ) − x1 f (x o ) .1712
x2 = ,= = 00.48
f (x1 ) − f (x o ) .352

You may now solve the following exercises:

E1) Using the Newton-Raphson method, find the square root of 10 with initial
approximation xo = 3.

38
E2) A fixed point iteration to find a root of 3x3 + 2x2 + 3x + 2 = 0 close to Solution of Non-Linear
Equations
2 + 3x k + 2x k2
xo = –0.5 is written as xk+1 = –
3x k2
Does this iteration converge? If so, iterate twice. If not, write a suitable form
of the iteration, show that it converges and iterate twice to find the root.

E3) Do three iterations of Secant method to find an approximate root of the

equation.
3x3 – 4x2 + 3x – 4 = 0
Starting with initial approximations xo = 0 and x1 = 1.

E4) Do three iterations of fixed point iteration method to find the smallest positive
roots of x2 – 3x + 1 = 0, by choosing a suitable iteration function, that
converges. Start with xo = 0.5.

E5) Obtain the smallest positive root of the equation of x3 – 5x + 1 = 0 by using 3

iterations of the bisection method.

E6) Starting with xo = 0, perform two iterations to find an approximate root of the
equation x3 – 4x + 1 = 0, using Newton-Raphson method.

E7) Do three iterations of the Secant method to solve the equation

x3 + x – 6 = 0,
starting with xo = 1 and x2 = 2.

E8) Apply bisection method to find an approximation to the positive root of the
equation.
2x – 3 Sinx – 5 = 0
rounded off to three decimal places.

E9) It is known that the equation x3 + 7x2 + 9 = 0 has a root between –8 and
–7. Use the regula-falsi method to obtain the root rounded off to 3 decimal
4
places. Stop the iteration when x i +1 x i < 10

E10) Determine an approximate root of the equation

Cosx – xex = 0
using Secant method with the two initial approximations as xo = 0 and
x1 = 1. Do two iterations

2.4 ITERATIVE METHODS & CONVERGENCE

CRITERIA
Let {xn} be a sequence of iterates of a required root α of the equation f(x) = 0,
generated by a given method.

The error at the nth iteration, denoted by en is given by

en = α – xn
The sequence of iterates {xn} converge to α if and only if en → 0 as n → ∞
otherwise the sequence of iterates diverges.

For each method of iteration considered by us, we shall discuss conditions under
which the iteration converges.

Let x0, x1, x2, etc be a sequence generated by some iterative method.

39
Computer Arithmetic 2.4.1 Order of Convergence of Iterative Methods
and Solution of
Non-linear Equations Definition 2: If an iterative method converges, that is, if {xn} converges to the
desired root α , and two constants p ≥ 1 and C > 0 exist such that

en+1
lim = C (C does not depend on n)
n →∞ enp

then p is called the order of convergence of the method and C is called the asymptotic
error constant. An iterative method with higher order of convergence than 1 is
expected to converge rapidly. If p = 1, 2, 3, …, then the convergence is called
linear, quadratic, cubic… respectively.

(i) For the Fixed Point Iteration method the order of convergence is generally 1,
that is, it is of first order (convergence is linear).
(ii) For the Newton-Raphson method, with xo near the root, the order of
convergence is 2, that is, of second order (convergence is quadratic).
(iii) For the Secant Method order of convergence is 1.618 ≈ 1.62 but it is not
guaranteed to converge.
The bisection method is guaranteed to converge, but convergence is slow. Regula-
falsi method is guaranteed to converge. However, it is slow and order of convergence
is 1.

2.4.2 Convergence of a Fixed Point Method

Theorem 5:

If g’(x) is continuous in some neighbourhood of the fixed point ξ of g, then the fixed
point method converges linearly provided g’( ξ ) ≠ 0.

Proof: en+1 = ξ – x n+1

= g( ξ ) – g(xn)
= g’( η n) ( ξ – xn)
for some η n lying between xn and ξ .
en+1 = en g’( η n)
Since g’(x) is continuous in a neighbourhood of ξ , we can write
g’( η n) = g’( ξ ) + hn such that lim hn = 0.
n →∞
en+1 = en{g’( ξ ) +hn}

On taking n → ∞ , we have

e n +1
lim = g' (ξ ) = C ≠ 0
n →∞ en

e n +1
Hence p = 1, since = g' (ξ )
en
Therefore, fixed point method converges linearly.

Note: Smaller the value of g' (ξ ) , faster would be the convergence.

Theorem 6: If g”(x) is continuous in some neighbourhood of the fixed point ξ of g,

40
then the fixed point method converges quadratically, provided g’( ξ ) =0 and g”( ξ )≠0. Solution of Non-Linear
Equations

Proof: We have

en+1 = ξ – xn+1
en+1 = g( ξ ) – g(xn)
= g( ξ ) – g( ξ – en)
By using Taylor’s series expansion, we have
e n2
en+1 = g( ξ ) – {g( ξ ) – en g’( ξ ) + g" (η n ) }
2

for some η n lying in the interval of xn and ξ . That is,

en+1 =-
e n2 ''
2
[ ]
g (ξ ) + hn since g”(x) is continuous, hn → 0. as n → ∞ .

e n +1 g" (ξ )
Thus, lim 2
= = C≠0
n→∞ en 2

Here p = 2, hence convergence is quadratic.

Fixed-point iteration is effective when it converges quadratically, as in Newton-

Raphson method discussed below.

N─R Method

We define for equation f(x) = 0 an iterative function g(x) as

f (x )
g(x) = x – , then the method is called Newton’s method. We state a
f' (x )
theorem without proof which suggests an interval in which if xo is taken then
f (x n )
Newton’s method converges. We generate the sequence {xn}as xn+1 = xn – ,n
f' (x n )
=1, 2, 3, …

2.4.3 Convergence of Newton’s Method

Theorem 7:

Suppose we are to solve f(x) = 0. If f’(x) ≠ 0 and f”(x) is continuous on the closed
finite interval [a, b] and let the following conditions be satisfied:

(i) f(a) f(b) < 0

(ii) f”(x) is either ≥ 0 or ≤ 0 for all x ∈ [a, b]
(iii) At the end points a, b

f (a ) f (b )
< b – a and < b – a.
f' (a ) f' (b )

Then Newton’s method converges to the unique solution ξ of f(x) = 0 in [a, b] for
any choice of x0 ∈ [a, b].

Theorem 8: Let f(x) be twice continuously differentiable in an open interval

containing a simple root ξ of f(x) = 0. Further let f"(x) exists in neighbourhood of.
Then the Newton’s method converges quadratically.
41
Computer Arithmetic f (x )
and Solution of Proof: g(x) = x – is continuously differentiable in some open neighbourhood
Non-linear Equations f ' (x )
of ξ . On differentiating g(x), we get

g′ (x) = 1 –
[ f' (x )]2 − f(x)f' (x )
[ f' (x )]2
f(x)f" (x )
=
[ f' (x )]2
g′′ ( ξ ) = 0, since f( ξ ) = 0 (f’( ξ ) ≠ 0 for a simple root ξ )
− 2f(x)[ f' (x )][ f" (x )] + [ f' (x )]2 { f' (x ) f" (x ) + f (x ) f" ' (x )}
2
Also g”(x) =
[ f' (x )]4
=
[ f' (x )]2 f" (x ) + f (x ) f' (x ) f" ' (x ) − 2f (x )[ f" (x )]2
[ f' (x )]3
f" (ξ )
g”( ξ ) = ≠0
f' (ξ )

By Taylor’s formula, we have

en+1 = ξ – xn+1 = g( ξ ) – g(xn)
1
= –g’( ξ )(xn– ξ ) – g”( η n)(xn– ξ )2 for some η n between ξ and xn. That is
2
1
en+1 = g’( ξ )en – g”( η n)e2 n
2
since g’( ξ ) = 0, and g”(x) is continuous, we have
1
en+1 ≅ – g”( ξ ) en2 .
2

Hence the Newton’s Method converges quadratically if of xo is chosen sufficiently

close to ξ , where ξ is a simple root of ξ .

2.4.4 Rate of Convergence of Secant Method

Suppose f(x) = 0 is to be solved. Consider the curve y = f(x).

Figure 10

Let the chord AB through the points A(xn–1, f(xn–1)) and B (xn, f(xn)) be drawn.
Suppose this intersects x–axis at C. Denote this value of x by xn+1. That is

42
 f(x n ) − f(x n −1 ) Solution of Non-Linear
y – f(xn-1) = (x – xn–1) Equations
x n − x n −1
y = 0, x = xn+1, we get

f(x n −1 )(x n − x n −1 )
xn+1 = xn–1 –
f ( x n ) − f ( x n −1 )

x n −1 f(x n ) − x n f(x n −1 )
=
f ( x n ) − f ( x n −1 )

This is known as secant method. The sequence {xn} is generated with starting points
x0, x1. We get x2, reject x0, and use x1, x2 to get x3 and so on.

Let en+1 = ξ – xn+1

x n −1 f(x n ) − x n f(x n −1 )
=ξ –
f ( x n ) − f ( x n −1 )
writing en = ξ – xn, en–1 = ξ – xn–1
and xn = ξ – en, xn–1 = ξ – en–1

we get
e n −1 f(ξ − e n ) − e n f(ξ − e n −1 )
en+1 =
f (ξ − e n ) − f (ξ − e n −1 )

 e n2 
= e n −1  f(ξ( − e n f' (ξξ− f" (ξξ+ higher order terms 
 2 

 e2 
− e n  f(ξ( − e n −1 f' (ξξ+ n f" (ξξ+ higher order terms 
 2 
since Q f( ξ ) = 0
f(ξ( − e n f' (ξξ− f(ξ( + e n −1 f' (ξξ

1 2
2
( )
e n e n −1 − e n e n2−1 f" (ξξ
en+1 ≅
− (e n − e n −1 ) f' (ξξ

1 f" (ξξ
= − enen–1, for sufficiently large n
2 f' (ξξ

1 f" (ξξ
Let − = α (fixed constant).
2 f' (ξξ
Then en+1 = α enen–1

Suppose en+1 = C enp ⇒ e n = Cenp−1 substituting these in previous results

1
p  en
α 1
=α
Cenp  = 1 e n 1+ p
en 
 C
C p
Equating powers of p, on both sides we get
1
P = 1 + ⇒ p2 − p −1 = 0
p
1± 5
P= , p = 1.618.
2

43
Computer Arithmetic Now after comparing the rate of convergence of fixed point method, N─R Method and
and Solution of Secant method, we find that secant is faster than fixed point month and N─R method
Non-linear Equations
is faster than secant method. For further qualitative comparison refer the books
mentioned.
Apart from the rate of convergence, the amount of computational effort required for
iteration and the sensitivity of the method to the starting value and the intermediate
values, are two main basis for comparison of various iterative methods discussed here.
In the case of Newton’s method, if f ′ (x) is near zero anytime during the iterative
cycle, it may diverge. Furthermore, the amount of computational effort to compute
f(x) and f ′′ (x) is considerable and time consuming. Whereas the fixed point method
is easy to programme.

You may now solve the following exercises.

E11) Let M denote the length of the initial interval [a0 ,b0 ] . Let (x 0 , x1 , x3 ...)
represent the successive midpoints generated by the bisection method. Show
M
that x i +1 − x i =
2 i+2
Also show that the number n of iterations required to generate an
approximation to a root to an accuracy ε is given by

n > −2 −
log ε ( M)
log2

E12) If x = ξ is a zero of f(x) of order 2, then f (ξ ) = 0 , f ' (ξ ) = 0 and f " (ξ ) ≠ 0 . Show

that in this case Newton-Raphson’s method no longer converges
quadratically. Also show that if f ' (ξ ) = 0 , f " (ξ ) ≠ 0 and f " ' (x ) is continuous in
the neighbourhood of ξ , the iteration
2f(x i )
x i +1 = x i − = g(x i )
f(x i )
does converge quadratically.

E13) The quadratic equation x 4 − 4x 2 + 4 = 0 has a double root at 2 . Starting

with x0 = 1.5, compute three successive approximations to the root by
f(x)
Newton-Raphson method. Do this with g 1 (x) = x − and
f' (x)
2f(x)
g 2 (x) = x − and comment on the order of convergence from your results.
f' (x)

E14) The following are the five successive iterations obtained by the Secant
method to find the real positive root of the equation x 3 − x − 1 = 0 starting with
x 0 = 1.0 and x 1 = 2.0.

n 2 3 4 5 6 7
xn 1.166667 1.2531120 1.3372064 1.3238501 1.3247079 1.3247180

Calculate e n and e n +1 e n e n −1 for n = 2, 3, 4. Also compute the constant

directly  f' ' (ξ ) 2f' (ξ ) assuming the value of ξ correct to eight decimal places
 
as ξ = 1.324718.

44
E15) If a 0 = 0 and b 0 = 1.0 , how many steps of the bisection method are needed to Solution of Non-Linear
Equations
determine the root with an error of at most 10 −5 ?

2.5 SUMMARY
In this unit we have covered the following points:
The methods for finding an approximate solution of equation in one variable involve
two steps:
(i) Find an initial approximation to a root.
(ii) Improve the initial approximation to get more accurate value of the root.

The following iterative methods have been discussed:

(i) Bisection method

(ii) Fixed point iteration method
(iii) Regula-falsi method
(iv) Newton-Raphson method
(v) Secant method

We have introduced the convergence criterion of an iteration process.

We have obtained the order/rate of convergence for the iterative methods discussed.
Finally we have given a comparative performance of these methods.

2.6 SOLUTIONS/ANSWERS
E1) x = 10 , i.e. x2 = 10. f(x) = x2 – 10
x n2 − 10 x 2 + 10
xn+1 = x n − = n , n = 0, 1, 2,
2x n 2x n
19 (3.167) 2 + 10
xo = 3, x1 = = 3.167, x2 = = 3.162
6 6.334

E2) Here φ ( x) = –
1
2
(2 + 3x + 2x ) 2
3x
φ ' ( x) = 1 (4 + 3x ) > 1
at xo = –0.5
3 3
x

Hence iteration does not converge.

If φ ( x) = –
1
3
(
2 + 2x 2 + 3x 3 , then )
φ ' ( x) = −
1
(4x + 9x 2
)< 1 at xo = –0.5
3

Hence in this case iteration converges

First iteration x1 = –0.708
Second iteration x2 = –0.646

E3) f(x) = 3x3 – 4x2 + 3x – 4, xo = 0, x1 = 1.

x n −1 f ( x n ) − x n f ( x n −1 )
xn+1 = , n = 1, 2, 3
f (x n ) − f ( x n −1 )
This gives x2 = 2, x3 = 1.167, x4 = 1.255

45
Computer Arithmetic E4) Root lies in [0, 1]. We take.
and Solution of
x 2 +1
Non-linear Equations x= = g(x)
3
2x
g' (x ) = ⇒ g'(x) < 1
3

Starting with x0 = 0.5, we have

5 169
x1 = = 0.417, x 2 = = 0.391 and x 3 = 0.384
12 432

E5) f(0) > 0 and f(1) < 0. The smallest positive root lies in ]0, 1[.

No. of bisection Bisected value f(xi) Improved

xi interval
1 0.5 – 1.375 ]0,0.5[
2 0.25 – 0.09375 ]0,0.25[
3 0.125 0.37895 ]0.125, 0.25[

It is enough to check the sign of f(x0) – the value need not be calculated.

The approximate value of the desired root is 0.1875.

E6) Here f(x) = x3 – 4x + 1, x0 = 0.

f (xx )
The iteration formula is xi +1 = x 2 −
f 1 ( xi )
2xi3 − 1
i.e. xi +1 = .
3xi2 − 4

This gives
x1 = 0.25, x1 = 0.254095 ≈ 0.2541

E7) f ( x) = x 3 + x = 6, x 0 = 1, x1 = 2
x f ( x n ) − x n f ( x n −1 )
x n +1 = n −1 n = 1, 2, 3, …
f ( x n ) − f ( x n −1 )

This gives x 2 = 1.5, x3 = 1.609 ≈ 1.61, x 4 = 1.64.

E8) Here f(x) = 2x – 3 Sinx – 5

x 0 1 2 2.5 2.8 2.9

f(x) – 5.0 – 5.51224 – 3.7278 – 1.7954 – 0.4049 0.0822

Thus a positive root lies in the interval [2.8, 2.9].

No. of bisection Bisected value x0 f (x0 ) Improved Interval

1 2.85 –0.1624 [2.85, 2.9]
2 2.875 –0.0403 [2.875, 2.9]
3 2.8875 –0.02089 [2.875, 2.8875]
4 2.88125

x 0 f(x 1 ) − x 1 f(x0 ) ( −8).9 − ( −7)( −55)

E9) x2 = = = 7.1406
f(x1 ) − f(x 0 ) 0 + 55
46
 Solution of Non-Linear
Equations
Similarly x 3 = −7.168174
The iterated values are presented in tabular form below:

No. of Interval Bisected The function

intersections value x0 value f ( xi )
1 ] –8, –7[ –7.1406 1.862856
2 ] –8, –7.1406[ –7.168174 0.358767
3
4
5
6

Complete the above table. You can find that the difference between the 5th
and 6th iterated values is 7.1748226 − 7.1747855 = 0.0000371 signaling a
stop to the iteration. We conclude that –7.175 is an approximate root rounded
to the decimal places.

E10) Here f(x) = cosx − xe 2 , x0 = 0 and x1 = 1

x0 f(x1 ) − x1 f(x0 )
x2 = = 0.3146653378
f(x1 ) − f(x0 )
x1 f(x 2 ) − x 2 f(x1 )
x3 = = 0.4467281466
f(x 2 ) − f(x1 )

E11) Starting with bisection method with initial interval [a 0 ,b0 ] (recall that in
1
each step the interval width is reduced by we have
2
b0 − a 0 M
b1 − a 1 = =
2 2

b1 − a 1 b0 − a 0
b2 − a 2 = =
2 2
b0 − a 0
and finally bn − a n =
2n
a −b
Let x n = n n .
2

an + bn
2

xn
an bn

xn+1

a n + 1 + bn +1 a n + bn
Then x n +1 − x n = −
2 2
a n + bn
We have either a n +1 = and bn +1 = bn
2
47
Computer Arithmetic a n + bn
and Solution of or a n +1 = a n and bn +1 = .
Non-linear Equations 2
In either case

bn − a n b0 − a 0
x n +1 − x n = =
2 2
2 n+2

M
We want x n +1 − x n = <ε.
2 n+ 2

This is satisfied if

 M 
log  n + 2  < logε
2 

log M – (n + 2) log 2 < log ε

nlog2 > – 2log2 + log M – log ε

n > −2 −
( M)
log ε
log2

E12) In case we have for a simple root ξ

f(x n )
x n +1 = x n − = g (x n )
f' (x n )
f(x)f" (x)
g' (x) = . Thus
[ f' (x)]2
f" (ξξ
g' (ξξ = 0 since f( ξ ) = 0 and g" (ξξ = (f' (ξξ ≠ 0)
f' (ξξ
But given that f( ξ ) = 0 = f’( ξ ) and f”( ξ) ≠ 0.

In this case
f(x)f" (x) f(x)
lim = lim lim f " ( x)
x →ξ [ f' (x)] 2 x →ξ [ f' (x)]2 x →ξ

f' (x) 1
= lim lim f" (x) = (by L’Hospital Rule)
x →ξ 2f(x)f" (x) x →ξ 2
1
That is g' (ξξ = ≠0
2
Hence it does not converge quadratically.

In case

2f(x n ) 2f(x)
x n +1 = x n − where g(x) = x −
f' (x n ) f' (x)
2f(x)f" (x) − [ f' (x)]2
g ' ( x) = and g' (ξξ = 0 .
[ f' (x)]2
Since
2f(x)f" (x)
g’(x) = − 1 and
[ f' (x)]2

48
 2f(x)f" (x) Solution of Non-Linear
lim g’(x) = lim −1 Equations
x →ξ x →ξ [ f' (x)]
2

2f(x)
= lim ⋅ lim f”(x) – 1
x →ξ [ f' (x)]2 x →ξ

1
= 2× − 1 = 0.
2

E13) f(1.5) = 5.0625 – 9 + 4 = .0625

f’(1.5) = 13.5 – 12 = 1.5

With g1 ( x)
.0625
x1 = 1.5 − = 1.5 – .04 = 1.46
1.5
f(1.46) = 4.543 – 8.52 + 4 = 0.02
f’(1.46) = 12.45 – 11.68 = 0.77
0.02
x2 = 1.46 − = 1.44
0.77

With g 2 ( x)
2 ×.0625
x1 = 1.5 − = 1.5 – 0.08 = 1.42
1.5
f(1.42) = 4.065 – 8.065 + 4 = 0
x2 = 1.42
Actual root = 1.4142. Hence convergence is faster with g 2 ( x) with two
decimal digit arithmetic.

E14) We have the following results in tabular form:

n 1 2 3 4 5
en 0.1580513 0.0716060 0.012884 0.0008679 0.0000101
en+1 enen−1 1.1034669 0.9705400 0.9318475

Also f" (ξξ 2f' (ξ ) = 0.93188 (ξ = 1.3247180 ) e5 e 4 e3 = 0.9318475. Hence

agreement is good for n = 4.

E15) Here M = b0 − a0 = 1 − 0 = 1

n > −2 −
( M)
log ε
log2
Here ε = 10 −5
log10 −5
So n > −2 −
log2

5log10
= −2 +
log2
5
= −2 +
log2
= −2 + 5 × 3.322
= −2 + 16.61
= 14.61
n ≥ 15

49
Computer Arithmetic
and Solution of
Non-linear Equations

50