Locating real multiple zeros of a real interval polynomial

ABSTRACT

For a real interval polynomial F, we provide a rigorous method for deciding whether there exists a polynomial in F that has a multiple zero in a prescribed interval in R. We show that it is sufficient to examine a finite number of edge polynomials in F. An edge polynomial is a real interval polynomial such that the number of coefficients that are intervals is one. The decision method uses the property that a univariate polynomial is of degree one with respect to each coefficient regarded as a variable. Using this method, we can completely determine the set of real numbers each of which is a multiple zero of some polynomial in F.

REFERENCES

• 1: 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.
• 2: W. Boege , R. Gebauer , H. Kredel, Some examples for solving systems of algebraic equations by calculating Groebner, Journal of Symbolic Computation, v.2 n.1, p.83-98, March 1986 [doi>10.1006/jsco.1996.0042]
• 3: Robert M. Corless , Patrizia M. Gianni , Barry M. Trager , Stephen M. Watt, The singular value decomposition for polynomial systems, Proceedings of the 1995 international symposium on Symbolic and algebraic computation, p.195-207, July 10-12, 1995, Montreal, Quebec, Canada [doi>10.1145/220346.220371]
• 4: Robert M. Corless , Hiroshi Kai , Stephen M. Watt, Approximate computation of pseudovarieties, ACM SIGSAM Bulletin, v.37 n.3, September 2003 [doi>10.1145/990353.990359]
• 5: M. A. Hitz and E. Kaltofen, The Kharitonov theorem and its applications in symbolic mathematical computation, Proc. Workshop on Symbolic-Numeric Algebra for Polynomials (SNAP96), pp. 20--21, 1996.
• 6: 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]
• 7: 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]
• 8: 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.
• 9: N. K. Karmarkar , Y. N. Lakshman, On approximate GCDs of univariate polynomials, Journal of Symbolic Computation, v.26 n.6, p.653-666, Dec. 1998 [doi>10.1006/jsco.1998.0232]
• 10: 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.
• 11: Ronald G Mosier, Root neighborhoods of a polynomial, Mathematics of Computation, v.47 n.175, p.265-273, July 1986 [doi>10.2307/2008093]
• 12: Masayuki Noro , Taku Takeshima, Risa/Asir—a computer algebra system, Papers from the international symposium on Symbolic and algebraic computation, p.387-396, July 27-29, 1992, Berkeley, California, United States [doi>10.1145/143242.143362]
• 13: H. Sekigawa and K. Shirayanagi, On the Location of Zeros of an Interval Polynomial, Proc. International Workshop on Symbolic-Numeric Computation 2005 (SNC2005), pp. 144--165, 2005.
• 14: H. Sekigawa and K. Shirayanagi, On the location of zeros of a complex interval polynomial, Abstracts of Presentations of 11th International Conference on Applications of Computer Algebra (ACA'2005), p. 15, 2005.
• 15: H. Sekigawa and K. Shirayanagi, On the location of pseudozeros of a complex interval polynomial, Proc. Asian Symposium on Computer Mathematics (ASCM2005), pp. 231--234, 2005.
• 16: Kiyoshi Shirayanagi, An algorithm to compute floating point Gro¨bner bases, Proceedings of the Maple summer workshop and symposium on Mathematical computation with Maple V : ideas and applications: ideas and applications, p.95-106, July 1993, Ann Arbor, Michigan, United States
• 17: Kiyoshi Shirayanagi, Floating point Gro¨bner bases, Mathematics and Computers in Simulation, v.42 n.4-6, p.509-528, Nov. 1996
• 18: K. Shirayanagi and M. Sweedler, A theory of stabilizing algebraic algorithms, Technical Report 95-28, Mathematical Sciences Institute, Cornell University, 1995.
• 19: Kiyoshi Shirayanagi , Moss Sweedler, Remarks on automatic algorithm stabilization, Journal of Symbolic Computation, v.26 n.6, p.761-765, Dec. 1998 [doi>10.1006/jsco.1998.0238]
• 20: 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]
• 21: A. Terui and T. Sasaki, Approximate zero-points of real univariate polynomial with large error terms, J. Information Processing Society of Japan, Vol. 41, No. 4, pp. 974--989, 2000.
• 22: Zhi Lihong , Wu Wenda, Nearest singular polynomials, Journal of Symbolic Computation, v.26 n.6, p.667-675, Dec. 1998 [doi>10.1006/jsco.1998.0233]

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
convex set, interval polynomial, real multiple zero