Principle:Avhz RustQuant Root Finding

Knowledge Sources	Brent - Algorithms for Minimization Without Derivatives Newton-Raphson Method
Domains	Numerical_Methods, Mathematics
Last Updated	2026-02-07 21:00 GMT

Overview

Root-finding algorithms for solving equations of the form f(x) = 0, implementing bisection, Brent's method, and Newton-Raphson.

Description

Root Finding in RustQuant provides a trait-based framework for numerical root-finding algorithms. The core abstraction is the Rootfinder trait, which defines the interface all solvers must implement:

• value(x) -- Evaluate the objective function at x.
• derivative(x) -- Evaluate the derivative at x (returns 0.0 for derivative-free methods).
• solve_impl() -- The internal solver algorithm.
• solve() -- The public entry point that performs bounds checking and bracket expansion before calling solve_impl().

A companion RootfinderData struct stores solver configuration and state, including accuracy tolerance, step size, search interval bounds, whether bounds are enforced, and an iteration counter. It defaults to machine-epsilon-based accuracy (f64::EPSILON.sqrt()) with a maximum of 1000 iterations.

Three algorithms are implemented:

• Bisection -- A bracketing method that repeatedly halves the interval. Guaranteed to converge for continuous functions but converges linearly. Requires only function evaluations.
• Brent's method -- A hybrid algorithm combining bisection, secant, and inverse quadratic interpolation. It inherits the robustness of bisection while achieving superlinear convergence in practice. Requires only function evaluations.
• Newton-Raphson -- A derivative-based method with quadratic convergence near the root. Falls back to bisection when the Newton step would leave the bracket or convergence is too slow. Requires both function and derivative evaluations.

All three solvers share a common bracket-expansion phase in their solve() method that uses a growth factor of 1.6 to widen the search interval until a sign change is found.

Usage

Use root-finding algorithms in quantitative finance for implied volatility calculation (solving for the volatility that makes a pricing model match an observed market price), yield-to-maturity computation, and calibration of model parameters. Brent's method is the default choice for robustness and speed. Newton-Raphson is preferred when an analytical derivative is available, such as the Black-Scholes vega for implied volatility.

Theoretical Basis

Bisection halves the bracket at each step:

$x_{\text{mid}}=\frac{x_{\text{min}}+x_{\text{max}}}{2}$

Convergence rate is linear with error bounded by $\frac{x_{\text{max}}-x_{\text{min}}}{2^n}$ after $n$ iterations.

Newton-Raphson updates via the tangent line:

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

Convergence is quadratic near a simple root: $|x_{n+1}-r|\le C|x_n-r{|}^2$.

Brent's method combines inverse quadratic interpolation with bisection fallback, achieving superlinear convergence (order approximately 1.618) while maintaining the guaranteed convergence of bisection.

The implementation includes a proximity test using a tolerance of $42\cdot \epsilon$ (where $\epsilon$ is machine epsilon) for determining when values are effectively zero or equal.

Related Pages

Implemented By

• Implementation:Avhz_RustQuant_Brent_Method
• Implementation:Avhz_RustQuant_Newton_Raphson
• Implementation:Avhz_RustQuant_RootFinder_Trait
• Implementation:Avhz_RustQuant_Bisection_Method