By: Habtamu Garoma 1

Math 2061: Numerical

Analysis I
Chapter 2

Solution of Nonlinear
Equations

April 23, 2025

 Root Finding Problems
2

Many problems in Science and

Engineering are expressed as:

Given a continuous function f(x),

find the value x such that f ( x) 0

These problems are called root finding problems.

By: Habtamu Garoma April 23, 2025

 Roots of Equations
3

A number x that satisfies an equation is

called a root of the equation.
The equation : x 4  3 x 3  7 x 2  15 x  18
has four roots :  2, 3, 3 , and  1 .
i.e., x 4  3 x 3  7 x 2  15 x  18 ( x  2)( x  3) 2 ( x  1)
The equation has two simple roots ( 1 and  2)
and a repeated root (3) with multiplici ty 2.

By: Habtamu Garoma April 23, 2025

 Zeros of a Function
4

Let f(x) be a real-valued function of a real

variable. Any number x for which
f(x)=0 is called a zero of the function.

Examples:
2 and 3 are zeros of the function f(x) = (x-2)(x-3).

By: Habtamu Garoma April 23, 2025

 Graphical Interpretation of
5
Zeros

 The real zeros of a f(x)

function f(x) are
the values of x at
which the graph of
the function
crosses (or
touches) the x-axis. Real zeros of f(x)

By: Habtamu Garoma April 23, 2025

 Simple Zeros
6

f ( x) x  1( x  2)

f ( x) ( x  1)x  2  x 2  x  2
has two simple zeros (one at x 2 and one at x  1)
By: Habtamu Garoma April 23, 2025
 Multiple Zeros
7

f ( x ) x  1
2

f ( x) x  1  x 2  2 x  1
2

has double zeros (zero with muliplicity 2) at x 1

By: Habtamu Garoma April 23, 2025

 Multiple Zeros
8

3
f ( x)  x

f ( x)  x 3 has a zero with muliplicity 3 at x 0

By: Habtamu Garoma April 23, 2025

 Solution Methods
9

Several ways to solve nonlinear equations

are possible:

 Analytical Solutions
 Possible for special equations only
 Graphical Solutions
 Useful
for providing initial guesses for other
methods
 Numerical Solutions
 Open methods
 Bracketing methods
By: Habtamu Garoma April 23, 2025
 Analytical Methods
10

Analytical Solutions are available for

special equations only.
Analytical solution of : a x 2  b x  c 0
 b  b 2  4ac
roots 
2a

No analytical solution is available for : x  e  x 0

April 23, 2025 By: Habtamu Garoma

 Graphical Methods
11

 Graphical methods are useful to provide an

initial guess to be used by other methods.

x
Solve e
2 Root
x
x e x
The root  [0,1] 1

root 0.6
1 2

By: Habtamu Garoma April 23, 2025

 Numerical Methods
12

Many methods are available to solve

nonlinear equations:
 Bisection Method
 False position Method

 Secant Method

 Newton’s Method

 Fixed point iterations

By: Habtamu Garoma April 23, 2025

 Bracketing Methods
13

 In bracketing methods, the method

starts with an interval that contains the
root and a procedure is used to obtain a
smaller interval containing the root.

 Examples of bracketing methods:

 Bisection method
 False position method

By: Habtamu Garoma April 23, 2025

 Open Methods
14

 In the open methods, the method starts

with one or more initial guess points. In
each iteration, a new guess of the root is
obtained.
 Open methods are usually more efficient
than bracketing methods.
 They may not converge to a root.

April 23, 2025 By: Habtamu Garoma

 Convergence Notation
15

A sequence x1 , x2 ,..., xn ,... is said to converge to x if

to every   0 there exists N such that :

xn  x   n  N

By: Habtamu Garoma April 23, 2025

 Convergence Notation
16

Let x1 , x2 ,...., converge to x.

xn 1  x
Linear Convergence : C
xn  x
xn 1  x
Quadratic Convergence : 2
C
xn  x
xn 1  x
Convergence of order P : p
C
xn  x

By: Habtamu Garoma April 23, 2025

 Speed of Convergence
17

 We can compare different methods in

terms of their convergence rate.
 Quadratic convergence is faster than
linear convergence.
 A method with convergence order q
converges faster than a method with
convergence order p if q>p.
 Methods of convergence order p>1 are
said to have super linear convergence.
By: Habtamu Garoma April 23, 2025
 By: Habtamu Garoma 18

BISECTION
METHOD
The Bisection Algorithm
Convergence Analysis of Bisection
Method
Examples

April 23, 2025

 Introduction
19

 The Bisection method is one of the simplest

methods to find a zero of a nonlinear function.
 It is also called interval halving method.
 To use the Bisection method, one needs an
initial interval that is known to contain a zero
of the function.
 The method systematically reduces the
interval. It does this by dividing the interval
into two equal parts, performs a simple test
and based on the result of the test, half of the
interval is thrown away.
 The procedure is repeated until the desired
interval size is obtained.
By: Habtamu Garoma April 23, 2025
 Intermediate Value
20
Theorem
 Let f(x) be defined on the
interval [a,b].
f(a)

 Intermediate value
theorem:
a b
if a function is continuous
and f(a) and f(b) have f(b)
different signs then the
function has at least one
zero in the interval [a,b].
By: Habtamu Garoma April 23, 2025
 Examples
21

 If f(a) and f(b) have

the same sign, the
function may have an
even number of real a b
zeros or no real zeros
in the interval [a, b]. The function has four real zeros

 Bisection method can

not be used in these
cases. a b
The function has no real zeros

By: Habtamu Garoma April 23, 2025

 Two More Examples
22

 If f(a) and f(b) have

different signs, the
function has at least
a b
one real zero.
The function has one real zero
 Bisection method
can be used to find
one of the zeros. a b

The function has three real zeros

By: Habtamu Garoma April 23, 2025

 Bisection Method
23

 If the function is continuous on [a,b] and

f(a) and f(b) have different signs,
Bisection method obtains a new interval
that is half of the current interval and
the sign of the function at the end points
of the interval are different.

 This allows us to repeat the Bisection

procedure to further reduce the size of
the interval.

By: Habtamu Garoma April 23, 2025

 Bisection Method
24

Assumptions:
Given an interval [a,b]
f(x) is continuous on [a,b]
f(a) and f(b) have opposite signs.

These assumptions ensure the existence

of at least one zero in the interval [a,b]
and the bisection method can be used to
obtain a smaller interval that contains the
zero.
By: Habtamu Garoma April 23, 2025
 Bisection Algorithm
25

Assumptions:
 f(x) is continuous on [a,b]
 f(a) f(b) < 0 f(a)
Algorithm:
Loop c b
1. Compute the mid point c=(a+b)/2
2. Evaluate f(c) a
3. If f(a) f(c) < 0 then new interval [a, c]
If f(a) f(c) > 0 then new interval [c, b]
f(b)
End loop

By: Habtamu Garoma April 23, 2025

 Bisection Method
26

b0
a0 a1 a2

By: Habtamu Garoma April 23, 2025

 Example
27

+ + -

+ - -

+ + -

By: Habtamu Garoma April 23, 2025

 Example
28

Can you use Bisection method to find a zero of :

f ( x)  x 3  3 x  1 in the interval [0,2]?

Answer:
f ( x) is continuous on [0,2]
and f(0) * f(2) (1)(3) 3  0
 Assumptions are not satisfied
 Bisection method can not be used

By: Habtamu Garoma April 23, 2025

 Example
29

Can you use Bisection method to find a zero of :

f ( x)  x 3  3 x  1 in the interval [0,1]?

Answer:
f ( x) is continuous on [0,1]
and f(0) * f(1) (1)(-1)  1  0
 Assumptions are satisfied
 Bisection method can be used

By: Habtamu Garoma April 23, 2025

 Best Estimate and Error
30
Level
Bisection method obtains an interval
that is guaranteed to contain a zero of
the function.

Questions:
 What is the best estimate of the zero of

f(x)?
 What is the error level in the obtained

estimate?
By: Habtamu Garoma April 23, 2025
 Best Estimate and Error
31
Level
The best estimate of the zero of the
function f(x) after the first iteration of
the Bisection method is the mid point of
the initial interval:
ba
Estimate of the zero : r 
2
b a
Error 
2

By: Habtamu Garoma April 23, 2025

 Stopping Criteria
32

Two common stopping criteria

1. Stop after a fixed number of iterations

2. Stop when the absolute error is less
than a specified value

How are these criteria related?

By: Habtamu Garoma April 23, 2025

 Stopping Criteria
33

cn : is the midpoint of the interval at the n th iteration

( cn is usually used as the estimate of the root).
r: is the zero of the function.

After n iterations :
0
b  a  x
error  r - cn  Ean  n  n
2 2

By: Habtamu Garoma April 23, 2025

 Convergence Analysis
34

Given f ( x), a, b, and 

How many iterations are needed such that : x - r  
where r is the zero of f(x) and x is the
bisection estimate (i.e., x ck ) ?

log(b  a )  log( )
n
log(2)
By: Habtamu Garoma April 23, 2025
 Convergence Analysis –
35
Alternative Form

log(b  a )  log( )
n
log(2)

 width of initial interval  b a

n log 2   log 2  
 desired error    

By: Habtamu Garoma April 23, 2025

 Example
36

a 6, b 7,  0.0005

How many iterations are needed such that : x - r  ?

log(b  a)  log( ) log(1)  log(0.0005)

n  10.9658
log(2) log(2)

 n 11
By: Habtamu Garoma April 23, 2025
 Example
37

 Use Bisection method to find a root of the

equation x = cos (x) with absolute error <0.02
(assume the initial interval [0.5, 0.9])

Question 1: What is f (x) ?

Question 2: Are the assumptions satisfied ?
Question 3: How many iterations are needed ?
Question 4: How to compute the new estimate ?

By: Habtamu Garoma April 23, 2025

 Cont’d
38

By: Habtamu Garoma April 23, 2025

 Bisection Method
Initial Interval
39

f(a)=-0.3776 f(b) =0.2784

Error < 0.2
a =0.5 c= 0.7 b= 0.9

By: Habtamu Garoma April 23, 2025

 Bisection Method
40

-0.3776 -0.0648 0.2784

Error < 0.1
0.5 0.7 0.9

-0.0648 0.1033 0.2784

Error < 0.05
0.7 0.8 0.9

By: Habtamu Garoma April 23, 2025

 Bisection Method
41

-0.0648 0.0183 0.1033 Error < 0.025

0.7 0.75
0.8

-0.0648 -0.0235 0.0183 Error < .0125

0.70 0.725 0.75

By: Habtamu Garoma April 23, 2025

 Summary
42

 Initial interval containing the root:

[0.5,0.9]

 After 5 iterations:
 Interval containing the root: [0.725, 0.75]
 Best estimate of the root is 0.7375
 | Error | < 0.0125

By: Habtamu Garoma April 23, 2025

 Example
43

Find the root of:

f ( x)  x 3  3 x  1 in the interval : [0,1]

* f(x) is continuous
* f( 0 ) 1, f (1)  1  f (a ) f (b)  0
 Bisection method can be used to find the root

By: Habtamu Garoma April 23, 2025

 Example
44

c= (a+b)
(b-a)
Iteration a b f(c)
2
2
1 0 1 0.5 -0.375 0.5
2 0 0.5 0.25 0.266 0.25
3 0.25 0.5 .375 -7.23E-3 0.125
4 0.25 0.375 0.3125 9.30E-2 0.0625
5 0.3125 0.375 0.34375 9.37E-3 0.03125

By: Habtamu Garoma April 23, 2025

 Example 2: Find the positive root of

𝑥3 − 𝑥 − 1 correct to four decimal places by

using the bisection method.

Solution

Let 𝑥3 − 𝑥 − 1 we know that f is continuous

on R. Thus we can apply the bisection method.

Now f(1) = -1 < 0 and f(2) = 5 > 0

Hence the root of f(x) lies between 1 and 2

𝑥0 = = 1.5and f(1.5) = 0.875 > 0

1+2
2
Take

 the root lies between 1 and 1.5

45 By: Habtamu Garoma April 23, 2025

 Take 𝑋1 = = 1.25 and f(1.25) = -0.296875 < 0
1+1.5
2

 The root lies between 1.25 and 1.5

𝑋2 = = 1.375
1.25+1.5
2
 Take and

f(1.375) = 0.224609375 > 0

 The root lies between 1.3125 and 1.375

𝑋3 = = 1.34375 and
1.3125+1.375
2
Take

f(1.34375) = 0.082611083 > 0

 The root lies between 1.3125 and 1.34375

𝑋4 = = 1.328125
1.3125+1.34375
2

f(1.328125) = 0.014575958 > 0

 The root lies between 1.3125 and 1.328125

46 By: Habtamu Garoma April 23, 2025
 1.3125  1.34375
x55  1.328125
2
1.32421875  1.326171875
x99  1.325195313
2
1.32421875  1.325195313
x10
10
 1.324707032
2
1.324707032  1.325195313
x11
11
 1.324951173
2
1.324707032  1.24951173
x12
12
 1.324829103
2
1.324707032  1.324829103
x13
13
 1.324768068
2
1.32470732  1.32473755
x15
15
 1.32472235
2
1.324707032  1.324768068
x14
14
 1.32473755
2

April 23, 2025

47 By: Habtamu Garoma
 Example 2
48

 Consider finding the root of

x
f (x)  e ((3.2 sin(x)  0.5cos(x))

on the interval [3, 4], this time with, εabs =

0.001.

By: Habtamu Garoma April 23, 2025

 Table 1. Bisection method applied to

49
a b f(a) f(b) c = (a + b)/2 f(c) Update new b − a

3.0 4.0 0.047127 -0.038372 3.5 -0.019757 b=c 0.5

3.0 3.5 0.047127 -0.019757 3.25 0.0058479 a=c 0.25

3.25 3.5 0.0058479 -0.019757 3.375 -0.0086808 b=c 0.125

3.25 3.375 0.0058479 -0.0086808 3.3125 -0.0018773 b=c 0.0625

3.25 3.3125 0.0058479 -0.0018773 3.2812 0.0018739 a=c 0.0313

3.2812 3.3125 0.0018739 -0.0018773 3.2968 -0.000024791 b = c 0.0156

3.2812 3.2968 0.0018739 -0.000024791 3.289 0.00091736 a=c 0.0078

3.289 3.2968 0.00091736 -0.000024791 3.2929 0.00044352 a=c 0.0039

3.2929 3.2968 0.00044352 -0.000024791 3.2948 0.00021466 a=c 0.002

3.2948 3.2968 0.00021466 -0.000024791 3.2958 0.000094077 a = c 0.001

3.2958 3.2968 0.000094077 -0.000024791 3.2963 0.000034799 a = c 0.0005

By: Habtamu Garoma April 23, 2025

 Cont’d
50

 Thus, after the 11th iteration, we note

that the final interval, [3.2958, 3.2968]
has a width less than 0.001 and |
f(3.2968)| < 0.001 and therefore we
chose b = 3.2968 to be our
approximation of the root.

By: Habtamu Garoma April 23, 2025

 Bisection Method
51

Advantages
 Simple and easy to implement

 One function evaluation per iteration

 The size of the interval containing the zero is reduced

by 50% after each iteration

 The number of iterations can be determined a priori

 No knowledge of the derivative is needed

 The function does not have to be differentiable

Disadvantage
 Slow to converge

 Good intermediate approximations may be discarded

By: Habtamu Garoma April 23, 2025

 By: Habtamu Garoma 52

2. Regula Falsi
Method

April 23, 2025

 Regula Falsi Method
 Also known as the false-position method, or
linear interpolation method.
 Unlike the bisection method which divides the
search interval by half, regula falsi
interpolates f(xu) and f(xl) by a straight line
and the intersection of this line with the x-
axis is used as the new search position.
 The slope of the line connecting f(xu) and f(xl)
represents the "average slope" (i.e., the
value of f'(x)) of the points in [xl, xu ].
By: Habtamu
53 Garoma April 23, 2025
f x  Introduction

f xU 
f ( x ) 0 (1)
In the Bisection method
f ( x L ) * f ( xU )  0 (2)
Exact root

xL
x L  xU
O xr xU x
xr  (3)
f xL  2
1

54
Figure 1 False-Position Method
By: Habtamu Garoma April 23, 2025
 False-Position
Method

Based on two similar triangles, shown in Figure 1,

one gets:
f ( xL ) f ( xU )
 (4)
xr  x L xr  xU
The signs for both sides of Eq. (4) is consistent, since

f ( x L )  0; xr  x L  0
f ( xU )  0; xr  xU  0
By: Habtamu Garoma April 23, 2025
 From Eq. (4), one obtains
xr  xL  f xU  xr  xU  f xL 
xU f x L  x L f xU  xr  f x L  f xU 
The above equation can be solved to obtain the nex
predicted root xr, as

xU f x L   x L f xU 
xr  (5)
f x L   f xU 
By: Habtamu Garoma April 23, 2025
The above equation,

f xU x L  xU  (6)

xr xU 
f x L  f xU 
or
f x L 
xr  x L  (7)
 f xU   f x L 
 
 xU  x L 
By: Habtamu Garoma April 23, 2025
 Step-By-Step False-Position
Algorithms

1. Choose x L and xUas two guesses for the root such

that    
f x L f xU  0
xU f x L  x L f xU 
2. Estimate the root, xm 
f x L  f xU 
3. Now check the following
(a) If f x L  f xm   0, then the root lies between
xL
and x ; then x L  x L and xU  xm
m

(b) If f xL  f xm   0, then the root lies between xm

and xU; then xL  xm and xU  xU
By: Habtamu Garoma April 23, 2025
 (c) If f xL  f xm  0 , then the root x
ism .
Stop the algorithm if this is true.
Find the new estimate of the root
xU f x L  x L f xU 
xm 
f x L  f xU 
Find the absolute relative approximate error as
xmnew  xmold
a  new
100
xm Garoma April 23, 2025
By: Habtamu
 f ( xi )( xi  xi  1 )
xi 1  xi 
f ( xi )  f ( xi  1 )
where
xmnew
= estimated root from present iteration
xmold
= estimated root from previous iteration
3
5. say s 10 0.001. If a 
, then
s go to step 3,
else stop the algorithm.
es: The False-Position and Bisection algorithms are
e similar. The only difference is the formula used to
ulate the new estimate of the root xm shown
, in steps
#2 and 4! By: Habtamu Garoma April 23, 2025
 Example
61

Example 1: Solve for a positive root of

by the method of false position.
Solution:
Let f(1) = -2 < 0 and f(0) = 1> 0
Now let us find the root that lies between 0
and 1
Take a = 0 and b = 1

3
 1  1  1
f      4   1   0.296296296  0
 3  3  3

1
 the root lies between 0 and
3
By: Habtamu Garoma April 23, 2025
62

 Hence

 f(0.257142857) = -0.011568513 < 0

The root lies between 0 and 0.257142857

 0.257142857
= 0.254202116
 1.011568513

f 0.254202116   0.00038225166  0

 The root still lies between 0 and

By: 0.254202116
Habtamu Garoma April 23, 2025
 Cont’d
63

By: Habtamu Garoma April 23, 2025

False-position vs Bisection
 False position in general performs better
than bisection method.
 Exceptional Cases:
 (Usually) When the deviation of f'(x) is high
and the end points of the interval are
selected poorly.
 For example,
10
f ( x)  x  1
with xl 0, xu 1.3
By: Habtamu
64 Garoma April 23, 2025
Bisection Method (Converge quicker)
Iteration xl xu xr εa (%) εt (%)
1 0 1.3 0.65 35
2 0.65 1.3 0.975 33.3 25
3 0.975 1.3 1.1375 14.3 13.8
4 0.975 1.1375 1.05625 7.7 5.6
5 0.975 1.05625 1.015625 4.0 1.6

False-position Method
Iteration xl xu xr εa (%) εt (%)
1 0 1.3 0.09430 90.6
2 0.09430 1.3 0.18176 48.1 81.8
3 0.18176 1.3 0.26287 30.9 73.7
4 0.26287 1.3 0.33811 22.3 66.2
5 0.33811 1.3 0.40788
By: Habtamu
17.1
Garoma
59.2
April 23, 2025
65
 By: Habtamu Garoma 66

3. secant Method

April 23, 2025

 Secant Method –
Derivation
f(x ) Newton’s Method
f(xi ) (1)
xi 1 = xi -
f (xi )
f ( x i)
x f x 
i, i

Approximate the
derivative f ( xi )  f ( xi  1 ) (2)
f ( xi ) 
f ( x i-1 ) xi  xi  1

Substituting Equation
X
x i+ 2 x i+ 1 xi
(2) into Equation (1)
gives the Secant
method f ( xi )( xi  xi  1 )
Figure 1: Geometrical illustration of xi 1  xi 
the Newton-Raphson f ( xi )  f ( xi  1 )
method. By: Habtamu Garoma April 23, 2025
 Secant Method –
Derivation
The secant method can also be derived from geometry:
f(x)
The Geometric Similar Triangles
AB DC

f(xi) B AE DE
can be written as
f ( xi ) f ( xi  1 )

C
xi  xi 1 xi  1  xi 1
f(xi-1)

E D A
On rearranging, the secant
X
xi+1 xi-1 xi method is given as

f ( xi )( xi  xi  1 )
Figure 2: Geometrical xi 1  xi 
representation of the Secant f ( xi )  f ( xi  1 )
By: Habtamu Garoma April 23, 2025
method.
Algorithm for Secant
Method

By: Habtamu Garoma April 23, 2025

 Step 1

Calculate the next estimate of the root from two initial guesses
f ( xi )( xi  xi  1 )
xi 1  xi 
f ( xi )  f ( xi  1 )
Find the absolute relative approximate error

xi 1- xi
a =  100
xi 1

By: Habtamu Garoma April 23, 2025

Step 2

Find if the absolute relative approximate error is

greater than the prespecified relative error
tolerance.

If so, go back to step 1, else stop the algorithm.

Also check if the number of iterations has

exceeded the maximum number of iterations.

By: Habtamu Garoma April 23, 2025

Secant Method - Flowchart

x0 , x1 , i 1

( xi  xi  1 )
xi 1  xi  f ( xi ) ;
f ( xi )  f ( xi  1 )
i i  1

NO Yes
xi 1  xi   Stop

By: Habtamu Garoma April 23, 2025

 Example

Find the roots of : 50

40
5 3
f ( x)  x  x  3 30

20

Initial points 10

x0  1 and x1  1.1 -10

-20

-30

-40

with error  0.001 -2 -1.5 -1 -0.5 0 0.5 1 1.5 2

By: Habtamu Garoma April 23, 2025

Example
x(i) f(x(i)) x(i+1) |x(i+1)-x(i)|

-1.0000 1.0000 -1.1000 0.1000

-1.1000 0.0585 -1.1062 0. 0062

-1.1062 0.0102 -1.1052 0.0009

-1.1052 0.0001 -1.1052 0.0000

By: Habtamu Garoma April 23, 2025

Example

Use Secant method to find the root of :

6
f ( x)  x  x  1
Two initial points x0 1 and x1 1.5

( xi  xi  1 )
xi 1  xi  f ( xi )
f ( xi )  f ( xi  1 )
By: Habtamu Garoma April 23, 2025
 Solution
76

_______________________________
k xk f(xk)
_______________________________
0 1.0000 -1.0000
1 1.5000 8.8906
2 1.0506 -0.7062
3 1.0836 -0.4645
4 1.1472 0.1321
5 1.1331 -0.0165
6 1.1347 -0.0005

By: Habtamu Garoma April 23, 2025

 Example
77

By: Habtamu Garoma April 23, 2025

 Secant Method – Example
Find root of f(x) = e-x - x = 0 with initial estimate of
x0 = 0 and x1 = 1. (Answer: α= 0.56714329)
f ( xi )( xi  1  xi )
xi 1  xi 
f ( xi  1 )  f ( xi )

i xi-1 xi f(xi-1) f(xi) xi+1 εt

0 0 1 1.00000 -0.63212 0.61270 8.0 %

1 1 0.61270 -0.63212 -0.07081 0.56384 0.58 %

2 0.61270 0.56384 -0.07081 0.00518 0.56717 0.0048 %

By: Habtamu Garoma

78 April 23, 2025
 Convergence Analysis
79

 The rate of convergence of the Secant

method is super linear:
xi 1  r

C ,  1.62
xi  r
r : root xi : estimate of the root at the i th iteration.

 It is better than Bisection method but

not as good as Newton’s method.
By: Habtamu Garoma April 23, 2025
Fixed Point
Iteration
The equation f(x) = 0, where f(x) = x3  7x + 3, may be re-
arranged to give x = (x3 + 3)/7.
Intersection of the graphs of y = x and y = (x3 + 3)/7
represent roots of the original equation x3  7x + 3 = 0.
4 y = (x3 + 3)/7
3

0
y

-5 -4 -3 -2 -1 0 1 2 3 4 5
-1
y=x
-2

-3

-4
x

Slide 80 By: Habtamu

April 23, 2025Garoma
 Fixed Point
Iteration
The equation f(x) = 0, where f(x) = x 3
 7x + 3, may be re-
81
arranged to give x = (x3 + 3)/7.
Intersection of the graphs of y = x and y = (x3 + 3)/7
represent roots of the original equation x3  7x + 3 = 0.

4
y = (x3 + 3)/7
3

0
y

-5 -4 -3 -2 -1 0 1 2 3 4 5
-1

y=x -2

-3

-4
x

By: Habtamu
April 23, 2025Garoma
Fixed Point Iteration
The rearrangement x = (x3 + 3)/7 leads to the iteration
3
x 3
xn 1  n , n  0, 1, 2, 3, ...
7
To find the middle root , let initial approximation x0 = 2.
3
x0  3 23  3
x1    1.57143
7 7
3
x1  3 1.571433  3
x2    0.98292
7 7
3
x2  3 0.982923  3
x3    0.56423
7 7
3
x3  3 0.564233  3 etc
x4    0.45423
7 7 .

The iteration slowly converges to give = 0.441 (to 3 s.f.)

By: Habtamu
April 23, 2025Garoma
Fixed Point Iteration
The rearrangement x = (x3 + 3)/7 leads to the iteration
3
x 3
xn 1  n , n  0, 1, 2, 3, ...
7
For x0 = 2 the iteration will converge on the middle root ,
since g’() < 1. 2

n xn
0 2 1.5

1 1.57143 y=x
2 0.98292 y = (x3 + 3)/7
y 1
3 0.56423
4 0.45423
5 0.44196 0.5

6 0.4409
7 0.44082 0
8 0.44081 0 0.5
 x3
1
x
1.5
x1
2
x0
x2

 = 0.441 (to 3 s.f.) By: Habtamu

April 23, 2025Garoma
 Fixed Point Iteration
breakdown
3
x 3
The rearrangement xn 1  n , n  0, 1, 2, 3, leads
... to the
iteration. 7
For x0 = 3 the iteration will diverge from the upper root .
10
n xn
8
0 3
1 4.28571 y
6

2 11.6739 4

3 227.702 2

4 1686559  x0 x1
0
5 6.9E+17 0 2 4 6 8 10
x

The iteration diverges because g’() > 1.

By: Habtamu
April 23, 2025Garoma
85 By: Habtamu Garoma April 23, 2025
 Newton-Raphson Method
(Also known as Newton’s Method)
86

Given an initial guess of the root x0,

Newton-Raphson method uses information
about the function and its derivative at
that point to find a better guess of the
root.

Assumptions:
 f(x) is continuous and the first derivative is
known
 An initial guess x0 such that f’(x0)≠0 is given

By: Habtamu Garoma April 23, 2025

 Newton Raphson Method
- Graphical Depiction -
87

 If the initial guess

at the root is xi,
then a tangent to
the function of xi
that is f’(xi) is
extrapolated
down to the x-
axis to provide
an estimate of
the root at xi+1.
By: Habtamu Garoma April 23, 2025
NEWTON-RAPHSON
ITERATION
The Newton Raphson method is based on the iteration:

f( xn )
xn 1  xn  , n  0, 1, 2, 3, ...

f ( xn )

with initial approximation x0 .

20
Gradient of tangent

15
f ( x0 )
f ' ( x0 ) 
10 x0  x1
f(x0)
5
f ( x0 )
 x1  x0 
0 x1 x0
f ( x0 )
2 3

-5

Slide 88 By: Habtamu

April 23, 2025Garoma
 Derivation of Newton’s
89
Method

By: Habtamu Garoma April 23, 2025

 Newton’s Method

Finding a root for: f  x   1 x 2  3

2

We will use Newton’s

Method to find the
root between 2 and 3.

90 By: Habtamu Garoma April 23, 2025


 1 2
1.5 f x   x  3
2
f  x   x

1.5
Guess: 3
1 2
f 3  3  3 1.5
z
2

(not drawn to scale)

mtangent  f 3 3

1.5 1.5
1.5 3 z
3 2.5 z 3
3 (new guess)
91 By: Habtamu Garoma April 23, 2025

 1 2
1.5 f x   x  3
2
f  x   x

Guess:2.5
1
f 2.5   2.5   3 .125
2

z 2
mtangent  f 2.5  2.5

.125
.125 z
2.5  2.45 2.5
2.5 (new guess)
92 By: Habtamu Garoma April 23, 2025

 1 2
1.5 f x   x  3
2
f  x   x

Guess: 2.45

f 2.45  .00125
z

mtangent  f 2.45  2.45

.00125
z
2.45
.00125
93 2.45  2.44948979592 (newApril
By: Habtamu Garoma guess)
23, 2025

2.45
 Guess: 2.44948979592

f 2.44948979592  .00000013016

Amazingly close to zero!

This is Newton’s Method of finding roots. It is an example

of an algorithm (a specific set of computational steps.)

It is also called the Newton-Raphson method

This is a recursive algorithm because a set of steps are

repeated with the previous answer put in the next
repetition. Each repetition is called is called an iteration.
94 By: Habtamu Garoma April 23, 2025

 3
Find where y  x  x crosses y 1 .
1 x3  x 0 x3  x  1 f  x  x3  x  1 f  x  3x 2  1
f  xn 
xn 1  xn 
n xn f  xn  f  xn  f  xn 
1
0 1 1 2 1 1.5
2
.875
1 1.5 .875 5.75 1.5  1.3478261
5.75

2 1.3478261 .1006822 4.4499055 1.3252004

1.3252004 
3
 1.3252004 1.0020584 1
95 By: Habtamu Garoma April 23, 2025

 Example
96

Find a zero of the function f(x)  x 3  2 x 2  x  3 , x0 4

f ' (x) 3 x 2  4 x  1
f ( x0 ) 33
Iteration 1 : x1  x0  4  3
f ' ( x0 ) 33
f ( x1 ) 9
Iteration 2 : x2  x1  3  2.4375
f ' ( x1 ) 16
f ( x2 ) 2.0369
Iteration 3 : x3  x2  2.4375  2.2130
f ' ( x2 ) 9.0742

By: Habtamu Garoma April 23, 2025

 Example
97

k (Iteration) xk f(xk) f’(xk) xk+1 |xk+1 –xk|

0 4 33 33 3 1

1 3 9 16 2.4375 0.5625

2 2.4375 2.0369 9.0742 2.2130 0.2245

3 2.2130 0.2564 6.8404 2.1756 0.0384

4 2.1756 0.0065 6.4969 2.1746 0.0010

By: Habtamu Garoma April 23, 2025

 Example
98

Use Newton' s Method to find a root of :

f ( x)  x 3  x  1
Use the initial point : x0 1.
Stop after three iterations, or
if xk 1  xk  0.001, or
if f ( xk )  0.0001.

By: Habtamu Garoma April 23, 2025

 Five Iterations of the
99
Solution
 k xk f(xk) f’(xk) ERROR
 ______________________________________
 0 1.0000 -1.0000 2.0000
 1 1.5000 0.8750 5.7500 0.1522
 2 1.3478 0.1007 4.4499 0.0226
 3 1.3252 0.0021 4.2685 0.0005
 4 1.3247 0.0000 4.2646 0.0000
 5 1.3247 0.0000 4.2646 0.0000

By: Habtamu Garoma April 23, 2025

 Example
100

Use Newton' s Method to find a root of :

f ( x) e  x  x
Use the initial point : x0 1.
Stop after three iterations, or
if xk 1  xk  0.001, or
if f ( xk )  0.0001.

By: Habtamu Garoma April 23, 2025

 Example
101

Use Newton' s Method to find a root of :

f ( x) e  x  x, f ' ( x)  e  x  1

f ( xk )
xk f ( xk ) f ' ( xk )
f ' ( xk )
1.0000 - 0.6321 - 1.3679 0.4621
0.5379 0.0461 - 1.5840 - 0.0291
0.5670 0.0002 - 1.5672 - 0.0002
0.5671 0.0000 - 1.5671 - 0.0000

By: Habtamu Garoma April 23, 2025

 Example
102

Estimates of the root of: x-cos(x)=0.

0.60000000000000 Initial guess

0.74401731944598 1 correct digit

0.73909047688624 4 correct digits
0.73908513322147 10 correct digits
0.73908513321516 14 correct digits

By: Habtamu Garoma April 23, 2025

 Example
103

In estimating the root of: x-cos(x)=0, to

get more than 13 correct digits:

 4 iterations of Newton (x0=0.8)

 43 iterations of Bisection method (initial
interval [0.6, 0.8])
 5 iterations of Secant method
( x0=0.6, x1=0.8)

By: Habtamu Garoma April 23, 2025

 Convergence Analysis
104

Theorem :
Let f(x), f ' (x) and f ' ' (x) be continuous at x r
where f(r) 0. If f ' (r) 0 then there exists   0
xk 1-r
such that x0 -r   2
C
xk -r
max f ' ' ( x)
1 x0 -r 
C
2 min f ' ( x)
x0 -r 

By: Habtamu Garoma April 23, 2025

 Convergence Analysis
Remarks
105

When the guess is close enough to a simple

root of the function then Newton’s method is
guaranteed to converge quadratic ally.

Quadratic convergence means that the number

of correct digits is nearly doubled at each
iteration.

By: Habtamu Garoma April 23, 2025

 Problems with Newton’s
106
Method
• If the initial guess of the root is far from
the root the method may not converge.
• Newton’s method converges linearly near
multiple zeros { f(r) = f’(r) =0 }. In such a
case, modified algorithms can be used to
regain the quadratic convergence.

By: Habtamu Garoma April 23, 2025

 Summary
107

Method Advantage Drawback

Bisection - Easy, Reliable, Convergent - Slow
- One function evaluation per - Needs an interval [a,b]
iteration containing the root, i.e.,
- No knowledge of derivative is f(a)f(b)<0
needed
Newton - Fast (if near the root) - May diverge
- Two function evaluations per - Needs derivative and an
iteration initial guess x0 such that
f’(x0) is nonzero

Secant - Fast (slower than Newton) - May diverge

- One function evaluation per - Needs two initial points
iteration guess x0, x1 such that
- No knowledge of derivative is f(x0)- f(x1) is nonzero
needed

By: Habtamu Garoma April 23, 2025