1D Root Finding: Open Methods

Overview

Open methods iterate from one or two starting points without maintaining a bracket. They forfeit the guaranteed convergence of bracketing methods but can achieve quadratic or higher convergence. Initial-value choice is critical: starting outside the basin of attraction can lead to divergence.

Related API: newton_raphson, secant_method / halley_method, schroder_method, king_method, popovski_method.

Newton-Raphson

Linearize $f$ at the current point and take the zero of the linearization as the next point:

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

Convergence

For a simple root ($f(\alpha) = 0,\ f'(\alpha) \neq 0$) with $f \in C^2$ and $x_0$ in the basin of attraction, Newton converges quadratically:

$$|x_{n+1} - \alpha| \approx \frac{|f''(\alpha)|}{2|f'(\alpha)|} \cdot |x_n - \alpha|^2.$$

At a multiple root ($f'(\alpha) = 0$), Newton degrades to linear convergence with ratio $1 - 1/m$ (where $m$ is the multiplicity). Schröder's method or an explicit multiplicity correction is then required.

Failure modes

• $f'(x_n) \approx 0$ causes divergence.
• Crossing an inflection point may oscillate.
• Starting outside the basin of attraction can jump to a different root or to infinity.

sangi's newton_raphson takes $f$ and $f'$ as callables. For polynomials, Polynomial::derivative() provides $f'$ and a doubled Horner loop evaluates $f$ and $f'$ in a single pass.

Secant Method

Replace Newton's $f'(x_n)$ by the divided difference of the previous two points:

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

Convergence

Convergence order: the golden ratio $\varphi = (1 + \sqrt{5})/2 \approx 1.618$. Slower than Newton's quadratic, but only one function evaluation per iteration. Attractive when $f'$ is unavailable in closed form or when each evaluation is extremely expensive.

When $f(x_n)$ and $f(x_{n-1})$ become nearly equal, the divided difference suffers catastrophic cancellation and the iteration diverges; stagnation detection is needed.

Halley's Method

The zero of the second-order Taylor expansion yields a cubically convergent iteration:

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

Equivalently, as a modified Newton step:

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

Convergence

Convergence order: cubic. Each iteration cubes the error, so total iteration count shrinks vs. Newton. The catch is the extra $f''$ evaluation; total cost wins as long as $f''$ costs less than about $\tfrac{1}{2} f'$.

For polynomials, a tripled Horner loop evaluates $f$, $f'$, and $f''$ in a single pass (the pattern used inside laguerre()).

Householder's Methods

A family generalizing Newton and Halley that achieves order $(d+1)$ convergence using derivatives up to order $d$:

$$x_{n+1} = x_n + d \cdot \frac{(1/f)^{(d-1)}(x_n)}{(1/f)^{(d)}(x_n)}.$$

• $d = 1$: Newton.
• $d = 2$: Halley.
• $d = 3$: fourth-order Householder.

Higher orders theoretically achieve any convergence rate, but they require successively higher derivatives and implementation complexity. Practical use stops at $d \leq 3$.

Schröder's Method (Multiple Roots)

For a root of multiplicity $m$, plain Newton converges only linearly. Schröder's method multiplies the Newton step by $m$ to restore quadratic convergence:

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

An alternative form that does not require knowing $m$:

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

This second form resembles Halley's but, unlike Halley, retains strict quadratic convergence at multiple roots (Halley loses its cubic order at multiple roots). sangi's schroder_method uses this multiplicity-free form.

King / Popovski (Fourth-Order)

A family of methods that uses only $f$ and $f'$ but achieves fourth-order convergence via a Newton step plus one correction.

King's method (1973)

After the Newton step $y_n = x_n - f(x_n)/f'(x_n)$, evaluate $f(y_n)$ and apply a correction:

$$x_{n+1} = y_n - \frac{f(y_n)}{f'(x_n)} \cdot \frac{f(x_n) + \beta f(y_n)}{f(x_n) + (\beta - 2) f(y_n)}.$$

The parameter $\beta \in \mathbb{R}$ defines the family; $\beta = 0$ recovers Ostrowski's method.

Popovski's method

Another Newton-plus-correction scheme achieving fourth-order convergence, with a different correction term that affects basin shape and stability.

Per-iteration cost

King / Popovski evaluate $f$ twice and $f'$ once per iteration (3× Newton's per-iteration cost). Fourth-order convergence usually beats two Newton iterations (4 evaluations); the break-even depends on relative evaluation costs.

Convergence Criteria and Stagnation Detection

sangi's ConvergenceCriteria<T> unifies three convergence tests:

• Variable: $|x_{n+1} - x_n| < \text{tol}_x \cdot (|x_n| + \text{tol}_x)$.
• Function value: $|f(x_n)| < \text{tol}_f$.
• Interval (bracketing only): $|b - a| < \text{tol}_x$.

It also detects stagnation:

• $|x_{n+1} - x_n|$ stops shrinking.
• $|f(x_n)|$ stops improving.
• $f'(x_n)$ approaches $0$ at the order of $\epsilon$ (Newton-family methods).

When stagnation is detected, RootFindingResult returns partial_success with the current best approximation and its estimated error. Making non-convergence visible to the caller enables a deliberate fallback to a different algorithm.

Choosing tolerances

A rule of thumb is $\text{tol}_x \approx \sqrt{\epsilon_{\text{machine}}}$ ($\approx 10^{-8}$ for double). With Newton-style quadratic convergence, the final iteration squares the error and crosses below machine precision in a single step, so tighter tol_x values are wasted.

Comparison Table

Rules of thumb: prefer Halley when $f''$ is cheap, secant or King/Popovski when no derivative is available, and Schröder when multiple roots are suspected.

References

• Ostrowski, A. M. (1973). Solution of Equations in Euclidean and Banach Spaces. 3rd ed. Academic Press.
• Traub, J. F. (1964). Iterative Methods for the Solution of Equations. Prentice-Hall.
• King, R. F. (1973). "A family of fourth order methods for nonlinear equations". SIAM Journal on Numerical Analysis, 10(5), 876–879.
• Schröder, E. (1870). "Über unendlich viele Algorithmen zur Auflösung der Gleichungen". Mathematische Annalen, 2, 317–365.