随机逼近两类信息的第n个最小误差之间的关系

摘要

多变量函数的逼近问题是信息复杂性理论（Information Based Complexity）中最主要的问题之一，被许多数学家广泛的研究。主要原因是许多多变量连续问题本质上都与多变量逼近密切相关，例如，多变量积分、偏微分方程和积分方程的解以及一些非线性问题等等。
　　 第n个最小误差（the nth minimAlerror）是信息复杂性理论所研究的主要问题之一，它与对应问题的信息与计算的复杂性密切相关，是在最多用n个信息运算的所有算法中最好的可能误差，也是ε-复杂性（complexity ε-）的研究基础。
　　 有了ε-复杂性，我们可以进一步研究1994年由美国纽约哥伦比亚大学WoźNiakowski教授提出的多变量逼近或积分问题的易处理性（tractability）问题，所以对于第n个最小误差的研究是很有必要的。
　　 对于第n个最小误差在信息复杂性理论中给出了很详细的介绍，其中包括在确定框架（the worst case setting/deterministic setting）下、平均框架（the averagesetting）下和随机框架(the randomized/stochastic setting)下对于信息类Λ的误差以及在此基础上定义的第n个最小误差。第n个最小误差的相关理论，以及一些理论的证明，为我们进一步研究ε-复杂性和易处理性问题提供了方法和依据。其中值得一提的是构造“水泵”函数（bump function）来求第n个最小误差和ε-复杂性的下界，是解决各种框架下和各种空间中的类似问题的重要方法。
　　 在本文中考虑两类信息，一类是由连续线性泛函组成的，称为线性信息，记作Λall，这类信息相对来讲容易分析，但是计算十分复杂；另一类是由函数值组成的，称为标准信息，记作stad，标准信息分析起来困难些，但是在许多情况下，只有标准信息在实际计算中才可以实现。
　　 本文中考虑了再生核希尔伯特空间中的多变量逼近问题，研究了在随机框架下线性信息和标准信息的第n个最小误差之间的关系。我们所考虑的函数是d维的，其中d 可以任意大。函数本身与其逼近之间通过加权的2 L-范数给出。
　　 本文的中心部分首先考虑逼近算子：SHG→，给出了在确定框架、随机框架下对于标准信息的第n个最小误差之间的关系，这个关系使我们推出随机框架下对于标准信息和线性信息的第n个最小误差之间的关系。接着考虑算子Sρ:H→Hρ，并得到了类似的结论。
　　 信息收敛阶或称收敛的速度是逼近理论的一个重要部分。收敛的阶显示了由n个线性泛函或n个函数值组成的算法的第n个最小误差收敛于0的速度。当然阶越大，问题越简单，所以对第n个最小误差的阶的研究是很有意义的。
　　 论文共分为三章。
　　 第一章预备知识，阐述了信息复杂性理论的一些基本内容，包括确定框架、平均框架和随机框架的误差以及第n个最小误差的定义、其上下界，以及以上三个框架下第n个最小误差之间的关系；介绍了与第n个最小误差密切相关的ε-复杂性的相关理论。
　　 第二章回顾了再生核希尔伯特空间的一些基本符号和理论；给出了希尔伯特空间中确定框架和平均框架下基于线性信息和标准信息的第n个最小误差之间的关系；重点论证了随机框架下多变量逼近在两类逼近算子, SSρ下，对于以上两类信息的第n个最小误差之间的关系：erann(^std)≦minK=0,1…(2eran[k+1/2](^all)2+AK/n)1/2erann(Sp,Astd)≦mink=0,1[erank(Sp,Aall)2+A/n∑I=1p1/2/λ21[1-1-k/oi(∑p1i=1)]]。
　　 第三章详细论述了随机框架下加权逼近标准信息的阶。多变量逼近是在再生核希尔伯特空间中进行研究的，其中有一些假设，如果定义到其它空间不一定得到相应的结果。

目录

文摘

英文文摘

声明

第一章预备知识

第二章确定、平均、随机框架下两类信息的第n个最小误差之间的关系

第三章随机逼近标准信息的阶

参考文献

致谢

读研期间科研情况