Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



A proof of convergence and an error bound for the method of bisection in $ {\bf R}\sp{n}$

Author: Baker Kearfott
Journal: Math. Comp. 32 (1978), 1147-1153
MSC: Primary 65H10
MathSciNet review: 0494897
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Let $ S = \langle {X_0},..,{X_m}\rangle $ be an m-simplex in $ {{\mathbf{R}}^n}$. We define "bisection" of S as follows. We find the longest edge $ \langle {X_i},{X_j}\rangle $ of S, calculate its midpoint $ M = ({X_i} + {X_j})/2$, and define two new m-simplexes $ {S_1}$ and $ {S_2}$ by replacing $ {X_i}$ by M or $ {X_j}$ by M.

Suppose we bisect $ {S_1}$ and $ {S_2}$, and continue the process for p iterations. It is shown that the diameters of the resulting Simplexes are no greater then $ {(\sqrt 3 /2)^{\left\lfloor {p/m} \right\rfloor }}$ times the diameter of the original simplex, where $ \left\lfloor {p/m} \right\rfloor $ is the largest integer less than or equal to $ p/m$.

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

  • [1] P. ALEXANDROFF & H. HOPF, Topologie, Chelsea, New York, 1935; reprinted 1973.
  • [2] MARVIN GREENBERG, Lectures on Algebraic Topology, Benjamin, New York, 1967. MR 0215295 (35:6137)
  • [3] R. B. KEARFOTT, Computing the Degree of Maps and a Generalized Method of Bisection, Ph. D. dissertation, Univ. of Utah, 1977.
  • [4] R. B. KEARFOTT, "An efficient degree-computation method for a generalized method of bisection," Numer. Math. (To appear.) MR 529902 (80g:65062)
  • [5] J. ROSENBERG & F. STENGER, "A lower bound on the angles of triangles constructed by bisecting the longest side," Math. Comp., v. 29, 1975, pp. 390-395. MR 0375068 (51:11264)
  • [6] MARTIN STYNES, An Algorithm for the Numerical Calculation of the Degree of a Mapping, Ph. D. dissertation, Oregon State Univ., 1977.
  • [7] FRANK STENGER, "An algorithm for the topological degree of a mapping in $ {{\mathbf{R}}^n}$," Numer. Math., v. 25, 1976, pp. 23-28.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65H10

Retrieve articles in all journals with MSC: 65H10

Additional Information

Article copyright: © Copyright 1978 American Mathematical Society

American Mathematical Society