（计算数学专业论文）方程近似解的计算复杂性.pdf

a b s t r a c t t h ep r o b l e mo no p t i m i z a t i o no fa p p r o x i m a t es o l u t i o no fo p e r a t o re q u a t i o n si sm a i n l yt o d e t e r m i n et h ee x a c to r d e r so fe r r o ra n dc o m p l e x i t yo fa l g o r i t h m s ，a n dc o n s t r u c tt h eo p t i m a l a l g o r i t h mr e a l i z i n gt h eo r d e r s c o m p l e x i t yo fo p e r a t i o n si sa l s oc a l l e dt h ec o s to fo p e r a t i o n t h e r e f o r e ，t h ep r o b l e mo f t h ee c o m p l e x i t yo fa p p r o x i m a t es o l u t i o no fo p e r a t o re q u a t i o n s ，r o u g h i n gs p e a k i n g ，i st h e m i n i m a lc o s ta m o n ga l la l g o r i t h m sw h i c hs o l v et h ep r o b l e mw i t he r r o ra tm o s t ，a n di t h a sw i d e l yp r a c t i c a lb a c k g r o u n d s g e n e r a l l ys p e a k i n g ，t h eo p t i m i z a t i o no fap r o b l e mc a n b ed o n ei nv a r i o u ss e t t i n g ，s u c ha sw o r s te a s es e t t i n g ，a v e r a g ec a s es e t t i n g ，p r o b a b i l i t yc a s e s e t t i n g ，t h ew o r s te a s es e t t i n gi s i nc o m m o nu s e ，b u tt h eo t h e r sa r ea l s oo fi n t e r e s t ，t o n o w ，a sf a ra st h eo p t i m i z a t i o no fa p p r o x i m a t es o l u t i o no fo p e r a t o re q u a t i o n si sc o n c e r n e d ， m a n y w o r k sh a v eb e e nd o n ei nt h ew o r s tc a s es e t t i n g i nt h ea v e r a g ec a s es e t t i n g ，h o w e v e r ， t h er e s u l ta b o u tt h i sp r o b l e mh a sh a r d l ye v e rb e e ns e e n i ti sw o r t hp o i n t i n go u tt h a ti fw ed e t e r m i n et h eo p t i m a lo r d e ro fa p p r o x i m a t es o l u t i o n o ns o m ec l a s s e so fe q u a t i o n s ，t h e nw em a yr o u g h l yj u d g et h a ta na l g o r i t h mi s g o o do r b a db yc o m p a r i n gt h eo p t i m a lo r d e rw i t ht h ee r r o ro ft h ea l g o r i t h mi no r d e rt oc h o o s et h e e f f e c t i v em e t h o df o ra p p r o x i m a t es o l v i n ge q u a t i o n s o nt h eo t h e rh a n d ，f r o mt h er e s u l t so f o p t i m i z a t i o n i th a sb e e nf o u n dt h a ts o m en u m e r i c a lm e t h o d s u s e dt os o l v ei n t e g r a le q u a t i o n s a r en o to p t i m a li ns e n s eo fa c c u r a c y ( e v e nw i t hr e s p e c tt oo r d e r ) t h er e p o r ti s m a i n l yd e v o t e dt ot h ep r o b l e m so no p t i m i z a t i o no fd i r e c t m e t h o d sf o r a p p r o x i m a t es o l u t i o na n di n f o r m a t i o nc o m p l e x i t yo fs o m ec l a s s e so fo p e r a t o re q u a t i o n s i t i so r g a n i z e di n t ot h r e ec h a p t e r s i nc h a p t e r1w eh a v ec o n s i d e r e dt h ep r o b l e mo fo p t i m i z a t i o no fa p p r o x i m a t es o l u t i o no f i n t e g r a le q u a t i o n so f s e v e r a lv a r i a b l e si nw o r s tc a s e w ed e t e r m i n et h ee x a c te r r o ro r d e ra n d c o n s t r u c tt h eo p t i m a le r r o ra l g o r i t h m i nc h a p t e r2t h ep r o b l e mo f 一c o m p l e x i t yo fi n t e g r a le q u a t i o n sh a v eb e e nc o n s i d e r e d i nw o r s tc a s e w ed e t e r m i n et h ee x a c to r d e ro ft h ec o m p l e x i t ya n dc o n s t r u c tt h eo p t i m a l a l g o r i t h mr e a l i z i n gt h eo r d e r i nc h a p t e r3w eh a v ec o n s i d e r e dt h e p r o b l e m o ft h eo p t i m i z a t i o no fa p p r o x i m a t es o l u t i o n o fo p e r a t o re q u a t i o n si nt h ea v e r a g ec a s ea n di t sa p p l i c a t i o n t os o l v ea b o v em e n t i o n e dp r o b l e m sw eh a v eu s e dt h ec l a s s i c a lm e t h o d sa n ds k i l l si n a p p r o x i m a t et h e o r y ，e s p e c i a l l yt h ep r o f o u n dr e s u l t so nw i d t ha n da p p r o x i m a t eb yf o u r i e r s u m m o r e o v e r ，s o m en e wi d e a sa n ds k i l l si nm o d e r na p p r o x i m a t et h e o r yh a v ea l s op l a y e d v e r yi m p o r t a n tr o l e s ，g e n e r a l l ys p e a k i n g ，t os y n t h e s i z et r a d i t i o n a lm e t h o d sa n dm o d e r n m a t h e m a t i c a li d e aa n dm e t h o d si nf u n c t i o n a la n a l y s i s ，l i n e a ra l g e b r a ，p r o b a b i l i s t i c t h e o r y m a yp r o v i d en e wm e a n st os o l v et h ep r o b l e mo fc o m p u t a t i o n a lc o m p l e x i t yo fc o n t i n u o u s p r o b l e m 刖置 方程近似解的优化和计算复杂性问题主要研究算子方程，特别是在数学物理中占重要地 位的积分方程的近似算法在某些度量( 如一致度量、平均和概率度量等) 下的优化问题及计 算复杂性。其中，优化问题主要研究某些近似方法在某类方程上所能保证的最优误差阶；计 算复杂性问题则解决的是在用最少的计算资源( 如计算机时、内存等) 的前提下解决问题的 内在的困难性。 算子方程近似解的直接方法起源于r i t z 、b u b n o v 及g a l e r k i n 的经典丁作。在直接方 法理论的发展中，k r y l o v 、k r a v c h u k 、k e l d i s h 、p e t r o v 、k a n t o r o v i c h 等著名学者做出了突出 的贡献。其中特别指出要给出刻划直接方法的统一的定义是很困难的，只知道一些刻划直接 方法特征的论述。如s o b o l e v 把求解方程的近似解归结为解一个有限维的线性代数方程组的 方法称为直接方法。这一方法的核心在于将问题离散化，用有限维空间中的线性代数方程 组来代替原方程这是在计算机上实现算法所必须的。要做到这一点，必须将求解的空间和 映像所在的空间离散化，并构造出原方程的近似模拟。离散化和构造的方式不同，就得到 各种不同的直接方法。所谓算子方程直接方法的优化就是确定它( 在某类方程上) 所能保 证的最优误差阶。在此问题上的结果先是d z y a d y k 得到。他考虑了第二类f r e d h o l m 积分方 程非自适直接方法的优化。此后，g a b d u l k h a e v 研究了带扰动的第二类f r e d h o l m 积分方程 非白适直接方法的优化。对于一般算子方程非自适直接方法的优化是由g a b d u l k h a e v 和 v e l e v 完成的。至此，算子方程非自适直接方法的优化的研究己臻于完善，许多一般性的问 题都己得到彻底的解决。然而应当注意的是上述优化无法充分利用具体方程的信息( 例如， 在积分方程的情形下，可能就忽略了核与自由项的某些性质，特别是光滑性) ，这无疑降低 了此类方法优化的意义；另一方面，也很浪费计算资源。为克服这一缺陷，提出了自适的直 接方法( t h ea d a p t i v ed i r e c tm e t h o d s ) 的优化。此中情形下，可根据前一计算结果的需要决定 是否需要计算下一个数据，从而有可能减少计算量，节省计算资源。在这方面的第一个结果 是p e r e v e r z e v 在1 9 8 2 年得到的，他考虑了核及自由项属于s o b o l e v 类的第二类f r e d h o l m 积分方程白适赢接方法的优化，得到在阶的意义f 的精确结果。但是，他仅在空间厶和c 中讨论，并且自由项是一元函数。此后在一些学者的努力下，这一问题有了很大进展， 主要表现在以下三个主要的方面： 1 在l 。空间中考虑第二类积分方程。在这方面首先是p e r e v e r z e v 在1 9 8 7 年研究了具有可 微核与自由项的第二类f r e d h o l m 积分方程自适直接方法的优化，把他本人1 9 8 2 年在 空间l 2 和c 中的工作推厂到赋范空间l 。( ，s p s ) 中，这里方程中的自由项仍是 一元幽数。1 9 9 0 年，p e r e v e r z e v 在空间l ，中考虑了自由项是二元函数的情形，从而把 他1 9 8 2 年的工作推广到了二维空间中( 就自由项而言) 。1 9 9 6 年，房艮孙在空间l 。( ， p ) 中得到核属于混合偏导数优控的函数类的第二类f r e d h o l m 积分方程自适直接方 法的优化 张新平得到该问题的极限情形( 即p = c o ) 下的解。此外，他还得到核属 于差分类的第二类f r e d h o l m 积分方程自适直接方法的优化的结果。以上工作中所考虑 的积分方程中积分算子的核都是可微核，而且核均具有限光滑性，为突破这一限制， u r u m b a e v 考虑了无限可微核的情形，得到了相应的结果。 2 在一般h i l b e r t 空间中考虑第二类算子方程。 在这方面有s o l o d k y 和p e r e v e r z e v 等人 的【：作，他们分别研究了h i l b e r t 空间中算子方程和v o l t e r r a 方程逼近解直接方法的优 化。 3 在上。中考虑弱奇异积分方程直接方法的优化。这里主要有p e r e v e r z e v 和s o l o d k y 1 9 9 3 年的工作以及u r u m b a e v l 9 9 4 年的工作。他们分别考虑了核为_ h 卜( t 一- r f r ) ( 。 口 是出现在g a u s s i a i l 测度中的常数。通过 研究，我们的上述猜测也得到了证实，具体见第三章。 agw e r s c h u l z a v e r a g ec a s ec o m p l e x i t yo f e l l i p t i cp a r t i a ld i f f e r e n t i a le q u a t i o n s ，jc o m p l e x i t y ，1 9 8 9 ，9 3 0 6 - - 3 3 0 c h a p t e r 1 o p t i m i z a t i o no fa p p r o x i m a t e s o l u t i o no f i n t e g r a le q u a t i o n s o f se v e r a l 场r i a b l e s 1 1i n t r o d u c t i o n l e t ( x ，| | - | i ) b eal i n e a ru o r m e ds p a c e ，as u b s e to fxi a n d “as e to fc o n t i n u o u sl i n e a ro p e r a t o r sh a c t i n g f r o m x 卜x a n ds u c h t h a t z = h z + f ( 1 1 ) i su n i q u e l ys o l v a b l ef o ra n yh w ，t h ec l a s so fs u c h e q u a t i o n sw i l lb ed e n o t e db yf ，习 f o l l o w i n gt h er e f 【1 】，a 8d i r e c tm e t h o d sf o rs o l v i n g ( 11 ) w es h a l lc o n s i d e rm e t h o d sf o rw h i c hf i n d i n g a na p p r o x i m a t es o l u t i o no f ( 1 1 ) r e d u c e st os o l v i n gaf i n i t es y s t e mo fl i n e a ra l g e b r a i ce q u a t i o n s i no t h e r w o r d s ，o n ed i r e c tm e t h o do ra n o t h e ro fs o l v i n g ( 1 1 ) i sar u l ea ，a c c o r d i n gt ow h i c h ，w i t ha no p e r a t o r h 7 t h e r ei sa s s o c i a t e das u b s p a c e 晶cxo fd i m e n s i o nm ，a n da no p e r a t o rh , nf r o mx i n t of ms u c h t h a tt h ee q u a t i o n z a = h m z a + j ( 1 2 ) i s u n i q u e l ys o l v a b l ea n d “i st a k e na st h ea p p r o x i m a t es o l u t i o no fe q u a t i o n ( 1 1 ) f o rf i x e dm ，t h es e to f a l ld i r e c tm e t h o d saw i l lb ed e n o t e d b ya m ，a n da f = w i l ld e n o t et h ec o l l e c t i o no fd i r e c tm e t h o d sa a m ， f o rw h i c h ，w i t h 剐io p e r a t o r 抒爿o n ea s s o c i a t e so n ea n dt h es a m ef i x e ds u b s p a c ef mcx t h e q u a n t i t y e ( m ，月，a )s u pi i z z a m ，1 ( 1 3 ) i st h ee r r o ro ft h em e t h o dao i lt h ec l a s s 丸，】，w h e r ega n dz aa r es o l u t i o no fe q s ( 11 ) a n d ( 1 2 ) ， r e s p e c t i v e l y , a n dt h el e a s tu p p e rb o u n di st a k e no v e ra l le q u a t i o n so fc l a s s 畔，月w i t h i nt h ef r a m e w o r ko f ag e n e r a la p p r o a c ht ot h e o p t i m i z a t i o no fa p p r o x i m a t em e t h o d s ( s e er e f 2 】2o rr e f if 3 ，p a g e6 0 ) ) ，i ti sm o r e n a t u r a lt oo p t i m i z ed i r e c tm e t h o d si nt h es e n s eo ft h eq u a n t i t y 。m ( w ，- 习，x ) = a 醋，。e ( 畔，j ，4 ) ( 1 4 ) i ft h e r ee x i s t sad i r e c tm e t h o da + m ，s u c ht h a t e 。( 畔，月，x ) = e ( 7 ，月，a ) t h e na i sc a l l e daa l m o s to p t i m a ld i r e c tm e t h o d0 nt h es e to fe q u a t i o n s 畔，习，w h e r e 口( 竹) xb ( 付) d e n o t e s n m ) 6 ( n ) a n dh ( n ) n ( 礼) ，t h en o t a t i o n ( n ) h ( n ) m e a n st h a tt h e r ee x i s t sac o n s t a n tc os u c ht h a t 。( n ) c o b ( n ) t a k ep l a c ef o ra l lnb e g i n n i n gw i t hs o m e 竹o t h er e s u l t sw h i c hh a v eb e e nf o u n dr e c e n t l yi nt h ei n v e s t i g a t i o no fe x t r e m ep r o b l e m so ft h et h e o r yo f a p p r o x i m a t i o nm a k e i tp o s s i b l et of i n dm o r ee f f e c t i v ea p p r o a c h e st ot h eo p t i m i z a t i o no fn u m e r i c a lm e t h o d s b u ti nt h ei n i t i a ls t a g eo ft h ew o r kt h eo p t i m i z a t i o no fd i r e c tm e t h o d so fs o l u t i o no f ( 11 ) i si nt h es e n s eo f t h eq u a n t i t y ( s e er e f 4 1 ) a m ( 【州，习，x ) 3 之限 i 览。8 ( w ，月，a ) ( 15 ) w en o t eh o w e v e rt h a to p t i m i z a t i o ni nt h es e n s eo ft h eq u a n t i t y ( 1 , 5 ) i se f f e c t e do nac o m p a r a t i v e l ys m a l l s e to fd i r e c tm e t h o d s f o rw h i c ht h er u l eaa s s o c i a t e sw i t he a c ho p e r a t o rh 7 to n ea n dt h es a m es u b s p a c e ，i en o n a d a p t i v ed i r e c tm e t h o d ，a n do n l ya f t e r w a r d si s t h i ss u b s p a c ec h o s e ni nt h eb e s tw a yf o rt h e e n t i r ec l a s s 瞰，月g e n e r a l l ys p e a k i n g ，t h i sa p p r o a c hd o e sn o tp e r m i to n et ou s ec o m p l e t e l yt h ei n f o r m a t i o n a b o u tt h ep r o p e r t i e so ft h ec o n c r e t ee q u a t i o n ( 11 ) ，f o re x a m p l e ，a b o u tt h ed i f f e r e n t i a b i l i t yo ft h ek e r n e la n d o ft h ef r e et e r mo ft h ei n t e g r a le q u a t i o ni na d d i t i o n f o rs l l f f i c i e n t l yl a r g ec l a s s e so fi n t e g r a le q u a t i o n si nt h e s e to fd i r e c tm e t h o d si nw h i c ho p t i m i z a t i o ni se f f e c t e di nt h es e n s eo f ( 1 5 ) ，a nn u m b e ro ff a m i l i a rm e t h o d s d on o ta p p e a r ，i np a r t i c u l a rt h em e t h o do fm e c h a n i c a lq u a d r a t u r e ( s e er e f 1 4 ) b u ti ft h eo p t i m i z a t i o ni s i nt h es e n s eo f ( 1 4 ) ，t h e na l lt h ed e f e c t sa b o v e - m e n t i o n e dw i l lb eo v e r c o m e t h e r e f o r e ，t oo p t i m i z ed i r e c t m e t h o d si nt h es e n s eo f ( 1 4 ) i sn a t u r ea n dr e a s o n a b l e t h ef i s tr e s u l to nd i r e c tm e t h o d sw a so b t a i n e db yp e r e v e r z e v 3 1 a f t e r w a r d s ，h eh a sas e r i e so fw o r k so n t h ep r o b l e m ( s e er c f 【4 1 ) f a n gg e n s u na n dm a 【6 jh a v es t u d i e dt h ep r o b l e mo fo p t i m i z a t i o no fa d a p t i v e d i r e c tm e t h o d sf o ra p p r o x i m a t es o l u t i o no fs o m ei n t e g r a le q u a t i o n sw i t hs m o o t hk e r n e l sa n df r e et e r m s b e l o n g i n gt ob e s o vc l a s s e s i nt h ep r e s e n tp a p e rw e c o n s i d e rt h ep r o b l e m0 na n i s o t r o p i cs o b o l e vc l a s s e s ，i t i sn o t et h a tt h ea n i s o t r o p i cs o b o l e vc l a s s e sa r eo n eo fi m p o r t a n tf u n c t i o nc l a s s e si na n a l y s i s ，a n dt h e ya r e d i f i e r e n tf r o mt h eb e s o vf u n c t i o nc l a s s e s 0 u rm a i nr e s u l ti st h ef o l i o w i n gt h e o r e m t h e o r e m1 1 1f o r1 p o 。，t h ea s y m p t o t i c o r m u l a 0 m ( 雪，l p ) m 一却( r ) i sr i g h t ，；e ，t h eo r d e ri sa l m o s to p t i m a l ，a n dt h eo r d e ri sr e a l i z e db yt h ed i r e c tm e t h o da + ( s e es e c t i o nj 纠 1 2p r e l i m i n a r i e s l e tr 4d e n o t ed d i m e n s i o n a le u c l i d e a ns p a c ew i t hl e b e s g u em e a s u r e 7 r d = 【一丌，竹】4 ，( 砷，x = ( z 1 ，t , d ) r 4 ，b eam e a s u r a b l e ，a l m o s te v e r y w h e r ef i n i t e ，f u n c t i o nw h i c hi s2 7 r p e r i o d i ci ne a c hv a r i a b l e w es h a l i w r i t e f6l f f o r l5 p o 。i f i l y l l p = ( ( 2 ”) “i f ( x ) l ，d x ) o o ， j f “ w h e r et h ei n t e g r a li sc o n s i d e r e da sal e b e s g u e i n t e g r a l 2 i nt h ec a s ep5 。i tw l l ib ec o n v e n l e n tf o ru st oa s s u i n et h a tt h es p a c el i s t h e8 p 8 。80 f 。“t i “o “8 f u a c t i o n sa n d l f ，。= s u p i ，【x ) i 0 0 x c o n s i d e rt h es o b 。l e vc i n s s 吁，1 兰p 。o ，r = ( r h ，) ，r ，n ，j = 1 2 ，d t w h i c h 。0 n s i 5 。80 f f u n c t i o n s ，( x ) h a v i n gt h ef o l l o w i n gi n t e g r a lr e p r e s e n t a t i o n f o re 酊h1sj 曼d f ，z ”h ，。d ) f r j ( x j 一) n l ：= 9 l p g ( x ) d z j = o ，j 21 ，2 ，d ) 辱，( ) ：2 o o c o s i 域一r 争j z r l e tu sa g r e e t h a t w ? = k f o r f w ：，l e t 忖忻= 扣嚣，( x ) i tc a nb ep r o v e d t h a t 吁i san o r mo n w 7 i tw i l lb ec o n v e n i e n tf o ru st ou s et h ef o l l o w i n gn o t a t i o n s l e t t ( b ) = 。k e i ( k ，砷：e k c ) ， k e x ( b ) d b = ( 6 l ，吣6 d ) n 。，( x ，y ) = 三x j y j ，= l d h ( x ) ：d 仇，( 。，) ，b ( 柚：矗王，。，( q ) ，9 ( r ) = ( 量r i l ) ，e = ( 譬 d b ( x ) = 尽仇，( ) ，( 柚= 旦王，鹏) ，夕( r ) = 暑7 ，1 卜e = 【普 。 2 e n = ( 2 e 一，2 e t “) ，(