畢 艷, 陳廣貴, 徐艷艷, 甘 瑩

（西華大學(xué) 數(shù)學(xué)與計(jì)算機(jī)學(xué)院,四川 成都610039）

1 引言與預(yù)備知識(shí)

眾所周知,計(jì)算機(jī)所使用的計(jì)算資源非常有限,因此,在解決問題的眾多算法中尋求最小計(jì)算成本的算法就尤為重要.算法的誤差和成本的不同定義導(dǎo)致了不同的框架（或稱為計(jì)算模型）:最壞情形的框架（或一致框架）、平均框架和概率框架.在最壞情形的框架下,成本和誤差是通過函數(shù)類中的“最壞”的元素的特征來定義的.因此,在綜合計(jì)算成本的條件下,最優(yōu)誤差算法是對(duì)于“最壞”元素產(chǎn)生最優(yōu)逼近,而對(duì)于大多數(shù)元素來講,最優(yōu)誤差算法所產(chǎn)生的逼近誤差可能不是最優(yōu)的,為了解決這一問題,我們通?？紤]在函數(shù)集上定義一概率測(cè)度,考慮其平均誤差和概率誤差.平均誤差給出了函數(shù)類在給定的測(cè)度下的逼近度的平均,反映了在一定的計(jì)算成本下大多數(shù)元素的最小誤差,它更為深刻地反映了函數(shù)類結(jié)構(gòu)的本質(zhì)特征.概率誤差則進(jìn)一步給出了達(dá)到某個(gè)誤差階的元素在給定的測(cè)度下的分布,更深刻的刻畫了函數(shù)類的內(nèi)在結(jié)構(gòu)特征.特別地,在最優(yōu)算法的研究中,要確定最壞框架、平均框架、概率框架下的最優(yōu)誤差階,往往是通過計(jì)算相應(yīng)情形下的函數(shù)集寬度而得到.

X是具有范數(shù)‖·‖線性賦范空間,W是X的有界子集,FN是X上的N-維子空間.定義W對(duì)FN的偏差為

是FN對(duì)x的最佳逼近.因此,W在X空間中的Kolmogorov N-寬度定義為

其中,FN取遍X中維數(shù)不超過N的所有線性子空間.

設(shè)W的子集B是由W中的開子集所生成的Borel域,μ是B上概率測(cè)度,也就是說μ是B上的σ-非負(fù)可加的函數(shù),且μ（W）＝1.記δ∈（0,1）的任意實(shí)數(shù),則W在X空間中關(guān)于測(cè)度μ的Kolmogorov概率（N,δ）-寬度定義為

其中,Gδ取遍B中測(cè)度不超過δ的所有線性子空間.

定義W在X空間中關(guān)于測(cè)度μ的Kolmogorov p-平均N-寬度為

其中,（2）式中的FN取遍X中維數(shù)不超過N的所有線性子空間.

經(jīng)典的N-寬度在最壞框架下,用某種意義下的最優(yōu)逼近工具給出這類函數(shù)的最優(yōu)恢復(fù),寬度值即對(duì)于“最壞”元素的最佳逼近的誤差估計(jì).然而,經(jīng)典的寬度未能給出對(duì)于大多數(shù)元素的誤差估計(jì),這也反映在對(duì)于大多數(shù)元素來說最佳逼近的誤差值一般小于經(jīng)典寬度值,無論從實(shí)際應(yīng)用還是理論分析的角度,研究全空間的逼近性質(zhì)都是很重要的.因此,如何在經(jīng)典寬度的基礎(chǔ)上拓廣寬度的概念,使之發(fā)揮更大的作用是至關(guān)重要的.于是引入了概率寬度和平均寬度的概念.概率寬度也刻畫了最佳逼近誤差,它的誤差則是由測(cè)度至少為1-δ的子集在最壞情況下定義的,反映了W的所有子集最佳逼近的μ分布,給出了達(dá)到某個(gè)誤差階的元素在給定測(cè)度下的分布,更為深刻的刻畫了函數(shù)類的內(nèi)在結(jié)構(gòu)特征.平均寬度所刻畫的最佳逼近誤差是由誤差在給定的測(cè)度下的積分定義的,它反映了空間大多數(shù)元素的最優(yōu)逼近.關(guān)于經(jīng)典寬度的相關(guān)知識(shí)可參閱文獻(xiàn)［1-4］,而關(guān)于概率寬度與平均寬度可參閱文獻(xiàn)［5-17］.

令Lq（T）,1≤q≤∞,表示周期為 2π的 q次Lebesgue 可積函數(shù)類,且‖· ‖Lq（T）為其上范數(shù).令x（t）,t∈［0,2π］為 Hilbert空間 L2（T）上的 2π為周期的函數(shù),則有

2 主要結(jié)果

3 離散化

4 主要結(jié)果的證明

這樣就完成了定理2的證明.

致謝西華大學(xué)研究生創(chuàng)新基金（04030209）對(duì)本文給予了資助,謹(jǐn)致謝意.

［1］ Pinkus A.n-widths in Approximation Theory［M］.Berlin:Springer-Verlag,1985:1-150.

［2］ Temlyakov V N.Approximation of functions with bounded mixed derivative［J］.Tr Mat Inst Akad Nauk SSSR,1986,178:1-112.

［3］ Traub J F,Wasilkowski G W,Wozniakowski H.Infirmation Based Complexity［M］.New York:Academic Press,1988:55-70.

［4］ Traub J F,Wozniakowski H.A General Theory of Optimal Algorithms［M］.New York:Academic Press,1980:5-80.

［5］ Maivorov V E.Widths of spaces,endowed with a Gaussian measure［J］.Russion Acad Sci Dokl Math,1992,45:305-309.

［6］ Maivorov V E.Kolmogorov's （n,δ） -widths of the spaces of the smooth functions［J］.Russion Acad Sci Sb Math,1994,79:265-279.

［7］ Maivorov V E.Linear widths of functions spaces equipped with the Gaussian measure ［J］.J Approx Theory,1994,77:74-88.

［8］ Maivorov V E,Wasilkowski G W.Probabilistic and average linear widths in L∞-norm with respect to r-fold Wiener measure［J］.J Approx Theory,1996,84:31-40.

［9］ Ritter K.Average Case Analysis of Numerical Problems,Lecture Notes in Maths［M］.Berlin:Springer-Verlag,2000:1733.

［10］ Sun Y S.Average n-width of point set in Hilbert space［J］.Chinese Sci Bull,1992,37:1153-1157.

［11］ Sun Y S,Wang C Y.μ-average widths on the Wiener space［J］.J Complexity,1994,10:428-436.

［12］ Sun Y S,Wang C Y.Average error bounds of best approximation of continuons functions on the Wiener space ［J］.J Complexity,1995,11:74-104.

［13］ Kuo H H.Gaussian Measure in Banach Space in Lecture Notes in Mathematics［M］.Berlin:Springer-Verlag,1975:463.

［14］ Ledoux M,Talagrand M.Probability in Banach Space［M］.Berlin:Springer-Verlag,1991:23.

［15］陳廣貴,蔡斌畏.無限維空間在概率框架和平均框架下的逼近特征［J］.西華大學(xué)學(xué)報(bào):自然科學(xué)版,2011,30（5）:25-28.

［16］張健,舒級(jí).低維空間中帶調(diào)和勢(shì)的非線性Schr? dinger方程［J］.四川師范大學(xué)學(xué)報(bào):自然科學(xué)版,2002,25（3）:226-228.

［17］張亞蘭,陳廣貴,羅新建.多重調(diào)和基樣條對(duì)多元帶有限函數(shù)的恢復(fù)［J］.四川師范大學(xué)學(xué)報(bào):自然科學(xué)版,2010,2:176-178.