QR方法求矩阵全部特征值.docx

数 值 分 析

课程设计

QR方法求矩阵全部特征值问题复述

用QR算法求矩阵特征值：

?23

?2

3

4

5

?6

2

1?

?4

4

5

6

7?

7

? ? ? ?

0?（i）(A)??2 3 1? （ii）H??0 3 6 7 8?

0

?

要求：

??1 1 1??

?

?

??0

0 2 8 9?

0 0 1 0??

根据QR算法原理编制求（i）与（ii）中矩阵全部特征值的程序并输出

计算结果（要求误差?10?5）

直接用现有的数学软件求（i），（ii）的全部特征值，并与（1）的结果比较。

问题分析

QR方法是目前公认为计算矩阵全部特征值的最有效的方法。它适用于任一种实矩。QR方法的原理是利用矩阵的正交分解产生一个与矩阵A相似的矩阵迭代序列，这个序列将收敛于一个上三角阵或拟上三角阵，从而求得原矩阵A的全部特征值。

QR是一个迭代算法，每一步迭代都要进行QR分解，再作逆序的矩阵乘法。要是对矩阵A直接用QR方法，计算量太大，效率不高。因此，一个实际的QR方法计算过程包括两个步骤，首先要对矩阵 A用初等相似变换约化为上Hessenberg矩阵，再用QR方法求上Hessenberg矩阵的全部特征值。

示意如下：

?x ? ? x?

???用Householder阵作正交相似变换 ?x ? ?

?

?

?

第一步A?不?需?迭代?，对?A的?每一?列计?算一??次?上Hessenberg阵B?

? ? ? ??

? ?

? x x?

???? x ? x?

?

?

B ?QR

?1 ? ? ??

第二步B?用?QR?变换?产生?迭?代序?列，?迭代?计?算?? k

B

k k?

?RQ ?

2

? x?

???k k k ? ?

?

?

?

n

对B矩阵的约化只需将每列次对角线上的元素约化为0。因此常常用平面旋转阵（Givens变换阵）来进行约化。

一、QR方法原理及收敛性

设A?Rn?n已实现了QR分解，记

A?A?QR

1 1 1

其中Q是正交阵，R是上三角阵。因为QT?Q?1，用Q对A

作正交相似变换有

1 1 1 1 1 1

QTAQ?A

1 1 1 2

可改写为 A ?Q?1AQ?Q?1QRQ?RQ

2 1 1 1 1 1 1 1 1 1

显然A

2

只是A

1

的QR分解因子阵的逆序相乘，而且A

2

与原矩阵A

1

有相同的特征

值。对矩阵A

2

再重复以上过程并继续下去，可以得到一个与原矩阵A有相同特

征值的矩阵序列。其过程如下：

记A?A

1

对A作正交分解 A?QR

1 1 1 1

作矩阵 A?RQ，A～A?A

2 1 1 2 1

对A作正交分解 A

2 2

?QR

2 2

作矩阵 A

3

?RQ，A

2 2 3

～A～A，A～A?A

2 1 3 1

重复以上过程可得一般的形式为

对

对A作正交分解

k

A ?QR

k

k k

(A?A)

1

构成矩阵序列

A ?RQ

k?1

（k=1,2……）

k k

A ～A

k?1

从矩阵A开始得到一个矩阵序列

A,A,A,?,A,?

1 2 3 k

这个矩阵序列中每一个矩阵都与原矩阵A(?A)相似，即都有与A相同的特征值。

1

这个矩阵序列{A}在实质上收敛于依次以?,?

,?,?

为对角元的上三角阵。

k

具体可以表示为

1 2 n

?? x ? x?

?1 ? ? ??

lim

A ?? 2 ?

k ? ? x?

???k?? ? ?

?

?

?

n

其中 a

ii

(k)??

i

(k??)

i?j时a

ij

(k)

?0 (k??)

i?j时a

ij

(k)的极限不一定存在。

二、用正交相似变换约化矩阵为上Hessenberg阵

用Householder变换可以将一个向量指定的某个分量以下的各分量变为0。我们只要求消掉A的次对角线以下的元素，即将A约化为上Hessenberg阵。为了使变换前后矩阵的特征值不变，需要用Householder矩阵对A作相似变换，即用

正交阵同时左乘和右乘A时，原来已变为0的元素不再改变。若设H是

1

Householder矩阵，用它对A的第一列元素的变换示意如下：

x??x??

x

?

?

x

?

?

x

?

x

?

?

?x x?

? ?

H AH ?