内容发布更新时间 : 2024/12/24 20:12:42星期一 下面是文章的全部内容请认真阅读。

QR方法

QR方法是求任意矩阵的全部特征值的一种有效方法，它是JACOBI方法的推广。

? 基本思想

利用矩阵的QR分解，通过逆序相乘产生对原矩阵的一系列正交相似变换，使其变 化为一个近似的上三角矩阵来求全部特征值。这里QR分解是指将矩阵化为一个正 交矩阵Q和一个上三角矩阵左乘的形式。

构造原理

实对称矩阵可用正交相似变换将其化为对角形矩阵，但对非对称矩阵，一般用正交相 似变换化不成对角矩阵，但SCHUR分解定理给我们一个有关这方面的结果。 定理3。（实SCHUR分解定理）设矩阵A∈R，则存在一个正交矩阵Q∈R，使

n*n

n*n

QAQ=

T

其中每个Bii是1*1或2*2的小矩阵，若Bii为1*1的，其元素就是A的实特征值，否则Bii的特征值是A一对共轭复特征值。

此定理的证明可参阅文献[3]。定理3指出了求矩阵A的全部特征值也可用正交相似变换的方法来做，正交相似变换的结果虽然不是对角矩阵，而是分块三角形矩阵，但它同样能很方便地求出全部特征值，有关一般矩阵的正交相似变换，我们不加证明地给出一个结论。

定理4。设非奇异矩阵A∈R，且有n个不同的特征值，记A=A。如果对整数k，有矩阵A的 QR分解为A=QkRk，则令A

(k)

(k)

(k+1)n*n

(1)

(k)

=QkAQk，当k→∞时有A本质上收敛于分块上三角形矩阵，这里

T(k)(k)

“本质上收敛”指A的主对角线上的元素或子块有确定的极限，其它元素或子块不管是否有极限。

此定理给出了求解一般矩阵全部特征值的方法。由定理3，A令，

(k+1)

=(Q1Q2....Qk)A(Q1Q2....Qk)，

T

则Qk也是正交矩阵，A

(k+1)

=QkAQk说明A

(k)

T(k)(k+1)

也是原矩阵A的正交相似变换，从而A

T

(k)

T

(k)

(k+1)

(k+1)

与A有相同

(k+1)

的特征值，n任意，此外，由A=QkRk，则有QkA= QkARk=Rk，故有A接交换Qk与Rk的乘积顺序得到，于是可的如下QR算法。 ①对A作QR分解A=QkRk。

②逆序相乘A的分解矩阵，A=RkQk。 ③判别A

(k+1)

(k)

(k)

(k)

(k)

=QkRk，这说明A可直

是否为主对角线为1*1或2*2的子块形式的分块上三角形矩阵，若是对角线上各子块

k，转①。

的特征值为所求特征值，终止，否则k+1

分析

从QR 算法的构造过程可以看到算法的主要计算量出现在QR分解上，如果直接对矩阵A 用QR方法求全部特征值，那麽涉及的计算量是很大的，因此应该先对A作预处理。应用

中常先对 做正交相似变换将其化为上Hessenberg矩阵H，然后再对H采用QR方法，可以大大减少计算量，这里Hessenberg矩阵也称为拟三角矩阵，它的非零元素比三角矩阵多了 一条次对角线，其形式为：

上Hessenberg矩阵 下Hessenberg矩阵

实际上，Hessenberg矩阵虽然不是三角矩阵，但它很接近三角矩阵，由于其每列只比三角矩阵 多一个非零元，故选用旋转变换做QR分解更简单些，因为对上Hessenberg矩阵H的第1列

到第n-1列，依次做旋转变换使H的主对角线下的元素都变为零，则H化为上三角矩阵R了，用矩阵描述就是

记

为J也是正交矩阵，

-1

，则J为正交矩阵，解出H，可得H=JR，因

-1

于是得H的QR分解容易验证按这个方法做对H做QR分解，然后使用QR算法则构造的

迭代序列都是上Hessenberg矩阵中进行，于是整个QR算法都在上Hessenberg矩阵中进行，这当然使QR算法的计算量大量减少。下面我们来

具体讨论一下一般矩阵相似约化到Hessenberg矩阵的方法，为说明此问题，引入镜面反射 阵概念。

定义4。设非零向量V=(V1,V2,.....,Vn)∈R，则称矩阵P=I－βVV为Hessenberg矩阵，式中

Tn-1T

。

易验证Householder矩阵P是对称，正交和对合的。

从定义可知Householder矩阵主要由一个非零向量V确定，若将V看某一过原点的超平面 π的法向量，则有任给一个非零向量α，经Householder矩阵P作用后，记为Pα，则α与Pα是关与超平面π对称，因此也称Householder矩阵是镜面反射阵。Householder矩阵可改变任一向量的方向，这可从下面定理得出。 定理5。任取非零向量X=(X1,X2,.....,Xn)∈R，可以选择一个Householder矩阵P，使Px=－бｅ1式中e1=(1,0,......,0)

T

T

n

是R的单位向量，

n

证： 作u=x+бｅ1，用u做一个Householder矩阵P=I－βuu,

-1T

因为

而

证毕

定理中β=б(б+x1)，为避免б+x1出现两个相似数相减引起有效数字损失，实用中常选