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