A7: Numerical Analysis - Material for the year 2020-2021

We have updated our Undergraduate exams guidance in preparation for the Trinity Term examinations.

Please see our new webpages dedicated to TT exams.

2020-2021
Lecturer(s): 
Prof. Yuji Nakatsukasa
Course Term: 
Hilary
Course Lecture Information: 

16 lectures

Course Overview: 

Scientific computing pervades our lives: modern buildings and structures are designed using it, medical images are reconstructed for doctors using it, the cars and planes we travel on are designed with it, the pricing of "Instruments'' in the financial market is done using it, tomorrow's weather is predicted with it. The derivation and study of the core, underpinning algorithms for this vast range of applications defines the subject of Numerical Analysis. This course gives an introduction to that subject. It covers the basics of three key fields in the subject: Numerical Linear Algebra, Approximation Theory, and Numerical Solution of Differential Equations.

Through studying the material of this course students should gain an understanding of numerical methods, their derivation, analysis and applicability. They should be able to solve certain mathematically posed problems using numerical algorithms. This course is designed to introduce numerical methods - i.e. techniques which lead to the (approximate) solution of mathematical problems which are usually implemented on computers. The course covers derivation of useful methods and analysis of their accuracy and applicability.

The course begins with a study of methods and errors associated with approximation of functions which are described by data values (interpolation or data fitting). Following this we turn to numerical methods of linear algebra, which form the basis of a large part of computational mathematics, science, and engineering. Key ideas here include algorithms for linear equations, least squares, and eigenvalues built on LU and QR matrix factorizations. We also treat the singular value decomposition (SVD), a fundamental matrix decomposition of major importance in data science.

We then return to approximation of functions, and discuss key concepts in orthogonal polynomials and best L2 polynomial approximation, and cover the beautiful method of Gauss quadrature for numerical integration.

The final part of this course treats the numerical solution of initial value problems for ordinary differential equations (ODEs), which directly complements the theoretical study of these problems in Part A Differential Equations I. We discuss basic and advanced methods for their numerical solution, the fundamental concept of numerical stability, and culminate with Dahlquist’s theorem that consistency and stability imply convergence.

The course requires elementary knowledge of functions, calculus, linear algebra and ordinary differential equations.
Although there are no assessed practicals for this course, the tutorial work involves a mix of written work and computational experiments. Knowledge of a programming language such as Matlab or Python would be desirable, but many examples will be provided.

Learning Outcomes: 

At the end of the course the student will know how to:

Find the solution of linear systems of equations.
Compute eigenvalues and eigenvectors of matrices.
Compress matrices vie the SVD.
Approximate functions of one variable by polynomials and piecewise polynomials (splines).
Compute good approximations to one-dimensional integrals.
Numerically solve initial value problems for ODEs.
Understand the stability of the numerical methods employed.
Use computing to achieve these goals.

Course Synopsis: 

Lagrange interpolation [1 lecture]

Gaussian elimination, LU, QR factorisations, least-squares problems [3.5 lectures]

Eigenvalues: Gershgorin’s Theorem, symmetric QR algorithm, polynomial rootfinding via eigenvalues [3.5 lectures]

SVD and low-rank matrix approximation [2 lectures]

Best approximation in inner product spaces, orthogonal polynomials, Gauss quadrature [3 lectures]

Forward and backward Euler, trapezium rule, leapfrog, Runge-Kutta methods [3 lectures]

Linear multi-step methods and Dahlquist’s theorem [2 lectures]

Reading List: 

The main recommended book for this course are:

1) L. N. Trefethen and D. Bau, Numerical Linear Algebra (SIAM, 1997). (For Numerical Linear Algebra)

2) L. N. Trefethen, Approximation Theory and Approximation Practice (SIAM, 2012; extended edition 2020). (Highly recommended for Function Approximation)

3) E. Süli and D. F. Mayers, An Introduction to Numerical Analysis (CUP, 2003). Of which the relevant chapters are: 6, 7, 2, 5, 9, 11. (For ODEs; covers the subject broadly)