TheoremStatement: Literature-sourcedProof: AI-adaptedPipeline-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Forcing residuals determine local inexact-Newton rates

Statement

Let $n \geq 0$ be an integer, let $U \subseteq R^{n}$ be open, let $F : U \to R^{n}$ be $C^{1}$ , and let $x_{*} \in U$ satisfy $F (x_{*}) = 0$ with $J_{*} : = D F (x_{*})$ invertible. Suppose $J = D F$ is $L$ -Lipschitz on a closed ball of positive radius about $x_{*}$ contained in $U$ . Fix $\overset{ˉ}{η} \in [0, 1)$ . For $n = 0$ use the zero operator-norm convention of An inexact Newton residual gives a local error recurrence. Consider any sequence $x_{k + 1} = x_{k} + p_{k}, J (x_{k}) p_{k} + F (x_{k}) = r_{k}, ∥ r_{k} ∥_{2} \leq η_{k} ∥ F (x_{k}) ∥_{2},$ with $0 \leq η_{k} \leq \overset{ˉ}{η}$ . Define $∥ v ∥_{*} : = ∥ J_{*} v ∥_{2}$ . There is $ρ > 0$ such that, if $∥ x_{0} - x_{*} ∥_{*} \leq ρ$ , every iterate remains in the ball and $∥ x_{k} - x_{*} ∥_{*} \leq q^{k} ∥ x_{0} - x_{*} ∥_{*}$ for some $q < 1$ . Consequently:

If $η_{k} \to 0$ , the iterates converge superlinearly (unless an exact root is reached, in which case the exact recurrence remains there).
If $η_{k} \leq C_{η} ∥ F (x_{k}) ∥_{2}$ for a constant $C_{η}$ , the iterates converge quadratically.

The fixed bound $\overset{ˉ}{η} < 1$ gives linear convergence. Since $J_{*}$ is invertible, these rates in $∥ \cdot ∥_{*}$ are equivalent to the same local rates in the Euclidean norm. For $F = \nabla f$ with $f \in C^{2} (U)$ (all ordered partial derivatives through order two exist and are continuous), $J (x) = \nabla^{2} f (x)$ , so the residual is the inexact Newton residual $\nabla^{2} f (x_{k}) p_{k} + \nabla f (x_{k})$ , using the Hessian convention of The Hessian matrix and critical points of a scalar field. This theorem concerns the unshifted full-step recurrence; it does not assert that a safeguarded line-search algorithm eventually selects that branch.

Facts & Assumptions

Given: $U, F, x_{*}, J, J_{*}, L, \overset{ˉ}{η}, (x_{k}), (p_{k}), (r_{k}), (η_{k})$ and the hypotheses in the Statement.

[F1]

An inexact Newton residual gives a local error recurrence: in a sufficiently small ball, $∥ F (x) ∥_{2} \leq C_{F} ∥ x - x_{*} ∥_{*}$ and $∥ x + p - x_{*} ∥_{*} \leq (η + C ∥ x - x_{*} ∥_{*}) ∥ x - x_{*} ∥_{*}$ whenever $J (x) p + F (x) = r$ and $∥ r ∥_{2} \leq η ∥ F (x) ∥_{2}$ .

[F2]

For $∣ r ∣ < 1$ the sequence $r^{k}$ is null, and for $∣ r ∣ > 1$ the sequence $∣ r ∣^{k}$ diverges to $+ \infty$ : if $∣ q ∣ < 1$ , then $q^{k} \to 0$ .

[F3]

The Hessian matrix and critical points of a scalar field: for a scalar field, the Hessian is the matrix of second partial derivatives; the gradient is defined from first partials by The Jacobian matrix of partial derivatives and the gradient in the scalar-valued case.

[F4]

A total derivative computes every directional derivative, and its matrix is the Jacobian: the matrix of a total derivative is the Jacobian, with column $j$ equal to the $j$ th partial derivative.

[F5]

If all partial derivatives exist on a neighbourhood and are continuous at a point, then the map is totally differentiable there with Jacobian derivative: continuous coordinate partial derivatives on an open set give total differentiability.

[F6]

Continuous mixed partials of order $k$ are invariant under permutations: for a $C^{k}$ scalar field, $k \geq 2$ , every iterated derivative of order $k$ is unchanged by permutations of its coordinate differentiations.

Proof

Given: The hypotheses and notation in the Statement.

1.1givenalgebra

If $n = 0$ , every iterate, residual and correction is the unique zero vector and $x_{k} = x_{*}$ for all $k$ . Choose any $ρ > 0$ and $q = (1 + \overset{ˉ}{η}) / 2 < 1$ ; all error bounds are $0 \leq 0$ . The exact-root alternative applies from the start, including the quadratic zero-error bound. For the remainder assume $n \geq 1$ .

1.2givenF1choosealgebra

Let $C_{F}, C$ and a radius $r_{0}$ be supplied by [F1], and let $K_{*} : = ∥ J_{*}^{- 1} ∥_{o p}$ . Set $q : = (1 + \overset{ˉ}{η}) / 2 < 1$ . Choose $ρ > 0$ with $K_{*} ρ \leq r_{0}$ and, when $C > 0$ , $C ρ \leq (1 - \overset{ˉ}{η}) / 2$ .

2.1givenF1step 1.2induction

Suppose $∥ x_{k} - x_{*} ∥_{*} \leq ρ$ . Then $∥ x_{k} - x_{*} ∥_{2} \leq K_{*} ρ \leq r_{0}$ , so [F1] applies and gives $∥ x_{k + 1} - x_{*} ∥_{*} \leq (η_{k} + C ∥ x_{k} - x_{*} ∥_{*}) ∥ x_{k} - x_{*} ∥_{*} \leq q ∥ x_{k} - x_{*} ∥_{*} \leq ρ$ . Induction proves every iterate remains in the ball and the geometric bound.

3.1givenF1F2step 2.1algebra

By [F2] and step 2.1, $∥ x_{k} - x_{*} ∥_{*} \to 0$ . If $x_{k} \neq x_{*}$ , divide the recurrence in [F1] by $∥ x_{k} - x_{*} ∥_{*}$ to get $\frac{∥ x_{k + 1} - x_{*} ∥_{*}}{∥ x_{k} - x_{*} ∥_{*}} \leq η_{k} + C ∥ x_{k} - x_{*} ∥_{*}$ . When $η_{k} \to 0$ , the right side tends to zero. If some $x_{k} = x_{*}$ , then $F (x_{k}) = 0$ and the residual bound gives $r_{k} = 0$ ; local invertibility in [F1] forces $p_{k} = 0$ , so all later iterates remain there.

3.2givenF1step 2.1algebra

If $η_{k} \leq C_{η} ∥ F (x_{k}) ∥_{2}$ , [F1] and step 2.1 yield $∥ x_{k + 1} - x_{*} ∥_{*} \leq (C_{η} C_{F} + C) ∥ x_{k} - x_{*} ∥_{*}^{2}$ , which is quadratic convergence in the $*$ norm.

4.1givenF3F4F5F6step 2.1algebra∎

In the specialization $F = \nabla f$ with $f \in C^{2} (U)$ , each $F_{i} = \partial_{i} f$ has continuous first partials. By [F5] it is totally differentiable, and by [F4] the matrix of $D F$ has entries $J_{i j} = \partial_{j} (\partial_{i} f)$ . By [F6] these equal $\partial_{i} (\partial_{j} f)$ , the entries of the Hessian in [F3]. Thus $J (x) = \nabla^{2} f (x)$ . Invertibility gives $K_{*}^{- 1} ∥ e ∥_{2} \leq ∥ e ∥_{*} \leq ∥ J_{*} ∥_{o p} ∥ e ∥_{2}$ for every $e$ . These fixed comparison constants transfer the linear, superlinear, and quadratic bounds from the $*$ norm to the Euclidean norm. The fixed- $\overset{ˉ}{η}$ geometric estimate of step 2.1 is linear convergence.

Depends on

Used by

Dependency tree · two levels

44 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Ron S. Dembo, Stanley C. Eisenstat, and Trond Steihaug, Inexact Newton Methods, SIAM Journal on Numerical Analysis 19 (1982), 400–408 (standard reference, not scraped)
Jorge Nocedal and Stephen J. Wright, Numerical Optimization, 2nd ed. (standard reference, not scraped)