论文标题
一类递归不平等的计算研究
A computational study of a class of recursive inequalities
论文作者
论文摘要
我们从证明理论和计算理论的角度研究了满足特定递归不平等的非负实数序列的收敛性能。我们首先建立了许多有关收敛速度的结果，设置了可计算率的条件，并且在不可计算的情况下提供相应的亚稳定率。然后，我们演示了如何应用上述定量结果来从非线性分析中的一系列证明中提取计算信息。在这里，我们既提供有关亚级别算法的新案例研究，概述了最近的结果，每种结果都涉及我们主要递归不平等的实例。本文包含了从证明理论和数学分析中的所有相关概念的定义，因此，我们希望普通受众可以访问它。
We examine the convergence properties of sequences of nonnegative real numbers that satisfy a particular class of recursive inequalities, from the perspective of proof theory and computability theory. We first establish a number of results concerning rates of convergence, setting out conditions under which computable rates are possible, and when not, providing corresponding rates of metastability. We then demonstrate how the aforementioned quantitative results can be applied to extract computational information from a range of proofs in nonlinear analysis. Here we provide both a new case study on subgradient algorithms, and give overviews of a selection of recent results which each involve an instance of our main recursive inequality. This paper contains the definitions of all relevant concepts from both proof theory and mathematical analysis, and as such, we hope that it is accessible to a general audience.
