Improvement on the Lehmer-Schur root detection method (Q1323000)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Improvement on the Lehmer-Schur root detection method |
scientific article |
Statements
Improvement on the Lehmer-Schur root detection method (English)
0 references
10 May 1994
0 references
The Schur-Cohn transformation is an important tool used to find how many roots of a polynomial are contained inside the unit circle of the complex plane. Using the same basic idea, a two-dimensional bisection scheme is derived for locating a certain root of a very high degree polynomial (typically \(N > 100)\). By successive applications of this transformation, the root is isolated to lie within a thin concentric annulus of width \(\eta \ll 1\) centered at the origin. This procedure determines the magnitude (or modulus) of the root with accuracy \(\eta\). The phase (or argument) of the root along this annulus is found by slightly perturbing the origin by an amount \(\varepsilon<1\) and constructing a new concentric annulus. The intersection of the two annuli yields an estimate of the root with accuracy \(2 \eta/ \varepsilon \). The root searching scheme is global and is faster than the Lehmer-Schur direct method, since in the proposed scheme the origin shifting is only needed twice for all roots, compared with many more in the Lehmer-Schur algorithm.
0 references
zeros of polynomials
0 references
Schur-Cohn transformation
0 references
two-dimensional bisection scheme
0 references
very high degree polynomial
0 references
root searching scheme
0 references
Lehmer-Schur direct method
0 references