设λ1 > λ2 ≥ L ≥ λn
⇒
| λ2 − p | | λn − p | 且 ω = max{ , } = min | λ1 − p | | λ1 − p | 即求极值问题 | λ2 − p | | λn − p | λ2 + λn * min max{ , } p = p | λ1 − p | | λ1 − p | 2
4
例：设
0 D ：z |≤ 2 4 1 3 ≤ λ1 ≤ 5 2 | 1 0 − 1 A= | D3：z + 4 |≤ 2 1 1 − 4 D = diag (1,1, 10 ) 9
D：z − 4 |≤ 1 孤立圆盘 1 |
′ = D −1 AD A
D1′ | z − 4 |≤ 1 ： ′ | D2：z |≤ 19 9 ′| D3：z + 4 |≤ 1.8
(1) | λ1 − p |>| λi − p | (i = 2,3, L, n)
max | λ j − p | (2)
2≤ j ≤ n
| λ1 − p |
| λ2 | < | λ1 |
20
如何选择 p ？ A = (aij ) ∈ R ，其特征值是实数，
n×n
则B = A − pI的主特征值为λ1 − p或λn − p
A v0 uk = max( Ak v0 ) L
16
k
v0 = ∑ α i xi
i =1
n
A v0 = ∑ α i λ x = λ (α1 x1 + ε k )
k
n
λi k ε k = ∑ α i ( ) xi → 0 (k → ∞) λ1 i =2 k k A v0 λ1 (α1 x1 + ε k ) uk = = k k max( A v0 ) max(λ1 (α1 x1 + ε k )) α1 x1 + ε k x1 → = max(α1 x1 + ε k ) max( x1 )
三个孤立圆盘
5
Th4 (Schur定理)
设A ∈ R ，则存在酉阵U使
n×n
r11 r12 L r1n r22 L r2 n H U AU = = R (上三角阵) ( ) O M rnn 其中λi = rii (i = 1,2,L , n)为A的特征值。
k k k k
v 迭代： k = Auk −1
k = 1,2, L
k
15
迭代序列
v1 = Au0
A2 v0 v2 = max( Av0 ) L Ak v0 vk = k −1 max( A v0 )
L
规范化序列
Av0 u1 = max( Av0 ) 2 A v0 u2 = 2 max( A v0 ) （*） L
A 的特征值为 1 1 1 ≤ ≤L≤ ； 对应的特征向量，1 , x2 ,L, xn， x | λ1 | | λ2 | | λn | 对A−1应用幂法即可！
24
反幂法的迭代公式
设u0 = v0 ≠ 0(α n ≠ 0)
vk 迭代： 规范： k = vk / µ k
(1)设A = (aij ) ∈ R
Th10
n× n
有n个线性无关的特征向量，
则由反幂法得到的向量序列{uk }, {vk }满足： xj (1) lim uk = k →∞ max( x j ) 且收敛速度由 1 | λj − p | (2) lim µ k = r= 确定。 k →∞ λj − p min | λi − p | i≠ j 1 p+ → λj
(3){uk }, {vk }由改进幂法得到，则有： x1 且收敛速度由 (1) lim uk = k →∞ max( x1 ) λ2 r =| | 确定。 (2) lim µ k = lim max(vk ) = λ1 λ1 k →∞ k →∞
19
改进r =| λ2 / λ1 | 加速方法 原点平移法 引进矩阵 B = A − pI L A：λ1，λ2， ，λn 特征向量相同 B：λ1 − p，λ2 − p， ，λn − p L
17
i =1 n
k i i
k 1
(**)
A v0 λ (α1 x1 + ε k ) vk = = k −1 k −1 max( A v0 ) max(λ1 (α1 x1 + ε k −1 ))
k
k 1
max(α1 x1 + ε k ) µ k = max(vk ) = λ1 → λ1 (k → ∞) max(α1 x1 + ε k −1 )
−1
Avk = uk −1
k = 1,2, L
综合得到：
25
Th8’ (反幂法)
(1)设A = (aij ) ∈ R
n× n
有n个线性无关的特征向量；
(2)设A的特征值满足： λ1 |≥ L ≥| λn −1 |>| λn |> 0 |
且Axi = λi xi (i = 1,2,L, n)
(3)有上述反幂法得到的向量序列{uk }, {vk }满足： xn (1) lim uk = 且收敛速度由 k →∞ max( xn ) λn 1 r =| | 确定。 (2) lim µ k = λn −1 k →∞ λ
k →∞
则：
λ1
(vk +1 )i = λ1 (2) lim k →∞ (v ) k i
12
若A的主特征值为实的重根 | λ1 |=| λ2 |= L =| λr |>| λr +1 | L ≥| λn | 设A有n个线性无关的特征向量，1 , x2 , L, xn， x
且Axi = λ1 xi (i = 1,2, L, r ) Axi = λi xi (i = r + 1, L, n)
13
非零向量的规范化
u0 = v0 ≠ 0
max(v)表示向量v 绝对值最大的分量
v v →u = max(v)
迭代序列
v1 = Au0
规范化序列
v1 u1 = max(v1 )
L
vk = Auk −1
L
vk uk = max(vk )
14
改进的幂法
设u0 = v0 ≠ 0(α1 ≠ 0)
µ = max(v ) max(v u 规范化： = v / µ
n
26
反幂法的应用 ―求近似特征值的特征向量
对( A − pI ) −1 应用幂法：
vk = ( A − pI ) u k −1 µ k = max(vk ) u k = vk / µ k
−1
27
即 Axi = λi xi (i = 1,2, L, n) ~ (2)取p = λ j (λ j的一个近似)，设( A − pI ) −1 ∃且 | λ j − p |<<| λi − p | (i ≠ j )
任取初始向量 v0 = ∑ α i xi (且α1 , L , α r 不全为零)
n
由幂法有
i =1
r
λi k vk = A v0 = λ (∑ α i xi + ∑ α i ( ) xi ) λ1 i =1 i = r +1 r vk lim k = ∑ α i xi
n
k
k 1
εk
k →∞
λ1
i =1
7
Def
为对称矩阵，∀x ≠ 0，称 ( Ax, x) R( x) = ( x, x ) 为对应向量x的瑞利(Rayleigh )商。
设A ∈ R
n× n
8
Th6 设A ∈ R n×n为对称矩阵，其特征值为
λ1 ≥ λ2 ≥ L ≥ λn , 其对应的特征向量 x1 , x2 ,L, xn
组成规范化正交组，则
( j = 1,2, L, n)
2
Th1 (1)设λ为A的特征值，且Ax = λx，其中x ≠ 0； m (2)设P( x) = r0 + r1 x + L + rm x 为任一m次多项式； m 定义矩阵 P( A) = r0 I + r1 A + L + rm A 则： (1) P(λ )为P( A)的特征值，即P( A) x = P(λ ) x； (2) P(λ )且x为P( A)的特征向量。 Th2 −1 设A与B为相似矩阵，即B = P AP，则 (1) A与B有相同的特征值； (2) 若y是B的特征向量，则Py是A的特征向量。
Axi = λi xi (i = 1,2, L , n)
{ x1 , x2 , L, xn }线性无关
| λ1 |>| λ2 |≥ L ≥| λn |
n×n
10
幂法的其本思想
任取初始向量 v0 ∈ R
n
v1 = Av0 2 v2 = Av1 = A v0
vk +1 = Avk = Ak +1v0
6
Th5 (实Schur分解)
设A ∈ R ，则存在正交矩阵Q使 R11 R12 L R1n R22 L R2 n T Q AQ = O M Rnn 其中对角块Rii (i = 1,2, L , m)为一阶或二阶方阵，
n×n
且每个一阶Rii 是A的实特征值，每个二阶对角 块的两个特征值是A的一对共轭复特征值。
则规范化向量序列uk 的Rayleigh商R(uk )给出λ1较好的 近似 ( Auk , uk ) λ2 2 k R(uk ) = = λ1 + o(( λ1 ) ) (uk , uk )
23
反幂法(逆迭代) 求矩阵按模最小的特征值及对应的特征向量
A∈ R