Theorem 3, p. 9 — the small gain theorem: ‖s¹‖^λ_F ≤ (ω₁γ₂⋯γ_m + ⋯ + ω_m)/(1 − γ₁⋯γ_m)
ProvedDIGing.Push.theorem_3control-theoryp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1small-gain
Let and let () be sequences of matrices. Suppose that for all positive integers and each there is an arrow , that is,
where the gains are nonnegative and . Then for every
that is, is bounded by the right-hand side.
This is the device that turns the four arrows of the Push-DIGing analysis into a bound on the optimality error.
Formalization Note Indices are 0-based: is s ⟨0, hm⟩ and the arrow is i ↦ finRotate m i. The bracket is written . The supremum, which may be infinite, is stated pointwise in . This statement is identical to the one in the companion DIGing mission.
Preamble
import Mathlib import Definitions.Def_DIGing_Undir_Common
Formal statement
namespace DIGing.Push
theorem theorem_3 {n p m : ℕ} (hm : 0 < m) (s : Fin m → ℕ → DIGing.Undir.Stack n p) (lam : ℝ)
(hlam0 : 0 < lam) (hlam1 : lam < 1) (γ ω : Fin m → ℝ) (hγ : ∀ i, 0 ≤ γ i)
(hprod : ∏ i, γ i < 1)
(harrow : ∀ K : ℕ, 0 < K → ∀ i : Fin m,
DIGing.Undir.ergK lam K (fun k => DIGing.Undir.frob (s (finRotate m i) k)) ≤ γ i * DIGing.Undir.ergK lam K (fun k => DIGing.Undir.frob (s i k)) + ω i) :
∀ k : ℕ, DIGing.Undir.frob (s ⟨0, hm⟩ k) / lam ^ k ≤
(1 - ∏ i, γ i)⁻¹ * ∑ j, ω j * ∏ l ∈ Finset.univ.filter (fun l => j < l), γ l := by sorry
end DIGing.Push
Source
arXiv:1607.03218v3, Theorem 3, (7), p. 9
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.