naginterfaces.library.zeros.poly_​real

naginterfaces.library.zeros.poly_real(a, scal=True)

poly_real finds all the roots of a real polynomial equation, using a variant of Laguerre’s method.

Deprecated since version 27.1.0.0: poly_real is deprecated. Please use poly_real_fpml() instead. See also the Replacement Calls document.

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

https://support.nag.com/numeric/nl/nagdoc_30.3/flhtml/c02/c02agf.html

Parameters

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

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

scalbool, optional

Indicates whether or not the polynomial is to be scaled. See Further Comments for advice on when it may be preferable to set $scal=False$ and for a description of the scaling strategy.

Returns

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

The roots. Complex conjugate pairs of roots are stored in consecutive elements of $z$.

Raises

NagValueError

(errno $1$)

On entry, $a\left[0\right]=0.0$.

Constraint: $a\left[0\right]\ne 0.0$.

(errno $1$)

On entry, $n=⟨value⟩$.

Constraint: $n\ge 1$.

(errno $2$)

The iterative procedure has failed to converge. This error is very unlikely to occur. If it does, please contact NAG immediately, as some basic assumption for the arithmetic has been violated.

(errno $3$)

poly_real cannot evaluate $P\left(z\right)$ near some of its zeros without underflow. If this message occurs please contact NAG.

(errno $3$)

poly_real cannot evaluate $P\left(z\right)$ near some of its zeros without overflow. If this message occurs please contact NAG.

Notes

In the NAG Library the traditional C interface for this routine uses a different algorithmic base. Please contact NAG if you have any questions about compatibility.

poly_real attempts to find all the roots of the $n$th degree real 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, originally proposed by Smith (1967).

The method of Laguerre (see Wilkinson (1965)) can be described by the iterative scheme

$$L\left(z_k\right)=z_{k+1}-z_k=\frac{-nP\left(z_k\right)}{P^{\prime }\left(z_k\right)\pm \sqrt{H\left(z_k\right)}}\text{,}$$

where $H\left(z_k\right)=(n-1)[(n-1){\left(P^{\prime }\left(z_k\right)\right)}^2-nP\left(z_k\right)P^{\prime \prime }\left(z_k\right)]$ and $z_0$ is specified.

The sign in the denominator is chosen so that the modulus of the Laguerre step at $z_k$, viz. $\left|L\left(z_k\right)\right|$, is as small as possible. The method can be shown to be cubically convergent for isolated roots (real or complex) and linearly convergent for multiple roots.

The function generates a sequence of iterates $z_1,z_2,z_3,\dots$, such that $\left|P\left(z_{k+1}\right)\right|<\left|P\left(z_k\right)\right|$ and ensures that $z_{k+1}+L\left(z_{k+1}\right)$ ‘roughly’ lies inside a circular region of radius $\left|F\right|$ about $z_k$ known to contain a zero of $P\left(z\right)$; that is, $\left|L\left(z_{k+1}\right)\right|\le \left|F\right|$, where $F$ denotes the Fejér bound (see Marden (1966)) at the point $z_k$. Following Smith (1967), $F$ is taken to be $min(B,1.445nR)$, where $B$ is an upper bound for the magnitude of the smallest zero given by

$$B=1.0001\times min(\sqrt{n}L\left(z_k\right),\left|r_1\right|,{\left|a_n/a_0\right|}^{1/n})\text{,}$$

$r_1$ is the zero $X$ of smaller magnitude of the quadratic equation

$$\frac{P^{\prime \prime }\left(z_k\right)}{2n(n-1)}{X}^2+\frac{P^{\prime }\left(z_k\right)}{n}X+\frac{1}{2}P\left(z_k\right)=0$$

and the Cauchy lower bound $R$ for the smallest zero is computed (using Newton’s Method) as the positive root of the polynomial equation

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

Starting from the origin, successive iterates are generated according to the rule $z_{k+1}=z_k+L\left(z_k\right)$, for $k=1,2,3,\dots$, and $L\left(z_k\right)$ is ‘adjusted’ so that $\left|P\left(z_{k+1}\right)\right|<\left|P\left(z_k\right)\right|$ and $\left|L\left(z_{k+1}\right)\right|\le \left|F\right|$. The iterative procedure terminates if $P\left(z_{k+1}\right)$ is smaller in absolute value than the bound on the rounding error in $P\left(z_{k+1}\right)$ and the current iterate $z_p=z_{k+1}$ is taken to be a zero of $P\left(z\right)$ (as is its conjugate ${\overline{z}}_p$ if $z_p$ is complex). The deflated polynomial $\tilde{P}\left(z\right)=P\left(z\right)/(z-z_p)$ of degree $n-1$ if $z_p$ is real ($\tilde{P}\left(z\right)=P\left(z\right)/\left((z-z_p)(z-{\overline{z}}_p)\right)$ of degree $n-2$ if $z_p$ is complex) is then formed, and the above procedure is repeated on the deflated polynomial until $n<3$, whereupon the remaining roots are obtained via the ‘standard’ closed formulae for a linear ($n=1$) or quadratic ($n=2$) equation.

Note that quadratic_real(), cubic_real() and quartic_real() can be used to obtain the roots of a quadratic, cubic ($n=3$) and quartic ($n=4$) polynomial, respectively.

References

Marden, M, 1966, Geometry of polynomials, Mathematical Surveys (3), American Mathematical Society, Providence, RI

Smith, B T, 1967, ZERPOL: a zero finding algorithm for polynomials using Laguerre’s method, Technical Report, Department of Computer Science, University of Toronto, Canada

Thompson, K W, 1991, Error analysis for polynomial solvers, Fortran Journal (Volume 3) (3), 10–13

Wilkinson, J H, 1965, The Algebraic Eigenvalue Problem, Oxford University Press, Oxford