特征值与特征向量

  • 特征值:求代数方程 $\varphi(\lambda)=|\lambda I-A|= 0$ 的根
  • 特征向量:求代数方程 $(\lambda I-A)x=0$ 的非零解
  • 若 $\lambda_i$ 是矩阵 $A$ 的特征值,则
    • $\sum_{i=1}^n\lambda_i=\text{tr} A$
    • $|A|=\prod \lambda_i$
  • $A$ 与 $B$ 互为相似矩阵 $\exists T,|T|\neq 0,B=T^{-1}AT$ 则
    • $A$ 与 $B$ 有相同的特征值
    • $x$ 是 $B$ 的一个特征向量,则 $Tx$ 是 $A$ 的特征向量
  • Gerschgorin’s 定理:$A$ 的每个特征值必属于以下某个圆盘之内 $|\lambda -a_{ii}|\leq \sum_{j=1,j\neq i}^n|a_{ij}|,i=1,\cdots,n$
    • 特征向量第 $i$ 个分量最大,则属于第 $i$ 个圆盘
  • $A$ 为对称矩阵,$R(x)=\frac{(Ax,x)}{(x,x)}$ 为对应向量 $x$ 的 Rayleigh 商 (特征值次序 $\lambda_1\geq \cdots \lambda_n$)
    • $\lambda_n\leq\frac{(Ax,x)}{(x,x)}\leq\lambda_1$
    • $\exists x\in\mathbb{R}^n,x\neq 0$ 使等号成立

幂法

  • 主特征值:最大特征值和相应特征向量
  • $v_{k+1}=Av_k$
    • $v_0=\sum_{i}a_ix_i$
    • $v_k=Av_{k-1}=\lambda_1^k(a_1x_1+\epsilon_k)$
    • $\epsilon_k=\sum_{i=2}^na_1(\frac{\lambda_i}{\lambda_1})^kx_i$
    • $\lim_{k\rightarrow\infty}\frac{(v_{k+1})_i}{(v_k)_i}=\lambda_1$
  • 规范化:$u=\frac{v}{\max(v)},\max(v)$ 为绝对值最大的分量
    • $v_k=Au_{k-1}=\frac{A^kv_0}{\max(A^{k-1}v_0)}$
    • $u_k=\frac{v_k}{\max(v_k)}=\frac{A^kv_0}{\max(A^kv_0)}$
    • $\max(v_k)\rightarrow\lambda_1$
    • 收敛比率:$r=\frac{\lambda_2}{\lambda_1}$
  • 加速方法
    • 原点平移法:$B=A-pI,B$ 特征值为 $\lambda_i-p$ 且特征相同,$|\frac{\lambda_2-p}{\lambda_1-p}|< |\frac{\lambda_2}{\lambda_1}|$
    • 特征值为实数时:$p=\frac{\lambda_1+\lambda_{n-1}}{2}$
    • Rayleigh 商加速法:$\frac{(Au_k,u_k)}{(u_k,u_k)}=\lambda_1+O((\frac{\lambda_2}{\lambda_1})^{2k})$
  • 反幂法:$A^{-1}$ 应用幂法,得主特征 $\frac{1}{\lambda_n}$

Householder 方法

  • $A\in\mathbb{R}^{n\times n},\exists$ 正交阵 $R$,对角块为一阶或二阶矩阵,每个一阶对角块为 $A$ 的实特征值,二阶对角块的两个特征值是 $A$ 的一对共轭复特征值

    $$R^TAR=\begin{bmatrix} T_{11} & T_{12} & \cdots & T_{1n} \newline & T_{22} & \cdots & T_{2n} \newline & & \ddots & \vdots \newline & & & T_{nn} \end{bmatrix}$$

  • 上 Hessenberg 阵:$i>j+1$ 时,$b_{ij}=0$

  • 单位向量 $w$,初等反射矩阵 $H=H(w)=I-2ww^T$

    • 对称阵 $H^T=H$
    • 正交阵 $H^TH=I$
    • 对合阵 $H^2=I$
    • 几何意义:做关于以 $w$ 为法向量的平面的反射
  • $x,y$ 为不相等 $n$ 维向量,$|x|_2=|y|_2$,则存在初等反射阵 $H$,$Hx=y$

    • $\omega=\frac{x-y}{|x-y|_2}$
    • $\sigma=\pm|x|_2,x\neq-\sigma e_1$,则存在反射阵 $H=I-2\frac{uu^T}{|u|_2^2}=I-\rho^{-1}uu^T$,使 $Hx=-\sigma e_1$,其中 $u=x+\sigma e_1,\rho=\frac{|u|_2^2}{2}$
  • 算法: 计算 $\sigma,\rho,u$ 使 $(I-\rho^{-1}uu^T)x=-\sigma e_1$

    • $\eta=\max_i|\alpha_i|$
    • $\alpha_i\leftarrow u_i=\frac{\alpha_i}{\eta}$
    • $\sigma=\text{sgn}(\alpha_1)(\sum_{i=1}^n\alpha_i^2)^{\frac{1}{2}}$
    • $\alpha_1\rightarrow u_1=\alpha_1+\sigma$
    • $\rho=\sigma u_1$
    • $\sigma\leftarrow\eta\sigma$
  • $HA$: $2n^2$ 次乘法

  • $A\in\mathbb{R}^{n\times n}$,则存在初等发射矩阵 $U_1,U_2,\cdots,u_{n-2}$ 使 $U_{n-1}\cdots U_2U_1AU_1U_2\cdots U_{n-2}=C$ 为 上 Hessenberg 阵

    • 约 $\frac{5}{3}n^3$ 次乘法运算
    • $A$ 为对称矩阵时,获得三对角矩阵;约 $\frac{2}{3}n^3$ 次乘法运算
  • 算法:化为上 Hessenberg 阵

    • 对 $A$ 进行了 $k-1$ 步正交相似约化后,$A_{11}^{(k)}\in\mathbb{R}^{k\times(k-1)}$ $$\begin{bmatrix} A_{11}^{(k)} & a_{12}^{(k)} & A_{13}^{(k)} \newline O & a_{22}^{(k)} & A_{23}^{(k)}\end{bmatrix}$$

    • 当 $a_{22}^{(k)}\neq 0$ 时,选择初等发射阵 $R_k$ 使 $R_k a_{22}^{(k)}=-\sigma_ke_1$

      $$U_k=\begin{bmatrix}I & O \newline O&R_k \end{bmatrix}$$

      $$A_{k+1}=U_kA_kU_k=\begin{bmatrix} A_{11}^{(k)} & a_{12}^{(k)} & A_{13}^{(k)}R_k \newline O & R_ka_{22}^{(k)} & R_kA_{23}^{(k)}R_k \end{bmatrix}$$

QR 算法

  • 平面旋转矩阵:$P_{ij}=I,P_{ij}(i,i)=c,P_{ij}(i,j)=s,P_{ij}(j,j)=1$
  • $x=(\alpha_1,\cdots,\alpha_n)^T,\alpha_i,\alpha_j$ 不全为 0,则存在旋转矩阵 $P_{ij}$ 使 $P_{ij}x=y\equiv(\alpha_1,\cdots,\alpha_i^{(1)},\cdots,\alpha_j^{(1)},\cdots,\alpha_n)^T$
    • $\alpha_i^{(1)}=\sqrt{\alpha^2_i+\alpha_j^2}$
    • $\alpha_j^{(1)}=0$
    • $c=\frac{\alpha_i}{\sqrt{\alpha^2_i+\alpha_j^2}}$
    • $s=\frac{\alpha_j}{\sqrt{\alpha^2_i+\alpha_j^2}}$
  • 非奇异矩阵 $A$ 可通过一系列平面旋转矩阵,$P_{n-1}\cdots P_2P_1A=R$ 为上三角矩阵且对角元素为正
  • QR 分解:$A\in\mathbb{R}^{n\times n}$ 为非奇异矩阵,则 $A$ 可分解为一正交矩阵 $Q$ 与上三角矩阵 $R$ 的乘积;当 $R$ 对角元素都为正时唯一
  • 基本 $QR$ 方法
    • $A_k=Q_kR_k$
    • $A_{k+1}=R_kQ_k$
    • $A_{k+1}$ 相似于 $A_k$
    • $A_{k+1}=(Q_1Q_2\cdots Q_k)^TA_1(Q_1Q_2\cdots Q_k)=\overline Q_k^T A_1\overline Q_k$
    • $A^k$ 的 QR 分解式为 $A^k=\overline Q_k\overline R_k$
  • QR 方法的收敛性:若 $A$ 特征值 $|\lambda_1|>|\lambda_2|\cdots|\lambda_n|>0$ 且有标准形 $A=XDX^{-1}$,且 $X^{-1}$ 有三角分解 $X^{-1}=LU$,则 QR 算法收敛于上三角矩阵,且对角元素为 $\lambda_i$
    • 对称阵收敛于对角阵
    • 若等模特征值只有实重特征值或多重复的共轭特征值,则收敛于分块上三角矩阵