Numerical Methods

Solution of Non-Linear Equations

Jayandra Raj Shrestha

May 2021

Institute of Engineering,
Tribhuvan University, Nepal

1
Non-linear Equations

• Any single variable function in the form of f (x) = 0 can be classified as a non-linear equation if
we cannot identify it clearly as a linear equation. E.g., Polynomial equations, transcendental
equations (equations composed of trigonometric functions, logarithmic functions, etc.)
• Linear equations have one and only one root and the solution for linear equations in standard
forms can be easily computed.
• Non-linear equations may have multiple or infinite number of roots or they may not possess any
real root at all.
• Analytical solution of non-linear equations demand different approach for each new form of the
problem whereas the same numerical technique may be employed for any such problem.
• Numerical techniques generally employ some mathematical principle iteratively in some tricky
manner to obtain one root at a time, numerically.
• Numerical techniques may be cumbersome than analytical techniques and produce only
approximate results, but may be the only alternate when analytical techniques are hard or
impossible to implement.
• Compared to analytical techniques, numerical techniques are far more easier to implement as
computer algorithms. 2
Bisection Method
Bisection Method

Iterative application of the Intermediate Value

Theorem to numerically find a real root of
non-linear equation.

Intermediate Value Theorem: b

f(x)
If a function f (x) = 0 is continuous between a
an interval (a, b) such that f (a) and f (b) are
of opposite signs, then there exists at least
one real root in the interval (a, b).

1
f (x) = + sin(x)
x3

3
Intermediate Value Theorem

b a
f(x)

f(x)
a b

x x
Multiple roots may exist if f (a) and f (b) are of Even if f (a) and f (b) are of opposite signs,
opposite signs and the function is continuous in existence of root cannot be guaranteed in (a, b)
(a, b). if the function is not continuous in (a, b).

4
Intermediate Value Theorem
f(x)

f(x)
a b a b

x x

No root in (a, b) if f (a) and f (b) are of same Even number of roots in (a, b) if f (a) and
signs (both +ve). f (b) are of same signs (both +ve).

5
Intermediate Value Theorem

a b a b
f(x)

f(x)
x x

No root in (a, b) if f (a) and f (b) are of same Even number of roots in (a, b) if f (a) and
signs (both -ve). f (b) are of same signs (both -ve).

6
Bisection Method

f(a)
f(c)
b
f(x)

a c f(b)
=(a+b)/2

Step 1: Determine the initial interval (a, b) which contains a root

a+b 7
Step 2: Bisect the interval (c = 2 )
Bisection Method

b
f(x)

a (old) a (new)

Step 3: If f (c) and f (a) are of same signs, take (c, b) as new interval; i.e., regard c as new a.
Otherwise take (a, c) as new interval; i.e, regard c as new b. 8
Bisection Method

b
f(x)

a c

Repeat Steps 2 and 3

9
Bisection Method

c b
f(x)

Repeat Steps 2 and 3

10
Bisection Method

c b
f(x)

|
a

Repeat Steps 2 and 3

11
When to stop?

For an accuracy of 3 decimal places:

Tolerable Error (ε) = 0.0005

Absolute Error:
|b − a| ≤ ε

Relative Error:
|b − a| |b − a| |b − a|
≤ε OR ≤ε OR ≤ε
|a| |b| |c|

Absolute Error in Functional Value:

|f (c)| ≤ ε

12
No. of iterations (n)

Error Tolerance = ε
Initial Interval = (a, b)
Regarding the size of interval (a, b) as error:
|b−a|
Error at nth iteration = 2n

|b − a| |b − a|
∴ ≤ε ⇒ 2n ≥
2n ε
 
|b − a|
log(2n ) ≥ log
ε

n log 2 ≥ log(|b − a|) − log(ε)

log(|b − a|) − log(ε)

∴n≥
log 2
13
Example

Find a real root of x sin(x) + cos(x) = 0 correct to three decimals using the Bisection Method.
Solution: Calculation Table:
Linear Search: i a+ b− c= a+b
2 f (c)
x 0 1 2 3 4 5 6 7 1 2 3 2.5 0.69504
f (x) 1 1.38 1.40 -0.57 -3.68 -4.51 -0.72 5.35 2 2.5 3 2.75 0.12527
3 2.75 3 2.875 -0.20727
Since f (2) = +ve and f (3) = −ve 4 2.75 2.875 2.8125 -0.03738
5 2.75 2.8125 2.7813 0.04475
and the function seems to be continuous in any interval, 6 2.7813 2.8125 2.7969 0.00391
there is at least one real root between x = 2 and x = 3. 7 2.7969 2.8125 2.8047 -0.01668
8 2.7969 2.8047 2.8008 -0.00637
Thus, let the initial interval be (a, b) = (2, 3). 9 2.7969 2.8008 2.7989 -0.00135
10 2.7969 2.7989 2.7979 0.00128
Successive computations are shown in the following 11 2.7979 2.7989 2.7984 -0.00004
table.

∵ |f (2.7984)| < 0.0005

∴ root = 2.798

14
Rate of Convergence

ε0 = |b − a|

|b − a| ε0
ε1 = =
2 2
|b − a| ε1
ε2 = 2
=
2 2

... ... ...

εn
εn+1 =
2
Linear Relationship between εn and εn+1 =⇒ Linear Convergence ! 15
Algorithm/Pseudocode for Bisection Method

Define: f(x)

Read: a, b, E
if f(a) × f(b) > 0 then
Print: Error
else
repeat
c ← (a + b)/2
if f(c) × f(a) < 0 then
b←c
else
a←c
end if
until |f(c)| ≤ E
Print: c
end if
16
Assignment

1. Find the +ve real root between 6 and 7 correct to 2 decimal places and a negative real
root correct to four decimal places of x sin(x) + cos(x) = 0 using the Bisection Method.
2. While finding a real root of a non-linear equation using bisection method, if the maximum
tolerable absolute error is 0.0005 (accuracy of three decimal places) and the initial starting
interval used is 1 (i.e., |a − b| = 1 initially) what would be the approximate number of
iterations required to obtain the specified accuracy of the root? What if the initial starting
interval used is 0.1?
3. Use bisection method to find the cube root of 7 correct to 4 decimal places by taking the
initial bracket with an interval of 0.1. [Hint: x3 − 7 = 0]
4. (Practical) Develop a simple algorithm and program code in C/C++ to find a real root of
a non-linear equation using the Bisection Method for a given function from user input
values of the interval (a, b) and error tolerance (E). Check your program by changing your
equation and also for different initial intervals of the same equation.

17