APPROXIMATE GCD AND ITS APPLICATION TO ILL-CONDITIONED ALGEBRAIC EQUATIONS

[摘要] We describe two algorithms of approximate GCD (greatest common divisor) for polynomials with coefficients of floating-point numbers. One is for univariate polynomials and the other for multivariate polynomials. The algorithms are careful extensions of the conventional Euclidean algorithm, and they are applied to solving ill-conditioned algebraic equations. Ill-conditioned univariate algebraic equations have multiple or close roots, and we can separate both multiple and close roots by successive calculation of approximate GCDs. We also consider an ill-conditioned system of algebraic equations which have an approximate common divisor. Conventional numeric root-finding methods such as Newton's method give no satisfactory result for such ill-conditioned systems. By using an approximate GCD algorithm for multivariate polynomials, the system is transformed into a well-conditioned one to which numeric methods are applied safely. Thus, we solve some numerically ill-conditioned problems by a combination of algebraic and numeric methods; we call such algorithms hybrid algorithms. This paper shows the importance and possible fruitfulness of the hybrid algorithm.

[发布日期] 1991-12-23

[效力级别]  Proceedings Paper

[关键词] SYMBOLIC COMPUTATION;NUMERIC COMPUTATION;ILL-CONDITIONED;ALGEBRAIC EQUATION