Error Bounds for Zeros of a Polynomial Based Upon Gerschgorin's Theorems

ABSTRACT

Given N approximations to the zeros of an Nth-degree polynomial, N circular regions in the complex z-plane are determined whose union contains all the zeros, and each connected component of this union consisting of K such circular regions contains exactly K zeros. The bounds for the zeros provided by these circular regions are not excessively pessimistic; that is, whenever the approximations are sufficiently well separated and sufficiently close to the zeros of this polynomial, the radii of these circular regions are shown to overestimate the errors by at most a modest factor simply related to the configuration of the approximations. A few numerical examples are included.

REFERENCES

• 1: Duane A. Adams, A stopping criterion for polynomial root finding, Communications of the ACM, v.10 n.10, p.655-658, Oct. 1967 [doi>10.1145/363717.363775]
• 2: AITKN, A.C. Determinants and Matrices, 9th ed. Oliver and Boyd, London, 1956, p. 119.
• 3: BIRKOFF, GEORGE D. An elementary double inequality for the roots of an algebraic equation having greatest absolute value. Bull. Amer. Math. Soe. 21 (1916), 494-495.
• 4: BURNSIDE, W.S.,ANDPANTON, A.W. The Theory of Equations.Longmans, Green and Co., London, 1886, pp. 297-298.
• 5: DXNIELS, J.W. Correcting approximations to multiple roots of polynomials. Numer. Math. 9 (1966), 99-102.
• 6: P. Henrici , Bruce O. Watkins, Finding zeros of a polynomial by the Q-D algorithm, Communications of the ACM, v.8 n.9, p.570-574, Sept. 1965 [doi>10.1145/365559.365619]
• 7: MXRDEN, M. Geometry of Zeros. Amer. Math. Soc.,Providence, R. I., 1966.
• 8: SMITH, B.T. ZERPOL, a zero finding algorithm for polynomials using Laguerre's method. Proc. 1967 Army Numerical Analysis Conference, Madison, Wis., May 1967 (Rep. 67-3, US Army Res. Office--Durham, Durham, N. C., Nov. 1967), pp. 153-174.
• 9: Error bounds, based upon Gerschgorin's theorems, for the zeros of a polynomiah Tech. Rep. 9, Dep. of Computer Sci., U. of Toronto, Toronto, Ontario, July 1969 (Ph.D. thesis).
• 10: SPITZEXRT, A. A generalization of Hermite's interpolation formula. Amer. Math. Mon. 67 (1960), 42-46.
• 11: STAFF, INSTITUTE OF COMPUTER SCIENCE, UNIVERSITY OF TORONTO. Programmer's Reference Manual for the IBM 7094-II Computer, 2nd ed., Vol. II. University of Toronto, Toronto, Ontario, 1968.
• 12: TAUSSKY, O., .A.ND MARCUS, M. Eigenvalues of finite matrices. In Todd, J., E d., A Survey of Numerical Analysis, McGraw-Hill, New York, 1962, pp. 279-313.
• 13: Richard F. Thomas, Jr. , Peter Henrici, Corrections to numerical data on Q-D algorithm, Communications of the ACM, v.9 n.5, p.322-323, May 1966 [doi>10.1145/355592.365600]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Number-theoretic computations (e.g., factoring, primality testing)

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Error analysis

General Terms:
Measurement, Performance, Reliability, Theory, Verification