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