Motivation
An implicit formula defines an equation for the next state. It does not by itself compute that state. A convergence theorem for exact implicit steps can be invalidated by stopping the algebraic solver too early, while solving every step to machine precision may spend effort far below the discretization error. We need a mathematical link between an equation residual, a state error and its accumulation over many steps.
Newton's method supplies fast local convergence when the Jacobian is invertible and does not vary too rapidly. These hypotheses have content. A nonlinear equation can have several roots, an ill-conditioned derivative or an initial guess that cycles. We will separate existence of the intended implicit root from convergence of the iteration used to find it.
The model is a finite-dimensional ODE with Euclidean vector norm and its induced matrix norm. The results below do not claim that every stiff nonlinear equation satisfies a global Lipschitz condition or that a single Newton theorem covers every practical solver.
Definitions
Backward Euler seeks a root of
Newton iteration is , where . In actual computation the displayed inverse means solving a linear system; explicitly forming an inverse is unnecessary. An unscaled algebraic residual is for an approximate step. The residual of the equation divided by is instead and has a different numerical tolerance.
The Euler exact-start defect is ; the trapezoidal defect uses its corresponding endpoint average. Both are unscaled state defects. For trapezoidal time stepping the root equation is
A Lipschitz constant controls state differences of . A second derivative bound controls the variation of . A bound on the inverse Jacobian converts an equation residual to a state error only when the relevant path and invertibility assumptions hold. Residual size and state accuracy are therefore related through conditioning, not by numerical equality.
Theorem/proposition
Theorem 10.1.1
(A complete sufficient Newton guarantee for backward Euler)
Fix the step time and suppose is globally in the state, with , , and . Then the implicit Euler root exists uniquely. Every Newton Jacobian is invertible, and
If , all iterates stay in that initial error ball and converge quadratically. A computable sufficient test for starting at is . When , Newton reaches the linear root in one step. These conditions are sufficient, not necessary for solvability of a stiff step.
Theorem 10.1.2
(Discretization and algebraic error budgets)
Suppose the exact ODE solution has a bounded second time derivative for Euler and a bounded third time derivative for trapezoidal stepping, has a uniform state Lipschitz bound on the compared trajectories, and . For inexact backward Euler on , with exact-start defects and unscaled solve residuals ,
Thus and preserve first-order global accuracy with a first-order accurate initial state. Trapezoidal stepping has the analogous bound under ; with third-order defects and it preserves second order. The state region and derivative assumptions must cover all actual approximate values used.
Proof sketch or proof idea
Proof
(Contraction, Neumann bound and the Newton remainder)
The map is a contraction on the complete space , giving existence and uniqueness. Since , the Neumann series gives . For error , the fundamental theorem along its segment yields
The Jacobian Lipschitz constant is , so this remainder has norm at most . Multiplication by the inverse Jacobian proves the Newton estimate. If , it implies , preserving the ball, and the squared-error estimate then gives quadratic convergence. Existence was established separately, so the iteration is not being used to assume its own target root.
To certify a start at , compare the fixed-point equation with that point:
Rearrangement gives the computable radius in the theorem. It may be conservative, especially for dissipative problems, but it is a genuine sufficient condition using available quantities.
Proof
(Propagating defects and solve residuals)
For the global budget, subtract the exact and inexact step equations. Backward Euler gives
The factor is at most , by integrating the derivative of . Iterating and bounding every propagation product proves the displayed estimate. There are at most defects and solve residuals, so per-step contributions accumulate to .
For trapezoidal steps, the old and new state evaluations give instead
The ratio of the two coefficients is bounded by . The same sum argument proves the second-order budget. No cancellation between algebraic and discretization errors has been assumed.
Proof X-ray
Where each hypothesis enters the Newton proof
The condition is used twice and for different purposes: first to make a contraction, which produces the root before any iteration is discussed, and then through the Neumann series to bound every Newton Jacobian inverse by , wherever the iterate lies. The second-derivative bound is used only once, in the integral remainder, which compares the Jacobian along the segment from to with the Jacobian at ; this comparison is the step that yields the square . The proof closes by induction: turns the quadratic estimate into , so the next iterate stays in the same ball and the estimate can be applied again. For the derivative is unbounded and no finite exists, which is why the cycle in the third worked example does not contradict the theorem.
Three separate questions have now been answered: the fixed-point argument identifies a unique root, the Newton argument explains when the chosen iteration reaches it, and the propagation argument explains how accurately that root must be approximated at every time step. None of them is answered merely by calling the time formula implicit or A-stable.
Worked examples
Worked example 10.1.3
(An actual nonlinear dissipative step)
For , and , solve . This example is not globally Lipschitz, so we use a direct scalar argument: , its limits have opposite signs, and it has a unique root in . On the positive half-line it is convex. Newton started at one decreases while remaining above the root, because the tangent of a convex increasing function crosses zero to the right of the true zero. The limit must be the root.
The successive values are , , and approximately . Their residuals are , , approximately and . Since , the mean-value theorem certifies that the root error is no larger than the residual. The root is about .
Taking , the continuous solution starting from one is , whose exact value at is . A highly accurate algebraic root still differs from that continuous value. Newton accuracy does not remove backward Euler's time discretization error.
Worked example 10.1.4
(Conditioning, and why sufficient conditions are not necessary)
For , the implicit root equation is . It has a unique root for every positive , inverse derivative at most one, and Newton solves it in one iteration. The global contraction test is sufficient but unnecessarily restrictive for this dissipative linear equation.
In contrast, for with and , the equation is . Its inverse derivative is . A residual of corresponds to a state error , not . Residual tolerances must be interpreted with the actual conditioning. A-stability statements for negative-real test modes do not describe this positive-growth problem.
Worked example 10.1.5
(Newton can cycle outside its hypotheses)
For the scalar equation , Newton takes to and back to . Both derivatives used are nonzero, yet the iteration never reaches a root. This is not a counterexample to the proved local theorem: the theorem's globally bounded-derivative hypothesis fails for this polynomial equation, so the theorem does not apply.
The lesson is precise. A small number of successful examples is not a global convergence proof, and an invertible Jacobian at the current point alone does not guarantee a useful next iterate. Damping, line searches or bracketing may improve a particular solver, but their guarantees require separate conditions. For the dissipative scalar example above, monotonicity and convexity supplied such a guarantee directly.
Choosing a stopping rule that matches the time method
A fixed tolerance independent of step size does not preserve a formal order under unlimited refinement: the number of residual contributions grows like . For Euler, a sufficient unscaled equation tolerance is a constant times ; for trapezoidal stepping it is a constant times . The constants should also reflect the desired final-time accuracy and propagation factor. These are sufficient budgets, not claims that every larger residual necessarily ruins a computation.
Concept lensAlgorithmic
One Newton step from the old state is a linearly implicit Euler step
Start Newton at . Since , the first iterate is
the linearly implicit Euler formula. Under the theorem's hypotheses , so with : a single iteration already meets the Euler budget. In the cubic example, .
A normalized residual divides the equation by . Its sufficient tolerance is therefore for Euler or for trapezoidal stepping. Confusing these conventions changes the cumulative budget by an entire power of the step. The same care is needed if variables are rescaled: a Euclidean tolerance for differently scaled coordinates represents different physical state errors.
If the Newton linear system is solved inexactly, let its equation residual be , so . Taylor expansion gives for Euler under the same derivative bound. This identifies the effect of the linear-solve error. Keeping it fixed while the nonlinear residual becomes tiny may prevent quadratic convergence; controlling it together with the nonlinear target avoids that unexplained accuracy floor.
A small Newton correction is useful evidence but should be checked against a residual and conditioning estimate. Conversely, an unnecessarily tiny residual can be expensive without improving the total solution. The time-step error and the algebraic error should be reported separately, with their norms and normalizations visible.
A residual can give an explicit certificate in the contraction setting. If is the implicit root, subtracting its equation yields . The reverse triangle inequality therefore gives . Hence the actual error of the approximate algebraic step is at most . For a trapezoidal equation the denominator is . These are global comparisons under the stated Lipschitz conditions, not estimates based solely on the Jacobian at the last iterate.
This certificate can be checked after stopping Newton, regardless of how many iterations were used. The iteration theorem predicts fast progress near the root; the residual certificate reports what was actually achieved. If the certified factor is very large, a tiny raw residual may still be inadequate. If a direct dissipativity argument gives a better bound, as for the dissipative linear equation , that bound can replace the conservative contraction constant. Either choice should be stated explicitly rather than hidden in an unexplained tolerance.
A residual check should use the same norm and equation normalization as the cumulative time-discretization error estimate.
The inverse Jacobian bound controls every Newton step uniformly because the theorem assumes derivative bounds on the whole state space, not merely near one point of the exact trajectory. With only local bounds, one must first specify a region containing the iterates and the segments joining them, and prove that the iteration never leaves it; otherwise the Taylor integral may pass through points the hypotheses do not cover. The stronger global assumptions are chosen here so that this sufficient theorem can be proved completely; the monotone scalar example shows one direction in which they can be relaxed.
Quadratic convergence describes the squared relation between successive errors near the root; it does not mean that the number of correct digits doubles unconditionally at every iteration. The constant , the initial distance and the floating-point and linear-solve accuracy all affect the stage that is actually observed. The starting-ball condition guarantees that each new error is smaller than the previous one, which is what allows the squared estimate to be applied repeatedly; without this invariance, a single Taylor expansion does not prove convergence of the whole iteration.
In a time computation, each Newton root also depends on the previously accepted numerical value, not on the exact solution. The global error proof must therefore propagate the old-state error as well; it cannot simply add up the per-step root errors. The exponential factor in the theorem plays exactly this role. A dissipative equation may admit a better propagation bound, but that requires its own proof; the general Lipschitz exponential bound should not be presented as if it guaranteed decay.
A practical report can list the time step, the final equation residual and the error-certificate constant used, so that readers can tell which kind of accuracy the computation achieved. An iteration count alone determines neither the root error nor the error budget of the final-time solution.
Common mistakes
Common mistake
(Applying the global theorem outside its hypotheses)
Do not apply the global Lipschitz theorem to the cubic step without checking its assumptions; is not globally Lipschitz, and that example has its own scalar monotonicity and convexity proof. Likewise, do not infer universal nonlinear solvability from scalar A-stability.
Common mistake
(Reading a Newton failure as a missing root)
A failure of Newton does not automatically mean the time-step equation has no solution. The cycle for concerns the iteration; the cubic still has a real root, since it is negative at and positive at .
Common mistake
(Reusing a tolerance without its scaling)
The finite-time budget assumes approximate states stay in the region covered by the Lipschitz bound; a solver that jumps outside that region needs a new argument. Backward Euler and trapezoidal steps have different discretization orders and therefore different sufficient solve tolerances, and a residual of the equation divided by takes a tolerance with one power of fewer than an unscaled one. Nor should the linear-system residual be confused with the outer nonlinear residual: the former affects the latter, and the latter affects the time step. Reusing a tolerance number without its scaling is not a mathematical accuracy policy.
Counterexample mode
Convergence near the root need not be quadratic
Claim: once Newton converges to an implicit root, it does so quadratically. Take backward Euler for with and . Then has the double root , and Newton gives . From the iterates are , , : the error only halves. Here , because . The repair is an invertible Jacobian at the root, which the theorem secures through .
Summary
An implicit step needs an existence argument, an iteration argument and a cumulative residual budget. A contraction and Jacobian variation bound provide one complete sufficient Newton theorem. Direct monotonicity can handle useful cases outside those assumptions. Per-step algebraic residuals must shrink at the same unscaled order as exact-start defects if the stated global accuracy is to be preserved by the deterministic bound.
Exercises
Quick check
(Reproduce the first two Newton updates for starting at one, and explain the residual-to-root-error bound.)
Use .
Solution · Answer
At one the residual is and derivative , giving . There the residual is and derivative , giving . The mean-value theorem writes with , so .
Quick check
(Euler has steps, each solve residual at most . Bound their accumulated contribution before the propagation factor.)
Sum unscaled residuals.
Solution · Answer
The sum is at most . Multiplication by the finite-time Lipschitz propagation constant preserves first order. A residual fixed independently of would instead have a worst-case sum proportional to .
Quick check
(A trapezoidal solver controls the residual of the equation divided by . What sufficient power of preserves second order?)
Convert back to the unscaled equation.
Solution · Answer
An unscaled residual is sufficient. Dividing it by gives a normalized tolerance . A normalized target supplies only an unscaled budget and is not the stated second-order guarantee.
Quick check
(For , what residual tolerance guarantees root error at most ?)
The inverse derivative is 1000.
Solution · Answer
Here the error is exactly . Require to guarantee error at most . The numerical value of a residual cannot be read directly as the state error.