Numerical Methods (Engr-280)

Roots – Finding zeros

Bracketing methods
Open Methods
Dakar American University of Science and Technology (DAUST)

Dr. Amadou Toure

06 April, 2023

Dr. Amadou Toure Numerical Methods (Engr-280) Roots – Finding zeros 06 April, 2023 1 / 15
Motivation
The velocity of a bungee jumper: 𝑣(𝑡) = √ 𝑚𝑔
𝐶 tanh (
√ 𝑔𝐶
𝑚 𝑡),
𝑑
𝑑

parameters: 𝑣 = downward velocity, 𝑡 = time, 𝑔 = gravity,

𝐶𝑑 = drag coefficient, 𝑚 = jumper’s mass.
𝑣 is expressed explicitly as a function of the model parameters
Medical studies have established that chances of sustaining vertebrae injury
increase significantly if velocity exceeds 36𝑚/𝑠 after 4𝑠 of free fall.
You want to determine the mass at which this criterion is exceeded.

Solution:

Cannot manipulate equation to explicitly solve for m (m is implicit)

Subtract 𝑣(𝑡) from both sides: 𝑓(𝑚) = √ 𝑚𝑔

𝐶 tanh (
√ 𝑔𝐶
𝑚 𝑡) − 𝑣(𝑡)
𝑑
𝑑

Now the answer is the value of 𝑚 that makes the function equal to zero.
Hence, we call this a “roots” problem.
Objective: how to use computer as tool to solve these problems
Dr. Amadou Toure Numerical Methods (Engr-280) Roots – Finding zeros 06 April, 2023 2 / 15
Graphical Method
𝑓(𝑚) = √ 𝑚𝑔
𝐶 tanh (
√ 𝑔𝐶
𝑚 𝑡) − 𝑣(𝑡)
𝑑
𝑑

Determine the mass of jumper with 𝐶𝑑 = 0.25𝑘𝑔/𝑚 to have 𝑣(𝑡) = 36𝑚/𝑠 after
𝑡 = 4𝑠 of free fall.
>> cd = 0.25; g = 9.81; v = 36; t = 4;
>> mp = linspace(50,200);
>> fp = sqrt(g*mp/cd).*tanh(sqrt(g*cd./mp)*t)− v;
>> plot(mp,fp),grid

root: where function crosses

Root the x-axis
a rough estimate; ≈ 145𝑘𝑔
The validity can be checked by
substituting into the equation:
√ 145
𝐶𝑑 tanh (
√ 𝑔𝐶
145 𝑡) − 𝑣 =
𝑑

0.0456;
can be used as starting guess
Dr. Amadou Toure Numerical Methods (Engr-280) Roots – Finding zeros 06 April, 2023 3 / 15
Root Finding Methods

Two major classes of methods, distinguished by the type of initial guess.

Bracketing methods - based on two initial guesses that “bracket” the
root—that is, are on either side of the root.
▶ For well-posed problems, the bracketing methods always work but
converge slowly (i.e., more iterations to home in on the answer).
Open methods - can involve one or more initial guesses, but there is
no need for them to bracket the root.
▶ the open methods do not always work (i.e., they can diverge), but
when they do they usually converge quicker.
In both cases, initial guesses are required.
▶ These may naturally arise from the physical context you are analyzing.
▶ In other cases, good initial guesses may not be obvious; then
automated approaches to obtain guesses would be useful.
one such approach: the incremental search.

Dr. Amadou Toure Numerical Methods (Engr-280) Roots – Finding zeros 06 April, 2023 4 / 15
Bracketing Methods

Bracketing methods
Find an interval, a “bracket”, that contains a zero of the function (a
root).
Repeatedly choose new points inside the bracket, and shrink the
bracket for every new point.

The bracket
We suppose that the function is continuous. Under that condition, it is
sufficient that the function has different signs at the endpoints of the
bracket. (Intermediate value theorem)

Dr. Amadou Toure Numerical Methods (Engr-280) Roots – Finding zeros 06 April, 2023 5 / 15
 General ways a root may occur in [𝑥𝑙 , 𝑥𝑢 ]
f(x)
f(x) f(x)

𝑥𝑙 𝑥𝑙 𝑥𝑢
𝑥𝑢 x 𝑥𝑙 𝑥𝑢 x x

f(x) f(x)

𝑥𝑢 𝑥𝑙 𝑥𝑢 x
𝑥𝑙 x

if 𝑓(𝑥𝑙 ) & 𝑓(𝑥𝑢 ) ≠ signs if 𝑓(𝑥𝑙 ) & 𝑓(𝑥𝑢 ) same sign,

odd number of roots either no roots or even number of roots
There are exceptions that require special strategies
Multiple roots (function is tangential to the x axis)
Discontinuous functions
Dr. Amadou Toure Numerical Methods (Engr-280) Roots – Finding zeros 06 April, 2023 6 / 15
Bracketing Methods: Bissection
𝑓(𝑚)

𝑚
Root

𝑥𝑙 𝑥𝑟 𝑥𝑢
Fisrt iteration
𝑥𝑙 𝑥𝑟 𝑥𝑢
Second iteration
𝑥𝑙 𝑥𝑟 𝑥𝑢
Third iteration
𝑥𝑙 𝑥𝑟 𝑥𝑢
Fourth iteration

Dr. Amadou Toure Numerical Methods (Engr-280) Roots – Finding zeros 06 April, 2023 7 / 15
Finding zeros of continuous functions with bisection
We want to find the zero of the continuous function 𝑓(𝑥)
1 Start with interval [𝑥 , 𝑥 ] (bracket) where 𝑓(𝑥) has different signs at
𝑙 𝑢
endpoints - there is a zero in the interval
𝑥𝑢 + 𝑥𝑙 𝑥 − 𝑥𝑙
2 Take midpoint 𝑥 =
𝑟 = 𝑥𝑢 − 𝑢 , check sign of 𝑓(𝑥𝑟 )
2 2
3 Move either 𝑥 or 𝑥
𝑙 𝑢 to 𝑥𝑟 to keep ≠ signs at endpoints
▶ 𝑓(𝑥𝑙 )𝑓(𝑥𝑟 ) < 0 → 𝑥𝑢 = 𝑥𝑟
▶ 𝑓(𝑥𝑟 )𝑓(𝑥𝑢 ) < 0 → 𝑥𝑙 = 𝑥𝑟
4 Repeat 2. and 3. until satisfied with the precision(𝜖𝑎 ) in [𝑥𝑙 , 𝑥𝑢 ].

Bisection is certain to give a good result, though it converge slowly

1
The absolute error between steps is halved: 𝐸𝑛+1 = 𝐸𝑛
2
𝑥𝑛𝑒𝑤 − 𝑥𝑜𝑙𝑑
the absolute relative approximate error 𝜖𝑎 = ∣ 𝑟 𝑛𝑒𝑤 𝑟 ∣ × 100
𝑥𝑟
|𝜖𝑎 | < 𝜖𝑠 as stopping criterion (𝜖𝑠 is pre-specified error tolerance)

Dr. Amadou Toure Numerical Methods (Engr-280) Roots – Finding zeros 06 April, 2023 8 / 15
Bracketing Methods: False-Position
𝑓(𝑥)
Based on two similar triangles:
𝑓(𝑥) → 𝑓(𝑥𝑙 ) 𝑓(𝑥𝑢 )
=
𝑓(𝑥𝑢 ) 𝑥𝑟 − 𝑥𝑙 𝑥𝑟 − 𝑥𝑢

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

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

𝑓(𝑥𝑢 ){𝑥𝑙 − 𝑥𝑢 }
or 𝑥𝑟 = 𝑥𝑢 −
𝑓(𝑥𝑙 ) − 𝑓(𝑥𝑢 )
𝑓(𝑥𝑙 )
or 𝑥𝑟 = 𝑥𝑙 −
𝑥𝑟 𝑓(𝑥𝑢 ) − 𝑓(𝑥𝑙 )
𝑥𝑢 − 𝑥𝑙
𝑥𝑙
𝑥𝑢 𝑥

𝑓(𝑥𝑙 )

Dr. Amadou Toure Numerical Methods (Engr-280) Roots – Finding zeros 06 April, 2023 9 / 15
Finding zeros of continuous functions with false position
We want to find the zero of the continuous function 𝑓(𝑥)
1 Start with interval [𝑥 , 𝑥 ] (bracket) where 𝑓(𝑥) has different signs at
𝑙 𝑢
endpoints - there is a zero in the interval
2 Make a line that connect 𝑓(𝑥 ) to 𝑓(𝑥 ). 𝑥 is the point where that
𝑙 𝑢 𝑟
𝑥𝑢 𝑓(𝑥𝑙 ) − 𝑥𝑙 𝑓(𝑥𝑢 )
line crosses the x-axis, i.e. 𝑥𝑟 =
𝑓(𝑥𝑙 ) − 𝑓(𝑥𝑢 )
3 Move either 𝑥 or 𝑥 to 𝑥 to keep ≠ signs at endpoints
𝑙 𝑢 𝑟
4 Repeat 2. and 3. until satisfied with the precision in [𝑥 , 𝑥 ].
𝑙 𝑢

If the distance to the root is “related to” the size of 𝑓(𝑥), the method
is better than bissection.

Dr. Amadou Toure Numerical Methods (Engr-280) Roots – Finding zeros 06 April, 2023 10 / 15
Open Methods: Newton-Raphson

initial guess at the root is 𝑥𝑖 ,

𝑓(𝑥) extend a tangent from the point
[𝑥𝑖 , 𝑓(𝑥𝑖 )].
slope = 𝑓(𝑥𝑖 ) The point where this tangent
𝑓(𝑥𝑖 ) crosses the x-axis usually represents
an improved estimate of the root.
𝑓(𝑥𝑖 ) − 0 the first derivative at x is
equivalent to the slope:
𝑥 ′ 𝑓(𝑥𝑖 ) − 0
𝑥𝑖+1 𝑥𝑖 𝑓 (𝑥𝑖 ) =
𝑥𝑖 − 𝑥𝑖+1
𝑥𝑖 − 𝑥𝑖+1 𝑓(𝑥 )
𝑥𝑖+1 = 𝑥𝑖 − ′ 𝑖 →
𝑓 (𝑥𝑖 )
Newton-Raphson formula.

Dr. Amadou Toure Numerical Methods (Engr-280) Roots – Finding zeros 06 April, 2023 11 / 15
Newton-Raphson Method: Algorithm

′
1 Evaluate 𝑓 (𝑥𝑖 ) symbolically
𝑓(𝑥𝑖 )
2 Initial guess 𝑥𝑖 ⟹ 𝑥𝑖+1 = 𝑥𝑖 −
𝑓 ′ (𝑥𝑖 )
𝑥𝑖+1 − 𝑥𝑖
3 Find 𝜖𝑎 = ∣ ∣ × 100
𝑥𝑖+1
4 compare with pre-specified error tolerance |𝜖𝑎 | < 𝜖𝑠
▶ Converge fast (quadratic convergence) if it converges
▶ requires only one guess
▶ There are situations where it performs poorly (i.e. multiple roots)

Dr. Amadou Toure Numerical Methods (Engr-280) Roots – Finding zeros 06 April, 2023 12 / 15
The Secant Method
Newton’s method requires a symbolic evaluation of the derivative.
Certain function’s derivatives may be difficult or inconvenient to
evaluate
′
The Secant’s method approximates 𝑓 (𝑥𝑖 ) by the slope of a line
through the last two iterations.
𝑓(𝑥𝑖 )
▶ Newton’s method: 𝑥𝑖+1 = 𝑥𝑖 −
𝑓 ′ (𝑥𝑖 )
′ 𝑓(𝑥𝑖 ) − 𝑓(𝑥𝑖−1 )
▶ Approximate the derivative: 𝑓 (𝑥𝑖 ) =
𝑥𝑖 − 𝑥𝑖−1
▶ Substitute into first equation:
𝑓(𝑥𝑖 )(𝑥𝑖 − 𝑥𝑖−1 )
𝑥𝑖+1 = 𝑥𝑖 −
𝑓(𝑥𝑖 ) − 𝑓(𝑥𝑖−1 )
Requires two guesses that do not need to bracket the root
Convergence rate is good, though not quite as excellent as with
Newtons method
Dr. Amadou Toure Numerical Methods (Engr-280) Roots – Finding zeros 06 April, 2023 13 / 15
 The Newton-Raphson method may exhibits poor convergence

″
Inflection point (i.e., 𝑓 (𝑥) = 0) occurs in tendency to oscillate around a local maximum
the vicinity of a root. Iterations beginning at or minimum Inflection point
𝑥0 progressively diverge from the root
𝑓(𝑥)
𝑓(𝑥)

𝑥2 𝑥1
𝑥1 𝑥0 𝑥2 𝑥
𝑥 𝑥0

Initial guess close to one root can jump several ′

a zero slope [𝑓 (𝑥) = 0] causes division by
roots away (near-zero slopes encountered)
zero; the solution shoots off horizontally
𝑓(𝑥) 𝑓(𝑥)

𝑥
𝑥0 𝑥4 𝑥1
𝑥2 𝑥3 𝑥
𝑥0 𝑥1
Convergence depends on nature of the function and accuracy of the initial guess.
Pick initial guess “sufficiently” close to the root.
Good guesses usually predicated on knowledge of physical problem or
using graphs that provide insight into the solution.
Good computer software should be designed to recognize slow convergence or divergence.
Dr. Amadou Toure Numerical Methods (Engr-280) Roots – Finding zeros 06 April, 2023 14 / 15
Bracketting methods vs Open Methods
𝑓(𝑥) 𝑓(𝑥)

• Open method:

𝑥𝑖 A formula used to project

𝑥 𝑥𝑖+1 𝑥 from 𝑥𝑖 to 𝑥𝑖+1 in iterative
𝑥𝑙 𝑥𝑢
fashion.
May diverge or
converge rapidly
𝑥𝑙 𝑥𝑢 𝑓(𝑥) depending on shape of
function and initial guess
𝑥𝑙 𝑥𝑢

𝑥𝑙 𝑥𝑢
𝑥𝑖
𝑥𝑙 𝑥𝑢 𝑥𝑖+1 𝑥

• Bracketting method:
Root constrained within interval.
Guaranteed to converge, slowly
Dr. Amadou Toure Numerical Methods (Engr-280) Roots – Finding zeros 06 April, 2023 15 / 15