Solving systems of nonlinear equations using the nonzero value of the topological degree

ABSTRACT

Two algorithms are described here for the numerical solution of a system of nonlinear equations F(X) = &THgr;, Q=0,0,&ldots;,0∈ R , and F is a given continuous mapping of a region D in Rⁿ into Rⁿ . The first algorithm locates at least one root of the sy stem within n-dimensional polyhedron, using the non zero v alue of the topological degree of F at &thgr; relative to the polyhedron; th e second algorithm applies a new generalized bisection method in order to compute an approximate solution to the system. Teh size of the original n-dimensional polyhedron is arbitrary, and the method is globally convergent in a residual sense. These algorithms, in the various function evaluations, only make use of the algebraic sign of F and do not require computations of the topological degree. Moreover, they can be applied to nondifferentiable continuous functions F and do not involve derivatives of F or approximations of such derivatives.

REFERENCES

• 1: ALEXANDROFF, P., AND HOPF, H. Topologie. Springer-Verlag, Berlin, 1935. Reprinted: Chelsea, Bronx, N.Y., 1965.
• 2: CRONIN, J. Fixed Points and Topological Degree in Nonlinear Analysis. American Mathematical Society, Providence, R.I., 1964.
• 3: A. Eiger , K. Sikorski , F. Stenger, A bisection method for systems of nonlinear equations, ACM Transactions on Mathematical Software (TOMS), v.10 n.4, p.367-377, Dec. 1984 [doi>10.1145/2701.2705]
• 4: GONNET, G.H. On the structure of zero finders. Bit 17 (1977), 170-183.
• 5: GRAPSA, T. N., AND VRAHATIS, M.N. The implicit function theorem for solving systems of nonlinear equations in R2. Int. J. Comput. Math. To be published.
• 6: HARVEY, C., AND STENGER, F. A two-dimensional analogue to the method of bisections for solving nonlinear equations. Q. Appl. Math. 5, 33 (1976), 351-368.
• 7: Ralph Baker Kearfott, Computing the degree of maps and a generalized method of bisection., 1977
• 8: KEARFOTT, R.B. An efficient degree-computation method for a generalized method of bisection. Numer. Math. 32 (1979), 109-127.
• 9: KEARFOTT, R.B. Abstract generalized bisection and a cost bound. Math. Comput. 49, 179 (July 1987), 187-202.
• 10: R. Baker Kearfott, Some tests of generalized bisection, ACM Transactions on Mathematical Software (TOMS), v.13 n.3, p.197-220, Sept. 1987 [doi>10.1145/29380.29862]
• 11: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 12: Jorge J. Moré , Michael Y. Cosnard, Algorithm 554: BRENTM, A Fortran Subroutine for the Numerical Solution of Nonlinear Equations [C5], ACM Transactions on Mathematical Software (TOMS), v.6 n.2, p.240-251, June 1980 [doi>10.1145/355887.355898]
• 13: Jorge J. Moré , Burton S. Garbow , Kenneth E. Hillstrom, Testing Unconstrained Optimization Software, ACM Transactions on Mathematical Software (TOMS), v.7 n.1, p.17-41, March 1981 [doi>10.1145/355934.355936]
• 14: ORTE(~A, J. M., AND RHEINBOLDT, W.C. iterative Solution of Nonlinear Equations in Several Variables. Academic Press, New York, 1970.
• 15: SIKORSKI, K. A three-dimensional analogue to the method of bisections for solving nonlinear equations. Math. Comput. 33, 146 (1979), 722-738.
• 16: SIKORSKI, K. Bisection is optimal. Numer. Math. 40 (1982), 111-117.
• 17: STENGER, F. Computing the topological degree of a mapping in R~. Numer. Math. 25 (1975), 23-38.
• 18: Martin Joseph Stynes, An algorithm for the numerical calculation of the degree of a mapping., 1977
• 19: STYNES, M. An algorithm for numerical calculation of topological degree. Appl. Anal. 9 (1979), 63-77.
• 20: STYNES, M. A simplification of Stenger's topological degree formula. Numer. Math. 33 (1979), 147-156.
• 21: STVNES, M. On the construction of sufficient refinements for computation of topological degree. Numer. Math. 37 (1981), 453-462.
• 22: VRAHATIS, M.N. On the nonzero value of the topological degree for locating roots of systems of nonlinear equations. Tech. Rep. 4, Dept. of Mathematics, Univ. of Patras, Patras, Greece, 1981.
• 23: VRAHATIS, M.N. Oil the construction of characteristic n-polyhedra for locating roots of systems of nonlinear equations. Tech. Rep. 5, Dept. of Mathematics, Univ. of Patras, Patras, Greece, 1981.
• 24: VRAHATXS, M.N. The topological degree for the generalized method of bisection. Tech. Rep. 6, Dept. of Mathematics, Univ. of Patras, Patras, Greece, 1981.
• 25: VRAHATIS, M.N. An error estimation for the method of bisection in Rn. Bull. Greek Math. Sac. 27 (1986), 161-174.
• 26: VRAHATIS, M. N., AND BOUNTIS, T.C. A convergence-improving iterative method for computing periodic orbits near bifurcation points. Submitted for publication.
• 27: M N Vrahatis , K I Iordanidis, A rapid generalized method of bisection for solving systems of non-linear equations, Numerische Mathematik, v.49 n.2-3, p.123-138, July 1986 [doi>10.1007/BF01389620]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.5 Roots of Nonlinear Equations
          Subjects: Systems of equations

Additional Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

General Terms:
Algorithms, Theory

Keywords:
existence of the solution, generalized method of bisection, isolation of a root, localization of a root, solution of nonlinear systems, topological degree of a mapping