API Reference

RootSolvers.jl

A Julia package for solving roots of non-linear equations using various numerical methods. Contains functions for finding zeros of scalar functions using robust iterative algorithms.

The main entry point is find_zero, which supports multiple root-finding methods and tolerance criteria.

Supported Methods

• Secant Method: Requires two initial guesses, uses linear interpolation
• Bisection Method: Requires bracketing interval with sign change, converges linearly
• Regula Falsi Method: Requires bracketing interval with sign change
• Brent's Method: Requires bracketing interval, combines bisection, secant, and inverse quadratic interpolation
• Newton's Method with AD: Requires one initial guess, uses automatic differentiation
• Newton's Method: Requires one initial guess and user-provided derivative

GPU and Broadcasting

For high-performance applications such as GPU kernels, one can broadcast find_zero efficiently by passing the method type directly (e.g., SecantMethod).

Method Selection Guide

• Bracketing methods (Bisection, Regula Falsi, Brent's): Use when you know an interval containing the root
• Brent's method: Recommended for robust, guaranteed convergence with superlinear rate
• Secant method: Good when you have two guesses but no bracketing interval
• Newton's methods: Fastest convergence when you have a good initial guess

Examples

using RootSolvers

# Find the square root of a quadratic equation using the secant method
sol = find_zero(x -> x^2 - 100^2,
               SecantMethod{Float64}(0.0, 1000.0),
               CompactSolution());

println(sol)
# CompactSolutionResults{Float64}:
# ├── Status: converged
# └── Root: 99.99999999994358

# Access the root value
root_value = sol.root  # 99.99999999994358

# Use Brent's method for robust convergence with bracketing interval
sol_brent = find_zero(x -> x^3 - 8,
                     BrentsMethod{Float64}(-1.0, 3.0),
                     CompactSolution());

# Use Newton's method with automatic differentiation for faster convergence
sol_newton = find_zero(x -> x^3 - 27,
                      NewtonsMethodAD{Float64}(2.0),
                      VerboseSolution());

find_zero(f, method, soltype=CompactSolution(), tol=nothing, maxiters=1_000)

Find a root of the scalar function f using the specified numerical method.

This is the main entry point for root finding in RootSolvers.jl. Given a function f, it finds a value x such that f(x) ≈ 0 using iterative numerical methods. The function supports various root-finding algorithms, tolerance criteria, and solution formats.

Arguments

• f::Function: The function for which to find a root. Should take a real scalar input and return a real scalar output.
• method::RootSolvingMethod: The numerical method to use. Available methods:
  • BisectionMethod: Bracketing method maintaining sign change (linear convergence, guaranteed)
  • SecantMethod: Uses linear interpolation between two points (superlinear convergence)
  • RegulaFalsiMethod: Bracketing method maintaining sign change (linear convergence, guaranteed)
  • BrentsMethod: Robust bracketing method combining bisection, secant, and inverse quadratic interpolation
  • NewtonsMethodAD: Newton's method with automatic differentiation (quadratic convergence)
  • NewtonsMethod: Newton's method with user-provided derivative (quadratic convergence)
• soltype::SolutionType: Format of the returned solution (default: CompactSolution):
  • CompactSolution: Returns only root and convergence status (GPU-compatible)
  • VerboseSolution: Returns detailed diagnostics and iteration history (CPU-only)
  • TwoPointSolution: Additionally returns the final two-point state (x0, x1, y0, y1) (two-point methods only; GPU-compatible)
• tol::Union{Nothing, AbstractTolerance}: Convergence criterion. If nothing (default), uses SolutionTolerance(1e-4) for Float64 or 1e-3 otherwise. Available tolerance types:
  • ResidualTolerance: Based on |f(x)|
  • SolutionTolerance: Based on |x_{n+1} - x_n|
  • RelativeSolutionTolerance: Based on |(x_{n+1} - x_n)/x_n|
  • RelativeOrAbsoluteSolutionTolerance: Combined relative and absolute tolerance
  • NoTolerance: Never converges; runs exactly maxiters iterations (fixed-iteration GPU workloads)
• maxiters::Int: Maximum number of iterations allowed (default: 1,000)

Returns

• AbstractSolutionResults: Solution object containing the root and convergence information. The exact type depends on the soltype parameter:
  • CompactSolutionResults: Contains root and converged fields
  • VerboseSolutionResults: Additionally contains err, iter_performed, and iteration history
  • TwoPointSolutionResults: Contains root, converged, err, and the final two-point state x0, x1, y0, y1 (two-point methods only; see TwoPointSolution)

Examples

using RootSolvers

# Find square root of 2 using secant method
sol = find_zero(x -> x^2 - 2, SecantMethod{Float64}(1.0, 2.0))
println("√2 ≈ $(sol.root)")  # √2 ≈ 1.4142135623730951

# Use Newton's method with automatic differentiation for faster convergence
sol = find_zero(x -> x^3 - 27, NewtonsMethodAD{Float64}(2.0))
println("∛27 = $(sol.root)")  # ∛27 = 3.0

# Get detailed iteration history
sol = find_zero(x -> exp(x) - 2, 
               NewtonsMethodAD{Float64}(0.5), 
               VerboseSolution())
println("ln(2) ≈ $(sol.root) found in $(sol.iter_performed) iterations")

# Use custom tolerance
tol = RelativeOrAbsoluteSolutionTolerance(1e-12, 1e-15)
sol = find_zero(x -> cos(x), 
               NewtonsMethodAD{Float64}(1.0), 
               CompactSolution(), 
               tol)
println("π/2 ≈ $(sol.root)")

# Robust bracketing method for difficult functions
sol = find_zero(x -> x^3 - 2x - 5, RegulaFalsiMethod{Float64}(2.0, 3.0))

Notes

f must be scalar and real-valued; systems of equations and complex roots are not supported.

find_zero never throws when a method fails to converge — it always returns a results object, so check sol.converged before using sol.root. A bracketing method given an interval with no sign change returns converged = false with sol.root set to the endpoint of smaller residual, rather than erroring. This non-throwing contract is what makes find_zero safe to broadcast on the GPU.

The solution-based tolerances (SolutionTolerance, RelativeSolutionTolerance) measure the change between successive iterates, |x_{n+1} - x_n|, for every method, including the bracketing ones. Every tolerance also reports convergence once |f(x)| drops below the machine epsilon of the residual type (except NoTolerance, which never reports convergence and runs exactly maxiters iterations).

For the two-point methods, the endpoint residuals can be passed pre-evaluated (find_zero(f, MethodType, x0, x1, y0, y1, ...)) to avoid re-evaluating f at endpoints the caller has already probed (e.g., during a bracket search).

Batch and GPU Root-Finding (Broadcasting)

You can broadcast find_zero over arrays of initial guesses to solve many root-finding problems in parallel, including on the GPU. To broadcast efficiently while using the same method for all problems, pass the method type:

using CUDA, RootSolvers
x0 = CUDA.fill(1.0, 1000)  # 1000 initial guesses on the GPU
# Pass the method type (e.g. SecantMethod) directly
sol = find_zero.(x -> x.^2 .- 2, SecantMethod, x0, x0 .+ 1, CompactSolution())

This is especially useful for large-scale or batched root-finding on GPUs. Only CompactSolution and TwoPointSolution are GPU-compatible (VerboseSolution stores iteration history and is CPU-only).

Method Selection Guide

• BisectionMethod: Simple general-purpose bracketing method, slow but guaranteed convergence
• SecantMethod: Good general-purpose method, no derivatives needed
• RegulaFalsiMethod: Use when you need guaranteed convergence with a bracketing interval
• BrentsMethod: Robust bracketing method combining bisection, secant, and inverse quadratic interpolation
• NewtonsMethodAD: Fastest convergence when derivatives are available via autodiff
• NewtonsMethod: Use when you can provide analytical derivatives efficiently

See Also

• BisectionMethod, SecantMethod, RegulaFalsiMethod, BrentsMethod, NewtonsMethodAD, NewtonsMethod
• CompactSolution, VerboseSolution, TwoPointSolution
• ResidualTolerance, SolutionTolerance, NoTolerance

SecantMethod{FT} <: RootSolvingMethod{FT}

The secant method for root finding, which uses linear interpolation between two points to approximate the derivative. This method requires two initial guesses but does not require the function to be differentiable or the guesses to bracket a root.

The method uses the recurrence relation:

\[x_{n+1} = x_n - f(x_n) \frac{x_n - x_{n-1}}{f(x_n) - f(x_{n-1})}\]

Convergence

• Order: Approximately 1.618 (superlinear)
• Requirements: Two initial guesses, continuous function
• Advantages: No derivative required, fast convergence
• Disadvantages: May not converge if initial guesses are poor

Fields

• x0::FT: First initial guess.
• x1::FT: Second initial guess.

Examples

method = SecantMethod{Float64}(0.0, 2.0)
sol = find_zero(x -> x^3 - 8, method)

RegulaFalsiMethod{FT} <: RootSolvingMethod{FT}

The Regula Falsi (false position) method for root finding. This is a bracketing method that maintains the sign change property and uses linear interpolation to find the root.

The method requires that f(x0) and f(x1) have opposite signs, ensuring that a root exists in the interval [x0, x1].

Convergence

• Order: Linear (slower than Newton's method)
• Requirements: Bracketing interval with f(x0) * f(x1) < 0
• Advantages: Guaranteed convergence, robust
• Disadvantages: Slower convergence than other methods

Fields

• x0::FT: Lower bound of bracketing interval.
• x1::FT: Upper bound of bracketing interval.

Examples

# Find root of x^3 - 2 in interval [-1, 2]
method = RegulaFalsiMethod{Float64}(-1.0, 2.0)
sol = find_zero(x -> x^3 - 2, method)

BisectionMethod{FT} <: RootSolvingMethod{FT}

The bisection method for root finding. This is a simple bracketing method that divides the interval in half at each iteration. The method requires that f(x0) and f(x1) have opposite signs, ensuring that a root exists in the interval [x0, x1].

The method uses the recurrence relation:

\[x_{n+1} = \frac{x_0 + x_1}{2}\]

where the interval [x0, x1] is updated based on the sign of f(x_{n+1}).

Convergence

• Order: Linear (slower than Newton's method)
• Requirements: Bracketing interval with f(x0) * f(x1) < 0
• Advantages: Guaranteed convergence, simple implementation
• Disadvantages: Slower convergence than other methods

Fields

• x0::FT: Lower bound of bracketing interval.
• x1::FT: Upper bound of bracketing interval.

Examples

# Find root of x^3 - 2 in interval [-1, 2]
method = BisectionMethod{Float64}(-1.0, 2.0)
sol = find_zero(x -> x^3 - 2, method)

BrentsMethod{FT} <: RootSolvingMethod{FT}

Brent's method for root finding, which combines the bisection method, secant method, and inverse quadratic interpolation. This is a bracketing method that maintains the sign change property and provides superlinear convergence.

The method requires that f(x0) and f(x1) have opposite signs, ensuring that a root exists in the interval [x0, x1].

Convergence

• Order: Superlinear (faster than Regula Falsi)
• Requirements: Bracketing interval with f(x0) * f(x1) < 0
• Advantages: Guaranteed convergence, fast convergence, robust
• Disadvantages: More complex than simpler bracketing methods

Fields

• x0::FT: Lower bound of bracketing interval.
• x1::FT: Upper bound of bracketing interval.

Examples

# Find root of x^3 - 2 in interval [-1, 2]
method = BrentsMethod{Float64}(-1.0, 2.0)
sol = find_zero(x -> x^3 - 2, method)

NewtonsMethodAD{FT} <: RootSolvingMethod{FT}

Newton's method for root finding using automatic differentiation to compute derivatives. This method provides quadratic convergence when close to the root and the derivative is non-zero. The implementation includes step size limiting and backtracking line search for robustness, and falls back to the secant method when the derivative becomes too small.

The method uses the iteration

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

where the derivative f'(x_n) is computed using ForwardDiff.jl.

Convergence

• Order: Quadratic (very fast near the root)
• Requirements: Differentiable function, good initial guess
• Advantages: Fast convergence, automatic derivative computation, robust step size control
• Disadvantages: May not converge if initial guess is poor or derivative is zero

Fields

• x0::FT: Initial guess for the root.

Examples

# Find cube root of 27
method = NewtonsMethodAD{Float64}(2.0)
sol = find_zero(x -> x^3 - 27, method)

NewtonsMethod{FT} <: RootSolvingMethod{FT}

Newton's method for root finding where the user provides both the function and its derivative. This method provides quadratic convergence when close to the root. The implementation includes step size limiting and backtracking line search for robustness, and falls back to the secant method when the derivative becomes too small.

The method uses the iteration

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

Convergence

• Order: Quadratic (very fast near the root)
• Requirements: Function and derivative, good initial guess
• Advantages: Fast convergence, no automatic differentiation overhead, robust step size control
• Disadvantages: Requires manual derivative computation

Fields

• x0::FT: Initial guess for the root.

Notes

When using this method, your function f should return a tuple (f(x), f'(x)) containing both the function value and its derivative at x.

Examples

# Find root of x^2 - 4, providing both function and derivative
f_and_df(x) = (x^2 - 4, 2x)
method = NewtonsMethod{Float64}(1.0)
sol = find_zero(f_and_df, method)

CompactSolution <: SolutionType

A memory-efficient solution type that returns only essential information about the root.

When used with find_zero, returns a CompactSolutionResults object containing only the root value and convergence status. This solution type is GPU-compatible and suitable for high-performance applications where memory usage is critical.

Accessing Results

The returned CompactSolutionResults object contains the following fields:

• sol.root: The found root value.
• sol.converged: Boolean indicating if the method converged.

Examples

sol = find_zero(x -> x^2 - 4, 
               SecantMethod{Float64}(0.0, 3.0), 
               CompactSolution())

# Access the root
println("Root: $(sol.root)")

# Check convergence
if sol.converged
    println("Root found successfully!")
else
    println("Method failed to converge")
end

VerboseSolution <: SolutionType

A solution type that returns detailed information about the root-finding process, including iteration history and convergence diagnostics.

When used with find_zero, returns a VerboseSolutionResults object containing the root, convergence status, error information, and complete iteration history.

Accessing Results

The returned VerboseSolutionResults object contains the following fields:

• sol.root: The found root value.
• sol.converged: Boolean indicating if the method converged.
• sol.err: Final error value (function value at the root).
• sol.iter_performed: Number of iterations performed.
• sol.root_history: Vector of all root values during iteration.
• sol.err_history: Vector of all error values during iteration.

Notes

This solution type stores iteration history and is primarily intended for CPU computations. For GPU computations or when memory usage is a concern, use CompactSolution instead.

Examples

sol = find_zero(x -> x^2 - 4, SecantMethod(1.0, 3.0), VerboseSolution())

# Access the root
root_value = sol.root

# Check convergence and diagnostics
if sol.converged
    println("Root found: ", root_value)
    println("Converged in ", sol.iter_performed, " iterations")
    println("Final error: ", sol.err)
else
    println("Method failed to converge")
end

# Access iteration history
println("First iteration root: ", sol.root_history[1])
println("Last iteration root: ", sol.root_history[end])

TwoPointSolution <: SolutionType

A memory-efficient, GPU-compatible solution type that, in addition to the root and convergence status, returns the final state of the two working points of a two-point method: the endpoints x0, x1 and their residuals y0, y1.

Supported by the two-point methods (SecantMethod, BisectionMethod, RegulaFalsiMethod, BrentsMethod). For the bracketing methods, the final points bracket the root whenever a sign change was found (y0 * y1 <= 0); if the input interval contained no sign change, the returned points are the inputs themselves and converged == false. For SecantMethod, the points are the last two iterates (no bracketing guarantee).

This solution type is intended for callers that implement their own convergence policy or post-processing on top of the solver, e.g., assessing convergence from the final bracket width after a fixed number of iterations (see NoTolerance), or sharpening the root with a final interpolation of the bracket at no extra residual evaluation.

Accessing Results

The returned TwoPointSolutionResults object contains the following fields:

• sol.root: The found root value.
• sol.converged: Boolean indicating if the method converged.
• sol.err: Residual f(root) at the returned root.
• sol.x0, sol.x1: Final positions of the two working points.
• sol.y0, sol.y1: Residuals at x0 and x1.

Examples

sol = find_zero(x -> x^2 - 4, RegulaFalsiMethod{Float64}(0.0, 3.0), TwoPointSolution())
width = abs(sol.x1 - sol.x0)  # final bracket width

CompactSolutionResults{FT} <: AbstractSolutionResults{FT}

Results type for CompactSolution containing minimal output.

VerboseSolutionResults{FT} <: AbstractSolutionResults{FT}

Results type for VerboseSolution containing detailed iteration history.

TwoPointSolutionResults{XT, YT} <: AbstractSolutionResults{XT}

Results type for TwoPointSolution: the root and convergence status plus the final two-point state (x0, x1, y0, y1) of the solver.

AbstractTolerance{FT}

Abstract type for tolerance criteria in RootSolvers.jl.

This is the base type for all tolerance types that define convergence criteria for root-finding algorithms. Each concrete tolerance type should implement the callable interface (tol)(x1, x2, y) for convergence checking. By convention, a tolerance also reports convergence when the residual |y| falls below the machine epsilon of its type, so an exact root is always detected regardless of the criterion.

Type Parameters

• FT: The floating-point type for tolerance values (e.g., Float64, Float32).

Subtypes:

• ResidualTolerance{FT}: Based on |f(x)|.
• SolutionTolerance{FT}: Based on |x_{n+1} - x_n|.
• RelativeSolutionTolerance{FT}: Based on |(x_{n+1} - x_n)/x_n|.
• RelativeOrAbsoluteSolutionTolerance{FT}: Combined relative and absolute tolerance.

Interface Requirements

All concrete subtypes must implement:

• (tol)(x1, x2, y): Check convergence using three arguments (previous iterate, current iterate, function value)

Examples

# Define a custom tolerance type
struct MyTolerance{FT} <: AbstractTolerance{FT}
    threshold::FT
end

# Implement the required interface
(tol::MyTolerance)(x1, x2, y) = abs(x2 - x1) < tol.threshold || abs(y) < eps(typeof(y))

# Use with find_zero
sol = find_zero(x -> x^2 - 4, SecantMethod(1.0, 3.0), CompactSolution(), MyTolerance(1e-6))

SolutionTolerance{FT}

A convergence criterion based on the absolute difference between consecutive iterates. The iteration stops when |x_{n+1} - x_n| < tol, where tol is the specified tolerance. Convergence is also triggered if |f(x)| is smaller than the machine epsilon for the value type.

This tolerance is appropriate when you want to ensure that consecutive iterates are sufficiently close, indicating that the solution has stabilized.

Fields

• tol::FT: Tolerance threshold for |x_{n+1} - x_n|.

Examples

tol = SolutionTolerance(1e-8)
sol = find_zero(x -> x^3 - 8, 
               SecantMethod{Float64}(1.0, 3.0),
               CompactSolution(),
               tol)

ResidualTolerance{FT}

A convergence criterion based on the absolute value of the residual (function value). The iteration stops when |f(x)| < tol, where tol is the specified tolerance (limited to the machine epsilon of the function value type).

This tolerance is appropriate when you want to ensure that the function value is sufficiently close to zero, regardless of how close consecutive iterates are.

Fields

• tol::FT: Tolerance threshold for |f(x)|.

Examples

tol = ResidualTolerance(1e-10)
sol = find_zero(x -> x^2 - 4, 
               NewtonsMethodAD{Float64}(1.0),
               CompactSolution(),
               tol)

RelativeSolutionTolerance{FT}

A convergence criterion based on the relative difference between consecutive iterates. The iteration stops when |(x_{n+1} - x_n)/x_n| < tol, where tol is the specified tolerance. Convergence is also triggered if |f(x)| is smaller than the machine epsilon for the value type.

This tolerance is appropriate when you want to ensure convergence relative to the magnitude of the solution, which is useful when the root value might be very large or very small.

Fields

• tol::FT: Relative tolerance threshold.

Examples

tol = RelativeSolutionTolerance(1e-6)
sol = find_zero(x -> x^2 - 1e6, 
               NewtonsMethodAD{Float64}(500.0),
               CompactSolution(),
               tol)

RelativeOrAbsoluteSolutionTolerance{FT}

A robust convergence criterion combining both relative and absolute tolerances. The iteration stops when either |(x_{n+1} - x_n)/x_n| < rtol OR |x_{n+1} - x_n| < atol.

This tolerance provides robust behavior across different scales of root values:

• The relative tolerance rtol ensures accuracy for large roots.
• The absolute tolerance atol ensures convergence when the root is near zero.

Fields

• rtol::FT: Relative tolerance threshold.
• atol::FT: Absolute tolerance threshold.

Examples

# Use relative tolerance of 1e-6 and absolute tolerance of 1e-10
tol = RelativeOrAbsoluteSolutionTolerance(1e-6, 1e-10)
sol = find_zero(x -> x^2 - 1e-8, 
               NewtonsMethodAD{Float64}(1e-3),
               CompactSolution(),
               tol)

NoTolerance{FT}

A criterion that forces the solver to run for exactly maxiters iterations, irrespective of tolerance reached, and returns converged = false. This is intended for GPU kernels where a data-dependent early exit is undesirable.

Callers assess convergence themselves from the returned state. On the GPU, pair it with TwoPointSolution (isbits, non-allocating) and check the bracket width abs(sol.x1 - sol.x0), or with CompactSolution and re-evaluate f(sol.root). On the CPU, VerboseSolution gives the richest picture — the final residual sol.err and the full sol.root_history/sol.err_history — but allocates, so it is CPU-only.

The type parameter FT is unused and exists only to satisfy the AbstractTolerance{FT} interface; the zero-argument constructor NoTolerance() is the intended entry point.

Examples

# Fixed-cost GPU-style solve: endpoint residuals already known from a bracket
# search, exactly 10 regula falsi iterations (10 residual evaluations, no
# data-dependent exit), convergence assessed by the caller from the bracket width
x0, x1 = 0.0, 1.0
y0, y1 = f(x0), f(x1)   # evaluated while locating the bracket
sol = find_zero(f, RegulaFalsiMethod, x0, x1, y0, y1, TwoPointSolution(),
                NoTolerance(), 10)
converged = abs(sol.x1 - sol.x0) < 1e-3