2026-03-07T00:47:05Z https://ipsj.ixsq.nii.ac.jp/oai

oai:ipsj.ixsq.nii.ac.jp:00059690 2025-01-20T06:33:06Z 5471:5480:5482

Approximate Greatest Common Divisor of Multivariate Polynomials and Its Application to III-Conditioned Systems of Algebraic Equations Approximate Greatest Common Divisor of Multivariate Polynomials and Its Application to III-Conditioned Systems of Algebraic Equations Masa-AkiOchi Matu-TarowNoda Tateaki, Sasaki Masa-Aki, Ochi Matu-Tarow, Noda Tateaki, Sasaki （IPSJ Best Paper Award、論文賞受賞） Let F F and D be multivariate polynomials andεbe a small positive number 0 < ε < < 1. If F=DF+△F where △F　is a polynomial with coefficients that are O(ε)-smaller than those of F D is called an approximate divisor of F of accuracy c. Given multivariate polynomials F and G an algorithm is proposed for calculating with accuracyεthe approximate greatest common divisor (GCD) of F and G. The algorithm is a naive extension of the conventional Euclidean algorithm but it is necessary to treat the polynomials carefully. As an application of the approximate GCD of multivariate polynomials the solution of a system of algebraic equations {F_1(x y . . . z)=0 . . . F_r(x y . . . z)=0} is considered where F_i and F_j i≠j have a non-trivial approximately common divisor. Such a system is ill-conditioned for conventional numerical methods and is transformed to a well-con-ditioned system by calculating approximate GCD's. A method is also given for determining the initial approximations of the roots for numerical iterative calculation. The proposed method is tested by using several examples and the results are very good. Let F, F and D be multivariate polynomials andεbe a small positive number,0 < ε < < 1. If F=DF+△F, where △F　is a polynomial with coefficients that are O(ε)-smaller than those of F, D is called an approximate divisor of F of accuracy c. Given multivariate polynomials F and G, an algorithm is proposed for calculating with accuracyεthe approximate greatest common divisor (GCD) of F and G. The algorithm is a naive extension of the conventional Euclidean algorithm, but it is necessary to treat the polynomials carefully. As an application of the approximate GCD of multivariate polynomials, the solution of a system of algebraic equations {F_1(x, y, . . . , z)=0,. . . , F_r(x, y, . . ., z)=0} is considered, where F_i and F_j, i≠j, have a non-trivial approximately common divisor. Such a system is ill-conditioned for conventional numerical methods, and is transformed to a well-con-ditioned system by calculating approximate GCD's. A method is also given for determining the initial approximations of the roots for numerical iterative calculation. The proposed method is tested by using several examples, and the results are very good. 情報処理学会 1991-12-31 eng journal article https://ipsj.ixsq.nii.ac.jp/records/59690 1882-6652 AA00700121 Journal of Information Processing 14 3 292 300 https://ipsj.ixsq.nii.ac.jp/record/59690/files/IPSJ-JIP1403009.pdf application/pdf 1.1 MB 1993-12-31