A condition number theorem for underdetermined polynomial systems
Author:
Jérôme Dégot
Journal:
Math. Comp. 70 (2001), 329335
MSC (2000):
Primary 65H10
Published electronically:
July 10, 2000
MathSciNet review:
1458220
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: 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 illconditioned 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
(96c:05009), http://dx.doi.org/10.1090/S00029947199512770951
 2.
JeanPierre
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
(98a:65062)
 3.
James
Weldon Demmel, On condition numbers and the distance to the nearest
illposed problem, Numer. Math. 51 (1987),
no. 3, 251–289. MR 895087
(88i:15014), http://dx.doi.org/10.1007/BF01400115
 4.
C. Eckart, G. Young, The approximation of one matrix by another of lower rank, Psychometrika 1, (1936), pp 211218.
 5.
Bruce
Reznick, An inequality for products of
polynomials, Proc. Amer. Math. Soc.
117 (1993), no. 4,
1063–1073. MR 1119265
(93e:11058), http://dx.doi.org/10.1090/S00029939199311192652
 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
(93k:65045), http://dx.doi.org/10.1090/S08940347199311759804
 1.
 B. Beauzamy, J. Dégot, Differential identities, Trans. Amer. Math. Soc. 347, (1995), no. 7, pp 26072619. MR 96c:05009
 2.
 JP. Dedieu, Approximate solutions of numerical problems, condition number analysis and condition number theorems, The mathematics of numerical analysis. Lectures in Appl. Math., vol. 32, Amer. Math. Soc., Providence, RI, 1996. MR 98a:65062
 3.
 J. Demmel, On condition numbers and the distance to the nearest illposed problem, Num. Math. 51, (1987), pp 251289. MR 88i:15014
 4.
 C. Eckart, G. Young, The approximation of one matrix by another of lower rank, Psychometrika 1, (1936), pp 211218.
 5.
 B. Reznick, An inequality for products of polynomials, Proc. Amer. Math. Soc. 117 (1993), 10631073. MR 93e:11058
 6.
 M. Shub, S. Smale, Complexity of Bézout's theorem: geometric aspects, Journal of the Amer. Math. Soc. 6 (1993), pp 459501. MR 93k:65045
Similar Articles
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/S0025571800009340
PII:
S 00255718(00)009340
Received by editor(s):
August 13, 1996
Published electronically:
July 10, 2000
Article copyright:
© Copyright 2000
American Mathematical Society
