矩阵特征值的计算.ppt

1,第七章 矩阵特征值的计算,数值分析, 正交变换与QR 算法,王伟,2,主要内容,正交变换,Sturm序列与二分法 QR 算法,Givens 变换 Householder 变换,基本算法 具有移位的QR算法,3,实对称阵特征值的计算,通过正交变换，将实对称矩阵约化为三对角阵，利用Sturm定理隔离特征值，最后用二分法求出所需特征值。,4,Givens变换,5,引例,6,Givens 变换,定义：称矩阵,为 Givens 变换，或 旋转变换。,7,Givens 变换,性质,(1) 只有四个元素与单位矩阵不同 (2) 正交： (3) 如果A是对称阵，则 也是对称阵 (4) 用 G 左乘一个矩阵时，只改变该矩阵中两行的值 (5) 用 G 右乘一个矩阵时，只改变该矩阵中两列的值,8,Givens 变换,定理：设 x = (x1, ., xi , . , xj , . , xn)T，且 xi , xj 不全为零，则存在 Givens 变换 G = G (i, j, )，使得,9,Givens 变换,计算步骤,(1) 构造 矩阵。一般地，对第i行Givens变换，构造 ，其中 (2) Givens变换： 。经过变换可以把 上的元素化为0。 通过 次变换，可以约化为三对角阵。,10,例 1 应用Givens方法把矩阵 约化为三对角阵。 解：设 ，令 ， 得 ，则,Givens 变换,11,Givens 变换,由 ，令 ，得 则 同理，得,12,Householder变换,13,Householder 变换,1985年，A.S.Householder提出用初等Hermite阵代替Givens阵将对称阵约化为三对角阵，只需要（n-2）次变换（Givens方法需要（1/2(n-1)(n-2)）次变换）就能达到简化目的。,14,Householder 变换,定义：设 且 ，称矩阵,为Householder变换。,15,Householder 变换,性质,(1) 对称： (2) 正交： (3) 对合： (4) 保模： (5),16,Householder 变换,定理：设 x, y Rn, x y 且 |x|2 = |y|2，则存在 n 阶 Householder 变换 H，使得 y = Hx,17,Householder 变换,定理：对任意的非零向量 x Rn，存在 Householder 变换 H，使得 Hx = e1 其中 = sgn(x1)|x|2, e1= (1, 0, ., 0)T ，, 的选取是为了防止在实际计算中 与 x1 互相抵消 若 x1=0, 则取 = |x|2,18,Householder 变换,计算步骤,(1) 构造 矩阵。 ，其中 为k维向量 (2) Householder变换。 经过变换可以把 上的元素化为0。 其中,通过（n-2）次变换，可以约化为三对角阵。,19,Householder 变换,例 2 对例1中的矩阵，用Householder 变换约化为三对角阵。 解： ，得向量 ，因此 , ，得,20,Householder 变换,当矩阵比较稠密时，具有更高的效率,21,Sturm序列与二分法,22,Sturm序列与二分法,设C是n阶对称阵A通过前面两种方法之一，约化为的三对角阵。,23,Sturm序列与二分法,其特征多项式,多项式序列 是一个Sturm序列。应用Sturm定理，可以求出在 内实根的个数和隔离出C的特征值区间，原则上可以用二分法求出全部或者部分特征值。 规定,24,Sturm序列与二分法,例3 考察矩阵C的特征值分布 解：C的特征多项式 对应的各阶主子式： 构成一个Sterm序列。,25,Sturm序列与二分法,考察当 时，多项式序列的変号数,由表可知，在 内有两个特征值，在（-2,0）内有两个特征值，在 没有特征值。然后用二分法可以求得所需精度的特征值。,26,一般矩阵特征值的计算,对任意非奇异矩阵，用QR算法迭代，它将收敛于一个上三角阵，主对角线上的元素近似为矩阵的特征值。,27,QR算法,28,QR算法,定理：设 矩阵A是n 阶 非奇异实矩阵，则存在正交分解 A = QR 其中 Q 是正交矩阵 ，R 是非奇异上三角矩阵 。 若限定 R 的对角线元素为正数，则此分解唯一 。,29,QR算法,设,( j = 1, . , n ),(1) 构造 H1 使得 H1 a1 = 1e1 ，令,(2) 构造 使得 ，令,QR 分解,30,QR算法,以此类推，经过 n-1 步，可得 Householder 矩阵 H1, H2, . , Hn-1 ，使得,令 ，即得,31,QR算法,例4 用 Householder 变换计算 的 QR 分解。,解：设 ，,则,32,QR算法,同理，构造,33,QR算法,基本算法,设 为n阶实矩阵，对A进行QR分解， ,再令 即完成一次迭代。 一般地迭代式， 由此得到矩阵序列 。 收敛于上三角矩阵（或分块 上三角矩阵），从而可以求出A的全部特征值与特征向量。 其中k=1,2,3,.,每一次迭代计算量较大，常常先把实矩阵A用Househouder法约化为拟上三角阵。,34,QR算法,定理： 设 ，进行QR分解并迭代 记 , 则有 （1） 相似于A； （2） 的QR分解为 。,35,QR算法,具有移位的QR算法,设A为n阶实矩阵，令 ，取适当的数 对矩阵作QR分解 令 ，这样完成一次迭代。 一般地，,可以证明 与 相