Numerical Linear Algebra ENM-TMA265 and GU-MMA600 7.5 credit points

All examination works written at 23.10.2012 are verified and You can get information about Your grades at expedition. Ask personal at expedition about information in LADOK.

All examination works written at 17.01.2013 are verified and You can get information about Your grades at expedition. Ask personal at expedition about information in LADOK.

All current and recent information will be placed here. Regarding examination at 23.10.2012: CTH students should not register for this exam. Only GU students can register for the examination. CTH and GU students will get their personal exam numbers from Observers of this exam. Examination at 23.10 will be at Maskinhuset at Chalmers:

Maskinhuset

Where exactly (in which one room) will be exam You will know at the day of examination: the announcement will be placed at the blackboard close to the entree of Maskinhuset. Notes: GU students can do re-examination but they can not high their scores (for example, from G to VG) but Chalmers students can do re-examination and high scores. At the latest lecture we have decided make re-examination at 17.01.2013 at 8.30. Please, follow this site to get exact information closer to the day of re-examination. Aboit re-examination at 17.01.2013: this date for re-examination is already in Chalmers studieportal. This means that Chalmers students can already register for this re-examination.

The schedule for the course can be found via the link to webTimeEdit top of the page.

Course coordinator: Larisa Beilina, larisa@chalmers.se

1. Demmel, Applied Numerical Linear Algebra, SIAM 1997, selled at Cremona. List of Errata for the Textbook
2. PETSc libraries which are a suite of data structures and routines for the scalable (parallel) solution of scientific applications; user manual

• Homeworks and computer exercises
• Homeworks
Deadlines for homeworks:
• Homework 1: 14 September
• Homework 2: 21 September
• Homework 3: 28 September
Homework 4: 5 October Deadline for computer exercises: 16 October
• Lecture 1
Introduction to the course. Read chapter 1 in the textbook yourselves. Introduction to linear algebra and numerical linear algebra. If this looks unfamiliar you should better consult you former literature in linear algebra and refresh your knowledges. We will concentrate on the three building bricks in Numerical Linear Algebra (NLA) : (1) Linear Systems, (2) Overdetermined systems by least squares, and (3) Eigenproblems. The building bricks serve as subproblems also in nonlinear computations by the idea of linearization. Examples: Newtons method for solving nonlinear systems of equations and projection on linearized constraints in nonlinear optimization. We introduced some basic concepts and notations: transpose, inverse, scalar (inner) product, outer product, and LU-factorization. We will discuss calculating the determinant by LU-factorization, solving a linear system by Gaussian elimination (backslash in MATLAB) and computing the characteristic equation by first computing the eigenvalues. We introduced the concepts symmetric and orthogonal matrix, positive (negative) definite and positive (negative) semidefinite matrix, indefinite matrix. Bandwidth of a matrix, in particular tridiagonal matrices and upper Hessenberg matrices.
• Lecture 2
We will continue with the introduction: submatrices, principal submatrices and leading principal submatrices. eigenvalues and eigenvectors, characteristic equation, spectral radius. diagonalization, spectral theorem. orthoganality, orthogonal complement, orthogonal projection, orthogonal components. Basic theory for linear systems: nullspace, rangespace, rank, consistence, uniqueness. Block matrices. Matrix multiplication by inner and outer products, 2 by 2 block triangular matrices and their inverses, low rank corrections, Sherman-Morrison formula. We will discuss why we need norms: (1) to measure errors, (2) to measure stability, (3) for convergence criteria of iterative methods, and (4) for convergence property for fix point iteration. Definition of Vector norms.
• Lecture 3
Matrix norms. We will demonstrate the solution of questions Q1.7 and Q1.13 of the course book. Chapter 2: System of linear equations. Gaussian elimination, LU-factorization. Gaussian elimination (and LU factorization) by outer products (elementary transformations). Pivoting, partial and total.
• Lecture 4
We will discuss the need of pivoting. Theorem 2.5 in the book. Different LU factorization algorithms. Complexity of the LU factorization. Error bounds for the solution Ax=y. Roundoff error analysis in LU factorization. Estimating condition numbers. Hagers's algorithm. Estimating the Relative Condition Number. Improving the accuracy of the solution Ax=y.
• Lecture 5
Componentwise error estimates. Error bound using the residual. Backward analysis. "A posteriori" error estimates. Estimating condition number. "A priori" error estimates. Reading adwise regarding perturbation theory and error analysis: You should understand the ideas, not remember details. Iterative refinement.Blocking Algorithms for Higher Performance. LAPACK, BLAS-routines. How to Optimize Matrix Multiplication. Real Symmetric Positive Definite Matrices. Cholesky algorithm.
• Lecture 6
Chapter 3: Linear least squares problems. Introduction and applications. Linear models and nonlinear models. Statistical models. A comment on other norms than the 2-norm. The normal equations, geometric interpretation. The generalized inverse. QR-factorization for linear least squares problems. A comparision between the normal equations and QR-factorization in a concrete application: Polynomial fitting.
• Lecture 7
Singular value decomposition (SVD). SVD and the fundamental subspaces. SVD for linear least squares problems. Numerical rank, truncated SVD, condition number, best approximation of a matrix, truncated pseudoinverse, truncated least squares.
• Lecture 8
Perturbation theory for the least-squares problem. Householder transformations and Givens rotations. QR-factorization by Householder transformation and Givens rotation. Examples of performing Householder transformation for QR decomposition and tridiagonalization of matrix.
• Lecture 9
Eaxmples of QR-factorization by Householder transformations. Chapter 4, Introduction to spectral theory, eigenvalues, right and left eigenvectors. Similar matrices. Spectral decomposition. Right invariant subspaces. Multiplicity, algebraic and geometric, defective eigenvalues. Canonical forms: Jordan form and Schur form.
• Lecture 10
Gerschgorin's theorem. Perturbation theory, Bauer-Fike theorem. Inverse iteration, invers iteration with shift. QR-iteration on Hessenberg matrices, preservation of Hessenberg form.
• Lecture 11
Regular Matrix Pencils and Weierstrass Canonical Form. Example with damped mass-spring system. Application of Jordan and Weierstrass Forms to Differential Equations. Generalized Schur Form for Regular Pencils. Definite Pencils. Singular Matrix Pencils and the Kronecker Canonical Form. Application of Kronecker Form to Differential Equations. Nonlinear Eigenvalue Problems.
• Lecture 12
Chapter 5, Symmetric eigen problems Perturbation theory: Weyl's theorem. Corollary regarding similar result for singular values. Application of Weyl's theorem: Error bounds for eigenvalues computed by a stable method. Courant-Fischer (CF) theorem. Inertia, Sylvester's inertia theorem. Theorem that the Rayleigh quotient is a good approximation to an eigenvalue. Relative Weyl theorem. Algorithms for the Symmetric eigenproblem: Tridiagonal QR iteration, Rayleigh quitient iteration, Divide-and-conquer algorithm. QR iteration with Wilkinson's shift.
• Lecture 13
Algorithms for symmetric matrices (continuation): bisection and inverse iteration algorithms. Spectrum slicing bisection. Jacobi's method.
• Lecture 14
Algorithms for the SVD: QR iteration, LR iteration, divide-and-conquer, bisection and inverse iteration, Jacobi's method for the SVD, one-sided Jacobi. Differential equations and eigenvalue problems. The Toda lattice.

Wednesdays 13-15 (except the first week) in computer room MVF24 (Mathematical Sciences in Physics building).
Fridays 13-15 in computer room MVF24 (exept the first week).
Computer labs and Matlab/PETSc excercises will be included in the assignments below. Matlab programs which will be used in computer exercises:

polyplot.m

eigscat.m

qrplt.m

Reference literature:

• Tobin A. Driscoll, Learning MATLAB, ISBN: 978-0-898716-83-2 (The book is published by SIAM)

The following sections in the textbook will be considered in the book. Chapters 6 and 7 are saved for the another course.

Chapter 1

mainly repetition and brief revision on basic linear algebra.

Chapter 2

1-6, 7 except 2.7.4 and 2.7.5

Chapter 3

1-5

Chapter 4

1-4

Chapter 5

1-4

The following questions in the textbook are recommended:

• Chapter 1: 1, 2, 3, 4, 5, 7, 13.
• Chapter 2: 3, 6, 7, 10, 11, 12, 17, 19.
• Chapter 3: 1, 2, 3(parts 1,2,3), 4, 5, 6, 8, 9, 11, 14, 15, 18.
• Chapter 4: 1, 3, 4, 5, 6, 7, 10, 11, 12, 13.
• Chapter 5: 1, 3 (for symmetric matrix), 6, 7, 14, 15, 16, 17, 18, 22, 27, 28.

To each chapter belong an optional homework assignment and a computer exercise. The homework assignments are similar to the questions in the textbook and such you could expect at the examination. In the computer exercises you will be trained in using different algorithms in numerical linear algebra using MATLAB or PETSc libraries. Either you will use already existing MATLAB and PETSC programs or write your own small MATLAB or PETSc codes. The homework assignments give bonus credit points for the examination. Since the occasions reserved for the computer exercises are without supervision you may put questions on these exercises to me at the lectures. Passed computer exercises will be graded with grades 3, 4, or 5, see examination below.

You may work in a group of 2 persons but hand in only one report for the group.

Wednesdays 13-15 (except the first week) in computer room MVF24 (Mathematical Sciences at Physics building) Fridays 13-15 in computer room MVF24 (exept the first week when it is in room MVF25). Hand in a short report of your work before the final exam.

• To pass this course you should pass the written exam and one of the 5 computer assignments. To get max 5 points for computer exercises I will use middle value for all 5 submitted computer labs. If middle value > 4.5 - then you will get 5 bonus points.
  
• The two compulsory home assignments should be handed in before the final exam generating max 5 bonus points.

Written examination

Final exam is compulsory, written, with a maximum score of 27 points.

The theory questions will be choosen from the following list

List of questions

You should be able to state and explain all definitions and theorems given in the course and also apply them in problem solving.

Grades are set according to the table below.

Grades Chalmers	Points		Grades GU	Points
-	<15		-
3	15-20		G	15-27
4	21-27		VG	>28
5	>28

The exam takes place at 23.10, Maskinhuset at Chalmers:

Maskinhuset

Bring ID and receipt for your student union fee (this is requirement only for Chalmers students. GU students can come on the exam without receipt).

Solutions to the exam will be published at the following link (will be added). You will be notified the result of your exam by email from LADOK (This is done automatically as soon as the exams have been marked an the results are registered.)
The exams will then be kept at the students office in the Mathematical Sciences building.
Check that the number of points and your grade given on the exam and registered in LADOK coincide.
Complaints of the marking should be written and handed in at the office. There is a form you can use, ask the person in the office.).

The following link will tell you all about the examination room rules at Chalmers: Examination room instructions

In Chalmers Student Portal you can read about when exams are given and what rules apply on exams at Chalmers.
At the exam, you should be able to show valid identification.
Before the exam, it is important that you report that you want to take the examination. You do this at Chalmers Student Portal.

Notice of result is obtained only by email via Ladok. (Not verbally at study expedition.) This is done automatically when the results are registered. Check that you have the right grades and score.

At the annual examination:
When it is practical a separate review is arranged. The date of the review will be announced here on the course website. Anyone who can not participate in the review may thereafter retrieve and review their exam on Mathematical sciences study expedition, Monday through Friday, from 9:00 to 13:00. Any complaints about the marking must be submitted in writing at the office, where there is a form to fill out.

At re-examination:
Exams are reviewed and picked up at the Mathematical sciences study expedition, Monday through Friday, from 9:00 to 13:00. Any complaints about the marking must be submitted in writing at the office, where there is a form to fill out.

Answers to exam questions are given here:

Examination 1 (23.10.2012)

Examination 2 (17.01.2013)

Old exams are given here:

Old exams