线性代数|机器学习-P13计算特征值和奇异值
文章目录
- 1. 特征值
- 2. 特征值求解思路
- 3. 奇异值求解思路
- 4. krylov 空间
1. 特征值
1.1 特征值求解思路
我们想要计算一个矩阵的特征值，一般是用如下公式：
∣ ∣ A − λ I ∣ ∣ = 0 → λ 1 , λ 2 , ⋯ , λ n \begin{equation} ||A-\lambda I||=0\rightarrow \lambda_1,\lambda_2,\cdots,\lambda_n \end{equation} ∣∣A−λI∣∣=0→λ1,λ2,⋯,λn
但这种方法最大的弊端是对于求解n个解的方程来说，太困难了，当n>100以后，简直无法想象，所以我们只有另辟蹊径，这时候我们想到了相似矩阵的性质，假设矩阵A相似于矩阵 B B B，那么矩阵A与矩阵 B B B特征值相同；
∣ ∣ A − λ a I ∣ ∣ = ∣ ∣ B − λ b I ∣ ∣ , B = P − 1 A P \begin{equation} ||A-\lambda_a I||=||B-\lambda_{b} I||,B=P^{-1}AP \end{equation} ∣∣A−λaI∣∣=∣∣B−λbI∣∣,B=P−1AP
∣ ∣ A − λ a I ∣ ∣ = ∣ ∣ P − 1 A P − λ b I ∣ ∣ = ∣ ∣ P − 1 A P − P − 1 λ b I P ∣ ∣ \begin{equation} ||A-\lambda_a I||=||P^{-1}AP -\lambda_{b} I||=||P^{-1}AP -P^{-1}\lambda_{b}I P|| \end{equation} ∣∣A−λaI∣∣=∣∣P−1AP−λbI∣∣=∣∣P−1AP−P−1λbIP∣∣
∣ ∣ P − 1 A P − P − 1 λ b I P ∣ ∣ = ∣ ∣ P − 1 ∣ ∣ ∣ ∣ A − λ b I ∣ ∣ ∣ ∣ P ∣ ∣ = ∣ ∣ A − λ b I ∣ ∣ \begin{equation} ||P^{-1}AP -P^{-1}\lambda_{b}I P||=||P^{-1}||||A-\lambda_{b}I||||P||=||A-\lambda_{b} I|| \end{equation} ∣∣P−1AP−P−1λbIP∣∣=∣∣P−1∣∣∣∣A−λbI∣∣∣∣P∣∣=∣∣A−λbI∣∣
- 所以得到当矩阵 A ∼ B → λ a = λ b A\sim B\rightarrow \lambda_a=\lambda_b A∼B→λa=λb
∣ ∣ A − λ b I ∣ ∣ = ∣ ∣ A − λ b I ∣ ∣ \begin{equation} ||A-\lambda_{b} I||=||A-\lambda_{b} I|| \end{equation} ∣∣A−λbI∣∣=∣∣A−λbI∣∣
那我们的思路是如果我们对于原矩阵A无法求特征值，那就找一个与A相似的矩阵B，如果矩阵B是一个上三角矩阵 C C C，那么我们对矩阵C进行 ∣ ∣ C − λ I ∣ ∣ = 0 ||C-\lambda I||=0 ∣∣C−λI∣∣=0,就直接发现主对角线上的元素就是特征值，真是方便的思路。
1.2 相似矩阵构造 A 0 ∼ A 1 A_0\sim A_1 A0∼A1
假设我们有一个矩阵 A 0 A_0 A0，我们知道不管什么方法一定能够通过QR分解，且Q为正交矩阵，R为上三角矩阵。那么可得如下：
A 0 = Q 0 R 0 ， Q 0 T Q 0 = I \begin{equation} A_0=Q_0R_0，Q_0^TQ_0=I \end{equation} A0=Q0R0，Q0TQ0=I
-
我们知道，矩阵 Q 0 Q_0 Q0一定可逆，所以矩阵 A 0 A_0 A0左右两边分别乘以 Q 0 T , Q 0 Q_0^T,Q_0 Q0T,Q0
Q 0 T A 0 Q 0 = Q 0 T Q 0 R 0 Q 0 = R 0 Q 0 \begin{equation} Q_0^TA_0Q_0=Q_0^TQ_0R_0Q_0=R_0Q_0 \end{equation} Q0TA0Q0=Q0TQ0R0Q0=R0Q0 -
我们发现矩阵A乘以矩阵 Q 0 Q_0 Q0后居然得到了 R 0 Q 0 R_0Q_0 R0Q0,我们定义新的矩阵 A 1 = R 0 Q 0 A_1=R_0Q_0 A1=R0Q0
Q 0 T A 0 Q 0 = A 1 → λ a 1 = λ a 0 \begin{equation} Q_0^TA_0Q_0=A_1\rightarrow \lambda_{a1}= \lambda_{a0} \end{equation} Q0TA0Q0=A1→λa1=λa0 -
小结1：当我们不断地用正交矩阵Q处理的时候，矩阵 A 1 A_1 A1逐渐会变成上三角矩阵
-
小结2： 当我们矩阵 A 0 A_0 A0通过 Q 0 Q_0 Q0变换成为对角矩阵 Λ \Lambda Λ
( Q 0 Q 1 ⋯ Q n ) T A 0 ( Q 0 Q 1 ⋯ Q n ) = A n → λ a 0 = λ a n \begin{equation} (Q_0Q_1\cdots Q_n)^TA_0(Q_0Q_1\cdots Q_n)=A_n\rightarrow \lambda_{a0}= \lambda_{an} \end{equation} (Q0Q1⋯Qn)TA0(Q0Q1⋯Qn)=An→λa0=λan
1.3 相似矩阵构造： A 0 − S I ∼ A 1 − S I A_0-SI\sim A_1-SI A0−SI∼A1−SI
- 重新构造相似矩阵 A 0 ∼ A 1 → A 0 − S I ∼ A 1 − S I A_0\sim A_1\rightarrow A_0-SI\sim A_1-SI A0∼A1→A0−SI∼A1−SI是为了加快运算速度，具体证明原因暂时不知道。。。后续研究！！！
由上面可得，当我们定义 A 0 = Q 0 R 0 A_0=Q_0R_0 A0=Q0R0时，我们只需要反转 Q 0 R 0 → R 0 Q 0 = A 1 Q_0R_0\rightarrow R_0Q_0=A_1 Q0R0→R0Q0=A1，就能得到 A 0 ∼ A 1 A_0\sim A_1 A0∼A1
Q 0 T A 0 Q 0 = A 1 ， Q 0 T Q 0 = I \begin{equation} Q_0^TA_0Q_0=A_1，Q_0^TQ_0=I \end{equation} Q0TA0Q0=A1，Q0TQ0=I
- 将等式两边减去 S I SI SI可得：
Q 0 T A 0 Q 0 − S I = A 1 − S I → Q 0 T A 0 Q 0 − Q 0 T S I Q 0 = A 1 − S I \begin{equation} Q_0^TA_0Q_0-SI=A_1-SI\rightarrow Q_0^TA_0Q_0-Q_0^TSIQ_0=A_1-SI \end{equation} Q0TA0Q0−SI=A1−SI→Q0TA0Q0−Q0TSIQ0=A1−SI - 整理可得：
→ Q 0 T ( A 0 − S I ) Q 0 = A 1 − S I → Q 0 − 1 ( A 0 − S I ) Q 0 = A 1 − S I \begin{equation} \rightarrow Q_0^T(A_0-SI)Q_0=A_1-SI\rightarrow Q_0^{-1}(A_0-SI)Q_0=A_1-SI \end{equation} →Q0T(A0−SI)Q0=A1−SI→Q0−1(A0−SI)Q0=A1−SI - 整理可得：
Q 0 − 1 ( A 0 − S I ) Q 0 = A 1 − S I → A 0 − S I ∼ A 1 − S I \begin{equation} Q_0^{-1}(A_0-SI)Q_0=A_1-SI\rightarrow A_0-SI\sim A_1-SI \end{equation} Q0−1(A0−SI)Q0=A1−SI→A0−SI∼A1−SI
2. 特征值求解思路
鼎鼎有名的Lapack线性代数库
https://netlib.org/lapack/
3. 奇异值求解思路
同理可以用迭代法求解奇异值，思路还是一样
-
- 通过正交矩阵 Q 0 , Q 1 Q_0,Q_1 Q0,Q1得到 A 0 = U Σ V T → A 1 = Q 0 A 0 Q 2 = ( Q 0 U ) Σ ( V T Q 2 ) A_0=U\Sigma V^T\rightarrow A_1=Q_0A_0Q_2=(Q_0U)\Sigma (V^TQ_2) A0=UΣVT→A1=Q0A0Q2=(Q0U)Σ(VTQ2)
-
- 最后得到 A n A_n An为
上双对角矩阵
- 最后得到 A n A_n An为
-
- 将 A n → A n − S I A_n\rightarrow A_n-SI An→An−SI后进行QR迭代
-
- 得到最后的 σ 1 , σ 2 , ⋯ , σ n \sigma_1,\sigma_2,\cdots,\sigma_n σ1,σ2,⋯,σn
4. krylov 空间
直接引用大神的笔记，具体后续整理