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.

✓ 9 results · all verified · 4 also independently AI-judged

Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 5 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.

Conjugate Gradients, MINRES and Preconditioning: Examples and Counterexamples

1 · Prerequisites

2 · Summary

These worked examples spend the theory on small systems. They show two-step CG on an SPD matrix, early termination at grade smaller than dimension, the effect of spectral clustering on the Chebyshev bound, and the distinct niches of CG and MINRES on indefinite data.

The page also records the main failure modes the A page warns about: symmetry without positive definiteness is not enough for CG, nonsymmetry breaks the $A$ -conjugacy theory, stationary splittings are compared through spectral radii, and a preconditioner can improve or worsen the condition number that actually controls CG.

3 · Logical flowchart

4 · Definitions, theorems and proofs

None yet.

5 · Examples, counterexamples and false statements

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passaudited 2026-09-01Open item page →

CG on a $2 \times 2$ Hermitian positive-definite system reaches the solution in at most two steps

Example

Take

$A = (\begin{array}{cc} 2 & 0 \\ 0 & 1 \end{array}), b = (\binom{2}{1}), x_{0} = (\binom{0}{0}) .$

Then $A$ is Hermitian positive definite and the exact solution is

$x_{*} = (\binom{1}{1}) .$

CG reaches $x_{*}$ by the second step.

Facts & Assumptions

Given: The displayed system and the exact-arithmetic CG recurrence started from $x_{0} = 0$ .

[L1]

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

[L2]

Exact-arithmetic CG terminates no later than the relative grade and hence in at most $n$ steps (In exact arithmetic, CG terminates no later than the relative grade and hence in at most $n$ steps).

Verification

technique · direct calculation

1.1

Here $r_{0} = p_{0} = b = (2, 1)^{T}$ , so $α_{0} = \frac{r_{0}^{T} r_{0}}{p_{0}^{T} A p_{0}} = \frac{5}{9}, x_{1} = (\binom{10 / 9}{5 / 9}), r_{1} = b - A x_{1} = (\binom{- 2 / 9}{4 / 9}) .$ Then $β_{0} = \frac{r_{1}^{T} r_{1}}{r_{0}^{T} r_{0}} = \frac{4}{81}, p_{1} = r_{1} + β_{0} p_{0} = (\binom{- 10 / 81}{40 / 81}) .$ One checks $r_{0}^{T} r_{1} = 2 (- 2 / 9) + 1 (4 / 9) = 0, p_{0}^{T} A p_{1} = (2, 1) \cdot (\binom{- 20 / 81}{40 / 81}) = 0,$ exactly as [L1] predicts.

L1algebra

2.1

Next $α_{1} = \frac{r_{1}^{T} r_{1}}{p_{1}^{T} A p_{1}} = \frac{20 / 81}{200 / 729} = \frac{9}{10},$ so $x_{2} = x_{1} + α_{1} p_{1} = (\binom{10 / 9}{5 / 9}) + \frac{9}{10} (\binom{- 10 / 81}{40 / 81}) = (\binom{1}{1}) = x_{*} .$ Thus the method terminates in two steps, which matches the $n = 2$ upper bound in [L2].

L2step 1.1∎

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passaudited 2026-09-01Open item page →

CG can terminate at a relative grade strictly smaller than the ambient dimension

Example

Let

$A = diag (1, 1, 2), b = (\begin{array}{c} 1 \\ 1 \\ 0 \end{array}), x_{0} = (\begin{array}{c} 0 \\ 0 \\ 0 \end{array}) .$

Then the initial residual is $r_{0} = b$ , its grade is $1$ , and CG reaches the exact solution in one step although the ambient dimension is $3$ .

Facts & Assumptions

Given: The displayed Hermitian positive-definite system.

[F1]

The grade $ν (A, r_{0})$ is the degree of the relative minimal polynomial of $r_{0}$ (The grade of a start vector and its relative minimal polynomial).

[L1]

Exact-arithmetic CG terminates no later than the relative grade (In exact arithmetic, CG terminates no later than the relative grade and hence in at most $n$ steps).

Verification

technique · direct calculation

1.1

Since $A r_{0} = r_{0}$ , the polynomial $q (z) = z - 1$ annihilates $r_{0}$ . The vector $r_{0}$ is nonzero, so no constant polynomial can annihilate it. Therefore $q_{A, r_{0}} (z) = z - 1$ and $ν (A, r_{0}) = 1$ by [F1]. In particular, $1 < 3 = \dim R^{3}$ .

F1algebra

2.1

The exact solution is $x_{*} = A^{- 1} b = (1, 1, 0)^{T} = r_{0}$ . Because $p_{0} = r_{0}$ and $α_{0} = \frac{r_{0}^{T} r_{0}}{p_{0}^{T} A p_{0}} = \frac{2}{2} = 1,$ the first CG update gives $x_{1} = x_{0} + α_{0} p_{0} = r_{0} = x_{*}$ . Thus the method stops at step $1 = ν (A, r_{0})$ , exactly as [L1] allows.

L1step 1.1algebra∎

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passaudited 2026-09-01Open item page →

Clustered eigenvalues give a visibly better CG condition-number bound than equally sized spread spectra

Example

Compare the Hermitian positive-definite matrices

$A_{c l} = diag (9, 10, 11), A_{s p} = diag (1, 10, 100) .$

Both are $3 \times 3$ , but the clustered spectrum of $A_{c l}$ gives a much sharper CG bound than the spread spectrum of $A_{s p}$ .

Facts & Assumptions

Given: The two displayed Hermitian positive-definite matrices.

[L1]

The CG error bound is $∥ e_{m} ∥_{A} \leq 2 {(\frac{\sqrt{κ_{2} (A)} - 1}{\sqrt{κ_{2} (A)} + 1})}^{m} ∥ e_{0} ∥_{A}$ (CG obeys the Chebyshev $A$ -norm bound in terms of the spectral condition number $κ_{2} (A)$ ).

Verification

technique · direct calculation

1.1

The spectral condition numbers are $κ_{2} (A_{c l}) = \frac{11}{9}, κ_{2} (A_{s p}) = 100.$ So the contraction factors in [L1] are $θ_{c l} = \frac{\sqrt{11 / 9} - 1}{\sqrt{11 / 9} + 1} = \frac{\sqrt{11} - 3}{\sqrt{11} + 3},$ and $θ_{s p} = \frac{\sqrt{100} - 1}{\sqrt{100} + 1} = \frac{9}{11} .$ Moreover $\sqrt{11} < 10 / 3$ , so $θ_{c l} < 1 / 18$ .

L1algebra

2.1

At $m = 2$ , [L1] yields $∥ e_{2} ∥_{A_{c l}} \leq 2 θ_{c l}^{2} ∥ e_{0} ∥_{A_{c l}} < \frac{1}{162} ∥ e_{0} ∥_{A_{c l}},$ whereas $∥ e_{2} ∥_{A_{s p}} \leq 2 θ_{s p}^{2} ∥ e_{0} ∥_{A_{s p}} = \frac{162}{121} ∥ e_{0} ∥_{A_{s p}} .$ Thus the clustered eigenvalues give a visibly sharper theoretical CG estimate than the spread spectrum of the same size.

L1step 1.1algebra∎

CounterexampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-09-01Open item page →

A symmetric indefinite matrix can make the CG denominator vanish or change sign before convergence

Statement refuted

Symmetry alone is enough for the CG denominator test: for every symmetric invertible matrix, every nonconverged CG step has $p_{k}^{T} A p_{k} > 0$ .

Facts & Assumptions

Given: The CG recurrence and the positive-denominator theorem for Hermitian positive-definite matrices.

[F1]

To test the proposed extension outside the positive-definite domain, define the attempted first search direction by $p_{0} : = r_{0} : = b - A x_{0}$ and inspect the attempted denominator $p_{0}^{T} A p_{0}$ . These are the same algebraic formulas used by CG on its legitimate domain (The conjugate-gradient recurrence); this fact does not assert that the cited definition applies to an indefinite matrix.

[L1]

For Hermitian positive-definite matrices, every nonconverged CG denominator is positive (Before convergence, every CG denominator $p_{k}^{*} A p_{k}$ is positive).

Counterexample

technique · direct calculation

1.1

Take $A = (\begin{array}{cc} 1 & 0 \\ 0 & - 1 \end{array}), b = (\binom{1}{1}), x_{0} = (\binom{0}{0}) .$ Then $A$ is symmetric and invertible but indefinite. By [F1], $r_{0} = p_{0} = b = (\binom{1}{1}),$ so $p_{0}^{T} A p_{0} = (1, 1) (\begin{array}{cc} 1 & 0 \\ 0 & - 1 \end{array}) (\binom{1}{1}) = (1, 1) (\binom{1}{- 1}) = 0.$ Yet $r_{0} \neq 0$ , so the method has not converged.

F1algebra

2.1

Step 1.1 shows that the first CG denominator can fail to be positive even before convergence. Therefore the refuted statement is false. The contrast with [L1] isolates the missing hypothesis: positive definiteness, not mere symmetry, is load-bearing.

L1step 1.1∎

CounterexampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-09-01Open item page →

A nonsymmetric invertible matrix does not fit the CG orthogonality and minimization theory

Statement refuted

The CG orthogonality and minimization theory applies to every invertible matrix.

Facts & Assumptions

Given: The CG recurrence and the GMRES affine-Krylov residual minimizer.

[F1]

To test the proposed extension outside the Hermitian positive-definite domain, define the attempted algebraic updates $α_{k} = \frac{r_{k}^{T} r_{k}}{p_{k}^{T} A p_{k}}, x_{k + 1} = x_{k} + α_{k} p_{k}, r_{k + 1} = r_{k} - α_{k} A p_{k}, p_{k + 1} = r_{k + 1} + β_{k} p_{k}$ with $p_{0} = r_{0}$ and $β_{k} = (r_{k + 1}^{T} r_{k + 1}) / (r_{k}^{T} r_{k})$ . These repeat the formulas used by CG on its legitimate domain (The conjugate-gradient recurrence); they are not claimed to constitute a run under that definition for nonsymmetric $A$ .

[L1]

GMRES is the residual minimizer over an affine Krylov space for a general matrix (The GMRES iterate as the residual minimizer over an affine Krylov space).

Counterexample

technique · direct calculation

1.1

Take $A = (\begin{array}{cc} 1 & 1 \\ 0 & 1 \end{array}), b = (\binom{0}{1}), x_{0} = (\binom{0}{0}) .$ Then $A$ is invertible but not symmetric. From [F1], $r_{0} = p_{0} = (\binom{0}{1}), α_{0} = \frac{1}{1} = 1, x_{1} = (\binom{0}{1}), r_{1} = b - A x_{1} = (\binom{- 1}{0}) .$ Also $β_{0} = \frac{r_{1}^{T} r_{1}}{r_{0}^{T} r_{0}} = 1, p_{1} = r_{1} + β_{0} p_{0} = (\binom{- 1}{1}) .$

F1algebra

2.1

Now $p_{0}^{T} A p_{1} = (0, 1) (\begin{array}{c} 0 \\ 1 \end{array}) = 1 \neq 0.$ So the search directions fail the basic $A$ -conjugacy identity already at the second direction, and the SPD CG theory cannot be transplanted to this nonsymmetric matrix. The appropriate general method here is the affine-Krylov residual minimizer named in [L1], not CG's Hermitian positive-definite theory.

L1step 1.1algebra∎

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passaudited 2026-09-01Open item page →

MINRES still minimizes the residual on a small symmetric indefinite system

Example

Take

$A = (\begin{array}{cc} 1 & 0 \\ 0 & - 1 \end{array}), b = (\binom{1}{1}), x_{0} = (\binom{0}{0}) .$

Then $A$ is symmetric and indefinite. MINRES at step $1$ gives the residual minimizer in the one-dimensional affine Krylov space.

Facts & Assumptions

Given: The displayed Hermitian indefinite system.

[L1]

For Hermitian matrices, including indefinite ones, MINRES minimizes the Euclidean residual over $x_{0} + K_{m} (A, r_{0})$ (For Hermitian $A$ , including the indefinite case, MINRES minimizes the Euclidean residual over $x_{0} + K_{m} (A, r_{0})$ ).

Verification

technique · direct calculation

1.1

Here $r_{0} = b$ , so $q_{1} = r_{0} / ∥ r_{0} ∥_{2} = (1, 1)^{T} / \sqrt{2}$ and $A q_{1} = (\binom{1 / \sqrt{2}}{- 1 / \sqrt{2}}), α_{1} = q_{1}^{T} A q_{1} = 0, β_{1} = 1, q_{2} = (\binom{1 / \sqrt{2}}{- 1 / \sqrt{2}}) .$ Thus the first Lanczos matrix is ${\overset{ˉ}{T}}_{1} = (\binom{0}{1}),$ and the step- $1$ least-squares problem is $\min_{y \in R} {∥ (\binom{\sqrt{2}}{0}) - (\binom{0}{y}) ∥}_{2},$ whose unique minimizer is $y_{1} = 0$ . Therefore $x_{1} = x_{0} + q_{1} y_{1} = 0$ .

algebra

2.1

The affine space $x_{0} + K_{1} (A, r_{0})$ is ${t (1, 1)^{T} : t \in R}$ . For such a vector, $b - A (\binom{t}{t}) = (\binom{1 - t}{1 + t}), {∥ b - A (\binom{t}{t}) ∥}_{2}^{2} = (1 - t)^{2} + (1 + t)^{2} = 2 + 2 t^{2},$ which is minimized exactly at $t = 0$ . So the explicit computation in step 1.1 matches [L1].

L1step 1.1algebra∎

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passaudited 2026-09-01Open item page →

Jacobi and Gauss-Seidel splittings can be compared by the spectral radii of their iteration matrices

Example

For

$A = (\begin{array}{cc} 4 & 1 \\ 2 & 3 \end{array}), b = (\binom{1}{1}), x_{0} = (\binom{0}{0}),$

compare the Jacobi splitting with

$M_{J} = (\begin{array}{cc} 4 & 0 \\ 0 & 3 \end{array}), N_{J} = (\begin{array}{cc} 0 & - 1 \\ - 2 & 0 \end{array}),$

and the Gauss-Seidel splitting with

$M_{G} = (\begin{array}{cc} 4 & 0 \\ 2 & 3 \end{array}), N_{G} = (\begin{array}{cc} 0 & - 1 \\ 0 & 0 \end{array}) .$

The Gauss-Seidel iteration matrix has the smaller spectral radius and the faster visible error decay on this system.

Facts & Assumptions

Given: The two displayed splittings of the same system.

[F1]

A stationary splitting has iteration matrix $B = M^{- 1} N$ (Stationary iteration from a matrix splitting $A = M - N$ ).

[L1]

A stationary splitting converges for every start exactly when $ρ (B) < 1$ (A stationary splitting converges for every start if and only if its iteration matrix has spectral radius below $1$ ).

Verification

technique · direct calculation

1.1

By [F1], $B_{J} = M_{J}^{- 1} N_{J} = (\begin{array}{cc} 0 & - 1 / 4 \\ - 2 / 3 & 0 \end{array}), B_{G} = M_{G}^{- 1} N_{G} = (\begin{array}{cc} 0 & - 1 / 4 \\ 0 & 1 / 6 \end{array}) .$ The eigenvalues of $B_{J}$ are $\pm 1 / \sqrt{6}$ , so $ρ (B_{J}) = 1 / \sqrt{6}$ , while the eigenvalues of $B_{G}$ are $0$ and $1 / 6$ , so $ρ (B_{G}) = 1 / 6$ . Both are below $1$ , and Gauss-Seidel has the smaller spectral radius.

F1L1algebra

2.1

The exact solution is $x_{*} = (1 / 5, 1 / 5)^{T}$ . Jacobi gives $x_{1}^{(J)} = (\binom{1 / 4}{1 / 3}), x_{2}^{(J)} = (\binom{1 / 6}{1 / 6}),$ so $∥ x_{1}^{(J)} - x_{*} ∥_{\infty} = \frac{2}{15}, ∥ x_{2}^{(J)} - x_{*} ∥_{\infty} = \frac{1}{30} .$ Gauss-Seidel gives $x_{1}^{(G)} = (\binom{1 / 4}{1 / 6}), x_{2}^{(G)} = (\binom{5 / 24}{7 / 36}),$ so $∥ x_{1}^{(G)} - x_{*} ∥_{\infty} = \frac{1}{20}, ∥ x_{2}^{(G)} - x_{*} ∥_{\infty} = \frac{1}{120} .$ Thus the splitting with smaller spectral radius also shows faster observed error decay here, consistent with [L1].

L1step 1.1algebra∎

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-09-01Open item page →

A diagonal positive-definite preconditioner can improve the relevant condition number

Example

Let

$A = diag (100, 1), M = diag (100, 1) .$

Then $M$ is diagonal and positive definite, and symmetric preconditioning turns the CG condition number from $100$ into $1$ .

Facts & Assumptions

Given: The displayed Hermitian positive-definite system and diagonal preconditioner.

[L1]

Symmetric positive-definite preconditioning preserves the Hermitian positive-definite CG problem and replaces the bound by the one for the transformed operator (Symmetric positive-definite preconditioning preserves a Hermitian positive-definite CG problem, and the CG bound uses the transformed condition number).

Verification

technique · direct calculation

1.1

The original spectral condition number is $κ_{2} (A) = \frac{100}{1} = 100.$ If $M = C C^{*}$ , then we may take $C = diag (10, 1)$ .

algebra

2.1

The symmetrically preconditioned operator is $C^{- 1} A C^{- *} = diag (1 / 10, 1) diag (100, 1) diag (1 / 10, 1) = I_{2},$ so $κ_{2} (C^{- 1} A C^{- *}) = 1.$ Therefore the relevant condition number has improved from $100$ to $1$ , exactly the transformed quantity singled out in [L1].

L1step 1.1algebra∎

CounterexampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-09-01Open item page →

A preconditioner can worsen the condition number that actually controls CG

Statement refuted

Every invertible, or even every symmetric positive-definite, preconditioner improves the condition number that governs CG.

Facts & Assumptions

Given: The residual-and-error maps for preconditioning and the symmetric positive-definite CG transform.

[F1]

Symmetric preconditioning replaces $A$ by the transformed operator $C^{- 1} A C^{- *}$ (Invertible preconditioners give equivalent linear systems, with the transformed residuals and errors written explicitly).

[L1]

The CG bound is governed by the spectral condition number of the transformed operator (Symmetric positive-definite preconditioning preserves a Hermitian positive-definite CG problem, and the CG bound uses the transformed condition number).

Counterexample

technique · direct calculation

1.1

Take $A = I_{2}, M = diag (1, 1 / 100) .$ Then $A$ is already Hermitian positive definite with $κ_{2} (A) = 1.$ Since $M = C C^{*}$ with $C = diag (1, 1 / 10)$ , [F1] gives the transformed operator $C^{- 1} A C^{- *} = diag (1, 10) I_{2} diag (1, 10) = diag (1, 100) .$

F1algebra

2.1

The transformed spectral condition number is therefore $κ_{2} (C^{- 1} A C^{- *}) = 100 > 1 = κ_{2} (A) .$ So this symmetric positive-definite preconditioner worsens the condition number that actually appears in the CG bound from [L1]. The refuted statement is false.

L1step 1.1algebra∎

Conjugate Gradients, MINRES and Preconditioning: Examples and Counterexamples

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

5 · Examples, counterexamples and false statements

CG on a 2×22×2 Hermitian positive-definite system reaches the solution in at most two steps

Example

Facts & Assumptions

Verification

CG can terminate at a relative grade strictly smaller than the ambient dimension

Example

Facts & Assumptions

Verification

Clustered eigenvalues give a visibly better CG condition-number bound than equally sized spread spectra

Example

Facts & Assumptions

Verification

A symmetric indefinite matrix can make the CG denominator vanish or change sign before convergence

Statement refuted

Facts & Assumptions

Counterexample

A nonsymmetric invertible matrix does not fit the CG orthogonality and minimization theory

Statement refuted

Facts & Assumptions

Counterexample

MINRES still minimizes the residual on a small symmetric indefinite system

Example

Facts & Assumptions

Verification

Jacobi and Gauss-Seidel splittings can be compared by the spectral radii of their iteration matrices

Example

Facts & Assumptions

Verification

A diagonal positive-definite preconditioner can improve the relevant condition number

Example

Facts & Assumptions

Verification

A preconditioner can worsen the condition number that actually controls CG

Statement refuted

Facts & Assumptions

Counterexample

Sources

CG on a $2 \times 2$ Hermitian positive-definite system reaches the solution in at most two steps