本文選題：信息與算法的復雜性 + 多變量函數(shù)積分�。� 參考：《安徽大學》2017年碩士論文

【摘要】：在許多定義在d維函數(shù)空間上多變量問題中,d可能非常大,當d很大時,這種問題幾乎不能通過傳統(tǒng)的解析方法解決,在給定誤差ε.允許的范圍內,只能通過逼近的方法去解決.而多變量問題的易處理性(tractability)就是研究逼近該問題算法的復雜性是怎樣依賴于ε-1和維數(shù)d的,它是由美國哥倫比亞大學Wozniakowski教授上個世紀九十年代中期提出的一種信息與算法的復雜性理論(information based complexity)分析方法.近年來,被越來越多的學者研究.多變量函數(shù)積分的逼近問題是多變量問題的易處理性研究中最古典的研究方向之一,其中無窮可微多變量函數(shù)積分的逼近問題大多數(shù)都是在L∞范數(shù)意義下研究的.例如,波蘭數(shù)學家Wojtaszcyzk證明了無窮可微多變量函數(shù)的積分問題在L∞范數(shù)意義下不是強易處理的(not strongly tractable).近年來一些學者提出了多變量問題的擬多項式易處理性(quasi-polynomial tractability)和弱易處理性(weak tractability)概念,指出有些多變量問題雖然不是易處理的或者不是強易處理的、但有可能是擬多項式易處理的或弱易處理的.本論文主要研究無窮可微多變量函數(shù)積分逼近問題的擬多項式易處理性和弱易處理性,用信息與算法的復雜性理論,對無窮可微多變量函數(shù)空間重新定義兩個范數(shù),在確定框架下,利用標準信息類(函數(shù)值作為信息),證明了無窮可微多變量函數(shù)積分的逼近問題是擬多項式易處理的,同時也是弱易處理的.另外,本文還研究了 Korobov空間上周期函數(shù)的振蕩積分問題.分別利用線性算法和好格子點法(good lattice method)對此問題進行逼近,并對算法進行誤差分析.全文分為四章:第一章,引言,首先介紹了信息與算法的復雜性理論知識和多變量問題的易處理性的研究發(fā)展歷程,以及它們的研究背景.其次,給出了證明過程中所需要的相關的泛函分析方面的知識,以及多變量問題易處理性的理論基礎.第二章,我們對無窮可微多變量函數(shù)空間定義了兩個新的范數(shù),利用多變量Taylor展開式的相關知識,證明了在函數(shù)空間Fd1上多變量的積分問題是擬多項式易處理的,在函數(shù)空間Fd2上多變量的積分問題是弱易處理的.第三章,主要采用標準信息類,研究了 Korobov空間的函數(shù)類Eα,d上的振蕩積分問題,證明了此問題不是易處理的,并且"遭受"維數(shù)的災難(the curse of dimension).另外,我們還采用好格子點法去逼近此問題,得出了逼近算法的誤差的上界.第四章,總結了前面的證明結果,并且提出了以后將會重點研究的方向.
[Abstract]:In many multivariable problems defined in d dimensional function space, d may be very large. When d is very large, this kind of problem can hardly be solved by traditional analytical method. To the extent permitted, it can only be solved by means of approximation. The tractability of multivariable problem is to study how the complexity of approximate algorithm depends on 蔚 -1 and dimension d. It is an information based complexity analysis method proposed by Professor Wozniakowski of Columbia University in the middle of 1990s. In recent years, more and more scholars study. The approximation problem of multivariable function integral is one of the most classical research directions in the research of multivariable problem's easiness, in which the approximation problem of infinitely differentiable multivariable function integral is mostly studied in the sense of L 鈭，

本文編號：2021445