BMFG 1313

ENGINEERING MATHEMATICS 1
Nonlinear Equations

Ser Lee Loh1, Wei Sen Loi2

[email protected], [email protected]
 Lesson Outcome

Upon completion of this lesson, the student should be able to:

1. Identify the range that contains root(s).

2. Compute roots for nonlinear equations by using Bisection
method, Simple Fixed-Point iteration and Newton-Raphson
method.
 Solution of a Nonlinear Equation, f(x)=0
(Polynomial, trigonometric, exponential, logarithmic equations)

Simple Newton-
Bisection
Fixed-Point Raphson
Method
Iteration Method

Intermediate Value Theorem

- Find the range that contains a root (answer)

Start the iteration with respective algorithm to get the

approximation solution
2.1 Intermediate Value Theorem

Let 𝑓𝑓 𝑥𝑥 = 0 be a non-linear equation. If 𝑓𝑓 𝑥𝑥 is a continuous function and

𝒇𝒇 𝒂𝒂 𝒇𝒇 𝒃𝒃 < 𝟎𝟎, then there exists at least a root in the interval 𝑎𝑎, 𝑏𝑏 .

When two points are connected by a

curve:
• One point below x-axis
• One point above x-axis
Then there will be at least one root
where the curve crosses the x-axis.
2.1 Intermediate Value Theorem

Example:
Given 𝑓𝑓 𝑥𝑥 = 𝑥𝑥 2 − 8𝑥𝑥 − 5, use intermediate value theorem to find the
interval that contains the negative root.

Solution:
𝑓𝑓 0 = −5 < 0
𝑓𝑓 −1 = 4 > 0
∴ 𝑓𝑓 0 𝑓𝑓 −1 < 0
Hence, the interval that contains the negative root is (−1,0).
2.1 Intermediate Value Theorem

Exercise 2.1:
1) Use intermediate value theorem to find the interval that contains the root
for 𝑓𝑓 𝑥𝑥 = 𝑥𝑥 3 + 𝑥𝑥 + 3.

2) Use intermediate value theorem to find the interval that

contains the smallest positive root of 𝑥𝑥 = 2 sin 𝑥𝑥.

[Ans: (-2,-1); (1,2)]

2.2 Bisection Method

The bisection method in y

mathematics is a root-finding
method that repeatedly bisects
an interval and then selects a a d c b
x
subinterval that contains the
root for further processing.

From (a,b), c is the midpoint of a and b

we choose (a,c), d is the midpoint of a and c
then we choose (d,c)
and so on…
until the range is small enough.
2.2.1 Bisection Method Algorithm
Write 𝑓𝑓 𝑥𝑥 = 0,
Find the initial interval 𝑎𝑎, 𝑏𝑏 , 𝑥𝑥 ∗ ∈ (𝑎𝑎, 𝑏𝑏)

𝑎𝑎𝑖𝑖 +𝑏𝑏𝑖𝑖
Compute 𝑐𝑐𝑖𝑖 = and 𝑓𝑓(𝑐𝑐𝑖𝑖 )
2

Set 𝑖𝑖 = 0
Stop the Yes Is 𝑏𝑏𝑖𝑖 − 𝑎𝑎𝑖𝑖 < 𝜀𝜀 or 𝑓𝑓(𝑐𝑐𝑖𝑖 ) < 𝜀𝜀 ??
iteration, where 𝜀𝜀 is the specified tolerance
𝑥𝑥 = 𝑐𝑐𝑖𝑖
Follow one path only No

If 𝑓𝑓 𝑎𝑎𝑖𝑖 𝑓𝑓 𝑐𝑐𝑖𝑖 < 0 If 𝑓𝑓 𝑐𝑐𝑖𝑖 𝑓𝑓 𝑏𝑏𝑖𝑖 < 0

If 𝑓𝑓 𝑐𝑐𝑖𝑖 = 0 Set 𝑎𝑎𝑖𝑖+1 = 𝑎𝑎𝑖𝑖 Set 𝑎𝑎𝑖𝑖+1 = 𝑐𝑐𝑖𝑖
and 𝑏𝑏𝑖𝑖+1 = 𝑐𝑐𝑖𝑖 and 𝑏𝑏𝑖𝑖+1 = 𝑏𝑏𝑖𝑖

Repeat the iteration, 𝑖𝑖 = 𝑖𝑖 + 1

2.2.1 Bisection Method Algorithm

Example:

Find the root of 𝑓𝑓 𝑥𝑥 = 𝑥𝑥 2 − 3 by using bisection method accurate

to within 𝜀𝜀 = 0.002 and taking 1,2 as starting interval.

(Answer correct to 4 decimal places)

Take that 𝑓𝑓(𝑐𝑐𝑖𝑖 ) < 𝜀𝜀 for your calculation.
2.2.1 Bisection Method Algorithm
Solution:
𝑖𝑖 𝑎𝑎𝑖𝑖 𝑏𝑏𝑖𝑖 𝑓𝑓(𝑎𝑎𝑖𝑖 ) 𝑓𝑓(𝑏𝑏𝑖𝑖 ) 𝑐𝑐𝑖𝑖 𝑓𝑓(𝑐𝑐𝑖𝑖 ) 𝑓𝑓(𝑐𝑐𝑖𝑖 )
0 1.0000 2.0000 -2.0000 1.0000 1.5000 -0.7500 0.7500
1 1.5000 2.0000 -0.7500 1.0000 1.7500 0.0625 0.0625
2 1.5000 1.7500 -0.7500 0.0625 1.6250 -0.3594 0.3594
3 1.6250 1.7500 -0.3594 0.0625 1.6875 -0.1523 0.1523
4 1.6875 1.7500 -0.1523 0.0625 1.7188 -0.0459 0.0459
5 1.7188 1.7500 -0.0457 0.0625 1.7344 0.0081 0.0081
6 1.7188 1.7344 -0.0457 0.0081 1.7266 -0.0190 0.0190
7 1.7266 1.7344 -0.0188 0.0081 1.7305 -0.0055 0.0055
8 1.7305 1.7344 -0.0054 0.0081 1.7325 0.0013 0.0013

Root, 𝑥𝑥 = 1.7325
2.2.1 Bisection Method Algorithm
Example:
Using the bisection method, find the root of

𝑓𝑓 𝑥𝑥 = 𝑥𝑥 6 − 𝑥𝑥 − 1

accurate to within 𝜀𝜀 = 0.003.

(Answer correct to 4 decimal places)

Take that 𝑏𝑏𝑖𝑖 − 𝑎𝑎𝑖𝑖 < 𝜀𝜀 for your calculation.
2.2.1 Bisection Method Algorithm
Solution:
𝑖𝑖 𝑎𝑎𝑖𝑖 𝑏𝑏𝑖𝑖 𝑓𝑓(𝑎𝑎𝑖𝑖 ) 𝑓𝑓(𝑏𝑏𝑖𝑖 ) 𝑐𝑐𝑖𝑖 𝑓𝑓(𝑐𝑐𝑖𝑖 ) 𝑏𝑏𝑖𝑖 − 𝑎𝑎𝑖𝑖
0 1.0000 2.0000 -1.0000 61.0000 1.5000 8.8906 1.0000
1 1.0000 1.5000 -1.0000 8.8906 1.2500 1.5647 0.5000
2 1.0000 1.2500 -1.0000 1.5647 1.1250 -0.0977 0.2500
3 1.1250 1.2500 -0.0977 1.5647 1.1875 0.6167 0.1250
4 1.1250 1.1875 -0.0977 0.6167 1.1562 0.2333 0.0625
5 1.1250 1.1562 -0.0977 0.2327 1.1406 0.0616 0.0312
6 1.1250 1.1406 -0.0977 0.0613 1.1328 -0.0196 0.0156
7 1.1328 1.1406 -0.0197 0.0613 1.1367 0.0206 0.0078
8 1.1328 1.1367 -0.0197 0.0204 1.1348 0.0004 0.0039
9 1.1328 1.1348 -0.0197 0.0008 1.1338 -0.0096 0.0020

The root is, x = 1.1338

2.2.1 Bisection Method Algorithm

Exercise 2.2:
Find the root of 𝑓𝑓 𝑥𝑥 = 𝑒𝑒 𝑥𝑥 (3.2 sin 𝑥𝑥 − 0.5 cos 𝑥𝑥) on the interval
3,4 by using bisection method accurate to within 𝜀𝜀 = 0.05.

(Answer correct to 4 decimal places)

Take that 𝑓𝑓(𝑐𝑐𝑖𝑖 ) < 𝜀𝜀 for your calculation
[Ans: 3.2969]
2.3 Simple Fixed-Point Iteration

The basic idea of the fixed-point iteration method is:

First, to reformulate an equation to an equivalent fixed-point problem:
𝑓𝑓 𝑥𝑥 = 0 ⇔ 𝑥𝑥 = 𝑔𝑔(𝑥𝑥)

Secondly, choose an initial guess 𝑥𝑥0 and use the iterative sequence 𝑥𝑥𝑛𝑛+1 = 𝑔𝑔(𝑥𝑥𝑛𝑛 ) to
compute an 𝑥𝑥 in such a way 𝑥𝑥 = 𝑔𝑔(𝑥𝑥).

*Note: A fixed point of a function 𝑔𝑔(𝑥𝑥) is a point 𝑘𝑘 where 𝑘𝑘 = 𝑔𝑔(𝑘𝑘). This point 𝑘𝑘 is not
the root of 𝑔𝑔 𝑥𝑥 = 0 but the root of 𝑓𝑓(𝑥𝑥).

There are infinite ways to present an equivalent fixed-point problem for a given
equation and it may lead to different roots found.
2.3 Simple Fixed-Point Iteration

Rearrange the function 𝑓𝑓 𝑥𝑥 = 0 into 𝑥𝑥 = 𝑔𝑔 𝑥𝑥

Write the iteration formula: 𝑥𝑥𝑖𝑖+1 = 𝑔𝑔 𝑥𝑥𝑖𝑖

where 𝑔𝑔′ (𝑥𝑥0 ) < 1, 𝑔𝑔′ (𝑥𝑥0 ) ≠ 0 for all 𝑥𝑥 ∈ [𝑎𝑎, 𝑏𝑏]

Repeat the iteration,

𝑖𝑖 = 𝑖𝑖 + 1
Compute 𝑥𝑥𝑖𝑖+1 = 𝑔𝑔 𝑥𝑥𝑖𝑖 Remarks:
The Fixed-point
iteration may converge
No to a root different from
Is 𝑥𝑥𝑖𝑖+1 − 𝑥𝑥𝑖𝑖 < 𝜀𝜀 ??
the expected one, or
where 𝜀𝜀 is the specified tolerance
it may diverge.
Yes Different
rearrangement will
Stop the iteration, converge at different
𝑥𝑥 = 𝑥𝑥𝑖𝑖+1 rates.
2.3 Simple Fixed-Point Iteration

Example:

Given 𝑓𝑓 𝑥𝑥 = 𝑥𝑥 2 − 2𝑥𝑥 − 3. Find the root of the function by using

simple fixed-point method accurate to within 𝜀𝜀 = 0.001 and taking
𝑥𝑥 = 4 as starting point.

(Answer correct to 4 decimal places)

2.3 Simple Fixed-Point Iteration
Solution:
1
a) 𝑥𝑥 = 𝑔𝑔 𝑥𝑥 = 2𝑥𝑥 + 3; 𝑔𝑔′ 𝑥𝑥 = and 𝑔𝑔′ 4 = 0.3 < 𝟏𝟏
2𝑥𝑥+3
This form will converge and give a solution
𝒊𝒊 𝒙𝒙𝒊𝒊 𝒙𝒙𝒊𝒊 − 𝒙𝒙𝒊𝒊−𝟏𝟏
0 4.0000
1 3.3166 0.6834
2 3.1037 0.2129
3 3.0344 0.0693
4 3.0114 0.0230
5 3.0038 0.0076
6 3.0013 0.0025
7 3.0004 0.0009

The value converging to root of 𝒙𝒙 = 𝟑𝟑. 𝟎𝟎𝟎𝟎𝟎𝟎𝟎𝟎

2.3 Simple Fixed-Point Iteration
Solution:
3 3
b) 𝑥𝑥 = 𝑔𝑔 𝑥𝑥 = ; 𝑔𝑔′ 𝑥𝑥 = − and 𝑔𝑔′ 4 = 0.75 < 𝟏𝟏
𝑥𝑥−2 𝑥𝑥−2 2
This form will converge and give a solution
𝒊𝒊 𝒙𝒙𝒊𝒊 𝒙𝒙𝒊𝒊 − 𝒙𝒙𝒊𝒊−𝟏𝟏
0 4.0000
1 1.5000 2.5000
2 -6.0000 7.5000
3 -0.3750 5.6250
4 -1.2632 0.8882
5 -0.9193 0.3439
6 -1.0276 0.1083 After 11 iterations, the
7 -0.9909 0.0367 value converging to root
8 -1.0030 0.0121 of 𝒙𝒙 = −𝟏𝟏
9 -0.9990 0.0040
2.3 Simple Fixed-Point Iteration
Solution:
𝑥𝑥 2 −3
c) 𝑥𝑥 = 𝑔𝑔 𝑥𝑥 = ; 𝑔𝑔′ 𝑥𝑥 = 𝑥𝑥 and 𝑔𝑔′ 4 = 4 ≮ 𝟏𝟏
2
This form will diverge and give no solution

𝒊𝒊 𝒙𝒙𝒊𝒊 𝒙𝒙𝒊𝒊 − 𝒙𝒙𝒊𝒊−𝟏𝟏

0 4.0000
1 6.5000 2.5000
2 19.6250 13.1250 value diverges
3 191.0703 171.4453 𝑥𝑥 2 −3
𝑔𝑔 𝑥𝑥 = is not a
2
4 18252.4298 18061.3595 suitable form for simple
5 166575595.3 16557342.9 fixed-point iteration
2.3 Simple Fixed-Point Iteration

Example:
Find the root of
𝑓𝑓 𝑥𝑥 = 3𝑥𝑥𝑒𝑒 𝑥𝑥 − 1
by using simple fixed-point iteration accurate to within 𝜀𝜀 = 0.0001.
Assume 𝑥𝑥0 = 1.

(Answer correct to 4 decimal places)

2.3 Simple Fixed-Point Iteration

Solution:
There are two possible forms of 𝑔𝑔 𝑥𝑥 :
1 1
𝑥𝑥 = 𝑔𝑔 𝑥𝑥 = 𝑒𝑒 −𝑥𝑥 and 𝑥𝑥 = 𝑔𝑔 𝑥𝑥 = ln
3 3𝑥𝑥
1 −𝑥𝑥 1
𝑔𝑔′ 𝑥𝑥 = − 𝑒𝑒 𝑔𝑔′ 𝑥𝑥 = −
3 𝑥𝑥
𝑔𝑔′ 1 = 𝟎𝟎. 𝟏𝟏𝟏𝟏 < 𝟏𝟏 𝑔𝑔′ 1 = 𝟏𝟏 ≮ 𝟏𝟏
Criteria is satisfied Criteria is not satisfied

1 −𝑥𝑥
∴ 𝑔𝑔 𝑥𝑥 = 𝑒𝑒
3
2.3 Simple Fixed-Point Iteration
Solution:
𝒊𝒊 𝒙𝒙𝒊𝒊 𝒙𝒙𝒊𝒊 − 𝒙𝒙𝒊𝒊−𝟏𝟏
0 1.0000
1 0.1226 0.8774
2 0.2949 0.1722
3 0.2482 0.0467
4 0.2601 0.0119
5 0.2570 0.0031
6 0.2578 0.0008
7 0.2576 0.0002
8 0.2576 0.0000
Thus, the root that satisfies the stopping criteria is 𝑥𝑥 = 0.2576.
2.3 Simple Fixed-Point Iteration

Exercise 2.3:
Locate the root of 𝑓𝑓 𝑥𝑥 = 𝑒𝑒 −𝑥𝑥 − 𝑥𝑥 by using simple fixed-point
iteration accurate to within 𝜀𝜀 = 0.003 where 𝑥𝑥 ∈ (0,1].

(Answer correct to 4 decimal places)

[Ans: 0.5664]
2.4 Newton-Raphson Method
From Taylor Series, expansion of 𝑓𝑓(𝑥𝑥) about a point 𝑥𝑥 = 𝑥𝑥0 is given by
𝑓𝑓 ′ 𝑥𝑥0 𝑓𝑓 ′′ 𝑥𝑥0
𝑓𝑓 𝑥𝑥 = 𝑓𝑓 𝑥𝑥0 + 𝑥𝑥 − 𝑥𝑥0 + (𝑥𝑥 − 𝑥𝑥0 )2 + ⋯
1! 2!
Let 𝑥𝑥 be a root of a function 𝑓𝑓(𝑥𝑥), i.e. 𝑓𝑓 𝑥𝑥 = 0 and 𝑥𝑥0 be an approximation to
the root 𝑥𝑥. Since 𝑓𝑓 𝑥𝑥 = 0 and only linear term is kept to approximate root 𝑥𝑥,
0 = 𝑓𝑓 𝑥𝑥0 + 𝑓𝑓 ′ 𝑥𝑥0 𝑥𝑥 − 𝑥𝑥0
Rearrangement of the equation gives
𝑓𝑓(𝑥𝑥0 )
𝑥𝑥 = 𝑥𝑥0 − ′
𝑓𝑓 (𝑥𝑥0 )
Hence, Newton-Raphson apply this algorithm iteratively to generate sequence
𝑓𝑓(𝑥𝑥𝑛𝑛 )
𝑥𝑥𝑛𝑛+1 = 𝑥𝑥𝑛𝑛 − ′
𝑓𝑓 (𝑥𝑥𝑛𝑛 )
2.4 Newton-Raphson Method
Write 𝑓𝑓 𝑥𝑥 = 0,
Given 𝑥𝑥0 reasonably close to the root

Compute 𝑓𝑓(𝑥𝑥0 ) and 𝑓𝑓 ′ (𝑥𝑥0 )

where 𝑓𝑓(𝑥𝑥0 ) ≠ 0 and 𝑓𝑓 ′ (𝑥𝑥0 ) ≠ 0
Set 𝑖𝑖 = 0
Repeat the iteration,
𝑓𝑓(𝑥𝑥𝑖𝑖 ) 𝑖𝑖 = 𝑖𝑖 + 1
Compute 𝑥𝑥𝑖𝑖+1 = 𝑥𝑥𝑖𝑖 −
𝑓𝑓′ (𝑥𝑥𝑖𝑖 )

No
Is 𝑥𝑥𝑖𝑖+1 − 𝑥𝑥𝑖𝑖 < 𝜀𝜀 or 𝑓𝑓(𝑥𝑥𝑖𝑖+1 ) < 𝜀𝜀 ??
where 𝜀𝜀 is the specified tolerance

Yes
Stop the iteration,
𝑥𝑥 = 𝑥𝑥𝑖𝑖+1
2.4 Newton-Raphson Method

Example:
Determine the root of the function
2
𝑓𝑓 𝑥𝑥 = − 𝑒𝑒 𝑥𝑥
𝑥𝑥
by using Newton-Raphson method with 𝑥𝑥0 = 0.8 accurate to within
𝜀𝜀 = 0.0001.

(Answer correct to 4 decimal places)

Take that 𝑓𝑓(𝑥𝑥𝑖𝑖 ) < 𝜀𝜀 for your calculation
2.4 Newton-Raphson Method
𝑓𝑓(𝑥𝑥𝑖𝑖 )
Solution: 𝑥𝑥𝑖𝑖+1 = 𝑥𝑥𝑖𝑖 − ′
𝑓𝑓 (𝑥𝑥𝑖𝑖 )
2 Check:
Given 𝑓𝑓 𝑥𝑥 = 𝑒𝑒 𝑥𝑥 − 𝑓𝑓 0.8 = −0.2745 ≠ 0
𝑥𝑥
2
hence, 𝑓𝑓 ′ 𝑥𝑥 = 𝑒𝑒 𝑥𝑥 + 2 𝑓𝑓 ′ 0.8 = 5.3505 ≠ 0
𝑥𝑥

𝑖𝑖 𝑥𝑥𝑖𝑖 𝑓𝑓(𝑥𝑥𝑖𝑖 ) 𝑓𝑓 ′ (𝑥𝑥𝑖𝑖 ) 𝑓𝑓(𝑥𝑥𝑖𝑖 )/𝑓𝑓 ′ (𝑥𝑥𝑖𝑖 ) 𝑓𝑓(𝑥𝑥𝑖𝑖 )

0 0.8000 -0.2745 5.3505 -0.0513 0.2745
1 0.8513 -0.0067 5.1024 -0.0013 0.0067
2 0.8526 0 5.0970 0 0

Root, 𝑥𝑥 = 0.8526 Reaching stopping

criteria
2.4 Newton-Raphson Method
Example:
Use the Newton-Raphson method to estimate the root of
𝑓𝑓 𝑥𝑥 = 3𝑥𝑥 + sin 𝑥𝑥 − 𝑒𝑒 𝑥𝑥
starting from 𝑥𝑥0 = 0 accurate to within
𝑥𝑥𝑖𝑖 − 𝑥𝑥𝑖𝑖−1 ≤ 0.0001.

(Answer correct to 4 decimal places)

 BEKG 2452 Numerical Methods

2.4 Newton-Raphson Method

𝑓𝑓(𝑥𝑥𝑖𝑖 )
Solution: 𝑥𝑥𝑖𝑖+1 = 𝑥𝑥𝑖𝑖 − ′
𝑓𝑓 (𝑥𝑥𝑖𝑖 )
Check:
Given 𝑓𝑓 𝑥𝑥 = 3𝑥𝑥 + sin 𝑥𝑥 − 𝑒𝑒 𝑥𝑥 𝑓𝑓 0 = −1 ≠ 0
hence, 𝑓𝑓 ′ 𝑥𝑥 = 3 + cos 𝑥𝑥 − 𝑒𝑒 𝑥𝑥 𝑓𝑓 ′ 0 = 3 ≠ 0
𝑖𝑖 𝑥𝑥𝑖𝑖 𝑓𝑓(𝑥𝑥𝑖𝑖 ) 𝑓𝑓 ′ (𝑥𝑥𝑖𝑖 ) 𝑓𝑓(𝑥𝑥𝑖𝑖 )/𝑓𝑓 ′ (𝑥𝑥𝑖𝑖 ) 𝑥𝑥𝑖𝑖 − 𝑥𝑥𝑖𝑖−1
0 0 -1.0000 3.0000 -0.3333
1 0.3333 -0.0685 2.5494 -0.0269 0.3333
2 0.3602 -0.0006 2.5022 -0.0002 0.0269
3 0.3604 -0.0001 2.5018 0 0.0002
4 0.3604 -0.0001 2.5018 0 0

Root, 𝑥𝑥 = 0.3604 Reaching stopping

criteria
2.4 Newton-Raphson Method

Exercise 2.4:
Use Newton Raphson method to find the solutions accurate to
within 10−4 for the problem
𝑓𝑓 𝑥𝑥 = ln 𝑥𝑥 − 1 + cos 𝑥𝑥 − 1
with initial guess 𝑥𝑥0 = 1.3

(Answer correct to 4 decimal places)

Take that 𝑥𝑥𝑖𝑖 − 𝑥𝑥𝑖𝑖−1 < 𝜀𝜀 for your calculation
[Ans: 1.3978]