Matrix algorithms

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

Chapter 8 · Triangular systems all chapters

Definitions, theorems and lemmas

  • Corollary 8.11

    μ-form for lower triangular M-matrices and b ≥ 0.

    Lean statement
    theorem higham8_11_mmatrix_forwardSub_relative_error (fp : FPModel) (n : ℕ)
        (L L_inv : Fin n → Fin n → ℝ)
        (x b : Fin n → ℝ)
        (hLT : ∀ i j : Fin n, i.val < j.val → L i j = 0)
        (hL_diag_pos : ∀ i : Fin n, 0 < L i i)
        (hL_offdiag : ∀ i j : Fin n, j.val < i.val → L i j ≤ 0)
        (hInv : IsInverse n L L_inv)
        (hTx : ∀ i, ∑ j : Fin n, L i j * x j = b i)
        (hb : ∀ i, 0 ≤ b i)
        (hn : gammaValid fp n)
        (hn1 : gammaValid fp (n + 1))
        (h2n : gammaValid fp (2 * n)) :
        let x_hat := fl_forwardSub fp n L b
        (∀ i, 0 ≤ x i) ∧
        (∀ i, 0 ≤ x_hat i) ∧
        (∀ i, |x i - x_hat i| ≤ mu fp n i.val * |x i|)

    higham8_11_mmatrix_forwardSub_relative_error · 1 more declaration under this item

  • Lemma 8.2

    Row-spec form for Algorithm 8.1.

    Lean statement
    theorem higham8_2_backSub_row_spec (fp : FPModel) (n : ℕ)
        (U : Fin n → Fin n → ℝ) (b : Fin n → ℝ)
        (hU : ∀ i, U i i ≠ 0)
        (hn : gammaValid fp n) :
        BackSubRowSpec fp n U b (fl_backSub fp n U b)

    higham8_2_backSub_row_spec · 3 more declarations under this item

  • Lemma 8.4

    Lemma 8.4 (Higham, 2nd ed., §8.1): order-independent backward error of ŷ = fl((∑ wᵢ)/bₖ) when the n-term sum is evaluated in any order (encoded by an arbitrary summation tree t). With the distinguished summand w p (Higham's c) kept unperturbed, bₖ ŷ (1 + θ₀) = ∑ᵢ wᵢ (1 + θᵢ) with every |θ| ≤ γ_n and θ p = 0. Unlike higham8_5_backSub_backward_error, which fixes the repository evaluation order, this is the sharp order-independent statement underlying Theorem 8.5. It is proved from the pivot-normalised summation-tree backward error SumTree.backward_error_pivot.

    Lean statement
    theorem higham8_4_anyOrder_backwardError (fp : FPModel) {n : ℕ} (t : SumTree n)
        (ht : gammaValid fp n) (w : Fin n → ℝ) (p : Fin n)
        (bk : ℝ) (hbk : bk ≠ 0) :
        ∃ (θ₀ : ℝ) (θ : Fin n → ℝ),
          |θ₀| ≤ gamma fp n ∧
          θ p = 0 ∧
          (∀ i, |θ i| ≤ gamma fp n) ∧
          bk * fp.fl_div (t.eval fp w) bk * (1 + θ₀) = ∑ i : Fin n, w i * (1 + θ i)

    higham8_4_anyOrder_backwardError · 1 more declaration under this item

  • Lemma 8.6

    Diagonal-dominance bound for |U⁻¹||U|.

    Lean statement
    theorem higham8_6_inv_abs_mul_bound_diagDom (n : ℕ)
        (U U_inv : Fin n → Fin n → ℝ)
        (hDD : IsDiagDominantUpper n U)
        (hInv : IsInverse n U U_inv) :
        ∀ i j : Fin n, i.val ≤ j.val →
          ∑ k : Fin n, |U_inv i k| * |U k j| ≤ 2 ^ (j.val - i.val)

    higham8_6_inv_abs_mul_bound_diagDom · 1 more declaration under this item

  • Lemma 8.9

    Inequality part: cond(T,x) ≤ cond(M(T),x) once |T⁻¹| ≤ M(T)⁻¹ and M(T)⁻¹ ≥ 0 are known.

    Lean statement
    theorem higham8_9_condAtSolution_le_comparisonMatrix (n : ℕ) (hn : 0 < n)
        (T T_inv M_inv : Fin n → Fin n → ℝ) (x : Fin n → ℝ)
        (habsInv : ∀ i j : Fin n, |T_inv i j| ≤ M_inv i j)
        (hM_nonneg : ∀ i j : Fin n, 0 ≤ M_inv i j) :
        ch7SkeelCondAtSolutionInf n hn T T_inv x ≤
          ch7SkeelCondAtSolutionInf n hn (comparisonMatrix n T) M_inv x

    higham8_9_condAtSolution_le_comparisonMatrix · 3 more declarations under this item

  • Theorem 8.3

    Algorithm 8.1 with Higham's row-specific constants.

    Lean statement
    theorem higham8_3_backSub_backward_error (fp : FPModel) (n : ℕ)
        (U : Fin n → Fin n → ℝ) (b : Fin n → ℝ)
        (hU : ∀ i, U i i ≠ 0)
        (hUT : ∀ i j : Fin n, j.val < i.val → U i j = 0)
        (hn : gammaValid fp n) :
        ∃ ΔU : Fin n → Fin n → ℝ,
          (∀ i, |ΔU i i| ≤ gamma fp (n - i.val) * |U i i|) ∧
          (∀ i j, i.val < j.val →
            |ΔU i j| ≤ gamma fp (j.val - i.val) * |U i j|) ∧
          (∀ i j, j.val < i.val → ΔU i j = 0) ∧
          ∀ i, ∑ j : Fin n, (U i j + ΔU i j) * fl_backSub fp n U b j = b i

    higham8_3_backSub_backward_error · 1 more declaration under this item

  • Theorem 8.5

    Upper-triangular back-substitution specialization.

    Lean statement
    theorem higham8_5_backSub_backward_error (fp : FPModel) (n : ℕ)
        (U : Fin n → Fin n → ℝ) (b : Fin n → ℝ)
        (hU : ∀ i, U i i ≠ 0)
        (hUT : ∀ i j : Fin n, j.val < i.val → U i j = 0)
        (hn : gammaValid fp n) :
        ∃ ΔU : Fin n → Fin n → ℝ,
          (∀ i j, |ΔU i j| ≤ gamma fp n * |U i j|) ∧
          ∀ i, ∑ j : Fin n, (U i j + ΔU i j) * fl_backSub fp n U b j = b i

    higham8_5_backSub_backward_error · 5 more declarations under this item

  • Theorem 8.7

    Componentwise forward error under condition (8.5).

    Lean statement
    theorem higham8_7_backSub_forward_error_diagDom (fp : FPModel) (n : ℕ)
        (U U_inv : Fin n → Fin n → ℝ)
        (x b : Fin n → ℝ)
        (hDD : IsDiagDominantUpper n U)
        (hInv : IsInverse n U U_inv)
        (hTx : ∀ i, ∑ j : Fin n, U i j * x j = b i)
        (hn : gammaValid fp n) :
        let x_hat := fl_backSub fp n U b
        ∀ i : Fin n,
          |x i - x_hat i| ≤
          2 ^ (n - i.val) * gamma fp n *
              Finset.sup' (Finset.univ.filter (fun j : Fin n => i.val ≤ j.val))
                ⟨i, by simp [Finset.mem_filter]⟩ (fun j => |x_hat j|)

    higham8_7_backSub_forward_error_diagDom · 1 more declaration under this item

  • Theorem 8.10

    Formalized with Higham's exact μ recurrence rather than an informal O(u^2) abbreviation.

    Lean statement
    theorem higham8_10_forwardSub_forward_error_mu_bound (fp : FPModel) (n : ℕ)
        (L L_inv M_inv : Fin n → Fin n → ℝ)
        (x b : Fin n → ℝ)
        (hL_diag : ∀ i : Fin n, L i i ≠ 0)
        (hLT : ∀ i j : Fin n, i.val < j.val → L i j = 0)
        (hInv : IsInverse n L L_inv)
        (hM_RInv : IsRightInverse n (comparisonMatrix n L) M_inv)
        (hM_inv_lt : ∀ i j : Fin n, i.val < j.val → M_inv i j = 0)
        (hTx : ∀ i, ∑ j : Fin n, L i j * x j = b i)
        (hn : gammaValid fp n)
        (hn1 : gammaValid fp (n + 1)) :
        let x_hat := fl_forwardSub fp n L b
        let y := fun i => ∑ j : Fin n, M_inv i j * |b j|
        ∀ i : Fin n, |x i - x_hat i| ≤ mu fp n i.val * y i

    higham8_10_forwardSub_forward_error_mu_bound · 1 more declaration under this item

  • Theorem 8.12

    First comparison-matrix inverse inequality.

    Lean statement
    theorem higham8_12_abs_inv_le_comparison_inv (n : ℕ)
        (U U_inv M_inv : Fin n → Fin n → ℝ)
        (hUT : ∀ i j : Fin n, j.val < i.val → U i j = 0)
        (hU_diag : ∀ i : Fin n, U i i ≠ 0)
        (hInv : IsInverse n U U_inv)
        (hM_RInv : IsRightInverse n (comparisonMatrix n U) M_inv)
        (hM_inv_ut : ∀ i j : Fin n, j.val < i.val → M_inv i j = 0) :
        ∀ i j : Fin n, |U_inv i j| ≤ M_inv i j

    higham8_12_abs_inv_le_comparison_inv · 8 more declarations under this item

  • Theorem 8.14

    Packaged ∞/1/2 norm chains in the source notation using the minimum diagonal magnitude.

    Lean statement
    theorem higham8_14_full_norm_chain (n : ℕ) (hn : 0 < n)
        (U U_inv M_inv W_inv : Fin n → Fin n → ℝ)
        (i0 : Fin n) {β : ℝ}
        (hUT : ∀ i j : Fin n, j.val < i.val → U i j = 0)
        (hU_diag : ∀ i : Fin n, U i i ≠ 0)
        (hInv : IsInverse n U U_inv)
        (hM_RInv : IsRightInverse n (comparisonMatrix n U) M_inv)
        (hW_RInv : IsRightInverse n (higham8_12_WMatrix n U) W_inv)
        (hβ : 0 ≤ β) (hβ1 : β ≤ 1)
        (hβ_bound : ∀ i j : Fin n, i.val < j.val → |U i j| ≤ β * |U i i|) :
        let α : ℝ :=
          Finset.inf' Finset.univ ⟨i0, Finset.mem_univ i0⟩
            (fun k : Fin n => |U k k|)
        (1 / α ≤ infNorm U_inv ∧
            infNorm U_inv ≤ infNorm M_inv ∧
            infNorm M_inv ≤ infNorm W_inv ∧
            infNorm W_inv ≤ infNorm (higham8_12_ZInvFormula n α β) ∧
            infNorm (higham8_12_ZInvFormula n α β) ≤
              (1 / α) * (2 : ℝ) ^ (n - 1)) ∧
          (1 / α ≤ oneNorm U_inv ∧
            oneNorm U_inv ≤ oneNorm M_inv ∧
            oneNorm M_inv ≤ oneNorm W_inv ∧
            oneNorm W_inv ≤ oneNorm (higham8_12_ZInvFormula n α β) ∧
            oneNorm (higham8_12_ZInvFormula n α β) ≤
              (1 / α) * (2 : ℝ) ^ (n - 1)) ∧
          (1 / α ≤ complexMatrixOp2 (realRectToCMatrix U_inv) ∧
            complexMatrixOp2 (realRectToCMatrix U_inv) ≤
              complexMatrixOp2 (realRectToCMatrix M_inv) ∧
            complexMatrixOp2 (realRectToCMatrix M_inv) ≤
              complexMatrixOp2 (realRectToCMatrix W_inv) ∧
            complexMatrixOp2 (realRectToCMatrix W_inv) ≤
              complexMatrixOp2 (realRectToCMatrix (higham8_12_ZInvFormula n α β)) ∧
            complexMatrixOp2 (realRectToCMatrix (higham8_12_ZInvFormula n α β)) ≤
              (1 / α) * (2 : ℝ) ^ (n - 1))

    higham8_14_full_norm_chain · 5 more declarations under this item

Equations and other results

  • Equation (8.14)

    Producer bridge. The literal rounded fan-in executor has exactly the source's perturbation-tree form. In addition to constructing all five perturbations, the theorem exposes certified local envelopes. The two composite envelopes retain the harmless higher-order terms explicitly: the matrix-product residual plus the backward error of the subsequent matrix-vector action. This theorem removes the former gap between the symbolic (8.14) expression and an actual sequence of fl_matMul/fl_matVec operations.

    Lean statement
    theorem higham8_14_fanIn7Executor_eq_roundedApply (fp : FPModel) (n : ℕ)
        (M1 M2 M3 M4 M5 M6 M7 : Fin n → Fin n → ℝ) (b : Fin n → ℝ)
        (hn : gammaValid fp n) :
        ∃ Δ1 Δ32 Δ54 Δ76 Δ7654 : Fin n → Fin n → ℝ,
          higham8_14_fanIn7Executor fp n M1 M2 M3 M4 M5 M6 M7 b =
            higham8_14_fanIn7RoundedApply n
              M1 M2 M3 M4 M5 M6 M7 Δ1 Δ32 Δ54 Δ76 Δ7654 b ∧
          (∀ i j, |Δ1 i j| ≤ gamma fp n * |M1 i j|) ∧
          (∀ i j,
            |Δ32 i j| ≤
              gamma fp n * (∑ k : Fin n, |M3 i k| * |M2 k j|) +
                gamma fp n * |fl_matMul fp n n n M3 M2 i j|) ∧
          (∀ i j,
            |Δ54 i j| ≤ gamma fp n * (∑ k : Fin n, |M5 i k| * |M4 k j|)) ∧
          (∀ i j,
            |Δ76 i j| ≤ gamma fp n * (∑ k : Fin n, |M7 i k| * |M6 k j|)) ∧
          (∀ i j,
            |Δ7654 i j| ≤
              gamma fp n *
                  (∑ k : Fin n,
                    |fl_matMul fp n n n M7 M6 i k| *
                      |fl_matMul fp n n n M5 M4 k j|) +
                gamma fp n *
                  |fl_matMul fp n n n
                    (fl_matMul fp n n n M7 M6)
                    (fl_matMul fp n n n M5 M4) i j|)

    higham8_14_fanIn7Executor_eq_roundedApply · 1 more declaration under this item

  • Equation (8.17)

    Literal-executor all-orders backward-error form. The actual (8.14) executor and (8.16) residual norm bound construct a rank-one backward perturbation with the corresponding explicit raw envelope.

    Lean statement
    theorem higham8_17_fanIn7Executor_backward_error_bound
        (fp : FPModel) (n : ℕ)
        (L M1 M2 M3 M4 M5 M6 M7 : Fin n → Fin n → ℝ)
        (b : Fin n → ℝ) (hn : gammaValid fp n)
        (hsolve :
          matMulVec n L
            (higham8_13_fanIn7Apply n M1 M2 M3 M4 M5 M6 M7 b) = b)
        (j0 : Fin n)
        (hxj0 :
          higham8_14_fanIn7Executor fp n M1 M2 M3 M4 M5 M6 M7 b j0 ≠ 0) :
        ∃ ΔL : Fin n → Fin n → ℝ,
          matMulVec n (fun i j => L i j + ΔL i j)
              (higham8_14_fanIn7Executor fp n M1 M2 M3 M4 M5 M6 M7 b) = b ∧
            infNorm ΔL ≤
              infNormVec
                  (matMulVec n (absMatrix n L)
                    (fun k =>
                      ((1 + gamma fp n) ^ 7 - 1) *
                        higham8_18_fanIn7AbsApply n M1 M2 M3 M4 M5 M6 M7 b k)) /
                |higham8_14_fanIn7Executor fp n M1 M2 M3 M4 M5 M6 M7 b j0|

    higham8_17_fanIn7Executor_backward_error_bound · 1 more declaration under this item

  • Equation (8.18)

    Literal-executor all-orders form. The actual seven rounded operations satisfy the source's product-of-absolute-matrices forward envelope. The exact coefficient (1+γₙ)^7-1 retains all higher-order terms; its first-order term is 7γₙ, matching the source's d'ₙ u + O(u²) form. No relative perturbation of an intermediate product is assumed, so exact cancellation in M3*M2, M5*M4, or M7*M6 is allowed.

    Lean statement
    theorem higham8_18_fanIn7Executor_forward_componentwise_bound
        (fp : FPModel) (n : ℕ)
        (M1 M2 M3 M4 M5 M6 M7 : Fin n → Fin n → ℝ)
        (b : Fin n → ℝ) (hn : gammaValid fp n) :
        ∀ i : Fin n,
          |higham8_14_fanIn7Executor fp n M1 M2 M3 M4 M5 M6 M7 b i -
            higham8_13_fanIn7Apply n M1 M2 M3 M4 M5 M6 M7 b i| ≤
          ((1 + gamma fp n) ^ 7 - 1) *
            higham8_18_fanIn7AbsApply n M1 M2 M3 M4 M5 M6 M7 b i

    higham8_18_fanIn7Executor_forward_componentwise_bound · 2 more declarations under this item

  • Equation (8.19)

    Literal-executor relative ∞-norm form.

    Lean statement
    theorem higham8_19_fanIn7Executor_forward_relative_infNorm_bound
        (fp : FPModel) (n : ℕ)
        (M1 M2 M3 M4 M5 M6 M7 : Fin n → Fin n → ℝ)
        (b : Fin n → ℝ) (hn : gammaValid fp n)
        (hx : 0 < infNormVec
          (higham8_13_fanIn7Apply n M1 M2 M3 M4 M5 M6 M7 b)) :
        infNormVec
            (fun i =>
              higham8_14_fanIn7Executor fp n M1 M2 M3 M4 M5 M6 M7 b i -
                higham8_13_fanIn7Apply n M1 M2 M3 M4 M5 M6 M7 b i) /
            infNormVec (higham8_13_fanIn7Apply n M1 M2 M3 M4 M5 M6 M7 b) ≤
          infNormVec
            (fun i =>
              ((1 + gamma fp n) ^ 7 - 1) *
                higham8_18_fanIn7AbsApply n M1 M2 M3 M4 M5 M6 M7 b i) /
            infNormVec (higham8_13_fanIn7Apply n M1 M2 M3 M4 M5 M6 M7 b)

    higham8_19_fanIn7Executor_forward_relative_infNorm_bound · 1 more declaration under this item

Chapter 9 · LU factorization and linear equations all chapters

  • Theorem 9.1

    Theorem 9.1 support, uniqueness of an exact LU certificate once the pivots are nonzero. The proof follows the Doolittle recurrences column by column: previous columns of L and rows of U determine the next row of U, then the nonzero pivot determines the next column of L. This is still only the uniqueness half of Theorem 9.1; it does not construct factors from leading principal minors.

    Lean statement
    theorem higham9_1_lu_unique_of_pivots_ne_zero {n : ℕ}
        {A L₁ U₁ L₂ U₂ : Fin n → Fin n → ℝ}
        (hLU₁ : LUFactSpec n A L₁ U₁)
        (hLU₂ : LUFactSpec n A L₂ U₂)
        (hU₁diag : ∀ k : Fin n, U₁ k k ≠ 0) :
        L₁ = L₂ ∧ U₁ = U₂

    higham9_1_lu_unique_of_pivots_ne_zero · 10 more declarations under this item

  • Theorem 9.3

    Generic LU backward-error-certificate form.

    Lean statement
    theorem higham9_3_lu_backward_error_gamma (fp : FPModel) (n : ℕ)
        (A L_hat U_hat : Fin n → Fin n → ℝ)
        (hn : gammaValid fp n)
        (hLU : LUBackwardError n A L_hat U_hat (gamma fp n)) :
        ∃ ΔA : Fin n → Fin n → ℝ,
          (∀ i j, |ΔA i j| ≤ gamma fp n *
            ∑ k : Fin n, |L_hat i k| * |U_hat k j|) ∧
          (∀ i j, ∑ k : Fin n, L_hat i k * U_hat k j = A i j + ΔA i j)

    higham9_3_lu_backward_error_gamma · 37 more declarations under this item

  • Theorem 9.5

    Source-shaped max-entry growth-factor form. This removes the free norm-growth bridge hypothesis from higham9_5_wilkinson_source_bound_of_growth_bridge: a bound on Higham's max-entry growth factor for the final U_hat implies the required ∞-norm bridge by elementary row-sum/max-entry inequalities.

    Lean statement
    theorem higham9_5_wilkinson_source_bound_of_entry_growth (fp : FPModel) (n : ℕ)
        (hn_pos : 0 < n)
        (A L_hat U_hat : Fin n → Fin n → ℝ)
        (b : Fin n → ℝ) (ρ : ℝ)
        (hAmax : 0 < maxEntryNorm hn_pos A)
        (hρ : 0 ≤ ρ)
        (hρU : growthFactorEntry hn_pos A U_hat hAmax ≤ ρ)
        (hL_diag : ∀ i : Fin n, L_hat i i ≠ 0)
        (hU_diag : ∀ i : Fin n, U_hat i i ≠ 0)
        (hLU : LUBackwardError n A L_hat U_hat (gamma fp n))
        (hn : gammaValid fp n)
        (hn3 : gammaValid fp (3 * n))
        (hL_bound : ∀ i j : Fin n, |L_hat i j| ≤ 1) :
        let y_hat := fl_forwardSub fp n L_hat b
        let x_hat := fl_backSub fp n U_hat y_hat
        ∃ ΔA : Fin n → Fin n → ℝ,
          (infNorm ΔA ≤ (↑n) ^ 2 * gamma fp (3 * n) * ρ * infNorm A) ∧
          (∀ i, ∑ j : Fin n, (A i j + ΔA i j) * x_hat j = b i)

    higham9_5_wilkinson_source_bound_of_entry_growth · 21 more declarations under this item

  • Theorem 9.8

    Real max-entry ρ ≥ θ bridge. If the final pivot supplies Higham's inverse-entry witness |u|⁻¹ ≤ β and |u| is bounded by the largest entry reached in U, then growthFactorEntry A U ≥ (αβ)⁻¹.

    Lean statement
    theorem higham9_8_growth_factor_ge_theta_real {n : ℕ} (hn : 0 < n)
        (A A_inv U : Fin n → Fin n → ℝ)
        (hA : 0 < maxEntryNorm hn A)
        (hAinv : 0 < maxEntryNorm hn A_inv)
        (u : ℝ) (hu_pos : 0 < |u|)
        (hu_entry : |u| ≤ maxEntryNorm hn U)
        (hu_inv_le : |u|⁻¹ ≤ maxEntryNorm hn A_inv) :
        1 / (maxEntryNorm hn A * maxEntryNorm hn A_inv) ≤
          growthFactorEntry hn A U hA

    higham9_8_growth_factor_ge_theta_real · 28 more declarations under this item

  • Theorem 9.9

    Column diagonally dominant nonsingular matrices in dimensions one and two have exact no-pivot LU factors with unit-bounded lower entries and max-entry growth factor at most 2. This packages the explicit 1 by 1 base case with the verified 2 by 2 endpoint, matching the small-dimension closure pattern used for the Wilkinson/Foster growth families elsewhere in this chapter.

    Lean statement
    theorem higham9_9_colDiagDominant_exists_LUFactSpec_growthFactorEntry_le_two_of_le_two
        {n : ℕ} (hn : 0 < n) (hle : n ≤ 2)
        (A : Fin n → Fin n → ℝ)
        (hDD : IsDiagDominant n A)
        (hdet : Matrix.det (Matrix.of A : Matrix (Fin n) (Fin n) ℝ) ≠ 0) :
        ∃ L U : Fin n → Fin n → ℝ,
          LUFactSpec n A L U ∧
            (∀ i j : Fin n, |L i j| ≤ 1) ∧
              ∃ hAmax : 0 < maxEntryNorm hn A,
                growthFactorEntry hn A U hAmax ≤ 2

    higham9_9_colDiagDominant_exists_LUFactSpec_growthFactorEntry_le_two_of_le_two · 25 more declarations under this item

  • Theorem 9.15

    Componentwise LU perturbation identity.

    Lean statement
    theorem higham9_15_lu_perturbation_identity (n : ℕ)
        (A L U δA δL δU : Fin n → Fin n → ℝ)
        (hLU : ∀ i j, ∑ k : Fin n, L i k * U k j = A i j)
        (hPerturbed : ∀ i j,
          ∑ k : Fin n, (L i k + δL i k) * (U k j + δU k j) = A i j + δA i j) :
        ∀ i j, δA i j =
          ∑ k : Fin n, L i k * δU k j +
          ∑ k : Fin n, δL i k * U k j +
          ∑ k : Fin n, δL i k * δU k j

    higham9_15_lu_perturbation_identity · 127 more declarations under this item

Chapter 10 · Cholesky factorization all chapters

  • Lemma 10.10

    Lemma 10.10 / equation (10.16) in honest form: the perturbed Schur complement equals the unperturbed one plus Higham's first-order term Ē = E₂₂ − E₂₁MA₁₂ − A₂₁ME₁₂ + A₂₁ME₁₁MA₁₂ plus a remainder that is entrywise bounded by an explicit polynomial times ε² — the exact statement behind the source's S(A+E) = S(A) + Ē + O(‖E‖²). The leading-block inverses enter through genuine inverse equations (M A₁₁ = 1 up to the resolvent identity), not assumed bounds on the conclusion.

    Lean statement
    theorem higham10_10_schur_complement_perturbation {k m : ℕ}
        (A11 E11 M X : Matrix (Fin k) (Fin k) ℝ)
        (A21 E21 : Matrix (Fin m) (Fin k) ℝ)
        (A12 E12 : Matrix (Fin k) (Fin m) ℝ)
        (A22 E22 : Matrix (Fin m) (Fin m) ℝ)
        (hM : M * A11 = 1) (hXi : (A11 + E11) * X = 1)
        (α μ χ ε : ℝ) (hα : 0 ≤ α) (hμ : 0 ≤ μ) (hχ : 0 ≤ χ) (hε : 0 ≤ ε)
        (hA21 : ∀ i j, |A21 i j| ≤ α) (hA12 : ∀ i j, |A12 i j| ≤ α)
        (hE21 : ∀ i j, |E21 i j| ≤ ε) (hE12 : ∀ i j, |E12 i j| ≤ ε)
        (hE11 : ∀ i j, |E11 i j| ≤ ε)
        (hMb : ∀ i j, |M i j| ≤ μ) (hXb : ∀ i j, |X i j| ≤ χ) :
        ∃ R : Matrix (Fin m) (Fin m) ℝ,
          (A22 + E22) - (A21 + E21) * X * (A12 + E12) =
            (A22 - A21 * M * A12)
            + (E22 - E21 * M * A12 - A21 * M * E12
                + A21 * (M * E11 * M) * A12)
            + R ∧
          ∀ i j : Fin m, |R i j| ≤
            ((k : ℝ) ^ 2 * μ + (k : ℝ) ^ 6 * α ^ 2 * μ ^ 2 * χ
              + 2 * ((k : ℝ) ^ 4 * α * μ * χ) + (k : ℝ) ^ 4 * μ * χ * ε)
              * ε ^ 2

    higham10_10_schur_complement_perturbation · 2 more declarations under this item

  • Lemma 10.11

    Source-strength pivot preservation. The finite no-ties and nonbreakdown hypotheses alone produce a positive radius. Any perturbation whose operator 2-norm is at most that radius preserves all first-r pivots, for both A + E and A - E.

    Lean statement
    theorem higham10_11_cp_pivot_sequence_stable_of_noTies_two_sided
        {n : ℕ} (hn : 0 < n) (A : Fin n → Fin n → ℝ) (r : ℕ)
        (hpivot : ∀ t : ℕ, t < r →
          0 < cpState hn A t (cpPivot hn A t) (cpPivot hn A t))
        (hnoTies : Higham10_11NoTies hn A r) :
        ∃ ε₀ : ℝ, 0 < ε₀ ∧
          ∀ E : Fin n → Fin n → ℝ, opNorm2 E ≤ ε₀ →
            (∀ s : ℕ, s < r →
              cpPivot hn A s = cpPivot hn (fun i j => A i j + E i j) s) ∧
            (∀ s : ℕ, s < r →
              cpPivot hn A s = cpPivot hn (fun i j => A i j - E i j) s)

    higham10_11_cp_pivot_sequence_stable_of_noTies_two_sided · 7 more declarations under this item

  • Lemma 10.12

    Lemma 10.12 core (Higham §10.3): for a positive semidefinite block matrix with leading block A₁₁ inverted in action by M, the solve vector Wv = M A₁₂ v satisfies λ_min(A₁₁) ‖Wv‖₂² ≤ vᵀ A₂₂ v — the quadratic-form content of Wᵀ A₁₁ W ⪯ A₂₂, sharpened through the Rayleigh bound. Choosing u = −Wv in the block-split quadratic form gives (Wv)ᵀA₁₁(Wv) ≤ vᵀA₂₂v; Rayleigh converts the left side.

    Lean statement
    theorem higham10_12_psd_w_action_bound {k m : ℕ} (hk : 0 < k)
        (A : Fin (k + m) → Fin (k + m) → ℝ)
        (hPSD : IsPosSemiDef (k + m) A)
        (M : Fin k → Fin k → ℝ)
        (hSym : IsSymmetricFiniteMatrix
          (fun i j : Fin k => A (Fin.castAdd m i) (Fin.castAdd m j)))
        (hMinv : ∀ (w : Fin k → ℝ) (i : Fin k),
          ∑ j : Fin k, A (Fin.castAdd m i) (Fin.castAdd m j) *
            (∑ t : Fin k, M j t * w t) = w i)
        (v : Fin m → ℝ) :
        finiteMinEigenvalue hk
            (fun i j : Fin k => A (Fin.castAdd m i) (Fin.castAdd m j))
            hSym *
          vecNorm2Sq (fun i : Fin k => ∑ t : Fin k, M i t *
            (∑ j : Fin m, A (Fin.castAdd m t) (Fin.natAdd k j) * v j)) ≤
        ∑ i : Fin m, ∑ j : Fin m,
          v i * A (Fin.natAdd k i) (Fin.natAdd k j) * v j

    higham10_12_psd_w_action_bound · 2 more declarations under this item

  • Lemma 10.13

    Complete-pivoting bound on ‖W‖_F² with Higham's (n−r)(4^r−1)/3 constant, in honest form: for an r × r upper-triangular block U with positive diagonal whose rows are pivot-dominated on and right of the diagonal — exactly what complete pivoting guarantees via the (10.13) column-tail invariant (tail_invariant_entry_le applied to the factor from psd_pivoted_cholesky_exists_tail) — the solution W of U W = B with pivot-dominated right-hand columns B (the border block R₁₂) satisfies ∑_{i,j} W i j ² ≤ m (4^r − 1)/3, m = n − r border columns.

    Lean statement
    theorem higham10_13_complete_pivoting_w_bound {r m : ℕ}
        (U : Fin r → Fin r → ℝ) (B W : Fin r → Fin m → ℝ)
        (hupper : ∀ i j : Fin r, j.val < i.val → U i j = 0)
        (hdiag_pos : ∀ i : Fin r, 0 < U i i)
        (hentry : ∀ i j : Fin r, i.val ≤ j.val → |U i j| ≤ U i i)
        (hB : ∀ (i : Fin r) (j : Fin m), |B i j| ≤ U i i)
        (hsolve : ∀ (i : Fin r) (j : Fin m),
          ∑ k : Fin r, U i k * W k j = B i j) :
        ∑ j : Fin m, ∑ i : Fin r, W i j ^ 2 ≤
          (m : ℝ) * (((4 : ℝ) ^ r - 1) / 3)

    higham10_13_complete_pivoting_w_bound · 2 more declarations under this item

  • Theorem 10.1

    Existence of the Cholesky factorization for real SPD matrices.

    Lean statement
    theorem higham10_1_cholesky_existence (n : ℕ)
        (A : Fin n → Fin n → ℝ) (hSPD : IsSymPosDef n A) :
        ∃ R : Fin n → Fin n → ℝ, higham10_1_CholeskyFactSpec n A R

    higham10_1_cholesky_existence · 2 more declarations under this item

  • Theorem 10.3

    R_hat^T R_hat = A + ΔA, with |ΔA| <= γ_{n+1} |R_hat^T| |R_hat| componentwise.

    Lean statement
    theorem higham10_3_cholesky_backward_error (fp : FPModel) (n : ℕ)
        (A R_hat : Fin n → Fin n → ℝ)
        (hn1 : gammaValid fp (n + 1))
        (hChol : higham10_2_CholeskyBackwardError n A R_hat (gamma fp (n + 1))) :
        ∃ ΔA : Fin n → Fin n → ℝ,
          (∀ i j, |ΔA i j| ≤ gamma fp (n + 1) *
            ∑ k : Fin n, |R_hat k i| * |R_hat k j|) ∧
          (∀ i j, ∑ k : Fin n, R_hat k i * R_hat k j = A i j + ΔA i j)

    higham10_3_cholesky_backward_error · 2 more declarations under this item

  • Theorem 10.4

    Cholesky factorization plus the two triangular solves gives (A + ΔA)x_hat = b, with Higham's absorbed γ_{3n+1} componentwise bound.

    Lean statement
    theorem higham10_4_cholesky_solve_backward_error (fp : FPModel) (n : ℕ)
        (A R_hat : Fin n → Fin n → ℝ)
        (b : Fin n → ℝ)
        (hR_diag : ∀ i : Fin n, R_hat i i ≠ 0)
        (hChol : higham10_2_CholeskyBackwardError n A R_hat (gamma fp (n + 1)))
        (hn1 : gammaValid fp (n + 1))
        (hn3 : gammaValid fp (3 * n + 1)) :
        let R_hatT := fun i j : Fin n => R_hat j i
        let y_hat := fl_forwardSub fp n R_hatT b
        let x_hat := fl_backSub fp n R_hat y_hat
        ∃ ΔA : Fin n → Fin n → ℝ,
          (∀ i j, |ΔA i j| ≤ gamma fp (3 * n + 1) *
            ∑ k : Fin n, |R_hat k i| * |R_hat k j|) ∧
          (∀ i, ∑ j : Fin n, (A i j + ΔA i j) * x_hat j = b i)

    higham10_4_cholesky_solve_backward_error · 1 more declaration under this item

  • Theorem 10.6

    Actual source closure. For an SPD input, a successful concrete Algorithm 10.2 run and its two concrete rounded triangular solves produce Higham's displayed scaled forward error bound with ε = n γ_(3n+1) / (1 - γ_(n+1)) and the literal spectral condition number of H = D⁻¹ A D⁻¹. No factorization-error, solve-error, inverse-action, or operator-norm certificate is an input to this theorem.

    Lean statement
    theorem higham10_6_actual_source_closed (fp : FPModel) (n : ℕ)
        (hn : 0 < n) (A : Fin n → Fin n → ℝ) (b x : Fin n → ℝ)
        (hSPD : IsSymPosDef n A)
        (hn1 : gammaValid fp (n + 1))
        (hn3 : gammaValid fp (3 * n + 1))
        (hgamma1 : gamma fp (n + 1) < 1)
        (hsuccess : ∀ j : Fin n, 0 < fl_cholPivot fp n A j)
        (hAx : matMulVec n A x = b)
        (hsmall : higham10SourceKappa2 A *
          ((n : ℝ) * (gamma fp (3 * n + 1) /
            (1 - gamma fp (n + 1)))) < 1) :
        let Rhat := fl_cholesky fp n A
        let yhat := fl_forwardSub fp n (fun i j : Fin n => Rhat j i) b
        let xhat := fl_backSub fp n Rhat yhat
        vecNorm2 (fun i => Real.sqrt (A i i) * xhat i -
            Real.sqrt (A i i) * x i) ≤
          higham10SourceKappa2 A *
              ((n : ℝ) * (gamma fp (3 * n + 1) /
                (1 - gamma fp (n + 1)))) /
            (1 - higham10SourceKappa2 A *
              ((n : ℝ) * (gamma fp (3 * n + 1) /
                (1 - gamma fp (n + 1))))) *
          vecNorm2 (fun i => Real.sqrt (A i i) * x i)

    higham10_6_actual_source_closed · 3 more declarations under this item

  • Theorem 10.7

    Theorem 10.7 (Demmel), exact source threshold for the concrete Algorithm 10.2 run (Higham, p. 200). If λ_min(D⁻¹AD⁻¹) > n γ_{n+1}/(1-γ_{n+1}), every raw rounded Cholesky pivot is positive. No run-level or stage-level certificate is assumed: all defect bounds are constructed from the preceding pivots.

    Lean statement
    theorem higham10_7_fl_cholesky_success_source (fp : FPModel) (n : ℕ)
        (hn0 : 0 < n) (A : Fin n → Fin n → ℝ)
        (hsym : ∀ i l : Fin n, A i l = A l i)
        (hAdiag : ∀ i : Fin n, 0 < A i i)
        (hn1 : gammaValid fp (n + 1))
        (hγ1 : gamma fp (n + 1) < 1)
        (hH_sym : IsSymmetricFiniteMatrix (fun i l : Fin n =>
          A i l / (Real.sqrt (A i i) * Real.sqrt (A l l))))
        (hthresh : (n : ℝ) *
          (gamma fp (n + 1) / (1 - gamma fp (n + 1))) <
          finiteMinEigenvalue hn0 (fun i l : Fin n =>
            A i l / (Real.sqrt (A i i) * Real.sqrt (A l l))) hH_sym) :
        ∀ j : Fin n, 0 < fl_cholPivot fp n A j

    higham10_7_fl_cholesky_success_source · 10 more declarations under this item

  • Theorem 10.14

    Equation (10.22), literal family form. For a family of floating-point models whose unit roundoff tends to zero, this theorem bounds the operator 2-norm of the matrix produced by the literal truncated Cholesky executor. The leading coefficient is exactly the one in the book, and the remainder is the uniform family-level O(u²) predicate. The hypotheses below are explicit small-roundoff radii on gamma and the actual source error; none assumes a bound on the final residual or trailing Schur block.

    Lean statement
    theorem higham10_14_equation_10_22_family_of_success
        {ι : Type*} {l : Filter ι} {r s : ℕ}
        (F : ι → FPModel) (U : RoundoffFamily ι l)
        (hunit : ∀ t, (F t).u = U.unit t)
        (A : Fin (r + s) → Fin (r + s) → ℝ)
        (hr0 : 0 < r)
        (hPSD : IsPosSemiDef (r + s) A)
        (hrank : (Matrix.of A).rank = r)
        (hA11 : IsSymPosDef r (higham10_14_block11 A))
        (hsuccess : ∀ t, ∀ q : Fin (r + s), q.val < r →
          0 < fl_cholPivot (F t) (r + s) A q)
        (hhalf : ∀ t, ((r + 1 : ℕ) : ℝ) * U.unit t ≤ 1 / 2)
        (hgammaRadius : ∀ t,
          (r : ℝ) * gamma (F t) (r + 1) ≤ 1 / 2)
        (hlinearAbsorb : ∀ t,
          (gamma (F t) (r + 1) /
              (1 - (r : ℝ) * gamma (F t) (r + 1))) *
            ((r + s : ℕ) : ℝ) *
              (complexMatrixOp2 (realRectToCMatrix (higham10_14_W A)) + 1) ^ 2 ≤
            1 / 4)
        (hquadraticAbsorb : ∀ t,
          (gamma (F t) (r + 1) /
              (1 - (r : ℝ) * gamma (F t) (r + 1))) *
            ((r + s : ℕ) : ℝ) * higham10_14_schurQuadraticCoeff A *
              complexMatrixOp2 (realRectToCMatrix
                (higham10_14_sourceError (F t) A r
                  (Nat.le_add_right r s))) ≤ 1 / 4)
        (hEone : ∀ t, complexMatrixOp2 (realRectToCMatrix
          (higham10_14_sourceError (F t) A r (Nat.le_add_right r s))) ≤ 1)
        (hinvRadius : ∀ t,
          complexMatrixOp2 (realRectToCMatrix
              (nonsingInv r (higham10_14_block11 A))) *
            complexMatrixOp2 (realRectToCMatrix
              (higham10_14_sourceError (F t) A r
                (Nat.le_add_right r s))) ≤ 1 / 2) :
        FamilyFirstOrderLe l U.unit
          (fun t =>
            2 * (r : ℝ) * gamma (F t) (r + 1) *
              complexMatrixOp2 (realRectToCMatrix A) *
              (complexMatrixOp2 (realRectToCMatrix (higham10_14_W A)) + 1) ^ 2)
          (fun t => complexMatrixOp2 (realRectToCMatrix
            (higham10_14_actualResidual (F t) A)))

    higham10_14_equation_10_22_family_of_success · 5 more declarations under this item

Chapter 11 · Symmetric indefinite and skew-symmetric systems all chapters

Definitions, theorems and lemmas

  • Algorithm 11.1

    Bunch-Parlett α is a root of 4α² − α − 1 = 0. This algebraic identity characterizes α = (1 + √17)/8 as the solution that minimizes the worst-case element growth.

    Lean statement
    theorem bunch_parlett_alpha_root :
        4 * bunchParlettAlpha ^ 2 - bunchParlettAlpha - 1 = 0

    bunch_parlett_alpha_root · 1 more declaration under this item

  • Algorithm 11.2

    Theorem 11.4 / Algorithm 11.2 cases-(1)/(2) scalar Schur-growth dispatch: the two branches accepting the leading scalar pivot a₁₁ share the same normalized one-step growth factor. Case-(2) obtains its active-row majorant from the explicit row-maximum side condition.

    Lean statement
    theorem higham11_4_bunch_kaufman_case1_or_case2_schur_growth_source_factor_of_row_max_le
        (b ci cj a11 arr ω1 ωr Amax : ℝ) (hω1 : 0 < ω1) (hωr_le : ωr ≤ ω1)
        (hcase :
          higham11_2_BunchKaufmanPartialPivotCase
            higham11_1_bunchParlettAlpha a11 arr ω1 ωr BunchKaufmanCase.case1 ∨
          higham11_2_BunchKaufmanPartialPivotCase
            higham11_1_bunchParlettAlpha a11 arr ω1 ωr BunchKaufmanCase.case2)
        (hb : |b| ≤ Amax) (hci : |ci| ≤ ω1) (hcj : |cj| ≤ ω1)
        (hω1_Amax : ω1 ≤ Amax) :
        |b - ci * cj / a11| ≤
          (1 + higham11_1_bunchParlettAlpha⁻¹) * Amax

    higham11_4_bunch_kaufman_case1_or_case2_schur_growth_source_factor_of_row_max_le · 11 more declarations under this item

  • Algorithm 11.6

    The tridiagonal pivoting parameter satisfies alpha^2 + alpha - 1 = 0.

    Lean statement
    theorem bunch_tridiagonal_alpha_root :
        bunchTridiagonalAlpha ^ 2 + bunchTridiagonalAlpha - 1 = 0

    bunch_tridiagonal_alpha_root · 18 more declarations under this item

  • Algorithm 11.9

    Skew 2×2 multiplier bound (Higham §11.3). For Bunch's skew-symmetric pivoting, the row of CE⁻¹ has entries −a_{i2}/a₂₁, a_{i1}/a₂₁; since the pivot a₂₁ is the largest-magnitude entry (|c| ≤ |a₂₁|), each multiplier — and hence every entry of L — is bounded by 1. Derived, not assumed.

    Lean statement
    theorem skew_twoByTwo_multiplier_bound (c a : ℝ) (ha : a ≠ 0) (hc : |c| ≤ |a|) :
        |c / a| ≤ 1

    skew_twoByTwo_multiplier_bound · 5 more declarations under this item

  • Theorem 11.3

    All-1×1-pivot (σ = id) case, printed first-order strength. For a symmetric input whose rounded all-1×1-pivot block-LDLᵀ path has nonzero successive pivots (and, at each stage, matching active first row/column), under the smallness n·u ≤ 1/100 there are computed factors L̂, D̂ and backward-error matrices ΔA₁, ΔA₂ with L̂D̂L̂ᵀ = A + ΔA₁, |ΔAₖ| ≤ p(n)·u·(|A| + |L̂||D̂||L̂ᵀ|), the printed Higham (11.5) envelope with linear polynomial p(n) = 20 n. Everything is derived from the floating-point model.

    Lean statement
    theorem higham11_3_block_ldlt_all_oneByOne_printed (fp : FPModel)
        (hval : gammaValid fp 3) (n : ℕ) (A : Fin n → Fin n → ℝ)
        (hsmall : (n : ℝ) * fp.u ≤ 1 / 100)
        (hp : FlAllOneSymmetricPivots fp n A) :
        ∃ L D ΔA1 ΔA2 : Fin n → Fin n → ℝ,
          (∀ i j, |ΔA1 i j|
              ≤ higham11_3_printedFirstOrderBound n A L D id (pPoly n) fp.u i j) ∧
          (∀ i j, |ΔA2 i j|
              ≤ higham11_3_printedFirstOrderBound n A L D id (pPoly n) fp.u i j) ∧
          (∀ i j, (∑ k₁, ∑ k₂, L i k₁ * D k₁ k₂ * L j k₂) = A i j + ΔA1 i j)

    higham11_3_block_ldlt_all_oneByOne_printed · 38 more declarations under this item

  • Theorem 11.8

    Theorem 11.8 product-size dependency: an AasenSpec supplies the structural zeros needed to turn a uniform exact outer-factor entry cap into (n-1) row and column sum majorants.

    Lean statement
    theorem higham11_8_aasen_outer_factor_row_col_sum_majorants_of_AasenSpec_entry_bound
        (n : ℕ) (hn : 1 < n)
        (A L T : Fin n → Fin n → ℝ) (σ : Fin n → Fin n) (κ : ℝ)
        (hspec : higham11_8_AasenSpec n A L T σ)
        (hentry : ∀ i j : Fin n, |L i j| ≤ κ) :
        (∀ i : Fin n, (∑ j : Fin n, |L i j|) ≤
            ((n - 1 : ℕ) : ℝ) * κ) ∧
          (∀ j : Fin n, (∑ i : Fin n, |L i j|) ≤
            ((n - 1 : ℕ) : ℝ) * κ)

    higham11_8_aasen_outer_factor_row_col_sum_majorants_of_AasenSpec_entry_bound · 176 more declarations under this item

Equations and other results

  • Equation (11.1)

    Exact all-1×1 block-LDLᵀ factorization existence (Higham eqs (11.1)/(11.2), the no-2×2-pivot / root-free LDLᵀ case). If A is symmetric and every successive Schur-complement pivot is nonzero (AllOnePivots), there exist factors L, D with ∑ L·D·Lᵀ = A — the exact PAPᵀ = LDLᵀ recursion (with P = I) underlying Theorem 11.3, obtained by iterating blockLDLT_assemble_step.

    Lean statement
    theorem exact_blockLDLT_all_oneByOne :
        ∀ (n : ℕ) (A : Fin n → Fin n → ℝ),
          (∀ i j, A i j = A j i) → AllOnePivots n A →
          ∃ L D : Fin n → Fin n → ℝ,
            ∀ I J, (∑ k₁, ∑ k₂, L I k₁ * D k₁ k₂ * L J k₂) = A I J

    exact_blockLDLT_all_oneByOne · 2 more declarations under this item

  • Equation (11.4)

    Self-contained 2×2 complete-pivoting element growth (Higham §11.1.1, eq. (11.4)). Combining twoByTwo_inverse_entry_bounds with twoByTwo_schur_growth: the Schur entry formed with the actual inverse of the pivot block E, namely E⁻¹ = d⁻¹[[e₂₂,−e₂₁],[−e₂₁,e₁₁]], is bounded by (1 + 2/(1−α))·μ₀ using only the pivot-block data and the entry bound μ₀ — no inverse-entry bounds are assumed.

    Lean statement
    theorem twoByTwo_schur_growth_of_block
        (b ci1 ci2 cj1 cj2 e11 e22 e21 μ0 μ1 α K : ℝ)
        (hμ1 : 0 ≤ μ1) (hα0 : 0 ≤ α) (hα1 : α < 1) (hμ : 0 < μ0)
        (he11 : |e11| ≤ μ1) (he22 : |e22| ≤ μ1)
        (he21 : e21 ^ 2 = μ0 ^ 2) (hμ1α : μ1 ≤ α * μ0)
        (hK : (1 - α ^ 2) * μ0 * K = 1)
        (hb : |b| ≤ μ0)
        (hci1 : |ci1| ≤ μ0) (hci2 : |ci2| ≤ μ0)
        (hcj1 : |cj1| ≤ μ0) (hcj2 : |cj2| ≤ μ0) :
        |b - (ci1 * (e22 / (e11 * e22 - e21 ^ 2) * cj1
                + -(e21 / (e11 * e22 - e21 ^ 2)) * cj2)
              + ci2 * (-(e21 / (e11 * e22 - e21 ^ 2)) * cj1
                + e11 / (e11 * e22 - e21 ^ 2) * cj2))|
          ≤ (1 + 2 / (1 - α)) * μ0

    twoByTwo_schur_growth_of_block · 1 more declaration under this item

  • Equation (11.6)

    Equation (11.6) verified algebraically: A = L D L^T for ε ≠ 0.

    Lean statement
    theorem higham11_6_partialPivotExample_factorization
        (ε : ℝ) (hε : ε ≠ 0) :
        ∀ i j : Fin 3,
          ∑ k₁ : Fin 3, ∑ k₂ : Fin 3,
            higham11_6_partialPivotExampleL ε i k₁ *
              higham11_6_partialPivotExampleD ε k₁ k₂ *
              higham11_6_partialPivotExampleL ε j k₂ =
          higham11_6_partialPivotExampleA ε i j

    higham11_6_partialPivotExample_factorization

  • Equation (11.11)

    First diagonal recovery. For H = T Lᵀ in an AasenSpec, the first diagonal H entry is the first tridiagonal diagonal entry of T.

    Lean statement
    theorem higham11_11_AasenSpec_identity_aasenH_diagonal_eq_T_of_zero
        (n : ℕ) (A L T : Fin n → Fin n → ℝ) (σ : Fin n → Fin n)
        (hspec : higham11_8_AasenSpec n A L T σ)
        (i : Fin n) (hi0 : i.val = 0) :
        higham11_10_aasenH n T L i i = T i i

    higham11_11_AasenSpec_identity_aasenH_diagonal_eq_T_of_zero · 3 more declarations under this item

  • Equation (11.12)

    Equation (11.12) derivation: the Aasen diagonal equation holds for any A = L·H with L unit lower triangular. Exact-arithmetic identity behind the Aasen recurrence (not the fl analysis): A i i = ∑_{j<i} L i j · H j i + H i i, by unit-lower-triangularity of L.

    Lean statement
    theorem higham11_12_aasen_diagonal_equation_of_product (n : ℕ)
        (A L H : Fin n → Fin n → ℝ)
        (hLdiag : ∀ i, L i i = 1)
        (hLupper : ∀ i j : Fin n, i.val < j.val → L i j = 0)
        (hprod : ∀ i k : Fin n, (∑ j, L i j * H j k) = A i k) :
        higham11_12_aasenDiagonalEquation n A L H

    higham11_12_aasen_diagonal_equation_of_product · 3 more declarations under this item

  • Equation (11.13)

    Equation (11.13) derivation: the Aasen subdiagonal equation holds for any A = L·H with L unit lower triangular. For k = i+1, A k i = ∑_{j≤i} L k j · H j i + H k i.

    Lean statement
    theorem higham11_13_aasen_subdiagonal_equation_of_product (n : ℕ)
        (A L H : Fin n → Fin n → ℝ)
        (hLdiag : ∀ i, L i i = 1)
        (hLupper : ∀ i j : Fin n, i.val < j.val → L i j = 0)
        (hprod : ∀ i k : Fin n, (∑ j, L i j * H j k) = A i k) :
        higham11_13_aasenSubdiagonalEquation n A L H

    higham11_13_aasen_subdiagonal_equation_of_product · 3 more declarations under this item

  • Equation (11.14)

    Equation (11.14) derivation: for A = L·H with L unit lower triangular and H banded (H j i = 0 for j > i+1, e.g. from higham11_10_aasenH_band), the below-diagonal next-column entries of L are L k next = (A k i − ∑_{j≤i} L k j·H j i) / H next i (next = i+1, k ≥ i+2), provided the pivot H next i ≠ 0. Exact-arithmetic Aasen recurrence, toward Thm 11.8.

    Lean statement
    theorem higham11_14_aasen_next_column_of_product (n : ℕ)
        (A L H : Fin n → Fin n → ℝ)
        (hHband : ∀ i j : Fin n, i.val + 1 < j.val → H j i = 0)
        (hprod : ∀ k i : Fin n, (∑ j, L k j * H j i) = A k i)
        (hHnz : ∀ i next : Fin n, next.val = i.val + 1 → H next i ≠ 0) :
        higham11_14_aasenNextColumnEquation n A L H

    higham11_14_aasen_next_column_of_product · 13 more declarations under this item

  • Equation (11.15)

    Equation (11.15) exact solve-chain bridge, unpermuted case. If the exact Aasen product is A = L T Lᵀ and the three exact solves in the chain are satisfied with identity permutation, then the resulting x solves A x = b. This is the algebraic base that the later rounded solve-chain perturbation must approximate.

    Lean statement
    theorem higham11_15_aasenSolveChain_identity_solve_of_product (n : ℕ)
        (A L T : Fin n → Fin n → ℝ) (b z y w x : Fin n → ℝ)
        (hprod : ∀ i j : Fin n,
          (∑ k₁ : Fin n, ∑ k₂ : Fin n, L i k₁ * T k₁ k₂ * L j k₂) = A i j)
        (hchain : higham11_15_aasenSolveChain n (fun i j => if i = j then 1 else 0)
          L T b z y w x) :
        ∀ i : Fin n, ∑ j : Fin n, A i j * x j = b i

    higham11_15_aasenSolveChain_identity_solve_of_product · 9 more declarations under this item

Chapter 12 · Iterative refinement all chapters

Definitions, theorems and lemmas

  • Theorem 12.3

    Theorem 12.3 / equation (12.10) (Higham, 2nd ed., printed p. 235), with the asymptotic remainder q displayed exactly rather than hidden behind O(u). The source's later statement q = O(u) needs a parameterized regularity hypothesis for t; this theorem proves the finite identity from which that asymptotic interpretation is obtained. Here gTerm, hTerm, tAtX, and tAtY stand for the corresponding source quantities at the computed correction, original solution, and corrected solution.

    Lean statement
    theorem higham12_10_exact_q_bound (n : ℕ)
        (A : Fin n → Fin n → ℝ)
        (x_hat d_hat : Fin n → ℝ) (b r r_hat : Fin n → ℝ)
        (f2 : Fin n → ℝ) (y : Fin n → ℝ)
        (u : ℝ) (gTerm hTerm tAtX tAtY : Fin n → ℝ)
        (hr : ∀ i : Fin n, r i = b i - ∑ j : Fin n, A i j * x_hat j)
        (hy : ∀ i : Fin n, y i = x_hat i + d_hat i + f2 i)
        (hf1 : ∀ i : Fin n,
          |r_hat i - ∑ j : Fin n, A i j * d_hat j| ≤
            u * (gTerm i + hTerm i))
        (hDeltaR : ∀ i : Fin n, |r_hat i - r i| ≤ u * tAtX i)
        (hf2 : ∀ j : Fin n, |f2 j| ≤ u * (|x_hat j| + |d_hat j|)) :
        ∀ i : Fin n,
          |b i - ∑ j : Fin n, A i j * y j| ≤
            u * (hTerm i + tAtY i + ∑ j : Fin n, |A i j| * |y j|) +
            u * (tAtX i - tAtY i + gTerm i +
              ∑ j : Fin n, |A i j| * (|x_hat j| - |y j| + |d_hat j|))

    higham12_10_exact_q_bound · 3 more declarations under this item

  • Theorem 12.4

    Theorem 12.4 / equation (12.22) (Higham, 2nd ed., printed pp. 236-238): an exact conditional companion with the printed two-gamma conclusion. The source's sufficient-condition function is approximate; here the needed componentwise dominance inequality remains an explicit hypothesis, so this is not the solver-derived endpoint.

    Lean statement
    theorem higham12_4_conditional_two_gamma_bound (n : ℕ) (fp : FPModel)
        (A : Fin n → Fin n → ℝ)
        (x_hat d_hat r_hat : Fin n → ℝ)
        (DeltaA_solve : Fin n → Fin n → ℝ)
        (mu nu : ℝ) (omega : Fin n → ℝ)
        (b : Fin n → ℝ)
        (r : Fin n → ℝ)
        (hr : ∀ i : Fin n, r i = b i - ∑ j : Fin n, A i j * x_hat j)
        (hres : ∀ i : Fin n, |r_hat i - r i| ≤ nu * |r i| + omega i)
        (hsolve : ∀ i : Fin n,
          ∑ j : Fin n, (A i j + DeltaA_solve i j) * d_hat j = r_hat i)
        (hDeltaA : ∀ i j : Fin n, |DeltaA_solve i j| ≤ mu * |A i j|)
        (y : Fin n → ℝ)
        (hy : ∀ i : Fin n, y i = x_hat i + d_hat i)
        (hmu_nonneg : 0 ≤ mu) (hnu_nonneg : 0 ≤ nu)
        (homega_nonneg : ∀ i : Fin n, 0 ≤ omega i)
        (hdom : ∀ i : Fin n,
          mu * ∑ j : Fin n, |A i j| * |d_hat j| + nu * |r i| + omega i ≤
            (2 * gamma fp (n + 1)) * ∑ j : Fin n, |A i j| * |y j|) :
        ∀ i : Fin n,
          |b i - ∑ j : Fin n, A i j * y j| ≤
            (2 * gamma fp (n + 1)) * ∑ j : Fin n, |A i j| * |y j|

    higham12_4_conditional_two_gamma_bound · 2 more declarations under this item

Equations and other results

  • Equation (12.2)

    Equation (12.2) residual perturbation bound after rewriting x_i = x + (x_i - x). This is the exact algebraic component of the displayed bound; the residual computation model supplies hDelta.

    Lean statement
    theorem higham12_2_residual_delta_bound (n : ℕ)
        (A : Fin n → Fin n → ℝ) (x x_i b DeltaR : Fin n → ℝ)
        (u gammaBar : ℝ)
        (hu : 0 ≤ u) (hc : 0 ≤ (1 + u) * gammaBar)
        (hAx : ∀ i : Fin n, ∑ j : Fin n, A i j * x j = b i)
        (hDelta : ∀ i : Fin n,
          |DeltaR i| ≤
            u * |b i - ∑ j : Fin n, A i j * x_i j| +
              (1 + u) * gammaBar *
                (|b i| + ∑ j : Fin n, |A i j| * |x_i j|)) :
        ∀ i : Fin n,
          |DeltaR i| ≤
            (u + (1 + u) * gammaBar) *
                ∑ j : Fin n, |A i j| * |x j - x_i j| +
              2 * (1 + u) * gammaBar *
                ∑ j : Fin n, |A i j| * |x j|

    higham12_2_residual_delta_bound

  • Equation (12.4)

    Equations (12.4)-(12.5) exact forward-error identity of one refinement step. With computed residual rc = (b - A x_i) + Δr, correction d solving (A + ΔA) d = rc, and rounded update y = x_i + d + Δx, the corrected forward error satisfies exactly A (y - x) = Δr - ΔA·d + A·Δx. This is the exact, inverse-free core of the recurrence (12.5) (before the source's asymptotic F_i, G_i, O(u^2) estimates).

    Lean statement
    theorem higham12_5_forward_error_identity (n : ℕ)
        (A DeltaA : Fin n → Fin n → ℝ)
        (x x_i d DeltaR DeltaX rc y b : Fin n → ℝ)
        (hAx : ∀ i : Fin n, ∑ j : Fin n, A i j * x j = b i)
        (hrc : ∀ i : Fin n,
          rc i = (b i - ∑ j : Fin n, A i j * x_i j) + DeltaR i)
        (hsolve : ∀ i : Fin n,
          ∑ j : Fin n, (A i j + DeltaA i j) * d j = rc i)
        (hy : ∀ i : Fin n, y i = x_i i + d i + DeltaX i) :
        ∀ i : Fin n,
          ∑ j : Fin n, A i j * (y j - x j) =
            DeltaR i - (∑ j : Fin n, DeltaA i j * d j)
              + (∑ j : Fin n, A i j * DeltaX j)

    higham12_5_forward_error_identity · 1 more declaration under this item

  • Equation (12.5)

    Uniform steady-state consequence of the Chapter 12 contraction skeleton.

    Lean statement
    theorem higham12_forward_error_steady_state (a : ℕ → ℝ) (eta tau : ℝ)
        (heta_nonneg : 0 ≤ eta) (heta_lt : eta < 1) (htau_nonneg : 0 ≤ tau)
        (hstep : ∀ k, a (k + 1) ≤ eta * a k + tau)
        (ha0 : 0 ≤ a 0) :
        ∀ k, a k ≤ a 0 + tau / (1 - eta)

    higham12_forward_error_steady_state · 1 more declaration under this item

Chapter 13 · Block LU factorization all chapters

Definitions, theorems and lemmas

  • Algorithm 13.1

    Exact output check for partitioned outer-product LU. If the algorithm's displayed steps hold -- A₁₁ = L₁₁ U₁₁, L₁₁ U₁₂ = A₁₂, L₂₁ U₁₁ = A₂₁, S = A₂₂ - L₂₁ U₁₂, and the recursive call returns S = L₂₂ U₂₂ -- then the assembled block factors multiply to the original matrix.

    Lean statement
    theorem higham13_algorithm13_1_partitioned_lu_reconstructs
        {m n α : Type*} [Fintype m] [Fintype n] [DecidableEq m] [DecidableEq n]
        [CommRing α]
        (L11 U11 A11 : Matrix m m α) (U12 A12 : Matrix m n α)
        (L21 A21 : Matrix n m α) (L22 U22 S A22 : Matrix n n α)
        (h11 : L11 * U11 = A11) (h12 : L11 * U12 = A12)
        (h21 : L21 * U11 = A21) (hSfact : L22 * U22 = S)
        (hSdef : S = A22 - L21 * U12) :
        Matrix.fromBlocks A11 A12 A21 A22 =
          Matrix.fromBlocks L11 0 L21 L22 * Matrix.fromBlocks U11 U12 0 U22

    higham13_algorithm13_1_partitioned_lu_reconstructs · 2 more declarations under this item

  • Algorithm 13.3

    Exact output check for block LU recursion. With U₁₁ = A₁₁, U₁₂ = A₁₂, L₂₁ A₁₁ = A₂₁, S = A₂₂ - L₂₁ A₁₂, and recursive factors S = L₂₂ U₂₂, the assembled block LU factors multiply to the original matrix.

    Lean statement
    theorem higham13_algorithm13_3_block_lu_reconstructs
        {m n α : Type*} [Fintype m] [Fintype n] [DecidableEq m] [DecidableEq n]
        [CommRing α]
        (A11 : Matrix m m α) (A12 : Matrix m n α)
        (L21 A21 : Matrix n m α) (L22 U22 S A22 : Matrix n n α)
        (h21 : L21 * A11 = A21) (hSfact : L22 * U22 = S)
        (hSdef : S = A22 - L21 * A12) :
        Matrix.fromBlocks A11 A12 A21 A22 =
          Matrix.fromBlocks 1 0 L21 L22 * Matrix.fromBlocks A11 A12 0 U22

    higham13_algorithm13_3_block_lu_reconstructs · 188 more declarations under this item

  • Algorithm 13.4

    Exact output check for recursively partitioned LU. The first recursive call supplies [A₁₁; A₂₁] = [L₁₁; L₂₁] U₁₁, the triangular solve supplies L₁₁ U₁₂ = A₁₂, and the second recursive call supplies S = L₂₂ U₂₂; after forming S = A₂₂ - L₂₁ U₁₂, the assembled block factors multiply to the original matrix.

    Lean statement
    theorem higham13_algorithm13_4_recursive_partitioned_lu_reconstructs
        {n α : Type*} [Fintype n] [DecidableEq n] [CommRing α]
        (L11 U11 A11 U12 A12 L21 A21 L22 U22 S A22 : Matrix n n α)
        (h11 : L11 * U11 = A11) (h21 : L21 * U11 = A21)
        (h12 : L11 * U12 = A12) (hSfact : L22 * U22 = S)
        (hSdef : S = A22 - L21 * U12) :
        Matrix.fromBlocks A11 A12 A21 A22 =
          Matrix.fromBlocks L11 0 L21 L22 * Matrix.fromBlocks U11 U12 0 U22

    higham13_algorithm13_4_recursive_partitioned_lu_reconstructs · 1 more declaration under this item

  • Lemma 13.9

    For a source-ordered SPD block matrix, ||A₂₁ A₁₁⁻¹||₂ <= sqrt(κ₂(A)). The leading inverse is modeled by the repository canonical inverse of the leading principal block, and κ₂(A) is the exact product kappa2 A (nonsingInv (r+s) A). The proof chooses a Cholesky factor from SPD, identifies A₁₁⁻¹ with R₁₁⁻¹R₁₁⁻ᵀ, and feeds the exact-kappa2 Cholesky route.

    Lean statement
    theorem
        higham13_lemma13_9_cholesky_route_rectOpNorm2Le_from_spd_leading_nonsingInv_kappa2
        {r s : ℕ} [Nonempty (Fin r)]
        (A : Fin (r + s) → Fin (r + s) → ℝ)
        (A22 : Fin s → Fin s → ℝ)
        (A21 : Fin s → Fin r → ℝ)
        (hA22_block : A22 =
          fun i j : Fin s =>
            A (finSumFinEquiv (Sum.inr i : Fin r ⊕ Fin s))
              (finSumFinEquiv (Sum.inr j : Fin r ⊕ Fin s)))
        (hA21_block : A21 =
          fun (i : Fin s) (j : Fin r) =>
            A (finSumFinEquiv (Sum.inr i : Fin r ⊕ Fin s))
              (finSumFinEquiv (Sum.inl j : Fin r ⊕ Fin s)))
        (hSPD : IsSymPosDef (r + s) A) :
        rectOpNorm2Le
          (rectMatMul A21
            (nonsingInv r
              (fun i j : Fin r =>
                A (finSumFinEquiv (Sum.inl i : Fin r ⊕ Fin s))
                  (finSumFinEquiv (Sum.inl j : Fin r ⊕ Fin s)))))
          (Real.sqrt (kappa2 A (nonsingInv (r + s) A)))

    higham13_lemma13_9_cholesky_route_rectOpNorm2Le_from_spd_leading_nonsingInv_kappa2 · 4 more declarations under this item

  • Lemma 13.10

    Lemma 13.10 proof route: the SPD Schur complement inherits the full matrix's operator-2 certificate. This combines the Loewner bound S <= A22, the trailing-principal-block operator certificate ||A22||_2 <= ||A||_2, and the PSD Schur-complement fact. It closes the ||S||_2 half of the source condition-number bound; the inverse half ||S^{-1}||_2 <= ||A^{-1}||_2 remains separate.

    Lean statement
    theorem higham13_lemma13_10_schur_opNorm2Le_of_full_operator_bound
        {r s : Type*} [Fintype r] [Fintype s] [DecidableEq r] [Nonempty s]
        (A11 : Matrix r r ℝ) (A21 : Matrix s r ℝ) (A22 : Matrix s s ℝ)
        {normA : ℝ}
        (hFull : (Matrix.fromBlocks A11 A21.transpose A21 A22).PosDef)
        (hA : finiteOpNorm2Le
          (fun i j : r ⊕ s => (Matrix.fromBlocks A11 A21.transpose A21 A22) i j)
          normA) :
        finiteOpNorm2Le
          (fun i j : s => (A22 - A21 * A11⁻¹ * A21.transpose) i j)
          normA

    higham13_lemma13_10_schur_opNorm2Le_of_full_operator_bound · 4 more declarations under this item

  • Theorem 13.2

    A uniform block matrix has a unique block LU factorization if and only if its first m leading principal block submatrices are nonsingular. For a matrix indexed by Fin (m+1), this is the source condition on the first m leading block prefixes, i.e. all prefixes except the whole matrix.

    Lean statement
    theorem BlockLUFactSpec.existsUnique_iff_leadingPrincipalBlockNonsingular13_2
        {m r : ℕ}
        (A : Fin (m + 1) → Fin (m + 1) → (Fin r → Fin r → ℝ)) :
        (∃ L U : Fin (m + 1) → Fin (m + 1) → (Fin r → Fin r → ℝ),
          BlockLUFactSpec (m + 1) r A L U ∧
            ∀ L' U' : Fin (m + 1) → Fin (m + 1) → (Fin r → Fin r → ℝ),
              BlockLUFactSpec (m + 1) r A L' U' → L' = L ∧ U' = U) ↔
          LeadingPrincipalBlockNonsingular13_2 A

    existsUnique_iff_leadingPrincipalBlockNonsingular13_2 · 11 more declarations under this item

  • Theorem 13.5

    Theorem 13.5 / equation (13.7) for an actual recursively computed partitioned LU execution. The conclusion exposes both the assembled matrix residual and the advertised first-order backward-error bound.

    Lean statement
    theorem higham13_theorem13_5_eq13_7_from_computation
        {ι : Type} [Fintype ι] {m : ℕ}
        {u c₁ c₂ c₃ normA normL normU normDeltaA : ℝ}
        {A DeltaA Lhat Uhat : Matrix ι ι ℝ}
        (hcomp : PartitionedLUComputationFirstOrder u c₁ c₂ c₃ m
          normA normL normU normDeltaA A DeltaA Lhat Uhat)
        (hu : 0 ≤ u) (hc₁ : 0 ≤ c₁) (hc₂ : 0 ≤ c₂) (hc₃ : 0 ≤ c₃) :
        (Lhat * Uhat = A + DeltaA) ∧
          FirstOrderLe u
            (u * (blockErrorDelta m * normA +
              blockErrorTheta c₁ c₂ c₃ m * normL * normU)) normDeltaA

    higham13_theorem13_5_eq13_7_from_computation · 6 more declarations under this item

  • Theorem 13.7

    Source-facing Euclidean column-BDD endpoint. The initial diagInv table states the printed quantity ||A_jj^{-1}||_2^{-1}. From full nonsingularity and this BDD condition, the theorem constructs the complete Algorithm 13.3 pivot sequence, the concrete block LU factors, and block diagonal dominance of every active Schur complement.

    Lean statement
    theorem higham13_theorem13_7_algorithm13_3_opNorm2_column
        {m r : ℕ} (hr : 0 < r)
        (A : Fin m → Fin m → Matrix (Fin r) (Fin r) ℝ)
        (diagInv : Fin m → Matrix (Fin r) (Fin r) ℝ)
        (hA : BlockMatrixNonsingular A)
        (hDiagRight : ∀ j : Fin m, IsRightInverse r (A j j) (diagInv j))
        (hDom : IsBlockDiagDomCol m
          (fun i j => opNorm2 (A i j))
          (fun j => (opNorm2 (diagInv j))⁻¹)) :
        ∃ pivotInv : ℕ → Matrix (Fin r) (Fin r) ℝ,
          (∀ k : ℕ, ∀ hk : k < m,
            IsRightInverse r
              (higham13_algorithm13_3_schurStageMatrixBlock A pivotInv k
                ⟨k, hk⟩ ⟨k, hk⟩)
              (pivotInv k)) ∧
          BlockLUFactSpec m r A
            (higham13_algorithm13_3_lowerFromMatrixStages A pivotInv)
            (higham13_algorithm13_3_upperFromMatrixStages A pivotInv) ∧
          SchurStageActiveColumnDom13_7
            (fun k i j => opNorm2
              (higham13_algorithm13_3_schurStageMatrixBlock A pivotInv k i j))
            (fun k j => matMulVecLowerNorm2 hr
              (higham13_algorithm13_3_schurStageMatrixBlock A pivotInv k j j))

    higham13_theorem13_7_algorithm13_3_opNorm2_column · 27 more declarations under this item

  • Theorem 13.8

    Source-facing Euclidean column-BDD endpoint. Under exactly the nonsingularity and BDD data used by Theorem 13.7, this constructs the block LU factors and proves the printed active-stage growth estimate ||A_ij^(k)||_2 <= 2 * max_ij ||A_ij||_2.

    Lean statement
    theorem higham13_theorem13_8_algorithm13_3_opNorm2_column
        {m r : ℕ} (hm : 0 < m) (hr : 0 < r)
        (A : Fin m → Fin m → Matrix (Fin r) (Fin r) ℝ)
        (diagInv : Fin m → Matrix (Fin r) (Fin r) ℝ)
        (hA : BlockMatrixNonsingular A)
        (hDiagRight : ∀ j : Fin m, IsRightInverse r (A j j) (diagInv j))
        (hDom : IsBlockDiagDomCol m
          (fun i j => opNorm2 (A i j))
          (fun j => (opNorm2 (diagInv j))⁻¹))
        (normMax : ℝ)
        (hMax : ∀ i j : Fin m, opNorm2 (A i j) ≤ normMax) :
        ∃ pivotInv : ℕ → Matrix (Fin r) (Fin r) ℝ,
          BlockLUFactSpec m r A
            (higham13_algorithm13_3_lowerFromMatrixStages A pivotInv)
            (higham13_algorithm13_3_upperFromMatrixStages A pivotInv) ∧
          ∀ k : ℕ, ∀ i j : Fin m, k ≤ m → k ≤ i.val → k ≤ j.val →
            opNorm2
              (higham13_algorithm13_3_schurStageMatrixBlock A pivotInv k i j) ≤
                2 * normMax

    higham13_theorem13_8_algorithm13_3_opNorm2_column · 26 more declarations under this item

Equations and other results

  • Equation (13.2)

    One exact block LU step with Schur complement. For an invertible leading block A₁₁, the 2-by-2 block matrix factors as [[I,0],[A₂₁ A₁₁^{-1},I]] * [[A₁₁,A₁₂],[0,S]], where S = A₂₂ - A₂₁ A₁₁^{-1} A₁₂.

    Lean statement
    theorem higham13_eq13_2_block_lu_step
        {m n α : Type*} [Fintype m] [Fintype n] [DecidableEq m] [DecidableEq n]
        [CommRing α]
        (A11 : Matrix m m α) (A12 : Matrix m n α)
        (A21 : Matrix n m α) (A22 : Matrix n n α) [Invertible A11] :
        Matrix.fromBlocks A11 A12 A21 A22 =
          Matrix.fromBlocks 1 0 (A21 * ⅟A11) 1 *
            Matrix.fromBlocks A11 A12 0 (A22 - A21 * ⅟A11 * A12)

    higham13_eq13_2_block_lu_step

  • Equation (13.4)

    Source-facing unpacking of the matrix-multiplication first-order model.

    Lean statement
    theorem higham13_eq13_4_from_matmul_spec {m n p : Type*} [Fintype n]
        (u c₁ normA normB normDelta : ℝ)
        (A : Matrix m n ℝ) (B : Matrix n p ℝ) (Chat DeltaC : Matrix m p ℝ)
        (h : MatMulFirstOrderSpec u c₁ normA normB normDelta A B Chat DeltaC) :
        Chat = A * B + DeltaC ∧
          MatMulFirstOrderBound u c₁ normA normB normDelta

    higham13_eq13_4_from_matmul_spec · 2 more declarations under this item

  • Equation (13.5)

    Source-facing unpacking of the left triangular-solve first-order model.

    Lean statement
    theorem higham13_eq13_5_from_triangular_solve_spec {m p : Type*} [Fintype m]
        (u c₂ normT normXhat normDeltaB : ℝ)
        (T : Matrix m m ℝ) (B DeltaB Xhat : Matrix m p ℝ)
        (h : TriangularSolveFirstOrderSpec u c₂ normT normXhat normDeltaB
          T B DeltaB Xhat) :
        T * Xhat = B + DeltaB ∧
          TriangularSolveFirstOrderBound u c₂ normT normXhat normDeltaB

    higham13_eq13_5_from_triangular_solve_spec · 3 more declarations under this item

  • Equation (13.6)

    Source-facing unpacking of the block-level LU first-order model.

    Lean statement
    theorem higham13_eq13_6_from_local_lu_spec {r : Type*} [Fintype r]
        (u c₃ normLhat normUhat normDeltaA : ℝ)
        (A DeltaA Lhat Uhat : Matrix r r ℝ)
        (h : LocalLUFirstOrderSpec u c₃ normLhat normUhat normDeltaA
          A DeltaA Lhat Uhat) :
        Lhat * Uhat = A + DeltaA ∧
          LocalLUFirstOrderBound u c₃ normLhat normUhat normDeltaA

    higham13_eq13_6_from_local_lu_spec · 1 more declaration under this item

  • Equation (13.10)

    Source-facing unpacking of the computed subtraction residual model.

    Lean statement
    theorem higham13_eq13_10_from_subtraction_spec {m p : Type*}
        (u normA normComputed normF : ℝ)
        (A Computed F Shat : Matrix m p ℝ)
        (h : SubtractionFirstOrderSpec u normA normComputed normF A Computed F Shat) :
        Shat = A - Computed + F ∧ normF ≤ u * (normA + normComputed)

    higham13_eq13_10_from_subtraction_spec · 1 more declaration under this item

  • Equation (13.14)

    Source-facing unpacking of the Algorithm 13.3 step-2 block-solve model.

    Lean statement
    theorem higham13_eq13_14_from_block_solve_spec {r s : Type*} [Fintype r]
        (u c₄ normLhat21 normA11 normE21 : ℝ)
        (Lhat21 A21 E21 : Matrix s r ℝ) (A11 : Matrix r r ℝ)
        (h : BlockSolveFirstOrderSpec u c₄ normLhat21 normA11 normE21
          Lhat21 A21 E21 A11) :
        Lhat21 * A11 = A21 + E21 ∧
          BlockSolveFirstOrderBound u c₄ normLhat21 normA11 normE21

    higham13_eq13_14_from_block_solve_spec

  • Equation (13.15)

    Source-facing unpacking of the diagonal-block solve model used in block back substitution.

    Lean statement
    theorem higham13_eq13_15_from_diagonal_block_solve_spec {r p : Type*} [Fintype r]
        (u c₅ normUii normDeltaUii : ℝ)
        (Uii DeltaUii : Matrix r r ℝ) (Xhat D : Matrix r p ℝ)
        (h : DiagonalBlockSolveFirstOrderSpec u c₅ normUii normDeltaUii
          Uii DeltaUii Xhat D) :
        (Uii + DeltaUii) * Xhat = D ∧
          DiagonalBlockSolveFirstOrderBound u c₅ normUii normDeltaUii

    higham13_eq13_15_from_diagonal_block_solve_spec · 10 more declarations under this item

  • Equation (13.18)

    Min-step abstraction. Higham's proof uses the reverse triangle inequality to pass from min_{‖x‖=1} ‖A_jj x‖ - c to min_{‖x‖=1} ‖(A_jj - A_j1 A_11^{-1} A_1j) x‖. This lemma records that normed-space step without choosing a concrete subordinate matrix norm.

    Lean statement
    theorem higham13_eq13_18_min_lower_bound {E : Type*}
        [SeminormedAddCommGroup E]
        (diag perturb schur : E → E) (diagMin schurMin perturbBound : ℝ)
        (hDiagMin : ∀ x : E, ‖x‖ = 1 → diagMin ≤ ‖diag x‖)
        (hSchurMin : ∃ x : E, ‖x‖ = 1 ∧ schurMin = ‖schur x‖)
        (hPerturb : ∀ x : E, ‖x‖ = 1 → ‖perturb x‖ ≤ perturbBound)
        (hSchur : ∀ x : E, schur x = diag x - perturb x) :
        diagMin - perturbBound ≤ schurMin

    higham13_eq13_18_min_lower_bound · 12 more declarations under this item

  • Equation (13.19)

    Packaged from its two displayed inequalities.

    Lean statement
    theorem higham13_eq13_19 {m : ℕ}
        (blockNorm : Fin m → Fin m → ℝ) (normA : ℝ)
        (hLower : ∀ i j : Fin m, blockNorm i j ≤ normA)
        (hUpper : normA ≤ blockNormSum13_19 blockNorm) :
        BlockNormComparison13_19 blockNorm normA

    higham13_eq13_19 · 4 more declarations under this item

  • Equation (13.20)

    Exact 2-by-2 partition display. Higham switches here to the entrywise max norm and writes A = [[A₁₁, A₁₂], [A₂₁, A₂₂]]. In Mathlib this is exactly the fromBlocks reconstruction from the four canonical block projections.

    Lean statement
    theorem higham13_eq13_20_partition {r s α : Type*}
        (A : Matrix (r ⊕ s) (r ⊕ s) α) :
        A = Matrix.fromBlocks A.toBlocks₁₁ A.toBlocks₁₂ A.toBlocks₂₁ A.toBlocks₂₂

    higham13_eq13_20_partition

  • Equation (13.22)

    Higham, 2nd ed., Chapter 13, Problem 13.4 and equation (13.22): for a matrix with at least two blocks, one exact Algorithm 13.3 pivot table supplies every recursive parent/suffix inverse obligation and yields the exact source n * rho^3 * kappa(A) * ‖A‖ product bound.

    Lean statement
    theorem higham13_problem13_4_eq13_22_exists_blockLUFact_succ_of_pivot_right_inverse
        {m r n : ℕ} (hr : 0 < r)
        (A : Fin ((m + 1) + 1) → Fin ((m + 1) + 1) →
          Matrix (Fin r) (Fin r) ℝ)
        (pivotInv : ℕ → Matrix (Fin r) (Fin r) ℝ)
        (hPivotRight : ∀ k : ℕ, ∀ hk : k < (m + 1) + 1,
          IsRightInverse r
            (higham13_algorithm13_3_schurStageMatrixBlock A pivotInv k
              ⟨k, hk⟩ ⟨k, hk⟩)
            (pivotInv k))
        (hdet : Matrix.det (blockMatrixFirstSplitFlat A :
          Matrix (Fin (r + (m + 1) * r)) (Fin (r + (m + 1) * r)) ℝ) ≠ 0)
        (hFulln : (((((m + 1) + 1) * r : ℕ) : ℝ) ≤ (n : ℝ))) :
        ∃ L U : Fin ((m + 1) + 1) → Fin ((m + 1) + 1) →
            Matrix (Fin r) (Fin r) ℝ,
          BlockLUFactSpec ((m + 1) + 1) r A L U ∧
            blockMaxNorm (Nat.succ_pos (m + 1)) hr L *
                blockMaxNorm (Nat.succ_pos (m + 1)) hr U ≤
              (n : ℝ) *
                (growthFactorEntry (Nat.add_pos_left hr ((m + 1) * r))
                  (blockMatrixFirstSplitFlat A)
                  (higham13_algorithm13_3_matrixStageHistoryGrowthMatrix
                    (Nat.add_pos_left hr ((m + 1) * r))
                    (Nat.succ_pos (m + 1)) hr A pivotInv)
                  (maxEntryNorm_pos_of_det_ne_zero
                    (Nat.add_pos_left hr ((m + 1) * r))
                    (blockMatrixFirstSplitFlat A) hdet)) ^ 3 *
                (maxEntryNormRect (Nat.add_pos_left hr ((m + 1) * r))
                    (Nat.add_pos_left hr ((m + 1) * r))
                    (blockMatrixFirstSplitFlat A) *
                  maxEntryNormRect (Nat.add_pos_left hr ((m + 1) * r))
                    (Nat.add_pos_left hr ((m + 1) * r))
                    (nonsingInv (r + (m + 1) * r)
                      (blockMatrixFirstSplitFlat A))) *
                maxEntryNormRect (Nat.add_pos_left hr ((m + 1) * r))
                  (Nat.add_pos_left hr ((m + 1) * r))
                  (blockMatrixFirstSplitFlat A)

    higham13_problem13_4_eq13_22_exists_blockLUFact_succ_of_pivot_right_inverse · 93 more declarations under this item

  • Equation (13.23)

    Source closure. For a point-row diagonally dominant matrix on which exact block Algorithm 13.3 succeeds, the scalar no-pivot producer supplies the ρ ≤ 2 history bound; the scalar/block active-stage bridge above transfers it to the global recursive Problem 13.4 aggregation. No growth, factor-norm, or target-scale premise is required from the caller.

    Lean statement
    theorem higham13_problem13_4_eq13_23_exists_blockLUFact_succ_of_pointRow
        {m r n : ℕ} (hr : 0 < r)
        (A : Fin ((m + 1) + 1) → Fin ((m + 1) + 1) →
          Matrix (Fin r) (Fin r) ℝ)
        (pivotInv : ℕ → Matrix (Fin r) (Fin r) ℝ)
        (hPivotRight : ∀ k : ℕ, ∀ hk : k < (m + 1) + 1,
          IsRightInverse r
            (higham13_algorithm13_3_schurStageMatrixBlock A pivotInv k
              ⟨k, hk⟩ ⟨k, hk⟩)
            (pivotInv k))
        (hRow : IsRowDiagDominant (((m + 1) + 1) * r) (blockMatrixFlatFin A))
        (hdet : Matrix.det (blockMatrixFirstSplitFlat A :
          Matrix (Fin (r + (m + 1) * r)) (Fin (r + (m + 1) * r)) ℝ) ≠ 0)
        (hFulln : (((((m + 1) + 1) * r : ℕ) : ℝ) ≤ (n : ℝ))) :
        ∃ L U : Fin ((m + 1) + 1) → Fin ((m + 1) + 1) →
            Matrix (Fin r) (Fin r) ℝ,
          BlockLUFactSpec ((m + 1) + 1) r A L U ∧
            blockMaxNorm (Nat.succ_pos (m + 1)) hr L *
                blockMaxNorm (Nat.succ_pos (m + 1)) hr U ≤
              8 * (n : ℝ) *
                (maxEntryNormRect (Nat.add_pos_left hr ((m + 1) * r))
                    (Nat.add_pos_left hr ((m + 1) * r))
                    (blockMatrixFirstSplitFlat A) *
                  maxEntryNormRect (Nat.add_pos_left hr ((m + 1) * r))
                    (Nat.add_pos_left hr ((m + 1) * r))
                    (nonsingInv (r + (m + 1) * r)
                      (blockMatrixFirstSplitFlat A))) *
                maxEntryNormRect (Nat.add_pos_left hr ((m + 1) * r))
                  (Nat.add_pos_left hr ((m + 1) * r))
                  (blockMatrixFirstSplitFlat A)

    higham13_problem13_4_eq13_23_exists_blockLUFact_succ_of_pointRow · 143 more declarations under this item

  • Equation (13.24)

    For the concrete Algorithm 13.3 factors of an SPD block matrix. No factor-norm premises are assumed: the two bounds and their printed product consequence are derived from SPD via Lemmas 13.9--13.10.

    Lean statement
    theorem higham13_eq13_24_algorithm13_3_spd
        {m r : ℕ} (hr : 0 < r)
        (A : Fin m → Fin m → Matrix (Fin r) (Fin r) ℝ)
        (hSPD : IsSymPosDef (m * r) (blockMatrixFlatFin A)) :
        ∃ pivotInv : ℕ → Matrix (Fin r) (Fin r) ℝ,
          (∀ k : ℕ, ∀ hk : k < m,
            IsRightInverse r
              (higham13_algorithm13_3_schurStageMatrixBlock A pivotInv k
                ⟨k, hk⟩ ⟨k, hk⟩)
              (pivotInv k)) ∧
          BlockLUFactSpec m r A
            (higham13_algorithm13_3_lowerFromMatrixStages A pivotInv)
            (higham13_algorithm13_3_upperFromMatrixStages A pivotInv) ∧
          opNorm2
              (blockMatrixFlatFin
                (higham13_algorithm13_3_lowerFromMatrixStages A pivotInv)) ≤
            1 + (m : ℝ) *
              Real.sqrt (kappa2 (blockMatrixFlatFin A)
                (nonsingInv (m * r) (blockMatrixFlatFin A))) ∧
          opNorm2
              (blockMatrixFlatFin
                (higham13_algorithm13_3_upperFromMatrixStages A pivotInv)) ≤
            Real.sqrt (m : ℝ) * opNorm2 (blockMatrixFlatFin A) ∧
          opNorm2
              (blockMatrixFlatFin
                (higham13_algorithm13_3_lowerFromMatrixStages A pivotInv)) *
            opNorm2
              (blockMatrixFlatFin
                (higham13_algorithm13_3_upperFromMatrixStages A pivotInv)) ≤
            Real.sqrt (m : ℝ) *
              (1 + (m : ℝ) *
                Real.sqrt (kappa2 (blockMatrixFlatFin A)
                  (nonsingInv (m * r) (blockMatrixFlatFin A)))) *
              opNorm2 (blockMatrixFlatFin A)

    higham13_eq13_24_algorithm13_3_spd · 1 more declaration under this item

  • Equation (13.25)

    As the exact first-order composition of Theorem 13.6 with equation (13.24).

    Lean statement
    theorem higham13_eq13_25_spd_firstOrder_from_eq13_24
        (err u c_n normA normLU kappa : ℝ) (m : ℕ)
        (hm : 0 < m) (hu : 0 ≤ u) (hc : 0 ≤ c_n) (hA : 0 ≤ normA)
        (hErr : FirstOrderLe u (c_n * u * (normA + normLU)) err)
        (hLU : normLU ≤
          Real.sqrt (m : ℝ) * (1 + (m : ℝ) * Real.sqrt kappa) * normA) :
        FirstOrderLe u
          (c_n * Real.sqrt (m : ℝ) * u * normA *
            (2 + (m : ℝ) * Real.sqrt kappa)) err

    higham13_eq13_25_spd_firstOrder_from_eq13_24 · 7 more declarations under this item

  • Equation (13.26)

    Problem 13.4 partition display. This is the same four-block partition as (13.20), with the additional source assumption that the leading block is nonsingular. The nonsingularity is recorded as an Invertible hypothesis for downstream Schur-complement and condition-number work; the display itself is again fromBlocks.

    Lean statement
    theorem higham13_eq13_26_partition {r s α : Type*}
        [Fintype r] [DecidableEq r] [Semiring α]
        (A : Matrix (r ⊕ s) (r ⊕ s) α) [Invertible A.toBlocks₁₁] :
        A = Matrix.fromBlocks A.toBlocks₁₁ A.toBlocks₁₂ A.toBlocks₂₁ A.toBlocks₂₂

    higham13_eq13_26_partition

Problems and exercises

  • Problem 13.1

    Problem 13.1 (Higham, 2nd ed., Chapter 13, p. 257), column-dominant block-tridiagonal LU step, in norm-level form. For a block tridiagonal A = L U with L and U block bidiagonal and U_{i-1,i} = A_{i-1,i}, the local subordinate-norm estimate ‖L_{i,i-1}‖ ≤ ‖A_{i,i-1}‖ ‖U_{i-1,i-1}^{-1}‖, together with the inherited column block diagonal dominance bound ‖A_{i,i-1}‖ ‖U_{i-1,i-1}^{-1}‖ ≤ 1, gives the source bounds ‖L_{i,i-1}‖ ≤ 1 and ‖U_{ii}‖ ≤ ‖A_{ii}‖ + ‖A_{i-1,i}‖.

    Lean statement
    theorem higham13_problem13_1_column_step_bounds
        (ellNorm uDiagNorm aDiagNorm aLowerNorm aUpperNorm uPrevInvNorm : ℝ)
        (hEll : ellNorm ≤ aLowerNorm * uPrevInvNorm)
        (hColDom : aLowerNorm * uPrevInvNorm ≤ 1)
        (hUDiag : uDiagNorm ≤ aDiagNorm + ellNorm * aUpperNorm)
        (hUpperNonneg : 0 ≤ aUpperNorm) :
        ellNorm ≤ 1 ∧ uDiagNorm ≤ aDiagNorm + aUpperNorm

    higham13_problem13_1_column_step_bounds

  • Problem 13.2

    Problem 13.2 (Higham, 2nd ed., Chapter 13, p. 257): for the 1-norm and infinity norm, point diagonal dominance and block diagonal dominance do not imply each other. The 1-norm statements use column diagonal dominance and block-column dominance; the infinity-norm statements use row diagonal dominance and block-row dominance.

    Lean statement
    theorem higham13_problem13_2_incomparability :
        (IsDiagDominant 4 higham13_problem13_2_point_col_not_block_col_matrix ∧
          ¬ IsBlockDiagDomCol 2
            higham13_problem13_2_point_col_not_block_col_blockNormOne
            higham13_problem13_2_point_col_not_block_col_invDiagOne) ∧
        (IsBlockDiagDomCol 2
            higham13_problem13_2_block_not_point_blockNormOne
            higham13_problem13_2_block_not_point_invDiagOne ∧
          ¬ IsDiagDominant 4 higham13_problem13_2_block_not_point_matrix) ∧
        (IsRowDiagDominant 4 higham13_problem13_2_point_row_not_block_row_matrix ∧
          ¬ IsBlockDiagDomRow 2
            higham13_problem13_2_point_row_not_block_row_blockNormInf
            higham13_problem13_2_point_row_not_block_row_invDiagInf) ∧
        (IsBlockDiagDomRow 2
            higham13_problem13_2_block_not_point_blockNormInf
            higham13_problem13_2_block_not_point_invDiagInf ∧
          ¬ IsRowDiagDominant 4 higham13_problem13_2_block_not_point_matrix)

    higham13_problem13_2_incomparability · 8 more declarations under this item

  • Problem 13.4

    Source-indexed exact-κ bounds with rho instantiated as the formal max-entry growth factor. This specializes higham13_problem13_4_maxEntry_bounds_from_source_schur_growth_exact_kappa by deriving the source Schur-growth premise from growthFactorEntry. The remaining mathematical source obligation is the concrete GE/stage bookkeeping certificate ||S||_max <= ||U||_max for the growth-factor matrix U.

    Lean statement
    theorem higham13_problem13_4_maxEntry_bounds_from_source_growthFactorEntry_exact_kappa
        {r s : ℕ} (hr : 0 < r) (hs : 0 < s) (hN : 0 < r + s)
        (A U : Fin (r + s) → Fin (r + s) → ℝ)
        (A11 : Matrix (Fin r) (Fin r) ℝ)
        (A12 : Matrix (Fin r) (Fin s) ℝ)
        (A21 : Matrix (Fin s) (Fin r) ℝ)
        (A22 : Matrix (Fin s) (Fin s) ℝ)
        [Invertible A11] [Invertible (A22 - A21 * ⅟A11 * A12)]
        [Invertible (Matrix.fromBlocks A11 A12 A21 A22)]
        (hA11_block : A11 =
          fun i j : Fin r =>
            A (finSumFinEquiv (Sum.inl i : Fin r ⊕ Fin s))
              (finSumFinEquiv (Sum.inl j : Fin r ⊕ Fin s)))
        (hA12_block : A12 =
          fun (i : Fin r) (j : Fin s) =>
            A (finSumFinEquiv (Sum.inl i : Fin r ⊕ Fin s))
              (finSumFinEquiv (Sum.inr j : Fin r ⊕ Fin s)))
        (hA21_block : A21 =
          fun (i : Fin s) (j : Fin r) =>
            A (finSumFinEquiv (Sum.inr i : Fin r ⊕ Fin s))
              (finSumFinEquiv (Sum.inl j : Fin r ⊕ Fin s)))
        (hA22_block : A22 =
          fun i j : Fin s =>
            A (finSumFinEquiv (Sum.inr i : Fin r ⊕ Fin s))
              (finSumFinEquiv (Sum.inr j : Fin r ⊕ Fin s)))
        (hApos : 0 < maxEntryNorm hN A)
        (n : ℕ)
        (hsn : (s : ℝ) ≤ (n : ℝ))
        (hS_le_U :
          maxEntryNormRect hs hs (A22 - A21 * ⅟A11 * A12) ≤
            maxEntryNorm hN U) :
        maxEntryNormRect hs hr ((A21 * ⅟A11 : Matrix (Fin s) (Fin r) ℝ)) ≤
            (n : ℝ) * growthFactorEntry hN A U hApos *
              (maxEntryNormRect hN hN A *
                maxEntryNormRect hN hN (nonsingInv (r + s) A)) ∧
          maxEntryNormRect hs hs (A22 - A21 * ⅟A11 * A12) *
              maxEntryNormRect hs hs
                ((⅟(A22 - A21 * ⅟A11 * A12)) : Matrix (Fin s) (Fin s) ℝ) ≤
            growthFactorEntry hN A U hApos *
              (maxEntryNormRect hN hN A *
                maxEntryNormRect hN hN (nonsingInv (r + s) A))

    higham13_problem13_4_maxEntry_bounds_from_source_growthFactorEntry_exact_kappa · 66 more declarations under this item

  • Problem 13.5

    Problem 13.5 (Higham, 2nd ed., Chapter 13, p. 258): if A = [[A11, A12], [A21, A22]] is point diagonally dominant by columns on the leading block columns and A11_inv is a right inverse of A11, then ‖A21 A11⁻¹‖₁ ≤ 1. The nonsingularity assumption on A11 is represented by the explicit right-inverse equation A11 * A11_inv = I, matching the repository's function-matrix API.

    Lean statement
    theorem higham13_problem13_5_oneNormRect_bound {r s : ℕ}
        (A11 : Fin r → Fin r → ℝ) (A21 : Fin s → Fin r → ℝ)
        (A11_inv : Fin r → Fin r → ℝ)
        (hdom : ∀ j : Fin r,
          higham13_problem13_5_columnOff A11 j +
            higham13_problem13_5_trailingCol A21 j ≤ |A11 j j|)
        (hright : ∀ i j : Fin r,
          ∑ k : Fin r, A11 i k * A11_inv k j = if i = j then 1 else 0) :
        oneNormRect (rectMatMul A21 A11_inv) ≤ 1

    higham13_problem13_5_oneNormRect_bound · 3 more declarations under this item

  • Problem 13.7

    Schur determinant identity. For a block matrix X = [[A, B], [C, D]] with invertible leading block A, Mathlib's Schur complement determinant theorem gives det X = det A * det (D - C A^{-1} B).

    Lean statement
    theorem higham13_problem13_7_det_schur
        {m n α : Type*} [Fintype m] [Fintype n] [DecidableEq m] [DecidableEq n]
        [CommRing α]
        (A : Matrix m m α) (B : Matrix m n α) (C : Matrix n m α) (D : Matrix n n α)
        [Invertible A] :
        (Matrix.fromBlocks A B C D).det = A.det * (D - C * ⅟A * B).det

    higham13_problem13_7_det_schur · 1 more declaration under this item

  • Problem 13.8

    Block inverse formula around an invertible leading block. This is the standard inverse formula expressed in terms of the Schur complement D - C A^{-1} B.

    Lean statement
    theorem higham13_problem13_8_block_inverse
        {m n α : Type*} [Fintype m] [Fintype n] [DecidableEq m] [DecidableEq n]
        [CommRing α]
        (A : Matrix m m α) (B : Matrix m n α) (C : Matrix n m α) (D : Matrix n n α)
        [Invertible A] [Invertible (D - C * ⅟A * B)]
        [Invertible (Matrix.fromBlocks A B C D)] :
        ⅟(Matrix.fromBlocks A B C D) =
          Matrix.fromBlocks
            (⅟A + ⅟A * B * ⅟(D - C * ⅟A * B) * C * ⅟A)
            (-(⅟A * B * ⅟(D - C * ⅟A * B)))
            (-(⅟(D - C * ⅟A * B) * C * ⅟A))
            (⅟(D - C * ⅟A * B))

    higham13_problem13_8_block_inverse

  • Problem 13.9

    Resolvent identity: (I - A B)^{-1} = I + A (I - B A)^{-1} B. The proof verifies that the displayed right-hand side is a right inverse of I - A B; the Invertible hypotheses record the nonsingularity conditions under which the inverses are interpreted.

    Lean statement
    theorem higham13_problem13_9_resolvent_identity
        {m n α : Type*} [Fintype m] [Fintype n] [DecidableEq m] [DecidableEq n]
        [CommRing α]
        (A : Matrix m n α) (B : Matrix n m α)
        [Invertible (1 - A * B : Matrix m m α)]
        [Invertible (1 - B * A : Matrix n n α)] :
        ⅟(1 - A * B) = 1 + A * ⅟(1 - B * A) * B

    higham13_problem13_9_resolvent_identity · 1 more declaration under this item

Chapter 15 · Condition-number estimation all chapters

Definitions, theorems and lemmas

  • Algorithm 15.3

    Algorithm 15.3 — full printed guarantee (Higham §15.3, Algorithm 15.3, p. 292), bundling both printed conclusions for the computed pair (γ, x): γ ≤ ‖A‖₁ and ‖Ax‖₁ = γ‖x‖₁.

    Lean statement
    theorem H15_Algorithm15_3_spec {n : ℕ} (hn : 0 < n)
        (A : Fin n → Fin n → ℝ) (fuel : ℕ) :
        H15_Algorithm15_3_gamma hn A fuel ≤ oneNorm A ∧
        oneNormVec (fun i => ∑ j : Fin n, A i j * H15_Algorithm15_3_x hn A fuel j) =
          H15_Algorithm15_3_gamma hn A fuel *
            oneNormVec (H15_Algorithm15_3_x hn A fuel)

    H15_Algorithm15_3_spec · 3 more declarations under this item

  • Algorithm 15.4

    Algorithm 15.4 — exact returned-ratio guarantee (Higham §15.3, Algorithm 15.4, p. 293). The estimator returns the maximum of its power-method estimate and the alternating-vector estimate. If the power arm wins, H15_Algorithm15_3_stored_gamma_realized supplies the normalized iterate at which that stored estimate was computed. If the alternating arm wins, take w = lapackAltVec directly. Thus in either branch there are genuine vectors w and v = A w satisfying the printed equality ‖v‖₁ / ‖w‖₁ = γ, together with γ ≤ ‖A‖₁.

    Lean statement
    theorem H15_Algorithm15_4_exact_ratio_witness {n : ℕ} (hn : 0 < n)
        (A : Fin n → Fin n → ℝ) :
        ∃ (w v : Fin n → ℝ),
          (∀ i, v i = ∑ j : Fin n, A i j * w j) ∧
          oneNormVec v / oneNormVec w = H15_Algorithm15_4_gamma hn A ∧
          H15_Algorithm15_4_gamma hn A ≤ oneNorm A

    H15_Algorithm15_4_exact_ratio_witness · 4 more declarations under this item

  • Algorithm 15.5

    Algorithm 15.5 solves U y = d. Immediate from linpackD being defined as the residual U y; recorded to match the book's step "solve U y = d".

    Lean statement
    theorem linpackY_solves {n : ℕ} (U : Fin n → Fin n → ℝ)
        (sgn : Fin n → (Fin n → ℝ) → ℝ) :
        matMulVec n U (linpackY U sgn) = linpackD U sgn

    linpackY_solves · 2 more declarations under this item

  • Theorem 15.6

    Theorem 15.6 (Dixon), closed source-shaped endpoint. For a certified inverse B = A⁻¹, a positive integer k, and θ > 1, the actual inverse Gram matrix is BᵀB = (AAᵀ)⁻¹; the left powered inequality holds for every unit vector; and the right powered inequality holds for a uniform sphere point with probability at least 1 - 0.8 * θ^(-k/2) * sqrt n. The powered event is exactly the nonnegative 2k-th-power form of display (15.7): ‖B‖₂ ≤ θ * (xᵀ(BᵀB)^k x)^(1/(2k)).

    Lean statement
    theorem higham15_6_dixon_closed
        (d k : ℕ) (hk : 0 < k)
        (A B : Fin (d + 1) → Fin (d + 1) → ℝ)
        (hR : IsRightInverse (d + 1) A B)
        (hL : IsLeftInverse (d + 1) A B)
        (θ : ℝ) (hθ : 1 < θ) :
        IsInverse (d + 1)
            (matMul (d + 1) A (matTranspose A))
            (matMul (d + 1) (matTranspose B) B) ∧
          (∀ x : OrthogonalSphere (d + 1),
            finiteQuadraticForm
                (matPow (d + 1)
                  (matMul (d + 1) (matTranspose B) B) k)
                (WithLp.ofLp (x : EuclideanSpace ℝ (Fin (d + 1)))) ≤
              opNorm2 B ^ (2 * k)) ∧
          ENNReal.ofReal
              (1 - ((4 : ℝ) / 5) * Real.sqrt (d + 1) *
                θ ^ (-(k : ℝ) / 2 : ℝ)) ≤
            standardGaussianDirectionMeasure d
              {x : OrthogonalSphere (d + 1) |
                opNorm2 B ^ (2 * k) ≤
                  (θ ^ k) ^ 2 *
                    finiteQuadraticForm
                      (matPow (d + 1)
                        (matMul (d + 1) (matTranspose B) B) k)
                      (WithLp.ofLp
                        (x : EuclideanSpace ℝ (Fin (d + 1))))}

    higham15_6_dixon_closed · 4 more declarations under this item

  • Theorem 15.9

    Theorem 15.9 (Ikebe; Higham, §15.6, p. 300), at its printed structural strength. For a nonempty irreducible tridiagonal matrix A, any matrix carrying the actual certificate A * A_inv = I has the rank-one inverse representation A_inv i j = x i * y j for i ≤ j, and A_inv i j = p i * q j for i ≥ j. No LU factorization, pivot-nonzero premise, inverse-entry formula, or target-bearing rank condition is assumed.

    Lean statement
    theorem H15_Theorem15_9_of_irreducible_rightInverse {n : ℕ} (hn : 0 < n)
        (T : TridiagData n) (A_inv : Fin n → Fin n → ℝ)
        (hIrred : IsIrreducibleTridiag T)
        (hRight : IsRightInverse n (tridiag_to_matrix T) A_inv) :
        ∃ (x y p q : Fin n → ℝ),
          (∀ i j : Fin n, i.val ≤ j.val → A_inv i j = x i * y j) ∧
          (∀ i j : Fin n, j.val ≤ i.val → A_inv i j = p i * q j)

    H15_Theorem15_9_of_irreducible_rightInverse · 1 more declaration under this item

Equations and other results

  • Equation (15.1)

    For nonnegative diagonal scaling, the infinity norm of |A⁻¹|d equals the matrix infinity norm of A⁻¹D.

    Lean statement
    theorem cond_norm_identity (n : ℕ) (_hn : 0 < n)
        (A_inv : Fin n → Fin n → ℝ) (d : Fin n → ℝ) (hd : ∀ i, 0 ≤ d i) :
        infNormVec (fun i => ∑ j : Fin n, |A_inv i j| * d j) =
        infNorm (fun i j => A_inv i j * d j)

    cond_norm_identity · 2 more declarations under this item

Chapter 16 · The Sylvester equation all chapters

  • Equation (16.2)

    Higham, 2nd ed., Chapter 16.1, equations (16.2)-(16.3), diagonal case: a positive uniform gap |a_i - b_j| >= sigma makes the square vec/Kronecker Sylvester coefficient nonsingular.

    Lean statement
    theorem sylvesterVecCoeff_diagonal_det_ne_zero_of_entrywise_abs_ge
        (n : Nat) (a b : Fin n -> Real) (sigma : Real)
        (hsigma : 0 < sigma)
        (hgap : forall i j, sigma <= |a i - b j|) :
        (sylvesterVecCoeff n n (Matrix.diagonal a) (Matrix.diagonal b)).det ≠ 0

    sylvesterVecCoeff_diagonal_det_ne_zero_of_entrywise_abs_ge · 180 more declarations under this item

  • Equation (16.4)

    Higham, 2nd ed., Chapter 16.2, equations (16.4)-(16.8), converse two-by-two spectral certificate: a nonnegative real discriminant for the adjacent real Schur block gives a concrete real eigenline. This is the algebraic obstruction to treating such a block as a genuine irreducible real 2 x 2 block.

    Lean statement
    theorem sylvesterTwoColumnRealSchurBlock_exists_real_eigenvector_of_disc_nonneg
        (n : Nat) (T : RMatFn n n) (p q : Fin n)
        (hdisc :
          0 ≤ (T p p - T q q) ^ 2 + 4 * T p q * T q p) :
        exists x : Fin 2 -> Real, x ≠ 0 ∧
          exists nu : Real,
            Matrix.mulVec (sylvesterTwoColumnRealSchurBlock n T p q) x =
              fun k => nu * x k

    sylvesterTwoColumnRealSchurBlock_exists_real_eigenvector_of_disc_nonneg · 230 more declarations under this item

  • Equation (16.9)

    Higham, 2nd ed., Chapter 16.2, equation (16.9), conditional exact residual-bound transport. Any Schur-coordinate Frobenius residual bound transfers unchanged to the reconstructed original-coordinate iterate.

    Lean statement
    theorem frobNormRect_sylvesterResidualRect_le_of_schur_transform (m n : Nat)
        (U R A : RMatFn m m) (V S B : RMatFn n n) (C Y : RMatFn m n)
        (rho : Real)
        (hU : IsOrthogonal m U) (hV : IsOrthogonal n V)
        (hA : A = rectMatMul U (rectMatMul R (matTranspose U)))
        (hB : B = rectMatMul V (rectMatMul S (matTranspose V)))
        (hres :
          frobNormRect
            (sylvesterResidualRect m n R S
              (rectMatMul (matTranspose U) (rectMatMul C V)) Y) <= rho) :
        frobNormRect
            (sylvesterResidualRect m n A B C
              (rectMatMul U (rectMatMul Y (matTranspose V)))) <= rho

    frobNormRect_sylvesterResidualRect_le_of_schur_transform · 18 more declarations under this item

  • Equation (16.15)

    Source-facing two-sided Sylvester eta/xi infimum bound from SVD data.

    Lean statement
    theorem sylvesterBackwardErrorInf_two_sided_sqrt_xiSq_of_svdOptimalPerturbations
        (n : Nat)
        (A B C Y U V : Fin n -> Fin n -> Real) (sigma : Fin n -> Real)
        (alpha beta gamma : Real)
        (hSVD : IsSVD n Y U V sigma)
        (halpha : 0 < alpha) (hbeta : 0 < beta) (hgamma : 0 < gamma)
        (hpos : forall i j : Fin n,
          0 < alpha ^ 2 * sigma j ^ 2 + beta ^ 2 * sigma i ^ 2 + gamma ^ 2) :
        Real.sqrt
            (xiSq n (svdResidual n U V (sylvesterResidual n A B C Y))
              sigma alpha beta gamma / 3) <=
          sylvesterBackwardErrorInf n A B C Y alpha beta gamma ∧
        sylvesterBackwardErrorInf n A B C Y alpha beta gamma <=
          Real.sqrt
            (xiSq n (svdResidual n U V (sylvesterResidual n A B C Y))
              sigma alpha beta gamma)

    sylvesterBackwardErrorInf_two_sided_sqrt_xiSq_of_svdOptimalPerturbations · 28 more declarations under this item

  • Equation (16.16)

    ξ² is nonneg when all denominators are positive.

    Lean statement
    lemma xiSq_nonneg {n : ℕ} (R_tilde : Fin n → Fin n → ℝ) (σ : Fin n → ℝ)
        (α β γ : ℝ)
        (hpos : ∀ i j : Fin n, 0 < α ^ 2 * σ j ^ 2 + β ^ 2 * σ i ^ 2 + γ ^ 2) :
        0 ≤ xiSq n R_tilde σ α β γ

    xiSq_nonneg

  • Equation (16.21)

    Lyapunov eta infimum bounded by the mu-scaled relative residual.

    Lean statement
    theorem lyapunovBackwardErrorInf_le_mu_relative_residual_of_symmetric_spectral
        (n : Nat)
        (A C Y U : Fin n -> Fin n -> Real) (lam : Fin n -> Real)
        (alpha gamma lamStar : Real)
        (hY : Y = matMul n U (matMul n (diagMatrix lam) (matTranspose U)))
        (hU : IsOrthogonal n U)
        (hC : IsSymmetricFiniteMatrix C) (hYsym : IsSymmetricFiniteMatrix Y)
        (hpos : forall i j : Fin n,
          0 < 2 * alpha ^ 2 * (lam i ^ 2 + lam j ^ 2) + gamma ^ 2)
        (hLam : forall i : Fin n, lamStar ^ 2 <= lam i ^ 2)
        (hDenom : 0 < 4 * alpha ^ 2 * lamStar ^ 2 + gamma ^ 2)
        (hScale : 0 < 2 * alpha * frobNorm Y + gamma) :
        lyapunovBackwardErrorInf n A C Y alpha gamma <=
          lyapunovAmplificationMu alpha gamma (frobNorm Y) lamStar *
            (frobNorm (lyapunovResidual n A C Y) /
              (2 * alpha * frobNorm Y + gamma))

    lyapunovBackwardErrorInf_le_mu_relative_residual_of_symmetric_spectral · 49 more declarations under this item

  • Equation (16.23)

    Higham, 2nd ed., Section 16.3-16.4, equations (16.23)-(16.24): a positive lower bound on the exact infimum model of sep(A,B) instantiates the structured first-order Psi certificate through the safe reciprocal condition value 1 / sigma.

    Lean statement
    theorem sylvesterPsi_of_pos_le_sylvesterSepInf_isPsiFirstOrderBound (n : Nat)
        (A B X : Fin n -> Fin n -> Real) (alpha beta gamma sigma : Real)
        (halpha : 0 < alpha) (hbeta : 0 < beta) (hgamma : 0 < gamma)
        (hsigma : 0 < sigma) (hX : 0 < frobNorm X)
        (hle : sigma <= sylvesterSepInf n A B) :
        SylvesterPsiFirstOrderBound n A B X alpha beta gamma
          (sylvesterPsi_of_inverseOpBound n X alpha beta gamma (1 / sigma))

    sylvesterPsi_of_pos_le_sylvesterSepInf_isPsiFirstOrderBound · 60 more declarations under this item

  • Equation (16.25)

    Higham, 2nd ed., Chapter 16.3, equations (16.25)-(16.26): a Sylvester operator sigma-min certificate makes the vectorized coefficient map injective.

    Lean statement
    theorem sylvesterVecCoeff_mulVec_injective_of_operator_sigmaMin
        (n : Nat) (A B : Fin n -> Fin n -> Real) (sigma : Real)
        (hsigma : 0 < sigma)
        (hSigmaMin : forall Y : Fin n -> Fin n -> Real,
          sigma * frobNorm Y <= frobNorm (sylvesterOp n A B Y)) :
        Function.Injective (Matrix.mulVec (sylvesterVecCoeff n n A B))

    sylvesterVecCoeff_mulVec_injective_of_operator_sigmaMin · 50 more declarations under this item

  • Equation (16.26)

    Higham, 2nd ed., Chapter 16.2.1 and 16.3, equations (16.26)-(16.27): under a positive Lyapunov operator sigma-min certificate, zero exact Lyapunov residual norm certifies that the residual-zero candidate is the unique exact solution. Scope: exact arithmetic and certificate transfer only. This removes the separate SepLowerBound assumption from the residual-zero uniqueness route; it does not construct the sigma-min certificate or model rounded residual arithmetic.

    Lean statement
    theorem lyapunov_solution_eq_of_residual_norm_zero_sigmaMin (n : Nat)
        (A C X Xhat : Fin n -> Fin n -> Real)
        (sigma : Real) (hsigma : 0 < sigma)
        (hSigmaMin : forall Y : Fin n -> Fin n -> Real,
          sigma * frobNorm Y <= frobNorm (lyapunovOp n A Y))
        (hExact : forall i j, lyapunovOp n A X i j = C i j)
        (hResidual : frobNorm (lyapunovResidual n A C Xhat) = 0) :
        forall i j, X i j = Xhat i j

    lyapunov_solution_eq_of_residual_norm_zero_sigmaMin · 125 more declarations under this item

  • Equation (16.27)

    Higham, 2nd ed., Chapter 16.3, equation (16.27): a finite Gram-eigenvalue lower bound for the printed Lyapunov vec/Kronecker coefficient instantiates the Lyapunov condition certificate with inverse-operator constant 1 / sqrt(lam).

    Lean statement
    theorem lyapunovCond_of_vecCoeff_gram_eigenvalues_isLyapunovConditionFirstOrderBound
        (n : Nat) (A X : Fin n -> Fin n -> Real) (alpha gamma lam : Real)
        (halpha : 0 < alpha) (hgamma : 0 < gamma) (hlam : 0 < lam)
        (hX : 0 < frobNorm X)
        (hEig : forall p : Prod (Fin n) (Fin n),
          lam <= finiteHermitianEigenvalues
            (finiteMatrixGram (lyapunovVecCoeff n A))
            (isSymmetricFiniteMatrix_finiteMatrixGram
              (lyapunovVecCoeff n A)) p) :
        LyapunovConditionFirstOrderBound n A X alpha gamma
          (lyapunovCond_of_inverseOpBound n X alpha gamma
            (1 / Real.sqrt lam))

    lyapunovCond_of_vecCoeff_gram_eigenvalues_isLyapunovConditionFirstOrderBound · 71 more declarations under this item

  • Equation (16.29)

    Higham, 2nd ed., Chapter 16.4, equation (16.29): source-numbered alias for the strict real-quasi-Schur shifted determinant-discharge practical residual endpoint.

    Lean statement
    theorem H16_eq16_29_realQuasiSchur_strictBlockMap_shifted_computed_residual_certificate
        (m n : Nat)
        (U R A : RMatFn m m) (V S B : RMatFn n n)
        (pA : Fin m -> Nat) (pB : Fin n -> Nat)
        (C X Xhat Rhat Ru : RMatFn m n)
        (hU : IsOrthogonal m U) (hV : IsOrthogonal n V)
        (hA : A = rectMatMul U (rectMatMul R (matTranspose U)))
        (hB : B = rectMatMul V (rectMatMul S (matTranspose V)))
        (hpAmono : Monotone pA)
        (hpAcard :
          forall c : Nat, (Finset.univ.filter (fun i : Fin m => pA i = c)).card <= 2)
        (hRstrict : forall i j : Fin m, pA j < pA i -> R i j = 0)
        (hpBmono : Monotone pB)
        (hpBcard :
          forall c : Nat, (Finset.univ.filter (fun j : Fin n => pB j = c)).card <= 2)
        (hpBstrict : forall {i j : Fin n}, j < i -> pB j < pB i)
        (hSstrict : forall i j : Fin n, pB j < pB i -> S i j = 0)
        (hshift : forall k : Fin n,
          Not (Matrix.det (sylvesterTriangularShiftedCoeff m R (S k k)) = 0))
        (hX : IsSylvesterSolutionRect m n A B C X)
        (hBudget : IsSylvesterComputedResidualBudget m n A B C Xhat Rhat Ru)
        (hXhat : 0 < sylvesterMaxEntryNormRect m n Xhat) :
        sylvesterMaxEntryNormRect m n (fun i j => X i j - Xhat i j) /
            sylvesterMaxEntryNormRect m n Xhat <=
          sylvesterVecMaxNorm m n
            (sylvesterPracticalBudgetVec m n
              (sylvesterVecCoeffNonsingInvAbs m n A B) Rhat Ru) /
            sylvesterMaxEntryNormRect m n Xhat

    H16_eq16_29_realQuasiSchur_strictBlockMap_shifted_computed_residual_certificate · 88 more declarations under this item

  • Equation (16.30)

    The residual for equation (16.30) is zero exactly when the generalized Sylvester equation holds.

    Lean statement
    theorem generalizedSylvesterAXB_CXD_residual_zero_iff_solution (m n : Nat)
        (A C : RMatFn m m) (B D : RMatFn n n) (E X : RMatFn m n) :
        (forall i j, generalizedSylvesterAXB_CXD_residual m n A C B D E X i j = 0) <->
          IsGeneralizedSylvesterAXB_CXD_Solution m n A C B D E X

    generalizedSylvesterAXB_CXD_residual_zero_iff_solution

  • Equation (16.31)

    Higham, 2nd ed., Chapter 16.5, equation (16.31): the two residuals vanish exactly when the coupled generalized Sylvester equations hold.

    Lean statement
    theorem generalizedSylvesterPair_residual_zero_iff_solution (m n : Nat)
        (A D : RMatFn m m) (B E : RMatFn n n)
        (C F0 X Y : RMatFn m n) :
        ((forall i j,
            generalizedSylvesterPairResidualLeft m n A B C X Y i j = 0) ∧
          (forall i j,
            generalizedSylvesterPairResidualRight m n D E F0 X Y i j = 0)) <->
          IsGeneralizedSylvesterPairSolution m n A D B E C F0 X Y

    generalizedSylvesterPair_residual_zero_iff_solution

  • Equation (16.32)

    The residual for equation (16.32) is zero exactly when the Riccati source equation holds.

    Lean statement
    theorem riccatiResidual_zero_iff_solution (m n : Nat)
        (A : RMatFn m m) (B : RMatFn n n) (F : RMatFn n m)
        (G X : RMatFn m n) :
        (forall i j, riccatiResidual m n A B F G X i j = 0) <->
          IsRiccatiSolution m n A B F G X

    riccatiResidual_zero_iff_solution

Chapter 17 · Stationary iterative methods all chapters

  • Equation (17.3)

    Finite-sum closed form for the source-sign computed stationary iteration.

    Lean statement
    theorem sourceComputedIteration_finite_sum (n : ℕ)
        (M N M_inv : Fin n → Fin n → ℝ) (b : Fin n → ℝ)
        (x_hat ξ : ℕ → Fin n → ℝ)
        (hLeft : IsLeftInverse n M M_inv)
        (hIter : SourceComputedIteration n M N b x_hat ξ)
        (m : ℕ) :
        ∀ i, x_hat (m + 1) i =
          matMulVec n (matPow n (iterMatrix n M_inv N) (m + 1)) (x_hat 0) i +
          ∑ k ∈ Finset.range (m + 1),
            matMulVec n (matPow n (iterMatrix n M_inv N) k)
              (matMulVec n M_inv (fun j => b j - ξ (m - k) j)) i

    sourceComputedIteration_finite_sum · 1 more declaration under this item

  • Equation (17.4)

    An exact solution of Ax = b is a fixed point of the stationary affine map x ↦ Gx + M⁻¹b, where G = M⁻¹N.

    Lean statement
    theorem stationary_solution_fixed_point (n : ℕ)
        (A M N M_inv : Fin n → Fin n → ℝ)
        (hS : SplittingSpec n A M N M_inv)
        (b x : Fin n → ℝ) (hAx : ∀ i, ∑ j : Fin n, A i j * x j = b i) :
        ∀ i, x i =
          matMulVec n (iterMatrix n M_inv N) x i + matMulVec n M_inv b i

    stationary_solution_fixed_point · 1 more declaration under this item

  • Equation (17.5)

    Finite-sum forward-error recurrence for the source-sign computed stationary iteration.

    Lean statement
    theorem sourceComputedIteration_error_finite_sum (n : ℕ)
        (A M N M_inv : Fin n → Fin n → ℝ)
        (hS : SplittingSpec n A M N M_inv)
        (b x : Fin n → ℝ) (hAx : ∀ i, ∑ j : Fin n, A i j * x j = b i)
        (x_hat : ℕ → (Fin n → ℝ)) (ξ : ℕ → (Fin n → ℝ))
        (hIter : SourceComputedIteration n M N b x_hat ξ)
        (m : ℕ) :
        ∀ i, x i - x_hat (m + 1) i =
          matMulVec n (matPow n (iterMatrix n M_inv N) (m + 1))
            (fun j => x j - x_hat 0 j) i +
          ∑ k ∈ Finset.range (m + 1),
            matMulVec n (matPow n (iterMatrix n M_inv N) k)
              (matMulVec n M_inv (ξ (m - k))) i

    sourceComputedIteration_error_finite_sum

  • Equation (17.8)

    Eq. 17.8 (Normwise forward bound): ‖e_{m+1}‖∞ ≤ q^{m+1}·‖e₀‖∞ + μ·‖M⁻¹‖∞/(1−q) where q ≥ ‖G‖∞ and μ ≥ ‖ξ_k‖∞ for all k. Proved by induction from normwise_one_step_bound using geometric contraction.

    Lean statement
    theorem normwise_forward_bound (n : ℕ) (hn : 0 < n)
        (A M N M_inv : Fin n → Fin n → ℝ)
        (hS : SplittingSpec n A M N M_inv)
        (b x : Fin n → ℝ) (hAx : ∀ i, ∑ j : Fin n, A i j * x j = b i)
        (x_hat : ℕ → (Fin n → ℝ)) (ξ : ℕ → (Fin n → ℝ))
        (hIter : ComputedIteration n M N b x_hat ξ)
        (q : ℝ) (hq : 0 ≤ q) (hq1 : q < 1) (hG : infNorm (iterMatrix n M_inv N) ≤ q)
        (μ : ℝ) (hμ : 0 ≤ μ) (hξ_bound : ∀ k, infNormVec (ξ k) ≤ μ)
        (m : ℕ) :
        infNormVec (fun i => x i - x_hat (m + 1) i) ≤
          q ^ (m + 1) * infNormVec (fun i => x i - x_hat 0 i) +
          μ * infNorm M_inv / (1 - q)

    normwise_forward_bound

  • Equation (17.10)

    |ξ_k,i| ≤ c_n u(1+θ_x) ∑_j (|M_{ij}|+|N_{ij}|)|x_j|.

    Lean statement
    theorem local_error_simplified (n : ℕ) (M N : Fin n → Fin n → ℝ)
        (b x : Fin n → ℝ)
        (hAx : ∀ i, ∑ j : Fin n, (M i j - N i j) * x j = b i)
        (x_hat : ℕ → (Fin n → ℝ)) (ξ : ℕ → (Fin n → ℝ))
        (cn_u θ_x : ℝ) (hcn : 0 ≤ cn_u) (_hθ : 0 ≤ θ_x)
        (hx_bound : ∀ k i, |x_hat k i| ≤ θ_x * |x i|)
        (hLocal : LocalErrorBound n M N b x_hat ξ cn_u) :
        ∀ k i, |ξ k i| ≤ cn_u * (1 + θ_x) *
          ∑ j : Fin n, (|M i j| + |N i j|) * |x j|

    local_error_simplified

  • Equation (17.16)

    Eq. 17.16 (Jacobi): |M| + |N| = |A| for M = diag(A), N = diag(A) − A.

    Lean statement
    theorem jacobi_splitting_abs (n : ℕ) (A : Fin n → Fin n → ℝ)
        (M N : Fin n → Fin n → ℝ)
        (hM : ∀ i j, M i j = if i = j then A i i else 0)
        (hN : ∀ i j, N i j = M i j - A i j) :
        ∀ i j, |M i j| + |N i j| = |A i j|

    jacobi_splitting_abs · 2 more declarations under this item

  • Equation (17.17)

    Eq. 17.17 (SOR): |M| + |N| ≤ f(ω)|A| where f(ω) = (1+|1−ω|)/ω.

    Lean statement
    theorem sor_splitting_bound (n : ℕ) (A : Fin n → Fin n → ℝ)
        (ω : ℝ) (hω_pos : 0 < ω)
        (D L U : Fin n → Fin n → ℝ)
        (hDecomp : ∀ i j, A i j = D i j + L i j + U i j)
        (hD : ∀ i j, i ≠ j → D i j = 0)
        (hL : ∀ i j, j.val ≥ i.val → L i j = 0)
        (hU : ∀ i j, j.val ≤ i.val → U i j = 0)
        (M_sor N_sor : Fin n → Fin n → ℝ)
        (hM : ∀ i j, M_sor i j = (1 / ω) * (D i j + ω * L i j))
        (hN : ∀ i j, N_sor i j = (1 / ω) * ((1 - ω) * D i j - ω * U i j)) :
        ∀ i j, |M_sor i j| + |N_sor i j| ≤ ((1 + |1 - ω|) / ω) * |A i j|

    sor_splitting_bound · 3 more declarations under this item

  • Equation (17.18)

    AG = HA: Since A = M − N, both sides equal N − NM⁻¹N.

    Lean statement
    theorem AG_eq_HA (n : ℕ) (A M N M_inv : Fin n → Fin n → ℝ)
        (hS : SplittingSpec n A M N M_inv) :
        matMul n A (iterMatrix n M_inv N) =
        matMul n (dualIterMatrix n N M_inv) A

    AG_eq_HA · 4 more declarations under this item

  • Equation (17.19)

    Eq. 17.19 (Normwise residual bound): ‖r_{m+1}‖∞ ≤ q^{m+1}·‖r₀‖∞ + μ·‖I−H‖∞/(1−q) where q ≥ ‖H‖∞ and μ ≥ ‖ξ_k‖∞ for all k. Derived by induction from normwise_one_step_residual_bound using geometric contraction.

    Lean statement
    theorem normwise_residual_bound (n : ℕ) (hn : 0 < n)
        (A M N M_inv : Fin n → Fin n → ℝ)
        (hS : SplittingSpec n A M N M_inv)
        (b x : Fin n → ℝ) (hAx : ∀ i, ∑ j : Fin n, A i j * x j = b i)
        (x_hat : ℕ → (Fin n → ℝ)) (ξ : ℕ → (Fin n → ℝ))
        (hIter : ComputedIteration n M N b x_hat ξ)
        (q : ℝ) (hq : 0 ≤ q) (hq1 : q < 1)
        (hH : infNorm (dualIterMatrix n N M_inv) ≤ q)
        (μ : ℝ) (hμ : 0 ≤ μ) (hξ_bound : ∀ k, infNormVec (ξ k) ≤ μ)
        (m : ℕ) :
        infNormVec (fun i => b i - ∑ j, A i j * x_hat (m + 1) j) ≤
          q ^ (m + 1) * infNormVec (fun i => b i - ∑ j, A i j * x_hat 0 j) +
          μ * infNorm (matSub_id n (dualIterMatrix n N M_inv)) / (1 - q)

    normwise_residual_bound · 3 more declarations under this item

  • Equation (17.21)

    Exact stationary iterates for a consistent singular system satisfy the same finite affine unrolling x_{m+1} = G^{m+1} x_0 + sum_{k=0}^m G^k M⁻¹ b. The proof uses only the nonsingularity of M, not nonsingularity of A, which is precisely why the identity remains valid at the start of the singular-system analysis.

    Lean statement
    theorem singular_stationary_iterate_finite_sum (n : ℕ)
        (A M N M_inv : Fin n → Fin n → ℝ)
        (hS : SplittingSpec n A M N M_inv)
        (b : Fin n → ℝ) (x_seq : ℕ → Fin n → ℝ)
        (hIter : SourceComputedIteration n M N b x_seq (fun _ _ => 0))
        (m : ℕ) :
        ∀ i, x_seq (m + 1) i =
          matMulVec n (matPow n (iterMatrix n M_inv N) (m + 1)) (x_seq 0) i +
          ∑ k ∈ Finset.range (m + 1),
            matMulVec n (matPow n (iterMatrix n M_inv N) k)
              (matMulVec n M_inv b) i

    singular_stationary_iterate_finite_sum · 1 more declaration under this item

  • Equation (17.29)

    Finite normwise surface: a uniform local-error norm bound ||ξ_t||∞ ≤ μ bounds ||S_m||∞ by μ sum ||G^k E M⁻¹||∞. The source's displayed c_n u(1+gamma_x)(||M||∞+||N||∞)||x||∞ is obtained by instantiating μ with the normwise local-error estimate.

    Lean statement
    theorem singularErrorSourceTerm_norm_bound (n : ℕ) (hn : 0 < n)
        (G E M_inv : Fin n → Fin n → ℝ) (ξ : ℕ → Fin n → ℝ)
        (μ : ℝ) (hμ : 0 ≤ μ)
        (hξ : ∀ t : ℕ, infNormVec (ξ t) ≤ μ) (m : ℕ) :
        infNormVec (singularErrorSourceTerm n G E M_inv ξ m) ≤
          μ * singularErrorSourceNormSum n G E M_inv m

    singularErrorSourceTerm_norm_bound · 4 more declarations under this item

Chapter 18 · Matrix powers all chapters

  • Theorem 18.1

    Theorem 18.1 (Higham–Knight), complex Jordan data, limit form, abstract error model — Higham, Accuracy and Stability of Numerical Algorithms, 2nd ed., §18.2, Theorem 18.1 (pp. 347–348). Let A be a REAL n×n matrix (the computed iteration is a floating-point object, hence real, matching the book's setting) with COMPLEX Jordan-form similarity data: X·X⁻¹ = I over ℂ (as the vector action IsComplexMatrixRightInverse), X⁻¹  X = J for the real-cast  i j = ((A i j : ℝ) : ℂ), J upper bidiagonal with ‖J_{ii}‖ ≤ ρ < 1, superdiagonal moduli ≤ 1, all other entries zero, and every run of consecutive nonzero superdiagonal entries of length ≤ t − 1 (max Jordan block size ≤ t, via cJordanRunLength); all 1 ≤ t. Under the Higham–Knight condition (18.13) 4t·c·κ∞(X)·‖A‖∞ < (1−ρ)^t, κ∞(X) := complexMatrixInfNorm X * complexMatrixInfNorm X_inv, every real computed-power sequence v with per-step componentwise budget c (ComputedMatPowVec, eqs (18.10)–(18.11)) satisfies ‖v_m‖∞ → 0. Scope: complex Jordan data as hypothesis (every complex matrix has one; JNF existence itself is not formalized — Mathlib lacks it); this is the full generality of the printed statement for a real input matrix A. No assumed contraction/absorption hypothesis: the absorbing similarity is PROVED from the Jordan data (complex_jordan_similarity_absorbs, δ-scaling construction with the (1+1/m)^m < e < 4 optimisation).

    Lean statement
    theorem higham_18_1_complex_jordan_tendsto (n : ℕ)
        (A : Fin n → Fin n → ℝ) (X X_inv J : CMatrix n n)
        (hXr : IsComplexMatrixRightInverse X X_inv)
        (hsim : complexMatrixMul X_inv (complexMatrixMul
          (fun i j => ((A i j : ℝ) : ℂ)) X) = J)
        (hshape : ∀ i j : Fin n, (j : ℕ) ≠ (i : ℕ) → (j : ℕ) ≠ (i : ℕ) + 1 →
          J i j = 0)
        (ρ : ℝ) (hρ0 : 0 ≤ ρ) (hρ1 : ρ < 1)
        (hdiagbd : ∀ i, ‖J i i‖ ≤ ρ)
        (hsup : ∀ i j : Fin n, (j : ℕ) = (i : ℕ) + 1 → ‖J i j‖ ≤ 1)
        (t : ℕ) (ht1 : 1 ≤ t)
        (hrun : ∀ k, cJordanRunLength n J k ≤ t - 1)
        (v : ℕ → (Fin n → ℝ)) (c : ℝ) (hc : 0 ≤ c)
        (hComp : ComputedMatPowVec n A v c)
        (hCond : 4 * (t : ℝ) * c *
          (complexMatrixInfNorm X * complexMatrixInfNorm X_inv) * infNorm A
          < (1 - ρ) ^ t) :
        Filter.Tendsto (fun m => infNormVec (v m)) Filter.atTop (nhds 0)

    higham_18_1_complex_jordan_tendsto · 5 more declarations under this item

Chapter 19 · QR factorization all chapters

Definitions, theorems and lemmas

  • Theorem 19.4

    Householder QR backward error for a tall rectangular matrix, stated with the public Split 3B source-facing name. For A : R^(m x n) with 0 < n and n <= m, the concrete zero-aware Householder QR panel algorithm returns an upper-trapezoidal R_hat and an exact orthogonal witness Q such that A + dA = Q R_hat, with each perturbation column bounded by gamma_tilde fp m n times the corresponding input column norm.

    Lean statement
    theorem householder_qr_backward_error
        (fp : FPModel) (m n : Nat) (A : Fin m -> Fin n -> Real)
        (hn : 0 < n) (hnm : n <= m)
        (hvalid : gammaValid fp (n * householderConstructApplyGammaIndex m)) :
        HouseholderQRBackwardError m n A
          (fl_householderQRPanel_Q fp m n A)
          (fl_householderQRPanel_R fp m n A)
          (gamma_tilde fp m n)

    householder_qr_backward_error · 1 more declaration under this item

  • Theorem 19.10

    Givens QR backward error for a tall rectangular matrix, stated with the public Split 3B source-facing name. For A : R^(m x n) with 0 < n and n <= m, the concrete staged Givens QR algorithm returns an upper-trapezoidal R_hat and an exact orthogonal witness Q such that A + dA = Q R_hat, with each perturbation column bounded by the repository's conservative gamma_tilde fp m n times the corresponding input column norm.

    Lean statement
    theorem givens_qr_backward_error
        (fp : FPModel) (m n : Nat) (A : Fin m -> Fin n -> Real)
        (_hn : 0 < n) (_hnm : n <= m)
        (hvalid : gammaValid fp 8) :
        GivensQRBackwardError m n A
          (Classical.choose
            (fl_givensQRStageFold_sequence_columnFrob_backward_error_uniform
              fp m n A (givensQRStageCount m n) hvalid))
          (fl_givensQRStageFold fp m n (givensQRStageCount m n) A)
          (gamma_tilde fp m n)

    givens_qr_backward_error · 3 more declarations under this item

Equations and other results

  • Equation (19.7)

    Columnwise rectangular matrix plus right-hand-side accumulation. This is the source-faithful Householder QR shape: each matrix column, and the right-hand side, may have its own rounded perturbation matrix at each step. The exact reflector sequence P k is common, so the final representation still uses one theoretical orthogonal factor Q, while the perturbation bounds are columnwise.

    Lean statement
    theorem rect_orthogonal_columnwise_vector_sequence_geometric (m n r : ℕ)
        (A : Fin m → Fin n → ℝ) (b : Fin m → ℝ)
        (A_hat : ℕ → Fin m → Fin n → ℝ)
        (b_hat : ℕ → Fin m → ℝ)
        (P : ℕ → Fin m → Fin m → ℝ)
        (ΔPA : ℕ → Fin n → Fin m → Fin m → ℝ)
        (ΔPb : ℕ → Fin m → Fin m → ℝ)
        (c : ℝ) (hc : 0 ≤ c)
        (hInitA : A_hat 0 = A)
        (hInitb : b_hat 0 = b)
        (hP : ∀ k, k < r → IsOrthogonal m (P k))
        (hΔPA : ∀ k, k < r → ∀ j : Fin n, frobNorm (ΔPA k j) ≤ c)
        (hΔPb : ∀ k, k < r → frobNorm (ΔPb k) ≤ c)
        (hNextA : ∀ k, k < r → ∀ i j,
          A_hat (k + 1) i j =
            matMulVec m (fun a b => P k a b + ΔPA k j a b)
              (fun a => A_hat k a j) i)
        (hNextb : ∀ k, k < r →
          b_hat (k + 1) =
            matMulVec m (fun a b => P k a b + ΔPb k a b) (b_hat k)) :
        ∃ (Q : Fin m → Fin m → ℝ)
            (ΔA : Fin m → Fin n → ℝ) (Δb : Fin m → ℝ),
          IsOrthogonal m Q ∧
          (∀ i j, A_hat r i j =
            matMulRectLeft (matTranspose Q) (fun a b => A a b + ΔA a b) i j) ∧
          (∀ i, b_hat r i =
            matMulVec m (matTranspose Q) (fun a => b a + Δb a) i) ∧
          (∀ j : Fin n,
            vecNorm2 (fun i => ΔA i j) ≤
              ((1 + c) ^ r - 1) * vecNorm2 (fun i => A i j)) ∧
          vecNorm2 Δb ≤ ((1 + c) ^ r - 1) * vecNorm2 b

    rect_orthogonal_columnwise_vector_sequence_geometric

  • Equation (19.8)

    If each local step coefficient is already bounded by gamma k, the residual accumulation over r steps is bounded by gamma (r*k). This is the formal version of absorbing repeated first-order local gamma bounds into one larger Higham gamma term.

    Lean statement
    lemma residualAccumBound_gamma_le_gamma_mul (fp : FPModel) (k : ℕ) :
        ∀ r : ℕ, gammaValid fp (r * k) →
          residualAccumBound (gamma fp k) r ≤ gamma fp (r * k)

    residualAccumBound_gamma_le_gamma_mul

  • Equation (19.11)

    Equation (19.11)/Theorem 19.4 columnwise backward-error form, using the public source-facing theorem name.

    Lean statement
    theorem eq19_11_columnwise_backward_error
        (fp : FPModel) (m n : Nat) (A : Fin m -> Fin n -> Real)
        (hn : 0 < n) (hnm : n <= m)
        (hvalid : gammaValid fp (n * householderConstructApplyGammaIndex m)) :
        HouseholderQRBackwardError m n A
          (fl_householderQRPanel_Q fp m n A)
          (fl_householderQRPanel_R fp m n A)
          (gamma_tilde fp m n)

    eq19_11_columnwise_backward_error

  • Equation (19.12)

    Equation (19.12) componentwise backward-error form, exposed as a source-labeled wrapper around the componentwise Theorem 19.4 surface.

    Lean statement
    theorem eq19_12_componentwise_backward_error
        (fp : FPModel) (m n : Nat) (A : Fin m -> Fin n -> Real)
        (hn : 0 < n) (hnm : n <= m)
        (hvalid : gammaValid fp (n * householderConstructApplyGammaIndex m)) :
        HouseholderQRComponentwiseBackwardError m n A
          (fl_householderQRPanel_Q fp m n A)
          (fl_householderQRPanel_R fp m n A)
          (gamma_tilde fp m n * frobNorm A)
          ((m : Real) * gamma_tilde fp m n)

    eq19_12_componentwise_backward_error

  • Equation (19.25)

    Equation (19.25) source row for the concrete staged Givens QR path. This packages the verified columnwise sequence perturbation bound under the conservative coefficient H19.Theorem19_10.gamma_tilde. The exact printed-constant comparison remains a separate audit from this source-row wrapper.

    Lean statement
    theorem eq19_25_columnwise_perturbation_bound
        (fp : FPModel) (m n : Nat) (A : Fin m -> Fin n -> Real)
        (hn : 0 < n) (hnm : n <= m)
        (hvalid : gammaValid fp 8) :
        Exists fun Q : Fin m -> Fin m -> Real =>
          GivensQRBackwardError m n A Q
            (fl_givensQRStageFold fp m n (givensQRStageCount m n) A)
            (gamma_tilde fp m n)

    eq19_25_columnwise_perturbation_bound · 3 more declarations under this item

  • Equation (19.32)

    Source-stage matrix recurrence A_k = A_{k+1} R_k behind Higham equation (19.32), with the current stage norm required to be nonzero.

    Lean statement
    theorem sourceStage_matrix_recurrence {m n : Nat}
        (A : Fin m -> Fin n -> Real) (k : Fin n)
        (hdiag : Ne (gsColumnNorm2 (stageVectors A k.val k)) 0) :
        sourceStage A k.val =
          matMulRect m n n (sourceStage A (k.val + 1)) (stepR A k)

    sourceStage_matrix_recurrence

  • Equation (19.33)

    Iterated source-stage recurrence behind the product term in Higham equation (19.33).

    Lean statement
    theorem sourceStage_initial_matrix_recurrence {m n : Nat}
        (A : Fin m -> Fin n -> Real) {t : Nat} (ht : t <= n)
        (hdiag : forall k : Fin n, k.val < t ->
          Ne (gsColumnNorm2 (stageVectors A k.val k)) 0) :
        A = matMulRect m n n (sourceStage A t) (stepRProduct A t)

    sourceStage_initial_matrix_recurrence

Chapter 20 · The least-squares problem all chapters

Definitions, theorems and lemmas

  • Lemma 20.6

    The rank-one projector from equation (20.22) is a vector 2-norm contraction.

    Lean statement
    theorem lsLemma20_6Projector_vecNorm2Sq_le {m : ℕ}
        (s : Fin m → ℝ) (hsq : vecNorm2Sq s ≠ 0) (v : Fin m → ℝ) :
        vecNorm2Sq (matMulVec m (lsLemma20_6Projector s) v) ≤ vecNorm2Sq v

    lsLemma20_6Projector_vecNorm2Sq_le · 29 more declarations under this item

  • Theorem 20.2

    Paired source-facing augmented-system form. The hypotheses keep the printed full-rank assumptions for both A and A + DeltaA; the proof uses full column rank of A to construct the inverse block in (20.6) and then combines the already proved relative bounds (20.9) and (20.10).

    Lean statement
    theorem lsAugmentedTheorem20_2_relative_bounds_full_column_rank
        {m n : ℕ}
        (νx : CVec n → ℝ) (hνx : IsComplexVectorNorm νx)
        (habsx : IsAbsoluteComplexVectorNorm νx)
        (νr : CVec m → ℝ) (hνr : IsComplexVectorNorm νr)
        (habsr : IsAbsoluteComplexVectorNorm νr)
        (A : Fin m → Fin n → ℝ)
        (DeltaA E : Fin m → Fin n → ℝ) (Deltab f b : Fin m → ℝ)
        (r s : Fin m → ℝ) (x y : Fin n → ℝ) (eps : ℝ)
        (hA : Function.Injective (rectMatMulVec A))
        (_hApert :
          Function.Injective (rectMatMulVec (fun i j => A i j + DeltaA i j)))
        (hExact : LSAugmentedSystem A b (0 : Fin n → ℝ) r x)
        (hPert :
          LSAugmentedSystem (fun i j => A i j + DeltaA i j)
            (fun i => b i + Deltab i) (0 : Fin n → ℝ) s y)
        (heps : 0 ≤ eps) (hE : ∀ i j, 0 ≤ E i j) (hf : ∀ i, 0 ≤ f i)
        (hxnorm_pos : 0 < νx (realVecToComplex x))
        (hrnorm_pos : 0 < νr (realVecToComplex r))
        (hDeltaA : ∀ i j, |DeltaA i j| ≤ eps * E i j)
        (hDeltab : ∀ i, |Deltab i| ≤ eps * f i) :
        (νx (realVecToComplex (fun j => x j - y j)) / νx (realVecToComplex x) ≤
          (eps *
            (νx (realVecToComplex
                (lsAugmentedEq20_8LeftMajorant (lsAplusOfGramNonsingInv A)
                  (lsComponentwiseDataMajorant E f y))) +
              νx (realVecToComplex
                (lsAugmentedEq20_8RightMajorant (lsGramNonsingInv A)
                  (lsComponentwiseTransposeMajorant E s))))) /
            νx (realVecToComplex x)) ∧
        (νr (realVecToComplex (fun i => r i - s i)) / νr (realVecToComplex r) ≤
          (eps *
            (νr (realVecToComplex
                (lsAugmentedEq20_7LeftMajorant A (lsAplusOfGramNonsingInv A)
                  (lsComponentwiseDataMajorant E f y))) +
              νr (realVecToComplex
                (lsAugmentedEq20_7RightMajorant (lsAplusOfGramNonsingInv A)
                  (lsComponentwiseTransposeMajorant E s))))) /
            νr (realVecToComplex r))

    lsAugmentedTheorem20_2_relative_bounds_full_column_rank · 28 more declarations under this item

Equations and other results

  • Equation (20.3)

    Using Higham's residual sign convention, the augmented system is equivalent to the rectangular normal equations.

    Lean statement
    theorem LSAugmentedNormalSystem.iff_rectLSNormalEquations {m n : ℕ}
        (A : Fin m → Fin n → ℝ) (b : Fin m → ℝ) (x : Fin n → ℝ) :
        LSAugmentedNormalSystem A b (lsResidualHigham A b x) x ↔
          RectLSNormalEquations A b x

    iff_rectLSNormalEquations

  • Equation (20.4)

    Equation (20.4) with s = b + Deltab - (A + DeltaA)y is equivalent to the normal equations for the perturbed least-squares problem.

    Lean statement
    theorem LSPerturbedAugmentedSystem.iff_rectLSNormalEquations {m n : ℕ}
        (A DeltaA : Fin m → Fin n → ℝ) (b Deltab : Fin m → ℝ)
        (y : Fin n → ℝ) :
        LSPerturbedAugmentedSystem A DeltaA b Deltab
            (lsResidualHigham (fun i j => A i j + DeltaA i j)
              (fun i => b i + Deltab i) y) y ↔
          RectLSNormalEquations (fun i j => A i j + DeltaA i j)
            (fun i => b i + Deltab i) y

    iff_rectLSNormalEquations · 2 more declarations under this item

  • Equation (20.15b)

    Transpose action of the transformed QR block [R; 0] on [h; d₂]: [R^T 0] [h; d₂] = R^T h.

    Lean statement
    theorem lsQRTallBlock_transpose_mulVec_append {n k : ℕ}
        (R : Fin n → Fin n → ℝ) (h : Fin n → ℝ) (d2 : Fin k → ℝ) :
        (fun j : Fin n =>
          ∑ i : Fin (n + k), lsQRTallBlock R i j * Fin.append h d2 i) =
          fun j : Fin n => ∑ i : Fin n, R i j * h i

    lsQRTallBlock_transpose_mulVec_append

  • Equation (20.17)

    The scaled augmented coefficient matrix C(alpha) = [[alpha I, A], [A^T, 0]] is symmetric.

    Lean statement
    theorem lsScaledAugmentedMatrix_symmetric {m n : ℕ} (alpha : ℝ)
        (A : Fin m → Fin n → ℝ) :
        IsSymmetricFiniteMatrix (lsScaledAugmentedMatrix alpha A)

    lsScaledAugmentedMatrix_symmetric · 12 more declarations under this item

  • Equation (20.22)

    The two projector blocks in equation (20.22), here P and I-P, add to the identity.

    Lean statement
    theorem lsLemma20_6Projector_add_complement {m : ℕ} (s : Fin m → ℝ)
        (i j : Fin m) :
        lsLemma20_6Projector s i j + lsLemma20_6ProjectorComplement s i j =
          idMatrix m i j

    lsLemma20_6Projector_add_complement

  • Equation (20.24)

    Consistency consequence: the local full-row-rank condition makes the equality constraint B x = d feasible for every right-hand side d.

    Lean statement
    theorem LSEFullRowRank.exists_feasible {p n : ℕ}
        {B : Fin p → Fin n → ℝ} (hB : LSEFullRowRank B)
        (d : Fin p → ℝ) :
        ∃ x : Fin n → ℝ, LSEFeasible B d x

    exists_feasible · 10 more declarations under this item

Chapter 21 · Underdetermined systems all chapters

  • Lemma 21.2

    Frobenius-norm form of the printed perturbation bound for the source-case single perturbation.

    Lean statement
    theorem higham21_lemma21_2_single_perturbation_frob_bound {m n : ℕ}
        (x : Fin n → ℝ)
        (DeltaA1 DeltaA2 : Fin m → Fin n → ℝ) :
        frobNormRect (undetLemma21_2SinglePerturbation x DeltaA1 DeltaA2) ≤
          Real.sqrt (frobNormRect DeltaA1 ^ 2 + frobNormRect DeltaA2 ^ 2)

    higham21_lemma21_2_single_perturbation_frob_bound · 44 more declarations under this item

  • Theorem 21.1

    Source-facing relative asymptotic form. The displayed remainder ratio is explicitly O(t^2), and the accompanying inequality is the exact meaning of the source's first-order coefficient plus quadratic remainder.

    Lean statement
    theorem higham21_theorem21_1_relative_asymptotic_bound_of_gram_det_ne_zero
        {m n : Nat}
        (nu : CVec n -> Real) (hnu : IsComplexVectorNorm nu)
        (habs : IsAbsoluteComplexVectorNorm nu)
        (A DeltaA E : Fin m -> Fin n -> Real)
        (b Deltab f : Fin m -> Real) (rho beta : Real)
        (hdet :
          Not (Matrix.det (rectGram A : Matrix (Fin m) (Fin m) Real) = 0))
        (hdet_t : forall t, |t| <= rho ->
          Not
            (Matrix.det
              (rectGram (higham21Eq21_7ScaledMatrix A DeltaA t) :
                Matrix (Fin m) (Fin m) Real) = 0))
        (hb : Not (b = 0))
        (hE : forall i j, 0 <= E i j) (hf : forall i, 0 <= f i)
        (hDeltaA : forall i j, abs (DeltaA i j) <= E i j)
        (hDeltab : forall i, abs (Deltab i) <= f i)
        (hrho : 0 < rho) (hbeta : 0 <= beta)
        (hG_t_inv : forall t, |t| <= rho ->
          frobNorm
            (undetGramNonsingInv
              (higham21Eq21_7ScaledMatrix A DeltaA t)) <= beta) :
        let x := rectMatMulVec (undetAplusOfGramNonsingInv A) b
        let remainderRatio : Real -> Real := fun t =>
          nu (realVecToComplex
              (higham21Eq21_7ExactRemainder A DeltaA b Deltab
                (undetGramNonsingInv A)
                (undetGramNonsingInv
                  (higham21Eq21_7ScaledMatrix A DeltaA t)) t)) /
            nu (realVecToComplex x)
        And
          (remainderRatio =O[nhds 0] (fun t : Real => t ^ 2))
          (forall t, |t| <= rho ->
            nu (realVecToComplex
                (fun j =>
                  higham21Eq21_7PerturbedSolution A DeltaA b Deltab
                        (undetGramNonsingInv
                          (higham21Eq21_7ScaledMatrix A DeltaA t)) t j -
                    higham21Eq21_7BaseSolution A b
                      (undetGramNonsingInv A) j)) /
                nu (realVecToComplex x) <=
              |t| *
                  ((nu (realVecToComplex
                        (higham21Theorem21_1NullspaceMajorant A E b)) +
                      nu (realVecToComplex
                        (higham21Theorem21_1DataMajorant A E b f))) /
                    nu (realVecToComplex x)) +
                remainderRatio t)

    higham21_theorem21_1_relative_asymptotic_bound_of_gram_det_ne_zero · 23 more declarations under this item

  • Theorem 21.4

    The printed full-row-rank and small-condition hypotheses construct the entire concrete Householder domain, including computed triangular nonbreakdown.

    Lean statement
    theorem Higham21QMethodFullRowRankComputedQRDomain.of_source_smallness
        {m k : Nat} (fp : FPModel)
        (A : Fin m -> Fin (m + k) -> Real)
        (hm : 0 < m)
        (hfull : lsRealRectColRank (finiteTranspose A) = m)
        (hvalid : gammaValid fp (Higham21QMethodRoundedGammaIndex m k))
        (hCondSmall :
          gamma fp (Higham21QMethodRoundedGammaIndex m k) *
              higham21Cond2With A (undetAplusOfGramNonsingInv A) < 1) :
        Higham21QMethodFullRowRankComputedQRDomain m k fp A

    of_source_smallness · 45 more declarations under this item

Chapter 22 · Vandermonde systems all chapters

  • Corollary 22.5

    Higham (22.22): for four nodes (n = 3), the generic factor product specializes to the six displayed factors U₀ U₁ U₂ L₂ L₁ L₀. The entries of these factors are the definitions immediately preceding (22.17), so this theorem is the source-label bridge for the displayed four-by-four example rather than a second factorization assumption.

    Lean statement
    theorem higham22_eq22_22_four_node_six_factor
        (theta beta gamma : ℕ → ℂ) (alpha : Fin 4 → ℂ) :
        higham22Algorithm22_2FactorProduct theta beta gamma alpha =
          ((higham22StageIIUpperFactor theta beta gamma alpha 0 *
              higham22StageIIUpperFactor theta beta gamma alpha 1) *
              higham22StageIIUpperFactor theta beta gamma alpha 2) *
            (higham22StageILowerFactor alpha 2 *
              (higham22StageILowerFactor alpha 1 *
                higham22StageILowerFactor alpha 0))

    higham22_eq22_22_four_node_six_factor · 3 more declarations under this item

Chapter 28 · A gallery of test matrices all chapters

Definitions, theorems and lemmas

  • Theorem 28.1

    Stewart's concrete Gaussian Householder producer has exactly normalized Haar law in every dimension.

    Lean statement
    theorem stewartOrthogonalGroupLaw_eq_normalizedOrthogonalHaar (n : ℕ) :
        stewartOrthogonalGroupLaw n = normalizedOrthogonalHaar n

    stewartOrthogonalGroupLaw_eq_normalizedOrthogonalHaar · 1 more declaration under this item

Equations and other results

  • Equation (28.1)

    The factor-derived inverse has exactly the entries printed in (28.1).

    Lean statement
    theorem factorInverseGram_eq_hilbertInverseFormula (n : ℕ) :
        hilbertCholeskyFactorInverse n *
            (hilbertCholeskyFactorInverse n).transpose =
          hilbertInverseFormula n

    factorInverseGram_eq_hilbertInverseFormula · 2 more declarations under this item

  • Equation (28.3)

    Generic factorization bridge: Hₙ = RᵀR for the printed upper-triangular factor.

    Lean statement
    theorem hilbertMatrix_eq_choleskyGram (n : ℕ) :
        hilbertMatrix n =
          (hilbertCholeskyFactor n).transpose * hilbertCholeskyFactor n

    hilbertMatrix_eq_choleskyGram · 2 more declarations under this item