Foundations of numerical computing · Lecture 1

Why Numerical Methods?

When no formula exists, we compute the answer step by step: guess, improve, repeat, and stop when it is good enough.

Md Mahbub E Noor · Assistant Professor
CSE-3107 Numerical Methods · B.Sc. 3rd Year 1st Semester
Department of CSE, University of Barishal

Today's goals

Explain why many real problems have no exact formula and need numerical methods
Describe the modelling pipeline: problem → model → algorithm → program → answer
Distinguish an analytical (exact) solution from a numerical (approximate) one
Run an iteration by hand and in code, and choose a sensible stopping rule
Compare bracketing and open iteration methods and their limitations

Today

A numerical method replaces "find the exact formula" with "compute a number that is as close as we need". Today: why, and the basic loop behind almost every method in this course.

Lab PCs: open the course folder and index.html. Everything works offline.

Foundations of numerical computing · you are here

L1 · Why Numerical Methods?→L2 · Floating-Point Numbers→L3 · Taylor Series and Order of Accuracy→L4 · Errors and Their Propagation→L5 · Conditioning and Stability

Md Mahbub E Noor

Lecture 1: Why Numerical Methods?

University of Barishal

2 / 17

Start here

The idea in one picture

Start with any reasonable guess for √2.Apply a rule that makes the guess better.Check: has the value stopped changing?Not yet, so go round the loop again.Each trip round the loop adds correct digits.Four trips: the digits have almost stopped moving.Two guesses in a row now agree to 5 decimals.Stop and report the answer. That loop is "iteration".

In plain words

A numerical method is a recipe of simple arithmetic steps, repeated
Each repeat (iteration) improves the answer a little
We stop when the answer is good enough for our purpose

New words today

algorithm: a finite list of steps a computer can follow
iteration: one trip round the loop
converge: the guesses settle towards one value
tolerance: how small a change we accept before stopping

Md Mahbub E Noor

Lecture 1: Why Numerical Methods?

University of Barishal

3 / 17

Many problems have no formula to plug into

Each of these is easy to state and has an answer, yet no finite formula gives it exactly.

Equation

Solve $x = \cos x$

No algebra isolates $x$ . The answer is $x \approx 0.739085$ , found only by computing.

Polynomial

Solve $x^5 - x - 1 = 0$

Abel (1824): there is no general formula for polynomials of degree 5 or more.

Integral

$\int_0^1 e^{-x^2}\,dx$

$e^{-x^2}$ has no elementary antiderivative, yet the area is a definite number ≈ 0.746824.

Differential equation

Pendulum $\theta'' = -\frac{g}{L}\sin\theta$

No formula for $\theta(t)$ in elementary functions; games and simulators step it forward numerically.

Large system

$A\mathbf{x} = \mathbf{b}$ with $10^6$ unknowns

Cramer's rule would need about $10^{6}!$ operations. Elimination or iteration is the only way.

Data

Fit a line to 10,000 points

The data have noise; no line passes through all points. We compute the best line (least squares).

Md Mahbub E Noor

Lecture 1: Why Numerical Methods?

University of Barishal

4 / 17

Analytical vs numerical solution

Analytical (exact)

A formula or symbolic expression
Exact: $x = \frac{-b \pm \sqrt{b^2-4ac}}{2a}$
Works for every input of that form at once
Often impossible for real problems
Example: $\int_0^1 x^2\,dx = \tfrac{1}{3}$

vs

Numerical (approximate)

An algorithm: a finite list of arithmetic steps
A number: $x \approx 0.739085$
Must be re-run for each new input
Works on almost any problem a computer can evaluate
Comes with an error we must estimate and control

An algorithm, an error estimate and a stopping rule: those three things together make a numerical method.

Md Mahbub E Noor

Lecture 1: Why Numerical Methods?

University of Barishal

5 / 17

The modelling pipeline

Numerical methods sit in the middle of every computational project. Errors can enter at every arrow.

Real problemHow hot will this CPU get?

→

Mathematical modelHeat equation, material constants

→

Numerical methodFinite differences, an iteration

→

ProgramPython, C, NumPy

→

Result + check87 °C ± 2 °C. Does it match a measurement?

Modelling error

The model ignores something real (air flow, friction).

Truncation error

The method stops early: finite steps instead of an infinite process. This course.

Round-off error

The computer keeps only about 16 digits. Lecture 2.

Md Mahbub E Noor

Lecture 1: Why Numerical Methods?

University of Barishal

6 / 17

Where numerical methods run every day in CSE

Machine learning

Training = optimisation

Gradient descent takes thousands of small steps downhill on a loss function. That is Lecture 25.

Graphics and games

Ray tracing and physics

Where does a light ray hit a curved surface? A root-finding problem (Lecture 9). Game physics steps ODEs with Euler-type methods (Lecture 21).

Speech and signals

Filters and the FFT

Speech enhancement fits filters by least squares (Lecture 23); spectra come from numerical integration and the FFT.

Web search

PageRank

Google's original ranking solves a linear system with billions of unknowns by repeated iteration (Lecture 14).

Navigation

GPS position

Your phone solves a nonlinear system of 4 equations (distance to satellites) with Newton's method (Lecture 10).

Data science

Regression and interpolation

Trend lines, filling missing sensor values, smooth curves through points (Lectures 15–18 and 23–24).

Md Mahbub E Noor

Lecture 1: Why Numerical Methods?

University of Barishal

7 / 17

The core idea: iteration

Start with a guess, apply a rule that improves it, repeat.

To find $\sqrt{N}$ : if $x$ is too big, then $N/x$ is too small, so average them
Rule: $x_{k+1} = \tfrac{1}{2}\left(x_k + \dfrac{N}{x_k}\right)$ (Babylonian / Heron's method, about 1800 BC)
Every step uses only $+$ , $\div$ and $\times\tfrac12$ : things a computer does well
Press Next step: the number of correct digits roughly doubles each time

Md Mahbub E Noor

Lecture 1: Why Numerical Methods?

University of Barishal

8 / 17

By hand: $\sqrt{2}$ starting from $x_0 = 1$

Problem 1Use

x_{k+1} = \tfrac{1}{2}(x_k + 2/x_k)

with

x_0 = 1

. Stop when two successive values agree to 4 decimal places.

1

x_1 = \tfrac12\left(1 + \tfrac{2}{1}\right) = \tfrac12(3) = 1.5

2

x_2 = \tfrac12\left(1.5 + \tfrac{2}{1.5}\right) = \tfrac12(1.5 + 1.333333) = 1.416667

3

x_3 = \tfrac12\left(1.416667 + \tfrac{2}{1.416667}\right) = \tfrac12(1.416667 + 1.411765) = 1.414216

4

x_4 = \tfrac12\left(1.414216 + \tfrac{2}{1.414216}\right) = 1.414214

;

\;|x_4 - x_3| = 0.000002 < 0.00005

, so stop

\sqrt{2} \approx 1.4142

(true value 1.41421356…). Four steps, using only arithmetic.

k	$x_k$	$\|x_k - x_{k-1}\|$
0	1.000000	—
1	1.500000	0.500000
2	1.416667	0.083333
3	1.414216	0.002451
4	1.414214	0.000002

Md Mahbub E Noor

Lecture 1: Why Numerical Methods?

University of Barishal

9 / 17

The same loop in Python and C

Press ▶ Run, then switch the tab to C and run again: same numbers
Change N to 10 and run
Change x (the first guess) to 1000: how many more steps?
Make tol 1e-20. What happens, and why? (Lecture 2)

Md Mahbub E Noor

Lecture 1: Why Numerical Methods?

University of Barishal

10 / 17

When do we stop iterating?

An iteration never reaches the exact answer, so we must decide when it is close enough.

Absolute change

|x_{k+1} - x_k| < \varepsilon

Relative change (scale-free)

\dfrac{|x_{k+1} - x_k|}{|x_{k+1}|} < \varepsilon

Residual (for f(x) = 0)

|f(x_{k+1})| < \varepsilon

Use relative change when $x$ may be very large or very small
A small change does not guarantee a small error, but for converging methods it is a good estimate
Always add a maximum number of iterations: if the method diverges, the loop must still end
"Correct to $d$ decimal places" means $|x_{k+1} - x_k| < 0.5 \times 10^{-d}$

Md Mahbub E Noor

Lecture 1: Why Numerical Methods?

University of Barishal

11 / 17

What makes a numerical method good?

Accurate

The error can be made as small as we need, and we can estimate it.

Efficient

Few operations per step and few steps. Cost matters when $n = 10^6$ .

Stable

Small round-off errors stay small instead of growing (Lecture 5).

Robust

Works for many inputs; fails loudly, not silently.

No method wins on all four. Bisection is robust but slow; Newton is fast but can fail. Choosing the method for the problem is the skill this course builds.

Md Mahbub E Noor

Lecture 1: Why Numerical Methods?

University of Barishal

12 / 17

Key summary

Types of iteration methods and their limitations

Family	Methods	Needs	Strength	Limitation
Bracketing	Bisection, False Position	An interval $[a,b]$ with $f(a)f(b)<0$	Always converges	Slow; needs a sign change; misses double roots like $(x-1)^2$
Open: fixed point	Iteration method $x = g(x)$	A rewrite $x = g(x)$ and $x_0$	Very simple	Converges only if $\|g'(x)\| < 1$ near the root
Open: Newton–Raphson	Tangent line	$f'(x)$ and $x_0$	Very fast (digits double)	Fails if $f'(x) \approx 0$ ; may diverge from a poor $x_0$
Open: Secant	Chord through last two points	$x_0$ , $x_1$ (no derivative)	Fast, no derivative	May diverge; division by $f(x_1)-f(x_0) \approx 0$
Linear systems	Jacobi, Gauss–Seidel	$A\mathbf{x}=\mathbf{b}$ , a starting vector	Cheap for huge sparse systems	Converges only for e.g. diagonally dominant $A$

Lectures 6–10 study each root-finding method in detail; Lecture 14 covers iterative methods for linear systems.

Md Mahbub E Noor

Lecture 1: Why Numerical Methods?

University of Barishal

13 / 17

Beyond the classroom

Where this shows up in CSE and machine learning

🧠

Training a neural network

Each epoch is one iteration $w_{k+1} = w_k - \eta \nabla L(w_k)$ . The stopping rule is a tolerance on the loss or a maximum number of epochs: exactly today's two tests.

🎮

Game physics at 60 frames per second

Every frame advances positions with a numerical ODE step. Too large a step and objects fly through walls: a stability failure.

📈

Recommendation and ranking

PageRank and many recommender systems repeat $x_{k+1} = Mx_k$ until the vector stops changing.

🔊

Speech processing

Pitch tracking finds roots of a correlation function; enhancement solves least-squares problems frame by frame.

Md Mahbub E Noor

Lecture 1: Why Numerical Methods?

University of Barishal

14 / 17

Practice

Practice problem

Problem 2"Why do we need to study numerical methods in CSE? Briefly describe different types of iteration methods and the limitations of each one of these."
Another wording: "Why are numerical methods considered indispensable in computer science, and how do they address challenges posed by mathematical functions that lack analytical solutions?"

How to write a complete answer

Open with a definition: an algorithm of finite arithmetic steps that computes an approximate answer with a controlled error
Give two or three concrete reasons with examples: no closed form ( $x=\cos x$ , quintics), huge systems, data with noise, ODEs
Name the families: bracketing (bisection, false position) and open (fixed point, Newton, secant)
One limitation each, in a small table
Finish with one CSE example (ML training, graphics, GPS)

Md Mahbub E Noor

Lecture 1: Why Numerical Methods?

University of Barishal

15 / 17

Checkpoint

Checkpoint · think, then discuss with your neighbourWhich one of these problems needs a numerical method?

ASolve

2x + 3 = 7

BSolve

x = \cos x

CArea of a circle of radius 3

DDerivative of

x^2

B. The others have exact formulas (

x=2

,

9\pi

,

2x

). For

x=\cos x

we iterate: try

x_{k+1} = \cos x_k

from

x_0 = 1

in the lab and watch it settle at 0.739085.

Md Mahbub E Noor

Lecture 1: Why Numerical Methods?

University of Barishal

16 / 17

Summary

Key points

Many problems (equations, integrals, ODEs, big systems, noisy data) have no exact formula
A numerical method = algorithm + error estimate + stopping rule
Iteration: guess → improve → check → repeat; Babylonian $\sqrt{N}$ doubles the correct digits each step
Stop on absolute or relative change, or residual, and always cap the iterations
Bracketing methods are safe but slow; open methods are fast but can diverge

Homework

By hand, find $\sqrt{5}$ with $x_0 = 2$ until 4 decimal places agree. Show the table.
In the lab, run $x_{k+1} = \cos x_k$ from $x_0 = 1$ . How many iterations until 6 decimals agree? Compare with Babylonian $\sqrt{2}$ .
Write a half-page answer to Problem 2 with your own CSE example.

Next lecture

Floating-point numbers. Why does $0.1 + 0.2 \ne 0.3$ in Python and C? How many digits does a computer really keep, and what is machine epsilon?

Md Mahbub E Noor

Lecture 1: Why Numerical Methods?

University of Barishal

17 / 17

Why Numerical Methods?

Today's goals

The idea in one picture

Many problems have no formula to plug into

Solve x=cos⁡xx = \cos xx=cosx

Solve x5−x−1=0x^5 - x - 1 = 0x5−x−1=0

∫01e−x2 dx\int_0^1 e^{-x^2}\,dx∫01​e−x2dx

Pendulum θ′′=−gLsin⁡θ\theta'' = -\frac{g}{L}\sin\thetaθ′′=−Lg​sinθ

Ax=bA\mathbf{x} = \mathbf{b}Ax=b with 10610^6106 unknowns

Fit a line to 10,000 points

Analytical vs numerical solution

Analytical (exact)

Numerical (approximate)

The modelling pipeline

Modelling error

Truncation error

Round-off error

Where numerical methods run every day in CSE

Training = optimisation

Ray tracing and physics

Filters and the FFT

PageRank

GPS position

Regression and interpolation

The core idea: iteration

By hand: 2\sqrt{2}2​ starting from x0=1x_0 = 1x0​=1

The same loop in Python and C

When do we stop iterating?

What makes a numerical method good?

Accurate

Efficient

Stable

Robust

Types of iteration methods and their limitations

Where this shows up in CSE and machine learning

Training a neural network

Game physics at 60 frames per second

Recommendation and ranking

Speech processing

Practice problem

Checkpoint

Summary

Solve $x = \cos x$

Solve $x^5 - x - 1 = 0$

$\int_0^1 e^{-x^2}\,dx$

Pendulum $\theta'' = -\frac{g}{L}\sin\theta$

$A\mathbf{x} = \mathbf{b}$ with $10^6$ unknowns

By hand: $\sqrt{2}$ starting from $x_0 = 1$