CE 2201

Numerical Methods & Computer Programming

Introduction

[Link]

2nd Year Even Semester Md. Rafiul Islam

 Course Outline
2

1. Course No. : CE 2201

2. Course and Title : Numerical Methods & Computer Programming
3. Credit Hours : 4.00
4. Contact Hours : 56 hrs./Semester
5. Course Prerequisites : N/A
6. Year and Semester : 2nd Year Even Semester
7. Course Instructor : 1. Md. Rafiul Islam, Assistant Professor, Dept. of Civil
Engineering, RUET, Email: mrislam@[Link]
2. Sumaya Tabassum, Lecturer, Dept. of Civil Engineering,
RUET, Email: sumayatabassum161@[Link]
Introduction
Objectives of Numerical Methods
o Introduce basic concepts of a few numerical methods
o Gain knowledge of numerical solution of different kinds of problems
occurring in engineering
Outcomes
At the end of the course, the student will be able to
CO1 Understand the basic of Numerical Methods and Computer Programming

Analyze Complex Engineering problems considering suitable Numerical methods

CO2
by accounting for advantages and limitations.
Apply computer programming in solving different numerical problems in civil
CO3
engineering.
 Course Outcomes (COs), Program Outcomes
(POs), Teaching Learning and Assessment
4

Domain/ level of
Mapped Delivery Methods and Assessment
CO No. Learning
PO Activities Tools
Taxonomy
Cognitive ▪ Lectures ▪ Class Test
CO1 PO1 ▪ Multimedia Presentation
(Understand) ▪ Final Exam
▪ White board & Marker
Pen ▪ Class Test
Cognitive
CO2 PO2 ▪ Question-answers in the ▪ Assignment
(Understand)
class ▪ Final Exam
▪ Student’s presentation ▪ Class Test
Cognitive Discussion
CO3 PO2 ▪ ▪ Assignment
(Understand) Active learning
▪ ▪ Final Exam
Introduction
Syllabus
o Numerical solution of algebraic and transcendental equations
o Matrices
o Solution of systems of linear equations
o Curve-fitting by least squares
o Finite differences
o Divided differences
o Interpolation
o Numerical differentiation and integration
o Numerical solution of differential equations
Reference Books
1. Introductory Methods of Numerical Analysis- S. S. Sastry
2. Numerical Methods for Engineers- Raymond and Steven
Analytical, Numerical and Empirical Solution
o Analytical- Exact solution. Example: Quadratic equation
o Empirical- Experimental solution. Example: Deflection from load test
o Numerical- An approximation. Example: Finite Element Analysis

[Link]
Numerical Methods and Analysis
o Numerical Methods- an approximate method
Numerical Methods
 Methods of finding the roots of an equation
 Methods of solving the system of linear algebraic equations
 Interpolation and regression analysis
 Numerical differentiation.
 Numerical integration
 Solution of differential equation
o Numerical Analysis- the study of numerical methods

[Link]
[Link]
Engineering Analysis and Numerical Methods

Applied Engineering Analysis, Author: Tai-Ran Hu

Necessity of Numerical Methods
o Mathematical solutions analytically using calculus
o Equations have to be solved using numerical methods
o No analytical solution
o Complex mathematical problems using arithmetic operation

[Link]
Solution of Algebraic and Transcendental Equations
• Algebraic equation: the form f(x) = 0 where f(x) is purely a polynomial
• Transcendental equation: f(x) involves trigonometrical, arithmetic or exponential
terms
Numerical methods for finding the roots of an equation:
 Bisection method
 Method of False Position
 Iteration Method
 Newton-Raphson Method
 Secant Method
 Ramanujan’s Method
 Muller’s Method
 Lin-Bairstow’s Method etc.
Bisection/Bipartition Method
Theorem: If a function 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 exists in (a, b) with f(p) = 0

Computational Steps:
Bisection Method…
o Convergence- narrows the gap towards exact solution
o Divergence- Opposite of convergence
o Bisection Method never diverges being bracket
o Bracketing Method- starting and maximum limit
o Open Method- one initial guess
Algorithm of Bisection Method
o Process or set of rules to be followed in calculations or other problem-
solving operations, especially by a computer
1. Start
2. Define function f(x)
3. Choose initial guesses x0 and x1 such that f(x0)f(x1) < 0
4. Choose pre-specified tolerable error e.
5. Calculate new approximated root as x2 = (x0 + x1)/2
6. Calculate f(x0)f(x2)
a. if f(x0)f(x2) < 0 then x0 = x0 and x1 = x2
b. if f(x0)f(x2) > 0 then x0 = x2 and x1 = x1
c. if f(x0)f(x2) = 0 then goto (8)
7. if |f(x2)| > e then goto (5) otherwise goto (8)
8. Display x2 as root.
9. Stop
Bisection Method…
15

Solution:
16
Flow Chart of Bisection Method
A flowchart is a visual representation
of the sequence of steps and decisions
needed to perform a process.
• The Oval or Pill Shape- the
start/end.
• The Rectangle Shape- process.
• The Parallelogram Shape-
input/output
• The Diamond Shape- decision.
• The Arrow Shape- sequence.
Advantages and Disadvantages of Bisection Method
Method of False Position
o Also called Regula Falsi Method or Linear
Interpolation Method or Method of Chords
o Suitable for non-linear equations
o If a function f(x) is a continuous function defined
on the interval [a, b], with f(a) and f(b) of
opposite sign, root lies between a and b.
o The equation of chord joining
Method of False Position…
o The point of intersection-
 Method of False Position…
1. Start
2. Read values of x0, x1 and e
3. Computer function of f(x0) and f(x1)
4. Check whether the product of f(x0) and f(x1) is negative or not
 If it is positive take another initial guesses.
 If it is negative then goto step 5.
5. Determine:
x = [x0*f(x1) – x1*f(x0)] / (f(x1) – f(x0))
6. Check whether the product of f(x0) and f(x) is negative or not
 If it is negative, then assign x0 = x;
 If it is positive, assign x1 = x;
7. Check whether the value of f(x) is greater than 0.00001 or not.
 If yes, goto step 5.
 If no, goto step 8.
8. Display x as root.
9. Stop
22
23
Iteration Method
• Find the solution of an equation f(x) = 0
• The equation can be expressed as x = 𝜑(x).
• Choose 𝜑(x) such that | 𝜑’(x)| < 1 at x = xo where xo, is some
initial guess
• Then the iterative method is applied by successive approximations
given by xn = 𝜑(xn – 1), that is, x1 = 𝜑(xo), x2 = 𝜑(x1) and so on.

 Find the root of the equation x3 + x2 – 1 = 0 on the interval [0,1]

up to 4 decimal places.

[Link]
Iteration Method…
Solution:
Given f(x) = x3 + x2 – 1 = 0
26
Newton-Raphson Method
Newton-Raphson Method…
Newton-Raphson Method…
• a tangent is drawn at the point [x0, f(x0)]
• cuts the x-axis at x1
• drawing another tangent at [x1, f(x1)],
which cuts the x-axis at x2
• continued till the desired accuracy is
achieved

[Link]
Algorithm of N-R Method

[Link]
31
32
Advantages and Disadvantages of N-R Method
Advantages: Disadvantages:
• Convergence- Fast • First derivative- difficult
• Guess- one only • Fails- first derivative=0
• Formulation- Easy • Sensitive- initial guess
• Formula- simple
• Behavior- easy to understand

[Link]
Failing of N-R Method
(i) If any of the approximations encounters a zero derivative (extreme point),
then the tangent at that point goes parallel to 𝑥-axis
(ii) Sometimes Newton-Raphson method may run into an infinite cycle or loop
(iii) In case of a point of discontinuity subsequent roots may diverge
Secant Method
• A serious disadvantage of the Newton – Raphson method is the
need to calculate 𝑓′ (𝑥) in each iteration. The situations where a
closed form for 𝑓′ (𝑥) is not available, secant method is suitable.

where 𝑥𝑛 and 𝑥𝑛−1 are the two approximations to the root. The iterative
formula for (𝑛 + 1)th approximation is given by
Secant Method..
The above formula can be written as,

Graphical:
Secant Method vs False Position
• Both use two initial estimates
• the latest estimate of the root replaces
whichever of the original values yielded in false
position
• two estimates always bracket the root in false
position; always convergent
• the secant method replaces the values in strict
sequence
• the two values can sometimes lie on the same
side of the root
• can be divergent
 Problem#01
*Use Bisection method to determine the drag coefficient c needed for a
parachutist of mass 68.1 kg to have a velocity of 40 m/s after free falling for
time t = 10 s. Note: The acceleration due to gravity is 9.81 m/s2
Problem#02
You are designing a spherical tank to hold water for a small village in a
developing country. The volume of liquid it can hold can be computed as

where V 5 volume (m3), h 5 depth of water in

tank (m), and R=the tank radius (m). If R = 3 m,
what depth must the tank be filled to so that it
holds 30 m3? Use three iterations of the Newton-
Raphson method to determine your answer.
Determine the approximate relative error after
each iteration.
Problem#01
Problem#02
Matrices
Matrices…
Matrices…
Matrices…
Matrices…
Properties
Matrices…
Upper Triangular Matrix

Lower Triangular Matrix

 Matrices…
Transpose of Matrix
 Matrices…
Inverse of Matrix
Matrices…
Matrices…
by combining the matrices for each of the systems
Matrices…
Matrices…
Solution of Systems of Linear Equations
Simultaneous linear equations
Solution of Systems of Linear Equations
The solution is obtained by
• Graphical method- A graphical solution is obtainable for two equations
• Cramer’s rule
• Elimination of unknowns
Prob.: Use the graphical method to solve

Soln: Let x1 be the abscissa. Solve 1st

Eq. for x2:
Cramer’s Rule
This is best suited to small number of equations.
The determinant can be illustrated for a set of three equations:
Cramer’s Rule…

Similar for x2 with the replacement of second column.

Elimination of Unknowns
The solution is obtained by

Direct methods Indirect methods

Gauss Gauss
Elimination Jacobi

Gauss Gauss
Jordan Seidel
Direct and Indirect/Iterative Methods
Direct methods are those in which
• Computation- in a finite number of steps
• Solution- exact
• The amount of computation- specified in advance
• Accuracy- independent
Indirect/iterative methods are those in which
• Computation- infinite number of steps
• Solution- approximate
• The amount of computation- an improved solution with each step of iteration
• Accuracy- depends on the number of iterations performed
Gauss-Elimination Method
One of the most popular techniques for solving simultaneous linear equations
of the form
[A][X] = [C]
Consists of 2 steps
1. Forward Elimination of Unknowns.
2. Back Substitution
Forward Elimination…
Step 1. Elimination of x1 from the second and third equations

Step 2. Elimination of x2 from the third equation

Step 3. From third equation x3 is known. Using x3 in the second equation x2 is

obtained. using both x2 And x3 in the first equation, the value of x1 is obtained.
Problem
Gauss-Elimination Method
Solve the problem:

Solution:
Gauss-Elimination Method…
Gauss-Elimination Method…
Gauss-Jordan Method
Solve the problem:

Solution:
 Gauss-Jordan Method…

R2/1.6667
R1=R1-R2/10
Gauss-Elimination and Gauss-Jordan Method
Solution of Systems of Linear
Equations

Traditional Method Matrix Method

Matrix Method

Row Echelon Method Upper Triangular

Reduced Row Echelon Identity Matrix
Method
Gauss-Elimination Method
Gauss-Elimination Method…
Gauss-Elimination Method…
Gauss-Jordan Method
Gauss-Jordan Method…
Gauss-Jordan Method…
Gauss-Jordan Method…
Pitfalls of Elimination Methods

• Division by Zero- elimination and the back-substitution phases

Pitfalls of Elimination Methods
Pitfalls of Elimination Methods
• Round-Off Errors- large number of equations
• Ill-Conditioned Systems
Pitfalls of Elimination Methods
• Round-Off Errors- large number of equations
• Ill-Conditioned Systems

Substitution of the results into the original equations would alert you to
the problem
Gauss-Jacobi/Jacobian Method
For a system of linear equations:

Solution to this system of equations Ax = B

[Link]
Gauss-Jacobi/Jacobian Method…
solve equation 1 for x1, equation 2 for x2 and so on equation n for xn

substituting these values only to the right hand side of the

above equations

[Link]
Gauss-Jacobi/Jacobian Method…
Substituting these values only to the right-hand side of the above
equations, First approximation. Continue up to accuracy

Convergence of Approximations
The system of equations is diagonally dominant

[Link]
Gauss-Jacobi/Jacobian Method…

[Link]
Gauss-Seidel Method

[Link]
Matrix Form-Jacobi Method
Matrix Form-Jacobi Method
Gauss-Seidel Method
The upward velocity of a rocket is given at three different times in the
following table Time (sec) Velocity (m/s)
5 106.8
8 177.2
12 279.2
The velocity data is approximated by a polynomial as

Find the values of 𝑎1, 𝑎2, 𝑎𝑛𝑑 𝑎3 using the Gauss-Seidel method. Assume an
initial guess of the solution as

and conduct two iterations.

[Link]
Gauss-Seidel Method
Gauss-Seidel Method
Gauss-Seidel Method
Problem
Suppose that a team of three parachutists is connected by a weightless cord while free-falling at a
velocity of 5 m/s
Problem
Interpolation
Interpolation: derive value between two points having a prescribed value
Extrapolation: predicting the value or state of a variable based on its
current state
Polynomial Interpolation
General formula for an nth-order polynomial is

(a) First-order (linear) connecting two points

(b) Second order (quadratic or parabolic) connecting three points
(c) Third-order (cubic) connecting four points
Newton’s Divided-difference Interpolating Polynomials
Linear Interpolation:
Using similar triangles

linear-interpolation formula
 Quadratic Interpolation
The error in linear interpolation resulted from our approximating a curve with a
straight line
AA particularly convenient form for this purpose is

This can be re-written

Quadratic Interpolation..
 General Form of Newton’s Interpolating Polynomials
We can generalize the linear and quadratic interpolation formulas for an nth order
polynomial passing through n+1 points

Data points required:

We use these data points and the following equations to evaluate the coefficients:
General Form of Newton’s Interpolating Polynomials..
The first finite divided difference is represented generally as

The second finite divided difference is represented generally as

nth finite divided difference is represented generally as

General Form of Newton’s Interpolating Polynomials..

Substituting into general formula

Newton’s divided-difference interpolating polynomial

Problem
The following logarithmic table is given.
Newton’s Forward Difference for Equally Spaced Data
Forward Difference for Equally Spaced Data..
Forward Difference..
Newton’s divided-difference interpolating polynomial

b3

bn
General Form..

Newton’s Forward Interpolation Formula

Forward Difference Table
Backward Difference for Equally Spaced Data
General Form
We choose the form
b0 b1 b2
b3

bn
Backward Difference Formula

Newton’s Backward Interpolation Formula

Backward Difference Table
Problem
Central Difference Formulae
These are suited for interpolation near the middle value
Gauss’ Central Difference Formulae
Gauss’ Forward Difference Formulae
Gauss’ Forward Central Difference Formulae
Proof:
Gauss’ Forward Central Difference Formulae…
Proof:
Gauss’ Forward Central Difference Formulae…
Proof:
Gauss’ Forward Central Difference Formulae…
Proof:
Gauss’ Forward Central Difference Formulae…
Proof:
Gauss’ Backward Central Difference Formula
Gauss’ Backward Central Difference Formula..
Gauss’ Backward Central Difference Formula..
Stirling’s Formula
Stirling’s Formula
Stirling’s Formula
1Find Solution using Stirling's formula
Bessel’s Formula
Bessel’s Formula
Bessel’s Formula
Bessel’s Formula
Bessel’s Formula
Find Solution using Bessel's formula
Lagrange Interpolation
Lagrange Interpolation…
Lagrange Interpolation…
Lagrange Interpolation…
Lagrange Interpolation…
Find Solution using Lagrange's Interpolation formula
Curve-fitting by Least Squares
Curve fitting- noise, general trend
Interpolation- curves directly through each point
Regression- a link between two variables: the
independent variable X and the dependent variable
Y

Applications are generally encountered:

Trend analysis-forecast dependent variable
Hypothesis testing- existing mathematical model is
compared with measured data
Curve-fitting by Least Squares
Fitting a Straight Line
Fitting a Straight Line…
Fitting a Straight Line…
Fitting a Straight Line…
Multiple Linear Least Square
Multiple Linear Least Square…
Multiple Linear Least Square…
Linearization of Nonlinear Relationships
o Linear regression provides a powerful technique for fitting the best line
to data, where the relationship between the dependent and
independent variables is linear
o But, this is not always the case, thus first step in any regression analysis
should be to plot and visually inspect whether the data is a linear model
or not

data is ill-suited
for linear
regression
Linearization of Nonlinear Relationships..
Three common examples and their linearization

All are expressed as

Linearization of Nonlinear Relationships..
Linearization of Nonlinear Relationships..
Linearization of Nonlinear Relationships..
Linearization of a Power equation and fit equation to
the data in table below using a logarithmic transformation of
the data.

Solution:
Linearization of Nonlinear Relationships..
Linearization of Nonlinear Laws…
Linearization of Nonlinear Laws…
Linearization of Nonlinear Relationships..
Linearization of a saturation-growth rate equation
to the data in table below.
Linearization of Nonlinear Relationships..
Linearization of Nonlinear Relationships
Curve Fitting by Polynomial
The least-squares procedure can be readily extended to fit the data to
a higher-order polynomial
Let us consider a second–order polynomial or quadratic
Polynomial Regression…
Taking the derivative of the above equation
Polynomial Regression…
Setting the equations equal to zero and rearrange

In matrix form:
Polynomial Regression…
Numerical Differentiation and Integration
Newton-Cotes Integration Formulas
Numerical Integration…
The Trapezoidal Rule
Numerical Integration…
The Trapezoidal Rule
Numerical Integration…
The Trapezoidal Rule
Numerical Integration
Numerical Integration…
Numerical Integration…
Numerical Integration…
Numerical Integration…
Numerical Integration…
Numerical Integration…
Numerical Integration…
Numerical Integration…
Numerical Integration…
Numerical Integration…
The cross-sectional area of a channel can be computed as
Numerical Integration…
A wind force distributed against the side of a skyscraper is measured as

Compute the net force and the line of action due to this distributed wind.
Numerical Integration…
Numerical Differentiation
Numerical Differentiation…
Numerical Differentiation…
Numerical Differentiation…
Numerical Differentiation…
Numerical Differentiation…
Numerical Differentiation…
Numerical Differentiation…
Solution of Ordinary Differential Equation
• no "nice" algebraic solution of differential equations
• Even if we can solve some differential equations algebraically, the solutions
may be quite complicated

[Link]
Solution of Ordinary Differential Equation

[Link]
Solution of Ordinary Differential Equation

This gives us a reasonably good approximation if we take plenty of terms, and if the
value of h is reasonably small.

[Link]
Solution of Ordinary Differential Equation

[Link]
Solution of Ordinary Differential Equation

[Link]
Solution of Ordinary Differential Equation

[Link]
Solution of Ordinary Differential Equation
Solution of Ordinary Differential Equation
Solution of Ordinary Differential Equation
Solution of Ordinary Differential Equation
Solution of Ordinary Differential Equation
Solution of Ordinary Differential Equation