PropositionStatement: Literature-sourcedProof: 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.

Residual formulas for normwise and componentwise backward error

Statement

Let $n \geq 1$ , let $A \in {GL}_{n} (R)$ , let $b \in R^{n}$ , let $\hat{x} \in R^{n}$ , and put $r = b - A \hat{x}$ .

Normwise formula (spectral norm). $η_{2} (\hat{x}) = \frac{∥ r ∥_{2}}{∥ A ∥_{2} ∥ \hat{x} ∥_{2} + ∥ b ∥_{2}},$ with the convention $0 / 0 : = 0$ .
Componentwise formula. With $(∣ A ∣ ∣ \hat{x} ∣)_{i} : = \sum_{j < n} ∣ a_{i j} ∣ ∣ {\hat{x}}_{j} ∣$ , $ω (\hat{x}) = \max_{i < n} \frac{∣ r_{i} ∣}{(∣ A ∣ ∣ \hat{x} ∣)_{i} + ∣ b_{i} ∣},$ where a term with $∣ r_{i} ∣ = 0$ and denominator $0$ is interpreted as $0$ . Every such degenerate term has $∣ r_{i} ∣ = 0$ , so the maximum is a finite real number.

Here $η_{2}$ and $ω$ are the backward errors of Normwise and componentwise backward error for an approximate linear-system solution, and $∥ \cdot ∥_{2}$ is the spectral (operator) norm, which on vectors is the Euclidean norm of Each $∥ \cdot ∥_{p}$ is a norm on $R^{n}$ , and the induced metrics are exactly $d_{1}$ , $d_{2}$ and $d_{\infty}$ of the published metric-spaces page.

Facts & Assumptions

Given: An invertible matrix $A \in {GL}_{n} (R)$ with $n \geq 1$ , vectors $b, \hat{x} \in R^{n}$ , the residual $r = b - A \hat{x}$ , and the backward errors $η_{2} (\hat{x})$ , $ω (\hat{x})$ .

[L1]

An admissible perturbation satisfies $Δ A \hat{x} - Δ b = r$ and the stated norm or entrywise bounds (Normwise and componentwise backward error for an approximate linear-system solution).

[L2]

Compatibility of the induced spectral norm: $∥ M y ∥_{2} \leq ∥ M ∥_{2} ∥ y ∥_{2}$ (Induced matrix norms are compatible with matrix-vector multiplication, submultiplicative, and satisfy ||I|| = 1), and the vector $2$ -norm is the Euclidean norm with the triangle inequality (Each $∥ \cdot ∥_{p}$ is a norm on $R^{n}$ , and the induced metrics are exactly $d_{1}$ , $d_{2}$ and $d_{\infty}$ of the published metric-spaces page).

[L3]

Cauchy–Schwarz: $∣ u^{T} v ∣ \leq ∥ u ∥_{2} ∥ v ∥_{2}$ , with equality for $v$ a positive multiple of $u$ (Cauchy-Schwarz $∣ ⟨ x, y ⟩ ∣ \leq ∥ x ∥_{2} ∥ y ∥_{2}$ with its equality case, the triangle inequality for $∥ \cdot ∥_{2}$ , the parallelogram law and polarisation).

[L5]

Absolute value: $∣ u + v ∣ \leq ∣ u ∣ + ∣ v ∣$ and $∣ u v ∣ = ∣ u ∣ ∣ v ∣$ (Absolute value in an ordered field).

Proof

technique · direct

1.1

Lower bound for the normwise error. For any admissible pair of [L1], $∥ r ∥_{2} = ∥ Δ A \hat{x} - Δ b ∥_{2} \leq ∥ Δ A ∥_{2} ∥ \hat{x} ∥_{2} + ∥ Δ b ∥_{2} \leq ε (∥ A ∥_{2} ∥ \hat{x} ∥_{2} + ∥ b ∥_{2})$ , using [L1], [L2] and the triangle inequality of [L2].

L1L2algebra

1.2

Attainment for the normwise error. Put $γ : = ∥ A ∥_{2} ∥ \hat{x} ∥_{2} + ∥ b ∥_{2}$ and suppose first $γ > 0$ . If $\hat{x} \neq 0$ , define $Δ A : = (∥ A ∥_{2} / γ) r {\hat{x}}^{T} / ∥ \hat{x} ∥_{2}$ and $Δ b : = - (∥ b ∥_{2} / γ) r$ ; then $Δ A \hat{x} - Δ b = r$ and, by [L3] applied row-wise, $∥ r {\hat{x}}^{T} ∥_{2} = ∥ r ∥_{2} ∥ \hat{x} ∥_{2}$ , so $∥ Δ A ∥_{2} = η ∥ A ∥_{2}$ and $∥ Δ b ∥_{2} = η ∥ b ∥_{2}$ with $η : = ∥ r ∥_{2} / γ$ .

L1L3algebraconstruct

1.3

If $\hat{x} = 0$ then $r = b$ and $γ = ∥ b ∥_{2} > 0$ ; the perturbations $Δ A = 0$ and $Δ b = - r$ satisfy $Δ A \hat{x} - Δ b = r$ with $∥ Δ b ∥_{2} = ∥ r ∥_{2} = η ∥ b ∥_{2}$ , so the same $η$ is attained.

L1algebraconstruct

1.4

If $γ = 0$ then $∥ A ∥_{2} ∥ \hat{x} ∥_{2} = 0$ and $b = 0$ , so $r = b - A \hat{x} = 0$ ; the convention $0 / 0 : = 0$ and the zero perturbations of [L1] give $η_{2} (\hat{x}) = 0$ , matching the formula.

L1algebra

1.5

Lower bound for the componentwise error. For any admissible pair of [L1], $∣ r_{i} ∣ = ∣ \sum_{j} Δ a_{i j} {\hat{x}}_{j} - Δ b_{i} ∣ \leq \sum_{j} ∣ Δ a_{i j} ∣ ∣ {\hat{x}}_{j} ∣ + ∣ Δ b_{i} ∣ \leq ε (\sum_{j} ∣ a_{i j} ∣ ∣ {\hat{x}}_{j} ∣ + ∣ b_{i} ∣)$ by [L5] and the entrywise bounds of [L1].

L1L5algebra

1.6

A term with denominator $0$ has $b_{i} = 0$ and $a_{i j} {\hat{x}}_{j} = 0$ for every $j < n$ , so $r_{i} = b_{i} - (A \hat{x})_{i} = 0$ ; thus every degenerate term carries numerator $0$ , and the maximum is finite as claimed.

givenalgebra

1.7

Attainment for the componentwise error. Put $d_{i} : = (∣ A ∣ ∣ \hat{x} ∣)_{i} + ∣ b_{i} ∣$ and $ω : = \max_{i < n} ∣ r_{i} ∣ / d_{i}$ with the convention of the statement. For each $i < n$ with $d_{i} > 0$ define $Δ b_{i} : = - r_{i} ∣ b_{i} ∣ / d_{i}$ and, for each $j < n$ , $Δ a_{i j} : = ∣ a_{i j} ∣ sgn ({\hat{x}}_{j}) r_{i} / d_{i}$ when ${\hat{x}}_{j} \neq 0$ and $Δ a_{i j} : = 0$ when ${\hat{x}}_{j} = 0$ ; for $d_{i} = 0$ set all these entries to $0$ .

constructalgebra

2.1

Hence every admissible $ε$ is at least $∥ r ∥_{2} / (∥ A ∥_{2} ∥ \hat{x} ∥_{2} + ∥ b ∥_{2})$ , so the infimum satisfies $η_{2} (\hat{x}) \geq ∥ r ∥_{2} / (∥ A ∥_{2} ∥ \hat{x} ∥_{2} + ∥ b ∥_{2})$ when the denominator is positive.

step 1.1algebra

2.2

For every $i < n$ with $(∣ A ∣ ∣ \hat{x} ∣)_{i} + ∣ b_{i} ∣ > 0$ , step 1.5 gives $ε \geq ∣ r_{i} ∣ / ((∣ A ∣ ∣ \hat{x} ∣)_{i} + ∣ b_{i} ∣)$ , so every admissible $ε$ is at least the maximum over such $i$ ; hence $ω (\hat{x}) \geq \max_{i < n} ∣ r_{i} ∣ / ((∣ A ∣ ∣ \hat{x} ∣)_{i} + ∣ b_{i} ∣)$ with the stated convention.

step 1.5algebra

2.3

For $d_{i} > 0$ one has $(Δ A \hat{x})_{i} = \sum_{j} ∣ a_{i j} ∣ ∣ {\hat{x}}_{j} ∣ r_{i} / d_{i} = r_{i} (∣ A ∣ ∣ \hat{x} ∣)_{i} / d_{i}$ and $Δ b_{i} = - r_{i} ∣ b_{i} ∣ / d_{i}$ , so $(Δ A \hat{x})_{i} - Δ b_{i} = r_{i}$ ; and $∣ Δ a_{i j} ∣ = ∣ a_{i j} ∣ ∣ r_{i} ∣ / d_{i} \leq ω ∣ a_{i j} ∣$ together with $∣ Δ b_{i} ∣ \leq ω ∣ b_{i} ∣$ , since $∣ r_{i} ∣ \leq ω d_{i}$ . For $d_{i} = 0$ every displayed entry vanishes and step 1.6 gives $r_{i} = 0$ .

step 1.7step 1.6L5algebra

3.1

Combining steps 2.1, 1.2, 1.3 and 1.4, the infimum is attained and equals $∥ r ∥_{2} / (∥ A ∥_{2} ∥ \hat{x} ∥_{2} + ∥ b ∥_{2})$ under the stated convention, which is claim 1.

step 2.1step 1.2step 1.3step 1.4

3.2

The perturbations of step 1.7 are admissible with $ε = ω$ by step 2.3, so $ω (\hat{x}) \leq ω$ ; with step 2.2 the formula of claim 2 holds.

step 2.3step 2.2L1

4.1

Claim 1 is step 3.1 and claim 2 is step 3.2.

step 3.1step 3.2∎

Depends on

Used by

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

Dependency tree · two levels

36 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

James Demmel, Math 221 Lecture 3: Vector Norms, Matrix Norms, and Condition Numbers (standard reference, not scraped)
L. N. Trefethen and D. Bau III, Numerical Linear Algebra, Lecture 12 (standard reference, not scraped)