Root finding and safeguarded Newton iteration

If a real continuous function has opposite signs at two interval endpoints, the intermediate value theorem guarantees at least one root between them. Bisection evaluates the midpoint and keeps a half-interval that preserves the sign change. After each successful subdivision the interval width halves. The midpoint's distance to some bracketed root is no larger than half that width, even when the derivative is unavailable. Uniqueness needs a separate argument, such as strict monotonicity throughout the interval.

Continuity is essential. A sign change across a pole does not certify a root, and even-multiplicity roots may touch zero without changing sign. Finite precision adds practical complications: a computed midpoint can round to an endpoint once the interval is extremely narrow. Function values can also overflow or be inaccurate near a singularity. Robust termination therefore checks interval progress, finite evaluations, and a scale-aware tolerance. It does not keep bisecting forever because a requested decimal tolerance is below representable spacing.

Linearize the function around the current iterate and solve the tangent equation for its zero. This gives Newton's update. Near a simple root, with a sufficiently smooth function and a nonzero derivative, the new error is proportional to the square of the old error in the asymptotic regime. Quadratic convergence explains its speed after a suitable starting point has been found. The conclusion is local; it gives no unconditional promise from an arbitrary initial guess.

A tiny derivative produces a large step, and an iterate can leave the domain, jump to another root, or enter a cycle. Multiple roots generally reduce ordinary Newton convergence to linear unless the method is modified. Safeguarding accepts a Newton proposal only when it is well-defined and makes adequate progress within a maintained bracket; otherwise it falls back to a bracketing step. This trades a little ideal local speed for protection against common global failures. The precise acceptance rules are part of the algorithm.

A small residual measures how close the function value is to zero, not directly how close the input is to a root. If the derivative magnitude is bounded below by a positive number on an interval joining a candidate to its root, the mean value theorem converts residual into a position bound. Near a flat or repeated root that conversion may be poor. Rescaling the entire function also changes residual size while leaving every root unchanged. A universal unscaled residual threshold is therefore misleading.

Use a combination of bracket width, a scaled step, and a residual interpreted through conditioning. State whether the result certifies a root in an interval or merely records that the iteration stagnated. For vector-valued equations, the derivative becomes a Jacobian and each Newton step requires a linear solve; forming an explicit inverse is unnecessary. The same philosophy survives: inspect the local model, control its domain, and distinguish solving the linearized equation from validating the original nonlinear residual.