引例：选择旅游地问题

有人打算外出旅游，他在选择旅游地时，主要考虑的因素有景色、费用、居

住、饮食和旅途五个因素，若这些因素依次用符号C1,C2,C3,C4,C5表示，则他选择旅游地的重要性可以用如下所谓成对比较矩阵

表示，这里，A的任一元素Aij表示Ci与Cj对旅游地重要性之比，其值按Saaty等人提出的1-9尺度确定（见文献[15]，310页），试求出这些因素对他选择旅游地的权重值。 这个问题可以由层次分析法解决，它的层次结构为：

设W1、W2、…、W5依次为景色、费用、居住、饮食及旅游的权重，令向量

，

由Saaty的研究结果，可知权重W是： 成对比较矩阵A的绝对值最大的特征值λmax所对应的归一化特征向量，即W满足：

,

于是本问题归结为求矩阵A的绝对值最大的特征值及其对应的特征向量问题对求特征值机特征向量问题，线性代数已经给出解法，但它不适于计算机处理，且当矩阵阶较大时更是求解困难，本章主要介绍怎样在计算机上解决此问题。

问题的描述与基本概念

求矩阵的特征值及特征向量的问题在实际问题中也经常遇到，如在工程技术中的振动问题和稳定性问题等，在这些问题中解出特征值或特征向量的计算机解法也称为代数特征问题的计算方法。下面介绍一下有关特征值问题的概念。

定义1 设矩阵A∈Rn×n，若存在某个实数或复数λ及非零向量X∈Rn满足AX=λX，则称λ是A的一个特征值，而X称为λ对应的一个特征向量。

定义2 称关于变量λ的行列式

为矩阵A的特征多项式，而FA(λ)=0称为特征方程。

特征多项式FA(λ)是关于λ的一个n次多项式，线性代数中指出：矩阵A的特征值就是其特征多项式FA(λ)的零点，因此，n阶矩阵A共有n个特征值。

求解矩阵A的特征值和特征向量的过程在线性代数中描述为 1）求出特征方程FA(λ)=0的根λ1, λ2，…，λn 2）对每个特征值λi，求出齐次线性方程组

的基础解系做为λi对应的特征向量， i=1,2,?,n

上述揭发理论很严密，但由于将特征多项式FA(λ)化为一个n次多项式很复杂且特征方程对舍入误差很敏感，特别当n较大时，这些问题更突出，由于这些原因，现在用计算机求解代数特征值问题不用线性代数的方法而用迭代加变换的处理方

法，它们具有编程简单，对舍入误差不敏感等优点，本章将介绍具有代表性的这类问题的计算机解法：幂法和反幂法，旋转法及QR方法。

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令，

则Qk也是正交矩阵，A这说明A

(k)

(k+1)

(k+1)

(k+1)

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

T

=QkAQk说明A

(k)

T(k)(k+1)

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

T

(k)

T

(k)

(k+1)

(k+1)

与A有相同

的特征值，n任意，此外，由A=QkRk，则有QkA= QkARk=Rk，故有A=QkRk (应该是RkQk)，

可直接交换Qk与Rk的乘积顺序得到，于是可的如下QR算法。

(k)

①对A作QR分解A=QkRk。

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

(k+1)

(k)

(k)

是否为主对角线为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