Editing Bisection method (section)

=== Characteristic bisection method ===
The '''characteristic bisection method''' uses only the signs of a function in different points. Lef ''f'' be a function from R<sup>d</sup> to R<sup>d</sup>, for some integer ''d'' ≥ 2. A '''characteristic polyhedron<ref>{{Cite journal |last=Vrahatis |first=Michael N. |date=1995-06-01 |title=An Efficient Method for Locating and Computing Periodic Orbits of Nonlinear Mappings |url=https://www.sciencedirect.com/science/article/pii/S0021999185711199 |journal=Journal of Computational Physics |language=en |volume=119 |issue=1 |pages=105–119 |doi=10.1006/jcph.1995.1119 |bibcode=1995JCoPh.119..105V |issn=0021-9991|url-access=subscription }}</ref>''' (also called an '''admissible polygon''')<ref name=":2">{{Cite journal |last1=Vrahatis |first1=M. N. |last2=Iordanidis |first2=K. I. |date=1986-03-01 |title=A rapid Generalized Method of Bisection for solving Systems of Non-linear Equations |url=https://doi.org/10.1007/BF01389620 |journal=Numerische Mathematik |language=en |volume=49 |issue=2 |pages=123–138 |doi=10.1007/BF01389620 |s2cid=121771945 |issn=0945-3245|url-access=subscription }}</ref> of ''f'' is a [[polytope]] in R<sup>''d''</sup>, having 2<sup>d</sup> vertices, such that in each vertex '''v''', the combination of signs of ''f''('''v''') is unique and the [[Degree of a continuous mapping#Maps from closed region|topological degree of ''f'' on its interior]] is not zero (a necessary criterion to ensure the existence of a root).<ref name=":3">{{cite journal |last1=Vrahatis |first1=M.N. |last2=Perdiou |first2=A.E. |last3=Kalantonis |first3=V.S. |last4=Perdios |first4=E.A. |last5=Papadakis |first5=K. |last6=Prosmiti |first6=R. |last7=Farantos |first7=S.C. |title=Application of the Characteristic Bisection Method for locating and computing periodic orbits in molecular systems |journal=Computer Physics Communications |date=July 2001 |volume=138 |issue=1 |pages=53–68 |doi=10.1016/S0010-4655(01)00190-4|bibcode=2001CoPhC.138...53V }}</ref> For example, for ''d''=2, a characteristic polyhedron of ''f'' is a [[quadrilateral]] with vertices (say) A,B,C,D, such that:

* {{tmath|1=\sgn f(A) = (-,-)}}, that is, ''f''<sub>1</sub>(A)<0, ''f''<sub>2</sub>(A)<0.
* {{tmath|1=\sgn f(B) = (-,+)}},  that is, ''f''<sub>1</sub>(B)<0, ''f''<sub>2</sub>(B)>0.
* {{tmath|1=\sgn f(C) = (+,-)}},  that is, ''f''<sub>1</sub>(C)>0, ''f''<sub>2</sub>(C)<0.
* {{tmath|1=\sgn f(D) = (+,+)}},  that is, ''f''<sub>1</sub>(D)>0, ''f''<sub>2</sub>(D)>0.
A '''proper edge''' of a characteristic polygon is a edge between a pair of vertices, such that the sign vector differs by only a single sign. In the above example, the proper edges of the characteristic quadrilateral are AB, AC, BD and CD. A '''diagonal''' is a pair of vertices, such that the sign vector differs by all ''d'' signs. In the above example, the diagonals are AD and BC.

At each iteration, the algorithm picks a proper edge of the polyhedron (say, A{{--}}B), and computes the signs of ''f'' in its mid-point (say, M). Then it proceeds as follows:

* If {{tmath|1=\sgn f(M) = \sgn(A)}}, then A is replaced by M, and we get a smaller characteristic polyhedron.
* If {{tmath|1=\sgn f(M) = \sgn(B)}}, then B is replaced by M, and we get a smaller characteristic polyhedron.
* Else, we pick a new proper edge and try again.

Suppose the diameter (= length of longest proper edge) of the original characteristic polyhedron is {{mvar|D}}. Then, at least <math>\log_2(D/\varepsilon)</math> bisections of edges are required so that the diameter of the remaining polygon will be at most {{mvar|&epsilon;}}.<ref name=":2" />{{Rp|page=11|location=Lemma.4.7}} If the topological degree of the initial polyhedron is not zero, then there is a procedure that can choose an edge such that the next polyhedron also has nonzero degree.<ref name=":3"/><ref>{{cite journal |last1=Vrahatis |first1=Michael N. |title=Solving systems of nonlinear equations using the nonzero value of the topological degree |journal=ACM Transactions on Mathematical Software |date=December 1988 |volume=14 |issue=4 |pages=312–329 |doi=10.1145/50063.214384}}</ref>