Topics

Fall 2023

1. Tu, Sep 5
   • Errors in computations
   • Absolute and relative error, error propagation at basic operations
     
   • Finite precision, floating numbers, the error of number representations
     
   W, Sep 6
   • Vector norm definition
     
   • inner product definition
   • 1-norm, 2-norm, p-norm, infinity norm and their relations
   • Matrix norm axioms


2. Tu, Sep 12 -- no classes (Sportnap)
   W, Sep 13
   
   • Matrix norm induced by a vector norm
   • Application to 1-norm, infinity norm
   • Adjoint of a matrix, self-adjoint matrices
   • Quadratic forms, positive (semi)definite, negative (semi)definite and indefinite matrices
   • Rayleigh quotient
     
3. Tu, Sep 19
   
   • Matrix norm induced by 2-norm
   • Application for self-adjoint matrices
     
   • Spectral radius
   • Gershgorin circles
   
   W, Sep 20
   • Singular values and singular value decomposition
   • SVD and the Moore-Penrose inverse
   • 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)
   • Condition number of a matrix
   
   
4. Tu, Sep 26
   • Relation between the relative error of A and of x (when b is exact)
   • Solution by rank-one-decomposition
   • - a space-efficient version
   
   W, Sep 27
   • The special case of tridiagonal matices, formulas for the solution
   • Iterative improvement, convergence
   • General iteration for linear systems, condition for convergence
     
   • Gauss-Seidel iteration and how to compute it
5. Tu, Oct 3
   • Successive over relaxation
   • Condition for convergence
   • A special case - optimal value for SOR
   
   W, Oct 4
   • Special case cont'd
   • Application: a partial differential equation system and its discretized version
   
   
6. Tu, Oct 10
   • Application cont'd
   • Gradient method
   • Conjugate directions
   
   W, Oct 11
   • Conjugate gradient method
   • Eigenvalue computation: power iteration
   
   


7. Tu, Oct 17
   • Power iteration
   • Inverse iteration
   
   W, Oct 18
   • Tridiagonalization
   • -- by involutary transformation (Householder transformation)
   • Sturm sequence
   • Theorem of Sturm
   
   
8. Tu, Oct 24
   • Eigenvalue localization of tridiagonal matrices by Sturm's theorem
   • Numerical SVD (via bidiagonal form)
   
   W, Oct 25
   • Numerical SVD example
   • QR decomposition
   • Hessenberg matrices


9. Tu, Oct 31


• Hessenberg matrices and their QR decompositions
• Computation of Hessenberg form
• QR with a shift
  
• Eigenvectors of Hessenberg matrices

W, Nov 1 - no classes


10. Tu, Nov 7
    • Lanczos method
    
    We, Nov 8
    • Lanczos method -- some proofs
    • Courant-Fisher theorem


11. Tu, Nov 14
    • Courant-Fisher theorem - proof
    • Theorem of Weyl
    • Interlacing property
    • Wielandt-Hoffman theorem
    We, Nov 15
    • Least square problem, normal equation


12. Tu, Nov 21
    • Non-negative and positive matrices
    • Primitive and irreducible matrices
    • Perron-Frobenius theorem
    
    W, Nov 22
    • Perron-Frobenius theorem -- some proofs
    • An application: nonnegative solution for x=Ax+b ( A, b nonnegative)


13. Tu, Nov 28 -- class is canceled
    
    W, Nov 29
    • Further properties od nonnegative matrices
    • Application: stochastic matrices


14. Tu, Dec 5

• Random simplification, sparsification pf matrices
• Matrix sampling