Numerical Linear Algebra (TM and GU)

7.5 credit points

september - october 2007




Lecturer and examiner


Ivar Gustafsson


- See you at the course start on wednesday september 5, time 13.15 in room MVF33 at Mathematical Sciences - Physics building.

Some words about the course

Numerical linear algebra problems arise in many different fields of science like computational fluid dynamics, solid mechanics, electrical networks, signal analysis, and optimisation.
In this course we study basic linear algebra concepts like matrix algebra, theory for linear systems of equations, spectral theory, and vector- and matrix norms as well as numerical aspects like efficiency, reliability, error analysis and condition numbers.
We consider three linear algebra building bricks in computation: For all three building bricks above we discuss numerical algorithms with respect to applicability, reliability, accuracy, and efficiency. By computer exercises the students get experiences in implementation and evaluation of numerical algorithms for linear algebra problems.

Course Literature


Lectures

Mondays 13-15 (except the first week when this lecture is on wednesday instead) in room MVF33 (Mathematical Sciences - Physics building)
Thursdays 9-12 in MVF33 at Mathematical Sciences (Matematiska Vetenskaper

Computer Exercises, without supervision

Wednesdays 13-15 (except the first week) in computer room MVF25 (Mathematical Sciences - Physics building)
Fridays 13-15 in computer room MVF25

Outline

The following sections in the textbook will be considered. Chapters 6 and 7 are saved for the course to follow next quarter: Large Sparse Matrix Problems.
Chapter 1, mainly repetition I hope. I will also give a 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, 6, 13 ( 7 as homework assignment and 20 as computer exercise)
Chapter 2: 6, 7, 10, 11, 12, 17, 19, 20 (3 and 18 as homework assignments)
Chapter 3: 1, 2, 3(parts 1,2,3), 5, 6, 7, 8, 9, 11, 14, 18 (4 as homework assignment)
Chapter 4: 1, 2, 3, 4, 5, 7, 10(parts 1,4), 11, 12, 13 (6 and 8 as homework assignments and 15 as computer exercise)
Chapter 5: 1, 3(for symmetric matrix), 6, 7, 13, 14, 15, 16, 17, 18, 22, 27, 28 (2 and 5 as homework assignments)

To each chapter belong an optional homework assignment and a compulsory 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. Either you will use already existing MATLAB programs or write your own small MATLAB codes.
The homework assignments give bonus credit points for the examination, well performed one per homework assignment. The examination contains 25 points and I usually require 13 points for passing.
Since the occasions reserved for the computer exercises are without supervision you may put questions on these exercises to me at the lectures. To some extent I might also help you with the homework assignments.
Passed computer exercises will be graded with grades 3, 4, or 5, see examination below.

Detailed program on line

September 5

Introduction:
- Read chapter one in the textbook yourselves. It is an introduction to numerical analysis and computer arithmetics. The first computer exercise is based on this stuff.
- My 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. The first homework assignment is based on this stuff.
I have talked about the three building bricks in 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 also discussed the needs for norms: (1) meashuring errors, (2) meashuring stability, and (3) convergence of iterative methods.
We also introduced some basic concepts and notations: transpose, inverse, scalar (inner) product, outer product, and LU-factorization.
We discussed calculating the determinant by LU-factorization and solving a linear system by Gaussian elimination (backslash in MATLAB).
I warned againts computing the explicit inverse when solving a linear system of equations.
We introduced the concepts symmetric and orthogonal matrix, positive (negative) definite and positive i(negative) semidefinite matrix,i indefinite matrix, and bandwidth of a matrix, in particular tridiagonal matrices and upper Hessenberg matrices.

September 6

We discussed the first CE and I presented examples of requested hand-in-graphics.
I continued the introduction:
submatrices, principal submatrices, leading principal submatrices.
eigenvalues and eigenvectors, characteristic equation, spectral radius.
diagonalization, spectral theorem.
orthoganality, orthogonal complement, orthogonal projection, orthogonal components.
Application: A linear programming problem.
Basic theory for linear systems: nullspace, rangespace, rank, consistence, uniqueness.
Block matrices.
Matrix multiplication by inner and outer products.
Introduction to HA1b: 2 by 2 block triangular matrices and their inverses, low rank corrections, Sherman-Morrison formula.
I gave you five Exercises on my introduction so far. If you want the solutions to these consult my lecture notes on request.

September 10

Vector- and matrixnorms.
I have demonstrated the solution of questions Q1.6 and Q1.13
Chapter 2: System of linear equations.
Gaussian elimination, LU-factorization.
Gaussian elimination by outer products (elementary transformations).

September 13

Pivoting, partial and total.
Growth factor, small numerical example.
Special matrices:
- Diagonally dominant,
- Symmetric positive definite
- Symmetric indefinite by 2x2 pivots
- Bandmatrices
- General sparse matrices in the course "Large Sparse Matrix Problems", given next fall.
Perturbation theory, condition number.
Componentwise error estimates, Bauer-Skeel condition number, a small numerical example.

September 17

Error bound using the residual.
Backward analysis.
"A posteriori" error estimates.
Estimating condition number.
"A priori" error estimates.
Iterative refinement.
I have demonstrated the solution of Q2.10 and Q2.12
Gerschorin's theorem, bounds on eigenvalues.

September 20

I have demonstrated the solution of Q2.19
Section 2.6. Blocking algorithms:
LAPACK, BLAS
hierarchy of memories
examples from implementation of matrix multiplication and Gaussian elimination with BLAS-3 routines.
Chapter 3: Linear least squares problems. Introduction and applications.

September 24

The normal equations, geometric interpretation, the generalixed inverse.
Normal equations of second kind.
Numerical aspects on computability and stability.
Perturbation theory.
Weigthed least squares as homework assignment.
I have demonstated the solution of Q3.3, part 1 and 3.
QR-factorization - an introduction.

September 27

QR-factorization for linear least squares problems
QR-decomposition and relation to the fundamental subspaces.
Underdetermined problems by QR-factorization.
A comparision between the normal equations and QR-factorization in a concrete application: Polynomial fitting.
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.
Applications: image compressing, signal processing and model reduction.
Least squares with linear equality constraints.
Total least squares

October 1

QR-factorization by Householder transformations.
I have demonstrated the solution of Question 3.9.
Chapter 4, Introduction to spectral theory, eigenvalues, right and left eigenvectors.
Similar matrices.
Spectral decomposition, right invariant subspaces, deflation.

October 4

Multiplicity, algebraic and geometric.
Canonical forms: Jordan form and Schur form
Bounds on eigenvalues, Gerschgorin's theorem
Perturbation theory, Bauer-Fike theorem, Theorems 4.4, 4.5, and 4.6
Algorithms for nonsymmetric eigenproblems:
The power method.

October 8

The power method - deflation for symmetric problems
Inverse iteration, invers iteration with shift, Rayleigh quotient iteration
Orthogonal (simultaneous) iteration.
QR-iteration, QR-iteration with shift
Transformation to Hessenberg form by Householder reflections or Givens rotations.

October 11

QR-iteration on Hessenberg matrices, presevation of Hessenberg form.
Choice of shift in Hessenberg QR-iteration, stopping criterion.
Implicit shift QR method (the ultimate method); bulge-chasing, comment on double shift.
I have demonstrated the solution of Question 4.12.
Chapter 5, Symmetric eigen problems
Perturbation theory: Weyl's theorem
Corallary regarding similar result for singular values
Courant-Fischer (CF) theorem
Applications of CF theorem:
- Error bound for eigenvalues computed by a stable method like QR-iteration.
- Cauchy interlace theorem
- A posteriori error bounds using the residual.
A result telling that the Rayleigh quotient is a good approximation to an eigenvalue.
Algorithms for symmetric eigen problems
1. Tridiagonal QR iteration, single shift and Wilkinson's shift

October 15

2. Rayleigh quotient iteration
3. Spectrum slicing - bisection
4. Divide and conquer method
5. Jacobi's method

October 18

Jacobi's method cont. Classical and cyclic versions.
Examplel on Jacobi's method
Methods for singular value decomposition
Reduction to bidiagonal form
LR iteration for bidiagonal matrix
One-sided Jacobi's method
I solved the questions 5.18 and 5.22.

Summary of the course

OBS! In parentheses means: Will not be examined.

Chapter 1: Basic concepts in linear algebra

Matrix algebra, scalar product, inverse, symmetric, orthogonal, positive definite, bandwidth, submatrices, orthogonal projection, orthogonal complement, eigenvalues, eigenvectors (left and right), characteristic equation, spectral radius.
Diagonalization (spectral theorem), nullspace, rangespace, rank.
Linear systems, consistence, homogeneous.
Block matrices, block factorization.
Schur complement, low-rank corrections.
Matrix- and vector norms.
Complex matrices, Hermitean, unitary.
Multiplicity of eigenvalues, canonical forms: (Jordan) and Schur.
Similar transformations
Invariant subspaces, deflation.
Bounds for eigenvalues, Gerschgorin.
Rayleigh quotient.
Triangular matrices, Hessenberg form.

Chapter 2: Systems of linear equations

Gaussian elimination with elementary transformations - outer product formulation.
LU-factorization, Jordan elimination.
Partial pivoting, growth factor.
Special matrices:
Diagonally dominant
Symmetric, positive definite, Cholesky factorization,
Symmetric indefinite, 2 by 2 pivot blocks
Perturbation theory, condition number, backward analysis, stability of an algorithm, estimating condition number, iterative refinement.
Blocking algorithms, BLAS, Gaussian elimination with BLAS-3 level algorithms.

Chapter 3: Linear least squares problems

Overdetermined systems, normal equations of first and second kind, underdetermined systems.
QR-decomposition
SVD-decomposition, also for rank defficient case. Truncated SVD, numerical rank, truncated least squares, pseudo-invers.
Least squares with linear equality constrants.
How to perform the QR-factorization: Gramm-Schmidt (not stable), Householder reflections, Givens rotations.
(Perturbation theory)

Chapter 4: Nonsymmetric eigen-problems

Perturbation theory, condition number for eigenvalues, Bauer-Fike theorem.
Power method, inverse iteration, Rayleigh quotient iteration.
Orthogonal iteration, QR iteration with shift. QR on Hessenberg form with explicit and implicit shift.
Preprocessing to Hessenberg form by Householder reflections or Givens rotations.

Chapter 5: Symmetric eigen-problems

Perturbation theory, Weyl's theorem, (Courant-Fischer).
Congruent transformations, inertia, spectrum slicing-bisection.
Tridiagonal QR iteration.
Divide and conquer.
Jacobi's method.
Algorithms for SVD.
Reduction to bidiagonal form B, SVD of B related to eigenvalues of T, tridiagonal.
LR iteration on bidiagonal matrix.
One-sided Jacobi's method.

Material for the course


Examination

Date for the written examination has to be decided by me and the students.
Means of assistance at the examination: none.
Passed examination is graded with grades 3, 4, or 5 and this grade is weighted together with the grades of the computer exercises to give a final grade for the course.

Examination: Thu October 25, 9-13 in MVF33

Examination marked: Contact me or the students' office (later) for you result.

Re-examination

If interested in re-examination (omtenta) contact me as soon as possible so we can decide for a date.

Re-examination: Thursday december 20, 9.00-13.00 in MVH11.

Nobody attended the re-examination.