初等变换求矩阵特征值发展历史

初等变换求矩阵特征值发展历史
初等变换求矩阵特征值发展历史

初等变换求矩阵特征值发展历史
矩阵的特征值与特征向量问题 物理、力学和工程技术中的许多问 题在数学上都归结为求矩阵的特征值和特征向量问题.计算方阵A的特征值,就是求特征方程 即 的根.求出特征值 后,再求相应的齐次线性方程组 的非零解,即是对应于 的特征向量.这对于阶数较小的矩阵是可以的,但对于阶数较大的矩阵来说,求解是十分困难,所以用这种方法求矩阵的特征值是不切实际的. 我们知道,如果矩阵A与B相似,则A与B有相同的特征值.因此人们就希望在相似变换下,把A化为最简单的形式.一般矩阵的最简单的形式是约当标准形.由于在一般情况下,用相似变换把矩阵A化为约当标准形是很困难的,于是人们就设法对矩阵A依次进行相似变换,使其逐步趋向于一个约当标准形,从而求出A的特征值. 本章介绍求部分特征值和特征向量的幂法,反幂法;求实对称矩阵全部特征值和特征向量的雅可比方法；求特征值的多项式方法；求任意矩阵全部特征值的QR方法. 第一节幂法与反幂法 一幂法 幂法是一种求任意矩阵A的按模最大特征值及其对应特征向量的迭代算法.该方法最大的优点是计算简单,容易在计算机上实现,对稀疏矩阵较为合适,但有时收敛速度很慢. 为了讨论简单,我们假设 (1)n阶方阵A的特征值 按模的大小排列为 (1) (2) 是对应于特征值 的特征向量 ; (3) 线性无关. 任取一个非零的初始向量 ,由矩阵A构造一个向量序列 (2) 称为迭代向量.由于 线性无关,构成n维向量空间的一组基,所以,初始向量 可唯一表示成 (3) 于是 (4) 因为比值 所以 (5) 当k充分大时有 (6) 从而 (7) 这说明当k充分大时,两个相邻迭代向量 与 近似地相差一个倍数,这个倍数便是矩阵A的按模最大的特征值 .若用 表示向量 的第 个分量,则 (8) 也就是说两个相邻迭代向量对应分量的比值近似地作为矩阵A的按模最大的特征值. 因为,又 ,所以有 ,因此向量 可近似地作为对应于 的特征向量. 这种由已知的非零向量 和矩阵A的乘幂构造向量序列 以计算矩阵A的按模最大特征值及其相应特征向量的方法称为幂法. 由(4)式知,幂法的收敛速度取决于比值 的大小.比值越小,收敛越快,但当比值 接近于1时,收敛十分缓慢. 用幂法进行计算时,如果 ,则迭代向量 的各个不为零的分量将随着k无限增大而趋于无穷.反之,如果 ,则 的各分量将趋于零.这样在有限字长的计算机上计算时就可能溢出停机.为了避免这一点,在计算过程中,常采用把每步迭代的向量 进行规范化,即用 乘以一个常数,使得其分量的模最大为1.这样,迭代公式变为 (9) 其中 是 模最大的第一个分量.相应地取 (10) 例1 设 用幂法求其模为最大的特征值及其相应的特征向量(精确到小数点后三位). 解 取 ,计算结果如表4-1所示. 表4-1 1 1 0 1 1 1 0 1 2 2 -2 2 2 1 -1 1 3 3 -4 3 -4 -0.75 1 -0.75 4 -2.5 3.5 -2.5 3.5 -0.714 1 -0.714 5 -2.428 3.428 -2.428 3.428 -0.708 1 -0.708 6 -2.416 3.416 -2.416 3.416 -0.707 1 -0.707 7 -2.414 3.414 -2.414 3.414 -0.707 1 -0.707 当k=7时, 已经稳定,于是得到 及其相应的特征向量 为 应用幂法时,应注意以下两点: (1)应用幂法时,困难在于事先不知道特征值是否满足(1)式,以及方阵A是否有n个线性无关的特征向量.克服上述困难的方法是：先用幂法进行计算,在计算过程中检查是否出现了预期的结果.如果出现了预期的结果,就得到特征值及其相应特征向量的近似值;否则,只能用其它方法来求特征值及其相应的特征向量. (2)如果初始向量 选择不当,将导致公式(3)中 的系数 等于零.但是,由于舍入误差的影响,经若干步迭代后, .按照基向量 展开时, 的系数可能不等于零.把这一向量 看作初始向量,用幂法继续求向量序列 ,仍然会得出预期的结果,不过收敛速度较慢.如果收敛很慢,可改换初始向量. 二 原点平移法 由前面讨论知道,幂法的收敛速度取决于比值 的大小.当比值接近于1时,收敛可能很慢.这时,一个补救的方法是采用原点平移法. 设矩阵 (11) 其中p为要选择的常数. 我们知道 与 除了对角线元素外,其它元素都相同,而A的特征值 与 的特征 之间有关系 ,并且相应的特征向量相同.这样,要计算 的按模最大的特征值,就是适当选择参数 ,使得 仍然是 的按模最大的特征值,且使 对 应用幂法,使得在计算 的按模最大的特征值 的过程中得到加速,这种方法称为原点平移法. 例2 设4阶方阵A有特征值 比值,令 作变换 则 的特征值为 应用幂法计算 的按模最大的特征值 时,确定收敛速度的比值为 所以对B应用幂法时,可使幂法得到加速. 虽然选择适当的p值,可以使得幂法得到加速,但由于矩阵的特征值的分布情况事先并不知道,所以在计算时,用原点平移法有一定的困难. 下面考虑当 的特征值为实数时,如何选择参数 ,以使得用幂法计算 时得到加速的方法. 设 的特征值满足 则对于任意实数 , 的按模最大的特征值 或. 如果需要计算 及时,应选择 使 且确定的收敛速度的比值 当,即时, 为最小.这时用幂法计算 及 时得到加速. 如果需要计算 及时,应选择 使 且确定收敛速度的比值 当即时, 为最小.这时用幂法计算 及 时得到加速. 原点平移的加速方法,是一种矩阵变换方法.这种变换容易计算,又不破坏A的稀疏性,但参数p的选择依赖于对A的特征值的分布有大致了解. 三反幂法 反幂法用于求矩阵A的按模最小的特征值和对应的特征向量,及其求对应于一个给定的近似特征值的特征向量. 设n阶方阵A的特征值按模的大小排列为 相应的特征向量为 .则 的特征值为 对应的特征向量仍然为 .因此,计算矩阵A的按模最小的特征值,就是计算 的按模最大的特征值.这种把幂法用到 上,就是反幂法的基本思想. 任取一个非零的初始向量 ,由矩阵 构造向量序列 (12) 用(12)式计算向量序列 时,首先要计算逆矩阵 .由于计算 时,一方面计算麻烦,另一方面当A为稀疏阵时, 不一定是稀疏阵,所以利用 进行计算会造成困难.在实际计算时,常采用解线性方程组的方法求 .（12）式等价于 (13) 为了防止溢出,计算公式为 (14) 相应地取 (15) (13)式中方程组有相同的系数矩阵A,为了节省工作量,可先对矩阵A进行三角分解 (16) 再解三角形方程组 (17) 当A是三对角方阵,或是非零元素较少且分布规律的方阵时,无论存储或计算都比较便.根据幂法的讨论,我们知道,在一定条件下,可求得 的按模最大的特征值和相应的特征向量,从而得到A的按模最小的特征值和对应的特征向量,称这种方法为反幂法.反幂法也是一种迭代算法,每一步都要解一个系数矩阵相同的线性方程组. 设p为任一实数,如果矩阵 可逆,则 的特征值为 对应的特征向量仍为 . 如果p是矩阵A的特征值 的一个近似值,且 则是矩阵 的按模最大的特征值.因此,当给出特征值 的一个近似值p时,可对矩阵 应用反幂法,求出对应于 的特征向量.反幂法迭代公式中的 通过方程组 求得. 例3 用反幂法求矩阵 的对应于特征值 的特征向量. 解取 解方程组 得 再解方程组 得 与 的对应分量大体上成比例,所以对应于 的特征向量为