The bisection method begins with a finite interval on which the continuous function has opposite signs at its endpoints. The intermediate value theorem guarantees a root inside. Evaluate at the midpoint . If , stop. Otherwise retain the half whose endpoints have opposite signs and repeat. An endpoint that is already a root is returned immediately. The nested intervals retain a root and their lengths halve, so their midpoints converge to a root.
If the starting length is , then after interval halvings the current midpoint is at most from some root remaining in the bracket. Thus, with the midpoint returned after those halvings, it suffices to takeIf iterations instead count midpoint evaluations starting with the initial midpoint as evaluation one, the usual bound is , with at least one evaluation unless an endpoint root has already been found. Stating the counting convention avoids an apparent one-step discrepancy.
The following R function uses the factored polynomial for evaluation, handles endpoint and midpoint roots, and returns a midpoint only once its error bound is at most
eps:bisect <- function(a, b, eps = 1e-8, maxiter = 1000L) {
f <- function(x) x * (x - 1) * (x - 2) * (x - 5)
stopifnot(length(a) == 1L, length(b) == 1L,
is.finite(a), is.finite(b), a < b,
length(eps) == 1L, is.finite(eps), eps > 0)
fa <- f(a)
fb <- f(b)
if (fa == 0) return(a)
if (fb == 0) return(b)
if (sign(fa) == sign(fb)) stop("Endpoints must bracket a sign change")
for (i in seq_len(maxiter)) {
m <- a + (b - a) / 2
fm <- f(m)
if (fm == 0 || (b - a) / 2 <= eps) return(m)
if (sign(fm) == sign(fa)) {
a <- m
fa <- fm
} else {
b <- m
}
}
stop("Iteration limit reached")
}Each update preserves the sign-changing bracket, and the stopping bound is the half-width of that bracket. Thus continuity and the intermediate value theorem justify the returned root approximation.
At the left endpoint . If , the endpoint is exactly a root and the function above immediately returns . For , , so the first midpoint is .
If , then and . The first retained bracket is , containing only the root zero, so the iterates converge to zero. If , the first midpoint is exactly the root one and is returned. If , then and . The retained bracket is , containing only the root two, so the iterates converge to two. HenceThis illustrates root selection by bisection with multiple roots in the initial bracket: bisection guarantees a root, but which root it chooses depends discontinuously on the starting endpoint.
Articles by others on the same topic
There are currently no matching articles.