### Numerical Linear Algebra - M1 - 8EC

PREREQUISITES
Any student who is seriously interested in this course should have:

a) a solid mathematical background, the emphasis of the course is on sound mathematical reasoning and on proving theorems;

b) linear algebraic capabilities that significantly surpass those that are taught in a first-year Bachelor course;

c) knowledge of the principles of numerical mathematics and have programming skills to comfortably work in MatLab.

[Why Matlab? Exercises, sample codes, assignments have all been formulated with Matlab.]

Ideally this means that in the Bachelor, the student has passed:

6 EC Linear Algebra;
6 EC Programming (preferably Matlab) and Algorithms;
6 EC Numerical Analysis;
6 EC Numerical Linear Algebra or 6 EC Representation Theory.

Elaborating on this, we expect that students have experience with:

[see wikipedia] proofs: induction; epsilon-delta; contradiction;
[see wikipedia] stability of algorithms, condition of maths problems;
[see wikipedia] matrix groups: general linear, orthogonal, unitary;
[see wikipedia] reflections (in particular in hyperplanes);
[see wikipedia] rotations (in particular in 2-d subspaces);
[see wikipedia] (bi-)orthogonalization (modified Gram-Schmidt);
[see wikipedia] matrix decompositions: lu, qr, chol, eig, svd, schur;
[see wikipedia] linear least squares problems;
[see wikipedia] Hessenberg matrices and Hessenberg reduction.

Student knows algorithms for linear systems/eigenvalue problems:

[see wikipedia] Gauss-Seidel method, Jacobi method;
[see wikipedia] Power Method; Rayleigh Quotient Iteration;
[see wikipedia] The QR-iteration for eigenvalues.

These above prerequisites can for example be obtained from:

L.N. Trefethen and D. Bau (1997). Numerical Linear Algebra, SIAM Society for Industrial and Applied

The first two weeks of the course the most important prerequisites will be reviewed.

Disclaimer: Reviewing is not the same as first-time teaching of material! If you have not studied these concepts before, the review may well be much too quick and too less detailed for you to follow.

AIM OF THE COURSE
This course is a first introduction into the main aspects of iterative methods

to approximate the solutions of finite- but high-dimensional linear equations,
eigenvalue problems. Many of these methods are based on the clever reduction of
the problem to an approximating problem of much smaller
dimensions. The smaller problem yields an approximate solution of the original
problem but simultaneously provides information how to set up the next reduced
problem whose corresponding approximation is better than the previous one. This
leads to a sequence of smaller problems that need to be solved in order to get increasingly better approximations of the solution of the original problem.

The aim is to teach students how to approximate solutions of large scale linear
algebra problems by cleverly designed small scale linear algebra problems, how
to analyse the approximation properties mathematically, and how to iplement the
corresponding methods in MatLab. Students are taught how to perform experiments
in MatLab and how to discuss their outcomes.

The focus will be on mathematical theorems and proofs. Instead of covering a
large number of algorithms, we study a smaller number of central algorithms in
greater detail, from defining mathematical principles via algorithms to their
efficient and stable implementation.

This course is part of Master Programmes in Mathematics and can be of added
value in the other MasterMath courses Parallel Algorithms, Systems and Control,
and Numerical Bifurcation Analysis of Large-scale systems. It also supplements
Numerical Methods for PDEs (stationary or time-dependent).

LECTURER
Jan Brandts, Korteweg-de Vries Institute for Mathematics, UvA