LemmaStatement: AI-adaptedProof: AI-adaptedPipeline-generatedjudge pass (gpt-6-luna)

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.

Rounded triangular substitution has a componentwise matrix backward error

Statement

Let $R \in R^{n \times n}$ be upper triangular with stored floating-point entries and nonzero diagonal, and let $y \in R^{n}$ have stored floating-point entries, where $n \geq 1$ and $(n + 3) u < 1$ . Use the operationwise arithmetic model of Operationwise real and complex floating point arithmetic with rounded square roots and fused multiply-add at unit roundoff $u$ . Compute descending substitution by the sequential rounded dot $s_{i} = fl (\sum_{j > i} R_{i j} {\hat{x}}_{j})$ (empty sum zero), $t_{i} = fl (y_{i} - s_{i})$ , and ${\hat{x}}_{i} = fl (t_{i} / R_{i i})$ . Assume each exact intermediate is zero or normal and each rounded result is finite, so every operation succeeds under that model. Then there is upper triangular $Δ R$ with $(R + Δ R) \hat{x} = y, ∣ Δ R ∣ \leq γ_{n + 3} ∣ R ∣, ∥ Δ R ∥_{F} \leq γ_{n + 3} ∥ R ∥_{F} .$ In particular $\hat{x} = 0$ forces $y = 0$ . Forward substitution has the transposed conclusion.

Facts & Assumptions

Given: The stated successful rounded recurrence, with no nonzero subnormal intermediate.

[F1]

Operationwise real and complex floating point arithmetic with rounded square roots and fused multiply-add gives each relative error at most $u$ and exact zeros.

[F2]

If |delta_i| <= u and n u < 1, then prod (1+delta_i) = 1 + theta_n with |theta_n| <= gamma_n bounds each dot-product coefficient error by its accumulated $γ$ factor.

[F3]

Forward and backward substitution are correct, unique, and quadratic in scalar operations supplies the descending and ascending exact triangular recurrences.

Proof

1.1givenF1F2F3algebra

Expand the rounded dot to obtain $s_{i} = \sum_{j > i} R_{i j} {\hat{x}}_{j} (1 + θ_{i j})$ , with $∣ θ_{i j} ∣ \leq γ_{n - i}$ , and use $s_{n} = 0$ . Write subtraction and division errors as $α_{i}, β_{i} \in [- u, u]$ . The computed row identity is then $R_{i i} {\hat{x}}_{i} / ((1 + α_{i}) (1 + β_{i})) + \sum_{j > i} R_{i j} {\hat{x}}_{j} (1 + θ_{i j}) = y_{i}$ . These identities also hold for zero intermediates by taking the corresponding error zero.

2.1F1step 1.1algebraconstruct

Choose $Δ R_{i i} = R_{i i} (((1 + α_{i}) (1 + β_{i}))^{- 1} - 1)$ and $Δ R_{i j} = R_{i j} θ_{i j}$ for $j > i$ , with zeros below the diagonal. Since $u < 1 / (n + 3) \leq 1 / 4$ , all denominators are positive and $∣ ((1 + α_{i}) (1 + β_{i}))^{- 1} - 1 ∣ \leq (1 - u)^{- 2} - 1 \leq 3 u / (1 - 3 u) = γ_{3}$ ; multiplying positive denominators verifies the last inequality. Thus every entry has the claimed bound.

3.1step 1.1step 2.1algebra∎

Step 1.1 gives $(R + Δ R) \hat{x} = y$ , and summing the squared entry bounds gives the Frobenius estimate. If $\hat{x} = 0$ , the same equation gives $y = 0$ , including dimension one without a division by $∥ \hat{x} ∥$ . Reversing the row order proves the lower-triangular version.

Depends on

Used by

Dependency tree · two levels

7 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

Stuart and Voss, Matrix Analysis and Algorithms (standard reference, not scraped)