Univariate Factor Separation and Separation of Multiple/Close Root Factors ⁄
摘要
Given univariate polynomials F , G0 and H0 such that F = G0H0 + ∆0, k∆0k/kFk = e0 ? 1, we consider calculating polynomials G1 and H1, such that F = G1H1 + ∆1,k∆1k/kFk = e1 ? e0, where kPk denotes a norm of a polynomial P . We call this operation univariate factor separation. We give a quadratically convergent algorithm to calculate G1 and H1. Furthermore, we derive a condition of convergence of the factor separation algorithm and discuss the accuracy of factor separated. We apply the factor separation to separating multiple/close root factors accurately in two ways. In the first way, we perform the approximate square-free decomposition of F with low accuracy, obtaining multiple/close root factors crudely, then apply the factor separation algorithm. In the second way, we solve the equation F (x) = 0 numerically, obtaining approximate roots among which the multiple/close roots are of low accuracies. We combine these multiple/close root factors to a polynomial and use it as an initial factor for the factor separation algorithm.