及 共 轭斜量 法。
直接法 的优 点是计 算 量小,并且可以事先估计,缺点是所需存储单元较多 ,编写程 序复 杂;迭代 法的优 点是原始系数矩阵始终不变,因而算法简单,编写 程序也比 较方 便,且 所 需存储 单元也较少,缺点是只有近似解序列收敛时才能被采用,而 且存在收敛性和收敛速度 的问题 。
对于中 等规 模的 n 阶 nlt100线性方 程组,由于直 接法 的准 确性和 可靠性,所以它们是经常被采用的方法。
对于较高 阶的方 程组,特别是对某些偏微分方程离散化后得到的大型稀疏方程组系数矩 阵中绝大 多数 为零元 素 ,由于直接解法的计算代价较高,使得迭代更具竞争力。
随着大 规模 并行计 算 机的快速发展,现在可以计算的规模越来越大,这些 计算多数 来源 于偏微 分 方程离 散后得到的大型稀疏线性方程组。
因此,大型稀疏线性代数 方程 组的求 解 已成为 数值算法研究的热点问题。
在许多应用学科和工程领域中,如流 体力学 、结构力 学、航空航天工程、电子工程等等,经常会遇到大型 1学院理学学士论文 第一章 引言稀疏非 对称线性方程组问题。
目前求解 这 类问题 最流 行的算 法 便是 GMRES 算法 。
本文主要分析 GMRES 算法的 加速 收敛现 象 和重新 开始 版本的 GMRESm算法的加速 收敛 现象。
2学院理学学士论文 第二章 GMRES 算法基础知识 第二章 GMRES 算法基础知识§2.1 向量范数 为了研 究迭 代法的 收 敛性 ,我们需要对 n 维向量和 n 阶方阵引进某种度量--向量范 数的概念。
向量范数是三维 Euclid 空间向量长度概念的推广,向量范数在数值 分析 中起着 极 其重要 的作用。
n n n n n 设 R 为实 n 维向量空间, C 为复 n 维向量空间。
我们记 K 为R 或C ,K 为实数域 R 或复数域 C 。
若 K n 上任一向量 X ,对应一个非负实数 X ,对于X Y K n 及 K ,满 足如 下条件: 非负性: X 0 ,且 X 0 的充要条件是 X 0 ; 齐次性: X X ; 三角不 等式: X Y X Y 。
则称 X 为向量 X 的范数上述三个条件称为向量范数公理。
常用的 向量 范数有 11 范数 n X 1 xi i 1 ; 22 范数 n 2 1 X 2 xi 2 i 1 ; 3 范数 X max xi 1 i n ; 4一般的 p 范数 n p 1 X p xi p i 1 。
3学院理学学士论文 第二章 GMRES 算法基础知识§2.2 线性方程组最小二乘问题 考虑确 定一 个向量 X ,使函数 X b AX 2 达到最小,这个问题称为 线 2 2性最小 二乘 问题,因 为它要 求剩余向量 r b AX 分量的平方和达到最小,而 且r 线性地依赖 于 X 。
其解 亦称为方程组 AX b 的最小二乘解。
现在介绍两种在 GMRES 算法中 用到的 正交 变换方 法,Gram-Schmidt 正交化方法、Givens 变换。
§2.2.1 Gram-Schmidt 正交化方法 设 1 2 ..... n 是 n 维空 间中 n 个线性无关的向量,则 1 2 1 1 / 1 2 2 2 2 1 1 2 2 / 2 2 ... n 1 n n n j j j 1 n n / n 2这时 1 2 ... n 是 n 个正交基向 量 1 2 2 1 3 1 ... n 1 2 2 3 2 ... n 2 1 2 ..... n 1 2 ... n 3 2 ... n 3 ... n 2 QR这时 Q 是正交 矩阵 , R 是上三角矩阵。
Schmidt 正交化 过程 就是将 矩阵 A 分解 为正交矩 阵与 上三角 矩 阵的乘 积 A QR即 A 的 QR 分解 。
§2.2.2 Givens 变换 欲把一个向量中许多分量化为零 ,可以 用 Householder 变换 ;如果只 将其 中一个分 量化为零,则采用 Givens 旋转得 到 H k 的 QR 分解。
一个 2 2 的 Givens 旋 4学院理学学士论文 第二章 GMRES 算法基础知识转是一 个如 下形式 的 归一矩 阵 c s G s cc 和 s 满足 c s 1 。
它将单位向量 c s 旋转到向量 Gc s 10 ,第二项为 2 2 T T T0。
一个 n n 的 Givens 旋转将单 位阵 I 的对角线上 2 2 的块替换为 2 2 的 Givens旋转 1 1 c s G s c 1 1 表示一 个 k 1 k 1 的带有在 j 和 j 1 行与列的 2 2 的 Givens 旋转。
令G j c s h 0 0 h 1 0 c0 s0 2 2 2 2 h 0 0 h 1 0 h 0 0 h 1 0 和 G0 G0 c0 s0 则 c 0 h 0 0 s 0 h 1 0 0 h 2 1 h 2 k 2 h 2 k 1 G 0 H k 1 h k 1 k 2 h k 1 k 1 h k k 1 5学院理学学士论文 第 三章 GM R E S 算 法 理 论 第三章 GMRES 算法理论§3.1 Krylov 子空间方法的基本理论 Krylov 子空间投影法是一类 非 常有 效的 大型 线性 方 程组 解法 ,已 被广泛应用于各 种领 域,随 着 左右空 间 Lm K m 的不同取法可以得到许多求解大型方程组的求解算 法。
考虑线 性 方程组 Ax b 其中, A 是 n n 阶的大型稀疏实矩 阵, 1.当 Lm K m 时,称为 Galerkin 方法又称 正交 投影法 。
A 为一般 矩阵时,有 FOM 算法;A 为对称正定矩阵时,有 CG算 法 。
2.当 Lm K m 时,称为斜投影方法。
当 Lm AK m 时,称为最小二乘法 , 当A 为一般 矩阵 时,有 GMRES 方法,GCR 方法等;当 A 为对称正定阵时,有 CR 方法。
所以 GMRES 算法又属于最小二乘 法。
下面是 迭代 方法的 流 程图: 是 是 考虑系数矩 阵是否 对 称 是否正定 使用 CG 方法 否 否 MINRES 方法 否 是否有足够 的存储 空 间 应用 GMRES 方法 图 3-1 迭代方法流程图 Fig3-1 Chart of iteration methods 对 于 以 上 大 型 线 性 方 程 组 , 令 右 空 间 K m Spanv1 v2 ....vm 和 左 空 间Lm Spanw1 w2 ...wm ,其中 vi wi i 1 2...m 各自线性无关。
假设 x0 为初始迭代 值 ,投影方 法寻 求这样 的 一种近 以解: 6学院理学学士论文 第 三章 GM R E S 算 法 理 论 xm x0 zm zm K m rm b Axm r0 Azm Lm通过求 解一 个最小 值 问题: rm Min b Axm Min r0 Azm xm K m x0 K m来解方 程组这就是 Krylov 子空间 投影方 法。
§3.2 Arnoldi 算法 Arnoldi 算法过程: 1 输入 A 和初始向 量 x 0 。
r0 b A x 0 q 1 r0 / r0 j 1 2 .
上一篇:
学校电费管理系统的设计与实现
下一篇:
餐饮管理系统的设计与实现(word论文|下载论文)