naginterfaces.library.zeros.poly_​complex_​fpml

naginterfaces.library.zeros.poly_complex_fpml(a, itmax=30, polish=1)

poly_complex_fpml finds all the roots of a complex polynomial equation, using a fourth-order convergent modification of Laguerre’s method.

For full information please refer to the NAG Library document for c02aa

https://support.nag.com/numeric/nl/nagdoc_30.2/flhtml/c02/c02aaf.html

Parameters

acomplex, array-like, shape $(n+1)$

$a\left[\text{i}\right]$ must contain the coefficient of $z^{n-\text{i}}$, for $\text{i}=0,1,\dots ,n$.

itmaxint, optional

The maximum number of iterations to be performed.

polishint, optional

Specifies the polishing technique used to refine root approximations.

$polish=0$

No polishing.

$polish=1$

Single iteration of Newton’s method.

$polish=2$

Iterative refinement using the compensated Horner’s method.

See also Selecting a Polishing Process.

Returns

zcomplex, ndarray, shape $\left(n\right)$

$z[\text{j}-1]$ holds the approximation of the root $z_{\text{j}}$, for $\text{j}=1,2,\dots ,n$.

berrfloat, ndarray, shape $\left(n\right)$

$berr[\text{j}-1]$ holds the relative backward error, $\eta \left(z_{\text{j}}\right)$, for $\text{j}=1,2,\dots ,n$.

condfloat, ndarray, shape $\left(n\right)$

$cond[\text{j}-1]$ holds the condition number, $\kappa \left(z_{\text{j}}\right)$, for $\text{j}=1,2,\dots ,n$.

convint, ndarray, shape $\left(n\right)$

$conv[\text{j}-1]$ indicates the convergence status of the root approximation, $z_{\text{j}}$, for $\text{j}=1,2,\dots ,n$.

$conv[j-1]\ge 0$

Successfully converged after $conv[j-1]$ iterations.

$conv[j-1]=-1$

Failed to converge after $itmax$ iterations.

$conv[j-1]=-2$

Overflow was encountered.

Note: if $polish=2$, $conv$ refers to convergence in the compensated polishing process.

Raises

NagValueError

(errno $1$)

On entry, the complex variable $a\left[0\right]=(0.0,0.0)$.

(errno $2$)

On entry, $n=⟨value⟩$.

Constraint: $n\ge 1$.

(errno $3$)

On entry, $itmax=⟨value⟩$.

Constraint: $itmax\ge 1$.

(errno $4$)

On entry, $polish=⟨value⟩$.

Constraint: $polish=0$, $1$ or $2$.

(errno $5$)

Convergence has failed for at least one root approximation.

(errno $6$)

poly_complex_fpml encountered overflow during at least one root approximation.

Notes

poly_complex_fpml attempts to find all the roots of the $n$th degree complex polynomial equation

$$P\left(z\right)=a_0{z}^n+a_1{z}^{n-1}+a_2{z}^{n-2}+\cdots +a_{n-1}z+a_n=0\text{.}$$

The roots are located using a modified form of Laguerre’s method, as implemented by Cameron (2018). An implicit deflation strategy is employed, which allows for high accuracy even when solving high degree polynomials. Linear ($n=1$) and quadratic ($n=2$) problems are obtained via the ‘standard’ closed formulae.

First, initial estimates of the roots are made using a method proposed by Bini (1996), which selects complex numbers along circles of suitable radii. Updates to each root approximation $z_{\text{j}}$, for $\text{j}=1,2,\dots ,n$, are then made using the iterative formula from Petković et al. (1997):

$${\hat{z}}_j=z_j-\frac{n}{G_j\pm \sqrt{(n-1)(n{H}_j-G_j^2)}}\text{,}$$

where

$$G_j=\frac{P^{\prime }\left(z_j\right)}{P\left(z_j\right)}-\sum _{1\text{;}\text{i}\ne j}^n\frac{1}{(z_j-z_{\text{i}})}\text{and}{H}_j=-{\left(\frac{P^{\prime }\left(z_j\right)}{P\left(z_j\right)}\right)}^{\prime }-\sum _{1\text{;}\text{i}\ne j}^n\frac{1}{{(z_j-z_{\text{i}})}^2}\text{.}$$

The nearest ${\hat{z}}_j$ to the current approximation is used, by selecting the sign that maximizes the denominator of the correction term. The subtraction of the sum terms when computing $G_j$ and $H_j$ determines the implicit deflation strategy of the modified Laguerre method.

The relative backward error of a root approximation $z_j$ is given by

$$\eta \left(z_j\right)=\frac{\left|P\left(z_j\right)\right|}{\alpha \left(z_j\right)}\text{,}$$

where $\alpha$ is the perturbed polynomial

$$\alpha \left(z\right)=\sum _0^n(3.8\text{k}+1)\left|a_{n-\text{k}}\right|{\left|z\right|}^{\text{k}}\text{.}$$

A root approximation is deemed to have converged if $\eta \left(z_j\right)\le 2\times$ machine precision, at which point updates of that root cease. If the stopping criterion holds, then the computed root is the exact root of a polynomial whose coefficients are no more perturbed than the floating-point computation of $P\left(z_j\right)$.

The condition number of each root is also computed, as a measure of sensitivity to changes in the coefficients of the polynomial. It is given by

$$\kappa \left(z_j\right)=\frac{\alpha \left(z_j\right)}{\left|z_j\right|\left|P^{\prime }\left(z_j\right)\right|}\text{.}$$

Root approximations can be further refined with optional ‘polishing’ processes. A simple polishing process is provided that carries out a single iteration of Newton’s method, which proves quick yet often effective. Alternatively, a compensated polishing process from Cameron and O’Neill (2019) can be applied. This iterative method combines the implicit deflation of the modified Laguerre method, with the accuracy of evaluating polynomials and their derivatives using the compensated Horner’s method from Graillat et al. (2005). Compensated polishing yields approximations with a limiting accuracy as if computed in twice the working precision.

It is recommended that you read Selecting a Polishing Process for advice on selecting an appropriate polishing process.

References

Bini, D A, 1996, Numerical computation of polynomial zeros by means of Aberth’s method, Numerical Algorithms (13), 179–200, Springer US

Cameron, T R, 2018, An effective implementation of a modified Laguerre method for the roots of a polynomial, Numerical Algorithms, Springer US, https://doi.org/10.1007/s11075-018-0641-9

Cameron, T R and O’Neill, A, 2019, On a compensated polishing technique for polynomial root solvers, To be published,

Graillat, S, Louvet, N, and Langlois, P, 2005, Compensated Horner scheme, Technical Report, Université de Perpignan Via Domitia

Petković, M, Ilić, S, and Tričković, S, 1997, A family of simultaneous zero-finding methods, Computers & Mathematics with Applications (Volume 34) (10), 49–59, https://doi.org/10.1016/S0898-1221(97)00206-X

Wilkinson, J H, 1959, The evaluation of the zeros of ill-conditioned polynomials. Part I, Numerische Mathematik (Volume 1) (1), 150–166, Springer-Verlag

See also

naginterfaces.library.examples.zeros.poly_complex_fpml_ex.main()