线性方程组求解、最小二乘法、特征值/特征向量求解是(数值)线性代数的主要研究内容。
在力学、气象学、电磁学、金融等学科中,许多问题最终都归结为特征值、特征向量的求解。
ARPACK使用IRAM(Implicit Restarted Arnoldi Method)求解大规模系数矩阵的部分特征值与特征向量。了解或者熟悉IRAM算法,必定有助于更好地使用ARPACK中相关特征值求解函数。
本文拟就ARPACK中特征值求解的IRAM算法进行分析,希望对从事相关研究的朋友们有所帮助。
注1:限于研究水平,分析难免不当,欢迎批评指正。
零、预修
对于n阶级复矩阵,若存在n阶向量与标量,满足,则称是矩阵的特征值,是对应的特征向量。
更一般地,若对于n阶级复矩阵、,若存在n阶向量与标量,满足,则称是矩阵的广义特征值,是对应的广义特征向量。
若,满足,则称为酉矩阵。
定义Hessenberg矩阵,
Schur分解定理:设,则存在酉矩阵,使得
其中,是上三角阵。
实Schur分解:设,则存在正交矩阵,使得
其中,是实数,或者是一个具有一对复共轭特征值的2阶仿真。
为了叙述方便,本文就标准特征值问题进行叙述,而不讨论广义特征值问题。
一、大型稀疏矩阵特征值算法
1.1 Lancos算法
1.2 Arnoldi算法
Arnoldi在1951年发表的文章中提出了一种获取大型稀疏矩阵的部分特征值、特征向量的方法。在这种方法中,通过Ritz\Galerkin余量法,将矩阵约化为低阶Hessenberg矩阵,进而求解该Hessenberg矩阵的特征值与特征向量,用以近似源矩阵部分特征值、特征向量,即
上式也可以写作
其中,,,,,,。
对于, 设
其中,
,,,
,则有
若取,则有
,
另外可以看出,即是Krylov子空间的一组标准正交基。
在实际数值计算过程中,由于计算精度等问题,通常很难保证,也就是说在矩阵逐列计算过程中,存在正交性丢失的问题。
针对此问题,Sorensen在1992的论文中提出了一种称之IRAM(Implicit Restarted Arnoldi Method)的算法。Sorensen认为误差实际上是初始向量的函数,可以通过不断选取新的初始向量,迭代Arnoldi过程次来强迫,并且给出了收敛性证明。
对于得到的,需要施加次带偏移的QR分解,以剔除不想要的特征值/特征向量。这实际上就是ARPACK使用的IRAM(Implicit Restarted Arnoldi Method))算法。
参考书籍
Golub G H , Loan C F V .Matrix Computations.Johns Hopkins University Press,1996.
Ford W .Numerical Linear Algebra with Applications using MATLAB. 2014.
徐树方. 数值线性代数(第二版). 北京大学出版社, 2010.
参考文献
Arnoldi W E .The principle of minimized iterations in the solution of the matrix eigenvalue problem[J].Quarterly of Applied Mathematics, 1951, 9(1).DOI:10.1093/qjmam/4.4.466.
D,C,Sorensen.Implicit Application of Polynomial Filters in a k-Step Arnoldi Method[J].Siam Journal on Matrix Analysis & Applications, 1992.DOI:10.1137/0613025.
Burrus C S , Cox S J , Radke R J .A Matlab Implementation of the Implicitly Restarted Arnoldi Method for Solving Large-Scale Eigenvalue Problems[J]. 2000.
R.B. Lehoucq, Analysis and Implementation of an Implicitly Restarted Arnoldi Iteration", Rice University Technical Report TR95-13, Department of Computational and Applied Mathematics.文章来源:https://www.toymoban.com/news/detail-800139.html
网络资料
ARPACKhttps://github.com/opencollab/arpack-ng文章来源地址https://www.toymoban.com/news/detail-800139.html
到了这里,关于数值线性代数:Arnoldi求解特征值/特征向量的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!