Pipeline-generated

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.

✓ 2 results · all verified · 2 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; all 2 also cleared it.

Krylov methods and Lanczos convergence

1 · Prerequisites

2 · Summary

For a real symmetric matrix, the Lanczos estimate keeps the top-eigenspace projection of the starting vector and the gap separating the wanted eigenvalue from the unwanted spectrum. A local scaled Chebyshev filter supplies the polynomial bound. The page treats repeated top eigenvalues, an absent top component, a collapsed unwanted interval, a scalar matrix, and exact invariant subspace breakdown as separate branches. Every Lanczos convergence statement is in exact arithmetic.

The cost proposition counts canonical CSR matvecs, one- or two-pass modified Gram–Schmidt, incremental Givens updates, and Krylov storage; it excludes convergence, wall-clock, and memory-bandwidth conclusions. The finite-precision items use the declared real operationwise model: exact-zero products and partial sums round exactly to zero, and nonzero exact intermediate results must be normal-range. They give explicit local Arnoldi and residual-gap terms, plus an a posteriori basis-orthogonality recurrence. A zero normalization or failed range hypothesis is a separate breakdown or inconclusive branch. The CG item relates its recursive residual to the exact residual and the energy-norm error; it asserts neither exact-grade termination nor monotonicity of the true residual.

The page retains all planned interfaces to the conjugate-gradient/MINRES, eigenvalue-iteration, Krylov/GMRES, matrix-norm, spectral-theorem, finite- precision direct-factorization, sparse-kernel, and stationary-iteration pages. All required page files are now present; of the nine prerequisite pages, the finite-precision direct-factorization, sparse-kernel, and stationary-iteration pages remain drafts, and the other six are published. The batch dependency record distinguishes the item bodies actually used by these proofs from page-level context.

3 · Logical flowchart

4 · Definitions, theorems and proofs

LemmaStatement: Literature-sourcedProof: AI-adaptedjudge pass (gpt-6-luna)Open item page →

A scaled Chebyshev polynomial suppresses a separated interval

Statement

Let $a > b > c$ be real numbers, let $k \in N$ with $k \geq 0$ , and put

$ξ (x) : = \frac{2 x - b - c}{b - c}, ξ_{a} : = ξ (a) = 1 + \frac{2 (a - b)}{b - c} > 1.$

Define

$p_{k} (x) : = \frac{T_{k} (ξ (x))}{T_{k} (ξ_{a})},$

where $T_{k}$ is the $k$ th Chebyshev polynomial of the first kind from Chebyshev polynomials of the first and second kinds by their three-term recurrences. Then $p_{k}$ is a real polynomial of degree exactly $k$ , $p_{k} (a) = 1$ , and

$\max_{x \in [c, b]} ∣ p_{k} (x) ∣ = \frac{1}{T_{k} (ξ_{a})} .$

Facts & Assumptions

Given: Real numbers $a > b > c$ , an integer $k \geq 0$ , the affine map $ξ$ , the exterior point $ξ_{a}$ , and the polynomial $p_{k}$ in the Statement.

[F1]

Chebyshev polynomials of the first and second kinds by their three-term recurrences: $T_{0} = 1$ , $T_{1} = X$ , and $T_{j + 1} = 2 X T_{j} - T_{j - 1}$ for $j \geq 1$ .

[F2]

Formal real polynomials, evaluation, degree, leading coefficient, and monic polynomials: the degree and leading coefficient of a nonzero formal real polynomial are determined by its highest nonzero coefficient.

[F3]

Square roots exist: a unique $\sqrt{a} \geq 0$ with $(\sqrt{a})^{2} = a$ ; the positives are ${x^{2} : x \neq 0}$ : every nonnegative real has a nonnegative square root.

Proof

1.1givenF1F3inductionalgebra

Fix $t \in [- 1, 1]$ . Since $1 - t^{2} \geq 0$ , choose $s \geq 0$ with $s^{2} = 1 - t^{2}$ by [F3]. Define real sequences by $u_{0} = 1$ , $v_{0} = 0$ , and $u_{j + 1} = t u_{j} - s v_{j}, v_{j + 1} = s u_{j} + t v_{j} .$ Direct expansion gives $u_{j + 1}^{2} + v_{j + 1}^{2} = (t^{2} + s^{2}) (u_{j}^{2} + v_{j}^{2}) = u_{j}^{2} + v_{j}^{2}$ , so induction from $u_{0}^{2} + v_{0}^{2} = 1$ gives $∣ u_{j} ∣ \leq 1$ . Also $u_{j} = t u_{j + 1} + s v_{j + 1}$ , by substituting the recurrences and using $t^{2} + s^{2} = 1$ . Hence $u_{j + 2} + u_{j} = (t u_{j + 1} - s v_{j + 1}) + (t u_{j + 1} + s v_{j + 1}) = 2 t u_{j + 1}$ . Since $u_{0} = 1$ and $u_{1} = t$ , [F1] and induction give $u_{j} = T_{j} (t)$ . Thus $∣ T_{j} (t) ∣ \leq 1$ ; equality holds at $t = 1$ , where $s = 0$ and $u_{j} = 1$ for every $j$ .

1.2givenF1inductionalgebra

For $ξ_{a} > 1$ , recurrence [F1] gives $T_{0} (ξ_{a}) = 1$ and $T_{1} (ξ_{a}) = ξ_{a} > 1$ . If $T_{j} (ξ_{a}) > T_{j - 1} (ξ_{a}) > 0$ , then $T_{j + 1} (ξ_{a}) = 2 ξ_{a} T_{j} (ξ_{a}) - T_{j - 1} (ξ_{a}) > (2 ξ_{a} - 1) T_{j} (ξ_{a}) > T_{j} (ξ_{a}) .$ Induction proves $T_{k} (ξ_{a}) > 0$ , so the normalizing denominator is nonzero.

1.3F1F2inductionalgebra

The recurrence gives $T_{0} = 1$ of degree $0$ and $T_{1} = X$ of degree $1$ with leading coefficient $1$ . If $j \geq 1$ , $T_{j}$ has degree $j$ and leading coefficient $2^{j - 1}$ , and $T_{j - 1}$ has degree $j - 1$ (with $T_{0}$ having degree $0$ when $j = 1$ ), then $2 X T_{j}$ has degree $j + 1$ and leading coefficient $2^{j}$ , while subtracting $T_{j - 1}$ cannot change that highest-degree term. By [F1], induction gives $\deg T_{k} = k$ and leading coefficient $2^{k - 1}$ for every $k \geq 1$ .

2.1givenstep 1.1step 1.2step 1.3algebra∎

The affine map $ξ$ is increasing, has nonzero slope $2 / (b - c)$ , and sends $[c, b]$ onto $[- 1, 1]$ . For $k \geq 1$ , step 1.3 shows that $T_{k} (ξ (x))$ has degree $k$ ; step 1.2 shows division by $T_{k} (ξ_{a}) > 0$ preserves that degree. For $k = 0$ , $p_{0} = 1$ has degree $0$ . Step 1.1 bounds the numerator on $[c, b]$ by $1$ in absolute value and attains $1$ at $x = b$ , since $ξ (b) = 1$ . Since $ξ (a) = ξ_{a}$ , steps 1.2 and 1.3 give $p_{k} (a) = 1$ and prove the maximum formula.

TheoremStatement: Literature-sourcedProof: AI-adaptedjudge pass (gpt-6-luna)Open item page →

Two-pass MGS Arnoldi has an explicit local relation and an a posteriori orthogonality bound

Statement

Let $A \in R^{n \times n}$ , $n \geq 1$ , and let the computed starting vector $q_{1}$ be nonzero. Fix $m \geq 1$ and, for $j = 1, \dots, m$ , compute each component of $z_{j} = fl (A q_{j})$ by the length- $n$ rounded dot product of that row with $q_{j}$ . Then perform two complete modified Gram–Schmidt passes: for $p = 1, 2$ and $i = 1, \dots, j$ , compute $h_{i j}^{(p)} = fl (q_{i}^{T} w_{i - 1, j}^{(p)}), w_{i j}^{(p)} = fl (w_{i - 1, j}^{(p)} - h_{i j}^{(p)} q_{i}),$ where $w_{0 j}^{(1)} = z_{j}$ and $w_{0 j}^{(2)} = w_{j j}^{(1)}$ . The vector update is componentwise one rounded product followed by one rounded subtraction. Store $h_{i j} = fl (h_{i j}^{(1)} + h_{i j}^{(2)})$ . Compute $t_{j} = fl ((w_{j j}^{(2)})^{T} w_{j j}^{(2)})$ as a length- $n$ dot product, $β_{j + 1} = fl (\sqrt{t_{j}})$ , and $q_{j + 1} = fl (w_{j j}^{(2)} / β_{j + 1})$ componentwise.

Assume all products, partial sums, square roots, divisions, and updates used here succeed in the operationwise model, so every nonzero exact product and partial sum is normal-range; exact-zero products and sums are permitted. Assume $n u < 1$ , $γ_{n} < 1$ , $2 u < 1$ , and $t_{j} > 0$ . Define $c_{n} = (1 - u) \sqrt{1 - γ_{n}}$ . Then $β_{j + 1} \geq c_{n} ∥ w_{j j}^{(2)} ∥_{2} > 0$ , and the computed columns satisfy $A q_{j} = \sum_{i = 1}^{j} h_{i j} q_{i} + β_{j + 1} q_{j + 1} + e_{j},$ where, writing $δ_{j}^{m v} = z_{j} - A q_{j}$ , $e_{j} = - δ_{j}^{n o r m} - δ_{j}^{m v} - \sum_{p = 1}^{2} \sum_{i = 1}^{j} ζ_{i j}^{(p)} - \sum_{i = 1}^{j} χ_{i j} q_{i},$ with $δ_{j}^{n o r m} = β_{j + 1} q_{j + 1} - w_{j j}^{(2)}$ , $ζ_{i j}^{(p)} = w_{i j}^{(p)} - (w_{i - 1, j}^{(p)} - h_{i j}^{(p)} q_{i})$ , and $χ_{i j} = h_{i j} - (h_{i j}^{(1)} + h_{i j}^{(2)})$ . These errors obey $∥ δ_{j}^{m v} ∥_{2} \leq γ_{n} {(\sum_{a = 1}^{n} {(\sum_{b = 1}^{n} ∣ A_{a b} ∣ ∣ q_{j, b} ∣)}^{2})}^{1 / 2}, ∥ δ_{j}^{n o r m} ∥_{2} \leq u ∥ w_{j j}^{(2)} ∥_{2},$ $∣ h_{i j}^{(p)} - q_{i}^{T} w_{i - 1, j}^{(p)} ∣ \leq γ_{n} ∥ q_{i} ∥_{1} ∥ w_{i - 1, j}^{(p)} ∥_{1},$ $∥ ζ_{i j}^{(p)} ∥_{2} \leq γ_{2} (∥ w_{i - 1, j}^{(p)} ∥_{2} + ∣ h_{i j}^{(p)} ∣ ∥ q_{i} ∥_{2}), ∣ χ_{i j} ∣ \leq u ∣ h_{i j}^{(1)} + h_{i j}^{(2)} ∣ .$

If the generated vectors $q_{1}, \dots, q_{m + 1}$ have full column rank, there is also an explicit conditioning-dependent orthogonality recurrence. Put $ν_{ℓ} = ∣ ∥ q_{ℓ} ∥_{2}^{2} - 1 ∣$ and $c_{ℓ i} = q_{ℓ}^{T} q_{i}$ . For fixed $j$ and $ℓ \leq j$ , set $G_{ℓ j}^{0} = ∣ q_{ℓ}^{T} z_{j} ∣ .$ For each pass $p$ , with $h_{i} = h_{i j}^{(p)}$ and $ζ_{i} = ζ_{i j}^{(p)}$ , define $\begin{aligned} G_{ℓ j}^{p} : = & ν_{ℓ} (G_{ℓ j}^{p - 1} + \sum_{i < ℓ} (∣ h_{i} ∣ ∣ c_{ℓ i} ∣ + ∥ q_{ℓ} ∥_{2} ∥ ζ_{i} ∥_{2})) + (1 + ν_{ℓ}) γ_{n} ∥ q_{ℓ} ∥_{1} ∥ w_{ℓ - 1, j}^{(p)} ∥_{1} \\ + ∥ q_{ℓ} ∥_{2} ∥ ζ_{ℓ} ∥_{2} + \sum_{i > ℓ} (∣ h_{i} ∣ ∣ c_{ℓ i} ∣ + ∥ q_{ℓ} ∥_{2} ∥ ζ_{i} ∥_{2}) . \end{aligned}$ Then the off-diagonal inner products satisfy $∣ q_{ℓ}^{T} q_{j + 1} ∣ \leq \frac{G_{ℓ j}^{2}}{β_{j + 1}} + \frac{u ∥ q_{ℓ} ∥_{2}}{c_{n}} .$ Consequently the Frobenius norm of the Gram defect of $Q_{m + 1}$ is at most ${(\sum_{i = 1}^{m + 1} ν_{i}^{2} + 2 \sum_{1 \leq ℓ < i \leq m + 1} {(\frac{G_{ℓ, i - 1}^{2}}{β_{i}} + \frac{u ∥ q_{ℓ} ∥_{2}}{c_{n}})}^{2})}^{1 / 2},$ where $∥ B ∥_{F} = (\sum_{a, b} ∣ B_{a b} ∣^{2})^{1 / 2}$ . A zero $t_{j}$ is a breakdown branch with no division or new vector; failure of any stated rounding or positivity hypothesis makes the bound inconclusive.

Facts & Assumptions

Given: The real matrix, operationwise model and hypotheses in the Statement, the initial vector $q_{1}$ , and the specified two-pass MGS algorithm.

[F1]

The Arnoldi process for building an orthonormal basis of a Krylov subspace: exact Arnoldi subtracts projections onto existing vectors and normalizes the residual; exact zero residual is breakdown.

[F2]

Operationwise real and complex floating point arithmetic with rounded square roots and fused multiply-add: real arithmetic operations round with relative error at most $u$ when they succeed, exact-zero operations return zero, and positive square roots are correctly rounded; for $k u < 1$ , $γ_{k} = k u / (1 - k u)$ .

[F3]

The computed floating-point dot product obeys componentwise and normwise error bounds: when every exact product, rounded product, and intermediate sum is nonzero normal-range, a length- $n$ dot product differs from its exact dot by at most $γ_{n}$ times the sum of the absolute products.

[F4]

Cauchy-Schwarz $∣ ⟨ x, y ⟩ ∣ \leq ∥ x ∥_{2} ∥ y ∥_{2}$ with its equality case, the triangle inequality for $∥ \cdot ∥_{2}$ , the parallelogram law and polarisation: for real vectors, $∣ x^{T} y ∣ \leq ∥ x ∥_{2} ∥ y ∥_{2}$ .

[F5]

If |delta_i| <= u and n u < 1, then prod (1+delta_i) = 1 + theta_n with |theta_n| <= gamma_n: padding any product of at most $n$ factors $1 + ε$ , $∣ ε ∣ \leq u$ , with factors $1$ allows the published $n$ -factor bound $γ_{n}$ when $n u < 1$ .

Proof

1.1givenF2F3F5algebra

Consider any length- $n$ dot product used here. Each exact product and partial sum is either zero or normal-range. By [F2], an exact-zero operation returns zero and contributes a factor $1 + 0$ , while every nonzero successful operation contributes a factor $1 + ε$ with $∣ ε ∣ \leq u$ . Unrolling the left-to-right sum, each exact product has a coefficient that is a product of at most $n$ such factors; padding with factors $1$ and applying [F5] bounds each coefficient's deviation from $1$ by $γ_{n}$ . Therefore the absolute dot-product error is at most $γ_{n}$ times the sum of the absolute exact products, including when exact-zero products or sums occur. This extends the narrower supplier bound [F3] to the operationwise model's exact-zero cases.

1.2givenF2F5algebra

For one component of an update, write the rounded product as $h q_{i} (1 + ϵ_{1})$ and the rounded subtraction as $(w - h q_{i} (1 + ϵ_{1})) (1 + ϵ_{2})$ , with $∣ ϵ_{1} ∣, ∣ ϵ_{2} ∣ \leq u$ ; an exact-zero operation has its corresponding $ϵ$ equal to zero by [F2]. Subtracting $w - h q_{i}$ and using the triangle inequality bounds the component error by $γ_{2} (∣ w ∣ + ∣ h q_{i} ∣)$ . Taking vector norms gives the stated $ζ$ estimate. The rounded addition combining two pass coefficients has error at most $u ∣ h^{(1)} + h^{(2)} ∣$ , including exact-zero sums, which is the stated $χ$ bound.

2.1givenstep 1.1algebra

Apply step 1.1 to each row dot product defining $z_{j}$ . The absolute error in row $a$ is at most $γ_{n} \sum_{b} ∣ A_{a b} ∣ ∣ q_{j, b} ∣$ . Taking the Euclidean norm of this vector of rowwise bounds proves the displayed $δ_{j}^{m v}$ estimate.

2.2givenF2step 1.1algebra

By step 1.1, $∣ t_{j} - ∥ w_{j j}^{(2)} ∥_{2}^{2} ∣ \leq γ_{n} ∥ w_{j j}^{(2)} ∥_{2}^{2}$ , so $t_{j} \geq (1 - γ_{n}) ∥ w_{j j}^{(2)} ∥_{2}^{2}$ . Correct rounding of the positive square root gives $β_{j + 1} \geq (1 - u) \sqrt{t_{j}}$ , proving the lower bound. Each component division gives $q_{j + 1, a} = (w_{j j, a}^{(2)} / β_{j + 1}) (1 + ϵ_{a})$ with $∣ ϵ_{a} ∣ \leq u$ , including zero components with $ϵ_{a} = 0$ ; hence $∣ δ_{j, a}^{n o r m} ∣ \leq u ∣ w_{j j, a}^{(2)} ∣$ and the displayed vector bound follows.

3.1givenF1step 2.1step 1.2step 2.2algebra

The two-pass updates telescope to $w_{j j}^{(2)} = z_{j} - \sum_{p = 1}^{2} \sum_{i = 1}^{j} h_{i j}^{(p)} q_{i} + \sum_{p = 1}^{2} \sum_{i = 1}^{j} ζ_{i j}^{(p)} .$ Also $h_{i j} = h_{i j}^{(1)} + h_{i j}^{(2)} + χ_{i j}$ , $w_{j j}^{(2)} = β_{j + 1} q_{j + 1} - δ_{j}^{n o r m}$ , and $z_{j} = A q_{j} + δ_{j}^{m v}$ . Substituting these identities into the telescoped equation yields $A q_{j} = \sum_{i} h_{i j} q_{i} + β_{j + 1} q_{j + 1} - δ_{j}^{n o r m} - δ_{j}^{m v} - \sum_{p, i} ζ_{i j}^{(p)} - \sum_{i} χ_{i j} q_{i} .$ This is the stated local Arnoldi relation, whose exact-arithmetic column shape is the one defined in [F1].

4.1givenstep 1.1step 1.2step 3.1algebrainduction

Fix $ℓ \leq j$ and one pass. Before its $i = ℓ$ update, the absolute value of $q_{ℓ}^{T} w_{ℓ - 1, j}^{(p)}$ is at most $G_{ℓ j}^{p - 1} + \sum_{i < ℓ} (∣ h_{i} ∣ ∣ c_{ℓ i} ∣ + ∥ q_{ℓ} ∥_{2} ∥ ζ_{i} ∥_{2})$ by the updates already made in this pass. At $i = ℓ$ , write the computed dot as that exact inner product plus a dot error $δ h$ ; then the new inner product is $(1 - ∥ q_{ℓ} ∥_{2}^{2}) q_{ℓ}^{T} w_{ℓ - 1, j}^{(p)} - ∥ q_{ℓ} ∥_{2}^{2} δ h + q_{ℓ}^{T} ζ_{ℓ}$ . Its absolute value is bounded by the first three terms in the definition of $G_{ℓ j}^{p}$ . Each later update $i > ℓ$ changes that inner product by $- h_{i} c_{ℓ i} + q_{ℓ}^{T} ζ_{i}$ , bounded by the corresponding summand there. Thus $∣ q_{ℓ}^{T} w_{j j}^{(p)} ∣ \leq G_{ℓ j}^{p}$ for both passes.

5.1givenstep 2.2step 4.1F4algebra∎

Step 4.1 with $p = 2$ gives $∣ q_{ℓ}^{T} w_{j j}^{(2)} ∣ \leq G_{ℓ j}^{2}$ . Since $β_{j + 1} q_{j + 1} = w_{j j}^{(2)} + δ_{j}^{n o r m}$ , [F4] and step 2.2 yield $∣ q_{ℓ}^{T} q_{j + 1} ∣ \leq G_{ℓ j}^{2} / β_{j + 1} + u ∥ q_{ℓ} ∥_{2} ∥ w_{j j}^{(2)} ∥_{2} / β_{j + 1} \leq G_{ℓ j}^{2} / β_{j + 1} + u ∥ q_{ℓ} ∥_{2} / c_{n} .$ Each diagonal entry of $Q_{m + 1}^{T} Q_{m + 1} - I$ has absolute value $ν_{i}$ , and each off-diagonal entry is bounded by the preceding inequality. Summing the squares of all entries proves the Frobenius Gram-defect bound.

TheoremStatement: Literature-sourcedProof: AI-adaptedjudge pass (gpt-6-luna)Open item page →

Finite-precision CG has a recursive-residual gap and an attainable-accuracy bound

Statement

Let $A \in R^{n \times n}$ , $n \geq 1$ , be symmetric positive definite, let $A x_{*} = b$ , and suppose the computed CG process from The conjugate-gradient recurrence completes steps $k = 0, \dots, j - 1$ in the no-range-failure model of Operationwise real and complex floating point arithmetic with rounded square roots and fused multiply-add. Assume $n u < 1$ and $2 u < 1$ , and that every nonzero exact product and partial sum in each length- $n$ matrix-vector dot product is normal-range; exact-zero products and sums are permitted. Write the actual stored scalars and vectors as $α_{k}, {\hat{x}}_{k}, {\hat{r}}_{k}, {\hat{p}}_{k}$ , and compute each component of ${\hat{q}}_{k} = fl (A {\hat{p}}_{k})$ by a rounded length- $n$ dot product. Set $δ_{k}^{A} : = {\hat{q}}_{k} - A {\hat{p}}_{k}$ . Compute the updates componentwise as ${\hat{x}}_{k + 1} = fl ({\hat{x}}_{k} + fl (α_{k} {\hat{p}}_{k})), {\hat{r}}_{k + 1} = fl ({\hat{r}}_{k} - fl (α_{k} {\hat{q}}_{k})),$ where the inner products and outer additions/subtractions are rounded operations and $α_{k}$ is the actual stored scalar used by the algorithm. Define the resulting update errors by $δ_{k}^{x} : = {\hat{x}}_{k + 1} - ({\hat{x}}_{k} + α_{k} {\hat{p}}_{k}), δ_{k}^{r} : = {\hat{r}}_{k + 1} - ({\hat{r}}_{k} - α_{k} {\hat{q}}_{k}) .$ For any index $j$ reached by the process, define $g_{j} : = {\hat{r}}_{j} - (b - A {\hat{x}}_{j}), Γ_{j} : = ∥ g_{0} ∥_{2} + \sum_{k < j} (∥ δ_{k}^{r} ∥_{2} + ∥ A ∥_{2} ∥ δ_{k}^{x} ∥_{2} + ∣ α_{k} ∣ ∥ δ_{k}^{A} ∥_{2}) .$ Here $∥ A ∥_{2}$ is the induced Euclidean operator norm. Then $∥ g_{j} ∥_{2} \leq Γ_{j}, ∥ b - A {\hat{x}}_{j} ∥_{2} \leq ∥ {\hat{r}}_{j} ∥_{2} + Γ_{j} .$ If $λ_{\min} > 0$ is the smallest eigenvalue of $A$ , then $∥ x_{*} - {\hat{x}}_{j} ∥_{A} \leq \frac{∥ b - A {\hat{x}}_{j} ∥_{2}}{\sqrt{λ_{\min}}} \leq \frac{∥ {\hat{r}}_{j} ∥_{2} + Γ_{j}}{\sqrt{λ_{\min}}},$ where $∥ e ∥_{A} = \sqrt{e^{T} A e}$ . The explicit operation errors obey $∥ δ_{k}^{A} ∥_{2} \leq γ_{n} {(\sum_{i = 1}^{n} {(\sum_{ℓ = 1}^{n} ∣ A_{i ℓ} ∣ ∣ {\hat{p}}_{k, ℓ} ∣)}^{2})}^{1 / 2},$ and, when $2 u < 1$ , $∥ δ_{k}^{x} ∥_{2} \leq γ_{2} (∥ {\hat{x}}_{k} ∥_{2} + ∣ α_{k} ∣ ∥ {\hat{p}}_{k} ∥_{2}), ∥ δ_{k}^{r} ∥_{2} \leq γ_{2} (∥ {\hat{r}}_{k} ∥_{2} + ∣ α_{k} ∣ ∥ {\hat{q}}_{k} ∥_{2}) .$ No exact-grade termination or monotonicity of the true residual is asserted.

Facts & Assumptions

Given: The real SPD system, a sequence of finite computed CG steps, the actual update errors in the Statement, and the definitions of $Γ_{j}$ and the energy norm.

[F1]

Operationwise real and complex floating point arithmetic with rounded square roots and fused multiply-add: each real addition and multiplication is rounded with relative error at most $u$ on a successful normal-range operation, exact-zero operations return zero, and for $k u < 1$ , $γ_{k} = k u / (1 - k u)$ .

[F2]

The computed floating-point dot product obeys componentwise and normwise error bounds: when every exact product, rounded product, and intermediate sum is nonzero normal-range, a length- $n$ dot product has absolute error at most $γ_{n} \sum_{ℓ} ∣ x_{ℓ} y_{ℓ} ∣$ .

[F3]

The conjugate-gradient recurrence: CG updates $x$ by adding $α p$ and updates the recursive residual by subtracting $α A p$ .

[F4]

The energy inner product $⟨ u, v ⟩_{A} = ⟨ A u, v ⟩$ and energy norm $∥ u ∥_{A}$ for a Hermitian positive-definite matrix: for real SPD $A$ , $∥ e ∥_{A}^{2} = e^{T} A e$ .

[F5]

Real spectral theorem: a self-adjoint endomorphism of a finite-dimensional real inner product space has an orthonormal eigenbasis: the real symmetric $A$ has an orthonormal eigenbasis; its eigenvalues are positive by positive definiteness.

[F6]

The matrix norm induced by a published vector p-norm: at $p = 2$ , $∥ A ∥_{2}$ is the supremum of $∥ A v ∥_{2}$ over $∥ v ∥_{2} \leq 1$ , hence $∥ A v ∥_{2} \leq ∥ A ∥_{2} ∥ v ∥_{2}$ .

[F7]

If |delta_i| <= u and n u < 1, then prod (1+delta_i) = 1 + theta_n with |theta_n| <= gamma_n: padding a product of at most $n$ relative-error factors with factors $1$ gives deviation at most $γ_{n}$ when $n u < 1$ .

Proof

1.1givenF3algebra

The update equations in the Statement give $\begin{aligned} g_{k + 1} & = {\hat{r}}_{k} - α_{k} (A {\hat{p}}_{k} + δ_{k}^{A}) + δ_{k}^{r} - (b - A ({\hat{x}}_{k} + α_{k} {\hat{p}}_{k} + δ_{k}^{x})) \\ = g_{k} + δ_{k}^{r} - α_{k} δ_{k}^{A} + A δ_{k}^{x} . \end{aligned}$ The $α_{k} A {\hat{p}}_{k}$ terms cancel exactly.

1.2givenF1F2F7algebra

In a row dot product, each exact product and each partial sum is either zero or normal-range by the Statement. At an exact zero, [F1] gives $fl (0) = 0$ , so its relative-error factor is $1$ ; every nonzero operation has a factor $1 + ε$ with $∣ ε ∣ \leq u$ . Unrolling the left-to-right sum gives at most $n$ such factors in the coefficient of each exact product, so [F7] gives an error at most $γ_{n} \sum_{ℓ} ∣ A_{i ℓ} {\hat{p}}_{k, ℓ} ∣$ , the same bound as the narrower dot-product estimate [F2]. Squaring these $n$ rowwise bounds and summing gives the displayed $∥ δ_{k}^{A} ∥_{2}$ bound. For either vector update, each component consists of one rounded product and one rounded addition or subtraction; an exact-zero operation again contributes factor $1$ . Unrolling those two relative errors and applying [F7] with two factors gives the component bound $γ_{2} (∣ v_{i} ∣ + ∣ α ∣ ∣ p_{i} ∣)$ , where $(v, p)$ is $({\hat{x}}_{k}, {\hat{p}}_{k})$ or $({\hat{r}}_{k}, {\hat{q}}_{k})$ . Taking the Euclidean norm and applying the triangle inequality gives the two displayed $γ_{2}$ bounds.

2.1givenstep 1.1F6induction

Taking Euclidean norms in step 1.1 and using [F6] yields $∥ g_{k + 1} ∥_{2} \leq ∥ g_{k} ∥_{2} + ∥ δ_{k}^{r} ∥_{2} + ∣ α_{k} ∣ ∥ δ_{k}^{A} ∥_{2} + ∥ A ∥_{2} ∥ δ_{k}^{x} ∥_{2} .$ Induction from $k = 0$ proves $∥ g_{j} ∥_{2} \leq Γ_{j}$ . Since ${\hat{r}}_{j} = (b - A {\hat{x}}_{j}) + g_{j}$ , the triangle inequality gives the recursive residual bound.

3.1givenF4F5step 2.1algebra∎

Let $e = x_{*} - {\hat{x}}_{j}$ . Then $A e = b - A {\hat{x}}_{j}$ . In the orthonormal eigenbasis of [F5], $∥ e ∥_{A}^{2} = e^{T} A e = \sum_{i} λ_{i} e_{i}^{2} \leq λ_{\min}^{} \sum_{i} λ_{i}^{2} e_{i}^{2} = λ_{\min}^{} ∥ A e ∥_{2}^{2} .$ Thus $∥ e ∥_{A} \leq ∥ b - A {\hat{x}}_{j} ∥_{2} / \sqrt{λ_{\min}}$ ; step 2.1 then proves the claimed bound.

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-6-luna)Open item page →

Lanczos largest Ritz values obey a Chebyshev start-angle bound, including degenerate branches

Statement

Let $A \in R^{n \times n}$ , $n \geq 1$ , be symmetric with ordered eigenvalues $λ_{1} \geq \dots \geq λ_{n}$ . Let $r$ be the multiplicity of $λ_{1}$ . If $r < n$ , assume $λ_{1} > λ_{r + 1}$ , and let $P$ be the orthogonal projection onto the $λ_{1}$ -eigenspace. Let $b \in R^{n}$ be a unit vector and, for $m \geq 1$ , define

$K_{m} : = span {b, A b, \dots, A^{m - 1} b}, θ_{m} : = \max_{0 \neq x \in K_{m}} \frac{x^{T} A x}{x^{T} x} .$

Thus $θ_{m}$ is the largest Rayleigh–Ritz value on $K_{m}$ ; if Lanczos runs through step $m$ without breakdown, it is the largest Ritz value of $Q_{m}^{T} A Q_{m}$ . If $r = n$ , then $A = λ_{1} I$ and $θ_{m} = λ_{1}$ for every $m \geq 1$ . Suppose $r < n$ .

If $P b = 0$ , then $θ_{m} \leq λ_{r + 1}$ for every $m$ ; no convergence to $λ_{1}$ is asserted.
If $P b \neq 0$ , put $τ : = \frac{∥ (I - P) b ∥_{2}}{∥ P b ∥_{2}} .$ If $λ_{r + 1} > λ_{n}$ , then for every $m \geq 1$ , $0 \leq λ_{1} - θ_{m} \leq \frac{(λ_{1} - λ_{n}) τ^{2}}{T_{m - 1} ⁣ {(1 + 2 \frac{λ_{1} - λ_{r + 1}}{λ_{r + 1} - λ_{n}})}^{2}} .$ For a simple top eigenvalue ( $r = 1$ ), $τ$ is the tangent of the angle between $b$ and a unit top eigenvector, so the starting-angle denominator is explicit.
If $P b \neq 0$ and $λ_{r + 1} = λ_{n}$ , then $λ_{1} - θ_{1} = (λ_{1} - λ_{n}) \frac{∥ (I - P) b ∥_{2}^{2}}{∥ b ∥_{2}^{2}}, θ_{m} = λ_{1} (m \geq 2) .$

When $r < n$ , $P b \neq 0$ , and exact Lanczos breakdown occurs at dimension $d$ , then $θ_{d} = λ_{1}$ and $K_{m} = K_{d}$ for all $m \geq d$ . These are exact-arithmetic claims; they give no finite-precision grade-termination guarantee.

Facts & Assumptions

Given: A real symmetric $A \in R^{n \times n}$ , its ordered eigenvalues, the top-eigenspace projection $P$ when $r < n$ , a unit start vector $b$ , the Krylov spaces $K_{m}$ , and the largest Rayleigh–Ritz values $θ_{m}$ defined in the Statement.

[F1]

The Lanczos process as Arnoldi specialized to a Hermitian matrix, with the usual real-subdiagonal phase convention: exact Lanczos is Arnoldi applied to a symmetric matrix, with real nonnegative subdiagonal coefficients before breakdown.

[F2]

Before breakdown, Arnoldi produces an orthonormal Krylov basis and a rectangular upper-Hessenberg factorization: before breakdown, the Arnoldi vectors form an orthonormal basis of $K_{m}$ and satisfy $A Q_{m} = Q_{m + 1} {\overset{ˉ}{H}}_{m}$ .

[F3]

Ritz values and Ritz vectors extracted from the Arnoldi Hessenberg reduction and An Arnoldi Ritz pair has residual norm controlled by the last Hessenberg subdiagonal entry: eigenvalues of $H_{m} = Q_{m}^{T} A Q_{m}$ are Ritz values with vectors $u = Q_{m} y$ ; if Arnoldi runs through step $m$ without breakdown and $H_{m} y = θ y$ , then $A u - θ u = h_{m + 1, m} (e_{m}^{T} y) v_{m + 1}$ .

[F4]

Courant-Fischer min-max principle for self-adjoint endomorphisms on finite-dimensional real inner product spaces and Real spectral theorem: a self-adjoint endomorphism of a finite-dimensional real inner product space has an orthonormal eigenbasis: every real symmetric compression has a largest Rayleigh–Ritz value equal to its largest eigenvalue, and $A$ has an orthonormal eigenbasis.

[F5]

A scaled Chebyshev polynomial suppresses a separated interval: for $a > b > c$ , the degree- $k$ scaled filter has value $1$ at $a$ and absolute value at most $1 / T_{k} (1 + 2 (a - b) / (b - c))$ on $[c, b]$ .

[F6]

The Arnoldi process for building an orthonormal basis of a Krylov subspace: each exact Arnoldi column has $A v_{j} = \sum_{i = 1}^{j} h_{i j} v_{i} + w_{j}$ ; exact breakdown at column $d$ means $w_{d} = 0$ .

[F7]

The Krylov subspace $K_{m} (A, b) = span {b, A b, \dots, A^{m - 1} b}$ : $K_{m} (A, b) = span {b, A b, \dots, A^{m - 1} b}$ .

Proof

1.1givenF1F2F3F4F7

If exact Lanczos runs through step $m$ without breakdown, [F1], [F2], and [F7] give an orthonormal basis $Q_{m}$ of $K_{m}$ and a symmetric compression $H_{m} = Q_{m}^{T} A Q_{m}$ . By [F3], each eigenpair of $H_{m}$ lifts to an exact Ritz pair of $A$ ; by [F4], the largest eigenvalue of $H_{m}$ is the maximum Rayleigh quotient on $K_{m}$ , namely $θ_{m}$ . If Lanczos breaks down earlier, no step- $m$ basis or Ritz assertion is used; $θ_{m}$ remains defined directly by the Rayleigh–Ritz formula in the Statement.

1.2givenF4F7algebra

Assume $r < n$ . By [F4], choose an orthonormal eigenbasis of $A$ whose first $r$ vectors span the range of $P$ . If $P b = 0$ , then $b$ is orthogonal to that eigenspace. For every integer $j \geq 0$ and every top eigenvector $u$ , symmetry gives $u^{T} A^{j} b = (A^{j} u)^{T} b = λ_{1}^{j} u^{T} b = 0$ . Thus every vector in $K_{m}$ lies in the orthogonal complement of the top eigenspace, where all Rayleigh quotients are at most $λ_{r + 1}$ ; this proves branch 1.

1.3givenF4algebra

If $r = n$ , every eigenvalue is $λ_{1}$ , so [F4] gives $A = λ_{1} I$ . Every nonzero $x \in K_{m}$ then has Rayleigh quotient $λ_{1}$ , proving the stated dimension-one/full-multiplicity branch.

1.4givenF4F5F7algebra

Assume $P b \neq 0$ and $λ_{r + 1} > λ_{n}$ . Apply [F5] with $a = λ_{1}$ , $b = λ_{r + 1}$ , $c = λ_{n}$ , and $k = m - 1$ to obtain a polynomial $p_{m - 1}$ of degree at most $m - 1$ with $p_{m - 1} (λ_{1}) = 1$ and $∣ p_{m - 1} (t) ∣ \leq δ_{m}$ on $[λ_{n}, λ_{r + 1}]$ , where $δ_{m} : = 1 / T_{m - 1} (1 + 2 (λ_{1} - λ_{r + 1}) / (λ_{r + 1} - λ_{n}))$ . By [F7], $x : = p_{m - 1} (A) b$ belongs to $K_{m}$ , and spectral decomposition gives $P x = P b$ and $∥ (I - P) x ∥_{2} \leq δ_{m} ∥ (I - P) b ∥_{2}$ .

1.5givenF4F7algebra

Assume $P b \neq 0$ and $λ_{r + 1} = λ_{n}$ . The spectral decomposition gives $A = λ_{n} I + (λ_{1} - λ_{n}) P$ . Hence $A b = λ_{n} b + (λ_{1} - λ_{n}) P b$ , so [F7] gives $P b \in K_{2}$ and it has Rayleigh quotient $λ_{1}$ ; this proves $θ_{m} = λ_{1}$ for $m \geq 2$ . For $m = 1$ , [F7] gives $K_{1} = span {b}$ , and the same decomposition gives the displayed exact formula for $λ_{1} - θ_{1}$ .

1.6givenF1F6F7inductionalgebra

Finally, assume $r < n$ , $P b \neq 0$ , and exact Lanczos breaks down at column $d$ . For $d > 1$ , no breakdown occurs at columns $j < d$ . Starting from $q_{1} = b / ∥ b ∥_{2}$ , inductively suppose $q_{1}, \dots, q_{j}$ form an orthonormal basis of $K_{j}$ . By the exact Arnoldi definition [F1, F6], the residual $w_{j} = A q_{j} - \sum_{i = 1}^{j} h_{i j} q_{i}$ lies in $K_{j + 1}$ , is orthogonal to $K_{j}$ , and is nonzero for $j < d$ ; hence its normalized vector $q_{j + 1}$ lies in $K_{j + 1} ∖ K_{j}$ . Since $K_{j + 1}$ is generated by $j + 1$ vectors, $q_{1}, \dots, q_{j + 1}$ form a basis of $K_{j + 1}$ . Thus $q_{1}, \dots, q_{d}$ form a basis of $K_{d}$ . For $d = 1$ , $q_{1}$ directly spans $K_{1}$ . Each $A q_{j} \in K_{d}$ for $j < d$ , and $A q_{d} \in K_{d}$ because its orthogonalized residual $w_{d}$ is zero. Hence $A K_{d} \subseteq K_{d}$ , and [F7] plus induction gives $K_{m} = K_{d}$ for $m \geq d$ .

2.1givenF4step 1.4algebra

In the eigenbasis of [F4], write $x = P x + (I - P) x$ . The two components are orthogonal, $A (P x) = λ_{1} P x$ , and all eigenvalues on the second component lie in $[λ_{n}, λ_{r + 1}]$ . Therefore $λ_{1} - \frac{x^{T} A x}{x^{T} x} = \frac{\sum_{j > r} (λ_{1} - λ_{j}) x_{j}^{2}}{∥ P x ∥_{2}^{2} + ∥ (I - P) x ∥_{2}^{2}} \leq (λ_{1} - λ_{n}) \frac{∥ (I - P) x ∥_{2}^{2}}{∥ P b ∥_{2}^{2}} \leq (λ_{1} - λ_{n}) δ_{m}^{2} τ^{2} .$ Since $θ_{m}$ is the maximum Rayleigh quotient on $K_{m}$ , it is at least the quotient of this nonzero $x$ and at most $λ_{1}$ . This proves branch 2, including $m = 1$ because $T_{0} = 1$ .

3.1givenF4step 1.6algebrainduction∎

Let $μ_{1} = λ_{1}, μ_{2}, \dots, μ_{s}$ be the distinct eigenvalues of $A$ . Since $r < n$ , $s \geq 2$ and the denominators below are nonzero. Define $p (t) : = \prod_{i = 2}^{s} \frac{t - μ_{i}}{λ_{1} - μ_{i}} .$ Then $p (λ_{1}) = 1$ and $p (μ_{i}) = 0$ for $i \geq 2$ . On the orthonormal eigenbasis from [F4], $p (A)$ therefore acts as the identity on the $λ_{1}$ -eigenspace and as zero on every other eigenspace, so $p (A) = P$ . Since $A K_{d} \subseteq K_{d}$ and $b \in K_{d}$ , every power of $A$ applied to $b$ lies in $K_{d}$ , whence $P b = p (A) b \in K_{d}$ . The nonzero vector $P b$ has Rayleigh quotient $λ_{1}$ , while no quotient can exceed $λ_{1}$ ; thus $θ_{d} = λ_{1}$ and the exact-breakdown branch follows.

TheoremStatement: Literature-sourcedProof: AI-adaptedjudge pass (gpt-6-luna)Open item page →

A computed GMRES correction has an explicit finite-precision residual gap

Statement

Let $A \in R^{n \times n}$ with $n \geq 1$ , let $r_{0} = b - A x_{0}$ , and let $m \geq 1$ . Put $Q_{m} = [q_{1} \dots q_{m}]$ , $Q_{m + 1} = [q_{1} \dots q_{m + 1}]$ , and ${\overset{ˉ}{H}}_{m} \in R^{(m + 1) \times m}$ . Suppose computed Arnoldi vectors satisfy $A Q_{m} = Q_{m + 1} {\overset{ˉ}{H}}_{m} + E_{m},$ where the columns of $E_{m}$ are the local error vectors of Two-pass MGS Arnoldi has an explicit local relation and an a posteriori orthogonality bound. Let $I$ be the $(m + 1)$ -by- $(m + 1)$ identity and $\overset{ˉ}{G} = Q_{m + 1}^{T} Q_{m + 1} - I$ and $η = ∥ \overset{ˉ}{G} ∥_{F}$ , where $∥ B ∥_{F} = (\sum_{a, b} ∣ B_{a b} ∣^{2})^{1 / 2}$ . Suppose $r_{0} = β_{1} q_{1} + δ_{0}, \hat{x} = x_{0} + Q_{m} y + δ_{x},$ where $y \in R^{m}$ is the coefficient vector returned by the computed GMRES least-squares stage and $δ_{x}$ is the update error (zero for an exact vector update). Define $e_{1} = (1, 0, \dots, 0)^{T} \in R^{m + 1}$ and the Arnoldi-coordinate least-squares residual $g : = β_{1} e_{1} - {\overset{ˉ}{H}}_{m} y,$ using the stored computed values, and let $r = b - A \hat{x}$ be the exact true residual. Then $∥ r - Q_{m + 1} g ∥_{2} \leq ∥ δ_{0} ∥_{2} + ∥ E_{m} ∥_{2} ∥ y ∥_{2} + ∥ A ∥_{2} ∥ δ_{x} ∥_{2},$ and $∥ r ∥_{2} \leq \sqrt{1 + η} ∥ g ∥_{2} + ∥ δ_{0} ∥_{2} + ∥ E_{m} ∥_{2} ∥ y ∥_{2} + ∥ A ∥_{2} ∥ δ_{x} ∥_{2} .$ Matrix $2$ -norms are induced by Euclidean vector norms. For the recomputation conclusion, assume the real operationwise model of Operationwise real and complex floating point arithmetic with rounded square roots and fused multiply-add with unit roundoff $u$ , $n u < 1$ , and successful row-dot and subtraction operations; every nonzero exact product and partial sum in a row dot is normal-range, and exact-zero products, sums, or subtractions are permitted. If the true residual is recomputed by these rounded row dot products and rounded subtraction, write $\hat{A x}$ for the computed product and $\hat{r} = fl (b - \hat{A x})$ . Then $∣ ∥ \hat{r} ∥_{2} - ∥ r ∥_{2} ∣ \leq ρ_{r e c}, ρ_{r e c} : = {(\sum_{i = 1}^{n} d_{i}^{2})}^{1 / 2},$ where $d_{i} : = γ_{n} \sum_{j = 1}^{n} ∣ A_{i j} ∣ ∣ {\hat{x}}_{j} ∣ + u ∣ b_{i} - {\hat{A x}}_{i} ∣ .$ No accuracy claim is made for the least-squares solve: its computed $y$ and the resulting $g$ appear explicitly.

Facts & Assumptions

Given: The computed Arnoldi relation, initial residual representation, iterate update representation, computed coefficient vector, and successful rowwise residual-recomputation operations in the Statement.

[F1]

Two-pass MGS Arnoldi has an explicit local relation and an a posteriori orthogonality bound: two-pass MGS produces $A Q_{m} = Q_{m + 1} {\overset{ˉ}{H}}_{m} + E_{m}$ and an explicit bound on $∥ Q_{m + 1}^{T} Q_{m + 1} - I ∥_{F}$ under its success and full-rank hypotheses.

[F2]

Operationwise real and complex floating point arithmetic with rounded square roots and fused multiply-add: successful real operations round with relative error at most $u$ , exact-zero operations return zero, and $γ_{n} = n u / (1 - n u)$ for $n u < 1$ .

[F3]

The computed floating-point dot product obeys componentwise and normwise error bounds: when every exact product, rounded product, and intermediate sum is nonzero normal-range, a length- $n$ row dot has absolute error at most $γ_{n}$ times the sum of absolute products.

[F4]

The matrix norm induced by a published vector p-norm: $∥ B v ∥_{2} \leq ∥ B ∥_{2} ∥ v ∥_{2}$ for the induced Euclidean matrix norm.

[F5]

Cauchy-Schwarz $∣ ⟨ x, y ⟩ ∣ \leq ∥ x ∥_{2} ∥ y ∥_{2}$ with its equality case, the triangle inequality for $∥ \cdot ∥_{2}$ , the parallelogram law and polarisation: for finite real vectors, $∣ u^{T} v ∣ \leq ∥ u ∥_{2} ∥ v ∥_{2}$ .

[F6]

Proof

1.1givenF1F4algebra

From the representations in the Statement, $\begin{aligned} r & = b - A (x_{0} + Q_{m} y + δ_{x}) \\ = r_{0} - A Q_{m} y - A δ_{x} \\ = Q_{m + 1} (β_{1} e_{1} - {\overset{ˉ}{H}}_{m} y) + δ_{0} - E_{m} y - A δ_{x} \\ = Q_{m + 1} g + δ_{0} - E_{m} y - A δ_{x} . \end{aligned}$ Subtracting $Q_{m + 1} g$ and applying the triangle inequality and [F4] proves the first bound.

2.1givenF1F4F5step 1.1algebra

For any $v \in R^{m + 1}$ , $∥ Q_{m + 1} v ∥_{2}^{2} = v^{T} (I + \overset{ˉ}{G}) v = ∥ v ∥_{2}^{2} + v^{T} \overset{ˉ}{G} v .$ By [F5], $∣ v^{T} \overset{ˉ}{G} v ∣ \leq ∥ v ∥_{2} ∥ \overset{ˉ}{G} v ∥_{2}$ . By [F4], $∥ \overset{ˉ}{G} v ∥_{2} \leq ∥ \overset{ˉ}{G} ∥_{2} ∥ v ∥_{2}$ , and $∥ \overset{ˉ}{G} ∥_{2} \leq ∥ \overset{ˉ}{G} ∥_{F} = η$ : for each row, [F5] bounds the square of its dot product with $v$ by the squared row norm times $∥ v ∥_{2}^{2}$ ; summing rows gives this inequality. Thus $∥ Q_{m + 1} v ∥_{2} \leq \sqrt{1 + η} ∥ v ∥_{2}$ . Apply this to $v = g$ in step 1.1 and use the triangle inequality to obtain the true-residual bound.

3.1givenF2F3F6algebra∎

For row $i$ , each exact product and partial sum is either zero or normal-range. By [F2], a zero operation returns zero and contributes relative-error factor $1$ , while every nonzero operation contributes a factor $1 + ε$ with $∣ ε ∣ \leq u$ . Unrolling the row dot gives at most $n$ factors in the coefficient of each product, so [F6] yields $∣ {\hat{A x}}_{i} - (A \hat{x})_{i} ∣ \leq γ_{n} \sum_{j} ∣ A_{i j} ∣ ∣ {\hat{x}}_{j} ∣$ , the same error bound as the narrower supplier [F3]. The rounded subtraction gives $∣ {\hat{r}}_{i} - (b_{i} - {\hat{A x}}_{i}) ∣ \leq u ∣ b_{i} - {\hat{A x}}_{i} ∣$ by [F2], with an exact-zero subtraction contributing zero error. Adding these errors shows $∣ {\hat{r}}_{i} - r_{i} ∣ \leq d_{i}$ , hence $∥ \hat{r} - r ∥_{2} \leq ρ_{r e c}$ . The reverse triangle inequality proves the stated difference of residual norms.

PropositionStatement: Literature-sourcedProof: AI-adaptedprecheck pendingjudge pass (gpt-6-luna)Open item page →

Unrestarted GMRES has a sparse matvec plus orthogonalization work bound

Statement

Let $A \in R^{n \times n}$ have a canonical CSR representation, with $n \geq 1$ , at least one stored entry in every row, and $s = nnz (A)$ . Let $r_{0} = b - A x_{0} \neq 0$ and $1 \leq m \leq n$ . Run unrestarted GMRES in exact arithmetic for at most $m$ Arnoldi columns. At column $j$ , compute one CSR matrix-vector product, orthogonalize against the $j$ existing vectors by either one or two complete modified Gram–Schmidt passes, and update the projected least-squares problem by applying prior Givens rotations and forming one new rotation. Each Givens rotation is an orthogonal $2 \times 2$ matrix on adjacent rows chosen to zero the current subdiagonal entry. If Arnoldi completes $m$ columns without breakdown, solve the resulting upper-triangular least-squares factor; if it breaks down earlier, stop at that column and make no claim about a separate rank-deficient fallback solve. Count field arithmetic and index work, and exclude the stored input matrix. The total work in the no-breakdown branch is $O (m s + m^{2} n)$ and the Krylov working storage is $O (m n)$ . The same bounds cover all matvec, orthogonalization, and projected-rotation work actually performed before an earlier breakdown. These are operation and storage bounds, not convergence or runtime claims.

Facts & Assumptions

Given: The canonical square CSR matrix, dimensions $n, s$ , nonzero initial residual, step bound $m$ , and algorithm specified in the Statement.

[F1]

Compressed sparse row matrices with stored-entry semantics: canonical storage has $s = nnz (A)$ ; CSR row intervals partition the stored entries.

[F2]

Validated compressed sparse row matrix-vector product: a valid CSR matvec visits each stored entry once and performs one multiply and one addition at each visit.

[F3]

CSR storage and exact matrix-vector operation counts: for a square record of order $n \geq 1$ with a nonempty stored row pattern, one exact matvec uses $O (s)$ work.

[F4]

The Arnoldi process for building an orthonormal basis of a Krylov subspace: Arnoldi orthogonalizes each $A v_{j}$ against the existing vectors and breaks down when its exact residual is zero.

[F5]

Before breakdown, Arnoldi produces an orthonormal Krylov basis and a rectangular upper-Hessenberg factorization: without breakdown, Arnoldi forms an orthonormal Krylov basis and its projected matrix is upper Hessenberg with positive subdiagonal entries.

[F6]

The GMRES iterate as the residual minimizer over an affine Krylov space: GMRES minimizes the true residual over the affine Krylov space, represented in exact Arnoldi coordinates by the projected least-squares problem.

Proof

1.1givenF1F2F3algebra

The canonical convention [F1] identifies the stored count with $s = nnz (A)$ . Each of at most $m$ columns uses one sparse matvec, which costs $O (s)$ by [F2] and [F3]. Summing over the columns gives $O (m s)$ work; if breakdown stops the run at $d < m$ , the sum through $d$ is no larger.

1.2givenF4algebra

At column $j$ , one complete MGS pass computes $j$ length- $n$ inner products and $j$ length- $n$ vector updates, hence $O (j n)$ arithmetic; two passes multiply this by the fixed factor two. Therefore total orthogonalization work through $m$ columns is $O (n \sum_{j = 1}^{m} j) = O (m^{2} n)$ , and stopping earlier only reduces it.

1.3givenF5F6algebra

In the no-breakdown branch, [F5] gives a projected matrix ${\overset{ˉ}{H}}_{m} \in R^{(m + 1) \times m}$ with nonzero subdiagonal entries $h_{j + 1, j}$ . For orthonormal $Q_{m + 1}$ and $r_{0} = β q_{1}$ , each candidate $x_{0} + Q_{m} y$ has residual $b - A (x_{0} + Q_{m} y) = Q_{m + 1} (β e_{1} - {\overset{ˉ}{H}}_{m} y) .$ Therefore [F6] reduces GMRES minimization to this projected least-squares problem. The submatrix formed by rows $2, \dots, m + 1$ is upper triangular with diagonal $h_{2, 1}, \dots, h_{m + 1, m}$ , so its columns are linearly independent. Thus ${\overset{ˉ}{H}}_{m}$ has full column rank. Applying one plane Givens rotation to each row pair eliminates one subdiagonal entry while preserving the Euclidean least-squares norm; the rotations create an upper-triangular $m \times m$ factor with nonzero diagonal. At column $j$ , applying the previous at most $j - 1$ rotations and forming the new rotation takes $O (j)$ scalar operations; all columns cost $O (m^{2})$ . Back substitution in the nonsingular triangular factor takes $O (m^{2})$ operations, and forming the Krylov correction costs $O (m n)$ . By [F6] this solves the specified GMRES projected least-squares problem.

2.1givenstep 1.1step 1.2step 1.3algebra∎

Since $n \geq 1$ and $m \leq n$ , $m^{2} \leq m^{2} n$ and $m n \leq m^{2} n$ . Adding the work bounds in steps 1.1, 1.2, and 1.3 gives $O (m s + m^{2} n)$ . Storing at most $m + 1$ length- $n$ basis vectors takes $O (m n)$ slots; the Hessenberg and Givens data take $O (m^{2})$ slots; temporary vectors use $O (n)$ slots. Since $m \leq n$ , both $m^{2}$ and $n$ are at most $m n$ , proving the storage bound. If breakdown occurs at column $d < m$ , the already formed basis and projected data use at most the same bounds with $d$ in place of $m$ , and no fallback least-squares solve is included.

5 · Examples, counterexamples and false statements

None yet.

Krylov methods and Lanczos convergence

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

A scaled Chebyshev polynomial suppresses a separated interval

Statement

Facts & Assumptions

Proof

Two-pass MGS Arnoldi has an explicit local relation and an a posteriori orthogonality bound

Statement

Facts & Assumptions

Proof

Finite-precision CG has a recursive-residual gap and an attainable-accuracy bound

Statement

Facts & Assumptions

Proof

Lanczos largest Ritz values obey a Chebyshev start-angle bound, including degenerate branches

Statement

Facts & Assumptions

Proof

A computed GMRES correction has an explicit finite-precision residual gap

Statement

Facts & Assumptions

Proof

Unrestarted GMRES has a sparse matvec plus orthogonalization work bound

Statement

Facts & Assumptions

Proof

5 · Examples, counterexamples and false statements

Sources