QR算法学习教程.pptx

《QR算法学习教程.pptx》由会员分享，可在线阅读，更多相关《QR算法学习教程.pptx（23页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、一 HouseholderHouseholder变换定义定义1设设 ,且且 ,则初等则初等矩阵矩阵 称为称为Householder变换矩阵，也称初等镜面反射矩阵。变换矩阵，也称初等镜面反射矩阵。Householder矩阵基本性矩阵基本性质质性质性质1H是对称正交矩阵，即是对称正交矩阵，即 性质性质2设设则则性质性质2的意义是任意向量的意义是任意向量 ,在在Householder变换作用下变换作用下,Euclid长度不变长度不变.此外，此外，由由 知知由于由于 是实数是实数,上式表示向量上式表示向量x-y与向量与向量w平行平行 第1页/共23页性质性质3 设设，则由向量，则由向量 确定的确定的H

2、ousehold矩阵矩阵H(w),使得使得Hx=y。第2页/共23页例例2 设设试求试求H矩阵矩阵,使使 直接验证直接验证 第3页/共23页计算计算 的算法如下：的算法如下：第4页/共23页二、矩阵的二、矩阵的QR分解分解定理定理1设矩阵设矩阵 矩阵矩阵Q，上三角矩阵，上三角矩阵R，使，使A=QR且当要求且当要求R的主的主对角元素均为正数时，则分解式是唯一的。对角元素均为正数时，则分解式是唯一的。且非奇异，则一定存在正交且非奇异，则一定存在正交A的非奇异性及的非奇异性及Householder变换矩阵的性质知，变换矩阵的性质知，一定可构造一定可构造n-1个个H矩阵矩阵 第5页/共23页例例3设矩

3、阵设矩阵 试作矩阵试作矩阵A=QR分解。分解。第6页/共23页第7页/共23页第8页/共23页通通常常采采用用的的方方法法是是先先将将矩矩阵阵相相似似约约化化为为上上Hessenberg形形式式的的矩矩阵阵,在在此此基基础础上上应应用用 QR迭迭代代.这这 时时,一一 个个 QR迭迭代代步步的的乘乘法法运运算算次次数数只只需需O(n)次次.三、相似约化为上三、相似约化为上Hessenberg矩阵矩阵对对 一一 般般 n阶阶 矩矩 阵阵,QR算算法法的的每每一一个个迭迭代代步步需需要要O(n)次次乘乘法法运运算算.如如果果矩矩阵阵阶阶数数稍稍大大，这这个个算算法法几乎没有实际的应用价值几乎没有实

4、际的应用价值.第9页/共23页例如：一个例如：一个5阶的上阶的上Hessenberg矩阵具有如下矩阵具有如下的的形式：形式：下下面面介介绍绍 QR方方法法时时，都都假假设设矩矩阵阵 A是是一一个个上上Hessenberg矩阵矩阵.所所谓谓上上 Hessenberg矩矩阵阵是是指指一一个个 n阶阶矩矩阵阵 A,如如果果当当 ij+1时时，aij=0，称称 A为为上上Hessenberg矩矩阵阵.定义定义1第10页/共23页设A是n阶矩阵且有QR分解AQR，这里，Q是酉矩阵，R是上三角矩阵.如果A是满秩并规定R有正对角元，这个分解是惟一的.五、五、QR算法算法QR方方法法是是 1 9 6 1年年由

5、由作作者者和和设计的设计的QR分解是分解是QR算法的基础算法的基础第11页/共23页(1)QR算法的基本思想算法的基本思想记记 AA1且有且有A1Q1R1.将等号右边两个矩阵因子的次序交换，得将等号右边两个矩阵因子的次序交换，得 A2R1Q1且且即即不难证明不难证明:即即矩阵序列矩阵序列Ak有相同的特征值有相同的特征值.第12页/共23页因为上因为上Hessenberg矩阵次对角线以下的元素全矩阵次对角线以下的元素全为为0,因此因此,只要证明只要证明,当当k时时,由迭由迭 代格式产生代格式产生的矩阵的矩阵Ak的次对角元趋向于零就可以了的次对角元趋向于零就可以了.记记容易得到容易得到 是是Ak的

6、一的一个个QR分解分解如如 果果 A是是一一个个满满秩秩的的上上 Hessenberg矩矩 阵阵,可可以以证证明明,经经过过一一个个 QR迭迭代代步步得得到到的的 A2Q-11A1Q1仍仍然然是是上上Hessenberg矩阵矩阵.第13页/共23页这里,基本收敛的含义指Ak的元素中除对角线以下的元素趋于零外,可以不收敛于R的元素.(2)QR算法的收敛性算法的收敛性 设设n阶矩阵阶矩阵A的的n个特征值满足个特征值满足|1|2|n|0，其相应的其相应的n个线性无关特征向量为个线性无关特征向量为x1,x2,xn.记记 X=(x1,x2,xn),Y=X-1.如如 果果 Y存存 在在 LU分分 解解,那

7、那 么么,矩矩 阵阵 Ak基基本本收收敛敛于于上上三三角矩阵角矩阵R.定理定理3第14页/共23页(3)QR算法的迭代过程算法的迭代过程1.一个一个QR迭代步的计算迭代步的计算 对对l=1,2,n-1,构构 造造 n-1个个平平面面旋旋转转矩矩阵阵 Pl,l+1,使使 A1的次对角元全部零化的次对角元全部零化实现实现A1的的QR分解的计算分解的计算这里这里第15页/共23页用Pl,l+1右乘，所得结果也放回矩阵A相应的元素中.2.QR算法的迭代控制算法的迭代控制当当迭迭代代步步数数 k充充分分大大时时,由由迭迭代代格格式式产产生生的的 Ak的的次次对角元趋于对角元趋于0.在在实实际际计计算算中

8、中,控控制制迭迭代代次次数数常常用用的的一一种种办办法法是是,预预先先给给定定一一个个小小的的正正数数,在在一一个个迭迭代代步步的的计计算算结结束束后后,对对l=n-1,n-2,1,依依次次判判别别次次对对角元的绝对值是否满足角元的绝对值是否满足第16页/共23页或更严格的准则或更严格的准则或不太严格的准则或不太严格的准则如果上面三个不等式中有一个成立如果上面三个不等式中有一个成立,把把看做实际上为零看做实际上为零.第17页/共23页例例4设矩阵设矩阵 试用试用QR算法求它的特征值。算法求它的特征值。第18页/共23页第19页/共23页第20页/共23页(4)带原点位移的算法带原点位移的算法由

9、算法收敛性证明可以看出，算法的由算法收敛性证明可以看出，算法的收敛速度收敛速度 依赖于矩阵相邻特征值的比值依赖于矩阵相邻特征值的比值.为了加快算法的收敛速度为了加快算法的收敛速度,在迭代过程中在迭代过程中,对矩对矩阵阵Ak确定一个原点位移量确定一个原点位移量sk,称称Ak-skI为为带原点位移量的矩阵带原点位移量的矩阵.再对再对Ak-skI应用应用QR算法算法.这时这时,迭代格式改为迭代格式改为称为称为带原点位移的带原点位移的QR算法算法第21页/共23页计算特征值问题的计算特征值问题的QR方法，实际上总是分成方法，实际上总是分成2个阶段：个阶段：对称矩阵对称矩阵三对角矩阵三对角矩阵对角矩阵对角矩阵一般矩阵一般矩阵上上Hessenberg矩阵矩阵上三角矩阵上三角矩阵第22页/共23页感谢您的观看！第23页/共23页