数值分析示范.pdf

数值分析实验 ——迭代计算矩阵全部特征值 杜知方 摘要 本报告介绍了迭代的算法原理及设计，检验了使用 Matlab 实现的迭代求矩阵全 部特征值的程序，验证了其计算各类矩阵的性能。 迭代原理涉及到矩阵相似变换、投影变换、特征子空间迭代与正交分解等多方面代 数学原理，是计算矩阵特征值的非并行算法中最主要的一种，可以以令人满意的精度算计几 乎各类矩阵的全部特征值。 实验首先对一随机矩阵进行了计算，分析了收敛过程，并与 Matlab 内置的特征值计算 函数计算结果进行了比较，相对误差为5.1932 × 10−15 ，同时用时仅为0.011秒。本节还计算 了3000阶方阵的特征值，用时825.2秒。在内存允许的情况下程序可算计大至5000阶方阵的 特征值，只是时间开消会更大。 当矩阵模长最大的两个特征值模长接近时，幂迭代性能非常差。本实验通过计算一个有 重特征值但非秩亏矩阵验证了迭代解决这类问题的性能。算法的精度仍然非常高，绝对 误差仅为6.6992 × 10−15 。 由于迭代的算法原理涉及特征子空间迭代，因此秩亏矩阵对本算法属于“坏问题”。 用矩阵特征值代数重数与几何重数的差值来衡量矩阵的矩亏程度。本次实验验证了程序在计 算秩亏矩阵时的性能，程序计算了一个秩亏程度为5 的矩阵的特征值，算法绝对误差为 0.0039395，大于非秩亏矩阵计算的结果。但精度高于Matlab 内置的特征值计算函数。 观察上一节计算结果发现矩阵不秩亏的两个特征值计算误差依然非常小，由此提出算法 误差与矩阵的秩亏程度大致成负相关。实验计算了秩亏程度为4和3的两个矩阵的特征值， 计算结果的绝对误差分别为2.0012 × 10−5和1.0555 × 10−5 ，计算结果符合了上述猜测。 最后实验更细致地考察了程序计算时间、迭代次数以及残差向量范数与矩阵的秩亏程度 的关系，发现三项指标均与矩阵的秩亏程度成负相关的关系。并且计算时间与迭代次数均在 可接受的范围内，而残差向量的范数在秩亏程度小于9时比较令人满意。 一、线性代数 使用幂法求矩阵绝对值最大的特征值原理简单，但效率低下，局限性大。算法只有在矩 阵有唯一绝对值最大特征值时才会收敛。即使这个条件满足，但当两个特征值模长接近时算 法的效率将变得非常低。而且在实践中我们经常需要求出一个矩阵的全部特征值（甚至往往 是复特征值）。这就要求一种更加强大高效的算法。而在并行计算模式出现前，迭代一直 占据着这一地位。 为了建立迭代算法，我们需要大量数学知识。 1.1 显示矩阵全部特征值的标准型 一个一般矩阵的特征值总是不容易看出来的，但是有些特殊形式的矩阵拥有这个性质。 1.1.1 对角形、三角形矩阵的全部特征值就是它对角线上的全部元素。 1.1.2 矩阵的特征值是相似不变量，即相似矩阵的特征值相同[1]。 ( ) 容易验证相似变换是 上的线性变换。基于上面两个定理，我们希望设计一种算法， 把矩阵通过相似变换化为显示出它全部特征值的形式。 1.1.3 任意矩阵 ∈ ()可以通过相似变换化为对角形当且仅当它有 个线性无关的 特征向量[2]。 这个条件问题不容易满足的，但是我们还有一个关于三角形矩阵的另外的一个结论。 1.1.4 任意矩阵 ∈ () 总可以通过相似变换化为上三角形。这个上三角形矩阵称为A 的Schur 标准形[3]。 然而这个结果仍然不是十分让人满意。因为大多数情况下，我们需要处理实数矩阵，我 们希望运行也是在实数下进行的，因为同样的计算量，复数形式消耗的时候是实数形式的四 倍左右。上一定理在数下有如下形式： 1.1.4 任意矩阵 ∈ () 总可以通过相似变换化为如下矩阵 1 ∗