积分曲线可信计算的理论，算法及其应用

Reliable computing algorithm of the integral curves plays an important role in the hybrid systems software of complex physical systems. Recently, the sum-of-squares (SOS) representation and rational vector recovery techniques are the main methods for exact safety verification of hybrid systems. However, they are inefficiency and applicable only to middle and small systems in practice. This project aims to build the Gap theory of algorithms for the integral curves by numerical approximate computations combined with sleeve bound computing, based on the variable-stepsize and variable-order (VSVO) piecewise analytical method (PAM) scheme of Taylor series method. For the two-dimensional vector field, the classic nonlinear hybrid systems, and part of the high-dimensional nonlinear systems, we present the stable and efficient algorithms for the approximate integral curves with error controlling. The features include a new research direction of the quantitative theory of error controllable computation in the intermediate expression of the integral curves, and measure the error controlling bound on integral curves and reliable bound of the given region compared with the traditional approaches, provide the basic theory of the correctness guarantee for analysis and verification of embedded software based on computer algebraic methods and tools. In recent years, our work shows the possibility of this direction.

积分曲线可信计算是复杂物理系统中混成系统软件的核心问题。近年来，在积分曲线数值近似积分方法的误差控制与可信判定方面，主要基于多项式平方和与有理向量重构技术，面临的问题是计算效率不高，只能解决中小规模问题。本项目结合数值近似计算方法和误差界的思想与技术，系统地提出采用变步长与变阶的泰勒级数分片解析方法的积分曲线误差控制Gap理论，并获取误差可控的近似数值解，针对二维向量场、经典非线性混成系统、部分高维非线性系统等较复杂的情形设计出高效算法。有别于传统的数值近似计算误差定性分析，本项目将建立积分曲线数值近似计算的中间过程精度控制定量理论，并建立度量积分曲线带误差界与给定限制区域的可信界，为基于计算机代数的理论和工具研究分析、验证嵌入式软件的正确性提供基础理论保证。目前我们已经取得了一些阶段性的结果，说明了基于符号与数值混合计算的积分曲线误差控制这种设想是可能实现的。

积分曲线可信计算是复杂物理系统中混成系统软件的核心问题。结合数值近似计算方法和误差界的思想与技术，系统地提出了采用变步长与变阶的泰勒级数分片解析方法的积分曲线误差控制Gap理论，并获取了误差可控的符号解。从给定点出发的向量场积分曲线分析了带误差界分片解析表达式度量的定量理论，主要结果包括：1）针对目前广泛讨论的Van der Pol问题，将美国加州理工学院Prajna博士学位论文中“危险区域”的界0.4，Summers博士学位论文中“危险区域”的界0.8，提高到1.2082（并获得不能超过1.209的上界，否则积分曲线进入“危险区域”）；2）针对Van der Pol问题多个约束区域的情形进行了研究，将Prajna在其博士学位论文中扰动半径区间为[-0.25, 0.25]，项目组扩大到[-0.8, 0.8]。此外，项目组研究了针对积分曲线数值计算中涉及的符号行列式问题，提出基于近似插值算法的符号行列式计算方法，定义了符号行列式变元次数矩阵，并设计了次数估计方法，分析了求解Vandermonde方程组的误差可控性，并给出了一个维数约化的方法；针对基于模型的复杂工业产品建模技术算法，进一步将积分曲线可信计算理论与算法推广到微分代数系统中，结合欧拉方法和保群算法得到了更高精度的保群算法；针对混沌系统中的经典控制问题，提出了一种基于快速下降控制方法的保群算法，此方法使受控混沌系统能够快速稳定到相空间的一个不动点。众所周知，算术表达式的精确计算是确保各类复杂计算正确性的基础。对于大多数主流软件来说，计算过程中“不正确的舍入误差”与机器误差，导致计算结果不稳定。针对此类计算不稳定问题，提出了中间运算的精度自适应技术，进而给出算术表达式的一种可信计算算法。与此同时，并将相关研究结果应用于光学技术等前沿领域。项目执行期间，负责人荣获2016年四川省海外高层次留学人才。项目组已发表（录用）论文12篇，申请了3项发明专利，投稿论文5篇；指导硕士生4名，协助指导博士生5名，在读研究生10余名。综上所述，项目实施过程中严格按照研究计划执行，达到并超过预期计划目标。