01_矩阵计算/线性代数基础

1 .矩阵计算 潘建瑜 华东师范大学数学系 

2 . 课程主要内容 • 线性方程组的直接解法 • 线性最小二乘问题的数值算法 • 非对称矩阵的特征值计算 • 对称矩阵特征值计算与奇异值分解 • 线性方程组迭代算法 • 特征值问题的迭代算法 (部分特征值和特征向量) 

3 .主要参考资料 • G. H. Golub and C. F. van Loan, “Matrix Computations (4th),” 2013. 对应中文版为:《矩阵计算》(第三版), 袁亚湘等译, 2001. • J. W. Demmel, “Applied Numerical Linear Algebra,” 1997. 对应中文版为:《应用数值线性代数》, 王国荣译, 2007. • L. N. Trefethen and D. Bau, III, “Numerical Linear Algebra,” 1997. 对应中文版为:《数值线性代数》, 陆金甫等译, 2006. • 徐树方, “矩阵计算的理论与方法,” 北京大学出版社, 1995. • 曹志浩, “数值线性代数,” 复旦大学出版社, 1996. 课程主页 http://math.ecnu.edu.cn/~jypan/Teaching/MatrixComp/ 

4 . 引言 计算数学, 也称 数值分析 或 计算方法. 1947 年 Von Neumann 和 Goldstine 在《美国数学会通报》发表了题为“高 阶矩阵的数值求逆”的著名论文, 开启了现代计算数学的研究 一般来说, 计算数学主要研究如何求出数学问题的近似解 (数值解), 包括 算法的设计与分析 (收敛性, 稳定性, 复杂性等) 计算数学主要研究内容: 数值逼近, 数值微积分, 数值代数, 微分方程数 值解, 最优化等 3/70 

5 . 为什么计算数学 科学计算是 20 世纪重要科学技术进步之一, 已与理论研究和实验研究相 并列成为科学研究的第三种方法. 现今科学计算已是体现国家科学技术 核心竞争力的重要标志, 是国家科学技术创新发展的关键要素 —— 国家自然科学基金 · 重大项目指南, 2014 计算科学是 21 世纪确保国家核心竞争能力的战略技术之一 —— 计算科学: 确保美国竞争力，2005 科学计算的核心/数学基础: 计算数学. 4/70 

6 .矩阵计算 (数值线性代数) 的重要性 If any other mathematical topic is as fundamental to the mathematical sciences as calculus and differential equations, it is numerical linear algebra. — Trefethen & Bau, 1997. 5/70 

7 .国家自然科学基金委员会关于计算数学的分类 (2018): • 计算数学与科学工程计算 (A0117) - 偏微分方程数值解 (A011701) - 流体力学中的数值计算 (A011702) - 一般反问题的计算方法 (A011703) - 常微分方程数值计算 (A011704) - 数值代数 (A011705) - 数值逼近与计算几何 (A011706) - 谱方法及高精度数值方法 (A011707) - 有限元和边界元方法 (A011708) - 多重网格技术与区域分解 (A011709) - 自适应方法 (A011720) - 并行计算 (A011711) 6/70 

8 .计算数学的主要任务 • 算法设计: 构造求解各种数学问题的数值方法 • 算法分析: 收敛性、稳定性、复杂性、计算精度等 • 算法实现: 编程实现、软件开发 好的数值方法一般需满足以下几点: • 有可靠的理论分析, 即收敛性稳定性等有数学理论保证 • 有良好的计算复杂性 (时间和空间) • 易于在计算机上实现 • 要有具体的数值试验来证明是行之有效的 矩阵计算基本问题 数值代数: 数值线性代数 (矩阵计算) 和数值非线性代数 7/70 

9 .数值线性代数 (矩阵计算) 主要研究以下问题: • 线性方程组求解 Ax = b, A ∈ Rn×n 非奇异 • (线性) 最小二乘问题 min ∥Ax − b∥2 , A ∈ Rm×n , m ≥ n x∈Rn 8/70 

10 .• 矩阵特征值问题 Ax = λx, A ∈ Rn×n , λ ∈ C, x ∈ Cn , x ̸= 0 • 矩阵奇异值问题 AT Ax = σ 2 x, A ∈ Rm×n , σ ≥ 0, x ∈ Rn , x ̸= 0 • 其它问题: 广义特征值问题, 二次特征值问题, 非线性特征值问题, 矩阵方程, 特 征值反问题, 张量计算, . . . . . . † 数值方法一般都是近似方法, 求出的解是有误差的, 因此误差分析非 常重要. 9/70 

11 .矩阵计算常用方法 (技术或技巧) • 矩阵分解 • 矩阵分裂 • 扰动分析 † 问题的特殊结构对算法的设计具有非常重要的影响. † 在编程实现时, 要充分利用现有的优秀程序库. 10/70 

12 .二十世纪十大优秀算法 (SIAM News, 2000) 1. 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) 11/70 

13 .第一讲 线性代数基础 1 线性空间与内积空间 2 向量范数与矩阵范数 3 矩阵与投影 4 矩阵标准型 5 几类特殊矩阵 6 Kronecker 积 

14 .1 线性空间与内积空间 • 数域, 如: Q, R, C • 线性空间, 如: Rn , Cn , Rm×n • 线性相关与线性无关, 秩, 基, 维数 • 线性子空间 • 像空间 (列空间, 值域) Ran(A), 零空间 (核) Ker(A) • 张成子空间: span{x1 , x2 , . . . , xk }, span(A) = Ran(A) 13/70 

15 . 直和 设 S1 , S2 是子空间, 若 S1 + S2 中的任一元素都可唯一表示成 x = x1 + x2 , x1 ∈ S1 , x2 ∈ S2 , 则称 S1 + S2 为直和, 记为 S1 ⊕ S2 . 定理 设 S1 是 S 的子空间, 则存在另一个子空间 S2 , 使得 S = S1 ⊕ S2 . 例 例: 设 A ∈ Cm×n , 则 Cn = Ker(A) ⊕ Ran(A∗ ), Cm = Ker(A∗ ) ⊕ Ran(A) 14/70 

16 .内积空间 • 内积, 内积空间, 欧氏空间, 酉空间 • 常见内积空间: - Cn : (x, y) = y ∗ x - Rn : (x, y) = y T x - Rm×n : (A, B) = tr(B T A) 正交与正交补 • 正交: 向量正交, 子空间正交 • 正交补: 存在且唯一 15/70 

17 .2 向量范数与矩阵范数 定义 (向量范数) 若函数 f : Cn → R 满足 (1) f (x) ≥ 0, ∀ x ∈ Cn , 等号当且仅当 x = 0 时成立; (2) f (αx) = |α| · f (x), ∀ x ∈ Cn , α ∈ C; (3) f (x + y) ≤ f (x) + f (y), ∀x, y ∈ Cn ; 则称 f (x) 为 Cn 上的范数, 通常记作 ∥ · ∥ 相类似地, 我们可以定义实数空间 Rn 上的向量范数. 16/70 

18 .常见的向量范数: • 1-范数: ∥x∥1 = |x1 | + |x2 | + · · · + |xn | √ • 2-范数: ∥x∥2 = |x1 |2 + |x2 |2 + · · · + |xn |2 • ∞-范数: ∥x∥∞ = max |xi | 1≤i≤n ( )1/p ∑ n • p-范数: ∥x∥p = |xi | p , 1≤p<∞ i=1 17/70 

19 .定义 (范数的等价性) Cn 上的向量范数 ∥ · ∥α 与 ∥ · ∥β 等价: 存在正常数 c1 , c2 , 使得 c1 ∥x∥α ≤ ∥x∥β ≤ c2 ∥x∥α , ∀ x ∈ Cn 定理 Cn 空间上的所有向量范数都是等价的, 特别地, 有 √ ∥x∥2 ≤ ∥x∥1 ≤ n ∥x∥2 , √ ∥x∥∞ ≤ ∥x∥2 ≤ n ∥x∥∞ , ∥x∥∞ ≤ ∥x∥1 ≤ n ∥x∥∞ . (证明留作练习) 18/70 

20 .定理 (Cauchy-Schwartz 不等式) 设 (·, ·) 是 Cn 上的内积, 则 对任意 x, y ∈ Cn , 有 |(x, y)|2 ≤ (x, x) · (y, y) (证明留作练习) △ √ 推论 设 (·, ·) 是 Cn 上的内积, 则 ∥x∥ = (x, x) 是 Cn 上的 一个向量范数. (证明留作练习) 定理 (范数的连续性) 设 ∥ · ∥ 是 Cn 上的一个向量范数, 则 △ f (x) = ∥x∥ 是 Cn 上的连续函数. 19/70 

21 . 矩阵范数 定义 (矩阵范数) 若函数 f : Cn×n → R 满足 (1) f (A) ≥ 0, ∀ A ∈ Cn×n , 等号当且仅当 A = 0 时成立; (2) f (αA) = |α| · f (A), ∀ A ∈ Cn×n , α ∈ C; (3) f (A + B) ≤ f (A) + f (B), ∀A, B ∈ Cn×n ; 则称 f (x) 为 Cn×n 上的范数, 通常记作 ∥ · ∥. 相容的矩阵范数: f (AB) ≤ f (A)f (B), ∀ A, B ∈ Cn×n 若未明确指出, 讲义所涉及矩阵范数都指相容矩阵范数 20/70 

22 .引理 设 ∥ · ∥ 是 Cn 上的向量范数, 则 △ ∥Ax∥ ∥A∥ = sup = max ∥Ax∥ x∈Cn , x̸=0 ∥x∥ ∥x∥=1 是 Cn×n 上的范数, 称为算子范数, 或诱导范数, 导出范数. † 算子范数都是相容的, 且 ∥Ax∥ ≤ ∥A∥ · ∥x∥, A ∈ Cn×n , x ∈ Cn † 类似地, 我们可以定义 Cm×n , Rn×n , Rm×n 上的矩阵范数. 21/70 

23 .引理 可以证明: ( ) ∑ n (1) 1-范数 (列范数): ∥A∥1 = max |aij | 1≤j≤n ( i=1 ) ∑n (2) ∞-范数 (行范数): ∥A∥∞ = max |aij | 1≤i≤n j=1 √ (3) 2-范数 (谱范数): ∥A∥2 = ρ(AT A) (证明留作练习) ∑ n ∑ n 另一个常用范数 F -范数 ∥A∥F = |aij |2 i=1 j=1 22/70 

24 .定理 (矩阵范数的等价性) Rn×n 空间上的所有范数都是等 价的, 特别地, 有 1 √ √ ∥A∥2 ≤ ∥A∥1 ≤ n ∥A∥2 , n 1 √ √ ∥A∥2 ≤ ∥A∥∞ ≤ n ∥A∥2 , n 1 ∥A∥∞ ≤ ∥A∥1 ≤ n ∥A∥∞ , n 1 √ √ ∥A∥1 ≤ ∥A∥F ≤ n ∥A∥2 . n (证明留作练习) 23/70 

25 .矩阵范数的一些性质 • 对任意的算子范数 ∥ · ∥, 有 ∥I∥ = 1 • 对任意的相容范数 ∥ · ∥, 有 ∥I∥ ≥ 1 • F -范数是相容的, 但不是算子范数 • ∥ · ∥2 和 ∥ · ∥F 是酉不变范数 • ∥AT ∥2 = ∥A∥2 , ∥AT ∥1 = ∥A∥∞ • 若 A 是正规矩阵, 则 ∥A∥2 = ρ(A) 24/70 

26 . 向量序列的收敛 { }∞ 设 x(k) k=1 是 Cn 中的一个向量序列, 如果存在 x ∈ Cn , 使得 (k) lim xi = xi , i = 1, 2, . . . , n, k→∞ { } 则称 x(k) (按分量) 收敛到 x, 记为 lim x(k) = x. k→∞ 定理 设 ∥ · ∥ 是 Cn 上的任意一个向量范数, 则 lim x(k) = x k→∞ 的充要条件是 lim ∥x(k) − x∥ = 0. k→∞ 25/70 

27 . 收敛速度 设点列 {εk }∞ k=1 收敛, 且 lim εk = 0. 若存在一个有界常数 k=∞ 0 < c < ∞, 使得 |εk+1 | lim = c, k→∞ |εk |p 则称点列 {εk } 是 p 次 (渐进) 收敛的. 若 1 < p < 2 或 p = 1 且 c = 0, 则称点列是超线性收敛的. † 类似地, 我们可以给出矩阵序列的收敛性和判别方法. 26/70 

28 .3 矩阵与投影 特征值与特征向量 • 特征多项式, 特征值, 特征向量, 左特征向量, 特征对 • n 阶矩阵 A 的谱: σ(A) {λ1 , λ2 , . . . , λn } • 代数重数和几何重数, 特征空间 • 最小多项式 • 可对角化, 特征值分解 • 可对角化的充要条件 • 特征值估计: Bendixson 定理, 圆盘定理 27/70 

29 . Bendixson 定理 1 1 设 A ∈ Cn×n , 令 H = (A + A∗ ), S = (A − A∗ ). 则有 2 2 λmin (H) ≤ Re(λ(A)) ≤ λmax (H), λmin (iS) ≤ Im(λ(A)) ≤ λmax (iS), 其中 Re(·) 和 Im(·) 分别表示实部和虚部. † 一个矩阵的特征值的实部的取值范围由其 Hermite 部分 确定, 而虚部则由其斜 Hermite 部分确定. 28/70