南京大学计算机科学与技术系：《数值计算方法》课程教学资源（PPT课件）第7章 矩阵特征值和特征向量的数值解法 7.1 幂法 7.2 Jacobi法 7.3 QR算法（1/2）

第7章矩阵特征值和特征向量的数值解法 设矩阵A∈R,如果存在数λ∈C及非零向量x∈C"满足方程 Ax∈λ,则称λ为矩阵A的一个特征值,x称为矩阵A的相应于特 征值λ的特征向量。为简单起见,下称λ,x为矩阵A的一特征对 特征值的计算,直接从特征方程()=det(I-A)=0出发会遇到很 大困难,当n稍大一些,行列式展开本身就很不容易,随后是高次代数 方程求解。因此,矩阵特征值的求解,主要是数值解法

第 7 章 矩阵特征值和特征向量的数值解法 设矩阵 n n A R   ，如果存在数C 及非零向量 n x C 满足方程 Axx，则称 为矩阵 A 的一个特征值，x 称为矩阵 A 的相应于特 征值 的特征向量。为简单起见，下称 ，x 为矩阵 A 的一特征对。 特征值的计算，直接从特征方程() = det(I − A) = 0 出发会遇到很 大困难，当 n 稍大一些，行列式展开本身就很不容易，随后是高次代数 方程求解。因此，矩阵特征值的求解，主要是数值解法

7.1幂法 711幂法原理及实用幂法 幂法主要用于求矩阵按模最大的特征值和相应的特征向量。设矩阵A的 n个特征值A(i=1,2,,n)满足: 入1|2图3…2n1(71.1) 相应的n个特征向量x(i=1,2,…,nm)线性无关。上述假设表明,入为非零单 实根,x1为实特征向量

7.1 幂法 7.1.1 幂法原理及实用幂法 幂法主要用于求矩阵按模最大的特征值和相应的特征向量。设矩阵 A 的 n 个特征值 ( 1,2,..., ) i i = n 满足： | | | | | | ... | | 1  2  3   n （7.1.1） 相应的 n 个特征向量 ( 1,2,..., ) xi i = n 线性无关。上述假设表明，1 为非零单 实根， 1 x 为实特征向量

7.1幂法 幂法基本原理是:任取非零实向量),做迭代 l46)=Al-1)=A4uO(k=1,2,)(7.1.2) (k+1) M=lm (k) (71.3 这里)表示向量)的第j个分量。 事实上,由于x(=1,2…,m)线性无关,故可构成R中一组基,于是 有0=∑ax,由式(712)可得

7.1 幂法 幂法基本原理是：任取非零实向量 (0) u ，做迭代 ( 1,2,...) (7.1.2) ( ) ( 1) (0) = = = − u Au A u k k k k 则 lim (7.1.3) ( ) ( 1) 1 k j k j k u u + →  = 这里 (k ) j u 表示向量 (k ) u 的第 j 个分量。 事实上，由于 ( 1,2,..., ) xi i = n 线性无关，故可构成 n R 中一组基，于是 有 = = n i i i u x 1 (0)  ，由式（7.1.2）可得

7.1幂法 =ASax=2a4x=∑a4x1=2[ax1+∑a(,)x1(7.14) 主要用于求矩阵按模最大的特征值和相应的特征向量。设矩阵A的 n个特征值A(i=1,2,…,n)满足: 2图3P…2n(7.1.1) 由于<1(=2,3,,n,当a1≠0.(x)≠0时有 k+1 “[ax1+∑a,() k→B()=lmn lim [a1x+∑a(")x

7.1 幂法 [ ( ) ] (7.1.4) 2 1 1 1 1 1 1 1 ( )     = = = = = = = = + n i i k i i k n i n i n i i k i i i k i i i k k u A x A x x x x          主要用于求矩阵按模最大的特征值和相应的特征向量。设矩阵 A 的 n 个特征值 ( 1,2,..., ) i i = n 满足： | | | | | | ... | | 1  2  3   n （7.1.1） 由于 1(i 2,3,...,n), 1 i  =   当1  0,(x1 ) j  0时有 1 2 1 1 1 1 1 2 1 1 1 1 1 ( ) ( 1) [ ( ) ] [ ( ) ] lim lim            = + + =   = + = + → + → i j k n i i i k i j k n i i i k k k j k j k x x x x u u

7.1幂法 由式(714)还可知,当k充分大时有 x2 a, 这表明是特征向量x,的一常数倍,即n()近似于特征向量x。 基于式(712)和式(713)幂法的主要缺点是:当A1|1或A1k1 时,由式(714)可知,l()会发生上溢或下溢,因此不实用。克服这一缺点 的常用方法是迭代每一步对向量4)规范化。引入函数max(u)),它表示取 向量u6)中按模最大的分量,例如,u()=(2,5,4),则max(()=5,这样 (k) m分的最大分量为,即完成了规范化

7.1 幂法 由式（7.1.4）还可知，当 k 充分大时有 1 1 1 ( ) u x k k    这表明 (k ) u 是特征向量 1 x 的一常数倍，即 (k ) u 近似于特征向量 1 x 。 基于式（7.1.2）和式（7.1.3）幂法的主要缺点是：当| 1 |1或| 1 |1 时，由式（7.1.4）可知， (k ) u 会发生上溢或下溢，因此不实用。克服这一缺点 的常用方法是迭代每一步对向量 (k ) u 规范化。引入函数 max（ (k ) u ），它表示取 向 量 (k ) u 中按模最大的分量，例如， (k ) u =(2,-5,4)T ,则 max( (k ) u )=-5,这 样 max( ) ( ) ( ) k k u u 的最大分量为 1，即完成了规范化

7.1幂法 由式(714)还可知,当k充分大时有 a,x 这表明l4是特征向量x1的一常数倍,即n)近似于特征向量x。 基于式(712)和式(71.3)幂法的主要缺点是:当1|>1或A1k1 时,由式(7.14)可知,u()会发生上溢或下溢,因此不实用。克服这一缺点 的常用方法是迭代每一步对向量l()规范化。引入函数max(l)),它表示取 向量n)中按模最大的分量,例如,l()=(2-5,4),则max(l4)=5,这样 (k) mW)的最大分量为1,即完成了规范化

7.1 幂法 由式（7.1.4）还可知，当 k 充分大时有 1 1 1 ( ) u x k k    这表明 (k ) u 是特征向量 1 x 的一常数倍，即 (k ) u 近似于特征向量 1 x 。 基于式（7.1.2）和式（7.1.3）幂法的主要缺点是：当| 1 |1或| 1 |1 时，由式（7.1.4）可知， (k ) u 会发生上溢或下溢，因此不实用。克服这一缺点 的常用方法是迭代每一步对向量 (k ) u 规范化。引入函数 max（ (k ) u ），它表示取 向 量 (k ) u 中按模最大的分量，例如， (k ) u =(2,-5,4)T ,则 max( (k ) u )=-5,这 样 max( ) ( ) ( ) k k u u 的最大分量为 1，即完成了规范化

7.1幂法 由于)中最大分量为1,即max(v()=1,故 (7.1.6) (A' 由式(714)有 有x+∑()x lim lim mx(ax+∑(") x)max(x)

7.1 幂法 由于 (k ) v 中最大分量为 1，即 max（ (k ) v ）=1，故 (7.1.6) max( ) (0) (0) ( ) A u A u v k k k = 由式（7.1.4）有 max( ) max( ( ) ) [ ( ) ] lim lim 1 1 2 1 i 1 1 1 2 1 i 1 1 1 ( ) x x x x x x v n i i k k n i i k k k k k = + + =   = = → →        

7.1幂法 由式(7.15)和式(7.16)有 m =max(u( k) max(Au)) max( au max(Ak+u(o) 于是 (x+∑()x mxax1+∑(") x)

7.1 幂法 由式（7.1.5）和式（7.1.6）有 max( ) max( ) max( ) max( ) ! (0) (0) ( ) ( 1) A u A u m u Au k k k k k + − = = = 于是 1 2 1 1 1 1 1 1 2 1 1 1 1 max( ( ) ) [ ( ) ] lim lim          = + + =   = − − = → → n i i k i k n i i k i k k k k x x x x m

7.1幂法 实用幂法迭代格式如下: 任取初始向量n0)≠0,作迭代 m,= max( u (k=0,2,)(71.5) Av lm mk =n max(x,) 事实上,由式(71.5)知 Aku(

7.1 幂法 实用幂法迭代格式如下： 任取初始向量 0 (0) u  ,作迭代 ( 0,1,2,...) (7.1.5) max( ) ( 1) ( ) ( ) ( ) ( ) =        = = = + k u Av m u v m u k k k k k k k 则 1 lim =  → k k m max( ) lim 1 ( ) 1 x x v k k = → 事实上，由式（7.1.5）知 = = k i i k k m A u v 0 (0) ( )

算法711实用幂法 (1)输入:an(j=12…m),1(=12,…),E 2)k=l; mo=max(u ); (3)V1=1/m2(i=1,2,…,m);

算法 7.1.1 实用幂法 (1) 输入：a (i, j = 1,2,n),u (i = 1,2,),; i j i (2) 1; max( ); 1 0 i i n k m u   = = (3) ( 1,2, , ); vi = ui m0 i =  n (4) ( 1,2, , ); 1 u a v i n n j i =  i j j =  =