（应用数学专业论文）基于cn格式的并行差分方法及其数值分析.pdf

ab s t r a c t a l o n g w i t h t h e d e v e l o p m e n t o f p a r a l l e l c o m p u t e r s , a s o r t o f p a r a l l e l d i ff e r e n c e m e t h o d , c a l l e d d o m a in d e c o m p o s i t i o n , h a s b e c o m e a p r a c t i c a l a n d e ff e c t i v e m e t h o d f o r s o l v in g i n p a r a l l e l l a r g e - s c a l e 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 s . i t m a y d i v i d e t h e d o m a i n f o r s o l v i n g p a r ti a l d i ff e r e n t i a l e q u a t io n s i n t o s e v e r a l s u b d o m a i n s s u c h t h a t c h a n g e t h e w h o l e p r o b l e m i n t o a f e w s u b d o m a i n p r o b l e m s o n s e v e r a l s u b d o m a i n s , w h i c h c a n b e d e a l t w i t h r e s p e c t i v e l y a n d i n d e p e n d e n t l y . t h e c e n t r a l d i ff i c u l ty o f d e s i g n i n g a d o m a in d e c o m p o s i t i o n m e t h o d i s h o w t o c o n s t r u c t p r o p e r l y t h e a p p r o x i m a t i o n o f t h e s o l u t i o n s a t t h e s u b d o m a i n i n t e r f a c e s s o t h a t m a k e t h e g l o b a l m e t h o d h a v e i d e a l s t a b i l i ty . t h e f a mo u s c r a n k - ni c o l s o n s c h e me i s a d i ff e r e n c e f o r n n i l a wi t h s e c o n d o r d e r p r e c i s i o n a n d i s p a i d m o r e a t t e n t i o n i n b o t h t h e o ry a n d p r a c t i c e . b u t t h e c l a s s i c a l c r a n k - n i c o l s o n s c h e m e i s i m p l i c i t a n d i t n e e d s t o s o l v e i n p a r a l l e l s y s t e m o f t r i d i a g o n a l e q u a t i o n s , w h i c h c a n t i m p l e m e n t p a r a ll e l c o m p u t a t i o n d i r e c t l y . b as e d 。 t h e c r a n k - n i c o l s o n s c h e m e , t h e p a p e r c o n s t r u c t e d t w o p a r al l e l fi n i t e d i ff e r e n c e m e t h o d s w i t h d o m a i n d e c o m p o s i t i o n a n d d i s c u s s e d t h e s t a b i l ity o f t h e m . t h e p a p e r i s o r g a n i z e d as f o l l o w s . i n c h a p t e r 1 , i t b r i e fl y r e v i e w e d t h e r e s e a r c h s i t u a t i o n a n d m a i n a c h i e v e me n t s o f t h e p a r a l l e l fi n i t e d i ff e r e n c e m e t h o d s u s e d t o s o l v e h e a t e q u a t i o n s . i n o r d e r t o m e e t t h e r e q u i r e m e n t o f t h e n u m e r i c al a n a l y s i s i n t h i s p a p e r , c h a p t e r 2 i n t r o d u c e d s o m e p r e p a r a t i o n k n o w l e d g e a n d d i s c u s s e d a b as i c d i ff e r e n c e s c h e m e . i n c h a p t e r 3 , b as e d o n t h e c r a n k - n i c o l s o n s c h e m e , t h e p a p e r p r e s e n t e d p a r a l l e l d i ff e r e n c e m e t h o d i w it h d o m a i n d e c o m p o s i t i o n , w h i c h c al c u l a t e d v al u e s o f t h e i n t e r i o r b o u n d a ry p o i n t s b y m e a n s o f c l as s i c al e x p l i c i t s c h e m e a t t h e b o u n d a ry o f s u b d o ma i n s a n d s o l v e d , w i t h t h e c r a n k - n i c o l s o n s c h e m e , t h e p r o b l e m s w i t h i n t h e s u b d i m a i n s . t h e s t a b i l i ty o f t h e al g o r i t h m w as a l s o a n a l y z e d , w h i c h l e d t o t h e c o n c l u s i o n t h a t t h e s t a b l e c o n d i t i o n i s r 41 . s t i l l b ase d o n t h e c r a n k - n i c o l s o n s c h e m e , c h a p t e r 4 a d v a n c e d p a r al l e l ab s t r a c t d i ff e r e n c e m e t h o d ii w i t h d o m a i n d e c o m p o s i t i o n , w h i c h c a l c u l a t e d t h e v a l u e s a t t h e s u b d o m a i n in t e r f a c e s b y u s i n g g r o u p e x p li c i t s c h e m e d e r i v e d fr o m s a u l y e v n o n - s y m m e t r i c d i ff e r e n c e f o r m u l a a n d t h e n s o l v e d , w i t h t h e c r a n k - n i c o l s o n s c h e me , t h e p r o b l e m s w i t h i n t h e s u b d i m a i n s . t h e p a p e r , t o o , a n a l y z e d t h e s t a b i l i ty w h i c h r e s u l t e d i n r:5 1 . 4 6 4 1 wa s t h e s t a b l e c o n d i t i o n . f i n a l l y , a s u m m a ry w a s m a d e i n c h a p t e r 5 . k e y w o r d s p a r a l l e l fi n i t e d i ff e r e n c e m e t h o d ; h e a t e q u a t i o n ; d o m a i n d e c o m p o s i t i o n ; cr a n k - ni c o l s o n s c h e me 南开大学学位论文版权使用授权书 本人完全了 解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容:按照学校要求提交学位论文的印刷本和电子版 本;学校有权保存学位论文的印 刷本和电 子版，并采用影印、缩印、 扫描、 数字化或其它手段保存论文; 学校有权提供目 录检索以及提供 本学位论文全文或者部分的阅览服务; 学校有权按有关规定向国家有 关部门 或者机构送交论文的复印件和电子版; 在不以赢利为目 的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学 位 论 文 作 者 签 名 : 仁叫 州 9 .- q 年 日月， 飞 扫 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名:闷 尧 乡 凡 学位论文作者签名: 4 ; ;h j习 解密时间:年月日 各密级的最长保密年限及书写格式规定如下: 少一 内部5 年 ( 最长5 年，可少于5 年) 从 秘密1 0 年 ( 最长1 0 年，可少于1 0 年) 机密2 0 年 ( 最长2 0 年， 可少于2 0 年) 孟 _ _ 一几 _ _一 _、_了 二， : _ 南开大学学位论文原创性声明 本人郑重声明: 所呈交的学位论文， 是本人在导师指导下， 进行 研究工作所取得的成果。 除文中己 经注明引 用的内 容外， 本学 位论文 的研究成果不包含任何他人创作的、 已 公开发表或者没有公开 发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体， 均己 在文中以明确方式标明。 本学位论文原创性声明的 法律责任 由本人承担。 学 位 论 文 作 者 签 “ : 仁 ii i 刊名年 “月 日 第一章引言 第一章引言 1 . 1 热传导方程井行差分方法的建立 热传导方程可以描述许多自 然现象，例如:热传导、扩散等。因此讨论求 解热传导方程的数值方法具有典型的理论意义和应用价值。 求解热传导方程主要有有限差分方法、有限元方法等，其中有限差分方法 是求解热传导方程的比较有效的常用的方法之一。基本的有限差分方法包括古 典显式格式、古典隐式格式和c r a n k - n i c o l s o n 格式 1 1 。从并行计算的观点看， 古 典 显 式 格 式 计 算 简 单 ， 便 于 编 程 ， 但 这 种 格 式 是 条 件 稳 定 的 ; 与 。 古 典 隐 2 式和c r a n k - n i c o l s o n 格式是绝对稳定的， 但要求解整体的线性代数方程组，不 能直接实现并行计算。 八十年代以来，一种被称为交替分组显式的并行方法得到了人们的关注。 1 9 8 3 年，e v a n s 和a b d u l l a h 提出t组显式格式 ( g r o u p e x p l i c i t s c h e m e )的 思想.他们利用左右两个方向的半隐式的 s a u l y e v格式将两个相邻的网格点 组成一个独立的二阶线性代数方程组，通过解这个方程组得到一种显式格式。 当格点数是偶数时正好两两成组;当格点数是奇数时，有一个点用一个单独的 s a u l y e v 格式计算， 根据这个格点在左右可以 分为g e l 和g e r 两种格式， 同单 独的s a u l y e v 格 式 ( 截断 误差为o ( o t l h 十 、 旦 。 2 在文 5 中y u a n等人构造的 方法为: 在子区域的边界点处采用组显( g e ) 格 第一章引言 式求解，子区域内点用隐式格式求解。并得到稳定性条件为r 0 , c - n 格式 ( 2 . 1 . 5 ) 一 ( 2 . 1 . 7 ) 按 e u c l i d 范 数关于初值稳定。 显 然 ， c r a n k - n i c o l s o n 格 式 绝 对 稳 定 ， 但 第n 层的 可必 须 通 过 解 线 性 代 数 方 程组得到。 2 . 1 . 3 s a u l y e r 非对称格式的 组显 ( g e ) 格式: u 1 0 一 u j一 = 2 ( v + u j .+1 一 一 u 1) 十 全 + 一 、 ( 2 . 1 . 8 ) j =1 , 2 , . . . , j 一l , n =0 , 1 , . . . , n一 1 . 二 二r ， 二.一 二 1 、r u i+ i- ” 一 u i + i = 2 (v + u l + 1 一 n a. ,.) + z n + v u j+ l ( 2 . 1 . 9 ) j =1 , 2 , - 二 ， j 一 l , n =0 , 1 , - , n-1 可= u , ( j h ) u o = u j = 0 整理( 2 . 1 . 8 ) 得: j = 0 , 1 ， 二 ，. , j n = 1 , 2 , . . . , n 。r _ 。 二 ，r. 二 ，。_ 3 r _ 。r (1 十 - 1 n 1_ , 一 万 u i+ i- . - i - r u ,一+ ( 1 一 2 ) u , - + 2 u ,+ ( 2 . 1 . 1 0 ) 整理( 2 . 1 . 9 ) 得: r。 * ，_r.。 二 ，r。_3 r . 一 尹厂 ” + “ 十 2 )u ; + 0 ” _ 万 与 一 十 ( 1 - 2 ) u i+ 1 + ru i + z- ( 2 . 1 . 1 1 ) 利 用 泰 勒 公 式 将 (2 .1 .10 ) 在 点 份 .+ !u j x 处 展 开 得 : 从 1。一 rt2.1.10 -(2 h.默+ 护默_1+ 2+ 12 r)默十 _12) 材ii h 1 、1. 4. 1 ， 8 u l n -+ 1 3 ， 、in -1 1 ., e u l n om , tl .t -1 z十: 刃了 -1 z-m r . .丈 , i z-rc-i 2 ) 斗 a r e r . l 4 o r 碍 ， 卜 “m v + 0 ( r + h ) 第二章预备知识 将 (2 .1 .1 1) 在 点 、 号 处 展 开 得 : r h t 2 es 8 0u b x b1 in + 1 1 .: 8 u z 十 石 r n 蕊 巧 万 u n + 1 , z) 1-48 + 1一2 + n。了 u-斗朴 0一无 左 了烤 一一 几 1 a u in + 1 . 1 ， y u l n + 1 3 . ， 、in + 1， .， c10u in + l , 弋t 4 ， 稳 定 性 步长 限 制 较 古 典显 式格式 放大了7 倍。 定理2 . 1 . 4 ( 收 敛性) 若 r= 命 且 k 与 j - “ 充 分 大 则 ， 与 t 无 关 的 正 常 数 “ ， 使 得 (2 .1.12 ) 一 ( 2 .1 . 1 6 ) 的 任 意 解u i 的 误 差弓( 其 中弓 = 砰一 可 )j = -o , l , . . j n = o ,1 ， . . n .在l 2 范 数 下满足: lie . 卜 o ( r + h 2 ) b n = 1 ,2 , . . n - 1 收 敛性分析表明， 尽 管此方法在内 界点处的截断 误差为o ( r 十 h ) ， 但解的 整体误 差仍达到o ( r + h 2 ) 。 第三章 区域分裂法i 及其稳定性分析 第三章区域分裂方法 i 及其稳定性分析 3 . 1 区域分裂方法 i 我们知道对问题 ( 2 . 1 . 1 ) 格式。 本节设计的差分格式为: 处使用 c 一 格式。 作不同的差分离散，则可分别得到不同的差分 内 界 点x , 处 使 用 古 典显 式 ， 子区 域内 点x , ( j m k ) 将问 题 ( 2 . 1 . 1 ) 的 求解区 域 0 , 1 分 解为 两 个子 域10 , x k 及(x k ,1 1 ， 其中 1 kj一 1 。 方法 i : u n + l 一 可 = 地 + 一 n + -r a + a _ u j 2 u k + - u k = r a 十 _ u k u p = 弓= 0 弓= u o ( j h ) 1 _ j k , k j - j 一 1 , o s n - n- 1 ( 3 . 1 . 1 ) 0_n5n -1( 3 . 1 . 2 ) 1_nsn( 3 . 1 . 3 ) j = 0 , 1 , . 二 ， j ( 3 . 1 . 4 ) 3 . 2 方法 i 的稳定性分析 设 m = e (u j ) 2 j lj . k ( u f + l - u k ) 2 ( n k + 1) 2 + ( u k ) 2。 二 、 ， 一 1 则 方 法i 的 稳 定 性分 析 可 大 体 分为 两 步 骤 : m +1 m ; mh 与艺(可 ) 2h 的 等 价 性 下面首先证明0 r l 时， m + _ m , 0 5 n 5 n一 1 第三章区域分裂法 1 及其稳定性分析 由( 3 . 1 . 2 ) 得: u kr + 2 一 u t + = r a + a - u t+ ( 3 . 2 . 1 ) ， ， ( 3 . 1 .2 ) + ( 3 . 2 . 1 ) 二 只 a i 寸 : 2 u n+ 2 一 l,. .， 褚 -=r d- _ u , 2 ( 3 . 2 . 2 ) 用 2u , 2 乘 (3 . 1. 1) 两 端 ， 并 对 j = l,-,k - l,k + i,.-,j - 1 求 和 得 : j-1l r (u l+1 )2 一 (u:)z = zr .r-1 +! 一 +!(u j)2 = 2 r y u, 2a +a -uj 2 j = l j = ij f k i l k ( 3 . 2 . 3 ) 用 zu1n+-2 u k 2 乘( 3 . 2 . 2 ) 两端得: ( u tk + 2 ) 2 一 ( u k ) 2 ( u k + 2 一 u . + 1 ) 2k(u k + ， 一 u k ) 2 ( u k + 2 - u k ) 2 2 4 4 4 ( 32 . 4 ) .i = 2 r u k 2 a , a _ u , 2 m, = du ll ) 益 :( u k( + i 一 u ) 2u k 4 + (u k + 1 ) 2 + ( u k ) 2 ( 3 . 2 . 5 ) ( 3 . 2 . 3 ) + ( 3 . 2 . 4 ) 得: 二 一 、 一 n+2 nuk - u k ) 22 一 2 r u j 2a +a _u j 2 = - 2 r_ (a +u j 2 )2 ( 3 . 2 . 6 ) 将( 3 . 2 . 2 ) 代入( 3 . 2 . 6 ) 得: m .+1 一 、+ 2 r (a +ul 2) 2 一 ; 2 (a +a uk 2)2 一 。 ( 3 . 2 . 7 ) 记 a + u j 2 ， 鸟，j , = 2 艺o) j2 一 r (e co k ) z 则( 3 . 2 . 7 ) 可整理为: m. ， - m + r j , = 0 第三章区域分裂法 i 及其稳定性分析 可 知若丙非负定，则m + 1 g m o 下 面讨论j , 非负定的情 况: j 1 = 2 艺心十 2 雌， + 2 m i 一 r (co . 一 w k- 1) x j = 0 j s k , k - 1 = 2 ecoj + (2 一 r ) to k_ 1 + ( 2 一 r ) tn k + 2 r co k m k- 1 j 司 介 k , k - 1 由 ， 一 了一 (2 - r)2 - r 2 = 4 - 4 r ? 0 ir一r l 得:r 5 1 所以当0 r 1 时，j , 非负定 且此时m + 1 s m 下面考虑m h 与艺( . j ) h 的 等 价 性 。 丫 m _ e( u j ) 2 - j z kj = 1 ( u k + i 一 u t ) 2 4 + (u k + 1)tk . 、 ， ( u + 1 + u : ) 2 一 ， 一 十 - 4 (u) j-1艺川问 将 ( 3 . 1 . 2 )代入上式可得: ( u j . ) 2 + ( 2 u , + r - + k _ u k ) 2 4 (u j ) 2 + (1 一 r ) ( u , , ) 2 + r ( 1 一 r ) u k (u t - 1 + 、 + :. ) + 普 1(、 一 )2 + (uk十 !)2 + ， 一 、 +1 , 即: 第三章区域分裂法 i 及其稳定性分析 m = 又 介 k -l . k , k +l 片 l (u j,)2 + (i + 争 (，一 )2 + (uk+ i )2+ (i一 r) 2(u k.)2 + 、 一 、 k(u k- i + 、 十。 十 誓 、 一，。、 十: ( 3 . 2 . 8 ) 进一步，m. 可写成下式: 、 一 _ 。卖 _ (u )2 + 3 (一 )2 (uk-1n)2 + (u kl,)2 + (、 一 )2+ j 2 (3 . ， ， ， j = 1 其 中 。 一 1+ 2+ 21一 3 (1- r)2j(uk-l.)2 + (、 一 )2卜 告 。 一 )2(ukn)2 + (卜 )* ( 卜 ， + *十 :) + 普 卜 。一 + : 有: 尸-4 _ 尸 2 一 ， 、 1 + 一一( 1 一r ) 4 3 r ( 1 一r ) 2 11布 r ( 1 一 r ) ( 1 r ( 1 一 r ) 2 _ r 2 2， 、 1 +一 一，( 1 一r) 4 3 2尸-4 易证 又此时 0 r _ 号 ( 一 )2 iiu 0 p2 另一方面，由于o r 1 ，由( 3 . 2 . 8 ) 式知: 第三章区域分裂法i 及其稳定性分析 m 又 (u j )2 + 4 1(、 一 ， + (u k+ ,) + ( u k sk- l x. k + 1 ; =1 + 2 ( u , ) 2 + (u k - )全(u k + l ) z + 1 (u k _ , ) 2 + (u k + ) z 2 2 2 2 e (u , ) 反 p :m h2u i iz 2 ， 。 、 2 一 。 一 u一 r) 3-u .2 m h 2 llu iiz 于是 又知 0 r 时 ， m h 与 lu il， 等 价 。 0 r 1 时m + l m. 则 :号 (， 一 )2 il ll2 : “ ” m - h . m 0h 2 iiu 0il2 2， ，、 2 一 1 k一 r i 3 - ilu 取 c : 二 2门、 2 一 吸 k一 了 ， 3 于是得到下述定理: 定理3 . 2 . 1 若 ( 区域分裂方法 i 的稳定性) ; = 丢 1 ， 则 方 法i 的 数 值 解 按 离 散 几 范 数 关 于 初 值 稳 定 . 即 : : 与 n 二 无 关的 正常数c ， 使得方 法i 的 任意解u i . ，均满足不等式: llu l : c llu il b n=0 , 1 , 2 . . . n 第四章区域分裂方法n 及其稳定性分析 第四章区域分裂方法n 及其稳定性分析 4 . 1 区域分裂方法ii 本 节 设 计 的 差 分 格 式 为 : 子 区 域的 内 界 点x k , + : 处 分 别 使 用s a u l y e v 对称格式构成的组显 ( g e ) 格式，子区域内部采用c 一格式。 将问 题( 2 . 1 . 1 ) 的 求 解区 域0 , t 分 解为两 个子 域r x , 及l x , . , i , 的非 其中 1 k k +1 j 一 1 。 方法1 1 : 、 ， 一 可 一 峨 奴1uj+l- uj = ro +q u,2 1 j k ,k + l j - j - 1,0 n n - 1 u k - - u k * = 2 (d + u k + 一 - u k ) + 冬 q+4 tk a l 0 nn-1 ( 4 . 1 . 1 ) ( 4 . 1 . 2 ) u k + l + 1 一 气 十 厂 u o = u , = 0 心= u l ( i h ) =二 2 . 月、r 。 ( u + u k + l” 一 v + u k . - + 2 v + 一 u k + 1 . 0 n n一 1 ( 4 . 1 . 3 ) 0nn-1( 4 . 1 .4 ) j = 0 , 1 , . . . , j( 4 . 1 . 5 ) 4 . 2 方法ii的稳定性分析 设 扩=艺(u j ) z 十e j -*. k + l j _t , k + l (u in + 1) 2 + (u , ) 2 2 日 + . 、 2 f k- j行- j j j =k x+ 11 则 方 法1 1 的 稳 定 性 分 析 可 大 体 分 为 两 步 骤 : m + 1 5 m ; m h 与 艺( 心 ) 2 h 的 等 价 性。 第四章区域分裂方法n 及其稳定性分析 下面首先证明:当0 r 1 .4 6 4 1 时， m. + m. d n =0 , 1 , 2 二 ， n - 1 由 ( 4 . 1 .2 ) , ( 4 . 1 .3 ) 联立方程组，解出 u k n + 1 二 1 十rzr uk+z* + r (1- r )u k+i, + (1- r )(1+ -r )uk,4 2 2 2 2 r +一【 1 十 2 - 十 匕 、 _ 4u k+. + 全 “ + 钾十 一明 1 , r 2 。 . ， r 2 、 二 . 八r 2 ,。 . ，. 尸 、 _ -l 弋 丁 u k + z十甘-弋 犷 l u k + i十l k 一r -二 丁 l u k十k r 十茸 丁 1 u k - i k州 卜r“ ( 4 .2 . 1 ) 气 + 1 l +r , r z + 2 r 卜百 一u k + z 十 、 ; -私+l + 2 (1- 2 )u k+ 百u k _ i r 2 r . . + 一 +二) 0 一 42 . r 2 + v u k + ，一 + 百v + v u k 一 一 牛(r + - , )+k2 十 z + 。 一 ， 一 r 2- - , )u k+. + (; 一 z + z)u k + u k-l* ( 4 . 2 .2 ) ( 4 .2 . 1 ) 两端分别 减去u ; ， ( 4 .2 .2 ) 两端分 别 减去u a + 进一步整理得: u k . + ， 一 u k . = r a a + qu k + ( 1 一 a ) 0 + 0 - u k + i k 气 + ，. +u k + i ， 一 u t + i - r a o + o 一 u t + + ( 1 一 。 ) a + d u , . ( 4 . 2 . 3 ) ( 4 . 2 . 4 ) 咔一l+r 其中。= 由( 4 .2 .3 ) 得: u t . + 2 一 u t .+ t = r a 0 + 0 u t . + + ( i 一 。 ) 0 + 0 - u . ,+ , i ( 4 . 2 . 5 ) 第四章区域分裂方法n 及其稳定性分析 ( 4 .2 .3 ) + ( 4 .2 .5 ) 得 : 2 u k .+ 2 一 u k . = 。 a 十 _ 叽 。 1r a 0 + 0 - u ,z + (1 一 。 )a + a - u k+ 厂 号 ( 4 . 2 . 6 ) 同理可得: uk+1.+2 - uk+ip2一 ， 、 、 、 1+ 。 一 a) 、 、 7a 0 +0 -a +4 + (1- a )0 +0 -uk.4z k ( 4 . 2 . 7 ) 1 ) 两 端， 并 对j = 1 , . 一 l , k + 2 , - - - j 一 1 求和得: l(u j.+ 1)2 一 (u jn)2) 一 zr j-1 、 .+-2 r a 20 + 一、 - 11, j m t .k + 1= 1 ( 4 . 2 . 8 ) 用 2 u k 2 与 2 u k+: 传 分 别 乘 (4 .2 .6 ) 、( 4 .2 .7 ) 两端，再与( 4 .2 . 8 ) 求和得: 习 (u .+2)2 - (u;)2 一 (u;.+2 - u y + (u - u l (u,.+2- u,!yd + d t -1 , i j 幼 滋刊 +兄 (u + 1) ， 一 (u ; - ) 2 ) j m k .k + lj = 1 一 ha 喻 叭、 1k. a a + q ukm +zi+ ( 1 一 。 ) 久a 哄， . ， _ u k + l 一 十 rj-1 、 .,-1人 八 .te u 20 +0 _uj 2 . i a 0 +0 -u k+lp 2 + (1- a 4 + 0 -u k ) 幼 !-1芍 rili 物 .+-i + 。 一 1、 .fi= y r uj 20 +q uj 2 + (a - 1)uk 20+q% 2 + 。 一 、 伽一 恤 +l 1人 八 ut+l 1+(a-1)uk+l 2 a + 0 -u k+ ln 2 十 (1 - a )u k+ 1 20 + 0 u k 2 一 、 j-l .t +恤 .+ 1 + (l 一 呱 .+11 人 奴 .4-1 一 人 奴 .+ 1-e u, 2a +0 -ui 2 + (1- a )uk 2(0 +0 _uk+l 2 - 0 +4 _u k 2 ) + 。 一 、1 人 、 1 一 人 、 群 )j 第四章区域分裂方法1 1 及其稳定性分析 沙 刁_ , l_1_1_1 _ , l_ . 1 = 2 r e可 2 0 + 0 u j 2 + (a - 1x 0 + 4 u k 户- a + a - u kz x u k+ .%- u k 2 ) 一 2 r 卜 觉 ( + 。 ，弓 )2 十 (。 一 1)(o 2十 _、 咭 ) . + 、 弓 一 2 ; j-12 r e (0+u, 号 )2 十 2 r(。 一 1) 十 、 弓 十 2 一 *弓 ( 4 .2 . 9 ) 记 m =又 ( u j . ) 2 +又e k u j一 u j j j m k ,k + l j = k , k + 1 介 1 ( u i . + 1 ) 2 + ( u j . ) 2 2 j = k ,k + l 将( 4 .2 .9 ) 式进一步整理，可有下式成立: m .+ ， - m 一u(0 + u j。 2 )2 j-ie间 j = k , k + 1 二+ 2. , i一“ i 2。 凡 气 -不厂一夕 十 2 r + 2 r(1 一 。 )a +u k弓 0 2十 u k. 2 一 。 记 + u 厂 号 一 憋 ， 将 (4 .2 .6 ) 及 “ .2 .7 ) 代 入 上 式 得 : m . + - m - r 2 a 0 _ w k + (1 一 。 ) a - w k + f 一 r 2 - a _ w k + + ( 1 一 a ) a w k l + 2 r ew j 2 + 2 r ( 1 - a ) w k 0 + a - w k = 0 ( 4 . 2 . 1 0 ) 记j 3 二 2 又 w , 2 + 2 (1 一 。 ) 、 十 一 、一 r a 一 、+ ( 1 一 。 ) 一 气1 z - r a 一 气 + ( 1 一 。 ) 一 、 2 则 ( 4 . 2 . 1 0 )可整理为: m- m + 从 = 0 可知:如果人非负定， 则有m + , m 。 下 面 考虑j 3 非负 定 的 条 件. 1 7 第四章区域分裂方法n 及其稳定性分析 化简: j , = 2e w i t + 2 - r ( a 2 + ( 1 一 a ) , ) ( 、 一 :， + w 2 ) + 2 ( 2 。 一 i ) . i i m k - i,k ,k + l + 2 ( 1 不下 、 - a ) + r ( 2 a - 1 ) z l w k ( w k - l + w - ) + 4 r a ( 1 一 a ) w k - iw 一 2 !-12 e ， 4 + 6 r + 2 r 一 r , ， ， . ， 、 . 2 wr十t w一 十w一 ， 十分， - 代tw_ 2 ( l +r ) 一 . . - ( 1 +r ) 3 r + r 2. 、 .十二 - ， 代 7x . l x . 十w, . ) 十 ( 1 十 r ) 一 ” r 2 ( r + 2 ) ( 1 + r ) 2 ww 仓 砚汤 翻 由: 4 +6 r +2 r 2 一r 3 2 3 r +r 2 2 r 2 ( r + 2 ) 2 3 r +r 2 2 3 r +r 2 2 3 r + r 2 2 4 +6 r +2 r 2 一r 3 巨 p : 4 + 6 r + 2 r 2 一 ; a 3 r + r 2 r 2 ( r + 2 ) 3 r +r 2 4 3 r +r 2 r 2 ( r + 2 ) 3 r + r 2 4 + 6 r + 2 r 2 一 r 3 易 得: r 1 .4 6 4 1 时，几非负定. 即:当。 r 1 .4 6 4 1 时，m + l m 下 面 考 虑 m h 钊 . a ll， 的 等 价 性 : j - 1， a + i 二、 21.。 月 + 1 . ，a 2 一弓， ， ，_一_，,u . tu .i-. -k 二， ， 月_、j 月 、.、三，.、， 尸 t肠月 尸 .， “ 一 ，弃,u i t 一 一 4 一 一 t 一 一 下 一 一 ，吕声十. 将( 4 . 2 . 3 ) 、( 4 .2 .4 ) 代入上式， 进一步有: 第四章区域分裂方法ii 及其稳定性分析 五 1 = e (u j ) 2 + j = 1j m k ,k + l 2 u k + a r 0 + a - u k + ( 1 一 。 ) r a + 0 - u , , 4 + 2 u k+ 1 + a r a + 0 - u k+ l + (i - a )r 0 + a - u k )2 一 *j-1 (uj)2 + 1+ 4 (a + (- a) w klijsk-i, 4+i,k+z + 去 (2 - 3a r 十 r)2 + (3 a r - 2 r)l)(u k)2 + 丢 。(，。 一 ， ， + ， 一 3a r + r)2)(u 。一 ， + 。 + 普 (1一 )2 + a 2 k) (uk+2)2 + 2 a r ( 2 一 3 a r + r ) + 2 ( 1 一 。 ) r ( 3 a r 一 2 r ) ( u k - l u k + u k + lu k + 2 ) + 2 a r ( 3 a ; 一 2 r ) + 2 ( 1 一 。 ) r ( 2 一 3 a r + r ) ( u k - i u k + 1 + u k u k + 2 ) + 4 a r 2 ( 1 一 a ) u k - 1 u k + 2 +