（计算数学专业论文）非线性椭圆边值问题数值解的并行块单调迭代方法.pdf

摘要 本文对一类非线性椭圆边值问题的数值解建立了具有并行运算功能的块单调迭 代方法。主要内容包括用有限差分方法将非线性椭圆边值问题离散为一个非线性代 数方程组，并以上解或者下解作为初始迭代值，对该方程组解的计算建立了并行块 单调迭代方法，迭代序列单调递增或者单调递减地收敛于方程组的解，单调收敛性 给出了并行计算方法和解的唯一性条件。对本文建立的方法和块j a c o b i 方法产生的 单调序列给出了理论比较结果，比较结果表明本文方法产生的迭代序列具有更快的 收敛性。同时，我们在文中给出了一个简单而且容易验证的条件来保证并行块单调 迭代方法的几何收敛性。数值结果显示了并行块单调迭代方法的并行效率以及它的 优点。 关键词：有限差分方程组，非线性椭圆边值问韪，并行块状迭代方法，单调收敛 性，几何收敛，上解和下解。 a b s t r a c t ap a r a l l e lb l o c km o n o t o n ei t e r a t i v em e t h o df o rt h en u m e r i c a ls o l u t i o n so fa n o n l i n e a re l l i p t i cb o u n d a r yv a l u ep r o b l e mi sp r e s e n t e d t h eb o u n d a r yv a l u ep r o b l e m u n d e rc o n s i d e r a t i o ni sd i s c r e t i z e di n t oas y s t e mo fn o n l i n e a ra l g e b r a i ce q u a t i o n s ，a n d t h ep a r a l l e lb l o c km o n o t o n ei t e r a t i v em e t h o di se s t a b l i s h e df o rt h es y s t e mu s i n ga n u p p e rs o l u t i o no r al o w e rs o l u t i o n 嬲t h e i n i t i a li t e r a t i o n t h es e q u e n c eo fi t e r a t i o n si s s h o w nt oc o n v e r g em o n o t o n i c a l l ye i t h e rf r o ma b o v eo rf r o mb e l o wt oa s o l u t i o no ft h e s y s t e m t h i sm o n o t o n ec o n v e r g e n c er e s n l ty i e l d sap a r a l l e lc o m p u t a t i o n a la l g o r i t h m a sw e l la sas u f f i c i e n tc o n d i t i o nf o rt h eu n i q u e n e s so ft h es o l u t i o n v a r i o u st h e o r e t i c a l c o m p a r i s o nr e s u l t sf o rt h es e q u e n c e sf r o mt h ep r o p o s e dm e t h o da n d t h eb l o c kj a c o b i i t e r a t i v em e t b o da r eg i v e n t h ec o m p a r i s o nr e s u l t ss h o wt h a tt h ec o n v e r g e n c eo ft h e s e q u e n c ef r o mt h ep r o p o s e dm e t h o d i sf a s t e r as i m p l ea n d e a s i l yv e r i f i e dc o n d i t i o n i so b t a i n e dt og u a r a n t e eag e o m e t r i cc o n v e r g e n c eo ft h ep a r a l l e lb l o c km o n o t o n e i t e r a t i o n s t h en u m e r i c a lr e s u l t sd e m o n s t r a t et h ek i g he f f i c i e n c ya n da d v a n t a g e so f t h i sf l e wa p p r o a c h k e y w o r d s f i n i t ed i f f e r e n c es y s t e m ，n o n l i n e a re l l i p t i cb o u n d a r yv a l u ep r o b - l e m ，p a r a l l e lb l o c ki t e r a t i v em e t h o d ，m o n o t o n ec o n v e r g e n c e ，g e o m e t r i cc o n v e r g e n c e ， u p p e ra n dl o w e rs o l u t i o n s 1 l l 学位论文独创性声明 本人所呈交的学位论文是我在导师的指导下进行的研究工作及取得的研究成 果。据我所知，除文中已经注明引用的内容外，本论文不包含其他个人已经发表或 撰写过的研究成果。对本文的研究做出重要贡献的个人和集体，均已在文中作了明 确说明并表示谢意。 作者签名：日期：丝丑：1 9 学位论文使用授权声明 本人完全了解华东师范大学有关保留、使用学位论文的规定，学校有权保留学 位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版。有权将学位论 文用于非赢利目的的少量复制并允许论文进入学校图书馆被查阅。有权将学位论文 的内容编入有关数据库进行检索。有权将学位论文的标题和摘要汇编出版。保密的 学位论文在解密后适用本规定 学位论文作者签名：聋辛复 导师签名：王元调 第一章引言 许多物理、化学、生物和工程科学方面的边值问题都可以由非线性椭圆方程来描 述，对于此类方程已有许多定性分析( 参见【1 9 1 ) ，同时对非线性椭圆边值问题的数值方 法也有大量的研究工作( 参见【1 4 ，6 - 1 8 ，2 0 - 2 4 ，2 6 - 2 8 ) ，用有限差分方法研究非线性椭圆 边值问题的数值解，相应的离散问题转化为一个非线性代数方程组。考虑边值问题 ， i ( d ( 1 ) u 。) 。+ ( d ( 2 ) 甜+ ，( z ，y ，u ) = 0 ， ( z ，y ) q ， ，1 、 la o u & , + 触= g ( 茁，剪) ， ( z ，y ) 砌， 、 其中q 为一个两维连通区域，舶为q 的边界，o u o u 是u 在边界勰上的单位外法 向量，d ( 2 ) d ( o ( 为y ) ( f = 1 ，2 ) 是闭连通区域孬兰q u 鲫上的正函数，o t 兰 n ( z ，y ) 和卢三卢( z ，y ) 是锄上的非负函数，且有o + 口 0 。，和g 为各自定义域内 的已知函数。对微分边值问题( 1 1 ) 通过使用有限差分逼近，并且对网格节点按照字典 排序法排列，即先沿。方向从左向右，再沿y 方向从下到上排列，( 1 1 ) 的离散问题可转 化为一个非线性代数方程组，它的向量形式为 也屿一( 0 一1 + q 叻+ 1 ) = f a u j ) + g ；， j = 0 ，1 ， ( 1 2 ) 其中对每个j ，v j 为沿z 方向的未知向量，a j 是一个三对角矩阵，其形式为： a j = t r i d i a g ( 一b i j ，a i d ，一6 ，j ) ， ( 1 3 ) g 和q 是非负对角矩阵，其形式如下： g = d i a g ( c o , j ，。枷) ，c j = d i a g ( 晶扩，如j ) ，c o = = 0 ，( 1 4 ) 8 ( v j ) 和g ；分别是与函数，( ，u ) 和9 有关的向r ( 见- f 面的( 2 6 ) ) 定k a y - - 个w = ( n + 1 ) x ( m + 1 ) ) 的块状三对角矩阵，它的对角元素为对角子 矩阵山，a 1 ，a n ，下次对角线的元素为子矩阵一a ，一岛，一c n ，上次对角线的元素 为子矩阵一锑，一c k 一，定义向量 f ( u ) 三( f o c v o ) ，f ( ) ) t ，g + 三( g ，g 备) t( 1 5 ) 其中( - ) t 代表一个列向量，则非线性方程组( 1 2 ) 可以被写为如下形式： a u = f ( u ) - i - 口 ( 1 6 ) 上面出现的m 和分别代表z 轴和y 轴方向的网格点数。值得一提的是只要选择合适 的有限元基底函数( 参见 8 ，9 】) ，采用有限元素法也可得到形式( 1 6 ) 。 由于函数，( ，u ) 为关于t , 非线性，所以关于( 1 6 ) ( 或者( 1 2 ) ) 的一个主要问题是如何 得到一个可靠而高效的数值算法来求其解。目前已经有许多迭代方法被应用于求解这 样的方程组，一些众所周知的基本方法是结合上、下解方法的p i c a r d ，j a c o b i 和g a t l s s s e i d e l 迭代方法，这些方法称为单调迭代方法，并且已经被应用于不同的非线性问题， 包括抛物型边值问题和椭圆型边值问题( 参见【l ，3 ，6 ，7 ，1 0 - 1 2 ，1 4 ，1 6 - - 1 8 ，2 0 - 2 4 ，2 6 - 2 s ) ，也 被应用于通过有限元素法( 参见【8 ，9 】) 得到的类似于( 1 6 ) 这样的方程组。这些方法被应 用于四阶非线性椭圆方程( 参见【2 3 ，2 8 1 ) 和非线性积分椭圆边值问题( 参见f 2 2 】) 。 单调迭代方法的一个优点是迭代序列单调递增或者单调递减地收敛于非线性方程 组的解。序列的单调收敛性不仅可以产生迭代序列的比较定理，而且每次迭代可以给 出改进的解的上、下界。另一方面，因为初始迭代是上解或者下解，此上、下解可以 直接根据方程组来构造而不需要利用精确解的一些信息，这就使得迭代初始值的选取 非常便利。但是，绝大部分的单调迭代方法是基于点式p i c a r d ，j a c o b i 和g a u s s - s e i d e l 迭 代。使用点式p i c a r d 迭代解决一维问题的数值解是十分有效的，但解决两维或者两维以 上的问题，不是很有效( 特别当网格点数非常大的时候) ，因为每次迭代都需要解一个线 性方程组。点式j a c o b i 和g a u s s - s e i d e l 迭代方法在计算多维问题的数值解上都很容易执 行，但是这两种方法的收敛率低于点式p i c a r d 迭代( 参见【2 0 】) 。为了在保持运算简便性 的基础上提高收敛率，点式j a c o b i 和g a u s s - s e i d e l 迭代被推广为块状单调迭代方法，称 为块状j a c o b i 和块状g a u s s - s e i d e l 单调迭代方法( 参见 2 0 ，2 3 1 ) 。这些块状迭代方法在很大 程度上提高了点式单调迭代的收敛率，并且迭代序列可以由为人们所熟悉的求解线性 代数方程组的一般算法很容易地得到，比如说t h o m a s 算法( 参见【2 0 ，2 3 】) 。块状j a c o b i 迭 代方法具有并行功能，但是比块状g a u s s - s e i d e l 迭代收敛要慢。虽然块状g a u s s - s e i d e l 迭代比块状j a c o b i 迭代收敛速率快，但是很难用并行算法实现，因为对于每一次迭代我 们都需要求解一次三角方程组。 本文的目的是对( 1 6 ) 建立一个新的块状单调迭代方法，该方法具有如下优点： 首先，本文建立的方法具有和块状j a c o b i - - 样的并行计算功能，且迭代序列具有单 2 调性和几何收敛性：其次，与块状j a c o b i 相比较，本文方法具有较快的收敛率，同 时，我们的数值结果表明本文方法的收敛率有时也快于块状g a u s s - s e i d e l 迭代方法； 最后，本文方法中迭代序列的计算是简单的，因为每次迭代都可以像块状j a c o b i 和块 状g a u s s - s e i d e l 迭代一样运用t h o m a s 算法来计算。 本文由五部分构成：在下一章，我们将以上、下解作为初始迭代值，给出( 1 6 ) 的 并行块状单调迭代方法。这种迭代方法给出了一个并行的计算方法，而且迭代序列单 调地收敛于( 1 6 ) 的极大解和极小解。我们还将给出解的唯一性条件，讨论上、下解的 一些构造技巧。在第三章，我们将并行单调迭代方法和块状j a c o b i 单调迭代方法分别产 生的单调迭代序列进行比较。比较结果表明，并行块状单调迭代方法的收敛速度快于 块状j a c o b i 迭代方法。在第四章，我们将估计并行块状单调迭代方法的收敛率，同时给 出一个简单的保证几何收敛性的条件。最后在第五章中，我们将给出一些数值结果表 明迭代序列的单调性、几何收敛性及其并行性，且与块状j a c o b i 和块状g a t m s - s e i d e l 方 法做比较，显示本文方法的优越性。 3 第二章并行块单调迭代方法 第一节并行块单调迭代方法 为了显示我们考虑( 1 2 ) 的动机，我们在矩形区域q = ( 0 ，l 。) x ( 0 ，l 。) 上考虑边 值问题( 1 1 ) ，令h 。= 厶m 为z 坐标轴方向的步长，b = l p 为坐标轴方向的步 长，且令( 戤，协) = ( i h 。，j ) ( i = 0 ，1 ，2 ，m ；j = 0 ，1 ，2 ，) 为网格剖分点。在 区域q 和而上网格点的集合分别由a 和五表示，在下面的文章中，我们可能使用下 标( ，j ) 代表网格点( x i ，协) 。我们定义： 地j = u ( 盈，协) ，五j ( u 甜) = f ( x t , y j ，地j ) ， 历j = 9 ( 如，协) ， ( 2 1 ) o = a ( 甄，协) ，风j = f 3 ( x ，协) 对微分边值问题( 1 i ) 通过使用标准中心差分逼近，我们得到有限差分方程组的形式如 下： a i j u i j 一( b t j u i l a - i f 醚i j 地+ 1 j + c , j u i , j 一1 j r - c j u i j + 1 ) = 五j ( 地j ) + 蛇， ( i ，j ) 五，( 2 2 ) 其中 b o , j = 醯幻= c ，0 = = 0 ， i = 0 ，1 ，mj = 0 ，1 ， ( 2 3 ) 蜗和( 1 1 ) 的边值条件有关。对于内部网格点( 兢，协) a ，( 2 2 ) 的系数形式如下： ， lb i j = ( 1 h ：) d 0 ( 鼢一k 2 ，协) ，磁j = ( 1 h ：) d 1 ( 如+ k 2 ，协) ， c i , j = ( 1 嵋) d ( 2 ( 轨，蚴一h l ，2 ) ， j = ( 1 ；) d ( 2 ( 既，盼+ h 口2 ) ， ( 2 4 ) io 叫= + 6 ；j + q j + j ( 例子详见【4 】) 。对于边界点( 魏，蜘) 0 = 0 ，m ，j = 0 ，1 ，或者j = 0 ，n ，i = o ，1 ，m ) ，上述系数与( 1 1 ) 的边界系数啦j = d ( 翰，协) 和危j = p ( 戤，珊) 有关，并 且有如下性质 a i j 0 ，玩j 0 ， 嘭j 0 ， 白j 0 ， j 0 ，a i j 玩j + 6 ，j + q j + j ( 2 5 ) 4 进一步地，当边界条件不是纯n e u m a n n 条件的时候，也就是p ( 茁，y ) 不恒为零，至少存 在一个( 1 ，j ) ，使得上述最后一个不等关系为严格不等式。对于每个j = 0 ，1 ，2 ， 我们定义向量 = ( u 咿，u f j ) r ，g ；2 ( 奶，旃j ) 丁， 乃( g j ) = ( o a “o j ) ，加j ( n m j ) ) t 那么方程组( 2 2 ) 可写为( 1 2 ) 的形式或其等价形式( 1 6 ) ，并且，丽的连通性保证了矩 阵一4 是不可约的( 参见 2 5 1 ) 。 根据( 2 4 ) 和( 2 5 ) ，对矩阵( 1 6 ) 中的a 我们给出如下假设： 假设( h ) 矩阵是不可约的，且有 龟j o ， j o ， ( 2 7 ) i = 0 ，1 ，2 ，尬j = 0 ，1 ，2 ， 假设( 日) 的一个直接结果是对于任何一个正对角矩阵r j 和任何一个非负对角矩 阵d o ，矩阵( 如+ r j ) - 1 ( j = 0 ，1 ，) 和( a + 口) 。存在而且是非负的( 参见【5 ，2 5 】) 。 并且，一4 的最小特征值知是非负的实数( 这里的最小特征值指模最小的特征值) 。 如果卢( z ，y ) 不恒等于零( 比如d i r i c h l e t 边值条件和r o b i n 边值条件) ，那么至少存在一 对( ，j ) ，使得0 4 j + 磁，f + q j + ，成立，且4 _ 1 是一个正矩阵，最小特征值a o 是正 的( 参见f 5 ，2 5 0 。否则，如果( z ，y ) 兰0 ( n e u m a n n 条件) ，那么对于任何的( i ，j ) ，a i d = 4 - 6 ：，4 - q j + ，成立，且矩阵a 是奇异的，最小特征值k = 0 ( 参见【5 ，2 5 】) 。假 设( 的另外一个有用的结果给出如下： 引理2 1 ( 见【2 6 】) 假设( h ) 成立，令口= d i a g ( d l ，d ) 是一个对角矩阵，m i m 画 - a o ，那么( 4 + 口) 4 存在且非负。 为了对( 1 2 ) 建立一个新的并行块状单调迭代方法，我们利用上、下解方法，上、 下解的定义给出如下： 定义2 1 如果向量厅三( 玩，巩) t 满足以下条件， a 一( q 一，+ q + - ) 2 易( 码) + 嘭， j = 0 ，1 ，( 2 8 ) 则称厅为( 1 2 ) 的上解。如果向量驴；( 0 0 ，氐) t i 满足 如玩一( q 玩一t + q 玩+ ，) s 乃( 玩) + g ， j = 0 ，1 ，n ( 2 9 ) 5 口岛 磁+ 狐小 哳醒 m 梳 一 毗 毗 ，、【 则称疗为( 1 2 ) 的下解。如果疗疗，则上、下解疗和d 被称为是有序的。 对于等价问题( 1 6 ) ，上面的定义等价于 _ 厅f ( 厅) + g + ，4 疗f ( 驴) + g + ( 2 1 0 ) 很明显地，( 1 2 ) 或者( 1 6 ) 的每一个解既是上解也是下解。 给定任何一对有序上、下解疗= ( 玩，西) t 和疗；( 玩，巩) t ，我们定义集 合 ( 疗，厅) 兰 矿r ；疗u 疗) ，( 玩，玩) 三 r f + 1 ；玩玩) ，( 2 1 1 ) 且定义 m 一三m a o c 一等( u 动；钆啦。) ，f j - d i a g ( 可。护) ，( z - z ) ， 其中砚j 是任何满足砚j m j 的正实数，玩j 和 t j 分别是向量疗和疗的分量，则问 题( 1 2 ) 等价于 ( 山+ r j ) = q 一1 + q + 1 + r j + 乃( ) + g ；， j = 0 ，1 ，2 ，n ( 2 1 3 ) 从( 2 1 2 ) 很明显地得到r j 是一个正的对角阵( 由此可得( + l ) 一1 o ) ，且对于任何 的2 巧k ， 0 巧+ 毋( ) 2 d 巧十乃( 巧)( 2 1 4 ) 我们现在以上解u 或者下解u 作为初始迭代值，给出并行单调迭代算法。假设 并行计算系统上有p 个处理器，且存在一个正整数q ，满足n = p q + r 一1 ，其 中0 r 0 的情形，可以类 似地处理( 见注释2 3 1 。 令如，如是非负整数序列0 ，1 ，2 ，的一个重排列，也就是，存在一个整数 函数? 使得 z ( k ) = 靠， k = 0 ，1 ，2 ， 对于任何一个1 = 1 ，2 ，p 和k = 0 ，1 ，2 ，q 一1 ，我们定义 j q ，k ) = z ( q 一1 ) q + ) ，巧，= j q ，o ) ，j q ，1 ) ，j q ，) ) 6 ( 2 1 5 ) 巧，一1 = ( n u l ls e t ) ( 2 1 6 ) 并行单调迭代方法：对于每一个k = 0 ，1 ，2 ，q 一1 ，通过迭代格式 ( ) + ) - ( m + ，l 脚) = q “) k 竺，+ q ( 1 ，k ) 嗡? 。+ f j ( z 朋叼：) + 乃( 1 ，t ) ( 嘭；：) ) + g ( f ” 计算嘭：妒( j = 1 ，2 ，p ) 的值，其中初始迭代值u ( 。) 是扩或者疗，且 “。+ 1 ) 一j 巧覆挈1 ， 如果对于某一r ：1 2 ，p ，j ( t ，七) 一1 巧，卜l ， 。“ 卜1 1 u j c m 妒 1 ， 碱 1 ，忡+ 1 ) 一j 嘭墨嚣l ， 如果对于某一f 1 p ，j ( t ，南) + 1 巧，卜l ， 。 h 1 1 嘁 酬 ( 2 1 8 ) 因为( a ( z ， ) + l ( f ) ) _ 1 是一个非奇异矩阵，且具有性质 ( a 们柚+ r 椰) ) 一120 ，( 2 1 9 ) 所以由( 2 1 7 ) 求得的序列是良定的。显然，上述并行块单调迭代方法具有如下基本优 点： 系数矩阵山( 1 ，) + f j ( 女) 是一个三对角矩阵，这些序列可以像块状j 猢b i 和块 状g a u s s s e i d e l 迭代一样通过t h o m a s 算法求得，其运算规律和解决一维问题完全 一样。 当p 1 时，这种算法具有很强的并行运算功能，因为对于任意一个 = 1 ，2 ，p ，u j ( m + 1 ) 可以相应的在由p 个处理器构成的并行计算系统的第f 个处理器 上运算而得到，并且计算任务是独立的，可以在不同处理器上同时完成。同时， 由于数据存储和计算任务被平均分配到了p 个处理器上，这就在很大程度上节省 了时间和存储空间。 当p = n + 1 ，q = 1 ，且z ( k ) = k ( = 0 ，1 ，2 ，) 时，上述迭代格式就是块 状j a c o b i j 塞代( 参见【2 0 】) ，现给出如下： 7 块状j a c o b i 迭代：对于任意一个j = o ，1 ，n ，通过如下公式计算巧”1 ( 如+ l ) 嘭”d = g 嘭m 2 + q 嘭省+ d 蟛州+ 乃( 以神) + q ， ( 2 2 0 ) 其中迭代初始值u ( o ) 是厅或者疗。 当p = 1 ，q = n + l ，且z ( 七) = k ( k = 0 ，1 ，2 ，) 时，如上迭代就变为下面的块 状g a u s s - s e i d e l ：i 塞代( 参见【2 0 】) ： 块状g 卸s s _ s e i d e l 迭代：对于任意一个j = 0 ，1 ，通过如下公式计算珂”+ 1 ( a j + l ) 巧”“= q 嘭等d + q 喇+ r y j 州+ 乃( 蟛帕) + q ， ( 2 2 1 ) 其中迭代初始值u ( o ) 是疗或者疗。 在上述并行单调迭代中p 和q 的不同取值产生不同的并行算法，现给出上述并行 单调迭代的两种特殊算法： 算法i f o r j = 1 ：2 ：2 【下n - 1 j + 1 ， ( 如+ r j ) 吨”+ 1 = g 咙m 2 + q 叼籍+ d 蟛州+ 乃( 巧州) + q ， e n d f o r 办 f o r j = 0 ：2 ：2 l 譬j ， ( a + l ) 叼”“= g 巧等d + q 蟛等”+ f j u ( m ) + 乃( 叼呻) + q e n d o rj 算法i i f o r j = 0 ：2 ：2 l 譬j ， ( 如+ r j ) 叼”“= g 咙要_ b 。t 1 j t 。 t i j + m 。) + r y j 州+ 乃( 以州) + q ， e n d f o rj i f o r j = 1 ：2 ：2 l 等+ 1 ， ( a + r j ) 咿“= g 巧等”+ q 叫嚣”+ r j 西州+ 乃( 叼州) + 嘭 e n c f f o rj r 当u ( o ) = 疗时，记由上述并行单调迭代算法产生的序列为 可”) i 百护，百留 ； 当u ( o ) = 疗时，记其对应的迭代序列为 型( ”) i 驴，翌妒) ，我们分别称这两个 序列为极大和极小序列。下面的引理给出这些序列的单调性。 引理2 2 由( 2 1 7 ) 产生的极大序列 可m ) ，极小序列 型( ”) 具有如下的单调性质 疗型( m 必m + 1 可m + 1 伊m 疗，m = 1 ，2 ，( 2 2 2 ) 并且对于每一个m ，伊”和旦m 分别为( 1 2 ) 的有序上、下解。 证明：当矿( 0 ) = 疗时，令由( 2 1 8 ) 产生的序列为 矿”) 三 矿护，矿妒) ， 当u 。) = 疗时，其对应的序列为 笪( ”) 三 纷，j 岔) ，令形嚣o ) = 碟，o ) 一 玩：k = 玩“o ) 一亓j o q , o ) ( 1 f p ) 因幽j v 刮，j 1 1 ( t o ) 一1 = 碟，0 ) - l = 玩( f ，0 ) - 1 ，且谚+ l = 可j 0 u , 0 1 + 1 = 嘭( 1 p ) + l ，由( 2 1 7 ) 永i ( 2 8 ) 得出 ( 如( 1 。) + r j ( f 0 ) ) 可嘿o ) = 山( 1 ，o ) 玩( f ，o ) 一g ( 1 ，。) u j ( t ，o 卜l c ! ；( 1 ，o ) 玩( 1 ，。) + 1 一乃( f ，o ) ( 玩( f ，。) ) 一哆( i ，o ) 0 根据( 2 1 9 ) ，可嘿。) 20 ，由此推出对于每个j = 1 ，2 ，p ，有玩：i 。) 磔 0 ) ，使用 关系( 2 9 ) ，通过类似的推理得出对于所有的1 = 1 ，2 ，p ，有蟛 l o ) 鳞? 脚成立。 令叫2 j _ ：。) = 玩一鳞k 由( 2 1 7 ) ， ( 4 ( 1 ，o ) + r j ( f ，o ) ) 喇o ) = q ( f ，o ) ( ( 1 o ) 一1 一( f 0 ) 一1 ) + q ( 1 ，o ) ( ( 1 ，o ) + l v s ( 1 ，o ) + 1 ) + l ( 1 ，o ) ( 玩( f ，o ) 一玩( 1 ，o ) ) + 乃( f ，o ) ( 玩( f ，o ) ) 一乃( 1 o ) ( 玩( 加) ) 再由( 2 1 4 ) 以及g 和q 的非负性可得( 冯( z ，o ) + l ( f ，o ) ) 喇拦o ) 0 ，又从( 2 1 9 ) 得，对 于所有的f = 1 ，2 ，p ，有喇如) o 成立。如上的结论说明，对于所有的l = 1 ，2 ，p ，都有瑚o ) 鸟咎。) 彰：i 。) 矽盟0 ) 成立。假设 瑞砷s 玛s 谚墨碟2 朋 ( 2 2 3 ) 对于所有的l = 1 ，2 ，p 和所有的0 冬七k 成立，其中0 q 一2 。由( 2 1 8 ) 得 出 巧。) - l 豌。) _ 1 ，e + 1 ) + ，唬。卅， 蛾州一。2 甥+ 1 ) 叫瑞川+ 。蟛+ 1 ) + 1 乃孙一。瑙叫乃孙删+ ，玛删十r 9 ( 2 2 4 ) 通过使用这些关系，运用与k = 0 时同样的推理过程可以证明当= + 1 时( 2 2 3 ) 仍 然成立由数学归纳法得，对于所有的z = 1 ，2 ，p 和k = 0 ，1 ，口一1 ( 2 2 3 ) 成立。 也就是堑( o 型( 1 铲1 移( 。 假设对于某个m o o ，( 2 2 2 ) b - 裁# ，那么由( 2 1 8 ) ， 碟赫1 = 拶j 高( 1 nj ( 1 ，o ) 一u ，o ) 一1 碟瑟k 破蒜j 所以刃龛苗”一_ ? 。t 州( tt o ，0 ) o + 1 1 一矽黯满足 v 。( r n 。o + 1 k 矽端+ 。 磙搿l = 破蒜j ( 4 ( f 。) + d ) ) 可嘣= g ( f 。) ( 刁揣一l 一蟒j ) + q ( 1 。) 、( 。r - t f l 州m ，o ) o ) + 1 一移。州j ( m ，o ) o + + 1 ) l ，x + l ( ) ( 矽窃盎一蠕1 ) + b ( 加) ( 5 高) 一日( 加) 、i v i - t 川( rm ，0 ) o + 1 ) 再由( 2 1 4 ) 、不等关系伊”铲”+ ”、g 和q 的非负性推出( a ( 加) + r j ( 啪) ) 可嘭掰1 0 a 由此得出对于所有的f = 1 ，2 ，p ，黟满1 0 ，也就是可黯1 谚掰2 成立。 类似的推理可得对于所有的f = 1 ，2 ，p ，_ y y j ( r a o + 2 1 u ( m o + j1 和谚箔卸蟛掰2 成 立。由对的归纳推理得出 孥东：； 一 u 。( t o 。o + ，2 s 可宝荡”一 一a o ，且对于任何的u ，有 f ( u ) 一f ( u 7 ) 一口( 矿一u 7 ) 那么问题( 1 2 ) 和( 1 6 ) 有一对有序上、下解。 证明：证明是构造性的。给定任何的v r y ，令缈是线性方程组 ( 2 3 0 ) ( a + v ) w = i a v f ( v ) 一g + i ，( 2 3 1 ) 的解，其中对于任何的p r x ，l v + i 代表一个由v + 的分量的绝对值组成的向量。因 为m i 啦也 一，由引理2 1 知，( 一4 + d ) - 1 存在且是非负的。这就充分说明了解w 唯 1 2 一地存在且w 0 。令疗：v + 且有疗：v w ，那么厅v2 疗，而且 由( 2 3 0 ) 和( 2 3 1 ) 得， 一4 疗一f ( 厅) 一g + 一a v + l a y f ( y ) 一g + i d w f ( 疗) 一g 2 r ( v ) 一f ( 疗) 一口彤0 由此说明疗是( 1 6 ) 的上解，类似地可以证明疗是下解。口 关于有序上、下解构造的更多结果请参考文献【2 0 】o 第三章单调序列的比较 第一节块状j a c o b i 迭代与并行块单调迭代方法序列的比较 在这一节中我们给出由并行块状迭代方法( 2 1 7 ) 和块状j a c o b i 方法( 2 2 0 ) 分别得到 的单调序列的一些比较结果。令疗和疗是( 1 2 ) 的一对有序上、下解，r j 是( 2 1 2 ) 中的 对角矩阵记由( 2 1 7 ) 和( 2 2 0 ) 分别产生的极大序列和极小序列为( 可掣， 型绺 ) 和 ( _ 苗) ，型苗) ) ，则这些序列单调地收敛于( 1 2 ) 在( 疗，疗) 上的极大解可和极小解卫， 且满足关系( 2 2 5 ) 。我们现在用此单调性来比较序列( 可掣) ， 翌蝌) ) 和( 百留) ， 盛 ) 。 定理3 1 令疗，疗是( 1 2 ) 的一对有序上、下解，且有假设( 日) 成立，那么极大、极 小序列( 可掣) ， _ u z b 和( - - u b ( m j ) ， 盈) ) 单调地收敛于( 1 2 ) 在( 疗，厅) 上的极大、极 小解( 可，翊，且满足关系( 2 2 5 ) ，进步地， 可蹭可嚣，型管型嚣，m ；1 ，2 证明：我们只需要证明( 3 1 ) ，令 崩= ( 帝，露) t ，- - 岫( m = ( 毋，砖) 丁， 令由( 2 1 8 ) 产生的极大序列形路) 的中间序列为 矿嚣 = ( 宵，- - v ( m ) r ) ( 3 1 ) ( 3 2 ) 为了证明关系可绺驴器，我们令刁”) = x p 一矿罗，关于 可嚣) ； ( 叉护，x 妒) t ) 的 迭代公式( 2 2 0 ) 可以被改写为 ( 山( 1 ， ) + f j ( f k ) ) 冠蒿 = g ( f k ) 磁) 一。+ q “的蜀础) + 。+ l ( 1 ，k ) ) 嗽) + 乃( 1 ) ( 冠豫) ) + 嘭( 1 印 ( 3 3 ) 其中k 一0 ，1 ，q 一1 和f = 1 ，2 ，p 。用( 3 3 ) 式减去( 2 1 7 ) 式，得出 ( 坞( 1 t ) + d “耐) 零荔) - o “姊( 习苏) 一。一z 嚣嚣。) + q 埘( 骜豫) + l 一- - vj ( 嚣般，) + l ( 1 埘( 冠豫) 一蹴) ) + 乃“姊( 冠础) ) 一乃( 1 q ( 啦) ) ( 3 4 ) 1 4 因为矿黠2 ls 百撼) 一。和啦导。刁撼) + 1 ，结合( 3 4 ) 和c j ( 1 k ) 与q ( 1 柚的非负性质， 得 ( a ( 1 ，) + f j ( 1 朋) 蹴m + 埘l ) ( 磁) - 1 一啦) _ 1 ) + q “砷( 磁) + 1 一可黜) + 1 ) + d ) ( 冠豫) 一彰础) ) + 乃( 1 ，* ) ( 冠豫) ) 一乃“。) ( 玩戳) ) ( 3 5 ) 此式可以被改写为 ( 山+ d ) 2 j 卅1 g ( 雄；一雄；) + q ( 砍i 一。r - 一r ，m + 。) ， + l ( 矽一矽) + 乃( 了【m ) 一乃( 矽) ， j = o ，1 ，2 ， ( 3 6 ) 上式中，令m = 0 ，对于所有的j ，有霹= 可【0 ，我们得到 ( 如- 4 - d ) 雹1 0 因为对于任何j ，有( 如+ r a _ 12o ，所以刁”0 ，也就是对于所有的j ；0 ，1 ，n ， 有冠1 彰”。通过使用( 3 6 ) 、( 2 1 4 ) 和g 与q 的非负性质，由归纳推理得，对于 所有的j = 0 ，1 ，n 和所有的m ，有叉剪。由此证明了对于所有的m ， 有可黑可器，这就证明了( 3 1 ) 的第一个关系成立。关于极小序列的第二个关系的证 明是类似的。口 定理3 1 的比较结果表明了选取相同的上解或下解做为迭代初始值，由并行块状单 调算法( 2 1 7 ) 产生的序列收敛速度大于块状j a c o b i 迭代( 2 2 0 ) 。这个结论表明了并行块 状单调迭代解法( 2 1 7 ) 更适合于并行数值计算。 并行块状单调迭代( 2 1 7 ) 和块状g a u s s - s e i d e l 迭代( 2 2 1 ) 之间没有明确的比较结 果。在第五章中我们的数值实验表明并行块状单调迭代f 2 1 7 ) 的收敛速度有时快于 块状g a u s s - s e i d e l ；i , 塞_ 代( 2 2 1 ) ，但是，我们注意到块状g a u s s s e i d e l j 医代是难于并行计算 的，因为每一个迭代都需要解一个三角方程组。 第二节不同r 值的并行块单调序列的比较 我们接下来对不同的l 由并行块状单调迭代( 2 1 7 ) 产生的序列建立类似的比较结 果。令d 是( 2 1 2 ) 中的对角矩阵。设e 是另外一个对角矩阵，二者满足关系e f j 。 1 5 那么q 0 。在( 2 ，1 4 ) 中，将e 代替l ，不等关系仍然成立。在( 2 1 7 ) 中用e 代 替r j ，并设相应的极大、极小序列为 矿”) 和 型( m ) ，其中矽：疗且垡o ) ；疗， 那么这些序列分别单调地收敛于( 1 2 ) 在( 疗，疗) 上的极大解可和极小解望。且满足关 系( 2 2 5 ) 。令 可” 和 卫( m ) 分别为由( 2 1 7 ) 产生的极大序列和极小序列，其中仃( “： 移和型( o ) = 疗，对于这些序列，我们有如下的比较结果。 定理3 2 设定理3 1 中的条件成立， ( ”) ， 垡m ) 具有如下的性质 那么极大、极小序列( 可”) ， 堑( m ) ) 和 可”，( m s 型( 嘲，m ：1 ，2 证明：考虑极大序列 驴”) 和 ” ，设 可”暑，可寸) t