Difference between revisions of "Bisection method"
(Created page with "The '''bisection method''' is a technique for locating real roots of a continuous function. ==Process== Applying the bisection method to a...") |
(→See also) |
||
| Line 14: | Line 14: | ||
*[[Newton's method]] | *[[Newton's method]] | ||
*[[Secant method]] | *[[Secant method]] | ||
| + | *[[Binary search]] | ||
Latest revision as of 11:53, 16 May 2022
The bisection method is a technique for locating real roots of a continuous function.
Process
Applying the bisection method to a function 
begins by selecting a lower bound 
and an upper bound 
. The values 
and 
should have opposite signs, guaranteeing that a root of lies in the interval 
by the Intermediate Value Theorem.
The method proceeds by considering 
, the midpoint of the interval. If by chance 
, then 
is the desired root. Otherwise, 
has the same sign as either or , so the process can be repeated with replacing or respectively.
Performance
Bisection halves the width of the interval containing the root at each step. In binary, this corresponds to gaining one digit of precision per iteration. While finding a root exactly at the midpoint of any step is rare, the endpoints of the intervals produced are guaranteed to converge to a root.
The bisection method will not find roots of even multiplicity because does not change sign at such roots. One way to correct the omission is to use the bisection method on the derivative 
, since a root of multiplicity 
of is a root of multiplicity 
of .
