Numerical Linear Algebra (Fall 2023)

Numerical Linear Algebra 数值线性代数 数值线性代数主要涉及高效处理向量和矩阵的本质思想，这些思想可以拓展应用到函数和算子。从这个意义上来说，数值线性代数实际上是泛函分析，但她始终强调实用的算法思想及其数学原理。如果说有其他数学科目像微积分和微分方程一样基础的话，那就是数值线性代数。

• Prerequisites:   Mathematical Analysis, Advanced Algebra, Matlab Programming

• Highlights:   专业核心课程，深入探讨数值线性代数

• Classroom quizzes:

  • Quiz I (Lectures 1 – 4), 2023年10月30日星期一10:00 – 12:00，海韵教学楼201

  • Quiz II (Lectures 5 – 10), 2023年12月11日星期一10:00 – 12:00，海韵教学楼201

• Final exam (Lectures 1 – 12), 2024年1月2日星期二10:30 – 12:30，海韵教学楼202

• Grading Policy: Assignments 30% + Classroom quizzes 20% + Final exam 50%

Instructor

• Kui Du, Email: kuidu@xmu.edu.cn Tel: 0592-2580672; Office: R536 Math & Phys Building, Haiyun Campus
  答疑：周一 11:50 – 12:30，周三 11:50 – 12:30，海韵教学楼201

• Teaching Assistant: Fang Wang 王方, Email: wangfangwf97@163.com

References

• Numerical Linear Algebra (NLA), Lloyd N. Trefethen and David Bau, III, SIAM, 1997. Twenty-fifth Anniversary Edition, 2022

• Applied Numerical Linear Algebra (ANLA), James Demmel, SIAM, 1997

• Matrix Analysis and Applied Linear Algebra (MAALA), Study and Solutions Guide, Carl D. Meyer, 2nd Edition, SIAM, 2023

• Numerical Linear Algebra An Introduction (NLAI), Holger Wendland, Cambridge University Press, 2018

• Iterative Methods and Preconditioners for Systems of Linear Equations (IMPSLE), Gabriele Ciaramella and Martin J. Gander, SIAM, 2022

• 数值线性代数, 徐树方, 高立, 张平文, 第二版, 北京大学出版社, 2013

• 数值线性代数, 曹志浩, 复旦大学出版社, 1996

• MathWorks MATLAB 帮助中心

Lecture Notes

• Lecture 1: Inner product, Orthogonality, Vector/Matrix norms.

• Lecture 2: Singular value decomposition (SVD).

• Lecture 3: Projector, Classical/Modified Gram–Schmidt orthogonalization, QR factorization.

• Lecture 4: Householder reflector, Givens rotation, Least squares problem.

• Lecture 5: LU factorization, Cholesky factorization, Gaussian elimination with pivoting.

• Lecture 6: Stationary iterative methods.

• Lecture 7: Eigenvalue problem.

• Lecture 8: Power/Inverse iteration, Rayleigh quotient iteration.

• Lecture 9: QR algorithm.

• Lecture 10: Jacobi method, Bisection method, Divide-and-conquer method.

• Lecture 11: Krylov subspace, Generalized minimal residual method.

• Lecture 12: Conjugate gradients.    (Proof of Theorem 1)

• Lecture 13: Biorthogonalization methods.

• Lecture 14: Krylov subspace methods for least squares problems.

• Lecture 15: Krylov subspace methods for eigenvalue problems.

• Lecture 16: From Lanczos to Gauss quadrature.

• Lecture 17: FFT and structured matrices.

• Lecture 18: Multigrid.

• Lecture 19: Conditioning of a problem.

• Lecture 20: Backward stability of an algorithm.

Assignments

• Policy: Late submission will not be accepted. No exceptions! 不接受迟交的作业。不接受任何理由!

• Assignment for Lecture 1. (100 points) 2023年9月20日（星期三）10点10分前交（以上课铃声为准，下同）

• Assignment for Lecture 2. (120 points) 2023年10月9日（星期一）10点10分前交

• Assignment for Lecture 3. (100 points) 2023年10月18日（星期三）10点10分前交

• Assignment for Lecture 4. (120 points) 2023年10月30日（星期一）10点10分前交

• Assignment for Lecture 5. (80 points) 2023年11月13日（星期一）10点10分前交

• Assignment for Lecture 6. (50 points) 2023年11月20日（星期一）10点10分前交

• Assignment for Lecture 7. (90 points) 2023年11月27日（星期一）10点10分前交

• Assignment for Lecture 8. (30 points) 2023年11月27日（星期一）10点10分前交

• Assignment for Lecture 9. (40 points) 2023年12月4日（星期一）10点10分前交

• Assignment for Lecture 10. (60 points) 2023年12月11日（星期一）10点10分前交

• Assignment for Lecture 11. (60 points) 2023年12月25日（星期一）10点10分前交

• Assignment for Lecture 12. (80 points) 2023年12月29日（星期五）10点10分前交

• Assignment for Lecture 13. (30 points)

• Assignment for Lecture 14. (40 points)

• Assignment for Lecture 15. (20 points)

• Assignment for Lecture 16. (20 points)

• Assignment for Lecture 17. (60 points)

• Assignment for Lecture 18. (20 points)

• Assignment for Lecture 19. (50 points)

• Assignment for Lecture 20. (30 points)

Other

• The Matrix Cookbook, Kaare Brandt Petersen and Michael Syskind Pedersen

• 矩阵求导术(上), 矩阵求导术(下)

• The Singular Value Decomposition, Applications and Beyond, Zhihua Zhang, arXiv:1510.08532, 2015

• Image Compression with Singular Value Decomposition, Tim Baumann

• The History of Numerical Analysis and Scientific Computing, SIAM

• Branches of Mathematics: Numerical analysis, Lloyd N. Trefethen, Princeton U. Press, 2008.

• 矩阵计算 / 数值线性代数, 华东师范大学, 潘建瑜

• Matrix Computations / Numerical Linear Algebra, U.C. Berkeley, James Demmel

• Computational Aspects of Matrix Theory, University of Minnesota, Yousef Saad