Intermediate Value Theorem

Intermediate Value Theorem (IVT)

The IVT is one of the most powerful results about continuous functions.

Statement

If (f) is continuous on ([a, b]) and (y) is any value between (f(a)) and (f(b)), then there exists some (c \in (a, b)) such that (f(c) = y).

Consequence: Root Finding

If (f(a)) and (f(b)) have opposite signs, then (f) has a root in ((a, b)). This is the basis of the bisection method.

The Bisection Method

1. Start with ([a, b]) where (f(a)) and (f(b)) have opposite signs
2. Compute the midpoint (m = (a + b) / 2)
3. If (f(a) \cdot f(m) < 0), the root is in ([a, m]); otherwise in ([m, b])
4. Repeat until the interval is small enough

Each step halves the interval, so after (n) steps the error is at most ((b - a) / 2^n).

Example: Finding (\sqrt{2})

(\sqrt{2}) is a root of (f(x) = x^2 - 2). Since (f(1) = -1 < 0) and (f(2) = 2 > 0), the IVT guarantees a root in ((1, 2)).

Your Task

Implement:

1. has_root(f, a, b) -- returns True if (f(a)) and (f(b)) have opposite signs
2. bisection(f, a, b, tol) -- finds a root of (f) in ([a, b]) using bisection, stopping when (b - a < \text{tol}). Returns the midpoint.