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

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

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

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

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