§5-1幂法 、幂法分析 幂法是用来计算实方阵的按模最大的特征值及 相应特征向量的一种迭代法 设n阶实方阵A有n个线性无关的特征向量42l2…ln 相应的特征值分别为4,2…,并按其绝对值的大小排列 1|>12 任给初始向量x。≠0由迭代公式 k+1=Axk(k=0,1,2,…) 得到向量序列{xk} 所以 1+C,l2+…+c.l
§5-1 幂法 一、幂法分析 幂法是用来计算实方阵的按模最大的特征值及 相应特征向量的一种迭代法 , , , , u1 u2 un , , , , 1 2 n 设n阶实方阵A有n个线性无关的特征向量 相应的特征值分别为 并按其绝对值的大小排列 1 2 n 即 0 x0 ( 0,1,2, ) xk+1 = Axk k = { }k x 任给初始向量 由迭代公式 得到向量序列 u u n un x0 =1 1 +2 2 ++ 所以
于是 xk Axk-I A x 41+Q22l2+…+Qn2m C11+C 由假设/411(=23,…m所以只要a1≠0就有 C11 k→>∞o 这说明序列收敛于A的与相对应的特征向量, 当k充分大时 即x为4的特征向量的近似值 令(xk)表示x的第个分量,则
. 即xk为1的特征向量的近似值 令(xk ) i表示xk的第i个分量，则 ( ( ) ( ) ) 1 2 1 2 1 1 1 2 1 1 1 2 2 2 2 0 2 1 n n k n k k n k n n k k k k k k u u u u u u x Ax A x A x = + + + = + + + = − = − = = 于是 1 1 1 lim u x k k k = → 1( 2,3, , ), 由假设 j 1 j = n 所以只要 1 0 就有 k k x 1 1 1 1 u1 x k k 这说明序列 收敛于A的与 相对应的特征向量， 当k充分大时
x4(x4+a2(2)n2+…+an()4n) k+1 (a11+a2(n2)ul2+…+ 所以 k X 即两相邻迭代向量分量的比值收敛于A 这种由已知非零向量x0及矩阵A的乘幂A构造向量序列 {xk}以计算A的按模最大特征值及相应特征向量的方法称为 乘幂法,简称为幂法 通常把迭代向量归一化,即把xk的最大分量化为1. 因此通常采用的幂法迭代公式为:
n i n k n k k n i n k n k k k i k i u u u u u u x x ( ( ) ( ) ) ( ( ) ( ) ) ( ) ( ) 1 2 1 2 1 1 1 2 1 1 2 1 1 2 1 1 2 1 1 1 + + + + + + = + + + + i k i k i k x x = + → ( ) ( ) 1 lim 所以 即两相邻迭代向量分量的比值收敛于 1 0 x k 这种由已知非零向量 及矩阵A的乘幂 A 构造向量序列 { }k x 以计算A的按模最大特征值及相应特征向量的方法称为 乘幂法，简称为幂法. 通常把迭代向量归一化，即把 的最大分量化为1. 因此通常采用的幂法迭代公式为： k x
mk=max(xk) Vk=. in (K k+1 其中,m2=max(x)表示x中绝对值最大的分量 由此可得: xk Ayk-l Ay n,m k1k-1 mkmk-1‘mh1mkmk-1…mm7o max(Axo)=max( A yo)mo=max( A" Ayo)mo=max("xmo max( a" y)m, mo max(Ayk=1)m1-1…mm max(x, m,1. m,m mkmk-I.mmo
其中， max( )表示 中绝对值最大的分量. k k k m = x x = = = = + ( 0,1, ) max( ) x 1 Ay k y x m m x k k k k k k k 1 1 0 0 1 1 0 1 2 2 1 m m m m A x m m m A y m m A y m Ay m x y k k k k k k k k k k k k k k − − − − − = = = = = = 由此可得： 1 1 0 1 1 0 1 1 1 0 1 1 0 1 1 0 1 0 0 1 0 0 0 max( ) max( ) max( ) max( ) max( ) max( ) max( ) m m m m x m m m Ay m m m A y m m A x A y m A Ay m A x m k k k k k k k k k k k − − − − − − − = = = = = = = = 而
所以 (+a2(ym2+…+a(xy1) y max( a xo) max( k (a, u,+a2( ()2+…+an()4n) (au4+0a2+…+an()n) max(a,u+a2(2)"u2+.+a(m)un) 从而 lim yk k→》∞ max(u,) 上式说明归一化向量序列{yk}收敛于按模最大的特征值 所对应的特征向量因此,当k充分大时,yk就是特征向量 1的近似值
max( ( ) ( ) ) ( ( ) ( ) ) max( ( ( ) ( ) )) ( ( ) ( ) ) max( ) 1 2 1 2 1 1 2 1 2 1 2 1 1 2 1 2 1 2 1 1 1 2 1 2 1 2 1 1 1 2 0 0 n n k n k n n k n k n n k n k k n n k n k k k k u u u u u u u u u u u u A x A x y + + + + + + = + + + + + + = = 所以 max( ) 1 1 lim u u yk k = → 从而 上式说明归一化向量序列 收敛于按模最大的特征值 所对应的特征向量.因此，当k充分大时， 就是特征向量 的近似值. { }k y 1 u k y
同理 A max(A"xo) (a4+a2()2+…+a1()vn) max(m(a,u,+a l21+…+an()n) 所以 A max(a,,+a2()u2++a( )un max( x max(a,u,+a2 ll+…+a, 故 lim max(xk)=M k 因此,当k充分大时,max(xA)就是按模最大的特征值A1的 近似值,即mk≈A1
max( ( ( ) ( ) )) ( ( ) ( ) ) max( ) 1 1 2 1 1 2 1 1 2 1 1 1 2 1 2 1 1 1 2 0 1 0 1 n n k n k k n n k n k k k k k k u u u u u u A x A x x Ay − − − − − + + + + + + = = = 同理 max( ( ) ( ) ) max( ( ) ( ) ) max( ) 1 1 2 1 1 2 1 1 2 1 2 1 2 1 1 1 2 n n k n k n n k n k k u u u u u u x − − + + + + + + = 所以 1 max( ) lim = → k k x 故 max( ) k x mk 1 因此，当k充分大时， 就是按模最大的特征值 的 近似值，即 . 1
二、幂法算法 目标求A=(an)∈R的按模最大特征值及相应的特征向量 输入A的阶数n;A的元素an1≤i,≤m,初始向量x 允许误差;最大迭代次数N 输出近似特征值λ和特征向量x或方法失败的信息 步骤s1置k=1,A=0 s2确定P,使x=maxx l≤i<n 置 s3置y=x/m s4当k≤N时,作S41~S47 s41置x=Ay, S42确定p,使x=maxx s43置m
二、幂法算法 n n A aij R = ( ) ; . ,1 , ; ; N A n A a i j n x i j 允许误差 最大迭代次数 的阶数 ； 的元素 初始向量 近似特征值和特征向量x或方法失败的信息. , 41 ~ 47. . . , . 1, 0. max 1 k N S S y x m m x p x x k p i i n p 当 时 作 置 置 确定 使 置 = = = = = ; , ; ; max 1 p i i n p m x p x x x Ay = = = 置 确定 使 置 目标 求 的按模最大特征值及相应的特征向量 输入 输出 步骤 S1 S2 S3 S4 S41 S42 S43
s44若m=0,则输出“特征向量”“y”“4有特征值0,选择新的向量x 并重新开始”停机 s45置y=x/m; s46若m-(<E,则输出(my停机 s47置k=k+1; s5输出“ Maximum num ber of iterations exceeded”;停机
1; . , ( , ); . ; ; . 0, : ; 0, k k m m m y y x m m y A x = + = − = = 置 若 则输出 停机 置 并重新开始”停机 S44 若 则输出“特征向量”“ ”“ 有特征值 选择新的向量 S45 S46 S47 S5 输出“Maximum number of iterations exceeded”;停机
作业: 教材P107习题2
作业： 教材P107 习题 2
