Lp范數(shù)下無(wú)窮可微多變量函數(shù)逼近不是強(qiáng)易處理的.pdf

1、信息與算法的復(fù)雜性(Information Based Complexity)是計(jì)算數(shù)學(xué)最主要的研究方向之一.在研究多變量函數(shù)的數(shù)值問(wèn)題時(shí)，當(dāng)自變量的個(gè)數(shù)d非常大時(shí)，幾乎不可能用解析的方法來(lái)處理.所以我們只能考慮在誤差不超過(guò)ε的條件下，通過(guò)逼近的方法來(lái)解決.算法的復(fù)雜性就是為了得到在誤差不超過(guò)ε的條件下的近似解，所需要算法的所有信息運(yùn)算與復(fù)合運(yùn)算的最小計(jì)算成本.信息的復(fù)雜性則是在誤差不超過(guò)ε的條件下，為解決這個(gè)d維變量數(shù)值問(wèn)題所需要的最

2、小信息數(shù)目n(ε，d).對(duì)于要解決的多變量問(wèn)題，信息的復(fù)雜性是算法的復(fù)雜性一個(gè)下界.一般來(lái)講，對(duì)于許多線性問(wèn)題，信息的復(fù)雜性是與算法的復(fù)雜性成比例的.因此，在本論文中我們將焦點(diǎn)集中在信息的復(fù)雜性上.
　　多變量問(wèn)題的易處理性（Tractability）是近年來(lái)信息與算法的復(fù)雜性最活躍的研究方向之一.它是研究信息的復(fù)雜性n（ε，d）如何依賴于ε-1和d.黃仿倫與張順證明了無(wú)窮可微多變量函數(shù)逼近問(wèn)題在L∝范數(shù)意義下不是強(qiáng)易處理的;Er

3、ich Novak與Wo(z)niakowski證明了無(wú)窮可微多變量函數(shù)逼近問(wèn)題在L∞范數(shù)意義下不是易處理的;Wojtaszczyk證明了無(wú)窮可微多變量函數(shù)的積分問(wèn)題在L∞范數(shù)意義下不是強(qiáng)易處理的.本論文主要在確定框架(deterministic setting)和Lp(p≥1)范數(shù)意義下研究這些問(wèn)題.我們證明了無(wú)窮可微多變量函數(shù)逼近問(wèn)題在Lp范數(shù)意義下不是強(qiáng)易處理的，同時(shí)給出了一種關(guān)于無(wú)窮可微多變量函數(shù)逼近問(wèn)題在L∞范數(shù)意義下不是易處

4、理的的構(gòu)造函數(shù)的證明方法.不僅如此，我們還證明了無(wú)窮可微多變量函數(shù)的積分問(wèn)題在Lp范數(shù)意義下不是強(qiáng)易處理的.從而將多變量問(wèn)題的易處理性研究從L∞函數(shù)類推廣到更大的Lp函數(shù)類.
　　論文共分為四章，第一章是預(yù)備知識(shí)，首先介紹了易處理性研究的發(fā)展歷史和研究背景，其次給出了在確定框架下信息與算法的復(fù)雜性以及易處理性的一些有關(guān)概念、記號(hào)與結(jié)果.
　　第二章主要證明了在使用Lp范數(shù)進(jìn)行逼近時(shí)，無(wú)窮可微多變量函數(shù)的逼近問(wèn)題與積分問(wèn)題不是