Numerical Linear Algebra (BSc)

Studiewijzer 2017/2018

Globale inhoud

This course covers how a number of standard linear algebra problems can be solved or numerically approximated in an efficient and stable way. As such, the course is not only valuable for students who aim to work outside the academic world, but also for those who wish to contribute to the theoretical developments that are still in progress. The charm of the course lies in two aspects. Firstly, the most obvious solution method is not necessarily the most efficient, and secondly, whilst designing an algorithm, one has to take into account its stability: although a computed solution to a problem usually does not solve that problem exactly, it should preferably solve a problem that is, in some norm, in some sense, close to the original problem (this will be made precise in the course). This can lead to surprising insights and results.

It is a common misconception that rounding errors are central in Numerical Linear Algebra. Although it cannot be denied that they play an important role, they are not fundamental. Indeedn it is also true that even if a computer were not to make any rounding error during all its computations, it still would not be able to compute eigenvalues or singular values of a larger matrix exactly (Abel-Ruffini Theorem). Thus, approximations and their error analysis are not just a consequence of the computer's finite precision arithmetic limitations, more often they are a mathematical necessity. 

The course treats a large part of the book ``Numerical Linear Algebra'' by L.N. Trefethen and D. Bau, a book used by graduate students at universities as Cornell, MIT, and Oxford. The first author is an influential contemporary numerical analyst. We refer to his personal website for parts of the book, and some interesting essays on the meaning of Numerical Analysis.

Topics to be covered: QR-decomposition using Gram-Schmidt, modified Gram-Schmidt, Givens rotations and Householder reflections, linear least-squares problems (full rank and rank-deficient), conditioning and stability, finite precision arithmetic, LU-decomposition with partial pivoting, Cholesky-decomposition, power method, inverse iteration, QR-iteration with shifts, bisection for eigenvalues, Sturm sequences, divide-and-conquer for eigenvalues, Jacobi method for eigenvalues, Golub-Kahan bidiagonalization.

Studiemateriaal

Literatuur

• Lloyd N. Trefethen and David Bau III: `Numerical Linear Algebra', SIAM Society for Industrial and Applied Mathematics, Philadelphia.

Overig

• A small number of hand-outs written by the lecturer.

Leerdoelen

The student

• can describe the following algorithms for linear algebra problems:  Classical Gram-Schmidt; Modified Gram-Schmidt; Householder-QR; Givens-QR; Least-squares using QR, Least-squares using Gauss' Normal Equations; Least-squares using SVD; LU-decomposition with partial pivoting; Cholesky-decomposition; reduction to Upper Hessenberg form; Power method; Inverse Iteration; QR-iteration with shifts; Bisection for eigenvalues; Jacobi method for eigenvalues; Divide-and-Conquer for eigenvalues; Golub-Kahan bidiagonalization;
• can prove and/or explain why the above algorithms produce (or converge to) the desired outcome;
• is able to implement the above algorithms on a computer, to experiment with the programs, and to analyze and critically comment their outcomes;
• is also able to perform the algorithms by hand in some very simple illustrative examples;
• knows how a computer performs elementary calculations (addition, subtraction, multiplication and division) on numbers and also which numbers are exactly representable within the computer;
• understands the concepts of `conditioning' and '(backward) stability' of problems and algorithms and is able to determine the conditioning of some simple linear algebra problems and the stability of some algorithms;
• grasps some new theoretical topics in linear algebra, such as the direct reduction to similar upper Hessenberg (or tridiagonal) form, and the direct orthogonal transformation to bidiagonal form of a matrix; understands the duality between power iteration and inverse iteration present in the QR-iteration.
• can prove perturbation bounds on eigenvalues and singular values.

Onderwijsvormen

• Hoorcollege
• Werkcollege
• Laptopcollege
• Zelfstudie

Lectures and exercise classes, some of which include Matlab-programming.

Verdeling leeractiviteiten

Academische vaardigheden

Using the Linear Algebra programming environment MatLab.

Aanwezigheid

Aanwezigheidseisen opleiding (OER-B):

• Van elke student wordt actieve deelname verwacht aan het onderdeel waarvoor hij/zij staat ingeschreven.
• Als een student door overmacht niet aanwezig kan zijn bij een verplicht onderdeel van het onderdeel, dient hij/zij dit zo snel mogelijk schriftelijk te melden bij de betreffende docent. De docent kan dan, eventueel na overleg met de studieadviseur, besluiten om de student een vervangende opdracht op te leggen.
• Het is niet toegestaan om verplichte onderdelen van een onderdeel te missen als er geen sprake is van overmacht.
• Bij kwalitatief of kwantitatief onvoldoende deelname, kan de examinator de student uitsluiten van verdere deelname aan het onderdeel of een gedeelte daarvan.
• Bij alle onderwijseenheden van jaar 1 en 2 is een student verplicht bij minimaal 80% van de werkcolleges en tutoraten aanwezig te zijn. Bovendien moet worden deelgenomen aan eventuele tussentoetsen en verplicht gesteld huiswerk. Als niet aan deze verplichting is voldaan, wordt de student uitgesloten voor de herkansing van de onderwijseenheid.

Aanvullende eisen voor dit vak:

Toetsing

The final grade for NLA is determined as follows. Consider:

• the grades T1 en T2 of both partial exams
• the grades M1, M2, M3, M4 of the Matlab assignments

Minimal requirements to pass are:

• T2 is at least 5.0;
• T1+T2 is at least 11.0;
• M1+M2+M3+M4 is at least 22.0;
• M4 is at least 5.0.

If you do not satisfy all four requirements, your final grade is the minimum of 5.0 and G, defined as

G = (1/3)(T1+T2)+(1/12)(M1+M2+M3+M4).

If you do satisfy the four requirements, and did not hand in any homework, your final grade is G rounded to halves, with the exception that 5.5 will (forcibly) not occur.

Homework bonus

Homework is graded by 0,1,2 or 3. Let H be the sum of the eight homework sets, then

E = G + (10-G)*(H/72)

and your final grade is E rounded to halves, with the exception that 5.5 will (forcibly) not occur.

Thus, if you score the maximum of 24 points for homework, you compensate one third of the difference between G and 10: it raises 5.5 to 7.0 and it raises 7.0 to 8.0.

Exam Resit

If T1+T2 < 11.0, or T2 < 5.0, you need to do the Exam Resit and score for it a grade T of at least 5.5.
2T then replaces T1+T2 in the definition of G.

No homework bonus will be assigned.

Replacing Matlab Assignment

Suppose that M1, M2, M3, M4 are such that M4 < 5.0 or M1+M2+M3+M4 < 22.0. Only if changing one of the scores for M1, M2, M3, M4 into 10 implies that all four minimal requirements above are satisfied, you may get one new Matlab assignment.

Its grade M will then replace M1, M2, M3, or M4 in the definition of G.

You can not get more than one Replacing Matlab Assignment. No homework bonus will be assigned.

No Show Formalities

The minimum score for T1 and T2 and each Mj is 1.0, also if you do not show up or do not hand in.

Not handing in homework scores 0 (logically).

Opdrachten

Matlab assignments

• four programming assignments

Onderstaande opdrachten komen aan bod in deze cursus:

•    Naam opdracht 1 : beschrijving 2
•    Naam opdracht 2 : beschrijving 1
•    ....

Fraude en plagiaat

Dit vak hanteert de algemene 'Fraude- en plagiaatregeling' van de UvA. Hier wordt nauwkeurig op gecontroleerd. Bij verdenking van fraude of plagiaat wordt de examencommissie van de opleiding ingeschakeld. Zie de Fraude- en plagiaatregeling van de UvA: www.uva.nl/plagiaat

Weekplanning

Rooster

Het rooster van dit vak is in te zien op DataNose.

Honoursinformatie

There is no honours extension of this course.

Aanvullende informatie

Students enrolling in this course should have a good grasp of Linear Algebra, good general computer programming abilities (preferably also in MatLab) and basic knowledge of Numerical Mathematics.

This corresponds to the following courses in the BSc Mathematics:

• Lineaire Algebra 1 (semester 1, year 1, from the book ``Lineaire Algebra'' by Igodt and Veys)
• Lineaire Algebra 2 (semester 2, year 1,from the Lecture Notes of Jan Brandts)
• Inleiding Programmeren voor Wiskundigen (semester 2, year 1, course by Andre Heck)
• Inleiding Numerieke Wiskunde (semester 2, year 1, from the Lecture Notes of Jan Brandts)
• Numerieke Analyse (semester 2, year 2, from the book ``An Introduction to Numerical Analysis'' by Suli and Mayers)

Contactinformatie

Coördinator

• dr. Jan Brandts

All details around this course can be found on the personal web page of the lecturer at: http://www.janbrandts.nl 

Follow the links ``teaching'' and ``numerical linear algebra''.