矩阵特征值问题.pdf

特征值问题特征值问题 1 特征值问题是线性代数的研究重点 在理论和应 用上都非常重要 理论上 矩阵的特征值就是线性算子的谱 因此 可以从泛函分析里找到理论的支撑和生长点 应用上 常微分方程 特征值问题是线性代数的研究重点 在理论和应 用上都非常重要 理论上 矩阵的特征值就是线性算子的谱 因此 可以从泛函分析里找到理论的支撑和生长点 应用上 常微分方程 ODE 和偏微分方程和偏微分方程 PDE 中 许多问题都可以转化为矩阵特征值问题 矩阵特征值问题的算法也是高性能计算机的主要 计算任务之一 可大致分为求解稠密 中小型矩 阵全部特征值的变换类方法和求解稀疏 大型矩 阵部分特征值的投影类方法 中 许多问题都可以转化为矩阵特征值问题 矩阵特征值问题的算法也是高性能计算机的主要 计算任务之一 可大致分为求解稠密 中小型矩 阵全部特征值的变换类方法和求解稀疏 大型矩 阵部分特征值的投影类方法 2 1 特征值的估计 特征值的估计 由于工程计算中求矩阵尤其是高阶矩阵的 精确特征值通常比较困难 而许多情况下我们 只需要知道特征值在什么范围内变化或者落在 什么区域内 例如判断方阵的幂级数是否收敛 只要看方阵的特征值的模或谱半径是否小于 由于工程计算中求矩阵尤其是高阶矩阵的 精确特征值通常比较困难 而许多情况下我们 只需要知道特征值在什么范围内变化或者落在 什么区域内 例如判断方阵的幂级数是否收敛 只要看方阵的特征值的模或谱半径是否小于1 因此特征值的估计就显得尤其必要 这方面的 理论在特征值问题中相当经典 因此特征值的估计就显得尤其必要 这方面的 理论在特征值问题中相当经典 3 工程计算中 求解特征值问题工程计算中 求解特征值问题 一 从特征值问题的稳定性说起一 从特征值问题的稳定性说起 的解 这里的解 这里 的特征对时 由于数据往往带有误差 因此我们计算出的特征对 实际上是 扰动后的特征值问题 的特征对时 由于数据往往带有误差 因此我们计算出的特征对 实际上是 扰动后的特征值问题 4 由于矩阵的特征多项式的系数是矩阵元素的连 续函数 而多项式的根都是其系数的连续函数 因此矩阵的特征值作为特征多项式的零点都连 续地依赖于矩阵的元素 因此矩阵元素的连续 变化时 必有对应特征值的连续变化 我们希望知道矩阵元素的变化对特征对的影响 由于我们一般只知道或的某个上界 因此有必要研究如何利用这样的上界 尽可能 准确地估计与 与之间的差距 从 而可确定特征值问题的稳定性 由于矩阵的特征多项式的系数是矩阵元素的连 续函数 而多项式的根都是其系数的连续函数 因此矩阵的特征值作为特征多项式的零点都连 续地依赖于矩阵的元素 因此矩阵元素的连续 变化时 必有对应特征值的连续变化 我们希望知道矩阵元素的变化对特征对的影响 由于我们一般只知道或的某个上界 因此有必要研究如何利用这样的上界 尽可能 准确地估计与 与之间的差距 从 而可确定特征值问题的稳定性 5 下述定理是特征值的这种连续性的定量分析 定理1 下述定理是特征值的这种连续性的定量分析 定理1 Ostrowski 设矩阵 的特征值分别为 令 设矩阵 的特征值分别为 令 1 对的任意特征值 存在的特 征值 使得 1 对的任意特征值 存在的特 征值 使得 2 存在的排列 使得 2 存在的排列 使得 6 遗憾的是矩阵的特征向量一般不是矩阵元素的 连续函数 因此不一定是稳定的 遗憾的是矩阵的特征向量一般不是矩阵元素的 连续函数 因此不一定是稳定的 例 2 例 2 矩阵 的特征值为 特征向量为 和 而的特征值为 特征向量为和 矩阵的 特征向量在处不连续 矩阵 的特征值为 特征向量为 和 而的特征值为 特征向量为和 矩阵的 特征向量在处不连续 7 二 盖尔 二 盖尔 Gerschgorin 定理 定理 把矩阵分裂成把矩阵分裂成 我们有理由猜测 如果足够小 的特征 值将位于的特征值 即元素 的某些小邻域内 我们有理由猜测 如果足够小 的特征 值将位于的特征值 即元素 的某些小邻域内 构造的扰动矩阵 显然构造的扰动矩阵 显然 8 定义3对方阵 称定义3对方阵 称 为矩阵的行盖尔 为矩阵的行盖尔 Gerschgorin 圆 称并 集为矩阵的行盖尔 圆 称并 集为矩阵的行盖尔 Gerschgorin 区域 这里区域 这里 类似地 可定义矩阵的列盖尔圆 类似地 可定义矩阵的列盖尔圆 9 定理4定理4 Gerschgorin 对方阵对方阵 1 矩阵的特征值都位于其行盖尔区域内 1 矩阵的特征值都位于其行盖尔区域内 2 若矩阵有个盖尔圆构成的并集是 连通区域 并且与其余个盖尔圆均不相 交 则中恰好有的个特征值 2 若矩阵有个盖尔圆构成的并集是 连通区域 并且与其余个盖尔圆均不相 交 则中恰好有的个特征值 10 1 的证明 的证明 设有特征对 这里 则设有特征对 这里 则 令 则 因此令 则 因此 从而从而 11 例 5 例 5 矩阵 的三个行 矩阵 的三个行Gerschgorin圆分别是 圆分别是 12 Wilkson在名著 代数特征值问题 中 先将矩 阵变换成 在名著 代数特征值问题 中 先将矩 阵变换成Jordan标准型 再用标准型 再用Gerschgorin定理 和对角相似变换 对不同特征值结构的特征值 问题进行了细致的扰动分析 定理 和对角相似变换 对不同特征值结构的特征值 问题进行了细致的扰动分析 因为相似变换不改变特征值 为了得到特征值 的更加准确的估计 因为相似变换不改变特征值 为了得到特征值 的更加准确的估计 Gerschgorin发现可以将矩 阵变换为其相似矩阵 以减少 发现可以将矩 阵变换为其相似矩阵 以减少 Gerschgorin圆的半径 达到隔离圆的半径 达到隔离Gerschgorin 圆的目的 为计算方便 常常取为对角矩阵圆的目的 为计算方便 常常取为对角矩阵 13 例 6 例 6 矩阵 经过对角相似变换后 得 矩阵 经过对角相似变换后 得 14 三个行三个行Gerschgorin圆分别收缩为 圆分别收缩为 15 定义7对方阵 如果定义7对方阵 如果 Gerschgorin定理与对角占优矩阵有密切关系 定理与对角占优矩阵有密切关系 则称矩阵为按行严格对角占优矩阵 则称矩阵为按行严格对角占优矩阵 则称矩阵为按行对角占优矩阵 如果则称矩阵为按行对角占优矩阵 如果 16 定理8定理8 Levy Desplanques 严格对角占优矩阵是可逆矩阵 的元素 严格对角占优矩阵是可逆矩阵 的元素 证明 证明 令 则矩阵令 则矩阵 因此 所以矩阵 可逆 即矩阵可逆 因此 所以矩阵 可逆 即矩阵可逆 17 根据定理8 严格对角占优矩阵没有零特 征值 而 根据定理8 严格对角占优矩阵没有零特 征值 而 由此 我们可以将由此 我们可以将Gerschgorin定理看成定理定理看成定理8 的 推论 这说明矩阵的特征值可能满足 的 推论 这说明矩阵的特征值可能满足 18 因此矩阵严格对角占优 根据定理因此矩阵严格对角占优 根据定理8 事实上 设矩阵的特征值不属于的事实上 设矩阵的特征值不属于的 Gerschgorin区域 则有区域 则有 这与是的特征值相矛盾 这与是的特征值相矛盾 历史上历史上Gerschgorin定理的确是从 严格对角占 优矩阵是非奇异的 这一事实推导出来的 定理的确是从 严格对角占 优矩阵是非奇异的 这一事实推导出来的 19 除了除了Gerschgorin区域外 区域外 Brauer发现优美的发现优美的 Cassini椭圆形也可以用于估计特征值 椭圆形也可以用于估计特征值 定理9定理9 Brauer 方阵的任意 特征值都位于个 方阵的任意 特征值都位于个Cassini椭圆 形的并集内 即 椭圆 形的并集内 即 20 21 三 特征值的界三 特征值的界 首先 根据矩阵的首先 根据矩阵的Cartesian分解 有分解 有 这里都 是 这里都 是Hermite矩阵 矩阵 如果 则是如果 则是Hermite矩阵 特征值 全为实数 当的元素在 矩阵 特征值 全为实数 当的元素在0附近变化时 的 特征值出现复数 因此矩阵可用于确定矩 阵的特征值的虚部变化范围 附近变化时 的 特征值出现复数 因此矩阵可用于确定矩 阵的特征值的虚部变化范围 22 1 1 定理10定理10 Schur 设的特征值为 则设的特征值为 则 2 2 3 这里 3 这里 并且当且仅当是正规矩阵时 等号成立 并且当且仅当是正规矩阵时 等号成立 23 1 的证明 的证明 设的设的Schur分解为 上三角阵 的主对角元就是 矩阵的特征值 所以根据 分解为 上三角阵 的主对角元就是 矩阵的特征值 所以根据F 范数的酉不变性 有 范数的酉不变性 有 24 2 的证明 的证明 由于 因此由于 因此 25 在上述证明中 当且仅当是正规矩阵时 上三角阵为对角矩阵 即 因此等号都成立 在上述证明中 当且仅当是正规矩阵时 上三角阵为对角矩阵 即 因此等号都成立 26 1 1 推论11推论11 Hirsch 对的任意特征值 有对的任意特征值 有 2 2 3 3 27 1 的证明 的证明 因此因此 28 例 12 例 12 矩阵 按推论 矩阵 按推论11所得特征值的变化范围为带型区域 所得特征值的变化范围为带型区域 这个结果显然比相应的这个结果显然比相应的Gerschgorin区域差 区域差 29 2 多项式特征值问题 多项式特征值问题 多项式特征值问题在多项式特征值问题在Matlab中可分别利用中可分别利用 Matlab函数函数eig eigs Polyeig等来解决 所涉 及的算法主要还是变换类算法 核心思想就是 通过各类变换尤其是相似变换将高阶特征值问 题转化为低阶特征值问题 例如 等来解决 所涉 及的算法主要还是变换类算法 核心思想就是 通过各类变换尤其是相似变换将高阶特征值问 题转化为低阶特征值问题 例如QEP可以线性 化为 可以线性 化为GEP再转化为再转化为SEP来求解 因此这些函数 比较适合于稠密 中小型的矩阵 来求解 因此这些函数 比较适合于稠密 中小型的矩阵 30 标准特征值问题标准特征值问题 SEP 即为 即为 一 从矩阵的视角看特征值问题一 从矩阵的视角看特征值问题 类似地 我们有二次特征值问题类似地 我们有二次特征值问题 QEP 按此视角 广义特征值问题按此视角 广义特征值问题 GEP 即为 即为 31 这里系数矩阵为矩阵 将矩阵元素即 多项式的次数推广到次 可得多项式特征值 问题 这里系数矩阵为矩阵 将矩阵元素即 多项式的次数推广到次 可得多项式特征值 问题 PEP 更进一步 从线性推广到非线性 我们有非线 性特征值问题 更进一步 从线性推广到非线性 我们有非线 性特征值问题 NEP NEP的主要算法都是基于求解非线性方程组的的主要算法都是基于求解非线性方程组的 Newton法及其变体 目前尚不成熟 法及其变体 目前尚不成熟 32 二 广义特征值问题二 广义特征值问题 结构动力分析 信号处理 通信等学科中经常 需要求解广义特征值 结构动力分析 信号处理 通信等学科中经常 需要求解广义特征值 对于稠密 低阶的矩阵 理论上可采用 等价变换将 对于稠密 低阶的矩阵 理论上可采用 等价变换将GEP转化为转化为SEP 例如逆变换 例如逆变换 Cayley变换等谱变换方法 对于稀疏大型矩阵 则用 变换等谱变换方法 对于稀疏大型矩阵 则用Arnoldi Lanczos等投影类解法 等投影类解法 33 例 1 广义特征值问题的直接变换法例 1 广义特征值问题的直接变换法 对于广义特征值问题 可以两边 做的逆变换 将之转化为 对于广义特征值问题 可以两边 做的逆变换 将之转化为SEP 这种方法的优点是特征向量不变 但缺点是矩 阵奇异时不能使用 并且当矩阵是正定 这种方法的优点是特征向量不变 但缺点是矩 阵奇异时不能使用 并且当矩阵是正定 Hermite阵时 矩阵一般不再是对称矩阵 因此不是保结构的算法 从而使计算复杂 阵时 矩阵一般不再是对称矩阵 因此不是保结构的算法 从而使计算复杂 34 例 2 广义特征值问题的位移求逆法例 2 广义特征值问题的位移求逆法 对于广义特征值问题 可以通过 适当选择位移 对于广义特征值问题 可以通过 适当选择位移 shift 或极点 或极点 pole 再通过 求逆 将之转化为 再通过 求逆 将之转化为SEP 这种方法的优点是特征向量不变 矩阵奇 异时也可以使用 并且在求解邻近的特征 值或绝对值很小的特征值时效率较高 缺点仍 然是一般不是特殊矩阵 这种方法的优点是特征向量不变 矩阵奇 异时也可以使用 并且在求解邻近的特征 值或绝对值很小的特征值时效率较高 缺点仍 然是一般不是特殊矩阵 35 例 3 广义特征值问题的例 3 广义特征值问题的Cayley变换法变换法 这种方法实质上仍然是位移求逆法 这种方法实质上仍然是位移求逆法 SI 对于广义特征值问题 如果已经 得到特征值的近似值 那么通过 对于广义特征值问题 如果已经 得到特征值的近似值 那么通过Cayley变换 可以将之转化为 变换 可以将之转化为SEP 显然显然 36 例 4 广义特征值问题的例 4 广义特征值问题的Cholesky分解法分解法 对于广义特征值问题 当是正 定 对于广义特征值问题 当是正 定Hermite矩阵时 可以通过矩阵时 可以通过Cholesky分解分解 将之转化为将之转化为SEP 矩阵仍然是矩阵仍然是Hermite矩阵 因此此算法是保 结构算法 并且说明特征值全是实数 矩阵 因此此算法是保 结构算法 并且说明特征值全是实数 37 设是广义特征值问题的 特征对 是标准特征值问题 的特征对 因为矩阵是 设是广义特征值问题的 特征对 是标准特征值问题 的特征对 因为矩阵是Hermite阵 所以有 完备的标准正交特征向量系 如果都是单 位特征向量 那么 阵 所以有 完备的标准正交特征向量系 如果都是单 位特征向量 那么 38 又由于又由于 所以 这说明 广义特征向量对矩阵是加权正 交的 或称特征向量矩阵是加权正交 所以 这说明 广义特征向量对矩阵是加权正 交的 或称特征向量矩阵是加权正交 共轭共轭 的 的 这说明 广义特征向量对矩阵是正交的 或称特征向量矩阵是正交 这说明 广义特征向量对矩阵是正交的 或称特征向量矩阵是正交 共轭共轭 的的 由于由于 39 这样 对任意 可得这样 对任意 可得 由于特征向量相互正交 因此它们也可以看 成维内积空间的一组基 只是内积空间 的内积必须定义为内积 即 由于特征向量相互正交 因此它们也可以看 成维内积空间的一组基 只是内积空间 的内积必须定义为内积 即 因此得展开式因此得展开式 40 例 5 广义特征值问题的同时合同对角化例 5 广义特征值问题的同时合同对角化 对于广义特征值问题 如果 均为 对于广义特征值问题 如果 均为Hermite矩阵 并且还是正定矩阵 那 么存在可逆矩阵 使得 矩阵 并且还是正定矩阵 那 么存在可逆矩阵 使得 这里是原广义特征值问 题的特征值 这里是原广义特征值问 题的特征值 41 证明 证明 由于是由于是Hermite正定矩阵 所以有正定矩阵 所以有 再根据是再根据是Hermite矩阵 所以有酉相似矩阵 所以有酉相似 令 则有令 则有 42 因此 最后根据 得 因此 最后根据 得 这说明是的特征值 因此也是 广义特征值的特征值 这说明是的特征值 因此也是 广义特征值的特征值 43 例 6 基于广义例 6 基于广义Schur分解的分解的QZ算法算法 对于广义特征值问题 我们的目标 是寻找可逆矩阵 使得 对于广义特征值问题 我们的目标 是寻找可逆矩阵 使得 均为标准型 我们称与是等 价的 注意到等价矩阵的特征对之间的关系 均为标准型 我们称与是等 价的 注意到等价矩阵的特征对之间的关系 44 虽然矩阵束也存在与虽然矩阵束也存在与Jordan标准型类似 的 标准型类似 的Weierstrass标准型及标准型及Kronecher标准型 但也 同 标准型 但也 同Jordan标准型一样 在数值计算上存在困难 从数值观点看 更吸引人的是 标准型一样 在数值计算上存在困难 从数值观点看 更吸引人的是Moler和和Stewart 1973 提出的广义 1973 提出的广义Schur分解 分解 对矩阵 存在酉矩阵 使得对矩阵 存在酉矩阵 使得 是上三角矩阵 是上三角矩阵 45 我们知道 在矩阵的我们知道 在矩阵的Schur分解中 上三角的对角元就是的特征值 分解中 上三角的对角元就是的特征值 在广义在广义Schur分解中 类似地 当时有 分解中 类似地 当时有 问题是当以及时 前 者出现所谓的 无穷特征值 即 后者的特征值则可取任意复数 即特征值的集 合 问题是当以及时 前 者出现所谓的 无穷特征值 即 后者的特征值则可取任意复数 即特征值的集 合 46 求解求解GEP的的QZ算法分三步 算法分三步 1 1 Hessenberg Triangular约化 即通过酉变 换先将化为上 约化 即通过酉变 换先将化为上Hessenberg矩阵 将化 为上三角阵 矩阵 将化 为上三角阵 2 2 QZ迭代 即对使用一步位移迭代 即对使用一步位移QR迭 代 将化为上三角阵或准上三角阵 同 时将化成上三角阵 这是本算法的核心 部分 迭 代 将化为上三角阵或准上三角阵 同 时将化成上三角阵 这是本算法的核心 部分 3 计算的特征对 并据此求出原 3 计算的特征对 并据此求出原 GEP的特征对 的特征对 47 3 Rayleigh商和广义商和广义Rayleigh商商 在物理 信息等学科及理论研究中 经常会遇 到 在物理 信息等学科及理论研究中 经常会遇 到Hermite矩阵的二次型函数的商的最大化或 最小化 这种商包括一个 矩阵的二次型函数的商的最大化或 最小化 这种商包括一个Hermite矩阵的矩阵的 Rayleigh商和两个商和两个Hermite矩阵的广义矩阵的广义Rayleigh 商 商 L Rayleigh在在1930年代研究振动系统的小 振荡时 为了找到合适的广义坐标 提出的一 种特殊形式的商 被后人称为 年代研究振动系统的小 振荡时 为了找到合适的广义坐标 提出的一 种特殊形式的商 被后人称为Rayleigh商 商 48 一 一 Rayleigh商商 二次型 如果存在 那么二次型 如果存在 那么 所以如果 我们自然也希望所以如果 我们自然也希望 49 定义1 设是定义1 设是Hermite矩阵 称矩阵 称 为矩阵的为矩阵的Rayleigh商 商 注意到注意到 因此我们可以把对的极性的讨论限定 在单位球面上 因此我们可以把对的极性的讨论限定 在单位球面上 50 单位球面是闭集 又因为是的连续 函数 因此根据多元函数的最值定理 在上存在最大值和最小值 由于特征值与 单位球面是闭集 又因为是的连续 函数 因此根据多元函数的最值定理 在上存在最大值和最小值 由于特征值与 Rayleigh商的关系 我们自然猜测 这些最值 与矩阵的特征值有什么关系 商的关系 我们自然猜测 这些最值 与矩阵的特征值有什么关系 51 可以证明 可以证明 Rayleigh商是商是Hermite特征值问题的 最佳逼近 即对任意 有 特征值问题的 最佳逼近 即对任意 有 因为由因为由 以及以及 所以有所以有 52 由于是由于是Hermite矩阵 因此设有谱分解矩阵 因此设有谱分解 这里是酉矩阵 并且假定 那么 这里是酉矩阵 并且假定 那么 53 所以所以 定理2 定理2 Rayleigh Ritz 设是设是Hermite 矩阵 其特征值为 则矩阵 其特征值为 则 54 其余特征值是否有类似结论呢 其余特征值是否有类似结论呢 设 并假定 即设 并假定 即 由于 因此前面的证明可修改为由于 因此前面的证明可修改为 55 类似地 假定 即类似地 假定 即 由于 因此前面的证明可修改为由于 因此前面的证明可修改为 56 综上 一般地 我们有综上 一般地 我们有 定理3 设是定理3 设是Hermite矩阵 其特征 值为 相应的标准正交特征向 量为 令 矩阵 其特征 值为 相应的标准正交特征向 量为 令 则则 57 遗憾的是 定理2中的公式实用价值不大 因为 它们将的计算限定在求 遗憾的是 定理2中的公式实用价值不大 因为 它们将的计算限定在求Rayleigh商在的局 部极值上 因此必须先求出 这在数值上是 比较困难的 商在的局 部极值上 因此必须先求出 这在数值上是 比较困难的 由于实际上是的 一个维子空间 因此我们希望将 搜索极值的空间放大到任意维子空 间 而增大后的集合的极大值不会比原集 合的小 极小值也不会比原集合大 由于实际上是的