Tentamenstof Numerieke Lineaire Algebra 2016

Op deze bladzijde vind je de stof voor de twee deeltentamens. Als globale richtlijn kan je gebruiken dat de opgaven van het werkcollege maatgevend zijn, wat betreft stof en niveau.

let op: de deeltentamens duren ieder slechts twee uur!

Het hertentamen daarentegen duurt wel drie uur.

Stof van het eerste deeltentamen

Het eerste deeltentamen gaat over de volgende behandelde stof:
  • Trefethen & Bau, Lectures 1 t/m 19
Zie ook de eerste deeltentamens 2013 en 2014 en 2015:
  • Eerste Deeltentamen 2013: pdf
  • Eerste Deeltentamen 2014: pdf
  • Eerste Deeltentamen 2015: pdf

Samenvatting van de stof:

Na een introductie in basisbegrippen uit de Lineaire Algebra, zoals de SVD, hebben we gekeken naar QR decomposities en verschillende manieren om die te berekenen. Wiskundig gezien zijn die equivalent, maar in finite precision arithmetics hebben ze verschillende eigenschappen. Het betrof:

  • Gram-Schmidt
  • Modified Gram-Schmidt
  • Givens rotations
  • Householder reflections
Verder zagen we verschillende methoden om Linear Least Squares (LLS) problemen op te lossen, die ook weer mathematisch equivalent zijn, maar niet in finite precision arithmetic:
  • Normaalvergelijkingen oplossen (pseudo-inverse)
  • QR-decompositie (verschillende manieren)
  • SVD
In een volgend deel bekeken we conditionering en stabiliteit, twee aspecten van eenzelfde vraagstuk, namelijk, wat je aan nauwkeurigheid kunt verwachten van een finite precision algoritme losgelaten op een zeker probleem. De conditionering van het probleem is daarbij inherent aan het probleem, de stabiliteit is een aspect van het algoritme. We bekeken
  • Definitie conditiegetallen
  • Finite Precision (floating point) Arithmetic
  • Stability, backward stability
  • Stabiliteit van Householder QR
  • Stabiliteit van back substitution
  • Conditionering van LLS problemen
  • Stabiliteit van LLS algoritmes

Tweede deeltentamen

Het tweede deeltentamen gaat over de volgende stof:
  • Trefethen & Bau, Lectures 20 t/m 31
Zie ook de tweede deeltentamens 2013 en 2014 en 2015:
  • Tweede Deeltentamen 2013: pdf
  • Tweede Deeltentamen 2014: pdf
  • Tweede Deeltentamen 2015: pdf
Merk op dat in 2013 ook Lectures 32 t/m 36 tot de stof behoorden! De opgaven daarover kan je dus overslaan.

Samenvatting van de stof:

Eerst bekeken we Gauss-eliminatie en LU decompositie met en zonder pivoting. Eerder in de cursus hadden we al gezien hoe je een Cholesky decompositie uitrekent van een symmetrische positief definiete matrix.

Na een herhaling van feiten over eigenwaarden kwam de observatie dat eigenwaardenmethoden noodzakelijkerwijs iteratief zijn en in de praktijk uit twee fasen bestaan.

De eerste fase is tridiagonalisatie (of, in het niet-hermietse geval, transformatie tot boven-Hessenbergmatrix). Vervolgens zagen we de eerste methodes,

  • machtsmethode
  • (shifted) inverse iteration
  • Rayleigh Quotient iteration
De laatste heeft cubische convergentie voor zelfgeadjungeerde matrices A. Daarna, in lectures 28 en 29, werd het QR algoritme geintroduceerd via de blok machtsmethode. De hierin verscholen inverse iteratie bleek de reden te zijn voor de snelle convergentie van de shifted QR iteratie.

Tot slot bekeken we drie andere eigenwaardemethoden, te weten

  • Jacobi-rotaties
  • Bisectie
  • Divide-and-Conquer
Het deel V over eigenwaarde eindigde met enkele observaties over het uitrekenen van de SVD, of via A*A of via een blokmatrix van afmetingen 2n x 2n. Ook bekeken we eerder al een directe methode tot bidiagonalisatie.

Zie tot slot ook de hertentamens 2013 en 2014 en 2015:

  • Hertentamen 2013: pdf
  • Hertentamen 2014: pdf
  • Hertentamen 2015: pdf
Merk op dat in 2013 ook Lectures 32 t/m 36 tot de stof behoorden!