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.
CG is the Krylov Galerkin method, and the th iterate uniquely minimizes the -norm of the error over
Statement
Let be Hermitian positive definite, let , let be an initial guess, let be the exact solution of , and let be the th conjugate-gradient iterate with initial residual . Then is the unique Krylov Galerkin iterate in , and for every ,
with equality only when .
Facts & Assumptions
Given: A Hermitian positive-definite system , an initial guess , the exact solution , the initial residual , and the th CG iterate .
A Krylov Galerkin iterate is an element of whose residual is orthogonal to (The th Krylov Galerkin iterate in the affine space for a Hermitian positive-definite system).
Residual orthogonality to is equivalent to -orthogonality of the error, and such an iterate is unique (Galerkin orthogonality turns residual orthogonality into -orthogonality of the error, and the Galerkin iterate is unique).
In exact arithmetic, the residuals are mutually orthogonal and the search directions are -conjugate (In exact arithmetic, CG residuals are mutually orthogonal and the search directions are -conjugate).
For every , the energy identity is where is the quadratic energy (For Hermitian positive-definite , the exact solution of is the unique minimizer of the quadratic energy).
Proof
The CG recurrence gives as a linear combination of , so . Also each residual satisfies , so for , and each therefore also lies in . By [L2], the nonzero residuals are mutually orthogonal, hence linearly independent; since they all lie in the -generated space , they form a basis of that space, and so do by the triangular relation . Thus .
By [L2], the residual is orthogonal to each earlier residual. Since step 1.1 shows that form a basis of and each lies in , the same orthogonality implies is orthogonal to . Therefore is a Krylov Galerkin iterate by [F1], and [L1] makes it unique.
Let and put . By [L1] and step 2.1, the error is -orthogonal to , so Hence , with equality only if , that is, . Using [L3], this is equivalent to saying that also uniquely minimizes the quadratic energy over the same affine Krylov space.
Depends on
- The $m$th Krylov Galerkin iterate in the affine space $x_0+K_m(A,r_0)$ for a Hermitian positive-definite system
- Galerkin orthogonality turns residual orthogonality into $A$-orthogonality of the error, and the Galerkin iterate is unique
- In exact arithmetic, CG residuals are mutually orthogonal and the search directions are $A$-conjugate
- For Hermitian positive-definite $A$, the exact solution of $Ax=b$ is the unique minimizer of the quadratic energy
Used by
Dependency tree · two levels
11 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
- Magnus R. Hestenes and Eduard Stiefel, Methods of Conjugate Gradients for Solving Linear Systems (standard reference, not scraped)
- Jonathan Richard Shewchuk, An Introduction to the Conjugate Gradient Method Without the Agonizing Pain (standard reference, not scraped)