Método de Aberth

El método de Aberth , o método de Aberth-Ehrlich o método de Ehrlich-Aberth , llamado así por Oliver Aberth ^{[ 1 ]} y Louis W. Ehrlich, ^{[ 2 ]} es un algoritmo de búsqueda de raíces desarrollado en 1967 para la aproximación simultánea de todas las raíces de un polinomio univariado .

Este método converge cúbicamente, lo que supone una mejora respecto al método de Durand-Kerner , otro algoritmo para aproximar todas las raíces a la vez, que converge cuadráticamente. ^{[ 1 ] [ 2 ]} (Sin embargo, ambos algoritmos convergen linealmente en múltiples ceros . ^{[ 3 ]} )

Este método se utiliza en MPSolve , que es el software de referencia para aproximar todas las raíces de un polinomio con una precisión arbitraria.

Dejar${\displaystyle p(x)=p_{n}x^{n}+p_{n-1}x^{n-1}+\cdots +p_{1}x+p_{0}}$sea ​​un polinomio univariado de grado${\displaystyle n}$con coeficientes reales o complejos. Entonces existen números complejos${\displaystyle z_{1}^{*},\,z_{2}^{*},\dots,z_{n}^{*}}$, las raíces de${\displaystyle p(x)}$, que dan la factorización :

${\displaystyle p(x)=p_{n}\cdot (x-z_{1}^{*})\cdot (x-z_{2}^{*})\cdots (x-z_{n}^{*}).}$

Aunque esos números son desconocidos, los límites superior e inferior de sus valores absolutos se pueden calcular a partir de los coeficientes del polinomio. Ahora se puede elegir${\displaystyle n}$números distintos en el plano complejo —distribuidos aleatoriamente o uniformemente— de tal manera que sus valores absolutos estén dentro de los mismos límites. (Además, si los ceros son simétricos, los puntos de partida no deben ser exactamente simétricos a lo largo del mismo eje, ya que esto puede impedir la convergencia). ^{[ 1 ]} Un conjunto de tales números se denomina aproximación inicial del conjunto de raíces de${\displaystyle p(x)}$Esta aproximación se puede mejorar iterativamente utilizando el siguiente procedimiento.

Dejar${\displaystyle z_{1},\dots ,z_{n}\in \mathbb {C} }$sean las aproximaciones actuales de los ceros de${\displaystyle p(x)}$. Luego, números de compensación${\displaystyle w_{1},\dots ,w_{n}\in \mathbb {C} }$se calculan como

${\displaystyle w_{k}={\frac {\frac {p(z_{k})}{p'(z_{k})}}{1-{\frac {p(z_{k})}{p'(z_{k})}}\cdot \sum _{j\neq k}{\frac {1}{z_{k}-z_{j}}}}},}$

dónde${\displaystyle p'(z_{k})}$es la derivada polinómica de${\displaystyle p}$evaluado en el punto${\displaystyle z_{k}}$.

El siguiente conjunto de aproximaciones de raíces de${\displaystyle p(x)}$es entonces${\displaystyle z_{1}-w_{1},\dots,z_{n}-w_{n}}$La calidad de la aproximación actual se puede medir mediante los valores del polinomio o mediante el tamaño de los desplazamientos.

Conceptually, this method uses an electrostatic analogy, modeling the approximated zeros as movable negative point charges, which converge toward the true zeros, represented by fixed positive point charges.^[1] A direct application of Newton's method to each approximated zero will often cause multiple starting points to incorrectly converge to the same root. The Aberth method avoids this by also modeling the repulsive effect the movable charges have on each other. In this way, when a movable charge has converged on a zero, their charges will cancel out, so that other movable charges are no longer attracted to that location, encouraging them to converge to other "unoccupied" zeros. (Stieltjes also modeled the positions of zeros of polynomials as solutions to electrostatic problems.)

Inside the formula of the Aberth method one can find elements of Newton's method and the Durand–Kerner method. Details for an efficient implementation, esp. on the choice of good initial approximations, can be found in Bini (1996).^[3]

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.^[4]

The iteration formula is the univariate Newton iteration for the function

${\displaystyle F(x)={\frac {p(x)}{\prod _{j=1;\,j\neq k}^{n}(x-z_{j})}}}$

If the values ${\displaystyle z_{1},\dots,z_{n}}$ are already close to the roots of ${\displaystyle p(x)}$, then the rational function ${\displaystyle F(x)}$ is almost linear with a dominant root close to ${\displaystyle z_{k}}$ and poles at ${\displaystyle 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 ${\displaystyle z_{k}}$ has a wide region of attraction.

The Newton step ${\displaystyle {\tfrac {F(x)}{F'(x)}}}$ in the univariate case is the reciprocal value to the logarithmic derivative

${\displaystyle {\begin{aligned}{\frac {F'(x)}{F(x)}}&={\frac {d}{dx}}\ln |F(x)|\\&={\frac {d}{dx}}{\big (}\ln |p(x)|-\sum _{j=1;\,j\neq k}^{n}\ln |x-z_{j}|{\big )}\\&={\frac {p'(x)}{p(x)}}-\sum _{j=1;\,j\neq k}^{n}{\frac {1}{x-z_{j}}}\end{aligned}}}$

Thus, the new approximation is computed as

${\displaystyle z_{k}'=z_{k}-{\frac {F(z_{k})}{F'(z_{k})}}=z_{k}-{\frac {1}{{\frac {p'(z_{k})}{p(z_{k})}}-\sum _ {j=1;\,j\neq k}^{n}{\frac {1}{z_{k}-z_{j}}}}}\,,}$

which is the update formula of the Aberth–Ehrlich method.

• MPSolve: Un paquete para el cálculo numérico de raíces de polinomios. Uso gratuito con fines científicos.