On a compensated Ehrlich-Aberth method for the accurate computation of all polynomial roots

Electronic Transactions on Numerical Analysis

article

Thomas R. Cameron¹  Stef Graillat² 

[1] Department of Mathematics;Sorbonne UniversitÃl’

关键词: polynomial evaluation;    error-free transformations;    polynomial roots;    backward error;    forward error;    rounding error analysis;   

DOI  :  10.1553/etna_vol55s401

学科分类：数学（综合）

来源: Kent State University * Institute of Computational Mathematics

【 摘 要 】

In this article, we use the complex compensated Horner method to derive a compensated Ehrlich-Aberth method for the accurate computation of all roots, real or complex, of a polynomial. In particular, under suitable conditions, we prove that the limiting accuracy for the compensated Ehrlich-Aberth iterations is as accurate as if computed in twice the working precision and then rounded to the working precision. Moreover, we derive a running error bound for the complex compensated Horner method and use it to form robust stopping criteria for the compensated Ehrlich-Aberth iterations. Finally, extensive numerical experiments illustrate that the backward and forward errors of the root approximations computed via the compensated Ehrlich-Aberth method are similar to those obtained with a quadruple precision implementation of the Ehrlich-Aberth method with a significant speed-up in terms of computation time.

【 授权许可】

Unknown