Aberth method

The Aberth method, or Aberth–Ehrlich method or Ehrlich–Aberth method, named after Oliver Aberth and Louis W. Ehrlich, is a root-finding algorithm developed in 1967 for simultaneous approximation of all the roots of a univariate polynomial.

This method converges cubically, an improvement over the Durand–Kerner method, another algorithm for approximating all roots at once, which converges quadratically. (However, both algorithms converge linearly at multiple zeros.)

This method is used in MPSolve, which is the reference software for approximating all roots of a polynomial to an arbitrary precision.

Description

Let

p

(

x

)

=

p

n

x

n

+

p

n

−

1

x

n

−

1

+

⋯

+

p

1

x

+

p

0

{\displaystyle p(x)=p_{n}x^{n}+p_{n-1}x^{n-1}+\cdots +p_{1}x+p_{0}}

be a univariate polynomial of degree

n

{\displaystyle n}

with real or complex coefficients. Then there exist complex numbers

z

1

∗

,

z

2

∗

,

…

,

z

n

∗

{\displaystyle z_{1}^{*},\,z_{2}^{*},\dots ,z_{n}^{*}}

, the roots of

p

(

x

)

{\displaystyle p(x)}

, that give the factorization:

p

(

x

)

=

p

n

⋅

(

x

−

z

1

∗

)

⋅

(

x

−

z

2

∗

)

⋯

(

x

−

z

n

∗

)

.

{\displaystyle 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

{\displaystyle 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.) A set of such numbers is called an initial approximation of the set of roots of

p

(

x

)

{\displaystyle p(x)}

. This approximation can be iteratively improved using the following procedure.

Let

z

1

,

…

,

z

n

∈

C

{\displaystyle z_{1},\dots ,z_{n}\in \mathbb {C} }

be the current approximations of the zeros of

p

(

x

)

{\displaystyle p(x)}

.