Bisection method: Difference between revisions

Revision as of 00:44, 24 April 2014

This article is about a root-finding algorithm. See all root-finding algorithms

Definition

The bisection method, also called the interval halving method, binary search method, and dichotomy method, is a root-finding algorithm.

Summary

Item	Value
Initial condition	works for a continuous function $f$ (or more generally, a function $f$ satisfying the intermediate value property) on an interval $[a,b]$ given that $f(a)$ and $f(b)$ have opposite signs.
Iterative step	At stage $i$ , we know that $f$ has a root in an interval $[a_{i},b_{i}]$ . We test $f$ at $(a_{i}+b_{i})/2$ . We then define the new interval $[a_{i+1},b_{i+1}]$ as the left half $[a_{i},(a_{i}+b_{i})/2]$ if the signs of $f$ at $a_{i}$ and $(a_{i}+b_{i})/2$ oppose one another, and as the right half otherwise.
Convergence rate	The size of the interval within which we are guaranteed to have a root halves at each step. The distance between the root and our "best guess" at any stage (say, the midpoint of the guaranteed interval) has an upper bound that halves at each step, so we have linear convergence.
Computational tools needed	Floating-point arithmetic to compute averages Ability to compute the value of a function at a point, or more minimalistically, determine whether the value is positive or negative.
Termination stage	We may terminate the algorithm based either on the size of the interval in the domain (i.e., we know that we are close to a root) or the closeness of the function value to zero. How we terminate depends on our goals.

Initial condition

The bisection method works for a continuous function $f$ (or more generally, a function $f$ satisfying the intermediate value property) on an interval $[a,b]$ given that $f(a)$ and $f(b)$ have opposite signs.

The bisection method can be used to find a root of a continuous function on a connected interval if we are able to locate two points in the domain of the function where it has opposite signs. We simply restrict the function to that domain and apply the method.

Iterative step

Let $a=a_{1},b=b_{1}$ .

At stage $i$ .

Prior knowledge:

$f(a_{i})$ and $f(b_{i})$ are both numerically distinguishable from zero (so they have defined signs, positive or negative) and they have opposite signs.
Combining that with the fact that $f$ is a continuous function, the intermediate value theorem tells us that $f$ has a root on $[a_{i},b_{i}]$ .

Iterative step:

Compute $f((a_{i}+b_{i})/2)$ .
If it is equal to (or numerically indistinguishable from) zero, then return $(a_{i}+b_{i})/2$ as the root and terminate the algorithm.
If $f((a_{i}+b_{i})/2)$ has sign opposite to $f(a_{i})$ (and therefore the same as $f(b_{i})$ ), then choose $a_{i+1}=a_{i}$ and $b_{i+1}=(a_{i}+b_{i})/2$ , so the new interval (for the next iteration) is $[a_{i+1},b_{i+1}]$ as the left half $[a_{i},(a_{i}+b_{i})/2]$ .
If $f((a_{i}+b_{i})/2)$ has sign opposite to $f(b_{i})$ (and therefore the same as $f(a_{i})$ ), the nchoose $a_{i+1}=(a_{i}+b_{i})/2$ and $b_{i+1}=b_{i}$ , so the new interval (for the next iteration) is $[a_{i+1},b_{i+1}]$ as the left half $[(a_{i}+b_{i})/2,b_{i}]$ .

@@ Line 4: / Line 4: @@
 The '''bisection method''', also called the '''interval halving method''', '''binary search method''', and '''dichotomy method''', is a root-finding algorithm.
+==Summary==
+{| class="sortable" border="1"
+! Item !! Value
+|-
+| Initial condition || works for a [[continuous function]] <math>f</math> (or more generally, a function <math>f</math> satisfying the [[intermediate value property]]) on an interval <math>[a,b]</math> given that <math>f(a)</math> and <math>f(b)</math> have opposite signs.
+|-
+| Iterative step || At stage <math>i</math>, we know that <math>f</math> has a root in an interval <math>[a_i,b_i]</math>. We test <math>f</math> at <math>(a_i + b_i)/2</math>. We then define the new interval <math>[a_{i+1},b_{i+1}]</math> as the left half <math>[a_i, (a_i+b_i)/2]</math> if the signs of <math>f</math> at <math>a_i</math> and <math>(a_i + b_i)/2</math> oppose one another, and as the right half otherwise.
+|-
+| Convergence rate || The size of the interval within which we are guaranteed to have a root halves at each step.<br>The distance between the root and our "best guess" at any stage (say, the midpoint of the guaranteed interval) has an upper bound that halves at each step, so we have linear convergence.
+|-
+| Computational tools needed || Floating-point arithmetic to compute averages<br>Ability to compute the value of a function at a point, or more minimalistically, determine whether the value is positive or negative.
+|-
+| Termination stage || We may terminate the algorithm based either on the size of the interval in the domain (i.e., we know that we are close to a root) or the closeness of the function value to zero. How we terminate depends on our goals.
+|}
+==Initial condition==
+The bisection method works for a [[continuous function]] <math>f</math> (or more generally, a function <math>f</math> satisfying the [[intermediate value property]]) on an interval <math>[a,b]</math> given that <math>f(a)</math> and <math>f(b)</math> have opposite signs.
+The bisection method can be used to find a root of a continuous function on a connected interval if we are able to locate two points in the domain of the function where it has opposite signs. We simply restrict the function to that domain and apply the method.
+==Iterative step==
+Let <math>a = a_1, b = b_1</math>.
+At stage <math>i</math>.
+'''Prior knowledge''':
+* <math>f(a_i)</math> and <math>f(b_i)</math> are both numerically distinguishable from zero (so they have defined signs, positive or negative) and they have opposite signs.
+* Combining that with the fact that <math>f</math> is a continuous function, the [[intermediate value theorem]] tells us that <math>f</math> has a root on <math>[a_i,b_i]</math>.
+'''Iterative step''':
+* Compute <math>f((a_i + b_i)/2)</math>.
+* If it is equal to (or numerically indistinguishable from) zero, then return <math>(a_i + b_i)/2</math> as the root and terminate the algorithm.
+* If <math>f((a_i + b_i)/2)</math> has sign opposite to <math>f(a_i)</math> (and therefore the same as <math>f(b_i)</math>), then choose <math>a_{i+1} = a_i</math> and <math>b_{i+1} = (a_i + b_i)/2</math>, so the new interval (for the next iteration) is <math>[a_{i+1},b_{i+1}]</math> as the left half <math>[a_i, (a_i+b_i)/2]</math>.
+* If <math>f((a_i + b_i)/2)</math> has sign opposite to <math>f(b_i)</math> (and therefore the same as <math>f(a_i)</math>), the nchoose <math>a_{i+1} = (a_i + b_i)/2</math> and <math>b_{i+1} = b_i</math>, so the new interval (for the next iteration) is <math>[a_{i+1},b_{i+1}]</math> as the left half <math>[(a_i+b_i)/2, b_i]</math>.