ExampleConstruction: AI-generatedVerification: AI-generatedPipeline-generatedprecheck pass

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.

A Lanczos Ritz value can miss the operator norm

Statement

Let $K = diag (1, 2)$ and start exact symmetric Lanczos at the unit vector $b = e_{1} = (1, 0)^{T}$ . At $m = 0$ , $K_{0} (K, b) = {0}$ and there is no Ritz value. For every $m \geq 1$ , $K_{m} (K, b) = span {e_{1}}$ , so its only Ritz value is $1$ , while the induced Euclidean operator norm is $∥ K ∥_{2} = 2$ . The Ritz value from this start does not certify the PDHG upper step-size bound.

Facts & Assumptions

Given: The symmetric matrix $K$ , start vector $b$ , and definitions of Krylov space, Ritz value and induced matrix norm.

[A1]

The matrix is symmetric, the start vector is $e_{1}$ , and arithmetic is exact.

[F1]

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

[F2]

Lanczos largest Ritz values obey a Chebyshev start-angle bound, including degenerate branches: if the starting vector has zero projection onto the top eigenspace, the largest Ritz value stays at most the next eigenvalue; no convergence to the top eigenvalue is asserted.

[F3]

Chambolle–Pock primal-dual hybrid gradient: PDHG requires a certified upper bound satisfying $τ σ ∥ K ∥_{2}^{2} < 1$ .

[F4]

The matrix norm induced by a published vector p-norm: $∥ K ∥_{2} = \sup_{∥ x ∥_{2} \leq 1} ∥ K x ∥_{2}$ .

Proof

1.1A1F1givenalgebra

Since $K b = e_{1} = b$ , every power $K^{j} b = b$ . For $m = 0$ , the spanning list is empty and its span is ${0}$ , with no nonzero vector on which to evaluate a Rayleigh quotient. For every $m \geq 1$ , the spanning set in [F1] consists of repetitions of the single nonzero vector $e_{1}$ , and the Rayleigh quotient on this one-dimensional subspace is $e_{1}^{T} K e_{1} / (e_{1}^{T} e_{1}) = 1$ . Exact Lanczos terminates after one vector with Ritz value $1$ .

2.1A1F2F3F4step 1.1algebra∎

For $x = (x_{1}, x_{2})$ , $∥ K x ∥_{2}^{2} = x_{1}^{2} + 4 x_{2}^{2} \leq 4 (x_{1}^{2} + x_{2}^{2})$ , with equality at $e_{2}$ , so [F4] gives $∥ K ∥_{2} = 2$ . The top eigenspace is $span {e_{2}}$ and $P b = 0$ ; [F2] identifies exactly this degenerate branch and supplies no top-eigenvalue convergence bound. Therefore the Ritz value $1$ is not the norm upper bound $2$ required by [F3].

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

25 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Yousef Saad, Iterative Methods for Sparse Linear Systems, 2nd ed., Chapter 6 (standard reference, not scraped)