下载文档原格式
CG算法的预处理技术：、为什么要对A进行预处理：其收敛速度依赖于对称正定阵A的特征值分布特征值如何影响收敛性：特征值分布在较小的范围内，从而加速CG的收敛性特征值和特征向量的定义是什么？（见笔记本以及收藏的网页）求解特征值和特征向量的方法：Davidson方法：Davidson 方法是用矩阵( D - θI)- 1( A - θI) 产生子空间，这里D 是A 的对角元所组成的对角矩阵。
θ是由Rayleigh-Ritz 过程所得到的A的近似特征值。
什么是子空间法：Krylov子空间叠代法是用来求解形如Ax=b 的方程，A是一个n*n 的矩阵，当n充分大时，直接计算变得非常困难，而Krylov方法则巧妙地将其变为Kxi+1=Kxi+b-Axi 的迭代形式来求解。
这里的K(来源于作者俄国人Nikolai Krylov姓氏的首字母)是一个构造出来的接近于A的矩阵，而迭代形式的算法的妙处在于，它将复杂问题化简为阶段性的易于计算的子步骤。
如何取正定矩阵Mk为：Span是什么？:设x_(1,)...,x_m∈V ,称它们的线性组合∑_(i=1)^m?〖k_i x_i \|k_i∈K,i=1,2...m〗为向量x_(1,)...,x_m的生成子空间，也称为由x_(1,)...,x_m张成的子空间。
记为L（x_(1,)...,x_m），也可以记为Span（x_(1,)...,x_m）什么是Jacobi迭代法：什么是G_S迭代法：请见PPT《迭代法求解线性方程组》什么是SOR迭代法：什么是收敛速度：什么是可约矩阵与不可约矩阵？：不可约矩阵（irreducible matrix）和可约矩阵（reducible matrix）两个相对的概念。
定义1：对于n 阶方阵A 而言，如果存在一个排列阵P 使得P'AP 为一个分块上三角阵，我们就称矩阵A 是可约的；否则称矩阵A 是不可约的。
定义2：对于n 阶方阵A=(aij) 而言，如果指标集{1，2，...，n} 能够被划分成两个不相交的非空指标集J 和K，使得对任意的j∈J 和任意的k∈K 都有ajk=0, 则称矩阵 A 是可约的；否则称矩阵A 是不可约的。
Krylov 子空间、优化问题与共轭梯度法自动化 富晓鹏工程实践中经常需要求解大型线性系统KU=F 。
在很多情况下矩阵K 是非常稀疏的，比如来自偏微分方程的离散化等，此时矩阵中每行仅有较少的非零元素。
面临这样的问题，我们首先面对的问题是，应该采用直接消元法还是迭代方法。
对前者来说，为充分利用系数特性，节点重编号是重要的；而对后者来说，适当的预处理是关键。
本文将重点放在后一类方法中的一种进行介绍与分析，即共轭梯度法。
共轭梯度法适用于矩阵K 为对称阵的情况，算法本身简洁高效，且与一些其他的数学理论、概念相紧密联系，本文分析了共轭梯度法与Krylov 子空间，以及优化问题之间隐含的联系，并简要给出算法框架。
1. 线性方程组迭代解法与Krylov 子空间我们考虑迭代法求解线性方程组Ax=b 。
假定未采用预处理矩阵P ，或P 矩阵已经隐含在A 与b 中。
迭代法求解格式如下：1()k k P x P A x b +⋅=-⋅+ (1)为说明问题，我们考虑简单的迭代格式P=I ，并且x 1=b 。
则迭代的最初几步为：2()2x I A b b b Ab =-+=- (2)232()33x I A x b b Ab A b =-+=-+ (3) …由上面几个式子可得，以上迭代格式第j 步的解x j 是b ，Ab ，…，A j -1b 的线性组合。
当A 矩阵稀疏时，这些向量可以采用矩阵向量乘法的稀疏技巧很快得到。
以上发现自然与Krylov 子空间的概念相联系起来。
Krylov 矩阵： K j = [b Ab A 2b … A j -1b]Krylov 子空间：K j = b ，Ab ，…，A j -1b 的所有线性组合Krylov 命名了向量b ，Ab ，…，A j -1b 的全部线性组合构成的子空间，并认为在这一子空间中，有比上例中特定元素更与线性方程组的解相接近的元素。
共轭梯度法就是在这一子空间中，每一步迭代都依照某种标准寻求最优元素的线性方程组解法。
Krylov 子空间的定义：定义：令N R υ∈，由1m A υυυ-，，，A 所生成的子空间称之为由υ与A 所生成的m 维Krylov 子空间，并记(),m K A v 。
主要思想是为各迭代步递归地造残差向量，即第n 步的残差向量()n r 通过系数矩阵A 的某个多项式与第一个残差向量()0r 相乘得到。
即()()()0n r p A r =。
但要注意，迭代多项式的选取应该使所构造的残差向量在某种内积意义下相互正交，从而保证某种极小性（极小残差性），达到快速收敛的目的。
Krylov 子空间方法具有两个特征：1.极小残差性，以保证收敛速度快。
2.每一迭代的计算量与存储量较少，以保证计算的高效性。
投影方法线性方程组的投影方法方程组Ax b =,A 是n n ⨯的矩阵。
给定初始()0x ,在m 维空间K(右子空间）中寻找x 的近似解()1x 满足残向量()1r b Ax =-与m 维空间L(左子空间）正交，即()1b Ax L -⊥，此条件称为Petrov-Galerkin 条件。
当空间K=L 时，称相应的投影法为正交投影法，否则称为斜交投影法.投影方法的最优性：１. (误差投影)设A 为对称正定矩阵,()0x 为初始近似解,且K=L,则()1x 为采用投影方法得到的新近似解的充要条件是()()()()01min z x Kx z ϕϕ∈+=其中,()()()12,z A x z x z ϕ=--2.(残量投影)设A 为任意方阵,()0x 为初始近似解,且L AK =,则()1x 为采用投影方法得到的新近似解的充要条件是()()()()01min z x Kx z ψψ∈+=其中()()122,z b Az b Az b Az ψ=-=--矩阵特征值的投影方法对于特征值问题Ax x λ=,其中A 是n ×n 的矩阵，斜交投影法是在m 维右子空间K 中寻找i x 和复数i λ满足i i i Ax x L λ-⊥,其中L 为m 维左子空间.当L=K 时，称此投影方法为正交投影法. 误差投影型方法： 取L=K 的正交投影法非对称矩阵的FOM 方法（完全正交法） 对称矩阵的IOM 方法和DIOM 方法 对称矩阵的Lanczos 方法 对称正定矩阵的CG 方法 残量投影型方法： 取L=AK 时的斜交投影法GMERS 方法（广义最小残量法） 重启型GMERS 方法、QGMERS 、DGMERSArnoldi 方法标准正交基方法：Arnoldi 方法是求解非对称矩阵的一种正交投影方法。
Krylov 子空间的定义:定义:令N R υ∈,由1m A υυυ-L ，，，A 所生成的子空间称之为由υ与A 所生成的m 维Krylov 子空间,并记(),m K A v 。
主要思想就是为各迭代步递归地造残差向量,即第n 步的残差向量()n r 通过系数矩阵A 的某个多项式与第一个残差向量()0r 相乘得到。
即()()()0n r p A r =。
但要注意,迭代多项式的选取应该使所构造的残差向量在某种内积意义下相互正交,从而保证某种极小性(极小残差性),达到快速收敛的目的。
Krylov 子空间方法具有两个特征:1、极小残差性,以保证收敛速度快。
2、每一迭代的计算量与存储量较少,以保证计算的高效性。
投影方法线性方程组的投影方法方程组Ax b =,A 就是n n ⨯的矩阵。
给定初始()0x ,在m 维空间K(右子空间)中寻找x 的近似解()1x 满足残向量()1r b Ax =-与m 维空间L(左子空间)正交,即()1b Ax L -⊥,此条件称为Petrov-Galerkin 条件。
当空间K=L 时,称相应的投影法为正交投影法,否则称为斜交投影法、投影方法的最优性:１、 (误差投影)设A 为对称正定矩阵,()0x 为初始近似解,且K=L,则()1x 为采用投影方法得到的新近似解的充要条件就是()()()()01min z x Kx z ϕϕ∈+=其中,()()()12,z A x z x z ϕ=--2.(残量投影)设A 为任意方阵,()0x 为初始近似解,且L AK =,则()1x 为采用投影方法得到的新近似解的充要条件就是()()()()01min z x Kx z ψψ∈+=其中()()122,z b Az b Az b Az ψ=-=--矩阵特征值的投影方法对于特征值问题Ax x λ=,其中A 就是n ×n 的矩阵,斜交投影法就是在m 维右子空间K 中寻找i x 与复数i λ满足i i i Ax x L λ-⊥,其中L 为m 维左子空间、当L=K 时,称此投影方法为正交投影法、 误差投影型方法: 取L=K 的正交投影法非对称矩阵的FOM 方法(完全正交法) 对称矩阵的IOM 方法与DIOM 方法 对称矩阵的Lanczos 方法 对称正定矩阵的CG 方法 残量投影型方法: 取L=AK 时的斜交投影法 GMERS 方法(广义最小残量法)重启型GMERS 方法、QGMERS 、DGMERSArnoldi 方法标准正交基方法:Arnoldi 方法就是求解非对称矩阵的一种正交投影方法。
