ν
= Aν
=
α iλi k xi ∑
i =1
v
α 1 ≠ 0, α 2 ≠ 0
v v v k = λ 1 α 1 x 1 + λ k α 2 x 2 + ... + λ k α n x n 2 n v v v k k k = λ 1 α 1 x 1 + ( − 1 ) λ 1 α 2 x 2 + ... + λ k α n x n n
ν
v(k ) = Aν v ( k −1) λ v = λ ∑ α i i xi λ1 i =1
n k k 1
越小越好。 希望 | λ2 / λ1 | 越小越好。
不妨设 λ1 > λ2 ≥ … ≥ λn ，且 | λ2 | > | λn |。 。 决定收敛的速度， 决定收敛的速度，特别 λn 是 | λλ2/ λ1 |λ1 2
O p = ( λ2 + λn ) / 2
令 B = A − pI ，则有 | λI−A | = | λI−(B+pI) | = | (λ−p)I−B | − − − 思 p 是假定的 p 究竟是多少 | λ p | | λ | 是假定的, 究竟是多少? 所以求B的特征根收 ⇒ λA − p = λB 。而 2 − < 2 ，所以求 的特征根收 路 | λ1 − p | | λ1 | 敛快。 敛快。 p 的选择或凭借于经验 或通过多次试算而得 的选择或凭借于经验, 或通过多次试算而得.
v
v
v
v v v v ( k ) , v ( k +1) , v ( k +2 ) 间近似地成立下述线性关系 不难验证: 不难验证 v v v v ( k +2 ) − (λ1 + λ 2 1λ 2 v ( k ) ≈ 0
可任取两组分量,并解下列方程组得 为求得λ1 和λ2,可任取两组分量 并解下列方程组得 q: 可任取两组分量 并解下列方程组得p,
v v v v ( k ) , v ( k +1) , v ( k +2 )
若是,就可求出 的模最大的特征值和相应的特征向量 若是 就可求出A的模最大的特征值和相应的特征向量 就可求出 的模最大的特征值和相应的特征向量.
实际计算时,由于其他情况的存在 由于其他情况的存在, 注: 实际计算时 由于其他情况的存在 上述三种情况均 不出现时, 需考虑其他算法. 不出现时 需考虑其他算法 因此乘幂法在某种意义上 来说只能用来试算. 来说只能用来试算 原点平移法
同号
所以
v (ν ( k + 2 ) ) i 2 ≈ λ1 v (k ) (ν ) i
v v v ( k +1) + λ1v ( k ) . 可以证明， 的特征向量为： 可以证明，对应于λ1的A的特征向量为： 的特征向量为
v v v v Av ( k +1) + λ1v ( k ) ) = v ( k +2) + λ1v ( k + 1) 事实上， 事实上， v v v 2v ≈ λ1 v ( k ) + λ1v ( k + 1) = λ1 (v ( k +1) + λ1v ( k ) )
类似地， 的特征向量为： 类似地，对应于λ2的A的特征向量为： 的特征向量为
v v v ( k +1) − λ1v ( k ) .
2° |λ1| =|λ2| > |λ3| ≥ … ≥ |λn| ° 此时, 也可能 此时 λ1 和λ2有可能是共轭复数 (也可能λ1=λ2, 也可能是 情况1° 情况 °λ1 =-λ2) ; |λ1|>|λ3|. n Q:如何找到表 如何找到表 v (0) v 不妨假设 ν = ∑ α i x i , α 1 ≠ 0, α 2 ≠ 0 示λ1(λ2)的较 的较 i =1 n 好的关系呢? 好的关系呢 v ( k + 1) v (k ) k v
1
A的绝对值最小的特征根 的绝对值最小的特征根
−1
= A ν in every step? Q: How must we compute ν v ( k +1) v ( k ) A: Solve a linear system Aν = ν with A factorized.
v(k )
若知道某一特征根 λi 的大致位置 p , 即对任意 j ≠ i 存在， 并且如果 有| λi − p | << | λj − p | ,并且如果 (A − pI)−1存在，则 思 可以用反幂法求 − pI)−1的主特征根 1/(λi − p ) ，收 路 可以用反幂法求(A 敛将非常快。 敛将非常快。 (2) 利用反幂法将特征根的近似值精确化 的近似值, 若λj’是A的特征值λj 的近似值 且设λj是A的特征方程的单 是 的 的 并满足: 根,并满足 | λj − λj’ | < | λi − λj | , i≠j. 并满足 的按模最小特征值 ⇒ λj − λj’是A- λj’I的按模最小特征值 是 的按模最小特征值.
10.2 Jacobi方法
给定实对称矩阵 ，计算步骤如下： 给定实对称矩阵A，计算步骤如下： 实对称矩阵 (1) 找出A中非对角元素绝对值最大的元素 ij，确定i和j; 找出 中非对角元素绝对值最大的元素a 确定 和 中非对角元素绝对值最大的元素 (2) 用下列公式确定 θ和sinθ： 用下列公式确定cos (3) 对A作正交变换 作正交变换 A1 = R T AR 当aii= ajj, aij＞0时, 取θ=π/4; 时 π i j 当aii= aij, aij＜0时, 取 θ=-π/4; 时 π 1 当aii≠aij时, O
v v v
v (ν ( k ) )i v ( k −1) ≈ λ1 (ν )i
ν
= Aν
v
………
k k ν ( k ) ≈ λ1 α 1 x 1 , ν ( k − 1 ) ≈ λ1 − 1α 1 x 1
v
充分大时， 当k 充分大时，有
规范化 为避免大数出现，需将迭代向量规范化，即每一步先保 为避免大数出现，需将迭代向量规范化， v v || v ||∞ = max | ν i | 。 再代入下一步迭代。 证 ||ν || = 1 ，再代入下一步迭代。一般用 1≤ i ≤ n v || ν ( k ) || ∞ = | ν i( k ) | 则有： 记： 则有：
R(i, j ) =
(4) 以A1代替 ，重复 代替A，重复(1),(2),(3)，直至 ij|＜ε ，直至|a ＜ (i≠j)时为止．此时 k中对角线元素即为所求 时为止． 时为止 此时A 对角线元素即为所求 的特征值，逐步变换矩阵R 的特征值，逐步变换矩阵 l,R2,…,Rk的乘积 列向量即为所求的特征向量 即为所求的特征向量. Uk＝R1R2...Rk 的列向量即为所求的特征向量
1° λ1= -λ2; ° 从任意 ν
ν
v (0) =
v ( 0)
|λ1| > |λ3| ≥ … ≥ |λn|
v (k ) v ( k −1)
n
v v (0) v v (0) v ( ≠ 0 出发，不妨假定 ν , x1 ) ≠ 0, (ν , x 2 ) ≠ 0; 出发，
∑
i =1
n
v α i xi ,
第10章 矩阵特征值与特征向量的计算
本章目标： 本章目标：计算矩阵的特征值及对应的特征向量
10.1 10.2 10.3 10.4 10.5 幂法及反幂法 Jacobi方法 QR方法 特征值与特征向量的MATLAB函数求解 实例解析
10.1 幂法及反幂法
一、幂法 条件： 条件：A 有特征根 |λ1| > |λ2| ≥ … ≥ |λn| ≥ 0，对应 个线性无 ，对应n个线性无 关的特征向量 x 1 , ... , x n 思路：从任意 ν (0) ≠ 0 出发，要求 (ν (0) , x1 ) ≠ 0 出发， 思路：
k
v v v ( k −1 ) v ( k − 1 ) = A k −1 v ( 0 ) u = ( k −1 ) | v ik −1 | ∏ k −1| v i( s ) |
s =0
s
v v v ( k ) = Au ( k − 1 ) =
v Ak v ( 0 ) k −1 | v i(ss ) | ∏ s =0
v v v k 充分大时, 当k 充分大时 有: ν ( k ) ≈ λ 1 [α 1 x 1 + ( − 1) k α 2 x 2 ] , v v v k ν ( k + 1 ) ≈ λ 1 + 1 [α 1 x 1 + ( − 1 ) k + 1 α 2 x 2 ] , v v v k ν ( k + 2 ) ≈ λ 1 + 2 [α 1 x 1 + ( − 1 ) k + 2 α 2 x 2 ] ,
二、反幂法 (1) 用反幂法求 的按模最小的特征根 用反幂法求A的按模最小的特征根 若 A 有| λ1 | ≥ | λ2 | ≥ … > | λn |, 则 对应同样一组特征向量。 对应同样一组特征向量。 A−1 的主特征根
v ( k +1)
A−1 有
> λ1 ≥ …≥ λ ≥ 1 λn n −1 1
v x i( k +2 ) + v x l( k +2 ) +
v v px i( k + 1) + qx i( k ) = 0 其余分量是否也满足 p = −(λ1 + λ2 ) v v q = λ1λ2 关系式? px l( k + 1) + qx l( k ) = 0 关系式 若满足
的两个根: 即, λ1 和λ2是方程λ2 + pλ + q=0 的两个根