共轭梯度法及其基本性质

共轭梯度法及其基本性质共轭梯度法及其基本性质 预备知识预备知识 定义定义 1 1 设设是对称正定矩阵 称是对称正定矩阵 称是是 A A 共轭的 是指共轭的 是指 性质性质 1 1 设有设有是彼此共轭的是彼此共轭的维向量 即维向量 即 则则一定是线性无关的 一定是线性无关的 证明 证明 若有一组数满足 则对一切一定有 注意到 由此得出 即所有的 因此 是线性无关的 性质 性质 设向量设向量是线性无关的向量组 则可通过它们的线性组是线性无关的向量组 则可通过它们的线性组 合得出一组向量合得出一组向量 而 而是两两共轭的 是两两共轭的 证明 我们用构造法来证实上面的结论 取 令 取 m 令 取 容易验证 符合性质 的要求 性质 设性质 设是两两 共轭的 是两两 共轭的 是任意指定的向量 那么是任意指定的向量 那么 从从出发 逐次沿方向出发 逐次沿方向搜索求搜索求的极小值 所得的极小值 所得 序列序列 满足 满足 证明 由下山算法可知 从出发 沿方向搜索 获得 从而 性质 设性质 设是两两 共轭的 则从任意指定的是两两 共轭的 则从任意指定的出发 依出发 依 次沿次沿搜索 所得序列搜索 所得序列满足 满足 其中 其中是方程组是方程组 5 1 1 5 1 1 的解 的解 证明 是性质 的直接推论 显然成立 由于是两两 共轭的 故是线性无关 的 所以对于向量可用线性表出 即存在一组数 使 由于及 得出 于是 再由得出 于是 与得出一样地 我们可以陆续得出 对比和的表达式可知 证明完毕证明完毕 性质 是性质 的直接推论 但它给出了一种求 的算法 这种 算法称之为共轭方向法 结合性质 我们可以得到如下的性质 性质 设性质 设是是上的一组线性无关的向量 则从任意指定的上的一组线性无关的向量 则从任意指定的 出发 按以下迭代产生的序列出发 按以下迭代产生的序列 取 取 计算 计算 取 取 计算计算 得出 得出 如此进行下去 直到第如此进行下去 直到第 n n 步 步 n n 计算 计算取取 计算计算 得出 得出 显然 显然 根据性质 可知 不论采用什么方法 只要能够构造不论采用什么方法 只要能够构造个两两 共轭的向量个两两 共轭的向量 作为搜索方向 从任一初始向量出发 依次沿两两 共轭的方向进行搜索 经作为搜索方向 从任一初始向量出发 依次沿两两 共轭的方向进行搜索 经 步迭代后 便可得到正定方程组步迭代后 便可得到正定方程组的解 的解 共轭梯度法共轭梯度法 算法步骤如下 预置步 任意 计算 并令取 指定算法终 止常数 置 进入主步 主步 如果 终止算法 输出 否则下行 计算 计算 置 转入 定理 定理 2 1 2 1 由共轭梯度法得到的向量组由共轭梯度法得到的向量组和和具有如下性质 具有如下性质 其中 其中 5 2 15 2 1 通常称之为通常称之为 KrylovKrylov 子空间子空间 证明 用归纳法 当时 因为 因此定理的结论成立 现在假设定理的结论对成立 我们来证明其对 也成立 利用等式及归纳假设 有 又由于 故定理的结论 对成立 利用归纳假定有 而由 所证知 与上述子空间正交 从而有定理的结论 对 也成立 利用等式 和 并利用归纳法假定和 所证之结论 就有 成立 而由的定义得 这样 定理的结论 对也成立 由归纳法假定知 进而 于是 再注意到 和 所证的结论表明 向量组和 都是线性无关的 因此定理的结论 对同样成立 定理证毕定理证毕 定理 5 2 1 表明 向量和分别是 Krylov 子空间 的正交基和共轭正交基 由此可见 共轭梯度法最多步便可得到 方程组的解 因此 理论上来讲 共轭梯度法是直接法 定理定理 5 2 25 2 2 用共轭梯度法计算得到的近似解用共轭梯度法计算得到的近似解满足满足 5 2 5 2 或或 5 2 5 2 其中其中 是方程组是方程组的解 的解 是由 是由 5 2 15 2 1 所定 所定 义的义的 KrylovKrylov 子空间 子空间 证明证明 注意到 则 5 2 2 和 5 2 3 是等价的 因此我们下面只证明 5 2 3 成立 假定共轭梯度法计算到 步出现 那么有 此外 对计算过程中的任一步 有 设是属于的任一向量 则由定理 5 2 1 的 知 可 以表示为 于是 而 再利用定理 5 2 1 的 就可以推出 于是定理得证 定理证毕定理证毕 由定理 5 2 1 我们容易得出 由此可得 5 2 4 另外 从理论上讲 该迭代法经次迭代 便能得到精确解 但考虑到计算 误差 可以作为无限迭代算法进行计算 直到为止 从而 我们得到如下实用的共轭梯度算法 预置步 预置步 任意 计算 并令取 指定算法终 止常数 置 进入主步 主步 主步 计算 如果 转入 3 否则 终止算法 输出计算结果 计算 置 转入 1 注 在算法 主步 中 引入变量注 在算法 主步 中 引入变量 及及 可以简 可以简 化计算 化计算 结合程序设计的特点 共轭梯度法可改为如下实用形式 算法 解对称正定方程组 实用共轭梯度法 whilewhile andand ifif elseelse endend endend 共轭梯度法作为一种实用的迭代法 它主要有下面的优点 算法中 系数矩阵 的作用仅仅是用来由已知向量产生向量 这不仅可充分利用 的稀疏性 而且对某些提供矩阵 较为困难而由已知向量产生向量又十分方便的应用问题 是很有益的 不需要预先估计任何参数就可以计算 这一点不像 等 每次迭代所需的计算 主要是向量之间的运算 便于并行化 5 5 2 3 2 3 收敛性分析收敛性分析 将共轭梯度法作为一种迭代法 它的收敛性怎样呢 这是本节下面主要讨论 的问题 定理 定理 2 3 2 3 如果如果而且而且 则共轭梯度法至多迭代 则共轭梯度法至多迭代 步即可得到方程组的精确解 步即可得到方程组的精确解 证明证明 注意到蕴含着子空间 的维数不会超过 由定理 2 1 即知定理的结论成立 定理证毕定理证毕 定理 5 2 3 表明 若线性方程组 5 1 1 的系数矩阵与单位相关一个 秩 的矩阵 而且 很小时 则共轭梯度法将会收敛得很快 定理定理 5 2 45 2 4 用共轭梯度法求得的用共轭梯度法求得的有如下的误差估计有如下的误差估计 5 2 55 2 5 其中其中 证明证明 由定理 5 2 1 可知 对任意的 有 记 则是常数项为 1 的次实系数多项式 令 为所有常数项为 1 的次数不超过的实系数多项式的全体 则由定理 5 2 2 和引理 5 1 1 得 其中是的特征值 由 Chebyshev 多项式逼近定理及 Chebyshev 多项式的性质 定义在 1 1 区间上的次 Chebyshev 多项式 是所有常数项为是所有常数项为 1 1 的次数不超过的次数不超过的实系数多项式中 在的实系数多项式中 在 1 1 1 1 上与上与 0 0 的偏差值最小的多项式 且偏差值为的偏差值最小的多项式 且偏差值为 1 1 对应的交错点组为 对应的交错点组为 因此 多项式 是中在上与