（計算數(shù)學(xué)專業(yè)論文）解半線性拋物問題的瀑布型多重網(wǎng)格法.pdf

碩士學(xué)位論文 摘要 瀑布型多重網(wǎng)格法是求解大型邊值問題的一種有效迭代解法。其主要的優(yōu)點是不要 求粗網(wǎng)格校正，故又稱單步多重網(wǎng)格法。g i s e l at i m m e r m a r m 用瀑布型多重網(wǎng)格法對半 線性橢圓問題進(jìn)行了求解，在粗網(wǎng)格上用牛頓法( n e 叭o n ) 將由線性有限元離散而得到的 非線性方程組線性化，在細(xì)網(wǎng)格上用瀑布型多重網(wǎng)格法解這個牛頓方程，并且提出了算法 和對算法的收斂性進(jìn)行了研究。 本文將瀑布型多重網(wǎng)格法推廣到半線性拋物問題，證明在能量范數(shù)下算法誤差的最 優(yōu)階，且有最優(yōu)或有擬最優(yōu)的計算工作量，并進(jìn)行數(shù)值試驗。 本文以半線性二階拋物型偏微分方程初邊值問題為模型問題構(gòu)造了瀑布型多重網(wǎng) 格法( c m g ) ，在最粗網(wǎng)格上用牛頓法( n e w t o n ) 將由線性有限元離散而得到的非線性方 程組線性化，在細(xì)網(wǎng)格上用瀑布型多重網(wǎng)格法解這個牛頓方程首先采用r i c h a r d s o n 迭代 法作為光滑子，我們證明了瀑布型多重網(wǎng)格法對二維半線性拋物型邊值問題在能量范數(shù) 下可獲得最優(yōu)收斂階。然后又對采用共軛梯度法( c g l 作為光滑子進(jìn)行了研究，并得到了 在此情況下，瀑布型多重網(wǎng)格法對二維半線性拋物型邊值問題在能量范數(shù)下可獲得最優(yōu) 收斂階。同時對這兩種情形，分析了計算工作量，得到了工作量的最優(yōu)性或擬最優(yōu)性， 這說明在半線性情形的計算工作量與線性情形是大致相當(dāng)?shù)?。?shù)值實驗也顯示了該算法 的有效性。 關(guān)鍵詞：拋物問題；瀑布型多重網(wǎng)格法；最優(yōu)性 解半線性拋物問題的瀑布型多重網(wǎng)格法 a b s t a c t t h ec a s c a d i cm u i t i g r i dm e t h o dh a sb e e ns h o w nt ob eo n eo ft h em o s te f f i c i e n ti t e r a t i v e t e c h n i q u e s f o rs o l v i n g l a r g e s c a l eb o u n d a r yv a l u ep r o b l e m s t h em a i na d v a n t a g eo ft h e m e t h o di sc o a r s e g r i d 一r r e c t i o nf r e e a n da sar e s u l ti tc a l lb ev i e w e da sao n e - w a ym u l t i g r i d m e t h o d g i s e l at i m m e r m a n n p r o p o s e dac a s c a d i cm u l t i g r i df o ra s e m i l i n e a re l l i p t i cp r o b l e m o nt h ec o a r e s t 鰣dt h en o n l i n e a re q u a t i o n sa r i s i n gf r o ml i n e a rf i n i t ee l e m e n td i s c r e t i z a t i o n s a r es o l v e db yn e w t o n sm e t h o d o nt h ef i n eg r i dt h en e w t o n se q u a t i o n si ss o l v e db yt h e c a s c a d i cm u l t i g r i dm e t h o d i nt h i sp a p e rw ee x t e n dt h ec a s c a d i cm u l t i g r i dm e t h o d t os e m i l i n e a r p a r a b o l i cp r o b l e m s i th a sb e e n p r o v e d t h a tt h em e t h o dh a so p t i m a lc o n v e r g e n c eo r d e ro ft h ee r r o ri ne n e r g yn o r m ， a n dh a st h eo p t i m a lo r q u a s i o p t i m a lc o m p u t a t i o nc o m p l e x i t y w ec o n s t r u c tc a s c a d i cm u l t i g r i dm e t h o df o ram o d e lp r o b l e m - - as e m i l i n e a rp a r a b o l i c p r o b l e m o n t h ec o a r e s t g r i d t h en o n l i n e a r e q u a t i o n sa r i s i n g f r o ml i n e a rf i n i t ed e m e n t d i s c r e t i z a t i o n sa r es o l v e db yn e w t o n sm e t h o d o nt h ef i n eg r i dt h en e w t o n se q u a t i o n si s s o l v e db yt h ec a s c a d i cm u l t i g r i dm e t h o d a tf i r s tw eu s er i c h a r d s o ni t e r a t i o na ss m o o t h i n g o p e r a t o r a n d p r o v e t h em e t h o dh a so p t i m a lc o n v e r g e n c eo r d e rf o rt h ee l t o ri nt h ee n e r g yn o r m t o2 - ds e m i l i n e a rp a r a b o l i cp r o b l e m t h e nw eu s ec o n j u g a t eg r a d i e n t ( c g ) a ss m o o t h e r sa n d p r o v et h i sm e t h o d h a so p t i m a lc o n v e r g e n c eo r d e ro ft h ee l t o ri nt h ee n e r g yn o r ma l s o f o r t h e s et w oc a s e s ，w e a n a l y s e t h e c o m p u t a t i o n a lc o m p l e x i t y t h e o p t i m a l i t y o r q u a s i o p t i m a l i t y o f t h e c o m p u t a t i o no f t h em e t h o di ss h o w n t h i sf a c t d i s p l a y s t h a tf o r c a s c a d i cm u l t i g r i dt h ec o m p u t a t i o n a lw o r ki ns e m i l i n e a fc a s ei sa l m o s tt h es a m ea st h a ti n l i n e a rc a s e f i n a l l yan u m e r i c a le x p e r i m e n ti sg i v e nt ot h ee f f e c t i v e n e s so ft h em e 血o d k e y w o r d s ：p a r a b o l i cp r o b l e m ；t h e c a s c a d i cm u l t i g r i dm e t h o d ；o p t i m a l i t y i i 湖南大學(xué) 學(xué)位論文原創(chuàng)性聲明 本人鄭重聲明：所呈交的論文是本人在導(dǎo)師的指導(dǎo)下獨立進(jìn)行研究所 取得的研究成果。除了文中特別加以標(biāo)注引用的內(nèi)容外，本論文不包含任 何其他個人或集體已經(jīng)發(fā)表或撰寫的成果作品。對本文的研究做出重要貢 獻(xiàn)的個人和集體，均已在文中以明確方式標(biāo)明。本人完全意識到本聲明的 法律后果由本人承擔(dān)。 作者簽名：專軍 日期：如p 年r 月，日 學(xué)位論文版權(quán)使用授權(quán)書 本學(xué)位論文作者完全了解學(xué)校有關(guān)保留、使用學(xué)位論文的規(guī)定，同意 學(xué)校保留并向國家有關(guān)部門或機(jī)構(gòu)送交論文的復(fù)印件和電子版，允許論文 被查閱和借閱。本人授權(quán)湖南大學(xué)可以將本學(xué)位論文的全部或部分內(nèi)容編 入有關(guān)數(shù)據(jù)庫進(jìn)行檢索，可以采用影印、縮印或掃描等復(fù)制手段保存和匯 編本學(xué)位論文。 本學(xué)位論文屬于 1 、保密口，在年解密后適用本授權(quán)書。 2 、不保密團(tuán)。 ( 請在以上相應(yīng)方框內(nèi)打“4 ”) 日期：帥十年r 月7 7 日 日期：腫廣月如日 芊，) 。 a 最o k 專吲 名名簽簽者師作導(dǎo) 碩士學(xué)位論文 引言 首先，我們將簡單的回顧半線性問題的多重網(wǎng)格法的歷史發(fā)展和瀑布型多重 網(wǎng)格法近幾年的主要理論成果 多重網(wǎng)格法( m u l t i g r i dm e t h o d ，簡稱m g 法1 是求解偏微分方程邊值問題的一種 有效的迭代解法，其基本思想早在2 0 世紀(jì)6 0 年代就由前蘇聯(lián)計算數(shù)學(xué)家 r e f e d o r e n k o 提出但當(dāng)時并沒有引起人們的很大注意7 0 年代中期以色列數(shù)學(xué)家 a b r a n d t 教授對它進(jìn)行全面的創(chuàng)造性的研究，提出了一些新的觀點使人們重新認(rèn) 識多重網(wǎng)格法的效率，這一方法受到了普遍的重視在這個時期我國著名的數(shù)學(xué)家 馮康也對多重網(wǎng)格法進(jìn)行了大量的研究工作尤其在8 0 年代之后，世界各國的計算 數(shù)學(xué)界都在這方面投入了大量的人力、物力，使得這個方法的理論研究取得重要的 成果，多重網(wǎng)格法的基本核心，包括基本原則、傳統(tǒng)應(yīng)用及理論都已經(jīng)建立，出現(xiàn)了一 系列的多重網(wǎng)格法的文章和專著，其中代表性的是參考文獻(xiàn)1 2 0 瀑布型多重網(wǎng)格法是多重網(wǎng)格法中的一種它是由d e n f l h a r d 2 1 - 2 2 提出的文 【2 1 1 中的數(shù)值試驗表明瀑布型多重網(wǎng)格法是非常有效的 瀑布型多重網(wǎng)格法的主要優(yōu)點在于不要求粗網(wǎng)格上校正，故又稱單步多重網(wǎng)格 法正因為如此，在細(xì)網(wǎng)格上進(jìn)行迭代時，與粗網(wǎng)格相關(guān)的誤差變成低頻，很難用傳統(tǒng) 的磨光算子減小，這樣，利用瀑布型多重網(wǎng)格法在每層上求解必須達(dá)到最細(xì)網(wǎng)格上 精度這就要在粗網(wǎng)格上進(jìn)行大量迭代，另一方面，瀑布型多重網(wǎng)格法誤差估計僅以 能量范數(shù)下保持最優(yōu) 瀑布型多重網(wǎng)格法又一個優(yōu)點是它的簡潔性每層上的迭代可以預(yù)先確定 一般只依賴于j - j ( j 表示最細(xì)網(wǎng)格層數(shù)，j 表示當(dāng)前網(wǎng)格層數(shù)) 而不依賴于空間維數(shù)， 也正是因為其不依賴空間維數(shù)，所以應(yīng)用于高維問題更有效 近年來，瀑布型多重網(wǎng)格法有了進(jìn)一步發(fā)展文獻(xiàn)f 1 7 1 9 b o m e m a n n 和 d e u f l h a r d 等人研究了用p 1 協(xié)調(diào)元離散二階橢圓的瀑布型多重網(wǎng)格法，已證明：對 三維問題，若采用標(biāo)準(zhǔn)的迭代法，飼如j a c o b i ，g a u s s s e i d e l ，r i c h a r d s o n 迭代法作為光 滑子，則該法是最優(yōu)的，但對二維問題僅是擬最優(yōu)的若采用共軛斜量法作為光滑子， 則對二維和三維問題都是最優(yōu)的石鐘慈和許學(xué)軍把上述結(jié)論推廣到更一般的協(xié) 調(diào)和非協(xié)調(diào)有限元，考察了板問題的瀑布型多重網(wǎng)格法，證明了此時若采用共軛斜 量法作為光滑子，該法是擬最優(yōu)的，而傳統(tǒng)的光滑子不能使用，還討論拋物問題( 見文 獻(xiàn)2 5 2 9 1 ) 曾金平和姜英軍將此方法應(yīng)用于求解非對稱橢圓邊值問題當(dāng)然上述算 法都是應(yīng)用于求解線性問題2 0 0 0 年，g i s e l a t i m m e r m a n n 將此方法應(yīng)用于求解半線 性橢圓邊值問題，用線性協(xié)調(diào)有限元離散得到一個非線性方程組并且在最粗網(wǎng)格 上用n e w t o n 法加以解決( 見文獻(xiàn)【3 2 】) 解半線性拋物線問題的瀑布型多重網(wǎng)格法 半線性拋物問題來源于物理學(xué)，工程技術(shù)，自動控制，生態(tài)系統(tǒng)及經(jīng)濟(jì)社會系統(tǒng) 中的大量問題，如何求解卻是計算數(shù)學(xué)的一個重要課題( 見文獻(xiàn) 3 2 3 9 1 ) 近幾十年 來，有關(guān)這一課題的研究發(fā)展十分迅速，相繼出現(xiàn)了許多新的數(shù)值解法，其中多重網(wǎng) 格法就是最為重要、最為常見的方法之一許多科學(xué)工作者都研究該法用于解橢圓 問題和拋物問題( 包括非線性的和線性的) 的求解 本文的目的是將瀑布型多重網(wǎng)格法推廣到半線性拋物問題 本文內(nèi)容組織如下：第一章，介紹我們所討論的問題，給出問題模型及其離散形 式，并給出可直接用于計算機(jī)編程的算法第二章，建立以r i c h a r d s o n 迭代為光滑子 時瀑布型多重網(wǎng)格法的收斂性理論和誤差估計，討論算法的最優(yōu)性第三章將給出 用c g 方法作光滑子時的收斂性理論和誤差估計第四章，給出數(shù)值實驗結(jié)果，以驗 證算法的有效性和理論誤差估計 2 碩士學(xué)位論文 1 1 問題與離散 第1 章問題與算法 p ，一血+ z ( x ，f ，h ) ；0于q 0 ，t 】 “b ，f ) - 0于a q 0 ，t ( 1 1 ) i “0 ，o ) e u u g ) 于q 其中q 為r 2 中有界凸多邊形為q x 0 丁 x 尺上連續(xù)函數(shù)，并且有常數(shù)吐，k 0 ，滿足 o s l b ，t ，v ) s ( 1 2 ) l ，w g ，t ，v 1s 七( 1 3 ) ( 1 1 ) 的弱形式為求“b ，f ) 日；( q ) ，o s ts r 使得 0 ，v ) + 口0 ，v ) + ( ，b ，t ，u ) ，v ) - 0v e u ：( q ) ( 1 4 ) 其中 n 0 ，v ) a 留聰v v d x 由l a x m i l g r a m 定理可得，此問題有唯一的解 現(xiàn)在我們構(gòu)造求解( 1 4 ) 的e u l e r g a l e r k i n 格式取時問步長為f ，一撐f 則e u l e r 向后格式為 r 。- “，v ) + n - “，v ) + k ，v ) ；0v v 月：g 2 )( 1 5 ) 其中有w “- “_ u n - 1 ( g n ，v ) 一( ，k ，“5 l v ) 一口“”1 ，v ) 取q 的正規(guī)三角形剖分族乜j ，其中由。產(chǎn)生0 的方法是：將l 。的每個三角 形的三邊中點連接，產(chǎn)生四個小三角形作巧的單元，記乙相應(yīng)的l a g r a n g e 線性空 間為網(wǎng)格尺寸為h j ，且有h 。- 2 h 將( 1 5 ) 作有限元離散，得( 1 4 ) 的 e u l e r g a l e r k i n 格式 已知越；。1 ，求m n 咋使得下個式成立： ：；b mw ；) ”+ 口a - i w ；，v + b ，v i 。v v e v ， ( ，s ， ”一7 采用多重網(wǎng)格法時取，k 巧的目的是求，一，的( 1 6 ) 對n = 1 , 2 3 逐步計 算? 則為u o g ) 的插值 對每個n 計算( 1 5 ) 的有限元解即用有限元解如下帶參數(shù)f 的橢圓問題：求 w 日：使 f _ 1 ( m y ) + 4 ( m v ) + b k w l v ) 矗0v v 片：( 1 7 ) 其中 ( g ( x ，w l v ) 一( ，0 ，t ，w + “l(fā) v ) 一a 0 ，v ) 3 解半線性拋物線問題的瀑布型多重網(wǎng)格法 容易算出，9 0 ，v ) 對v 的導(dǎo)數(shù)為 咖，v ) ：l i r a 血號乒趔 ：1 i m 壘：! ! ! ! 坐) 二生：! ! ! = b ，v + “) 同理也容易得到 g 。0 ，v ) 一，w g ，v ) 因此由條件( 1 2 ) ，( 1 _ 3 ) 可得 0 5 9 v g ，v ) s ( 1 8 ) k 。b ，v 1 當(dāng)七 記 4 ( w ，v ) ；z w ，v ) + n ( w ，v ) + b b ，w l v ) 則4 ( w ，v ) 在w 處的階g 微分為 4 ( w ；齜v ) 。凹坐塑掣 ：1 i l ! ：! 墮! 絲! ! l ! 業(yè)! ! 型! ! ) ! 絲坐墮叢立! 墮坐) 二叢墜叢d 型必 所以有 ：i i m ! ：! g 塑! ) ! q 堅坐蝗壘：墜墮正直型叢立 t 葉o t = r 一1 ( a v ，v ) + 口( 跏，v ) + ( g ，& ，r ) 品塢v ) 1 2 算法 4 ( w ；她v ) 一1 慨v ) + 扛y ) 噸，b ，w 挑v ) 在構(gòu)造算法之前先定義以下兩個范數(shù)： 批；l 。+ n p ，v 洋 ，。k ( w ；，y 癢p 。( v ，v ) + n ( y ，v ) + ( g ，b ，w ，v 癢 現(xiàn)在構(gòu)造求解( 1 1 ) 的瀑布型多重網(wǎng)格法 對n ：1 , 2 逐次求解j ：j 時的( 1 6 ) ，即用橢圓問題瀑布型多重網(wǎng)格法求解 4 碩士學(xué)位論文 ( 1 7 ) 對每個n ，求解( 1 7 ) 的具體步驟如下： 求w 。v o ，使 a ，【w o ，v ) = 0 v v v o 求得近似解以， 對j = 1 ，2 ，j 求解n e w t o n 方程。 4 ：( w ：一。；z ，一w ：- i ，v j ) ；一4 。【w _ ，v ，) v v ( 1 9 ) 也可寫為： 4 b ；。；z ，v ，) 。4 ( w ；- l ，y j ) + 4 ：( w ：一，；w j - i , v j ) 一( g “：一。l v a 在這里我們用磨光線性算子l j 來迭代求解方程 4 ( w ；一，；z j , v j ) = ( g ，v ，) 也就是： z ，一j ? ，z ；s 7 ，b j z o ) 此處z ? h 。是初值。 因為i i 是線性算子，所以s ，也是線性算子，因此，s 7 也是h ，_ h 的線性 算子假設(shè)算子s ? 滿足如下兩個磨光性質(zhì)： l l s ：，噸。墨七( 1 盯1 1 ) - 詈l l v 川。 矗7 粉v 也。s ( 1 仃1 礙產(chǎn)m ， ( 1 1 0 ) ( 1 1 1 ) 注：( 2 9 】對r i c h a r d s o n 迭代作為光滑子證明了上述性質(zhì)，對共軛梯度法迭代具 有與上式不同的性質(zhì)，我們將在第三章中討論 算法：c m g 第一步，在i 。0 上求出誡h 。，作為( 1 7 ) 的近似解 第二步，對于j l 2 ，解n e w t o n 方程( 1 9 ) 1 3幾個重要引理 w ；- 1 7 w 在這一節(jié)中，將要介紹幾個引理，它是【1 3 ，1 4 】中的重要引理的推廣，它在多 重網(wǎng)格法收斂性研究中對r 的一致的估計中起關(guān)鍵作用( 見文獻(xiàn)【1 3 ，1 4 ，2 9 】) 5 解半線性拋物線問題的瀑布型多重網(wǎng)格法 引理1 3 1 ，設(shè)f c o i t - 1 0 ，v ) + nv ，v 1 1 l i v l l 。，一k ( w ；州驢zc ， k ( 川v ，v 】；p 。( v ，v ) + n 0 ，v ) + b ，b ，w 卜，v l h - 1 ( v ，v ) + n d ，v ) + p ，v 1 在這里取c 。一m 強(qiáng)k 對 k ( ，v 1s c l 眥 上面定義的兩個范數(shù)是等價的兩個范數(shù)，所以可以得到如下式子 c 。1 批s 。s c 注：文獻(xiàn)【3 2 】中的( 1 1 ) 式是其收斂性證明的基礎(chǔ)，仔細(xì)檢查可知，為了文獻(xiàn)【3 2 】 中的( 1 1 ) 式成立，本文( 1 8 ) 式左端不等式是必不可少的 很容易證明以下這個推論 推論1 3 1 存在常數(shù)c ，0 ，使得有下式成立 c 一1 1 p i h ，( 。) 1 p 0 ，sc 1 卜0 h t ( n ) 引理1 3 3 b 3 】設(shè)w 為( 1 7 ) 的解，w ，為的有限元逼近，則有與| l l ，與f 無關(guān)的 7 解半線性拋物線問題的瀑布型多重網(wǎng)格法 常數(shù)c 使 l 1 ww , l i s c h j ( 1 仃k 喇。 i i w - w , i i 。s 曲；( 1 + f 一1 n ；) 1 l ；4 。 證n n 文獻(xiàn)【1 3 】中的引理2 2 8 f 1 1 4 ) ( 1 1 5 ) 碩士學(xué)位論文 第2 章算法最優(yōu)性( r ic h a r d s o n 迭代情形) 在這一章中將給出以r i c h a r d s o n 迭代為光滑子時的瀑布型多重網(wǎng)格法的最優(yōu) 性e h 1 1 在我們的剖分下有 j 一2 - j h ，在算法中我們?nèi)∝ = k 川j + 1 ， 為取 整函數(shù) 2 1 幾個引理 對于j = 0 1 2 j ，令 呲刊k ， e j = l l w ，一w ；i l ， d ，= l l w ；一w 圳， 且令“：= u ： 在隨后的論述中我們對常數(shù)以序列的形式加以區(qū)分這一章的內(nèi)容安排如 下：在引理2 1 1 中將講述兩個能量范數(shù)1 1 | l m 與恍相關(guān)兩個連續(xù)逼近解“：與“；。之 間的關(guān)系，在引理2 1 2 和引理2 1 3 中我將證明兩個誤差e j 與d j 的遞推關(guān)系在弓 理2 1 4 中給出使得e 有界的一個重要的條件定理2 2 1 則給出了這篇文章的主要 結(jié)論 引理2 1 1 存在與j 無關(guān)的常數(shù)c 。使得1 1 1 i ，。與l l t l ，有如下關(guān)系成立： + 。s1 + c 。k d j 批 證明：利用t a y l o r 展開 g ，b ，w ；) 一g ，b ，w ；。) + g 。0 ，c x w ；一w ；一，) 其中；= 亭g 臉于w _ - w ；。g ) ，w ；= w ；b ) 之間 所以有 俐；+ 。一4 v ) 9 ( 2 1 ) 又因為 所以上式可化為 其中 解半線性拋物線問題的瀑布型多重網(wǎng)格法 = k - t - ，v ) + 口，v ) + b ，b ，w ：卜，v ) = r - ( v ，v ) + 口- ，v ) + k ，b ，w ；一。l ，v ) + b 。b ，毒x w ；一一一，l ，v ) 1 1 v 1 1 ；：- 一p ，y ) + 口0 ，v ) + b 。b ，w ：一，l ，v ) 乒 刪；+ 1 s 呲+ ( g 。b ，c x w ；一w ：。- ，v ) ( g 。g ，d w ；一w ；。卜，v ) = 正g 。b ，考如；一w ；一。l ，2 d x ( 由許瓦茲不等式可得) 又因為 s 正k b ，c i l w ；一w v 2 d x s j | ；, f o i w ；一w ：。l c d x 蔓七一w 圳。 蚓l 。k v z ) 2 出 ：b 4 出陽崛。 所以由嵌入定理和范數(shù)等價可得 所以 g 。b ，c x w ；一w ，v ) s c k l i w ；一w 洲州i t v u = 。， 呲+ 。州e + c l d 加虻 綜上所述可得 ；o + q k d 加曠 s c l k 1 w ；一以打眥 刪ms ( 1 + c x k d ，m i ，s ( 1 + c 。k d 肭 ， 1 0 碩士學(xué)位論文 上面這個引理給出了任意給定的層上的式子能由前一層的式子來表示，特別 是對后面兩個引理關(guān)于e j ；f l ：l d 的遞推關(guān)系起到重要作用下一個引理將給出關(guān)于 e 的一個迭代估計式 引理2 1 2設(shè)瀑布型多重網(wǎng)格法的光滑子滿足如下磨光性質(zhì) l l s ? ：v s ( 1 + f 4 a j l ) - ”1 卜1 i ， 讎v l ；。聳( 1 + g - 1 f 聲 其中a ，= d 協(xié)產(chǎn)) 則存在與j 無關(guān)的常數(shù)c ：，c ，c 。，c ，使得e j 有 e ，s ( 1 + - f 嘞；廣( 1 + c 。船h k ，。+ c ：勛；( 1 + f 4 矗；壯眶 + c ，觸，( 1 + r 4 一；1 p o 。e ，- ，+ c 一婦知+ c s 等( 1 + f 。 ；) _ ?！懊? 。 ( 2 2 ) ( 2 3 ) 證明：該算法中的誤差是由兩個部分引起，一是由于n e w t o n 法引起，二是 由于用迭代法解線性方程而引起的即 e j = 1 1 w ，一w ；l l ，s 1 1 w ，一z ，+ 1 1 z ，一w ；l i ， 由文獻(xiàn)【1 5 】可知n e w t o n 法的誤差滿足如下估計式 一。，s 政一劃 由引理1 3 2 及推論1 3 1 可知：h 1 ( q ) 范數(shù)是與1 1 1 i 。：帥。，是等價的，我們將左邊用咖， 代替h ，( q ) 范數(shù)，右邊則用i | i j 。代替曰，( q ) 范數(shù)，于是有 1 | w ，一z 川，墨c 七j i ，v ，一w ；一，l l ：一。 又用范數(shù)的等價性和誤差分析( 1 1 4 ) 式，b h j 。= 2 h j 則有 i w ，一w m 。s l l w ，一憶+ i l w h w 扎。 解半線性拋物線問題的瀑布型多重網(wǎng)格法 s c 1 1 w ，一w j - 1 n + e ，。 s c i w - - w ，一。l 。+ c i w - - w 卜。l l ，+ e ， s c ”n ，( 1 + r 。1 ；) 1 。- + c h j q ( 1 + f 。 ，i l ；0 。+ e 卜。 又由正規(guī)剖分可得| l z 。一2 h ，所以有 即有 因為有 1 1 w j - w ；， f 卜。s c ：一，( 1 + f 一1 ；8 ；0 。+ e ，。 _ 峙以m w 硝一。 s c 七【c ： ，e + f 。 ；乒 事8 。+ e 卜a i z ，一w 川，- l p 暑( z ，一w ；一t l ， 一( k ，一w j ) + 一w j - 1 ) + ( w 壙嵋城 ( 又因為s 是一個線性算法) = l p 囂g ，一w ，) + s 品一，一w i - i ) + s 0 。一嵋。l ， s 慨( z ，飛卜慨一t l s j t ( w j ，w “ ( 由磨光性質(zhì)( 2 2 ) ，( 2 3 ) ) ( 由引理2 1 1 可知) s ( 1 + - r 4 a - 1 廣忱飛n + ( 1 + f 4 巧1 h k 。一 帆，一w 乩s ( 1 托腳h 。一w 圳，。 一1 + c l k d h 鼻_ 1 ( 2 4 ) ( 2 5 ) w w 葉一： 、廠 ar+ ，q 鏟1 坼 c+ 又因為吩- l = 2 故有 碩士學(xué)位論文 一h ! l - i l w - w 川。+ l l w - w h i | 。 由( 2 4 ) ，( 2 5 ) ，( 2 6 ) 可得 c ；( 1 + f 一1 ；】l ；0 。+ c 二，( 1 + - f _ 1 互，j l ； l 。 s c ；( 1 + r 一1 j l l ；0 。 1 l z ，一w ；l l = 1 i s 囂g ，一w ；一。4 ， s ( 1 + f 4 f 川k ，一 + ( 1 + f 1 巧1 ) _ 0 。一嵋。l | ， l w ，一w j - 1 憶 s c 尼( 1 + r 一1 1 1 ) - ” c ：n ，( 1 + f “ ；磚 l ；1 1 0 + e ，一 + ) _ 等+ 1 l l 主f 。+ ( 1 + f 4 a - 1 ) “( 1 + c ，船卜，- ，。 ( 因為 一d 惦產(chǎn)) ) s c 七( 1 + r - 1 h ；) _ ”【c ： ，( 1 + f 1 ；乒i i ；l i 。+ e ，一，】2 所以可得 + c 0 ；0 。+ ( 1 + f 一1 ；) - 唧( 1 + c 。矗，k ，4 e j = 1 1 w ，一w ；l l ，s 1 1 w , 一z 川，+ l i e ，一w ；l l ， s c 七 c ：n ，( 1 + f 1 ；乒0 ；i l4 e t _ l 】2 + c t ( 1 + f 一1 ；) _ “ 【c ： ，( 1 + r 。1 ，t j 乒l i 主l i 。+ e j q 】2 + c 削眺 ( 2 6 ) 生： 、廠町 一f+ ，u 堅：唧 c+ 丑r+ ，q 生，町 c 一一： 、廠 r+ ，u 生：孵 f+ ，u 生：唧 將上式整理得 解半線性拋物線問題的瀑布型多重網(wǎng)格法 + ( 1 + r - 1 ；) - “，1 + q k d h h e ，s ( 1 + r 一1 ；) _ ”( 1 + c 。七一，。k ，。+ c ：肋；( 1 + 百。1 n ； ；0 i 塢咖嘞哪! - 卜，h 銘塢沙f 嘞；州乩 下一個引理將給出關(guān)于d 的一個遞推估計式 引理2 1 3d ：滿足如下估計式 d j o ，能由上式選取足夠少的氏，丸使得 ( 1 + 砒肌啪。) 】j s c ， ( 2 - 8 ) 成立 證明：對于任意的c 0 ，函數(shù) g 。，= 【。+ c z ) ( t + 詈x ) ；】一“8 1 在( o ，+ 0 0 ) 上是連續(xù)的，且有 堅哿g 。，= 婪珊【。+ 。) ( + 量z ) ；】一“ ：u m 。 h 扣【c 1 r ( i + ) 】。 因此存在6 ( c ) o ，( 6 與c 有關(guān)，故記為6 ( c ) ) 。使得 g g ) s 2 z 【o ，6 】 解半線性拋物線問題的瀑布型多重網(wǎng)格法 即有 s 2 。 兩邊取以2 為底的對數(shù)則有 n ：h 。s ! k m i n c r 2 _ j , 1 ，6 ( c h 由于當(dāng)x 【o ，6 】有g(shù) ( x ) s 2 即有 h ；e 銣2 詈z 1 。 j l o g 一l o g 靦os b g 洶。) s 2 ( e t + d 確。) ( + 詈七。) i 】一1 。畦= ；2 【( 1 + c 舫。) ( 1 + 砌。硅】b 8 s z 又因為有墨瓦1 ，兩邊取對數(shù)可得 結(jié)合( 2 1 0 ) 式可得 一1 0 9 j 1 1 s ( 1 + 。舫。x 1 + 幽。) ；s 2 ( 1 + c 舫ox 1 城曠* 由( 2 9 ) 式可得 ( 1 + 鉑。x 1 城小 ( 1 + 蛾x 1 城曠時 s 【( 1 + 妣x 1 + 嘁曠 ( 1 + 妣x l + 叫咖爭 ( 2 9 ) f 2 1 0 ) 即有： 【( 1 + c 脅。) ( 橢小2 c ， 注：這個定理中很重要的一點在于通過與h o , h ，j 無關(guān)的常數(shù)c ，給出了 碩士學(xué)位論文 ( 1 + m 。x i 砜) ；卜上界，對于算法的收斂性證明和對時間步德耵至關(guān)重要 的作用 2 2 收斂性定理 下面將給出的是這篇文章的一個最為重要的結(jié)論 定理2 2 1 設(shè)磨光算子s ；滿足磨光性質(zhì)( 2 2 ) ，( 2 3 ) ，在j 層上的迭代次數(shù)滿 足 m ，= k ，蘆j + 1 j 一1 ，2 ，3 j ( 2 - 1 1 ) 此處盧 4 h o 和h s 滿足( 2 7 ) 式時間步f 滿足f a o ( h 。) 設(shè)以是j = o 上的方程( 1 7 ) 的近似解，且有 e 。蔓eh j ( 1 + r 。1 n ；0 ；l | 。s 。( 2 1 2 ) 則對于選取足夠小的h o 及h ，使算法得到一個近似解w ；滿足 e ，s c 。 ，( 1 + - f - 1 ；p i i ；0 。 ( 2 1 3 ) 此處 c 8 = 2 c 7 t 樂刪。線c ，南】 證明：首先定義兩個常數(shù) c 。= ( c 。c ，+ c ，+ c 。c 。j 眵0 。 吣扣n 卜丟如。x 贏j ( 1 + 出。x l 城卟2 c ，m 2 - ， 1 7 f 2 1 4 ) ( 2 1 5 ) ( 2 1 6 ) 解半線性拋物線問題的瀑布型多重網(wǎng)格法 鏟【( 1 + 執(zhí)x 1 城) ；卜蚓稚磚p ? ) ( 1 + 拋肌砌。擴(kuò) 吩扯訓(xùn)拈堿x 1 + 叫卜 ( 2 1 7 ) ( 2 1 8 ) ( 2 1 9 ) 用數(shù)學(xué)歸納法證明上述三個不等式 當(dāng)，= 0 時，由( 2 1 2 ) ( 2 1 3 ) 式顯然成立 假設(shè)當(dāng)f j 時上面三個不等式成立，下證明當(dāng)i = + l 時成立由引理2 1 2 可知： 因為 _ r “i l o ，m 產(chǎn)1 所以有 ( 1 + f 。1 _ l l ；) - 一“1 所以有e 1 喁卜h 磁，k j + c ：峨1 蠕械 均訕f 嘞卅卜姊c s 摯 甜爭 s ( 1 + c 。z 矗，k ，+ c ：z 啦二。( 1 + f 4 知 ；0 ：+ c ，觸，。q + r 一1 一舂，l 凈l i 。e ， 蠔婦j + c s 等p 二，戶姚 s 1 + 七【c ，d ，+ c ， ，。6 + f 4 鼻。# ；。+ c 。e ，】卜，+ c z 七一二t ( 1 + f 。 知；0 i + c s 等”釁8 。 s f - + 七( c ，c ，h ，( 1 + f 。1 n ；乒4 9 。0 。+ c 3 h i + l ( 1 + f 一1 ；+ 1 、10 9 一9 ) + c 4 c skh i ( 1 + f 。1 ；) ： 齜卜 礎(chǔ)仃k 制卜摯百嘞州。 1 8 0 i j 怕j i 0 = 呈 忙憎e 硅 2 ， 2 j f f 卜 + g 0 j 0 吒 島 v i s e d 碩士學(xué)位論文 s 【+ 七一，( 1 + r 1 ；p ( c ，c ，+ c ，+ c 。c 。1 p l i 。 e j + c 2 k h 二。( 1 + r 。1 矗。 ；i i i 塢等( 1 酬；扎 蘭i + c ，a k h o h 4 講嬲m 緋卜篙h “沖l s ( 1 蝎朋。) ( 1 仃k e e ，+ c z k h 二。1 酬廿c ，等w 。札 ( 又因為f o ( h 。) 即有f h 。一口) 球托融) ( 1 + 戰(zhàn)娃e j + c 2 k h 蓋。( 1 盯1 洲0 等( 1 盯1 酬；1 1 0 將e 的假設(shè)代入上式 s ( 1 + c , o k h o ) ( 1 + 砜心緘x 1 城小塢喇p 砰) 崢肌叫卜塢。塞沙f 嘞巾礎(chǔ)喊磅r + c z 蝙( 1 汀1 姍c ，等( 1 仃1 蠕札 巾幽。x 1 城) ；y e o + qk 峨霪 ? p 砰) 【( 1 嘲x 1 城曠1 塢。恥訓(xùn)緲誡m 。) ；廠 這就是i - j + 1 時的情形下面將證明當(dāng)i ，j + 1 時的( 2 1 8 ) 和( 2 1 9 ) 成立 又因為h ，。- 2 h 及( 2 1 1 ) ，( 2 1 6 ) 可以得到如下式子 e ，“s 2 c ，e 。+ 2 c ，c z 七9 ；0 i 鬈_ h ? ( 1 + f 。1 _ l ? ) + 2 c ，c s0 ；6 。薯嘉( 1 + f 一1 ，i ? ) 1 9 解半線性拋物線問題的瀑布型多重網(wǎng)格法 妣 + 4 c k 餓扣咖制。喜善 蛾舢脅w 乒1 。m k 喇。2 n ：+ 1 4 + 4 c 7 2 c 5 毒薹2 。， 又因為 所以有 所以( 2 2 0 ) 式可化為 瑤s 譬 ， 托 砌：c t h j 。拙舳h 嘞州。+ _ c 4 k 州 i + 4 c 沁去冀斟 蛾， i i i i o 刮鳳 吼吣一1 磚乒+ 爭2 ：h ig 。+ 卻s 舢1 霹睜釁1 1 0 + 2 c 7 c s 肌h 薌, 毒 如 h 嘞群巾弘化 i 1 毒 釓幻艫霹帆 其中系數(shù)c 。為 鏟2 十爭嬸專毒1 下面證明當(dāng)i j + 1 時的d 撐由引理2 1 3 可知 、liil， 一2 三 ，j_ = 三孓龠 虬1 孵 碩士學(xué)位論文 d ，+ 。s e ，。+ c 。 ，。：- l h 蓋：聲l i ；8 。+ 【1 + c ：t d ， ， c 由假設(shè)當(dāng)i = ，時d j o 存在唯一的多項式辦。己，九，( o ) = 1 ，使得c h e b y s h e v 多項式k + ，b ) 可表為 k 。b ) = ( 一1 ) j ，l ( 擁+ 1 k 廬。，協(xié)2 ) 并且多項式九。是極大極小問題 磐剖_ p g l - r a i n ! m ( o ， 】i 1 v p 己p ( 0 ) = 1 的解，最小值由p 式給出 蚓峨。坼瓜舊+ 1 ) 而且蚓妒- 。g j _ 1 由這個引理可以得到如下引理 引理3 1 2 存在一個線性算子臻a 辦，忸 ) ，此處以一巴，九。( 0 ) = 1 使 得： 慨b 要州i 。 雌_ ( 3 - ) 解半線性拋物線問題的瀑布型多重網(wǎng)格法 1 瞻v 川。s 。， v v s _ ( 3 2 ) 證明：( 1 ) 設(shè)妒。，妒：，為的正交基，且有b ，) = 6 “，此處6 口是k r o n e c k e r 符號并且滿足 a j ，妒。墨a “妒。= o , 1 , 2 n ， 其中o s 五1 s 元2s s 互一， o ，能由上式選取足夠少的h o ，使得 ( 3 4 ) 【( 1 + 出。x l 堿小c ， ( 3 5 ) 成立。 證明類似于引理2 1 4 下面將給出是在以共軛梯度法為光滑子的情形下算法的收斂性定理 定理3 2 1 設(shè)磨光算子s ，滿足磨光性質(zhì)( 3 1 ) ，( 3 。2 ) 在j 層上的迭代次數(shù)滿 足 m = b ，盧川j + l ，- 1 ，2 ，3 j ( 3 6 ) 此處盧 2 h o 和以滿足( 3 4 ) 式時間步f 滿足r o ( h o ) 設(shè)以是，= o 上的方程( 1 7 ) 的近似解，且有 e 。s s ，( 1 + f 1 ；乒9 ；8 。 。 ( 3 7 ) 則對于選取足夠小的h o 及b 使算法得到一個近似解w 二滿足 勺s c 。 ，( 1 + f 1 ；) ：歸1 l 。 ( s s ) 碩士學(xué)位論文 此處 鏟2 c ，卡z g o + 2 c 5 c 7 而切) 證明：首先定義兩個常數(shù)： 。9 = 3 c 8 + 。6 適當(dāng)?shù)倪x取h 。，使得 = ( c l c 9 + c 3 + c 4 1 9 0 。 h 。s 曇i i l i n 庀 印。拯 孤1 由h 。的選取及引理3 2 4 可得： ( 1 + 幽。x 1 + 毗小z c ，m 2 j 對于j 一0 ，t , 2 j 我們將看到如下不等式成立， 可知 ( 3 9 ) ( 3 1 0 ) f 3 1 1 ) 鏟 ( 1 + 啪。x 1 城) ；卜啦( 1 一 州( 1 誡x 1 堿曠 塢。 扣f 訓(xùn) ? 鼎 ( 1 + 砌o x l + 甌甲 e 產(chǎn) k 1 巧喇。 d ，c ， ，( 1 + f - 1 ；# l i ；i i 。 ( 3 1 2 ) ( 3 1 3 ) r 3 1 4 ) 用數(shù)學(xué)歸納法證明上述三個不等式 當(dāng)，一o 時，由( 3 7 ) 可知，( 3 8 ) 式顯然成立 假設(shè)當(dāng)i 互j 時上面三個不等式成立，下證明當(dāng)i - j + 1 時成立由引理3 2 2 e ，“s ( 1 + c ，t 矗，k ，+ c ：觸太。( 1 + r 一1 五；虻+ c 3 c h j + l ( 1 + z 。1 一五。e8 ；l 。e ， 解半線性拋物線問題的瀑布型多重網(wǎng)格法 + c 。b 知。+ c ；! ! i 三i 等n ；( 1 + r 。1 n 二。 ；9 。 s 1 + t ( c t d j + c 3 h j + 1 ( + f 。