矩阵特征值的计算

矩阵特征值的计算1第1页，共36页，2023年，2月20日，星期二主要内容正交变换

Sturm序列与二分法QR算法

Givens

变换Householder

变换基本算法具有移位的QR算法2第2页，共36页，2023年，2月20日，星期二实对称阵特征值的计算通过正交变换，将实对称矩阵约化为三对角阵，利用Sturm定理隔离特征值，最后用二分法求出所需特征值。3第3页，共36页，2023年，2月20日，星期二

Givens变换4第4页，共36页，2023年，2月20日，星期二引例令005第5页，共36页，2023年，2月20日，星期二Givens变换定义：称矩阵为Givens变换，或旋转变换。ijij6第6页，共36页，2023年，2月20日，星期二Givens变换性质(1)

只有四个元素与单位矩阵不同(2)正交：(3)如果A是对称阵，则也是对称阵(4)用G

左乘一个矩阵时，只改变该矩阵中两行的值(5)用G

右乘一个矩阵时，只改变该矩阵中两列的值7第7页，共36页，2023年，2月20日，星期二Givens变换定理：设x=(x1,...,xi

,...,xj,...,xn)T，且xi

,xj不全为零，则存在Givens变换G=G(i,j,)，使得

8第8页，共36页，2023年，2月20日，星期二Givens变换计算步骤(1)构造矩阵。一般地，对第i行Givens变换，构造

，其中(2)Givens变换：。经过变换可以把上的元素化为0。通过次变换，可以约化为三对角阵。9第9页，共36页，2023年，2月20日，星期二例1应用Givens方法把矩阵约化为三对角阵。解：设，令，得，则Givens变换10第10页，共36页，2023年，2月20日，星期二Givens变换由，令，得则同理，得11第11页，共36页，2023年，2月20日，星期二

Householder变换12第12页，共36页，2023年，2月20日，星期二Householder变换1985年，A.S.Householder提出用初等Hermite阵代替Givens阵将对称阵约化为三对角阵，只需要（n-2）次变换（Givens方法需要（1/2(n-1)(n-2)）次变换）就能达到简化目的。13第13页，共36页，2023年，2月20日，星期二Householder变换定义：设且，称矩阵为Householder变换。14第14页，共36页，2023年，2月20日，星期二Householder变换性质(1)

对称：(2)正交：(3)对合：(4)保模：(5)15第15页，共36页，2023年，2月20日，星期二Householder变换定理：设

x,yRn,x

y

且||x||2=||y||2，则存在n阶Householder变换H，使得

y=Hx

16第16页，共36页，2023年，2月20日，星期二Householder变换定理：对任意的非零向量xRn，存在Householder变换H，使得

Hx=e1

其中=sgn(x1)||x||2,e1=(1,0,...,0)T

，的选取是为了防止在实际计算中与x1互相抵消若x1=0,则取=||x||217第17页，共36页，2023年，2月20日，星期二Householder变换计算步骤(1)构造矩阵。，其中为k维向量(2)Householder变换。

经过变换可以把上的元素化为0。其中

通过（n-2）次变换，可以约化为三对角阵。18第18页，共36页，2023年，2月20日，星期二Householder变换例2对例1中的矩阵，用Householder变换约化为三对角阵。解：，得向量，因此,，得19第19页，共36页，2023年，2月20日，星期二Householder变换当矩阵比较稠密时，具有更高的效率20第20页，共36页，2023年，2月20日，星期二

Sturm序列与二分法21第21页，共36页，2023年，2月20日，星期二Sturm序列与二分法

设C是n阶对称阵A通过前面两种方法之一，约化为的三对角阵。22第22页，共36页，2023年，2月20日，星期二Sturm序列与二分法其特征多项式多项式序列是一个Sturm序列。应用Sturm定理，可以求出在内实根的个数和隔离出C的特征值区间，原则上可以用二分法求出全部或者部分特征值。规定23第23页，共36页，2023年，2月20日，星期二Sturm序列与二分法例3考察矩阵C的特征值分布

解：C的特征多项式

对应的各阶主子式：

构成一个Sterm序列。24第24页，共36页，2023年，2月20日，星期二Sturm序列与二分法考察当时，多项式序列的変号数+-+-+4+0-0+2+++++0+++++0由表可知，在内有两个特征值，在（-2,0）内有两个特征值，在没有特征值。然后用二分法可以求得所需精度的特征值。25第25页，共36页，2023年，2月20日，星期二一般矩阵特征值的计算对任意非奇异矩阵，用QR算法迭代，它将收敛于一个上三角阵，主对角线上的元素近似为矩阵的特征值。26第26页，共36页，2023年，2月20日，星期二

QR算法27第27页，共36页，2023年，2月20日，星期二QR算法定理：设

矩阵A是n阶

非奇异实矩阵，则存在正交分解

A=QR其中Q是正交矩阵，R是非奇异上三角矩阵。若限定R的对角线元素为正数，则此分解唯一。28第28页，共36页，2023年，2月20日，星期二QR算法设

(j=1,...,n)(1)构造H1使得H1a1=1e1

，令(2)构造

使得

，令

QR分解29第29页，共36页，2023年，2月20日，星期二QR算法以此类推，经过n-1步，可得Householder矩阵H1,H2,...,Hn-1，使得令，即得30第30页，共36页，2023年，2月20日，星期二QR算法例4用Householder变换计算的QR分解。解：设，则31第31页，共36页，2023年，2月20日，星期二QR算法同理，构造32第32页，共36页，2023年，2月20日，星期二QR算法基本算法设为n阶实矩阵，对A进行QR分解，,再令即完成一次迭代。一般地迭代式，由此得到矩阵序列。收敛于上三角矩阵（或分块上三角矩阵），从而可以求出A的全部特征值与特征向量。其中k=1,2,3,...每一次迭代计算量较大，常常先把实矩阵A用Househouder法约化为拟上三角阵。33第33页，共36页，2023年，2月20日，星期二QR算法定理：设，进行QR分解并迭代记,则有（1）相似于A；（2）的QR分解为。34第34页，共36页，2023年，2月20日，星期二QR算法具有移位的QR算法设A为n阶实矩阵，令，取适当的数对矩阵作QR分解令，这样完成一次