（计算数学专业论文）hamiltonjacobibellman方程的数值解.pdf

! 罂：! ：! ：i ! ：! ：i ：壅堡墼鍪堡壁 a b s t r a c t t h eh a m i l t o n - j a c o b i b e l l m a ne q u a t i o n sh a v eb e e nw i d e l yu s e di ne n g i n e e r i n g a n de c o n o m y ，a n dt h et h e o r ya sw e l la st h en u m e r i c a ls o l u t i o n sf o rt h e mh a v ea t t r a c t e d m u c ha t t e n t i o n i nt h i sp a p e r ，w ed i s c u s sm a i n l yt h en u m e r i c a ls o l u t i o no ft h ed i s c r e t e p r o b l e mo fak i n do fh a m i l t o n j a c o b i b e l l m a ne q u a t i o n s f i r s t ，w ec o n s i d e ra ni t e r a t i v ea l g o r i t h mo fj a c o b it y p ea n dt h ec o r r e s p o n d i n g d o m a i nd e c o m p o s i t i o na l g o r i t h mf o raa p p r o x i m a t eq u a s i v a r i a t i o n a li n e q u a l i t ys y s t e m o f t h eh a m i l t o n - j a c o b i - b e l l m a ne q u a t i o na n dt h ec o r r e s p o n d i n gc o n v e r g e n c e p r o b l e m w ei n t r o d u c e t h ei t e r a t i v em e t h o do fj a c o b it y p et os o l v et h ed i s c r e t e p r o b l e mo ft h eq u a s i v a “a t i o n a li n e q u a l i t ys y s t e m an e wp r o o ff o r t h em o n o t o n e c o n v e r g e n c eo ft h ei t e r a t i v em e t h o di sg i v e nu n d e ra p p r o p r i a t ec o n d i t i o n s t h ed o m a i n d e c o m p o s i t i o nm e t h o do fj a c o b it y p ef o rt h eq u a s i v a r i a t j o n a li n e q u a l i t ys y s t e mi s p r o p o s e da n dt h ec o r r e s p o n d i n gm o n o t o n ec o n v e r g e n c et h e o r yi se s t a b l i s h e d 。 s e c o n d ,w ep r o p o s ea ni t e r a t i v ea l g o r i t h mo fg a u s s - s e i d e lt y p ea n dad o m a i n d e c o m p o s i t i o na l g o r i t h m b a s e do nt h ea l g o r i t h m so fj a c o b it y p e ， w ec o n s t r u c t a l g o r i t h m s o fg a u s s s e i d e l t y p e o n e o ft h ea d v a n t a g e so ft h e a l g o r i t h m s o f g a u s s s e i d e l t y p ei s t h a tt h e y ，i ne a c hi t e r a t i o n ，u s et h en e w e s tm e s s a g e si nt h e c o m p u t a t i o n h e n c e , t h ea l g o r i t h m so fg a u s s s e i d e lt y p ea r ef a s t e rt h a nt h ea l g o r i t h m s o fj a c o b it y p eg e n e r a l l y u n d e ra p p r o p r i a t ec o n d i t i o n st h em o n o t o n ec o n v e r g e n c eo f t h ea l g o r i t h m so fg a u s s - s e i d e lt y p ei sp r o v e d t h ec o r r e s p o n d i n gc o n v e r g e n c et h e o r y i se s t a b l i s h e da l s of o rd o m a i nd e c o m p o s i t i o nm e t h o do fg a u s s s e i d e lt y p e f i n a l l y ，w ep r o p o s e an e wi t e r a t i v em e t h o df o r s o l v i n g t h ed i s c r e t e h a m i l t o n - j a c o b i b e l l m a ne q u a t i o n sd i r e c t l y c o m p a r e dw i t ht h ea l g o r i t h m sm e n t i o n e d a b o v e ，o n eo ft h ea d v a n t a g e so ft h em e t h o di st h a ti td o e sn o tn e e dt os o l v ea n yl i n e a r e q u a t i o n so ri n e q u a l i t i e s s ot h ei m p l e m e n t a t i o no ft h em e t h o di sv e r ys i m p l ea n de a s y a l t h o u g hi t sc o n v e r g e n c er a t ei ss l o w ，n a m e l yi tn e e d sm o r ei t e r a t i v et i m e s , t h e p r o c e d u r ei sv e r ys i m p l e ，m o r e o v e r ，i ti sc o n v e n i e n tt ob ep a r a l l e l l i z e d f u r t h e r m o r e ， c o r r e s p o n d i n gt h e o r e t i c a lr e s e a r c h e so nh o wt oc h o o s et h ei n i t i a l v a l u ei nt h eg i v e n a l g o r i t h mh a v eb e e ns t u d i e di nd e t a i l s 。 t os h o wt h ee f f e c t i v e n e s so f t h ea l g o r i t h m sp r o p o s e dh e r e ，n u m e r i c a le x p e r i m e n t s h a v e b e e np e r f o r m e d t h en u m e r i c a lr e s u l t ss h o wt h ee f f e c t i v i t yo ft h ea l g o r i t h m s k e yw o r d s ：h a m i l t o n - j a c o b i - b e l l m a ne q u a 娃o n s ；l l e r a t 主v ea l g o r i t h m ；d o m a i n d e c o m p o s i t i o nm e t h o d ；q u a s i v a r i a t i o n a li n e q u a l i t y ；m o n o t o n e c o n v e r g e n c e 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其 他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果 由本人承担。 作者签名：i 垛苑哞日期：厶彭年岁月f 夕日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查 阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位 论文。 本学位论文属于： l 、保密口，在年解密后适用本授权书。 2 、不保密囱 ( 请在以上相应方框内打“”) 作者签名： 导师签名： 1 1 春芄璋 国丈 日期：扫口厶年岁月印日 日期：卜6 年j 月心日 硕士学位论文 第1 章绪论 在这一章中我们将概述h a m i l t o n j a c o b i 。b e l l m a n 方程( 简称h j b 方程) 及 其数值解研究的一些存关研究成栗，并简介本文结果。 1 。1h a m i l t o n j a c o b i b e l l m a n 方程 考虑如下形式的一类j 线性二阶椭圆h a m i l t o n j a c o b i b e l l m a n 方程的 d i r i c h l e t 问题： s u p a ( v ) u 0 ) 一， ，v ) = 0 i nq “一0o na q( 1 1 ) 其中a ( v ) 一- 0 5 t r 0 7 v ) d 2 一g ( x ，v ) d + c 0 ，d ，a ( v ) 是二阶致椭圆算子，d 是梯 度算子( 也可用v 表示) ，d 2 是二阶导数矩阵，0 5 t r o t r d 2 ；y 痒。上，这墅c 岛9 魄缸， 是给定的函数， g ，疗是函数向量，v 是一个控镣变量，且v 矿，v c r ”，q 是靛2 中的有界开区域， a q 足够光滑，0 ，v ) 是给定的光滑实函数。 h a m i l t o n - j a c o b i - b e l l m a n 方程来源于r b e l l m a n 在文献f 1 e e 运用动态规划 原理求解一类随枫控铡闽题。 自那时以来，特别是二十世纪八十年代以来，h a m i l t o n 。j a c o b i b e l l m a n 方 程的理论研究涤受数学家和工程师们的关注，取得了匝大进展和广泛的应用( 见 文献【3 1 2 】) 。 当控制变量集v 为有限集时，( 1 1 ) 可写成如下形式： 豁口一，) # 0 i nq u 一0o n8 q ( 1 2 ) 己ce v a n s ，pll i o n s 簧在文献【8 ，9 】中证明了( 1 2 ) 可用下述拟变分不等 式缀邋近： 口弛，v u i ) ( f i , v 一摊) ，v j o 。 ( 2 1 ) 定义2 1 。1 设a e r ，如泶a 非鸯其，a z o ，且0 ，i # j ，i ，一毛2 ，嚣尉称a 为m 矩阵( 简称m 孵) 。( 见文献 3 6 ，3 7 】) 本文憾设( 1 5 ) 、( 1 7 中的e 为m 阵，这是一个合理的假设，参看文献 2 7 ， 3 2 1 。 下面，我们给出h j b 方程翡j a c o b i 型迭代爨法：( 见文献 2 0 】) 记0 一( c ，1 ，u ”) ，疗“一( u “3 ，u “t “) 。 算法2 1 ： 步1 ：敬初值u o = 0 ，迭代终止猴则s 0 ， 步2 ：求u ”o r “，n = l 2 ， ( 掣u ”一f ，v u 4 ) o ，y v k + u “4 l “，( 2 2 ) 玎“o k + 秽”一1 靠， i 霉毛2 ，m ， u 8 唯矗f “端u 4 _ d 。 步3 ；搬果| | u “一u “黔s ，羽簿葵；蠢粼n ：= 羲+ 1 ，返黧步2 。 算法2 2 ： 步1 ：取初悠u o ，使e u “一f2 0 ，迭代终止猴则s ，0 ， 步2 ：( e u “一f ，y u “o ) z 0 ，n = l 2 ， v v 墨七+ u “。1 。+ l ，u ”。s k + u “- 1 。“， i l 2 ，m ，u “1 ，埘+ 1 雀u “一1 步3 ：如栗0 u 一u ”惦s ，则停算；否则，n ：= n + l ，返涸步2 。 虫熟知豹定壤( 援l 文献 2 8 】) ，予问题( 2 2 ) 等价予下碉互孙问题： g u ”一f ) s o ，( u “4 一k u “。“) s 毡q j u “一f iu “。一k u ”o “) = 0 ( 2 。3 ) 下面，我们证明棼法2 1 的单调收敛缝，为便于诞嘲，我们绘融一个重要的弓i 理如下， 引理2 1 没c 为骓降，颤= v r 2 ：v ，若戎磷，且口2 龟，( c o 一f i , v 一疗) 0 ， v v e k f ，i l ，2 ，哭l 有疗2 疗1 。 硕士学位论文 证：设n = 氆2 ，棚 ，1 1 = s e n ：玩2 = 菇) ，则当s 时， 玩2 = 露急戎瓯1 ( 2 4 ) 当s e n 1 1 对，玩2 c 程，由互补性质知( c 玩2 一f ) 。一0 ，同时( c 玩1 一f ) ，s 0 ， 两式相减得到( c 够2 一疗1 执皂0 ，即 ( c 妙2 一疗1 ) ) ，u 毒o ，即g u 痧2 - d 1 ) ，u + g 嵋 够2 一疗1 h o g g c n s o ，列由( 2 4 ) 知c v l 够2 一疗1 ) s o ，所以c 珥，碣移2 一疗1 ) ，磁芑o ，又 c u 为m 阵，故 矽2 一疗1 ) 。0 ( 2 5 ) 由( 2 4 ) 与( 2 5 ) 知疗2 疗1 。 下嚣我们给出算法2 1 的纂调收敛性定理。 定理2 1 假设0 为m 阵， 移“ 由算法2 1 产生，则迭代解序列 移“) 单调递增收敛于 问题( 1 5 ) 的解u 。 证明：单调性， 先诞疗1 疗衄，由算法2 1 步1 知，初僮舀o = o ，下标集合t = ，： 疗一k ) ，i l ，2 ，m ，当j 五辩，疗= 七，0 ，即 咄，掣2 0 ( 2 6 ) 当，醚，痧yc 七，由互补性质知，( 政- f ) j = 0 ，即口疗y - f ) ，珥一。0 ， 故 t n v j n 。电鼍q i + 1 2 。，亩等j = f 。q j 2 1 、 由( 2 1 ) 、( 2 6 ) 与骓簿的性质知， 0 肌一疗1 , 1 兰f v ，= o ( 2 8 ) 丽m 阵的主子阵仍为m 阵，所以由( 2 8 ) 推出疗= o ，此式与( 2 6 ) 一越表 明 疗“0 。疗o o ( 2 9 ) 再证疗2 j 疗“，i = 1 , 2 ，m 。我们有留疗“一，v 一疗u ) 0 ， v s 露+ 疗。m ， 够1 j s k + 疗o ，“，口疗“一f j ，v 一疗2 ) 0 ，v 蓝k + 疗1 m ，疗2 ，k + 疗1 。“，又0 为m 障， 虽疗1 川苫疗o “，所以由引理2 1 得出疗2 。惫疗“，i 一1 ，2 ， f 。 用数学i 穗纳法证明痧”。之疗“一，m 一毛2 ，。 假设当m ：z 时，有疗口七疗。“成立，剡当m z + 1 时，有 ( 0 疗“一f ，v 一疗“) 赢0 , v s 惫+ 疗l - l , i + l 疗巧s k + 疗m ， ( c 疗m 一f i ，v 一疗m 。) 芑o ，v s k + 疗球，疗。s 膏+ 驴巧， 由假设与引理2 1 知驴“1 。z 疗“，所以有疗州疗一“，m 一1 ，2 ，成立。 有界性，设疗满足0 疗+ 一f 一0 ，政7 ”一f s 0 ，两式相减则得到 掣西一够“。) 0 ，r 为m 阵，故痧”s 疗，即 疗” 有上界疗，n l 2 h a m il t o n j a c o b i b e l l m a n 方程的数值辫 由，知矽“ 单调且蠢上爨，赠 痧“ 必蠢掇隈疗8 ，却麓疗“。m 移。 影疗一f 7 墨o ，痧8 。蓝良+ 疗”。“，( 叠痧舢一f ，疗一k 一彩4 以m ) 篇o ( 2 1 0 ) 在( 2 1 0 ) 中取极限德，寥疗一f s 0 ，扩s 是+ 拶“，嘏疗。一，彩。一k 一驴“) 一0 霹疗= u 是( 1 5 ) 的解。 由一知，由算法2 1 产生豹迭代躲序列 疗” 单调递增收敛于闷题( 1 。5 ) 的解u 。 洼：同瑗，我们w 诞硅i 算法2 2 产生的迭代解序列 d 撕 单调递减收敛予阀题( 1 5 ) 的解u 。 2 。2h a m i l t o n - j a c o b i 。b e l l m a n 方程的j a c o b i 型区域分躲算法及其收敛 性 文献 1 8 ，1 9 ，2 1 1 分嗣研究了不闲类型静h a m i l t o n - j a c o b i - b e l l m a n 方程的区 域分解算法。篡中与本文密切摇关的是两叔子教授在 1 9 p p 研究了h j b 方程的 j a c o b i 囊区域分孵算法，其方法适嗣予多予域愫形，本文戴给嫩一类算法如下： 算法2 3 ： 步1 ：设；m u 2 ，取u o = o ，这代终止准则 0 ，m ：= l ； 步2 ：对i 一1 ，2 ，m ，对，一1 , 2 ，并季亍求解下列问题： u 8 州栉o ，暖u 叫”一f ，v u ”o ) 0 ，v v e 胃。， 其中秽。* p 掣：一譬“，当s = n j ；k 老+ 譬- 1 , + 1 当s j 步3 ：，“l m a x “砧，u o i l2 ，m 。 步4 ：如聚l i u 一u ”| | * s ，粼停算；否则m ：。m + l ，返圆步2 。 算法2 + 4 ： 步1 ：取稠後u 。，使l u “一f ；0 ，迭代终止准雯| l 0 ，m ：= l ； 步2 ：对i * l ，2 ，m ，对，一1 , 2 ，并行求解下列闷题： u 4 ，蹬。，( 掣u “，“一f i , v u ”7 ) 老0 v v e ；。， 其e e 掣。 v r “：k = 叼。，当s ；n n ，；坟蓝七+ 叼- l i + i 当s n j ) 。 步3 ：u ”j m i n u ”鼬，u 4 4 2 i l ，2 ，m 。 步4 ：如采| i v 一u 4 艮ss ，刚停算；森剡m ：= m + l ，返围步2 。 下箍，我们诞明算法2 3 豹单调收敛健，为便于涯明，我们绘出另一个重要 豹引遐如下， 引理2 2 设w 舞m 阵，f 一是u 1 2 ，n j 2 一妒，一p e ：vs 妒。，致= 妒当s i z 。 若谚a 程，羹移。譬，( w 疗“一f ，v 一痧”。) 毫o ，蜥茸，i ；l ，2 ，烫4 疗2 舀1 。 硕士学位论文 证明：设墨，； s j ，：霹= 1 】f ，； ，刚当s 只，时， 玩2 妒? 芑妒：z 玩1 ( 2 1 1 ) 当s 墨，对，霹t 妒；，由互幸 性质知( w 玩2 一f ) ，一o ，同时( w 玩1 - f ) ，- = 0 ，两式 相减得到( w ( 玩2 一玩) ) ，邕o ，当s 点，时，即珥，( d s 2 一彰1 ) ，乏o ，即 w ，l 鹕。 ( a s 2 一玩1 ) 城。+ 碣。 岷( 瓯2 一玩1 ) 圳兄o ，两k 嵋，如峭，s o ，由( 2 1 1 ) 与已 知条件的定义得积2 - 0 = 1 ) 。4 ，o ，故k 域。 。目。( 以2 一或1 b ：峭；s o ，于楚 域，( 瓯2 一玩1 ) o ，又k 峨。 为m 阵，所以 妙s 2 一玩1 h 怫，之o ( 2 。1 2 ) 此式与( 2 1 1 ) 及己知一起得到西2 疗1 。 下面，我们给融算法2 3 的单调收敛性定理。 定理2 2 假设0 为m 阵及 扩) 由算法2 3 产生，则迭代解序列 扩 单调递增收敛予 问题( 1 5 ) 的鳃u 。 证明： 单调性，先诞疗1 惫疗o ，设l ，一秘1 ：瓯埘。= 需+ 司2 ，当s l 。时， 疗：砧一膏+ 疗r ，- 0 = d s o ( 2 1 3 ) 当s l 时，由算法2 3 步2 知 疗s 1 鼬一疗，。4 = o = 疗s 。 ( 2 1 4 ) 当s l l 。时，玩1 砧t 七+ 司。，由互补性质知脚1 - f ) ，一o ， 另一方面，暖疗。一f ) ，墨0 ，两式相减得( 1 2 矽u 。一疗o ) ) ；0 ，则当s 1 l 。， 口面枷一拶) ) m 域，0 ，即 1 ，“，( 西1 3 , 1 - - 疗。) mw l ，f m ，批l ( 疗1 h 一疗。) 码+ 0 、，以，西1 鼬一疗。) m ，皂o ， 由( 2 1 4 ) 知穆1 一疗。) 鹕- o ，则z 鹄域。( 移1 3 3 - d o ) 一0 ，由( 2 1 3 ) 知 ( 疗1 甜一疗。) u , - 0 ，而0 1w l ， ，s o ，所以f l 磁， 。影1 鼬一疗。) 1 1s o ， 故有三i i ，“，( 疗1 砧- d 。) 、。o ，闲露l ，以，为m 阵，所以 移u 3 一护) 麒抛，乏0 ( 2 1 5 ) 由( 2 1 3 ) ，( 2 1 4 ) ，( 2 1 5 ) 得到 移1 挪疗。 ( 2 1 6 ) 同理可证 疗u 2 疗o ( 2 1 7 ) 则由算法2 3 步3 ，( 2 。1 6 ) ，( 2 1 7 ) 知疗1 痧o 。 下证驴2 痧1 ，设n ：一 s e n l u 现s 砧一七+ 彩y 2 ，当s 2 ：时， 7 h a m i l t o n j a c o b i b e l l m a n 方程的数值解 疗= 量+ 霹啦七瓯m ( 2 1 8 ) 当s e n 职时，由算法2 3 步2 知 瓯2 口一玩u 3 ( 2 1 9 ) 当s 舨2 ：时，霹舢t 七+ 露。，由互补性质知嘏岔2 肌一f ) ，。0 ， 另一方霞一疗m f ) ；s o ，两式相减褥到0 m 、矽2 砧一疗1 3 1 ) s o ， 则当s e n l n 2 2 对，矗炳、 ( 疗2 嚣一疗1 3 3 ) o ，即 三f l 、如娜( t 7 2 撕一疗1 “) m + 0 l ，m ( 疗m 一驴1 。3 ) + r 】岷够2 鼬一疗1 3 3 ) 如芑o ，类 似中，由( 2 1 8 ) ，( 2 1 9 ) 知0 1 w 1 够2 赫一巧1 船) w = o rl 挑慨如西2 埘一疗瑶3 ) 如o ， 故得到0 l 、 k 以、。够2 3 3 - t ? u 3 ) 以、o ，丽0 l 、 k 川、如为m 辫，则 彬“一面u 3 ) m 岷芑o ( 2 2 0 ) 由( 2 1 8 ) ，( 2 1 9 ) ，( 2 2 0 ) 知疗2 j 3 之疗1 勰，同理可证 疗2 上2 疗埔2( 2 。2 1 ) 由算法2 3 步3 ，( 2 2 0 ) ，( 2 2 1 ) 可得巧2 疗1 。 下面我们用数学i | j 纳法证明：疗“惫疗”球，l l 2 ，假设当n = h 时，疗虾痧“ 成立，当n = h + l 对，则由算法2 3 步2 与引理2 2 可知扩“疗蛳成立，h = l ， 2 ，故由上两式w 知，原命题疗“o 驴“o ，n l ，2 ，成立。 有界性，设疗”满足疗”一f = 0 ，舅疗“一f s 0 ，鹾式穗减则得至1 0 心”一疗蛳) 0 ， 叠为m 阵，故痧蛳墨疗，即移6 0 ) 有上界疗”，弹；1 , 2 ，。 出一知彬6 ) 单调鸯上界，故迭代解序列移6 有极限疗，即 i m 扩= 巧。 ( 见文献 1 8 1 ) 由解的唯一性，驴即是阀题( 1 5 ) 的解u 。 由一知，由算法2 3 产生的迭代解序列矽“) 纂调递增收敛于闽题( 1 5 ) 的解u 。 注：弼理，我们还可证明算法2 4 的解序列舻” 的荦调收敛憾，即矽“ 荦调递减 收敛予问题( 1 5 ) 的解u 。 8 硕士学位论文 第3 章g a u s s s e i d e l 型迭代算法 在这一章，我们将针对h j b 方程的d i r i c h l e t 问题的逼近问题的离散形式即 问题( 1 5 ) 提出一类g a u s s s e i d e l 型迭代算法及相应的区域分解算法。在3 1 中， 我们介绍了g a u s s s e i d e l 型迭代算法，给出了在一定假设条件下由该算法产生的 迭代解序列的单调收敛性证明；在3 2 中我们介绍了g a u s s s e i d e l 型区域分解算 法，给出了在一定假设条件下由该算法产生的解序列的单调收敛性证明。 3 1 h a m i l t o n - j a c o b i b e l l m a n 方程的c r a u s s - s e i d e l 型迭代算法及其收敛陛 在这一节，我们研究了h j b 方程的g a u s s s e i d e l 型迭代算法，并给出其单 调收敛性证明。 如前所述，文献【8 ，9 】证明了( 1 2 ) 可用( 1 _ 3 ) 逼近，在本节我们考虑用 下列拟变分不等式组逼近问题( 1 2 ) ： ( 2 zv 一打) 2 ( ，。，v 一) ，v 日；( q ) ，v v 蔓七+ f f h ， i s k + 五。4 i = 1 ，2 ，m ， ( 3 1 ) 其中疗m = 打o ，k 0 ， 且扩 ，p ) 一 ， i = 1 , 2 ，m 下面我们证明问题( 1 3 ) 与( 3 1 ) 是等价的。 定理3 1 问题( 1 3 ) 与( 3 1 ) 是等价的，即若f ，“2 ，“”) 为( 1 3 ) 的解，何t , f f 2 ，) 为( 3 1 ) 的解，贝0 厅皇“1 ，i l2 ，m 。 证明：因为何，v ) ； ，而( h ，v ) = ( 爿“，v ) ，所以啦，v ) 一a 咐1 ， 所以( 3 1 ) 可写成 a m - i + l 幢1 ，v 一) 2 ( ，v i f , ) ，v vs 七+ 1 7 h d 4 s k + t 7 i q , i ；1 2 一，m 令一。“，则上式可写成 口m - i + 1 ( i + l ，v 一矿州) 芑( ，2 ，v w 1 ) ， v v 三七+ 一 w m 一s k + w r 一( 。) ；k + 一1 ，i 。1 , 2 一m ， 也就是 ( ，v w ) 2 ( ，2 ，v w 。) ，咖s k + “ ，s k + “，i = 1 2 叫m 它与( 1 3 ) 形式相同，由解的唯一性得 = ，f ；1 ，2 ，m ， 所以存盯。儿= = u ，也就是酽= “1 儿，i = 1 ，2 ”，m 。证牛 所以疗盯“= h ，= u 1 ，乜就是酽= 埘1 “，i = 1 ，2 ”，m 。证毕 h a m i l t o n j a c o b i - b e l l m a n 方程的数值瓣 闯遂( 3 1 ) 的离散形式如下： ( r u 一，v u ) 惫0 ，v v e r “，v s k + u 卜1 u 墨k + u i - l , i t 2 ，m ( 3 2 ) 它与( l 5 ) 裔定理3 1 所述的类似豹等价拣。 鳃( 3 2 ) 豹g a u s s s e i d e l 型迭代算法始下， 算法3 1 步1 ；取初德u o = o ，迭代终止准则 o ， 步2 ：求，4 0 r 4 ，m 一1 , 2 ， ( c u 琳j 一芦v u 坩o ) 0 ，v v s k + f ”，( 3 3 ) u 4 蕉k + “- 1 ， i 葛1 ，2 ，冉f ， u ”筘茹移叶坍， 步3 ：如果| l u ”1 一u ”器s ，贱停算；否则m ：m m + l ，转步2 。 算法3 2 疹1 ：取初德u o ，使得u 。一f i = 0 ，迭代终止准粼 o ， 步2 ：求u “r 4 ，柳= 1 2 ， ( l u # 一f 。v u “o ) 0 ，v v s k + ，“l _ 王，( 3 4 ) u ”。k + u “。一， i 一1 , 2 ，m ， u ”= u “。捌， 步3 ：如果l u 1 一u ”牾，则停算；否则m 肼+ 1 ，转步2 。 下蕊，我稍给出g a u s s 。s e i d e l 型迭代葵法3 。1 的肇调收敛憔证聪，为便予证 明，给班一个薰要静弓| 理鲡下： 引理3 1 子翊透( 3 2 ) 等价予下列拟互补阔题： ( i u “。一，2 ) s 0 ，u “u 4 。正+ 七，( 掣u 卅。一f ) ( u 辨一u 。以一k ) 蕊0 下蘸，我们绘爨算法3 1 豹肇谣牧敛牲定理。 定理3 2 假设 疗” 由算法3 1 产生，则迭代解序判 疗” 单调递增收敛于问题( 3 2 ) 的解c ，。 诞明：毙证单调性， 溺数学弱续法诞拶“疗一，鼯矮谖痧“。，疗“。，m 一毛2 ， f 一1 ，2 ，尉。 首先证当m = l 时，疗1 麓o ，即须诞疗1 。= 疗“，i 一1 2 ，m ，出算法3 1 步1 翔： 疗。一0 ，郎疗蛳= o ，i ；1 , 2 ，m 下蘧，我们用数学归纳法诞疗1 一= 移“，f = l 2 ，m ，当i = l 时，须证移1 3 = 疗o 。= o 。 不妨墩下拣集合矗= j n ：疗y = 盘+ 疗y ，警，了；时， 1 0 疗尹。膏+ 疗? 州；七，o * 疗尹 ( 3 5 ) 当j e n j f i 。5 ，疗尹惫霹捌，由互补性质知，( 叠疗尹一f 1 ) j 妫，即脚y f 1 k m o ， 则有1 v l v 。舀+ 叠，u 疗z 一礤“，出( 2 1 ) ，( 3 5 ) 与m 阵豹链袋知 疗，o 。d v m 0 1 ( 3 6 ) 出( 3 5 ) 与( 3 6 ) 雯硅 驴1 j 急疗鲇。0 ，i = 1 , 2 ，m ( 3 7 ) 当i 。2 时，须迸疗埔移。一一0 。不妨取下栎集合j ：= i e n ：疗 2 = 女+ 疗y ， 当，誊歹：时，疗；2 * 膏+ 疗尹，凌( 3 7 ) 我霹j 得到香；2 豇，o 一痧；2 ；鄄当，歹2 时， 曙竣 ( 3 8 ) 当j n j 。时，疗尹t 七+ 彩y ，由互补性旗知，( 脚；2 - f 2 ) = o ，划当j n j ：时 有( 缈；一f 2 w ：。o ，邦_ 气v ：搿峨疗品：+ 珞啦也j 。1 , ；2 - - 群2 v ：， 由( 2 1 ) ，( 3 8 ) 与m 蓐的憔蕨翔，警j 芒n j ：眩， 疗1 m , 2毒o 尝口0 , 2 v ， ( 3 9 ) 囊( 3 8 ) 与( 3 9 ) 知 疗1 0 惫y o , 2 ( 3 + 1 0 ) 下谣诞明i * 3 , 4 ，m 时也有移1 。移o 成立， 假设当i k 对，有 黟聃惫移蚶。0 ( 3 1 1 ) 当i ；| i + 1 时，要谨痧站“乏疗。4 “一0 ，取，m 一 j 芒：毋芦“一豇+ 疗 ， 当，毯j 。时，由假设有 疗y 一霉+ 疗芦o ( 3 。1 2 ) 当j g n j 。融，谚州一c 蠢+ 移芦，由互於往震翔，( 叠“疗y “- f “1 j ) w 魄。一o ， 蟛k + v l 。v 。疗磁。十塌k + v l 。抵哦1m f “，垤。，由( 2 1 ) ，( 3 1 2 ) 与m 阵的性质知 。( j 慨l , k + l 。套o = 疗品戡； ( 3 1 3 ) 由( 3 。1 2 ) 与( 3 1 3 ) 知有 疗“= 杉”，l = 3 ，4 ，。，m ( 3 1 4 ) 成立，最蜃由( 3 7 ) ，( 3 1 0 ) ，( 3 1 4 ) 知痧1 黟。成立，鼹疗驴“，i 。1 ，2 ，m 成立。 蒜诞警m ；2 时，疗2 驴，嚣须诞疗2 疗“，f 一毛2 ，m 假设当f = k 时，鸯 t 7 2 , 。未驴1 0 ( 3 1 5 ) 当i 。后+ l 辩，由算法3 。1 步2 易知，移2 “鬈痧2 。十素，驴1 。“g 巧城+ 七， 由( 3 1 5 ) 及弓l 瑷2 2 雄鲡 疗2 # + 1 疗城“( 3 1 6 ) h a m i l t o n j a c o b i b e l l m a n 方程的数值解 由( 3 1 5 ) 与( 3 1 6 ) 可知疗2 j 未疗“，i 一1 ，2 ，m 即有疗2 芑疗1 。 下面用数学归纳法证明当m ，2 时，疗“= 疗”1 ，即”。疗”“，m - 3 , 4 ，h i 一1 , 2 ，m 。当m = k ，假设有 疗蛳疗“j 成立，另当n l = k + l 时，须涯疗“1 j 疗“，当i = l 时，由算法 疗js 驴“冉+ 】j 篇k + 疗，疗j s 疗冉+ 七；k + 疗，丽由( 3 1 7 ) 疗“1 j 疗。3 ( 3 1 7 ) 3 1 步2 知， 与弓l 理2 ，2 可知 当i = 2 时，由算法3 1 步2 易知驴“，2 式疗“3 + j j ，且疗 2s 扩3 + | j ，则由 知驴“，2 疗 ；同理可证 ( 3 1 8 ) ( 3 1 8 ) 疗“o 疗“，f ，3 ，4 ，m ， ( 3 1 9 ) 那么由，的结果知u 。“疗一，掰一毛2 ，n 。即有疗”。，疗”“， m = l 2 ，n ，i 一1 , 2 ，m 有界性， 设疗5 满足r 痧5 一f ，0 ，z 疗一f 墨0 ，谣式相减则得到0 够5 一疗州) 0 ，而 影为m 阵，敖疗“。s ，即彬”) 有上赛厅5 ，m - 1 , 2 ，m 。丽矽椰 是孳调有赛， 故必存极限疗8 存在，郄l i m d 4 j = 疗8 。下甄我们证明疗8 是问题( 3 。2 ) 的解，由 定理3 2 的已知条件及算法3 1 步2 如下式成立， 掣疗一f s o , d 4 ，s | i + 疗4 4 ，( f 移一f ，疗“一k 一疗“。1 ) = 0 ( 3 2 0 ) 在( 3 2 0 ) 中取极限得0 疗8 一f s 0 ，痧8 墨七+ 疗“1 ，( 0 疗4 一f ，疗“一k 一疗4 “) 。0 ， 即知疗8 楚( 3 2 ) 的解，放存疗。= u 。 由一可知，由算法3 1 产生的迭代解序列缈“ 苇调递增收敛于润题( 3 2 ) 的解。 注：同理，我们可以证明算法3 2 的解序列单调递减收敛于闯题( 3 2 ) 的解u 。 3 2h a m i l t o n j a c o b i b e l l m a n 方程的、g a u s s s e i d e l 型区域分解算法及 其收敛性 在这一节，我们分绥h j b 方程的g a u s s s e i d e l 型区域分解算法，我们给如 了其在一定假设条停下该算法的单调收敛性证明。与2 2 一样，分解n = 姨u n 2 。 算法3 3 ： 步1 ：取u o = 0 ，迭代终止准则 0 ，m ：= 1 ； 步2 ：对i 一1 , 2 ，+ ，m ，j * 1 , 2 ，并行求解下列问题： u ”7 j 甲，( r u “一，2 ，v 一厂”。) 急0 ，v v 掣。， 其中 掣一p 彤- l ：s c ? “，当s = ，；u k + u j _ 1 ，当s f 步3 ：u ”= m a x u ”j ，u “2 i = l 2 ，m e 步4 ：如采l 疗1 一疗4 k s ，剡停算；否剡m ：= m + 1 ， 转步2 。 算法3 4 步1 ：取裙德u o ，使得l u o f m 0 ，迭代终止准则s 0 ，l l l ：= l ； 步2 ：对i ；l 2 ，m ，j 一1 ，2 ，并行求勰下硼阍题： u “秽o ，篮，峨j 一，v u 州7 ) 2 0 ，v v e 群。 其中芹。一 v e r “：k = u 7 “，当s m ；v ss 惫+ u 7 。tl 当s j 步3 ：u “。一m i n u m , , 1u 柳。 ， i = l 2 埘。 步4 ：如槊h ，”1 一u “艮s ，则停算；否则m ：= m 串l ，转步2 。 下睡，我们给蹴了g a u s s s e i d e l 黧嚣域分鳃算法3 3 的单调收敛性涯爨定理。 霆理3 。3 假设叠为m 降及c a 由算法3 3 产生，受i 迭代解序捌 扩 罄调递增收敛予 阏题( 3 2 ) 的解u 。 诞明；我们先证其单调性， 先证疹t 疗o ：首先证痧辩痧o ，蠢箨法3 3 步1 知扩* 0 ，邸疗。一o ，i = 毛2 ，m 。 设啊，t m ：拶。1 鼬- 乐+ 疗 ，当s m 。时， 谚3 3 一j 十霹。o = 瓯o ( 3 。2 1 ) 姿s e n 姨辩，由算法3 3 步2 知 玩琊= 瓯邮= o = v s o ( 3 2 2 ) 当s l 虬时，识啦，1 墨七+ 疗；o 。意+ 以3 一七，出互补性质知( 舾- f 2 ) ，w o ， 雯一方瑶，( 1 2 0 0 f xs o ，两式榻减褥g ( t 3 m - t 7 0 ) ) ，邕o ， 刚当s 专l m ，眵够靼4 一痧o ) ) l 碣，o ，繇有 0 m 慨； 。( 疗1 雒一疗。) i 巩；+ 三i 雌。峨( 疗1 如一疗。) w l + m m ，c a l i , 1 - - 。) 麓0 ， 由( 3 2 2 ) 知( 疗1 舶一疗。k 喊；o ，则t m 啦，w t ( 疗1 雌一痧。) 嵋。0 ， 由( 3 2 1 ) 翔影1 雒一疗。) 娥，毒o ，两0 川嘲；幽，o ，掰以0 l 磷，鼻；，( 疗1 , 1 , 1 疗。) m ，o ，敬鸯 ”l i 慨。c a l ”一驴。) l ，o ，因】，娜域，为m 阵，所以 够1 3 3 - t j o ) l 弧。o ( 3 2 3 ) 南( 3 。2 1 ) ，( 3 ，2 2 ) ，