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

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

Example

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 scalar input and return a 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)
  • 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)
• tol::Union{Nothing, AbstractTolerance}: Convergence criterion (default: SolutionTolerance(1e-3)):
  • 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
• maxiters::Int: Maximum number of iterations allowed (default: 10,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

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))

Batch and GPU Root-Finding (Broadcasting)

You can broadcast find_zero over arrays of methods or initial guesses to solve many root-finding problems in parallel, including on the GPU:

using CUDA, RootSolvers
x0 = CUDA.fill(1.0, 1000)  # 1000 initial guesses on the GPU
method = SecantMethod.(x0, x0 .+ 1)
# f should be broadcastable over arrays
sol = find_zero.(x -> x.^2 .- 2, method, CompactSolution())

This is especially useful for large-scale or batched root-finding on GPUs. Only CompactSolution is GPU-compatible.

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
• NewtonsMethodAD: Fastest convergence when derivatives are available via autodiff
• NewtonsMethod: Use when you can provide analytical derivatives efficiently

See Also

• BisectionMethod, SecantMethod, RegulaFalsiMethod, NewtonsMethodAD, NewtonsMethod
• CompactSolution, VerboseSolution
• ResidualTolerance, SolutionTolerance

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

Example

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

Example

# 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

Example

# 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

Example

# 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.

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

Example

# 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.

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

Note

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.

Example

# 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

Example

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

Note

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.

Example

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])

AbstractTolerance{FT} <: AbstractType

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.

Type Parameters

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

Concrete Implementations

• 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)

Example

# 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|

Example

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)|

Example

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 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

Warning

This tolerance criterion can fail if x_n ≈ 0 during iteration, as it involves division by x_n. Consider using RelativeOrAbsoluteSolutionTolerance for more robust behavior.

Example

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

Example

# 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)