Contents:
Problems of numerical linear algebra 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 will study following topics:
- For solving linear systems of equations we will present Gaussian
elimination with different pivoting strategies and blocking algorithms.
- For least-squares problems we study
QR-factorisation and Singular Value Decomposition
(SVD).
- The methods for solution of eigenvalue problems which are based on transformation
techniques for symmetric and non-symmetric matrices.
- The basic iterative methods (Jacobi, Gauss-Seidel and Successive overrelaxation (SOR)) for solution of linear systems.
- Introduction to the Krylov subspace methods.
For all topics above we will discuss numerical algorithms with respect to applicability, reliability, accuracy, and efficiency.
By implementing computer exercises in MATLAB and C++/PETSc the students will get experience in implementation and evaluation of numerical algorithms for problems of
linear algebra.
By the completion of this course the students will be able to:
- use numerical linear algebra as building bricks in computation.
- make a linear algebra model of problems from the physical reality.
- derive and use the numerical techniques needed for a professional solution of a given linear algebra problem.
- use computer algorithms, programs and software packages to compute solutions to current problems.
- critically analyze and give advice regarding different choices of models, algorithms, and software with respect to efficiency and reliability.
- critically analyze the accuracy of the obtained numerical result and to present it in a visualized way.
The course consists of 36 lecture hours, 20 exercise hours and gives 7.5 points.
The course code for engineering schools and students registered at Chalmers is TMA265. The course code for students registered in GU is MMA600.
Latest news
Welcome to the course! The schedule for the course can be found in TimeEdit.
Template for the report, pdf file
Template for the report, tex file
27.10.2017: I'm checking your exams. I will leave your works at mvexp latest at 3 November. Below you can find answers to examination.
Answers to examination at 24.10.2017
31.10.2017: All examination works written at 24.10.2017 are verified and you can get information about your grades at expedition. Ask personal at expedition about information in LADOK.
For homeworks and computer exercises, see section Program.
All students should register for this course. For registration see antagning.se
The student representatives that have been selected for this course now are:
MPENM cyren@student.chalmers.se OSCAR CYRÉN
MPENM karhes@student.chalmers.se KARIN HESSLOW
MPENM jagersj@student.chalmers.se JONAS JAGERS
FK sachinj@student.chalmers.se SACHIN JANARDHANAN
MPENM wickius@student.chalmers.se OLLE WICKIUS
Here are some available projects for Master works:
Efficient implementation of Helmholtz equation with applications in medical imaging
Optimal control of drugs in the mathematical model of dynamics of a tumor-immune system
Main paper for the project "Optimal control of drugs in the mathematical model of dynamics of a tumor-immune system"
Optimization approach in the design of approximate cloaking structures
I thank all of You who will answer to the following course evaluation survey (I assume that it is only for students at Chalmers, but GU students can fill out course evaluation from GU-page):
Course evaluation survey
This survey helps me get feedback from You and improve course for the next time.
I will be very grateful if You can fill it.
Teachers
Course coordinator: Larisa Beilina
larisa@chalmers.se,
room 2089,
homepage
Course literature
Demmel,
Applied Numerical Linear Algebra, SIAM 1997.
List of Errata for the Textbook
L. Beilina, E. Karchevskii, M. Karchevskii, Numerical Linear Algebra: Theory and Applications, Springer, 2017. Will be selled at Cremona after publication.
Readme for Matlab programs
Matlab programs
PETSc libraries which are a suite of data structures and routines for the scalable (parallel) solution of scientific applications;
user manual
Program
Day |
Time |
Place |
Remarks |
MON |
13:15-15:00 |
Euler |
Lecture |
WED |
13:15-15:00 |
MVF24, MVF25 |
Computer exercises |
THU |
10:00-11:45 |
Pascal |
Lecture |
FRI |
13:15-15:00 |
MVF24, MVF25 |
Computer exercises |
24.10.2017 |
14.00-18.00 |
SB |
Examination |
05.01.2018 |
14.00-18.00 |
SB |
Examination |
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. We considered example of application of
linear systems: image compression using SVD, image deblurring.
We introduced some basic concepts and notations: transpose, lower
and upper triangular matrices, singular matrices, symmetric and
positive definite matrix, conjugate transpose matrix, row echelon form, rank, cofactor.
Lecture 1
Lecture 2
We will continue with the introduction: eigenvalues and
eigenvectors, characteristic equation, spectral radius,
diagonalization, orthoganality, invertible matrix. We will discuss why we need norms:
(1) to measure errors, (2) to measure stability, (3) for
convergence criteria of iterative methods. We will discuss computer
exercise 1 and perturbation theory in polynomial evaluation.
Lecture 2
Lecture 3
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 and uniqueness of factorization of A.
Different versions of algorithms of Gaussian elimination. Example: how to solve Poisson's equation on a unit square using LU factorization.
Complexity of the LU
factorization. Error bounds for the solution Ax=b. Roundoff error
analysis in LU factorization. Estimating condition
numbers. Hagers's algorithm.
Lecture 5
Componentwise error estimates.
Improving the Accuracy of a Solution for Ax=b: Newton's method and equilibration technique. Convergence of the Newton's method.
Real Symmetric Positive Definite
Matrices. Cholesky algorithm.
Lecture 6
Band Matrices, example: application of Cholesky decomposition in the solution of ODE.
Continuation of considering example: application of Cholesky
decomposition in the solution of ODE. Linear least squares
problems. Introduction and applications. The normal
equations. Example: Polynomial fitting to curve. Solution of
nonlinear least squares problems: examples.
Lecture 6
Lecture 7
QR and Singular value decomposition (SVD). SVD and the
fundamental subspaces. SVD for linear least squares problems.
Numerical rank, condition number.
Lecture 8
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. Moore-Penrose pseudoinverse. Rank-Deficient Least Squares
Problems.
Lecture 8
Lecture 9
Introduction to spectral theory, eigenvalues, right and
left eigenvectors. Similar matrices. Defective eigenvalues. Canonical forms: Jordan
form and Schur form, real Schur form.
Lecture 10
Gerschgorin's theorem.
Perturbation theory, Bauer-Fike theorem.
Discussed
algorithms for the non-symmetric eigenproblems: power method,
inverse iteration, inverse iteration
with shift, orthogonal iteration.
Lecture 11
Discussed
algorithms for the non-symmetric eigenproblems:
QR iteration and QR-iteration with shift.
Hessenberg matrices, preservation of Hessenberg form.
Hessenberg reduction. Tridiagonal and bidiagonal reduction.
Regular Matrix Pencils and Weierstrass Canonical Form.
Lecture 12
Regular Matrix Pencils and Weierstrass Canonical Form.
Singular Matrix Pencils and the
Kronecker Canonical Form.
Application of Jordan and Weierstrass
Forms to Differential Equations.
Symmetric eigenproblems 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. Definite Pencils.
Lecture 13
Theorem that the Rayleigh quotient is a good approximation to
an eigenvalue.
Algorithms for the Symmetric eigenproblem: Tridiagonal QR iteration,
Rayleigh quitient iteration, Divide-and-conquer algorithm. QR
iteration with Wilkinson's shift. Divide-and-conquer, bisection and
inverse iteration, different versions of
Jacobi's method.
Lecture 14
Algorithms for symmetric matrices (continuation): different versions of
Jacobi's method. Algorithms for the
SVD: QR iteration and Its Variations for the Bidiagonal SVD.
The basic iterative methods (Jacobi, Gauss-Seidel and Successive
overrelaxation (SOR)) for solution of linear systems. Jacobi,
Gauss-Seidel and SOR for the solution of the Poisson's equation in two
dimension. Study of Convergence of Jacobi, Gauss-Seidel and SOR.
Introduction to the Krylov subspace methods.
Conjugate gradient algorithm. Preconditioning for Linear Systems.
Preconditioned conjugate gradient algorithm.
Common preconditioners.
Example of construction of a lower triangular
matrix using Given's rotation.
Computer labs
Wednesdays 13-15 (except the first week) in computer room MVF24, MVF25 (Mathematical Sciences in Physics building).
Fridays 13-15 in computer room MVF24, MVF25.
Computer labs and Matlab/PETSc excercises will be included in the
assignments below.
Computer Exercises
Matlab programs which will be used in computer exercises:
Poisson2D_LU.m
DiscretePoisson2D.m
BackSub.m
ForwSub.m
LU_factor.m
Templates for programs written in PETSc:
Template for computing of discretized Laplacian
Template for the main program in PETSC for LU decomposition
Example of Makefile to be able compile PETSc program at Chalmers
Template for petsc function which removes zeros from the original matrix. We can work then with resulting matrix without zeros in the same way as with original matrix.
Additional templates of PETSc-Makefile and main program in PETSc:
Example of the main program in PETSC.
Example of the Makefile to compile the above main program like that: make hello
Reference literature:
Learning MATLAB, Tobin A. Driscoll ISBN: 978-0-898716-83-2
(The book is published by SIAM).
Course requirements
The learning goals of the course can be found in the course
plan .
The following sections of the textbook
Applied Numerical Linear Algebra, SIAM 1997. will be considered in the
book:
- 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
- Chapter 6
-
1-6, except 6.3.3, 6.5.6, 6.6.4,6.6.6
The following questions of the textbook
Applied Numerical Linear Algebra, SIAM 1997. 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.
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 and computer labs 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 or come directly to my office during time for the computer exercises.
Assignments
Wednesdays 13-15 in computer rooms MVF24, MVF25 (Mathematical Sciences at Physics building)
Fridays 13-15 in computer rooms MVF24, MVF25. Hand in a short report of your work
before the final exam.
Homeworks and computer exercises
Link to the homeworks:
Homeworks
One more time link to the computer ex.:
Computer Exercises
Deadlines for homeworks and comp.ex.:
Homework 1 and comp. ex. 1: 15 September
Homework 2: 22 September
Homework 3 and comp.ex. 2: 6 October
Homework 4 and comp.ex. 3: 13 October
Comp.ex. 4,5: 20 October
Examination
- To pass this course you should pass the written exam and 2 computer assignments, see description of comp. assignments above.
- The two compulsory home assignments should be handed in before the final exam.
- Written examination
-
- Final exam is compulsory, written.
- 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 |
>27 |
5 |
>27 |
|
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 link which will be written at this homepage.
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
Examination procedures
In
Chalmers Student Portal you can read about when exams are given
and what rules apply on exams at Chalmers. In addition to that, there is
a schedule
when exams are given for courses at University of Gothenburg.
Before the exam, it is important that you sign up for the examination.
If you study at Chalmers, you will do this by the
Chalmers Student Portal, and if you study at University of
Gothenburg, you sign up via GU's
Student Portal.
At the exam, you should be able to show valid identification.
After the exam has been graded, you can see your results in Ladok by
logging on to your Student portal.
At the annual (regular) examination:
When it is practical, a separate review is arranged. The date of the
review will be announced here on the course homepage. Anyone who can not
participate in the review may thereafter retrieve and review their exam
at the Mathematical
Sciences Student office. Check that you have the right grades and
score. 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 retrieved at the Mathematical
Sciences Student office. Check that you have the right grades and
score. Any complaints about the marking must be submitted in writing at
the office, where there is a form to fill out.
Old exams
Old exams given before 2012/2013 are presented at the following link:
Old exams