第零讲引言 本讲义主要介绍矩阵计算Matrix Computations,也称数值线性代数Numerical Linear Algebra) 中基本问题的数值求解方法，具体包括： ·线性方程组的直接解法 ·线性最小二乘问题的数值解法 ·非对称矩阵的特征值计算 ·对称矩阵特征值计算 ·矩阵奇异值分解 ·线性方程组的定常迭代法 ·线性方程组的Krvlov子空间迭代法 主要参紫格料 G.Golub and C.E van Loan,Matrix Computations,4th Edition,2013. J.W.Demmel,Applicd Numerical Linear Algebra,1997. L.N.Trefethen and D.Bau,III,Numerical Linear Algebra,1997. 徐树方，矩阵计算的理论与方法，1995. 二十世纪最优秀的十大算法(op10 Algorithms) We tried to assemble the 10algorithms with the greatest influence on the development and practice of science and engineering in the 20th century -Editors 1.Metropolis Algorithm for Monte Carlo/Monte Carlo method (1946) 2.Simplex Method for Linear Programming(（1947)） 3.Krvloy Subspace Iteration Methods (1950) 4.The Decompositional Approach to Matrix Computations(1951) 5.The Fortran Optimizing Compiler(1957) 5.QRAlgo ithm for Computing Eige values(1959-61) Quicksort Algorithm for Sorting (1962) 8.Fast Fouricr Transform(1965) 9.Integer Relation Detection Algorithm(1977) 10.Fast Multipole Method (1987) (下划线：属于数值线性代数：波浪线：与数值线性代数密切相关) .Dongarra and E Sullivan,Guest Editors Introduction to the top 10algorithms,Computing in Science& Engineering.2(2000).22-23.https://doi.org/10.1109/MCISE.2000.814652 B.A.Cipra,The Best of the 20th Century:Editors Name Top 10 Algorithms,SIAM News,Volume 33. Number 4.2000.https://archive.siam.org/pdf/news/637.pdf
仅供课堂教学使用，请勿外传 第零讲 引言 本讲义主要介绍矩阵计算 (Matrix Computations, 也称数值线性代数 Numerical Linear Algebra) 中基本问题的数值求解方法, 具体包括: • 线性方程组的直接解法 • 线性最小二乘问题的数值解法 • 非对称矩阵的特征值计算 • 对称矩阵特征值计算 • 矩阵奇异值分解 • 线性方程组的定常迭代法 • 线性方程组的 Krylov 子空间迭代法 主要参考资料 ▶ G. Golub and C. F. van Loan, Matrix Computations, 4th Edition, 2013. ▶ J. W. Demmel, Applied Numerical Linear Algebra, 1997. ▶ L. N. Trefethen and D. Bau, III, Numerical Linear Algebra, 1997. ▶ 徐树方, 矩阵计算的理论与方法, 1995. 二十世纪最优秀的十大算法 (Top 10 Algorithms) “We tried to assemble the 10 algorithms with the greatest influence on the development and practice of science and engineering in the 20th century” — Editors 1. Metropolis Algorithm for Monte Carlo / Monte Carlo method (1946) 2. ✿✿✿✿✿✿✿ Simplex ✿✿✿✿✿✿✿ Method✿✿✿ for✿✿✿✿✿✿ Linear✿✿✿✿✿✿✿✿✿✿✿✿ Programming (1947) 3. Krylov Subspace Iteration Methods (1950) 4. The Decompositional Approach to Matrix Computations (1951) 5. The Fortran Optimizing Compiler (1957) 6. QR Algorithm for Computing Eigenvalues (1959-61) 7. Quicksort Algorithm for Sorting (1962) 8. ✿✿✿ Fast✿✿✿✿✿✿✿ Fourier✿✿✿✿✿✿✿✿✿ Transform (1965) 9. Integer Relation Detection Algorithm (1977) 10. ✿✿✿ Fast✿✿✿✿✿✿✿✿✿ Multipole✿✿✿✿✿✿✿✿ Method (1987) (下划线: 属于数值线性代数; 波浪线: 与数值线性代数密切相关.) ▷ J. Dongarra and F. Sullivan, Guest Editors Introduction to the top 10 algorithms, Computing in Science & Engineering, 2 (2000), 22–23. https://doi.org/10.1109/MCISE.2000.814652 ▷ B. A. Cipra, The Best of the 20th Century: Editors Name Top 10 Algorithms, SIAM News, Volume 33, Number 4, 2000. https://archive.siam.org/pdf/news/637.pdf 1
2 第零讲引言 Nicholas J..Higham版本(2016 3.Singular value decomposition,QR and QZ algorithms 4.Monte-Carlo methods tion Methods 7.JPEG 8.PageRank 9.Si四pgx见eQd 10.Kalman filter N.Higham,The Mathematics,016.https://nhigham./6/3 29/the-top-10-algorithms-in-applied-mathematics/ 0.1计算数学介绍 l947年，Von Neumann和Goldstine在Bulletin of the AMS(美国数学会通报)上发表了题为 “Numerical inverting of matrices of high order”(高阶矩阵的数值求逆)的著名论文Il25],开启了现代 计算数学的研究.半个多世纪以来，伴随若计算机技术的不断进北，计算数学得到了蓬勃发展.并 逐渐成为了一个独立和重要的学科. 通俗地讲，科学计算就是通过数学建模将实际问题转化为数学问题，然后对数学问题进行离 散和数值求解，从而得到原问题的近似解，同时对得到的近似解进行误差估计，以确保近似解的可 靠性.科学计算利用先进的计算能力认识和解决复杂的科学工程问题，它融建模、算法、软件研 制和计算模拟为一体，是计算机实现其在高科技领域应用的必不可少的纽带和工具.计算已不仅 仅只是作为验证理论模型正确性的手段，大最的事例表明它已成为重大科学发现的一种重要手段 [142).科学计算已经和理论研究与实验研究一起，成为当今世界科学技术创新的主要方式[138， 也是当前公认的从事现代科学研究的第三种方法。 高性能科学计算在国家安全和科技创新等方面的重要作用也日益受到世界各国的重视.欧美 等国家已投入巨资，大力发展先进的计算方法，研制大型的实用软件.2005年6月，美国总统信息 技术咨询委员会(President's Information Technology Advisory Committee)在给美国总统提交的报告 《计算科学：确保美国章争力》(Computational science:Ensuring america'Competitiveness)中明确阐 述了计算科学的重要性.报告认为，虽然计算本身也是一门学科，但是其有促进其他学科发展的作 用，21世妃科学上最重要的、经济上最有前途的前沿研究都有可能通过先进的计算技术和计算科 学而得到解决.报告还认为，在迅猛发展的高性能计算技术推动下，计算科学将是21世纪确保国 家核心竞争能力的战略技术之一，而科学计算则是计算科学中最主要的内容。 科学计算的核心是计算数学[1421.计算数学，也称数值分析或计算方法，主要研究各种数学 问题的有效数值计算方法及其相关的数学理论，包括算法的设计与分析（收敛性，稳定性，复杂性 等).其研究内容有数值代数（饯性和非线性），数值逼近（插值，函数通近和数据拟合），数值积分与 数值微分，微分方程数值解（常微分方程，偏微分方程）.最优化理论与方法等， http://math.ecnu.edu.cn/-jypan
仅供课堂教学使用，请勿外传 · 2 · 第零讲 引言 Nicholas J. Higham 版本 (2016) 1. ✿✿✿✿✿✿✿ Newton✿✿✿✿ and ✿✿✿✿✿✿✿✿✿✿✿✿ quasi-Newton✿✿✿✿✿✿✿✿ methods 2. Matrix factorizations (LU, Cholesky, QR) 3. Singular value decomposition, QR and QZ algorithms 4. Monte-Carlo methods 5. ✿✿✿ Fast✿✿✿✿✿✿✿ Fourier✿✿✿✿✿✿✿✿✿ Transform (1965) 6. Krylov Subspace Iteration Methods 7. JPEG 8. PageRank 9. ✿✿✿✿✿✿✿ Simplex ✿✿✿✿✿✿✿ method 10. Kalman filter ▷ N. Higham, The Top 10 Algorithms in Applied Mathematics, 2016. https://nhigham.com/2016/03/ 29/the‐top‐10‐algorithms‐in‐applied‐mathematics/ 0.1 计算数学介绍 1947 年, Von Neumann 和 Goldstine 在 Bulletin of the AMS (美国数学会通报) 上发表了题为 “Numerical inverting of matrices of high order” (高阶矩阵的数值求逆) 的著名论文 [125], 开启了现代 计算数学的研究. 半个多世纪以来, 伴随着计算机技术的不断进步, 计算数学得到了蓬勃发展, 并 逐渐成为了一个独立和重要的学科. 通俗地讲, 科学计算就是通过数学建模将实际问题转化为数学问题, 然后对数学问题进行离 散和数值求解, 从而得到原问题的近似解, 同时对得到的近似解进行误差估计, 以确保近似解的可 靠性. 科学计算利用先进的计算能力认识和解决复杂的科学工程问题, 它融建模、算法、软件研 制和计算模拟为一体, 是计算机实现其在高科技领域应用的必不可少的纽带和工具. 计算已不仅 仅只是作为验证理论模型正确性的手段, 大量的事例表明它已成为重大科学发现的一种重要手段 [142]. 科学计算已经和理论研究与实验研究一起, 成为当今世界科学技术创新的主要方式 [138], 也是当前公认的从事现代科学研究的第三种方法. 高性能科学计算在国家安全和科技创新等方面的重要作用也日益受到世界各国的重视. 欧美 等国家已投入巨资, 大力发展先进的计算方法, 研制大型的实用软件. 2005 年 6 月, 美国总统信息 技术咨询委员会 (President’s Information Technology Advisory Committee) 在给美国总统提交的报告 《计算科学: 确保美国竞争力》(Computational Science: Ensuring America’s Competitiveness) 中明确阐 述了计算科学的重要性. 报告认为, 虽然计算本身也是一门学科, 但是其有促进其他学科发展的作 用, 21 世纪科学上最重要的、经济上最有前途的前沿研究都有可能通过先进的计算技术和计算科 学而得到解决. 报告还认为, 在迅猛发展的高性能计算技术推动下, 计算科学将是 21 世纪确保国 家核心竞争能力的战略技术之一, 而科学计算则是计算科学中最主要的内容. 科学计算的核心是计算数学 [142]. 计算数学, 也称数值分析或计算方法, 主要研究各种数学 问题的有效数值计算方法及其相关的数学理论, 包括算法的设计与分析 (收敛性, 稳定性, 复杂性 等). 其研究内容有数值代数 (线性和非线性), 数值逼近 (插值, 函数逼近和数据拟合), 数值积分与 数值微分, 微分方程数值解 (常微分方程, 偏微分方程), 最优化理论与方法等. http://math.ecnu.edu.cn/~jypan
0.1计算数学介绍 方有关计算数学和数值线性代数的定义可以参考Golub教授的History of numerical linear alge- bra:A personal view[5,或Trefethen教授的Numerical analysis[l2l] 计算数学的主要任务 ·算法设计：构造求解各种数学问题的高效数值方法 ·算法分析：研究数值方法的收敛性、稳定性、复杂性、计算精度等。 算法实现：编程实现、软件开发 一个好的数值方法一般需满足以下几点： ·有可靠的理论分析，即收敛性稳定性等有数学理论保证 ·有良好的计算复杂性（时间和空间）。 ·易于在计算机上编程实现， ·要有具体的数值试验来证明算法是行之有效的. 关于术语“数值方法”或“数值算法”，一般情况下我们将不加区分地使用 凸数值方法一般都是近似方法，求出的解是有误差的，因此误差分析也很重要 又供课堂教学 http://math.ecnu.edu.cn/-jypan
仅供课堂教学使用，请勿外传 0.1 计算数学介绍 · 3 · b 有关计算数学和数值线性代数的定义可以参考 Golub 教授的 History of numerical linear algebra: A personal view [51], 或 Trefethen 教授的 Numerical analysis [121]. 计算数学的主要任务 - 算法设计: 构造求解各种数学问题的高效数值方法. - 算法分析: 研究数值方法的收敛性、稳定性、复杂性、计算精度等. - 算法实现: 编程实现、软件开发. 一个好的数值方法一般需满足以下几点: • 有可靠的理论分析, 即收敛性稳定性等有数学理论保证. • 有良好的计算复杂性 (时间和空间). • 易于在计算机上编程实现. • 要有具体的数值试验来证明算法是行之有效的. b 关于术语 “数值方法” 或 “数值算法”, 一般情况下我们将不加区分地使用. b 数值方法一般都是近似方法, 求出的解是有误差的, 因此误差分析也很重要. http://math.ecnu.edu.cn/~jypan
.4 第零讲引言 0.2数值线性代数 If any other mathematical topic is as fundamental to the mathematical sciences as calculus and differential equations,it is numerical linear algebra. -Trefethen Bau III [1201,1997. ·数值代数，包含数值线性代数和数值非线性代数，是计算数学的基础142 ·数值线性代数，也称阵计算，基本问题： 线性方程组求解 Ar=b,A∈Rnxn非奇异 线性最小二乘问题 mA虹-b2,A∈Rmxm 矩阵特征值问题 Ar=A,A∈Rxm,A∈C,x∈C,x≠0 矩阵奇异值问题 AAr=2x,AE Rmxn,≥0，E∈R,E≠0 其它问题：广义特征值问题，二次特征值问题，非线性特征值问题，矩阵方程，特征值反问 题，张量计算，随机数值线性代数，等等。 ·矩阵计算常用方法技术，技巧或工具) -矩阵分解：LU分解，Cholesky分解，QR分解，Schur分解，SVD分解等1 ·矩阵分裂：定常迭代法，预处理子构造等 矩阵降维：子空间迭代法 凸问题的特殊结构对算法的设计具有非常重要的影响 凸动手编写程序对理解和掌握算法非常有帮助. 凸在实际应用中，要充分利用现有的优秀程序库 The Big Six Matrix Factorizations,Nick Higham,20 http://math.ecnu.edu.cn/-jypan
仅供课堂教学使用，请勿外传 · 4 · 第零讲 引言 0.2 数值线性代数 If any other mathematical topic is as fundamental to the mathematical sciences as calculus and differential equations, it is numerical linear algebra. — Trefethen & Bau III [120], 1997. • 数值代数, 包含数值线性代数和数值非线性代数, 是计算数学的基础 [142]. • 数值线性代数, 也称矩阵计算, 基本问题: - 线性方程组求解 Ax = b, A ∈ R n×n 非奇异. - 线性最小二乘问题 min x∈Rn ∥Ax − b∥2, A ∈ R m×n . - 矩阵特征值问题 Ax = λx, A ∈ R n×n , λ ∈ C, x ∈ C n , x ̸= 0. - 矩阵奇异值问题 A ⊺ Ax = σ 2x, A ∈ R m×n , σ ≥ 0, x ∈ R n , x ̸= 0. - 其它问题: 广义特征值问题, 二次特征值问题, 非线性特征值问题, 矩阵方程, 特征值反问 题, 张量计算, 随机数值线性代数, 等等. • 矩阵计算常用方法 (技术, 技巧或工具) - 矩阵分解: LU 分解, Cholesky 分解, QR 分解, Schur 分解, SVD 分解等 1 - 矩阵分裂: 定常迭代法, 预处理子构造等 - 矩阵降维: 子空间迭代法 b 问题的特殊结构对算法的设计具有非常重要的影响. b 动手编写程序对理解和掌握算法非常有帮助. b 在实际应用中, 要充分利用现有的优秀程序库. 1The Big Six Matrix Factorizations, Nick Higham, 2022. http://math.ecnu.edu.cn/~jypan
第一讲线性代数基础 这里介绍本讲义所涉及的线性代数基础知识，特别是线性空间和矩阵的相关基础知识】 本讲主要参考文献 R.A.Horn and C.R.Johnson,Matrix Analysis,1985.2nd edition,2013.[71] R.A.Horn and C.R.Johnson,Topics in Matrix,1991.[72] 戴华，矩阵论，2001.[1397 1.1线性空间与内积空间 1.1.1线性空间 线性空间是线性代数最基本的概念之一，它是定义在某个数域上并满足一定条件的集合.我 们首先给出数域的概念 定义11（数域）设了是包含0和1的一个数集，如果量中的任意两个数的和，差，积，商（除数不 为0)仍然在F中，则称区为一个数域 例11常见的数域有：有理数域Q,实数域R和复数域C. 白本讲义只考虑实数域R和复数域C 定义12（饯性空间）设S是一个非空集合，F是一个数城(C或R).在S上定义一种代数运算 称为加法，记为“+”（即对任意工，y∈S,都存在唯一的之∈，使得=十，并定义一个从 F×S到S的代数运算，称为数乘，记为“，”（即对任意a∈了和任意x∈S,都存在唯一的y∈S, 使得=α·.如果这两个运算满足下面的规则，则称(S,+,)是数域F上的一个线性空间（通 常简称S是数域F上的一个线性空间)： ·加法四条规则 ()交换律：x+=+x,Hx,y∈S (2)结合律：(x十)+之=x+(g+),x,,之∈S (3③)零元素：存在一个元素0，使得x+0=五，Hx∈S (④逆运算：对任意xeS,都存在负元素∈S,使得x+影=0，记=-: ·数乘四条规则 ()单位元：1x=五，1∈,x∈S (2)结合律：a·(B,x)=(aB)·x,a,BeR,x∈s 5
仅供课堂教学使用，请勿外传 第一讲 线性代数基础 这里介绍本讲义所涉及的线性代数基础知识, 特别是线性空间和矩阵的相关基础知识. 本讲主要参考文献 ▶ R. A. Horn and C. R. Johnson, Matrix Analysis, 1985. 2nd edition, 2013. [71] ▶ R. A. Horn and C. R. Johnson, Topics in Matrix Analysis, 1991. [72] ▶ 戴华, 矩阵论, 2001. [139] 1.1 线性空间与内积空间 1.1.1 线性空间 线性空间是线性代数最基本的概念之一, 它是定义在某个数域上并满足一定条件的集合. 我 们首先给出数域的概念. 定义 1.1 (数域) 设 F 是包含 0 和 1 的一个数集, 如果 F 中的任意两个数的和, 差, 积, 商 (除数不 为 0) 仍然在 F 中, 则称 F 为一个数域. 例 1.1 常见的数域有: 有理数域 Q, 实数域 R 和复数域 C. b 本讲义只考虑实数域 R 和复数域 C. 定义 1.2 (线性空间) 设 S 是一个非空集合, F 是一个数域 (C 或 R). 在 S 上定义一种代数运算, 称为加法, 记为 “+” (即对任意 x, y ∈ S, 都存在唯一的 z ∈ S, 使得 z = x + y), 并定义一个从 F × S 到 S 的代数运算, 称为数乘, 记为 “·” (即对任意 α ∈ F 和任意 x ∈ S, 都存在唯一的 y ∈ S, 使得 y = α · x). 如果这两个运算满足下面的规则, 则称 (S, +, ·) 是数域 F 上的一个线性空间 (通 常简称 S 是数域 F 上的一个线性空间): • 加法四条规则 (1) 交换律: x + y = y + x, ∀ x, y ∈ S; (2) 结合律: (x + y) + z = x + (y + z), ∀ x, y, z ∈ S; (3) 零元素: 存在一个元素 0, 使得 x + 0 = x, ∀ x ∈ S; (4) 逆运算: 对任意 x ∈ S, 都存在负元素 y ∈ S, 使得 x + y = 0, 记 y = −x; • 数乘四条规则 (1) 单位元: 1 · x = x, 1 ∈ F, ∀ x ∈ S; (2) 结合律: α · (β · x) = (αβ) · x, ∀ α, β ∈ F, x ∈ S; 5