《带特征向量重新开始GMRES算法的补足收敛性质》由会员分享,可在线阅读,更多相关《带特征向量重新开始GMRES算法的补足收敛性质(48页珍藏版)》请在金锄头文库上搜索。
1、南 京 航 空 航 天 大 学硕 士 学 位 论 文带 特 征 向 量 重 新 开 始 GMRES 算 法 的 补 足 收 敛 性 质姓 名 : 尚 元 元申 请 学 位 级 别 : 硕 士专 业 : 运 筹 学 与 控 制 论指 导 教 师 : 戴 华 ;钟 宝 江20060301南 京 航 空 航 天 大 学 硕 士 学 位 论 文摘 要 重 新 开 始 的 算 法 是 求 解 大 型 非 对 称 线 性 方 程 组 最 为 流 行 的 方 法 之 一 传 统 上 认 为 , 由 于 迭 代 过 程 的 重 新 开 始 , 先 前 循 环 所 得 到 的 信 息 会 丢 失 , 如 子 空
2、 间 基 的 正 交 关 系 , 从 而 导 致 算 法 收 敛 速 度 下 降 为 了 改 善 残 量 的 收 敛速 度 , 可 以 在 算 法 重 新 开 始 时 保 留 一 些 前 次 迭 代 循 环 的 信 息 比较常用的办法是在 子 空 间 中 加 入 k 个 极 小 调 和 值 所 对 应 的 调 和 向 量 , 形 成 带 特征 向 量 的 重 新 开 始 算 法 数 值 试 验 表 明 , 在 计 算 量 大 致 相 等 的 情 况 下 , 带 特征 向 量 的 重 新 开 始 算 法 往 往 比 一 般 的 重 新 开 始 算 法 具 有 更 高 的 收敛率 最 近 , 重
3、新 开 始 算 法 的 补 足 收 敛 性 质 引 起 了 人 们 的 兴 趣 补 足 收 敛 性质是指, 算 法 在 重 新 开 始 时 并 不 会 完 全 丢 失 前 次 迭 代 循 环 的 信 息 ,在迭代残 量 的 收 敛 过 程 中 , 相 继 的 循 环 能 够 形 成 一 种 相 互 补 足 的 关 系 本 文 通 过分 析 带 特 征 向 量 的 重 新 开 始 算 法 中 有 关 调 和 值 的 数 据 , 研 究 了 这 一算 法 的 补 足 收 敛 性 质 结 果 表 明 , 在整个算法过程中, 随 着 迭 代 步 数 的 增 加 , 所 加入 的 调 和 向 量 将 逐
4、 步 使 得 方 程 组 系 数 矩 阵 的 k 个 极 小 特 征 值 得 到 很 好 地 逼近 这 一 过 程 类 似 于 求 解 特 征 值 问 题 的 一 种 斜 投 影 子 空 间 方 法 同 时 , 算法 的 残 量 在 除 去 这 k 个 特 征 值 的 其 它 特 征 值 方 向 上 呈 现 补 足 收 敛 行 为 带 特 征 向量 重 新 开 始 算 法 的 收 敛 速 度 由 此 得 到 改 善 本 文 最 后 根 据 重 新 开 始 算 法 的 补 足 循 环 性 质 , 提 出 了 带 有 效 特 征 向 量的 重 新 开 始 算 法 对 于 带 特 征 向 量 的 重
5、 新 开 始 算 法 来 说 , 第 一 步 是执 行 普 通 迭 代 , 得 到 所 需 调 和 向 量 而 对 于 新 算 法 来 说 , 第 一 步 则 是在 重 新 开 始 算 法 的 一 次 补 足 循 环 中 求 得 最 有 效 的 调 和 对 由 于 有 效调 和 值 对 极 小 k 个 特 征 值 的 更 好 逼 近 , 残 量 的 收 敛 能 够 得 到 进 一 步 改 善 关 键 词 : 线性系统; 迭代法; ; 特征值; 调和 值 i 带 特 征 向 量 重 新 开 始 GMRES 算 法 的 补 足 收 敛 性 质AbstractRestarted GMRES is o
6、ne 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
7、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 faste
8、r 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) cycl
9、es 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 itera
10、tionproceeds. 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 adde
11、d 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 R
12、itzvaluesii承诺书 本 人 郑 重 声 明 : 所 呈 交 的 学 位 论 文 , 是 本 人 在 导 师 指 导 下 , 独 立 进行 研 究 工 作 所 取 得 的 成 果 尽 我 所 知 , 除 文 中 已 经 注 明 引 用 的 内 容 外 ,本 学 位 论 文 的 研 究 成 果 不 包 含 任 何 他 人 享 有 著 作 权 的 内 容 对 本 论 文所 涉 及 的 研 究 工 作 做 出 贡 献 的 其 他 个 人 和 集 体 , 均 已 在 文 中 以 明 确 方式标明 本 人 授 权 南 京 航 空 航 天 大 学 可 以 有 权 保 留 送 交 论 文 的 复 印
13、 件 , 允许 论 文 被 查 阅 和 借 阅 , 可 以 将 学 位 论 文 的 全 部 或 部 分 内 容 编 入 有 关 数据 库 进 行 检 索 , 可 以 采 用 影 印 、 缩 印 或 其 他 复 制 手 段 保 存 论 文 ( 保 密 的 学 位 论 文 在 解 密 后 适 用 本 承 诺 书 )作 者 签 名 : 日 期: 带 特 征 向 量 重 新 开 始 GMRES 算 法 的 补 足 收 敛 性 质图 表 目 录 图 ( )和 算 法 的 比 较 图 双 扭 线 图 算 法 的 特 征 曲 线 图 ( )和 算 法 的 比 较 图 应 用 ( ) 算 法 第 到 次 循 环 的 双 扭 线 图 应 用 算 法 第 、 次 循 环 的 特 征 曲 线 图 ( )和 算 法 的 比 较 图 应 用 ( ) 算 法 第 到 次 循 环 的 双 扭 线 图 应 用 算 法 第 、 次 循 环 的 特 征 曲 线 图 和 算 法 的 比 较 图 和 算 法 的 比 较 表 应 用 () 和 算 法 所 得 调 和 值 表 应 用 () 和 算 法 所 得 调 和 值 表 应