Aberth method

From Wikipedia, the free encyclopedia

The Aberth-method, sometimes named Aberth-Ehrlich method is a root-finding algorithm for simultaneous approximation of all the root of a univariate polynomial. It is similar to the Weierstrass (Durand-Kerner) method, but uses a slightly different formula for the updates of the current approximations.

[edit] Description

Let $p(x)=p_nx^n+p_{n-1}x^{n-1}+\dots+p_1x+p_0$ be a univariate polynomial of degree n with real or complex coefficients. Let $z_1,\dots,z_n\in\mathbb C$ be the current approximations of the zeros of p(x). Then updates $w_1,\dots,w_n\in\mathbb C$ are computed as

$w_k=-\frac{\frac{p(x_k)}{p'(x_k)}}{1-\frac{p(x_k)}{p'(x_k)}\cdot \sum_{j\ne k}\frac1{z_k-z_j}}$ .

The next set of approximations of roots of p(x) is then $z_1+w_1,\dots,z_n+w_n$ .

Thus the Aberth method is a combination of Newton's method and the Weierstrass/Durand-Kerner method. Details for an efficient implementation, esp. on the choice of good initial approximations, are to be found in Bini (1996).

[edit] Derivation from Newton's method

The iteration formula is the univariate Newton iteration for the function

$F(x)=\frac{p(x)}{\prod_{j=0;\,j\ne k}^n(x-z_k)}$

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 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 bassins of attraction get rather small.

The Newton step in the univariate case is the reciprocal value to the logarithmic derivative

$\begin{matrix} \frac{F'(x)}{F(x)} &=&\frac{d}{dx}\ln|F(x)|\\ &=&\frac{d}{dx}\big(\ln|p(x)|-\sum_{j=0;\,j\ne k}^n\ln|x-z_j|\big)\\ &=&\frac{p'(x)}{p(x)}-\sum_{j=0;\,j\ne k}^n\frac1{x-z_j} \end{matrix}$

Thus,

$z_k'=z_k-\frac{F(x)}{F'(x)}=\frac1{\frac{p'(z_k)}{p(z_k)}-\sum_{j=0;\,j\ne k}^n\frac1{z_k-z_j}}$

results in the Aberth-Ehrlich iteration.

The iteration may be executed in a simultaneous Jacobi-like iteration where first all new approximations are computed from the old approximations or in a sequential Gauss-Seidel like iteration that uses each new approximation from the time it is computed.

[edit] Literature

Ehrlich, L. W. (1967). "A modified Newton method for polynomials". Comm. ACM 10(2): 107-108.
Aberth, O. (1973). "Iteration methods for finding all zeros of a polynomial simultaneously". Math. Comp. 27(122): 339-344.
Bini, Dario Andrea (1996). "Numerical computation of polynomial zeros by means of Aberth's method". Numerical Algorithms 13: 179-200.

Retrieved from "http://en.wikipedia.org../../../a/b/e/Aberth_method.html"

Category: Root-finding algorithms

Aberth method

From Wikipedia, the free encyclopedia

[edit] Description

[edit] Derivation from Newton's method

[edit] Literature

Views

Navigation

Search