QR分解求特征值的方法很简单，计算过程如下：
文章图片
文章图片
QR本身可以看作一个将矩阵A转化为上三角矩阵R的过程，通过householder，givens转换等手段，构造一系列的变换矩阵T，将矩阵转换为上三角矩阵R，而变换矩阵的逆矩阵则构成了Q。一定条件下，经过n次迭代后，迭代矩阵An会神奇的收敛成一个上三角矩阵，其对角阵对应的元素就是An的特征值，也是原始矩阵A的特征值，是不是很神奇。那么为什么会收敛成这样呢？直觉上，这是一种幂法，经过不断地迭代，使得特征值保留下来，非特征值部分要么变大，要么收敛为0。事实上，这种求特征值地方法确实属于一种特殊地幂法。我们所知道地幂法和反幂法都是针对最大或者最小的特征值来的，像QR这种一网打尽的方式，实在难以想象。为什么QR这种迭代方式会最终收敛到特征值呢？我找了国内外不少网站，也没有找到浅显的解释。这里将这几天找到的资料整理一下，按照自己的理解说一下。
这个问题看来是一个复杂的问题，所以这里简化了它的收敛证明过程。考虑一种比较特殊的矩阵QR分解形式
假定矩阵A满足以下两个条件
1.A是对称正定矩阵，且特征值各不相同，保证了QR分解的唯一性
2.A可以表示为
文章图片
,
文章图片
且有
文章图片
，L为下三角矩阵，L的对角线全部为1，U为上三角矩阵
另外，需要知道以下几点性质
1.上三角矩阵乘以上三角矩阵仍然是上三角矩阵，对于下三角矩阵也是同理
2.上三角矩阵求逆，仍然是上三角矩阵，对于下三角矩阵也是同理
首先，求得
文章图片
的推导公式
文章图片
假设我们的问题中
文章图片
收敛成立，最终可以得到
文章图片
,只要能证明这一点就行了，但是最关键的是想看到幂法是如何其作用的。
令
文章图片
文章图片
令
文章图片
,代入上式
文章图片
其中，
文章图片
由此可以得到
文章图片
，于是有
文章图片
其中，
文章图片
分别为正交矩阵和上三角矩阵，由QR分解的唯一性可以知道，
文章图片
，
文章图片
再来看看
文章图片
文章图片
我们可以看到，QR迭代过程，可以看作消去Q矩阵的过程。像幂法一样，QR也有平移的算法，以上介绍的是非平移的算法过程。由于A是对称正定矩阵，最终分解得到了对角阵，而不是上三角矩阵。为了尽量的描述简单，加了不少苛刻的条件，下面将条件稍微放宽些，A只是正定，不再是对称，其他条件保持不变，于是
文章图片
不再成立。
文章图片
由于
文章图片
文章图片
文章图片
由于
文章图片
，
文章图片
令
文章图片
,毫无疑问，M，R和T都是上三角矩阵，且有
文章图片
,可以看到M的对角线元素收敛于特征值。
上面就是QR收敛的证明过程，证明过程并不严密，且由于条件特殊，并不具备普遍性。确实如此，这个算法本身收敛性是有限制的，并非对所有矩阵都能满足。要做到普遍适用，应该要用到移位的QR算法。
参考：
https://www.zhihu.com/question/54455860
https://people.kth.se/~eliasj/qrmethod.pdf
【数据科学|为何QR分解收敛于特征值】http://pi.math.cornell.edu/~web6140/TopTenAlgorithms/QRalgorithm.html
推荐阅读
- paddle|动手从头实现LSTM
- 人工智能|干货！人体姿态估计与运动预测
- 推荐系统论文进阶|CTR预估 论文精读(十一)--Deep Interest Evolution Network(DIEN)
- Python专栏|数据分析的常规流程
- 读书笔记|《白话大数据和机器学习》学习笔记1
- Pytorch学习|sklearn-SVM 模型保存、交叉验证与网格搜索
- Python机器学习基础与进阶|Python机器学习--集成学习算法--XGBoost算法
- 深度学习|深度学习笔记总结
- 机器学习|机器学习Sklearn学习总结
- 机器学习|线性回归原理与python实现