### Topics covered

#### Fall 2017

1. (Mo, Sep 4)
• Errors in computations
• Absolute and relative error and their change by basic operations
• Finite precision, floating numbers, the error of number representations

2. (Tu, Sep 5 )
• Linear algebra review
• Vector norm definition
• inner product definition
• 1-norm, 2-norm, p-norm, infinity norm and their relations
• Matrix norm definition

3. (Mo, Sep 11)
• Matrix norm induced by a vector norm
• Application to 1-norm, infinity norm
• Quadratic forms, positive (semi)definite, negative (semi)definite and indefinite matrices

4.  (Tu, Sep 12)
• Rayleigh quotient
• Connection between theinduced 2-norm of matrix A and eigenvalues of A*A
• Its application for self-adjoint matrices
• Gershgorim circles

5. (Mo, Sep 18)
• Proof of Gershgorin's Theorem
• Singular values and singular value decomposition
• Definition of Moore-Penrose inverse

6.  (Tu, Sep 19)
• Application: computation of Moore-Penrose inverse by SVD
• Linear systems Ax=b
• The best approximation  if there is no solution
• Relation between the relative error of b and of x (when A is exact)
• Relation between the relative error of A and of x (when b is exact)
• Condition number of a regular matrix
• Direct method to solve the system: by rank-one-decomposition
• A space efficient way to do it
• The special case of tridiagonal matices, formulas for the solution

7.  (Mo, Sep 25)
• Iterative improvement of the solution
• Estimate of the norm of error, condition to ensure fast convergence
• General iteration for linear systems, condition for convergence
• Gauss-Seidel iteration and how to compute it

8.  (Tu, Sep 26)
• Successive over relaxation
• a special case

9.  (Mo, Oct 2)
• spec. case cont'd
• Tensor product of matrices
• Poisson equation (partial differential equation) and its discrete version

10.  (Tu, Oct 3)
• Trade-off between the density of the grid and the sped of convergence

11.  (Mo, Oct 9)
• Eigenvalue computation: power iteration

12.  (Tu, Oct 10) -- the class is cancelled, see you on Monday

13.  (Mo, Oct 16)
• Inverse iteration
• Householder transformation
• Sturm sequence

14.  (Tu, Oct 17)
• Theorem of Sturm
• Eigenvalue localization of tridiagonal matrices by Sturm's theorem

15.  (Tu, Oct 24)
• Numerical SVD (via bidiagonal form)
• QR decomposition
• QR algorithm
• Hessenberg matrices and their QR decompositions

16.  (Mo, Oct 30)
• Computation of Hessenberg form
• QR with a shift

17.  (Tu, Oct 31)
• Eigenvalues  of Hessenberg matrices
• Lanczos method

18.  (Mo, Nov 6)
• Lanczos method cont'd (proof of correctness, speed of convergence - w/o proof)
• Courant-Fisher theorem

19.  (Tu, Nov 7)
• Proof of Courant-Fisher theorem
• Theorem of Weyl
• Eigenvalue estimates when the matrix is modified by a matrix of rank one
• Interlacing property

20.  (Mo, Nov 13)
• Proof of interlacing property
• Wielandt-Hoffman theorem
21.  (Tu, Nov 14)
• Theorem of Birkhoff on doubly stochastic matrices
• Wielandt-Hoffman for singular values
• Least squares problem -- some examples
22.  (Mo, Nov 20)
• Normal equation of Least squares problem
• Application: fitting line to data points
• (In)stability -- example
• Full rank case: solution by QR transformation
23.  (Tu, Nov 21)
• Least squares for matriix of not full rank - by SVD
• Generalized eigenvalues
• properties, examples
• the triangle case
24.  (Mo, Nov 27)
• Generalized eigenvalues cont'd
• algorithm for the symmetrical case
• by Cholesky decomposition when B is positive definite
• Intro to Linear Matrix Inequalities from the application side (by Bálint)
25.  (Tu, Nov 28)
• Linear Matrix inequalities
• basic properties
• sketch of algorithms
26.  (Mo, Dec 4)  -- the class is canceled
27.  (Tu. Dec 5)  -- the class is canceled