A Theory of Real Approximations, with Applications

精确几何计算（EGC）是求解非鲁棒数值计算最成功的方法之一。EGC的基础是{\em保证精度计算}，这是一种计算模式，其中每个数值数量可以计算到任何用户指定的精度。在过去的十年中，主要的软件库和许多健壮的算法和应用程序都是基于EGC原理实现的。现在缺少的是一种计算模型来捕捉这种模式。PI引入了一个{\em实逼近理论}来填补这一空白。该方法假设一个合适的可计数集合$\mathbb{F}$ $\mathbb{Z}\ib\mathbb{F}\ib\mathbb{R}$)的{\em可表示实数}，具有所有数值输入和输出都来自$\mathbb{F}$的属性。目前有两种理论直接解决了实际计算的具体性质：Weihrauch等人的TTE学派，以及Blum， Shub和Smale （BSS）的代数学派。PI的方法不同于这两所学校，但又与它们相辅相成。PI进一步引入了一个{\em数值计算模型}，被视为图灵模型和BSS模型之间的中间模型。该开发以经典复杂性理论为依据，但直接受到当前EGC软件开发的推动。研究课题包括：*实值逼近的可计算性和复杂性。通过诸如$NP$-完备性等主题，以及Blum， Shub和Smale的代数理论，建立了与标准复杂性理论的联系。* EGC软件实现的基本问题：动态建设性零边界、几何分离边界、近似求值的复杂性和精度敏感复杂性。其中一些问题（例如，零界限）涉及实验验证与理论研究的结合。实现是使用核心库完成的，核心库是PI正在进行的开源库项目。知识价值。其中一个解决了长期感兴趣的主题，即为实际计算及其复杂性提供基础。PI接近真实近似值的方法是简洁的，可以证明与当前的方法不同，出乎意料，但在计算实践中牢固地扎根。从设计上讲，这个新理论是一个EGC理论。但它也可以作为数值计算的基础，这是斯梅尔和其他人所呼吁的。更广泛的影响。通过将EGC应用于鲁棒性问题，这项工作有望影响计算科学和工程的许多领域。本研究中的实际工作作为核心库软件的一部分免费分发。这个具有独特接口模型的库被广泛应用，因为任何c++程序都可以调用它来保证准确性。保证精度计算的应用超出了非鲁棒性，从验证猜想到测试软件。与过去一样，PI积极参与到相关领域和更大的计算社区的各种扩展工作中。

Exact Geometric Computation (EGC) is one of the most successful approaches to nonrobust numerical computation. The basis of EGC is {\em guaranteed accuracy computation}, a computational mode in which each numerical quantity can be computed to any user-specified accuracy. In the last 10 years, major software libraries and many robust algorithms and applications have been implemented based on EGC principles. What is lacking is a model of computation to capture this mode. The PI introduces a {\em theory of real approximation} which fills this gap. The approach postulates a suitable countable set $\mathbb{F}$ $\mathbb{Z}\ib\mathbb{F}\ib\mathbb{R}$) of {\em representable reals}, with the property that all numerical input and output come from $\mathbb{F}$. Two current theories directly address the specific nature of real computation: the TTE School of Weihrauch and others, and the Algebraic School from Blum, Shub and Smale (BSS). The PI's approach is distinct from both schools, but complements them. The PI further introduces a {\em Numerical Computational Model}, seen as an intermediate model between the Turing model and the BSS model. The development is informed by classical complexity theory, yet directly motivated by current development of EGC software.Research topics include: * The computability and complexity of real approximation. Connections are made to standard complexity theory via such topics as $NP$-completeness, and also to the algebraic theory of Blum, Shub and Smale.* Fundamental questions motivated by the implementation of EGC software: dynamic constructive zero bounds, geometric separation bounds, complexity of approximate evaluation, and precision-sensitive complexity.Some of these questions (e.g., zero bounds) involve a combination of experimental validation with theoretical studies. Implementation is done using the Core Library, the PI's ongoing open-source library project.INTELLECTUAL MERIT.One addresses a topic of long-standing interest, namely, providing a foundation for real computation and its complexity. The PI's approach to real approximation is concise, provably distinct from current approaches, unexpected, yet firmly grounded in computing practice. The new theory is, by design, a theory for EGC. But it can also serve as a foundation for numerical computation, something which Smale and others have called for. BROADER IMPACT. Through the applications of EGC to robustness issues, this work is expected impact many areas of omputational science and engineering. The practical work in this research is distributed freely as part of the Core Library software. This library, with its unique interface model, is widely applicable because any C++program can invoke it to achieve guaranteed accuracy. Guaranteed accuracy computation has applications beyond nonrobustness, from verifying conjectures to testing software. The PI, as in the past, is actively engaged in various outreach efforts to related fields, and to the larger computing community.