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 , , undergo successful QR steps of Scaled Householder reflector formation and application, with . Use from The scaled computed Householder step satisfies the local backward error premise and set . The exact orthogonal product represented by the stored reflectors has reduced first columns , and the computed triangular block is . Then If applying the stored reflectors in the same order to a separate vector , by their rounded rank-one updates without column overwrites, succeeds at every update, the resulting full vector satisfies The bounds are for fixed dimensions. An explicitly rounded dense product for is not asserted exactly orthogonal.
Facts & Assumptions
Given: Successful no-underflow QR and vector updates in the stated operationwise arithmetic.
The scaled computed Householder step satisfies the local backward error premise supplies each exact orthogonal representative and its local matrix and separate-block bound.
Successive Householder or Givens transformations produce full and reduced QR factorisations with the standard dense operation counts supplies exact orthogonal-product and triangular-block conventions.
Proof
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 , so [F1] bounds every local error by times the current active-block norm, hence by that times the current full-matrix norm. A completed full step therefore has norm at most times the preceding norm. Induction bounds the matrix before step by .
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 , and exact column overwrites make the final lower block zero. Thus [F2] identifies , with .
For the separate vector, [F1] bounds each update discrepancy by times its current norm. The identical norm induction and orthogonal transport argument bound its total discrepancy from the exact product by . Since for fixed , 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
- Fundamentals of Numerical Computation, floating-point arithmetic (standard reference, not scraped)
- Fundamentals of Numerical Computation, Householder triangularization (standard reference, not scraped)
- Fundamentals of Numerical Computation, QR factorization and least squares (standard reference, not scraped)
- Stuart and Voss, Matrix Analysis and Algorithms, Warwick lecture notes (standard reference, not scraped)