矩阵计算讲义
目 录 第零讲 引言 1 0.1 计算数学介绍 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 0.2 数值线性代数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 第一讲 线性代数基础 5 1.1 线性空间与内积空间 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.1.1 线性空间 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.1.2 内积空间 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.1.3 正交与正交补 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.2 矩阵与投影 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.2.1 矩阵的秩 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.2.2 特征值与特征向量 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.2.3 特征值的粗略估计 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.2.4 不变子空间 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.2.5 投影变换 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.3 向量范数与矩阵范数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.3.1 向量范数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.3.2 矩阵范数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 1.3.3 谱半径与范数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 1.3.4 最佳逼近与正交投影 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 1.4 矩阵标准型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 1.4.1 Jordan 标准型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 1.4.2 Schur 分解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 1.5 几类特殊矩阵 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 1.5.1 对称正定矩阵 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 1.5.2 对角占优矩阵 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 1.5.3 不可约矩阵 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 1.6 Kronecker 积 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 1.7 课后习题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 iii
· iv · 目 录 第二讲 线性方程组直接方法 38 2.1 LU 分解与 Gauss 消去法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 2.1.1 LU 分解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 2.1.2 LU 分解的实现 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 2.1.3 Gauss 消去法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.1.4 选主元 LU 分解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 2.1.5 矩阵求逆 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 2.1.6 分块 LU 分解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 2.2 特殊方程组的求解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 2.2.1 对称正定线性方程组 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 2.2.2 对称不定线性方程组 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 2.2.3 三对角线性方程组 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 2.2.4 带状线性方程组 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 2.2.5 Toeplitz 线性方程组 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 2.3 扰动分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 2.3.1 矩阵条件数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 2.3.2 δx 与 xˆ 的关系 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 2.3.3 δx 与 x∗ 的关系 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 2.3.4 δx 与残量的关系 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 2.3.5 相对扰动分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 2.4 误差分析 * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 2.4.1 LU 分解的舍入误差分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 2.4.2 Gauss 消去法的舍入误差分析 . . . . . . . . . . . . . . . . . . . . . . . . . . 66 2.5 解的改进 * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 2.5.1 高精度运算 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 2.5.2 矩阵元素缩放或平衡 (Scaling or equilibration) . . . . . . . . . . . . . . . . . . 68 2.5.3 迭代改进法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 2.6 课后习题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 第三讲 线性最小二乘问题 73 3.1 问题介绍 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 3.1.1 超定方程组 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 3.1.2 欠定方程组 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 3.2 几类重要的矩阵变换 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
目 录 · v · 3.2.1 初等矩阵变换 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 3.2.2 Gauss 变换 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 3.2.3 Householder 变换 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 3.2.4 Givens 变换 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 3.2.5 正交变换的舍入误差分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 3.3 QR 分解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 3.3.1 QR 分解的存在性与唯一性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 3.3.2 基于 MGS 的 QR 分解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 3.3.3 基于 Householder 变换的 QR 分解 . . . . . . . . . . . . . . . . . . . . . . . . 86 3.3.4 列主元 QR 分解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 3.3.5 基于 Givens 变换的 QR 分解 . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 3.3.6 QR 分解的稳定性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 3.4 奇异值分解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 3.4.1 奇异值，奇异向量和奇异值分解 . . . . . . . . . . . . . . . . . . . . . . . . 94 3.4.2 奇异值基本性质 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 3.4.3 奇异值更多性质 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 3.4.4 奇异值扰动分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 3.5 线性最小二乘问题的求解方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 3.5.1 正规方程 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 3.5.2 Cholesky 分解法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 3.5.3 QR 分解法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 3.5.4 奇异值分解法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 3.6 广义逆与最小二乘 * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 3.6.1 广义逆 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 3.6.2 广义逆基本性质 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 3.6.3 广义逆的计算 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 3.6.4 广义逆与线性最小二乘 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 3.6.5 左逆和右逆 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 3.7 最小二乘扰动分析 * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 3.8 推广与应用 * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 3.8.1 最小二乘问题的推广 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 3.8.2 最小二乘问题的应用 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 3.9 课后习题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
· vi · 目 录 第四讲 非对称特征值问题 114 4.1 幂迭代法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 4.1.1 算法介绍 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 4.1.2 收敛性分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 4.1.3 位移策略 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 4.2 反迭代法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 4.2.1 算法介绍 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 4.2.2 Rayleigh 商迭代 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 4.3 正交迭代法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 4.4 QR 迭代法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 4.4.1 QR 迭代与幂迭代的关系 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 4.4.2 QR 迭代与反迭代的关系 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 4.4.3 QR 迭代与正交迭代的关系 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 4.4.4 QR 迭代的收敛性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 4.4.5 带位移的 QR 迭代法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 4.5 带位移的隐式 QR 迭代法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 4.5.1 上 Hessenberg 矩阵 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 4.5.2 隐式 QR 迭代 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 4.5.3 位移的选取 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 4.5.4 收缩 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 4.6 特征向量的计算 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 4.7 广义特征值问题 * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 4.7.1 广义特征值基本理论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 4.7.2 广义 Schur 分解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 4.7.3 QZ 迭代法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 4.8 应用 * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 4.8.1 多项式求根 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 4.8.2 Goolge 网页排名：PageRank . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 4.9 课后习题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 第五讲 对称特征值问题 141 5.1 Jacobi 迭代法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 5.2 Rayleigh 商迭代法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 5.3 对称 QR 迭代法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
目 录 · vii · 5.4 分而治之法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 5.5 对分法和反迭代法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 5.6 奇异值分解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 5.6.1 二对角化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 5.6.2 Golub-Kahan SVD 算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160 5.6.3 dqds 算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160 5.6.4 Jacobi 算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162 5.7 扰动分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164 5.7.1 特征值与 Rayleigh 商 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164 5.7.2 对称矩阵特征值的扰动分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 5.7.3 对称矩阵特征向量的扰动 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 5.7.4 Rayleigh 商逼近 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168 5.7.5 相对扰动分析 * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168 5.8 应用: SVD 与图像压缩 * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170 5.9 课后习题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 第六讲 线性方程组基本迭代法 173 6.1 矩阵分裂与迭代法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176 6.1.1 Jacobi 迭代法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176 6.1.2 Gauss-Seidel 迭代法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177 6.1.3 SOR 迭代法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178 6.1.4 SSOR 迭代法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179 6.1.5 AOR 迭代法 * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180 6.1.6 Richardson 迭代法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180 6.1.7 分块迭代法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 6.2 收敛性分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182 6.2.1 基本概念 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182 6.2.2 不可约对角占优矩阵 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184 6.2.3 对称正定矩阵 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185 6.2.4 相容次序矩阵 * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186 6.3 应用: Poisson 方程求解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190 6.3.1 一维 Poisson 方程 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190 6.3.2 二维 Poisson 方程 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191 6.3.3 收敛性分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
· viii · 目 录 6.3.4 快速求解方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197 6.4 加速方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201 6.4.1 外推技术 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201 6.4.2 Chebyshev 多项式加速 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202 6.5 交替方向法与 HSS 迭代法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207 6.5.1 多步迭代法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207 6.5.2 交替方向法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207 6.5.3 HSS 方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208 6.6 课后习题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210 第七讲 Krylov 子空间迭代法 213 7.1 Krylov 子空间 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213 7.1.1 Arnoldi 过程与 Lanczos 过程 . . . . . . . . . . . . . . . . . . . . . . . . . . . 213 7.1.2 Krylov 子空间方法一般格式 . . . . . . . . . . . . . . . . . . . . . . . . . . . 216 7.2 GMRES 方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218 7.2.1 算法描述 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218 7.2.2 具体实施细节 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219 7.2.3 GMRES 方法的中断 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222 7.2.4 带重启的 GMRES 方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222 7.3 共轭梯度法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224 7.3.1 算法基本过程 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224 7.3.2 实用迭代格式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224 7.4 收敛性分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229 7.4.1 CG 的收敛性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229 7.4.2 CG 的超收敛性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230 7.4.3 GMRES 的收敛性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231 7.5 预处理方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235 7.5.1 预处理方法介绍 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235 7.5.2 预处理 CG 方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236 7.5.3 预处理 GMRES 方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239 7.5.4 预处理子构造 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241 7.6 课后习题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244 参考文献 245
第零讲 引言 本讲义主要介绍矩阵计算 (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. 0.1 计算数学介绍 1947 年, Von Neumann 和 Goldstine 在 Bulletin of the AMS (美国数学会通报) 上发表了题为 “Numerical inverting of matrices of high order” (高阶矩阵的数值求逆) 的著名论文 [130], 开启了现代 计算数学的研究. 半个多世纪以来, 伴随着计算机技术的不断进步, 计算数学得到了蓬勃发展, 并 逐渐成为了一个独立和重要的学科. 通俗地讲, 科学计算就是通过数学建模将实际问题转化为数学问题, 然后对数学问题进行离 散和数值求解, 从而得到原问题的近似解, 同时对得到的近似解进行误差估计, 以确保近似解的可 靠性. 科学计算利用先进的计算能力认识和解决复杂的科学工程问题, 它融建模、算法、软件研 制和计算模拟为一体, 是计算机实现其在高科技领域应用的必不可少的纽带和工具. 计算已不仅 仅只是作为验证理论模型正确性的手段, 大量的事例表明它已成为重大科学发现的一种重要手段 [147]. 科学计算已经和理论研究与实验研究一起, 成为当今世界科学技术创新的主要方式 [143], 也是当前公认的从事现代科学研究的第三种方法. 高性能科学计算在国家安全和科技创新等方面的重要作用也日益受到世界各国的重视. 欧美 等国家已投入巨资, 大力发展先进的计算方法, 研制大型的实用软件. 2005 年 6 月, 美国总统信息 技术咨询委员会 (President’s Information Technology Advisory Committee) 在给美国总统提交的报告 《计算科学: 确保美国竞争力》(Computational Science: Ensuring America’s Competitiveness) 中明确阐 述了计算科学的重要性. 报告认为, 虽然计算本身也是一门学科, 但是其有促进其他学科发展的作 1
· 2 · 第零讲 引言 用, 21 世纪科学上最重要的、经济上最有前途的前沿研究都有可能通过先进的计算技术和计算科 学而得到解决. 报告还认为, 在迅猛发展的高性能计算技术推动下, 计算科学将是 21 世纪确保国 家核心竞争能力的战略技术之一, 而科学计算则是计算科学中最主要的内容. 科学计算的核心是计算数学 [147]. 计算数学, 也称数值分析或计算方法, 主要研究各种数学 问题的有效数值计算方法及其相关的数学理论, 包括算法的设计与分析 (收敛性, 稳定性, 复杂性 等). 其研究内容有数值代数 (线性和非线性), 数值逼近 (插值, 函数逼近和数据拟合), 数值积分与 数值微分, 微分方程数值解 (常微分方程, 偏微分方程), 最优化理论与方法等. b 有关计算数学和数值线性代数的定义可以参考 Golub 教授的 History of numerical linear algebra: A personal view [52], 或 Trefethen 教授的 Numerical analysis [126]. 计算数学的主要任务 - 算法设计: 构造求解各种数学问题的高效数值方法. - 算法分析: 研究数值方法的收敛性、稳定性、复杂性、计算精度等. - 算法实现: 编程实现、软件开发. 一个好的数值方法一般需满足以下几点: • 有可靠的理论分析, 即收敛性稳定性等有数学理论保证. • 有良好的计算复杂性 (时间和空间). • 易于在计算机上编程实现. • 要有具体的数值试验来证明算法是行之有效的. b 关于术语 “数值方法” 或 “数值算法”, 一般情况下我们将不加区分地使用. b 数值方法一般都是近似方法, 求出的解是有误差的, 因此误差分析也很重要
0.2 数值线性代数 · 3 · 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 [125], 1997. • 数值代数, 包含数值线性代数和数值非线性代数, 是计算数学的基础 [147]. • 数值线性代数, 也称矩阵计算, 基本问题: - 线性方程组求解 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 TAx = σ 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