矩阵的特征值与特征向量

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial

矩阵特征值的与特征向量

若矩阵$A$，列向量$X$，常数$\lambda$满足$AX=\lambda X$,则我们称$\lambda$是$A$的一个特征值，$X$是$A$的一个特征向量

解析解

一元高次方程$det(X-\lambda E)=0$,这在X的阶很高的时候，几乎是无用的。

近似解

因为我们难以得到矩阵特征值的解析解，所以这里使用近似解来逼近。

Given变换

Given变换是一种旋转变换，他的变换矩阵与单位矩阵相比只有四个元素不一样,变换矩阵如下 $$ $$\begin{array}{r}\left[\begin{array}{cc}& 1\\ & & .\\ & & & .\\ & & & & .\\ & & & & & \cos \theta & & & & \sin \theta \\ & & & & & & .\\ & & & & & & & .\\ & & & & & & & & .\\ & & & & & -\sin \theta & & & & \cos \theta \\ & & & & & & & & & & .& \\ & & & & & & & & & & & .& \\ & & & & & & & & & & & & .& \\ & & & & & & & & & & & & & 1& \end{array}\right]\end{array}$$

$$ 不难证明这个矩阵是正交矩阵，不难证明左乘这个变换只会改变两行,右乘这个矩阵只会改变两列

Hessenberg矩阵

次对角线下方元素为0 $$\begin{array}{r}\left[\begin{array}{cccccc}& x& x& x& x& x\\ & x& x& x& x& x\\ & & x& x& x& x\\ & & & x& x& x\\ & & & & x& x\end{array}\right]\end{array}$$ 任何一个方阵都有上海森伯格形式的相似矩阵，

幂法

幂法是最基础的算法，我们先来描述一下这个过程 我们随机选择一个初始列向量$Y$，假设它能够被矩阵A的特征向量线性组合出来，则$$\begin{array}{r}\underset{N\to \mathrm{\infty }}{lim}{A}^{N}Y\end{array}=\mathrm{一}\mathrm{个}\mathrm{特}\mathrm{征}\mathrm{向}\mathrm{量}$$ 这里使用快速幂算法就亏大了快速幂迭代一次$O(N^3)$，普通迭代一次$O(N^2)$，所以普通迭代就行了， 证明: 对于大部分$Y$来说，如果它能够被组合出来即$Y=k_1{X}_1+K_2{X}_2+K_3{X}_3+...$，且满足特征值满足条件${\lambda }_1>{\lambda }_2>...$ 则有$A^{N}Y=k_1{A}^N{X}_1+k_2{A}^N{X}_2+...=k_1{\lambda }_1^N{X}_1+k_2{\lambda }_2^N{X}_2+...$，所以这个极限是显然趋近于特征值绝对值最大的特征向量的。 所以这个算法在大多数情况下都能成功。考虑到幂法会增长很快，我们可以在迭代过程中单位化。

反幂法

求逆以后在用幂法，我们会得到特征值最小的特征向量,这很容易证明。

jacobi迭代法

只能处理对称矩阵 这个算法使用相似矩阵，每次使用一个Given变换，让绝对值最大的非对角线上的元素变为0，这导致了整体势能的下降，最终相似矩阵的非对角线元素会趋近于0，Given变换是一个稀疏矩阵，他和单位矩阵只有四个元素不同，是一种旋转矩阵，加上相似变换以后，这导致他只会改变两行和两列,最终我们就得出了特征值。

QR迭代法

还是先说做法，再给出证明，根据QR分解我们有$A=QR$，构造$A_2=RQ=Q^{-1}AQ$,我们就不难发现$A_2$与$A$相似,我们用同样的办法，从$A_1$得到$A_2$,从$A_2$得到$A_3$...不断的迭代下去，最终$A_i$对角线一下的元素会趋近于0，这是特征值就算出来了.QR算法的本质其实还是幂法， 我们考虑幂法的过程，他可以求出一个特征向量，如果我们在幂法结束以后，得到了$X_1$，然后我们再随机选择一个$Y_2$,把$Y_2$中$X_1$的分量去掉，然后进行幂法迭代，这时候我们会得到特征值第二大的特征向量，因为$Y_2$再去掉$X_1$方向上的分量以后，已经不再包含$X_1$方向上的值了，也即$k_1$为0,这时候幂法得到的极限是第二大特征向量，随后我们可以顺序得到第三大、第四大、、、,这样太蠢了，我们考虑一次性把他们呢求出来，我们一次性就选择n个随机向量构成矩阵Z，然后用A左乘得到AZ，然后对AZ 使用斯密斯正交化得到$Z_2$，可以证明$Z_n$将趋近于A的所有特征向量构成的矩阵。证明很多细节地方没有处理，这也就是为什么QR算法会失败的原因，但QR算法在大多数情况下是能够成功的， 即我们得到了算法迭代$Y_i=GramSchmidt(A{Y}_{i-1})$,这个算法叫归一化算法，和上面那个算法优点小区别,但本质上是一样的，只是标记不一样而已。 如果我们能够提前把矩阵变为上海森伯格形式，QR算法的速度将大大提高。