Chapter_特征值和乘幂法方法ppt课件.ppt

第九章矩阵特征值问题的数值方法 Numericalmethodsforeigenvalueproblems 引言 Introduction 工程实践中有多种振动问题 如桥梁或建筑物的振动 机械机件 飞机机翼的振动 工程实践中有多种振动问题 如桥梁或建筑物的振动 机械机件 飞机机翼的振动 及一些稳定性分析和相关分析可转化为求矩阵特征值与特征向量的问题 设A是n阶矩阵 x是非零列向量 如果有数 存在 满足Ax x 那么 称x是矩阵A关于特征值 的特征向量 1特征值与特征向量 Eigenvalueandeigenvector 如果把右端写为 Ix 那么又可写为 I A x 0即 I A 0 记 它是关于参数 的n次多项式 称为矩阵A的特征多项式 其中a0 1 n A 齐次线性方程组 定义1 A的特征值也称为A的特征根 显然 当 是A的一个特征值时 它必然是f 0的根 反之 如果 是f 0的根 那么齐次方程组 I A x 0有非零解向量x 使Ax x成立 从而 是A的一个特征值 矩阵特征值和特征向量有如下主要性质 n阶矩阵A是降秩矩阵的充分必要条件是A有零特征值 设矩阵A与矩阵B相似 那么它们有相同的特征值 n阶矩阵A与AT有相同的特征值 设 i j是n阶矩阵A的两个互异特征值 x y分别是其相应的右特征向量和左特征向量 那么 xTy 0 定理1 定理2 定理3 定理4 2Hermite矩阵特征值问题 设A为n阶矩阵 其共轭转置矩阵记为AH 如果A AH 那么 A称为Hermite矩阵 一 Hermite矩阵的有关性质 设是Hermite矩阵A的n个特征值 有以下性质 全是实数 有相应的n个线性无关的特征向量 它们可以化为一组标准酉交的特征向量组 即 是酉空间中的一组标准酉交基 记U 它是一个酉阵 即UHU UUH I 那么 即A与以为对角元的对角阵相似 A为正定矩阵的充分必要条件是全为正数 设是Hermite矩阵A的n个特征值 那么 因此 又由 得 定理5 证明 如果A的n个特征值为其相应的标准酉交的特征向量为那么有 设A是Hermite矩阵 那么 设x是一个非零向量 A是Hermite矩阵 称为矩阵A关于向量x的Rayleigh商 记为R x 或 定理6 定理7 二 极值定理 极值定理 设Hermite矩阵的n个特征值为 其相应的标准酉交特征向量为 用Ck表示酉空间Cn中任意的k维子空间 那么 或 定理8 矩阵特征值问题的性态是很复杂的 通常分别就单个特征值或整体特征值给出条件数进行分析 对于Hermite矩阵 由于其特征值问题的特殊性质 其特征值都是良态的 下面先证明Hermite矩阵特征值的扰动定理 三 Hermite矩阵特征值问题的性态 矩阵特征值问题与求解线性方程组问题一样 都存在当矩阵A的原始数据有小变化 小扰动 时 引起特征值问题的变化有大有小的问题 如果引起的变化小 称该特征值问题是良态的 反之 称为病态的 扰动定理 设矩阵A E A E都是n阶Hermite矩阵 其特征值分别为 那么 设矩阵A关于特征值 1 2 n的标准酉交特征向量为u1 u2 un 是由ui ui 1 un生成的n i 1维子空间 对中任意非零向量x 由极值定理 有 定理9 证明 由定理 又由定理 对任意x 0 有 从而有 另一方面 A A E E 那么 重复上面的过程 可得 从而有 设矩阵A和A A E都是n阶Hermite矩阵 其特征值分别为和 那么 这个定理表明 扰动矩阵E使A的特征值的变化不会超过 E 2 一般 E 2小 因此 Hermite矩阵特征值是良态的 定理10 乘幂法是适用于求一般矩阵按模最大特征值及相应特征向量的算法 3乘幂法 设A是n阶矩阵 其n个特征值按模从大到小排序为 又假设关于 1 2 n的特征向量v1 v2 vn线性无关 一 乘幂法 任意取定初始向量x0 建立迭代公式 故当k 时 xk 1ka1v1 因此 xk可看成是关于特征值 1的近似特征向量 有一严重缺点 当 1 1 或 1 1时 vk 中不为零的分量将随k的增大而无限增大 计算机就可能出现上溢 或随k的增大而很快出现下溢 因此 在实际计算时 须按规范法计算 每步先对向量xk进行 规范化 迭代格式改为 因为 对任意给定的初始向量x0 类似地 当 1 0时 按模最大特征值 1及其相应的特征向量v1的乘幂法的计算公式 当 1 0时 若 1为A的实重根 幂法仍然有效 试用幂法求按模最大的特征值和相应的特征向量 例1 通过B求 1 p的速度快于通过A求 1的速度 二 加速方法 幂法计算A的特征值 1的收敛速度主要由决定 有特征值 1 p 2 p n p 选择p使 1 p仍为B的主特征值 且满足 求按模最小特征值及相应特征向量的反幂法 又称为反迭代法 4反幂法 反幂法可以求一个非奇异矩阵A的逆矩阵A 1的按模最小的特征值及相应的特征向量 又可以求A的某个近似特征值相应的特征向量 若A非奇异 且Ax x 则A 1x 1x 因此 求A按模最小特征值就是求A 1按模最大特征值 一 i的近似求法 若A有特征值 i i有近似值 先对矩阵进行LU分解 记 半迭代法 的命名也由此而得 二 半迭代法 一种选取特殊的初始向量x0的反幂法 选取初始向量x0满足 x0 1 这时z0 x0 对照上页中的第二个式子 可把z0看成满足Le z0 这里 e 1 1 1 T 而z0的各个分量的取值多少是无关重要的 这样 在第一个迭代步的计算中 只需求解上页中的上三角方程组Ux1 e 假设 例2 试用反幂法求矩阵A最接近于的特征值和相应的特征向量 取 作半迭代 计算结果如表 由于A是对称矩阵 做一次Rayleigh商加速 与精确值 s 2相比 这次加速有较好效果 理论上 实对称矩阵A正交相似于以A的特征值为对角元的对角阵 问题是如何构造这样的正交矩阵呢 Jacobi方法就是通过构造特殊的正交矩阵序列 通过相似变换使A的非对角线元素逐次零化来实现对角化的 5Jacobi方法 一 平面旋转矩阵与相似约化 先看一个简单的例子 设是二阶实对称矩阵 即a21 a12 其特征值为 1 2 容易验证BT B 且 当时 为使RTAR为对角阵 要求b12 b21 0 解之得 一般的n阶平面旋转矩阵 构造一个相似矩阵序列 使 Ak 收敛于一个对角阵 其中Qk为平面旋转矩阵 其旋转角 k由使Ak的绝对值最大元a k pq a k qp 0或按列依次使A的非对角元零化来确定 二 经典的Jacobi方法 设A是实对称矩阵 记A1 A Jacobi方法的基本思想是用迭代格式 Ak 1 QTkAkQk k 1 2 设A是n阶实对称矩阵 那么由Jacobi方法产生的相似矩阵序列 Ak 的非对角元收敛于0 也就是说 Ak 收敛于以A的特征值为对角元的对角 因此 定理11 又由假设 因此 这样 便有 从而 当 循环Jacobi方法必须一次又一次扫描 才能使 Ak 收敛于对角阵 计算量很大 在实际计算中 往往用一些特殊方法来控制扫描次数 减少计算量 减少阈值的方法通常是先固定一个正整数M n 扫描一次后 让 而阈值的下界是根据实际问题的精度要求选定的 三 实用的Jacobi方法 下面介绍一种应用最为广泛的特殊循环Jacobi方法 阈Jacobi方法 阈Jacobi方法首先确定一个阈值 在对非对角元零化的一次扫描中 只对其中绝对值超过阈值的非对角元进行零化 当所有非对角元素的绝对值都不超过阈值后 将阈值减少 再重复下一轮扫描 直至阈值充分小为止 当Ak 1的非对角元素充分小 Qk的第j列qj可以看成是近似特征值a k 1 jj相应的特征向量了 四 用Jacobi方法计算特征向量 假定经过k次迭代得到Ak 1 RTk RT1AR1 Rk 这时Ak 1是满足精度要求的一个近似的对角阵 记Qk R1R2 Rk Qk 1Rk 则 Qk是一个正交矩阵 Ak 1 QTkAQk 在实际计算中 把Qk看成是Qk 1右乘一个平面旋转矩阵得到 不妨记Q0 I Qk的元素按下式计算 理论上 一个实对称矩阵正交相似于一个以其特征值为对角元的对角阵 但是 经典的结果告诉我们 一个大于4次的多项式方程不可能用有限次四则运算求根 因此 我们不可能期望只用有限次相似变换将一个实对称矩阵约化为一个对角阵 下面先介绍将一个实对称矩阵相似约化为实对称三对角矩阵的方法 再讨论求其特征值的对分法 6对分法 一 相似约化为实对称三对角矩阵 将一个实对称矩阵正交相似约化为一个实对称三对角矩阵的算法 可归纳如下 记A 1 A 对k 1 2 n 2 二 Sturm序列的性质 设实对称三对角矩阵为 其中 i 0 i 1 2 n 1 多项式序列 pi i 0 1 n 称为Sturm序列 记T I的第i阶主子式为 其特征矩阵为T I 定义2 令p0 1 p1 1 pi i pi 1 2i 1pi 2 i 2 3 n pi 是i阶实对称矩阵的特征多项式 因此 pi i 1 2 n 的根全是实根 设 是pi 的一个根 那么 pi 1 pi 1 0 即相邻的两个多项式无公共根 pi 1 pi 1 0 即pi 1 与pi 1 反号 pi 的根都是单根 并且将pi 1 的根严格隔离 pi i 1 2 n 的根都是实根 当i为奇数 当i为偶数 定理12 证明 定理13 定理14 定理15 三 同号数和它的应用 设p0 1 pi i 1 2 n 是一个Sturm序列 称相邻的两个数中符号一致的数目为同号数 记为ai 若某个pi 0 规定与pi