Numerical Methods & Scientific Computing: lecture notes
Numerical Methods & Scientific Computing: lecture notes
Dr Hailong Guo
July 21, 2020
Numerical Methods & Scientific Computing: lecture notes
1
Overview
2 MATLAB
3 Stochastic simulation
Pseudorandom numbers Simulations
Statistical errors
4 Errors
Floating point numbers Error propagation
5 Root-finding
6 Linear Systems
LU factorization Special matrices Matrix norms Error analysis
7 Data fitting
8 IVPs
Euler’s method
RK methods
Other MATLAB solvers
9 Good programming practice
Numerical Methods & Scientific Computing: lecture notes
Numerical Methods & Scientific Computing
A new syllabus in 2017 — a revision of MAST30028 Numerical & Symbolic Mathematics.
We study how to solve mathematical problems that cannot be done by hand using numerical methods.
Example
solve a large linear system of equations
Example
solve a complicated differential equation to give numerical values of solution at certain times, not formulae
• Demo
Numerical Methods & Scientific Computing: lecture notes
New topics
Since this subject now covers only numerical methods, not symbolic software, we get to cover more topics:
Example
use computer simulation to explore the behaviour of stochastic (probabilistic) models
Example
fit data to linear and nonlinear models
Example
an introduction to useful software engineering tools
Numerical Methods & Scientific Computing: lecture notes
Overview
What are Numerical Methods?
Numerical Methods also called
Computational Mathematics 620-381 before 2010 Numerical Analysis (includes proof of error properties) Scientific Computing
As a software platform, we use MATLAB. We also briefly show NumPy. Alternatives include: Octave, SciPad, Julia, C, Fortran, …
Numerical Methods & Scientific Computing: lecture notes
Overview
From ‘Trefethen’s Maxims’
There are three great branches of science: theory, experiment, and computation.
As technology advances, the ingenious ideas that make progress possible vanish into the inner workings of our machines, where only experts may be aware of their existence. Numerical algo- rithms, being exceptionally uninteresting and incomprehensible to the public, vanish exceptionally fast.
L.N.Trefethen, Oxford
Numerical Methods & Scientific Computing: lecture notes
Overview
Discrete or continuous?
Some mathematical problems are naturally discrete
Example
algebra (inc. linear algebra), graph theory, combinatorics, bioinformatics, pattern matching …
Some mathematical problems are naturally continuous
Example
analysis, integrals, limits, differential equations ….
Numerical Methods & Scientific Computing: lecture notes
Overview
More from Trefethen… ..
The big gulf in the mathematical sciences is between the continu- ous problems (and people) and the discrete ones. Most scientists and engineers are in the continuous group, and most computer scientists are in the discrete one.
Definition
Numerical analysis is the study of algorithms for the problems of
continuous mathematics
=⇒ not for the problems of discrete mathematics (graph theory, pattern matching, discrete optimization etc. → Computer Science)
Numerical Methods & Scientific Computing: lecture notes
Overview
What is it for?
Many BIG problems:
climate change modeling drug design salinity/pollution monitoring
require heavy ‘scientific computing’.
NOT (typically) bioinformatics — more discrete.
Numerical Methods & Scientific Computing: lecture notes
Overview
Where to find more…
Numerical methods are covered briefly in several other UoM subjects.
and more fully in one other subject:
ENGR30003 Numerical Programming for Engineers
More specialized subjects e.g. PDEs, optimization, CFD exist at Masters level.
Example
BMEN20001, COMP20005, PHYC20013
Example
MAST90026 Computational Differential Equations
Numerical Methods & Scientific Computing: lecture notes
Overview
Week 1: aim to cover
Errors in scientific computing (now)
Programming in MATLAB; 1D arrays (vectors) in MATLAB (Lab 1) Output in MATLAB; variable scope in MATLAB (Lecture 2)
Numerical Methods & Scientific Computing: lecture notes
Overview
Goals
We need mathematics to
1 understand the problem
2 construct an algorithm
3 prove it gives the answer (in principle)
4 estimate how long/ how much memory it takes
For many discrete problems, that’s all.
complexity
Numerical Methods & Scientific Computing: lecture notes
Overview
For continuous problems, also need to
approximate the continuous problem by a discrete one
— this produces truncation error
show that resultant errors stay small enough for a useful result — this property is called stability
Numerical Methods & Scientific Computing: lecture notes
Overview
Sources of error in scientific computing
Modeling error: does the model capture reality?
Measurement error: are the experiments/observations accurate?
Programming errors: does the program do what was intended?
Computational error: do the numerical results approximate the true mathematical solution?
Statistical error: for stochastic problems, there is unavoidable error due to randomness; how do we deal with that?
For deterministic models, we focus on Truncation error and Roundoff errors which together are the Computational error . Usually one of these is dominant.
Numerical Methods & Scientific Computing: lecture notes
Overview
Truncation error
arises because we need to approximate continuous objects (functions, integrals, DEs ..) by discrete ones (sums …)
Example
the dominant error in solving IVPs
Numerical Methods & Scientific Computing: lecture notes
Overview
Roundoff error
arises because we need to approximate real numbers by numbers we can store in computer
A good algorithm minimizes computational error and maximizes efficiency (possibly a tradeoff here).
Example
the only error in solving linear systems by direct methods
Numerical Methods & Scientific Computing: lecture notes
Overview
Statistical error
Arises because of randomness in stochastic models
Every realization of a stochastic process produces a different result
We have to average over many realizations to get average or distributional information. Then we can use statistical methods to estimate the statistical error.
The computational error is still present but may be dominated by statistical error, depending on the noise level.
Numerical Methods & Scientific Computing: lecture notes
Overview
Measures of error
Let xˆ be approximate value of x absolute error: e = xˆ − x
r e l a t i v e e r r o r : r = ( xˆ − x ) / x = e / x not useful if x = 0
a better measure if x can be large
N o t e : xˆ = x ( 1 + r )
Numerical Methods & Scientific Computing: lecture notes
Overview
Significant figures
A number correct to n decimal places has absolute error < 1/2 in nth decimal place =⇒ e < 0.5 × 10−n
Example
22/7 ≈ 3.14285714285 approximates π ≈ 3.14159265358 to 2 decimal places since e ≈ 0.00126448926735 < 0.5 × 10−2
A common measure of relative error is number of significant figures:
Mathematica uses Accuracy and Precision to denote absolute error and relative error, resp.
Example
NA ∼ 6.023 × 1023 is known to about 4 significant figures
Numerical Methods & Scientific Computing: lecture notes
Overview
How many significant figures do we need?
According to Trefethen:
No physical constants are known to more than around 11 digits, and no truly scientific problem requires computation with much more precision than this. (OK, throw in another 5 or 6 digits to counter the slow accumulation of rounding errors in very long calculations – using numerically stable algorithms, of course, without which you’re sunk in any precision.)
By contrast engineering accuracy = 2–3 digits
Numerical Methods & Scientific Computing: lecture notes
Overview
End of Lecture 1