带原点位移的QR方法.ppt

《带原点位移的QR方法.ppt》由会员分享，可在线阅读，更多相关《带原点位移的QR方法.ppt（28页珍藏版）》请在三一文库上搜索。

1、1,8.4.2 带原点位移的QR方法,定理20中 的速度依赖于比值 ，,当 很小时，收敛较快，如果 为 的一个估计，且对 运用QR算法，则 元素将以收敛因子 线性收敛于零， 元素将比在基本 算法中收敛更快.,为了加速收敛，选择数列 ，按下述方法构造矩阵 序列 ，称为带原点位移的QR算法.,设,对 进行QR分解,形成矩阵,2,求得 后，将 进行QR分解,（4.4）,形成矩阵,（4.5）,如果令 ，则有 ， 并且矩阵 有QR分解式,在带位移QR方法中，每步并不需要形成 和 ，可按 下面的方法计算：,首先用正交变换（左变换）将 化为上三角阵， 即,3,(当 为上海森伯格阵或对称三对角阵时， 可为平面

2、旋转阵)， 则,下面考虑用QR方法计算上海森伯格阵的特征值.,设 为上海森伯格阵，即,如果 ，则称 为不可约上海森 伯格阵.,4,设 ，由定理17可选正交阵 使 为上海森伯格阵，对 应用QR算法.,QR算法：,对于,（4.6）,假设由（4.6）迭代产生的每一个上海森伯格阵 都是不可 约的，否则，若在某步有,5,于是，这个问题就分离为 与 两个较小的问题. 当 或 时，有,或,6,即可求出 的特征值 或 （由 右下 角二阶阵的特征值求得），且求 的其余特征值时，转化 为降阶求 的特征值.,实际上，每当 的次对角元适当小时，就可进行 分离. 例如，如果,就把 视为零.,一般取 ，其中 是计算中有效

3、数字的位数.,7,8.4.3 用单步QR方法计算上海森伯格阵特征值,上海森伯格阵的单步QR方法：选取 并设,对于 （用位移来加速收敛）,由 实际计算为,8,（1） 左变换：,（2） 右变换：,其中 为平面旋转阵.,（1） 左变换计算,确定平面旋转阵 使,9,设已完成第1次， 第 次左变换，即有,（4.7）,确定平面旋转阵 ，使 变为0，且 完成第 次左变换 计算（只,10,需计算（4.7）阵第 行及第 行元素）.,继续这一过程，最后有,（2） 右变换计算,在第 次右变换 中，只需计算 第 列及第 列元素.,最后,11,由上述讨论指出，如果 为上海森伯格阵，则 用QR算法产生的 亦是上海森伯格阵

4、. 即 上海森伯格阵在QR变换下形式不变.,讨论一个极端的情况,定理22 设：（1） 为不可约上海森伯格阵； （2） 为 一个特征值. 则QR方法,12,中,证明 记,由设 为不可约阵，则上海森伯格阵 亦为不可约.,由将上海森伯格阵 约化为上三角阵 的平面旋转 变换的取法可知,13,又因为 为奇异矩阵，从而得到 . 因此， 的最后一行为 ，即,这样在QR方法迭代中，参数 可选为 ，即 的 元素. 通常可以作为特征值的最好近似.,算法3（上海森伯格阵的QR算法）给定 为上 海森伯格阵，本算法计算,且 覆盖,14,15,如果用不同的位移 ，反复应用算法3就产生正 交相似的上海森伯格阵序列 . 当

5、充分小时，可将它置为零就得到 的近似特征值 . 再将矩阵降阶，对较小矩阵连续应用算法.,例8 用QR方法计算对称三对角矩阵,16,的全部特征值.,解 选取 ，则,17,18,现在收缩，继续对 的子矩阵 进行变换，得到,故求得 近似特征值为,而 的特征值是,19,算法3是在实数中进行选择位移 , 不能逼近一 个复特征值，所以算法3不能用来计算 的复特征值.,20,8.4.4* 双步QR方法（隐式QR方法）,第3节中将 经过正交相似变换化为上海森伯 格矩阵 ，即 ，其中 不是唯一的. 但是， 如果规定了正交矩阵 的第一列，则 和 除差1因 子外唯一.,定理23（隐式Q定理）设 , 且：,（1） 及

6、 都是 正交阵，且有 都是上海森伯格阵.,（2） 为不可约上海森伯格阵，且 （即 与 第1列相同）. 则：,（1） , 且 ; （2） , 其中 ，,21,即 和 在 意义上“本质上相等”.,算法3不能用来求 的一个复特征值，当 （上海森 伯格阵）的依模最小特征值是复数时，位移参数 可取为某步 右下角的二阶矩阵,（4.8）,的特征值.,当 的特征值 与 为复数时，如果应用算法3就要 引进复数运算，这对于实矩阵 是不必要的，在某些条件 下，可以用正交相似变换将 约化为实Schur型.,隐式位移的QR方法，即用 与 作位移连续进行二次,22,单步的QR迭代，使用复位移，又避免复数运算.,（1） 设

7、 为上海森伯格阵，取共轭复 数 作两步位移的QR方法，即,（4.9）,显然 有QR分解,（4.10）,事实上，由(4.9)式并利用,23,有,且 阵为实矩阵，这是因为（即使 特征值为复数）,（4.11）,其中 为实数.,于是，（4.10）式为实矩阵 的QR分解，并且可以 选取 和 使 为实的正交阵.,由此得出,24,是实矩阵.,如果用下述算法就能保证 是实矩阵,(a) 直接形成实矩阵,(b) 计算 阵的实QR分解,(c) 令,但是(a)需要 次乘法运算，不实用.,（2） 根据隐式Q定理，如果按下述算法进行，就有可 能用 次运算来实现从 到 的转换.,(a) 求与 有相同第一列的正交阵,(b)

8、应用豪斯霍尔德方法将 化为一个上海,25,森伯格阵，即,记 , 上式为,显然， 的第一列与 的第一列相同，即 与 第一 列相同（ ）.,若 与 两者都是不可约上海森伯格阵， 则由隐式Q定理 与 本质上相等.,（3） 如何寻求正交阵 .,由于 (为 的QR分解），则,26,说明 第一列即是 第一列的一个倍数，于是，对 阵的第一列（非零）寻求初等反射阵 使,即,这说明 与 具有相同的第一列.,由于 , 则,其中,（4.12）,27,双步QR方法：设 为不可约上海森伯 格阵.,(a) 计算 阵的第一列. 即按（4.12）式计算,(b) 确定初等反射阵 使,即确定初等反射阵 使,28,(c) 计算初等反射阵 使,为上海森伯格阵，则 与 第一列 相同且 .,这样上面的算法就完成了从 到 的变换，但没有 明显的应用到位移 和 .,