数值分析课件第8章3-4节

《数值分析课件第8章3-4节》由会员分享，可在线阅读，更多相关《数值分析课件第8章3-4节（64页珍藏版）》请在金锄头文库上搜索。

1、1,8.3 豪斯霍尔德方法,8.3.1 引言,本节讨论两个问题,（1） 用初等反射阵作正交相似变换约化一般实矩阵 为上海森伯格阵.,（2） 用初等反射阵作正交相似变换约化对称矩阵 为对称三对角阵.,于是，求原矩阵特征值问题，就转化为求上海森伯格阵 或对称三对角阵的特征值问题.,2,8.3.2 用正交相似变换约化一般矩阵为 上海森柏格阵,设 .,我们的目标是选择初等反射阵 ，,使 经正交相似变换约化为一个上海森伯格阵.,3,（1） 设,选择初等反射阵,其中 ，不妨设 , 否则这一 步不需要约化.,使,4,（3.1）,令,其中,则,5,其中,6,(2) 第 步约化：,且,7,其中 为 阶上海森伯格

2、阵，,设 ，于是可选择初等反射阵 使 ，,其中, 计算公式为,8,（3.2）,令,则,9,（3.3）,其中 为 阶上海森伯格阵.,第 步约化只需计算 及 .,当 为对称阵时，只需计算 .,10,总结上述讨论，有下面定理.,（3） 重复上述过程，则有,11,定理17,则存在初等反射阵 使,算法1,设 ，,本算法计算 (上海森伯格型)，,其中 为初等反射阵的乘积.,(1) 计算初等反射阵 使,（豪斯霍尔德约化矩阵为上海森伯格阵）,设,（豪斯霍尔德约化矩阵为上海森伯格型）,12,(2) 约化计算,本算法约需要 次乘法运算，要明显形成 还需 要附加 次乘法.,13,例7,矩阵约化为上海森伯格阵.,用豪

3、斯霍尔德方法将,解,使 ，,选取初等反射阵,其中,(1) 计算,14,则有,(2) 约化计算,令,15,则,16,8.3.3 用正交相似变换约化对称阵为对称三对角阵,定理18,（豪斯霍尔德约化对称阵为对称三对角阵）,设,为对称矩阵，,使,则存在初等反射阵,17,证明,又由于 的对称性，故只需计算 的对角线以下 元素.,注意到,18,引进记号,则,19,算法2,（豪斯霍尔德约化对称阵为对称三对角阵）,的对角元 存放在数组 内.,的次对角元素 存放在数组 内.,数组 最初可用来存放 及 ，确定 中向量 的分量存放在 的相应位置.,冲掉 ，约化 的结果冲掉 ，数组 的上部分 元素不变.,20,如果第

4、 步不需要变换则置 为零.,21,22,对对称阵 用初等反射阵正交相似约化为对称三对角 阵大约需要 次乘法.,23,8.4 QR 方 法,8.4.1 QR算法,QR方法是一种变换方法，是计算一般矩阵（中小型矩 阵）全部特征值问题的最有效方法之一.,QR方法主要用来计算：,（1）上海森伯格阵的全部特征值问题，,（2）计算对称三对角矩阵的全部特征值问题，且QR方法具有收敛快，算法稳定等特点.,24,设 ，且对 进行QR分解，即,对于一般矩阵 （或对称矩阵），首先用豪斯 霍尔德方法将 化为上海森伯格阵 （或对称三对角阵），,然后再用QR方法计算 的全部特征值.,其中 为上三角阵， 为正交阵.,显然，

5、 是由 经过正交相似变换得到，因此 与 特征 值相同.,于是可得到一个新矩阵,25,再对 进行QR分解，又可得一个新的矩阵，重复这一过 程可得到矩阵序列：,设,将 进行QR分解,作矩阵,求得 后将 进行分解,形成矩阵,QR算法，就是利用矩阵的QR分解，按上述递推法则 构造矩阵序列 的过程.,26,只要 为非奇异矩阵，则由QR算法就完全确定 .,定理19,设 . 构造QR算法：,记 则有,（1） 相似于 ，即,（2）,（3） 的QR分解式为,（基本QR方法）,（4.1）,27,证明,用归纳法，,显然，当 时有 ，,设 有分解式,于是,其中利用了,（1）,（2）显然，下面证（3）.,28,由第5章

6、定理30或定理31知，将 进行QR分解，即将 用正交变换（左变换）化为上三角矩阵,其中 , 故,这就是说 可由 按下述方法求得：,（1） 左变换 (上三角阵）；,（2） 右变换,29,定理20,设 .,(1) 如果 的特征值满足： ；,(2) 有标准型 其中 ，,（QR方法的收敛性）,且设 有三角分解 ( 为单位下三角阵， 为上三角阵.则由QR算法产生的 本质上收敛于上三角矩阵，,即,30,若记 ，则,（4.2）,当 时 极限不一定存在.,（4.3）,31,定理21,关于QR算法收敛性的进一步结果有：,设 ，且 有完备的特征向量集合，如果 的 等模特征值中只有实重特征值或多重复的共轭特征值，则

7、 由QR算法产生的 本质收敛于分块上三角矩阵（对角 块为一阶和二阶子块）且对角块中每一个22子块给出 的 一对共轭复特征值，每一个一阶对角子块给出 的实特征值，,即,32,其中 ， 为22子块，它给出 的一对共轭特征 值.,33,则 元素将以收敛因子 线性收敛于零，,8.4.2 带原点位移的QR方法,定理20中 的速度依赖于比值 ，,当 很小时，收敛较快.,如果 为 的一个估计，且对 运用QR算法，,为了加速收敛，选择数列 ，按下述方法构造矩阵 序列 ，称为带原点位移的QR算法.,设,元素将比在基本算法中收敛更快.,34,对 进行QR分解,形成矩阵,求得 后，将 进行QR分解,（4.4）,形成

8、矩阵,（4.5）,若令 ，,则有 ，,并且矩阵 有QR分解式,35,在带位移QR方法中，每步并不需要形成 和 ，可按 下面的方法计算：,首先用正交变换（左变换）将 化为上三角阵，,即,当 为上海森伯格阵或对称三对角阵时， 可为平面旋转阵，,则,36,下面考虑用QR方法计算上海森伯格阵的特征值.,设 为上海森伯格阵，即,如果 ，则称 为不可约上海森伯格阵.,设 ，由定理17可选正交阵 使,对 应用QR算法.,为上海森伯格阵，,37,QR算法：,对于,（4.6）,假设由（4.6）迭代产生的每一个上海森伯格阵 都是不可 约的，,否则，若在某步有,于是，这个问题就分离为 与 两个较小的问题.,38,当

9、 或 时，有,或,由此可得到 的特征值 ，或由 右下角二阶 阵的特征值求出 .,39,对降阶的 ，用类似的方法可求出 的其余特征值.,实际上，每当 的次对角元适当小时，就可进行分离.,就把 视为零.,一般取 ，其中 是计算中有效数字的位数.,例如，如果,40,8.4.3 用单步QR方法计算上海森伯格阵的特征值,上海森伯格阵的单步QR方法：,选取 并设,对于 （用位移来加速收敛）,由 实际计算为,41,（1）左变换：,（2）右变换：,其中 为平面旋转阵.,（1） 左变换计算,确定平面旋转阵 使,42,（4.7）,设已完成第1次， 第 次左变换，即有,第 次变换的工作就是要确定平面旋转阵 ，,使

10、变为0，且完成第 次左变换,43,这时只需计算（4.7）阵第 行及第 行元素.,这是因为平面旋转阵 只改变矩阵的 行和 行.,继续这一过程，最后有,（2） 右变换计算,在第 次右变换 中，只需计算 第 列及第 列元素.,44,最后,由上述讨论指出，如果 为上海森伯格阵，,则用QR算法产生的 也是上海森伯格阵.,即上海森伯格阵在QR变换下形式不变.,45,下面讨论一个极端的情况 .,定理22,设：（1） 为不可约上海森伯格阵；,（2） 为 一个特征值.,中,则QR方法,证明,记,46,由设 为不可约阵，则上海森伯格阵 也不可约.,由将上海森伯格阵 约化为上三角阵 的平面旋转 变换的取法可知,又因

11、为 为奇异矩阵，,从而得到 .,因此， 的最后一行为 ，,即,这样在QR方法迭代中，参数 可选为 ，即 的 元素,通常可以作为特征值的最好近似.,47,算法3,且 覆盖,（上海森伯格阵的QR算法）,给定 为上海森伯格阵，本算法计算,48,49,如果用不同的位移 ，反复应用算法3就产生正 交相似的上海森伯格阵序列 .,当 充分小时，可将它置为零就得到 的近似特征值 .,再将矩阵降阶，对较小矩阵连续应用算法.,50,例8,用QR方法计算对称三对角矩阵,的全部特征值.,解,选取 ，则,51,52,现在收缩，继续对 的子矩阵 进行变换，得到,53,故求得 近似特征值为,而 的特征值是,算法3是在实数中

12、进行选择位移 , 不能逼近一 个复特征值，所以算法3不能用来计算 的复特征值.,54,8.4.4* 双步QR方法（隐式QR方法）,第3节中将 经过正交相似变换化为上海森伯格矩阵 ，即 ，其中 不是惟一的.,但是，如果规定了正交矩阵 的第一列，则 和 除 差1因子外惟一.,定理23,设 , 且：,（1） 及 都是 正交阵，且有 都是上海森伯格阵.,（隐式Q定理）,（2） 为不可约上海森伯格阵，且 （即 与 第1列相同）.,55,（1） ,且 ;,（2） ,其中 .,则：,即 和 在 意义上“本质上相等”.,算法3不能用来求 的一个复特征值.,当 的按模最小特征值是复数时，位移参数 可取为某步 右

13、下角的二阶矩阵,（4.8）,的特征值.,56,当 的特征值 与 为复数时，如果应用算法3就要 引进复数运算，这对于实矩阵 是不必要的.,在某些条件下，可以用正交相似变换将 约化为实Schur型.,隐式位移的QR方法，即用 与 作位移连续进行二次 单步的QR迭代，使用复位移，又避免复数运算.,（1） 设 为上海森伯格阵，取共轭复 数 作两步位移的QR方法，即,57,显然 有QR分解,（4.10）,事实上，由(4.9)式并利用,（4.9）,有,58,且 阵为实矩阵.,这是因为（即使 的特征值为复数）,（4.11）,其中,于是，（4.10）式为实矩阵 的QR分解，并且可以 选取 和 使 为实的正交阵

14、.,由此得出,为实数.,59,是实矩阵.,如果用下述算法就能保证 是实矩阵:,(a) 直接形成实矩阵,(b) 计算 阵的实QR分解,(c) 令,但是(a)需要 次乘法运算，不实用.,（2） 根据隐式Q定理，如果按下述算法进行，就有可 能用 次运算来实现从 到 的转换.,(a) 求与 有相同第一列的正交阵,60,(b) 应用豪斯霍尔德方法将 化为一个上海森 伯格阵，即,记 , 上式为,显然， 的第一列与 的第一列相同，即 与 第一 列相同（ ）.,若 与 两者都是不可约上海森伯格阵，,则由隐式Q定理， 与 本质上相等.,（3） 如何寻求正交阵 .,61,由于 (为 的QR分解），则,于是，对 阵的第一列（非零）寻求初等反射阵 ,说明 第一列即是 第一列的一个倍数.,即,这说明 与 具有相同的第一列.,使,由于 , 则,62,其中,（4.12）,双步QR方法：,设 为