Notes and course material for MATH50003 Numerical Analysis (2023–24)
Lecturer: Dr Sheehan Olver
Office hour: Mondays 11am, Huxley 6M40
- I.1 Rectangular Rule and I.2 Divided Differences
- I.3 Dual Numbers and I.4 Newton's method
- II.1 Integers and II.2 Reals
- II.3 Floating Point Arithmetic and II.4 Interval Arithmetic
- III.1 Structured Matrices and III.2 Differential Equations via Finite Differences
- III.3 Cholesky Factorisations and III.4 Polynomial Regression
- III.5 Orthogonal and Unitary Matrices and III.6 QR Factorisation
- IV.1 Fourier Expansions and IV.2 Discrete Fourier Transform
- IV.3 Orthogonal Polynomials and IV.4 Classical Orthogonal Polynomials
- IV.5 Gaussian Quadrature
- Mock computer-based exam (Solutions)
- Computer-based exam (Solutions)
- Mock final exam (2(c/d) are not relevant.) (Solutions)
- Final exam (pen-and-paper, 80% of term mark): 7 May 2024, 10:00–13:00
- MATH50003 Introduction to Julia
- The Julia Documentation
- Ben Lauwens, Think Julia
- The Julia–Matlab–Python Cheatsheet
- Tobin A. Driscoll & Richard J. Braun, Fundamentals of Numerical Computation, Julia Edition, Chapters 1–3, 7
- Nicholas J. Higham, Accuracy and Stability of Numerical Algorithms, Chapters 1–3
- Michael L. Overton, Numerical Computing with IEEE Floating Point Arithmetic, Chapters 2–6
- Lloyd N. Trefethen & David Bau III, Numerical Linear Algebra, Chapters 1–4
- Lloyd N. Trefethen, Approximation Theory and Approximation Practice, Chapters 1–4, 17–19
- David A. Ham, Just enough Git to get by
Broadly speaking, numerical analysis is the study of approximating solutions to continuous problems in mathematics, for example, integration, differentiation, and solving differential equations. There are three key topics in numerical analysis:
- Design of algorithms: discuss the construction of algorithms and their implmentation in software.
- Convergence of algorithms: proving under which conditions algorithms converge to the true solution, and the rate of convergence.
- Stability of algorithms: the study of robustness of algorithms to small perturbations in data, for example, those that arise from measurement error, errors if data are themselves computed using algorithms, or simply errors arising from the way computers represent real numbers.
The modern world is built on numerical algorithms:
- Fast Fourier Transform (FFT): Gives a highly efficient way of computing Fourier coefficients from function samples, and is used in many places, e.g., the mp3 format for compressing audio and JPEG image format. (Though, in a bizarre twist, GIF, a completely uncompressed format, has made a remarkable comeback.)
- Singular Value Decomposition (SVD): Allows for approximating matrices by those with low rank. This is related to the PageRank algorithm underlying Google.
- Stochastic Gradient Descent (SGD): Minima of high-dimensional functions can be effectively computed using gradients in a randomised algorithm. This is used in the training of machine learning algorithms.
- Finite element method (FEM): used to solve many partial differential equations including in aerodynamics and weather prediction. Firedrake is a major project based at Imperial that utilises finite element method.
This is not to say that numerical analysis is only important in applied mathematics. It is playing an increasing important role in pure mathematics with important proofs based on numerical computations:
- The Kepler conjecture. This 400 year conjecture on optimal sphere packing was finally proved in 2005 by Thomas Hales using numerical linear programming.
- Numerical verification of the Riemann Hypothesis. It has been proved that there are no zeros of the Riemann zeta function off the critical line provided the imaginary part is less than 30,610,046,000.
- Steve Smale's 14th problem on the stability of the Lorenz system was solved using interval arithmetic.
Note these proofs are rigorous: as we shall see it is possible to obtain precise error bounds in numerical calculations, and the computations themselves can be computer-verified (a la The Lean Theorem Prover). As computer-verified proofs become increasingly important, the role of numerical analysis in pure mathematics will also increase, as it provides the theory for rigorously controlling errors in computations. Note that there are many computer-assisted proofs that do not fall under numerical analysis because they do not involve errors in computations or approximation or involve discrete problems, for example, the proof the Four Colour Theorem.
In this course we will use the programming language Julia. This is a modern, compiled, high-level, open-source language developed at MIT. It is becoming increasingly important in high-performance computing and AI, including by Astrazeneca, Moderna and Pfizer in drug development and clinical trial accelleration, IBM for medical diagnosis, MIT for robot locomotion, and elsewhere.
It is ideal for a course on numerical analysis because it both allows fast implementation of algorithms but also has support for fast automatic-differentiation, a feature that is of increasing importance in machine learning. It also is low level enough that we can really understand what the computer is doing. As a bonus, it is easy-to-read and fun to write.
To run Julia in a Jupyter notebook on your own machine:
- Download Julia v1.10
- Open the Julia app which will launch a new window
- Install the needed packages by typing (
]will change the prompt to a package manager):
] add IJulia Plots ColorBitstring SetRounding- Build Jupyter via
] build IJulia- Launch Jupyter by typing
using IJulia
notebook()- Download the labs to the same folder as the Jupyter notebook is running.