一类具有界混合偏导数函数类的非线性逼近.pdf

《一类具有界混合偏导数函数类的非线性逼近.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、详细中文摘要随着科学技术的突飞猛进，计算机已经渗透到社会生活和科学技术的各个领域，成为主要的计算工具，计算机所能使用的计算资源是有限的.因此，在解决间题的众多算法中寻求最小计算成本算法的重要性就突现出来，这就是连续问题计算复杂性(又称为信息基复杂性，以下简称计算复杂性)所要解决的问题.求解问题的计算复杂性指的是在给定误差范围内，在利用其部分信息对待求解问题进行求解的众多算法中寻求对资源，如时间，计算机内存，“消耗”最小的算法.换言之，计算复杂性就是寻求最经济的算法，这种最经济的算法称为最优算法.这里的“信息”指的是在求解间题

2、时所能获得的有关该问题的已知条件，通常这种信息只是待求解间题的一部分.尤其在科学技术和工程领域(如经济，物理，人工智能模式识别，信号处理和控制论)的大多数间题，这种信息都有Partial,Noisy和Priced的特点.计算复杂性理论涉及众多学科领域.值得指出的是，计算复杂性的问题与函数逼近论有着密切的联系，它不仅需要运用逼近论中经典的方法技巧(如A.N.Kolmogorov、S.M.Nikolskii[15]、Pinkus[16]等人关于部分和逼近及宽度理论的成果、N项逼近、测度分布下的宽度、小波分析!2,28]等)，还要

3、综合运用调和分析，数值分析，计算数学，代数数论，随机分析等领域内一些新的思想与方法·Micchelli,Traub[23,24,25]阐明了宽度理论与计算复杂性的联系.Traub、Wozniakoskwii、Wasikowski[24,叫等关于连续问题的基于信息的复杂性的工作及Sul'din、Larkin[8,21,22]等关于测度分布下的函数逼近间题的工作，阐明了宽度理论与最优恢复理论的重要联系.基于此，Voronin、Temirgaliev[20]、Mathe[13]、Maiorov[11,12}建立了平均宽度与概率宽度

4、的基本概念，将计算averagecasesetting和probabilitysetting下的计算复杂性及最优误差阶的问题分别转化为计算相应函数类的平均宽度和概率宽度.经典宽度，平均宽度以及概率宽度，大多数研究的是利用线性信息逼近的问题，这类模型相对简单，算法复杂度不大，计算成本较小，然而在现实生活的实际问题中，信息更多的是以非线性的形式呈现的，用线性信息去逼近非线性的信息就会产生逼近阶较低的问题，因此基于非线性信息的非线性逼近就成为一种必要，当然在某些特殊的情形下这两类逼近具有相同的逼近效果，但大多数时候由于利用非线性信

5、息所能构造的的算法增多，所以逼近的精确阶也相应地得到提高.在此背景之下，本文将继续前人的工作，对一类具有有界混合偏导数的函数类的基于非线性信息的非线性宽度进行估计，并得出其非线性宽度阶的精确估计.下面我们首先从伪维数的定义引入非线性宽度的概念.对实数‘，sgn(t)表示符号函数，当t>0时，其值为1，其它情形为一1.对向量xERd,sgn(x):一(sgn(XI),....sgn(xd))如果M是SZ上的一个实值函数集合，那么M的伪维数定义为满足下面条件的最大整数Y1:存在SZ中的点a',...,a'，以及b=(bt,...

6、,bn)ER"使得集合{sgn(y):，=(f(ai)+b,,，f(a')+bn),fEM}的基数为20'.如果不存在这样的最大的。，那么M的伪维数是正无穷.我们将M的伪维数记为dimp(1b1)一个实值1f数集的伪维数的概念最先是由Pollard[17]提出的，之后，作为伪维数的拓广，Haussle:引入了Vapnik-Chervonekis维数.伪维数和Vapnik-Chervoneki。维数是一个函数类的容量(capacity)的度量.它们在模式识别、消退估计、经验过程、学习理论中都有重要的应用.设x是赋有拟范数”·1

7、1的线性空间，W和M是x的子集，E(W,M,X)elf一0)fsEuWp9GrnEMr给出了由M对W逼近的最坏误差.如果M是线性子集，就得到经典的基于线,哇信息逼近的情形.而基于非线性信息的非线性逼近指的是集合M是非线性子集时的情形.设从是X的一个子集族，我们考虑的是由M中的集合M对W逼近的最坏误差，即考虑d(W,M,X):一概E(W,M,X)如果M是维数不超过。的线性子空间的集合，那么(2)中的d(W,M,X)正是经典的Kolmogorov，宽度4(W,X).我们主要研究的是最近由Ratsaby和Maiorov[1d,咧引

8、入的非线性。-宽度PP.(WIX).对。上的一个实值函数空间.如果(2)中的M是X的所有伪维数不超过。的子集族，那么(2)中的d(W,M,X)称为非线性。一宽度，记作蹂(城X):=d(城州，X).(3)计算函数类的非线性宽度的核心问题就是确定其渐近精确阶，此前在这方面的工作特别是!6,7]