Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 

 

On perturbation of roots of homogeneous algebraic systems


Authors: S. Tanabé and M. N. Vrahatis
Journal: Math. Comp. 75 (2006), 1383-1402
MSC (2000): Primary 12D10, 65H10
Published electronically: March 31, 2006
MathSciNet review: 2219034
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: A problem concerning the perturbation of roots of a system of homogeneous algebraic equations is investigated. The question of conservation and decomposition of a multiple root into simple roots are discussed. The main theorem on the conservation of the number of roots of a deformed (not necessarily homogeneous) algebraic system is proved by making use of a homotopy connecting initial roots of the given system and roots of a perturbed system. Hereby we give an estimate on the size of perturbation that does not affect the number of roots. Further on we state the existence of a slightly deformed system that has the same number of real zeros as the original system in taking the multiplicities into account. We give also a result about the decomposition of multiple real roots into simple real roots.


References [Enhancements On Off] (What's this?)

  • 1. Paul Alexandroff and Heinz Hopf, Topologie, Erster Band. Grundbegriffe der mengentheoretischen Topologie, Topologie der Komplexe, topologische Invarianzsätze und anschliessende Begriffsbildunge n, Verschlingungen im n-dimensionalen euklidischen Raum, stetige Abbildungen vo n Polyedern, Chelsea Publishing Co., New York, 1965 (German). MR 0185557
  • 2. V. I. Arnol′d, S. M. Guseĭn-Zade, and A. N. Varchenko, Singularities of differentiable maps. Vol. I, Monographs in Mathematics, vol. 82, Birkhäuser Boston, Inc., Boston, MA, 1985. The classification of critical points, caustics and wave fronts; Translated from the Russian by Ian Porteous and Mark Reynolds. MR 777682
  • 3. Dimitris J. Kavvadias and Michael N. Vrahatis, Locating and computing all the simple roots and extrema of a function, SIAM J. Sci. Comput. 17 (1996), no. 5, 1232–1248. MR 1404871, 10.1137/S1064827594265666
  • 4. Baker Kearfott, An efficient degree-computation method for a generalized method of bisection, Numer. Math. 32 (1979), no. 2, 109–127. MR 529902, 10.1007/BF01404868
  • 5. S.V. Kovalevskaya, Zur Theorie der partiellen Differentialgleichungen, Journal für reine und angewandte Mathematik 80 (1875), 1-32.
  • 6. B. Mourrain, M. N. Vrahatis, and J. C. Yakoubsohn, On the complexity of isolating real roots and computing with certainty the topological degree, J. Complexity 18 (2002), no. 2, 612–640. Algorithms and complexity for continuous problems/Algorithms, computational complexity, and models of computation for nonlinear and multivariate problems (Dagstuhl/South Hadley, MA, 2000). MR 1919452, 10.1006/jcom.2001.0636
  • 7. Nicholas M. Patrikalakis and Takashi Maekawa, Shape interrogation for computer aided design and manufacturing, Springer-Verlag, Berlin, 2002. MR 1891533
  • 8. E. Picard, Sur le nombre des racines communes à plusieurs équations simultanées, Journal de Mathématiques Pures et Applliquées ($ 4^e$ série) 8 (1892), 5-24.
  • 9. E. Picard, Traité d'analyse, 3rd ed., chap. 4.7, Gauthier-Villars, Paris, 1922.
  • 10. Frank Stenger, Computing the topological degree of a mapping in 𝑅ⁿ, Numer. Math. 25 (1975/76), no. 1, 23–38. MR 0394639
  • 11. Martin Stynes, A simplification of Stenger’s topological degree formula, Numer. Math. 33 (1979), no. 2, 147–155. MR 549445, 10.1007/BF01399550
  • 12. Martin Stynes, On the construction of sufficient refinements for computation of topological degree, Numer. Math. 37 (1981), no. 3, 453–462. MR 627117, 10.1007/BF01400322
  • 13. Michael N. Vrahatis, Solving systems of nonlinear equations using the nonzero value of the topological degree, ACM Trans. Math. Software 14 (1988), no. 4, 312–329 (1989). MR 1062479, 10.1145/50063.214384
  • 14. Michael N. Vrahatis, Algorithm 666. CHABIS: a mathematical software package for locating and evaluating roots of systems of nonlinear equations, ACM Trans. Math. Software 14 (1988), no. 4, 330–336 (1989). MR 1062480, 10.1145/50063.51906
  • 15. M. N. Vrahatis and K. I. Iordanidis, A rapid generalized method of bisection for solving systems of nonlinear equations, Numer. Math. 49 (1986), no. 2-3, 123–138. MR 848518, 10.1007/BF01389620

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 12D10, 65H10

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


Additional Information

S. Tanabé
Affiliation: Department of Mathematics, Independent University of Moscow, Bol’shoj Vlasievskij pereulok 11, 121002 Moscow, Russia
Email: tanabe@mccme.ru

M. N. Vrahatis
Affiliation: Computational Intelligence Laboratory (CI Lab), Department of Mathematics, University of Patras Artificial Intelligence Research Center (UPAIRC), University of Patras, GR–26110 Patras, Greece
Email: vrahatis@math.upatras.gr

DOI: http://dx.doi.org/10.1090/S0025-5718-06-01847-3
Keywords: Polynomial systems, location of zeros
Received by editor(s): May 26, 2004
Received by editor(s) in revised form: June 2, 2005
Published electronically: March 31, 2006
Additional Notes: This work was partially supported by the Greek State Scholarship Foundation (IKY)
Article copyright: © Copyright 2006 American Mathematical Society