会达到加速收敛的目的.
如把Aitken加速方法用于例3,则有
k
0 1 2 3 … 10 11 12
k
10 7.2 6.5 … 6.003352 6.001675 6.000837
u(k)
(1,1,1)T (1,0.8,0.1)T (1,0.75,-0.111)T (1,0.730769,-0.188034)T ………………….. (1,0.714405,-0.249579)T (1,0.714346,-0.249790)T (1,0.714316,-0.249895)T
适当选取非奇异对角矩阵D=diag(d1,d2,…,dn),则矩
阵D-1AD与矩阵A有相同的特征值,且对角元素相同. 而矩阵
D-1AD对应的n个圆盘为
n a d ij j Ri | a ii j 1 di j i , i 1,2, , n
v Au max( v (k ) ) k u ( k ) v ( k ) k
(k ) ( k 1)
, k 1,2,3,
n
i 1
可得
u
(k )
A v i 2 n k (0) max( A v ) max( a1 x 1 a i ( ) k x i )
i
k
(0)
a1 x 1 a i ( ) k x i
i2
1
u
所以
(k )
A v i 2 n k (0) max( A v ) max( a1 x 1 a i ( ) k x i )
1 i
k
(0)
a1 x 1 a i ( ) k x i
i
n
i2
( k 1) i
( k 1)
a1 x 1 1 v
k 1 1
(k )
1 v
或取
/v
(k ) i
i 1,2, , n
( ( v nk 1) 1 v1( k 1) v 2k 1) 1 ( ( k ) ( k ) ( k ) ) n v1 v 21 vn
0 1
2 3 4
1 0.25
0.10250 0.042292 0.017451
0 0.2
0.083333 0.034389 0.014190 0.41 0.41260 0.41263 0.41665 0.41267 0.41263
可取0.41263 ,x1(0.017451,0.014190)T .
k 0 1 2 3 … 10 11 12
k 10 7.2 6.5 … 6.003352 6.001675 6.000837
u(k) (1,1,1)T (1,0.8,0.1)T (1,0.75,-0.111)T (1,0.730769,-0.188034)T ………………….. (1,0.714405,-0.249579)T (1,0.714346,-0.249790)T (1,0.714316,-0.249895)T
1
lim u
k
(k )
x1 max( x1 )
max[ a1 x 1 a i ( ) k x i ]
i
其收敛速度由比值|2/1|来确定. 又由于
n
k max( v ) 1
(k )
max[ a1 x 1 a i ( ) k 1 x i ]
i
R(x) (Ax, x) (x, x)
设n阶实对称矩阵A的特征值为12…n ,则有
1 R(x)n
1 max R(x)
x0
, n min R(x)
x0
( A R(x)E)x 2 min ( A E)x 2

可见,如果x是特征向量,则R(x)是对应的特征值. 如果x仅 是一近似特征向量,则R(x)是对应的特征值的一个近似值.
r 1 1 n 1
若a1,a2,…,ar不全为零, 则对充分大的k有
k v ( k ) 1 [a1 x 1 a 2 x 2 a r x r ]
由于a1x1+a2x2+…+arxr 是对应1的特征向量, 若仍记为x1 , 则有: v(k) 1kx1 ,故前面的结论仍然成立. 3. 设1=-2,且 |1=|2|>3 n ,这时,(5.1) 式可写成
§1 乘幂法和反幂法
§1.1 乘幂法
乘幂法是用来求矩阵A按模最大的特征值和相应的特 征向量的方法. 设A是单构矩阵, 即A有n个线性无关的特征向量.
A的n个特征值为
|1 2 n
对应的特征向量为 x1,x2,…xn 线性无关. 我们要求1 和 x1 . 乘幂法的基本思想是取初始向量v(0)Rn,作迭代 v(k+1) =Av(k) =Ak+1v(0) , k=0,1,2,… 产生迭代序列v(k). 由于x1,x2,…xn 线性无关, 从而有 v(0) =a1x1+a2x2+…+anxn 故有 v(k) = Akv(0) =a11kx1+a22kx2+…+annkxn (5.1)
对非零向量v,用max(v)表示v的按绝对值最大的分量,
称向量u=v/max(v)为向量v的规范化向量. 例如, 设向量
v=(2,1,-5,-1)T,则max(v)=-5,u=(-0.4,-0.2,1,0.2)T.可
见规范化向量u总满足‖u‖=1.
乘幂法的规范化计算公式为: 任取初始向量u(0)=v(0) 0,计算
可取 1 6.000837, x1 (1,0.714316,-0.249895)T.
实际上,A的3个特征值分别为1=6,2=3,3=2.
2. 设1=2==r,且 |1>r+1n ,这时,(5.1) 式可写成
k v ( k ) 1 [a1 x1 a 2 x 2 a r x r a r 1 ( ) k x r 1 a n ( ) k x n ]
Ri=aiiri,i=1,2,…,n
则 (1)A的任一特征值至少位于其中一个圆盘内;
(2)在m个圆盘相互连通(而与其余n-m个圆盘互不连通)
的区域内,恰有A的m个特征值(重特征值按重数记).
例1 设矩阵
4 1 0 A 1 0 1 1 1 4
而特征向量 x1 v(k). 乘幂法的收敛速度取决于|2/1|的大小.
例2
求矩阵A的按模最大的特征值
1 4 A 1 5
解
k v1(k)
1 6
1 5
取v(0)=(1,0)T ,计算v(k)=Av(k-1), 结果如下
v2(k) v1(k)/v1(k-1) v2(k)/v2(k-1)
12 13
3.454288 4.631924
(0.539495, 1, 1)T (0.465893, 1, 1)T
2 4
1 12 13 3.454288 4.631924 4,
x1=13u(13)+1u(12)=(4.315961, 8.631924, 8.631924)T,
试讨论A的特征值的分布. 解 由A确定的3个圆盘分别为
R1=-41, R2=2, R3=+42 y 所以
315 -2<22 -63<-2
-6 -4 -2 0 2 3 4 5
x
实际上， 1=4.20308 , 2=-0.442931 , 3=-3.76010
i 2 n
1
所以
i2
1
lim k 1
k
因此,当k充分大时可取:
1 k , x1 u(k) .
如用规范化乘幂法解例2,仍取u(0)=v(0)=(1,0)T,则有 k k u1(k) u2(k) 0 1 0.25 2 0.41 3 4 0.412602 0.412627
~ k
6.266667 ……… 6.000017 6.000003 6.000000
k 0 1 2 3 4 5 6 7 8 9 10 11
k 11 3.553628 4.679204 3.461124 4.635465 3.452655 4.632116 3.454315 4.631929 3.454291 4.631920
u(k) (1,1,2)T (0.454545, 0.909091, (0.537222, 0.972116, (0.465201, 0.994041, (0.539392, 0.998269, (0.465721, 0.999627, (0.539487, 0.999892, (0.465890, 0.999975, (0.539495, 0.999993, (0.465893, 0.999999, (0.539495, 1, 1)T (0.465893, 1, 1)T 1)T 1)T 1)T 1)T 1)T 1)T 1)T 1)T 1)T
1
0
1
0.8
1
36 0.813138
故可取 1 0.412627, x1 (1,0.813138)T.
例3 设
4 14 0 A 5 13 0 1 0 2
用乘幂法求A的按模最大的特征值和相应特征向量. 解 取初值u(0)=v(0)=(1,1,1)T,计算得
1. 设|1>2n , 这时,(5.1)式可写成
k v ( k ) 1 [a1 x1 a 2 ( ) k x 2 a n ( ) k x n ]
2 n 1 1
若a10, 则对充分大的k有
v
因而有
(k )
a1 x 1 , v
k 1
1 vi( k 2) / vi( k )