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.

✓ 11 results · all verified · 7 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 4 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.

Conjugate Gradients, MINRES and Preconditioning

1 · Prerequisites

2 · Summary

This page follows the Hermitian Krylov route that the preceding Arnoldi and GMRES page leaves open. It begins with the quadratic energy behind conjugate gradients, identifies the Galerkin condition that characterizes the affine Krylov iterate, and then proves the exact-arithmetic CG structure: positivity of the denominators, residual orthogonality, $A$ -conjugacy, finite termination, and the standard Chebyshev bound.

The second half specializes Arnoldi to Lanczos, defines MINRES from the tridiagonal least-squares problem, and closes with stationary splittings and preconditioning. The page keeps the central trap explicit: CG needs Hermitian positive definiteness, while MINRES needs only Hermitian structure and preconditioning must be analyzed through the transformed operator rather than praised generically.

3 · Logical flowchart

4 · Definitions, theorems and proofs

DefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (gpt-5.6-terra)audited 2026-09-01Open item page →

The energy inner product $⟨ u, v ⟩_{A} = ⟨ A u, v ⟩$ and energy norm $∥ u ∥_{A}$ for a Hermitian positive-definite matrix

Definition

Let $A \in M_{n} (C)$ be Hermitian positive definite in the sense of Hermitian positive-definite matrices and Cholesky factorisation A = LL* with positive diagonal. For vectors $u, v \in C^{n}$ , define the energy inner product

$⟨ u, v ⟩_{A} : = ⟨ A u, v ⟩,$

where $⟨ \cdot, \cdot ⟩$ is the standard coordinate inner product of The standard formulas $⟨ x, y ⟩ = \sum_{k < n} x_{k} y_{k}$ on $R^{n}$ and $\sum_{k < n} x_{k} \overline{y_{k}}$ on $C^{n}$ are inner products. Because $A$ is Hermitian positive definite, this is an inner product on $C^{n}$ , and its induced norm

$∥ u ∥_{A} : = \sqrt{⟨ u, u ⟩_{A}}$

is the energy norm of $u$ .

Equivalently, if $A = L L^{*}$ is the Cholesky factorization from Hermitian positive-definite matrices and Cholesky factorisation A = LL* with positive diagonal, then $⟨ u, v ⟩_{A} = ⟨ L^{*} u, L^{*} v ⟩$ and $∥ u ∥_{A} = ∥ L^{*} u ∥_{2}$ .

DefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (gpt-5.6-terra)audited 2026-09-01Open item page →

The quadratic energy $ϕ (x) = \frac{1}{2} ⟨ A x, x ⟩ - Re ⟨ b, x ⟩$ of a Hermitian positive-definite linear system

Definition

Let $A \in M_{n} (C)$ be Hermitian positive definite, and let $b \in C^{n}$ . The quadratic energy of the linear system $A x = b$ is the real-valued function

$ϕ : C^{n} \to R, ϕ (x) : = \frac{1}{2} ⟨ A x, x ⟩ - Re ⟨ b, x ⟩,$

where the coordinate inner product is the one from The standard formulas $⟨ x, y ⟩ = \sum_{k < n} x_{k} y_{k}$ on $R^{n}$ and $\sum_{k < n} x_{k} \overline{y_{k}}$ on $C^{n}$ are inner products. The diagonal term is real because $⟨ A x, x ⟩ = ∥ x ∥_{A}^{2}$ by The energy inner product $⟨ u, v ⟩_{A} = ⟨ A u, v ⟩$ and energy norm $∥ u ∥_{A}$ for a Hermitian positive-definite matrix.

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-5.6-terra)audited 2026-09-01Open item page →

For Hermitian positive-definite $A$ , the exact solution of $A x = b$ is the unique minimizer of the quadratic energy

Statement

Let $A \in M_{n} (C)$ be Hermitian positive definite, let $b \in C^{n}$ , and let $ϕ$ be the quadratic energy from The quadratic energy $ϕ (x) = \frac{1}{2} ⟨ A x, x ⟩ - Re ⟨ b, x ⟩$ of a Hermitian positive-definite linear system. Then the system $A x = b$ has a unique solution $x_{*}$ , and for every $x \in C^{n}$ one has

$ϕ (x) - ϕ (x_{*}) = \frac{1}{2} ∥ x - x_{*} ∥_{A}^{2} .$

In particular, $x_{*}$ is the unique minimizer of $ϕ$ .

Facts & Assumptions

Given: A Hermitian positive-definite matrix $A \in M_{n} (C)$ , a vector $b \in C^{n}$ , and the quadratic energy $ϕ (x)$ .

[F1]

The quadratic energy is $ϕ (x) = \frac{1}{2} ⟨ A x, x ⟩ - Re ⟨ b, x ⟩$ (The quadratic energy $ϕ (x) = \frac{1}{2} ⟨ A x, x ⟩ - Re ⟨ b, x ⟩$ of a Hermitian positive-definite linear system).

[L1]

The energy norm is defined by $∥ u ∥_{A}^{2} = ⟨ A u, u ⟩$ for Hermitian positive-definite $A$ (The energy inner product $⟨ u, v ⟩_{A} = ⟨ A u, v ⟩$ and energy norm $∥ u ∥_{A}$ for a Hermitian positive-definite matrix).

[L2]

A matrix is Hermitian positive definite if and only if it has a Cholesky factorization $A = L L^{*}$ with positive diagonal, and that factor is unique (A matrix admits a Cholesky factorisation with positive diagonal exactly when it is Hermitian positive definite, and that factor is unique).

Proof

technique · direct

1.1L2algebra

By [L2], there is a lower-triangular matrix $L$ with positive diagonal such that $A = L L^{*}$ . Hence $L$ and $L^{*}$ are invertible, so $A$ is invertible and the system $A x = b$ has the unique solution $x_{*} : = A^{- 1} b$ .

2.1F1L1step 1.1algebra

Since $A x_{*} = b$ , [F1] gives $ϕ (x) - ϕ (x_{*}) = \frac{1}{2} ⟨ A (x - x_{*}), x - x_{*} ⟩ + Re ⁣ (\frac{1}{2} ⟨ A x_{*}, x - x_{*} ⟩ - \frac{1}{2} ⟨ A (x - x_{*}), x_{*} ⟩) .$ Because $A$ is Hermitian, $⟨ A x_{*}, x - x_{*} ⟩ = ⟨ x_{*}, A (x - x_{*}) ⟩$ is the complex conjugate of $⟨ A (x - x_{*}), x_{*} ⟩$ , so the real part in parentheses vanishes. Therefore $ϕ (x) - ϕ (x_{*}) = \frac{1}{2} ⟨ A (x - x_{*}), x - x_{*} ⟩ = \frac{1}{2} ∥ x - x_{*} ∥_{A}^{2} .$

3.1L1step 2.1∎

By [L1], the quantity $∥ x - x_{*} ∥_{A}^{2}$ is nonnegative and is zero only when $x = x_{*}$ . Step 2.1 therefore shows $ϕ (x) \geq ϕ (x_{*})$ for every $x$ , with equality only at $x_{*}$ . Hence $x_{*}$ is the unique minimizer of $ϕ$ .

DefinitionDefinition: AI-adaptedProof: Not applicablejudge pass (gpt-5.6-terra)audited 2026-09-01Open item page →

The $m$ th Krylov Galerkin iterate in the affine space $x_{0} + K_{m} (A, r_{0})$ for a Hermitian positive-definite system

Definition

Let $A$ be Hermitian positive definite, let $A x = b$ , let $x_{0}$ be an initial guess, and put

$r_{0} : = b - A x_{0} .$

For $m \geq 0$ , an element $x_{m} \in x_{0} + K_{m} (A, r_{0})$ is the $m$ th Krylov Galerkin iterate when its residual

$r_{m} : = b - A x_{m}$

is orthogonal to $K_{m} (A, r_{0})$ in the standard inner product. The next proposition identifies this residual condition with $A$ -orthogonality of the error $x_{*} - x_{m}$ .

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

Galerkin orthogonality turns residual orthogonality into $A$ -orthogonality of the error, and the Galerkin iterate is unique

Statement

Let $A$ be Hermitian positive definite, let $A x = b$ , let $x_{0}$ be an initial guess, let $r_{0} = b - A x_{0}$ , let $x_{*}$ be the exact solution of $A x = b$ , and let $x_{m} \in x_{0} + K_{m} (A, r_{0})$ . Then the following are equivalent:

$b - A x_{m}$ is orthogonal to $K_{m} (A, r_{0})$ in the standard inner product.
$x_{*} - x_{m}$ is orthogonal to $K_{m} (A, r_{0})$ in the energy inner product.

When these conditions hold, the vector $x_{m}$ is the unique element of $x_{0} + K_{m} (A, r_{0})$ with that property.

Facts & Assumptions

Given: A Hermitian positive-definite system $A x = b$ , an initial guess $x_{0}$ , $r_{0} = b - A x_{0}$ , the exact solution $x_{*}$ , and a vector $x_{m} \in x_{0} + K_{m} (A, r_{0})$ .

[F1]

A Krylov Galerkin iterate is an element of $x_{0} + K_{m} (A, r_{0})$ whose residual is orthogonal to $K_{m} (A, r_{0})$ (The $m$ th Krylov Galerkin iterate in the affine space $x_{0} + K_{m} (A, r_{0})$ for a Hermitian positive-definite system).

[L1]

The energy inner product is $⟨ u, v ⟩_{A} = ⟨ A u, v ⟩$ (The energy inner product $⟨ u, v ⟩_{A} = ⟨ A u, v ⟩$ and energy norm $∥ u ∥_{A}$ for a Hermitian positive-definite matrix).

Proof

technique · direct

1.1F1L1algebra

For every $v \in K_{m} (A, r_{0})$ , the identity $A x_{*} = b$ gives $⟨ b - A x_{m}, v ⟩ = ⟨ A (x_{*} - x_{m}), v ⟩ = ⟨ x_{*} - x_{m}, v ⟩_{A}$ by [L1]. Hence the residual is orthogonal to $K_{m} (A, r_{0})$ if and only if the error is $A$ -orthogonal to $K_{m} (A, r_{0})$ .

2.1L1step 1.1algebra∎

Suppose $x_{m}$ and $y_{m}$ both lie in $x_{0} + K_{m} (A, r_{0})$ and both satisfy the equivalent conditions from step 1.1. Then $d : = x_{m} - y_{m}$ lies in $K_{m} (A, r_{0})$ , and both errors are $A$ -orthogonal to $d$ . Subtracting the two orthogonality relations gives $0 = ⟨ x_{*} - x_{m}, d ⟩_{A} - ⟨ x_{*} - y_{m}, d ⟩_{A} = ⟨ y_{m} - x_{m}, d ⟩_{A} = - ⟨ d, d ⟩_{A} .$ Positive definiteness of the energy inner product therefore forces $d = 0$ , so $x_{m} = y_{m}$ .

DefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (gpt-5.6-terra)audited 2026-09-01Open item page →

The conjugate-gradient recurrence

Definition

Let $A$ be Hermitian positive definite, let $A x = b$ , and fix an initial guess $x_{0}$ . Set

$r_{0} : = b - A x_{0}, p_{0} : = r_{0} .$

For every index $k$ with $r_{k} \neq 0$ , define

$α_{k} : = \frac{⟨ r_{k}, r_{k} ⟩}{⟨ A p_{k}, p_{k} ⟩}, x_{k + 1} : = x_{k} + α_{k} p_{k}, r_{k + 1} : = r_{k} - α_{k} A p_{k},$

and then

$β_{k} : = \frac{⟨ r_{k + 1}, r_{k + 1} ⟩}{⟨ r_{k}, r_{k} ⟩}, p_{k + 1} : = r_{k + 1} + β_{k} p_{k} .$

This is the conjugate-gradient recurrence.

PropositionStatement: Literature-sourcedProof: AI-generatedverified 2026-09-26 (gpt-6-sol)Open item page →

Before convergence, every CG denominator $p_{k}^{*} A p_{k}$ is positive

Statement

Assume the conjugate-gradient recurrence of The conjugate-gradient recurrence is defined through step $k$ for a Hermitian positive-definite matrix $A$ . If $r_{k} \neq 0$ , then $p_{k} \neq 0$ and

$p_{k}^{*} A p_{k} = ∥ p_{k} ∥_{A}^{2} > 0.$

Facts & Assumptions

Given: A Hermitian positive-definite system $A x = b$ , a CG run through step $k$ , and a nonzero residual $r_{k}$ .

[F1]

CG uses the recurrence $α_{j} = \frac{⟨ r_{j}, r_{j} ⟩}{⟨ A p_{j}, p_{j} ⟩}, r_{j + 1} = r_{j} - α_{j} A p_{j}, β_{j} = \frac{⟨ r_{j + 1}, r_{j + 1} ⟩}{⟨ r_{j}, r_{j} ⟩}, p_{j + 1} = r_{j + 1} + β_{j} p_{j}$ with $p_{0} = r_{0}$ (The conjugate-gradient recurrence).

[L1]

For Hermitian positive-definite $A$ , the energy norm satisfies $∥ u ∥_{A}^{2} = ⟨ A u, u ⟩,$ and it is positive on nonzero vectors (The energy inner product $⟨ u, v ⟩_{A} = ⟨ A u, v ⟩$ and energy norm $∥ u ∥_{A}$ for a Hermitian positive-definite matrix).

Proof

technique · direct

1.1F1inductionalgebra

We first show by induction on $j \leq k$ that $⟨ p_{j}, r_{j} ⟩ = ⟨ r_{j}, r_{j} ⟩$ . For $j = 0$ this is immediate from $p_{0} = r_{0}$ in [F1]. If it holds at $j < k$ , conjugate symmetry gives $⟨ r_{j}, p_{j} ⟩ = ⟨ r_{j}, r_{j} ⟩$ , since the latter is real. The inner product is linear in its first argument, so [F1] gives $⟨ r_{j + 1}, p_{j} ⟩ = ⟨ r_{j}, p_{j} ⟩ - α_{j} ⟨ A p_{j}, p_{j} ⟩ = 0$ . Conjugate symmetry then gives $⟨ p_{j}, r_{j + 1} ⟩ = 0$ , whence $⟨ p_{j + 1}, r_{j + 1} ⟩ = ⟨ r_{j + 1}, r_{j + 1} ⟩ + β_{j} ⟨ p_{j}, r_{j + 1} ⟩ = ⟨ r_{j + 1}, r_{j + 1} ⟩ .$ Thus the identity holds for every $j \leq k$ .

2.1L1step 1.1algebra∎

At $j = k$ , step 1.1 gives $⟨ p_{k}, r_{k} ⟩ = ⟨ r_{k}, r_{k} ⟩ > 0$ because $r_{k} \neq 0$ . Hence $p_{k} \neq 0$ . By [L1], $p_{k}^{*} A p_{k} = ⟨ A p_{k}, p_{k} ⟩ = ∥ p_{k} ∥_{A}^{2} > 0,$ which is the desired positivity of the denominator.

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-5.6-terra)audited 2026-09-01Open item page →

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

Statement

Let $A$ be Hermitian positive definite, and run the conjugate-gradient recurrence in exact arithmetic. For all indices $i \neq j$ for which the quantities are defined,

$⟨ r_{i}, r_{j} ⟩ = 0, p_{i}^{*} A p_{j} = 0.$

Thus the residuals are mutually orthogonal and the search directions are $A$ -conjugate.

Facts & Assumptions

Given: A Hermitian positive-definite system $A x = b$ and an exact-arithmetic CG run.

[F1]

CG uses the recurrence $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 $α_{k} = \frac{⟨ r_{k}, r_{k} ⟩}{⟨ A p_{k}, p_{k} ⟩}, β_{k} = \frac{⟨ r_{k + 1}, r_{k + 1} ⟩}{⟨ r_{k}, r_{k} ⟩}$ (The conjugate-gradient recurrence).

[L1]

If $r_{k} \neq 0$ , then $p_{k}^{*} A p_{k} > 0$ (Before convergence, every CG denominator $p_{k}^{*} A p_{k}$ is positive).

[L2]

The energy inner product is $⟨ u, v ⟩_{A} = ⟨ A u, v ⟩$ (The energy inner product $⟨ u, v ⟩_{A} = ⟨ A u, v ⟩$ and energy norm $∥ u ∥_{A}$ for a Hermitian positive-definite matrix).

Proof

technique · induction on the later index

1.1F1baseihalgebra

We prove by induction on $k \geq 0$ that $r_{0}, \dots, r_{k}$ are pairwise orthogonal and $p_{0}, \dots, p_{k}$ are pairwise $A$ -conjugate. For $k = 0$ there is nothing to prove. Assume the claim through step $k$ . Because $p_{j} = r_{j} + β_{j - 1} p_{j - 1}$ for $j \geq 1$ and $r_{j} = p_{j} - β_{j - 1} p_{j - 1}$ , the spans $span {p_{0}, \dots, p_{j}}$ and $span {r_{0}, \dots, r_{j}}$ agree for every $j$ .

2.1F1L2step 1.1ihalgebra

For $i < k$ , the induction hypothesis and step 1.1 give $⟨ r_{i}, r_{k + 1} ⟩ = ⟨ r_{i}, r_{k} ⟩ - α_{k} ⟨ r_{i}, A p_{k} ⟩ = - α_{k} ⟨ r_{i}, p_{k} ⟩_{A} = 0,$ using [L2], because $r_{i}$ lies in $span {p_{0}, \dots, p_{i}}$ and $p_{k}$ is $A$ -conjugate to each of those earlier directions. Also, $⟨ r_{k}, r_{k + 1} ⟩ = ⟨ r_{k}, r_{k} ⟩ - α_{k} ⟨ r_{k}, p_{k} ⟩_{A} .$ Since $r_{k} = p_{k} - β_{k - 1} p_{k - 1}$ for $k \geq 1$ , the induction hypothesis gives $⟨ r_{k}, p_{k} ⟩_{A} = ⟨ p_{k}, p_{k} ⟩_{A}$ , and for $k = 0$ the same identity is immediate. Using [F1], we obtain $⟨ r_{k}, r_{k + 1} ⟩ = ⟨ r_{k}, r_{k} ⟩ - α_{k} ⟨ p_{k}, p_{k} ⟩_{A} = 0$ . Thus $r_{k + 1}$ is orthogonal to every earlier residual.

3.1F1L1step 2.1discharge-inductionalgebra∎

For $i < k$ , Hermitian symmetry and [F1] give $p_{i}^{*} A p_{k + 1} = p_{i}^{*} A r_{k + 1} + β_{k} p_{i}^{*} A p_{k} = (A p_{i})^{*} r_{k + 1} .$ Because $A p_{i} = α_{i}^{- 1} (r_{i} - r_{i + 1})$ from [F1], step 2.1 implies $(A p_{i})^{*} r_{k + 1} = 0$ , so $p_{i}^{*} A p_{k + 1} = 0$ . For $i = k$ , step 2.1 yields $⟨ r_{k}, r_{k + 1} ⟩ = 0$ , hence $p_{k}^{*} A r_{k + 1} = (A p_{k})^{*} r_{k + 1} = α_{k}^{- 1} (r_{k} - r_{k + 1})^{*} r_{k + 1} = - α_{k}^{- 1} ⟨ r_{k + 1}, r_{k + 1} ⟩ .$ Therefore $p_{k}^{*} A p_{k + 1} = p_{k}^{*} A r_{k + 1} + β_{k} p_{k}^{*} A p_{k} = - α_{k}^{- 1} ⟨ r_{k + 1}, r_{k + 1} ⟩ + β_{k} p_{k}^{*} A p_{k} = 0,$ because $β_{k} = ⟨ r_{k + 1}, r_{k + 1} ⟩ / ⟨ r_{k}, r_{k} ⟩$ and $α_{k} = ⟨ r_{k}, r_{k} ⟩ / (p_{k}^{*} A p_{k})$ by [F1], with positivity from [L1] ensuring these divisions are valid before convergence. This closes the induction.

TheoremStatement: AI-adaptedProof: AI-generatedprecheck passaudited 2026-09-01Open item page →

CG is the Krylov Galerkin method, and the $m$ th iterate uniquely minimizes the $A$ -norm of the error over $x_{0} + K_{m} (A, r_{0})$

Statement

Let $A$ be Hermitian positive definite, let $A x = b$ , let $x_{0}$ be an initial guess, let $x_{*}$ be the exact solution of $A x = b$ , and let $x_{m}$ be the $m$ th conjugate-gradient iterate with initial residual $r_{0} = b - A x_{0}$ . Then $x_{m}$ is the unique Krylov Galerkin iterate in $x_{0} + K_{m} (A, r_{0})$ , and for every $x \in x_{0} + K_{m} (A, r_{0})$ ,

$∥ x_{*} - x_{m} ∥_{A} \leq ∥ x_{*} - x ∥_{A},$

with equality only when $x = x_{m}$ .

Facts & Assumptions

Given: A Hermitian positive-definite system $A x = b$ , an initial guess $x_{0}$ , the exact solution $x_{*}$ , the initial residual $r_{0} = b - A x_{0}$ , and the $m$ th CG iterate $x_{m}$ .

[F1]

[L1]

Residual orthogonality to $K_{m} (A, r_{0})$ 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_{*}) = \frac{1}{2} ∥ x - x_{*} ∥_{A}^{2},$ where $ϕ$ is the quadratic energy (For Hermitian positive-definite $A$ , the exact solution of $A x = b$ is the unique minimizer of the quadratic energy).

Proof

technique · direct

1.1L2algebra

The CG recurrence gives $x_{m} - x_{0}$ as a linear combination of $p_{0}, \dots, p_{m - 1}$ , so $x_{m} \in x_{0} + span {p_{0}, \dots, p_{m - 1}}$ . Also each residual satisfies $r_{j} = r_{0} - A (x_{j} - x_{0})$ , so $r_{j} \in K_{j + 1} (A, r_{0}) \subseteq K_{m} (A, r_{0})$ for $j < m$ , and each $p_{j} = r_{j} + β_{j - 1} p_{j - 1}$ therefore also lies in $K_{m} (A, r_{0})$ . By [L2], the nonzero residuals $r_{0}, \dots, r_{m - 1}$ are mutually orthogonal, hence linearly independent; since they all lie in the $m$ -generated space $K_{m} (A, r_{0})$ , they form a basis of that space, and so do $p_{0}, \dots, p_{m - 1}$ by the triangular relation $p_{j} \in r_{j} + span {r_{0}, \dots, r_{j - 1}}$ . Thus $x_{m} \in x_{0} + K_{m} (A, r_{0})$ .

2.1F1L1L2step 1.1

By [L2], the residual $r_{m}$ is orthogonal to each earlier residual. Since step 1.1 shows that $p_{0}, \dots, p_{m - 1}$ form a basis of $K_{m} (A, r_{0})$ and each $p_{j}$ lies in $span {r_{0}, \dots, r_{j}}$ , the same orthogonality implies $r_{m}$ is orthogonal to $K_{m} (A, r_{0})$ . Therefore $x_{m}$ is a Krylov Galerkin iterate by [F1], and [L1] makes it unique.

3.1L1L3step 2.1algebra∎

Let $x \in x_{0} + K_{m} (A, r_{0})$ and put $v : = x - x_{m} \in K_{m} (A, r_{0})$ . By [L1] and step 2.1, the error $x_{*} - x_{m}$ is $A$ -orthogonal to $v$ , so $∥ x_{*} - x ∥_{A}^{2} = ∥ (x_{*} - x_{m}) - v ∥_{A}^{2} = ∥ x_{*} - x_{m} ∥_{A}^{2} + ∥ v ∥_{A}^{2} .$ Hence $∥ x_{*} - x_{m} ∥_{A} \leq ∥ x_{*} - x ∥_{A}$ , with equality only if $v = 0$ , that is, $x = x_{m}$ . Using [L3], this is equivalent to saying that $x_{m}$ also uniquely minimizes the quadratic energy over the same affine Krylov space.

TheoremStatement: Literature-sourcedProof: AI-generatedprecheck passaudited 2026-09-01Open item page →

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

Statement

Let $A \in M_{n} (C)$ be Hermitian positive definite, let $A x = b$ , let $x_{0}$ be an initial guess, let $r_{0} = b - A x_{0}$ , and let $ν = ν (A, r_{0})$ be the grade of $r_{0}$ . Then exact-arithmetic conjugate gradients reaches the exact solution no later than step $ν$ . In particular, $ν \leq n$ , so CG terminates in at most $n$ steps.

Facts & Assumptions

Given: A Hermitian positive-definite system $A x = b$ , an initial guess $x_{0}$ , the initial residual $r_{0} = b - A x_{0}$ , the grade $ν = ν (A, r_{0})$ , and the exact solution $x_{*}$ .

[F1]

The grade $ν (A, r_{0})$ is the degree of the monic polynomial of least degree that annihilates $r_{0}$ , and it is $0$ when $r_{0} = 0$ (The grade of a start vector and its relative minimal polynomial).

[L1]

If $A$ is invertible, then the exact solution of $A e = r_{0}$ lies in $K_{ν} (A, r_{0})$ (If $A$ is invertible, the exact solution of $A x = b$ lies in the Krylov space at the grade).

[L2]

The $m$ th CG iterate uniquely minimizes the $A$ -norm of the error over $x_{0} + K_{m} (A, r_{0})$ (CG is the Krylov Galerkin method, and the $m$ th iterate uniquely minimizes the $A$ -norm of the error over $x_{0} + K_{m} (A, r_{0})$ ).

Proof

technique · direct

1.1F1L1algebra

If $r_{0} = 0$ , then $A x_{0} = b$ , so CG has already reached the exact solution at step $0 = ν$ by [F1]. Assume now that $r_{0} \neq 0$ . The initial error $e_{0} : = x_{*} - x_{0}$ satisfies $A e_{0} = r_{0}$ , so [L1] gives $e_{0} \in K_{ν} (A, r_{0})$ . Therefore $x_{*} = x_{0} + e_{0} \in x_{0} + K_{ν} (A, r_{0}) .$

2.1L2step 1.1

If CG has already reached $x_{*}$ at some step $m < ν$ , then it has certainly terminated no later than step $ν$ . Otherwise the recurrence defines the $ν$ th iterate, so [L2] applies with $m = ν$ . Since $x_{*}$ itself belongs to the admissible affine space from step 1.1 and has zero error, the minimal $A$ -norm error over that space is $0$ . Hence the unique minimizer is $x_{ν} = x_{*}$ , so CG terminates no later than step $ν$ .

3.1F1step 2.1algebra∎

Because $A$ is $n \times n$ , the $n + 1$ vectors $r_{0}, A r_{0}, \dots, A^{n} r_{0}$ are linearly dependent. Thus some nonzero polynomial of degree at most $n$ annihilates $r_{0}$ , and the minimal possible degree in [F1] therefore satisfies $ν \leq n$ . Combining this with step 2.1 gives termination in at most $n$ steps.

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passaudited 2026-09-01Open item page →

CG obeys the Chebyshev $A$ -norm bound in terms of the spectral condition number $κ_{2} (A)$

Statement

Let $A \in M_{n} (C)$ be Hermitian positive definite, let $x_{*}$ solve $A x = b$ , let $e_{m} : = x_{*} - x_{m}$ be the error in the $m$ th exact-arithmetic CG iterate, let $0 < λ_{\min} \leq λ_{\max}$ be the smallest and largest eigenvalues of $A$ , and let

$κ : = \frac{λ_{\max}}{λ_{\min}} .$

Then for every $m \geq 0$ ,

$∥ e_{m} ∥_{A} \leq 2 {(\frac{\sqrt{κ} - 1}{\sqrt{κ} + 1})}^{m} ∥ e_{0} ∥_{A} .$

Facts & Assumptions

Given: A Hermitian positive-definite matrix $A$ , the exact solution $x_{*}$ , the CG iterates $x_{m}$ , the errors $e_{m} = x_{*} - x_{m}$ , and the extremal eigenvalues $0 < λ_{\min} \leq λ_{\max}$ of $A$ .

[L1]

[L2]

In an orthonormal basis, a Hermitian matrix is normal (In an orthonormal basis, self-adjoint means conjugate-transpose symmetry and normal means commuting with the conjugate transpose).

[L3]

A normal endomorphism of a finite-dimensional complex inner-product space has an orthonormal eigenbasis (Complex spectral theorem: a normal endomorphism of a finite-dimensional complex inner product space has an orthonormal eigenbasis, and conversely).

Proof

technique · direct

1.1L1algebra

Every vector in $x_{0} + K_{m} (A, r_{0})$ has the form $x_{0} + A z (A) e_{0}$ for some polynomial $z$ of degree at most $m - 1$ , because $r_{0} = A e_{0}$ . Hence every attainable error has the form $e_{0} - A z (A) e_{0} = p (A) e_{0},$ where $p (0) = 1$ and $\deg p \leq m$ . By [L1], the actual CG error therefore satisfies $∥ e_{m} ∥_{A} \leq \min_{\begin{array}{c} p (0) = 1 \\ \deg p \leq m \end{array}} ∥ p (A) e_{0} ∥_{A} .$

2.1L2L3step 1.1algebra

Since $A$ is Hermitian, [L2] and [L3] give an orthonormal basis of eigenvectors, so $A = U Λ U^{*}$ with $U$ unitary and $Λ = diag (λ_{1}, \dots, λ_{n})$ , where each $λ_{j} > 0$ . Writing $U^{*} e_{0} = c$ , one gets $∥ p (A) e_{0} ∥_{A}^{2} = ⟨ A p (A) e_{0}, p (A) e_{0} ⟩ = \sum_{j = 1}^{n} λ_{j} ∣ p (λ_{j}) ∣^{2} ∣ c_{j} ∣^{2} \leq \max_{λ \in [λ_{\min}, λ_{\max}]} ∣ p (λ) ∣^{2} ∥ e_{0} ∥_{A}^{2} .$ Thus $∥ e_{m} ∥_{A} \leq \min_{\begin{array}{c} p (0) = 1 \\ \deg p \leq m \end{array}} \max_{λ \in [λ_{\min}, λ_{\max}]} ∣ p (λ) ∣ ∥ e_{0} ∥_{A} .$

3.1step 2.1algebra∎

Let $t (λ) : = \frac{λ_{\max} + λ_{\min} - 2 λ}{λ_{\max} - λ_{\min}}, p_{m} (λ) : = \frac{T_{m} (t (λ))}{T_{m} ⁣ (\frac{λ_{\max} + λ_{\min}}{λ_{\max} - λ_{\min}})},$ where $T_{m}$ is the $m$ th Chebyshev polynomial. Then $p_{m} (0) = 1$ , $\deg p_{m} = m$ , and $∣ T_{m} (t) ∣ \leq 1$ on $[- 1, 1]$ , so $\max_{λ \in [λ_{\min}, λ_{\max}]} ∣ p_{m} (λ) ∣ \leq \frac{1}{∣ T_{m} ⁣ (\frac{λ_{\max} + λ_{\min}}{λ_{\max} - λ_{\min}}) ∣} .$ With $κ = λ_{\max} / λ_{\min}$ , the denominator equals $T_{m} ((κ + 1) / (κ - 1))$ . For $s > 1$ , $T_{m} (s) = \frac{(s + \sqrt{s^{2} - 1})^{m} + (s - \sqrt{s^{2} - 1})^{m}}{2} \geq \frac{(s + \sqrt{s^{2} - 1})^{m}}{2},$ and at $s = (κ + 1) / (κ - 1)$ one has $\frac{1}{s + \sqrt{s^{2} - 1}} = \frac{\sqrt{κ} - 1}{\sqrt{κ} + 1} .$ Therefore $\max_{λ \in [λ_{\min}, λ_{\max}]} ∣ p_{m} (λ) ∣ \leq 2 {(\frac{\sqrt{κ} - 1}{\sqrt{κ} + 1})}^{m} .$ Combining this polynomial with step 2.1 gives the stated bound.

RemarkRemark: AI-adaptedProof: Not applicablejudge pass (gpt-5.6-terra)audited 2026-09-01Open item page →

In floating-point arithmetic, CG can lose exact residual orthogonality, $A$ -conjugacy, and the finite-termination guarantee

Remark

The orthogonality and finite-termination theorems on this page are exact arithmetic statements. In floating-point arithmetic, rounding errors perturb the three-term recurrence, so later residuals need not remain exactly orthogonal and later search directions need not remain exactly $A$ -conjugate. Once those identities drift, the argument that forces termination by the relative grade no longer applies verbatim. Practical CG often still converges well, but the exact algebraic structure is only approximate.

DefinitionDefinition: AI-adaptedProof: Not applicableaudited 2026-09-01Open item page →

The Lanczos process as Arnoldi specialized to a Hermitian matrix, with the usual real-subdiagonal phase convention

Definition

Let $A$ be Hermitian and let $q_{1} = b / ∥ b ∥_{2}$ for a nonzero start vector $b$ . Running Arnoldi on $(A, b)$ is called the Lanczos process when one records the coefficients, at every step before Arnoldi breakdown, in the three-term form

$A q_{j} = β_{j - 1} q_{j - 1} + α_{j} q_{j} + β_{j} q_{j + 1} (j \geq 1, q_{0} : = 0, β_{0} : = 0),$

with $α_{j} \in R$ and the phase of $q_{j + 1}$ chosen so that $β_{j} \geq 0$ is real. In matrix form this is the Hermitian specialization of The Arnoldi process for building an orthonormal basis of a Krylov subspace.

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-5.6-terra)audited 2026-09-01Open item page →

With a Hermitian matrix, Arnoldi collapses to the Lanczos three-term recurrence and a real symmetric tridiagonal projection

Statement

Let $A$ be Hermitian, and run Arnoldi on $(A, b)$ through step $m$ without breakdown. Write

$A Q_{m} = Q_{m + 1} {\overset{ˉ}{H}}_{m}, Q_{m} = [q_{1} \dots q_{m}] .$

Then there exist real numbers $α_{1}, \dots, α_{m}$ and nonnegative real numbers $β_{1}, \dots, β_{m}$ such that

$A q_{j} = β_{j - 1} q_{j - 1} + α_{j} q_{j} + β_{j} q_{j + 1} (1 \leq j \leq m, q_{0} : = 0, β_{0} : = 0) .$

Moreover, $T_{m} : = Q_{m}^{*} A Q_{m}$ is a real symmetric tridiagonal matrix.

Facts & Assumptions

Given: A Hermitian matrix $A$ and an Arnoldi run through step $m$ without breakdown.

[F1]

The Lanczos process is Arnoldi specialized to a Hermitian matrix, with the phase chosen so that the subdiagonal coefficients are real and nonnegative (The Lanczos process as Arnoldi specialized to a Hermitian matrix, with the usual real-subdiagonal phase convention).

[L1]

Arnoldi yields an orthonormal basis and an upper-Hessenberg factorization $A Q_{m} = Q_{m + 1} {\overset{ˉ}{H}}_{m},$ with column relations $A q_{j} = \sum_{i = 1}^{j + 1} h_{i j} q_{i}$ (Before breakdown, Arnoldi produces an orthonormal Krylov basis and a rectangular upper-Hessenberg factorization).

[L2]

An upper-Hessenberg matrix has $h_{i j} = 0$ for $i > j + 1$ , and a real symmetric tridiagonal matrix has zeros whenever $∣ i - j ∣ > 1$ (Upper Hessenberg matrices and real symmetric tridiagonal matrices).

Proof

technique · direct

1.1L1L2algebra

Fix $j$ and let $i \leq j - 2$ . By [L1], $A q_{i}$ lies in $span {q_{1}, \dots, q_{i + 1}}$ , which is orthogonal to $q_{j}$ . Since $A$ is Hermitian, $h_{i j} = q_{i}^{*} A q_{j} = (A q_{i})^{*} q_{j} = 0.$ Together with the upper-Hessenberg zero pattern from [L2], this shows that the only possibly nonzero coefficients in column $j$ are $h_{j - 1, j}$ , $h_{j j}$ , and $h_{j + 1, j}$ . Therefore each Arnoldi column relation collapses to a three-term recurrence.

2.1F1step 1.1algebra

Hermitian symmetry also gives $h_{j, j - 1} = \overline{h_{j - 1, j}}$ . Under the phase convention in [F1], the subdiagonal coefficients $h_{j + 1, j}$ are real and nonnegative; write $β_{j} : = h_{j + 1, j}$ and $α_{j} : = h_{j j}$ . Since $h_{j j} = q_{j}^{*} A q_{j}$ equals its own complex conjugate, each $α_{j}$ is real. Hence $A q_{j} = β_{j - 1} q_{j - 1} + α_{j} q_{j} + β_{j} q_{j + 1},$ which is the Lanczos recurrence.

3.1L2step 1.1step 2.1∎

The projected matrix is $T_{m} = Q_{m}^{*} A Q_{m} = (q_{i}^{*} A q_{j})_{i, j} = (h_{i j})_{1 \leq i, j \leq m}$ . Step 1.1 shows $h_{i j} = 0$ for $∣ i - j ∣ > 1$ , and Hermitian symmetry together with the reality from step 2.1 shows $h_{i j} = h_{j i} \in R$ on the remaining bands. Thus $T_{m}$ is a real symmetric tridiagonal matrix in the sense of [L2].

DefinitionDefinition: Literature-sourcedProof: Not applicableaudited 2026-09-01Open item page →

The MINRES iterate from the Lanczos tridiagonal least-squares problem

Definition

Let $A$ be Hermitian, let $x_{0}$ be an initial guess for $A x = b$ , let $r_{0} = b - A x_{0}$ , and put $β = ∥ r_{0} ∥_{2}$ . Assume Lanczos runs through step $m$ without breakdown and yields

$A Q_{m} = Q_{m + 1} {\overset{ˉ}{T}}_{m}, r_{0} = β q_{1} = β Q_{m + 1} e_{1},$

with ${\overset{ˉ}{T}}_{m}$ tridiagonal in the sense of With a Hermitian matrix, Arnoldi collapses to the Lanczos three-term recurrence and a real symmetric tridiagonal projection. A vector

$x_{m} : = x_{0} + Q_{m} y_{m}$

is an $m$ th MINRES iterate when $y_{m}$ minimizes

$∥ β e_{1} - {\overset{ˉ}{T}}_{m} y ∥_{2}$

over all $y \in C^{m}$ . Such a minimizer exists by For a linear map $T : V \to W$ between finite-dimensional inner-product spaces, $x$ minimises $∥ T x - b ∥$ if and only if $T^{*} (T x - b) = 0$ , equivalently $T^{*} T x = T^{*} b$ ; minimisers exist and any two differ by an element of $\ker T$ .

TheoremStatement: Literature-sourcedProof: AI-generatedprecheck passaudited 2026-09-01Open item page →

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

Statement

Let $A$ be Hermitian, let $x_{0}$ be an initial guess for $A x = b$ , let $r_{0} = b - A x_{0}$ , and let $x_{m}$ be an $m$ th MINRES iterate from the Lanczos tridiagonal least-squares problem. Then

$∥ b - A x_{m} ∥_{2} = \min_{x \in x_{0} + K_{m} (A, r_{0})} ∥ b - A x ∥_{2} .$

This remains valid when $A$ is Hermitian indefinite.

Facts & Assumptions

Given: A Hermitian matrix $A$ , an initial guess $x_{0}$ , the residual $r_{0} = b - A x_{0}$ , and an $m$ th MINRES iterate $x_{m}$ .

[F1]

A MINRES iterate has the form $x_{m} = x_{0} + Q_{m} y_{m}$ , where $y_{m}$ minimizes $∥ β e_{1} - {\overset{ˉ}{T}}_{m} y ∥_{2}$ for the Lanczos tridiagonalization (The MINRES iterate from the Lanczos tridiagonal least-squares problem).

[L1]

For Hermitian $A$ , Arnoldi collapses to the Lanczos factorization with tridiagonal ${\overset{ˉ}{T}}_{m}$ (With a Hermitian matrix, Arnoldi collapses to the Lanczos three-term recurrence and a real symmetric tridiagonal projection).

[L2]

Arnoldi reduces GMRES to the small least-squares problem $\min_{y} ∥ β e_{1} - {\overset{ˉ}{H}}_{m} y ∥_{2}$ (Arnoldi reduces GMRES to a least-squares problem for the small Hessenberg matrix).

[L3]

GMRES minimizes the Euclidean residual over $x_{0} + K_{m} (A, r_{0})$ (GMRES minimizes the residual norm over the affine Krylov space $x_{0} + K_{m} (A, r_{0})$ ).

Proof

technique · direct

1.1F1L1L2

By [L1], the Hermitian Arnoldi factorization uses the same orthonormal Krylov basis $Q_{m}$ as Arnoldi but with ${\overset{ˉ}{H}}_{m} = {\overset{ˉ}{T}}_{m}$ tridiagonal. Therefore the least-squares problem in [L2] is exactly the Lanczos least-squares problem recorded in [F1].

2.1F1L3step 1.1∎

Step 1.1 shows that the vector $x_{m} = x_{0} + Q_{m} y_{m}$ coming from [F1] is also the GMRES iterate at step $m$ . Applying [L3] gives $∥ b - A x_{m} ∥_{2} = \min_{x \in x_{0} + K_{m} (A, r_{0})} ∥ b - A x ∥_{2} .$ Neither step 1.1 nor [L3] uses positive definiteness, only Hermitian structure, so the same conclusion holds for Hermitian indefinite $A$ .

DefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (gpt-5.6-terra)audited 2026-09-01Open item page →

Stationary iteration from a matrix splitting $A = M - N$

Definition

Let $A \in M_{n} (F)$ admit a matrix splitting

$A = M - N,$

where $M \in {GL}_{n} (F)$ is invertible in the sense of Invertible matrices and the general linear group ${GL}_{n} (F)$ . The associated stationary iteration for the system $A x = b$ is

$x_{k + 1} = M^{- 1} N x_{k} + M^{- 1} b .$

Its iteration matrix is

$B : = M^{- 1} N .$

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-5.6-terra)audited 2026-09-01Open item page →

A stationary splitting converges for every start if and only if its iteration matrix has spectral radius below $1$

Statement

Let $A = M - N$ be a matrix splitting in $M_{n} (C)$ with stationary iteration

$x_{k + 1} = M^{- 1} N x_{k} + M^{- 1} b,$

and let $B : = M^{- 1} N$ be its iteration matrix. Then the following are equivalent:

For every right-hand side $b$ and every initial vector $x_{0}$ , the iterates converge to the unique solution of $A x = b$ .
The spectral radius $ρ (B)$ is strictly less than $1$ .

Facts & Assumptions

Given: A complex matrix splitting $A = M - N$ with invertible $M$ , its stationary iteration, and its iteration matrix $B = M^{- 1} N$ .

[F1]

The stationary iteration is $x_{k + 1} = B x_{k} + M^{- 1} b$ with $B = M^{- 1} N$ (Stationary iteration from a matrix splitting $A = M - N$ ).

[L1]

The field $C$ is algebraically closed (The complex numbers are algebraically closed).

[L2]

Over an algebraically closed field, every endomorphism has Jordan form (Every finite-dimensional endomorphism over an algebraically closed field has Jordan form).

[L3]

The spectrum is the root set of the characteristic polynomial (For every finite-dimensional space, $σ_{F} (T)$ is exactly the set of roots in $F$ of $χ_{T}$ ).

Proof

technique · direct

1.1F1algebra

A vector $x$ is a fixed point of the stationary iteration if and only if it solves $A x = b$ : indeed, by [F1], $x = B x + M^{- 1} b ⟺ M x = N x + b ⟺ A x = b .$ Therefore, whenever $x_{*}$ solves $A x = b$ , the error $e_{k} : = x_{k} - x_{*}$ satisfies $e_{k + 1} = B x_{k} + M^{- 1} b - x_{*} = B (x_{k} - x_{*}) = B e_{k} .$

2.1L1L2L3step 1.1algebra

Assume $ρ (B) < 1$ . By [L1], [L2], and [L3], we may write $B = S J S^{- 1}$ with $J$ Jordan and every eigenvalue $λ$ of $B$ satisfying $∣ λ ∣ < 1$ . On a Jordan block $J_{λ} = λ I + N$ with nilpotent $N$ , one has $J_{λ}^{k} = \sum_{j = 0}^{s - 1} (\binom{k}{j}) λ^{k - j} N^{j} .$ Because $∣ λ ∣ < 1$ , each scalar factor $(\binom{k}{j}) λ^{k - j}$ tends to $0$ , so every Jordan block tends to $0$ . Hence $J^{k} \to 0$ and therefore $B^{k} \to 0$ . Since $1 \notin σ (B)$ , the matrix $I - B$ is invertible by [L3]. Define $x_{*} : = (I - B)^{- 1} M^{- 1} b .$ Then $(I - B) x_{*} = M^{- 1} b$ , so $x_{*} = B x_{*} + M^{- 1} b$ , and step 1.1 shows that $x_{*}$ solves $A x = b$ . For any initial vector $x_{0}$ , step 1.1 gives $e_{k} = B^{k} e_{0} \to 0$ , so the iterates converge to $x_{*}$ . If $y$ is another solution of $A x = b$ , then step 1.1 also gives $y = B y + M^{- 1} b$ , hence $y - x_{*} = B (y - x_{*}) .$ Iterating and using $B^{k} \to 0$ yields $y - x_{*} = B^{k} (y - x_{*}) \to 0$ , so $y = x_{*}$ . Thus the iterates converge to the unique solution of $A x = b$ for every $b$ and every $x_{0}$ .

3.1L3step 1.1algebra∎

Conversely, assume the iteration converges for every $b$ and every $x_{0}$ . Taking $b = 0$ , statement 1 gives convergence to the unique solution of $A x = 0$ . By step 1.1 that unique solution is also the unique fixed point of $x \mapsto B x$ , so it is $0$ . Hence for every start $x_{0}$ one has $B^{k} x_{0} = x_{k} \to 0$ , which means $B^{k} \to 0$ . If $B v = λ v$ with $v \neq 0$ , then $λ^{k} v = B^{k} v \to 0,$ so $λ^{k} \to 0$ and therefore $∣ λ ∣ < 1$ . By [L3], every spectral value of $B$ is such an eigenvalue over $C$ , and thus $ρ (B) < 1$ .

DefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (gpt-5.6-terra)audited 2026-09-01Open item page →

Left preconditioning, right preconditioning, and symmetric preconditioning of a linear system

Definition

Let $A x = b$ be a linear system.

If $P \in {GL}_{n} (F)$ is invertible, the left-preconditioned system is

$P^{- 1} A x = P^{- 1} b .$

If $P \in {GL}_{n} (F)$ is invertible and $y : = P x$ , the right-preconditioned system is

$A P^{- 1} y = b, x = P^{- 1} y .$

If $M$ is Hermitian positive definite, then by A matrix admits a Cholesky factorisation with positive diagonal exactly when it is Hermitian positive definite, and that factor is unique it has a Cholesky factor $M = C C^{*}$ with $C$ invertible. The corresponding symmetric preconditioning is

$C^{- 1} A C^{- *} y = C^{- 1} b, x = C^{- *} y .$

PropositionStatement: Literature-sourcedProof: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-09-01Open item page →

Invertible preconditioners give equivalent linear systems, with the transformed residuals and errors written explicitly

Statement

Let $A x = b$ be a linear system. In the error formulas in parts 2 and 3, assume $x_{*}$ is a solution of $A x = b$ and put $e : = x - x_{*}$ . The corresponding transformed exact solutions are denoted by $y_{*}$ .

If $P \in {GL}_{n} (F)$ and $P^{- 1} A x = P^{- 1} b,$ then the left-preconditioned system has exactly the same solution set as $A x = b$ . Its residual is $\tilde{r} = P^{- 1} r$ , where $r = b - A x$ .
If $P \in {GL}_{n} (F)$ and $y : = P x$ , then $A P^{- 1} y = b$ is equivalent to $A x = b$ . Its residual is the same physical residual $\hat{r} = b - A P^{- 1} y = r$ , and its error is $\hat{e} = y - y_{*} = P e$ , where $y_{*} : = P x_{*}$ .
If $M = C C^{*}$ is Hermitian positive definite and $y : = C^{*} x$ , then $C^{- 1} A C^{- *} y = C^{- 1} b$ is equivalent to $A x = b$ . Its residual is $r_{s y m} = C^{- 1} r,$ and its error is $e_{s y m} = y - y_{*} = C^{*} e,$ where $y_{*} : = C^{*} x_{*}$ .

Facts & Assumptions

Given: A linear system $A x = b$ , the left, right, and symmetric preconditioned forms from the definition, and, when an error formula is used, a solution $x_{*}$ of $A x = b$ .

[F1]

Left, right, and symmetric preconditioning are exactly the transformed systems $P^{- 1} A x = P^{- 1} b, A P^{- 1} y = b, C^{- 1} A C^{- *} y = C^{- 1} b$ with the accompanying variable changes (Left preconditioning, right preconditioning, and symmetric preconditioning of a linear system).

[L1]

An invertible matrix has a two-sided inverse (Invertible matrices and the general linear group ${GL}_{n} (F)$ ).

Proof

technique · direct

1.1F1L1algebra

For left preconditioning, [L1] implies $A x = b ⟺ P^{- 1} A x = P^{- 1} b .$ For any trial vector $x$ , the transformed residual is $P^{- 1} b - P^{- 1} A x = P^{- 1} (b - A x) = P^{- 1} r .$

1.2F1L1algebra

For right preconditioning, put $y = P x$ , so $x = P^{- 1} y$ by [L1]. Then $A x = b ⟺ A P^{- 1} y = b .$ The right-preconditioned residual is $b - A P^{- 1} y = b - A x = r,$ and if $y_{*} = P x_{*}$ then $y - y_{*} = P (x - x_{*}) = P e .$

2.1F1L1algebra∎

For symmetric preconditioning, [F1] writes $x = C^{- *} y$ , equivalently $y = C^{*} x$ . Therefore $A x = b ⟺ C^{- 1} A C^{- *} y = C^{- 1} b .$ If $y_{*} = C^{*} x_{*}$ , then $C^{- 1} b - C^{- 1} A C^{- *} y = C^{- 1} (b - A x) = C^{- 1} r,$ and $y - y_{*} = C^{*} (x - x_{*}) = C^{*} e .$ Thus each transformed system is equivalent to the original one, with the displayed residual and error maps.

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

Symmetric positive-definite preconditioning preserves a Hermitian positive-definite CG problem, and the CG bound uses the transformed condition number

Statement

Let $A \in M_{n} (C)$ be Hermitian positive definite, let $x_{*}$ solve $A x = b$ , and let $M$ be Hermitian positive definite. Write $M = C C^{*}$ , and define

$\tilde{A} : = C^{- 1} A C^{- *}, \tilde{b} : = C^{- 1} b, y : = C^{*} x, y_{*} : = C^{*} x_{*} .$

Then $\tilde{A}$ is Hermitian positive definite, the transformed system

$\tilde{A} y = \tilde{b}$

is equivalent to $A x = b$ , and

$∥ y - y_{*} ∥_{\tilde{A}} = ∥ x - x_{*} ∥_{A} .$

Consequently, if

$κ : = \frac{λ_{\max} (\tilde{A})}{λ_{\min} (\tilde{A})},$

then exact-arithmetic CG on the transformed system obeys

$∥ y_{*} - y_{m} ∥_{\tilde{A}} \leq 2 {(\frac{\sqrt{κ} - 1}{\sqrt{κ} + 1})}^{m} ∥ y_{*} - y_{0} ∥_{\tilde{A}},$

which is the preconditioned CG bound.

Facts & Assumptions

Given: A Hermitian positive-definite matrix $A$ , a Hermitian positive-definite preconditioner $M$ , and the symmetric transform $\tilde{A} = C^{- 1} A C^{- *}$ .

[F1]

Symmetric preconditioning uses the variable change $y = C^{*} x$ coming from a Cholesky factorization $M = C C^{*}$ (Left preconditioning, right preconditioning, and symmetric preconditioning of a linear system).

[L1]

Equivalent preconditioned systems have the transformed residual and error maps recorded explicitly (Invertible preconditioners give equivalent linear systems, with the transformed residuals and errors written explicitly).

[L2]

A Hermitian positive-definite matrix has a Cholesky factorization $M = C C^{*}$ with invertible $C$ (A matrix admits a Cholesky factorisation with positive diagonal exactly when it is Hermitian positive definite, and that factor is unique).

[L3]

CG obeys the Chebyshev $A$ -norm bound with the spectral condition number of its Hermitian positive-definite coefficient matrix (CG obeys the Chebyshev $A$ -norm bound in terms of the spectral condition number $κ_{2} (A)$ ).

Proof

technique · direct

1.1L2algebra

By [L2], the preconditioner has a factorization $M = C C^{*}$ with invertible $C$ . For any nonzero $z$ , $z^{*} \tilde{A} z = (C^{- *} z)^{*} A (C^{- *} z) > 0,$ because $C^{- *} z \neq 0$ and $A$ is Hermitian positive definite. Also ${\tilde{A}}^{*} = (C^{- 1} A C^{- *})^{*} = C^{- 1} A^{*} C^{- *} = C^{- 1} A C^{- *} = \tilde{A} .$ So $\tilde{A}$ is Hermitian positive definite.

2.1F1L1step 1.1algebra

By [F1] and [L1], the transformed system $\tilde{A} y = \tilde{b}$ is equivalent to $A x = b$ , and its transformed error is $e_{s y m} = y - y_{*} = C^{*} (x - x_{*})$ . Therefore $∥ y - y_{*} ∥_{\tilde{A}}^{2} = (y - y_{*})^{*} \tilde{A} (y - y_{*}) = (x - x_{*})^{*} A (x - x_{*}) = ∥ x - x_{*} ∥_{A}^{2} .$ Hence the energy norms agree under the symmetric change of variables.

3.1L3step 1.1step 2.1∎

Since step 1.1 shows that $\tilde{A}$ is Hermitian positive definite, [L3] applies to the transformed system and gives $∥ y_{*} - y_{m} ∥_{\tilde{A}} \leq 2 {(\frac{\sqrt{κ} - 1}{\sqrt{κ} + 1})}^{m} ∥ y_{*} - y_{0} ∥_{\tilde{A}},$ where $κ = λ_{\max} (\tilde{A}) / λ_{\min} (\tilde{A})$ is the spectral ratio from the Statement. By step 2.1, this is exactly the preconditioned CG estimate expressed in the original variables. The bound depends on the transformed operator $\tilde{A}$ , not on $κ_{2} (A)$ by itself.

5 · Examples, counterexamples and false statements

None yet.

Conjugate Gradients, MINRES and Preconditioning

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

The energy inner product ⟨u,v⟩A=⟨Au,v⟩⟨u,v⟩A​=⟨Au,v⟩ and energy norm ∥u∥A∥u∥A​ for a Hermitian positive-definite matrix

Definition

The quadratic energy ϕ(x)=12⟨Ax,x⟩−Re⁡⟨b,x⟩ϕ(x)=21​⟨Ax,x⟩−Re⟨b,x⟩ of a Hermitian positive-definite linear system

Definition

For Hermitian positive-definite AA, the exact solution of Ax=bAx=b is the unique minimizer of the quadratic energy

Statement

Facts & Assumptions

Proof

The mmth Krylov Galerkin iterate in the affine space x0+Km(A,r0)x0​+Km​(A,r0​) for a Hermitian positive-definite system

Definition

Galerkin orthogonality turns residual orthogonality into AA-orthogonality of the error, and the Galerkin iterate is unique

Statement

Facts & Assumptions

Proof

The conjugate-gradient recurrence

Definition

Before convergence, every CG denominator pk∗Apkpk∗​Apk​ is positive

Statement

Facts & Assumptions

Proof

In exact arithmetic, CG residuals are mutually orthogonal and the search directions are AA-conjugate

Statement

Facts & Assumptions

Proof

CG is the Krylov Galerkin method, and the mmth iterate uniquely minimizes the AA-norm of the error over x0+Km(A,r0)x0​+Km​(A,r0​)

Statement

Facts & Assumptions

Proof

In exact arithmetic, CG terminates no later than the relative grade and hence in at most nn steps

Statement

Facts & Assumptions

Proof

CG obeys the Chebyshev AA-norm bound in terms of the spectral condition number κ2(A)κ2​(A)

Statement

Facts & Assumptions

Proof

In floating-point arithmetic, CG can lose exact residual orthogonality, AA-conjugacy, and the finite-termination guarantee

Remark

The Lanczos process as Arnoldi specialized to a Hermitian matrix, with the usual real-subdiagonal phase convention

Definition

With a Hermitian matrix, Arnoldi collapses to the Lanczos three-term recurrence and a real symmetric tridiagonal projection

Statement

Facts & Assumptions

Proof

The MINRES iterate from the Lanczos tridiagonal least-squares problem

Definition

For Hermitian AA, including the indefinite case, MINRES minimizes the Euclidean residual over x0+Km(A,r0)x0​+Km​(A,r0​)

Statement

Facts & Assumptions

Proof

Stationary iteration from a matrix splitting A=M−NA=M−N

Definition

A stationary splitting converges for every start if and only if its iteration matrix has spectral radius below 11

Statement

Facts & Assumptions

Proof

Left preconditioning, right preconditioning, and symmetric preconditioning of a linear system

Definition

Invertible preconditioners give equivalent linear systems, with the transformed residuals and errors written explicitly

Statement

Facts & Assumptions

Proof

Symmetric positive-definite preconditioning preserves a Hermitian positive-definite CG problem, and the CG bound uses the transformed condition number

Statement

Facts & Assumptions

Proof

5 · Examples, counterexamples and false statements

Sources

The energy inner product $⟨ u, v ⟩_{A} = ⟨ A u, v ⟩$ and energy norm $∥ u ∥_{A}$ for a Hermitian positive-definite matrix

The quadratic energy $ϕ (x) = \frac{1}{2} ⟨ A x, x ⟩ - Re ⟨ b, x ⟩$ of a Hermitian positive-definite linear system

For Hermitian positive-definite $A$ , the exact solution of $A x = b$ is the unique minimizer of the quadratic energy

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

Before convergence, every CG denominator $p_{k}^{*} A p_{k}$ is positive

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

CG is the Krylov Galerkin method, and the $m$ th iterate uniquely minimizes the $A$ -norm of the error over $x_{0} + K_{m} (A, r_{0})$

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

CG obeys the Chebyshev $A$ -norm bound in terms of the spectral condition number $κ_{2} (A)$

In floating-point arithmetic, CG can lose exact residual orthogonality, $A$ -conjugacy, and the finite-termination guarantee

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

Stationary iteration from a matrix splitting $A = M - N$

A stationary splitting converges for every start if and only if its iteration matrix has spectral radius below $1$