数值分析第8章——矩阵特征值问题计算课件

1、第八章 矩阵特征值问题计算,对n 阶方阵A求数 和非零向量x ,使其满足Ax=x 这样的 值称为矩阵A的特征值，非零向量 x 称为矩阵A的与特征值 相对应的一个特征向量。,1,PPT学习交流,定义1 设矩阵A, BR nn，若有可逆阵P，使 则称A与B相似。,定理1 若矩阵A, BR nn且相似，则 （1）A与B的特征值完全相同； （2）若x是B的特征向量，则Px便为A的特征向量。,8.1 预备知识,2,PPT学习交流,定理2： 设AR nn具有完全的特征向量系，即存在n个线性无关,其中i为A的特征值，P的各列为相应于i的特征向量。,的特征向量构成Rn的一组基底，则经相似变换可化A为,对角阵，

2、即有可逆阵P，使,3,PPT学习交流,定理3 ：AR nn，1, , n为A的特征值，则,（2）A的行列式值等于全体特征值之积，即,（1）A的迹数等于特征值之和，即,4,PPT学习交流,定理4,5,PPT学习交流,定理5 设AR nn为对称矩阵，其特征值12n，则,（1）对任意AR n，x0，,（2）,（3）,6,PPT学习交流,定理6 （Gerschgorin圆盘定理） 设AR nn，则,表示以aii为中心，以 半径为的复平面上的n个圆盘。,（2）如果矩阵A的m个圆盘组成的并集S（连通的）与其余,（1）A的每一个特征值必属于下述某个圆盘之中，,n m个圆盘不连接，则S内恰包含m个A的特征值。

3、,7,PPT学习交流,8,PPT学习交流,9,PPT学习交流,10,PPT学习交流,11,PPT学习交流,12,PPT学习交流,定理7,13,PPT学习交流,14,PPT学习交流,一 幂法,1 基本思想,任取非零向量 v0 , 则可唯一表示为,设n 阶矩阵A 的特征值 , 满足 ,且其对应有n个线性无关的特 征向量 x1 , x2, , xn ，即,8.2 幂法和反幂法,15,PPT学习交流,则,16,PPT学习交流,其中,由假设条件,所以当k充分大时，有,从而,所以,17,PPT学习交流,即为矩阵 A 的对应特征值 1 的近似特征向量。,且,18,PPT学习交流,则对任意非零初始向量,，下面

4、的式子成立,定理,19,PPT学习交流,迭代公式 (1)实质上是由矩阵A的乘幂 Ak与非零向量 v0 相乘来构造向量序列 xk , 从而计算主特征值及其对应的主特征向量,故称这种方法为幂法。,20,PPT学习交流,则对任意非零初始向量,定理,按照下述方法构造的向量序列,则有,21,PPT学习交流,2. 幂法实用计算公式,22,PPT学习交流,解取 v0=(0,0,1)T , 则,23,PPT学习交流,直到k=8 时的计算结果见下表,从而,24,PPT学习交流,二、幂法的加速,1、原点平移法,如果是矩阵 A 的特征值,则对任意的实数p, 矩阵 A-pE 的特征值为 -p,且 A 与 A-pE 的

5、特征向量相同.据此, 如果要计算 A 的主特征值 1 , 只要选择合适的数 p,使 1-p 为矩阵 A-pE 的主特征值,且,那么,对矩阵 A-pE 应用幂法求其主特征值 1-p ,收敛速度将会加快.这种通过求 A-pE 的主特征值和特征向量,进而得到A的主特征值和特征向量的方法叫原点平移法。,25,PPT学习交流,且使,显然,当 2 - p = - (n- p ),即 P= ( 2+ n ) 2 时,上式取最小值;如果希望计算 n , 类似的讨论可知应选取 p= (1 + n-1)2 。,则对任意实数p,矩阵 A-pE 的主特征值为1-p或 n-p , 要求 1 , 则选 p 使,26,PP

6、T学习交流,例2 用原点平移加速法求例1中矩阵A的主特征值与其对应的特征向量。 解 取p=-2.5, 做平移变换B=A-pE，则,对B应用幂法，仍取 x0=(0,0,1)T , 则,27,PPT学习交流,迭代5步的计算结果见下表,0.5, 1, 0.7500,13.5000,6.7500, 13.5000, 10.1250,5,0.5, 1, 0.7500,13.5007,6.7503, 13.5007, 10.1256,4,0.5, 1, 0.7507,13.5179,6.76, 13.5179, 10.1406,3,0.5, 1, 0.7545,14,7, 14, 10.5625,2,0.

7、5, 1, 0.875,4,2, 4, 3.5,1,k,可得到B的主特征值 113.5000 特征向量 v1 (0.5 ,1.0, 0.7500)T 因此,A的主特征值为 1 = 1 +p 11.0000, 特征向量仍为v1 =(0.5,1,0.7500)T。,28,PPT学习交流,29,PPT学习交流,30,PPT学习交流,设A为n阶实对称矩阵，称,为向量 x 的瑞利商，其中 ( x, x)= xT x 为内积。不难证明，对实对称矩阵A，如果其特征值满足,2、瑞利商加速,由幂法公式生成的 xk 的瑞利商满足,由此可见，R(xk) 比 mk 更快的收敛于1 。,31,PPT学习交流,幂法的瑞利

8、商加速迭代公式为,其中A为n阶实对称矩阵。 对给定的误差限 ，当 | mk mk-1 | 时，取,32,PPT学习交流,三、反幂法,反幂法是用于求非奇异矩阵A的按模最小的特征值和对应特征向量的方法. 而结合原点平移法的反幂法则可以求矩阵A的任何一个具有先验了解的特征值和对应的特征向量。,设矩阵A非奇异,其特征值i (i=1,2,n) ,满足,其相应的特征向量 x1 , x2, , xn 线性无关,则 A-1 的特征值为1/ i ，对应的特征向量仍为 xi (i=1,2, ,n).,33,PPT学习交流,此时,A-1 的特征值满足,因此,对 A-1 应用幂法,可求出其主特征值 1/ n 和特征向

9、量 xn uk ,从而求得A的按模最小特征值 n 1/ 和对应的特征向量 xn uk ， 这种方法称为反幂法。,34,PPT学习交流,为了避免求 A-1 ,可通过解线性方程组A vk= uk-1 得到yk ，采用LU分解,即先对 A 进行LU分解 A=LU , 此时反幂法的迭代公式为,35,PPT学习交流,对给定的误差 ，当 | | 时，得,显然，反幂法的收敛速度取决于比值 ，比值越小，收敛越快。,例3 用反幂法求矩阵 的对应于特征值 的特征向量,36,PPT学习交流,解 取 解方程组,得,解方程组,得,37,PPT学习交流,与 的对应分向量大体上成正比, 所以对应于 的特征向量为,38,PP

10、T学习交流,QR 算法也是一种迭代算法,是目前计算任意实的非奇异矩阵全部特征值问题的最有效的方法之一.该方法的基础是构造矩阵序列 ,并对它进行QR 分解.,由线性代数知识知道,若A 为非奇异方阵,则A 可以分解为正交矩阵Q 与三角形矩阵R 的乘积,即A=QR ,而且当R的对角线元素符号取定时,分解式是唯一的.,8.4 QR算法,39,PPT学习交流,若A为奇异方阵,则零为A的特征值.任取一数 p 不是A 的特征值,则 A-pI 为非奇异方阵.只要求出 A-pI 的特征值,就很容易求出A的特征值, 所以假设A 为非奇异方阵,并不防碍讨论的一般性.,设A 为非奇异方阵,令 , 对 进行QR 分解,

11、 即把 分解为正交矩阵 与上三角形矩阵 的乘积,作矩阵 继续对 进行QR分解,并定义,40,PPT学习交流,一般地,递推公式为,QR 算法就是利用矩阵的QR 分解,按上述递推公 式构造矩阵序列 .只要A 为非奇异方阵,则由QR算 法就完全确定 这个矩阵序列 具有如下性质.,性质1 所有都相似,它们具有相同的特征值.,41,PPT学习交流,证明,因为,若令 , 则 为正交阵,且有 因此 与A 相似,他们具有相同的 特征值.,42,PPT学习交流,性质2 的 QR 分解式为 其中,证明 用归纳法. 显然当 k=1 时,有,假设 有分解式,于是,43,PPT学习交流,因为 , 所以,定理 1 如果

12、收敛于非奇异矩阵 , 为上三 角形矩阵,则 存在并且是上三角形矩阵.,因为 都是正交阵, 所以 也是正交阵,同 样 也是上三角阵, 从而 的QR分解式为,44,PPT学习交流,证明 因为 收敛,故下面极限存在,由于 为上三角形矩阵,所以 为上三 角形矩阵.,又因为 所以 存在, 并且是上三角形矩阵.,45,PPT学习交流,定理 2 ( QR 算法的收敛性) 设A 为n 阶实矩阵.,(1) A的特征值满足:,(2) 其中 且设 有三角分解式 ( L 的单 位下三角阵,U 为上三角阵).,则由 QR 算法得到的矩阵序列 本质上收敛于 上三角形矩阵.即 满足,46,PPT学习交流,的极限不一定存在.

13、,证明 因为 矩阵 决定 的收敛 性.又 我们利用 求 , 然后讨 论 的收敛性.,由定理条件 得,47,PPT学习交流,其中 的 ( i , j ) 元素 为,于是,由假设,当 i j 时, 故,设方阵X 的QR 的分解式为,由,48,PPT学习交流,由 知, 对充分大的 k , 非奇异, 它应有唯一的 QR 分解式 ,并且,于是,但上三角阵 的对角线元素不一定大于零.,为此,引入对角阵,以便保证 的对交线元素都是正数,49,PPT学习交流,从而得到 的QR 分解式,由 的 QR 分解式的唯一性得到,从而,由于 所以,50,PPT学习交流,从而,其中,于是,因为 为上三角阵, 为对角阵,且元

14、素为1 或-1, 所以,51,PPT学习交流,的极限不一定存在,52,PPT学习交流,例 1 用 QR 算法求矩阵 特征值. A的特征值为-1,4,1+2i .,53,PPT学习交流,解 令 用施密特正交化过程将 分解为,54,PPT学习交流,将 与 逆序相乘, 求出,用 代替A 重复上面过程,计算11次得,55,PPT学习交流,由 不难看出, 矩阵A 的一个特征值是4 ,另一个特 征值是-1 ,其它两个特征值是方程,的根.求得为,56,PPT学习交流,上Hessenberg化,57,PPT学习交流,58,PPT学习交流,59,PPT学习交流,60,PPT学习交流,61,PPT学习交流,62,

15、PPT学习交流,63,PPT学习交流,用正交变换化对称矩阵为对称三对角阵,64,PPT学习交流,带原点位移的QR算法,65,PPT学习交流,66,PPT学习交流,用单步QR方法计算上Hessenberg特征值,67,PPT学习交流,68,PPT学习交流,69,PPT学习交流,70,PPT学习交流,71,PPT学习交流,72,PPT学习交流,73,PPT学习交流,74,PPT学习交流,75,PPT学习交流,76,PPT学习交流,77,PPT学习交流,78,PPT学习交流,79,PPT学习交流,80,PPT学习交流,81,PPT学习交流,82,PPT学习交流,83,PPT学习交流,84,PPT学习

16、交流,85,PPT学习交流,86,PPT学习交流,隐式QR算法,87,PPT学习交流,88,PPT学习交流,89,PPT学习交流,90,PPT学习交流,91,PPT学习交流,92,PPT学习交流,定理6,设A为n阶实对称矩阵，则必存在正交矩阵,P使得,其中,为A的n个特征值。,证,设A的互不相同的特征值为,根据性质1和性质3知，,对应于特征值,93,PPT学习交流,把它们标准正交化，,特征向量组，,特征向量共有n个，,并有,其中,为A的n个特征值。,这样的,特征值的特征向量是正交的，,向量两两正交，以它们为列向量构成正交矩阵P，,又由性质2知，,A的属于不同,故这n个单位特征,94,PPT学习

17、交流,由定理6可知，实对称矩阵的对角化问题，实质上 是求正交矩阵P的问题，计算P的步骤如下：,（1）,（2）,求出齐次线性方,标准正交的特征向量，,求出实对称矩阵A的全部特征值,对于各个不同的特征值,对基础解系,这个向量组所含向量,95,PPT学习交流,（3）,（4）,则P为正交矩阵且使得,为对角阵，对角线上的元素为,相应特征向量的特征值。,取,96,PPT学习交流,例13,解,得特征值,97,PPT学习交流,98,PPT学习交流,7.2 对称QR方法,对称矩阵的三对角化,99,PPT学习交流,带原点位移的QR迭代,100,PPT学习交流,101,PPT学习交流,隐式QR迭代,102,PPT学

18、习交流,103,PPT学习交流,定义Jacobi方法是用来计算实对称矩阵A 的全部特征值及其相应特征向量的一种变换方法.,Jacobi方法的基本思想是通过一系列的平面旋转矩阵构成的正交变换将对称矩阵逐步化为对角阵,从而得到A的全部特征值及其相应的特征向量.,定理 (1)如果n 阶方阵A满足 则称A为正交阵.,7.3 Jacobi方法,104,PPT学习交流,(2) 设A 是n 阶实对称矩阵,则A 的特征值都是 实数,并且有互相正交的n 个特征向量.,(3) 相似矩阵具有相同的特征值.,(4) 设A 是n 阶实对称矩阵,P 为n 阶正交阵,则 B=PAP 也是对称矩阵.,(5) n 阶正交矩阵的

19、乘积是正交矩阵。,设A 是n 阶实对称矩阵,则必有正交矩阵P ， 使,105,PPT学习交流,由(6) 可知,对于任意的 阶实对称矩阵A , 只要能求得一个 正交阵P ,使,则可得到A 的全部特征值及其相应的特征向量,这就是雅克比方法的理论基础.,其中 的对角线元素是A 的n 个特征值，正交矩阵P 的第i 列是A 的对应于特征值 的特征向量。,下面我们详细介绍雅可比方法。首先引进 中 的平面旋转变换.变换,106,PPT学习交流,记为 ,其中,107,PPT学习交流,X= ,Y = ,称为 平面内的平面旋转矩阵.容易得到如 下性质:,则称 x= 为 中 平面内的一个旋转变换,(2) 的主对角线

20、元素中除第i 个与第j 个元素为 外,其它元素均为1;非对角元素中除第i 行第 j 列元素为 ,第j 行第i 列元素为 外,其它元素均为零.,(1) 为正交矩阵,108,PPT学习交流,(3) 只改变A的第i行第j 行元素, AP只改变A 的 第i 列第j 列元素,所以 只改变A 的第i 行, 第j 行,第i 列,第j 列元素.,设A= 为n 阶实对称矩阵, 为一非对角线元素.令 则 为实对 称矩阵,且 与A 有同的特征值. 通过直接计算知,109,PPT学习交流,当取 满足关系式 时, 且,由于在正交相似变换下, 矩阵元素的平方和不变,所以若用D(A) 表示矩阵A的对角线元素的平方和,用S(

21、A) 表示A 的非对角元素平方和,则由(11)式得,110,PPT学习交流, 的非对角元素平方和A的非对角元素平方,且将事先选定的非对角元素消去了,这说明用 对A 作正交相似变换化为 后, 的 对角线元素平方和比A 的对角元素平方和增加了,和减少了,111,PPT学习交流,因此,只要我们逐次地用这种变换,就可以使得 矩阵A 的非对角线元素平方和趋于零,也即使得矩阵A 逐步化为对角阵.,这里需要说明一点:并不是对矩阵A的每一对非对角线非零元素进行一次这样的变换就能得到对角阵.因为在用变换消去 的时候,只有第 i 行,第 j 行,第 i 列,第 j 列元素在变化,如果 或 为零,经变换后又往往不是零了.,112,PPT学习交流,雅克比方法就是逐步对矩阵A 进行正交相似变换,消去非对角线上的非零元素,直到将A的非对角线元素化为接近与零为止,从而求得A的去全特征值,把逐次的正交相似变换矩阵乘起来,便是所要求的特征向量.,Jacobi的计算步骤归纳如下:,第一步 在矩阵A 的非对角元素中选取一个非零 元素 .一般来说,取绝对值最大的非对 角线元素.,113,PPT学习交流,第二步 由公式 求出 , 从而得 平面旋转矩阵,第三步 , 的元