Root Finding

Methods
Engineering Mathematics and Modelling II
Learning Outcomes
At the end of this lesson, students should be able to:-
● Apply graphical, closed, and open methods to find roots
Outline

■ What are roots?

■ Graphical method

■ Closed method

■ Open method
 What are roots?
You have previously learnt how to solve a quadratic equation.
The values calculated which satisfy the equation (using the
formula below) are called “roots”.

The roots represent the values of x that

make the function 𝑓(𝑥) (LHS of equation)
equal to zero (RHS of equation)

This is called an exact or analytical

solution.

Other equations must be solved using

approximation methods
 Roots of
Equations:
Methods
 01

Graphical Method
Plot – Guess – Refine
 Graphical Method
The basic strategy:-

● Plot the function – the plot provides an initial

guess, and an indication of potential problems

● Select an initial guess

● Iteratively refine the initial geuss with a root-

finding algorithm
 Graphical Method
Solve the following equation
using graphical method

9.8 68.1 −
𝑐
10
𝑓 𝑐 = 1−𝑒 68.1 − 40
𝑐
Graphical Method
 02

Closed Method
Bracketing – Bisection/False Position
 Closed Method – Bracketing
● A root is bracketed on the interval [𝒂, 𝒃] if 𝑓(𝑎) and
𝑓(𝑏) have OPPOSITE sign
● A sign change occurs for singularities as well as roots
 Closed Method – Bracketing
● Bracketing is used to make initial guesses at the roots,
not to accurately estimate the values of the roots.
 Closed Method – Bracketing
Some General Rules
If 𝑓(𝑎) and 𝑓 𝑏 have the same sign, then there If 𝑓(𝑎) and 𝑓 𝑏 have opposite signs, then there
are an even number of roots or no roots in the are an odd number of roots in the interval
interval
 Closed Method – Bracketing
Step 1: Choose lower 𝑥𝑙 and upper 𝑥𝑢 guesses for the root such that the function
changes sign over the interval. This can be checked by ensuring that 𝑓 𝑥𝑙 𝑓 𝑥𝑢 < 0
Step 2: An estimate of the root 𝑥𝑟 is determined (inside the bracket)
Step 3: Make the following evaluations to determine in which sub-interval the root lies:-
a) If 𝑓(𝑥𝑙 )𝑓(𝑥𝑟 ) < 0, the root lies in the lower sub-interval. Therefore, set 𝑥𝑢 = 𝑥𝑟
and return to step 2.
b) If 𝑓 𝑥𝑙 𝑓 𝑥𝑟 > 0, the root lies in the upper sub-interval. Therefore, set 𝑥𝑙 = 𝑥𝑟
and return to step 2.
c) If 𝑓 𝑥𝑙 𝑓 𝑥𝑟 = 0, the root equals 𝑥𝑟 ; terminate the computation.
 Closed Method – Bracketing
Step 1: Choose lower 𝑥𝑙 and upper 𝑥𝑢 guesses for the root such that the function
changes sign over the interval. This can be checked by ensuring that 𝑓 𝑥𝑙 𝑓 𝑥𝑢 < 0
 Closed Method – Bisection
𝑎1 + 𝑏1
Step 2: An estimate of the root 𝑥𝑟 is determined by:- 𝑥𝑖,1 =
2
 Closed Method – Bisection
a) If 𝑓(𝑥𝑙 )𝑓(𝑥𝑟 ) < 0, the root lies in
the lower sub-interval. Therefore,
set 𝑥𝑢 = 𝑥𝑟 and return to step 2.
b) If 𝑓 𝑥𝑙 𝑓 𝑥𝑟 > 0, the root lies in
the upper sub-interval. Therefore,
set 𝑥𝑙 = 𝑥𝑟 and return to step 2.
c) If 𝑓 𝑥𝑙 𝑓 𝑥𝑟 = 0, the root equals
𝑥𝑟 ; terminate the computation.
 Closed Method – Bisection
a) If 𝑓(𝑥𝑙 )𝑓(𝑥𝑟 ) < 0, the root lies in
the lower sub-interval. Therefore,
set 𝑥𝑢 = 𝑥𝑟 and return to step 2.
b) If 𝑓 𝑥𝑙 𝑓 𝑥𝑟 > 0, the root lies in
the upper sub-interval. Therefore,
set 𝑥𝑙 = 𝑥𝑟 and return to step 2.
c) If 𝑓 𝑥𝑙 𝑓 𝑥𝑟 = 0, the root equals
𝑥𝑟 ; terminate the computation.
 Closed Method – Bisection Example
Use bisection method to find the root(s) of the following equation:-

9.8 68.1 −
𝑐
10
𝑓 𝑐 = 1−𝑒 68.1 − 40
𝑐

The first step is to guess two values of the unknown 𝑐 that gives values of 𝑓(𝑐) with
different signs.
Let us start with the values of 14 and 15
 Closed Method – Bisection Example
9.8 68.1 𝑐 9.8 68.1 14
Step 1: 𝑓 𝑐 = 1− 𝑒
− 68.1 10
− 40 𝑓 14 = 1−𝑒
− 68.1 10
− 40 = 1.5687
𝑐 14
9.8 68.1 15
− 68.1 10
𝑓 15 = 1−𝑒 − 40 = −0.4248
15

Step 2: Therefore the initial estimate root,

𝑥𝑟 lies at the midpoint of the interval

14 + 15
Iteration 0 𝑥𝑟 = = 14.5
2
 Closed Method – Bisection Example
Step 3: Based on the 3 values [14, 14.5, 15] b) If 𝑓 𝑥𝑙 𝑓 𝑥𝑟 > 0, the root lies in
the upper sub-interval. Therefore,
always test these two values to determine set 𝑥𝑙 = 𝑥𝑟 and return to step 2.
which condition from step 3 applies
Therefore, the root lies
𝑓 14 = 1.5687
between [14.5, 15]
𝑓 14.5 = 0.5523
14.5 + 15
𝑓 14 𝑓 14.5 > 0 Iteration 1 𝑥𝑟 = = 14.75
2
condition (b) applies
continue in this manner until convergence
When to terminate the algorithm”?

Usually we do not have information Relative error is the criterion used

about the location of the root. for the bisection method; it is
defined as:
Hence, we need a criterion that is 𝑥𝑟new − 𝑥𝑟old
not dependent on knowledge of the err =
𝑥𝑟new
root location!
Where 𝑥𝑟new and 𝑥𝑟old are the roots
for the present and previous
iterations.
 Closed Method – False Position
The False Position Method (FPM) is a modification of the bisection method.
This method considers the distance of the limit from the root.

𝑓 𝑥𝑢 − 0 𝑓 𝑥𝐿 − 𝑓(𝑥𝑢 )
From the figure: =
𝑥𝑢 − 𝑥𝑟 𝑥𝐿 − 𝑥𝑢

𝑓(𝑥𝑢 )(𝑥𝐿 −𝑥𝑢 )

Solving for 𝑥𝑟 = 𝑥𝑢 −
𝑓 𝑥𝐿 −𝑓(𝑥𝑢 )

FPM also using the bracketing algorithm

(identical to bisection except for step 2)
Closed Method – False Position
Bisection method False position method
 Exercise
Given the function 𝑓(𝑥) = 2𝑥 3 − 3, apply the
methods below to find the root of the function. Use
3 iterations each. Choose initial guesses of [0, 2].
i. Bisection method
ii. False position method
 03

Open Method
Fixed Point Iteration, Newton Raphson, Secant
Open Method – Fixed Point Iteration
A very simple (basic) method

Only works when the iteration function is convergent

𝑥 = 𝑔(𝑥)
Predict new value of
𝑥𝑖+1 = 𝑔(𝑥𝑖 ) 𝑥 as a function of old
(previous) value of 𝑥
Open Method – Fixed Point Iteration
Method
Rearrange the function 𝑓(𝑥) = 0 𝑥 2 − 2𝑥 + 3 = 0
so that 𝑥 is on the left-hand side of
the equation:
𝑥 = 𝑔(𝑥) 𝑥2 + 3
𝑥=
This method uses ONE initial 2
guess instead of a range.
Estimator is then: 𝑥𝑖2 + 3
𝑥𝑖+1 = 𝑔(𝑥𝑖 ) 𝑥𝑖+1 =
2
Open Method – Fixed Point Iteration
Iter Root
Example 1 -------------------------
0 0
𝑓(𝑥) = 𝑒 −𝑥 − 𝑥 1.0000 1.0000
2.0000 0.3679
We want to find the root, so set 3.0000 0.6922
4.0000 0.5005
the function to be equal to 0 5.0000 0.6062
6.0000 0.5454
0 = 𝑒 −𝑥 − 𝑥 7.0000 0.5796
8.0000 0.5601
Rearrange the equation 9.0000 0.5711
10.0000 0.5649
𝑥𝑖+1 = 𝑒 −𝑥 11.0000 0.5684
12.0000 0.5664
Initial guess 𝑥 = 0 13.0000 0.5676
14.0000 0.5669
15.0000 0.5673
16.0000 0.5671
17.0000 0.5672
18.0000 0.5671
19.0000 0.5672
Open Method – Fixed Point Iteration
Example 2 𝑓 𝑥 = 𝑥 − 𝑥 1/3 − 2
1 3
To solve 𝑥 − 𝑥 − 2 = 0, rewrite as 𝑥new = 𝑥old + 2 or 𝑥new = 𝑥old − 2
1/3
3
 Open Method – Newton-Raphson
Easiest explained graphically
′
𝑑𝑦 𝑓 𝑥𝑖 − 0
slope 𝑓 𝑥𝑖 = =
𝑑𝑥 𝑥𝑖 − 𝑥𝑖+1

𝑓 𝑥𝑖
𝑥𝑖+1 = 𝑥𝑖 −
𝑓′(𝑥𝑖 )
Newton-Raphson Method
 Open Method – Newton-Raphson
Example 1
𝑓(𝑥) = 𝑒 −𝑥 − 𝑥
Initial guess 𝑥 = 0 Iter Root
-------------------------
𝑓 ′ 𝑥𝑖 = −𝑒 −𝑥 − 1 0 0
1.0000 0.5000
Using Newton-Raphson formula 2.0000 0.5663
3.0000 0.5671
gives us:- 4.0000 0.5671

𝑒 −𝑥𝑖 − 𝑥𝑖
𝑥𝑖+1 = 𝑥𝑖 −
−𝑒 −𝑥𝑖 − 1
 Open Method – Newton-Raphson
Disadvantages

The differential term 𝑓′(𝑥) in the

Newton-Raphson formula needs
more mathematical knowledge
(hence more difficult) to calculate
than 𝑓(𝑥)
𝑓(𝑥𝑖 )
Since 𝑥𝑖+1 = 𝑥𝑖 − , the new
𝑓′(𝑥𝑖 )
guess will be (infinitely) far from
the old guess whenever 𝑓′(𝑥𝑖 ) ≈ 0
Open Method – Secant
How to find the slope of the red line?

′
𝑑𝑦 𝑓 𝑥𝑖 − 𝑓(𝑥𝑖−1 )
𝑓 𝑥𝑖 = ≈
𝑑𝑥 𝑥𝑖 − 𝑥𝑖−1

Newton-Raphson Method
𝑓 𝑥𝑖 Substitute
𝑥𝑖+1 = 𝑥𝑖 −
𝑓′(𝑥𝑖 )
Open Method – Secant
How to find the slope of the red line?

′
𝑑𝑦 𝑓 𝑥𝑖 − 𝑓(𝑥𝑖−1 )
𝑓 𝑥𝑖 = ≈
𝑑𝑥 𝑥𝑖 − 𝑥𝑖−1
This is called backward
finite difference
Secant Method
𝑥𝑖 − 𝑥𝑖−1
𝑥𝑖+1 = 𝑥𝑖 − 𝑓(𝑥𝑖 )
𝑓 𝑥𝑖 − 𝑓(𝑥𝑖−1 )
 Open Method – Secant
How it works
 Open Method – Secant
Example 1
𝑓(𝑥) = 𝑒 −𝑥 − 𝑥 with initial values 𝑥0 = 1 and 𝑥−1 = 0
First iteration Second iteration
𝑓 𝑥−1 = 𝑓 0 = 𝑒 0 − 0 = 1 𝑓 𝑥0 = 𝑓 1 = 𝑒 −1 − 1 = −0.63212
𝑓 𝑥0 = 𝑓 1 = 𝑒 −1 − 1 = −0.63212 𝑓 𝑥1 = 𝑓 0.6127 = 𝑒 −0.6127 − 0.6127 = −0.07081
𝑥𝑖 − 𝑥𝑖−1 0.6127 − 1
𝑥𝑖+1 = 𝑥𝑖 − 𝑓(𝑥𝑖 ) 𝑥2 = 0.6127 − −0.07081
𝑓 𝑥𝑖 − 𝑓(𝑥𝑖−1 ) −0.07081 − (−0.63212)
= 0.56384
1−0
𝑥1 = 0 − −0.63212 = 0.6127
−0.63212 − 1
 Open Method – Secant
Example 1
𝑓(𝑥) = 𝑒 −𝑥 − 𝑥 with initial values 𝑥0 = 1 and 𝑥−1 = 0
Third iteration
Iter Root
𝑓 𝑥1 = 𝑓 0.6127 = 𝑒 −0.6127 − 0.6127 = −0.07081 ------------------------
𝑓 𝑥2 = 𝑓 0.56384 = 𝑒 −0.56384 − 0.56384 = 0.00518 -1.0000 0
0 1.0000
0.56384 − 0.5126 1.0000 0.6127
𝑥3 = 0.56384 − 0.00518 2.0000 0.5638
0.00518 − (−0.07081) 3.0000 0.5672
= 0.56717 4.0000 0.5671
Real World Example
Real World Example
3 3 −ℎ
30 = 𝜋ℎ2
3

9−ℎ
0= 𝜋ℎ2 − 30
3
9−ℎ
𝑓(ℎ) = 𝜋ℎ2 − 30
3

𝑓(𝑥𝑢 )(𝑥𝐿 − 𝑥𝑢 )
𝑥𝑟 = 𝑥𝑢 −
𝑓 𝑥𝐿 − 𝑓(𝑥𝑢 )
False Position Method
Real World Example
9−ℎ
𝑓(ℎ) = 𝜋ℎ2 − 30
3

𝑓(𝑥𝑢 )(𝑥𝐿 − 𝑥𝑢 )
𝑥𝑟 = 𝑥𝑢 −
𝑓 𝑥𝐿 − 𝑓(𝑥𝑢 )

Iter Root
-----------------------
1.0000 1.5915
2.0000 1.9866
3.0000 2.0239
4.0000 2.0267
5.0000 2.0269
6.0000 2.0269