确定多项式实根的人工鱼群算法

本文提出了一种确定多项式实根的人工鱼群算法。利用随机K分法,对多项式的实根区间进行优化,来确定多项式方程全部实根位置。算例结果表明,所提出的确定多项式实根的人工鱼群算法能够快速地实现任意多项式的实根分离,随机K分法能够较快地优化多项式实根所在区间,求出任意多项式的全部实根。该方法具有求解精度高、收敛速度快等优点。     

一类三角形几何不等式的自动证明

讨论了一类只含三角函数的三角形几何不等式的自动证明问题。运用代数方法将其有理化,在不新增加根式的条件下将问题转换为一个二元多项式不等式的证明,设计的基于胞腔分解和实根分离的算法实现了二元多项式不等式的自动证明,输出的证明过程可以手工验证或借助一些数学软件进行理解。实验表明上述算法对一大批具有相当难度,特别是关于三角函数的几何不等式十分高效,并且能够解决三角形内角的任意有理倍数函数的不等式机器证明问题。     

基于区间—遗传算法求解非线性方程组

将非线性方程组的求解转化为函数优化问题,结合遗传算法的群体搜索、全局收敛的优点,及区间算法特有的解的存在性检验准则,提出了一种区间—遗传算法。在迭代计算过程中,区间算法为遗传算法搜索提供可靠区域,同时遗传算法为区间算法提供安全的初始区域。数值实验表明,该算法能够在较大范围的初始区间内快速,可靠地迭代得到高精度的区间解,是求解非线性方程组的一种有效的算法。     

基于模算术系数解析的稀疏插值算法

稀疏多元多项式插值是利用多项式的稀疏结构及其给定的插值点信息重构黑盒函数的一种有效策略，被广泛应用于科学和工程领域。传统的基于Prony方法的稀疏插值算法，其复杂度与多项式项数和次数相关，遇到大规模问题时由于执行多个高阶代数运算而效率较低。提出一种新的求解稀疏多元多项式插值问题的算法，核心操作是利用模算术解析单变元多项式的系数，避免了传统方法必需的高阶方程组求解、高次方程求根等。该算法设定一变元为主元，将黑盒多元多项式视为该主元的单变元多项式，通过解析主元的系数多项式在不同插值点处的函数值，进而重构这些系数多项式以恢复整个多元多项式。理论分析和数值实验表明了算法的有效性和可行性。     

基于Dixon结式和逐次差分代换的多项式秩函数探测方法

秩函数探测是循环程序终止性分析的重要方法，目前，已有很多研究者致力于为线性循环程序探测对应的线性秩函数，然而，针对具有多项式循环条件和多项式赋值的多项式型的循环，现有的秩函数探测方法还有所不足，解决方案大多是不完备的、或者具有较高的时间复杂度。针对现有工作对于多项式秩函数探测方法不足的问题，基于扩展Dixon结式（KSY方法）和逐次差分代换（SDS）方法，提出一种为多项式循环程序探测多项式型秩函数的方法。首先，将待探测的秩函数模板看作带参数系数的多项式，将秩函数的探测转换为寻找满足条件的参数系数的问题；然后，进一步将问题转换为判定相应的方程组是否有解的问题，至此，利用KSY方法中的扩展的Dixon结式，将问题更进一步简化为带参系数多项式（即结式）严格为正的判定问题；最后，利用SDS方法，找到一个充分条件，使得得到的结式严格为正，此时，可以获取满足条件的参数系数的取值，从而找到一个满足条件的秩函数，通过实验验证该秩函数探测方法的有效性。实验结果表明，利用该方法，可以有效地为多项式循环程序找到多项式秩函数，包括深度为d的多阶段多项式秩函数，与已有方法相比，该方法能够更高效地找到多项式秩函数，对于基于柱形代数分解（CAD）方法的探测方法因时间复杂度问题无法而应对的一些循环，利用所提方法能够在几秒内为这些循环找到秩函数。     

非线性方程求解的泛灰数学方法

在概述泛灰数的概念及其运算规则的基础上，介绍了泛灰数与区间数的转化，利用泛灰数的可扩展性对区间进行分析。根据对求解区间的泛灰函数性（如果在区间上有解，则0∈F（X）进行判定是否有解，剔除无解区间，细化有解区间，从而求解非线性方程的全部解，泛灰数不仅具有区间分析功能，且能解决区间分析所不能解决的问题，基于泛灰数的性质提出了求解非线性方程一种新方法。算例证明了算法的有效性，该方法已成功用于求解机构学问题。     

多项式函数型回归神经网络模型及应用

文中利用回归神经网络既有前馈通路又有反馈通路的特点，将网络隐层中神经元的激活函数设置为可调多项式函数序列，提出了多项式函数型回归神经网络新模型，它不但具有传统回归神经网络的特点，而且具有较强的函数逼近能力，针对递归计算问题，提出了多项式函数型回归神经网络学习算法，并将该网络模型应用于多元多项式近似因式分解，其学习算法在多元多项式近似分解中体现了较强的优越性，通过算例分析表明，该算法十分有效，收敛速度快，计算精度高，可适用于递归计算问题领域，该文所提出的多项式函数型回归神经网络模型及学习算法对于代数符号近似计算有重要的指导意义。     

定点算术数据通路的等价性检验方法

以vanishing多项式理想的极小强Gr-bner基为理论基础,提出一种针对定点算术数据通路的等价性检验方法.通过使用多项式函数建模定点数据通路的设计规范和寄存器传输级实现,将等价性检验问题转化为判断一个多项式函数是否为vanishing多项式、vanishing多项式理想的极小强Gr-bner基被用来有效地解决该问题.理论分析和实验结果表明,与现有的算法相比,该方法在时间消耗上具有一定的优势.     

求解一类凸优化问题的区间迭代算法

研究了一类非线性带约束的凸优化问题的求解.利用Kuhn-Tucker条件将凸优化问题等价地转化为多变元非线性方程组的求解问题.基于区间算术的包含原理及改进的Krawczyk区间迭代算法,提出一个求解凸优化问题的区间算法.对于目标函数和约束函数可微的凸优化,所提算法具有全局寻优的特性.在数值实验方面,与遗传算法、模式搜索法、模拟退火法及数学软件内置的求解器进行了比较,结果表明所提算法就此类凸优化问题能找到较多且误差较小的全局最优点.     

一个新的多项式实根分离算法

本文提出了分离多项式方程P(x)=0的实根的一个新的计算机代数算法,它解决了王湘浩教授在[1]中提出的用连分数变换分离有重根多项式的实根的问题.对于有重根的n次多项式P(x),该算法具有时间复杂性上界O(n~6L~3(|P|_0)),远远优于现有的解决同样问题的计算机代数算法的时间上界O(n~(10)+n~7L~3(|P|_0)).该算法已在计算机代数系统SAC-2上实现.上机实验的结果也初步证实了新算法的优越性.     

A constructive approach for finding arbitrary roots of polynomials by neural networks

This paper proposes a constructive approach for finding arbitrary (real or complex) roots of arbitrary (real or complex) polynomials by multilayer perceptron network (MLPN) using constrained learning algorithm (CLA), which encodes the a priori information of constraint relations between root moments and coefficients of a polynomial into the usual BP algorithm (BPA). Moreover, the root moment method (RMM) is also simplified into a recursive version so that the computational complexity can be further decreased, which leads the roots of those higher order polynomials to be readily found. In addition, an adaptive learning parameter with the CLA is also proposed in this paper; an initial weight selection method is also given. Finally, several experimental results show that our proposed neural connectionism approaches, with respect to the nonneural ones, are more efficient and feasible in finding the arbitrary roots of arbitrary polynomials.     

Structural Interval Reliability Algorithm Based on Bernstein Polynomials andEvidence Theory

Structural reliability is an important method to measure the safety performance of structures under the influence of uncertain factors. Traditional structural reliability analysis methods often convert the limit state function to the polynomial form to measure whether the structure is invalid. The uncertain parameters mainly exist in the form of intervals. This method requires a lot of calculation and is often difficult to achieve efficiently. In order to solve this problem, this paper proposes an interval variable multivariate polynomial algorithm based on Bernstein polynomials and evidence theory to solve the structural reliability problem with cognitive uncertainty. Based on the non-probabilistic reliability index method, the extreme value of the limit state function is obtained using the properties of Bernstein polynomials, thus avoiding the need for a lot of sampling to solve the reliability analysis problem. The method is applied to numerical examples and engineering applications such as experiments, and the results show that the method has higher computational efficiency and accuracy than the traditional linear approximation method, especially for some reliability problems with higher nonlinearity. Moreover, this method can effectively improve the reliability of results and reduce the cost of calculation in practical engineering problems.     

基于实数多项式的根值最小范数算法

在根值最小范数算法中须对复数多项式求根,计算量较大。针对此问题,提出了一种基于实数多项式的根值最小范数算法,该算法适用于均匀线性阵列。首先通过保角变换将分布在复平面单位圆的变量映射到实数轴的[-1,1]范围内,其能够将算法中的复数多项式转换为实数多项式;其次对该实数多项式求根,并从中选出[-1,1]范围内的根值;最后将筛选出的根值代入信号频谱函数中,根据频谱函数的值选择出最优的波达方向估值。理论分析说明本文算法比根值最小范数算法的时间复杂度低;仿真实验表明,与根值最小范数相比,在信号和噪声不相关时,本文算法的均方根误差略小,在信号和噪声相关时,随着信噪比的增加,本文算法的均方根误差逐渐变小。     

An algebraic criterion for robust stability of linear controlsystems

A new robust stability test for linear control systems is described. The condition at which robust stability is violated is transformed into an equivalent problem in which the existence of a real root of a multivariable polynomial is investigated. This multivariable problem is reduced to that of the solvability of a set of univariable polynomial equations in real numbers, for which a number of efficient numerical methods are available. The use of the method is illustrated in the design of feedback control for an open-loop unstable batch chemical reactor     

Estimation of nonlinear systems via a Chebyshev approximation approach

This paper proposes to decompose the nonlinear dynamic of a chaotic system with Chebyshev polynomials to improve performances of its estimator. More widely than synchronization of chaotic systems, this algorithm is compared to other nonlinear stochastic estimator such as Extended Kalman Filter (EKF) and Unscented Kalman Filter (UKF). Chebyshev polynomials orthogonality properties is used to fit a polynomial to a nonlinear function. This polynomial is then used in an Exact Polynomial Kalman Filter (ExPKF) to run real time state estimation. The ExPKF offers mean square error optimality because it can estimate exact statistics of transformed variables through the polynomial function. Analytical expressions of those statistics are derived so as to lower ExPKF algorithm computation complexity and allow real time applications. Simulations under the Additive White Gaussian Noise (AWGN) hypothesis, show relevant performances of this algorithm compared to classical nonlinear estimators.     

Bounds for an interval polynomial

We discuss the evaluation of the range of values of an interval polynomial over an interval. Several algorithms are proposed and tested on numerical examples. The algorithms are based on ideas by Cargo and Shiska [2] and Rivlin [4]. The one basic algorithm uses Bernstein polynomials. It is shown to converge to the exact bounds and it has furthermore the property that if the maximum respectively the minimum of the polynomials occurs at an endpoint of the interval then the bound is exact. This is a useful property in routines for polynomials zeros. The other basic method is based on the meanvalue theorem and it has the advantage that the degree of approximation required for a certain apriori tolerance is smaller than the degree required in the Bernstein polynomial case. The mean value method is shown to be at least quadratically convergent and the Bernstein polynomial method is shown to be at least linearly convergent.     

On the computing time of the continued fractions method

The maximum computing time of the continued fractions method for polynomial real root isolation is at least quintic in the degree of the input polynomial. This computing time is realized for an infinite sequence of polynomials of increasing degrees, each having the same coefficients. The recursion trees for those polynomials do not depend on the use of root bounds in the continued fractions method. The trees are completely described. The height of each tree is more than half the degree. When the degree exceeds one hundred, more than one third of the nodes along the longest path are associated with primitive polynomials whose low-order and high-order coefficients are large negative integers. The length of the forty-five percent highest order coefficients and of the ten percent lowest order coefficients is at least linear in the degree of the input polynomial multiplied by the level of the node. Hence the time required to compute one node from the previous node using classical methods is at least proportional to the cube of the degree of the input polynomial multiplied by the level of the node. The intervals that the continued fractions method returns are characterized using a matrix factorization algorithm.     

Numerical solution of a system of fuzzy polynomials by fuzzy neural network

In this paper, a new approach for solving systems of fuzzy polynomials based on fuzzy neural network (FNN) is presented. This method can also lead to improve numerical methods. In this work, an architecture of fuzzy neural networks is also proposed to find a real root of a system of fuzzy polynomials (if exists) by introducing a learning algorithm. Finally, we illustrate our approach by numerical examples.     

Interval Arithmetic in Cylindrical Algebraic Decomposition

Cylindrical algebraic decomposition requires many very time consuming operations, including resultant computation, polynomial factorization, algebraic polynomial gcd computation and polynomial real root isolation. We show how the time for algebraic polynomial real root isolation can be greatly reduced by using interval arithmetic instead of exact computation. This substantially reduces the overall time for cylindrical algebraic decomposition.