Aberth method

Let p(x)=p_nx^n+p_{n-1}x^{n-1}+\cdots+p_1x+p_0 be a univariate polynomial of degree n with real or complex coefficients. Then there exist complex numbers z^*_1,\,z^*_2,\dots,z^*_n, the roots of p(x), that give the factorization: :p(x)=p_n\cdot(x-z^*_1)\cdot(x-z^*_2)\cdots(x-z^*_n). Although those numbers are unknown, upper and lower bounds for their absolute values are computable from the coefficients of the polynomial. Now one can pick n distinct numbers in the complex plane—randomly or evenly distributed—such that their absolute values are within the same bounds. (Also, if the zeros are symmetrical, the starting points must not be exactly symmetrical along the same axis, as this can prevent convergence.) The updates of the roots may be executed as a simultaneous Jacobi-like iteration where first all new approximations are computed from the old approximations or as a sequential Gauss–Seidel-like iteration that uses each new approximation from the time it is computed. A very similar method is the Newton-Maehly method. It computes the zeros one after another, but instead of an explicit deflation it divides by the already acquired linear factors on the fly. The Aberth method is like the Newton-Maehly method for computing the last root while pretending you have already found the other ones. ==Derivation from Newton's method==

The iteration formula is the univariate Newton iteration for the function :F(x)=\frac{p(x)}{\prod_{j=1;\,j\ne k}^n(x-z_j)} If the values z_1,\dots,z_n are already close to the roots of p(x), then the rational function F(x) is almost linear with a dominant root close to z_k and poles at z_1,\dots,z_{k-1},z_{k+1},\dots,z_n that direct the Newton iteration away from the roots of p(x) that are close to them. That is, the corresponding basins of attraction get rather small, while the root close to z_k has a wide region of attraction. The Newton step \tfrac{F(x)}{F'(x)} in the univariate case is the reciprocal value to the logarithmic derivative :\begin{align} \frac{F'(x)}{F(x)} &= \frac{d}{dx}\ln|F(x)|\\ &= \frac{d}{dx}\big(\ln|p(x)|-\sum_{j=1;\,j\ne k}^n\ln|x-z_j|\big)\\ &= \frac{p'(x)}{p(x)}-\sum_{j=1;\,j\ne k}^n\frac1{x-z_j} \end{align} Thus, the new approximation is computed as :z_k'=z_k-\frac{F(z_k)}{F'(z_k)}=z_k-\frac1{\frac{p'(z_k)}{p(z_k)}-\sum_{j=1;\,j\ne k}^n\frac1{z_k-z_j}}\,, which is the update formula of the Aberth–Ehrlich method. ==Literature==