# Root Finding

Mathematics I · Scientific Programming · https://tryals.app/learn/mathematics-i/root-finding

## Numerical Root-Finding & Bisection

Most equations $f(x) = 0$ defy algebra—there is no general formula for degree-5 polynomials, let alone mixtures of exponentials and trig. **Root-finding** algorithms locate solutions **numerically** to any desired accuracy by iterating.

**Bisection** is the simplest and most robust method. It relies on the Intermediate Value Theorem: if a continuous $f$ has opposite signs at $a$ and $b$, a root lies between them.

Bisection repeatedly halves the interval, keeping the half where the sign change persists. Each step halves the error, guaranteeing convergence (given an initial sign change) with **linear** speed.

## Newton's Method & Trade-offs

**Newton's method** uses the **tangent line** from a guess $x_n$ to find the next zero:

$$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$$

Near a root, Newton's converges **quadratically**: correct digits roughly double each step.

| Feature | Bisection | Newton's Method |
| --- | --- | --- |
| **Speed** | Slow (linear) | Fast (quadratic) |
| **Reliability** | Guaranteed convergence | Can diverge or cycle |
| **Requirements** | Initial sign change | Derivative $f'$ & close start |

**Common pitfall:** Assuming **Newton's method always converges**. It fails if $f'(x_n) = 0$ (division by zero) or from poor starts. Hybrid methods use bisection for safety, then Newton's for speed.

## Practice questions

6 of this lesson's 11 practice questions, with answers. The full set is in the app.

### 1. Newton's method is always preferable to bisection because it converges quadratically.

**Answer:** False

**Why:** False. Newton needs a derivative and a good starting guess, and it can diverge, cycle, or divide by a near-zero derivative. Bisection is slow and *guaranteed* once it brackets a sign change. Robust solvers combine them, Brent's method, taking Newton steps when they behave and bisecting when they do not.

Page: https://tryals.app/practice/mathematics-i/root-finding/newtons-method-is-always-preferable-to-bisection-because-it

### 2. Hybrid algorithms combine bisection and Newton's method into a single routine. What structural limitation in both techniques justifies using them together rather than choosing the faster one alone?

A. Newton's method fails whenever equations contain non-polynomials
B. Bisection guarantees convergence only when initial guesses are poor
C. Newton's scheme requires bracketed signs to compute derivatives
D. Bisection isolates a safe basin before local speed takes over

**Answer:** D. Bisection isolates a safe basin before local speed takes over

**Why:** Newton's quadratic speed is strictly local and risks division by zero or divergence without a nearby initial guess. Bisection provides the global bracket needed to enter that local basin reliably, though it lacks the fast refinement required for high precision.

Page: https://tryals.app/practice/mathematics-i/root-finding/hybrid-algorithms-combine-bisection-and-newtons-method-into-a-single

### 3. Newton's method converges fast but not from every starting point. What can go wrong?

A. Convergence is guaranteed once the interval brackets a root
B. Nothing: convergence from any starting point is guaranteed for continuous functions
C. The tangent can send the iterate far away or into a cycle
D. The method converges to the wrong root, but always to some root

**Answer:** C. The tangent can send the iterate far away or into a cycle

**Why:** Newton is locally fast and globally unreliable. Bisection is the reverse, slow and guaranteed, which is exactly why production root-finders combine them.

Page: https://tryals.app/practice/mathematics-i/root-finding/newtons-method-converges-fast-but-not-from-every-starting-point

### 4. Complete the precondition for bisection.

**Answer:** Bisection can be started only when f has **opposite signs** at the two endpoints of the interval.

**Why:** Opposite signs at the endpoints force a continuous function to cross zero somewhere between them, which is the guarantee bisection exploits. With the same sign there may be no root, or an even number of them, and the method has nothing to bisect.

Page: https://tryals.app/practice/mathematics-i/root-finding/complete-the-precondition-for-bisection

### 5. Let f(x) = x cubed - x - 2. Sort each interval by whether bisection can be started on it.

**Answer:**

- Sign change: can start: 1 to 2, 0 to 2
- No sign change: 0 to 1, 2 to 3, minus 2 to 0

**Why:** f(-2) = -8, f(0) = -2, f(1) = -2, f(2) = 4, f(3) = 22, so only intervals with one endpoint at or beyond 2 and one below it change sign. The interval 0 to 1 has two negative values, so bisection has nothing to work with even though the function is perfectly well behaved there.

Page: https://tryals.app/practice/mathematics-i/root-finding/let-f-x-x-cubed-x-2-sort-each-interval-by-whether-bisection

### 6. Near a root Newton's method roughly doubles the number of correct digits at each step. Starting from a guess with 1 correct digit, how many correct digits should you expect after 3 steps?

**Answer:** 8

**Why:** 1, 2, 4, 8, quadratic convergence. Bisection would have gained roughly one binary digit per step over the same three steps, which is the concrete meaning of 'quadratic beats linear' once you are close enough for Newton to be safe.

Page: https://tryals.app/practice/mathematics-i/root-finding/near-a-root-newtons-method-roughly-doubles-the-number-of-correct