LemmaStatement: AI-adaptedProof: AI-generatedPipeline-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.

Finite-budget Newton preserves its domain and returns a status in bounded outer work

Statement

For admissible inputs of Finite-budget Newton for a square vector residual with budget $N \in N_{0}$ , every entered iterate lies in $U$ . The procedure makes at most $N$ correction calls, at most $N$ accepted updates, and at most $N + 1$ explicit outer residual evaluations. It returns a stated residual, singular-Jacobian, invalid-trial or budget status. Termination is in the exact-arithmetic model where residual and Jacobian evaluations, domain decisions and correction calls return in finite time. No convergence, tolerance-attainment or backend complexity claim follows.

Facts & Assumptions

Given: The algorithm's admissible inputs and returning primitives.

[F1]

Finite-budget Newton for a square vector residual evaluates $F (x_{k})$ once at an entered index, checks residual and budget before correction, and accepts an update only after checking membership in $U$ .

Proof

technique · induction

1.1givenF1base

At the initial entered index $0$ , the point $x_{0}$ lies in $U$ , no correction or update has occurred, and the pass explicitly evaluates one residual.

1.2IH

For an entered index $k \leq N$ , assume the preceding entered indices are exactly $0, \dots, k - 1$ , every entered point through $x_{k}$ lies in $U$ , and at most $k$ correction calls and accepted updates have occurred before pass $k$ .

2.1givenF1step 1.2algebra

A continuing pass requires $k < N$ . It makes one correction call; a singular correction or invalid trial returns without entering another index. Otherwise the domain test gives $x_{k + 1} \in U$ , and the next index is $k + 1$ with one additional correction call and accepted update. Thus the assertion of step 1.2 holds at the next entered index.

3.1givenF1step 1.1step 1.2step 2.1discharge-induction∎

The base and induction step prove membership of all entered iterates and that their indices form an initial segment of $0, \dots, N$ . At $k = N$ the residual or budget branch returns before a correction. Hence there are at most $N + 1$ explicit residual evaluations, $N$ correction calls and $N$ accepted updates. Singular or invalid-trial returns only shorten the execution. The finitely many returning primitives therefore terminate with a stated status, including when $N = 0$ .

Depends on

Finite-budget Newton for a square vector residual

Used by

Cited to discharge well-definedness by Finite-budget Newton for a square vector residual.

Dependency tree · two levels

5 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

Tobin A. Driscoll and Richard J. Braun, Fundamentals of Numerical Computation (standard reference, not scraped)