第8章 矩阵特征值与特征向量的计算.ppt

研究生学位课程数值分析 1 第8章矩阵特征值和特征向量的计算 很多工程计算中 会遇到特征值和特征向量的计算 如 机械 结构或电磁振动中的固有值问题 物理学中的各种临界值等 这些特征值的计算往往意义重大 求解线性方程组的迭代法 重要一点是判断迭代法的收敛性 判断方法之一就是看迭代矩阵的特征值的模是否都小于1 研究生学位课程数值分析 2 PA 是 的高次的多项式 它的求根是很困难的 设法通过数值方法是求它的根 通常对某个特征值 可以用些针对性的方法来求其近似值 若要求所有的特征值 则可以对A做一系列的相似变换 收敛 到对角阵或上 下 三角阵 从而求得所有特征值的近似 n阶方阵A的特征值是特征方程PA det A E 0的根 A的特征向量是齐次线性方程组 A E x 0的非零解 研究生学位课程数值分析 3 定理1 A Rn n 1 n为A的特征值 则 2 A的行列式值等于全体特征值之积 即 1 A的迹数等于特征值之和 即 特征根和特征向量的基本结论 定理2设 为A Rn n的特征值且Ax x 其中x不为0 则 1 c 为cA的特征值 c为常数且不为0 2 p为A pI的特征值 即 A pI x p x 3 k为Ak的特征值 4 设A为非奇异阵 那么且为特征值 即 研究生学位课程数值分析 4 定义设矩阵A B Rn n 若有可逆阵P 使则称A与B相似 定理若矩阵A B Rn n且相似 则 1 A与B的特征值完全相同 2 若x是B的特征向量 则Px便为A的特征向量 研究生学位课程数值分析 5 8 1幂法和反幂法 8 1 1幂法 幂法是用来求矩阵A按模最大的特征值和相应的特征向量的方法 也称为主特征值和主特征向量 设A是单构矩阵 即A有n个线性无关的特征向量 A的n个特征值为 1 2 n 对应的特征向量为 1 2 n线性无关 我们要求 1和 1 幂法的基本思想是取初始非零向量x0 Rn 作迭代xk 1 Axk Ak 1x 0 k 0 1 2 产生迭代序列 xk 由于 1 2 n线性无关 从而有x0 1 1 2 2 n n 8 3 研究生学位课程数值分析 6 故有xk Akx0 1 1k 1 2 2k 2 n nk n 设 1 2 n 这时 上式可写成 若 1 0 则对充分大的k有 因而有 从而特征向量 1 xk 乘幂法的收敛速度取决于 2 1 的大小 研究生学位课程数值分析 7 实际计算时 常把每一步计算的迭代向量xk规范化 对非零向量x 用max x 表示x的按绝对值最大的分量 称向量y x max x 为向量x的规范化向量 例如 设向量x 2 1 5 1 T 则max x 5 y 0 4 0 2 1 0 2 T 可见规范化向量y总满足 y 1 幂法的规范化计算公式为 任取初始向量x0 y0 0 计算 可得 研究生学位课程数值分析 8 所以 其收敛速度由比值 2 1 来确定 又由于 所以 因此 当k充分大时可取 1 mk 1 xk 研究生学位课程数值分析 9 用乘幂法求A的按模最大的特征值和相应特征向量 例8 1设 解取初值x0 y0 1 1 1 T 计算得 可取 1 6 000837 1 1 0 714316 0 249895 T 实际上 A的3个特征值分别为 1 6 2 3 3 2 研究生学位课程数值分析 10 8 1 2加速技术 由于 所以 乘幂法收敛速度取决于比值 2 1 当 2 1 1时 收敛是很慢的 1 Aitken加速方法 由上式可知 可见 序列 mk 线性收敛于 1 构造Aitken序列 会达到加速收敛的目的 研究生学位课程数值分析 11 2 原点位移法 作矩阵B A pE 则B的特征值为qi i p i 1 2 n 而且对应的特征向量相同 如果选取p 使q1仍然是B的按模最大特征值 且满足 则对B应用乘幂法可达到加速收敛的目的 程序见P170 例8 2 研究生学位课程数值分析 12 反幂法是求矩阵按模最小的特征值和相应特征向量的方法 8 1 3反幂法 设A是n阶非奇异矩阵 其特征值为 1 2 n 1 n 0 对应的特征向量为 1 2 n 则有A 1的特征值为 对应的特征向量为 n n 1 1 要想求 n和 n只需对A 1应用乘幂法 任取初始向量x0 y0 0 作 研究生学位课程数值分析 13 也可将上式改写成 式 8 8 称为反幂法 显然有 每一步求xk需要求解线性方程组 可采用LU分解法求解 研究生学位课程数值分析 14 8 9 研究生学位课程数值分析 15 Jacobi方法是求实对称矩阵全部特征值和特征向量的一种矩阵变换方法 8 2Jacobi方法 实对称矩阵A具有下列性质 1 A的特征值均为实数 其对应的特征向量线性无关且两两正交 2 存在正交矩阵Q 使QTAQ diag 1 2 n 而且 Q的第i个列向量恰为 i的特征向量 3 若记A1 QTAQ 则A1仍为对称矩阵 直接找Q不大可能 我们可以构造一系列特殊形式的正交阵Q1 Qn对A作正交变换 使得对角元素比重逐次增加 非对角元变小 当非对角元已经小得无足轻重时 可以近似认为对角元就是A的所有特征值 Jacobi方法就是这样一类方法 研究生学位课程数值分析 16 平面解析几何中的平面坐标旋转变换 表示平面上坐标轴旋转角 的变换 8 2 1平面旋转矩阵 旋转正交相似变换 在三维空间直角坐标系中 ox1y1平面绕着oz1轴旋转 角的坐标变换为 一般地 在n维向量空间Rn中 沿着xiyj平面旋转 角的变换矩阵为 研究生学位课程数值分析 17 称Rij 为平面旋转矩阵或Givens变换矩阵 Rij 具有下列性质 ij 研究生学位课程数值分析 18 研究生学位课程数值分析 19 研究生学位课程数值分析 20 设实对称矩阵A apq n n 记B RijT ARij bpq n n则它们元素之间有如下关系 2 Rij 为正交矩阵 即Rij 1 RijT 3 如果A为对称矩阵 则RijT ARij 也为对称矩阵 且与A有相同的特征值 4 RijT A仅改变A的第i行与第j行元素 ARij 仅改变A的第i列与第j列元素 研究生学位课程数值分析 21 所以有 从而 由上面两式可得 如果aij 0 适当选取角 使 研究生学位课程数值分析 22 只需角 满足 由式 8 15 令t tan 则t满足方程 t2 2dt 1 0 为保证 4 取绝对值较小的根 有 于是 且 研究生学位课程数值分析 23 非对角线元素的平方和 由可知 研究生学位课程数值分析 24 我们有以下的收敛性定理保证上述计算过程 8 2 2Jacobi方法 研究生学位课程数值分析 25 收敛性定理 证 则有 反复利用上式 即得 研究生学位课程数值分析 26 设k充分大时 有 这里需要说明一点 并不是对矩阵A的每一对非对角线非零元素进行一次这样的变换就能得到对角阵 因为在用变换消去的时候 只有第i行 第j行 第i列 第j列元素在变化 如果或为零 经变换后又往往不是零了 因此 Qk RT1RT2 RTk的列向量xj j 1 2 n 为A的近似特征向量 研究生学位课程数值分析 27 的全部特征值 解记A0 A 取i 1 j 2 aij 0 a12 0 2 于是有 例用Jacobi方法计算对称矩阵 从而有 研究生学位课程数值分析 28 所以 再取i 2 j 3 aij 1 a23 1 2 020190 类似地可得 以下依次有 研究生学位课程数值分析 29 从而A的特征值可取为 1 2 125825 2 8 388761 3 4 485401 特征向量为R1TR2T RkT 研究生学位课程数值分析 30 为了减少搜索非对角线绝对值最大元素时间 对经典的Jacobi方法可作进一步改进 1 循环Jacobi方法 按 1 2 1 3 1 n 2 3 2 4 2 n n 1 n 的顺序 对每个 i j 的非零元素aij作Jacobi变换 使其零化 逐次重复扫描下去 直至S A 为止 2 过关Jacobi方法 取单调下降收敛于零的正数序列 k 先以 1为关卡值 依照1中顺序 将绝对值超过 1的非对角元素零化 待所有非对角元素绝对值均不超过 1时 再换下一个关卡值 2 直到关卡值小于给定的精度 研究生学位课程数值分析 31 用Jacobi方法求得的结果精度一般都比较高 特别是求得的特征向量正交性很好 所以Jacobi方法是求实对称矩阵全部特征值和特征向量的一个较好的方法 它的弱点是计算量大 对原矩阵是稀疏矩阵 旋转变换后不能保持其稀疏的性质 一般适用于阶数不高的矩阵 研究生学位课程数值分析 32 8 3QR方法 60年代出现的QR算法是目前计算中小型矩阵的全部特征值与特征向量的最有效方法 实矩阵 非奇异 理论依据 任一非奇异实矩阵都可分解成一个正交矩阵Q和一个上三角矩阵R的乘积 而且当R的对角元符号取定时 分解是唯一的 同理可得 Ak相似于A k 2 3 故他们有相同特征根 研究生学位课程数值分析 33 QR算法的收敛性 定理 设n阶矩阵A的n个特征值满足 n 0 其相应的n个线性无关特征向量为x1 x2 xn 记X x1 x2 xn Y X 如果Y存在LU分解 那么 矩阵序列Ak基本收敛于上三角矩阵R 这里 基本收敛的含义指 Ak 的对角元均收敛 且严格下三角部分的元素均收敛于零 但严格上三角部分的元素没有收敛的要求 定理设n阶矩阵A非奇异实对称矩阵 则矩阵序列 Ak 收敛于对角阵 研究生学位课程数值分析 34 QR方法收敛性 研究生学位课程数值分析 35 QR方法收敛性 研究生学位课程数值分析 36 QR方法运算量很大 为了减少运算量 常在使用QR方法之前把矩阵A简化为拟上三角矩阵 或称之为海森伯格矩阵 次对角元以下的元素全为零 8 3 2化一般矩阵为拟上三角矩阵 形状为 研究生学位课程数值分析 37 为镜面反射矩阵 或Householder变换矩阵 Houholder矩阵H H v 有如下性质 1 2 3 记S为以v为法向量的平面 则几何上x与y Hx关于平面S对称 因为 研究生学位课程数值分析 38 x 据前面定义和性质 有下面的定理 证 研究生学位课程数值分析 39 由此可得 定理得证 研究生学位课程数值分析 40 与平面旋转不同的是 镜面反射变换可成批的消去向量的非零元 程序见P187 研究生学位课程数值分析 41 与平面旋转变换不同的是 镜面反变换可成批的消去向量的非零元 将任意矩阵A简化为海森伯格矩阵的步骤如下 研究生学位课程数值分析 42 研究生学位课程数值分析 43 研究生学位课程数值分析 44 研究生学位课程数值分析 45 研究生学位课程数值分析 46 研究生学位课程数值分析 47 研究生学位课程数值分析 48 研究生学位课程数值分析 49 用Household方法对矩阵A作正交相似变换 使A相似与上Hessenberg阵 算法如下 研究生学位课程数值分析 50 研究生学位课程数值分析 51 用Givens变换对上Hessenberg阵作QR分解 研究生学位课程数值分析 52 研究生学位课程数值分析 53 研究生学位课程数值分析 54 研究生学位课程数值分析