《Chapter9-2-QR算法PPT演示课件.ppt》由会员分享，可在线阅读，更多相关《Chapter9-2-QR算法PPT演示课件.ppt（23页珍藏版）》请在三一文库上搜索。
1、1,QR方法在特征值计算问题的发展上具有里程碑 意义。在1955年的时候人们还觉得特征值的计算 是十分困扰的问题，到1965年它的计算基于 QR方法的程序已经完全成熟。直到今天QR方法 仍然是特征值计算的有效方法之一。, 7 QR方法,2,一 Householder变换,定义1,设 ,且 , 则初等矩阵,称为Householder变换矩阵，也称初等镜面反射矩阵。,Householder矩阵基本性质,性质1,H是对称正交矩阵，即,性质2,设,则,性质2的意义是任意向量 , 在Householder变换作用下, Euclid长度不变. 此外，由,知,由于,是实数, 上式表示向量x-y与向量w平行,
2、3,性质3,设,，则由向量,确定的Household矩阵H(w),使得Hx=y。,4,例2,设,试求H矩阵, 使,直接验证,5,计算,的算法如下：,6,二、矩阵的QR分解,定理1,设矩阵,矩阵Q，上三角矩阵R，使A=QR且当要求R的主对角元素均为正数时，则分解式是唯一的。,且非奇异，则一定存在正交,A的非奇异性及Householder变换矩阵的性质知，一定可构造n-1个H矩阵,7,例3,设矩阵,试作矩阵A=QR分解。,8,9,10,通常采用的方法是先将矩阵相似约化为上 Hessenberg形式的矩阵, 在此基础上应用QR迭 代. 这时, 一个QR迭代步的乘法运算次数只需 O(n)次.,三、相似
3、约化为上Hessenberg矩阵,对一般n阶矩阵, QR算法的每一个迭代步需要 O(n)次乘法运算.如果矩阵阶数稍大，这个算法 几乎没有实际的应用价值.,11,例如：一个5阶的上Hessenberg矩阵具有如下的 形式：,下面介绍QR方法时，都假设矩阵A是一个上 Hessenberg矩阵.,所谓上Hessenberg矩阵是指一个n阶矩阵A,如果当ij+1时，aij=0，称A为上Hessenberg矩阵.,定义1,12,设A是n阶矩阵且有QR分解AQR，这里，Q是 酉矩阵，R是上三角矩阵. 如果A是满秩并规定R 有正对角元，这个分解是惟一的.,五、QR算法,QR方法是1961年由作者J.G.F.
4、Francis和 V.N.Kublanovskaya设计的,QR分解是QR算法的基础,13,(1)QR算法的基本思想,记 AA1且有A1Q1R1.,将等号右边两个矩阵因子的次序交换，得 A2R1Q1,不难证明:,即,矩阵序列Ak有相同的特征值.,14,因为上Hessenberg矩阵次对角线以下的元素全为0, 因此, 只要证明, 当k时, 由迭 代格式产生的矩阵Ak的次对角元趋向于零就可以了.,记,容易得到 是Ak的一个QR分解,如果A是一个满秩的上Hessenberg矩阵, 可以证明, 经过一个QR迭代步得到的A2Q-11A1Q1仍然是上 Hessenberg矩阵.,15,这里, 基本收敛的含
5、义指Ak的元素中除对角线以 下的元素趋于零外, 可以不收敛于R的元素.,(2) QR算法的收敛性,设n阶矩阵A的n个特征值满足 |1|2|n|0， 其相应的n个线性无关特征向量为x1, x2, , xn.,记 X=(x1,x2,xn), Y= X-1.,如果Y存在LU分解, 那么, 矩阵Ak基本收敛于上三 角矩阵R.,定理3,16,(3) QR算法的迭代过程,1. 一个QR迭代步的计算,对l=1,2,n-1, 构造n-1个平面旋转矩阵Pl,l+1,使 A1的次对角元全部零化,实现A1的QR分解的计算,这里,17,用Pl,l+1右乘，所得结果也放回矩阵A相应的元素中.,2. QR算法的迭代控制,
6、当迭代步数k充分大时, 由迭代格式产生的Ak的次 对角元趋于0.,在实际计算中, 控制迭代次数常用的一种办法 是, 预先给定一个小的正数, 在一个迭代步的 计算结束后, 对l=n-1, n-2,1, 依次判别次对 角元的绝对值是否满足,18,或更严格的准则,或不太严格的准则,如果上面三个不等式中有一个成立, 把 看做实际上为零.,19,例4,设矩阵,试用QR算法求它的特征值。,20,21,22,(4)带原点位移的算法,由算法收敛性证明可以看出，算法的 收敛速度 依赖于矩阵相邻特征值的比值.,为了加快算法的收敛速度, 在迭代过程中, 对矩 阵Ak确定一个原点位移量sk, 称Ak-skI为带原点位移量的矩阵.,再对Ak-skI应用QR算法.,这时, 迭代格式改为,称为带原点位移的QR算法,23,计算特征值问题的QR方法，实际上总是分成2 个阶段：,对称矩阵,三对角矩阵,对角矩阵,一般矩阵,上Hessenberg矩阵,上三角矩阵,