（计算数学专业论文）解周期块状三对角线性代数方程组的新算法.pdf

西北工业大学硕 卜 学位论文 摘要 具有周期边界条件的椭圆型偏微分方程为 一 p x y u x 一 ax y u a x y u f x y x y s 2 u x y u x i y u x y 二 u x y l z x 一 a 0 通过建立矩形网格剖分 按照e v a n s 的离散化方法 可以得到下面的差分格式 d u 一 1 u 1 一 r u 一 b f u r 一 t f u s 写成矩阵乘法形式a u s 其中a是周期块状三对角矩阵 另外 利用n ih e i 和i s h i i 提出的拟谱组合紧差分格式离散化浅水方程 粤 v d u 一 f u ta n o v 一 8 丝 0 ac o s o n 粤 十 v v 十 了 竺 ta n 0 十 g 鱼 o f口一口 a 0 助 二 h 面加c o s b 一 二 十v v r l十 叹 二 u ja c o s h 6 a a b 也将得到周期块状三对角线性代数方程组 本文给出了求解周期块状三对角线性代数方程组的几种迭代方法和直接方 法 并与现有的一些算法进行了比 较 主要内容如下 i 通过对系数矩阵的不完全l u 分 解 导出了 一次p e 方 法和二次p e 方法 在此基础上通过引入参数k 得到了一次p e 方法和二次p e k 方法 本文着重讨论 一次p e 方法 简称p e 方法 和一次p e k 方法 简称p e k 方法 证明了 系数矩 阵为h e r m i t e 正定矩阵 m一 矩阵和h 矩阵时 p e 方法和p e k 方法的可解性与收 敛性 通过算例说明 p e方法和 p e 方法的收敛性要比 现有的一些方法 如块 j a c o b i 方法和对称块g a u s s s e i d e i s b g s 方 法 好 2 建立了 求解周期块状三对角线性代数方程组的两种直接方法 三参数组 方法和线性插值方法 对于一些块追赶法无法解决的问题 新算法可以解决 因 西北工业大学硕 七 学位论文 此这两种直接方法是对块追赶法的补充 关健词 线 性 代数 方 程 组 周期 块 伏三 对角 矩 阵 p e 方 法 p e 方 法 三参数组方法 线性插值方法 西北工业大学硕士 学位论文 ab s t r a c t t h e g e n e r a l e l l i p t i c p a r t i a l d i ff e r e n t i a l e q u a t i o n w i t h p e r i o d i c b o u n d a ry c o n d i t i o n s i s a s f o l l o ws 一 p x y 二 二 一 p x y u y y a x y u r x y u x y 二 u x 1 y u x y u r y 1 1 x y e 口 x y a n s u p p o s e t h a t t h e r er e c t a n g u l a r m e s h fr o m e v a n s d i s c r e t i z a t i o n a s m e t h o d t h e f o l l o w i n g d从 d i ff e r e n c e s c h e me i s o b t a i n e d 1 0 一 r i u 一 n u 一 一 t u j 二 s 1 i t c a n b e w r i t t e n i n m a t r i x n o t a t i o n a s a u s w h e r e a i s p e r i o d i c b l o c k t r i d i a g o n a l m a t r i x o v e r u s inga c o m b in e d c o m p a c t d i ff e r e n c e s c h e m e p r o p o s e d b y n i h e i a n d i s h i i a n d d i s c r e t i z i n g t h e s h a l l o w w a t e r e q u a t i o n s v v u 一 f u 十节 t a n b v 8 a c o s b 十 v v v f u ta n o u 里 加 次加 次 v h 一 h a c o s b a u 加c o s 0 几 二 佗 二u ij 尤do we c a n a l s o g e t a u s w h o s e c o e f fi c i e n t m a t r i x i s l a r g e p e r i o d i c b l o c k t r i d i a g o n a l m a t r i x i n t h i s p a p e r s e v e r a l n e w i t e r a t i v e m e t h o d s a n d d i r e c t m e t h o d s f o r s o l v i n g l i n e a r s y s t e m b l o c k t r i d i a g o n a l m a t r i x w h o s e c o e f f i c i e n t m a t r i x i s l a r g e p e r i o d i c a r e p r o p o s e d t h e y a r ewi t h s o me exi s t i n g m e t h o d s t h e ma i n w o r k i s a s f o l l o w s 1 b y i n c o m p l e t e ly l u t r i a n g u l a r d e c o m p o s i t i o n o f t h e c o e f f i c i e n t i i i 西北工业大学硕士学位论文 m a t r i x l i n e a r p e m e t h o d a n d q u a d r a t i c p e m e t h o d a r e o b t a i n e d t h e n w e p r o p o s e l i n e a r p e k m e t h o d a n d q u a d r a t i c p e k m e t h o d t h r o u g h i n t r o d u c i n g a p a r a me t e r m e t h o d i e k l i n e a r p e m e t h o d i e p e m e t h o d a n d l i n e a r p e k p e k m e t h o d a r e m a in l y d i s c u s s e d i n t h e p a p e r u n d e r t h e c o n d i t i o n t h a t t h e c o e f f i c i e n t m a t r i x i s h e r m i t e p o s i t i v e d e f i n i t e m a t r i x m ma t r i x h m a t r i x t h e s o l v a b i l i t i e s a n d c o n v e r g e n c e s o f t h e t w o me t h o d s p r o v e d s o m e e x a m p l e s a r e g i v e n t o i l l u s t r a t e t h a t t h e i r c o n v e r g e n c e s a r e b e tt e r t h a n s o m e e x i s t i n g m e t h o d s s u c h a s b l o c k j a c o b i m e t h o d a n d s b g s m e t h o d 2 p r e s e n t t w o d ir e c t m e t h o d s f o r s o l v i n g l i n e a r s y s t e m w h o s e c o e f f i c i e n t m a t r i x i s l a r g e p e r io d i c b l o c k t r i d i a g o n a l m a t r i x t h r e e p a r a m e t e r i c m e t h o d a n d l i n e a r i n t e r p o l a t i o n m e t h o d s o m e p r o b l e m s c a n b e s o l v e d b y t h e s e t w o n e w d i r e c t m e t h o d s w h i l e g a u s s e l i m i n a t i o n m e t h o d c a n t s o l v e s o t h e y a r e s u p p l e m e n t t o g a u s s e l i mi n a t i o n me t h o d k e y w o r d s l i n e a r a l g e b r a i c e q u a t i o n s p e r i o d i c b l o c k t r i d i a g o n a l m a t r i x p e m e t h o d p e k m e t h o d t h r e e p a r a m e t e r m e t h o d l i n e a r i n t e r p o l a t i o n m e t h o d i v 西北t 业大学硕 上 学位论文 第一章p e方法与p e 方法介绍 1 1引言 线性代数方程组a x f经常出现在科学与 工程的许多领域中 而且很多 数值求 解问题最后也是归结于求某些线性代数方程组 如何有效地求解线性代数方程组 是 科学与工程计算中 最基本 应用最广泛的问题 也是计算数学中的一 个重要方向和课 题 例如实际应用中的网络分析问题 结构分析问题和数据分析问题等 数学上的样 条逼近问 题 最小二乘计算 微分方程组数值解问题等 最终都可以归结为求解线性 代数方程组的问题 特殊的周期块状三对角线性方程组也有广泛的应用背景 例如在电离层电场理论和飞行器设计中 经常要求解具有周期边界条件的椭圆型 或 抛物 型偏 微分 方 程 4 1 2 1 在 文 献 4 1 中 e v a n s 通 过 适当 的 离 散逼 近 将 此 类问 题转 化为大型线性方程组的求解 此方程组的系数矩阵就是周期块状三对角矩阵 考虑具 有周期边界条件的椭圆型偏微分方程 一 ax y u x 二 一 p x y u y y v x y u ax y x y e d u x y u x i y u x y u x y 1 2 x y e a o l 和1 2 分别是口在x 轴和y 轴方向的投影距离 并假设当 x y e t 2 u a 2 时 p x y 0 u x y 0 且在s l 的部分点上q x y 0 建立矩形网格剖分 x i y 1 0 u x y 0 且在s l 的部分点上q x y 0 建立矩形网格剖分 x i y 1 0 成立 则称a为h e n n i t e 正定矩阵 引 理1 1 h e r m i t e 矩阵a为正定 矩阵的充 要条件 是a的 全部特征值为 正数 引理 1 2 e 1 h e r m it e 矩阵a为正定矩阵的充要条件是存在n 阶可逆矩阵p 使 得a二 p l 引理 1 3 16 1 若a与c 均为n 阶 h e r m i t e正定矩阵 且a c c a 则a c也为 h e r m i t e 正定矩阵 引理1 4 11 6 1 若a为n 阶h e r n t i t e 正定矩阵 c为任一列满秩矩阵 则c a c 为 h e r m i t e 正定矩阵 引理 1 5 h e r m it e矩阵a为正定矩阵的充要条件是a的n 个顺序主子式全为正 数 引理1 6 设a为n 阶h e r m i t e 正定矩阵 则有 t r a a a i 二 1 2 西北工业大学硕 i 一 学位论文 的取值范围考虑 提出了新型二次p e k 方法与二次e p e 方法 讨论了当系数矩阵为 h e r m i t e i e 定矩阵 m 一 矩阵及h 矩阵时新型二次p e k 方法的收敛性和当系数矩阵为对 称正定矩阵 可正定 化矩阵时 二次e p e k 方法的 收敛性 2 0 0 4 年 吴蕾 等将p e 方 法的思 想应用于求解块状五对角线 性方程组 提出了 一次p e 方法 一次p 马方法 二次p e方法和二次p e k 方法 讨论了当系数矩阵为h e r m i t e 正定矩阵 m 矩阵时 上 述 几 种方 法的收 敛 性 u 1 本文借鉴上述研究方法的思想 对系数矩阵为周期块状三对角矩阵的线性方程组 建立了p e方法和p e k 方法 讨论了当系数矩阵为h e r m it e 正定矩阵 m 矩阵和 h 矩阵时这两种方法的收敛性问题 论文所给的算例表明 p e 方法要比块j a c o b i 方法 s b g s 方法收敛快 在论文的最后两章 还建立了 求解周期块状三对角线性方程组的 两种直接方法一三参数组法和线性插值法 对这两种方法解的存在性和运算量进行了 分析 并讨论了数值稳定性等问题 1 2预备知识 本节主要对论文中所涉及的基本概念和引理做简单的介绍 一 h e r m i t e 正定矩阵 定义1 1 设a为n 阶h e r r n it e 矩阵 若对任意n 维列向 量x t 0 都有 x a x 0 成立 则称a为h e r m i t e 半正定矩阵 若对任意n 维列向量x 0 都有 x a x 0 成立 则称a为h e n n i t e 正定矩阵 引 理1 1 h e r m i t e 矩阵a为正定 矩阵的充 要条件 是a的 全部特征值为 正数 引理 1 2 e 1 h e r m it e 矩阵a为正定矩阵的充要条件是存在n 阶可逆矩阵p 使 得a二 p l 引理 1 3 16 1 若a与c 均为n 阶 h e r m i t e正定矩阵 且a c c a 则a c也为 h e r m i t e 正定矩阵 引理1 4 11 6 1 若a为n 阶h e r n t i t e 正定矩阵 c为任一列满秩矩阵 则c a c 为 h e r m i t e 正定矩阵 引理 1 5 h e r m it e矩阵a为正定矩阵的充要条件是a的n 个顺序主子式全为正 数 引理1 6 设a为n 阶h e r m i t e 正定矩阵 则有 t r a a a i 二 1 2 西北工业大学硕士学位论文 其中凡 a 为a的特征值 二 对角占优矩阵 定 义1 2 118 1若 矩阵a 二 a 满 足 la l e l a 一 二 1 2 一 则称a为按行对角占优矩阵 若满足 la 卜 l la i 二 1 2 n 则称a为按行严格对角占优矩阵 类似地 可以定义按列对角占优矩阵和按列严格对角占优矩阵的概念 按行对角 占优矩阵和按列对角占 优矩阵统称为对角占优矩阵 定 义1 3 16 1设 矩阵a a u 满 足a 0 i 1 2 n 若 有 正 对 角 矩 阵q 使 1 2 弓 1 理 a q 为 按 行严 格对 角占 优 矩阵 则 称a 为 行 广义 对 优矩阵 q a为按列严格对角占 优矩阵 则称a为列广义对优矩阵 1 7 1 6 引理 1 8 1 1 6 1 若a为严格对角占优矩阵 则a可逆 设m二 m i n 为 严 格 对 角占 优 矩 阵 n n 则 艺星1卜1 卜 nil m a x 二 i m in l 定 义1 4 i 6 设 矩 阵 a a n 2 若 集 合 w二 1 2 二 n 的 任 意 两 个 非 空 不 相 交 的 子 集s 和t 满 足s 十 t 甲 且 有 i 和j 使 得i e s j e t 以 及 a s 0 则 称 a为不可约矩阵 否则称a为可约矩阵 定义1 5 16 若矩阵a为不可约矩阵 ia i e la l l 且满足 l 1 2 一 n 至少有一个不等式严格成立 则称a为不可约弱对角占优矩阵 引 理1 9 116 1 设a a 为h e r m it e 矩 阵 且a 0 当a 严 格 对 角 占 优 或 不 可约弱对角占优时 a为正定矩阵 西北t业大学硕 l 学位论文 三 非负矩阵 元素都是非负实数的矩阵称为非负矩阵 这类矩阵在数理经济学 概率论 弹性 系统的微振动理论等领域都有广泛的应用 下面介绍非负矩阵的基本性质 定 义 6 116设 矩 阵 a a 定 义 ia 卜 一a 一无 即 将 矩 阵 a 的 所 有 元 素 都 用 它 的 绝 对 值 1a 1 代 替 得 到 的 矩 阵 定 义1 7 116 设 a a b 二 b ra 均 为 实 矩 阵 一 a 0 i 1 n j 1 n 称b a 一 a j i 1 m j 1 一 n 称b a 引 理1 1 0 116 若 矩 阵 m和 n 为 同 阶 的 方 阵 且 m i m f 上述迭代格式的每一步都要求解如下形式的方程组 d 才 之 d 对矩阵m进行三角分解可得 m lu 其中l 为下三角矩阵 u为上三角矩阵 若上面的等式严格成立 则称这种分解为完 全l u分解 否则若有 m t lu 成立 则称这种分解为不完全l u分解 记r二 m一 l u 则有 m lu r 西北t业大学硕 l 学位论文 三 非负矩阵 元素都是非负实数的矩阵称为非负矩阵 这类矩阵在数理经济学 概率论 弹性 系统的微振动理论等领域都有广泛的应用 下面介绍非负矩阵的基本性质 定 义 6 116设 矩 阵 a a 定 义 ia 卜 一a 一无 即 将 矩 阵 a 的 所 有 元 素 都 用 它 的 绝 对 值 1a 1 代 替 得 到 的 矩 阵 定 义1 7 116 设 a a b 二 b ra 均 为 实 矩 阵 一 a 0 i 1 n j 1 n 称b a 一 a j i 1 m j 1 一 n 称b a 引 理1 1 0 116 若 矩 阵 m和 n 为 同 阶 的 方 阵 且 m i m f 上述迭代格式的每一步都要求解如下形式的方程组 d 才 之 d 对矩阵m进行三角分解可得 m lu 其中l 为下三角矩阵 u为上三角矩阵 若上面的等式严格成立 则称这种分解为完 全l u分解 否则若有 m t lu 成立 则称这种分解为不完全l u分解 记r二 m一 l u 则有 m lu r 西北工业大学硕士学位论文 二 收敛性及其性质 在研究线性代数方程组 a x t 的迭代解法中 相当多的迭代格式可以表示为 x k p g x k g k 0 1 2 二 l 2 其中g是n 阶矩阵 称之为迭 代矩阵 s 是与a 和t 有关的向 量 而x 0 是 任意 选定 的列向量 称为初始向量 这种迭代法被称为线性迭代法 对于迭代方法 人们关心 的是它的收敛性和收敛速度 定义 1 8 11 9 如果对于任意的初始向 量x i0 i 由迭代格式 1 2 得出的向量序列 fv 0 使 得 l i m x 二工 其中x 为一极限常向 量 则称迭代格式 1 2 是收敛的 否则 弓 理1 1 1 1 19 1迭 代格式 1 2 收敛的充要条 件是 迭 代矩阵g p g 1 称为发散的 的谱半径满足 引 理1 1 2 1 若 迭 代 矩 阵 g 的 某 种 范 数 咧 1 则 迭 代 格 式 1 2 是 收 敛 的 定义1 9 迭代格式 1 2 的平均收敛速度定义为 r g 一 去 in lig ii 其 中 矩 阵 范 数 11 11 使 得 司 1 定义1 1 0 迭代格式 1 2 的渐近收敛速度定义为 r g 一 i n p g 下面的引理可以说明这两种收敛速度之间的关系 引 理1 1 3 设凡 为迭代 格式 1 2 的 平均收 敛 速度 则 煦凡 g 一 in p g 从这个引理可以 看出 当迭代次数趋于无穷大时 平均收敛速度有极限 而且该 极限与所取的矩阵范数无关 它由迭代矩阵的谱半径唯一确定 三 p e 方法简介 p e 方法是1 9 7 7 年美国学者wi l l i a m s h e l l i w e l l 在第三届计算流体力学年会上 提出的一种拟消去 p s e u d o e l i m i n a t i o n 迭代法 简称为p e方法 他当 时只 把这种方 西北工业大学硕 l 学位论文 法用在五点差分方程的迭代求解上 并且用实际例子说明了 这种方法比一些传统的求 解这类方程组的 迭代方法收敛速度快 但并没有从理论上加以证明 后来胡 家赣等人 对此进行了多方面的研究 并得出了一些理论成果 厂 面就来介绍 h e l l i w e l l 针对块 三对角线性代数方程组提出的p e 方法的基本思想 考虑大型稀疏块三对角线性代数方程组 a x f 其中a为块三对角矩阵 今氏 耳杰 c二 布 叹几 筑凡 厂 月 一 a 子 矩 阵b 为n 阶 方阵 戒为n x n 长 方 阵 砚为n x n 长 方阵 用i 表 示n 阶 单 位矩阵 并对a进行块三角分解 假定分解式存在 队 二 t 人 i m 久 d 几人 r 子 片 一一 a 将右端两个矩阵作乘法运算可得 d u a 2 鱿 d d认 a a u 一 氏 a d m u a u d 阿队 1 a 比较以上两种a的表达式可得 d 拭 d b 一 a u b 一 a d c u d 尸 c i 二 2 3 m i 1 2 m一 1 当p 找 一 a d l e 1 则 对 任意实 参数k p e 方 法收 敛 若 存 在i 使 得 a 叹 1 选 取to 使 得入二 m in a g i 0 1 则 参数k 满足0 k 时 p e k 方法收敛 证明 1 a b a 半正 定 山a正定知筑 i 因为 m 正定 又由丫 c 知a b i c a b i a b c 二 b b z a b c l 双2 双z 1 1一 一 所以 耳 a 川c 的 特 征 值 为 非 负 实 数 从 而i 十 崎 峨 川砚 的 特征 值为 正 数 故 该 矩阵 可 逆 根据 式 1 9 可 得s i i 1 m 一 1 可 逆 2 由 1 易 知 1 g 0 直接计算可得 n二 m一 a二 d i a g o n z 一 n m o 其中n s 找 不 一 双 况十 峨 划c 一 一 双 b i k b a b c 一 a i 一 k b a b 2 c z b c 一 b 一 胡 川戒 1双 达 c 一 2 川 b i 脚 a 耳 仁 一 b a b c 一 k a 州a 毗c i 2 川c b w 2 1 式 2 1 最 后一 个 等号 右 端的 第一 项为h e r m it e 半正 定 矩阵 当a g 或 1 g 1 时 矩阵w 的 特征 值为 非 负实 数 且 b w 二 b 阮 k g 一 十 g 一 i 卜 b k g b 厂 十 b ig 一 双 为h e r m i t e 矩阵 由 引 理2 1 知式 2 1 的 第二 项 也为h e r m it e 半正 定 矩阵 因 此 n 为 i i i 半正定矩阵 从而n的 特征值为非负实 数 由a n a 一 2 a 一 n a乃 a 2 可知 双 a n 为 非 负 实 数 由 弓 理2 2 可得 双 m n 1 故p e k 方 法 收 敛 已 知 n 一 峨川减 一 1毗c 2 州c 一 双 哄 当 0 双 乓 0 而 当 i g j 或a g 1 时 矩阵w的 特征 值 为 非 负 实 数 因 此 在 的 条 件 下 w 的特征值为非负实数 下面的推导过程同 当k l 时 p e 方法成为p e方法 由定理2 2 可得 证毕 若a为h e r m i t e 正定矩阵 p e方法可行并且收敛 需要指出 定理2 2 只是判定p e 方法收敛的充分条件 西北工业大学硕上 学位论文 如 果 方 程 组 1 4 的 系 数 矩阵a 满 足 引 理1 9 的 条 件 即a a 为h e r m it e 矩 阵 a 0 且a 严格对角占 优或不可 约弱对角占 优时 也 可用p e k 方法 进行 求解 2 2 二次p e方法的收敛性 在二 次p e 方 法中 s 的 表 达式 为 s b i b a 川c b a 川c 2 一 i 2 m 一 1 定理 2 3 若a为 h e r m i t e矩阵 则二次 p e 方法中的矩阵m s i 1 m一 1 均为h e r m i t e 矩阵 证明因为a为h e r m i t e 矩阵 所以有 b h 双 a h c a t 一 c m 由 此 可 得s ih 衅 戏 况 当 i 二 2 m 一 1 时 有 畔 b i i i b a b t c 1 b a b c 1 2 1 h 不 茸 戒 州c i 1 茸 戌 川c i 2 h i 双 二 i a b c b i a b c b 2 一 b b i 十 b i a j川c b a j川c b a 川c b 1 一 双 b i l l s 因此s i 1 m一 1 是h e r m it e 矩阵 再由 1 1 0 鸿嵘凡 s 2 a t c 2 且 戒 不 二 a s c a m a s c 茂 不 s m 十 a 兀 一 2 a m 阵沐 风 一 u l 一一 m 可得m m 从而 n m一 a m 一 a m一 a n 故n也是 h e r m i t e矩阵 定理2 4 若a为h e r m i t e 正定矩阵 则二次p e 方法可解 而且是收敛的 证明 首 先证明 第一 个结论 由a正 定可知入 i 1 m 正 定 故况 n 和 证毕 b 可 逆 又由a h 二 c 可 知 戒 川 a b a 是半正定矩阵 其特征值是非负实数 从而 b 的特征值也为非负实数 a b c b22 双 a b c b 2 b 故不 b a 州c 十 b a 双 认 c 的 特征 值 大 于 等 于1 因 此该 矩阵可 逆 从 而戈 7 1 二 m 一 1 可 逆 再来证明第二个结论 直接计算可得 西北工业大学硕上 学位论文 如 果 方 程 组 1 4 的 系 数 矩阵a 满 足 引 理1 9 的 条 件 即a a 为h e r m it e 矩 阵 a 0 且a 严格对角占 优或不可 约弱对角占 优时 也 可用p e k 方法 进行 求解 2 2 二次p e方法的收敛性 在二 次p e 方 法中 s 的 表 达式 为 s b i b a 川c b a 川c 2 一 i 2 m 一 1 定理 2 3 若a为 h e r m i t e矩阵 则二次 p e 方法中的矩阵m s i 1 m一 1 均为h e r m i t e 矩阵 证明因为a为h e r m i t e 矩阵 所以有 b h 双 a h c a t 一 c m 由 此 可 得s ih 衅 戏 况 当 i 二 2 m 一 1 时 有 畔 b i i i b a b t c 1 b a b c 1 2 1 h 不 茸 戒 州c i 1 茸 戌 川c i 2 h i 双 二 i a b c b i a b c b 2 一 b b i 十 b i a j川c b a j川c b a 川c b 1 一 双 b i l l s 因此s i 1 m一 1 是h e r m it e 矩阵 再由 1 1 0 鸿嵘凡 s 2 a t c 2 且 戒 不 二 a s c a m a s c 茂 不 s m 十 a 兀 一 2 a m 阵沐 风 一 u l 一一 m 可得m m 从而 n m一 a m 一 a m一 a n 故n也是 h e r m i t e矩阵 定理2 4 若a为h e r m i t e 正定矩阵 则二次p e 方法可解 而且是收敛的 证明 首 先证明 第一 个结论 由a正 定可知入 i 1 m 正 定 故况 n 和 证毕 b 可 逆 又由a h 二 c 可 知 戒 川 a b a 是半正定矩阵 其特征值是非负实数 从而 b 的特征值也为非负实数 a b c b22 双 a b c b 2 b 故不 b a 州c 十 b a 双 认 c 的 特征 值 大 于 等 于1 因 此该 矩阵可 逆 从 而戈 7 1 二 m 一 1 可 逆 再来证明第二个结论 直接计算可得 西北工业人学硕士学位论文 n m一 a d i a g o n z n m o 其中 n s 减 t 一 双 s 十 减 s c 一 飒 一 双 式 g g 一 a i g g b i c 一 双 二 双 i g 讨 一 十 a 川c 峨 叹 一 t 川c 十 a g b c 一 双 2 2 这 里g b a 川c 利 用 恒 等 式 i g 十 g z 一 i 一 g g i 十 g 十 g 2 一 对 式 2 2 最后一个等号右端第一项变形可以得到 n b i 一 留 i g 研 一 减 川c 十 式 叹 b 砚 一 氏 嵘 b 1 c 一 一 双 双 讨 i g 可 一 十 a g b c i 减 嵘 州c 2 3 容 易 验证 式 2 3 的 最后两 项 均为h e r m i t e 半 正 定 矩阵 设叹的 特征 值为a 由 定 理2 2 的 证明 可 知a 0 则g 不 十 g g 的 特 征 值 为 一 生 止 0 1 兄 兄 2 由 定 理2 3 可 知况为h e r m it e 矩阵 所以 双 了 忧 叹 讨丫 为h e r m i te 矩 阵 又 由 双 为 正 定 矩阵 及引 理2 1 可得戏 讨 i 十 叹十 留丫 为 半正 定 矩阵 因 此n为 半 正 定 矩阵 宜一 l 一 l 1一 从而n的 特征值非负 由a n a 2 a 2 n a 2 a 2 可知a a n 为非负实数 引理2 2 可得0 5 双m n i 故二次p e方法收敛 由 证毕 2 3 数值算例 例2 1 设具有周期边界条件的椭圆型偏微分方程边界问题为 一 a2u a2uaxz aye 一 v y 一 一 t u 气 x x u u 气 x ye 0 1 x e 0 1 y 1 这里口 0 1 x 0 按照e v a n s 的 离散化方法得到形如式 1 4 的线性方程组 选取 们 州月川 4 二 申矛上 jl胜人 月片 1 广lesesesesesesesesesesesesl 1 戏减 c i f 4 二 j 十 共 k n i j l 阴 1 l l 川 i月 i 脚 i m 1 n n i 根据引理 1 9 易知系数矩阵a为h e r m i t e正定矩阵 2 n 石 分别用p e k 方法 块j a c o b i 方法 和 s b g s方法求解此方程组 计算结果见表2 1 和表 2 2 ma t l a b语言p i v 1 5 0 g h z 西北工业人学硕士学位论文 n ma d i a g o n 2 d 其中 n j s 4 a l 一b i s j a i s 2 1 c 一b j 置 f g j g 1 a i h 十g f l 雠i 酢 c i 一置 b j 十g g a 8 c h a gl s 2 c 一l 4 g 孟 丑二c 川一b 2 2 这里e b 4 茸1 1 l c 1 利用恒等式 g g 2 j r g g 3 j rq g g 2 1 对式 2 2 最后一个等号右端第一项变形可以得到 n e 1 一g 研 g 姘 1 a b c l a gt 8 1 l c h a g 王t b 二c 一b e 研 g j 研 4g f 一 b 2 c 一 4 罐 e c 一 2 3 容易验证式 2 3 的最后两项均为h e r m i t e 半正定矩阵 设q 的特征值为a 由定理2 2 的证明可知 0 则研 q 研 的特征值为 者 1 五 五2 由定理2 3 可知m 为h e r m i t e 矩阵 所以置g g f 研 为h e r m i t e 矩阵 又由b i 为正定矩阵及引理2 1 可得置研 g i 研 为半正定矩阵 因此j 为半正定矩阵 从而 r 的特征值非负 由爿 1 n a a2 n a2 a2 可知2 a n 为非负实数 由 引理2 2 可得o 旯 m 1 l 故二次p e 方法收敛 证毕 2 3 数值算例 例2 1设具有周期边界条件的椭圆型偏微分方程边界问题为 f 一鲁一喜 y 口 i 一萨一矿引 y 川刨 1 o y 1 力y l o 1 i u x 0 u x 1 x o 1 这里刃 0 1 0 1 按照e v a n s 的离散化方法得到形如式 1 4 的线性方程组 选取 置 4 5一l l4 5 一l a j c 一i z 高k 熹 熹 熹 熹 焘 t 根据引理1 9 易知系数矩阵a 为h e r m i t e 正定矩阵 分别用p e 方法 块j a c o b i 方法 和s b q s 方法求解此方程组 计算结果见表2 1 和表2 2 m a t l a b 语言p i v 一1 5 0 0 h z 1 4 o o 堕些三些查堂墅兰兰垡兰苎 一 微机 时间单位为秒 初始向量知 1 1 7 终止准则为1 0 计算时间和参数 的关系见图2 1 和图2 2 表2 1 迭代次数和计算时间对比 5 m 5 0 0棚 0 0 0 m 5 0 0 0 1 0 0 0 0 方法 时间次数时间 次数时间 次数时间 次数 块j a c o b i 1 1 55 2 8 1 1 71 0 8 l1 2 0 5 5 0 51 2 21 1 2 9 s b g s3 7 3 2 93 76 5 1 3 73 2 6 73 76 5 t 3 3 k 0 5 2 52 5 8 2 65 6 32 72 8 0 82 75 5 8 5 k 1 o1 8 1 9 51 83 9 3 1 81 9 3 61 94 0 5 4 七 1 4 1 11 2 8 1 12 5 6 l i 1 2 7 31 22 8 2 8 k 1 5 1 01 1 81 02 3 41 0 1 2 0 6 1 0 2 3 6 3 p e t 2 5 4l l1 6 2 61 l3 5 5 7 k 1 61 11 2 61 1 2 0 1 81 9 41 83 8 6 1 82 4 2 71 84 9 6 6 k 2 53 5 3 5 73 67 3 03 74 5 6 93 79 3 9 0 k 3 0 1 1 11 0 7 7 1 1 32 2 8 21 1 01 3 4 01 1 72 7 9 6 表2 2 速代次数和计算时间对比 聊 m 5 0m h 7 5珊 玎 l o o 方法 次数时间次数时间次数时问 块j a c o b i 1 1 53 0 51 1 79 3 91 1 82 4 6 5 s b g s 3 91 8 53 96 2 3 4 0 1 5 5 4 七 0 5 2 51 5 22 64 9 72 61 4 5 6 后 1 o1 81 2 11 83 5 31 81 1 8 7 k 1 4 l l0 8 7l l2 6 8u 9 2 7 七 1 51 0o 8 71 02 6 31 08 4 3 p e t k 1 61 2o 9 91 22 7 21 21 0 4 2 k 2 0 1 8 1 2 1 1 93 8 2 1 91 2 7 7 k 2 53 61 9 53 65 8 53 61 9 1 2 女 3 0 1 1 05 5 21 1 21 6 9 91 1 3 4 8 2 5 囹2 1 计算时问和参数七的关系 5 两北工业大学硕卜学位论立 图2 2 计算时间和参数k 的关系 卅 盯 从表2 1 和图2 i 可以看出 对于固定的n 5 p e l5 方法的计算时间大约是s b g s 方法的4 0 是块j a e o b i 方法的2 5 从表2 2 和图2 2 可以看出 当 厅时 p e ls 方法的计算时间大约是s b g s 方法的5 0 是块j a c o b i 方法的3 5 需要指出 对 于本算例 当0 3 时 p b 方法就不再收敛 对于m 的情况 随着阶数的增高 p 民方法的计算时间与s b g s 方法的计算时阳j 之比将会大于5 0 例2 2 线性方程组a r f 的系数矩阵0 形如式 1 4 所示 分别取 置 丑 4 h p 1 14 1 4 而9 2 1 一昙4 g 1 2 其中p 2 i h f l r n 吼 j h l n h o 1 分别用p 匕方法 块j a c o b i 方法和s b g s 方法求解此方程组 计算结果见表2 3 和表2 4 m a t l a b 语言p 1 5 0 g h z 微机 时间单位为秒 初始向量 1 1 1 终止准则为1 0 1 0 计算时间和参数 的关系见图2 3 表2 3 迭代次数争计算时间对比 n 5 g 慨 一2 4 一 一 c a 月删 i j h 4 1 一 堕苎三些查兰堡 兰堡笙苎 m 0 0 0 5 0 0 0 1 0 0 0 0 方法 次数时间 次数时间次数时间 块j a c o b i 1 6 71 5 0 8 1 6 77 5 5 31 6 71 5 2 4 s b g s 3 56 1 53 53 0 4 2 3 5 6 1 5 8 k 1 01 8 3 8 31 81 9 6 71 83 8 1 0 k 1 41 22 6 8 1 21 3 9 81 22 6 8 2 k 1 5 1 02 4 41 01 2 0 51 02 3 0 0 p e t k 1 61 02 3 21 01 1 9 91 02 3 0 6 k 1 71 l2 5 51 11 2 8 4 l l 2 5 0 6 k 2 01 53 3 0 1 5 1 6 7 01 53 2 9 9 表2 4 迭代次数和计算时问对比 脚 九 m 行 2 5坍 5 0 n 7 5 方法 次数 时间 次数 时间次数时间 块j a c o b i2 0 2 36 8 77 9 0 91 8 6 2 s b g s3 3 32 6 71 6 1 77 1 1 02 5 6 8 3 4 4 7 k 1 o 1 4 61 0 17 5 3 3 0 o l1 1 3 8 1 3 8 5 k 2 34 8o 3 92 0 47 9 73 5 8 4 4 9 4 k 2 44 2o 3 3 1 7 9 7 4 93 1 7 5 9 1 1 p e 女 k 2 55 30 4 11 5 6 5 6 82 7 95 1 7 7 k 2 6 8 3 o 6 01 3 53 7 22 4 4 4 5 2 6 k 2 71 9 31 4 22 0 3 5 2 l2 1 1 3 9 0 7 k 2 8 失效失效 失效 图2 3 计算时问和参数j i 的关系 从表2 3 和图2 3 可以看出 对于固定的订 5 p e l5 方法 或p e l6 方法 的计算 时间大约是s b g s 方法的4 0 是块j a c o b i 方法的1 6 从表2 4 可以看出最优参数 k 会随着m 和一的增大发生改变 例2 3 线性方程组出 的系数矩阵爿形如式 1 4 所示 分别取 西北t 业大学硕上学位论文 晟 一 1 兰 1 qi 一 2亨aq2 一 主矗 l 圭 屯 釉 一 2 h p 1 1 4 1 1 4 k 1 2 a c 置一o 0 0 0 1 i i 其中p f 1 h f 1 m q 2 j 一1 矗 1 n h 0 0 1 分别用p 岛方法 块j a c o b i 方法和s b g s 方法求解此方程组 计算结果见表2 5 m a t l a b 语言p i v 一1 5 0 g h z 微机 时阳j 单位为秒 初始向量 1 1 1 终止准则为1 0 o 表2 5 迭代次数和计算时间对比 n 5 埘 1 0 0m 5 0 0 打 0 0 0 m 5 0 0 0 方法 次数时间次数时间次数时间次数时间 块j a e o b i失效失效 失效 失效 s b g s 失效失效失效失效 k 1 o3 0 65 8 6失效失效失效 k 1 92 5o 5 1 2 5 2 6 0 2 5 5 2 34 34 3 4 0 k 2 0 2 2o 5 02 12 3 82 1 4 4 1 3 8 3 8 2 1 k 2 12 1o 4 52 02 1 1 2 1 4 4 2 3 4 3 4 7 2 p e 女 k 2 22 30 4 92 32 4 02 4 5 0 23 03 0 7 7 k 2 32 60 5 52 52 6 12 85 7 62 93 0 0 9 k 2 43 00 6 33 13 2 43 46 9 03 5 3 5 4 6 k 2 53 30 6 83 93 9 l4 28 4 56 26 1 5 8 扶表2 5 可以看出块j a e o b i 方法和s b g s 方法无法解决的情况p 磁方法可以解决 最优参数k 会随着m 的增大发生改变 西北丁业大学硕 卜 学位论文 第三章系数矩阵为m一 矩阵时算法的收敛性 本章主要讨论当周期块状三对角线性方程组的系数矩阵a为m 矩阵时 p e方法 和p e 方法的可解性和收敛性问 题 并针对p e 方法研究参数k 的选取范围 m一 矩阵 全称非奇异 m 矩阵 经常出 现在诸如偏微分 方程的 有限 差分 和有限元素 法 经济 学的投入产出法 运筹学中的线性余问 题等不同的科技领域中 m 矩阵这个术语是 o s t r o w s k i 在 1 9 3 7年首先提出的 其性质己 被广泛研究与应用 本节介绍的是可逆 m 一 矩阵 m 矩阵有多种等价定义 这里采用逆非负矩阵作为它的定义 而把其它的 等价定义作为性质来看待 3 1 预备知识 为了讨论p e方法和 p e k 方法的收敛性 需要介绍下面几个定义和引理 涉及的 矩阵a均指一般矩阵 定 义3 1 116 若 矩阵a a 满 足a j 1 2 n 则 称a 为 z 型矩阵 定义3 2 16 1 若矩阵a为z 型矩阵 且a o