Mekelle University- MIT

Computational Methods
Lecture slides
2025 E.c/- 2017/2018 E.c Semester I/II

Lectured by: Knife Teka([Link].)

Computational Methods and Numerical Analysis

What is Computational Methods :

● Computational methods are techniques used to solve mathematical problems using

algorithms and computers. Since many real-world problems cannot be solved analytically
(with exact formulas), computational methods provide approximate but accurate-enough
solutions through numerical techniques.
● What is Numerical Analysis : A branch of mathematics that Studies accuracy of
approximations, Focuses on efficiency in computation. It is Foundation of many computational
methods.

Typical examples of Computational methods in Engineering & Technology :

● Root finding
● Solving linear/nonlinear equations
● Numerical differentiation & integration
● Optimization methods
● Simulation of real-world systems
Application of Root findings in ENGINEERING & TECHNOLOGY

❖ Computing: Numerical solvers in simulations.

❖ Robotics: Kinematics & dynamics equations.
❖ Image Processing: Edge detection, reconstruction.
❖ GIS: Coordinate transformations, terrain models.
❖ Signal Systems & Control: Poles, zeros, stability.
❖ Engineering: Fluid flow, circuits, structural analysis.

Test 1: Write Graphics Design & Generative AI Applications for root finding. [2 pages]
Root finding & Types

What is root finding in Mathematical Equation :

⇒ A root of an equation is a value of x such that: f(x) = 0

How many types of Equations :

⇒ Linear equation a form of f(x) = ax + b. Root x = -b/a ,

⇒ Nonlinear can be divided in to three:

(a) Polynomial Equations
Example: x³ − 4x + 1 = 0

Other examples:

● Quadratic: x² + 5x + 6 = 0

Higher-order: x⁵ − 2x³ + x − 7 = 0
(b) Trigonometric Equations
Example: sin(x) − x/2 = 0

Other examples:

● tan(x) = x
● cos(x) = e⁻ˣ

(c) Transcendental Equations

Example: eˣ − ln(x) = 0

Other examples:

● e⁻ˣ = x
● ln(x) + x² = 0
● x = cos(x)
Method of solving nonlinear equations

❖ Bisection Method :
➢ Xmid shit to left or right. f(a).f(b) is -ve.

❖ Newton-Raphson Method

❖ Secant Method

❖ Fixed Point Iteration

These are iterative method for approximating.

Examples of root finding & types:
❖ Find root/s of the equation by yourself : x³ − 4x + 1 = 0
❖ Find root/s of the equation by Bisection, Secant, Newton raphson.

Degree 3 polynomial cross X- axis at 3 points.

Find the other roots as well.
The 3 roots

● x1≈−2.1149
● x2≈0.2541
● x3≈1.8608

But, how ?

Let we check (a,b ) interval: [-3, -2] the [-2, 0] , [0, 1], [1, 2]
 Assignment
❖ Cardanos & Ferrari’s methods : Write down their formula. Are these methods
used for degree 5+ polynomial? Which method is good for all degree polynomial.
What happen the Oscillation & slope when degree increases?

9
Newton Raphson Method.

Interval [0, 1] , with Initial Guess X0= 0. The required thing is F’(Xn) must be not Zero.

Converges to 0.25
after 3 steps
Secant Method.

Interval [0, 1]

Converges to 0.25
after 6 steps
HOW about to other functions
Why Computational with system of linear equations
The methods Gaussian Elimination (a direct
method) and the Jacobi Iteration (an iterative
method). These methods are the computational tools
used to actually find the unknown values (x) in these
systems. We need both direct and iterative methods
because no single technique is optimal for every
problem. Both are used to solve a system of linear
equations, Ax=b, but they are needed for different
reasons, primarily relating to the size and structure
of the coefficient matrix A.

E.g. The IT Department needs to purchase markers,

dusters, and staples to meet specific inventory needs.
They work with three suppliers, each providing a
different combination of these items per unit
purchased. We'll model this as a system of linear
equations and solve it using Gaussian elimination. The
goal is to determine how many units to buy from each
supplier to exactly meet the required quantities of 150
… Why Computational with system of linear equations
Interpretation for the IT Department: The department should purchase approximately 9 units from Supplier A, 2 units from Supplier B,
and 7 units from Supplier C (rounding to whole units for practicality). Verify the totals:

● Markers: 10(9)+15(2)+5(7)=90+30+35=155 10(9) + 15(2) + 5(7) = 90 + 30 + 35 = 155 10(9)+15(2)+5(7)=90+30+35=155 (slightly over

150).
● Dusters: 5(9)+10(2)+20(7)=45+20+140=205 5(9) + 10(2) + 20(7) = 45 + 20 + 140 = 205 5(9)+10(2)+20(7)=45+20+140=205 (slightly
over 200).
● Staples: 20(9)+10(2)+15(7)=180+20+105=305 20(9) + 10(2) + 15(7) = 180 + 20 + 105 = 305 20(9)+10(2)+15(7)=180+20+105=305
(slightly over 300).

This is close but may require adjustment (e.g., integer programming) for exact quantities or to account for practical constraints like whole
units.
Why Computational
➔ It transforms a mathematical problem into a numerical solution using
algorithms.
➔ It approximates a solution for a problem that might be too complex to solve
symbolically. Linear or nonlinear.
New Example Scenario

What if the IT Department needs to procure 7 types of office supplies: 120 markers, 100 dusters, 140 staples,
80 pens, 60 notebooks, 50 toner cartridges, and 70 cables. They source these from 7 suppliers, each providing
a unique combination of these items per unit purchased. The goal is to determine how many units to buy from
each supplier to meet these exact quantities. The system is modeled as 7 linear equations with 7 variables, and
we’ll solve it using the Jacobi method.
The need for both Direct
and Iterative methods
comes down to a
trade-off between
speed, memory, and
accuracy, which is
determined by the size
and strucure of the
coefficient matrix A.
Class work : Slove this system of
Linear equations in Gussuan & Jaccobi
Each equation uses only previous iteration
values : that’s what makes it the Jacobi method
(unlike Gauss–Seidel, which uses the newest
values as soon as they’re available).
Why Jacobi for This Example?

● Diagonal Dominance: The matrix is

strictly diagonally dominant,
ensuring Jacobi convergence.
● Large System: With 7 variables,
iterative methods like Jacobi are
computationally simpler than
Gaussian elimination O(n3) O(n^3)
O(n3) complexity, especially for
sparse or structured matrices.
● Approximation Needs: If the IT
Department only needs an
approximate solution (e.g., for
planning), Jacobi is efficient and can
stop early.

Comparison with Previous Example

This example differs from the previous one

by:

● Using different coefficients (e.g., 10,

12, 15, etc., vs. 5, 6, 7, etc.).
● Different right-hand side values (120
100, 140, etc., vs. 100, 120, 150, etc.).
 Homework 5% - Numerical Computing

● Problem: Predicting Temperature

Distribution in a Metal Rod (Finite
Difference Method - FDM)
● Problem Description: A 1D metal rod (length

L= 10 cm) is heated at one end at 100°C while

the other end is kept at 0°C. We assume
steady-state heat conduction (temperature
does not change with time).

⇒ DO this in python google colab

 Convergence - Numerical Computing
●
Interpolation and curve fitting:

Let’s see the following:

Regression versus Curve fitting versus Interpolation?

Classification assigns an object to a

category (label).
→ You get a discrete answer (yes/no,
cat/dog, type A/type B).

Regression predicts a numerical value for an

object.
→ You get a continuous answer (2.3, 78.9,
1024.5, etc.).
 No. Method Name Ease Min. Data Distanc Main Idea / Notes
Level Points e
Needed (x-spaci
ng)

1⃣ Linear ⭐ 2 points Any Straight-line between

Interpolation Easiest (equal or two known points. Very
unequal) fast, low accuracy for
curved data.
Interpolation Methods
2⃣ Quadratic ⭐⭐ 3 points Any Fits a 2nd-degree
Interpolation polynomial (parabola) From Easier to Heavier
through three data
points. Better accuracy.

3⃣ Newton’s ⭐⭐⭐ 3 or more Equally Uses finite differences;

Forward / spaced efficient for tabulated
Backward data. Forward for start
Interpolation region, backward for end
region.

4⃣ Lagrange ⭐⭐⭐ n+1 points Unequal Single polynomial fitting

Interpolation ⭐ ly all points; accurate but
spaced computationally heavier
for many points.

5⃣ Cubic Spline ⭐⭐⭐ ≥ 4 points Any Piecewise cubic

Interpolation ⭐⭐ polynomials ensure
Heaviest smoothness; very
accurate for smooth
Assignment 3:
1. Discuss geospatial interpolation with its formulas & demos.
2. Find function modeling for random number in AVIATOR game
Scenario: Fuel Consumption Analysis for a Delivery Truck
Situation:
A logistics company is analyzing the fuel efficiency of their delivery trucks. They
have empirical data showing fuel consumption at specific speeds, but need to
estimate consumption at intermediate speeds to optimize delivery routes and save
costs.

Known Data Points:

The fleet manager has measured fuel consumption (in liters per 100 km) at these
speeds:

Speed (km/h) Fuel Consumption (L/100km)

60 12.5
80 14.0
100 16.5
120 20.0
Problem:
The company wants to determine the most fuel-efficient speed for highway
driving. They specifically need to know the fuel consumption at 90 km/h and 110
km/h to compare different driving strategies.
Interpolation :
Interpolation is a mathematical technique to estimate unknown values that fall between known data points.
It constructs a continuous function from discrete samples, allowing prediction of intermediate values.
Formula (General Idea):
Given points (x0,y0), (x1,y1), ..., (xn,yn),
find f(x) such that f(xi) = yi, and use f(x) for any x in the range.
Why use it?
- Data is often sampled at discrete points.
- We need values in between for accuracy, visualization, or computation.

Application Areas:

⇒ Pixel Color Interpolation (Bilinear Interpolation)

⇒ Sensor Data with Gaps Like Temperature Distribution in a Metal Plate
⇒ Perlin Noise in Procedural Generation (Games, Terrain)-->
Interpolate between random gradient values at grid points.
⇒ Sound Wave Resampling
⇒ Animation Keyframe
Random Gradient Texture
Types of Interpolations with their formulas:
Can we solve this with Linear interpolation:
Speed (km/h) Fuel Consumption (L/100km)
60 12.5
80 14.0
100 16.5
120 20.0
Problem:
The company wants to determine the most fuel-efficient speed for highway driving. They specifically need to know the fuel
consumption at 90 km/h and 110 km/h to compare different driving strategies.
Can we use Quadratic interpolation for
estimating 90km/h using these 3 points:

● (80, 14.0)
● (100, 16.5)
● (120, 20.0)

The answer is Yes. See slide number 31

Cubic Spline Interpolation Spline Cubic Polynomial Interpolation - General Form
means: Requires exactly 4 data points (x₀,y₀), (x₁,y₁), (x₂,y₂),
➢ We have 3 separate
(x₃,y₃): to generate ONE general P₃(x) = a₀ + a₁x + a₂x²
functions: S₁(x), S₂(x), S₃(x)
➢ Each works only on its own + a₃x³
interval Coefficients determined by:
➢ They connect smoothly at a₀ + a₁x₀ + a₂x₀² + a₃x₀³ = y₀
the data points a₀ + a₁x₁ + a₂x₁² + a₃x₁³ = y₁
Cubic means: a₀ + a₁x₂ + a₂x₂² + a₃x₂³ = y₂
➢ Each Sᵢ(x) has the form: a +
b(x-xᵢ) + c(x-xᵢ)² + d(x-xᵢ)³
a₀ + a₁x₃ + a₂x₃² + a₃x₃³ = y₃
➢ Highest power is x³ (cubic Key properties:
term) ● Single polynomial through all 4 points
➢ Contains x² and x³ terms, not ● Degree = 3 (cubic)
just linear ● Global interpolation (not piecewise)
Requires minimum 2 data points Difference from Cubic Spline:
(would be linear). For 4 data points: ● Cubic Polynomial: One polynomial for all points
produces 3 cubic polynomials. For n+1 ● Cubic Spline: Divides into multiple piecewise
data points: produces n cubic cubic polynomials (3 splines for 4 points)
polynomials ● Cubic Polynomial is global, Cubic Spline is
piecewise
We can also want to solve cubic spline interpolation for the data: (80, 14.0), (100, 16.5), (120, 20.0), (140, 25.0)
 Class Exercise:

Medical Scenario: Patient Heart Rate Monitoring

Data Points: (Time in minutes, Heart Rate in BPM)
● (0, 72), (5, 85), (10, 78), (15, 92), (20, 88)
Problem: Estimate heart rate at 7 minutes and 13 minutes?
Lagrange, Hermite interpolations with IVP, and ODE
Concepts
Core Idea: Find a single polynomial P(x) of the
minimum degree that passes through every
given data point.

⇒ Lagrange Interpolation is a numerical method used

to find a polynomial that exactly passes through a given
set of data points.

⇒ Gives a single polynomial P(x) of degree n for n+1 data

points.

⇒ Exact fit at all given points. Easy to apply for small data
sets.

Limitations:
For many data points, the polynomial becomes very
high-degree and oscillates (especially near the ends) — this
is called Runge’s phenomenon.

Recomputing the polynomial if a new data point is added.

Likewise the sum notation, the
product notation ∏ (Pi) used to
multiply all items.

The given points “activates”

its own data point (Xi,Yi) and is
zero at all other data points.

In short Li(x) is weighting

polynomial for point i, that
connects Yi correctly.
Runge’s phenomenon refers to the
large oscillations (wiggly behavior) that
occur when using high-degree
polynomial interpolation over equally
spaced points.

Lagrange: Good for small, exact

interpolation.

Spline: Better for smooth, stable

interpolation over many points.
Exercise: For data points
(X0,Y0)=(1,2),
(X1,Y1)=(2,3),
(X2,Y2)=(4,1),
(X3,Y3)=(5,4).
Find general polynomial.
In Lagrange interpolation:

● If you have n + 1 data points, the interpolation polynomial will

have degree ≤ n.

● So for 4 data points (X0,X1,X2,X3), n=3⇒polynomial degree 3

Hermite Interpolation
Home work : Compare graph
of these data points:
(-5, 3), (0, 9), (3, 1) , (7, 5)
By:
❖ Lagrange
❖ Cubic spline
❖ Hermite ?

SLOPE constraint, Co