反幂法用来计算矩阵按模最小的特征值及其特征向量.ppt

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