Rounding-error and perturbation analysis

The catalogue's first page explains what each entry shows.

Chapter 1 · Principles of finite precision all chapters

Definitions, theorems and lemmas

  • Lemma 1.1

    Predicate form: among all perturbations to A that make y an exact solution, the optimal operator-2 perturbation budget is ||b - Ay||₂ / ||y||₂, and it is attained by the rank-one perturbation (b - Ay)yᵀ/(yᵀy).

    Lean statement
    theorem higham_lemma_1_1_operator2_predicate (n : ℕ)
        (A : Fin n → Fin n → ℝ) (y b : Fin n → ℝ)
        (hy : vecNorm2 y ≠ 0) :
        let η := vecNorm2 (residualVec n A y b) / vecNorm2 y
        matrixOnlyBackwardError2Le n A y b η ∧
          ∀ c : ℝ, matrixOnlyBackwardError2Le n A y b c → η ≤ c

    higham_lemma_1_1_operator2_predicate · 6 more declarations under this item

Problems and exercises

  • Problem 1.1

    Problem 1.1 packaged form: when both denominators are nonzero and both relative errors are below one, the exact-denominator and computed-denominator relative errors bound each other by the standard E/(1±E) envelopes.

    Lean statement
    theorem problem_1_1_relError_bounds
        (computed exact : ℝ) (hexact : exact ≠ 0) (hcomputed : computed ≠ 0)
        (hrel : relError computed exact < 1)
        (hrelTilde : relErrorComputedDenom computed exact < 1) :
        (relError computed exact / (1 + relError computed exact) ≤
            relErrorComputedDenom computed exact ∧
          relErrorComputedDenom computed exact ≤
            relError computed exact / (1 - relError computed exact)) ∧
        (relErrorComputedDenom computed exact /
              (1 + relErrorComputedDenom computed exact) ≤
            relError computed exact ∧
          relError computed exact ≤
            relErrorComputedDenom computed exact /
              (1 - relErrorComputedDenom computed exact))

    problem_1_1_relError_bounds · 3 more declarations under this item

  • Problem 1.4

    Correctness of the stable square-root formula when 0 <= a and the input is nonzero.

    Lean statement
    theorem complexSqrtStable_nonnegA_sq {a b : ℝ}
        (ha : 0 ≤ a) (hnz : a ≠ 0 ∨ b ≠ 0) :
        complexFromRealImag
            (complexSqrtStableXNonnegA a b)
            (complexSqrtStableYNonnegA a b) ^ 2 =
          complexFromRealImag a b

    complexSqrtStable_nonnegA_sq · 2 more declarations under this item

  • Problem 1.5

    Exact source identity for Problem 1.5's compensated logarithm formula: with exact arithmetic, formula (A.1) computes log(1+x).

    Lean statement
    theorem logOnePlusCompensatedExact_eq_log_one_add (x : ℝ) :
        logOnePlusCompensatedExact x = Real.log (1 + x)

    logOnePlusCompensatedExact_eq_log_one_add · 5 more declarations under this item

  • Problem 1.9

    A two-product determinant evaluated as fl(fl(a11*a22) - fl(a21*a12)) has absolute error bounded by gamma_3 * (|a11*a22| + |a21*a12|). This is the concrete floating-point kernel used by Higham Problem 1.9 for the Cramer numerator determinants.

    Lean statement
    theorem flDet2x2_error_le_gamma3
        (fp : FPModel) (h3 : gammaValid fp 3)
        (a11 a12 a21 a22 : ℝ) :
        |flDet2x2 fp a11 a12 a21 a22 - det2x2 a11 a12 a21 a22| ≤
          gamma fp 3 * det2x2AbsTerms a11 a12 a21 a22

    flDet2x2_error_le_gamma3 · 3 more declarations under this item

  • Problem 1.10

    Problem 1.10 form using the named explicit higher-order remainder.

    Lean statement
    theorem flSampleVarianceTwoPass_relError_le_linear_u_add_problem110_remainder {n : ℕ}
        (fp : FPModel) (x : Fin n → ℝ)
        (hn : 1 < n) (hVpos : 0 < sampleVarianceTwoPass x)
        (hsumpos : 0 < ∑ i : Fin n, (x i - flSampleMean fp x) ^ 2)
        (hγ : gammaValid fp (n + 3)) :
        relError (flSampleVarianceTwoPass fp x) (sampleVarianceTwoPass x) ≤
          ((n + 3 : ℕ) : ℝ) * fp.u +
            flSampleVarianceTwoPassProblem110Remainder fp x

    flSampleVarianceTwoPass_relError_le_linear_u_add_problem110_remainder · 1 more declaration under this item

Chapter 2 · Floating-point arithmetic all chapters

Definitions, theorems and lemmas

  • Theorem 2.2

    Strict arbitrary-output version of Higham Theorem 2.2 on the finite normal range: every finite nearest-rounded value, not only the existentially selected one, satisfies a strict signed relative-error witness.

    Lean statement
    theorem nearestRoundingToFinite_signedRelErrorWitness_lt_of_finiteNormalRange
        {fmt : FloatingPointFormat} {x y : ℝ}
        (hround : fmt.nearestRoundingToFinite x y)
        (hx : fmt.finiteNormalRange x) :
        ∃ δ : ℝ,
          |δ| < fmt.unitRoundoff ∧ signedRelErrorWitness y x δ

    nearestRoundingToFinite_signedRelErrorWitness_lt_of_finiteNormalRange · 2 more declarations under this item

  • Theorem 2.3

    Problem 2.4 / Theorem 2.3 for the finite nearest-rounding relation.

    Lean statement
    theorem problem2_4_theorem2_3_nearest_finite
        {fmt : FloatingPointFormat} {x : ℝ}
        (hx : fmt.finiteNormalRange x) :
        ∃ y δ : ℝ,
          fmt.nearestRoundingToFinite x y ∧
            |δ| ≤ fmt.unitRoundoff ∧ 1 + δ ≠ 0 ∧ y = x / (1 + δ)

    problem2_4_theorem2_3_nearest_finite · 3 more declarations under this item

  • Theorem 2.4

    Higham Theorem 2.4's magnitude/exponent condition itself forces the exact subtraction onto a finite radix lattice. In particular, representability of x-y is a conclusion rather than part of the hypothesis.

    Lean statement
    theorem fergusonMagnitudeExponentConditionLe_sub_finiteSystem
        {fmt : FloatingPointFormat} {x y : ℝ}
        (h : fmt.fergusonMagnitudeExponentConditionLe x y) :
        fmt.finiteSystem (x - y)

    fergusonMagnitudeExponentConditionLe_sub_finiteSystem · 2 more declarations under this item

  • Theorem 2.5

    Source-shaped inclusive form of Higham Theorem 2.5 (Sterbenz) for the concrete finite round-to-even operation wrapper.

    Lean statement
    theorem finiteRoundToEvenOp_sub_finiteSystem_eq_exact_of_sterbenzRatioConditionLe
        {fmt : FloatingPointFormat} {x y : ℝ}
        (hx : fmt.finiteSystem x)
        (hy : fmt.finiteSystem y)
        (hsterbenz : fmt.sterbenzRatioConditionLe x y) :
        fmt.finiteRoundToEvenOp BasicOp.sub x y = x - y

    finiteRoundToEvenOp_sub_finiteSystem_eq_exact_of_sterbenzRatioConditionLe · 1 more declaration under this item

Equations and other results

  • Equation (2.1)

    Normalized finite values lie in the source-facing finite normal range.

    Lean statement
    theorem normalizedSystem_finiteNormalRange
        {fmt : FloatingPointFormat} {y : ℝ}
        (hy : fmt.normalizedSystem y) :
        fmt.finiteNormalRange y

    normalizedSystem_finiteNormalRange

  • Equation (2.4)

    Lean statement
    theorem finiteRoundToEvenSqrt_standardModel_lt_of_finiteNormalRange
        {fmt : FloatingPointFormat} {x : ℝ}
        (_hx_nonneg : 0 ≤ x) (hsqrt : fmt.finiteNormalRange (Real.sqrt x)) :
        ∃ δ : ℝ,
          |δ| < fmt.unitRoundoff ∧
            fmt.finiteRoundToEvenSqrt x = Real.sqrt x * (1 + δ)

    finiteRoundToEvenSqrt_standardModel_lt_of_finiteNormalRange · 1 more declaration under this item

  • Equation (2.7)

    Kahan's parenthesized area has the same squared value as Heron's radicand for ordered nondegenerate triangle sides.

    Lean statement
    theorem kahanHeronArea_sq_eq_heronRadicand_of_kahanOrderedTriangleSides
        {a b c : ℝ} (h : kahanOrderedTriangleSides a b c) :
        kahanHeronArea a b c ^ 2 = heronRadicand a b c

    kahanHeronArea_sq_eq_heronRadicand_of_kahanOrderedTriangleSides · 2 more declarations under this item

  • Equation (2.8)

    Normal-range branch of Higham's additive underflow model (2.8) for the ordinary finite primitive-operation wrapper: away from underflow, η = 0.

    Lean statement
    theorem finiteRoundToEvenOp_strictAdditiveUnderflowModel_normal_branch_of_finiteNormalRange
        {fmt : FloatingPointFormat} {op : BasicOp} {x y : ℝ}
        (hxy : fmt.finiteNormalRange (BasicOp.exact op x y)) :
        ∃ δ η : ℝ,
          strictAdditiveUnderflowModelWitness (fmt.finiteRoundToEvenOp op x y)
            (BasicOp.exact op x y) fmt.unitRoundoff fmt.gradualUnderflowEtaBound
            δ η

    finiteRoundToEvenOp_strictAdditiveUnderflowModel_normal_branch_of_finiteNormalRange

Chapter 3 · Basics (dot products, γ(n)) all chapters

Definitions, theorems and lemmas

  • Algorithm 3.2

    Running error recurrence bound (Higham §3.3, Algorithm 3.2 core). Suppose e i is the partial dot-product error after i steps, sHat i is the computed partial sum after step i, and zHat i is the computed product at step i. If the local inverse-model derivation gives e_{i+1} = e_i - eps_i*sHat_i - delta_i*zHat_i with |eps_i| <= u, |delta_i| <= u, and e_0 = 0, then the final error is bounded by the source running accumulator: |e_n| <= u * sum_i (|sHat_i| + |zHat_i|). This theorem is the checked induction behind Algorithm 3.2. A concrete executable fl_runningDotProduct theorem still has to instantiate the local inverse-model hypotheses for every multiplication and addition.

    Lean statement
    theorem runningError_bound_from_local_errors (n : ℕ) (u : ℝ)
        (e : Fin (n + 1) → ℝ) (sHat zHat delta eps : Fin n → ℝ)
        (he0 : e 0 = 0)
        (hrec : ∀ i : Fin n,
          e i.succ = e i.castSucc - eps i * sHat i - delta i * zHat i)
        (hdelta : ∀ i, |delta i| ≤ u)
        (heps : ∀ i, |eps i| ≤ u) :
        |e (Fin.last n)| ≤ u * runningErrorMu n sHat zHat

    runningError_bound_from_local_errors · 1 more declaration under this item

  • Lemma 3.3

    Lean statement
    lemma gamma_mul (fp : FPModel) (j k : ℕ) (θj θk : ℝ)
        (hj  : |θj| ≤ gamma fp j)
        (hk  : |θk| ≤ gamma fp k)
        (hval : gammaValid fp (j + k)) :
        ∃ θ : ℝ, |θ| ≤ gamma fp (j + k) ∧ (1 + θj) * (1 + θk) = 1 + θ

    gamma_mul · 15 more declarations under this item

  • Lemma 3.4

    In scalar product form.

    Lean statement
    theorem prod_one_add_delta_eq_one_add_eta_bound_101 (n : ℕ) {u : ℝ}
        (hnpos : 0 < n) (delta : Fin n → ℝ)
        (hdelta : ∀ i : Fin n, |delta i| < u)
        (hnu : (n : ℝ) * u < (1 / 100 : ℝ)) :
        ∃ eta : ℝ,
          |eta| < (101 / 100 : ℝ) * (n : ℝ) * u ∧
            (∏ i : Fin n, (1 + delta i)) = 1 + eta

    prod_one_add_delta_eq_one_add_eta_bound_101 · 4 more declarations under this item

  • Lemma 3.5

    Complex addition error model (Higham Chapter 3, Lemma 3.5, addition case). The computed operation uses two rounded real additions and satisfies the source complex relative-error form with radius u.

    Lean statement
    theorem fl_complexAdd_rel_error_model (fp : FPModel) (x y : ℂ) :
        complexRelErrorModel (fl_complexAdd fp x y) (x + y) fp.u

    fl_complexAdd_rel_error_model · 3 more declarations under this item

  • Lemma 3.6

    Finite-sequence normwise form. For any matrix norm N satisfying nonnegativity, subadditivity, and submultiplicativity, component factor bounds N (Delta X_j) <= delta_j * N X_j imply N (prod_j (X_j + Delta X_j) - prod_j X_j) <= (prod_j (1 + delta_j) - 1) * prod_j N(X_j). The theorem uses non-strict inequalities, which are the repository's usual formal surface; the source's strict version follows by monotonic weakening in applications with strict hypotheses.

    Lean statement
    theorem matSeqProd_normwise_perturbation_bound (n m : ℕ)
        (N : (Fin n → Fin n → ℝ) → ℝ)
        (hN_nonneg : ∀ A, 0 ≤ N A)
        (hN_zero : N (fun _ _ => 0) ≤ 0)
        (hN_id : N (idMatrix n) ≤ 1)
        (hN_add : ∀ A B,
          N (fun i j => A i j + B i j) ≤ N A + N B)
        (hN_mul : ∀ A B, N (matMul n A B) ≤ N A * N B)
        (X ΔX : Fin m → Fin n → Fin n → ℝ) (δ : Fin m → ℝ)
        (hδ : ∀ r, 0 ≤ δ r)
        (hΔ : ∀ r, N (ΔX r) ≤ δ r * N (X r)) :
        N (fun i j =>
          matSeqProd n m (fun r i j => X r i j + ΔX r i j) i j -
            matSeqProd n m X i j) ≤
          (scalarSeqProd m (fun r => 1 + δ r) - 1) *
            scalarSeqProd m (fun r => N (X r))

    matSeqProd_normwise_perturbation_bound · 1 more declaration under this item

  • Lemma 3.7

    Concrete Frobenius/spectral instantiation. The sole perturbation hypothesis is the one printed in the source, ‖ΔX_j‖_F ≤ δ_j ‖X_j‖₂. In particular, no separate spectral perturbation bound is assumed: it is derived internally from ‖ΔX_j‖₂ ≤ ‖ΔX_j‖_F.

    Lean statement
    theorem lemma3_7_frobenius_spectral_perturbation_bound (n m : ℕ)
        (X ΔX : Fin m → Fin n → Fin n → ℝ) (δ : Fin m → ℝ)
        (hδ : ∀ r, 0 ≤ δ r)
        (hΔF : ∀ r, frobNorm (ΔX r) ≤ δ r * opNorm2 (X r)) :
        frobNorm (fun i j =>
          matSeqProd n m (fun r i j => X r i j + ΔX r i j) i j -
            matSeqProd n m X i j) ≤
          (scalarSeqProd m (fun r => 1 + δ r) - 1) *
            scalarSeqProd m (fun r => opNorm2 (X r))

    lemma3_7_frobenius_spectral_perturbation_bound · 1 more declaration under this item

  • Lemma 3.8

    Finite-sequence componentwise form. If each factor in a matrix product is perturbed componentwise as |ΔX_j| <= δ_j |X_j| with δ_j >= 0, then the whole product satisfies |prod_j (X_j + ΔX_j) - prod_j X_j| <= (prod_j (1 + δ_j) - 1) * prod_j |X_j| componentwise.

    Lean statement
    theorem matSeqProd_componentwise_perturbation_bound (n m : ℕ)
        (X ΔX : Fin m → Fin n → Fin n → ℝ) (δ : Fin m → ℝ)
        (hδ : ∀ r, 0 ≤ δ r)
        (hΔ : ∀ r i j, |ΔX r i j| ≤ δ r * |X r i j|) :
        ∀ i j,
          |matSeqProd n m (fun r i j => X r i j + ΔX r i j) i j -
            matSeqProd n m X i j| ≤
            (scalarSeqProd m (fun r => 1 + δ r) - 1) *
              matSeqProd n m (fun r => absMatrix n (X r)) i j

    matSeqProd_componentwise_perturbation_bound · 1 more declaration under this item

  • Lemma 3.9

    Componentwise bound. For the concrete routine fl(x - a(b^T x)), implemented as a rounded dot product, rounded scalar-vector multiply, and componentwise rounded subtraction, the error satisfies |Delta y| <= gamma_{n+3} (I + |a||b^T|)|x|.

    Lean statement
    theorem fl_rankOneUpdate_componentwise_error_bound (fp : FPModel) (n : ℕ)
        (a b x : Fin n → ℝ) (hγ : gammaValid fp (n + 3)) :
        ∀ i : Fin n,
          |fl_rankOneUpdate fp n a b x i - rankOneUpdateExact n a b x i| ≤
            gamma fp (n + 3) * rankOneUpdateAbsBudget n a b x i

    fl_rankOneUpdate_componentwise_error_bound · 2 more declarations under this item

Equations and other results

  • Equation (3.1)

    Dot-product local-factor expansion (Higham §3.1, equations (3.1)--(3.2)). For a positive-length left-to-right dot product, expose the actual local multiplication factors and local addition factors instead of immediately compressing them into gamma witnesses. The first product term carries every addition factor; term i.succ carries the suffix of addition factors from the step where that term enters the accumulator. This is the source-shaped expansion used before deriving the backward and forward dot-product error bounds.

    Lean statement
    theorem dotProduct_factor_expansion_succ (fp : FPModel) (n : ℕ)
        (x y : Fin (n + 1) → ℝ) :
        ∃ mulDelta : Fin (n + 1) → ℝ, ∃ addDelta : Fin n → ℝ,
          (∀ i, |mulDelta i| ≤ fp.u) ∧
          (∀ i, |addDelta i| ≤ fp.u) ∧
          fl_dotProduct fp (n + 1) x y =
            x 0 * y 0 * (1 + mulDelta 0) *
                (∏ i : Fin n, (1 + addDelta i)) +
              ∑ i : Fin n,
                x i.succ * y i.succ * (1 + mulDelta i.succ) *
                  sumSuffixErrorProduct n addDelta i

    dotProduct_factor_expansion_succ · 1 more declaration under this item

  • Equation (3.3)

    Dot product componentwise backward error (Higham §3.1, equation 3.3). The computed floating-point dot product satisfies: fl_dotProduct fp x y = ∑ i, x i * y i * (1 + η i) where each |η i| ≤ γ(n). This is the primary backward error result from which backward stability (3.4) and the forward bound (3.5) derive.

    Lean statement
    theorem dotProduct_backward_error (fp : FPModel) (n : ℕ)
        (x y : Fin n → ℝ) (hn : gammaValid fp n) :
        ∃ η : Fin n → ℝ,
          (∀ i, |η i| ≤ gamma fp n) ∧
          fl_dotProduct fp n x y = ∑ i : Fin n, x i * y i * (1 + η i)

    dotProduct_backward_error · 2 more declarations under this item

  • Equation (3.4)

    Fully permuted form of Higham (3.4). The permutation chooses the order in which the products enter the arbitrary summation tree. The resulting perturbations are transported back to the original coordinates, so the conclusion is stated for the original x and y, not for their reordered copies.

    Lean statement
    theorem sumTreeDotProduct_backward_stable_any_permuted_order
        (fp : FPModel) {n : ℕ} (t : SumTree n) (σ : Equiv.Perm (Fin n))
        (x y : Fin n → ℝ) (hγ : gammaValid fp n) :
        ∃ Δx Δy : Fin n → ℝ,
          (∀ i, |Δx i| ≤ gamma fp n * |x i|) ∧
          (∀ i, |Δy i| ≤ gamma fp n * |y i|) ∧
          fl_sumTreeDotProduct fp t (fun i => x (σ i)) (fun i => y (σ i)) =
            ∑ i : Fin n, (x i + Δx i) * y i ∧
          fl_sumTreeDotProduct fp t (fun i => x (σ i)) (fun i => y (σ i)) =
            ∑ i : Fin n, x i * (y i + Δy i)

    sumTreeDotProduct_backward_stable_any_permuted_order · 2 more declarations under this item

  • Equation (3.5)

    Dot product rounding error bound (Higham §3.1, equation 3.5). The computed floating-point dot product satisfies: |fl_dotProduct fp x y - ∑ i, x i * y i| ≤ γ(n) * ∑ i, |x i| * |y i|. Proof sketch: 1. For n = 0 the result is trivial. 2. For n = n'+1, extract mul rounding errors: fl_mul (x i) (y i) = x i * y i * (1 + δ i) with |δ i| ≤ u ≤ γ(1). 3. Apply fl_sum_error_init to the n' accumulated additions starting from fl_mul (x 0) (y 0) with initial-accumulator error Θ and per-term errors θ i, all bounded by γ(n'). 4. Combine each pair (δ i, Θ or θ i) via gamma_mul to get a single error η i with |η i| ≤ γ(n'+1) = γ(n). 5. Total error is ∑ x i * y i * η i; apply triangle inequality to get the bound.

    Lean statement
    theorem dotProduct_error_bound (fp : FPModel) (n : ℕ)
        (x y : Fin n → ℝ)
        (hn : gammaValid fp n) :
        |fl_dotProduct fp n x y - ∑ i : Fin n, x i * y i| ≤
          gamma fp n * ∑ i : Fin n, |x i| * |y i|

    dotProduct_error_bound · 2 more declarations under this item

  • Equation (3.6)

    Outer product forward error bound (Higham §3.1, equation 3.6). The computed outer product satisfies, componentwise: |Â - xyᵀ| ≤ u|xyᵀ|. Formally: for each entry (i, j), |fl_outerProduct fp x y i j - x i * y j| ≤ fp.u * |x i * y j|. Proof: by definition Âᵢⱼ = fl(xᵢ * yⱼ) = xᵢ * yⱼ * (1 + δᵢⱼ) with |δᵢⱼ| ≤ u, so Âᵢⱼ − xᵢyⱼ = xᵢyⱼ · δᵢⱼ, and |Âᵢⱼ − xᵢyⱼ| = |xᵢyⱼ| · |δᵢⱼ| ≤ u|xᵢyⱼ|.

    Lean statement
    theorem outerProduct_error_bound (fp : FPModel) (m n : ℕ)
        (x : Fin m → ℝ) (y : Fin n → ℝ) :
        ∀ i : Fin m, ∀ j : Fin n,
          |fl_outerProduct fp m n x y i j - x i * y j| ≤ fp.u * |x i * y j|

    outerProduct_error_bound · 2 more declarations under this item

  • Equation (3.7)

    Exact split of γ_n into its first-order unit-roundoff term plus the quadratic-and-higher rational remainder.

    Lean statement
    lemma gamma_eq_linear_plus_quadratic_remainder (fp : FPModel) (n : ℕ)
        (hn : gammaValid fp n) :
        gamma fp n =
          (n : ℝ) * fp.u + (((n : ℝ) * fp.u) ^ 2) /
            (1 - (n : ℝ) * fp.u)

    gamma_eq_linear_plus_quadratic_remainder · 2 more declarations under this item

  • Equation (3.9)

    Small-nu dot-product forward bound (Higham §3.4, equation (3.9)). For the repository's non-strict FPModel, the result is stated with <=. The source's displayed strict inequality follows in the usual nondegenerate strict-local-error regime.

    Lean statement
    theorem dotProduct_error_bound_101_succ (fp : FPModel) (n : ℕ)
        (x y : Fin (n + 1) → ℝ)
        (hu_pos : 0 < fp.u)
        (hnu : ((n + 1 : ℕ) : ℝ) * fp.u < (1 / 100 : ℝ)) :
        |fl_dotProduct fp (n + 1) x y - ∑ i : Fin (n + 1), x i * y i| ≤
          (101 / 100 : ℝ) * ((n + 1 : ℕ) : ℝ) * fp.u *
            ∑ i : Fin (n + 1), |x i| * |y i|

    dotProduct_error_bound_101_succ · 1 more declaration under this item

  • Equation (3.10)

    Stewart counter reciprocal rule: if c = <k> and u < 1, then 1/c = <k>.

    Lean statement
    lemma relErrorCounter_inv (fp : FPModel) (k : ℕ) (c : ℝ)
        (hc : relErrorCounter fp k c) (hu : fp.u < 1) :
        relErrorCounter fp k (1 / c)

    relErrorCounter_inv · 3 more declarations under this item

Problems and exercises

  • Problem 3.2

    All-positive-factor product form. If every exponent in Lemma 3.1 is +1, the product admits the stronger Kielbasinski--Schwetlick radius n*u/(1 - n*u/2) under the larger guard n*u < 2. This non-strict local-error variant matches the repository FPModel convention |delta_i| <= u; strictness of the final radius comes from 0 < u.

    Lean statement
    theorem prod_one_add_delta_eq_one_add_phi_bound_problem32 (n : ℕ) {u : ℝ}
        (hnpos : 0 < n) (hu_pos : 0 < u) (delta : Fin n → ℝ)
        (hdelta : ∀ i : Fin n, |delta i| ≤ u)
        (hnu : (n : ℝ) * u < (2 : ℝ)) :
        ∃ phi : ℝ,
          |phi| < ((n : ℝ) * u) / (1 - (1 / 2 : ℝ) * ((n : ℝ) * u)) ∧
            (∏ i : Fin n, (1 + delta i)) = 1 + phi

    prod_one_add_delta_eq_one_add_phi_bound_problem32 · 1 more declaration under this item

  • Problem 3.5

    Common left-factor backward error. For square nonsingular B, the componentwise forward-error matrix for fl(A*B) can be moved to the left factor: fl(A*B) = (A + DeltaA) * B, with the source-style componentwise bound |DeltaA| <= gamma_n * |A| * |B| * |B_inv|. This is the global backward-error result that complements the columnwise backward-error theorem above.

    Lean statement
    theorem matMul_backward_error_common_A_of_inverse (fp : FPModel) (n : ℕ)
        (A B B_inv : Fin n → Fin n → ℝ)
        (hn : gammaValid fp n) (hB : IsInverse n B B_inv) :
        ∃ ΔA : Fin n → Fin n → ℝ,
          (∀ i k,
            |ΔA i k| ≤
              gamma fp n *
                ∑ l : Fin n,
                  (∑ r : Fin n, |A i r| * |B r l|) * |B_inv l k|) ∧
          ∀ i j,
            fl_matMul fp n n n A B i j =
              ∑ k : Fin n, (A i k + ΔA i k) * B k j

    matMul_backward_error_common_A_of_inverse · 1 more declaration under this item

  • Problem 3.6

    Problem 3.6 square-root lower bound, pointwise form. If a relative componentwise backward-error radius epsilon is feasible and the source majorant entry g_ij is positive, then sqrt (1 + |r_ij| / g_ij) - 1 <= epsilon. Taking the maximum over all entries gives the displayed lower bound for the minimal feasible radius omega.

    Lean statement
    theorem matMulRelativeBackwardFeasible_sqrt_lower_bound_entry (m n p : ℕ)
        (A : Fin m → Fin n → ℝ) (B : Fin n → Fin p → ℝ)
        (C : Fin m → Fin p → ℝ) {epsilon : ℝ}
        (hepsilon : 0 ≤ epsilon)
        (hfeas : matMulRelativeBackwardFeasible m n p A B C epsilon)
        (i : Fin m) (j : Fin p)
        (hg : 0 < matMulRelativeMajorant m n p A B i j) :
        Real.sqrt
              (1 + |matMulResidual m n p A B C i j| /
                matMulRelativeMajorant m n p A B i j) -
            1 ≤
          epsilon

    matMulRelativeBackwardFeasible_sqrt_lower_bound_entry · 3 more declarations under this item

  • Problem 3.8

    Direct route. The route fl(fl(x*x) - fl(y*y)) has an absolute error bound proportional to |x*x| + |y*y|. This is the cancellation-sensitive majorant.

    Lean statement
    theorem fl_squareDiff_direct_error_bound (fp : FPModel)
        (hγ : gammaValid fp 2) (x y : ℝ) :
        |fl_squareDiff_direct fp x y - (x ^ 2 - y ^ 2)| ≤
          gamma fp 2 * (|x * x| + |y * y|)

    fl_squareDiff_direct_error_bound · 1 more declaration under this item

  • Problem 3.12

    Assume the quadrature weights and nodes are represented as floating-point inputs, the function values satisfy fhat_i = fl(f(x_i)) with |fhat_i - f_i| <= eta |f_i|, and the weighted sum is evaluated left-to-right. Then the computed quadrature value is bounded by the analytic quadrature error plus a finite-sum arithmetic budget: |I - Jhat| <= |I - J| + (eta + gamma_n * (1 + eta)) sum_i |w_i||f_i|. The first term is the mathematical quadrature error; the eta term is the function-evaluation error; the gamma_n term is the floating-point summation of the perturbed weighted values.

    Lean statement
    theorem fl_quadrature_error_bound_of_function_value_rel_error
        (fp : FPModel) (n : ℕ) (w f fhat : Fin n → ℝ) (I : ℝ)
        (hn : gammaValid fp n) {eta : ℝ} (_heta_nonneg : 0 ≤ eta)
        (hf : ∀ i : Fin n, |fhat i - f i| ≤ eta * |f i|) :
        |I - fl_quadrature fp n w fhat| ≤
          |I - quadratureRule n w f| +
            (eta + gamma fp n * (1 + eta)) *
              ∑ i : Fin n, |w i| * |f i|

    fl_quadrature_error_bound_of_function_value_rel_error

Chapter 4 · Summation all chapters

Definitions, theorems and lemmas

  • Algorithm 4.1

    A SumTree n performs exactly n − 1 additions.

    Lean statement
    lemma numAdds_eq (t : SumTree n) : t.numAdds + 1 = n

    numAdds_eq · 1 more declaration under this item

Equations and other results

  • Equation (4.2)

    General Algorithm 4.1 local-error identity (Higham §4.2, equation (4.2)). Any source-shaped contribution sum is exactly S_n - S_hat_n for the same tree.

    Lean statement
    theorem runningErrorContribution_eq_error (fp : FPModel)
        (t : SumTree n) (v : Fin n → ℝ) (e : ℝ)
        (hcontrib : runningErrorContribution fp t v e) :
        exactSum t v - eval fp t v = e

    runningErrorContribution_eq_error · 1 more declaration under this item

  • Equation (4.4)

    Recursive summation backward error (Higham §4.2, eq. 4.4). The computed recursive sum satisfies: fl_recursiveSum fp n v = ∑ i, v i * (1 + θ i) where each |θ i| ≤ γ(n - 1). Backward result: the computed sum is the exact sum of perturbed inputs vᵢ * (1 + θᵢ). The bound γ(n-1) is tight: no number xᵢ participates in more than n - 1 additions (Higham §4.2). The first step fl_add 0 (v 0) = v 0 is exact by fl_add_zero, leaving only n - 1 rounding steps; this is captured via fl_sum_error_tight.

    Lean statement
    theorem recursiveSum_backward_error (fp : FPModel) (n : ℕ) (v : Fin n → ℝ)
        (hn : gammaValid fp (n - 1)) :
        ∃ θ : Fin n → ℝ,
          (∀ i, |θ i| ≤ gamma fp (n - 1)) ∧
          fl_recursiveSum fp n v = ∑ i : Fin n, v i * (1 + θ i)

    recursiveSum_backward_error · 5 more declarations under this item

  • Equation (4.5)

    Higham's printed p. 83 increasing-order data have cancellation amplification exactly matching the ratio 1 + 6M in the nonnegative M regime.

    Lean statement
    theorem p91Increasing_heavyCancellationAtLeast {M : ℝ} (hM : 0 ≤ M) :
        HeavyCancellationAtLeast (p91IncreasingInput M) (1 + 6 * M)

    p91Increasing_heavyCancellationAtLeast · 5 more declarations under this item

  • Equation (4.6)

    Pairwise summation backward error (Higham §4.2). For n = 2^r inputs, pairwise summation satisfies: fl_pairwiseSum fp r v = ∑ i, v i * (1 + η i) where each |η i| ≤ γ(r). Each element takes part in exactly r additions; the backward error factor per element is therefore γ(r), not γ(n-1) as in recursive summation. Proof sketch: induction on r. - Base: no addition, so η ≡ 0 and γ(0) = 0. - Step: IH gives left and right halves each with error ≤ γ(r). The final fl_add introduces δ with |δ| ≤ u ≤ γ(1). gamma_mul combines each per-element γ(r) error with δ into γ(r+1).

    Lean statement
    theorem pairwiseSum_backward_error (fp : FPModel) (r : ℕ) (v : Fin (2 ^ r) → ℝ)
        (hr : gammaValid fp r) :
        ∃ η : Fin (2 ^ r) → ℝ,
          (∀ i, |η i| ≤ gamma fp r) ∧
          fl_pairwiseSum fp r v = ∑ i : Fin (2 ^ r), v i * (1 + η i)

    pairwiseSum_backward_error · 3 more declarations under this item

Problems and exercises

  • Problem 4.1

    One-signed data have condition number exactly one, provided the exact sum is nonzero.

    Lean statement
    theorem summationConditionNumber_eq_one_of_oneSigned {ι : Type*} [Fintype ι]
        (v : ι → ℝ) (hv : OneSigned v) (hsum : (∑ i, v i) ≠ 0) :
        summationConditionNumber v = 1

    summationConditionNumber_eq_one_of_oneSigned · 4 more declarations under this item

  • Problem 4.2

    Arbitrary-length IEEE-double finite recursive trace for Wilkinson's Problem 4.2 source family. Under the IEEE-double t = 53 instantiation and r <= 52, the concrete finite round-to-even recursive trace returns 2^r.

    Lean statement
    theorem wilkinsonProblem42_ieeeDouble_finiteRecursiveSum_eq_pow
        {r : ℕ} (hr : r ≤ 52) :
        finiteRoundToEvenRecursiveSum FloatingPointFormat.ieeeDoubleFormat
            (2 ^ r) (wilkinsonProblem42Vector 53 r) =
          (2 : ℝ) ^ r

    wilkinsonProblem42_ieeeDouble_finiteRecursiveSum_eq_pow · 2 more declarations under this item

  • Problem 4.3

    Source-shaped variable-gamma expansion for left-to-right recursive summation. For m + 2 inputs, the first exact zero-accumulator step means x₁ and x₂ share the same suffix of m + 1 rounded additions, while the later term x_{j+3} carries only the remaining m - j rounded additions.

    Lean statement
    theorem recursiveSum_problem43_variableGamma (fp : FPModel) (m : ℕ)
        (v : Fin (m + 2) → ℝ) (hvalid : gammaValid fp (m + 1)) :
        ∃ θ12 : ℝ, ∃ θ : Fin m → ℝ,
          |θ12| ≤ gamma fp (m + 1) ∧
          (∀ j : Fin m, |θ j| ≤ gamma fp (m - j.val)) ∧
          fl_recursiveSum fp (m + 2) v =
            (v 0 + v (Fin.succ (0 : Fin (m + 1)))) * (1 + θ12) +
              ∑ j : Fin m, v j.succ.succ * (1 + θ j)

    recursiveSum_problem43_variableGamma · 6 more declarations under this item

  • Problem 4.4

    Bidirectional packaged form of the exhaustive Problem 4.4 answer.

    Lean statement
    theorem problem44_outputs_exactly_Icc :
        (∀ xs : List Problem44Term,
            xs.Perm problem44Source → problem44Output xs ∈ Finset.Icc 0 10) ∧
          (∀ k : ℕ,
            k ∈ Finset.Icc 0 10 →
              ∃ xs : List Problem44Term,
                xs.Perm problem44Source ∧ problem44Output xs = k)

    problem44_outputs_exactly_Icc · 1 more declaration under this item

  • Problem 4.5

    Advantage of the positive side: its summation condition number is one whenever its exact partial sum is nonzero.

    Lean statement
    theorem plusMinusPositive_conditionNumber_eq_one {n : ℕ} (v : Fin n → ℝ)
        (hsum : plusMinusExactPositive n v ≠ 0) :
        summationConditionNumber (plusMinusPositive v) = 1

    plusMinusPositive_conditionNumber_eq_one · 2 more declarations under this item

  • Problem 4.7

    Formal answer to Problem 4.7: route (b) is the cancellation-aware denominator evaluation. Its proved standard-model error bound is controlled by a majorant invariant under a common limiting offset, unlike the route (a) and route (c) majorants displayed above.

    Lean statement
    theorem aitkenDenominator_recommended_route_b (fp : FPModel)
        (hγ : gammaValid fp 2) (alpha x0 x1 x2 : ℝ) :
        |fl_aitkenDenominatorB fp (alpha + x0) (alpha + x1) (alpha + x2) -
            aitkenDenominatorB (alpha + x0) (alpha + x1) (alpha + x2)| ≤
          gamma fp 2 * aitkenDenominatorBMajorant x0 x1 x2

    aitkenDenominator_recommended_route_b

  • Problem 4.8

    Once the product entering the logarithm has relative perturbation θ, a final logarithm perturbation η gives the exact error formula log(1+θ)+η.

    Lean statement
    theorem logExpProduct_final_error_eq
        {n : ℕ} (x : Fin n → ℝ) (θ η pHat result : ℝ)
        (hθpos : 0 < 1 + θ)
        (hp : pHat = Real.exp (∑ i : Fin n, x i) * (1 + θ))
        (hlog : result = Real.log pHat + η) :
        result - ∑ i : Fin n, x i = Real.log (1 + θ) + η

    logExpProduct_final_error_eq · 1 more declaration under this item

  • Problem 4.9

    Direct route error against the exact [a,b] grid, exposing the stored-step error.

    Lean statement
    theorem fl_gridDirect_error_bound (fp : FPModel)
        (a b hhat : ℝ) (n i : ℕ) (hγ : gammaValid fp 2) :
        |fl_gridDirect fp a hhat i - gridPointExact a b n i| ≤
          gamma fp 2 * (|a| + |(i : ℝ) * hhat|) +
            (i : ℝ) * |hhat - (b - a) / (n : ℝ)|

    fl_gridDirect_error_bound · 2 more declarations under this item

Chapter 5 · Polynomials and Horner's method all chapters

Definitions, theorems and lemmas

  • Algorithm 5.1

    Source-shaped a posteriori running bound. Under the inverse local Horner-step estimate (5.4), the final Algorithm 5.1 quantity bounds the actual Horner evaluation error.

    Lean statement
    theorem fl_hornerDesc_running_error_bound_of_inverseLocal
        (fp : FPModel) (x : ℝ) (coeffsDesc : List ℝ)
        (hlocal : hornerStepInverseLocalError fp x) :
        |fl_hornerDesc fp x coeffsDesc - polyDesc x coeffsDesc| ≤
          fl_hornerRunningBound fp x coeffsDesc

    fl_hornerDesc_running_error_bound_of_inverseLocal · 3 more declarations under this item

  • Algorithm 5.2

    End-to-end all-order identification for Algorithm 5.2: after the final factorial scaling, its Taylor-state output is exactly the formal derivative obtained by differentiating every Horner update. There are no order-specific premises.

    Lean statement
    theorem polyDescHigherDeriv_eq_hornerFormalDerivativeFunctionDesc
        (alpha : ℝ) (i : ℕ) (coeffsDesc : List ℝ) :
        polyDescHigherDeriv alpha i coeffsDesc =
          hornerFormalDerivativeFunctionDesc alpha coeffsDesc i

    polyDescHigherDeriv_eq_hornerFormalDerivativeFunctionDesc · 2 more declarations under this item

Equations and other results

  • Equation (5.1)

    Exact Horner evaluation is the displayed monomial polynomial (5.1), for descending coefficient lists.

    Lean statement
    theorem hornerDesc_eq_polyDesc (x : ℝ) (coeffsDesc : List ℝ) :
        hornerDesc x coeffsDesc = polyDesc x coeffsDesc

    hornerDesc_eq_polyDesc

  • Equation (5.2)

    Lean statement
    theorem fl_hornerFold_backward_error_coefficients
        (fp : FPModel) (x : ℝ) :
        ∀ (rest : List ℝ) (y : ℝ),
          gammaValid fp (2 * rest.length) →
          ∃ thetaY : ℝ, ∃ pairs : List (ℝ × ℝ),
            |thetaY| ≤ gamma fp (2 * rest.length) ∧
            pairs.map Prod.fst = rest ∧
            (∀ p ∈ pairs, |p.2| ≤ gamma fp (2 * rest.length)) ∧
            rest.foldl (fl_hornerStep fp x) y =
              y * (1 + thetaY) * x ^ rest.length +
                polyDescPairsPerturbed x pairs

    fl_hornerFold_backward_error_coefficients · 1 more declaration under this item

  • Equation (5.3)

    Higham (5.3), forward-error form following from the coefficientwise backward-error expansion (5.2).

    Lean statement
    theorem fl_hornerDesc_forward_error_bound
        (fp : FPModel) (x : ℝ) (coeffsDesc : List ℝ)
        (hvalid : gammaValid fp (2 * (coeffsDesc.length - 1))) :
        |fl_hornerDesc fp x coeffsDesc - polyDesc x coeffsDesc| ≤
          gamma fp (2 * (coeffsDesc.length - 1)) * polyDescAbs x coeffsDesc

    fl_hornerDesc_forward_error_bound · 3 more declarations under this item

  • Equation (5.4)

    Higham, 2nd ed., Chapter 5, Section 5.1, local Horner step model: one rounded Horner update is a rounded multiplication followed by a rounded addition, with each local relative error bounded by the unit roundoff.

    Lean statement
    theorem fl_hornerStep_unroll (fp : FPModel) (x y a : ℝ) :
        ∃ δmul δadd : ℝ,
          |δmul| ≤ fp.u ∧
          |δadd| ≤ fp.u ∧
          fl_hornerStep fp x y a =
            ((x * y) * (1 + δmul) + a) * (1 + δadd)

    fl_hornerStep_unroll · 2 more declarations under this item

  • Equation (5.5)

    Lean statement
    theorem highamBidiagonalEq55QuadraticRemainder_nonneg
        (fp : FPModel) (alpha : ℝ) (n : ℕ)
        (qhat : Fin n → ℝ) (i : Fin n) :
        0 ≤ highamBidiagonalEq55QuadraticRemainder fp alpha n qhat i

    highamBidiagonalEq55QuadraticRemainder_nonneg · 3 more declarations under this item

  • Equation (5.6)

    The convolution of two copies of the explicit upper-triangular inverse. It is the finite-sum bridge needed for the third matrix displayed below (5.6).

    Lean statement
    theorem highamBidiagonalUInv_square_entry
        (r : ℝ) (n : ℕ) (i j : Fin n) :
        (∑ k : Fin n,
          highamBidiagonalUInv r n i k * highamBidiagonalUInv r n k j) =
          if i.val ≤ j.val then
            ((j.val - i.val + 1 : ℕ) : ℝ) * r ^ (j.val - i.val)
          else 0

    highamBidiagonalUInv_square_entry · 7 more declarations under this item

  • Equation (5.7)

    Direct coupled backward-error form of Higham (5.7) for the first derivative: the rounded derivative output is the exact derivative of a coefficientwise-perturbed polynomial, with every coefficient perturbation bounded by gamma (2 * (coeffsDesc.length - 1)).

    Lean statement
    theorem fl_hornerDerivativeDesc_snd_backward_error_coefficients_coupled
        (fp : FPModel) (x : ℝ) (coeffsDesc : List ℝ)
        (hvalid : gammaValid fp (2 * (coeffsDesc.length - 1))) :
        ∃ pairs : List (ℝ × ℝ),
          pairs.map Prod.fst = coeffsDesc ∧
          (∀ p ∈ pairs,
            |p.2| ≤ gamma fp (2 * (coeffsDesc.length - 1))) ∧
          (fl_hornerDerivativeDesc fp x coeffsDesc).2 =
            polyDescPairsDerivPerturbed x pairs

    fl_hornerDerivativeDesc_snd_backward_error_coefficients_coupled · 4 more declarations under this item

  • Equation (5.8)

    Equation (5.8)'s displayed sum/product Newton form is equal to the standard nested evaluation recurrence immediately following the displayed formula.

    Lean statement
    theorem newtonForm_eq_newtonFormNested
        (x : ℝ) (coeffs nodes : List ℝ) :
        newtonForm x coeffs nodes = newtonFormNested x coeffs nodes

    newtonForm_eq_newtonFormNested

  • Equation (5.9)

    Scalar row version of Higham (5.9): one rounded divided-difference entry is the exact L_k row update multiplied by the local error factors from the two subtractions and the division. The denominator of the rounded division is kept as an explicit nonzero hypothesis, matching FPModel.model_div.

    Lean statement
    theorem fl_dividedDifferenceStep_entry_error_factors
        (fp : FPModel) (nodes coeffs : ℕ → ℝ) {k j : ℕ}
        (hj : k < j)
        (hden : nodes j - nodes (j - k - 1) ≠ 0)
        (hdenHat :
          fp.fl_sub (nodes j) (nodes (j - k - 1)) ≠ 0) :
        ∃ δnum δden δdiv : ℝ,
          |δnum| ≤ fp.u ∧ |δden| ≤ fp.u ∧ |δdiv| ≤ fp.u ∧
            fl_dividedDifferenceStep fp nodes coeffs k j =
              dividedDifferenceStep nodes coeffs k j *
                ((1 + δnum) / (1 + δden)) * (1 + δdiv)

    fl_dividedDifferenceStep_entry_error_factors · 3 more declarations under this item

  • Equation (5.11)

    Componentwise product perturbation bound for computed divided-difference columns. This is the finite-vector form of Higham (5.10)-(5.11): the computed column differs from the exact L_{m-1} ... L_0 f column by the gap between the rounded absolute product majorant and the exact absolute product majorant.

    Lean statement
    theorem fl_dividedDifferenceFiniteCoeffs_abs_sub_exact_le_absLProduct_gap_gamma3
        (fp : FPModel) (nodes f : ℕ → ℝ) {n : ℕ} (m : ℕ)
        (hden : ∀ k j, k < j → j < n + 1 →
          nodes j - nodes (j - k - 1) ≠ 0)
        (hdenHat : ∀ k j, k < j → j < n + 1 →
          fp.fl_sub (nodes j) (nodes (j - k - 1)) ≠ 0)
        (hγ : gammaValid fp 3) :
        ∀ i : Fin (n + 1),
          |fl_dividedDifferenceFiniteCoeffs fp nodes f n m i -
            dividedDifferenceFiniteCoeffs nodes f n m i| ≤
            dividedDifferenceAbsLProductAction nodes (gamma fp 3) n m
              (fun i : Fin (n + 1) => |f i.val|) i -
              dividedDifferenceAbsLProductAction nodes 0 n m
                (fun i : Fin (n + 1) => |f i.val|) i

    fl_dividedDifferenceFiniteCoeffs_abs_sub_exact_le_absLProduct_gap_gamma3 · 3 more declarations under this item

  • Equation (5.14)

    The multiplication count is not merely asymptotic: it is exactly 2⌊√n⌋ for every degree n.

    Lean statement
    theorem higham5_ps_matrix_multiplications_exact (n : ℕ) :
        higham5PSMatrixMultiplications n = 2 * Nat.sqrt n

    higham5_ps_matrix_multiplications_exact · 4 more declarations under this item

Problems and exercises

  • Problem 5.2

    The exact beginner power-building loop evaluates the same ascending polynomial as the displayed monomial formula.

    Lean statement
    theorem beginnerPowerEvalAsc_eq_polyAsc
        (x : ℝ) (coeffsAsc : List ℝ) :
        beginnerPowerEvalAsc x coeffsAsc = polyAsc x coeffsAsc

    beginnerPowerEvalAsc_eq_polyAsc · 1 more declaration under this item

  • Problem 5.3

    Exact even/odd decomposition p(x) = p_even(x^2) + x*p_odd(x^2), for ascending coefficients.

    Lean statement
    theorem polyAsc_evenOdd_split (x : ℝ) :
        ∀ coeffsAsc : List ℝ,
          polyAsc x coeffsAsc =
            polyAsc (x * x) (evenCoeffsAsc coeffsAsc) +
              x * polyAsc (x * x) (oddCoeffsAsc coeffsAsc)

    polyAsc_evenOdd_split · 2 more declarations under this item

  • Problem 5.5

    Root-product evaluation has exactly two relative-error factors per root: one for forming x - x_i and one for multiplying it into the accumulator.

    Lean statement
    theorem fl_rootProductEvalFrom_exists_relErrorCounter
        (fp : FPModel) (x : ℝ) :
        ∀ (roots : List ℝ) (acc : ℝ),
          ∃ c : ℝ,
            relErrorCounter fp (2 * roots.length) c ∧
              fl_rootProductEvalFrom fp x roots acc =
                rootProductEvalFrom x roots acc * c

    fl_rootProductEvalFrom_exists_relErrorCounter · 1 more declaration under this item

Chapter 6 · Norms all chapters

Definitions, theorems and lemmas

  • Lemma 6.3

    Lemma 6.3 foundation, concrete matrix form: for unit source and target vectors there is a rank-one matrix with local mixed subordinate matrix norm value 1 mapping the source vector to the target vector.

    Lean statement
    theorem exists_rankOneCMatrix_isMixedSubordinateMatrixNormValue_one
        {n m : ℕ} {να : CVec n → ℝ} {νβ : CVec m → ℝ}
        (hα : IsComplexVectorNorm να) (hβ : IsComplexVectorNorm νβ)
        {x : CVec n} {y : CVec m} (hx : να x = 1) (hy : νβ y = 1) :
        ∃ A : CMatrix m n,
          IsMixedSubordinateMatrixNormValue να νβ A 1 ∧
            complexMatrixVecMul A x = y

    exists_rankOneCMatrix_isMixedSubordinateMatrixNormValue_one · 2 more declarations under this item

  • Lemma 6.6

    Lemma 6.6 (a)(i). If ‖a_j‖₂ ≤ ‖b_j‖₂ for every column j, then ‖A‖_F ≤ ‖B‖_F.

    Lean statement
    theorem lemma66_a_frobenius_le {m n : ℕ} (A B : CMatrix m n)
        (h : ∀ j, lemma66_colNorm2 A j ≤ lemma66_colNorm2 B j) :
        complexMatrixFrobenius A ≤ complexMatrixFrobenius B

    lemma66_a_frobenius_le · 9 more declarations under this item

  • Theorem 6.2

    The easy direction of Higham, Theorem 6.2: monotone vector norms are absolute.

    Lean statement
    theorem absolute_of_monotone_complexVectorNorm {n : ℕ} {ν : CVec n → ℝ}
        (hmono : IsMonotoneComplexVectorNorm ν) :
        IsAbsoluteComplexVectorNorm ν

    absolute_of_monotone_complexVectorNorm · 2 more declarations under this item

  • Theorem 6.4

    Theorem 6.4 with the printed ambient-radius normalization. Along any eventually positive relative radius rho -> 0, the actual supremum of (||B-S||/||S||) / rho over ||D|| <= rho*||A|| tends to ||A|| * ||S||. The sharp perturbation is chosen on the boundary d = rho*a; perturbed right inverses and both first-order norm witnesses are constructed internally.

    Lean statement
    theorem mixedInverseAmbientRelativeAmplificationRadiusSup_tendsto_conditionNumberProduct_of_positive_radii
        {ι : Type*} {l : Filter ι}
        {n : ℕ} {να νβ : CVec n → ℝ} {A S : ComplexVectorMap n n}
        {a s : ℝ} {rho : ι → ℝ} (hn : 0 < n)
        (hα : IsComplexVectorNorm να) (hβ : IsComplexVectorNorm νβ)
        (hAlin : IsComplexVectorMapLinear A)
        (hSlin : IsComplexVectorMapLinear S)
        (hS_left : ∀ x : CVec n, S (A x) = x)
        (hapos : 0 < a) (hspos : 0 < s)
        (hA : IsMixedSubordinateNormValue να νβ A a)
        (hS : IsMixedSubordinateNormValue νβ να S s)
        (hrho_pos : Filter.Eventually (fun i => 0 < rho i) l)
        (hrho : Filter.Tendsto rho l (nhds 0)) :
        IsMixedConditionNumberProductValue να νβ A S (a * s) ∧
          Filter.Tendsto
            (fun i => mixedInverseAmbientRelativeAmplificationRadiusSup
              να νβ A S a s (rho i)) l (nhds (a * s))

    mixedInverseAmbientRelativeAmplificationRadiusSup_tendsto_conditionNumberProduct_of_positive_radii

  • Theorem 6.5

    Concrete-matrix reciprocal condition-number form of Theorem 6.5. This is the source-facing matrix wrapper around the local Gastinel-Kahan theorem.

    Lean statement
    theorem complexMatrix_relativeSingularDistance_min_eq_inv_conditionNumberProduct
        {n : ℕ} {να νβ : CVec n → ℝ} {A Ainv : CMatrix n n}
        {a s : ℝ} (hα : IsComplexVectorNorm να) (hβ : IsComplexVectorNorm νβ)
        (ha : 0 < a) (hs : 0 < s)
        (hAinv_inv : IsComplexMatrixInverse A Ainv)
        (hA : IsMixedSubordinateMatrixNormValue να νβ A a)
        (hAinv : IsMixedSubordinateMatrixNormValue νβ να Ainv s) :
        ∃ κ : ℝ,
          IsMixedConditionNumberProductValue να νβ
            (complexMatrixVecMul A) (complexMatrixVecMul Ainv) κ ∧
            IsMinimumMixedRelativeSingularDistance να νβ
              (complexMatrixVecMul A) a κ⁻¹

    complexMatrix_relativeSingularDistance_min_eq_inv_conditionNumberProduct

Equations and other results

  • Equation (6.1)

    Finite complex Hölder inequality for the source-facing L^p family. This covers finite conjugate exponents; endpoint cases are handled by separate 1/∞ lemmas.

    Lean statement
    theorem complexVecLpNorm_holder {n : ℕ} {p q : ℝ}
        (hpq : p.HolderConjugate q) (a x : CVec n) :
        ‖∑ i : Fin n, a i * x i‖ ≤
          complexVecLpNorm (ENNReal.ofReal q) a * complexVecLpNorm (ENNReal.ofReal p) x

    complexVecLpNorm_holder · 1 more declaration under this item

  • Equation (6.2)

    General normed-space form of Higham's duality theorem: the canonical embedding into the continuous double dual preserves the norm.

    Lean statement
    theorem higham6_dual_of_dual_norm_eq_original
        {𝕜 E : Type*} [RCLike 𝕜]
        [SeminormedAddCommGroup E] [NormedSpace 𝕜 E] (x : E) :
        ‖NormedSpace.inclusionInDoubleDual 𝕜 E x‖ = ‖x‖

    higham6_dual_of_dual_norm_eq_original · 1 more declaration under this item

  • Equation (6.3)

    Hahn-Banach norming functional for a unit vector in the abstract norm ν.

    Lean statement
    theorem exists_normingFunctionalAt_of_unit_vector (hν : IsComplexVectorNorm ν)
        {x : CVec n} (hx : ν x = 1) :
        ∃ φ : CVec n → ℂ, IsNormingFunctionalAt ν x φ

    exists_normingFunctionalAt_of_unit_vector

  • Equation (6.5)

    Lean statement
    theorem complexMatrixOp2_eq_top_singularValue {m n : ℕ}
        (hn : 0 < n) (A : CMatrix m n) :
        complexMatrixOp2 A =
          complexMatrixSingularValue A ⟨0, hn⟩

    complexMatrixOp2_eq_top_singularValue

  • Equation (6.9)

    Upper-bound skeleton: if S has mixed subordinate value s as a β -> α map and Δ has α -> β bound 1, then S ∘ Δ ∘ S has β -> α bound s^2.

    Lean statement
    theorem mixedSubordinate_inverseSandwich_bound
        {n : ℕ} {να νβ : CVec n → ℝ} {S Δ : ComplexVectorMap n n} {s : ℝ}
        (hs0 : 0 ≤ s)
        (hS : IsMixedSubordinateNormValue νβ να S s)
        (hΔ : MixedSubordinateBound να νβ Δ 1) :
        MixedSubordinateBound νβ να
          (complexVectorMapComp S (complexVectorMapComp Δ S)) (s ^ 2)

    mixedSubordinate_inverseSandwich_bound

  • Equation (6.14)

    Local Schneider-Strang comparison formula. If the two vector-ratio maxima exist, then the corresponding maximum matrix-norm ratio is their product.

    Lean statement
    theorem schneiderStrang_mixedSubordinateMatrixNormRatio_isMax
        {m n : ℕ} (hn : 0 < n)
        {ναSrc νβSrc : CVec n → ℝ} {ναTgt νβTgt : CVec m → ℝ}
        (hαSrc : IsComplexVectorNorm ναSrc) (hβSrc : IsComplexVectorNorm νβSrc)
        (hαTgt : IsComplexVectorNorm ναTgt) (hβTgt : IsComplexVectorNorm νβTgt)
        {cTgt cSrc : ℝ}
        (hTgt : IsMaxVectorNormRatioValue ναTgt νβTgt cTgt)
        (hSrc : IsMaxVectorNormRatioValue νβSrc ναSrc cSrc) :
        IsMaxMixedSubordinateMatrixNormRatioValue ναSrc ναTgt νβSrc νβTgt
          (cTgt * cSrc)

    schneiderStrang_mixedSubordinateMatrixNormRatio_isMax · 1 more declaration under this item

  • Equation (6.15)

    Sharp finite square matrix p/q ratio: max_{A != 0} ||A||_p / ||A||_q = n^|1/p - 1/q|, stated for the local mixed-subordinate matrix norm-value API.

    Lean statement
    theorem complexMatrixLpNorm_pq_ratio_isMax
        {n : ℕ} (hn : 0 < n) {p q : ℝ} (hp : 1 ≤ p) (hq : 1 ≤ q) :
        IsMaxMixedSubordinateMatrixNormRatioValue
          (complexVecLpNorm (n := n) (ENNReal.ofReal p))
          (complexVecLpNorm (n := n) (ENNReal.ofReal p))
          (complexVecLpNorm (n := n) (ENNReal.ofReal q))
          (complexVecLpNorm (n := n) (ENNReal.ofReal q))
          ((n : ℝ) ^ |p⁻¹ - q⁻¹|)

    complexMatrixLpNorm_pq_ratio_isMax · 5 more declarations under this item

  • Table 6.1

    Finite vector norm monotonicity: if 1 <= q <= p, then ||x||_p <= ||x||_q. Together with complexVecLpNorm_le_card_rpow_mul_complexVecLpNorm_of_exponent_le, this is the vector-level norm equivalence content behind Higham equation (6.4).

    Lean statement
    theorem complexVecLpNorm_le_complexVecLpNorm_of_exponent_le
        {n : ℕ} {p q : ℝ} (hq : 1 ≤ q) (hqp : q ≤ p) (x : CVec n) :
        complexVecLpNorm (ENNReal.ofReal p) x ≤
          complexVecLpNorm (ENNReal.ofReal q) x

    complexVecLpNorm_le_complexVecLpNorm_of_exponent_le · 2 more declarations under this item

Chapter 7 · Perturbation theory for linear systems all chapters

  • Corollary 7.6

    Higham, 2nd ed., Chapter 7, Corollary 7.6 / equation (7.23), in the repository's explicit inverse-Gram and sInf model: the source diagonal scaling D* = diag(a_jj^(-1/2)) gives a two-sided SPD operator-2 condition product at most n times the infimum over reciprocal diagonal two-sided scalings of DAD.

    Lean statement
    theorem corollary7_6_cholesky_scaled_cond_le_card_sInf_symmetric_scalings
        {n : ℕ} (hn : 0 < n)
        (A R Rinv : Fin n → Fin n → ℝ)
        (hGram : ∀ i j : Fin n, (∑ k : Fin n, R k i * R k j) = A i j)
        (hGramDiag : ∀ j : Fin n, (∑ k : Fin n, R k j * R k j) = A j j)
        (hdiag : ∀ j : Fin n, 0 < A j j) :
        ch7SymmetricOp2ScaledCond A (ch7CholeskyInverseGram Rinv)
            (ch7SymmetricDiagEquilibratingScale2 A)
            (ch7SymmetricDiagEquilibratingInvScale2 A) ≤
          (n : ℝ) *
            sInf (ch7SymmetricOp2ScaledCondSet A (ch7CholeskyInverseGram Rinv))

    corollary7_6_cholesky_scaled_cond_le_card_sInf_symmetric_scalings · 10 more declarations under this item

  • Lemma 7.9

    Componentwise core: if ω(E|x̂|+f) bounds the residual componentwise, then ω |A⁻¹|(E|x̂|+f) bounds |A⁻¹||r|.

    Lean statement
    theorem lemma7_9_componentwise_bound (n : ℕ)
        (A A_inv : Fin n → Fin n → ℝ) (y b : Fin n → ℝ)
        (E : Fin n → Fin n → ℝ) (f : Fin n → ℝ) (ω : ℝ)
        (hωres : ∀ j, |residualVec n A y b j| ≤
          ω * (∑ k : Fin n, E j k * |y k| + f j)) :
        ∀ i, ch7ResidualImage n A A_inv y b i ≤
          ω * ch7AmplifiedRhsEF n A_inv E f y i

    lemma7_9_componentwise_bound · 2 more declarations under this item

  • Theorem 7.1

    Arbitrary subordinate-norm Rigal-Gaches wrapper over complex matrices.

    Lean statement
    theorem theorem7_1_subordinate
        {n : ℕ} (hn : 0 < n) {ν : CVec n → ℝ} (hν : IsComplexVectorNorm ν)
        {A E : CMatrix n n} {y b f : CVec n} {e ε : ℝ}
        (hε : 0 ≤ ε)
        (hE : IsMixedSubordinateMatrixNormValue ν ν E e) :
        (ν (fun i => b i - complexMatrixVecMul A y i) ≤
          ε * (e * ν y + ν f)) ↔
        (∃ ΔA : CMatrix n n, ∃ Δb : CVec n,
          MixedSubordinateMatrixBound ν ν ΔA (ε * e) ∧
          ν Δb ≤ ε * ν f ∧
          complexMatrixVecMul (fun i j => A i j + ΔA i j) y =
            fun i => b i + Δb i)

    theorem7_1_subordinate · 7 more declarations under this item

  • Theorem 7.2

    Higham Theorem 7.2 / equation (7.4) in arbitrary subordinate-norm form over complex matrices. If Ax = b, (A + ΔA)y = b + Δb, ‖ΔA‖ ≤ ε ‖E‖, ‖Δb‖ ≤ ε ‖f‖, and ε ‖A⁻¹‖ ‖E‖ < 1, then ‖x-y‖ / ‖x‖ ≤ ε / (1 - ε ‖A⁻¹‖ ‖E‖) * (‖A⁻¹‖ ‖f‖ / ‖x‖ + ‖A⁻¹‖ ‖E‖).

    Lean statement
    theorem theorem7_2_subordinate_forward_error_bound
        {n : ℕ} (hn : 0 < n) {ν : CVec n → ℝ} (hν : IsComplexVectorNorm ν)
        {A Ainv E ΔA : CMatrix n n}
        {x y b f Δb : CVec n} {ε e s : ℝ}
        (hε : 0 ≤ ε)
        (hE : IsMixedSubordinateMatrixNormValue ν ν E e)
        (hAinv : IsMixedSubordinateMatrixNormValue ν ν Ainv s)
        (hΔA : MixedSubordinateMatrixBound ν ν ΔA (ε * e))
        (hΔb : ν Δb ≤ ε * ν f)
        (hInv : IsComplexMatrixLeftInverse A Ainv)
        (hAx : complexMatrixVecMul A x = b)
        (hPerturbed : complexMatrixVecMul (fun i j => A i j + ΔA i j) y =
          fun i => b i + Δb i)
        (hεse : ε * s * e < 1) (hx : 0 < ν x) :
        ν (fun i => x i - y i) / ν x ≤
          ε / (1 - ε * s * e) * (s * (ν f / ν x) + s * e)

    theorem7_2_subordinate_forward_error_bound

  • Theorem 7.3

    Oettli–Prager theorem (Higham Theorem 7.3, full characterization). The componentwise backward error ω(y) := min{ε : ∃ ΔA, Δb with |ΔA| ≤ εE, |Δb| ≤ εf, (A+ΔA)y = b+Δb} satisfies: ω(y) = max_i |r_i| / (E|y| + f)_i. Here we state the equivalence: |r| ≤ ε(E|y| + f) if and only if such ΔA, Δb exist.

    Lean statement
    theorem oettli_prager (n : ℕ)
        (A : Fin n → Fin n → ℝ) (y b : Fin n → ℝ)
        (E : Fin n → Fin n → ℝ) (f : Fin n → ℝ)
        (ε : ℝ) (hε : 0 ≤ ε)
        (hE : ∀ i j, 0 ≤ E i j) (hf : ∀ i, 0 ≤ f i) :
        (∀ i, |residualVec n A y b i| ≤
          ε * (∑ j : Fin n, E i j * |y j| + f i)) ↔
        (∃ (ΔA : Fin n → Fin n → ℝ) (Δb : Fin n → ℝ),
          (∀ i j, |ΔA i j| ≤ ε * E i j) ∧
          (∀ i, |Δb i| ≤ ε * f i) ∧
          (∀ i, ∑ j : Fin n, (A i j + ΔA i j) * y j = b i + Δb i))

    oettli_prager · 3 more declarations under this item

  • Theorem 7.4

    Higham Theorem 7.4 / equation (7.10) in arbitrary absolute-norm form over complex matrices. If Ax = b, (A + ΔA)y = b + Δb, |ΔA| <= ε |E|, |Δb| <= ε |f|, and ε || |A⁻¹| |E| || < 1 in an absolute norm ν, then ν (x-y) / ν x <= ε / (1 - ε || |A⁻¹| |E| ||) * ν (|A⁻¹| (|E| |x| + |f|)) / ν x.

    Lean statement
    theorem theorem7_4_absolute_forward_error_bound
        {n : ℕ} (hn : 0 < n) {ν : CVec n → ℝ} (hν : IsComplexVectorNorm ν)
        (habs : IsAbsoluteComplexVectorNorm ν)
        {A Ainv E ΔA : CMatrix n n}
        {x y b f Δb : CVec n} {ε m : ℝ}
        (hε : 0 ≤ ε)
        (hM : IsMixedSubordinateMatrixNormValue ν ν
          (complexMatrixMul (complexAbsMatrix Ainv) (complexAbsMatrix E)) m)
        (hΔA : ∀ i j, ‖ΔA i j‖ ≤ ε * ‖E i j‖)
        (hΔb : ∀ i, ‖Δb i‖ ≤ ε * ‖f i‖)
        (hInv : IsComplexMatrixLeftInverse A Ainv)
        (hAx : complexMatrixVecMul A x = b)
        (hPerturbed : complexMatrixVecMul (fun i j => A i j + ΔA i j) y =
          fun i => b i + Δb i)
        (hεm : ε * m < 1) (hx : 0 < ν x) :
        ν (fun i => x i - y i) / ν x ≤
          ε / (1 - ε * m) *
            (ν (complexMatrixVecMul (complexAbsMatrix Ainv)
                  (complexVecAdd
                    (complexMatrixVecMul (complexAbsMatrix E) (complexAbsVec x))
                    (complexAbsVec f))) / ν x)

    theorem7_4_absolute_forward_error_bound

  • Theorem 7.5

    p = 1 minimum-attainment form over all reciprocal right diagonal scalings in the explicit Aplus model. The equilibrating column scaling is a genuine least element of the condition-product value set, not only an infimum value.

    Lean statement
    theorem theorem7_5_p1_column_equilibration_isLeast_right_scalings {m n : ℕ}
        (A : Fin m → Fin n → ℝ) (Aplus : Fin n → Fin m → ℝ)
        (hcol : ∀ j : Fin n, 0 < ch7RectColumnNorm1 A j) :
        IsLeast (ch7OneNormRightScaledCondSet A Aplus)
          (ch7OneNormRightScaledCond A Aplus
            (ch7ColumnEquilibratingScale1 A)
            (fun j : Fin n => ch7RectColumnNorm1 A j))

    theorem7_5_p1_column_equilibration_isLeast_right_scalings · 98 more declarations under this item

  • Theorem 7.7

    Theorem 7.7 (Stewart and Sun), source-shaped finite Frobenius scaling package: the canonical diagonal diag((‖b_j‖₂ / ‖a_j‖₂)^(1/2)) attains the lower bound Σ_j ‖a_j‖₂ ‖b_j‖₂, and every inverse diagonal pair is bounded below by it.

    Lean statement
    theorem theorem7_7_stewart_sun_frobenius_scaling {n : ℕ}
        (A A_inv : Fin n → Fin n → ℝ)
        (hcol : ∀ j : Fin n, 0 < ch7ColumnNorm2 A j)
        (hrow : ∀ j : Fin n, 0 < ch7InverseRowNorm2 A_inv j) :
        (∀ d dInv : Fin n → ℝ,
          (∀ j : Fin n, d j * dInv j = 1) →
            ch7StewartSunFrobeniusValue A A_inv ≤
              ch7FrobeniusRightScaledCond A A_inv d dInv) ∧
        ch7FrobeniusRightScaledCond A A_inv
          (ch7StewartSunScale A A_inv) (ch7StewartSunInvScale A A_inv) =
            ch7StewartSunFrobeniusValue A A_inv

    theorem7_7_stewart_sun_frobenius_scaling · 2 more declarations under this item

Chapter 26 · Automatic error analysis all chapters

  • Equation (26.6)

    Consequently, the stable branch in (26.6) solves the quadratic for w^3 when its radicand is nonnegative.

    Lean statement
    theorem stableCubicWCube_quadratic (p q : ℝ) (h : 0 ≤ cubicRadicand p q) :
        stableCubicWCube p q ^ 2 + q * stableCubicWCube p q - p ^ 3 / 27 = 0

    stableCubicWCube_quadratic · 2 more declarations under this item

  • Equation (26.8)

    A linear functional on a finite real coordinate space is exactly the sum of its coordinate derivatives.

    Lean statement
    theorem linearizedForwardError26_8_eq {N : Nat}
        (derivative : (Fin N → ℝ) →L[ℝ] ℝ)
        (delta : Fin N -> Real) :
        linearizedForwardError26_8 derivative delta = derivative delta

    linearizedForwardError26_8_eq · 2 more declarations under this item

Chapter 27 · Software issues in floating point all chapters

  • Equation (27.1)

    Equation (27.1) as the printed complex identity. The branch assumption c ≠ 0 is the explicit domain condition for forming d/c; the source chooses this branch when |c| ≥ |d| and uses the symmetric branch otherwise.

    Lean statement
    theorem higham27_eq27_1_smith_complex_division (a b c d : ℝ) (hc : c ≠ 0) :
        (a + b * Complex.I) / (c + d * Complex.I) =
          ⟨smithDivReal a b c d, smithDivImag a b c d⟩

    higham27_eq27_1_smith_complex_division