MAT 2003 Applied Numerical Method

Module 1. Solutions of Algebraic an Transcendental Equations in One Variable

Prasad Enagandula
Assistant Professor
Department of Mathematics
VIT Bhopal University

Title Applied Numerical Methods

Module 1. Solutions of Algebraic an Transcendental Equations in One Variable Applied Numerical Method

Syllabus

Introduction to Direct and Iterative methods - Bisection method, Fixed point

Iteration method - order and condition of convergence - Secant and Newton-
Raphson methods for simple roots - Rates of convergence.

2
Syllabus Dr. [Link]
Module 1. Solutions of Algebraic an Transcendental Equations in One Variable Applied Numerical Method

Definitions

In this chapter we shall discuss some numerical methods for solving algebraic and
transcendental equations.

Algebraic Equation:
The equation f(x)=0 is said to be algebraic if f(x) is a polynomial only in x
For example: 𝑥 3 − 7𝑥 = 3 = 0, 𝑥 4 − 3𝑥 3 − 7𝑥 2 + 3𝑥 + 2 = 0

Transcendental Equation:
If f(x) contains some other functions, namely, Trigonometric, Logarithmic, Exponential, etc.,
then the equation f (x) = 0 is called a Transcendental Equation.
For example: 3tanx-4sinx+3x=0, 𝑒 𝑥 = 4𝑥

3
Definition Dr. [Link]
Module 1. Solutions of Algebraic an Transcendental Equations in One Variable Applied Numerical Method

Introduction
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).
The methods of finding the roots of f (x) = 0 are classified as,
1. Direct Methods
2. Numerical Methods.
Direct methods give the exact values of all the roots in a finite number of steps. Numerical methods
are based on the idea of successive approximations. In these methods, we start with one or two
initial approximations to the root and obtain a sequence of approximations x0, x1,…xk which in the
limit as k converge to the exact root x = a.
There are no direct methods for solving higher degree algebraic equations or transcendental
equations. Such equations can be solved by Numerical methods. In these methods, we first find an
interval in which the root lies. If a and b are two numbers such that f (a) and f (b) have opposite signs,
then a root of f (x) = 0 lies in between a and b. We take a or b or any valve in between a or b as first
approximation x1. This is further improved by numerical methods. Here we discuss few important
Numerical methods to find a root of f (x) = 0. 4
Introduction Dr. [Link]
 Module 1. Solutions of Algebraic an Transcendental Equations in One Variable Applied Numerical Method

Theorem (Intermediate Value Theorem): If a function f (x) assumes values of opposite sign at the

end points of interval (a,b) ,

i.e., f (a) f (b)  0

then there will be at least one number c(a,b) such that f (c) = 0.

Geometry of the Theorem:

5
Intermediate Value theorem Dr. [Link]
Module 1. Solutions of Algebraic an Transcendental Equations in One Variable Applied Numerical Method

List of Methods

The following methods will be discussed to find a root of the given Algebraic an
Transcendental Equations
1. Bisection Method
2. The Iteration Method(or Fixed point Iteration method)
3. Newton Raphson Method(Method of Tangent)
4. Secant Method

6
Methods Dr. [Link]
Module 1. Solutions of Algebraic an Transcendental Equations in One Variable Applied Numerical Method

[Link] Method

7
Bisection Method Dr. [Link]
 Module 1. Solutions of Algebraic an Transcendental Equations in One Variable Applied Numerical Method

Introduction
Bisection method is used to find an approximate root in an interval by repeatedly
bisecting into subintervals. It is a very simple and robust method but it is also relatively
slow. Because of this it is often used to obtain a rough approximation to a solution which
is then used as a starting point for more rapidly converging methods. This method is
based on the intermediate value theorem for continuous functions.

8
Bisection Method Dr. [Link]
 Module 1. Solutions of Algebraic an Transcendental Equations in One Variable Applied Numerical Method

Algorithms

Step1:Identify two points x = a and x = b such that f (a) and f (b) are having opposite signs.
Then there will be a root of f (x) = 0 in between a and b. (Let f(a)<0,f(b)>0)
Step2:Let the first approximation be the mid point of the interval (a, b).
𝑎+𝑏
i.e. 𝑥1 =
2
Step3: Let us suppose f(x1) >0, and immediate previously we have f(a)<0 then root lies in
between a and x1. The second approximation to the root is given by,
𝑎+𝑥1
𝑥2 =
2
Step4: If we have f(x2) <0 , immediate previously we have f(x1) >0, then the next
approximation is given by
𝑥2 +𝑥1
𝑥3 =
2
Repeate the same procedure to get other approximations until the root is found to
desired accuracy.

9
Bisection Method Dr. [Link]
Module 1. Solutions of Algebraic an Transcendental Equations in One Variable Applied Numerical Method

Number of Iterations-Bisection Method

Using Bisection Method, in order to calculate an approximate root of a function within

tolerance ε, the number n of iterations we need to perform is:

𝑏−𝑎
log( )
𝑛≥ ∈
𝑙𝑜𝑔2

Example: Find the number of iterations required and root of the corresponding of
f(x)= 𝑥 6 − 𝑥 − 1 accurate with in ∈ = 0.001

Sol: we will get a=1 and b=2 , ∈ = 0.01 is given, then

𝑏−𝑎 2−1
log( ∈ ) log( )
0.001
𝑛≥ = = 9.97
𝑙𝑜𝑔2 𝑙𝑜𝑔2

Therefore at n=10 is the minimum root we will get at 𝑥10 =x=1.0338

10
Bisection Method Dr. [Link]
Module 1. Solutions of Algebraic an Transcendental Equations in One Variable Applied Numerical Method

Example: Find the root of the following polynomial function using the bisection method x3 – 4x – 9.

11
Bisection Method Dr. [Link]
Module 1. Solutions of Algebraic an Transcendental Equations in One Variable Applied Numerical Method

12
Bisection Method Dr. [Link]
Module 1. Solutions of Algebraic an Transcendental Equations in One Variable Applied Numerical Method

Exercise
1. Bisection method
a) Find a real root of the equation x 3 − 3x + 1 = 0 Ans: 1.5323
b) Find a real root of the equation x 3 − x + 11 = 0 Ans: 2.3737
c) Find a Positive root of xlog10 x = 1.2 Ans: 2.6875
d) Find a negative root of the equation x 3 − 2x + 5 = 0 Ans: -6.169

13
Bisection Method Dr. [Link]
Module 1. Solutions of Algebraic an Transcendental Equations in One Variable Applied Numerical Method

[Link] Point Iteration Method

14
Fixed Point Iteration Method Dr. [Link]
Module 1. Solutions of Algebraic an Transcendental Equations in One Variable Applied Numerical Method

The Iteration Method ( or Fixed point Iteration method)

,
Finding approximate solutions to the equation

f(x) = 0 ...(1)

for a given f. In many cases, it is not possible to and the exact solutions to equation (1). Even if f(x) is a
quadratic or cubic polynomial, the (real) solutions to the equation (1) could be irrationals.
we first change the equation (1) to a form called fixed point form
x = 𝜑(x) …(2)
in such a way that any solution to equation (2) is a solution to equation (1).
Then the formula for fixed point iteration is
𝑥𝑛+1 = 𝜑𝑛 𝑥 , 𝑛 = 0,1,2, . .
Note:
The sequence of approximations x0, x1, x2,…xn given by (2) converges to the root 𝛼 in the interval I, if
| 𝜑′(x) |< 1 for all x in I.

15
Fixed Point Iteration Method Dr. [Link]
Module 1. Solutions of Algebraic an Transcendental Equations in One Variable Applied Numerical Method

Example: Find the root of the following polynomial function using the fixed point iteration x3 +7x-2.

Sol: Given that f(x)= x3 +7x-2.

f(0)=-2<0
f(1)=6>0
Therefore the root lies between 0 and 1
0+1
Let x0 = = 0.5
2

We can change f(x)=0 to a fixed point form x = φ x

There are different forms
i) x = φ1 x = 2-6x-x 3
1
ii) x = φ2 x = 2 − x 3 and etc
7

Now we need to check which of the above two satisfies the condition φ′(x) < 1, xϵ 0,1
For φ1 ′ x =6-3x 2 and φ1 ′ 0.5 =6-3(0.5)2 = 5.25 > 0, it is clear that φ1 ′ 0.5 >1
There for φ1 x is not convergent we should not take it for this method
−3𝑥 2 −3(0.5)2
And for φ2 ′ x = and φ2 ′ 0.5 = = −0.1071 > 0,it is clear that φ2 ′ 0.5 <1
7 7

There for φ2 x is convergent we should take it for this method

1
Then the formula for fixed point iteration is 𝑥𝑛+1 = 𝜑𝑛 𝑥 , 𝑛 = 0,1,2, . . Where φn x = 2 − 𝑥𝑛 3
7 16
Fixed Point Iteration Method Dr. [Link]
Module 1. Solutions of Algebraic an Transcendental Equations in One Variable Applied Numerical Method

1
𝑥𝑛+1 = 𝜑𝑛 𝑥 , 𝑛 = 0,1,2, . . Where φn x = 2 − 𝑥𝑛 3
7
1 1
𝑥1 = 2 − 𝑥0 3 = 2 − (0.5)3 =0.2678
7 7
1 1
𝑥2 = 2 − 𝑥1 3 = 2 − (0.2678)3 =0.2829
7 7

1 1
𝑥3 = 2 − 𝑥2 3 = 2 − (0.2829)3 =0.2824
7 7
1 1
𝑥4 = 2 − 𝑥3 3 = 2 − (0.2824)3 =0.2824
7 7

𝑥3 ≅ 𝑥4
Therefore our required root x=0.2824

Exercise on Iterative Method(Successive Approximation Method)

1. Find a real root of the equation x 3 − 3x + 1 = 0 up to 3 decimals Ans: 1.532
2. Fnd a real root of the equation cosx = 3x − 1 up to 4 decimals Ans: 0.6071
3. Find a real root of the equation 2x 3 − 2x − 5 = 0 up to 3 decimals Ans: 1.6003
4. Find a real root of the equation x 3 + 2x 2 + x − 1 = 0 Ans: 0.4657
5. Find a real root of the equation 3x-log10 x = 6 = 0 up to 3 decimals Ans:2.1079

17
Fixed Point Iteration Method Dr. [Link]
Module 1. Solutions of Algebraic an Transcendental Equations in One Variable Applied Numerical Method

[Link] Raphson Method

18
Newton Raphson Method Dr. [Link]
Module 1. Solutions of Algebraic an Transcendental Equations in One Variable Applied Numerical Method

Newton Raphson Method

19
Newton Raphson Method Dr. [Link]
Module 1. Solutions of Algebraic an Transcendental Equations in One Variable Applied Numerical Method

20
Newton Raphson Method Dr. [Link]
Module 1. Solutions of Algebraic an Transcendental Equations in One Variable Applied Numerical Method

21
Newton Raphson Method Dr. [Link]
Module 1. Solutions of Algebraic an Transcendental Equations in One Variable Applied Numerical Method

22
Newton Raphson Method Dr. [Link]
Module 1. Solutions of Algebraic an Transcendental Equations in One Variable Applied Numerical Method

23
Newton Raphson Method Dr. [Link]
Module 1. Solutions of Algebraic an Transcendental Equations in One Variable Applied Numerical Method

Exercise on Newton Raphson Method

1. Find a real root of the equation x 3 − 3x + 1 = 0 up to 3 decimals Ans: 1.532
2. Find a real root of the equation xex − 2 = 0 up to 3 decimals Ans: 0.8528
3. Evaluate 12 to four places of decimals using newton Raphson Method Ans: 3.5420
4. Evaluate 1/ 23 four places of decimals using newton Raphson Method Ans: 0.5671
3 3
5. Derive the formula for N using newton Raphson Method and evaluate 48

24
Newton Raphson Method Dr. [Link]
Module 1. Solutions of Algebraic an Transcendental Equations in One Variable Applied Numerical Method

[Link] SECANT METHOD

25
Secant Method Dr. [Link]
Module 1. Solutions of Algebraic an Transcendental Equations in One Variable Applied Numerical Method

THE SECANT METHOD

A potential problem in implementing the Newton-Raphson method is the evaluation of the derivative.
Although this is not inconvenient for polynomials and many other functions, there are certain
functions whose derivatives may be extremely difficult or inconvenient to evaluate. For these cases,
the derivative can be approximated by a backward finite divided difference, as in (Fig.)

This approximation can be substituted into Newton Raphson

method formula to yield the following iterative equation:

26
Secant Method Dr. [Link]
Module 1. Solutions of Algebraic an Transcendental Equations in One Variable Applied Numerical Method

27
Secant Method Dr. [Link]
Module 1. Solutions of Algebraic an Transcendental Equations in One Variable Applied Numerical Method

Example: Find a root of an equation f(x)=𝑥 3 -x-1 using Secant method up to 2 decimals

28
Secant Method Dr. [Link]
Module 1. Solutions of Algebraic an Transcendental Equations in One Variable Applied Numerical Method

𝑥5 ≈ 𝑥6 (up to 2 decimals) ,∴ 𝑥=1.3247 29

Secant Method Dr. [Link]
Module 1. Solutions of Algebraic an Transcendental Equations in One Variable Applied Numerical Method

Exercise on Secant Method

a) Find a real root of the equation x 3 − x − 1 = 0 up to 2 decimals Ans: 1.3247

b) Find a real root of the equation cosx − x = 0 up to 3 decimals Ans: 0.7390

c) Find a real root of the equation e−x − x = 0 Ans: 3.5420

d) Find a real root of the equation x 6 − x − 1 = 0 up to 3 decimals Ans: 0.5671

30
Secant Method Dr. [Link]
Module 1. Solutions of Algebraic an Transcendental Equations in One Variable Applied Numerical Method

[Link] of Convergence

31
Newton Raphson Method Dr. [Link]
Module 1. Solutions of Algebraic an Transcendental Equations in One Variable Applied Numerical Method

Order of Convergence: For any iterative numerical method, each successive iteration gives an
approximation that moves progressively closer to actual solution. This is known as convergence. Any
numerical method is said have order of convergence p , if p is the largest positive number such that

𝜖𝑛+1 < 𝑘 𝜖𝑛 𝑝

Or

∈𝑛+1
lim𝑛→∞ = k and 𝑘 > 0
∈𝑛 𝑝

where 𝜖𝑛+1 and 𝜖𝑛 are errors in 𝑛𝑡ℎ and (𝑛 + 1)𝑡ℎ iterations, k is a finite positive constant

32
Order of Convergence Dr. [Link]
Module 1. Solutions of Algebraic an Transcendental Equations in One Variable Applied Numerical Method

**Imp: Find order of convergence for Newton Raphson and Secant Method

Newton Raphson

33
Order of Convergence Dr. [Link]
Module 1. Solutions of Algebraic an Transcendental Equations in One Variable Applied Numerical Method

34
Order of Convergence Dr. [Link]
Module 1. Solutions of Algebraic an Transcendental Equations in One Variable Applied Numerical Method

35
Order of Convergence Dr. [Link]
Module 1. Solutions of Algebraic an Transcendental Equations in One Variable Applied Numerical Method

Secant Method

36
Order of Convergence Dr. [Link]
Module 1. Solutions of Algebraic an Transcendental Equations in One Variable Applied Numerical Method

37
Order of Convergence Dr. [Link]
Module 1. Solutions of Algebraic an Transcendental Equations in One Variable Applied Numerical Method

38
Order of Convergence Dr. [Link]
Module 1. Solutions of Algebraic an Transcendental Equations in One Variable Applied Numerical Method

39
Order of Convergence Dr. [Link]