迭代方法和预处理技术 上PDF电子书下载

第一部分 基础知识 1

第1章 基础知识 3

1.1 迭代法的基本概念 3

1.1.1 迭代法的定义与分类 3

1.1.2 收敛性与收敛速度 4

1.1.3 相容性与敏感性分析 7

1.2 矩阵 8

1.2.1 基本矩阵类型 8

1.2.2 具有特殊性质的矩阵类型 12

1.2.3 矩阵分解 15

1.3 大型稀疏矩阵的存储与运算 17

1.3.1 稀疏矩阵的存储格式 17

1.3.2 基本稀疏矩阵运算 21

1.4 矩阵分裂 26

1.4.1 正规分裂 28

1.4.2 非负、弱非负、弱和更弱分裂 28

1.4.3 H， H相容和M分裂 29

1.5 投影方法 30

1.5.1 子空间、值域和核 30

1.5.2 投影算子 31

1.5.3 投影方法 35

1.6 正交基的构造 44

1.6.1 Gram-Schmidt和Householder过程 44

1.6.2 Arnoldi过程 48

1.6.3 Lanczos过程 50

1.6.4 Lanczos双正交化过程 51

1.7 并行算法基本概念 54

1.7.1 并行算法的概念和分类 54

1.7.2 并行算法的复杂性 55

1.7.3 加速比与效率 55

1.7.4 可扩展性分析 56

第二部分 迭代方法 59

第2章 分裂迭代法 61

2.1 经典迭代法 61

2.1.1 Richardson迭代法 61

2.1.2 Jacobi迭代法 64

2.1.3 Gauss-Seidel迭代法 66

2.2 松弛型迭代法 68

2.2.1 SOR迭代法 68

2.2.2 AOR迭代法 76

2.3 HSS方法 82

2.3.1 方法介绍 82

2.3.2 收敛性理论 84

2.3.3 PHSS迭代法 90

2.4 基于缩减技术的迭代法 96

2.4.1 缩减方法 96

2.4.2 实现与讨论 99

2.5 红黑排序 105

第3章 并行多分裂方法 110

3.1 一般并行多分裂方法 110

3.1.1 基本概念 110

3.1.2 收敛性定理与收敛速度估计 112

3.2 松弛型多分裂迭代法 114

3.2.1 系统松弛法 115

3.2.2 局部松弛法 115

3.3 二级多分裂迭代法 116

3.3.1 方法 117

3.3.2 收敛性定理 118

3.3.3 数值试验 120

3.4 松弛型二级多分裂迭代法 122

3.4.1 方法 123

3.4.2 收敛性定理 125

3.4.3 数值试验 129

3.5 块二级多分裂拟消去迭代法 132

3.5.1 方法 132

3.5.2 收敛性定理 135

3.5.3 数值试验 137

3.6 异步多分裂迭代法 138

3.6.1 多分裂迭代法的混乱模式 138

3.6.2 异步块二级多分裂迭代法 140

3.6.3 异步松弛型非定常二级多分裂方法 143

3.7 网格计算环境中线性多分裂的负载平衡 151

3.7.1 GREMLINS库中使用的并行线性多分裂方法 152

3.7.2 负载平衡 154

第4章 Krylov子空间迭代法 159

4.1 Krylov子空间与预处理迭代 159

4.1.1 Krylov子空间 159

4.1.2 预处理迭代 161

4.2 正交投影方法 162

4.2.1 共轭梯度（CG）方法及其收敛性 163

4.2.2 预处理共轭梯度方法 171

4.2.3 CGNR和CGNE方法 174

4.2.4 COCG和GCG方法 177

4.2.5 完全正交化（FOM）方法 182

4.3 正交化（极小残差）方法 187

4.3.1 GMRES方法及其实现 188

4.3.2 GMRES方法的收敛性 198

4.3.3 GMRES方法的变形 203

4.3.4 预处理GMRES方法 209

4.3.5 CR， GCR， ORTHOMIN和ORTHODIR方法 217

4.4 双正交化方法 220

4.4.1 BiCG， QMR及CGS方法 221

4.4.2 BiCGSTAB方法 228

4.4.3 BiCRSTAB方法 233

4.4.4 TFQMR方法 242

4.5 混合型Krylov子空间方法 247

4.5.1 QMRCGSTAB方法 248

4.5.2 BiCGSTAB（l）方法 254

4.5.3 GPBiCG方法 265

4.5.4 IDR（s）：一簇诱导降维方法 269

4.6 方法综述与选择指导 278

第5章 并行Krylov子空间迭代法 283

5.1 并行性能模型 285

5.1.1 性能模型 285

5.1.2 通讯开销降低的影响 290

5.1.3 模型的计时比较 295

5.2 并行共轭梯度方法 297

5.2.1 降低全局通讯次数 297

5.2.2 CG与MCG的并行性能 301

5.2.3 重叠通讯和计算 304

5.2.4 CG与parCG的并行性能 306

5.3 并行多搜索方向共轭梯度方法 308

5.3.1 MSD-CG方法 309

5.3.2 性质和引理 313

5.3.3 收敛性与相容性 316

5.3.4 数值试验 323

5.4 多预处理CG方法 330

5.4.1 MPCG方法 331

5.4.2 理论分析 333

5.4.3 数值试验 336

5.5 并行GMRES方法 340

5.5.1 GMRES（m）的并行性能 340

5.5.2 通讯冗余降低：parGMRES（m） 341

5.5.3 GMRES（m）和parGMRES（m）的性能 344

5.6 并行BiCG方法 347

5.6.1 Lanczos过程 347

5.6.2 改进的BiCG方法 350

5.6.3 并行实现 352

5.6.4 数值试验 354

5.7 并行BiCR方法 355

5.7.1 IBiCR方法算法设计 356

5.7.2 并行性能分析 357

5.7.3 可扩展性等效率分析 359

5.7.4 数值试验 362

5.8 并行BiCGSTAB方法 365

5.8.1 改进的BiCGSTAB方法 365

5.8.2 重叠计算和组通讯 368

5.9 并行BiCRSTAB方法 374

5.9.1 IBiCRSTAB的算法设计 374

5.9.2 性能和等效率分析 376

5.9.3 数值试验 378

5.10 并行QMR方法 382

5.10.1 改进的QMR方法 382

5.10.2 大同步并行结构 385

5.10.3 理论复杂性分析 388

5.10.4 数值试验 390

5.11 并行IDR（s）方法 393

5.11.1 具有极小同步化点的一种有效IDR（s）变形 394

5.11.2 求最优参数s 402

5.11.3 Q的稀疏列向量 404

第6章 非线性代数方程组迭代方法 406

6.1 问题来源与求解方法 406

6.2 迭代方法的收敛速度和收敛性 407

6.2.1 迭代方法的收敛因子 408

6.2.2 迭代方法的收敛阶 408

6.2.3 迭代法的收敛性 411

6.3 Newton法与拟Newton法 412

6.3.1 Newton法 412

6.3.2 Newton法的收敛性 414

6.3.3 非线性迭代收敛准则 416

6.3.4 拟Newton方法 416

6.3.5 逆拟Newton迭代 418

6.4 非精确Newton法 421

6.4.1 非精确Newton法 422

6.4.2 强制项及其选取 424

6.4.3 Newton-Krylov子空间方法 428

6.4.4 JFNK方法 430

6.4.5 Newton-Krylov方法中的预处理 433

6.4.6 函数评估和Jacobi矩阵计算中的误差分析 435

6.5 非线性迭代的全局化方法 439

6.5.1 全局收敛的非精确Newton法 439

6.5.2 NGECB方法 442

6.5.3 NGQCGB方法 444

6.5.4 NGLM方法 458

第7章 解法器软件包介绍 485

7.1 BLAS：基本线性代数子程序 485

7.2 ScaLAPACK：可扩展线性代数库 486

7.3 MUMPS：多前沿大规模并行稀疏直接解法器 489

7.4 SuperLU：超级LU分解 490

7.5 PSBLAS：并行稀疏基本线性代数 491

7.6 PIM：线性方程组并行迭代方法库 492

7.7 PETSc：可移植可扩展科学计算工具箱 493

7.8 KINSOL：非线性代数解法器 495

参考文献 497

索引 518

《信息与计算科学丛书》已出版书目 524