A condition number theorem for underdetermined polynomial systems

Author:
Jérôme Dégot

Journal:
Math. Comp. **70** (2001), 329-335

MSC (2000):
Primary 65H10

Published electronically:
July 10, 2000

MathSciNet review:
1458220

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

The condition number of a numerical problem measures the sensitivity of the answer to small changes in the input. In their study of the complexity of Bézout's theorem, M. Shub and S. Smale prove that the condition number of a polynomial system is equal to the inverse of the distance from this polynomial system to the nearest ill-conditioned one. Here we explain how this result can be extended to underdetermined systems of polynomials (that is with less equations than unknowns).

**1.**Bernard Beauzamy and Jérôme Dégot,*Differential identities*, Trans. Amer. Math. Soc.**347**(1995), no. 7, 2607–2619. MR**1277095**, 10.1090/S0002-9947-1995-1277095-1**2.**Jean-Pierre Dedieu,*Approximate solutions of numerical problems, condition number analysis and condition number theorem*, The mathematics of numerical analysis (Park City, UT, 1995) Lectures in Appl. Math., vol. 32, Amer. Math. Soc., Providence, RI, 1996, pp. 263–283. MR**1421339****3.**James Weldon Demmel,*On condition numbers and the distance to the nearest ill-posed problem*, Numer. Math.**51**(1987), no. 3, 251–289. MR**895087**, 10.1007/BF01400115**4.**C. Eckart, G. Young,*The approximation of one matrix by another of lower rank*, Psychometrika**1**, (1936), pp 211-218.**5.**Bruce Reznick,*An inequality for products of polynomials*, Proc. Amer. Math. Soc.**117**(1993), no. 4, 1063–1073. MR**1119265**, 10.1090/S0002-9939-1993-1119265-2**6.**Michael Shub and Steve Smale,*Complexity of Bézout’s theorem. I. Geometric aspects*, J. Amer. Math. Soc.**6**(1993), no. 2, 459–501. MR**1175980**, 10.1090/S0894-0347-1993-1175980-4

Retrieve articles in *Mathematics of Computation*
with MSC (2000):
65H10

Retrieve articles in all journals with MSC (2000): 65H10

Additional Information

**Jérôme Dégot**

Affiliation:
Lycée Fénelon, 2, rue de l’éperon, 75006 Paris, France

Email:
jerome.degot@wanadoo.fr

DOI:
http://dx.doi.org/10.1090/S0025-5718-00-00934-0

Received by editor(s):
August 13, 1996

Published electronically:
July 10, 2000

Article copyright:
© Copyright 2000
American Mathematical Society