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.
Lanczos handles repeated top eigenvalues, absent top components, and exact breakdown
Example
Check four branches of Lanczos largest Ritz values obey a Chebyshev start-angle bound, including degenerate branches: (i) and ; (ii) with ; (iii) with ; and (iv) the same with . Verify the Rayleigh–Ritz values, top-eigenspace components, and exact invariant-subspace breakdown dimensions.
Facts & Assumptions
Given: The matrices, vectors, Krylov spaces, and Rayleigh–Ritz values in the Example.
Lanczos largest Ritz values obey a Chebyshev start-angle bound, including degenerate branches: if the top eigenvalue has multiplicity , every Rayleigh–Ritz value is ; if , every ; if the unwanted interval collapses and , then for ; and exact breakdown at dimension with gives .
The Arnoldi process for building an orthonormal basis of a Krylov subspace: exact breakdown at a column means its orthogonalized residual is zero.
The Lanczos process as Arnoldi specialized to a Hermitian matrix, with the usual real-subdiagonal phase convention: for a real symmetric matrix, exact Lanczos is the corresponding exact Arnoldi process specialized to the Hermitian three-term recurrence.
Verification
In case (i), take . Then , , and is invariant under . The first Arnoldi residual is zero, so Lanczos breaks down at ; every nonzero vector has Rayleigh quotient , giving for all by [F1]. In case (ii), projects onto , so . Here and , so , an invariant subspace. The first Arnoldi residual is nonzero, while makes the second residual zero; hence Lanczos breaks down at . Since has Rayleigh quotient , the maximum is , as [F1] predicts for the collapsed interval branch.
In case (iii), projects onto , so ; gives for every , and therefore , in agreement with [F1]. At the first Arnoldi column, already lies in , so subtracting its projection leaves zero residual. Thus [F3]–[F4] give exact Lanczos breakdown at without a top component.
In case (iv), and are independent, so ; this space is invariant under . At the second Arnoldi column, , so subtracting its two orthogonal projections leaves zero residual. Thus [F3]–[F4] give exact Lanczos breakdown at . Since , [F1] gives ; directly, , so and its Rayleigh quotient is .
Depends on
- Lanczos largest Ritz values obey a Chebyshev start-angle bound, including degenerate branches
- The Krylov subspace $K_m(A,b)=\operatorname{span}\{b,Ab,\dots,A^{m-1}b\}$
- The Arnoldi process for building an orthonormal basis of a Krylov subspace
- The Lanczos process as Arnoldi specialized to a Hermitian matrix, with the usual real-subdiagonal phase convention
Used by
Nothing in the library uses this result yet.
Dependency tree · two levels
13 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
- Youcef Saad, Iterative Methods for Sparse Linear Systems, 2nd ed., §§6.6 and 6.11.1, printed pp. 194–195 and 209–210 (standard reference, not scraped)
- David Bindel, Matrix Computations (CS 6210), Cornell University, Fall 2012, Lectures 38–39 (standard reference, not scraped)