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
Athat makeyan 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 → η ≤ chigham_
lemma_ · 6 more declarations under this item1_ 1_ operator2_ predicate
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_ · 3 more declarations under this item1_ rel Error_ bounds Problem 1.4
Correctness of the stable square-root formula when
0 <= aand 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 bcomplex
Sqrt · 2 more declarations under this itemStable_ nonneg A_ sq 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)log
One · 5 more declarations under this itemPlus Compensated Exact_ eq_ log_ one_ add Problem 1.9
A two-product determinant evaluated as
fl(fl(a11*a22) - fl(a21*a12))has absolute error bounded bygamma_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 a22fl
Det2x2_ · 3 more declarations under this itemerror_ le_ gamma3 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 xfl
Sample · 1 more declaration under this itemVariance Two Pass_ rel Error_ le_ linear_ u_ add_ problem110_ remainder
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 δnearest
Rounding · 2 more declarations under this itemTo Finite_ signed Rel Error Witness_ lt_ of_ finite Normal Range 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_ · 3 more declarations under this itemtheorem2_ 3_ nearest_ finite 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-yis 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)ferguson
Magnitude · 2 more declarations under this itemExponent Condition Le_ sub_ finite System 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 - yfinite
Round · 1 more declaration under this itemTo Even Op_ sub_ finite System_ eq_ exact_ of_ sterbenz Ratio Condition Le
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 yEquation (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 + δ)finite
Round · 1 more declaration under this itemTo Even Sqrt_ standard Model_ lt_ of_ finite Normal Range 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 ckahan
Heron · 2 more declarations under this itemArea_ sq_ eq_ heron Radicand_ of_ kahan Ordered Triangle Sides 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 δ ηfinite
Round To Even Op_ strict Additive Underflow Model_ normal_ branch_ of_ finite Normal Range
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 iis the partial dot-product error afteristeps,sHat iis the computed partial sum after stepi, andzHat iis the computed product at stepi. If the local inverse-model derivation givese_{i+1} = e_i - eps_i*sHat_i - delta_i*zHat_iwith|eps_i| <= u,|delta_i| <= u, ande_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 executablefl_runningDotProducttheorem 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 zHatrunning
Error_ · 1 more declaration under this itembound_ from_ local_ errors 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 itemLemma 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 + etaprod_
one_ · 4 more declarations under this itemadd_ delta_ eq_ one_ add_ eta_ bound_ 101 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.ufl_
complex · 3 more declarations under this itemAdd_ rel_ error_ model Lemma 3.6
Finite-sequence normwise form. For any matrix norm
Nsatisfying nonnegativity, subadditivity, and submultiplicativity, component factor boundsN (Delta X_j) <= delta_j * N X_jimplyN (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))mat
Seq · 1 more declaration under this itemProd_ normwise_ perturbation_ bound 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_ · 1 more declaration under this itemfrobenius_ spectral_ perturbation_ bound 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 jmat
Seq · 1 more declaration under this itemProd_ componentwise_ perturbation_ bound 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 ifl_
rank · 2 more declarations under this itemOne Update_ componentwise_ error_ bound
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
gammawitnesses. The first product term carries every addition factor; termi.succcarries 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 idot
Product_ · 1 more declaration under this itemfactor_ expansion_ succ 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)dot
Product_ · 2 more declarations under this itembackward_ error 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
xandy, 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)sum
Tree · 2 more declarations under this itemDot Product_ backward_ stable_ any_ permuted_ order 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|dot
Product_ · 2 more declarations under this itemerror_ bound 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|outer
Product_ · 2 more declarations under this itemerror_ bound Equation (3.7)
Exact split of
γ_ninto 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_ · 2 more declarations under this itemlinear_ plus_ quadratic_ remainder Equation (3.9)
Small-
nudot-product forward bound (Higham §3.4, equation (3.9)). For the repository's non-strictFPModel, 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|dot
Product_ · 1 more declaration under this itemerror_ bound_ 101_ succ Equation (3.10)
Stewart counter reciprocal rule: if
c = <k>andu < 1, then1/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)rel
Error · 3 more declarations under this itemCounter_ inv
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 radiusn*u/(1 - n*u/2)under the larger guardn*u < 2. This non-strict local-error variant matches the repositoryFPModelconvention|delta_i| <= u; strictness of the final radius comes from0 < 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 + phiprod_
one_ · 1 more declaration under this itemadd_ delta_ eq_ one_ add_ phi_ bound_ problem32 Problem 3.5
Common left-factor backward error. For square nonsingular
B, the componentwise forward-error matrix forfl(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 jmat
Mul_ · 1 more declaration under this itembackward_ error_ common_ A_ of_ inverse Problem 3.6
Problem 3.6 square-root lower bound, pointwise form. If a relative componentwise backward-error radius
epsilonis feasible and the source majorant entryg_ijis positive, thensqrt (1 + |r_ij| / g_ij) - 1 <= epsilon. Taking the maximum over all entries gives the displayed lower bound for the minimal feasible radiusomega.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 ≤ epsilonmat
Mul · 3 more declarations under this itemRelative Backward Feasible_ sqrt_ lower_ bound_ entry 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_
square · 1 more declaration under this itemDiff_ direct_ error_ bound 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; theetaterm is the function-evaluation error; thegamma_nterm 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|
Chapter 4 · Summation all chapters
Definitions, theorems and lemmas
Algorithm 4.1
A
SumTree nperforms exactlyn − 1additions.Lean statement
lemma numAdds_eq (t : SumTree n) : t.numAdds + 1 = nnum
Adds_ · 1 more declaration under this itemeq
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_nfor 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 = erunning
Error · 1 more declaration under this itemContribution_ eq_ error 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 inputsvᵢ * (1 + θᵢ). The bound γ(n-1) is tight: no number xᵢ participates in more than n - 1 additions (Higham §4.2). The first stepfl_add 0 (v 0) = v 0is exact byfl_add_zero, leaving only n - 1 rounding steps; this is captured viafl_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)recursive
Sum_ · 5 more declarations under this itembackward_ error Equation (4.5)
Higham's printed p. 83 increasing-order data have cancellation amplification exactly matching the ratio
1 + 6Min the nonnegativeMregime.Lean statement
theorem p91Increasing_heavyCancellationAtLeast {M : ℝ} (hM : 0 ≤ M) : HeavyCancellationAtLeast (p91IncreasingInput M) (1 + 6 * M)p91Increasing_
heavy · 5 more declarations under this itemCancellation At Least Equation (4.6)
Pairwise summation backward error (Higham §4.2). For
n = 2^rinputs, pairwise summation satisfies:fl_pairwiseSum fp r v = ∑ i, v i * (1 + η i)where each|η i| ≤ γ(r). Each element takes part in exactlyradditions; the backward error factor per element is therefore γ(r), not γ(n-1) as in recursive summation. Proof sketch: induction onr. - Base: no addition, so η ≡ 0 and γ(0) = 0. - Step: IH gives left and right halves each with error ≤ γ(r). The finalfl_addintroduces δ with |δ| ≤ u ≤ γ(1).gamma_mulcombines 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)pairwise
Sum_ · 3 more declarations under this itembackward_ error
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 = 1summation
Condition · 4 more declarations under this itemNumber_ eq_ one_ of_ one Signed Problem 4.2
Arbitrary-length IEEE-double finite recursive trace for Wilkinson's Problem 4.2 source family. Under the IEEE-double
t = 53instantiation andr <= 52, the concrete finite round-to-even recursive trace returns2^r.Lean statement
theorem wilkinsonProblem42_ieeeDouble_finiteRecursiveSum_eq_pow {r : ℕ} (hr : r ≤ 52) : finiteRoundToEvenRecursiveSum FloatingPointFormat.ieeeDoubleFormat (2 ^ r) (wilkinsonProblem42Vector 53 r) = (2 : ℝ) ^ rwilkinson
Problem42_ · 2 more declarations under this itemieee Double_ finite Recursive Sum_ eq_ pow Problem 4.3
Source-shaped variable-
gammaexpansion for left-to-right recursive summation. Form + 2inputs, the first exact zero-accumulator step meansx₁andx₂share the same suffix ofm + 1rounded additions, while the later termx_{j+3}carries only the remainingm - jrounded 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)recursive
Sum_ · 6 more declarations under this itemproblem43_ variable Gamma 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_ · 1 more declaration under this itemexactly_ Icc 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) = 1plus
Minus · 2 more declarations under this itemPositive_ condition Number_ eq_ one 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 x2Problem 4.8
Once the product entering the logarithm has relative perturbation
θ, a final logarithm perturbationηgives the exact error formulalog(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 + θ) + ηlog
Exp · 1 more declaration under this itemProduct_ final_ error_ eq 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_
grid · 2 more declarations under this itemDirect_ error_ bound
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 coeffsDescfl_
horner · 3 more declarations under this itemDesc_ running_ error_ bound_ of_ inverse Local 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 ipoly
Desc · 2 more declarations under this itemHigher Deriv_ eq_ horner Formal Derivative Function Desc
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 coeffsDescEquation (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 pairsfl_
horner · 1 more declaration under this itemFold_ backward_ error_ coefficients 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 coeffsDescfl_
horner · 3 more declarations under this itemDesc_ forward_ error_ bound 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_
horner · 2 more declarations under this itemStep_ unroll Equation (5.5)
Lean statement
theorem highamBidiagonalEq55QuadraticRemainder_nonneg (fp : FPModel) (alpha : ℝ) (n : ℕ) (qhat : Fin n → ℝ) (i : Fin n) : 0 ≤ highamBidiagonalEq55QuadraticRemainder fp alpha n qhat ihigham
Bidiagonal · 3 more declarations under this itemEq55Quadratic Remainder_ nonneg 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 0higham
Bidiagonal · 7 more declarations under this itemUInv_ square_ entry 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 pairsfl_
horner · 4 more declarations under this itemDerivative Desc_ snd_ backward_ error_ coefficients_ coupled 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 nodesEquation (5.9)
Scalar row version of Higham (5.9): one rounded divided-difference entry is the exact
L_krow 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, matchingFPModel.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_
divided · 3 more declarations under this itemDifference Step_ entry_ error_ factors 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 fcolumn 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|) ifl_
divided · 3 more declarations under this itemDifference Finite Coeffs_ abs_ sub_ exact_ le_ abs LProduct_ gap_ gamma3 Equation (5.14)
The multiplication count is not merely asymptotic: it is exactly
2⌊√n⌋for every degreen.Lean statement
theorem higham5_ps_matrix_multiplications_exact (n : ℕ) : higham5PSMatrixMultiplications n = 2 * Nat.sqrt nhigham5_
ps_ · 4 more declarations under this itemmatrix_ multiplications_ exact
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 coeffsAscbeginner
Power · 1 more declaration under this itemEval Asc_ eq_ poly Asc 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)poly
Asc_ · 2 more declarations under this itemeven Odd_ split Problem 5.5
Root-product evaluation has exactly two relative-error factors per root: one for forming
x - x_iand 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 * cfl_
root · 1 more declaration under this itemProduct Eval From_ exists_ rel Error Counter
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
1mapping 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 = yexists_
rank · 2 more declarations under this itemOne CMatrix_ is Mixed Subordinate Matrix Norm Value_ one Lemma 6.6
Lemma 6.6 (a)(i). If
‖a_j‖₂ ≤ ‖b_j‖₂for every columnj, 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 Blemma66_
a_ · 9 more declarations under this itemfrobenius_ le 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_ · 2 more declarations under this itemmonotone_ complex Vector Norm 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||) / rhoover||D|| <= rho*||A||tends to||A|| * ||S||. The sharp perturbation is chosen on the boundaryd = 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))mixed
Inverse Ambient Relative Amplification Radius Sup_ tendsto_ condition Number Product_ 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 κ⁻¹complex
Matrix_ relative Singular Distance_ min_ eq_ inv_ condition Number Product
Equations and other results
Equation (6.1)
Finite complex Hölder inequality for the source-facing
L^pfamily. This covers finite conjugate exponents; endpoint cases are handled by separate1/∞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) xcomplex
Vec · 1 more declaration under this itemLp Norm_ holder 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_ · 1 more declaration under this itemof_ dual_ norm_ eq_ original 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 φ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⟩Equation (6.9)
Upper-bound skeleton: if
Shas mixed subordinate valuesas aβ -> αmap andΔhasα -> βbound1, thenS ∘ Δ ∘ Shasβ -> αbounds^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)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)schneider
Strang_ · 1 more declaration under this itemmixed Subordinate Matrix Norm Ratio_ is Max 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⁻¹|)complex
Matrix · 5 more declarations under this itemLp Norm_ pq_ ratio_ is Max Table 6.1
Finite vector norm monotonicity: if
1 <= q <= p, then||x||_p <= ||x||_q. Together withcomplexVecLpNorm_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) xcomplex
Vec · 2 more declarations under this itemLp Norm_ le_ complex Vec Lp Norm_ of_ exponent_ le
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 andsInfmodel: the source diagonal scalingD* = diag(a_jj^(-1/2))gives a two-sided SPD operator-2 condition product at mostntimes the infimum over reciprocal diagonal two-sided scalings ofDAD.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_ · 10 more declarations under this itemcholesky_ scaled_ cond_ le_ card_ s Inf_ symmetric_ scalings 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 ilemma7_
9_ · 2 more declarations under this itemcomponentwise_ bound 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_ · 7 more declarations under this itemsubordinate 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)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 itemTheorem 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| || < 1in 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)Theorem 7.5
p = 1minimum-attainment form over all reciprocal right diagonal scalings in the explicitAplusmodel. 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_ · 98 more declarations under this itemp1_ column_ equilibration_ is Least_ right_ scalings 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_invtheorem7_
7_ · 2 more declarations under this itemstewart_ sun_ frobenius_ scaling
Chapter 26 · Automatic error analysis all chapters
Equation (26.6)
Consequently, the stable branch in (26.6) solves the quadratic for
w^3when 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 = 0stable
Cubic · 2 more declarations under this itemWCube_ quadratic 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 deltalinearized
Forward · 2 more declarations under this itemError26_ 8_ eq
Chapter 27 · Software issues in floating point all chapters
Equation (27.1)
Equation (27.1) as the printed complex identity. The branch assumption
c ≠ 0is the explicit domain condition for formingd/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⟩