-特征值问题的计算方法1课件

第八章第八章 特征值问题计算特征值问题计算 一、一、特征值特征值和和特征向量特征向量的的基本概念与性质基本概念与性质1 基本概念与性质基本概念与性质设设 ，若存在向量，若存在向量 和复数和复数 满足满足，则称，则称 是矩阵是矩阵 的的特征值特征值，是特征值是特征值相应的相应的特征向量特征向量。特征特征多项式多项式 的根的集合：的根的集合：谱集谱集矩阵矩阵A的特征根模的最大值称为矩阵的特征根模的最大值称为矩阵A的谱半径：的谱半径：于是得到两个特征根分别为：于是得到两个特征根分别为：例例8.1 求矩阵求矩阵A的特征根与特征向量的特征根与特征向量特征特征多项式为：多项式为：对应的特征向量对应的特征向量分别为：分别为：于是得到两个特征根分别为：于是得到两个特征根分别为：例例8.2 求矩阵求矩阵A的特征根与特征向量的特征根与特征向量特征特征多项式为：多项式为：对应的特征向量对应的特征向量分别为：分别为：其中其中称称 为为 的的代数重数代数重数（简称（简称重数重数）；）；为为 的的几何重数几何重数。设设 ，对于矩阵对于矩阵 的的特征值特征值 ，如果，如果，则称该特征值，则称该特征值 为为 的一个的一个半单半单特征值。特征值。若若 的所有特征值都是的所有特征值都是半单半单的，则称的，则称 是是非亏损非亏损的。的。是是非亏损非亏损的等价条件是的等价条件是 有有n个个线性无关线性无关的特征向量的特征向量一般的，对矩阵一般的，对矩阵A，其特征多项式可表示为其特征多项式可表示为设设 ，若存在矩阵若存在矩阵 ，使得，使得则称则称 和和 是是相似相似的。的。相似相似矩阵有相同的特征值矩阵有相同的特征值设设寻求已知矩阵寻求已知矩阵 的的相似相似矩阵矩阵 ，要求：，要求：矩阵矩阵 的的特征值特征值和和特征向量特征向量容易计容易计算算本章本章QR算法的计算算法的计算思想：思想：关于矩阵关于矩阵相似，相似，有后面的结论有后面的结论设设 ，有，有 r个个互不相同互不相同的特征值的特征值 ，其其重数重数分别为分别为 ，则一定存在，则一定存在非奇异非奇异矩阵矩阵使得使得（Jordan分解）分解）其中其中且除了且除了 的的排列排列次序次序外，外，是是唯一唯一的。的。称作称作 的的Jordan标准型标准型设设 ，则存在，则存在酉酉矩阵矩阵 ，使得：，使得：（Schur分解）分解）其中其中 是是上三角上三角矩阵，且适当选择矩阵，且适当选择 ，可使，可使 的元素的元素按任意指定的顺序排列。按任意指定的顺序排列。设设 ，令，令（圆盘圆盘定理）定理）/*Disc Theorem*/则则设设 为为对称对称矩阵，则存在矩阵，则存在正交正交矩阵矩阵（谱谱分解定理）分解定理）/*Spectral Decomposition*/其中其中 是是 的的n个特征值。个特征值。使得使得设设 为为对称对称矩阵，且矩阵，且 的特征值为的特征值为（极大极小极大极小定理）定理）其中其中 表示表示 中所有中所有k维子空间的全体。维子空间的全体。则有则有设设 为为对称对称矩阵，其特征值分别为矩阵，其特征值分别为（Weyl定理）定理）则有则有说明：说明：对称对称矩阵的特征值总是矩阵的特征值总是良态良态的。的。注意注意：实际问题中矩阵一般都是由：实际问题中矩阵一般都是由计算计算或或实验实验得到，得到，本身必然存在本身必然存在误差误差，不妨假设，不妨假设 例例8.3求矩阵求矩阵A的特征根与特征向量的特征根与特征向量其特征其特征多项式为：多项式为：于是得到两个特征根分别为：于是得到两个特征根分别为：若取初始向量若取初始向量为：为：先做先做xk+1=A*xk迭代，并计算迭代，并计算|xk+1|/|xk|可发现可发现对应的特征向量对应的特征向量分别为：分别为：|xk|表示的分量模长的最大值，即取无穷范数表示的分量模长的最大值，即取无穷范数1.500000000000001.666666666666671.800000000000001.888888888888891.941176470588241.969696969696971.984615384615381.992248062015501.996108949416341.998050682261211.99901.99951.99981.99991.9999|xk+1|/|xk|xk0.5,1.51.5,2.53.5,4.57.5,8.515.5,16.531.5,32.563.5,64.5127.5,128.5255.5,256.5511.5,512.51023.5,1024.52047.5,2048.54095.5,4096.58191.5,8192.51638.4,1638.5结果表明结果表明|xk+1|/|xk|收敛到最大特收敛到最大特征根，征根，xk 收敛到对收敛到对应的特征向量。应的特征向量。k123456789101112131415但但xk 的绝对值越来越大，的绝对值越来越大，xk/|xk|即为对应特征即为对应特征向量向量1;1考虑对每次迭代结果归一化，考虑对每次迭代结果归一化，若做如下迭代：若做如下迭代：xk+1=A*xk/|A*xk|则有则有xk 收敛到对应的特征向量，收敛到对应的特征向量，|A*xk|收敛到最大特征根。收敛到最大特征根。1.500000000000001.666666666666671.800000000000001.888888888888891.941176470588241.969696969696971.984615384615381.992248062015501.996108949416341.998050682261211.99901.99951.99981.99991.9999|A*xk|xk0.3333,1.00000.6000,1.00000.7778,1.00000.8824,1.00000.9394,1.00000.9692,1.00000.9845,1.00000.9922,1.00000.9961,1.00000.9980,1.00000.9990,1.00000.9995,1.00000.9998,1.00000.9999,1.00000.9999,1.0000结果表明结果表明|A*xk|收敛到收敛到A的最大特的最大特征根，征根，xk 收敛到对收敛到对应的特征向量。应的特征向量。k123456789101112131415由此得到幂法的思想：由此得到幂法的思想：任取初始向量任取初始向量x0做以下迭代：做以下迭代：xk+1=A*xk/|A*xk|若干步后，用若干步后，用|A*xk|作为最大特作为最大特征根的近似，用征根的近似，用xk 作为对应的特作为对应的特征向量的近似征向量的近似。2 幂幂 法法/*Power Method*/幂法幂法是计算一个矩阵的是计算一个矩阵的模最大模最大的特征值和对应的特征的特征值和对应的特征 向量的一种向量的一种迭代迭代方法（又称为方法（又称为乘乘幂法幂法）。）。基本基本思想思想假设假设 是可是可对角化对角化的，即的，即 存在如下分解：存在如下分解：其中其中不妨假设不妨假设对于对于说明：当说明：当k充分大时充分大时,的一个的一个近似特征向量近似特征向量为为特征向量可以相差一个特征向量可以相差一个倍数倍数因为向量因为向量 中含有中含有未知量未知量 ，实际不能计算，实际不能计算但我们关心的仅是但我们关心的仅是 的的方向方向，故作如下处理：，故作如下处理：令令其中其中 为为 的的模最大分量模最大分量若用下式迭代，若用下式迭代，收敛性依然成立收敛性依然成立 幂法迭代幂法迭代算法算法：For k=1,2,3,if输出输出 和和设设 和和 均均收敛收敛，由，由算法算法知知幂法幂法可以计算矩阵的可以计算矩阵的模最大模最大的特征值和对应的特征向量的特征值和对应的特征向量因因解：解：Step1例例4 4：利用利用幂法幂法求下列矩阵求下列矩阵 的的模模最大的特征值及相应的最大的特征值及相应的特征向量特征向量.(取初始向量为取初始向量为 )Step2Step3Step4特征值及相应的特征值及相应的特征向量特征向量精确值精确值为为:幂法幂法的收敛性的收敛性：设设 有有 p个个互不相同互不相同的特征值满足：的特征值满足：且且模最大模最大特征值特征值 是是半单半单的，如果初始向量的，如果初始向量 在在的特征子空间上的的特征子空间上的投影投影不为零，则由不为零，则由幂法幂法算法产生的算法产生的向量向量序列序列 收敛到收敛到 的一个特征向量的一个特征向量 ，且，且数值数值序列序列 收敛到收敛到 。特征特征子空间：子空间：证明：证明：设设 有如下有如下Jordan分解：分解：是属于是属于 的的Jordan块构成的块上三角矩阵块构成的块上三角矩阵是是半单半单的特征值的特征值令令将将 和和 如下分块：如下分块：记记 是属于是属于 的一个特征向量的一个特征向量几点说明几点说明：定理定理8.2.1条件不满足时，条件不满足时，幂法幂法产生的产生的向量向量序列序列 可能有可能有若干若干个收敛于不同向量的个收敛于不同向量的子序列子序列；幂法幂法的收敛的收敛速度速度取决于取决于 的大小；的大小；加速加速方法：适当选取方法：适当选取 ，对，对 应用应用幂法幂法称之为称之为原点平移法原点平移法原点平移法原点平移法不改变不改变矩阵矩阵 的特征向量的特征向量 幂法幂法可以计算第二个可以计算第二个模最大模最大特征值特征值 常用常用的方法：的方法：降阶降阶方法（方法（收缩收缩技巧）技巧）设已经计算出设已经计算出模最大模最大特征值特征值 及其特征向量及其特征向量 根据对称矩阵的性质，有根据对称矩阵的性质，有 如何求出其他如何求出其他特征值特征值 ，及其特征向量，及其特征向量 于是于是 例例8.5 8.5 用幂法计算 的最大特征值和相应的特征向量.计算过程如表8-1.表8-1的结果是用8位浮点数字进行运算得到的，的分量值是舍入值.于是得到 及相应的特征向量 和相应的特征向量的真值（8位数字）为 幂法的加速幂法的加速 原点平移法原点平移法 由前面讨论知道，应用幂法计算 的主特征值的收敛速度主要由比值 来决定，但当 接近于1时，收敛可能很慢.一个补救的办法是采用加速收敛的方法.引进矩阵 其中 为选择参数.设 的特征值为 ，则 的相应特征值为 ，而且 的特征向量相同.如果要计算 的主特征值 ，就要适当选择 使 仍然是 的主特征值，且使 对 应用幂法，使得在计算 的主特征值 的过程中得到加速.这种方法通常称为原点平移法.例例 设 有特征值 比值 .作变换 则 的特征值为 应用幂法计算 的主特征值 的收敛速度的比值为 选择有利的 值，虽然能够使幂法得到加速，但问题在于如何选择适当的参数 .设 的特征值满足（2.10）则不管 如何，的主特征值为 或 .当希望计算 及 时，首先应选择 使 且使收敛速度的比值 显然，当 ,即 时 为最小，这时收敛速度的比值为 当 的特征值满足（2.10）且 能初步估计时，就能确定 的近似值.当希望计算 时，应选择 例例6 6 计算矩阵的主特征值.使得应用幂法计算 得到加速.作变换 取 ，则 对 应用幂法，计算结果如表8-2.由此得 的主特征值为 的主特征值 为 与例3结果比较，上述结果比例3迭代15次还好.若迭代15次，（相应的 ).原点位移的加速方法，是一个矩阵变换方法.这种变换容易计算，又不破坏矩阵 的稀疏性，但 的选择依赖于对 的特征值分布的大致了解.