[摘记]数值方法09——特征系统

注：以下来自《C++数值算法一书》，仅对章节内容做摘要，为的是给自己扫盲，不涉及算法。

一个N*N阶矩阵A如果满足下式，则它具有一个特征向量x和相应的特征值λ：

需要满足下式：

展开之后得到λ的N阶多项式，其根就是特征值。总存在N个特征值，由于重根的相同特征值被称为退化。

（本章涉及很多很多线性代数知识，楼主线代不好，可能写着写着晕掉了）

1. 对称矩阵的雅可比变换

思想，雅可比方法是由一系列形如

的正交相似变换组成，每一步变换用来将某一非对角元素零化的平面旋转。如此变化累积起来，就得到特征向量的矩阵：，而最终得到对角化矩阵的对角元素就是特征值。

2. 将对称矩阵约化为三对角形式：Givens约化和Householder约化

思想：寻找特征值和特征向量的最优策略是，首先将矩阵化成一个简单的形式，在开始一个迭代过程。对于对称矩阵来说，最好的简单形式是三对角形式。Givens约化是对雅可比方法的一个改进。当把矩阵化简为三对角形式时就停止运算，而不是一直到化为对角形式。这样使得整个过程在有限步内完成，而不是像雅可比方法那样一直迭代到收敛。

Householder方法用n-2个正交变换将n*n的对称矩阵A约化为三对角矩阵。每次变换将一整行和一整列中的相应元素化为0。

3. 三对角矩阵的特征值和特征向量

思想：一旦得到了三对角矩阵，确定它的特征值的一种可能途径就是直接寻找特征值多项式的根，用之前学过的求根方法迭代处理。如果只需要计算一小部分特征值和特征向量，使用QR或者QL算法则更有效。

QR将矩阵A分解为一个正交矩阵Q和一个上三角矩阵R，而QL将矩阵A分解为一个正交矩阵Q和一个下三角矩阵L。QL算法比QR算法的舍入误差小。QL算法对于一般矩阵的运算量是每次迭代O(n^3)，这运算量太大，但它对于三对角矩阵每次迭代运算量只有O(n)，对于Hessenberg矩阵是O(n^2)。

4. 埃尔米特矩阵

思想：埃尔米特矩阵可以用雅可比变换寻找特征值与特征向量，也可以用Householder方法约化后进行QL分解。

5. 将一般矩阵化为Hessenberg形式

思想：对于一般矩阵（非对称矩阵），将其约化为一种简单的形式，然后对这个简单的形式进行某种迭代。这里所说的简单形式，就是Hessenberg形式。

可以采用高斯选主元的消去法得到矩阵的Hessenberg形式。

6. 实Hessenberg矩阵的QR算法

思想：带有位移的QR算法

7. 用逆迭代法改进特征值并求解特征向量

思想：令y是如下线性系统的解：

其中b是一个随机向量，而τ是靠近A的某一特征值λ，则y接近λ所对应的特征向量。这一过程可迭代进行：用y替代b并解出新的y，新的y更接近真实的特征向量。

本文原创，转载请注明出处

http://www.cnblogs.com/luluathena/