Inexact Newton Methods with Adaptive Linear Tolerances

130 concepts105 papers1 proposal

When simulating complex physical phenomena—such as fluid dynamics, structural mechanics, or financial derivatives—we routinely encounter large systems of nonlinear equations. The standard mathematical tool for solving these is Newton's method (or related Picard and quasilinearization variants), which iteratively linearizes the problem.

This creates a nested, two-level loop structure:

  1. The Outer Loop: Updates the global nonlinear state estimate ($x_{k+1} = x_k + \Delta x_k$).
  2. The Inner Loop: Solves a massive linear system governed by the Jacobian matrix ($J_k \Delta x_k = -f(x_k)$) to find the next update step.

Historically, computational frameworks spent enormous effort solving this inner linear system to near-perfect machine precision at every single outer step. However, a powerful realization has transformed modern scientific computing: solving early inner linear systems exactly is a massive waste of computational resources.

By intentionally solving the inner linear systems inexactly using adaptive tolerances, we can drastically accelerate nonlinear solvers without sacrificing their final accuracy or mathematical robustness.


The Core Inefficiency of Exact Linearization

To understand why inexact methods work, consider the behavior of Newton's method. As shown by David John et al. in GOODE: A Gaussian Off-The-Shelf Ordinary Differential Equation Solver, quasilinearization transforms a difficult nonlinear problem into a sequence of linear sub-problems. This strategy is ubiquitous; for instance, Federico Danieli et al. in DeepPCR: Parallelizing Sequential Operations in Neural Networks leverage an iterative Newton-based framework to linearize highly sequential operations so they can be processed by parallel linear solvers.

However, during the early iterations of the outer loop, the current estimate $x_k$ is often far from the true solution. Because the Jacobian matrix $J_k$ depends directly on $x_k$, the linear system being solved in the inner loop is itself only a rough approximation of the local nonlinear landscape.

If the linear system itself is based on an inaccurate outer state, calculating its exact solution down to the 10th decimal place yields no practical benefit. The resulting update step $\Delta x_k$ will still point in a generally correct direction, but the high-precision details are immediately erased by the next outer nonlinear update.


The Intuition of Adaptive Tolerances

Inexact Newton methods exploit this mismatch by introducing an adaptive stopping criterion for the inner linear solver. Instead of solving $J_k \Delta x_k = -f(x_k)$ exactly, the inner solver terminates as soon as the linear residual satisfies:

$$\| J_k \Delta x_k + f(x_k) \| \le \eta_k \| f(x_k) \|$$

Here, $\eta_k \in 0, 1)$ is known as the forcing term or adaptive tolerance.

The core mechanism relies on dynamically adjusting $\eta_k$ based on the progress of the outer loop:

  • Far from the solution (Early iterations): The nonlinear residual $\|f(x_k)\|$ is large. We choose a loose, large tolerance $\eta_k$ (e.g., $\eta_k = 0.1$). The inner solver does a minimal amount of work—just enough to find a rough descent direction—and hands control back to the outer loop.
  • Close to the solution (Late iterations): As the outer loop converges, $\|f(x_k)\|$ shrinks. To preserve Newton's signature quadratic convergence, we progressively tighten $\eta_k$ toward zero, forcing the inner solver to compute highly precise updates when they actually matter.

As noted by [William Gropp in Parallel Newton-Krylov-Schwarz Algorithms for the Transonic Full Potential Equation, solving inner linear systems to a relatively loose tolerance early on significantly reduces total computation time without compromising the convergence of the outer nonlinear solver. This avoids the computational waste of over-solving intermediate linear steps.

Kookjin Lee reinforces this intuition in Inexact Methods for Symmetric Stochastic Eigenvalue Problems, demonstrating that high precision in early outer-loop iterations provides no benefit to the final convergence rate, making adaptive stopping criteria essential for optimizing overall computational efficiency. Similarly, Lars Diening et al. in A Relaxed Kačanov iteration for the p-poisson problem emphasize that failing to use inexact solvers for linear sub-problems leads to high cumulative computational costs that can render iterative linearization prohibitively expensive.


Scaling Up: The Newton-Krylov-Schwarz Architecture

For large-scale engineering applications, the inner linear system cannot be solved using direct matrix inversion due to memory constraints. Instead, researchers combine inexact Newton methods with iterative Krylov subspace methods (like GMRES) and domain decomposition preconditioning. This hierarchical framework is often referred to as Newton-Krylov-Schwarz (NKS).

[Outer Loop: Newton Iteration]
       │
       ▼ (Linearize system around current guess x_k)
[Inner Loop: Krylov Subspace Solver (e.g., GMRES)] ──► [Terminates early via Adaptive Tolerance η_k]
       │
       ▼ (Preconditioned via Schwarz Domain Decomposition)
[Subdomain Solvers: Processed in Parallel]

This architecture scales exceptionally well on modern supercomputers. Jizu Huang et al. in Parallel energy-stable solver for a coupled Allen-Cahn and Cahn-Hilliard system demonstrate that integrating inexact Newton methods with Krylov subspace solvers and Schwarz-type domain decomposition allows numerical solvers to scale efficiently to tens of thousands of processing cores. By decomposing the global problem into smaller sub-domains and solving them approximately, they decouple physical non-linearities from the linear system solution.

This framework is highly adaptable across diverse domains:


Robustness Across Mathematical Landscapes

A common concern is whether relaxing the precision of the inner loop introduces numerical instability, particularly in highly nonlinear or singular problems. Empirical evidence shows that when paired with proper stabilization techniques—such as consistent linearization or damping—inexact solvers remain remarkably robust.

For instance, Shoaib A. Goraya et al. in Two-way coupled stabilized finite element method for transient thermal convection in irregular geometries with electromagnetic force fields show that applying consistent linearization to stabilized equations ensures that nonlinear solvers achieve quadratic convergence, drastically reducing the total number of iterations required even when handling highly nonlinear multi-physics interactions.

In the context of highly singular partial differential equations, such as the elliptic Monge-Ampère equation, Brittany D. Froese et al. in Convergent Finite Difference Solvers for Viscosity Solutions of the Elliptic Monge-Ampère Equation in Dimensions Two and Higher demonstrate that a damped Newton's method successfully converges to the correct discretized solution. Building on this, Jean-David Benamou et al. in Numerical solution of the Optimal Transportation problem using the Monge-Ampère equation show that employing Newton's method to solve discretized optimal transport systems results in a remarkably fast solver, achieving computational speeds comparable to solving a simple linear Laplace equation.

Finally, the benefits extend to time-dependent evolution equations. Yuka Hashimoto et al. in Inexact shift-invert Arnoldi method for evolution equations prove that allowing internal linear systems within a subspace projection process to be solved approximately with an adaptive tolerance significantly reduces the computational overhead per step, without sacrificing the precision of the final numerical solution.

By matching the inner linear precision to the outer nonlinear error, inexact Newton methods eliminate redundant calculations, providing a mathematically rigorous blueprint for high-performance scientific computing.

History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_iterative_nonlinear_solver_6e3bb9fe,
  title = {iterative nonlinear solver},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/iterative-nonlinear-solver/rdr_6e3bb9fe599742ceb5c1a453034f445c},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_iterative_nonlinear_solver_6e3bb9fe_v1,
  title = {iterative nonlinear solver},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/iterative-nonlinear-solver/rdr_6e3bb9fe599742ceb5c1a453034f445c/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake