（計算數(shù)學(xué)專業(yè)論文）拋物型偏微分方程的幾類新的并行算法及其收斂性分析.pdf

原創(chuàng)性聲明 本人鄭重聲明：所呈交的學(xué)位論文，是本人在導(dǎo)師的指導(dǎo)下，獨立進 行研究所取得的成果。除文中已經(jīng)注明引用的內(nèi)容外，本論文不包含任何 其他個人或集體已經(jīng)發(fā)表或撰寫過的科研成果。對本文的研究作出重要貢 獻的個人和集體，均已在文中以明確方式標明。本聲明的法律責任由本人 承擔。 論文作者簽名：尷 日 期：型壘：! 。 關(guān)于學(xué)位論文使用授權(quán)的聲明 本人完全了解山東大學(xué)有關(guān)保留、使用學(xué)位論文的規(guī)定，同意學(xué)校保 留或向國家有關(guān)部門或機構(gòu)送交論文的復(fù)印件和電子版，允許論文被查閱 和借閱：本人授權(quán)山東大學(xué)可以將本學(xué)位論文的全部或部分內(nèi)容編入有關(guān) 數(shù)據(jù)庫進行檢索，可以采用影印、縮印或其他復(fù)制手段保存論文和匯編本 學(xué)位論文。 ( 保密論文在解密后應(yīng)遵守此規(guī)定) 論文作者簽名：譚導(dǎo)師簽名：弛期： 山東大學(xué)碩士學(xué)位論文 拋物型偏微分方程的幾類新的 并行算法及其收斂性分析 楊建華 ( 山東大學(xué)數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院，濟南2 5 0 1 0 0 ) 摘要 當今實踐中提出的問題，計算規(guī)模越來越大，精度要求越來越高，而單機計算 的速度已接近極限，因此不可避免地促進了并行計算和區(qū)域分解算法的發(fā)展 s c h w a r z 算法可以把復(fù)雜區(qū)域分解為若干相互覆蓋的子區(qū)域，在子區(qū)域上可以 用快速算法求解。所謂加性s c h w a r z 算法的發(fā)展，又可克服交替方法的串行性，更 利于并行處理本文我們給出半線性對流一擴散方程的一種加性s c h w a r z 算法， 這種算法是基于區(qū)域分解的由誤差估計，我們知收斂率與每個時間步長上的迭 代次數(shù)無關(guān) 加性s c h w a r z 方法是解橢圓問題及其它靜態(tài)問題的一種有效的迭代方法，在 這篇文章中我們將用此方法解決下面的拋物型對流，擴散問題： 象一耋嘉掣磐圳川) 瞇q j “= 0( z t ) a q j “( z ，0 ) = “o ( z ) z q 首先，我們從純代數(shù)的角度給出我們的第一類并行算法由于此算法是基于區(qū) 域分解和子區(qū)域校正的，所以我們需要對區(qū)域q 進行剖分，在每個小空間w ( n 。) 上定義相關(guān)的投影算子： 砰：伊_ w 許進超 5 給出了一種子域校正形式的 并行算法，可簡單表述為：u “e ”= 札d 4 + 耋。龜我們將利用許進超的并行方法 考慮我們的對流一擴散問題，從而構(gòu)造我們的第一類并行算法 其次，在前面剖分的基礎(chǔ)上，引進粗空間v h ，并且定義投影算子珊：v “_ v h ，i，、l 山東大學(xué)碩士學(xué)位論文 在每個小區(qū)域上解邊值問題，得霞：( ? = 1 2 。，) 再解得粗空間v h 上的有限 元解舀o 則我們可得一平均值面= 了玎1 a 。以此為基礎(chǔ)我們可以構(gòu)造第二類并行 1 2 u 算法 我們還需要給出一些條件： 條件( a ) 對任意的z 而存在一個開集合職和i 1 ，2 ，) 使得x d 。 且d 。nn q ： 條件( b ) 對任意的z 豆至多存在個包含。的子區(qū)域 在文章的第三章和第四章詳細介紹了兩種算法的構(gòu)造，并分別證明了解的收斂性 針對兩算法得到了不同的收斂性定理，即： 定理3 1 設(shè)問題p j 的解“充分光滑，w “為并行加性s c h w a r z 算法的 解當a t = d f h 2 ) ，h = o ( h ) 時，有 “n w “c ( + 1 + t + ( 會；+ 魯) 號) c - ， 其中c 為依賴于u 但與迭代次數(shù)空間網(wǎng)格剖分參數(shù)h 和h 與時問步長t 無關(guān)的常數(shù) 定理4 1 設(shè)問題r ，j 的解u 充分光滑，w “為平均化并行加性s c h w a r z 算 法的解，則有 l | u “一t ，“l(fā) 一莖c ( n + 1 + t 十( ，一高) ”) c z ， 其中c 為依賴于u 但與迭代次數(shù)m ，空間網(wǎng)格剖分參數(shù) h 以及時間步長t 無關(guān)的常數(shù) 關(guān)鍵字：區(qū)域分解；拋物問題；子域校正；收斂率；誤差估計 一2 一 山東大學(xué)碩士學(xué)位論文 s o m en e w p a r a l l e la l g o r i t h m sf o rp a r a b o l i c e q u a t i o n sa n dc o n v e r g e n c ea n a l y s i s a b s t r a c t s c t l w a r zm e t h o dc a nd e c o m p o s i z et h ew h o l ep r o b l e mi n t oai n n ：n 1 ) e ro fs m a l l p r o b l e m s t h e ns o l v et h es m a l lp r o b l e m si n p a r a l l e lt h r o u g h o u td f i sp a p e rw e w m g i x + ea na d d i t i v es c h w a r za l g o r i t h mf o rs o m es e m i l i n e a rp a r a b o l i cc o n v e c t i o n d i f f u s i t i o np r o b l e m st h i sa l g o r i t h mi sb a s e do nd o m a i nd e c o m p o s i t i o n ，s ot h e c o n v e r g e n c er a t ew i l lh a v er e l a t i o nw i t ht h ed e c o m p o s i t i o np a r a m e t e rw ec o s i d e r t h ed e p e n d e n c eo fc o n v e r g e n c er a t eo np a r a m e t e r so ft i m e - s t e pa n ds p a c e i n e s h s a n d g i x e t h ee r r o re s t i m a t e s f r o mt h er e s l ：l tw ec a nf i n dt h a tt h ec o n v e r g e n c er a t e i s i n d e p e n d e n to ft h ei t e r a t i o nn u m b e ra te a c ht i m el m e l a d d i t i v es c h w a r zm e t h o d b a s e do nd o m a i nd e c o m p o s i t i o n ，i sa p o w e r f u li t e i a t i o nm e t h o df o rs o l v i n ge l l i p t i ce q u a t i o n sa n do t h e rs t a t i o n a r ) p r o b l e m si nt h i s p a p e rv c ew i l lu s et h i sm e t h o dt os o h et h ef o l l o w i n gp a r a b o l i cc o i l ；e c t i o n d i f f u s i o n p r o b l e m s ( x ，t )( 3 7 ，t ) q j ( r t ) 0 9 j z f 2 f i r s t ，f r o mt h ev i e w p o i n to fa l g e b r i cw eg i x ea na b s t r a c t t h e o r 3 a b o u to u r f i r s tp a r a l l e la l g o r i t h mw h i c hi sb a s e do i ld o m a i n d e c o m p o s i t i o na n ds u b s p a c ec o r r e c t i o nf o rd o i n gt h i sw en e e dt oi n t r o d u c eo u rb a s i cd e c o m p o s i t i o no fqa n d 一3 一 枷瑚 一 淼m 弓虧鼬 哪 酊蛐 學(xué) ， 墊 。：豆 “ 參州。啦 一 | | 已 絲乩 以 山東大學(xué)碩士學(xué)位論文 t i j ec o r r e s p o n d i n gp r o j e c t i o n s 掣。：v 一v ? s i n gt i l ep a r a l l e lt h e o r e ma n ds u b s p a c ec o r r e c t i o nm e t h o dg i v e nb yjx u ( ) w e c a ng e ta na l g o r i t h md e s c r i b e da s “，”“。= w “+ 2 0 葺 s e c o n d 冊i n n - o d u t x 、t h ec o a r s es p a c ev a n dd e f i n et h ep r o j e c t i o n 璐：v _ w ( ) nc v ( 、r j 。s u b s p a c e 州g e t 矗。( ? = 12 ，。，) b y s o l v i n gt h ea i l t i2 a s ( t e s e r i b e di nt h i sp a p e r a l s ow p ( ：a 1 1g e l | t h es o l u t i o no ft h ec o a r s ef i n i t e e l e m e n t s d a c e w ew r i r et h i ss o l u t i o na s 0 t h e nw em a k et h ea v e r a g e 面= 擊e 識f r o m t h i sw a y w ec a r lm a k eu po l l rs e c o n da l g o r i t h m ea l s os u p p o s e ： c o n d i t i o n ( 1f o ra 1 1 。豆t h e r ee x i s t s a i l o p e nd o m a i nd ta n di 1 2 a t ) s u c ht h a t 一d ? a n dd ，nq 岳q c o n d i t i o nf b l f ma n ? 7 。 豆t h e r ea r ea tm o s l - a 0s u b d o m a i nt h a tzc a l l b e l o n gt o u s i n gt h ea b s t r a c tp a r a l h 、1a l g o r i l h mt os o l v e ( 】u ip a r a b o l i cc o n e c t i o n d i f f u s i o n p r o b l e m w e ( 。a i l g e l t h ef o l l o w i n g c o r r e s p o n d i n gt ot h e s e 6 1 lr o a l g o r i t h m s w eg e t l l o d i f f e r e n tc o n v e r g e n c er e s u i t sa sf o l l o u i i l g ： t h e o r e m3 1 s u p p o s et h a tt h es o l u t i o no fr 3 1 ) i ss “f f i c i e n t l ys m o o t h a n dt h a t t 1 一“b et t z es o t u t i o r ? o f 地ep a r a l l e ls u b s p a c ec o r r e c t i o na l g o r i t h m w h e na ta n dh a r es 聽c i e n t l ys m a l l 玎a t = o ( s 2 ) h = 。( 日) ，叫e h a v e 怯叫怪c h k + i + a t + ( 豢+ 芻) 等) ， e 7 cd e n o t e s 口q e n e r i cc o n s t a n ti n d e p e n d e n to l a t ha n dh b u td e p e n d e n to n t h e o r e m3 1 s u p p o s et h a tt h e , s o l u t i o n0 f ( 31 ) i ss u f f i c i e n t l ys m o o t ha n d t h a t i i b et h es o l u t i o no ft h ea v e r a g i n gp a r a l l e la l g o r i t h m j w eh a v e | l “n 一- 一。川。墨c ( n 一l 一土t + ( - 一志) ”) ，c 。， 一4 一 山東大學(xué)碩士學(xué)位論文 w h c t ( ( 、d e n o t e x 。g e n e r i cc o n s t a n tm d e p e n d e n to fa t a n d hb u td e p e n d e n to n 。u k e yw o r d s ：d o m a i nd e c o m p o s i t i o n ：p a r a b o l i cp r o b l e m s ；s u b s p a c ec o r r e c t i o n c o l l v e r g e l l e er a t e ：e r r o re s t i m a t e s 一5 一 山東大學(xué)碩士學(xué)位論文 第一章引言 數(shù)學(xué)物理及工程問題，如油、氣藏的勘探與開發(fā)、大型結(jié)構(gòu)工程航天器的設(shè) 計、天氣預(yù)報、反應(yīng)堆計算等，無不歸結(jié)于求解大型偏微分方程計算區(qū)域往往是 高維的、大范圍的，其形態(tài)可能很不規(guī)則，給計算帶來很大的困難在實踐中，對 這些問題的計算精度要求越來越高，而單機計算的速度已接近極限，囤此不可避 免地促進了并行計算與區(qū)域分解算法的發(fā)展 簡而言之，區(qū)域分解算法是把計算區(qū)域分解為若干子域，子域的形狀盡可能 的規(guī)剛，于是原問題的求解轉(zhuǎn)化為在子域上求解，區(qū)域分解算法具有其它方法無 以比擬的優(yōu)越性： l 它把大問題轉(zhuǎn)化為若干小問題，縮小計算規(guī)模 2 算法是高度并行的， 3 子區(qū)域形狀如果規(guī)則，其上或者允許使用熟知的快速算法，或者已經(jīng)有解 這類規(guī)則問題的高效率軟件備用 4 允許使用局部擬一致網(wǎng)格，無需用整體擬一致網(wǎng)格甚至各子域可以用不 同離散方法進行計算 5 允許不同子域選用不同的數(shù)學(xué)模型，以便整體模型更適合于工程物理實際 情況 重疊型區(qū)域分解算法以s c h w a r z 交替法為理論依據(jù)1 8 7 0 年德國數(shù)學(xué)家 h a s c h w a r z ( f 2 m 首次用交替方法論證了兩個相互重疊區(qū)域和集上l a p l a c e 方 程d i r i c h t e t 問題解的存在性稍后n c u m a n n 注意到這思想工作可以用于求解兩 個相互重疊區(qū)域的d i r i c h l e t 問題1 8 9 0 年p i c a r d 進一步發(fā)展了s c h w a r z 的思 想，用之于解非線性橢圓型偏微分方程，并把算法定名為s c h w a r z 交替法本世 紀三十年代蘇聯(lián)數(shù)學(xué)家基于變分原理闡述s c h w a r z 算法，并推廣到彈性力學(xué)問題 上，其中尤以s o b o l | e w ，m i k h l i n 的貢獻最為卓越，有關(guān)討論可見m i k h l i n 的專著 | 9 但真正認識到s c h w a r z 算法在數(shù)值分析的潛力，是6 0 年代以后的事那時解 矩形區(qū)域上的偏微分方程出現(xiàn)了一批新算法，如快速付氏變換，交營方向法及基 于張量運算的顯式解，這些算法對于非矩形域無用武之地，然而，s e h w a r z 算法可 以把復(fù)雜區(qū)域分解為若干相互覆蓋的子區(qū)域，在子區(qū)域上可以用快速算法求解， 一7 一 山東大學(xué)碩士學(xué)位論文 這就增大了人們研究的興趣此期間，v e r n e r m i l l e r 和m i t c h e l l 等做了許多工 作，m i l l e r ( f 1 0 1 ) 還給出了收斂性估計 s c h w a r z 算法令人注目的發(fā)展是近幾年才開始的，其中并行計算的發(fā)展大大 刺激了研究者的興趣我國康立山教授首先認識到s c h w a r z 算法在異步并行計算 中的應(yīng)用，法國g l o w i n s k i 等應(yīng)用s c h w a r z 算法加速共軛梯度法，并在流體力學(xué)計 算上取得成功然而對s c h w a r z 算法作出全新解釋當歸功于pl l i o n s ( 1 4 1 5 ) 他在首屆國際區(qū)域分解算法會議的論文中，巧妙地把s c h w a r z 方法與投影方法聯(lián) 系起來從而使那些看來復(fù)雜的收斂性證明，簡化為對投影算子的估計對于多個 區(qū)域重疊的情形，甚至非線性問題的s c l l w a r z 方法皆在統(tǒng)一框架下得到處理在 第二屆國際區(qū)域分解算法會議上，l i o n s 又提出s c h w a r z 算法的隨機解釋( 1 5 ) 把位勢理論，布朗運動和s c h w a r z 交替方法聯(lián)系起來，這種多學(xué)科間滲透引起人 們極大的興趣 總之，以s e h w a r z 算法為基礎(chǔ)的重疊型區(qū)域分解算法，目前正由于p ，l l i o n s 的卓越貢獻得到新的認識，成為構(gòu)造新算法的理論依據(jù)為了適合并行計算的需 要，所謂加性s ( 、h w a r z 算法得到發(fā)展，w i d l u n d ，呂濤，石濟民，林振寶等皆獨立 提出不同算法，這些算法可克服交替方法的串行性，更利于并行處理 加性s c h w a r z 方法是解橢圓問題及其它靜態(tài)問題的一種有效的迭代方法，在 ( 【3 【4 1 ) x cc a i 構(gòu)造了幾種解拋物型問題的加性s c h w a r z 算法，并且證明了算法 是收斂的然而，作者沒有詳細討論收斂率對各參數(shù)的關(guān)系在( 【6 【7 ) 作者給出 了一種解拋物問題的不重疊區(qū)域分解方法，由于在交點上利用顯格式，所以需要 穩(wěn)定性條件a ts ；h 2 本文第二章是預(yù)備知識，簡單介紹了橢圓型方程的有限元理論以及并行子區(qū) 域校正方法；第三章針對要求解的問題模型，對求解域進行剖分，給出了拋物型偏 微分方程的一類新的并行子區(qū)域校正算法；并通過對誤差的分析，得到了很好的 收斂性結(jié)論；第四章對要求解的問題模型，給出了拋物型偏微分方程的另一類基 于平均計算的并行算法第五章是結(jié)語 符號說明：本文中，l 2 ( n ) h 7 ( f i ) 定義為普通的索伯列夫空間，”l l ，”| | r 分別為此兩空間上的范數(shù)c c 無論有否下標皆指正常數(shù)，在不同的地方它們可 能會有不同的值，但這些值都與參數(shù) ，h ，t 無關(guān) 一8 一 山東大學(xué)碩士學(xué)位論文 第二章預(yù)備知識 本章中我們給出二階橢圓型偏微分方程邊值問題有限元方程的加性s c h w a r z 算法及其相關(guān)的數(shù)學(xué)理論 2 1 橢圓型偏微分方程的有限元方法 我們考慮下面的問題：求u ( z ，t ) 使得 嬲卜m ， f 2 1 1 q 為砰中的有界多邊形域，其邊界為a n 。設(shè)對所有的i j 皆有a , i j ：a j i 且存 在常數(shù)。使得 ( 6 ，2 ) 7 r 2 ( 22 ) 則問題2 1 的變分形式為：求“( t ) 砩( q ) t d 使得 其中 。( 讓，u ) = ( f ，口) ， f 瑤( q )( 23 ) j 。( ， ) = 矗i , j = l 差鴦出( 2 - 4 ) 。 【z 4 j l ( ，u ) = 矗f v d x 我們假設(shè)雙線性形式滿足： ( 1 ) 有界性： i o ( “，u ) i s | | u f f 8 ( n ) i j 。lh 3 ( n ) v u ，口硪( q ) ， 一9 一 v 7 一 6 已 0 。吲 山東大學(xué)碩士學(xué)位論文 ( 2 ) 強制性 o ( u ，口) 1 i i v u i l l 。( n 1v u 丑j ( q ) 下面，我們將使用有限元方法離散橢圓問題2 3 ，從而得到問題的離散格式， 然后利用區(qū)域分解的技巧給出一個基于子區(qū)域校正的算法。我們利用協(xié)調(diào)有限元 方法來解方程( 2 3 ) 。為了簡便其見，我們利用r 2 上的分片線性三角形元我們先 對區(qū)域q 進行二級剖分，然后給出相應(yīng)的有限元空間，最后推導(dǎo)問題的g a l e r k i n 方程 首先，對區(qū)域q r 2 作初始正規(guī)三角剖分，q ，( i = 1 ，2 ，、) 是初始大單 元，相互不重疊，日是相應(yīng)于初剖分的網(wǎng)參數(shù)；其次，對每個哦精細加密得出 網(wǎng)參數(shù)為h 的q 的擬一致剖分渺，其單元為礙( j = l ，) 。然后定義b 級剖分 和一級剖分上的分片線性有限元函數(shù)空間 v ”= u 日i 在q 連續(xù)，t ，8 h 在q ，上線性，且在a q 上 日= o ) ， 伊= v h i 在n 連續(xù)， “l(fā) 一在一上線性，且在a q 上“= o ) ： 顯然v hcv 6 且給出定義 a “= x l h 一級剖分的所有內(nèi)點) ， a h = x i h 一級剖分的所有內(nèi)點) 我們得到方程( 2 3 ) 的一g a l e r k i n 逼近：求u “沙使得 a ( u “，u “) = ( ， “) v 礦伊( 2 5 ) u “的存在唯一性在f 1 9 1 中已進行了充分的論證利用節(jié)點基函數(shù)，方程( 2 5 ) 可 以轉(zhuǎn)化為解線性方程組，此方程組的系數(shù)矩陣通常情況下不僅是龐大稀疏的，而 且是具有病態(tài)條件數(shù)的，所以我們需要作一下預(yù)處理設(shè)方程( 25 ) 的線性形式為 a u = g ，( 2 6 ) 其中a 為剛度矩陣由條件( - 4 ) 我們可得存在n 的一個開覆蓋 q ) 墨。使得 d n q q ：由單位分解的理論( 見 1 ) ，可知存在光滑函數(shù)協(xié)( i = l ，2 ，) 滿 足吼= 1 ，0 協(xié)sl ，s u p p ( 慨) co 。，且有i i p , l l w sc h 令p ? = i h ￥9 i ， l = 1 這兒厶：硪( q ) _ 沙為插值算子，則? = 1 。 一1 0 一 山東大學(xué)碩士學(xué)位論文 2 2 子區(qū)域校正法 為了使s c h w a r z 交替法的計算并行化，出現(xiàn)了加性s c h w a r z 方法，d r y j a 與 w i d l u n d 皆提出不同的算法本文中，我們將以徐進超【5 中提出的子區(qū)域校正法 為基礎(chǔ)來構(gòu)造并行算法下面從純代數(shù)的角度簡單介紹一下子區(qū)域校正法 設(shè)向量空間v 的一個分解所包含的子空間u v ( 1si 莖) 滿足 ， v = ( 27 ) z = 1 n 也就是說，對任意的 v 都存在坼u ( 1 冬2 ) 使得u = 地通常， 的這種分解是不唯一的對任意i 我們定義q 只：v _ ”和4 ：v - 通過： ( q ，“t ：i ) = ( “v i ) ，( 只u t 1 。) = ( u c ，) v u v t k 1 瓏( 2 8 ) 與 ( a ，u ，t ) = ( _ 4 “，。：) v u ，u i 1 峨( 2 9 ) q ，和只皆為正交投影，：為j 4 在上的限制且為s p d 由它們的定義，可以 得到 ，只= q ，( 21o ) 此等式非常重要，在本文中將多次用到利用上面的定義我們可得如果u 為( 2 6 ) 的解，則 4 ，弛= 9 i( 2 1 1 ) 其中“。= 只“，m = q ：9 這個方程可看作方程( 2 6 ) 在k 上的限制子空間上的 方程( 2u ) 可近似求解對任意? 我們定義 ，的一個近似逆算子r i ：一u 、故 可得方程1 5 ) 近似解玩= r ：， 從子區(qū)域校正的角度我們可得下面的并行算法，這個算法類似于j a c o b i 迭代 法，其原理是對每個小子域進行殘量修正，各個子域計算時可以并行 令“。為方程( 2 1 0 ) 的近似解，此解的精確性可由二r “。= ，一4 u “8 計算， 如果r “= 0 或者充分小，則可得所求解否則，我們考慮殘量方程： e = r o l d 山東大學(xué)碩士學(xué)位論文 顯然“= “州“+ e 為( 26 ) 的解我們不直接解上面的殘量方程，而是考慮殘量方 程在每個小空間k 上的限制方程： 4 ：e ：= q ：r 0 2 4 由于我們只是考慮在每個小子域上的校正，所以只需要近似求解上面的限制方程 所以可得一次更新 可寫成 龜= r ：q 。r 刪 1 = z i “一b ( 一a u “4 ) 其中 ， b = e r 。q 。 ( 2 1 2 ) z = 0 這樣可得一并行的迭代算法注意到，如果任給咒：v - 為s p d 則( 22 1 ) 中的b 為s p d 1 2 一 q 。瑚 + “ = u眥 u 山東大學(xué)碩士學(xué)位論文 第三章拋物型偏微分方程的一類新的 并行子區(qū)域校正算法 我們考慮下面的問題：求u ( x ，t ) 使得 q 為r 2 中的有界多邊形域，其邊界為0 9 - j ：( 0 ，t 為時間域設(shè)對所有的i ，j 皆有( 2 i j = a j , 且存在常數(shù)7 使得 2 。巧磊62 7 l ej 2v = ( f 1 ，f 2 ) t 兄2 ( 32 ) 叼= l 則前面問題( 3 1 ) 的變分形式為；求“( f ) 硪( q ) ，t j 使得 拋物型問題變分形式( 3 3 ) 的解的存在和唯一性是顯而易見的( 1 9 ) 3 1 拋物型偏微分方程初邊值的有限元方法 ( 3 3 ) 我們使用有限元方法求解拋物型問題變分形式( 3 3 j 的解。在時司方向上我們 利用向后的歐拉格式令t 為時間步長，p = n a t ，1 i “= “( 護) ，有 與等= 象+ o ( s 艫g ”， ( 3 a ) _ 百一2 瓦+ “，t “4 7 在時間方向上離散，則問題( 3 3 ) 的第一個方程可由下面的時間離散格式近似 ( 1 1 n f 9 2 n - i ，刨) + ( 礦， ) = ( ，( 擴一1 ) ，口) + ( 礦，計) v 可硪( q ) ，( 3 5 ) 一1 3 一 墮眠 m 。 叼卜 旦岫擴 謄一 1 0 h t砷吐礎(chǔ) 曲“口 = 、卜 ) t t d 沁 0 | i + j ，0 煎挑“ ，(、【 山東大學(xué)碩士學(xué)位論文 其中 礦= 與筍籌+ ，( 叫u “) - 。( 霧刪 因此我們可以得到問題( 3 3 ) 的時間離散格式 ( 與，卅n ( , nv ) 刈r 1 ) ，”) v ”磁( q ) ， 令 a ( u ，u ) = ( u ，u ) + a t a ( u ，u ) v v 礎(chǔ)( q ) ， 1 1 “| | ：( a ( u u ) ) 2 = ( i i u 惦+ t i | u 悒) 1 膽， f 。= ( n ( u “) ) 則時間離散方程可改寫為 一( u “訓(xùn)) = ( “一1 + t f ( u “一1 ) ， ) ，v v 嘲( q ) ， ( 3 6 ) ( 3 7 ) 下面，我們將進一步在空間方向進行離散，從而得到問題的全離散格式。類似于橢 圓問題有限元方法構(gòu)造二級有限元剖分的有限元函數(shù)空間v “硪( q ) 。我們可 得方程( 3 3 ) 的g a l e r k i n 逼近：求u 6 伊使得 a ( u “v ) = ( u ”。1 + a t f ( u ”1 ) ，y ) ，v v “，( 3 8 ) 驢的存在唯性在 1 9 中已進行了充分的論證利用節(jié)點基函數(shù)，方程( 3 8 ) 可 以轉(zhuǎn)化解線性方程組，此方程組的系數(shù)矩陣通常情況下不僅是龐大稀疏的，而且 是具有病態(tài)條件數(shù)的，所以我們需要作一下預(yù)處理在下節(jié)中，我們利用區(qū)域分解 的技巧給出一個基于子區(qū)域校正的算法。 3 2 算法的構(gòu)造 哦的定義同第一章第二節(jié)，對每個q 。構(gòu)造真包含皿的子域f 2 并設(shè)p 的 頂點也是渺的頂點且設(shè)存在q o 使得 1 4 d i s t ( o f 2 。nq ，a q 。nf 2 ) 2o 日， i = 1 ，2 ，- 一， 山東大學(xué)碩士學(xué)位論文 令伊c 明是上的分片線性元空間又設(shè)嵫= 沙n 明( 07 ( i = 1 ，2 ，) 剛有限元空間伊可以表為個子空間的和： y “= 叫+ 罐+ + 垛 定義能量投影p ? ：v “_ 磚、使v 驢儼有 a ( q ?？趆 “) = 4 ( 掣“妒“) v 妒“e 講i = 1 ，2 ， 令p “= 矸一- 劈+ + 礤則前面的離散問題( 3 8 ) 可轉(zhuǎn)化為下面的等價形式 p 擴= 9 ：一1 這兒g ：一。的計算不依賴于u “。 注意到p 關(guān)于范數(shù)4 是對稱的，因此可以利用共軛梯度法求解本文我們 研究方程( 38 ) 的加性s c l w a r z 迭代求解方法。假設(shè)重疊型區(qū)域分解 q ：) 叁。滿 足條件( a ) 和( b ) 。 給出下面的加性s c h w a r z 算法： 并行子區(qū)域校正算法：取m 為每一時間步上的迭代次數(shù)。對n 1 ，分三步 求w n v “： 第一步：取初始函數(shù)霹= i i 。： 第二步：對j = 1 2 7 w ，在予區(qū)域上作同步并行迭代：對i = 1 2， 求砭，眇，使得 4 ( ，i ) = ( 妒? ( h n 一1 - i - 土t ，( i 可一1 ”1 一) 4 ( 可霹一i ：妒? 1 7 ) vv w ( 3 9 ) 取 _ 孵= 碌。+ 醒 ( 3 1 0 ) 七= l 第三步：取 h 一= 配f 3 1 1 ) 返回第一步開始下一時間步迭代。 在下面一節(jié)里，我們將證明并行加性s c h w a r z 算法具有很快的收斂性。 1 5 山東大學(xué)碩士學(xué)位論文 3 3 收斂性分析和誤差估計 本節(jié)我們給出并行加性s c h w a r z 算法的收斂性分析和誤差估計下面的收斂 性定理是本文的主要結(jié)果 定理3 1 設(shè)問題r 3 的解u 充分光滑，w “為并行加性c o c h w a r z 算法的 解，當z = o ( h 2 ) h = o ( g ) 時，有 ”u ”一一，7 “”一g ( h k - i + a , t + ( 會：+ 寺) 警) ， c 。- 。， 其中c 為依賴于“但與迭代次數(shù)m 空間網(wǎng)格剖分參數(shù)h 和h 與時間步長t 無關(guān)的常數(shù) 根據(jù)已有的橢圓問題加性s c h w a r z 算法的收斂性分析，當?shù)螖?shù)趨于無窮 時，本文中的對拋物問題的加性s c h w a r z 算法是收斂的但已有的研究結(jié)果并未給 出迭代次數(shù)與空間網(wǎng)格剖分參數(shù)a 和日及時間步長t 的關(guān)系在定理31 中， 我們建立了迭代次數(shù)與逼近精度的關(guān)系從中可以發(fā)現(xiàn)：通常迭代很少幾步即可 達到最優(yōu)的逼近精度為了證明上面的收斂性定理，我們給出一些重要的引理 引理3 1 存在常數(shù)c o 0 使得對1s is 和0 751 j 姒，一馴幽。川一，sc 專一i i 肌vv 沙 ( 31 3 ) 證明：注意到有限元空間的逼近性，我們有 1 1 ( i 一厶) ( 妒? v ) i 盯，墨c h 2 一l i d 2 ( 妒? ) i i ! 既然妒? 和i j 是線性，于是由有限元函數(shù)的逆性質(zhì)得 l i d 2 ( 妒? r ) l i 工。sc _ | v ? 1 i 工v ll 。c h ”一1 日一1 l 一1 1 日r ，r = 0 ，1 引理31 證畢 引理3 2 存在常數(shù)c 1 0 使得 卸w h c v 掣n 州t ( 芻+ 宰) 岍川川w 川刈、圳 ( 3 1 4 ) 一1 6 山東大學(xué)碩士學(xué)位論文 證明：注意到：對任意1 j w 沙 刪i 妒? 砷w ) ：壹、：即t 2 ( ，簧型o q x j - 咖： 卜 燮 9 x i 紫) 1= ? 1 ：譬拙( ，荔型咖t 1 一掣) l # 1l i ，2 1 、 。 。 7 j = 4 ( 、i w 7 ) + 4 ( ( 一j n ) ( 妒硝 _ + a tr ，、，籌百o p ：w ，) 我們有： 1 4 ( 1 ：h 一) 一4 ( ，? 釜妒。h r 。ht t ，) l 墨ni - ( ( ，一 ) ( 妒? v ) 爿。w 7 ) t = ll = 1 + t 耋妻，1 ( 0 。0 1 ，籌砷w ) 一( a i j l7 籌，寫學(xué)) c i x 1 l ( ，一厶) ( ? ) il h ，i i p , q _ 【1 1 4 i = 1 + c 昔( i i w i ? i 爿w ll ! + i l v l l c z l i v 辟w l i l ：) 曼c ( 魯+ 等) 1 1 1 - l i i i l l r i i - 這里我們使用了引理31 引理3 2 證畢 引理3 3 設(shè)問題p 的解u 充分光滑， u “為標準有限元形式的解，則有 “一”i ，= o ( h ”1 + t ) s = 0 1 ( 3 1 5 ) 現(xiàn)在我們可以證明定理3 1 定理7 的證明：我們考慮并行子區(qū)域校正算法的解與與標準有限元方法的 解之間的誤差首先我們給出誤差方程。并行子區(qū)域校正算法的實質(zhì)是用迭代法 一1 7 斗 一j 如瓦 生眠 伽 ， 。 山東大學(xué)碩士學(xué)位論文 求解初值為? ”1 的方程 4 ( 形n ，v ) = ( t ，( wr n - - 1 ) + w ，“一1 ，17 ) v ， ( 3 1 6 ) 記e n ：帚n 一( r n 和e n ：w 一u n 我們有 a ( e “) = ( e ”一1 、) + a t ( f ( w ”一1 ) 一f ( u ”- 1 ) ) v ) ，vv 1 i ( 3 1 7 ) 或等價地 a ( e “，1 ) = a ( t i 一一w 一，1 7 ) + ( e “一1 ，1 + ) + a t ( f ( w “一1 ) 一f ( u n - - 1 ) ) 、v ) vi v i f 3 1 8 ) 從誤差方程我們可以看到，誤差項休一“的估計是關(guān)鍵，它反映了迭代誤差對 整體逼近誤差的影響。 由并行子區(qū)域校正算法的迭代方程： 霹= 弼一，+ e 露，可得 2 = _ 另一方面，我們又有 ) + 4 ( e 黿，：1 7 ) vr h ( 31 9 ) z = i 7 a ( e 露，1 ) = 妒? ( w “1 + a t f ( h n - - 1 ) ) 掣v ) 一a ( 麗：一。，妒? 曄1 ) o = it 2 i ：窆f 4 ( 霈n 妒? p 2 r ) z = j 。 令e ，n = 翳一u ”，則 4 ( 勺n ，? ) = a ( e 。，v ) + _ 4 ( 麗：”一礦 所以有 一1 8 一 _ 4 ( e ；一e “，) = 4 ( e 。一e ”，) + a ( e “一e j n 1 e ? 辟l 7 ) z = l r = a ( e 二，一e “( ，一妒? 砑) 1 ) z = i f 32 0 1 ( 3 2 1 ) f 3 2 2 1 vv 磚，妒 引 山東大學(xué)碩士學(xué)位論文 綜上所述，可得 4 ( 髟n e “，e ? 一e “) = 4 ( e ，n 一，一e “，( 一i = 0 妒? 掣) ( 哆一e “) ) 又由引理3 2 得： ；坩悒( 豢+ 雨a t ) 忙；- 1 - - e ”悒，s ， m 遞推得： 注意到 ( 3 2 3 ) ( 3 2 4 ) ( 3 2 5 ) = i l e “一1 一e “+ u “一1 一u “i i j ， 因此 i l e n - e 憶s e 。( 豢+ 第) 詈 1 i e - 1 - e + c 。l l 籌隊a t c s 粥， 故 牝刈d 。+ m 豢+ 豢) 罟 1 i e - 1 - e 憶+ 腳孰寸z ， 下面，我們估計方程( 3 2 7 ) 的右邊項在方程( 3 1 7 ) 中令u = e ”，則我們可得 i i e “l(fā) i j = ( e ”，e “) + a t ( f ( w “) 一，( u “。1 ) ) ，e “) ：f e n ，e n ) + t ( ，e n ，e “) ( 1 + c x , ) l l e “。i e “m ( 3 2 8 ) 其中，為，的介于w n 一與u n 一- 之間某點上的_ 階導(dǎo)數(shù)，e n 一1 = ，( w ”1 ) 一 f ( u ”_ 1 ) 所以 | 1 e ”i l ( 1 + e t ) | | 礦。| | ( 3 2 9 ) 一1 9 一 b i - 叫 e e 一 一 晤 舊 “ m o h 嵋 坐艫 + 一。 竺驢 ，一 ， h r 妙 衽 刮 一 廿 忙 嘧 山東大學(xué)碩士學(xué)位論文 由方程( 3 1 7 ) ，可得 ( e ”一e “一1 ，口) + x t a ( e “一e “一1 ，u ) = a t ( f7 e ”1 ，口1 一a t a ( e ”1 ，u ) ( 3 3 0 ) 令v = e ”一e 一1 莢似十萬欄陋2 9 ) 的讓明，剛得 i i e “一礦_ 1 l i 莖a t l 2 l i e ”1 + e 圳e “- 1 l l 由( 3 2 7 ) ，( 3 2 9 ) ，( 3 - 3 1 ) 可得下面的結(jié)果 艙刈。s ( 1 + c a t 川擴+ g ( 豢+ 刪a t 、m 2 a t l 2 忙一。 一t ( 篆+ 豢) 州2 又2 a b a 2 + b 2 所以 ( i i e “一1 l + e ( 豢+ 豢) “7 2t t ，1 ，2 l ；e n 一1 l i 。) s l t e - l l l 。刪e n _ 2 + c 2 ( 豢十第) ”i i e n - 1 ( 豢+ _ a t ，、m a t l l 擴： s ( 彬( 豢+ 第) v “悒 顯然，存在常數(shù)c 5 使得 ( + c 2 ( 豢+ 豢) ”) 冬，+ 。g ( 豢+ 豢) ” ( 3 3 1 ) ( 3 3 2 ) ( 3 3 3 ) 礦 膽 膽 瞪 m 劫擴 十 1 旦艫e廠， 弋壘鏟 + + 竺儼 r ，一 i g = + 因此 山東大學(xué)碩士學(xué)位論文 s ( + g ( 豢+ 第) ”) 2 ( + c t ( 豢+ 第) “1 2 0 使得 d i s t ( o q inq ，a q ，nq ) a h ，i = 1 ，2 ，一， 令伊c 明是渺上的分片線性元空間， 空間又設(shè)世= 杪n 嘲( n ：) ( i = 1 ，2 ， 個子空間的和： 哪= v 日c 哪是q 日上的分片線性元 ) 則有限元空間y “可以表為+ 1 v “= w + 坩+ + 塢 定義能量投影砷：杪_ 嘴，使v 滬伊有 a ( p ， “，妒“) = a ( v “，妒“) ，v 妒“wi = 0 1 ，一， 令p “= 珊+ p ，+ + 璐，則前面的離散問題( 3 8 ) 可轉(zhuǎn)化為下面的等價形式 p “u “= 炙一l 這兒g ：一。的計算不依賴于【，“。 注意到p “關(guān)于范數(shù)4 是對稱的，因此可以利用共軛梯度法求解本文我們 研究方程( 3 8 ) 的加性s c h w a r z 迭代求解方法假設(shè)重疊型區(qū)域分解 f 2 ：) 墨l 滿 足條件( a ) 和( b ) 給出下面的加性s c h w a r z 算法 并行平均化算法：取m 為每一時間步上的迭代次數(shù)對n 1 ，分三步求 w n v “： 第一步： 取初始函數(shù)一w o = w “， 一2 2 山東大學(xué)碩士學(xué)位論文 第二步：對= 1 ，2 m ，在子區(qū)域上作同