Interval Newton's Method

Interval Newton's method extends the classical Newton method to work with intervals instead of single points.

For a system of equations $F(x) = 0$, the method works as follows:

  1. Initialization: Start with an initial interval $X^{(0)}$ that is known to contain a solution

  2. Iteration: For each step $k$, compute:

    \[X^{(k+1)} = (m(X^{(k)}) - F(m(X^{(k)})) / F'(X^{(k)})) \cap X^{(k)}\]

    where:

    • \[m(X^{(k)})\]

      is the midpoint of the current interval

    • \[F'(X^{(k)})\]

      is the interval Jacobian matrix

    The intersection with $X^{(k)}$ ensures the interval never grows, providing better convergence guarantees.

  3. Convergence: The method continues until the interval becomes sufficiently small or other stopping criteria are met.

Available Functions

Types of input

LACE.jl supports polynomial systems with the following coefficient types:

  • Rational coefficients using AbstractAlgebra or Nemo polynomials
  • Interval coefficients using the BigInterval type from MPFI.jl with DynamicPolynomials

Variants of the algorithm

LACE provides two main variants of the interval Newton method:

Standard Interval Newton (interval_newton): Uses intersection operations between iterations. Typically used when:

  • The initial interval is known to contain the solution

Classical Interval Newton (interval_classic_newton): Traditional implementation without intersection operations. Typically used when:

  • The initial interval may not contain the solution

Standard Interval Newton Method

The standard interval Newton method is the recommended choice for applications where an interval containing a single root is already known and needs to be refined.

<!– See LACE.interval_newton –>

Classical Interval Newton Method

The classical interval Newton method provides the traditional implementation without intersection operations. This can be useful when:

  • The input polynomial system has interval coefficients and the starting point/interval is either a single point or an interval that does not contain (all) the solutions.
  • The input polynomial system has rational coefficients and the starting interval does not necessarily contain the solution.

<!– LACE.interval_classic_newton –>

Parameter Guidelines

Precision Settings

  • input_precision: Is the precision of the input coefficients when converted in the internal representation. Should be less than the precision of input coefficients for meaningful results.
  • work_precision: Higher values give more accurate intermediate results but slower computation
  • target_precision: Controls the desired tightness of the solution interval
  • output_precision: Should be ≤ work_precision for meaningful results

Iteration Control

  • max_nb_loops: Start with 10-20 for most problems
  • refine: Use 1 for most cases, 0 only for specific heuristics
  • verbose: Use 1 for debugging, 0 for quiet operation

Usage Examples

Basic Usage with AbstractAlgebra

using LACE, AbstractAlgebra, MPFI

# Define polynomial ring and variables
R, (x, y) = polynomial_ring(QQ, ["x", "y"])

# Define system of equations
f = x^2 + y^2 - 1  # Circle: x² + y² = 1
g = x - y          # Line: x = y

sys = [f, g]

# Initial point (approximate solution)
initial_point = [BigFloat(0.7), BigFloat(0.7)]

input_precision = 52
target_precision = 52
work_precision = 52
output_precision = 52
max_nb_loops = 10

# Solve using interval Newton
 status, solution, constants = interval_newton(sys, initial_point, input_precision, work_precision,target_precision,output_precision,max_nb_loops)

println("Status: ", status)
println("Solution: ", solution)
println("Kantorovich constants: ", constants)

Using DynamicPolynomials with Intervals