矩阵特征值的计算精选PPT.ppt
矩阵特征值的计算矩阵特征值的计算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 变换变换，或，或 旋转变换旋转变换。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 不全为零，则存不全为零，则存在在 Givens 变换变换 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页，此课件共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)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|217第17页，此课件共36页哦Householder 变换l 计算步骤计算步骤(1)构造构造 矩阵。矩阵。，其中，其中 为为k维向量维向量(2)Householder变换。变换。经过变换可以把经过变换可以把 上的元素化为上的元素化为0。其中其中 通过（通过（n-2）次变换，可以约化为三对角阵。）次变换，可以约化为三对角阵。18第18页，此课件共36页哦Householder 变换例 2 对例1中的矩阵，用Householder 变换约化为三对角阵。解：，得向量 ，因此 ,，得19第19页，此课件共36页哦Householder 变换 当矩阵比较稠密时，具有更高的效率20第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序列与二分法考察当 时，多项式序列的変号数 +-+-+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 是非奇异上三角矩阵是非奇异上三角矩阵。若限定若限定 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算法同理，构造32第32页，此课件共36页哦QR算法l基本算法基本算法 设设 为为n阶实矩阵，对阶实矩阵，对A进行进行QR分解，分解，,再令再令 即完成一次迭代。即完成一次迭代。一般地迭代式，一般地迭代式，由此得到矩阵序列由此得到矩阵序列 。收敛于上三角矩阵（或分块收敛于上三角矩阵（或分块 上三角矩阵），从而可以求出上三角矩阵），从而可以求出A的全部特征值与特征向量。的全部特征值与特征向量。其中其中k=1,2,3,.每一次迭代计算量较大，常常先把实矩阵每一次迭代计算量较大，常常先把实矩阵A用用Househouder法约化为拟上三角阵。法约化为拟上三角阵。33第33页，此课件共36页哦QR算法定理：定理：设设 ，进行，进行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页哦
