数据科学算法ch8-特征值计算

幂法

如果说 低阶方阵我们可以用搞死消元法来计算，但是在高阶方阵中，用这种方法显然效率太低。因此，我们需要找到快速的、高效的特征值和特征向量计算方法

幂法就是这样一种方法，是计算举证最大的特征值和对应特征向量的一种向量迭代法

算法过程：

1. 首先，令初始向量 $x_0$
2. 向前递推，公式：当 $k=1,2\cdots$

$$\begin{cases} y_k = Ax_{k-1}\\ m_k = \max(y_k)\\ x_{k} = y_k/m_k\\ \end{cases}$$

1. 收敛到 $x_k^T,m$ 不再变化的时候，停止

反幂法

反幂法是用来求解矩阵A 绝对值最小的非零特征值$\lambda_n$ 的。

算法如下：

1. 任取初始向量 $x_0\neq 0$
2. 当 $k=1,2\cdots$ 时

$$\begin{cases} y_k = A^{-1}x_{k-1}\Rightarrow Ay_k = x_{k-1}\\ m_k = \max(y_k)\\ x_{k} = y_k/m_k\\ \end{cases}$$

此外，反幂法的优势就是，可以通过修改幂法算法来求解方程的任意特征值。

算法如下：

1. 取 $x_0 = (1,\cdots,1)$， 和一个常数 $\lambda$
2. 对于 $k=1,2\cdots$

$$\begin{cases} (A-\lambda I)y_k = x_{k-1}\\ m_k = \max(y_k)\\ x_{k} = y_k/m_k\\ \end{cases}$$

最终我们可以得到，$\boldsymbol A$ 最接近于 $\lambda$ 的特征值等于： $1/m_k +\lambda$ ， 然后，标准化 $x_k$ 即为该特征值的对应特征向量

瑞丽商迭代法