[拼音]:daishu tezhengzhi wenti shuzhi jiefa [外文]:numerical method for algebraic eigenvalue problems 对元素为实数或复数的 n×n矩阵A,求数λ和n维非零向量 x使Ax=λx,这样的问题称为代数特征值问题,也称矩阵特征值问题,λ和 x分别称为矩阵A的特征值和特征向量。代数特征值问题的数值解法是计算数学的主要研究课题之一,它常出现于动力系统和结构系统的振动问题中。在常微分方程和偏微分方程的数值分析中确定连续问题的近似特征系,若用有限元方法或有限差分方法求解,最终也化成代数特征值问题。此外,其他数值方法的理论分析,例如确定某些迭代法的收敛性条件和初值问题差分法的稳定性条件,以及讨论计算过程对舍入误差的稳定性问题等都与特征值问题有密切联系。求解矩阵特征值问题已有不少有效而可靠的方法。 矩阵A的特征值是它的特征多项式Pn(λ)呏det(λI-A)的根, 其中I为单位矩阵。但阶数超过4的多项式一般不能用有限次运算求出根,因而特征值问题的计算方法本质上是迭代性质的,基本上可分为向量迭代法和变换方法两类。 向量迭代法是不破坏原矩阵A,而利用A对某些向量作运算产生迭代向量的求解方法,多用来求矩阵的部分极端特征值和相应的特征向量,特别适用于高阶稀疏矩阵。乘幂法、反幂法都属此类,隆措什方法也常作为迭代法使用。 变换方法是利用一系列特殊的变换矩阵(初等下三角阵、豪斯霍尔德矩阵、平面旋转矩阵等),从矩阵A出发逐次进行相似变换,使变换后的矩阵序列趋于容易求得特征值的特殊形式的矩阵(对角阵、三角阵、拟三角阵等);多用于求解全部特征值问题,其优点是收敛速度快,计算结果可靠,但由于原矩阵A被破坏,当A是稀疏矩阵时,在计算过程中很难保持它的稀疏性,因而大多数变换方法只适于求解中小规模稠密矩阵的全部特征值问题。雅可比方法、吉文斯-豪斯霍尔德方法以及LR方法、QR方法等都属此类。 乘幂法计算矩阵的按模最大的特征值及对应特征向量的一种向量迭代法。设 A为具有线性初等因子的矩阵,它的n 个线性无关的特征向量是ui(i=1,2,…,n),特征值排列次序满足 ![]() 式中 又称同时迭代法,乘幂法的直接推广,能同时求出模最大的一些特征值和相应的特征向量。它与乘幂法的差别主要在二个方面: (1)同时用p(p>1)个正交规范向量进行类似于乘幂法的迭代,将迭代向量看作一个p 维子空间的正交规范基,每次迭代后得到一个新的子空间; (2)迭代过程中,在p 维子空间上应用里茨原理进行加速。这个方法更便于使用计算机自动计算,而且加快了收敛速度,是大型稀疏矩阵特征值问题的有效解法。 反幂法又称反迭代,其原理是:设矩阵A非奇异,为求 A的模最小的特征值和相应的特征向量而对A-1使用乘幂法。A-1的特征值次序是 ![]() 在一定条件下 ![]() 当 用相似变换将矩阵 A 约化为三对角矩阵的一种方法,其特点是不破坏原矩阵A 。目前能实际使用的是 A对称时的对称隆措什方法:取初始向量v1,‖v1‖=1,递推地计算 ![]() 它的特征值可由二分法求得。由于舍入误差的影响,隆措什方法所产生的隆措什向量很快失去正交性,因而这方法长期来被认为不稳定,很少用于实际计算。近年来对隆措什方法作了深入研究,进行了大量实际计算和细致的误差分析,并且观察到如下的所谓隆措什现象:将m步递推关系写为 对称矩阵可以通过正交相似变换化为对角阵,其对角元是原矩阵的全部特征值。雅可比方法就是通过一系列特殊的正交相似变换──雅可比旋转,使对称矩阵近似对角化从而求得特征值和特征向量的方法。记A0=A,作正交相似序列 ![]() p、q的选取应使 ![]() ![]() ![]() ![]() ![]() 选 ![]() 可使 ![]() 当k → 一种计算对称矩阵A的全部或部分特征值及对应特征向量的方法,包括下述三个主要部分: (1)利用豪斯霍尔德变换(正交相似变换)将A化为对称三对角矩阵C,整个过程由n-2步组成,第r步的变换矩阵是 ![]() 法计算C 的特征值。当βi≠0(i=2,3,…,n)时,由C-λI 的顺序主子式组成的多项式序列P0(λ)呏1,P1=α1-λ, (3)应用带近似特征值位移的反幂法求C 的对应特征向量,再利用①中的变换矩阵Q1,Q2,…,Qn-2 求得A的对应特征向量。吉文斯-豪斯霍尔德方法速度快,计算过程稳定,一般说来优于雅可比方法,但它也要破坏原矩阵,因而适用于求解中小型矩阵的特征值问题。 LR方法原理及基本算法如下:当A的前n-1个顺序主子式不为零时,可将A分解为A=LR,其中L是单位下三角阵,R 是上三角阵。记A1=A,进行迭代循环:作AK的LR分解 ![]() 件下,AK→R(k→ 求矩阵特征值的最有效方法之一,是LR方法的酉类似,基本算法如下:作A的分解A=QR,其中Q是酉矩阵,R 是上三角阵。记A1=A,进行迭代循环 对特征值问题Ax=λx,设A的元素经小的扰动ΔA(即‖ΔA‖/‖A‖很小)变为A+ΔA,特征值λ(假定是单的)和特征向量 x相应地变为λ+Δλ和x+Δx,若|Δλ|/‖ΔA‖(或‖Δx‖/‖ΔA‖)非常大,则称特征值 λ(或特征向量x)是病态的,否则称为良态的。病态与否是特征值问题的固有性质,与用何种方法进行数值求解无关。然而,误差分析理论指出,受原始数据在计算机中表示的舍入误差和数值方法求解过程中舍入误差的影响而求得的对 A的特征值问题的近似解,等于对A+ΔA的特征值问题的精确解,这里ΔA是一族依赖于数值方法的扰动矩阵。稳定的数值方法能保证‖ΔA‖/‖A‖是小的,但不能使病态问题变成良态的。求解病态特征值问题是近年发展起来的矩阵不变子空间计算的重要内容。 广义特征值问题数值解法最一般的矩阵特征值问题是非线性的。 设T(λ)是 n×n 矩阵,其元素是λ的解析函数,确定数λ和非零向量x,使 T(λ)x=0,这称为非线性特征值问题, λ是特征值,x是相应的特征向量。一种重要的特殊情况是一次广义特征值问题:A和B是n×n矩阵,求数λ和非零向量x,使 Ax=λBx,B=I时就是通常特征值问题;较一般的是 r次广义特征值问题:Ai(i=1,2,…,r)是n×n矩阵, 求数λ和非零向量x,使 ![]() 的非线性特征值问题,当用线性化方法求解时,最终也归为求解一系列一次广义特征值问题。对于一次广义特征值问题Ax=λBx,当B非奇异时,可化为通常特征值问题(B-1A)x=λx,当A、B对称,且B正定时,可化为对称特征值问题(U -TAU-1)(Ux)=λ(Ux),其中U是B 的乔莱斯基分解B=U TU中的上三角阵。利用化为通常特征值问题来求解一次广义特征值问题有时是很有效的,但有下列缺点: (1)当A和B是稀疏矩阵,特别是带形矩阵时,约化后的矩阵B-1A或 U -TAU-1一般是稠密的; (2)当B关于求逆的性态很差时,直接约化会带来很大误差。对一次广义特征值问题已发展了不少其他有效解法而不必预先化到通常特征值问题,一类是松弛法,包括逐次超松弛法、逐次坐标超松弛法和共轭梯度法等;另一类是变换方法,包括广义雅可比方法、广义吉文斯方法以及QZ方法等,后者是QR方法对一次广义特征值问题的直接推广。
|