The Digital Collision

Abstract

An autonomous drone flies along y = x² − 3x + 1 while a jammer's interference boundary follows y = e⁻ˣ; the safety system must find where they meet, i.e. solve f(x) = x² − 3x + 1 − e⁻ˣ = 0, which has no algebraic solution. This report compares three root-finding methods on that problem by running them, not by quoting a textbook. It locates all three crossings, measures iterations, convergence order and true computational cost, maps Newton–Raphson's starting-point sensitivity across 2,401 starts, and recommends a safeguarded hybrid for a real system. Every number was re-computed against a 40-digit reference solution.

The problem

A collision point is any x where the drone's height equals the jammer boundary. Moving everything to one side gives f(x) = x² − 3x + 1 − e⁻ˣ = 0. Because the equation mixes a polynomial with an exponential, no closed-form formula exists — exactly the situation numerical root-finding is for. Newton–Raphson also needs f′(x) = 2x − 3 + e⁻ˣ.

Three methods, three personalities

Bisection halves a sign-changing bracket every step: linear convergence with ratio exactly 0.5, slow but guaranteed inside a valid bracket — 12 iterations to 3 decimal places.

Regula Falsi replaces the midpoint with the chord's root: still linear (ratio ≈ 0.358) and still bracketed, but one endpoint tends to stick — 8 iterations.

Newton–Raphson rides the tangent and roughly squares the error each step: quadratic convergence, 5 iterations from x₀ = 2 — but it is the only one of the three that can fail.

Head-to-head results

Tightening accuracy from 3 to 10 decimals costs Bisection 24 extra iterations and Regula Falsi 16, but Newton–Raphson only 1 (iterations at 3/6/10 dp: Bisection 12/22/36, Regula Falsi 8/15/24, Newton–Raphson 5/5/6).

Measured convergence matched theory: the error ratios settle to the predicted constants, and wall-clock and evaluation counts confirm that iteration count alone overstates Newton's advantage at low precision.

Starting-point sensitivity

Started at x₀ = −25, Newton–Raphson wanders for 27 iterations and lands on a different crossing. Sweeping 2,401 starting values across [−6, 6] shows the basins of attraction: 41.3% converge to C, 36.5% to A and 22.1% to B — the method is fast, but only once a good start is known.

Recommended design for a real drone

Bracket first, Newton second, bisection as the parachute. A safeguarded Newton method (as in Numerical Recipes' rtsafe) scans for a sign change, tries a Newton step, accepts it only if it stays inside the bracket, and otherwise falls back to bisection. In a six-method comparison that also included the secant and Illinois methods, the safeguarded hybrid was fastest and the only fast method that cannot be misled by a bad start.

1def safeguarded_newton(f, df, a, b, tol=5e-4, max_iter=100):2    if f(a) * f(b) > 0:3        raise ValueError("no sign change on [a, b]")4    x = (a + b) / 25    for _ in range(max_iter):6        fx, dfx = f(x), df(x)7        x_new = x - fx / dfx if dfx else None8        if x_new is None or not (a < x_new < b):9            x_new = (a + b) / 2          # bisection parachute10        if f(a) * f(x_new) < 0: b = x_new11        else: a = x_new12        if abs(x_new - x) < tol:13            return x_new14        x = x_new15    return x

Verification

All results come from a single Python script, and the roots were checked against a 40-digit mpmath solution (C = 2.649219887767292965348, A = −2.893116430925271220316, B = 0 exactly). Iteration counts, error ratios, evaluation counts, basin percentages and timings are all reproducible.