《数值分析-第8-9讲-QR方法.ppt》由会员分享,可在线阅读,更多相关《数值分析-第8-9讲-QR方法.ppt(50页珍藏版)》请在三一办公上搜索。
1、朱立永,北京航空航天大学 数学与系统科学学院,数值分析,Password:beihang答疑时间:星期四下午2:305:30答疑地点:主216,第八讲矩阵特征值与特征向量的计算(2)-Jacobi方法和QR方法,第三章 矩阵特征值与特征向量的计算,常用的求特征值的方法有,幂法与反幂法 Jacobi法 QR方法,上次课内容回顾,幂法可以用来求矩阵模最大的特征值和特征向量;反幂法可以用来求矩阵模最小的特征值和特征向量;理论上可以用带原点平移的反幂法求得矩阵所有特征值和特征向量;在用幂法与反幂法求矩阵特征值和特征向量时,初始值u0的第一个分量不要为零;当|1|=|2|,但1=-2 时,直接幂法失败;
2、当|n-1|=|n|,但n-1=-n 时,直接反幂法失败;当是多重特征值时,幂法和反幂法仍有效。,Jacobi法,只适用于实对称方阵可以求出所有特征值和特征向量,矩阵的两个重要的基本性质:(1)如 A 为实对称矩阵,则一定存在正交矩阵 Q,使之相似于一个对角矩阵,而该对角矩阵的对角元正是 A 的特征值。(2)一个矩阵左乘一个正交矩阵或右乘一个正交矩阵,其F范数(Frobenius)不变。,Jacobi法的基本原理,Jacobi法基于的原理是:对一个实对称矩阵 A一定存在一个正交矩阵 R(R-1=RT)使得 RTAR=D,其中 Ddiagd1,d2,dn。我们有 D 的对角元素即为 A 的特征值
3、,对应的 R 的行向量即为相应的特征向量。思路:通过一系列的旋转变换(正交变换)把A中非对角线上的非零元变为零。,下面的矩阵是一个 n 阶正交矩阵:,(p),(q),旋转变换 Upq其元素特点:,如果apq0那么我们可以选取一个,,,(A(1)仍为实对称矩阵)使得,A(1)的元素为:,选取满足,我们就有,Jacobi法的算法,令k1,R(1)I,给定矩阵A(A(1),收敛条件找绝对值最大的计算,sin 和 cos,其中满足计算A(k1)计算R(k+1)如果 则停止,否则返回第 2 步,Jacobi算法的收敛性,定理:设A是实对称矩阵,由Jacobi方法第k次迭代得到的矩阵记为A(k),记,则有
4、,成立。,QR方法,cf:矩阵计算,G.H.Golub&F.Van Loan 袁亚湘等译,第五章(5.1、5.2节),QR方法是计算中小型矩阵特征值和特征向量的有效方法之一;QR方法最重要的一步是对A进行正交分解使得AQR,其中Q为一特殊正交矩阵;理论上,QR方法可以应用于任何矩阵,但对以下几类矩阵效率很高:1)对称三对角矩阵;2)Hessenberg矩阵;3)对称带状矩阵,QR方法的理论依据,定理(实Schur分解定理):设A是一个n阶实方阵,那么存在一个正交矩阵Q使得A相似于,其中对角块为一阶或二阶方阵,每一个一阶对角块对应于A的一个实特征值,每一个二阶对角块的两个特征值是A的一对共轭复特
5、征值。,QR方法的一般形式,由于 产生的矩阵序列Ak中的每一个 矩阵都与A有相同的特征值。要解决的问题是上述算法的工作量和Q的选择!,定理:对任意实方阵A,由QR方法产生的矩阵序列Ak本质上收敛于分块上三角矩阵(对角块以上的元素可能不收敛!),其中对角块为一阶或二阶方阵,每一个一阶对角块对应于A的一个实特征值,每一个二阶对角块的两个特征值是A的一对共轭复特征值。,Q的选择Householder矩阵(镜面映象变换),定义:设为n维单位向量,即T=1;H=I-2T Householder变换(矩阵),(1)Householder矩阵是正交矩阵,(2),(3)记S为与w垂直的平面,则几何上x与y=H
6、x关于平面S对称。事实上,由,几何意义,引理3.1:设有非零向量s和单位向量e,则必存在Householder矩阵H使得Hse,其中是实数且,与平面旋转不同的是,镜面反射变换可成批的消去向量的非零元。,定理:设A是一个n阶实方阵,那么A可分解为一个正交矩阵Q和一个上三角矩阵R的乘积,AQR,减少QR算法的工作量矩阵的拟上三角化,把A变成Hessenberg矩阵(拟上三角矩阵)的目是减少QR方法的计算量;把A变成Hessenberg矩阵(拟上三角矩阵)能够减少QR方法计算量的主要原因是对拟上三角矩阵的QR分解时,Q一定是拟上三角矩阵;RQ(Ak1)的乘积为拟上三角矩阵。,QR方法,定理:对任意实
7、方阵A,由QR方法产生的矩阵序列Ak本质上收敛于分块上三角矩阵(对角块以上的元素可能不收敛!),其中对角块为一阶或二阶方阵,每一个一阶对角块对应于A的一个实特征值,每一个二阶对角块的两个特征值是A的一对共轭复特征值。,QR方法的加速带原点位移的QR 方法,尽管通过Householder矩阵已把矩阵A相似地变成为Hessenberg矩阵从而已减少了QR方法的不少工作量,但上述方法工作量仍太大,其中主要工作量在第二步的QR分解和收敛速度问题!,带原点位移的QR 方法为加速收敛,每次选取位移,作该矩阵序列有如下性质:(1)(2)如 为拟上三角,则 也为拟上三角矩阵(拟上三角矩阵指的是次对角线下的元素
8、为零的矩阵)(3)如取位移 为,则 最后一行非对角元二阶收敛于零(特别对于对称矩阵,能达到三阶收敛),其余次对角元收敛于零的速度会慢一些。,加速技术下的算法:(1)确定计算精度10E-m(2)对矩阵 取加速因子 进行加速(3)判断矩阵 的最后一行非对角元素是否小于要求的精度,如果不小于,继续加速迭代,如已经小于精度,停止计算,并划掉矩阵的最后一行和最后一列,产生一个子矩阵(4)对子矩阵重复进行上面的加速计算,带原点位移的QR 方法的总结:(1)利用Householder矩阵,将矩阵 A 相似于拟上三角矩阵(尤其,对于对称矩阵可以化为三对角矩阵)(2)利用带原点位移的QR 方法构造矩阵序列(3)对矩阵 取加速因子 进行加速(4)判断矩阵 的最后一行非对角元素(由于是拟上三角矩阵,只有一个元素)是否小于要求的精度(5)如已经小于精度,停止计算,并划掉矩阵的最后一行和最后一列,产生一个子矩阵,对子矩阵重复进行上面的加速计算。,QR方法的加速2带双步位移的QR方法,尽管通过Householder矩阵已把矩阵A相似地变成为Hessenberg矩阵从而已减少了QR方法的不少工作量,但上述方法工作量仍太大,其中主要工作量在第二步的QR分解和收敛速度问题!,作业,教材第66页习题8、10、12课外阅读,