On perturbation of roots of homogeneous algebraic systems

Tanabé, S.; Vrahatis, M.

doi:10.1090/S0025-5718-06-01847-3

On perturbation of roots of homogeneous algebraic systems
HTML articles powered by AMS MathViewer

by S. Tanabé and M. N. Vrahatis;

Math. Comp. 75 (2006), 1383-1402

DOI: https://doi.org/10.1090/S0025-5718-06-01847-3

Published electronically: March 31, 2006

PDF | Request permission

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

Paul Alexandroff and Heinz Hopf, Topologie, Chelsea Publishing Co., New York, 1965 (German). Erster Band; Grundbegriffe der mengentheoretischen Topologie, Topologie der Komplexe, topologische Invarianzsätze und anschliessende Begriffsbildunge n, Verschlingungen im n-dimensionalen euklidischen Raum, stetige Abbildungen von Polyedern. MR 185557
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, DOI 10.1007/978-1-4612-5154-5
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, DOI 10.1137/S1064827594265666
Baker Kearfott, An efficient degree-computation method for a generalized method of bisection, Numer. Math. 32 (1979), no. 2, 109–127. MR 529902, DOI 10.1007/BF01404868
S.V. Kovalevskaya, Zur Theorie der partiellen Differentialgleichungen, Journal für reine und angewandte Mathematik 80 (1875), 1–32.
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, DOI 10.1006/jcom.2001.0636
Nicholas M. Patrikalakis and Takashi Maekawa, Shape interrogation for computer aided design and manufacturing, Springer-Verlag, Berlin, 2002. MR 1891533
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.
E. Picard, Traité d’analyse, 3rd ed., chap. 4.7, Gauthier–Villars, Paris, 1922.
Frank Stenger, Computing the topological degree of a mapping in $\textbf {R}^{n}$, Numer. Math. 25 (1975/76), no. 1, 23–38. MR 394639, DOI 10.1007/BF01419526
Martin Stynes, A simplification of Stenger’s topological degree formula, Numer. Math. 33 (1979), no. 2, 147–155. MR 549445, DOI 10.1007/BF01399550
Martin Stynes, On the construction of sufficient refinements for computation of topological degree, Numer. Math. 37 (1981), no. 3, 453–462. MR 627117, DOI 10.1007/BF01400322
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, DOI 10.1145/50063.214384
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, DOI 10.1145/50063.51906
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, DOI 10.1007/BF01389620