CSE-125

Computer Programming &

Engineering Analysis

Lecture: 2
Numerical Analysis
Saadman Sakib

Department of CSE
CUET
Outline Numerical Solution of Algebraic and Transcendental Equations
Bisection Method
Method of False Position(Regula Falsi method)
Newton-Raphson Method

Iterative Methods for Solving Simultaneous Linear

Equations
Gauss-Jacobi’s iteration method
Gauss-Seidal’s iteration method

Ordinary Differential Equations: Finite Difference Method

Partial Differential Equations:
Difference Quotient, Geometrical Interpretation
Solution of Laplace and Poisson Equations
Errors in Numerical Integration

Numerical Integration:
Trapezoidal Rule
Simpson’s Rule
Numerical Analysis
Numerical analysis is a branch of mathematics that focuses on developing and analyzing
algorithms for solving mathematical problems numerically (i.e., using approximate rather
than exact solutions).

These problems often involve continuous mathematical functions and equations that are
too complex for analytical (exact) solutions, making numerical methods essential.
Topics included in Numerical Analysis:
•Root finding (e.g., Bisection Method, Newton-Raphson Method)
•Linear algebra (solving systems of linear equations)
•Interpolation and approximation (fitting functions to data points)
•Differential equations (solving ordinary and partial differential equations)
•Optimization (finding maximum or minimum values of functions)
•Integration (numerical integration techniques like Simpson's rule or trapezoidal rule)
 Numerical Solution of
Algebraic and
Transcendental Equations

06/10/2024 Department of CSE, Chittagong University of Engineering & Technology 4

Transcendental Equation
An expression of the form
𝑓(𝑥) = 𝑎0𝑥𝑛 +𝑎1𝑥𝑛-1 + ⋯ + 𝑎𝑛-1𝑥 + 𝑎𝑛 , 𝑎0 ≠ 0 is
called a polynomial of degree ‘𝑛’
and
the polynomial 𝑓(𝑥) = 0 is called an algebraic
equation of 𝑛𝑡ℎ degree.
Transcendental Equation
If 𝑓(x) contains trigonometric, logarithmic or exponential
functions, then 𝑓(x) = 0 is called a transcendental equation.

For example, 𝑥2 +2 sin𝑥 + 𝑒𝑥 = 0 is a transcendental equation.

The Problem (Finding the ROOTS)
Degree of 𝑓(x) <=4, we apply direct methods

But
if Degree of 𝑓(x) > 4 or it involves transcendental functions,
direct methods do not exist and we need to apply
numerical methods to find the roots of the equation 𝑓(x) = 0.
Solutions

1. Bisection Method
2. Method of False Position(Regula Falsi method)
3. Newton-Raphson Method
4. Gauss-Jacobi’s iteration method
5. Gauss-Seidal’s iteration method

06/10/2024 Department of CSE, Chittagong University of Engineering & Technology 8

 Bisection Method

06/10/2024 Department of CSE, Chittagong University of Engineering & Technology 9

Bisection Method (or Bolzano Method)
Bisection method is used to
find an approximate root in
an interval by repeatedly
bisecting into subintervals.

06/10/2024 Department of CSE, Chittagong University of Engineering & Technology 10

Bisection Method (or Bolzano Method)

06/10/2024 Department of CSE, Chittagong University of Engineering & Technology 11

Bisection Method (or Bolzano Method)

06/10/2024 Department of CSE, Chittagong University of Engineering & Technology 12

Bisection Method (or Bolzano Method)

06/10/2024 Department of CSE, Chittagong University of Engineering & Technology 13

Example 1
Apply bisection method to find a root of the equation 𝑥4 + 2𝑥3 - 𝑥 - 1 = 0
correct to two decimal points
Solution: f(x) = 𝑥4 + 2𝑥3 - 𝑥 – 1
Here,
f(0) = -1
f(1) = 1
∴ 𝑓(0) . 𝑓(1) < 0 thus interval [0,1]
Initial approximation: 𝑎 = 0, 𝑏 = 1

06/10/2024 Department of CSE, Chittagong University of Engineering & Technology 14

Example 1
interval [0,1]

interval [0.5,1]

interval [0.75,1]

interval [0.75, 0.875]

06/10/2024 Department of CSE, Chittagong University of Engineering & Technology 15

Example 1
interval [0.75, 0.875]

interval [0.8125, 0.875]

interval [0.84375, 0.875]

06/10/2024 Department of CSE, Chittagong University of Engineering & Technology 16

Example 1
interval [0.8594, 0.875]

interval [0.8125, 0.8672]

First 2 decimal places have been stabilized; hence 0.8633 is the real root
correct to two decimal places.

06/10/2024 Department of CSE, Chittagong University of Engineering & Technology 17

Example 2
Using Bisection Method, find the negative root of
x3 – x + 11 = 0
Solution: Let, f(x) = x3 - x + 11

Let, x = -x
So, Our equation becomes
-x3 + x + 11 = 0
x3 - x – 311 = 0
Φ(x) = x - x - 11
Therefore, we shall find the positive root of Φ(x) = 0
 Regula Falsi Method

06/10/2024 Department of CSE, Chittagong University of Engineering & Technology 19

 Regula Falsi Method
• The convergence process in the bisection method is very slow.
• It depends only on the choice of end points of the interval [a,b].
• The function f(x) does not have any role in finding the point c
(which is just the mid-point of a and b).
• It is used only to decide the next smaller interval [a,c] or [c,b].

06/10/2024 Department of CSE, Chittagong University of Engineering & Technology 20

 Regula Falsi Method
A better approximation to c can be obtained by taking the straight line
L joining the points (a,f(a)) and (b,f(b)) intersecting the x-axis. To
obtain the value of c we can equate the two expressions of the slope m
of the line L.

06/10/2024 Department of CSE, Chittagong University of Engineering & Technology 21

 The False-Position Method
(Regula-Falsi)
• An alternative method that exploits
this graphical insight is to join f(xl)
and f(xu) by a straight line. The
intersection of this line with the x axis
represents an improved estimate of the
root.
• The fact that the replacement of the
curve by a straight line gives a “false
position” of the root is the origin of
the name, method of false position, or
in Latin, regula falsi.
• It is also called the linear interpolation
method.

by Lale Yurttas, Texas A&M University Chapter 5 22

 Procedure
•

by Lale Yurttas, Texas A&M University Chapter 5 23

Example 1
Apply Regula-Falsi method to find a root of the equation 𝑥3 + 𝑥 - 1 = 0
correct to two decimal places.
Solution: f(x) = 𝑥3 + 𝑥 - 1
Here,
f(0) = -1
f(1) = 1
∴ 𝑓(0) . 𝑓(1) < 0 thus interval [0,1]
Initial approximation: 𝑎 = 0, 𝑏 = 1

06/10/2024 Department of CSE, Chittagong University of Engineering & Technology 24

Example 1
interval [0,1]

interval [0.5,1]

interval [0.636,1]

06/10/2024 Department of CSE, Chittagong University of Engineering & Technology 25

Example 1
interval [0.636,1]

interval [0.6711,1]

06/10/2024 Department of CSE, Chittagong University of Engineering & Technology 26

 First 2 decimal places have been stabilized; hence
0.6796 is the real root correct to two decimal places.
 Newton-Raphson Method

06/10/2024 Department of CSE, Chittagong University of Engineering & Technology 28

Theory

06/10/2024 Department of CSE, Chittagong University of Engineering & Technology 29

06/10/2024 Department of CSE, Chittagong University of Engineering & Technology 30
Example 1
Use Newton-Raphson method to find a root of the equation 𝑥3 - 5𝑥 + 3 = 0
correct to three decimal places.
Solution: f(x) = 𝑥3 - 5𝑥 + 3
and f’(x) = 3𝑥2 - 5
Here,
f(0) = 3
f(1) = -1
∴ 𝑓(0) . 𝑓(1) < 0 thus interval [0,1]
Initial approximation: 𝑎 = 0, 𝑏 = 1

06/10/2024 Department of CSE, Chittagong University of Engineering & Technology 31

Example 1
interval [0,1]

06/10/2024 Department of CSE, Chittagong University of Engineering & Technology 32

Example 1

Hence a root of the equation 𝑥3 - 5𝑥 + 3 = 0 correct to three

decimal places is 0.6566

06/10/2024 Department of CSE, Chittagong University of Engineering & Technology 33

Example 2

Here,
f(0) = -28 f(5) = -3
f(1) = -27 f(6) = 8
f(2) = -24
f(3) = -19 So,
f(4) = -12
06/10/2024 Department of CSE, Chittagong University of Engineering & Technology 34
Example 2

Hence a root of the equation 𝑥3 - 5𝑥 + 3 = 0 correct to three

decimal places is 0.6566

06/10/2024 Department of CSE, Chittagong University of Engineering & Technology 35

Example 2

Hence value of 28 correct to three decimal places is 5.2915

06/10/2024 Department of CSE, Chittagong University of Engineering & Technology 36

Solution of Systems of Linear Equations

37
 Naive Gaussian Elimination
Naive Gaussian Elimination
Examples

38
Naive Gaussian Elimination
• The method consists of two steps:
• Forward Elimination: the system is reduced to upper
triangular form. A sequence of elementary operations is
used.
• Backward Substitution: Solve the system starting from
the last variable.

39
Elementary Row Operations

• Adding a multiple of one row to another

• Multiply any row by a non-zero constant

40
Example
Forward Elimination

41
Example
Forward Elimination

42
Example
Forward Elimination

43
Example
Backward Substitution

44
 Gauss-Jordan Method

Gauss-Jordan Algorithm
Examples

45
Gauss-Jordan Method
• The method reduces the general system of equations AX=B to IX=B where I is an
identity matrix.

• Only Forward elimination is done and no backward substitution is needed.

• It takes 50% more time than Naive Gaussian method.

46
Gauss-Jordan Method
Example

47
Gauss-Jordan Method
Example

48
Gauss-Jordan Method
Example

49
Gauss-Jordan Method
Example

50
Gauss-Jacobi’s iteration
method

06/10/2024 Department of CSE, Chittagong University of Engineering & Technology 51

Example 1

Solution:

06/10/2024 Department of CSE, Chittagong University of Engineering & Technology 55

Example 1

06/10/2024 Department of CSE, Chittagong University of Engineering & Technology 56

06/10/2024 Department of CSE, Chittagong University of Engineering & Technology 57
 Values of variables have been
stabilized
∴ approximate solution is given
by
𝑥 = 0.186, 𝑦 = 0.331
and 𝑧 = -0.423
06/10/2024 Department of CSE, Chittagong University of Engineering & Technology 58
Gauss-Seidal’s iteration
method

06/10/2024 Department of CSE, Chittagong University of Engineering & Technology 59

System of equations given in ③ is improved
by taking latest values of the variables as

06/10/2024 Department of CSE, Chittagong University of Engineering & Technology 60

06/10/2024 Department of CSE, Chittagong University of Engineering & Technology 61
Example 1

Solution:

06/10/2024 Department of CSE, Chittagong University of Engineering & Technology 62

Example 1

06/10/2024 Department of CSE, Chittagong University of Engineering & Technology 63

06/10/2024 Department of CSE, Chittagong University of Engineering & Technology 64
 Values of variables have been
stabilized
∴ approximate solution is given by
𝑥 = 0.187, 𝑦 = 0.332 and 𝑧 = -0.423

Clearly numbers of iterations for the solution to converge in

Gauss Seidal’s method are much less than Gauss Jacobi’s method.

06/10/2024 Department of CSE, Chittagong University of Engineering & Technology 65

 Introduction to Least Squares for
Curve Fitting

66
06/10/2024 Department of CSE, Chittagong University of Engineering & Technology
 Motivation
Given a set of experimental data:
x 1 2 3
y 5.1 5.9 6.3

● The relationship between x

and y may not be clear.
● We want to find an
expression for f(x).
1 2 3

67
06/10/2024 Department of CSE, Chittagong University of Engineering & Technology
Motivation - Curve Fitting
Given a set of tabulated data, find a curve or a
function that best represents the data.
Given:
1. The tabulated data
2. The form of the function
3. The curve fitting criteria

Find the unknown coefficients

68
06/10/2024 Department of CSE, Chittagong University of Engineering & Technology
Least Squares Regression
Linear Regression
• Fitting a straight line to a set of paired observations:
(x1, y1), (x2, y2),…,(xn, yn).
y=a0+a1x+e
a1-slope.
a0-intercept.
e-error, or residual, between the model and the observations.

69
06/10/2024 Department of CSE, Chittagong University of Engineering & Technology
Selection of the Functions
•

70
06/10/2024 Department of CSE, Chittagong University of Engineering & Technology
Decide on the Criterion
•

71
06/10/2024 Department of CSE, Chittagong University of Engineering & Technology
Least Squares
Given: xi x1 x2 …. xn
yi y1 y2 …. yn

The form of the function is assumed to be

known but the coefficients are unknown.
•

The difference is assumed to be the result of

experimental error.

72
06/10/2024 Department of CSE, Chittagong University of Engineering & Technology
Determine the Unknowns
•

73
06/10/2024 Department of CSE, Chittagong University of Engineering & Technology
Determine the Unknowns
•

74
06/10/2024 Department of CSE, Chittagong University of Engineering & Technology
Example 1
x 1 2 3
• y 5.1 5.9 6.3

75
06/10/2024 Department of CSE, Chittagong University of Engineering & Technology
Remember
•

76
06/10/2024 Department of CSE, Chittagong University of Engineering & Technology
Example 1
•

77
06/10/2024 Department of CSE, Chittagong University of Engineering & Technology
Example 1
i 1 2 3 sum
xi 1 2 3 6

yi 5.1 5.9 6.3 17.3

x i2 1 4 9 14

xi y i 5.1 11.8 18.9 35.8

78
06/10/2024 Department of CSE, Chittagong University of Engineering & Technology
Example 1

79
06/10/2024 Department of CSE, Chittagong University of Engineering & Technology
Do the same for Quadratic Equations

06/10/2024 Department of CSE, Chittagong University of Engineering & Technology