TheoremStatement: AI-adaptedProof: AI-generatedprecheck passaudited 2026-08-31

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.

Arnoldi reduces GMRES to a least-squares problem for the small Hessenberg matrix

Statement

Let $r_{0} = b - A x_{0} \neq 0$ and set $β = ∥ r_{0} ∥_{2}$ . Run Arnoldi on $(A, r_{0})$ through step $m$ without breakdown, so that $v_{1} = r_{0} / β$ . Then every vector $x \in x_{0} + K_{m} (A, r_{0})$ has the form $x = x_{0} + Q_{m} y$ for some $y \in F^{m}$ , and

$b - A x = Q_{m + 1} (β e_{1} - {\overset{ˉ}{H}}_{m} y) .$

Consequently,

$\min_{x \in x_{0} + K_{m} (A, r_{0})} ∥ b - A x ∥_{2} = \min_{y \in F^{m}} ∥ β e_{1} - {\overset{ˉ}{H}}_{m} y ∥_{2} .$

Facts & Assumptions

Given: A linear system $A x = b$ , an initial guess $x_{0}$ , the nonzero initial residual $r_{0} = b - A x_{0}$ , and an Arnoldi run on $(A, r_{0})$ through step $m$ without breakdown.

[F1]

A GMRES iterate minimizes the residual norm over $x_{0} + K_{m} (A, r_{0})$ (The GMRES iterate as the residual minimizer over an affine Krylov space).

[L1]

Arnoldi gives an orthonormal basis of $K_{m} (A, r_{0})$ and the factorization $A Q_{m} = Q_{m + 1} {\overset{ˉ}{H}}_{m}$ with $Q_{m + 1}^{*} Q_{m + 1} = I$ (Before breakdown, Arnoldi produces an orthonormal Krylov basis and a rectangular upper-Hessenberg factorization).

Proof

technique · direct

1.1L1constructalgebra

By [L1], the columns of $Q_{m}$ form a basis of $K_{m} (A, r_{0})$ , so every $x \in x_{0} + K_{m} (A, r_{0})$ can be written uniquely as $x = x_{0} + Q_{m} y$ . Since $r_{0} = β v_{1} = β Q_{m + 1} e_{1}$ and $b - A x_{0} = r_{0}$ , one has $b - A x = r_{0} - A Q_{m} y = Q_{m + 1} β e_{1} - Q_{m + 1} {\overset{ˉ}{H}}_{m} y = Q_{m + 1} (β e_{1} - {\overset{ˉ}{H}}_{m} y) .$

2.1F1L1step 1.1∎

The columns of $Q_{m + 1}$ are orthonormal by [L1], so multiplying by $Q_{m + 1}$ preserves the Euclidean norm. Therefore $∥ b - A x ∥_{2} = ∥ β e_{1} - {\overset{ˉ}{H}}_{m} y ∥_{2} .$ Taking minima over the corresponding parametrized sets gives the stated small least-squares problem. This is the residual norm whose minimizers [F1] calls GMRES iterates.

Depends on

Used by

Dependency tree · two levels

10 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, CSCI 8314 Set 13: Krylov subspace methods; Introduction; Krylov subspaces; Gram-Schmidt process (review); The Arnoldi process; FOM and GMRES (standard reference, not scraped)