多项式近似因式分解的可信验证

The Verification of Approximate Polynomial Factorization

摘要: 众所周知，系数有扰动多项式的因式分解是不连续的。因此，传统的多项式因式分解对于数值计算来说是一个不适定问题。本文利用区间算法，研究多项式近似因式分解的可信计算。给定一个实多项式，本文利用已有算法计算给定多项式其因式分解流形结构，设计算法输出在该因式分解流形结构中一系数为区间的因式分解。算法保证，在该区间因式分解中存在一系数为实数的因式分解，其所对应的多项式为在确定的因式分解流形结构中与给定多项式残差最小的多项式。

Abstract: It is well-known for a polynomial with perturbed coefficients, its factorization is discontinuous. Therefore, the traditional polynomial factorization is an ill-posed problem for numerical computation. This paper is to study the trusted computing of polynomial approximate factorization on the basis of interval algorithm. Given a polynomial of real coefficients, this paper uses the existing algorithm to compute the structure of factorization manifold, and provides a verification algorithm to compute a factorization with interval coefficients in the computed factorization manifold structure. The algorithm is guaranteed that there exists a real factorization within this interval factorization such that the corresponding polynomial of the real factorization is the polynomial with the minimum residual in the computed decomposition manifold structure.