Halfinterval

Halfinterval, also called the half-interval method, is a simple, robust root-finding technique used to locate a zero of a continuous function on an interval. If f is continuous on [a,b] and f(a) and f(b) have opposite signs, the intermediate value theorem guarantees a root c in (a,b). The method repeatedly halves the interval by evaluating the midpoint m = (a+b)/2 and determining which subinterval contains a root via the sign of f(m). If f(a)·f(m) ≤ 0, replace b by m; otherwise replace a by m. This preserves a subinterval on which the root lies. The process is repeated until the interval width |b−a| is below a chosen tolerance or f(m) is sufficiently close to zero.

Convergence for the halfinterval method is linear with rate 1/2. After n iterations, the interval width is at most (b−a)/2^n, so the root is known to lie within that tolerance of either endpoint. Each iteration typically requires one function evaluation, in addition to the initial evaluations at a and b.

Requirements and limitations include that f must be continuous on [a,b], and f(a) and f(b) must have opposite signs to guarantee a root in the interval. While robust and easy to implement, the halfinterval method is generally slower than higher-order methods like Newton-Raphson for well-behaved functions, though it remains a reliable first approach, especially when derivative information is unavailable or the function is irregular.

Relation to other methods: the halfinterval method is essentially the bisection method, also known as interval halving, and is widely taught as a foundational algorithm for root finding and for illustrating the existence of roots via the intermediate value theorem.