CHAPTER 2 - NON LINEAR TRANSCENDENTAL AND NUMERICAL METHODS

POLYNOMIAL FUNCTION TECHNIQUE AND ANALYSIS

◼ Review Non Linear Transcendental and Polynomial Function

◼ Define and Understand the concept of Bisection Method
◼ Identify the steps and procedures involved in Bisection Method
◼ Apply Bisection Method in root finding for Non Linear Transcendental and
Polynomial Function

TRY THIS!

DIRECTION: Solve the following as your self assessment or practice problem for this
module. Since this is a formative exam, this will not be graded and not required to be
submitted.

1. Do three iterations (by hand) of the bisection method, applied to f(x) = x 3

— 2,
using a = 0 and b = 2.

2. Use the Bisection method to find solutions accurate to within 10−2 for x 4 − 2x3 −
4x2 + 4x + 4 = 0 on each interval.
(a) [-2,-1]
(b) [0,2]
(c) [2,3]
(d) [-1,0]

3. For each of the functions listed below, do a calculation by hand (i.e., with a
calculator) to find the root to an accuracy of 0.1. This process will take at most
five iterations for all of these, and fewer for several of them.
2
(a) f(x) = x - 𝑒 −𝑥 , [a,b] = [0,1]
1
(b) f(x) = ln x + x , [a,b] = [ ,1]
10
(c) f(x) = x3 – 3, [a,b] = [0,3]
(d) f(x) = x6 – x - 1, [a,b] = [0,2]
(e) f(x) = 3 – 2x , [a,b] = [0,2]

MODULE 3: BISECTION METHOD ZDMAÑAGO 1

CHAPTER 2 - NON LINEAR TRANSCENDENTAL AND NUMERICAL METHODS
POLYNOMIAL FUNCTION TECHNIQUE AND ANALYSIS

LET’S LEARN!

In this chapter we will one of the most common problems of numerical

approximation, the root-finding problem. This process involves finding a root, or
solution, of an equation of the form f (x) = 0, for a given function. A root of this equation
is also called a zero of the function f(x). First we are going to review algebraic equation
particularly non linear polynomials and transcendental functions

ALGEBRAIC EQUATION. An Algebraic Equation is a polynomial equation of the form

Pn(x) = f(x) = a0 x n + a1 x n–1 + a2 x n–2 + … + an–1 x + an = 0

Examples:
x 4 – x 2 + 5 = 0, 4x 2 – x + 7 = 0; 2x3 – x 2 + 5x + 7 = 0

TRANSCENDENTAL EQUATION. A Transcendental equation is an equation which

contains polynomials, trigonometric functions, logarithmic functions, exponential
functions etc.,

Examples:

tan x – e 2x = 0; sin x – xe x = 0; x e 2x = cos x

It is an important problem to find the roots or zeros or solutions of an equation

of the form f(x) = 0 in science and engineering where f(x) is continuous in the required
interval. A root of the equation f(x) = 0 is the value of x, say x = c for which f(c) = 0.

Figure 1 shows the geometrical interpretation of a root of an equation f(x) = 0 is

the value of x at which the graph of the equation y = f(x) crosses the x – axis

c
Figure 1

Geometrical Interpretation of a root of f (x) = 0

PROPERTIES OF THE ROOT

1. A number c is a simple root of f(x) = 0 if f(c) = 0 and f’(c) ≠ 0, then we can write
f(x) = (x-c) g(x), where g(c) ≠ 0
2. A number c is a multiple root of f(x) = 0 if f(c) = f 1(c)= ….. = fm-1(c) = 0 and f m(c) =
0 then we can write f(x) = (x-c)m g(x), where g(c) ≠ 0

MODULE 3: BISECTION METHOD ZDMAÑAGO 2

CHAPTER 2 - NON LINEAR TRANSCENDENTAL AND NUMERICAL METHODS
POLYNOMIAL FUNCTION TECHNIQUE AND ANALYSIS

➢ A polynomial equation of degree n will have exactly n roots, real or

complex, simple or multiple
➢ A transcendental equation may have one root or no root or infinite number
of roots depending on the form of f (x).

There are two classified methods of finding the roots of f (x) = 0

1. Direct Methods
Direct methods give the exact values of all the roots in a finite number of
steps.
2. Numerical Methods.
Numerical methods are based on the idea of successive approximations.

There are no direct methods for solving higher degree algebraic

equations or transcendental equations.

Numerical Methods in Finding Roots of Non Linear Transcendental and

Polynomial Function

BISECTION METHOD. The simplest numerical procedure for finding a root is to

repeatedly halve the interval [a, b], keeping the half for which f(x) changes sign.
This procedure is called the bisection method. This is the first technique on
finding root of a non linear equation which is based on the Intermediate Value
Theorem and also called the Binary-search method.

Suppose f(x) is a continuous function defined on the interval [a, b], with f (a) and f
(b) of opposite sign. The Intermediate Value Theorem implies that a number c exists in
(a, b) with f (c) = 0. The procedure will also work when there is more than one root in the
interval (a, b) and we will assume for simplicity that the root in this interval is unique.
This method calls for a repeated halving (or bisecting) of subintervals of [a, b] and, at
each step, locating the half containing c.

ADVANTAGE:

▪ A global method: it always converges no matter how far you start from the
actual root.

DISADVANTAGE:

▪ It cannot be used to find roots when the function is tangent is the axis and
does not pass through the axis.

For example: f(x) = x2

▪ It converges slowly compared with other methods.

STEPS/PROCEDURES IN PERFORMING THE BISECTION METHOD

1. Identify two points x = a and x = b such that f (a) and f (b) are having opposite
signs. Let f (a) be negative and f (b) be positive. Then there will be a root of f (x) =
0 in between a and b.

MODULE 3: BISECTION METHOD ZDMAÑAGO 3

CHAPTER 2 - NON LINEAR TRANSCENDENTAL AND NUMERICAL METHODS
POLYNOMIAL FUNCTION TECHNIQUE AND ANALYSIS

2. Let the first approximation be the midpoint of the interval (a, b)

𝒂+𝒃
𝒙𝟏 =
𝟐

3. If f(x1) = 0, then x1 is a root, otherwise root lies between a and x 1 or x1 and b

according as f (x1) is positive or negative
4. Then again bisect the interval and continue the process until the root is found to
desired accuracy (ε) .

Note: The interval width is reduced by a factor of one–half at each step and at
|𝑏−𝑎|
the end of the nth step, the new interval will be [a n, bn] of length . The number
2𝑛
of iterations n required to achieve accuracy ∈ is given by

|𝒃 − 𝒂|
𝐥𝐨𝐠 𝒆
𝒏 ≥ 𝜺
𝐥𝐨𝐠 𝒆 𝟐

5. If 𝒃𝒏 − 𝒙𝒏 ≤ ε, then accept 𝒙𝒏 as the root and stop.

EXAMPLE 1.1.

Find a real root of the equation f (x) = x 3 – 2x – 1 = 0, using Bisection method.

SOLUTION:

STEP 1: Identify two points x = a and x = b such that f (a) and f (b) are having opposite
signs.

➢ To find the interval in which the root lies, use trial and error method
If x = a = 1
f(1) = (1) 3 – 2(1) – 1 = - 2 , f(1) is negative
If x = b = 2
f(2) = (2) 3 – 2(2) – 1 = 3, f(2) is positive
➢ Since f (a) is negative and f (b) is positive. Then there will be a root of f (x) = 0 in
between the interval a and b.
➢ Thus, a root of f(x) = x 3 – 2x – 1 = 0 lies between 1 and 2

STEP 2: Let the first approximation be the midpoint of the interval (a, b) → (1,2)
𝒂+𝒃 𝟏+𝟐
𝒙𝟏 = =
𝟐 𝟐
𝒙𝟏 = 𝟏. 𝟓

STEP 3 : Test or check if f(x1) = 0, then x 1 is a root, otherwise root lies between a and x 1
or x1 and b according as f (x 1) is positive or negative.

Note: if f(x1) = + (a, x1) is the interval for the next approximation

MODULE 3: BISECTION METHOD ZDMAÑAGO 4

CHAPTER 2 - NON LINEAR TRANSCENDENTAL AND NUMERICAL METHODS
POLYNOMIAL FUNCTION TECHNIQUE AND ANALYSIS

f(𝒙𝟏 ) = 𝒇(𝟏. 𝟓) = (1.5)3 – 2(1.5) -1

f(𝒙𝟏 ) = −𝟎. 𝟔𝟐𝟓

Note: if f(x1) = + ⇒ (a, x1) is the new interval for the next approximation

if f(x1) = - ⇒ (x1, b) is the new interval for the next approximation

➢ Since f (x1) is negative , then the new interval is (x 1, b) → ( 1.5, 2)

➢ Then find the second approximation:

1.5 + 2
𝑥2 =
2
𝒙𝟐 = 𝟏. 𝟕𝟓

f(𝑥2 ) = 𝑓(1.75) = (1.75) 3 – 2(1.75) -1

f(𝒙𝟐 ) = 𝟎. 𝟖𝟓𝟗𝟑𝟕𝟓

➢ Since f(x2) is positive , then the new interval is (1.5, 1.75)

➢ Then find the third approximation:
1.5 + 1.75
𝑥3 =
2
𝒙𝟑 = 𝟏. 𝟔𝟐𝟓

f(𝑥3 ) = 𝑓(1.625) = (1.625)3 – 2(1.625) -1

f(𝒙𝟑 ) = 𝟎. 𝟎𝟒𝟏𝟎𝟐

➢ Since f(x3) is positive , then the new interval is (1.5, 1.625)

➢ Then find the fourth approximation
1.5 + 1.625
𝑥4 =
2
𝒙𝟒 = 𝟏. 𝟓𝟔𝟐𝟓

f(𝑥4 ) = 𝑓(1.5625) = (1.5625) 3 – 2(1.5625) -1

f(𝒙𝟒 ) = −𝟎. 𝟑𝟏𝟎𝟑𝟎

➢ Since f(x4) is negative , then the new interval is (1.5625, 1.625)

➢ Then find the fifth approximation
1.5625 + 1.625
𝑥5 =
2
𝒙𝟓 = 𝟏. 𝟓𝟗𝟑𝟕𝟓

f(𝑥5 ) = 𝑓(1.59375) = (1.59375)3 – 2(1.59375) -1

f(𝒙𝟓 ) = −𝟎. 𝟏𝟑𝟗𝟑𝟏𝟑

➢ Since f(x5) is negative , then the new interval is (1.59375, 1.625)
➢ Then find the sixth approximation
1.59375 + 1.625
𝑥6 =
2
𝒙𝟔 = 𝟏. 𝟔𝟎𝟗𝟑𝟕𝟓

MODULE 3: BISECTION METHOD ZDMAÑAGO 5

CHAPTER 2 - NON LINEAR TRANSCENDENTAL AND NUMERICAL METHODS
POLYNOMIAL FUNCTION TECHNIQUE AND ANALYSIS

f(𝑥6 ) = 𝑓(1.609375) = (1.609375)3 – 2(1.609375) -1

f(𝒙𝟔 ) = −𝟎. 𝟎𝟓𝟎𝟑𝟑

➢ Since f(x6) is negative , then the new interval is (1.609375, 1.625)
➢ Then find the seventh approximation
1.609375 + 1.625
𝑥7 =
2
𝒙𝟕 = 𝟏. 𝟔𝟏𝟕𝟏𝟖𝟕𝟓

f(𝑥7 ) = 𝑓(1.6171875) = (1.6171875)3 – 2(1.6171875) -1

f(𝒙𝟕 ) = −𝟎. 𝟎𝟎𝟒𝟗𝟓𝟐

Since there is no given accuracy, the question is when we are going to stop the
approximation? It is important to analyze the value of f(x) at every corresponding
approximation. In this case, you are going to stop the approximation if the value of

f(𝒙𝒏 ) = 𝟎 or f(𝒙𝒏 ) ≈ 𝟎

In this example, after the seventh (7th) iteration, f(𝒙𝟕 ) is closest to zero.
Therefore, we can conclude that the real root of the given function is
𝒙 = 𝟏. 𝟔𝟏𝟕𝟏𝟖𝟕𝟓

NOTE: The given non linear function is in third degree so it can be solved using your
scientific calculator. You can check this problem if it is approximately equal using your
calculator

TABLE: BISECTION METHOD for f (x) = x 3 – 2x – 1 = 0

No. of 𝒂+𝒃
Approximatio a b [a,b] 𝒙𝒏 = f(𝒙𝒏 )
n (Iteration) 𝟐
1 1 2 [1,2] 1.5 −𝟎. 𝟔𝟐𝟓
2 1.5 2 [1.5,2] 1.75 𝟎. 𝟖𝟓𝟗𝟑𝟕𝟓
3 1.5 1.75 [1.5,1.75] 1.625 𝟎. 𝟎𝟒𝟏𝟎𝟐
4 1.5 1.625 [1.5, 1.625] 1.5625 −𝟎. 𝟑𝟏𝟎𝟑𝟎
5 1.5625 1.625 [1.5625, 1.625] 1.59375 −𝟎. 𝟏𝟑𝟗𝟑𝟏𝟑
6 1.59375 1.625 [1.59375,1.625] 1.609375 −𝟎. 𝟎𝟓𝟎𝟑𝟑
7 1.609375 1.625 [1.609375,1.625] 1.6171875 −𝟎. 𝟎𝟎𝟒𝟗𝟓𝟐

EXAMPLE 1.2.

Find the largest root of f(x) = x6 − x − 1 = 0 accurate to within ε = 0.001

SOLUTION:

STEP 1: Identify two points x = a and x = b such that f (a) and f (b) are having
opposite signs

➢ To find the interval in which the root lies, use trial and error method
If x = a = 1

MODULE 3: BISECTION METHOD ZDMAÑAGO 6

CHAPTER 2 - NON LINEAR TRANSCENDENTAL AND NUMERICAL METHODS
POLYNOMIAL FUNCTION TECHNIQUE AND ANALYSIS

f(1) = (1) 6 – (1) – 1 = - 1 , f(1) is negative

If x = b = 2
f (2) = (2) 6 – (2) – 1 = 61 , f(2) is positive
➢ Since f (a) is negative and f (b) is positive. Then there will be a root of f (x) = 0 in
between the interval a and b.
➢ Thus, a root of f(x) = x6 – x – 1 = 0 lies between 1 and 2

STEP 2: To find how many iterations will be necessary, use

|𝒃 − 𝒂| |𝟐 − 𝟏|
𝐥𝐨𝐠 𝐥𝐨𝐠
𝒏 ≥ ∈ ≥ 𝟎. 𝟎𝟎𝟏
𝐥𝐨𝐠 𝟐 𝐥𝐨𝐠 𝟐
𝒏 ≥ 𝟗. 𝟗𝟔𝟓𝟕𝟖

➢ Since n ≈ 10, we can solve this problem until 10 th iteration

STEP 3: Let the first approximation be the midpoint of the interval (a, b) → (1,2)
𝐚+𝐛 𝟏+𝟐
𝐱𝟏 = =
𝟐 𝟐
➢ 𝐱𝟏 = 𝟏. 𝟓

STEP 4: Test or check if f(x 1) = 0, then x1 is a root, otherwise root lies between a and x 1
or x1 and b according as f (x 1) is positive or negative.

f(𝒙𝟏 ) = 𝒇(𝟏. 𝟓) = (1.5)6 – (1.5) -1

f(𝒙𝟏 ) = 𝟖. 𝟖𝟗𝟎𝟔𝟐𝟓
➢ Since f (x1) is positive , then the new interval is (a,x1) → ( 1, 1.5)

Then find the second approximation:

1 + 1.5
𝑥2 =
2
𝒙𝟐 = 𝟏. 𝟐𝟓

f(𝑥2 ) = 𝑓(1.25) = (1.25) 6 – (1.25) -1

f(𝒙𝟐 ) = 𝟏. 𝟓𝟔𝟒𝟔𝟗𝟕𝟑

➢ Since f(x2) is positive , then the new interval is (1, 1.25)

➢ Then find the third approximation:
1 + 1.25
𝑥3 =
2
𝒙𝟑 = 𝟏. 𝟏𝟐𝟓

f(𝑥3 ) = 𝑓(1.125) = (1.125)6 – (1.125) -1

f(𝒙𝟑 ) = −𝟎. 𝟎𝟗𝟕𝟕𝟏𝟑𝟓

➢ Since f(x3) is negative , then the new interval is (1.125, 1.25)

MODULE 3: BISECTION METHOD ZDMAÑAGO 7

CHAPTER 2 - NON LINEAR TRANSCENDENTAL AND NUMERICAL METHODS
POLYNOMIAL FUNCTION TECHNIQUE AND ANALYSIS

➢ Then find the fourth approximation

1.125 + 1.25
𝑥4 =
2
𝒙𝟒 = 𝟏. 𝟏𝟖𝟕𝟓

f(𝑥4 ) = 𝑓(1.1875) = (1.1875) 6 – (1.1875) -1

f(𝒙𝟒 ) = 𝟎. 𝟔𝟏𝟔𝟔𝟓𝟑

➢ Since f(x4) is positive , then the new interval is (1.125, 1.1875)

➢ Then find the fifth approximation
1.125 + 1.1875
𝑥5 =
2
𝒙𝟓 = 𝟏. 𝟏𝟓𝟔𝟐𝟓

f(𝑥5 ) = 𝑓(1.15625) = (1.15625)6 – (1.15625) -1

f(𝒙𝟓 ) = 𝟎. 𝟐𝟑𝟑𝟐𝟔𝟗
➢ Since f(x5) is positive, then the new interval is (1.125, 1.15625)
➢ Then find the sixth approximation
1.125 + 1.15625
𝑥6 =
2
𝒙𝟔 = 𝟏. 𝟏𝟒𝟎𝟔𝟐𝟓

f(𝑥6 ) = 𝑓(1.140625) = (1.140625)6 – (1.140625) -1

f(𝒙𝟔 ) = 𝟎. 𝟎𝟔𝟏𝟓𝟕𝟕𝟖
➢ Since f(x6) is positive , then the new interval is (1.125, 1.140625)
Then find the seventh approximation
1.125 + 1.140625
𝑥7 =
2
𝒙𝟕 = 𝟏. 𝟏𝟑𝟐𝟖𝟏𝟐𝟓

f(𝑥7 ) = 𝑓(1.1328125) = (1.1328125)6 – (1.1328125) -1

f(𝒙𝟕 ) = −𝟎. 𝟎𝟏𝟗𝟓𝟕𝟓𝟔

➢ Since f(x7) is negative , then the new interval is (1.1328125, 1.140625)

Then find the eighth approximation

1.1328125 + 1.140625
𝑥8 =
2
𝒙𝟖 = 𝟏. 𝟏𝟑𝟔𝟕𝟏𝟖𝟕𝟓

f(𝑥8 ) = 𝑓(1.13671875) = (1.13671875)6 – (1.13671875) -1

f(𝒙𝟖 ) = 𝟎. 𝟎𝟐𝟎𝟔𝟏𝟖
➢ Since f(x8) is positive , then the new interval is (1.1328125,1.13671875)

Then find the ninth approximation

1.1328125 + 1.13671875
𝑥9 =
2
𝒙𝟗 = 𝟏. 𝟏𝟑𝟒𝟕𝟔𝟓𝟔𝟐𝟓
MODULE 3: BISECTION METHOD ZDMAÑAGO 8
 CHAPTER 2 - NON LINEAR TRANSCENDENTAL AND NUMERICAL METHODS
POLYNOMIAL FUNCTION TECHNIQUE AND ANALYSIS

f(𝑥9) = 𝑓(1.134765625) = (1.134765625)6 – (1.134765625) -1

f(𝒙𝟗 ) = 𝟎. 𝟎𝟎𝟎𝟒𝟐𝟔𝟖𝟒

➢ Since f(x9) is positive , then the new interval is (1.1328125,1.134765625 )

Then find the tenth or final approximation

1.1328125 + 1.134765625
𝑥10 =
2
𝒙𝟏𝟎 = 𝟏. 𝟏𝟑𝟑𝟕𝟖𝟗𝟎𝟔𝟑

f(𝑥10 ) = 𝑓(1.133789063) = (1.133789063)6 – (1.133789063) -1

f(𝒙𝟏𝟎 ) = − 𝟎. 𝟎𝟎𝟗𝟓𝟕𝟗𝟗𝟑

Since the given accuracy ε = 0.001, we need to analyze 𝒃𝒏 − 𝒙𝒏 ≤ ε for us to

decide which will be the final answer for the largest root of the given function.

The table below shows the summary of results after 10th iteration.

TABLE: BISECTION METHOD for f (x) = x 6 – x – 1 = 0

No. of
Approximati 𝒂+𝒃
a b [a,b] 𝒙𝒏 = 𝒃𝒏 - 𝒙𝒏 f(𝒙𝒏 )
on 𝟐
(Iteration)
1 1 2 [1,2] 1.5 0.5 8.890625
2 1 1.5 [1, 1.5] 1.25 0.25 1.5646973
3 1 1.25 [1,1.25] 1.125 0.125 -0.0977135
4 1.125 1.25 [1.125, 1.25] 1.1875 0.0625 0.616653
5 1.125 1.1875 [1.125, 1.1875] 1.15625 0.03125 0.233269
6 1.125 1.15625 [1.125, 1.15625] 1.140625 0.015625 0.0615778
7 1.125 1.140625 [1.125, 1.140625] 1.1328125 0.0078125 −0.0195756
8 1.1328125 1.140625 [.1328125, 1.13671875 0.0039025 0.020618
1.140625]
9 1.1328125 1.13671875 [1.1328125, 1.134765625 0.002021875 0.00042684
1.13671875]
10 1.1328125 1.134765625 [1.1328125, 1.133789063 0.000976562 − 0.00957993
[1.134765625]

In this example, after the tenth (10th) iteration, f(𝒙𝟏𝟎 ) is closest to zero.
Therefore, we can conclude that the largest real root of the given function is
𝒙 = 𝟏. 𝟏𝟑𝟒𝟕𝟔𝟓𝟔𝟐𝟓

MODULE 3: BISECTION METHOD ZDMAÑAGO 9

CHAPTER 2 - NON LINEAR TRANSCENDENTAL AND NUMERICAL METHODS
POLYNOMIAL FUNCTION TECHNIQUE AND ANALYSIS

Prepared by: s

ENGR. ZENDY D. MAÑAGO

EE Faculty

References:

1. Epperson, James F (2013). “An IntroductionNumerical Methods and Analysis”. 2nd

ed. John Wiley & Sons, Inc
2. Burden, Richard L. and J. Douglas Faires. (2011) .“Numerical Analysis”. 9th ed.
Cengage Learning

MODULE 3: BISECTION METHOD ZDMAÑAGO 10