论文标题
经典领域的新进展：多项式根 -
New Progress in Classic Area: Polynomial Root-squaring and Root-finding
论文作者
论文摘要
DLG的根平面迭代是由于1826年的蒲公英，并由Lobachevsky和Graeffe 1837重新发现，一直是19世纪及以后的单变量多项式P（x）的根找到的主要方法，但如今却不是如此，但由于这些迭代是严重的数值问题，因此不是如此。试图避免这些问题，我们发现了适用于牛顿的反比率-p'（x）/p（x）的迭代的简单而新颖的降低，与p（x）零零和反向多项式的功率总和的近似。可以基于牛顿的身份或库奇积分，可以独立于DLG迭代来设计和执行所得的多项式根界。在前一种情况下，计算涉及一组输入多项式的领先或尾部系数。在后一种情况下，我们必须扩展变量并增加算术计算成本，以确保数值稳定性。然而，至少对于快速的根部再填充，成本仍然可以管理，并且可以将算法应用于黑匣子多项式P（x） - 由黑匣子给出，以评估比率p'（x）/p（x），而不是通过其系数。这可以实现重要的计算益处，包括一组P（X）或甚至所有零的零的有效递归以及并发近似，可以快速评估输入多项式的加速度，并扩展到Matrix或多项矩阵的近似值，如果可以效率地逐渐数据，则可以进行a spress的效率。我们还回想起了我们最近的快速算法近似root Radii，即，与P（X）的零相对于根部或任何复杂值的根距离，并将其应用于多项式迭代的快速黑盒初始化，例如，通过功能迭代的方式，例如牛顿，牛顿，ehrlich's ehrlich's，ehrlich's and weerierstrass's and weerierstrass。
The DLG root-squaring iterations, due to Dandelin 1826 and rediscovered by Lobachevsky 1834 and Graeffe 1837, have been the main approach to root-finding for a univariate polynomial p(x) in the 19th century and beyond, but not so nowadays because these iterations are prone to severe numerical stability problems. Trying to avoid these problems we have found simple but novel reduction of the iterations applied for Newton's inverse ratio -p'(x)/p(x) to approximation of the power sums of the zeros of p(x) and its reverse polynomial. The resulting polynomial root-finders can be devised and performed independently of DLG iterations, based on Newton's identities or Cauchy integrals. In the former case the computation involve a set of leading or tailing coefficients of an input polynomial. In the latter case we must scale the variable and increase the arithmetic computational cost to ensure numerical stability. Nevertheless the cost is still manageable, at least for fast root-refinement, and the algorithms can be applied to a black box polynomial p(x)--given by a black box for the evaluation of the ratio p'(x)/p(x) rather than by its coefficients. This enables important computational benefits, including efficient recursive as well as concurrent approximation of a set of zeros of p(x) or even all of its zeros, acceleration where an input polynomial can be evaluated fast, and extension to approximation of the eigenvalues of a matrix or a polynomial matrix, being efficient if the matrix can be inverted fast, e.g., is data sparse. We also recall our recent fast algorithms for approximation of the root radii, that is, the distances to the roots from the origin or any complex value to the zeros of p(x), and apply it for fast black box initialization of polynomial root-finding by means of functional iterations, e.g., Newton's, Ehrlich's, and Weierstrass's.
