无穷可微多变量函数积分的易处理性研究

摘要

在许多定义在d维函数空间上多变量问题中，d可能非常大，当d很大时，这种问题几乎不能通过传统的解析方法解决，在给定误差ε允许的范围内，只能通过逼近的方法去解决.而多变量问题的易处理性(tractability)就是研究逼近该问题算法的复杂性是怎样依赖于ε-1和维数d的，它是由美国哥伦比亚大学Wo(z)niakowski教授上个世纪九十年代中期提出的一种信息与算法的复杂性理论(information based complexity)分析方法.近年来，被越来越多的学者研究.
　　多变量函数积分的逼近问题是多变量问题的易处理性研究中最古典的研究方向之一，其中无穷可微多变量函数积分的逼近问题大多数都是在L∞范数意义下研究的.例如，波兰数学家Wojtaszcyzk证明了无穷可微多变量函数的积分问题在L∞范数意义下不是强易处理的(not strongly tractable).近年来一些学者提出了多变量问题的拟多项式易处理性(quasi-polynomial tractability)和弱易处理性(weak tractability)概念，指出有些多变量问题虽然不是易处理的或者不是强易处理的、但有可能是拟多项式易处理的或弱易处理的.本论文主要研究无穷可微多变量函数积分逼近问题的拟多项式易处理性和弱易处理性，用信息与算法的复杂性理论，对无穷可微多变量函数空间重新定义两个范数，在确定框架下，利用标准信息类（函数值作为信息），证明了无穷可微多变量函数积分的逼近问题是拟多项式易处理的，同时也是弱易处理的.另外，本文还研究了Korobov空间上周期函数的振荡积分问题.分别利用线性算法和好格子点法(good lattice method)对此问题进行逼近，并对算法进行误差分析.
　　第一章引言，首先介绍了信息与算法的复杂性理论知识和多变量问题的易处理性的研究发展历程，以及它们的研究背景.其次，给出了证明过程中所需要的相关的泛函分析方面的知识，以及多变量问题易处理性的理论基础.
　　第二章对无穷可微多变量函数空间定义了两个新的范数，F1d={f∈C∞[-1/2，1/2]d）:sup k∈N0∑|β|=k‖Dβf‖∞/β!≤1}F2d={f∈C∞(B(0,rd)):supk∈N0‖(e)kv‖∞≤1, B(0，rd)={x∈Rd:‖x‖≤rd}}.利用多变量Taylor展开式的相关知识，证明了在函数空间F1d上多变量的积分问题是拟多项式易处理的，在函数空间F2d上多变量的积分问题是弱易处理的.
　　第三章主要采用标准信息类，研究了Korobov空间的函数类Eα,d上的振荡积分问题，证明了此问题不是易处理的，并且“遭受”维数的灾难(the curseof dimension).另外，还采用好格子点法去逼近此问题，得出了逼近算法的误差的上界.
　　第四章总结了前面的证明结果，并且提出了以后将会重点研究的方向.

目录

声明

摘要

第一章 绪论

§1．1 研究背景

§1．2 预备知识

§1．3 信息复杂性相关理论

§1．4 多变量问题的易处理性相关理论

第二章 无穷可微函数积分问题的易处理性

§2．1 问题引入

§2．2 无穷可微函数的积分问题是拟多项式易处理的

§2．3 无穷可微函数的积分问题是弱易处理的

第三章 Korobov空间上振荡积分问题

§3．1 问题引入

§3．2 Korobov空间上振荡积分的非易处理性

§3．3 采用格子点法对Korobov空间上振荡积分的误差分析

第四章 总结与展望

参考文献

致谢

攻读硕士学位期间科研情况