Mathematics of Computation

Author(s): Reiner Horst.
Journal: Math. Comp. 66 (1997), 691-698.
MSC (1991): Primary 51M20, 90Bxx; Secondary 52B10, 65M50, 65N50, 90Cxx
Retrieve article in: PDF
This article is available free of charge

Abstract: A generalized procedure of bisection of $n$

-simplices is introduced, where the bisection point can be an (almost) arbitrary point at one of the longest edges. It is shown that nested sequences of simplices generated by successive generalized bisection converge to a singleton, and an exact bound of the convergence speed in terms of diameter reduction is given. For regular simplices, which mark the worst case, the edge lengths of each worst and best simplex generated by successive bisection are given up to depth $n$

. For

and

, the sequence of worst case diameters is provided until it is halved.

1.: A. Adler, On the bisection method for triangles, Math. Comp. 40 (1983), 571-574. MR 84d:51028
2.: E.L. Allgower and K. Georg, Numerical Continuation Methods: An Introduction, Springer Series in Computational Mathematics, 13, Berlin, Heidelberg, New York, 1990. MR 92a:65165
3.: E.L. Allgower and K. Georg, Continuation and Path Following, Acta Numerica 1 (1993), 1-64. MR 94k:65076
4.: B.C. Eaves, A course in triangulations for solving equations with deformations, Lecture Notes in Economics and Mathematical Systems 234, Springer-Verlag, Berlin, Heidelberg, New York 1984. MR 87m:90111
5.: A. Eiger, K. Sikorski, F. Stenger, A bisection method for systems of nonlinear equations, ACM Trans. Math. Software 10 (1984), 367-377. MR 86g:65102
6.: R. Horst, A new branch and bound approach for concave minimization problems, Lecture Notes in Computer Science 41, 330-337, Springer-Verlag, Berlin, Heidelberg, New York, 1975.
7.: R. Horst, An algorithm for nonconvex programming problems, Math. Programming 10 (1976), 312-321.
8.: R. Horst and P.M. Pardalos (editors), Handbook of Global Optimization, Kluwer, Dordrecht, Boston, 1995. CMP 96:09
9.: R. Horst and H. Tuy, Global Optimization, 2nd revised edition, Springer-Verlag, Berlin, Heidelberg, New York, 1993. MR 94m:90004
10.: B. Kearfott, A proof of convergence and an error bound for the method of bisection in $\mathbb {R} ^n$ Math. Comp. 32 (1978), 1147-1153. MR 58:13677
11.: A. Liu and B. Joe, On the shape of tetrahedra from bisection, Math. Comp. 63 (1994), 141-154. MR 94j:65113
12.: M.-C. Rivara, Mesh refinement processes based on the generalized bisection of simplices, SIAM J. Numer. Anal. 21 (1984), 604-613. MR 85i:65159
13.: M.-C. Rivara, Algorithms for refining triangular grids suitable for adaptive and multigrid techniques, Internat. J. Numer. Methods Engrg. 20 (1984), 745-756. MR 85h:65258
14.: M.-C. Rivara, A grid generator based on 4-triangles conforming mesh-refinement algorithms, Internat. J. Numer. Methods Engrg. 24 (1987), 1343-1354.
15.: I.G. Rosenberg and F. Stenger, A lower bound on the angles of triangles constructed bisecting the longest side, Math. Comp. 29 (1975), 390-395. MR 51:11264
16.: K. Sikorski, A three dimensional analogue to the method of bisections for solving nonlinear equations, Math. Comp. 33 (1979), 722-738. MR 80i:65058
17.: F. Stenger, Computing the topological degree of a mapping in $\mathbb {R} ^n$ , Numer. Math. 25 (1976), 23-38. MR 52:15440
18.: M. Stynes, On faster convergence of the bisection method for all triangles, Math. Comp. 35 (1980), 1195-1201. MR 81j:51023

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2009, American Mathematical Society Privacy Statement		Search the AMS