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.

Updated-Jacobian Newton has local quadratic convergence at a simple root

Statement

Let $n \geq 1$ , let $U \subseteq R^{n}$ be open, and let $F : U \to R^{n}$ be $C^{2}$ , meaning $F$ is $C^{1}$ and its first derivative is itself continuously differentiable. Write $J (x) = D F (x)$ as a matrix in the standard basis. Let $x_{*} \in U$ satisfy $F (x_{*}) = 0$ and suppose $J (x_{*})$ is invertible. Suppose there are $R > 0$ and $L \geq 0$ such that the closed Euclidean ball ${\overline{B}}_{2} (x_{*}, R) : = {x \in R^{n} : ∥ x - x_{*} ∥_{2} \leq R}$ lies in $U$ and $∥ J (x) - J (y) ∥_{o p} \leq L ∥ x - y ∥_{2} (x, y \in {\overline{B}}_{2} (x_{*}, R)),$ where $∥ A ∥_{o p} : = \sup_{∥ v ∥_{2} = 1} ∥ A v ∥_{2}$ . Then there are $r \in (0, R]$ and $K > 0$ such that every $J (x)$ on ${\overline{B}}_{2} (x_{*}, r)$ is invertible with $∥ J (x)^{- 1} ∥_{o p} \leq K$ . Put $C : = K L / 2$ and choose $ρ \in (0, r]$ with $C ρ \leq 1 / 2$ (if $L = 0$ , any $ρ \leq r$ works).

For every $x_{0} \in {\overline{B}}_{2} (x_{*}, ρ)$ , each update attempted by Finite-budget Newton for a square vector residual is defined, remains in this ball, and satisfies $∥ x_{k + 1} - x_{*} ∥_{2} \leq C ∥ x_{k} - x_{*} ∥_{2}^{2} .$ If the ordinary exact-Jacobian Newton recurrence is continued indefinitely, these estimates imply $x_{k} \to x_{*}$ with a quadratic error bound. A finite budget may stop before the residual tolerance is met; root status records only that tolerance, not an exact-zero certificate. This result gives no arbitrary-start or global-convergence guarantee.

Facts & Assumptions

Given: $n, U, F, x_{*}, R, L$ and the Jacobian conditions in the Statement; a residual tolerance $ε \geq 0$ , update budget $N \in N_{0}$ , and an initial value $x_{0} \in {\overline{B}}_{2} (x_{*}, ρ)$ .

[F1]

Newton maps are uniform contractions near a point with invertible derivative: if $F$ is $C^{1}$ on an open subset of $R^{n}$ and $D F (x_{*})$ is invertible, there is a closed ball about $x_{*}$ on which every $D F (x)$ is invertible and its inverse has a uniform operator-norm bound. Its additional contraction conclusion concerns the fixed-inverse map $T_{y} (x) = x + B (y - F (x))$ with $B = D F (x_{*})^{- 1}$ .

[F2]

Vector Newton remainder under a Lipschitz Jacobian: for $x$ in a convex region containing $x_{*}$ , $∥ F (x) - F (x_{*}) - J (x) (x - x_{*}) ∥_{2} \leq (L / 2) ∥ x - x_{*} ∥_{2}^{2}$ when $J$ is $L$ -Lipschitz there.

[F3]

Newton correction for a square vector residual: if $J (x_{k})$ is invertible, the unique correction solves $J (x_{k}) s_{k} = - F (x_{k})$ ; otherwise the correction is unavailable.

[F4]

Finite-budget Newton for a square vector residual: the exact-Jacobian procedure tests the residual and update budget before a correction, and checks trial membership in $U$ before updating.

[F5]

Continuously differentiable maps, local inverses, and local diffeomorphisms: $C^{1}$ means total differentiability at every point and continuity of the derivative-matrix entries.

[F6]

The Jacobian matrix of partial derivatives and the gradient in the scalar-valued case: the Jacobian entries in the standard basis are the first partial derivatives; A total derivative computes every directional derivative, and its matrix is the Jacobian identifies this matrix with the matrix of $D F$ .

[F7]

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

Proof

1.1givenF1F5choose

Apply [F1] at $x_{*}$ . It supplies a radius $r_{0} > 0$ and a finite inverse bound $K > 0$ on ${\overline{B}}_{2} (x_{*}, r_{0})$ . Set $r : = \min {R, r_{0}}$ , so the ball remains inside $U$ , the Jacobian remains $L$ -Lipschitz, and $∥ J (x)^{- 1} ∥_{o p} \leq K$ throughout it. Only this inverse-bound conclusion of [F1] is used; the contraction there is for a fixed inverse matrix, not for the updated-Jacobian recurrence.

2.1step 1.1givenchoosealgebra

Let $C : = K L / 2$ . If $C > 0$ , choose $0 < ρ \leq \min {r, (2 C)^{- 1}}$ ; if $C = 0$ , choose any $0 < ρ \leq r$ . Then $C ρ \leq 1 / 2$ .

3.1givenF2F3F5F6step 1.1step 2.1algebra

Suppose an update is attempted at $x_{k} \in {\overline{B}}_{2} (x_{*}, ρ)$ and put $e_{k} : = x_{k} - x_{*}$ . The inverse bound makes the correction in [F3] unique. Since $F (x_{*}) = 0$ , [F2] and $J (x_{k}) e_{k} - F (x_{k}) = J (x_{k}) e_{k} - [F (x_{k}) - F (x_{*})]$ give $e_{k + 1} = J (x_{k})^{- 1} (J (x_{k}) e_{k} - F (x_{k}))$ and $∥ e_{k + 1} ∥_{2} \leq C ∥ e_{k} ∥_{2}^{2}$ . The full trial is in $U$ because $∥ e_{k + 1} ∥_{2} \leq C ρ ∥ e_{k} ∥_{2} \leq ∥ e_{k} ∥_{2} / 2 \leq ρ / 2$ .

4.1givenF4F7step 3.1induction∎

Starting from $x_{0}$ in the stated ball, induction using step 3.1 shows every attempted update is valid, remains in the ball, and obeys the quadratic bound. It also gives $∥ x_{k} - x_{*} ∥_{2} \leq 2^{- k} ∥ x_{0} - x_{*} ∥_{2}$ for every generated iterate; [F7] makes this tend to zero if the recurrence is continued indefinitely. The finite-budget algorithm may stop earlier under its own residual or budget rule.

Depends on

Used by

Dependency tree · two levels

52 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

E. Hairer and G. Wanner, Solving Ordinary Differential Equations II, Chapter VI: Iterative Methods—Nonlinear Equations (standard reference, not scraped)
Tobin A. Driscoll and Richard J. Braun, Fundamentals of Numerical Computation, version 1.0 (standard reference, not scraped)