补充资料：代数特征值问题数值解法

    　　对元素为实数或复数的 n×n矩阵A，求数λ和n维非零向量 x使Ax=λx，这样的问题称为代数特征值问题,也称矩阵特征值问题，λ和 x分别称为矩阵A的特征值和特征向量。代数特征值问题的数值解法是计算数学的主要研究课题之一，它常出现于动力系统和结构系统的振动问题中。在常微分方程和偏微分方程的数值分析中确定连续问题的近似特征系，若用有限元方法或有限差分方法求解，最终也化成代数特征值问题。此外，其他数值方法的理论分析，例如确定某些迭代法的收敛性条件和初值问题差分法的稳定性条件，以及讨论计算过程对舍入误差的稳定性问题等都与特征值问题有密切联系。求解矩阵特征值问题已有不少有效而可靠的方法。
　　
　　矩阵A的特征值是它的特征多项式P_n(λ)呏det(λI-A)的根, 其中I为单位矩阵。但阶数超过4的多项式一般不能用有限次运算求出根，因而特征值问题的计算方法本质上是迭代性质的，基本上可分为向量迭代法和变换方法两类。
　　
　　向量迭代法是不破坏原矩阵A，而利用A对某些向量作运算产生迭代向量的求解方法，多用来求矩阵的部分极端特征值和相应的特征向量，特别适用于高阶稀疏矩阵。乘幂法、反幂法都属此类，隆措什方法也常作为迭代法使用。
　　
　　变换方法是利用一系列特殊的变换矩阵（初等下三角阵、豪斯霍尔德矩阵、平面旋转矩阵等）,从矩阵A出发逐次进行相似变换，使变换后的矩阵序列趋于容易求得特征值的特殊形式的矩阵（对角阵、三角阵、拟三角阵等）；多用于求解全部特征值问题，其优点是收敛速度快，计算结果可靠，但由于原矩阵A被破坏，当A是稀疏矩阵时，在计算过程中很难保持它的稀疏性，因而大多数变换方法只适于求解中小规模稠密矩阵的全部特征值问题。雅可比方法、吉文斯－豪斯霍尔德方法以及LR方法、QR方法等都属此类。
　　
　　乘幂法 　计算矩阵的按模最大的特征值及对应特征向量的一种向量迭代法。设 A为具有线性初等因子的矩阵，它的n 个线性无关的特征向量是u_i(i=1,2,...,n)，特征值排列次序满足是一个n维非零向量,于是若│λ₁│>│λ₂│, 则当α₁≠0,且k足够大时，A^kz₀除相差一个纯量因子外趋于λ₁所对应的特征向量，这就是乘幂法的基本思想。实际计算中最简单情况的乘幂法的迭代格式是：取初始向量z₀，计算
　　式中指中绝对值最大的一个分量,这时 一般情形下，由于计算格式依赖于A的特征值的分布情况,实际使用很不方便，只是在求阶数非常高的矩阵的个别特征值和相应的特征向量时偶尔使用。然而乘幂法的基本思想是重要的，由它可导出许多实用的计算方法，例如反幂法和子空间迭代法,它也是其他一些有效计算方法（例如LR方法,QR方法）的理论基础。
　　
　　子空间迭代法 　又称同时迭代法，乘幂法的直接推广，能同时求出模最大的一些特征值和相应的特征向量。它与乘幂法的差别主要在二个方面：①同时用p(p>1)个正交规范向量进行类似于乘幂法的迭代，将迭代向量看作一个p 维子空间的正交规范基，每次迭代后得到一个新的子空间；②迭代过程中，在p 维子空间上应用里茨原理进行加速。这个方法更便于使用计算机自动计算，而且加快了收敛速度，是大型稀疏矩阵特征值问题的有效解法。
　　
　　反幂法 　又称反迭代,其原理是:设矩阵A非奇异,为求 A的模最小的特征值和相应的特征向量而对A^-1使用乘幂法。A^-1的特征值次序是取z₀为初始向量，迭代格式为
　　在一定条件下反幂法的每次迭代要解一个线代数方程组。这种原始的反幂法在实际计算中很少应用，实际使用的反幂法总是带原点位移的，且位移常取为已求得的近似特征值，而用反幂法求其对应的特征向量。设慞_i是 A的某特征值λ_i的近似值，带原点位移慞_i的反幂法的迭代格式是：取初始向量z₀，计算
　　当 时, 按方向收敛于特征向量u_i，收敛商是慞_i越精确,收敛就越快，但就越接近奇异矩阵,因而在迭代过程中需要求解非常病态的方程组。然而已经证明，这个病态性质对于反幂法的按方向收敛于特征向量是无关紧要的，而且当慞_i相当精确时，一般只要一、二次反迭代就可求得相当精确的近似特征向量。反幂法是由已知近似特征值求对应近似特征向量的有效方法。
　　
　　隆措什方法 　 用相似变换将矩阵 A 约化为三对角矩阵的一种方法，其特点是不破坏原矩阵A 。目前能实际使用的是 A对称时的对称隆措什方法：取初始向量v₁，‖v₁‖=1，递推地计算　 式中 α_i和β_i由使｛v_i｝为正交规范化的条件确定，即 当精确计算时v_n+1=0，上述过程可写成矩阵形式 其中T_n是对称三对角矩阵它的特征值可由二分法求得。由于舍入误差的影响,隆措什方法所产生的隆措什向量很快失去正交性，因而这方法长期来被认为不稳定,很少用于实际计算。近年来对隆措什方法作了深入研究，进行了大量实际计算和细致的误差分析,并且观察到如下的所谓隆措什现象：将m步递推关系写为其中是m维行向量。对足够大的m,矩阵T_m的特征值包括A的所有相异特征值。注意,当出现舍入误差时，可能m>n。对高阶矩阵A,对不大的m(m<),T_m常包含A的相当精确的近似特征值。由于隆措什方法的这一特性，还由于该方法能保持A的稀疏性,所以目前它已成为求高阶对称稀疏矩阵部分特征值的最有效方法。
　　
　　雅可比方法 　对称矩阵可以通过正交相似变换化为对角阵,其对角元是原矩阵的全部特征值。雅可比方法就是通过一系列特殊的正交相似变换──雅可比旋转，使对称矩阵近似对角化从而求得特征值和特征向量的方法。记A₀=A,作正交相似序列其中R_k是(p,q)超平面的雅可比旋转矩阵，即p、q的选取应使中非对角元绝对值最大者。A_k和A_k-1仅在第p 行(列)和第行(列)不同,它们之间的关系为
　　
　　
　　
　　　
　　
　　
　　
　　选
　　可使
　　当k →时,A_K趋于对角阵,这就是经典雅可比方法。此方法在第k次变换前要搜索A_k-1的非对角元中绝对值最大者以确定雅可比旋转矩阵的旋转平面，但这很费时间。为避免这种消耗,可改用循环雅可比方法:在n(n-1)/2次的相继雅可比旋转(称为一次扫描)中,每个非对角元,不管按什么次序，恰好消去一次。其中最方便的是特殊循环雅可比方法，即每次扫描都按(1,2)，(1,3)，...，(1,n)；(2,3)，...，(2,n)；...；(n-1,n)的次序进行。实际计算中最广泛使用的是特殊循环雅可比方法的一种变形，称为阈雅可比方法：确定一个正数作阈值，在特殊循环的一次扫描中只对绝对值超过阈值的非对角元所在的平面进行旋转变换，反复扫描，当所有非对角元的绝对值都不超过阈值时减小阈值，再按新的阈值进行扫描，如此继续下去，直至阈值充分小而达到近似对角化。雅可比方法的优点是：能在求特征值的同时求得相当精确的近似正交规范特征向量系；缺点是：与其他变换方法相比，收敛速度较慢。它适用于求解低阶稠密矩阵的全部特征值问题，对近似对角（即非对角元素较小）的对称矩阵特别有效，常应用于子空间迭代法的里茨加速过程中。
　　
　　吉文斯-豪斯霍尔德方法 　一种计算对称矩阵A的全部或部分特征值及对应特征向量的方法，包括下述三个主要部分:①利用豪斯霍尔德变换(正交相似变换)将A化为对称三对角矩阵C，整个过程由n-2步组成,第r步的变换矩阵是 其中记A₀=A，当A_r-1的第r阶顺序主子矩阵已是三对角形时,第r步将A_r-1变换为使A_r的第r+1阶顺序主子矩阵是三对角的。经n-2步变换后，得到对称三对角矩阵法计算C 的特征值。当β_i≠0（i=2,3,...，n）时,由C-λI 的顺序主子式组成的多项式序列P₀(λ)呏1，P₁=α₁-λ，构成一个斯图姆序列。用α（α）表示P₀(α)，P₁(α),...,P_n(α)中相邻二数符号一致的数目，它就是 P_n（λ）在[α，)中根的个数。设C 的特征值是λ₁>λ₂>...>λ_n,而且α(l₀)≥m,α(u₀)≤r>m 。用二等分［l₀，u₀］，计算α（r₁）。若α（r₁）≥m，则取l₁=r₁,u₁=u₀；否则取l₁=l₀,u₁=r₁。因此继续进行这样的二分过程,就可求得λ_m的近似值。③应用带近似特征值位移的反幂法求C 的对应特征向量,再利用①中的变换矩阵Q₁,Q₂,...,Q_n-2 求得A的对应特征向量。吉文斯-豪斯霍尔德方法速度快,计算过程稳定,一般说来优于雅可比方法,但它也要破坏原矩阵，因而适用于求解中小型矩阵的特征值问题。
　　
　　LR方法 　原理及基本算法如下：当A的前n-1个顺序主子式不为零时，可将A分解为A=LR，其中L是单位下三角阵,R 是上三角阵。记A₁=A,进行迭代循环:作A_K的LR分解计算由此得矩阵序列{A_K}，每个A_K都与A相似：
　　
　　 件下，A_K→R(k→)，其中R 是上三角阵，其对角元是 A的全部特征值。实际计算中为加快收敛速度常引进原点位移，记第k次迭代的原点位移为s_K,带原点位移的LR算法是:所得矩阵序列{A_K}中的每个矩阵也都与A相似,s_K常取为A_K的右下角元素。LR方法主要用于求解复矩阵的特征值问题，其优点是计算量少，收敛速度快，缺点是计算稳定性差，适用范围较小。求得近似特征值后，常用带位移的反幂法求对应特征向量。
　　
　　QR方法 　求矩阵特征值的最有效方法之一，是LR方法的酉类似，基本算法如下：作A的分解A=QR，其中Q是酉矩阵,R 是上三角阵。记A₁=A,进行迭代循环矩阵序列{A_K}中每一矩阵都与A相似:Q^H表示矩阵Q的共轭转置矩阵。在一定条件下A_k趋于上三角阵，但其上三角部分的元素不一定有极限，这样的收敛称为基本收敛，这对求特征值来说已足够，因为基本收敛的"极限矩阵"的对角元是A 的全部特征值。每次迭代需作一次QR分解和一次矩阵乘法。为减少计算量,总是先将A经酉相似变换化为上黑森贝格矩阵H，再对H 应用 QR算法,上黑森贝格矩阵经QR迭代仍保持上黑森贝格形。为加速QR过程的收敛，常引进原点位移，它和带位移的LR算法完全类似, 第k步的位移s_k常取为A_k的右下角元素 ，或右下角二阶矩阵的特征值中最接近 者。带原点位移的QR算法的渐近收敛速度至少是2次,当A对称时可达3次。对实矩阵A，当A有复共轭特征值时带实原点位移的QR算法不可能收敛，为此发展了对实矩阵的双重步QR算法，其基本思想是将可能带复原点位移的QR算法中的相继二步合并成一个双重步以避免复运算。当求得近似特征值后，可用带位移的反幂法求对应的特征向量。
　　
　　病态特征值问题 　对特征值问题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次广义特征值问题:A_i（i=1,2,...,r）是n×n矩阵, 求数λ和非零向量x,使。令x⁽⁰⁾=x,r次广义特征值问题即可化为一次广义特征值问题：
　　
　　的非线性特征值问题，当用线性化方法求解时，最终也归为求解一系列一次广义特征值问题。对于一次广义特征值问题Ax＝λBx，当B非奇异时,可化为通常特征值问题(B^-1A)x=λx，当A、B对称，且B正定时,可化为对称特征值问题(U ^-TAU^-1)(Ux)＝λ(Ux)，其中U是B 的乔莱斯基分解B＝U ^TU中的上三角阵。利用化为通常特征值问题来求解一次广义特征值问题有时是很有效的，但有下列缺点：①当A和B是稀疏矩阵，特别是带形矩阵时，约化后的矩阵B^-1A或 U ^-TAU^-1一般是稠密的；②当B关于求逆的性态很差时,直接约化会带来很大误差。对一次广义特征值问题已发展了不少其他有效解法而不必预先化到通常特征值问题，一类是松弛法，包括逐次超松弛法、逐次坐标超松弛法和共轭梯度法等；另一类是变换方法,包括广义雅可比方法、广义吉文斯方法以及QZ方法等，后者是QR方法对一次广义特征值问题的直接推广。
　　
　　

参考书目
　　　曹志浩著：《矩阵特征值问题》，上海科学技术出版社，上海，1980。
　　

说明：补充资料仅用于学习参考，请勿用于其它任何用途。