0.背景
搜索技术的很多方面的知识发现都依赖于特征值或奇异值问题，涉及到特征值计算问题。
计算特征值没有直接的方法。
定位特征值的计算方法基于幂迭代的思想，这是求解特征值的一类迭代方法。该思想的一个复杂版本被称为QR算法，是确定典型矩阵所有特征值的一般方法。
特征值问题若消减为求解根的问题，在稍有误差的多项式上用根求解器求根，会带来灾难性后果。
1.幂迭代法
幂迭代法的主要思想：占优特征值对应的特征向量在多次计算后会在计算过程中占优。
主要方法：归一化和与矩阵A相乘。
随着迭代不断改进了近似的特征向量，那么如何得到特征值呢？瑞利商。
幂迭代法的局限：局限于求解绝对值最大的特征值。
幂迭代法的逆：如果幂迭代法用于矩阵的逆矩阵，可以找到最小的特征值。
现在我们知道了如何找出矩阵的最大或最小值，那么怎么找到其他的特征值呢？
幂迭代法这里给出了一个解决方法：
为了找出矩阵A在实数s附近的特征值，对（A-sI)^-1使用幂迭代法得到（A-sI)^-1的最大特征值b，则x=b^-1+s为矩阵A在实数s附近的特征值。
2.QR算法
QR算法是一种可以一次找出所有特征值的方法。
QR分解是把矩阵分解成一个正交矩阵与一个上三角矩阵的积。QR 分解的实际计算有很多方法，例如 Givens 旋转、Householder 变换，以及 Gram-Schmidt 正交化等等。
设
for j=1,2,3...
end
上述过程可称做归一化同时迭代，在第j步，得到的的列是A的特征向量的近似，对角线元素是近似的特征值。
这种算法成为无移动的QR算法，但是它对于矩阵A的要求很严格（即A为对称矩阵，且满足特征值），即使A是对称矩阵不满足定理的条件时，也可能失败。以及该算法难以做出修改以计算复数特征值，以及迭代速度比较慢。
因此我们需要做出一组改进使得特征值计算更加一般化并加速收敛。
3.上海森伯格
上海森伯格的主要思想是使用上海森伯格形式的相似矩阵替换A，即在QR迭代之前应用相似变换，在A中放置更多的0，同时保持特征值。此外，上海森伯格将消去QR迭代无法收敛到复数特征的问题。
上海森伯格矩阵形式如下图所示：
那么怎么将矩阵A变换成上海森伯格形式呢？Householder变换。
Householder 变换
Householder 变换可以将向量的某些元素变成零，同时保持该向量的范数不变。
通过逐步在矩阵A的左侧和右侧乘上反射子H，从而得到一个具有相同的特征值的特征矩阵。
做3步运算的结果：
左侧为我们得到的上海森伯格矩阵5x5矩阵，由于该矩阵和A相似，它与A具体相同的特征值以及特征值的重数。
一般的对于一个nxn矩阵A，需要n-2个Householder 步将A变成上海森伯格形式。
4.移动QR算法
移动QR算法则是利用幂迭代的技巧大大加速收敛速度。
为了减少计算量，一般先利用Householder矩阵将矩阵A变成拟上三角矩阵（上海森伯格形式）,然后采用双步位移的QR方法计算的特征值。
使用双步位移的QR方法求矩阵A全部特征值的具体算法过程如下：
5.高斯消去与LU分解
高斯消去
高斯消去是求解合适规模的线性方程的有用工具，可以有效地求解具有n个未知数的n个方程。高斯消去主要由两个不等同的部分组成，相对计算代价庞大的消去过程，和相对计算代价小的回代过程。n个方程n个未知数的消去计算，可以在
次操作后完成。
LU分解
LU分解是高斯消去的矩阵形式，它包含把系数矩阵A写做下三角矩阵L和上三角矩阵U的乘积。其中，U矩阵是由传统的高斯消去过程得到上三角矩阵，而对应的L矩阵则是：把1放在主对角线上，然后乘子按消去时它们的特定位置放在下三角矩阵得到。
如何利用LU分解转化回代步骤？
Ax=b ---> LUx=b --->c=Ux Lc=b 求c---> Ux=c 求x
但是，并不是所有的矩阵都可以进行LU分解，我们需要在LU分解前做一些工作：部分主元。
部分主元
部分主元的思想是在每一步消除步骤之前，找到第一列中最大的一个元素，其对应行和主元行进行交换，即PA=LU。文章来源：https://www.toymoban.com/news/detail-714175.html
高斯列主元法的优势在于它有一个选主元的过程，这样做可以避免程序在进行消去操作时选取的主元素为0的情况，也减小了计算的舍入误差，从而提高了程序的普适性和结果的准确性。文章来源地址https://www.toymoban.com/news/detail-714175.html
到了这里，关于《数值分析》-3-特征值与特征矩阵的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
