南 京 航 空 航 天 大 学硕 士 学 位 论 文带 特 征 向 量 重 新 开 始 GMRES 算 法 的 补 足 收 敛 性 质姓 名 ： 尚 元 元申 请 学 位 级 别 ： 硕 士专 业 ： 运 筹 学 与 控 制 论指 导 教 师 ： 戴 华 ;钟 宝 江20060301南 京 航 空 航 天 大 学 硕 士 学 位 论 文摘 要 重 新 开 始 的 算 法 是 求 解 大 型 非 对 称 线 性 方 程 组 最 为 流 行 的 方 法 之 一 传 统 上 认 为 ， 由 于 迭 代 过 程 的 重 新 开 始 ， 先 前 循 环 所 得 到 的 信 息 会 丢 失 ， 如 子 空 间 基 的 正 交 关 系 ， 从 而 导 致 算 法 收 敛 速 度 下 降 为 了 改 善 残 量 的 收 敛速 度 ， 可 以 在 算 法 重 新 开 始 时 保 留 一 些 前 次 迭 代 循 环 的 信 息 比较常用的办法是在 子 空 间 中 加 入 k 个 极 小 调 和 值 所 对 应 的 调 和 向 量 ， 形 成 带 特征 向 量 的 重 新 开 始 算 法 数 值 试 验 表 明 ， 在 计 算 量 大 致 相 等 的 情 况 下 ， 带 特征 向 量 的 重 新 开 始 算 法 往 往 比 一 般 的 重 新 开 始 算 法 具 有 更 高 的 收敛率 最 近 ， 重 新 开 始 算 法 的 补 足 收 敛 性 质 引 起 了 人 们 的 兴 趣 补 足 收 敛 性质是指， 算 法 在 重 新 开 始 时 并 不 会 完 全 丢 失 前 次 迭 代 循 环 的 信 息 ，在迭代残 量 的 收 敛 过 程 中 ， 相 继 的 循 环 能 够 形 成 一 种 相 互 补 足 的 关 系 本 文 通 过分 析 带 特 征 向 量 的 重 新 开 始 算 法 中 有 关 调 和 值 的 数 据 ， 研 究 了 这 一算 法 的 补 足 收 敛 性 质 结 果 表 明 ， 在整个算法过程中， 随 着 迭 代 步 数 的 增 加 ， 所 加入 的 调 和 向 量 将 逐 步 使 得 方 程 组 系 数 矩 阵 的 k 个 极 小 特 征 值 得 到 很 好 地 逼近 这 一 过 程 类 似 于 求 解 特 征 值 问 题 的 一 种 斜 投 影 子 空 间 方 法 同 时 ， 算法 的 残 量 在 除 去 这 k 个 特 征 值 的 其 它 特 征 值 方 向 上 呈 现 补 足 收 敛 行 为 带 特 征 向量 重 新 开 始 算 法 的 收 敛 速 度 由 此 得 到 改 善 本 文 最 后 根 据 重 新 开 始 算 法 的 补 足 循 环 性 质 ， 提 出 了 带 有 效 特 征 向 量的 重 新 开 始 算 法 对 于 带 特 征 向 量 的 重 新 开 始 算 法 来 说 ， 第 一 步 是执 行 普 通 迭 代 ， 得 到 所 需 调 和 向 量 而 对 于 新 算 法 来 说 ， 第 一 步 则 是在 重 新 开 始 算 法 的 一 次 补 足 循 环 中 求 得 最 有 效 的 调 和 对 由 于 有 效调 和 值 对 极 小 k 个 特 征 值 的 更 好 逼 近 ， 残 量 的 收 敛 能 够 得 到 进 一 步 改 善 关 键 词 ： 线性系统； 迭代法； ； 特征值； 调和 值 i 带 特 征 向 量 重 新 开 始 GMRES 算 法 的 补 足 收 敛 性 质AbstractRestarted GMRES is one of the most popular methods for solving largenonsymmetric linear systems. It is traditionally known that some information like theorthonormality of Krylov subspace may lose at the time of restarting. This slowsdown the convergence. To improve the convergence, we can retain some of theinformation lost at the time of restarting. A common algorithm is the restartedGMRES augmented with eigenvectors, referred to as GMRES-E, which addseigenvectors corresponding to k smallest eigenvalues to the Krylov subspace.Numerical experiments indicate that the convergence of GMRES-E algorithm isusually faster than restarted GMRES with almost equal expenses.Recently, the complementary behavior of restarted GMRES has attracted a wideinterest. It is shown that some important information of the previous GMRES cyclesmay be saved automatically by the iteration approximates, with which successiveGMRES(m) cycles can complement one another harmoniously in reducing theiteration residual. In this paper we study the complementary behavior of GMRES-Eby a data analysis of harmonic Ritz values. It is shown that the harmonic Ritz valuesunder consideration converge to k smallest eigenvalues gradually as the iterationproceeds. At the same time, complementary behavior is observed on the othereigenvector directions. With this model, convergence of the residual is improved.Finally, a restarted GMRES algorithm augmented with effective eigenvectors isproposed. For the new algorithm, the harmonic Ritz vectors added to the Kryovsubspace come from a complementary cycle, rather than a restarting cycle of restartedGMRES. In consequence, the smallest eigenvalues can be approximated more closelyand then convergence of residual is improved.Key words. linear systems; iterative methods; GMRES; eigenvalues; harmonic Ritzvaluesii承诺书 本 人 郑 重 声 明 ： 所 呈 交 的 学 位 论 文 ， 是 本 人 在 导 师 指 导 下 ， 独 立 进行 研 究 工 作 所 取 得 的 成 果 尽 我 所 知 ， 除 文 中 已 经 注 明 引 用 的 内 容 外 ，本 学 位 论 文 的 研 究 成 果 不 包 含 任 何 他 人 享 有 著 作 权 的 内 容 对 本 论 文所 涉 及 的 研 究 工 作 做 出 贡 献 的 其 他 个 人 和 集 体 ， 均 已 在 文 中 以 明 确 方式标明 本 人 授 权 南 京 航 空 航 天 大 学 可 以 有 权 保 留 送 交 论 文 的 复 印 件 ， 允许 论 文 被 查 阅 和 借 阅 ， 可 以 将 学 位 论 文 的 全 部 或 部 分 内 容 编 入 有 关 数据 库 进 行 检 索 ， 可 以 采 用 影 印 、 缩 印 或 其 他 复 制 手 段 保 存 论 文 （ 保 密 的 学 位 论 文 在 解 密 后 适 用 本 承 诺 书 ）作 者 签 名 ： 日 期： 带 特 征 向 量 重 新 开 始 GMRES 算 法 的 补 足 收 敛 性 质图 表 目 录 图 （ ）和 算 法 的 比 较 图 双 扭 线 图 算 法 的 特 征 曲 线 图 （ ）和 算 法 的 比 较 图 应 用 （ ） 算 法 第 到 次 循 环 的 双 扭 线 图 应 用 算 法 第 、 次 循 环 的 特 征 曲 线 图 （ ）和 算 法 的 比 较 图 应 用 （ ） 算 法 第 到 次 循 环 的 双 扭 线 图 应 用 算 法 第 、 次 循 环 的 特 征 曲 线 图 和 算 法 的 比 较 图 和 算 法 的 比 较 表 应 用 （） 和 算 法 所 得 调 和 值 表 应 用 （） 和 算 法 所 得 调 和 值 表 应