第三讲 矩阵特征值计算 —— 幂法与反幂法.

Presentation on theme: "第三讲 矩阵特征值计算 —— 幂法与反幂法."— Presentation transcript:

1 第三讲 矩阵特征值计算 —— 幂法与反幂法

2 主要内容 特征值基本性质 幂法与反幂法 正交变换与矩阵分解 QR 方法 应用：Google 网页排名

3 特征值性质 A x =  x 特征值与特征向量 (   C, x  0 ) 基本性质 (1) (2) (3)
(4) 若 A 对称，则存在正交矩阵 Q，使得

4 Rayleigh 商 定理：设 A 是 n 阶实对称矩阵，其特征值为 则对任意非零向量 x，有 且
称为矩阵 A 关于 x (x  0) 的 Rayleigh 商

5 幂 法

6 幂法 幂法（乘幂法，幂迭代） 计算矩阵的主特征值（按模最大）及其特征向量
假设：(1) |1| > |2|  …  |n|  0 (2) 对应的 n 个线性无关特征向量为：x1, x2, ..., xn 计算过程： (1) 任取一个非零向量 v0，要求满足 (x1,v0)  0 (2) 对 k = 1, 2, ... ，直到收敛，计算

7 幂法的收敛性 收敛性分析 设 越小，收敛越快

8 幂法的收敛性 当 k 充分大时，有 ( j =1, 2, ... , n ) 又 vk 为 1 的近似特征向量

9 幂法的收敛性 定理：设 A 有 n 个线性无关的特征向量，其特征值满足 则由幂法生成的向量满足 注：幂法的收敛速度取决于 的大小

10 幂法 幂法中存在的问题 改进方法：规范化

11 改进的幂法 改进的幂法 定理：设 A 有 n 个线性无关的特征向量，其特征值满足
(1) 任取一个非零向量 v0，要求满足 (x1,v0)  0 (2) 对 k = 1, 2, ... ，直到收敛，计算 定理：设 A 有 n 个线性无关的特征向量，其特征值满足 则由改进的幂法生成的向量满足

12 举例 例：用改进的幂法计算下面矩阵的主特征值和对应的特征向量 Eig01.m

13 幂法的加速 幂法的加速：原点平移法 幂法的收敛速度取决于 的大小 当 r 接近于 1 时，乘幂法收敛会很慢！ 带位移的幂法
幂法的收敛速度取决于 的大小 当 r 接近于 1 时，乘幂法收敛会很慢！ 幂法的加速：原点平移法 带位移的幂法 令 B = A – I，则 B 的特征值为：i -  选择适当的 p 满足： (1) ( j = 2, ... , n ) 保持主特征值 (2) 加快收敛速度 用幂法计算矩阵 B 的主特征值：1 - 

14 举例 例：用带位移的幂法计算下面矩阵的主特征值和对应的特征向量，取 p=0.75 Eig02.m 问题：如何求其它特征值？

15 反 幂 法

16 反幂法 反幂法 计算矩阵的按模最小的特征值及其特征向量
假设：(1) |1|  |2|  …  |n-1| > |n| > 0 (2) 对应的 n 个线性无关特征向量为：x1, x2, ..., xn A-1 的特征值为： 对应的特征向量仍然为 x1, x2, ..., xn 反幂法：用幂法计算矩阵 A-1 的主特征值和特征向量

17 反幂法 反幂法 定理：设 A 有 n 个线性无关的特征向量，其特征值满足 (1) 任取一个非零向量 v0，要求满足 (xn,v0)  0
(2) 对 k = 1, 2, ... ，直到收敛，计算 定理：设 A 有 n 个线性无关的特征向量，其特征值满足 则由反幂法生成的向量满足

18 反幂法的加速 问题：如何选择参数 p ？ 可以使用原点平移法对反幂法进行加速 离 n 越近越好（但不能相等）
反幂法的收敛速度取决于 的大小 当 r 接近于 1 时，反乘幂法收敛会很慢！ 可以使用原点平移法对反幂法进行加速 问题：如何选择参数 p ？ 离 n 越近越好（但不能相等）

19 Rayleigh 商加速 Rayleigh 商加速 (1) 任取一个非零向量 v0，要求满足 (xn,v0)  0
(2) 对 k = 1, 2, ... ，直到收敛，计算

20 几点注记 带位移的反幂法中需要计算 带位移的反幂法可以用于计算任何一个特征值 k 将参数  取为 k 附近
若已知特征值，计算特征向量时，可使用带位移的反幂法 令  足够靠近 k