ExampleConstruction: AI-adaptedVerification: AI-adaptedPipeline-generatedprecheck passaudited 2026-08-29

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.

A backward-stable computed solution of an ill-conditioned system can still have large forward error

Example

Fix an arithmetic model with unit roundoff $0 < u < 1$ and set $ε = u$ . Take $A = diag (1, ε)$ and $b = (1, ε)$ , whose exact solution is $x = (1, 1)$ . On the singleton input class consisting of this system, let an algorithm return $\hat{x} = (1, 0)$ . Its normwise backward error is at most $u / 2$ , so this algorithm is backward stable on the declared class, yet its relative forward error is $1 / \sqrt{2}$ : ill conditioning is not instability, and backward stability does not remove ill conditioning.

Facts & Assumptions

Given: An arithmetic model with unit roundoff $u \in (0, 1)$ , the parameter $ε = u$ , the matrix $A = diag (1, ε)$ , the vector $b = (1, ε)$ , the exact solution $x = (1, 1)$ , and an algorithm on the singleton input class $I = {(A, b)}$ that returns $\hat{x} = (1, 0)$ .

[L1]

The normwise backward error is $η_{2} (\hat{x}) = ∥ r ∥_{2} / (∥ A ∥_{2} ∥ \hat{x} ∥_{2} + ∥ b ∥_{2})$ for $r = b - A \hat{x}$ (Residual formulas for normwise and componentwise backward error).

[L2]

Along admissible perturbations tending to zero, relative forward error is at most $(κ_{r e l} + o (1))$ times relative backward error (Local conditioning times backward error controls forward error to first order).

[A1]

For the fixed linear map $f (b) = A^{- 1} b$ , one has $f (b + h) - f (b) = A^{- 1} h$ by linearity.

Verification

technique · direct

1.1

The residual is $r = b - A \hat{x} = (0, ε)$ and $∥ r ∥_{2} = ε$ ; also $∥ A ∥_{2} = 1$ , $∥ \hat{x} ∥_{2} = 1$ and $∥ b ∥_{2} = \sqrt{1 + ε^{2}}$ .

algebra

1.2

The forward error is $∥ x - \hat{x} ∥_{2} = ∥ (0, 1) ∥_{2} = 1$ and the relative forward error $1 / \sqrt{2}$ , order one even as $ε \to 0^{+}$ .

algebra

1.3

The conditioning conversion. For the problem map $f (b) = A^{- 1} b$ the absolute condition number is $κ_{a b s} = ∥ A^{- 1} ∥_{2} = 1 / ε$ , attained in the second coordinate, and the computed answer is exact for the perturbed input $\tilde{b} : = A \hat{x} = (1, 0) = b + h$ with $h = (0, - ε)$ . By [A1], $f (b + h) - f (b) = A^{- 1} h = (0, - 1)$ , and direct substitution gives $1 / \sqrt{2} = κ_{r e l} ∥ h ∥_{2} / ∥ b ∥_{2}$ .

A1algebra

2.1

By [L1], the normwise backward error is $η_{2} (\hat{x}) = ε / (1 + \sqrt{1 + ε^{2}}) \leq ε / 2 = u / 2$ . Thus the one constant $C = 1 / 2$ works for every input in the declared singleton class $I$ , so the algorithm is normwise backward stable there in the specialized sense of Forward and backward stability for a problem family under an arithmetic model.

givenL1step 1.1algebra

3.1

Steps 2.1, 1.2 and 1.3 show that this backward-stable algorithm on an ill-conditioned problem class has order-one forward error even though its backward error is order $u$ ; [L2] records the general first-order conditioning principle illustrated exactly here. Backward stability controls the data perturbation, and only conditioning controls the answer.

L2step 2.1step 1.2step 1.3∎

Depends on

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

L. N. Trefethen and D. Bau III, Numerical Linear Algebra, Lecture 15 (standard reference, not scraped)