ExampleConstruction: AI-generatedVerification: AI-generatedPipeline-generatedprecheck passjudge pass (gpt-6-luna)

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.

A two-dimensional SPD quadratic gives the same FR and linear-CG trace

Example

Take $A = diag (1, 2)$ , $b = (1, 1)$ , and $f (x) = \frac{1}{2} x^{T} A x - b^{T} x, x_{0} = (0, 0) .$ Use exact-SPD-quadratic mode with outer budget $K \geq 2$ and $c_{1} = 1 / 10$ , $c_{2} = 1 / 4$ . An exact-line-search FR run reaches the solution in two steps, with the same directions and steps as linear CG.

Facts & Assumptions

Given: The quadratic, start point, and exact-line-search conditions in the Example.

[F1]

FR and unrestarted PR+ match linear CG on SPD quadratics: on a real SPD quadratic in exact arithmetic, FR exact-line-search iterates, residuals and directions equal linear CG through the zero-residual exit.

[F2]

The conjugate-gradient recurrence: $α_{k} = (r_{k}^{T} r_{k}) / (p_{k}^{T} A p_{k})$ , $r_{k + 1} = r_{k} - α_{k} A p_{k}$ , $β_{k} = (r_{k + 1}^{T} r_{k + 1}) / (r_{k}^{T} r_{k})$ , and $p_{k + 1} = r_{k + 1} + β_{k} p_{k}$ .

Verification

Given: $A = diag (1, 2)$ , $b = (1, 1)$ , and $x_{0} = (0, 0)$ .

1.1givenF2algebra

The initial residual and gradient are $r_{0} = (1, 1)$ and $g_{0} = - r_{0} = (- 1, - 1)$ , so $d_{0} = (1, 1)$ . By [F2], $α_{0} = (r_{0}^{T} r_{0}) / (d_{0}^{T} A d_{0}) = 2 / 3$ , giving $x_{1} = (2 / 3, 2 / 3)$ and $r_{1} = (1 / 3, - 1 / 3)$ .

2.1F2step 1.1algebra

The next coefficient is $β_{0} = (r_{1}^{T} r_{1}) / (r_{0}^{T} r_{0}) = (2 / 9) / 2 = 1 / 9$ , hence $d_{1} = r_{1} + β_{0} d_{0} = (4 / 9, - 2 / 9)$ . Also $d_{1}^{T} A d_{1} = 8 / 27$ , so $α_{1} = (2 / 9) / (8 / 27) = 3 / 4$ .

3.1F1step 2.1algebra∎

Therefore $x_{2} = x_{1} + α_{1} d_{1} = (1, 1 / 2)$ and $r_{2} = b - A x_{2} = 0$ . By [F1], the exact-line-search FR run has these same directions, step lengths, and terminal point.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

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