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 fixed-point iteration returns a status in bounded outer work

Statement

For admissible inputs of Fixed-point iteration with a residual stop and finite budget with budget $N \in N_{0}$ , every entered iterate belongs to $X$ . The procedure uses at most $N$ updates and $N + 1$ fixed-point residual evaluations and returns one of its stated statuses. Termination is in the model where each map evaluation, metric evaluation and comparison returns in finite time. These counts specify outer procedure operations and give no bound on the internal cost of evaluating the supplied map or metric.

Facts & Assumptions

Given: The algorithm's metric space, self-map, initial point, tolerance and finite budget, and returning evaluation primitives.

[F1]

Fixed-point iteration with a residual stop and finite budget evaluates its residual once at each entered index, tests tolerance before budget, returns at index $N$ if tolerance fails, and updates only when $k < N$ .

Proof

technique · induction

1.1givenF1base

At the initial entered index $0$ , the point $x_{0}$ belongs to $X$ , no update has occurred, and the single pass 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 $X$ , and at most $k$ updates have occurred before pass $k$ .

2.1givenF1step 1.2algebra

If pass $k$ continues, [F1] requires $k < N$ and sets $x_{k + 1} = G (x_{k}) \in X$ by the self-map condition. The next index is $k + 1$ and exactly one additional update has occurred. Thus the assertion of step 1.2 holds at the next entered index. A return creates no further index or update.

3.1givenF1step 1.1step 1.2step 2.1discharge-induction∎

The base and induction step prove membership of every entered iterate and that the entered indices form an initial segment of $0, \dots, N$ . At index $N$ , either the residual test returns or the budget test returns before another update. Hence there are at most $N + 1$ residual evaluations and $N$ updates. Every pass contains finitely many returning primitives, so the procedure terminates with a stated status, including when $N = 0$ .

Depends on

Fixed-point iteration with a residual stop and finite budget

Used by

Nothing in the library uses this result yet.

Cited to discharge well-definedness by Fixed-point iteration with a residual stop and finite budget.

Dependency tree · two levels

2 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)