Alphabeta Math
TheoremStatement: AI-adaptedProof: AI-generatedprecheck passaudited 2026-09-01
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 mth iterate uniquely minimizes the A-norm of the error over x0+Km(A,r0)

Statement

Let A be Hermitian positive definite, let Ax=b, let x0 be an initial guess, let x be the exact solution of Ax=b, and let xm be the mth conjugate-gradient iterate with initial residual r0=bAx0. Then xm is the unique Krylov Galerkin iterate in x0+Km(A,r0), and for every xx0+Km(A,r0),

xxmAxxA,

with equality only when x=xm.

Facts & Assumptions

Given: A Hermitian positive-definite system Ax=b, an initial guess x0, the exact solution x, the initial residual r0=bAx0, and the mth CG iterate xm.

[F1]

A Krylov Galerkin iterate is an element of x0+Km(A,r0) whose residual is orthogonal to Km(A,r0) (The mth Krylov Galerkin iterate in the affine space x0+Km(A,r0) for a Hermitian positive-definite system).

[L1]

Residual orthogonality to Km(A,r0) is equivalent to A-orthogonality of the error, and such an iterate is unique (Galerkin orthogonality turns residual orthogonality into A-orthogonality of the error, and the Galerkin iterate is unique).

[L2]

In exact arithmetic, the residuals are mutually orthogonal and the search directions are A-conjugate (In exact arithmetic, CG residuals are mutually orthogonal and the search directions are A-conjugate).

[L3]

For every x, the energy identity is ϕ(x)ϕ(x)=12xxA2, where ϕ is the quadratic energy (For Hermitian positive-definite A, the exact solution of Ax=b is the unique minimizer of the quadratic energy).

Proof

technique · direct
1.1

The CG recurrence gives xmx0 as a linear combination of p0,,pm1, so xmx0+span{p0,,pm1}. Also each residual satisfies rj=r0A(xjx0), so rjKj+1(A,r0)Km(A,r0) for j<m, and each pj=rj+βj1pj1 therefore also lies in Km(A,r0). By [L2], the nonzero residuals r0,,rm1 are mutually orthogonal, hence linearly independent; since they all lie in the m-generated space Km(A,r0), they form a basis of that space, and so do p0,,pm1 by the triangular relation pjrj+span{r0,,rj1}. Thus xmx0+Km(A,r0).

L2algebra
2.1

By [L2], the residual rm is orthogonal to each earlier residual. Since step 1.1 shows that p0,,pm1 form a basis of Km(A,r0) and each pj lies in span{r0,,rj}, the same orthogonality implies rm is orthogonal to Km(A,r0). Therefore xm is a Krylov Galerkin iterate by [F1], and [L1] makes it unique.

F1L1L2step 1.1
3.1

Let xx0+Km(A,r0) and put v:=xxmKm(A,r0). By [L1] and step 2.1, the error xxm is A-orthogonal to v, so xxA2=(xxm)vA2=xxmA2+vA2. Hence xxmAxxA, with equality only if v=0, that is, x=xm. Using [L3], this is equivalent to saying that xm also uniquely minimizes the quadratic energy over the same affine Krylov space.

L1L3step 2.1algebra

Depends on

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