特征值问题的计算方法.ppt
第八章 特征值问题的计算方法/*Computational Method of Eigenvalue Problem*/,本章主要介绍矩阵的特征值和特征向量的计算方法。,特征值和特征向量的基本概念与性质,1 基本概念与性质,若 的所有特征值都是半单的，则称 是非亏损的。,相似矩阵有相同的特征值,设,本章QR算法的基本思想：,说明：对称矩阵的特征值总是良态的。,注意：实际问题中矩阵一般都是由计算或实验得到，本身必然存在误差，不妨假设,2 幂法与反幂法/*Power Method and Reversed Power Method*/,幂法是计算一个矩阵的模最大的特征值和对应的特征 向量的一种迭代方法（又称为乘幂法）。,一、幂法的基本思想与算法,假设 是可对角化的，即 存在如下分解：,其中,不妨假设,对于,说明：当k充分大时,的一个近似特征向量为,特征向量可以相差一个倍数,因为向量 中含有未知量，实际不能计算,但我们关心的仅是 的方向，故作如下处理：,令,其中 为 的模最大分量,幂法迭代算法：,设 和 均收敛，由算法知,解：,Step1,Step2,Step3,Step4,特征值及相应的特征向量精确值为:,幂法的收敛性：,证明：,设 有如下Jordan分解：,是属于 的Jordan块构成的块上三角矩阵,是半单的特征值,令,将 和 如下分块：,记,是属于 的一个特征向量,几点说明：,幂法的收敛速度取决于 的大小；,幂法可以计算第二个模最大特征值,常用的方法：降阶方法（收缩技巧）,设已经计算出模最大特征值 及其特征向量,对向量，采用复的Household变换计算酉矩阵,其中 是n-1阶方阵,二、反幂法的基本思想与算法,反幂法是求一个矩阵的模最小的特征值和对应的特征 向量的一种迭代方法（又称为反迭代法）。,设，则,不妨假设 的特征值为,则 的特征值为,反幂法算法：,若 和 均收敛，由幂法知,带位移的反幂法：,实际应用中，反幂法主要用于求特征向量。,且用某种方法已经得到 的特征值 的近似值,对矩阵 采用反幂法迭代格式为：,记,假设 的特征值满足,求解方程组 化为：,带位移的反幂法迭代格式：,设矩阵 存在Doolittle分解：,解：,其中,Step1,反幂法具有一次“迭代性”,Step2,所求近似特征向量为：,3 Jacobi方法,Jacobi法：计算实对称矩阵全部特征值和相应特征向量,基本思想,对,存在正交矩阵，满足,记,则,正交相似变换求法：通过Givens变换来实现,经典Jacobi方法,设,令,非对角“范数”,例如取,记,首先由 确定,其次确定旋转平面,由F-范数的正交不变性,设 经过一次正交相似变换后变为矩阵,注意到,经典Jacobi方法的迭代格式：,证明见教材,经典Jacobi方法的迭代算法,需比较 个元素,习惯上称 次Jacobi迭代为一次“扫描”,循环Jacobi方法,自然顺序：,按照自然顺序的循环Jacobi方法是渐进平方收敛的,4 QR 方 法,基本思想,QR方法的迭代格式,设,令,对矩阵 进行QR分解,再对矩阵 进行QR分解,一、QR基本迭代方法,一般地有：,QR方法的迭代算法：,由迭代格式同时还得到：,记,代入,等式两端同时右乘,记,其中 是 的第一列，是 的相应元素,QR方法的收敛性,证明：,令,则有,且,当m充分大时，存在唯一QR分解：,且,（QR分解）,记 的QR分解为：,为保证上述QR分解中上三角矩阵的对角元为正，令,由QR分解唯一性知：,代入,趋于上三角阵,实QR迭代格式,设,二、实Schur标准形,见文献13,称下述形状的矩阵为上Hessenberg矩阵,三、上Hessenberg化,基本思想和约化过程：,记矩阵,下面采用Householde变换寻找,Step1 选取Householde变换，使得,其中,令,其中,Step2 选取Householde变换，使得,其中,令,令,其中,按照前述方法，经过n-2步后，可以得到：,记，则,称分解式 为矩阵 的上Hessenberg分解,上Hessenberg分解算法（）,然后对上Hessenberg矩阵进行QR迭代,上Hessenberg矩阵的QR迭代算法：,实用的QR迭代算法（仅计算特征值）,四、三对角化（对称矩阵的上Hessenberg化）,设 为对称矩阵，的上Hessenberg分解为,其中 为对称三对角矩阵。,Step1 选取Householde变换，使得,其中,令,其中,主要工作量在于计算,减少运算量,三对角分解算法（）,五、隐式对称的QR迭代方法（仅适用于对称矩阵）,带原点位移的QR迭代格式：,迭代过程中产生的矩阵序列 均为三对角矩阵,的选取方法：,著名的Wilkinson位移,一种简单的取法-,记矩阵,令,取,收敛性见文献4,隐式对称QR迭代的实现方法,设一次对称QR迭代的格式为,例如：n=4时,Wilkinson位移隐式对称分解迭代算法（）,终止法则：的下三角元素均趋于零,注：此算法仅给出了1次的迭代过程.,
