数值乘幂法和QR算法

1、9.5 乘幂法9.5.1 求 设A是n阶矩阵，其n个特征值按模从大到小排序为123n任意取定初始向量x001 12 21(0)n nxava va v a1011221 1 122 2nnnn nxAxa Ava Ava Avavavav22222101 11222nnnxAxA xavavav.建立迭代公式 ：1kkxAx因为),3,2(11nii因此，xk可看成是关于特征值1的近似特征向量 有一严重缺点，当|1|1 （或| 1 |0时21 122111211 12211()()|()()|kknnnkkkkknnnb vbvbvzb vbvbv111|kk1 11 1|kbvzbv1 11

2、 1|kbvzbv 当1j+1时，aij=0，称A为上Hessenberg矩阵.例如：一个5阶的上Hessenberg矩阵具有如下的形式： *0*00*000*A下面介绍QR方法时，都假设矩阵A是一个上Hessenberg矩阵. 9.7.3 QR算法 设A是n阶矩阵且有QR分解AQR，(2) 这里，Q是酉矩阵，R是上三角矩阵.如果A是满秩并规定R有正对角元，这个分解是惟一的. 设A是n阶矩阵且有QR分解AQR， 这里，Q是酉矩阵，R是上三角矩阵.如果A是满秩并规定R有正对角元，这个分解是惟一的. QR方法是1961年由作者J.G.F.Francis和V.N.Kublanovskaya设计的QR

3、分解是QR算法的基础一、QR算法的基本思想 记AA且有AQ 1R1.将等号右边两个矩阵因子的次序交换，得ARQ，且 ，(3) 即AA.不难证明:即Ak+1AkA，矩阵序列Ak有相同的特征值. 记12111AQ AQ111111kkkkkkkAQ A QQQ A QQ12kkQQQQ12kkRR RR容易得到 是Ak的一个QR分解kkkAQ R 如果A是一个满秩的上Hessenberg矩阵，可以证明，经过一个QR迭代步得到的A2QA1Q仍然是上Hessenberg矩阵. 因为上Hessenberg矩阵次对角线以下的元素全为0，因此，只要证明，当k时，由迭 代格式(4)产生的矩阵Ak的次对角元趋向

4、于零就可以了. 二、 QR算法的收敛性 定理9.7.3设n阶矩阵A的n个特征值满足|n|0，其相应的n个线性无关特征向量为x1，x2，xn. 记X(x1,x2,xn), Y= X.如果Y存在LU分解，那么，由(4) 式产生的矩阵Ak基本收敛于上三角矩阵R.这里，基本收敛的含义指Ak的元素中除对角线以下的元素趋于零外，可以不收敛于R的元素. 三、 QR算法的迭代过程 1. 一个QR迭代步的计算 对l=1，2，n-1，构造n-1个平面旋转矩阵Pl,l+1,使A1的次对角元全部零化，实现A1的QR分解的计算，这里,1,1,1,11,1,1,2,l ll lllljl ll lllllcsaajlln

5、scaa 1,1,122221,1,lllll ll lllllllllaacsaaaa221,llllraa用Pl,l+1右乘(24)，所得结果也放回矩阵A相应的元素中.,1,1,1,1,1,1(,)(,),1,2,1l ll li li lili ll ll lcsaaaascil2. QR算法的迭代控制 当迭代步数k充分大时，由迭代格式(4)产生的Ak的次对角元趋于0.在 实 际计算中，控制迭代次数常用的一种办法是，预先给定一个小的正数，在一个迭代步的计 算结束后，对l=n-1, n-2,，1，依次判别次对角元的绝对值是否满足 或更严格的准则是 或不太严格的准则是 如果上面三个不等式中有一个成立， 把 看做实际上为零. 1,llaA1,1,1min,llllllaaa1,1,1llllllaaa1,lla9.7.4 带原点位移的算法 由算法收敛性证明可以看出，算法的收敛速度 依赖于矩阵相邻特征值的比 值.为了加快算法的收敛速度，在迭代过程中，对矩阵Ak确定一个原点位移量sk，称Ak-skI为带原点位移量的矩阵，再对Ak-skI应用算法.这时，迭代格式改为 称为带原点位移的QR算法