信号处理中一类非线性方程组的快速求解

在声纳和雷达信号处理中,需要求解一类维数可变的非线性方程组,这类方程组具有混合三角多项式方程组形式.由于该问题有很多解,且其对应的最小二乘问题有很多局部极小点,用牛顿法等传统的迭代法很难找到有物理意义的解.若把它化为多项式方程组,再用解多项式方程组的符号计算方法或现有的同伦方法求解,由于该问题规模太大而不能在规定的时间内求解,而当考虑的问题维数较大时,利用已有的方法甚至根本无法求解.综合利用我们提出的解混合三角多项式方程组的混合同伦方法和保对称的系数参数同伦方法,我们给出该类问题一种有效的求解方法.利用这种方法,可以达到实时求解的目的,满足实际问题的需要.     

直接多胞体同伦方法求解混合三角多项式方程组

混合三角多项式方程组是科学工程计算中常见的一类非线性方程组,它的每项由一部分变元及另一部分变元的三角函数构成.文章主要考虑利用直接多胞体同伦方法求解混合三角多项式方程组.数值结果表明文中的方法优于已有的求混合三角多项式方程组全部解的数值方法.     

基于Bregman距离函数的可靠性分析

针对概率结构可靠性问题,引入Bregman距离函数,建立了基于同伦算法(HM)的可靠性分析模型.利用极限状态方程,将可靠性指标求解转化为一个非线性约束优化问题.结合同伦思想的基本理论和Bregman距离函数,构造同伦方程组,采用路径跟踪算法对该方程组进行求解.通过相应的数值算例探讨了不同函数形式以及不同程度非线性问题的可靠性计算,并与其他方法计算结果进行了对比,分析结果表明该模型能够有效求解概率结构可靠性问题.     

解非光滑方程组的广义数值延拓算法(I)---基本理论

本文研究了求解B-可微方程组的广义数值延拓算法的基本理论.其基本出发点是利用同伦延拓思想,建立相应的非光滑同伦方程组,论证其跟踪路径的存在唯一性及连续性.据此,在另文中进一步获得了广义数值延拓算法的适定性、收敛性,进而将新算法应用于几类重要的规划问题.     

基于连续同伦的多方对策之Nash均衡点的机械化求解方法

Nash定理证明非合作n人矩阵对策一定有混合平衡解,现有文献多讨论n=2时混合平衡解的求法,一般用优化或逼近的方法.文章给出了一种机械化求解方法,通过构造非合作多人矩阵对策的混合平衡局势所满足的多项式方程组,应用方程组求解软件由此可直接求出多人对策的问题的各种混合平衡解.     

Reid-Zhi符号数值混合消元方法的一个应用

将Reid和Zhi提出的符号数值混合消元方法应用于求解多项式优化问题,将多项式优化问题转化为矩阵最小特征值求解问题,并在Maple软件中实现了算法.     

Legendre多项式法求一类变阶数分数阶微分方程数值解

本文利用Legendre多项式求解一类变分数阶微分方程.结合Legendre多项式,给出三种不同类型的微分算子矩阵.通过微分算子矩阵,将原方程转化一系列矩阵的乘积.最后离散变量,将矩阵的乘积转化为代数方程组,通过求解方程组,从而得到原方程的数值解.数值算例验证了本方法的高度可行性和准确性.     

解非光滑方程组的广义数值延拓算法(Ⅰ)──基本理论

本文研究了求解Ｂ－可微方程组的广义数值延拓算法的基本理论．其基本出发点是利用同伦廷拓思想,建立相应的非光滑同伦方程组,论证其跟踪路径的存在唯一性及连续性．据此,在另文中进一步获得了广义数值延拓算法的适定性、收敛性,进而将新算法应用于几类重要的规划问题．     

用Zernike多项式进行波面拟合的一种新算法

该文提出了一种用于计算全息数字波面干涉仪中实现波面Ｚｅｒｎｉｋｅ多项式拟合的精确算法。该算法不同于传统的直接构造方程和Ｇｒａｍ－Ｓｃｈｍｉｄｔ正交化方法,而是用Ｈｏｕｓｅｈｏｌｄｅｒ变换对矛盾方程的广义增广矩阵进行正交三角化,直接求解拟合系数。它避免了构造法方程组,从而避免了以前的方法因构造的法方程组出现严重病态而引入的计算误差,并且易于编程,因而是一种比较理想的实现Ｚｅｒｎｉｋｅ多项式拟合的算法     

一般形式的奇异对偶积分方程组正交多项式求解法

基于Jacobi正交多项式法,直接求解一般形式的对偶积分方程组,将对偶积分方程组中的未知函数,表示成n次Jacobi正交多项式级数,用正交多项式将奇异对偶积分方程组,化成线性代数方程组,通过求解级数中的各项系数,由此给出奇异对偶积分方程组的一般性解,并严格证明了奇异对偶积分方程组和由它化成的线性代数方程组的等价性,解的存在性和解的表示形式不唯一性．本文给出的理论解和解法,可供求解复杂的数学、物理、软科学中的混合边值问题应用．     

Dynamic Enumeration of All Mixed Cells

The polyhedral homotopy method, which has been known as a powerful numerical method for computing all isolated zeros of a polynomial system, requires all mixed cells of the support of the system to construct a family of homotopy functions. The mixed cells are reformulated in terms of a linear inequality system with an additional combinatorial condition. An enumeration tree is constructed among a family of linear inequality systems induced from it such that every mixed cell corresponds to a unique feasible leaf node, and the depth-first search is applied to the enumeration tree for finding all the feasible leaf nodes. How to construct such an enumeration tree is crucial in computational efficiency. This paper proposes a dynamic construction of an enumeration tree, which branches each parent node into its child nodes so that the number of feasible child nodes is expected to be small; hence we can prune many subtrees which do not contain any mixed cell. Numerical results exhibit that the proposed dynamic construction of an enumeration tree works very efficiently for large scale polynomial systems; for example, it generated all mixed cells of the cyclic-15 problem for the first time in less than 16 hours.     

Computing curve intersection by homotopy methods

Intersection problems are fundamental in computational geometry, geometric modeling and design and manufacturing applications, and can be reduced to solving polynomial systems. This paper introduces two homotopy methods, i.e. polyhedral homotopy method and linear homotopy method, to compute the intersections of two plane rational parametric curves. Extensive numerical examples show that computing curve intersection by homotopy methods has better accuracy, efficiency and robustness than by the Ehrlich-Aberth iteration method. Finally, some other applications of homotopy methods are also presented.     

Computing curve intersection by homotopy methods

Intersection problems are fundamental in computational geometry, geometric modeling and design and manufacturing applications, and can be reduced to solving polynomial systems. This paper introduces two homotopy methods, i.e. polyhedral homotopy method and linear homotopy method, to compute the intersections of two plane rational parametric curves. Extensive numerical examples show that computing curve intersection by homotopy methods has better accuracy, efficiency and robustness than by the Ehrlich–Aberth iteration method. Finally, some other applications of homotopy methods are also presented.     

Computing singular solutions to nonlinear analytic systems

Summary A method to generate an accurate approximation to a singular solution of a system of complex analytic equations is presented. Since manyreal systems extend naturally tocomplex analytic systems, this porvides a method for generating approximations to singular solutions to real systems. Examples include systems of polynomials and systems made up of trigonometric, exponential, and polynomial terms. The theorem on which the method is based is proven using results from several complex variables. No special conditions on the derivatives of the system, such as restrictions on the rank of the Jacobian matrix at the solution, are required. The numerical method itself is developed from techniques of homotopy continuation and 1-dimensional quadrature. A specific implementation is given, and the results of numerical experiments in solving five test problems are presented.     

Regenerative cascade homotopies for solving polynomial systems

A key step in the numerical computation of the irreducible decomposition of a polynomial system is the computation of a witness superset of the solution set. In many problems involving a solution set of a polynomial system, the witness superset contains all the needed information. Sommese and Wampler gave the first numerical method to compute witness supersets, based on dimension-by-dimension slicing of the solution set by generic linear spaces, followed later by the cascade homotopy of Sommese and Verschelde. Recently, the authors of this article introduced a new method, regeneration, to compute solution sets of polynomial systems. Tests showed that combining regeneration with the dimension-by-dimension algorithm was significantly faster than naively combining it with the cascade homotopy. However, in this article, we combine an appropriate randomization of the polynomial system with the regeneration technique to construct a new cascade of homotopies for computing witness supersets. Computational tests give strong evidence that regenerative cascade is superior in practice to previous methods.     

Birkhoff型三角插值

1 引言 Birkhoff三角插值是近年来比较活跃的一个研究课题,涉及Birkhoff三角插值的研究文献也很多(如G.G.Lorentz~([1]),沈燮昌~([2])等综合性文章).     

Incomplete Gröbner basis as a preconditioner for polynomial systems

Precondition plays a critical role in the numerical methods for large and sparse linear systems. It is also true for nonlinear algebraic systems. In this paper incomplete Gröbner basis (IGB) is proposed as a preconditioner of homotopy methods for polynomial systems of equations, which transforms a deficient system into a system with the same finite solutions, but smaller degree. The reduced system can thus be solved faster. Numerical results show the efficiency of the preconditioner.     

Solving systems of polynomial equations by bounded and real homotopy

Summary The homotopy method for solving systems of polynomial equations proposed by Chow, Mallet-Paret and Yorke is modified in two ways. The first modification allows to keep the homotopy solution curves bounded, the second one to work with real polynomials when solving a system of real equations. For the first method numerical results are presented.     

Application of homotopy perturbation methods for solving systems of linear equations

In this paper, homotopy perturbation methods (HPMs) are applied to obtain the solution of linear systems, and conditions are deduced to check the convergence of the homotopy series. Moreover, we have adapted the Richardson method, the Jacobi method, and the Gauss-Seidel method to choose the splitting matrix. The numerical results indicate that the homotopy series converges much more rapidly than the direct methods for large sparse linear systems with a small spectrum radius.