Alphabeta Math
TheoremStatement: Literature-sourcedProof: Literature-sourcedPipeline-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.

The scaled Householder QR implementation is backward stable

Statement

Let A∈Rm×n, m≥n≥1, undergo successful QR steps of Scaled Householder reflector formation and application, with mu<1. Use κm from The scaled computed Householder step satisfies the local backward error premise and set βQ=(1+κm)n−1. The exact orthogonal product represented by the stored reflectors has reduced first n columns Q^, and the computed triangular block is R^. Then A+ΔA=Q^R^,∥ΔA∥F≤βQ∥A∥F. If applying the stored reflectors in the same order to a separate vector b, by their rounded rank-one updates without column overwrites, succeeds at every update, the resulting full vector c^ satisfies ∥c^−QfullTb∥2≤βQ∥b∥2. The bounds are O(u) for fixed dimensions. An explicitly rounded dense product for Qfull is not asserted exactly orthogonal.

Facts & Assumptions

Given: Successful no-underflow QR and vector updates in the stated operationwise arithmetic.

[F1]

The scaled computed Householder step satisfies the local backward error premise supplies each exact orthogonal representative and its local matrix and separate-block bound.

Proof

1.1givenF1algebrainduction

Embed each active orthogonal representative into the full row dimension and each local perturbation by zeros outside its active block. All active row counts are at most m, so [F1] bounds every local error by κm times the current active-block norm, hence by that times the current full-matrix norm. A completed full step therefore has norm at most 1+κm times the preceding norm. Induction bounds the matrix before step k by (1+κm)k∥A∥F.

2.1F1F2step 1.1algebra

Transport each local error back through the preceding orthogonal factors. Orthogonal multiplication preserves Frobenius norm, as follows by summing the preserved squared column norms. The transported errors sum to ΔA, and exact column overwrites make the final lower block zero. Thus [F2] identifies A+ΔA=Q^R^, with ∥ΔA∥F≤κm∑k=0n−1(1+κm)k∥A∥F=βQ∥A∥F.

3.1F1step 1.1step 2.1algebra∎

For the separate vector, [F1] bounds each update discrepancy by κm times its current norm. The identical norm induction and orthogonal transport argument bound its total discrepancy from the exact product by κm∑k=0n−1(1+κm)k∥b∥2=βQ∥b∥2. Since κm=O(u) for fixed m, the claimed fixed-dimension backward and application bounds follow.

Depends on

Used by

Dependency tree · two levels

12 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