1、Krylov子空间的定义：定义：令，由所生成的子空间称之为由与A所生成的m维Krylov子空间，并记。主要思想是为各迭代步递归地造残差向量，即第n步的残差向量通过系数矩阵A的某个多项式与第一个残差向量相乘得到。即。但要注意，迭代多项式的选取应该使所构造的残差向量在某种内积意义下相互正交，从而保证某种极小性（极小残差性），达到快速收敛的目的。Krylov子空间方法具有两个特征：1.极小残差性，以保证收敛速度快。2.每一迭代的计算量与存储量较少，以保证计算的高效性。投影方法线性方程组的投影方法方程组,A是的矩阵。给定初始,在m维空间K(右子空间）中寻找x的近似解满足残向量与m维空间L(左子空间）正
2、交，即，此条件称为Petrov-Galerkin条件。当空间K=L时，称相应的投影法为正交投影法，否则称为斜交投影法.投影方法的最优性：. (误差投影)设A为对称正定矩阵,为初始近似解,且K=L,则为采用投影方法得到的新近似解的充要条件是 其中,2. (残量投影)设A为任意方阵,为初始近似解,且,则为采用投影方法得到的新近似解的充要条件是其中矩阵特征值的投影方法对于特征值问题,其中A是nn的矩阵，斜交投影法是在m维右子空间K中寻找和复数满足,其中L为m维左子空间.当L=K时，称此投影方法为正交投影法.误差投影型方法：取L=K的正交投影法 非对称矩阵的FOM方法（完全正交法）对称矩阵的IOM方法
3、和DIOM方法 对称矩阵的Lanczos方法对称正定矩阵的CG方法残量投影型方法：取L=AK时的斜交投影法GMERS方法（广义最小残量法）重启型GMERS方法、QGMERS、DGMERSArnoldi方法标准正交基方法：Arnoldi方法是求解非对称矩阵的一种正交投影方法。Arnoldi算法就是对非对称矩阵A，产生Krylov子空间的一组标准正交基的方法。该算法构造的一组标准正交基和Hessenberg矩阵，基于Gram-Schmit正交化方法首先，选取一个Euclid范数为1的向量,对,通常可取，在已知的情况下,不妨设线性无关(否则构造完毕),则可求出与每个都正交的向量而不难看出，再记，得到
4、与都正交的向量，重复此过程，即可得到一组标准正交基。若期间某个j使得，则说明v的次数是j，且是A的不变子空间。Arnoldi算法：（1） 取向量，满足（2） 按（2）式计算，再按（1）式计算（3） 按（3）式计算，若，则停止，否则按（4）式计算（4） 若，则，转（2），否则停止 （1） （2） （3） （4）定理：如果记以为列构成的矩阵为,由定义的(m+1)m阶上Hessenberg矩阵（假设一个阶矩阵A，在时，它的，那么这个矩阵A就叫做Hessenberg矩阵）为,删除最后一行得到的矩阵为，则： 在Arnoldi算法中，可能有较大舍入误差，改写：修正的Arnoldi算法：（1） 取向量，满足
5、（2） 计算（3） 依次对，计算与（4） 计算，若，则停止，否则计算（5） 若，则，转（2），否则停止FOM（完全正交化）方法非对称矩阵的FOM方法：解方程组的投影法的矩阵表示设阶矩阵与的列分别构成K与L的一组基。记，有当非奇异时，有，从而得到迭代公式：FOM算法：（1）计算，置（2）计算（3）依次对，计算与（4）计算，若，则置，转（6）（5）计算，若，则置，转（2）（6）按下式计算不难看出，当采用上述FOM算法时，需要存储所有的，(i=1,2,m)，当m增大时，存储量以量级增大.而FOM计算量是.可见其代价十分高昂.因此我们考虑重启的FOM算法重启型FOM算法：（1） 计算（2） 生成的一组
6、标准正交基，得到（3） 按下式计算，若满足精度要求，则停止，否则置，转（1）。IOM方法非对称矩阵的IOM方法所谓不完全正交化方法(IOM),是指在正交化过程中,仅与最近k个正交,这样做虽然破坏的正交性,但是降低了计算量.当然k选得越小，对每个j对应的计算量也越小,但可能要选更大的m才能取得满足精度要求的近似解.IOM算法仅仅是把FOM算法的第三步改为，计算与。 但采用IOM后，仍然需要存储,因为在第(vi)步中仍然需要这些向量.解决这个问题可以考虑采用H的LU分解，通过自身分解的迭代更新以减少每一步的存储量DIOM算法：（1） 计算，置（2） 计算（3） 对，依次计算与（4） 计算（5） 按
7、（4）式更新的LU分解，若，则停止（6） 按（3）式计算，按（2）式计算，其中时，（7） 按（1）式计算，若符合精度要求，则停止，否则，转（2） （1） （2） （3） （4）Lanczos方法Lanczos方法是求解大规模稀疏对称矩阵端部特征问题的一种常用的正交投影方法。它在Krylov子空间上对对称矩阵采用Rayleign-Ritz方法，得到某些特征值和特征向量的近似。基本思想是给定一初始向量，逐步地构造出由该初始向量和对称阵生成的Krylov子空间的标准正交基。通过简单的三项递推公式将大规模对称阵投影为小规模对称三对角阵，然后用此三对角阵的特征对来得出原始矩阵的近似特征对。由于三对角阵好
8、的结构和小的维数，在准确运算下，每一步所需存储量和计算量是常量，不会随着子空间维数的增加而改变。Lanczos算法：（1） 计算，置（2） 计算，其中当时（3） 计算与（4） 计算，若，则置转（5），否则置，若，则，转（2）（5） 置，计算（6） 计算Lanczos双正交化方法 在双正交化过程中，取 容易看出A和在其中扮演对偶的角色，此方法特别适用于需要求解两个系数矩阵分别是A和的方程组.基于Lanczos双正交化过程的双共轭梯度法BiCG算法：（1） 计算，选取使得，置方向向量，并置m=0（2） 计算与向量，如果满足精度要求，则停止（3） 计算参数，与向量，置m=m+1,转（2）CG方法CG
9、法用来解对称且正定方程组十分有效，但若是拿来解非对称或是非正定的线性方程组则会发生中断。它是借由迭代的方式产生一序列的方向向量用来更新迭代解以及残向量，虽然产生的序列会越来越大，但是却只需要存储少数的向量。当系数矩阵A相当大而且稀疏，此时CG法几乎就是高斯消去法。CG法理论上虽然保证最多n步能解出线性方程组的解，但是若系数矩阵是病态的，此时累进误差会让CG法在n步后无法求得充分精确的近似解。CG算法：（1）计算，选取，置（2）计算参数，更新向量与残向量，若满足精度要求，则停止（3）计算，置，转（2）CG法是解正定对称线性方程组最有效的方法之一，该方法充分利用了矩阵A的稀疏性，每次迭代的主要计算
10、量是向量乘法。 GMRES方法GMRES算法要求系数矩阵A是非奇异，非对称的n维方阵。GMRES算法利用Arnoldi变换构造一正交基来表示Krylov子空间。GMRES方法把方程组的求解化为一个极小问题的求解，不去直接求,转而去解此极小问题，这是GMRES方法的独到之处。 GMRES算法的收敛性完全取决于系数矩阵A的特征值的性质。GMRES算法：（1） 计算，置（2） 计算（3） 依次对，计算与（4） 计算，若，则置，转（6）（5） 计算，若，则置，转（2）（6） 求，计算求解最小二乘问题的算法：（1） 令，（2） 计算，置（3） 置向量，计算（表示矩阵第i行从i+1列到m列的元素构成的列向
11、量）（4） 置，计算（5） 若，转（2）（6） 依次对，计算所得到的即为所求的 GMRES算法允许Krylov子空间维数增加到n，而且总是在最大迭代次数n内终止运算；另一种重启型GMRES算法严格要求子空间维数为一个定值m，在进行了m次迭代后，以得到的最后迭代结果作为初始点重新进行Arnoldi变换，当残余向量满足时，终止计算。综合考虑时间和空间复杂度，重启型的GMRES算法更适合。重启型GMRES算法：（1） 计算（2） 生成的一组标准正交基，得到（3） 求，计算，若满足精度要求，则停止，否则置，转（1） 同样可以采取不完全正交的方法，在正交化过程中,仅与最近k个正交就能得到QGMRES方法
12、。为了避免存储，可以对进行QR分解.这种算法被称为DQGMRES。QGMRES算法：（1） 计算（2） 计算（3） 对，计算与（4） 计算，若，则置，转（6）（5） 计算，若，则置，转（2）（6） 求，计算Krylov子空间方法解矩阵特征值问题Arnoldi方法求解非对称矩阵特征值由定理： 而，则有如下结论：（1） 若，则是A的不变子空间，从而的所有特征值是A的特征值子集。（2） 若，则的特征值对是，即，由上述定理可得： 以上讨论说明,可以用的特征值 (又称Ritz值)来近似A的特征值,用向量(又称Ritz向量)来近似相应的特征向量.事实上, 为A在Krylov子空间上的正交投影. 由于是上H
13、essenberg阵，它的特征值求解难度远小于原问题,例如可以采取分解法来求解.求解矩阵特征值的Arnoldi方法：（1） 给定m，取向量，满足（2） 计算（3） 依次对，计算与（4） 计算，若，则停止，否则计算（5） 若，则，转（2）（6） 计算的特征值对及A关于的Ritz向量Arnoldi算法构造标准正交基存在的问题： 1需要存储所有的基向量,当m很大时,存储量大 2理论上为了保证收敛速度,m越大越好Lanczos方法求解对称矩阵特征值 A是对称阵时,是三对角阵，仍然采用的特征值来近似A的特征值，相应的Ritz向量来近似A的特征向量. 问题转化为三对角阵特征值的求解问题，而它的求解，复杂度
14、大大减小，有很多成熟的办法，如分而治之法，QR法等，可以在并行机上达到tO(logN)的量级.求解对称矩阵特征值的Lanczos方法：（1）计算，置（2） 计算，其中当时（3） 计算与（4） 计算，若，则置转（5），否则置，若，则，转（2）（5） 计算的特征对及A的关于的Ritz向量预条件法 Krylov子空间方法的收敛性一般都和矩阵的特征值分布有关，特征值分布越集中，收敛速度越快，若特征值分布较分散，则收敛的很慢，此时可以采用预条件子来改善矩阵的特征值分布. 选取矩阵使得A的特征值比A集中，并且容易求得，于是将原问题化为问题,这是左预条件法，还可采用右预条件法和分裂预条件法在求解矩阵特征值问
15、题时，可以利用chebyshev多项式来加快收敛 所谓多项式加速,就是采用作为迭代初始向量,其中 为多项式,如果, 其中为A的特征值对应的特征向量则。 将特征值按实部递减顺序排列,其中为r个“想要”的特征值,将“不想要”的特征值点集用S表示.如果多项式,能使得S尽可能小,则相当于让求解过程产生加速.而Chebyshev多项式由于它的特殊性质,恰好能满足这种要求.不过，至今,仍无有效方法确定Chebyshev多项式的某些参数. 块方法、调和投影法 当矩阵的特征值分布较密集或有重特征值时，常规的Arnoldi方法或Lanczos方法就必须取m很大时才能收敛，此时可以采用块方法取可以使得无须很大的m就可让迭代收敛，并且此方法适合改为并行算法。 当特征值密集时，还可采用调和投影法，这也是最近研究的一个热点。当左右子空间的基满足时，称为调和投影，它除了可以通过选取位移点改善原矩阵的特征值分布外，还可以将内部特征值问题化为外部特征值问题.
