Study On Symbolic Numerical Algorithm In Solving Polynomial System

Many problems in scientific computation can be transformed to compute the polynomial system. Symbolic computation and numerical computation are two types of computation methods. The symbolic computation has no error and can obtain the correct solution. However, the symbolic computation needs more storage space because of large symbolic expressions, which lowers the efficiency of symbolic algorithm and limits the application in pratical. Numerical computation obtains the approximate solution through interpolation, fitting and iteration methods. It is widely used to solve practical engineering problems because of high efficiency. But due to the constraints of ill-conditioned problem and approximate computation, the convergence slows down or even lost, and the correctness and reliabe of the result need to be verified. Aiming at the above mentioned problems, this thesis discusses some related computational problems in automated reasoning and scientific computing using hybrid symbolic numerical computation, analyzes and implements several efficient and reliable algorithms for those problems, and applies these algorithms to some engineering problems.The main innovation in this dissertation includes:1. An explicit formula is proposed to compute the dual space of a nonlinear system at a singular point, and an augmented system is constructed through the dual space.Meanwhile, the Jacobian matrix of augmented system was full rank at the initial point,and then the algorithm recover quadratical convergence of Newton’s iteration. In addition, we obtain the multiplicity of the singular solution form the dimension of the dual space. At last, we use the algorithm for solving the ill problem in power flow system.2. Based on the homotopy continuation technique and the Newton interval algorithm, an efficient and reliable hybrid algorithm is presented for isolating the real roots of semi-algebraic system. This method first obtains the isolated real roots interval of polynomial system, and then uses interval extension to verify the establishment of inequalities in the semi-algebraic system. This algorithm overcomes the shortcoming of the symbolic algorithm, which only computes the small size system and rational system.The algorithm is efficient and can be parallelized.3. A new ideal is proposed for solving the real roots of the transcendental functionsfrom circuit design problem. The method first replaces the exponential function by its Taylor expansion, and then obtains the approximate real roots of the polynomial systems through the homotopy method. At last, the real roots of transcendental functions are found based on these approximate real roots using the Newton’s method.The method overcomes the low efficiency of the interval Newton’s method.4. For computing the real roots of the no pure-dimensional polynomial system, a new system is obtained based on a full rank matrix. In the new system, the dimension of the connect component is equal to the difference between the number of equations and the number of system variables. Then construct a homotopy which guarantees finding a point on each connected component. The algorithm overcomes the shortcoming of the existing algorithms which can not obtain all the real roots. The algorithm can be parallelized for computing the different connect component. Meanwhile, based on the property of Lyapunov function, the Lyapunov function of a differential system is obtained through solving a real root of a positive dimensional system. The experiment shows that this method is more efficient than the existing methods.5. Through the relationship among the Sylvster, Dixon, and the Mixed Cayley-Sylveter resultant matrices, the relation of the three kinds of resultants are proved which shows that the difference among them is only a polynomial factor, and the variable of the polynomial is the coefficients of the system. Meanwhile, a recursive algorithm is proposed for constructing the Cayley-Sylveter matrix.