目录 第零讲引言 0.1计算数学介绍 2 0.2数值线性代数 第一讲线性代数基础 11线性空间与内积空间 111线性空间.…… 112内积空间.，. 113正交与正交补·…：…。…………… 9 12矩阵与投影。，… 121矩阵的秩。。…………… 10 1.2.2特征值与特征向量 ·…。。··…。…。。…·。·…。。·…。…。…。 12 1.2.3特征值的粗略估计 。。。。。。。。。。，。。g·。。。。。。。。。 14 1.2.4不变子空间 15 125投影变换。………… 16 13向量范数与矩阵范数………………… 19 131向量范数。…………………… 19 132矩阵范数…………………… 21 1.3.3谱半径与范数 23 1.3.4最佳通近与正交投影 24 1.4矩阵标准型....。.. 25 1.4.1 Jordan标准型.. 25 1.4.2Shur分解.. 26 1.5几类特殊矩阵，。.。 27 151对称正定矩阵…… 152对角占优矩阵…·……··…·· 28 153不可约矩阵. 28 1.6 Kronecker积31
仅供课堂教学使用，请勿外传 目 录 第零讲 引言 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 不可约矩阵 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 1.6 Kronecker 积 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 iii
.iv. 目录 第二讲线性方程组直接方法 33 21U分解与Gas消去法.·· 34 2.1.1LU分解 。。， 34 2.1.2LU分解的实现 35 213Gau消去法.…… 38 2.1.4选主元LU分解 ……………………… 0 215矩阵求逆…·到 2.1.6分块1U分解 22特殊方程组的求球解··………· 43 221对称正定线性方程组·…·……… 43 2.2.2对称不定线性方程组 45 2.2.3三对角线性方程组 22.4带状线性方程组.··，。···········… 2.2.5 Toeplitz线性方程组 23扰动分析·…·…………···…………·…… 54 2.3.1矩阵条件数 54 232与的关系.…………… 55 2.3.36x与x,的关系 55 23.4x与残量的关系.… 56 23.5相对扰动分析。··。··… 2.4误差分析·..·，·.· 59 2.41LU分解的舍入误差分析.····················· 59 2.4.2Gaus消去法的舍入误差分析 25解的改进··… 2.5.1高精度运算 61 2.52矩阵元素缩放或平衡())········ 61 2.5.3迭代改进法 61 第三讲线性最小二乘问题 63 31间题介绍。·…·…·………· 3.11超定方程组 6 3.1.2欠定方程组 64 3.2几类重要的矩阵变换 65 3.2.1初等矩阵变换 65 http://math.ecnu.edu.cn/-jypan
仅供课堂教学使用，请勿外传 · iv · 目 录 第二讲 线性方程组直接方法 33 2.1 LU 分解与 Gauss 消去法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.1.1 LU 分解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.1.2 LU 分解的实现 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.1.3 Gauss 消去法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 2.1.4 选主元 LU 分解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 2.1.5 矩阵求逆 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 2.1.6 分块 LU 分解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 2.2 特殊方程组的求解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.2.1 对称正定线性方程组 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.2.2 对称不定线性方程组 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 2.2.3 三对角线性方程组 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 2.2.4 带状线性方程组 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 2.2.5 Toeplitz 线性方程组 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 2.3 扰动分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 2.3.1 矩阵条件数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 2.3.2 δx 与 xˆ 的关系 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 2.3.3 δx 与 x∗ 的关系 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 2.3.4 δx 与残量的关系 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 2.3.5 相对扰动分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 2.4 误差分析 * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 2.4.1 LU 分解的舍入误差分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 2.4.2 Gauss 消去法的舍入误差分析 . . . . . . . . . . . . . . . . . . . . . . . . . . 59 2.5 解的改进 * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 2.5.1 高精度运算 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 2.5.2 矩阵元素缩放或平衡 (Scaling or equilibration) . . . . . . . . . . . . . . . . . . 61 2.5.3 迭代改进法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 第三讲 线性最小二乘问题 63 3.1 问题介绍 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 3.1.1 超定方程组 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 3.1.2 欠定方程组 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 3.2 几类重要的矩阵变换 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 3.2.1 初等矩阵变换 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 http://math.ecnu.edu.cn/~jypan
目录 .V 3.2.2Gaus5变换.，. 66 3.2.3 Houscholder变换」 66 3.2.4 Givens变换. 69 3.2.5正交变换的舍人误差分析 71 33QR分解. 3 33.1QR分解的存在性与唯一性...·.。73 33.2基于MGS的QR分解·…·· 75 3.3.3基于Householder变换的QR分解.·.····..。.········ 76 3.3.4列主元QR分解.... 79 3.35基于Givens变换的QR分解。··· 80 336QR分解的稳定性··…… 81 3.4奇异值分解……………… 83 3.41奇异值，奇异向量和奇异值分解。.·。····.· 3.42奇异值基本性质.。………… 3.43奇异值更多性质... 86 344奇异值扰动分析…。…。……… 87 35线性最小二乘问题的求解方法·……·…· 89 3.51正规方程………… 89 3.5.2 Cholesky分解法 89 % 35.4奇异值分解法。.·……·…… % 3.6广义逆与最小二乘·... 2 3.61广义逆. 92 3.6.2广义逆基本性质.. 92 3.6.3广义逆的计算. 93 3.64广义逆与线性最小二乘…·……· 94 3.65左逆和右逆·...... 94 37最小二乘扰动分析。… 95 38推广与应用* 6 3.81最小二乘问题的推广..。96 3.82最小二乘问题的应用，..，，·...·.. http://math.ecnu.edu.cn/-jypan
仅供课堂教学使用，请勿外传 目 录 · v · 3.2.2 Gauss 变换 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 3.2.3 Householder 变换 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 3.2.4 Givens 变换 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 3.2.5 正交变换的舍入误差分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 3.3 QR 分解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 3.3.1 QR 分解的存在性与唯一性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 3.3.2 基于 MGS 的 QR 分解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 3.3.3 基于 Householder 变换的 QR 分解 . . . . . . . . . . . . . . . . . . . . . . . . 76 3.3.4 列主元 QR 分解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 3.3.5 基于 Givens 变换的 QR 分解 . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 3.3.6 QR 分解的稳定性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 3.4 奇异值分解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 3.4.1 奇异值，奇异向量和奇异值分解 . . . . . . . . . . . . . . . . . . . . . . . . 83 3.4.2 奇异值基本性质 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 3.4.3 奇异值更多性质 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 3.4.4 奇异值扰动分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 3.5 线性最小二乘问题的求解方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 3.5.1 正规方程 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 3.5.2 Cholesky 分解法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 3.5.3 QR 分解法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 3.5.4 奇异值分解法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 3.6 广义逆与最小二乘 * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 3.6.1 广义逆 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 3.6.2 广义逆基本性质 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 3.6.3 广义逆的计算 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 3.6.4 广义逆与线性最小二乘 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 3.6.5 左逆和右逆 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 3.7 最小二乘扰动分析 * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 3.8 推广与应用 * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 3.8.1 最小二乘问题的推广 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 3.8.2 最小二乘问题的应用 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 http://math.ecnu.edu.cn/~jypan
.vi. 目录 第四讲非对称特征值问题 4.1幂迭代法··.. ……………100 411算法介绍…100 412收敛性分析·....101 413位移策略…102 42反选代法.…103 421算法介绍.….…103 4.2.2 Rayleigh商选代 103 43正交选代法。……… 105 4.4QR迭代法 107 441QR选代与幂选代的关系… ,107 4.4.2QR选代与反选代的关系， 108 443QR迭代与正交选代的关系.，，··， 108 4.4.4QR选代的收敛性.··.· 108 4.4.5带位移的QR迭代法 1g。年。。。。，。。里t。g。。。。。里g1g。。。▣。 ,109 4.5带位移的隐式QR迭代法 111 45.l上Hessenberg矩阵......11l 4.5.2隐式QR迭代 ,113 4.5.3位移的选取 ,115 45.4收缩……… ,119 46特征向量的计算120 47广义特征值问题*..。··…121 4.7.1广义特征值基本理论 121 47.2广义Shur分解.......，. .121 473QZ选代法 122 4.8应用·。 4.8.1多项式求根 123 4.8.2 Goolge网页排名：PageRank 124 第五讲对称特征值向问题 125 51 Jacobi选代法 125 52 Rayleigh商迭代法 ,129 53对称QR选代法· ,130 5.4分而治之法 ·132 http://math.ecnu.edu.cn/-jypan
仅供课堂教学使用，请勿外传 · vi · 目 录 第四讲 非对称特征值问题 100 4.1 幂迭代法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 4.1.1 算法介绍 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 4.1.2 收敛性分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 4.1.3 位移策略 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 4.2 反迭代法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 4.2.1 算法介绍 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 4.2.2 Rayleigh 商迭代 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 4.3 正交迭代法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 4.4 QR 迭代法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 4.4.1 QR 迭代与幂迭代的关系 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 4.4.2 QR 迭代与反迭代的关系 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 4.4.3 QR 迭代与正交迭代的关系 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 4.4.4 QR 迭代的收敛性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 4.4.5 带位移的 QR 迭代法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 4.5 带位移的隐式 QR 迭代法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 4.5.1 上 Hessenberg 矩阵 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 4.5.2 隐式 QR 迭代 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 4.5.3 位移的选取 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 4.5.4 收缩 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 4.6 特征向量的计算 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 4.7 广义特征值问题 * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 4.7.1 广义特征值基本理论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 4.7.2 广义 Schur 分解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 4.7.3 QZ 迭代法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 4.8 应用 * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 4.8.1 多项式求根 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 4.8.2 Goolge 网页排名：PageRank . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 第五讲 对称特征值问题 125 5.1 Jacobi 迭代法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 5.2 Rayleigh 商迭代法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 5.3 对称 QR 迭代法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 5.4 分而治之法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 http://math.ecnu.edu.cn/~jypan
目录 .vii. 5.5对分法和反迭代法.· .,.138 5.6奇异值分解.·140 5.6.1二对角化..，，. 5.62Golb-Kahan SVD算法..........142 5.63dd算法..143 56.4hcbi算法145 5.7扰动分析 147 5.7.1特征值与Rayleigh商 14 5.7.2对称矩阵特征值的扰动分析 148 5.7.3对称矩阵特征向量的扰动 149 5.7.4 Rayleigh商通近......................... ,151 575相对扰动分析…………… 15 58应用， 153 5.81SVD与图像压缩..............153 第六讲线性方程组定常迭代法 154 61定常选代法····· ·155 62矩阵分裂选代法..157 62.1 Jacobi选代法，， 157 6.2.2Gaus-Seidel迭代法 158 623S0R法代法。·… 159 6.2.4SSOR迭代法.·。 6.2.5AOR迭代法·. .161 6.2.6 Richardson迭代法 ,162 6.2.7分块迭代法 。。 162 63收敛性分析..··。 164 6.3.1基本概念.. 164 6.3.2不可约对角占优矩阵 166 633对称正定矩阵..167 63.4相容次序矩阵168 6.4应用：Poisson方程求解 .171 6.4.1一维Poisson方程... .171 6.4.2二维Poisson方程.............................172 6.43收敛性分析··.··· ·175 http://math.ecnu.edu.cn/-jypan
仅供课堂教学使用，请勿外传 目 录 · vii · 5.5 对分法和反迭代法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 5.6 奇异值分解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 5.6.1 二对角化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 5.6.2 Golub-Kahan SVD 算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142 5.6.3 dqds 算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 5.6.4 Jacobi 算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 5.7 扰动分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 5.7.1 特征值与 Rayleigh 商 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 5.7.2 对称矩阵特征值的扰动分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 5.7.3 对称矩阵特征向量的扰动 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 5.7.4 Rayleigh 商逼近 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151 5.7.5 相对扰动分析 * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151 5.8 应用 * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 5.8.1 SVD 与图像压缩 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 第六讲 线性方程组定常迭代法 154 6.1 定常迭代法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 6.2 矩阵分裂迭代法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 6.2.1 Jacobi 迭代法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 6.2.2 Gauss-Seidel 迭代法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158 6.2.3 SOR 迭代法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 6.2.4 SSOR 迭代法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160 6.2.5 AOR 迭代法 * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161 6.2.6 Richardson 迭代法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162 6.2.7 分块迭代法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162 6.3 收敛性分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164 6.3.1 基本概念 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164 6.3.2 不可约对角占优矩阵 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 6.3.3 对称正定矩阵 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167 6.3.4 相容次序矩阵 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168 6.4 应用: Poisson 方程求解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 6.4.1 一维 Poisson 方程 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 6.4.2 二维 Poisson 方程 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172 6.4.3 收敛性分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175 http://math.ecnu.edu.cn/~jypan
vii。 目录 6.4.4快速求解方法 ,177 65加速方法181 6.51外推技术...181 6.52 Chebyshev多项式加速. 182 66交替方向法与HSS选代法···，，。.…，·.187 6.6.1多步选代法 …………。…187 6.6.2交替方向法 ……187 188 第七讲Krylov子空间选代法 190 7.1Kyov子空间，....，.，，... 190 7.1.Arnoldi过程与Lanczos过程 190 7.1.2Klow子空间方法一般格式 193 7.2 GMRES方法，····， 195 7.2.1算法描述 195 7.2.2具体实施细节.. 196 723 GMRES方法的中断........199 7.2.4带重启的GMRES方法 19 7.3共轭梯度法. 01 73.1算法基本过程··.···· ,201 7.3.2实用迭代格式 201 7.4收敛性分析. 206 7.4.1CG的收敛性.... 。。。。 206 7.4.2CG的超收敛性 207 7.4.3 GMRES的收敛性 208 7.5预处理方法...... 212 7.5.1预处理方法介绍 212 7.5.2预处理CG方法 213 7.5.3预处理GMRES方法... 216 754预处理子构造…………………… 218 第入讲特征值问题的选代解法 221 ,221 8.2 Rayleigh-Riz方法 .222 8.3Lanc0s方法............. 223 8.4 Arnoldi方法 225 8.5非对称Lanczos方法 ,226 http://math.ecnu.edu.cn/-jypan
仅供课堂教学使用，请勿外传 · viii · 目 录 6.4.4 快速求解方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177 6.5 加速方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 6.5.1 外推技术 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 6.5.2 Chebyshev 多项式加速 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182 6.6 交替方向法与 HSS 迭代法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187 6.6.1 多步迭代法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187 6.6.2 交替方向法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187 6.6.3 HSS 方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188 第七讲 Krylov 子空间迭代法 190 7.1 Krylov 子空间 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190 7.1.1 Arnoldi 过程与 Lanczos 过程 . . . . . . . . . . . . . . . . . . . . . . . . . . . 190 7.1.2 Krylov 子空间方法一般格式 . . . . . . . . . . . . . . . . . . . . . . . . . . . 193 7.2 GMRES 方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195 7.2.1 算法描述 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195 7.2.2 具体实施细节 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196 7.2.3 GMRES 方法的中断 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199 7.2.4 带重启的 GMRES 方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199 7.3 共轭梯度法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201 7.3.1 算法基本过程 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201 7.3.2 实用迭代格式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201 7.4 收敛性分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206 7.4.1 CG 的收敛性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206 7.4.2 CG 的超收敛性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207 7.4.3 GMRES 的收敛性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208 7.5 预处理方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212 7.5.1 预处理方法介绍 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212 7.5.2 预处理 CG 方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213 7.5.3 预处理 GMRES 方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216 7.5.4 预处理子构造 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218 第八讲 特征值问题的迭代解法 221 8.1 投影算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221 8.2 Rayleigh-Ritz 方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222 8.3 Lanczos 方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223 8.4 Arnoldi 方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225 8.5 非对称 Lanczos 方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226 http://math.ecnu.edu.cn/~jypan
目录 附录A IEEE浮点运算标准 228 A1浮点数与定点数 228 A2EEE中的浮点数的表示方法.··..····.。...228 A3EEE中的浮点数运算，.，....，.，.，.，.，.，.，.，...，232 A.4浮点运算舍人误差分析 234 A5课后习题…………………237 附录B数值计算中的误差 238 B1误差与有效数字……………… ,238 B.1.1基本算术运算的误差估计 240 B.1.2函数求值的误差估计 .240 B.2误差分析... .241 B21定量分析。········ ,241 B2.2定性分析 ,241 B3数值稳定性…… 242 B.3.1数学问题的稳定性 242 B.3.2病态问题与条件数 242 B.3.3算法的稳定性. 243 B3,4数值计算注意事项········ 244 B.4拓展阅读.， 245 B5课后习题 246 附录C高性能计算一科学计算软件介绍 247 C1科学计算发展.·.，...， 247 C.1.1数值分析经典论文 ………248 C.1.Longer list of papers 249 C2矩阵运算的复杂度.·， ·251 C3矩阵乘积的快速算法 .251 C.4数值线性代数程序库 ,253 C.4.1 BLAS.. 253 C42 LAPACK ......................................253 C.4.3ARPACK 253 C4.4其它· 254 C5交互式数学软件 .254 .254 http://math.ecnu.edu.cn/-jypan
仅供课堂教学使用，请勿外传 目 录 · ix · 附录 A IEEE 浮点运算标准 228 A.1 浮点数与定点数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228 A.2 IEEE 中的浮点数的表示方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228 A.3 IEEE 中的浮点数运算 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232 A.4 浮点运算舍入误差分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234 A.5 课后习题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237 附录 B 数值计算中的误差 238 B.1 误差与有效数字 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238 B.1.1 基本算术运算的误差估计 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240 B.1.2 函数求值的误差估计 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240 B.2 误差分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241 B.2.1 定量分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241 B.2.2 定性分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241 B.3 数值稳定性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242 B.3.1 数学问题的稳定性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242 B.3.2 病态问题与条件数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242 B.3.3 算法的稳定性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243 B.3.4 数值计算注意事项 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244 B.4 拓展阅读 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245 B.5 课后习题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246 附录 C 高性能计算 – 科学计算软件介绍 247 C.1 科学计算发展 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247 C.1.1 数值分析经典论文 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248 C.1.2 Longer list of papers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249 C.2 矩阵运算的复杂度 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251 C.3 矩阵乘积的快速算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251 C.4 数值线性代数程序库 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253 C.4.1 BLAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253 C.4.2 LAPACK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253 C.4.3 ARPACK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253 C.4.4 其它 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254 C.5 交互式数学软件 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254 C.5.1 MATLAB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254 http://math.ecnu.edu.cn/~jypan
目录 C.5.2 Mathematica 255 C53Mple…… .255 C5.4 SageMath.··· 256 参考文献 257 课堂教学使用， http://math.ecnu.edu.cn/-jypan
仅供课堂教学使用，请勿外传 · x · 目 录 C.5.2 Mathematica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255 C.5.3 Maple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255 C.5.4 SageMath . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256 参考文献 257 http://math.ecnu.edu.cn/~jypan
算法目录 2.1Gaus消去法 34 2.2LU分解.... 36 2.3LU分解佣A存储L和U) 37 2.4LU分解IKN型)···· 38 2.5 Gauss消去法 ”。。。”·。。”。。。””4。。”·。。”。·。。。。4。。·。。·4 38 2.6回代求解Lg=b和Ur=y. 39 2.7向后回代求解Ux=y例存储方式)..·.·. 41 2.9 Cholesky分解 2.10改进的平方根法，，， 44 2.11追赶法 2.12带状矩阵的LU分解。 49 2.l3求解ule-Walker方程组的Levinson-Durbin算法..··. 2.l4求解对称正定Toeplitz线性方程组的Levinson-Durbin算法 53 2.15通过迭代改进解的精度 3.1计十算Householder向量 68 70 3.3Gram-Schmidt正交化过程 73 3.4基于MGS的QR分解 3.5基于Householder变换的OR分解 78 3.6基于Givens变换的QR分解 4.1幂迭代法Power Iteration) % 4.2带位移的反迭代法Inverse teration)) ,103 4.3 Rayleigh商选代法(Rayleigh Quotient Iteration(RQ) 103 4.4正交迭代法(Orthogonal Iteration)....·.·.,.··..··.·······,,. 105 4.5QR迭代法(QR Iteration)) 107 4.6带位移的QR迭代法(QR Iteration with shift)................·... .109 4.7Hessenberg(Upper Hessenberg Reduction) 112 126 5.2经典Jacobi迭代算法 127 5.3循环acobi迭代算法（逐行扫描）.. 127 5.4 Rayleigh商送代算法(RQL,Rayleigh Quotient Iterations) 129 5.5十算对称三对角矩阵的特征值和特征向量的分而治之法（函数形式），...，，.，，134 xi
仅供课堂教学使用，请勿外传 算 法 目 录 2.1 Gauss 消去法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.2 LU 分解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 2.3 LU 分解 (用 A 存储 L 和 U) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 2.4 LU 分解 (IKJ 型) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 2.5 Gauss 消去法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 2.6 回代求解 Ly = b 和 Ux = y . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 2.7 向后回代求解 Ux = y (列存储方式) . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 2.8 部分选主元 LU 分解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 2.9 Cholesky 分解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 2.10 改进的平方根法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 2.11 追赶法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 2.12 带状矩阵的 LU 分解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 2.13 求解 Yule-Walker 方程组的 Levinson-Durbin 算法 . . . . . . . . . . . . . . . . . . . . 52 2.14 求解对称正定 Toeplitz 线性方程组的 Levinson-Durbin 算法 . . . . . . . . . . . . . . 53 2.15 通过迭代改进解的精度 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 3.1 计算 Householder 向量 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 3.2 Givens 变换 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 3.3 Gram-Schmidt 正交化过程 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 3.4 基于 MGS 的 QR 分解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 3.5 基于 Householder 变换的 QR 分解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 3.6 基于 Givens 变换的 QR 分解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 4.1 幂迭代法 (Power Iteration) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 4.2 带位移的反迭代法 (Inverse Iteration) . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 4.3 Rayleigh 商迭代法 (Rayleigh Quotient Iteration (RQI)) . . . . . . . . . . . . . . . . . . 103 4.4 正交迭代法 (Orthogonal Iteration) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 4.5 QR 迭代法 (QR Iteration) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 4.6 带位移的 QR 迭代法 (QR Iteration with shift) . . . . . . . . . . . . . . . . . . . . . . 109 4.7 上 Hessenberg 化 (Upper Hessenberg Reduction) . . . . . . . . . . . . . . . . . . . . . . 112 5.1 Jacobi 迭代算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 5.2 经典 Jacobi 迭代算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 5.3 循环 Jacobi 迭代算法 (逐行扫描) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 5.4 Rayleigh 商迭代算法 (RQI, Rayleigh Quotient Iterations) . . . . . . . . . . . . . . . . . 129 5.5 计算对称三对角矩阵的特征值和特征向量的分而治之法 (函数形式) . . . . . . . . . 134 xi
xii. 算法目录 5.6修正的Newton算法 136 5.7计算矩阵D+uu的特征值和特征向量的稳定算法··········137 5.8对分法：计算A在[a,)中的所有特征值.···. .138 59带位移的LR算法······ ,143 5.10qds算法的单步(B→B+1) 144 5.11dds算法的单步(B→B+).·· 145 5.12单边Jacobi旋转的单步 145 5.13单边Jacobis:计算A=Uv 146 6.1 Jacobi迭代法，」 158 6.2Gaus-Seidel迭代法 158 6.3求解线性方程组的SOR迭代法..」 159 6.4SSOR迭代法 160 6.5求解二维离散Poisson方程的Jacobi选代法， ,174 6.6求解二维离散Poisson方程的红黑排序G-S迭代法 174 6.7求解二维离散Poisson方程的SOR迭代法，，，，.，，·，，，，.，，，·，，，·. 175 6.8二维离散Poisson方程的快速方法 180 6.9 Chebyshev加速方法 185 7.1 Arnoldi过程(MGS 191 7.2 Lanczos过程 193 7.3 Krvlov子空间迭代算法 194 7.4 GMRES方法基本框架 195 7.5实用GMRES方法 198 7.6 GMRES():带重启的GMRES方法 199 了7共梯度法(CG)。。,。。. ,204 7.8两边预处理CG方法 214 7.9PCG:预处理CG方法，..，...， 214 7.10基于P-内积的CG方法 216 7.11右预处理GMRES方法 .217 8.】暴洪代：计算品大特征值 221 82 Rayleigh Ritz算法..······························ 222 8.3 Lanczos算法 223 8.4 Arnoldi算法 225 8.5非对称Lan2os算法 227 A1 Horner法则.··· 235 A2带舍入误差的Horner法则···· 236 http://math.ecnu.edu.cn/-jypan
仅供课堂教学使用，请勿外传 · xii · 算 法 目 录 5.6 修正的 Newton 算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 5.7 计算矩阵 D + uu ⊺ 的特征值和特征向量的稳定算法 . . . . . . . . . . . . . . . . . . 137 5.8 对分法: 计算 A 在 [a, b) 中的所有特征值 . . . . . . . . . . . . . . . . . . . . . . . . 138 5.9 带位移的 LR 算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 5.10 qds 算法的单步 (Bi → Bi+1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 5.11 dqds 算法的单步 (Bi → Bi+1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 5.12 单边 Jacobi 旋转的单步 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 5.13 单边 Jacobi: 计算 A = UΣV ⊺ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 6.1 Jacobi 迭代法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158 6.2 Gauss-Seidel 迭代法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158 6.3 求解线性方程组的 SOR 迭代法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 6.4 SSOR 迭代法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160 6.5 求解二维离散 Poisson 方程的 Jacobi 迭代法 . . . . . . . . . . . . . . . . . . . . . . . 174 6.6 求解二维离散 Poisson 方程的红黑排序 G-S 迭代法 . . . . . . . . . . . . . . . . . . . 174 6.7 求解二维离散 Poisson 方程的 SOR 迭代法 . . . . . . . . . . . . . . . . . . . . . . . . 175 6.8 二维离散 Poisson 方程的快速方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180 6.9 Chebyshev 加速方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185 7.1 Arnoldi 过程 (MGS) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191 7.2 Lanczos 过程 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193 7.3 Krylov 子空间迭代算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194 7.4 GMRES 方法基本框架 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195 7.5 实用 GMRES 方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198 7.6 GMRES(k): 带重启的 GMRES 方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . 199 7.7 共轭梯度法 (CG) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204 7.8 两边预处理 CG 方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214 7.9 PCG: 预处理 CG 方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214 7.10 基于 P-内积的 CG 方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216 7.11 右预处理 GMRES 方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217 8.1 幂迭代: 计算最大特征值 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221 8.2 Rayleigh Ritz 算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222 8.3 Lanczos 算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223 8.4 Arnoldi 算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225 8.5 非对称 Lanczos 算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227 A.1 Horner 法则 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235 A.2 带舍入误差的 Horner 法则 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236 http://math.ecnu.edu.cn/~jypan