《高中数学 反幂法用来计算矩阵按模最小的特征值及其特征向量》由会员分享,可在线阅读,更多相关《高中数学 反幂法用来计算矩阵按模最小的特征值及其特征向量(38页珍藏版)》请在金锄头文库上搜索。
1、 8.2.3 反幂法 反幂法用来计算矩阵按模最小的特征值及其特征向量, 也可用来计算对应于一个给定近似特征值的特征向量. 设 为非奇异矩阵, 的特征值次序记为 相应的特征向量为 ,则 的特征值为 对应的特征向量为 . 因此计算 的按模最小的特征值 的问题就是计算 的按模最大的特征值的问题. 1对于 应用幂法迭代(称为反幂法),可求得矩阵 的主特征值 ,从而求得 的按模最小的特征值 . 反幂法迭代公式为: 任取初始向量 , 构造向量序列 迭代向量 可以通过解方程组 求得. 定理15 设 为非奇异矩阵且有 个线性无关的特征 向量,其对应的特征值满足 2则对任何初始非零向量 ,由反幂法构造的向量 序
2、列 满足收敛速度的比值为 . 反幂法中也可以用原点平移法来加速迭代过程或求其 他特征值及特征向量. 如果矩阵 存在,其特征值为 3对应的特征向量仍然是 . 对矩阵 应用幂法,得到反幂法的迭代公式 (2.12)如果 是 的特征值 的一个近似值,且设 与其 他特征值是分离的,即就是说 是 的主特征值,可用反幂法计算4特征值及特征向量. 设 有 个线性无关的特征向量 , 则 其中 5同理可得: 定理16 设 有 个线性无关的特征向量, 的特征值及对应的特征向量分别记为 及 , 而 为 的近似值, 存在,且则对任意的非零初始向量 ,由反幂法迭代公式 (2.12)构造的向量序列 满足 6且收敛速度由比值
3、 确定. 由该定理知,对 (其中 ) 应用反幂法, 可用来计算特征向量 . 只要选择的 是 的一个较好的近似且特征值分离情 况较好,一般 很小,常常只要迭代一二次就可完成特征 向量的计算. 反幂法迭代公式中的 是通过解方程组 求得的. 为了节省工作量,可以先将 进行三角分解 7其中 为某个排列阵,于是求 相当于解两个三角形方程 组 可以按下述方法选择 :选 使 (2.13)用回代求解(2.13)即得 ,然后再按公式(2.12)进行迭 代. 反幂法计算公式 1. 分解计算 82. 反幂法迭代 9例6 用反幂法求 的对应于计算特征值 (精确特征值为 ) 的特征向量(用5位浮点数进行运算). 解 用
4、部分选主元的三角分解将 (其中 ) 分解为 其中 10由 ,得 11由 ,得 对应的特征向量是 由此看出 是 的相当好的近似. 特征值 , 的真值为128.3 豪斯霍尔德方法 8.3.1 引言 本节讨论两个问题(1) 用初等反射阵作正交相似变换约化一般实矩阵 为上海森伯格阵.(2) 用初等反射阵作正交相似变换约化对称矩阵 为 对称三对角阵.于是,求原矩阵特征值问题,就转化为求上海森伯格阵 或对称三对角阵的特征值问题. 8.3.2 用正交相似变换约化一般矩阵为上海森柏格阵 设 . 可选择初等反射阵 使 经正交相似变换约化为一个上海森伯格阵. 13(1) 设 其中 ,不妨设 , 否则这一 步不需要
5、约化. 选择初等反射阵 使 , 其中 14(3.1)令则 15其中 (2) 第 步约化:重复上述过程,设对 已完成第1步 ,第 步正交相似变换,即有 或 16且 17其中 为 阶上海森伯 格阵, 设 ,于是可选择初等反射阵 使 , 其中, 计算公式为 (3.2)18令 则 (3.3)其中 为 阶上海森伯格阵. 第 步约化只需计算及 (当 为对称阵时,只需计算 ). 19(3) 重复上述过程,则有 总结上述讨论,有 20定理17 (豪斯霍尔德约化矩阵为上海森伯格阵)设,则存在初等反射阵 使 算法1(豪斯霍尔德约化矩阵为上海森伯格型) 设 ,本算法计算 (上海森伯格型), 其中 为初等反射阵的乘积
6、. (1) 计算初等反射阵 使 (2) 约化计算 21本算法约需要 次乘法运算,要明显形成 还需要附加 次乘法. 例7 用豪斯霍尔德方法将 矩阵约化为上Hessenberg阵. 22解 选取初等反射阵 使 ,其中 . (1) 计算 则有 23(2) 约化计算: 令 则 248.3.3 用正交相似变换约化对称阵为对称三 对角阵 定理18 (豪斯霍尔德约化对称阵为对称三对角阵)设为对称矩阵,则存在初等反射阵 使 25证明 由定理17,存在初等反射阵 使为上海森伯格阵, 且亦是对称阵,因此, 为对称三对角阵. 由上面讨论可知,当 为对称阵时,由 一步约化计算中只需计算 及 . 又由于 的对称性,故只
7、需计算 的对角线以下 元素. 注意到 引进记号 26则 算法2(豪斯霍尔德约化对称阵为对称三对角阵) 设为对称阵,本算法确定初等反射阵 使 (为对称三对角阵). 的对角元 存放在数组 内, 的次对 角元素 存放在数组 内. 数组 最初可用来存放 及 ,确定 中向量 的分量存放在 的相应位置. 冲掉 ,约化 的结果冲27掉 ,数组 的上部分元素不变. 如果第 步不需要变换则 置 为零. 2829对对称阵 用初等反射阵正交相似约化为对称三对角阵大约需要 次乘法. 308.4 QR 方 法 8.4.1 QR算法 QR方法是一种变换方法,是计算一般矩阵(中小型矩 阵)全部特征值问题的最有效方法之一.
8、QR方法主要用来计算:(1)上海森伯格阵的全部特征 值问题,(2)计算对称三对角矩阵的全部特征值问题,且 QR方法具有收敛快,算法稳定等特点. 对于一般矩阵 (或对称矩阵),则首先用豪斯 霍尔德方法将 化为上海森伯格阵 (或对称三对角阵), 然后再用QR方法计算 的全部特征值. 设 ,且对 进行QR分解,即 31其中 为上三角阵, 为正交阵,于是可得到一新矩阵 显然, 是由 经过正交相似变换得到,因此 与 特征 值相同. 再对 进行QR分解,又可得一新的矩阵,重复这一过 程可得到矩阵序列: 设 将 进行QR分解 作矩阵 求得 后将 进行QR分解 形成矩阵 32QR算法,就是利用矩阵的QR分解,
9、按上述递推法则 构造矩阵序列 的过程. 只要 为非奇异矩阵,则由QR 算法就完全确定 . 定理19(基本QR方法)设 . 构造QR算法: (4.1)记 ,则有 (1) 相似于 ,即 (2) (3) 的QR分解式为 33证明 (1),(2)显然,现证(3). 用归纳法,显然,当 时有 ,设有分解式 于是 其中利用了 由第5章定理30或定理31知,将 进行QR分解,即将用正交变换(左变换)化为上三角矩阵 34其中 , 故 这就是说 可由 按下述方法求得: (1) 左变换 (上三角阵); (2) 右变换 定理20(QR方法的收敛性)设 , (1) 如果 的特征值满足: ; (2) 有标准型 其中 , 且设 有三角分解 ( 为单位下三角阵, 为 上三角阵,则由QR算法产生的 本质上收敛于上三角35矩阵,即若记 ,则 (4.2)(4.3)当 时 极限不一定存在. 36定理21 如果对称矩阵 满足定理20的条件,则由QR 算法产生的 收敛于对角阵 . 关于QR算法收敛性的进一步结果为: 设 ,且 有完备的特征向量集合,如果 的 等模特征值中只有实重特征值或多重复的共轭特征值,则 由QR算法产生的 本质收敛于分块上三角矩阵(对角 块为一阶和二阶子块)且对角块中每一个22子块给出 的 一对共轭复特征值,每一个一阶对角子块给出 的实特征值, 即 37其中 为22子块,它给出 一对共轭特征值. 38