多变量问题的对数多项式与弱易处理性研究

发布时间：2018-04-27 18:35

本文选题：信息与算法的复杂性 + 多变量问题的易处理性　；参考：《安徽大学》2017年硕士论文

【摘要】：在许多学科中,例如物理学、化学、计算机科学、量子力学、金融学、经济学等,我们经常会遇到定义在d维多变量函数空间的数值逼近问题,其中d可能很大,成百上千,甚至更大,当d很大的时候,通常我们在指定的误差ε下,用函数的泛函(线性信息)或函数值(标准信息)作为信息构造算法来逼近该问题.逼近该多变量数值问题算法的复杂性,记为C(n,ε,d),一直是近年来计算数学的主要研究方向之一.逼近该多变量问题算法所需的最少信息个数称为信息的复杂性,记为n(ε,d).显然信息的复杂性是算法复杂性的一个下界,尤其对于许多线性问题,信息的复杂性与算法的复杂性是成一定的比例,所以算法复杂性的研究重点集中于信息的复杂性研究上.多变量问题的易处理性主要研究n(ε,d)如何依赖于ε和d,传统的多变量问题研究时,对于任给的d是固定的,那么就容易忽略了维数d的影响,而n(ε,d)有可能依赖于d的指数形式增长,所以对于多变量问题的复杂性还需要新的大量的研究.1994年,波兰数学家Wozniakowski教授提出了多变量问题易处理性的许多新慨念与理论,例如,多变量问题的不易处理性(intractability)、强易处理性(strong tractabili-ty)、弱易处理性(weak tractability)、多项式易处理性(polynomial tractability)、弱拟多项式易处理性(weak and quasi-polynomial tractability)、对数多项式易处理(polylog tractability),许多学者研究并得出大量成果.本文主要在平均框架下对多变量问题的对数多项式易处理性与弱易处理性做进一步研究.本文的工作主要包括以下几章:第一章,首先简要介绍信息与算法的复杂性与易处理性相关研究背景和发展历史,给出本文需要的复杂性的一些基本概念和符号以及结果.第二章,我们主要在平均框架下讨论多变量问题的易处理性,并给出了多变量问题是对数多项式易处理及(s,lnk)弱易处理的充要条件,随后对于特殊的加权逼近问题,我们证明了加权逼近问题S是lnk弱易处理性,并且在线性信息与标准信息下是等价的.第三章,我们还是在平均框架下,针对张量积问题进行讨论,首先我们介绍了基本知识,并给出了张量积问题是(s,t)弱易处理的充要条件,然后证明了线性张量积问题既不是(1,ln1)弱易处理也不是对数多项式易处理的.第四章,对前面几章进行总结,提出自己今后关于进一步研究的工作,并给出了几个自己暂时未解决的问题.
[Abstract]:In many disciplines, such as physics, chemistry, computer science, quantum mechanics, finance, economics and so on, we often encounter numerical approximation problems defined in d dimensional multivariable function space, where d can be very large, hundreds of thousands, Even larger, when d is very large, we usually use the functional of function (linear information) or the value of function (standard information) as the information construction algorithm to approach the problem under the specified error 蔚. Approximating the complexity of the multivariable numerical algorithm, denoted as Cnn, 蔚 DX, has been one of the main research directions of computational mathematics in recent years. The minimum number of information needed to approximate the multivariable problem algorithm is called the complexity of the information, which is denoted as n (蔚 / d). It is obvious that the complexity of information is a lower bound of algorithm complexity, especially for many linear problems, the complexity of information is proportional to the complexity of algorithm, so the research of complexity of algorithm focuses on the research of complexity of information. The easiness of multivariable problem is mainly studied how n (蔚 d) depends on 蔚 and d. When traditional multivariable problem is studied, it is easy to ignore the influence of dimension d when the given d is fixed. While n (蔚) may depend on the exponential growth of d, the complexity of multivariate problems needs a lot of new research. In 1994, Professor Wozniakowski, a Polish mathematician, put forward many new ideas and theories on the easiness of multivariable problems, such as, The intractability, strong tractable, weak tractability, polynomial tractability, weak and quasi-polynomial tractability, weak and quasi-polynomial tractability and logarithmic polynomials of multivariable problems are easy to deal with. Many scholars have studied and obtained a great deal of results. In this paper, the logarithmic polynomial easiness and weakly easiness of multivariable problems are studied in the average frame. The main work of this paper includes the following chapters: the first chapter briefly introduces the research background and development history of complexity and processability of information and algorithm, and gives some basic concepts, symbols and results of complexity needed in this paper. In the second chapter, we mainly discuss the controllability of multivariable problem under the average frame, and give the necessary and sufficient condition that the multivariable problem is logarithmic polynomial easy and weak easy to deal with, and then for the special weighted approximation problem, We prove that the weighted approximation problem S is lnk weakly easy to deal with and is equivalent to the standard information under linear information. In the third chapter, we discuss the tensor product problem under the average frame. Firstly, we introduce the basic knowledge and give the necessary and sufficient conditions for the tensor product problem to be weakly easy to deal with. Then it is proved that the linear tensor product problem is neither weakly easy to deal with nor logarithmic polynomial to deal with. In the fourth chapter, the author summarizes the previous chapters, puts forward his future work on further research, and gives some unsolved problems for the time being.
【学位授予单位】：安徽大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O241.5

【相似文献】