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 10: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
.