The nearest polynomial with a zero in a given domain

ABSTRACT

For a real univariate polynomial f and a bounded closed domain D ⊂ C whose boundary C is a simple closed curve of finite length and is represented by a piecewise rational function, we provide a rigorous method for finding the real univariate polynomial f such that f has a zero in D and ||f -- f||∞ is minimal. First, we prove that the absolute value of every coefficient of f -- f is ||f -- f∞ with at most one exception. Using this property and the representation of C, we reduce the problem to solving systems of algebraic equations, each of which consists of two equations with two variables. Furthermore, every equation is of degree one with respect to one of the two variables.

REFERENCES

• 1: L. V. Ahlfors. Complex Analysis (3rd edition). McGraw-Hill, 1979.
• 2: A. C. Bartlett, C. V. Hollot and Huang Lin. Root Location of an Entire Polytope of Polynomials: It Suffices to Check the Edges. Mathematics of Controls, Signals and Systems, Vol.1, pp.61--71, 1988.
• 3: S. P. Bhattacharyya , H. Chapellat , L. H. Keel, Robust Control: The Parametric Approach, Prentice Hall PTR, Upper Saddle River, NJ, 1995
• 4: M. A. Hitz and E. Kaltofen. The Kharitonov Theorem and its Applications in Symbolic Mathematical Computation. In Proc. Workshop on Symbolic-Numeric Algebra for Polynomials (SNAP96), pp.20--21, 1996.
• 5: Markus A. Hitz , Erich Kaltofen, Efficient algorithms for computing the nearest polynomial with constrained roots, Proceedings of the 1998 international symposium on Symbolic and algebraic computation, p.236-243, August 13-15, 1998, Rostock, Germany [doi>10.1145/281508.281624]
• 6: Markus A. Hitz , Erich Kaltofen , Y. N. Lakshman, Efficient algorithms for computing the nearest polynomial with a real root and related problems, Proceedings of the 1999 international symposium on Symbolic and algebraic computation, p.205-212, July 28-31, 1999, Vancouver, British Columbia, Canada [doi>10.1145/309831.309937]
• 7: E. Kaltofen. Efficient Algorithms for Computing the Nearest Polynomial with Parametrically Constrained Roots and Factors. Lecture at the Workshop on Symbolic and Numerical Scientific Computation (SNSC '99), 1999.
• 8: V. L. Kharitonov. Asymptotic Stability of an Equilibrium Position of a Family of Systems of Linear Differential Equations. Differentsial 'nye Uravneniya, Vol.14, No.11, pp.2086--2088, 1978.
• 9: Ronald G Mosier, Root neighborhoods of a polynomial, Mathematics of Computation, v.47 n.175, p.265-273, July 1986 [doi>10.2307/2008093]
• 10: L. Qiu , E. J. Davison, A simple procedure for the exact stability robustness computation of polynomials with affine coefficient perturbations, Systems & Control Letters, v.13 n.5, p.413-420, Dec. 1989 [doi>10.1016/0167-6911(89)90108-4 ]
• 11: A. Rantzer. Stability Conditions for Polytopes of Polynomials. IEEE Trans. Auto. Control, Vol.37, No. 1, pp.79--89, 1992.
• 12: Nargol Rezvani , Robert M. Corless, The nearest polynomial with a given zero, revisited, ACM SIGSAM Bulletin, v.39 n.3, September 2005 [doi>10.1145/1113439.1113442]
• 13: Walter Rudin, Real and complex analysis, 3rd ed., McGraw-Hill, Inc., New York, NY, 1987
• 14: Hiroshi Sekigawa , Kiyoshi Shirayanagi, Locating real multiple zeros of a real interval polynomial, Proceedings of the 2006 international symposium on Symbolic and algebraic computation, July 09-12, 2006, Genoa, Italy [doi>10.1145/1145768.1145819]
• 15: H. Sekigawa and K. Shirayanagi. On the Location of Zeros of an Interval Polynomial. In Symbolic-Numeric Computation, edited by Dongming Wang and Lihong Zhi, pp.167--184, Birkhä user, 2007.
• 16: Hans J. Stetter, The nearest polynomial with a given zero, and similar problems, ACM SIGSAM Bulletin, v.33 n.4, p.2-4, 12/01/1999 [doi>10.1145/500457.500458]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Algebraic algorithms

General Terms:
Algorithms, Theory

Keywords:
perturbation, polynomial, zero