第三讲 矩阵特征值计算及其应用 — 正交变换与QR方法.

Presentation on theme: "第三讲 矩阵特征值计算及其应用 — 正交变换与QR方法."— Presentation transcript:

1 第三讲 矩阵特征值计算及其应用 — 正交变换与QR方法

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

3 Householder 变换 定义：设 且 ，称矩阵 基本性质 为Householder变换，或反射变换。 注：若不要求
定义：设 且 ，称矩阵 为Householder变换，或反射变换。 基本性质 注：若不要求 则 Householder 变换 定义为 (1) 对称： (2) 正交： (3) 对合： (4) 保模： (5)

4 Householder 变换 定理：设 x, y  Rn, x  y 且 ||x||2 = ||y||2，则存在 n 阶 Householder 变换 H，使得 y = Hx 证：取

5 Householder 变换 定理：对任意的非零向量 x  Rn，存在 Householder 变换 H，使得 Hx = e1
其中  = -sign(x1)||x||2, e1= (1, 0, ..., 0)T ，  的选取是为了防止在实际计算中  与 x1 互相抵消 若 x1=0, 则取  = ||x||2

6 Givens 变换 定义：称矩阵 i j i j 为 Givens 变换，或 旋转变换。

7 Givens 变换 基本性质 (1) 只有四个元素与单位矩阵不同 (2) 正交： (3) 用 G 左乘一个矩阵时，只改变该矩阵中两行的值

8 Givens 变换 定理：设 x = (x1, ..., xi , ... , xj , ... , xn)T，且 xi , xj 不全为零，则存在 Givens 变换 G = G (i, j, )，使得

9 QR 分解 定理：（QR 分解） 设 n 阶实矩阵 A 非奇异，则存在正交分解 A = QR
可通过Gram-Schmidt 正交化过程实现

10 QR 分解算法 算法（QR 分解） 考虑到稳定性，采用Householder变换 设 ( j = 1, ... , n )
(1) 构造 H1 使得 H1 a1 = 1e1 ，令 (2) 构造 使得 ，令

11 QR 分解算法 以此类推，经过 n-1 步，可得 Householder 矩阵 H1, H2, ... , Hn-1 ，使得 令 ，即得
令 ，即得 QR分解的运算量：约

12 QR 分解举例 例：用 Householder 变换计算 的 QR 分解 解：(板书) 节省运算量

13 Schur 分解 定理：（Schur 分解） 设 A 为 n 阶实矩阵，则存在正交矩阵 Q，使得 其中 Rii 是一阶或二阶方阵。
拟上三角矩阵 若 Rii 是一阶方阵，则它就是 A 的特征值； 若 Rii 是二阶方阵，则其特征值为 A 的两个共轭复特征值。

14 QR 迭代 QR 迭代算法 计算矩阵的所有特征值和特征向量 计算过程 (1) 令 A1＝A (2) 对 k = 1, 2, ... ，
计算 Ak 的 QR 分解 计算 直到 Ak+1 收敛到一个 拟上三角阵 优点：可以计算所有特征值和特征向量 缺点：收敛慢，运算太大，约 O(n4)

15 实用的 QR 迭代 实用的 QR 迭代算法 先采用 Householder 变换，通过相似变换，将矩阵 A 转化为上 Hessenberg 矩阵 H，运算量 O(n3) 对 H 进行隐式 QR 迭代，每步运算量 O(n2) 选择适当的位移策略，对算法进行加速，这样平均2到3步就能收敛到一个特征值，因此总迭代步数约 2n 到 3n 将总运算量从 O(n4) 降到 O(n3) 具体实施细节可参见相关文献

16 MATLAB计算特征值 用 Maltab自带函数 计算特征值 计算所有特征值和特征向量：eig
E=eig(A); E 中包含 A 的所有特征值 [V,D]=eig(A); D 为 A 的所有特征值组成的对角阵， V 为相应的特征向量组成的矩阵，即 AV=VD 大规模稀疏矩阵的部分特征值和特征向量：eigs