反幂法用来计算矩阵按模最小的特征值及其特征向量市公开课特等奖市赛课微课一等奖课件.pptx

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