Bisection method

The bisection, continued bisection or also called interval bisection method is a method of mathematics and computer science. Through them a convergent sequence of nested intervals is generated. The word is composed of Bi "two " and Section " cut". It stands for two-division.

Basically find bisection method always used when a problem can be solved by being split into two approximately equal-sized sub-problems, which can then be treated individually on their own.

Example

A simple example is the following problem is: Find a number between 1 and 1000 The guess is a player, he receives as an indication only " greater than" or "less " or "hits ". . Suppose the number is 512 If a player uses to rate the bisection method of binary search, results in the following dialog:

If the player had instead sought linear and started at 1, then the dialogue would have taken the following course:

Instead of ten questions he had so 512 questions used, the bisection is here so much more efficient.

Runtime and convergence

Discrete event

In the discrete case, when the underlying problem has only a finite number of solutions to be tested, such a problem can always be seen as a search: in a finite amount of M is an element x to the characteristic P ( x) = 0 are found. p is in this case a function

Be, where p (y ) = 0 if and only intended to apply when the requested property is satisfied, ie y = x. In order to solve this problem by bisection, should continue to apply:

• P (Y) < 0 if y < x
• P ( y) > 0 if y > x

The p function is thus not only results in the ( at P (x ) = 0), but has in the other case, the direction in which must be searched. This course is tacitly assumed that M is ordered by a relation <.

M is divided into two preferably equal halves by first p of an element is evaluated as close as possible to the center of M. The case that M due to an odd number of elements only can only share about equal parts in two, can be suppressed, it affects at large element numbers as well as not enough. After each step, ie, one half of recently studied amount to be discarded, the amount is halved with each evaluation of p. The method ends at the latest, when the amount contains only one element, this must be what is sought, if it was ever included in the initial amount. So in order to reduce a lot of size m by continued halving to 1, n steps are necessary to:

Thus, the method has a running time of O (log ( m)).

Continuous case

In the continuous case is usually an interval as a solution looking for, this is part of another interval finite interval. The number of possible solutions is infinite, since each sub-interval (generally of a particular length ) is eligible. An example will illustrate this:

Wanted a zero of a strictly monotonically increasing function f in the interval [a, b]. This should be given with an accuracy, so it is searched for a subinterval of [a, b] that contains the zero and has at most the length. Since there are infinitely many such intervals, they can be tried not just all. However:

• A strictly monotonically increasing function f has an interval [ l, r ] if and only one zero if f ( l) <0 and f (r) > 0.

This leads to the following algorithm:

Similar to the discrete case, the algorithm ends at the latest when the interval falls below the length. So:

This results in a logarithmic running time depending on the ratio of the interval length to the desired accuracy.

Advantages and disadvantages of the method

The bisection is suitable for the following cases:

• A sign change is in the given interval before and the function is continuous
• The initial values ​​of the conventional method ( Newton's method, regulators Falsi ) are not sufficiently close enough to zero so that there is no local convergence occurs
• Multiple zeros reduce the rate of convergence of the classical method

Disadvantages of the bisection:

• In simple cases ( strictly monotonic function ) it is slower than a quadratic convergent method
• Without change of sign in the given interval additional tests are needed to distinguish a local minimum of a zero

Bisection and binary

There is a close correlation between bisection and binary trees. During a bisection a decision is in every step taken whether to continue with the left or the right subset, and be decided in each node when going through a binary tree from the root must determine whether the left or right edge to be followed. There are to a given set size and a bisection method exactly an associated binary tree that describes all potential courses of bisection. The tree has it as many sheets as the given problem can provide possible results. Since approximately halved with every decision in a node, the number of possible results, it has about

Levels. This corresponds to the duration of the bisection, as the number of layers determines the length of travel from top to bottom, which in turn is equal to the propagation time. The resulting by this assignment tree corresponds to a balanced binary search tree.

Bisection and binary numbers

Bisection example, can be also used to determine the binary representation of a number. A number between 0 and m-1 can be obtained by a sequence of " greater - or - equal " - are identified and " small " decisions. If m is chosen as a power of 2, so you can always click the item " right of center " to be typed, since the amount has an even size. For m = 8, which implies, for example, the set { 0, ..., 7} - the search for the two seems to be running as follows:

• 4 - small
• 2 - greater than or equal (on a "hit" is omitted )
• 3 - small

Thus, the 2 is described in detail. If we now substitute for " less than" 0 and for " greater than or equal to" 1, we obtain 010 This is just the binary representation of 2