矩阵特征值的计算优秀PPT.ppt

《矩阵特征值的计算优秀PPT.ppt》由会员分享，可在线阅读，更多相关《矩阵特征值的计算优秀PPT.ppt（36页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、矩阵特征值的计算矩阵特征值的计算1现在学习的是第1页，共36页主要内容n 正交变换正交变换n Sturm序列与二分法序列与二分法nQR 算法算法l Givens 变换变换l Householder 变换变换l 基本算法基本算法l 具有移位的具有移位的QR算法算法2现在学习的是第2页，共36页实对称阵特征值的计算 通过正交变换，将实对称矩阵约化为三对角阵，利用Sturm定理隔离特征值，最后用二分法求出所需特征值。3现在学习的是第3页，共36页 Givens变换变换4现在学习的是第4页，共36页引例令 0 05现在学习的是第5页，共36页Givens 变换定义定义：称矩阵称矩阵为为 Givens

2、变换变换，或，或 旋转变换旋转变换。ijij6现在学习的是第6页，共36页Givens 变换l 性质性质(1)只有四个元素与单位矩阵不同只有四个元素与单位矩阵不同(2)正交：正交：(3)如果如果A是对称阵，则是对称阵，则 也是对称阵也是对称阵(4)用用 G 左乘一个矩阵时，只改变该矩阵中两行的值左乘一个矩阵时，只改变该矩阵中两行的值(5)用用 G 右乘一个矩阵时，只改变该矩阵中两列的值右乘一个矩阵时，只改变该矩阵中两列的值7现在学习的是第7页，共36页Givens 变换定理定理：设设 x=(x1,.,xi,.,xj,.,xn)T，且，且 xi,xj 不全为零，则存在不全为零，则存在 Given

3、s 变换变换 G=G(i,j,)，使得，使得 8现在学习的是第8页，共36页Givens 变换l 计算步骤计算步骤(1)构造构造 矩阵。一般地，对第矩阵。一般地，对第i行行Givens变换，构造变换，构造 ，其中，其中 (2)Givens变换：变换：。经过变换可以把。经过变换可以把 上的元素化为上的元素化为0。通过通过 次变换，可以约化为三对角阵。次变换，可以约化为三对角阵。9现在学习的是第9页，共36页例 1 应用Givens方法把矩阵约化为三对角阵。解：设 ，令 ，得 ，则Givens 变换10现在学习的是第10页，共36页Givens 变换由 ，令 ，得 则同理，得11现在学习的是第11

4、页，共36页 Householder变换变换12现在学习的是第12页，共36页Householder 变换 1985年，A.S.Householder提出用初等Hermite阵代替Givens阵将对称阵约化为三对角阵，只需要（n-2）次变换（Givens方法需要（1/2(n-1)(n-2)）次变换）就能达到简化目的。13现在学习的是第13页，共36页Householder 变换定义定义：设设 且且 ，称矩阵，称矩阵为为Householder变换变换。14现在学习的是第14页，共36页Householder 变换l 性质性质(1)对称：对称：(2)正交：正交：(3)对合：对合：(4)保模：保模：

5、(5)15现在学习的是第15页，共36页Householder 变换定理定理：设设 x,y Rn,x y 且且|x|2=|y|2，则存在，则存在 n 阶阶 Householder 变换变换 H，使得，使得 y=Hx 16现在学习的是第16页，共36页Householder 变换定理定理：对任意的非零向量对任意的非零向量 x Rn，存在，存在 Householder 变换变换 H，使得使得 Hx=e1 其中其中 =sgn(x1)|x|2,e1=(1,0,.,0)T，l 的选取是为了的选取是为了防止在实际计算中防止在实际计算中 与与 x1 互相抵消互相抵消l 若若 x1=0,则取则取 =|x|21

6、7现在学习的是第17页，共36页Householder 变换l 计算步骤计算步骤(1)构造构造 矩阵。矩阵。，其中，其中 为为k维向量维向量(2)Householder变换。变换。经过变换可以把经过变换可以把 上的元素化为上的元素化为0。其中其中 通过（通过（n-2）次变换，可以约化为三对角阵。）次变换，可以约化为三对角阵。18现在学习的是第18页，共36页Householder 变换例 2 对例1中的矩阵，用Householder 变换约化为三对角阵。解：，得向量 ，因此 ,，得19现在学习的是第19页，共36页Householder 变换 当矩阵比较稠密时，具有更高的效率20现在学习的是第

7、20页，共36页 Sturm序列与二分法序列与二分法21现在学习的是第21页，共36页Sturm序列与二分法 设C是n阶对称阵A通过前面两种方法之一，约化为的三对角阵。22现在学习的是第22页，共36页Sturm序列与二分法其特征多项式多项式序列 是一个Sturm序列。应用Sturm定理，可以求出在 内实根的个数和隔离出C的特征值区间，原则上可以用二分法求出全部或者部分特征值。规定23现在学习的是第23页，共36页Sturm序列与二分法例3 考察矩阵C的特征值分布 解：C的特征多项式 对应的各阶主子式：构成一个Sterm序列。24现在学习的是第24页，共36页Sturm序列与二分法考察当 时，

8、多项式序列的変号数 +-+-+4 +0 -0 +2 +0 +0由表可知，在 内有两个特征值，在（-2,0）内有两个特征值，在 没有特征值。然后用二分法可以求得所需精度的特征值。25现在学习的是第25页，共36页一般矩阵特征值的计算 对任意非奇异矩阵，用QR算法迭代，它将收敛于一个上三角阵，主对角线上的元素近似为矩阵的特征值。26现在学习的是第26页，共36页 QR算法算法27现在学习的是第27页，共36页QR算法定理：定理：设设 矩阵矩阵A是是n 阶阶 非奇异非奇异实矩阵实矩阵，则存在正交分解，则存在正交分解 A=QR其中其中 Q 是正交矩阵是正交矩阵，R 是非奇异上三角矩阵是非奇异上三角矩阵

9、。若限定若限定 R 的对角线元素为正数，则此分解唯一的对角线元素为正数，则此分解唯一。28现在学习的是第28页，共36页QR算法设设(j=1,.,n)(1)构造构造 H1 使得使得 H1 a1=1e1，令，令(2)构造构造 使得使得 ，令，令l QR 分解分解29现在学习的是第29页，共36页QR算法以此类推，经过以此类推，经过 n-1 步，可得步，可得 Householder 矩阵矩阵 H1,H2,.,Hn-1，使得使得令令 ，即得，即得30现在学习的是第30页，共36页QR算法例4 用 Householder 变换计算 的 QR 分解。解：设 ，则31现在学习的是第31页，共36页QR算法

10、同理，构造32现在学习的是第32页，共36页QR算法l基本算法基本算法 设设 为为n阶实矩阵，对阶实矩阵，对A进行进行QR分解，分解，,再令再令 即完成一次迭代。即完成一次迭代。一般地迭代式，一般地迭代式，由此得到矩阵序列由此得到矩阵序列 。收敛于上三角矩阵（或分块收敛于上三角矩阵（或分块 上三角矩阵），从而可以求出上三角矩阵），从而可以求出A的全部特征值与特征向量。的全部特征值与特征向量。其中其中k=1,2,3,.每一次迭代计算量较大，常常先把实矩阵每一次迭代计算量较大，常常先把实矩阵A用用Househouder法约化为拟上三角阵。法约化为拟上三角阵。33现在学习的是第33页，共36页QR算

11、法定理：定理：设设 ，进行，进行QR分解并迭代分解并迭代记记 ,则有则有（1）相似于相似于A；（2）的的QR分解为分解为 。34现在学习的是第34页，共36页QR算法l具有移位的具有移位的QR算法算法 设设A为为n阶实矩阵，令阶实矩阵，令 ，取适当的数，取适当的数 对矩阵作对矩阵作QR分解分解令令 ，这样完成一次迭代。，这样完成一次迭代。一般地，一般地，可以证明可以证明 与与 相似，相似，中所有的矩阵具有相同的特征值集。中所有的矩阵具有相同的特征值集。35现在学习的是第35页，共36页QR算法（1）设设A经相似变换后已成为拟上三角阵，选移经相似变换后已成为拟上三角阵，选移 ，则，则 很快趋近于很快趋近于0；（2）如果如果A是对称阵，经相似变换约化为三对角阵，选位移是对称阵，经相似变换约化为三对角阵，选位移 为矩为矩阵最右下角的二阶主子式。阵最右下角的二阶主子式。l 的选取的选取 是是 最右下角元素。最右下角元素。36现在学习的是第36页，共36页