计算方法B.裴玉茹.07.特征值与奇异值(2)

• PPT（特征值）

特征值与奇异值

• 特征值：Eigenvalue
• 特征向量：Eigenvector

1. 定理

相似矩阵

• 若存在非奇异矩阵 $S$，满足 $A=S^{-1}BS$，则称矩阵 $A$ 与矩阵 $B$ 为相似矩阵
• 相似矩阵特征值相等
  • 假定 $x\ne 0$
  • 那么有 $S^{-1}BSx=Ax=\lambda x$
  • $BSx=SAx=\lambda Sx$
  • 于是 $\lambda$ 是矩阵 $B$ 的特征值，$Sx$ 是对应的特征向量

Schur 定理

• $A$ 为任意矩阵，存在非奇异矩阵 $U$ 使得 $T=U^{-1}AU$，其中 $T$ 为上三角矩阵，对角线元素为矩阵 $A$ 的特征值

image-20211114185219902

• 如果 $A$ 是对称矩阵，则存在正交矩阵 $Q$ 使得 $D=Q^{-1}AQ=Q^{T}AQ$，其中 $D$ 为对角线矩阵，对角线元素为矩阵 $A$ 的特征值

• 如果 $\Vert Ux{\Vert }_2=\Vert x{\Vert }_2$，$U$ 为酉矩阵，具有保范性质
  • 正交矩阵是酉矩阵

Jacobi 方法

• 用于求解实对称矩阵的特征值
• 通过旋转矩阵，构造相似矩阵
  • 如下是 $Q^T$

• 旋转矩阵 $Q$：第 $i,j$ 行出现和单位矩阵不一样的元素（$\cos \theta ,\sin \theta$）
• 记 $B=Q^{-1}AQ$，我们会发现 $B$ 只有第 $i,j$ 行和第 $i,j$ 列和 $A$ 不一样

$$\left[\begin{array}{cc}{b}_{ii}& b_{ij}\\ b_{ji}& b_{jj}\end{array}\right]={\left[\begin{array}{cc}c& -s\\ s& c\end{array}\right]}^T\left[\begin{array}{cc}{a}_{ii}& a_{ij}\\ a_{ji}& a_{jj}\end{array}\right]\left[\begin{array}{cc}c& -s\\ s& c\end{array}\right]$$

$$\left[\begin{array}{cc}{b}_{ii}& 0\\ 0& b_{jj}\end{array}\right]=\left[\begin{array}{cc}{a}_{ii}{c}^2+a_{jj}{s}^2+2cs{a}_{ij}& cs(a_{jj}-a_{ii})+a_{ij}(c^2-s^2)\\ cs(a_{jj}-a_{ii})+a_{ij}(c^2-s^2)& a_{jj}{c}^2+a_{ii}{s}^2-2cs{a}_{ij}\end{array}\right]$$

• 整个矩阵结果如下

• 思路：不断地消去非对角线元素
  • 正交变换 $F$ 范数不变
  • 上述变换后，对角线上的元素平方和变大了，非对角线上元素的平方和变小了
  • 经过有限次变换，能够求得特征值

推论

• 如果矩阵 $A$ 为对称矩阵，其 $n$ 个特征向量构成单位正交集，矩阵 $A$ 的特征值为实数

正定性与特征值

• 对称矩阵 $A$ 为正定矩阵当且仅当矩阵 $A$ 的所有特征值都是正数
  • 利用特征向量正交、线性即证
• 证明

Gerschgorin 圆盘定理

• $k$ 个圆的并集指的是原本就相交形成的连通区域
• 证明

2. 幂方法

• note
• 占优特征值
  • ${\lambda }_1={\lambda }_2=\cdots ={\lambda }_k$
  • ${\lambda }_1=-{\lambda }_2$
    • 无法确定正负

逆幂方法

• $(A-qI{)}^{-1}x$ 使用幂方法
  • $q$ 的选择决定了收敛速度
  • $q$ 与特征值 ${\lambda }_k$ 越接近，收敛越快

3. 收缩方法

• 在计算了主特征值的近似值后，可以通过紧缩获得矩阵其它特征值

Wielandt 收缩

• 构造一个新的矩阵 $B$，其特征值除了占优特征值之外与 $A$ 相同，其中占优特征值被替换为 0
  • 只有占有特征值与 $A$ 不同

定理

• 假设 ${\lambda }_1,\cdots ,{\lambda }_n$ 是 $A$ 的特征值，其特征向量 $v^{(1)},\cdots ,v^{(n)}$，且 ${\lambda }_1$ 的重数为 1
• 设 $x$ 为向量满足 $x^T{v}^{(1)}=1$，则矩阵 $B=A-{\lambda }_1{v}^{(1)}{x}^T$
  • $B$ 的特征值为 $0,{\lambda }_2,\cdots ,{\lambda }_n$，特征向量为 $v^{(1)},w^{(1)}\cdots ,w^{(n)}$
  • $v^{(i)}=({\lambda }_i-{\lambda }_1)w^{(i)}+{\lambda }_1{x}^T{w}^{(i)}{v}^{(1)}$

算法细节

• 如何构造 $x$

• 发现矩阵 $B=A-{\lambda }_1{v}^{(1)}{x}^T$ 的第 $i$ 行全为 0
  • 代入即得
• $Bw=\lambda w$
  • 因此，$w$ 的第 $i$ 个分量是 0，所以 $B$ 的第 $i$ 列对解没有贡献，去掉第 $i$ 行和第 $i$ 列得到 $(n-1)\times (n-1)$ 矩阵 $B^{\prime }$
    • 行列式展开的角度也行
• 对 $B^{\prime }$ 应用幂方法，得到 ${\lambda }_2$ 与 $w^{\prime (2)}$， 并插入 0 得到 $w^{(2)}$
• 问题：易受舍入误差影响

Householder 变换

• $P=I-2w{w}^T$，其中 $w^{T}w=1,w\in {\mathbb{R}}^n$
  • $P$ 是对称正交矩阵

目标

• 利用 Householder 方法计算对称三对角线矩阵 $B$，其与给定的对称矩阵 $A$ 相似
  • 和这部分有些接近

步骤

• 定义矩阵变换 $P^{(1)}$ 满足 $A^{(2)}=P^{(1)}A{P}^{(1)}$
  • 显然 $P^{(2)}$ 是对称矩阵，$P^{(1)},A$ 都是对称矩阵
• 试图在变换后保证
  • $a_{11}^{(2)}=a_{11}$
    • $w_1=0$ 即可
  • $a_{j1}^{(2)}=0,(j=3,\cdots ,n)$
• 也就是说，利用 HouseHolder 变换将 $(a_{21},a_{31},\cdots ,a_{n1}{)}^T$ 转换为 $(\alpha ,0,\cdots ,0{)}^T$

• ${\hat{w}}^T\hat{y}$ 是 $1\times 1$ 的，因此可以提前

求解参数

• 计算具体的 $\alpha$ 值

$$\begin{array}{c}(\alpha ,0,\cdots ,0)=(a_{21}-r{w}_2,a_{31}-r{w}_3,\cdots ,a_{n1}-r{w}_n)\\ \mathrm{其}\mathrm{中}r={\hat{w}}^T\hat{y}\end{array}$$

$$\begin{array}{c}\alpha =a_{21}-r{w}_2\\ a_{i1}-r{w}_i=0,i=3,\cdots ,n\end{array}$$

• 对 $2r{w}_i$ 平方求和

$$4r^2\sum _{j=2}^n{w}_j^2=(a_{21}-\alpha {)}^2+\sum _{j=3}^n{a}_{j1}^2$$

• 左边：$4r^2(1-w_1^2)=4r^2$

$$4r^2=-2\alpha a_{21}+{\alpha }^2+\sum _{j=2}^n{a}_{j1}^2$$

• 再由 $P$ 的正交性

$${\alpha }^2=(\hat{P}\hat{y}{)}^T(\hat{P}\hat{y})={\hat{y}}^T{\hat{P}}^T\hat{P}\hat{y}={\hat{y}}^T\hat{y}=\sum _{j=2}^n{a}_{j1}^2$$

• 结合上面两个式子，得到

$$2r^2=-\alpha a_{21}+\sum _{j=2}^n{a}_{j1}^2=-\alpha a_{21}+{\alpha }^2$$

• 可以求解得到 $\alpha ,w$

$$\alpha =-\mathrm{sgn}(a_{21})\sqrt{\sum _{j=2}^n{a}_{j1}^2}$$

$$2r^2=-\alpha a_{21}+{\alpha }^2$$

$$\begin{array}{c}{w}_2={\displaystyle \frac{a_{21}-\alpha }{2r}}\\ w_i={\displaystyle \frac{a_{i1}}{2r}},i=3,\cdots ,n\end{array}$$

• 之后的步骤类似前面的，收缩方法

4. QR 迭代

• QR 方法
  • 同时确定对称矩阵所有特征值的矩阵约化方法
  • QR 方法可以生成一组矩阵 $A=A^{(1)},A^{(2)},\cdots ,A^{(n)}$
  • $A^{(1)}=A$ 分解为矩阵乘积 $A^{(1)}=Q^{(1)}{R}^{(1)}$
    • $Q^{(1)}$ 为正交矩阵
    • $R^{(1)}$ 为上三角矩阵
  • $A^{(2)}$ 定义为 $A^{(2)}=R^{(1)}{Q}^{(1)}$
  • 接着继续对 $A^{(2)}$ 进行 QR 分解
  • 可以得到 $A^{(i+1)}=(Q^{(i)}{)}^T{A}^{(i)}{Q}^{(i)}$
    • 相似变换，特征值不变
• $A^{(i+1)}$ 与 $A^{(i)}$ 具有相同的特征值，$A^{(i+1)}$ 变为对角线矩阵，其对角线上值为矩阵 $A$ 的特征值

• $Q^{\mathrm{\infty }}$ 与 $A^{\mathrm{\infty }}$ 的特征向量相同
  • $AB=BA$ $\Rightarrow$ $A$ 与 $B$ 具有相同的特征向量
• 由于 $Q^{\mathrm{\infty }}$ 是正交矩阵，$Q^{\mathrm{\infty }}$ 的特征值为 $\pm 1$
• 假设 $A^{\mathrm{\infty }}x=\lambda x$，则有

$$\lambda x=A^{\mathrm{\infty }}x=Q^{\mathrm{\infty }}{R}^{\mathrm{\infty }}x=R^{\mathrm{\infty }}{Q}^{\mathrm{\infty }}x=\pm R^{\mathrm{\infty }}x$$

• 得出结论
  • $A^{\mathrm{\infty }}$ 的特征值与 $A$ 的特征值相同
  • 与 $R^{\mathrm{\infty }}$ 的特征值相同，即 $R^{\mathrm{\infty }}$ 的对角线元素（可能会差符号）
  • 与 $Q^{\mathrm{\infty }}$ 的特征向量相同

构造 QR

• 考虑旋转矩阵
  • 旋转矩阵为正交矩阵
    • $p_{ii}=p_{jj}=\cos \theta ,p_{ji}=-p_{ij}=\sin \theta$

三对角线稀疏矩阵

• 矩阵 $A$ 为三对角线矩阵 ，对其使用旋转矩阵进行 QR 分解
  • 让对角线以下元素变成 0
  • (1,3) 可能变为非零向量，(1,4)、(1,n) 为 0

• 算法流程

• 矩阵 $A$ 三对角线最上面一条对角线不一定需要和最下面相同，不需要为 $b_n$
• 接着使用上面的方法进行迭代
• $A^{(2)}$ 对角线以外的项比 $A^{(1)}$ 的相应项小，$A^{(1)}$ 更接近对角矩阵
• 为什么 $A^{(2)}$ 还是三对角线矩阵 ？
  • $A^{(2)}=(Q^{(1)}{)}^T{A}^{(1)}{Q}^{(1)}$
  • 因为旋转矩阵只会影响行列 $i,j$
  • note
• 收敛速度
  • 对于特征值$|{\lambda }_1|>|{\lambda }_2|>\cdots >|{\lambda }_n|$
  • $A^{(i+1)}$ 的元素 $b_{j+1}^{(i+1)}$ 收敛到 0 的速度依赖于比值 ${\displaystyle \frac{|{\lambda }_{j+1}|}{|{\lambda }_j|}}$，接近于 1 的时候收敛速度较慢

平移方法（三对角线）

• 当 $b_n^{(i+1)}$ 足够小，假设 ${\lambda }_n\approx a_n^{(i+1)}$
• 删除矩阵的第 n 行与第 n 列，计算 ${\lambda }_{n-1}$
• 收敛速度依赖于 ${\displaystyle \frac{|{\lambda }_{j+1}-s|}{|{\lambda }_j-s|}}$ , 一般为三阶收敛速度 平移需要加回到特征值