上海工程技术大学计算方法课件chapter9_2_qr算法.pptVIP

QR方法在特征值计算问题的发展上具有里程碑 意义。在1955年的时候人们还觉得特征值的计算 是十分困扰的问题，到1965年它的计算——基于 QR方法的程序已经完全成熟。直到今天QR方法 仍然是特征值计算的有效方法之一。 一 Householder变换 设A是n阶矩阵且有QR分解A＝QR，这里，Q是 酉矩阵，R是上三角矩阵. 如果A是满秩并规定R 有正对角元，这个分解是惟一的. 这里, 基本收敛的含义指{Ak}的元素中除对角线以 下的元素趋于零外, 可以不收敛于R的元素. ②用Pl,l+1右乘，所得结果也放回矩阵A相应的元素中. * § 7 QR方法 定义1 设 ,且 , 则初等矩阵 称为Householder变换矩阵，也称初等镜面反射矩阵。 Householder矩阵基本性质 性质1 H是对称正交矩阵，即 性质2 设 则 性质2的意义是任意向量 , 在Householder变换作用下, Euclid长度不变. 此外，由 知 由于 是实数, 上式表示向量x-y与向量w平行 性质3 设 ，则由向量 确定的Household矩阵H(w),使得Hx=y。 例2 设 试求H矩阵, 使 直接验证 计算 的算法如下： 二、矩阵的QR分解 定理1 设矩阵 矩阵Q，上三角矩阵R，使A=QR且当要求R的主对角元素均为正数时，则分解式是唯一的。 且非奇异，则一定存在正交 A的非奇异性及Householder变换矩阵的性质知，一定可构造n-1个H矩阵 例3 设矩阵 试作矩阵A=QR分解。 通常采用的方法是先将矩阵相似约化为上 Hessenberg形式的矩阵, 在此基础上应用QR迭 代. 这时, 一个QR迭代步的乘法运算次数只需 O(n２)次. 三、相似约化为上Hessenberg矩阵 对一般n阶矩阵, QR算法的每一个迭代步需要 O(n３)次乘法运算.如果矩阵阶数稍大，这个算法 几乎没有实际的应用价值. 例如：一个5阶的上Hessenberg矩阵具有如下的 形式： 下面介绍QR方法时，都假设矩阵A是一个上 Hessenberg矩阵. 所谓上Hessenberg矩阵是指一个n阶矩阵A,如果当ij+1时，aij=0，称A为上Hessenberg矩阵. 定义1 五、QR算法 QR方法是1961年由作者J.G.F.Francis和 V.N.Kublanovskaya设计的 QR分解是QR算法的基础 (1)QR算法的基本思想 记 A＝A1且有A1＝Q1R1. 将等号右边两个矩阵因子的次序交换，得 A2＝R1Q1 且 即 不难证明: 即 矩阵序列{Ak}有相同的特征值. 因为上Hessenberg矩阵次对角线以下的元素全为0, 因此, 只要证明, 当k→∞时, 由迭 代格式产生的矩阵Ak的次对角元趋向于零就可以了. 记 容易得到 是Ak的一个QR分解 如果A是一个满秩的上Hessenberg矩阵, 可以证明, 经过一个QR迭代步得到的A2＝Q-11A1Q1仍然是上 Hessenberg矩阵. (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 (3) QR算法的迭代过程 1. 一个QR迭代步的计算 ①对l=1,2,…,n-1, 构造n-1个平面旋转矩阵Pl,l+1,使 A1的次对角元全部零化 实现A1的QR分解的计算 这里 2. QR算法的迭代控制 当迭代步数k充分大时, 由迭代格式产生的Ak的次 对角元趋于0. 在实际计算中, 控制迭代次数常用的一种办法 是, 预先给定一个小的正数ε, 在一个迭代步的 计算结束后, 对l=n-1, n-2,…,1, 依次判别次对 角元的绝对值是否满足 或更严格的准则 或不太严格的准则 如果上面三个不等式中有一个成立, 把 看做实际上为零. 例4 设矩阵 试用QR算法求它的特征值。