文档介绍:krylov子空间算法
Krylov子空间的定义:
定义:令,由所生成的子空间称之为由与A所生成的m维Krylov子空间,并记。
主要思想是为各迭代步递归地造残差向量,即第n步的残差向量通过系数矩阵A的某个多项式与第一个残差向过简单的三项递推公式将大规模对称阵投影为小规模对称三对角阵,然后用此三对角阵的特征对来得出原始矩阵的近似特征对。由于三对角阵好的结构和小的维数,在准确运算下,每一步所需存储量和计算量是常量,不会随着子空间维数的增加而改变。
Lanczos算法:
计算,,,置
计算,其中当时
计算与
计算,若,则置转(5),否则置,若,则,转(2)
置,计算
计算
Lanczos双正交化方法
在双正交化过程中,取
容易看出A和在其中扮演对偶的角色,此方法特别适用于需要求解两个系数矩阵分别是A和的方程组.
基于Lanczos双正交化过程的双共轭梯度法BiCG算法:
计算,选取使得,置方向向量,,并置m=0
计算与向量,,,如果满足精度要求,则停止
计算参数,与向量,,置m=m+1,转(2)
CG方法
CG法用来解对称且正定方程组十分有效,但若是拿来解非对称或是非正定的线性方程组则会发生中断。它是借由迭代的方式产生一序列的方向向量用来更新迭代解以及残向量,虽然产生的序列会越来越大,但是却只需要存储少数的向量。当系数矩阵A相当大而且稀疏,此时CG法几乎就是高斯消去法。CG法理论上虽然保证最多n步能解出线性方程组的解,但是若系数矩阵是病态的,此时累进误差会让CG法在n步后无法求得充分精确的近似解。
CG算法:
(1)计算,选取,置
(2)计算参数,更新向量与残向量,若满足精度要求,则停止
(3)计算,置,转(2)
CG法是解正定对称线性方程组最有效的方法之一,该方法充分利用了矩阵A的稀疏性,每次迭代的主要计算量是向量乘法。
GMRES方法
GMRES算法要求系数矩阵A是非奇异,非对称的n维方阵。GMRES
算法利用Arnoldi变换构造一正交基来表示Krylov子空间。
GMRES方法把方程组的求解化为一个极小问题的求解,不去直接求,转而去解此极小问题,这是GMRES方法的独到之处。
GMRES算法的收敛性完全取决于系数矩阵A的特征值的性质。
GMRES算法:
计算,,,置
计算
依次对,计算与
计算,若,则置,转(6)
计算,若,则置,转(2)
求,计算
求解最小二乘问题的算法:
令,
计算,置
置向量,计算(表示矩阵第i行从i+1列到m列的元素构成的列向量)
置,计算
若,转(2)
依次对,计算所得到的即为所求的
GMRES算法允许Krylov子空间维数增加到n,而且总是在最大迭代次数n内终止运算;另一种重启型GMRES算法严格要求子空间维数为一个定值m,在进行了m次迭代后,以得到的最后迭代结果作为初始点重新进行Arnoldi变换,当残余向量满足时,终止计算。综合考虑时间和空间复杂度,重启型的GMRES算法更适合。
重启型GMRES算法:
计算
生成的一组标准正交基,得到
求,计算,若满足精度要求,则停止,否则置,转(1)
同样可以采取不完全正交的方法,在正交化过程中,仅与最近k个正交就能得到QGMRES方法。为了避免存储,。
QGMRES算法:
计算
计算
对,计算与
计算,若,则置,转(6)
计算,若,则置,转(2)
求,计算
Krylov子空间方法解矩阵特征值问题
Arnoldi方法求解非对称矩阵特征值
由定理:
而,则有如下结论:
若,则是A的不变子空间,从而的所有特征值是A的特征值子集。
若,则的特征值对是,即,由上述定理可得:
以上讨论说明,可以用的特征值 (又称Ritz值)来近似A的特征值,用向量(又称Ritz向量), 为A在Krylov子空间上的正交投影.
由于是上Hessenberg阵,它的特征值求解难度远小于原问题,例如可以采取分解法来求解.
求解矩阵特征值的Arnoldi方法:
给定m,取向量,满足
计算
依次对,计算与
计算,若,则停止,否则计算
若,则,转(2)
计算的特征值对及A关于的Ritz向量
Arnoldi算法构造标准正交基存在的问题:
1需要存储所有的基向量,当m很大时,存储量大
2理论上为了保证收敛速度,m越大越好
Lanczos方法求解对称矩阵特征值
A是对称阵时,是三对角阵,仍然采用的特征值来近似A的特征值,相应的Ri