论文部分内容阅读
信息与算法的复杂性(Information Based Complexity)是计算数学最主要的研究方向之一.在研究多变量函数的数值问题时,当自变量的个数d非常大时,几乎不可能用解析的方法来处理.所以我们只能考虑在误差不超过ε的条件下,通过逼近的方法来解决.算法的复杂性就是为了得到在误差不超过ε的条件下的近似解,所需要算法的所有信息运算与复合运算的最小计算成本.信息的复杂性则是在误差不超过ε的条件下,为解决这个d维变量数值问题所需要的最小信息数目n(ε,d).对于要解决的多变量问题,信息的复杂性是算法的复杂性一个下界.一般来讲,对于许多线性问题,信息的复杂性是与算法的复杂性成比例的.因此,在本论文中我们将焦点集中在信息的复杂性上. 多变量问题的易处理性(Tractability)是近年来信息与算法的复杂性最活跃的研究方向之一.它是研究信息的复杂性n(ε,d)如何依赖于ε-1和d.黄仿伦与张顺证明了无穷可微多变量函数逼近问题在L∝范数意义下不是强易处理的;Erich Novak与Wo(z)niakowski证明了无穷可微多变量函数逼近问题在L∞范数意义下不是易处理的;Wojtaszczyk证明了无穷可微多变量函数的积分问题在L∞范数意义下不是强易处理的.本论文主要在确定框架(deterministic setting)和Lp(p≥1)范数意义下研究这些问题.我们证明了无穷可微多变量函数逼近问题在Lp范数意义下不是强易处理的,同时给出了一种关于无穷可微多变量函数逼近问题在L∞范数意义下不是易处理的的构造函数的证明方法.不仅如此,我们还证明了无穷可微多变量函数的积分问题在Lp范数意义下不是强易处理的.从而将多变量问题的易处理性研究从L∞函数类推广到更大的Lp函数类. 论文共分为四章,第一章是预备知识,首先介绍了易处理性研究的发展历史和研究背景,其次给出了在确定框架下信息与算法的复杂性以及易处理性的一些有关概念、记号与结果. 第二章主要证明了在使用Lp范数进行逼近时,无穷可微多变量函数的逼近问题与积分问题不是强易处理的.另外我们还利用构造函数的证明方法再次证明了在L∝范数意义下,无穷可微多变量函数的逼近问题不是易处理的. 第三章在阐述了无穷可微多变量函数积分问题的易处理性的研究现状之后,给出了H(o)lder空间和Korobov空间上函数的积分问题不是易处理的的结论. 第四章对前面几章的主要证明结论进行了总结,并且提出今后的工作重点和研究方向,将继续在平均框架和随机框架下多变量问题的易处理性研究.