隨機逼近兩類信息的第n個最小誤差之間的關(guān)系.pdf

1、多變量函數(shù)的逼近問題是信息復(fù)雜性理論（Information Based Complexity）中最主要的問題之一，被許多數(shù)學(xué)家廣泛的研究。主要原因是許多多變量連續(xù)問題本質(zhì)上都與多變量逼近密切相關(guān)，例如，多變量積分、偏微分方程和積分方程的解以及一些非線性問題等等。
　　 第n個最小誤差（the nth minimAlerror）是信息復(fù)雜性理論所研究的主要問題之一，它與對應(yīng)問題的信息與計算的復(fù)雜性密切相關(guān)，是在最多用n個信息運算

2、的所有算法中最好的可能誤差，也是ε-復(fù)雜性（complexity ε-）的研究基礎(chǔ)。
　　 有了ε-復(fù)雜性，我們可以進(jìn)一步研究1994年由美國紐約哥倫比亞大學(xué)Wo?Niakowski教授提出的多變量逼近或積分問題的易處理性（tractability）問題，所以對于第n個最小誤差的研究是很有必要的。
　　 對于第n個最小誤差在信息復(fù)雜性理論中給出了很詳細(xì)的介紹，其中包括在確定框架（the worst case settin

3、g/deterministic setting）下、平均框架（the averagesetting）下和隨機框架(the randomized/stochastic setting)下對于信息類Λ的誤差以及在此基礎(chǔ)上定義的第n個最小誤差。第n個最小誤差的相關(guān)理論，以及一些理論的證明，為我們進(jìn)一步研究ε-復(fù)雜性和易處理性問題提供了方法和依據(jù)。其中值得一提的是構(gòu)造“水泵”函數(shù)（bump function）來求第n個最小誤差和ε-復(fù)雜性的下界

4、，是解決各種框架下和各種空間中的類似問題的重要方法。
　　 在本文中考慮兩類信息，一類是由連續(xù)線性泛函組成的，稱為線性信息，記作Λall，這類信息相對來講容易分析，但是計算十分復(fù)雜；另一類是由函數(shù)值組成的，稱為標(biāo)準(zhǔn)信息，記作stad，標(biāo)準(zhǔn)信息分析起來困難些，但是在許多情況下，只有標(biāo)準(zhǔn)信息在實際計算中才可以實現(xiàn)。
　　 本文中考慮了再生核希爾伯特空間中的多變量逼近問題，研究了在隨機框架下線性信息和標(biāo)準(zhǔn)信息的第n個最小誤差之

5、間的關(guān)系。我們所考慮的函數(shù)是d維的，其中d 可以任意大。函數(shù)本身與其逼近之間通過加權(quán)的2 L-范數(shù)給出。
　　 本文的中心部分首先考慮逼近算子：SHG→，給出了在確定框架、隨機框架下對于標(biāo)準(zhǔn)信息的第n個最小誤差之間的關(guān)系，這個關(guān)系使我們推出隨機框架下對于標(biāo)準(zhǔn)信息和線性信息的第n個最小誤差之間的關(guān)系。接著考慮算子Sρ:H→Hρ，并得到了類似的結(jié)論。
　　 信息收斂階或稱收斂的速度是逼近理論的一個重要部分。收斂的階顯示了由n

6、個線性泛函或n個函數(shù)值組成的算法的第n個最小誤差收斂于0的速度。當(dāng)然階越大，問題越簡單，所以對第n個最小誤差的階的研究是很有意義的。
　　 論文共分為三章。
　　 第一章預(yù)備知識，闡述了信息復(fù)雜性理論的一些基本內(nèi)容，包括確定框架、平均框架和隨機框架的誤差以及第n個最小誤差的定義、其上下界，以及以上三個框架下第n個最小誤差之間的關(guān)系；介紹了與第n個最小誤差密切相關(guān)的ε-復(fù)雜性的相關(guān)理論。
　　 第二章回顧了再生核希

7、爾伯特空間的一些基本符號和理論；給出了希爾伯特空間中確定框架和平均框架下基于線性信息和標(biāo)準(zhǔn)信息的第n個最小誤差之間的關(guān)系；重點論證了隨機框架下多變量逼近在兩類逼近算子, SSρ下，對于以上兩類信息的第n個最小誤差之間的關(guān)系：erann(^std)≦minK=0,1…(2eran[k+1/2](^all)2+AK/n)1/2erann(Sp,Astd)≦mink=0,1[erank(Sp,Aall)2+A/n∑I=1p1/2/λ21[1-