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