非线性系统求解的误差可控算法及其应用

Solving nonlinear system is one of the basic problems in scientific computation and practical situations. Rapid development of science and technology makes an urgent request for more and more accuracy while numerical algorithms, as a traditional choice, will inevitably introduce errors. Reliable and stable algorithms for solving nonlinear systems guarantee their applications in high-risk and high-precision situations. Both Rump interval algorithm and alpha theory are main methods computing verified error bounds for the solutions of nonlinear systems. As for Newton method for simple roots of nonlinear systems, although alpha theory provides the convergence anlysis that only depends on initial values, its computational complexity is too high. Rump interval algorithm verifies the existence of solutions using interval operation, but does not have comprehensive convergence analysis in theory. This project will compare these two error controllable algorithms in sensitivity and precision, which will shed considerable light on the convergence analysis of Rump interval algorithms for computing single solutions of nonlinear systems and singular solutions of univariate nonlinear functions. Furthermore, this project will apply the theory and methods mentioned above to the verifying cases of greatest common divisor of approximated polynomials, factorization of approximated polynomial, eigenvalues of approximated structure matrix, and approximated algebraic interpolation.

非线性系统求解是科学计算与工程应用中的基本问题之一。数值算法可求解一般非线性系统，但计算结果不可避免存在误差。科技的迅猛发展对计算结果的准确性要求越来越高，设计可靠、稳定的非线性系统求解算法能为其在高风险、高精度领域的应用提供保障。Rump区间算法和alpha理论是非线性系统求解两类主要的误差可控算法，对计算非线性系统单根，alpha理论给出了牛顿法收敛的初始条件，但计算复杂度较高，而Rump区间算法是利用区间运算验证解的存在性，实际计算中比较实用，但理论上缺乏完整的收敛性分析。本项目拟比较这两类方法的敏感度和精度，利用比较的结果给出Rump区间算法求解非线性系统单根、单变量非线性函数多重根的收敛性分析。同时将非线性系统求解的相关理论、方法应用于近似多项式最大公因子、近似多项式因式分解、近似结构矩阵特征值以及近似代数插值的可信验证中。

非线性系统求解是科学计算与工程应用中的基本问题之一。非线性系统求解的误差可控算法能为其在高风险、高精度领域的应用提供保障。. 本项目在理论方面完善了Rump区间牛顿迭代法的收敛性分析，给出了仅利用非线性系统在初值近似值处的信息，Rump区间牛顿法的收敛的一个充分条件，并证明了在计算近似解的可信误差界的精度方面，alpha理论要高于Rump区间牛顿法。. 本项目在算法方面利用Rump 算法和Kantorovich定理，设计了计算近似多元多项式最近最大公因子、近似矩阵特征值及实验点集的代数插值函数的误差可控算法。具体如下：. (1) 设计算法输出给定多项式组相应的摄动区间多项式组，在该区间多项式组中一定存在实多项式组，该实多项式组是与给定实多项式组距离最近的具有非平凡最大公因子的多项式组。 . (2) 提出了计算矩阵特征值的Verifyeig算法。该算法输出给定矩阵的微小摄动区间矩阵及其可信误差界，以及该微小摄动区间矩阵高精度的特征值及其误差界。算法保证在微小摄动区间矩阵中存在实矩阵，在高精度特征值其误差界范围内，存在该实矩阵的一个几何重数为q的精确特征值。项目组将Verifyeig算法改进，提出了矩阵亏损特征值及其重根结构的可信验证算法。算法保证，给定矩阵在输出的可信误差界范围内一定存在一矩阵，使得输出的给定矩阵高精度特征值为其精确特征值。算法同时验证了特征值的几何重数和最小约当块的维数。. (3) 设计算法输出给定实验点集的容许点集及其可信误差界一个低次多项式。在输出的容许点集的可信误差界范围内存在另一容许点集，输出的低次多项式在该容许点集上精确消逝。.项目执行期间，项目组共发表学术论文5篇，其中SCI检索论文3篇，EI检索论文2篇。本项目提出的相关理论和算法可应用于可信软件的研发中。