Hostname: page-component-586b7cd67f-r5fsc Total loading time: 0 Render date: 2024-11-23T22:19:42.413Z Has data issue: false hasContentIssue false
  • English
  • Français

AN ALGORITHM FOR FINDING ALL ZEROS OF VECTOR FUNCTIONS

Part of: Nonlinear algebraic or transcendental equations Computer aspects of numerical algorithms

Published online by Cambridge University Press:  01 June 2008

IBRAHEEM ALOLYAN
IBRAHEEM ALOLYAN*
Affiliation:
Mathematics Department, College of Science, King Saud University, PO Box 2455, Riyadh 11451, Saudi Arabia (email: [email protected])
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Computing a zero of a continuous function is an old and extensively researched problem in numerical computation. In this paper, we present an efficient subdivision algorithm for finding all real roots of a function in multiple variables. This algorithm is based on a simple computationally verifiable necessity test for the existence of a root in any compact set. Both theoretical analysis and numerical simulations demonstrate that the algorithm is very efficient and reliable. Convergence is shown and numerical examples are presented.

Keywords

numerical solution of nonlinear system of equationexclusion testdecomposable functionscomputational complexity

MSC classification

Secondary: 65H10: Systems of equations 65Y20: Complexity and performance of numerical algorithms
Type
Research Article
Information
Bulletin of the Australian Mathematical Society , Volume 77 , Issue 3 , June 2008 , pp. 353 - 363
Copyright
Copyright © 2008 Australian Mathematical Society

References

[1]Allgower, E. and Georg, K., Introduction to Numerical Continuation Methods (SIAM, Philadelphia, PA, 2003).Google Scholar
[2]Allgower, E., Erdmann, M. and Georg, K., ‘On the complexity of exclusion algorithms for optimization’, J. Complexity 18 (2002), 573–588.CrossRefGoogle Scholar
[3]Alolyan, I., ‘A new exclusion test for finding the global minimum’, J. Comput. Appl. Math. 200(2) (2007), 491–502.CrossRefGoogle Scholar
[4]Csendes, T. and Ratz, D., ‘Subdivision direction selection in interval methods for global optimization’, SIAM J. Numer. Anal. 34(3) (1997), 922–938.Google Scholar
[5]Georg, K., ‘A new exclusion test’, Proc. Int. Conf. on Recent Advances in Computational Mathematics, J. Comput. Appl. Math. 152(1–2) (2003), 147–160.Google Scholar
[6]Georg, K., ‘Improving the efficiency of exclusion algorithms’, Adv. Geom. 1 (2001), 193–210.CrossRefGoogle Scholar
[7]Hsu, C. S. and Guttalu, R. S., ‘Index evaluation for dynamical systems and its application to locating all of the zeros of a vector function’, J. Appl. Mech. 50 (1983), 858–862.CrossRefGoogle Scholar
[8]Hsu, C. S. and Zhu, W. H., ‘A simplical mapping method for locating the zeros of a function’, Quart. Appl. Math. 42 (1984), 41–59.Google Scholar
[9]Kearfott, R., ‘Rigorous global search: continuous problems’, in: Nonconvex Optimization and its Applications, Vol. 13 (Kluwer Academic, Dordrecht, 1996).Google Scholar
[10]Kearfott, R. B., ‘Empirical evaluation of innovations in interval branch and bound algorithms for nonlinear algebraic systems’, SIAM J. Sci. Comput. 18(2) (1997), 574–594.CrossRefGoogle Scholar
[11]Moore, R., Methods and Applications of Interval Analysis, SIAM Studies in Applied Mathematics, 2 (SIAM, Philadelphia, PA, 1979).CrossRefGoogle Scholar
[12]Morgan, A. P., Sommese, A. J. and Watson, L. T., ‘Finding all isolated solutions to polynomial systems using HOMPACK’, ACM Trans. Math. Software 15 (1989), 93–122.Google Scholar
[13]Rheinboldt, W. C., Numerical Analysis of Parametrized Nonlinear Equations (Wiley, New York, 1986).Google Scholar
[14]Using MATLAB (The MathWorks Inc. Natick, MA, 1996).Google Scholar
[15]Sosonkina, M., Watson, L. T. and Stewart, D. E., ‘A note on the end game in homotopy zero curve tracking’, ACM Trans. Math. Software 22 (1996), 281–287.Google Scholar
[16]Vrahatis, M. N. and Iordanidis, K. L., ‘A rapid generalized method of bisection for solving systems of non-linear equations’, Numer. Math. 49 (1986), 123–138.Google Scholar
[17]Vrahatis, M. N., ‘Solving systems of nonlinear equations using the nonzero value of the topological degree’, ACM Trans. Math. Software 14 (1988), 312–328.CrossRefGoogle Scholar
[18]Watson, L. T., ‘Globally convergent homotopy methods: A tutorial’, Appl. Math. Comput. 31 (1989), 369–396.CrossRefGoogle Scholar
[19]Xu, Z.-B., Zhang, J.-S. and Leung, Y.-W., ‘A general CDC formulation for specializing the cell exclusion algorithms of finding all zeros of vector functions’, Appl. Math. Comput. 86 (1997), 235–259.CrossRefGoogle Scholar
[20]Yakoubsohn, J. C., ‘Numerical analysis of a bisection-exclusion method to find the zeros of univariant analytic functions’, J. Complexity 21 (2005), 651–772.CrossRefGoogle Scholar