（计算数学专业论文）一种拟grünwald插值算子的误差分析.pdf

一种拟g r i i n w a l d 插值算子的误差分析 摘要 信息基复杂性理论是一门非常年轻的计算科学理论。在其出现后的短短几十年 里，它的实用价值很快就得到了广泛重视这一理论的结粜对计算机算法的应用和 发展起到了巨大的指导性作用利用连续函数的有限信息对连续函数的避近研究是 信息基复杂性理论的一项重要内容丽对于逼近算法的选挣，在以函数值计算为可 允许信息泛函的前提下，插值莽子无疑是一种重要的信息基逼近莽子本文一方面 确定了以第二类c h e f h e y 多项式的零点为插值节点组的一种拟g r i i n w a l d 插值算 子列在加权k 意义下收敛速度的一种估计( 在阶的意义下是精确的) ；另一方面了 确定了该算子在w i e n c r 空间中平均误差的弱渐近阶本文按内容分为四章 本文第一章为绪论 本文第二章给出了以第二类c h d v s h e v 多项式的零点为插值节点组的一种拟 g r f i n w a l d 插值算子列在加权k 范数下收敛速度的个估计，并说明其在弱渐近阶 的意义下是精确的 本文第三章证明了在如范数逼近的意义下基于第二类c h c b y s h c v 多项式零点 的g r n w a l d 插值算子列在w i e n e r 空间下的平均误差是不收敛于o 的 本文第四章给出了于厶逼近的意义下一种拟g r i i m v a l d 插值算子列在w i e n e r 空同上的平均误差的弱浙近阶通过本章的结论可以得出，基于第二类c h e b y s h e v 多项式零点的拟g r n w e l d 插值多项式列的平均误差能被最佳逼近多项式列逼近的 平均误差所控制，并且作为形式简单且恢复函数为多项式的一种信息基算法，其在 w i c n e r 空间上的平均误差列弱等价于以函数值计算为可允许信息算子的最小平均 信息半径列因此说明了在统计学的意义下，插值多项式算予一方面是实现最佳逼 近多项式计算的理想算法，另一方面是实现最优信息基算法的理想计算工具，且具 有性质优良的恢复函数 关键词信息基复杂性；c h e b y s h e v 多项式；g r f i n w a l d 插值算子；拟g r n n w a l d 插值算子 加权岛范敦；加权b 收敛；w i e n e r 空间；平均误差 t h ee r r o ra n a l y s i so fak i n do fq u a s i - g r i n w a l d i n t e r p o l a t i o no p e r a t o r a b s t r a c t h l f o r m a t i o n - b e s c dc o m p l e ：d t yba 邺m m n gt h e o r yo fc o m p u t e rs c i e n c ew i t h r c s u l t st h a th a v ea m a z i n gi n t p l i c a t i o n sf o rt h ed c v e l o p m o n ta n di i 鼬o fa l g o r i t h m s i t sp r a c t i c a lv a l u ei sw i d e l ya c c e p t c x la f t e ri ta p p e n r e , d t l l cs t u d yo fa p p r c o d m a - t i o nf o rc o n t i n u o t mf u n c t i o n st r u i n gf i n i t ei n f o r m a t i o nf o r m so n eo ft h ec o n t e n t so f i n f o n m l t i o n - b a s e dc o m p l e x i t yt h e o r y c o n s i d e r i n gt h ep e r m i s s i b l ei n f o r m a t i o nf u n c - t i o n a l sa f r of u n c t i o ne v a l u a t i o n s , i n t e r p o l a t i o ni sa ni m p o r t a n ti n f o r m a t i o n - b a s e da p - p r o x i n m t i o no p e r a t o rf o rt h ec h o i c eo fa p p r o x i m a t i o na l g o r i t h m s i nt h i sp a p e r 骶 f i r s ts h o wa ne s t i m a t i o no ft h er a t eo fw c i g h t c dl pc o n v e r g e n c eo fak i n do fq u a s i - g r f i n w a l di n t e r p o l a t i o no p e r a t o rb a s e do nt h ez e r o o ft h ec h e b y 吐e vp o l y n o m i a l o ft h es c c o n dk i n d ( t h er a t ei se x a c ti nt h es e n s eo fo r d e r ) t h e n 耽o b t a i naw e a k a s y m p t o t i co r d e ro ft h ea v e r a g ec l t o ro ft h i so p e r a t o ri nt h ew i e n e rs p a g 。o u r p a p e rkd i v i d e di n t of o u rc h a p t c r t h cf i r s tc h a p t e ri si n t r o d u c t i o n i nt h es e c o n dc h a p t e r 。髋z i v ea ne s t i m a t i o no ft h er a t eo fw e i g h t e dl pc o n v 口- g e n c co fq u a s i - g r f m w a l di n t e r p o l a t i o no p e r a t o r , w h i c hi sb a s e do nt h e7 宅r 0 6o ft h e c h e b y s h c vp o l y n o m i a lo ft h es e c o n dk i n d ，a n dt h ec o n v e r g e n c er a t ei ss h o w nt ob e e x a c ti nt h e8 c n s co fw e a ka s y m p t o t i co r d e r i nt h et h i r dc h a p t e rw cs h o wt h ea v e r a g ec l t o ro ft h es c q l 】c n o fg r i m w a l d i n t e r p o l a t i o no p e r a t o r s ，w h i c ha mb a s e do i lt h ez e r o so ft h ec h e b 嘞e ，p o l y n o m i a l o ft h es e c o n dk i n d i 8n o tc o n v e r g e n tt oz e r oi nl z a p p r o x i m a t i o ni nt h ew i e n e r s p a c e i nt h el a s tc h a p t e rw co b t a i naw e a ka s y m p t o t i co r d e ro ft h ea v e r a g ee r r o r o fq u a s i - g r i i n w a l di n t e r p o l a t i o no p e r a t o ri nl f a p p r o o c i m a t i o ni nt h ew i e n e rs p a c e a c c o r d i n gt ot h er e s u l t s ，w ec a nc o n c l u d et h a tt h ea 琳a 学ee r r o ro fq u a s i - g r i i n w a l d i n t e r p o l a t i o np o l y n o m i a l w h i c hj 8b a s e do nt h ez c r o ft h ec h e b y s h e vp o l y n o m i a l o ft h es e c o n dk i n d ，i sb o u n d e db yt h ea v e r a g ee r r o ro ft h eb e s ta p p r o x i m a t i o np o l y - n o m i a l m o r e o v e r ，a 8a l li n f o r m a t i o n b a s e dm g o f i t h m ，q u a s i - g r g n w a l di n t e r p o l a t i o n i sap o l y n o m i a lo fs i m p l ef o r m u l a t i o na n di t sa v e r a g ee r r o ri nt h ew i e n e rs p a c ei s w e a k l ye q u i v a l e n tt ot h em i n i m a la v e r a g er a d i u so fi n f o r m a t i o n ，f o rw h i c ht h ep e r - m i s s i b l ei n f o r m a t i o no p e r a t o r sa r ef u n c t i o nc v a l u a t i o n s h e n c ei ti n d i c a t e st h a ti n t h es e n s eo fs t a t i s t i c s ，i n t e r p o l a t i o no p e r a t o r so no n eh a n da r ei d e a la l g o r i t h m sf o r t h ec o m p u t a t i o no fb e s ta p p r o x i m a t i o np o l y n o m i a l s ；o nt h eo t h e rh a n d ，t h e ya r e 2 a l s oi d e a lc o m p u t a t i o n a lt o o l sf o ro p t i m a lj n l b n n a l i o m b a 8 e da l g o f t h 卫陷a n dp m s c g r e s t o r ef u n c t i o n sw i t h 霉dp r o p c r t i c s k e yw o r d s i n f o r m a t i o n - b a s c dc o m p l e x i t y ；g r f m w a l di n t c r p o l a t i o np o l y n o - m i a l ；q u a s i - g r 证n w a l di n t c r p o | a t i o np o l y n o m i a l ；w c i g h t o d “n o r m ；钳i g l l t 砌oo d l l - v c x g c n c c ；w i e n c rs p a c c ；a v c r a g ec r r o r 第一章绪论 在当今日新月异的科学技术发展中，数字计莽机的应用已经必不可少了然而。 计算机在运作时的资源是有限的任何个筇法在实理过程中部会占用计算资源。这 是解决每个问题时所固有的特点在如今资源有限的社会环境中。处理任何问题 都要讲究时效性以及资源的合理配设和有效使用于是，计算复杂性( c o m p u t a t i o n a l c o m p l e x i t y ) 理论应运而生我们常常会为解决个问题设计出各种不同的算法，当 计算机运行每个算法时，它的成本( c o s t ) 如运行的时间。占用的内存，以及费用 等是不愿相同的计筇复杂性正足衡量计算机处理算法问题时的内在必要成本，它 指的是所有能解决该问题的算法中所消耗的最小成本计算复杂性是计算科学中一 个重要的不变量，它与任何个特定的算法无关 计算复杂性理论中的一个核心概念是信息( i n f o r m a t i o n ) ，它是指我1 | 门对于铸 要解决的问题已掌握的内容在工程或科学研究中出现的大多数同题，其信息具有 三个方面的特征- 第一。信息不完全( p a r t i a i ) ，这是由于计算机能存储的数集有限 并且我们在实际中能够获得的信息也是有限的。比如，我们只能计算函数在有限个 点处的函数值；第二。信息本身不够精确( n o s y ) ，就函数值来说，这些值在获得或 者存储时很有可能产生误差( 例如敫字存绪时会被四舍五入) ；第三，信息是有偻的 ( p r i o o d ) ，获取问题元素的每个信息都是有成本的。例如，积分中被积函数值的计 算是需要时问的对具有上述特征的问题的复杂性研究形成了计算复杂性理论的一 个重要分支一一信息基复杂性( i n f o r m a t i o n - b a s c dc o m p l e x i t y ) j f t r a u b ，g w w a s i l k o w s k i 以及h w o s n i a l 的w s k i 在文献【1 1 1 中深入地论述了这理论它的实用 性是很广瑟的在我f n 生活中的许多领域都需要应甩信息基复杂性理论这些领域 包括经济、数值分析，物理，人工智能，科学工程计算地球物理学，决策理论控 制理论以及信号处理等 当然实际生活中还存在另类同题，这类问题的信息是完整的( c o m p l c t e ) ，精 确的( e x a c t ) 和无偿的( h 傥) 计算复杂性中处理这类同题的分支理论称为组合复杂 性( c o m b i n a t o r i a lc o m p l e x i t y ) 无论实际问题是属于哪种复杂性理论，我们所追求 的算法都必须是成本最小的 在信息基复杂性问题中，由于其信息不完全的特点。我们在解决同题时只能寻 求近似解因此，误差( e r r o r ) 的概念就变得尤为重要了在求近似解时，我们通常 要求算法的误差不超过e ，这样的e 被称作阀值算法的成本和误差可以有各种各 样的衡量标准，如最差情形( w o r s tc a s es c t t i n 曲，平均情形( a v e r a g ec a b es e t t i n g ) 以 及概率情形( p r o b a b i l i s t i cs e t t i n g ) 等本文所研究的同题属于平均情形下的信息基 复杂性的问题 一般地，在实际问题中关于目标函数的信息往往是有限个点的函数值，因此算 法的构造就只能依赖于这些函数值注意到插值算子是连续函数空闭上类非常有 1 用的逼近工具，更重要的是它们的算法表达式明显是仅依赖于有限个点的函数值， 并且其恢复函数是多项式，具有很好的运算性质和光滑性这点寻l 起了我| j 仃对擂 值算子逼近误差的研究兴趣多项式插值算子有很多种。对于不同的插值节点组。 相同的插值莽子的表达式及特性部相去甚远本文所选用的插值节点组是第二类 c h e b y s h c v 多项式的零点文献f 5 j 说明了在此节点下许多插值算子( 包括著名的 l a g r a n g e 插值和h e r m i t c - f c j r 插值) 的收敛性都很差。特别是在l 和1 两点附 近g r n w a l d 插值算子也不例外因此我们考虑文献【6 】给出的一种拟g r n 舳| d 插值算子本文共分为三个部分，第一部分得到了拟o r i n w a l d 插值莽子在加权上， 范数下收敛速度的个估计，并说明了其在弱渐近阶的意义下是精确的；第二部分 确定了基于第二类c h c b y s h c v 多项式零点的g r f i n w a l d 插值算子在w i c n c r 空问下 的平均误差的弱渐近阶，这个结果说明它不是最优的逼近工具；第三部分确定了拟 g r f i n w a l d 插值算子在w i c n c r 空间下的平均误差的弱渐近阶，此结果说明此算子在 一定意义下是最佳逼近工具现分别介绍如下： 1 1 一种拟g r f i n w a l d 插值算子的加权k 收敛速度 设( x ) 为( - i ，t l 上的连续函数。则以第二类c h c b y s h c v 多项式“( z ) ( ( o 口) = 窭雩；乒塑) 的全部零点 “= 。籍) ：。为插值节点组的，( z ) 的g r i i n w a l d 插 值多项式为 g 。( ，甸= f ( t 。) 瑾( z ) ， i r = - - i 其中。 l t ( x ) = 燕，n 文献用证明了g 一，在( - 1 ，1 ) 上处处收敛于，( z l 而且是内闭一致收敛 的文献【6 】证明了g 。( ，善) 在如意义下不是收敛算子列。并对g 。( ， 善) 进行了 修正。给出了一种拟g r i n w a l d 插值多项式 g ：( 功= ，( “) x ：( z ) ， 其中。t o = 1 ，l = 一1 ，且 姒加雩器一删= 等器 刈垆篙 ( 巩k - 1 , - - , n ， 文献f 8 】讨论了上述算子于岛范数及以了再1 为权的加权。范数下的收 2 协衅浅溢葛 而且1 占计的阶尾精确的，其中u 0 ( ， ) 为文献1 9 l 中定义的权为，( z ) = 撕r ：的 g 表示仅与p 有关的正常数 f q k ( ，嘉) + 峥】，p l ， 【i 瓯( ，砷一m 妒石与叫5s a h ( ， ) + 毕】，p ；t ， 【q h ( ，丢) + 毕】， o p g “ 陂( ，$ 卜m 妒( 一矿户叫。s g b ( ，两+ 堕丛争】，a = g t ， l g h ( ，矗) + 黔】， 出口 g 1 ， 而且估计的阶在a g 一1 时是精确的 1 2g r 证n w a l d 插值算子在w i e n e r 空间上的平均误差 设f 是个集合，g 是个范数为h n 的线性赋范空间，卢是定义在f 的 b o r e l 子集上的概率测度设s 是f 到g 的个可测映射，被称为解算子在实际 问题中，对每个，只s ( ，) 是我们要逼近的目标函数设是f 到j 矿的个 可测映射，圣是舻到g 的个可测映射，与垂分别被称为信息算子和算法当 1 p + o o 时，逼近o o n 关于测度p 的p - 平均误差为 e p ( s t ，雪，“i i ) = ( 上o s ( z ) 一西( ( z ) ) p p ( d ，) ) 。 信息关于测度p 的信息半径为 r p ( ，s ，弘，1 1 8 ) ：= i 掣勺( s ，圣，p ，i i 0 ) 着存在个算法妒使得 勺( 最圣，p ，q - h ) ；r ( 蜀p ，i 8 ) ， 则称妒为相应予信息的最优岁 = 泼 关于测度p 的最小信息半径为 ( n ，s ，p ，”0 ) _ i n f r ，( m 只“4 h ) 若有信息以及算法矿使得 ( n ，s ，p ，i i 1 i ) = r p ( ，最圣，“h h ) ， 则称为基数为n 的最优信息，妒为基数为n 的最优算法，圣o + 是为基数为 ，l 的信息基最优逼近 当最优信息和最优算法不容易确定的时候，我l 订考虑同题的弱浙近情形，也就是 寻找基数为n 的信息基逼近垂n o ，艟得逼近所产生的平均误差唧( 只 ，圣。，p ，n h ) 弱( 强) 等价于相应的最优信息半径咋( n ，s “h 0 ) 。称之为弱( 强) 最优信息基逼近 列 在过去的几年中。科学工作者们巳经针对线性情形给出了一套完整的理论，在 这套理论中，是个实可分的b 扯a c h 空间，p 是f 上的高斯测度，s 和都是 线性莽予相关理论请参阅l e c , 1 9 8 6 ；l e ea n dw a s i l k o k i ，1 9 8 6 ) 同时，逼近理论 中的一些深层次的概念，如宽度非线性宽度等，已经被应用到信息基复杂性理论 中 诧们注意到在已有的关于连续函数的信息基算子逼近工作当中。所研究的逼近 工具都是分段线性遢近( 或佯条函数) 在这些逼近方法中。恢复函数若采用分段线 性函数则它的光滑性不好，而若采用样条函数提高其光滑性则其系数计算时需要解 大量的线性方程。这无形中增加了计算量多项式插值作为连续函数空问上常用的 逼近工具。其在平均情形之下的误差分析却尚未见讨论本文讨论插值算子的平均 误差问题，具体描述如下- 设 x = ，：【0 ，1 】一r i ，连续且，( o ) = 0 ， 剐对每个n 1 ，b 8 ( 形) 和0 = t o t l t ，s1 且t o = 0 来说， w i e n e r 测度，为 u ( ，x ：( ，( t 1 ) ，( t 。) ) b ) = 垂南上净锱 对于厶。( ，) = ，( 缸) 来说，u 的关联算子由l 。( g 五。) = r a i n x , ，勋 给出。即 f ( x 1 ) f ( x 2 ) w ( d f ) = m i n x l ，勋 ，忱1 ，如【o ，1 j ( 2 ) 在本文当中。我酊漫，；仃e c - 1 ，1 l ：9 ( t ) = ，协一1 ) x ) t s 是恒等算 子。对于f 的每个可测子集a c 只我l 门定义 p ( a ) = ，( 9 ( t ) 。，( 2 一1 ) ，a ) ) ( ) 对于1s p ，我们记g ， 为【一l ，l l 上关于权( 1 一矿r 的所有工，可积函数按 如下范数h h 构成的线性赋范空同 f l f l l p = ( i ，( 圳，( 1 。妇) 5 ，v ，e 当q = 0 时。g p a 即为平常的0 空同 许多文章如f 1 - 4 l 都已讨论了平均情形下计算争逼近的复杂性。并给出了以计 算函数在固定点的函数值为可允许信息泛函的非自适应最小平均信息半径列的弱渐 近阶为 ( n ，s ，p 岛) x 赤 ( 3 ) 本文这一章的研究目的是摄考察基于第二类c l l c b y 出c r 节点组的g 埔n 硼黼插 值算子在w i c 唧空间下的平均误差是否能达到上述的弱渐近阶研究结果如下 定理3 1 设g i ( ，z ) 是如上定义的。则当- 1 a 毒时。以( 1 一扩) d 为权 的如范数下的平均误差 c 2 ( g ，g 2 ，。) n 一，- 1 n 三 从定理3 1 可以看出，当q = o ，p = 2 时，基于第二类c h c b y 8 h e v 节点组的 g 埔n 铆d d 插值算子在w i c n c r 空闻下平均误差不能达到( 3 ) 式的弱渐近阶 1 3 拟g r 砬n w a l d 插值算子在w i c m r 空同上平均误差的弱渐近阶 由1 2 的结论，我们知道对g 哺n w a l d 算子进行修正是有必要的，在这一部分 我们将讨论修正之后的拟g 而矾柚d 插值算子逼近的平均误差结论为t 定理4 1 设g ：( ， 甸是如上定义的拟g r 缸n 啪1 d 插值多项式，则我们有 e 2 ( 嚷，如) s 而u ， e 4 ( 嚷，l 4 ) s 靠 运用相同的方法经过一些更为繁琐的计算，我们猜想对于任意的偶数p ，都有 粥s ( 扩 5 结合上述结果及文献【2 l 。由h b l d c r 不等式可知。对于1 p , q + o o ， 粥 ) x ( 扩 在这里a = b 是指存在着与n 无关的常数f 。使得a c s b 墨c a 这一部分的结沦意味着拟g r f m 靴d d 插值莽子作为一种特殊的信息基逼近算 予。在逼近阶的意义下达到了最佳信息墓避近筇予的收敛速度。它几乎就是最佳逼 近算子有人曾计算j a c k s o n 莽子的平均误差在阶的意义下也得到了这个速度( 见 文献f 1 2 i ) 。但j a c k s o n 算子的计算需要知道所有点的函数值，这在实际中是不可实 施的另外值得一提的是，对于最佳逼近多项式列来说。其相应的平均误差的阶也 是知也就是说。拟g r i i n w a l d 插值算子作为一种多项式插值算子。对于l q 范效逼 近。其在w i e n e r 空间下的平均误差弱等价于相应的最佳逼近多项式的平均误差 这些结果充分说明了，从概率的角度来 j 六拟g r f m w a l d 插值是一种性质优良的逼 近工具 6 第二章一种拟g r i n w a l d 插值算子的加权b 收敛速度 2 1 引言 设，( ) 为 - 1 ，l 】上的连续函数，则以第二类6 h c b y s h c v 多项式以( z ) ( 讥( c 口) = 些铲) 的全部零点 “= 瞄格 ：。为插值结点组的，( z ) 的g r f i n w a l d 插 值多项式为 g 。( ，= ，( 坟) 瑾( z ) ， 七= l 其中， ) = d ，七- l 文献们证明了g 。( ，功在( - 1 ，1 ) 上处处收敛于，( 动。而且是内闭一致收敛 的文献【6 l 证明了g 。( ，王) 在如意义下不是收敛算子歹| i 。并对g 。( ，进行了 修正。给出了一种拟g r f i n w a l d 插值多项式 n + 1 嚷( ， 习= ，( t - ) 砭( z ) k 畜o “垆譬器川功王雩丽u n c x ) 溉扛) - 篙 扛) ，b 1 一川 文献 8 】讨论了上述算子于b 范数及以忐为权的加权范数下的收 跏川叫圳刊篙搿三 而且估计的阶是精确的，其中t ( ， ) 为文献【9 】中定义的权为妒( z ) = 们? = 的 7 伽川叫州，志司；端二篓二肇】：= ： i o b ( ，丢) + 峰】， o l 一1 ， c l r = g 一1 ， 一l a - 1 ，则有 ( 驰圳) 佻 茹，：筝，c 8 ( 言c 圳) c - 一矿，。出；f c 妄f 耄等墨；监p 嫡n 娜1 础 = 妄r ( 砉l 羔酱1 ) 一伽 = z 南( 砉l 拦1 ) 咖狲1 伽 + 喜f ( 妄i 差器1 ) 一伽 一：五+ 死 ( 8 ) 其中巩= ；高鲁我们先考虑死t 设a ( o ) = 瞄口s i n ( 倍卜1 ) 8 一m + 1 ) s i n 8 c 咄科- 1 ) p ， 注意到a ( o ) = o ，( o ) = 0 以及l a ( e ) l s c ( n + 1 ) 2 ，0 e 而即有 l a ( o ) l j a 1 ) 2 织o 双方钿， ( 9 ) b + 1 ) 龇雨：名 经过筒单的计算我仃丁知u ( c o s e ) = 主器，联系( 9 ) 式得到 n ；，南i 以( 嘲o ) 1 ，( s i n 口r 鲥1 甜+ ，南峨( c 0 b o ) 1 ，陋口矿n + 1 羽 j o j 鼎t = j ( 赢l 篙，陋p ) 斟1 础+ 愿钏9 ( 血。) 槲l - 印抛 s + 1 严z 0 商辨“) p ，壁炉l - p 棚 ， ，研兰! sg(，l+1)妒缸00) 现在估计，对任一。，lsasl 墨】，当口( 采 t ，与去字) 时，由文献1 8 】 引理2 的证明过程可知 i 竺墼婴is c 垫掣一 ( 1 1 ) 勺 删口一姗如一 j 一 由( 1 1 ) 式可计算得 掌( 妄i 差器舯尸瑚缉护学 a g 一1 ， a = g 一1 9 ( 1 2 ) 等 ( 目器旷c 一棚仨搿，口薯 上。唑萨x 嚣： 似， 2 3 定理2 1 的证明 取p n ( z ) 为，( z ) 在c - 1 ，1 j 上的ni 欠最佳逼近多项式，则 g ( ，z ) 一，( 。) = g ：( ，一r ，动+ 嚷( 只i ，功一r ( 。) + r ( z ) 一，( 霉)( 1 5 ) 我们易算出 瑶扛) + x l ( z ) 2 再结合( 4 ) 式得 l 嚷( ，一r ，z ) i = l ( ，一r ) ) x ：o ) i 4 1 i f - r 峙 于是，由( 5 ) 式可知 上。i 嚷( ，一r ，z ) i ( 1 一矿) 。出冬g 嵋( ，石1 ) ，( 1 6 1 ，1 - 1 l ，一r ( 力| p ( 1 一矿) 8 出昂嵋( ，：) ( 1 7 ) j 文献【6 l 给出了如下展开式 嚷( 酬- p n ( 垆k = z 踯t ) 南( 川腻一荟讹也) 媛( 枷8 ) 对于上式等号后面的第二个式子，我们从 1 i d 中的( 4 0 ) 式可推出t 当a ；时， 噻黝( 川翮z 1 1 ( ，。如 s i 砉只( 。一啪x ：扛1 1 刁吉季如q 嵋( ，；) ( 1 9 ) 1 0 当一l l 一1 时，存在s o 1 使得n 一1 + 彘 利用h s l d e r 不等式及( 2 3 ) 式可知 ( 争i ) p ( 1 翻。如 s 【( 砉俐) ( t 一确叫苦 ( - 一硝9 叫“希g 矿似) 由( 1 5 ) 至( 2 4 ) 式我们可得定理中上界的估计 最后。我们证明当口l l 时估计的阶是精确的取i o ( - ) = 1 崩 g ：( 知，习一矗扛) = n ( 1 一瑚峨( 。) 伽+ 1 ) 2 令z = c 0 8 以则由【2 5 ) 式川得刍，l a 町 l g ：( 加) _ ，o ( z ) l p ( 1 。如 ；fl业一sin(【n+1)$cosn8(n+1)2sin20 n + 1 ) 。i n o i 恤俨1 胡钏( 2 6 ) 一上i 【 7 当n l 一1 时，应用引理2 1 2 得 r l 耥蛳蝴棚 = 两1 1 ) 扣厶( i 汹s i n 匀印 ( 驴n + 1 ) e l 瑚一 苦争，a i 。- - i , l 咖，i 。妯 g 一1 ，剐有 z i 耥| ，( 刚州棚叫刍) ( 刎 另取a = a r 菌n ，寥= 【型掣一豹，则容易计算得 rl 号高暑等产蛳一，槲1 棚2j ( i 塑甓群r 蛳一，槲1 棚 2 赤喜管l 掣+ 1 l p 酬彩 、南叠群南瑚芝磊壹南= 象，衅。勘篙 。i 南喜群甜m + 1 ) e 硼象， 一哮 由( 3 0 ) 式可知，只要n 一1 ， z 1 i 业( n - 瑞i - 1s i 型n 8 | ，i 恤俨妣鲁 ( 3 1 ) ) 、 一。，l p ” 从( 2 9 ) 和( 3 1 ) 式我们可以推出当d 一1 时， 肌b 。i + n 2 ( n + 1 ) 矿e 1 ) 2 s i n 鬈s i 型n 8 i ，( 酬讲1 棚之鲁 ( 3 2 ) ，oi ( n + 。口 ( n + 1 ) i 一。矿 又i i , v o l l * = l ，( ，：) = 0 ，这样由( 2 7 ) 及( 3 2 ) 两式便知定理2 1 当n 一1 时收敛速度估计的阶是精确的 第三章g r f i n w a l d 插值算子在w i e n e r 空问上的平均误差 3 1 ；i 言 设，是个集合，g 是一个范数为h * 的线性赋范空问。，l 屉定义在，的 b o r e l 子集上的概率测度设s 是，剜g 的个可测映射。被称为解筇子在实际 问题中，对每一个，e s c f ) 是我们要逼近的目标函数设是f 到p 的个 可测映射。雪是舻到g 的个可测映射。与垂分别被称为信息算子和算法当 1 p + o o 时。逼近 o n 关于测度_ i i 的p _ 平均误差为 ( s ，圣，i i i i i ) ：= ( fl l s ( 一圣( ( 动) l l ，j e ( 彤) ) 5 信息关于测度弘的信息半径为 r p ( s j l ，4 h ) ：= _ m f e p ( s , n , e p ，雎) 若存在个算法妒使得 勺( 只m 妒，“l h ) 一r d 以s p * h ) 则称圣为相应于信息的最优算法 关于测度卢的最小信息半径为 r p ( n ，s p ，0 ) - i ，呼r p ( 只“n ) 若有信息以及算法妒使得 r ，( n ，s “1 1 1 ) = r p ( n ，s ，圣，芦，l i h ) ， 则称为基数为n 的最优信息，圣为基数为n 的最优算法，妒o n 是为基数为 n 的信息基最优逼近 当最优信息和最优算法不容易确定的时侯，我们考虑问题的弱渐近情形。也就是 寻找基数为n 的信息基逼近圣枞使得逼近所产生的平均误差e p ( 最，圣。，p ，i i 1 1 ) 弱( 强) 等价于相应的最优信息半径( f l ，只“1 1 | 1 ) 称之为弱( 强) 最优信息基逼近 列 在过去的几年中，科学工作者们已经针对线性情形给出了套完整的理论，在 这套理论中f 是个实可分的b a n a c h 空间，p 是f 上的高斯测度，s 和都是 线性算子( 相关理论请参阅l e e ，1 9 8 6 ；l e ea n dw a s i l k o w s k i ，1 9 8 6 ) 同时，逼近理论 中的一些深层次的概念，如宽度非线性宽度等，已经被应用到信息基复杂性理论 中 我们注意到在已有的关于连续函数的信息基算子遇近工作当中，所研究的逼近 工具都是分段线性逼近( 或样条函数) 在这些逼近方法中，恢复函数若采用分段线 1 4 性函数则它的光滑性不好面若采用样条函数提高其光滑性则其系数计算时镐要解 大量的线性方程。这无形中增加了计算量面多项式插值作为连续函数空问上常用 的逼近工具。其在平均情形之下的误差分析却尚未见讨论本文在讨论插值筇子的 平均误差问题时，具体描述如下设 x = ，：f o ，1 j 一屁i 瓞续且，( o ) = 0 则对每一个n21 ，b6 联船) 和0 = t o 2 i t 。1 且u o = 0 来说。 w i e n e r 测度u 为 “，( ，x ：( ，( t 1 ) ，f ( t 。) ) b ) = 垂丽1 上c k 矧 对于l 。( 力= ，( ) 来说，u 的关联莽子由l n ( q 工) = m i n x a ，z 2 ) 给出。即 厂f ( x 1 ) f ( x a p ( 们；m i n x l * 2 ：2 ，勋【o ，1 1 j x 在本文当中，我们设f = ，c - 1 ，1 】：o ( t ) ；，( 墨一1 ) ex ，s 是恒等算 予。对于，的每一个可测子集a c 只我们定义 p ( a ) = u ( 幻( t ) = ，( 封一1 ) ，f a ) ) ( + ) 对于1 p ，我们记g ，。为【- i ，i 】上关于权( 1 一护) a 的所有k 可积函数按 如下范数i i 1 l 构成的线性赋范空间 l l ，l i ，= ( 叭刮p ( 1 a 砂v ， 当o t = 0 时，q ，。即为平常的岛空间 许多文章如1 1 4 】都已讨论了平均情形下计算争逼近的复杂性，并给出了以计 算函数在固定点的函数值为可允许信息泛函的非自适应最小平均信息半径列的弱渐 近阶为 r p ( n , 只p ，如) 袁 本文这一章的研究目的是想考察基于第二类c h e b y s h e v 节点组的g r i i n w a l d 插 值算子在w i e n e r 空间下平均误差是否能达到上述的弱渐近阶研究结果如下一 定理3 1 设g n ( ，z ) 是如上定义的，则当一1 口 毒时，以( 1 一护) o 为权 的岛范数下的平均误差有 1 e 2 ( 瓯，g 矗) x ，i 一，- 1 口 妄 从定理3 1 可以看出。当dto , p = 2 时，基于第二类c h e b y s h e v 节点组的 g r f i n w a l d 插值算子在w i c n e r 空问下平均误差不能达到上述的弱渐近阶 设 3 2 预备知识和引理 扣( 字m ，+ 字仆，) 誊络 + 言他) ( 1 c - 吨，( 热) 2 k = l ”。一7 是以第二类c h e l 巧 s h e v 零点为插值节点组的次数不高于2 n + 1 次的拟h e r m i t o - f e j 自插值多项式( 见文献f 5 1 ) 。其中巩o ) 为第二类c h c b y s h c v 多项式于是我们 通过简单的计算可得 g 。( ，“) 一仉( “) ；0 ，k = 1 ，m( 3 4 ) 砩( ， “) 一繇( ，“) = f ：t ， 1 3 一t k 磋，七= l ，挖 g k ( ，1 ) 一l 孔( ，1 ) = ，( t ) ( 1 + t i ) 2 一，( 1 ) ( k ( ，一1 ) - q 。( ，一1 ) = ，( 乓) ( 1 - t k ) 2 - i ( - i ) ( 鲫 ( 3 0 ) ( 3 7 ) = ( 1 ( 1 圳k i k 厂( n + 州1 ) ( x 甸- t a ) ) 2 ，m ( 勰) = t l + x 器，帅= 生2 盟i n + 1 ) 2 ， ( 3 9 ) 机( 刁= ( 1 石- z 了2 ) 可( 1 币- i t ) 矿u ：( x ) ，七= 1 ，n ( 4 0 ) 则由( 3 4 ) 至( 4 0 ) 式。可得 田一功刊功匡m m 圳2 叫，】 + 嘶) b 钓( i - t k ) 2 - i ( - i l k = 1) j 瞧m t ) 熹绯) = 1 一 = 器静以t 均+ 搿娄地， 1 6 0 ，存在与，和f i 都无关的f 使得对i e c - i ，l 】， l ，( 曲一k ( ，刁| p ( 1 一护) 。d z s c j ( , ：) ( 4 3 ) l ，( 曲一k ( ，刁i ( 1 一护) 一l d zs三) ( 4 3 ) j l 其中，对于任意t o ti ，( ，t ) 是定义在【- - 1 ，1 1 上的i 的光滑模由( 4 3 ) 式我们可 知，当口一；时 ，1 i ( z ) 一l 巩( ，z ) 1 2 ( 1 一矿) 。正e i ? l 产( ，：) ( 4 4 ) j - - 1 而当一1 口 一时，同样由( 4 3 ) 式再结合h 6 1 d e r 不等式可得 ， i ，( $ ) 一哦( ，) 1 2 ( 1 一舻) 4 d ：c j 一1 ( ( 一确孚如) 毕( l ，( 墨卜q 以圳一承( 一胡一；如) 警 2 ( ，：) - ( 4 容易证明，对于9 ( z ) = f ( 2 z c 1 ) 来说，( 吼击) = 2 u ( ， 嘉) 因此由( “) 和( 4 5 ) 以 及文献【1 2 j 我们得到 j l s c 上( ，j ) 弘( d ，) s g 上舻( 9 ，：如( d g ) s 了c