{-# OPTIONS --safe --cubical-compatible --guardedness --exact-split --double-check #-}
module Real.Interval.Exp.Approx where
open import Data.Nat as Nat using (ℕ; zero; suc; z≤n; s≤s)
import Data.Nat.Properties as NatP
open import Data.Product using (_,_; proj₁; proj₂)
open import Data.Rational using (ℚ; 0ℚ; 1ℚ; _≤_; _<_; _+_; _-_; ∣_∣)
renaming (-_ to neg)
open import Data.Rational.Properties using
(≤-refl; ≤-trans; <⇒≤; <-≤-trans; <-trans; <-asym; +-mono-≤; +-mono-≤-<
; +-monoˡ-<; +-identityˡ; +-identityʳ; +-inverseˡ; +-inverseʳ; +-assoc
; +-monoˡ-≤; +-monoʳ-≤; neg-antimono-≤)
open import Relation.Binary.PropositionalEquality using
(_≡_; refl; sym; trans; cong; cong₂; subst; subst₂)
open import Real using (ε; CauchySeq; half)
open import Real.CauchyToInterval using
(cauchy→realI; point; centre-point; centre-cauchy→realI; M; K; K≥k; μ≤M)
open import Real.IntervalEquiv using (centre; l; u)
open import Real.Interval using (δ; δ-pos; δ-half)
open import Real.Interval.Arith using (0ℝ)
open import Real.Interval.Complete using (_⟶_)
open import Real.Interval.ContinuityRecipBasic using
(l-cauchy→realI; u-cauchy→realI)
open import Real.Interval.Embed using (δ0≡half)
open import Real.Interval.Exp.Core as ExpCore using
(term; term-nonNeg; expPartial; expPartial-cauchy; expSeq; expq
; expPartial-nonNeg; expPartial-suc; _≤ℕ_)
open import Real.Interval.Kit using (abs-swap; half+half≡1)
open import Real.Interval.LimitLaws using (ε-mono; abs<⇒lower)
open import Real.Interval.Node using (l-dyadic; u-dyadic)
open import Real.Interval.Order using (_<ℝ_)
open import Real.Interval.OrderComplete.Base using (_≤ℝ_)
expq-approx : (q : ℚ) (0≤q : 0ℚ ≤ q)
→ (λ n → point (expPartial q n)) ⟶ expq q 0≤q
expq-approx q 0≤q k =
let μK : ℕ
μK = proj₁ (expPartial-cauchy q 0≤q (K k))
bound = proj₂ (expPartial-cauchy q 0≤q (K k))
Mk : ℕ
Mk = M (expSeq q 0≤q) k
μK≤Mk : μK ≤ℕ Mk
μK≤Mk = μ≤M (expSeq q 0≤q) k
in μK , (λ n n≥ →
let h : ∣ expPartial q n - expPartial q Mk ∣ < ε (K k)
h = bound n Mk n≥ μK≤Mk
eL : centre (point (expPartial q n)) k ≡ expPartial q n
eL = centre-point (expPartial q n) k
eR : centre (expq q 0≤q) k ≡ expPartial q Mk
eR = centre-cauchy→realI (expSeq q 0≤q) k
absEq : ∣ centre (point (expPartial q n)) k - centre (expq q 0≤q) k ∣
≡ ∣ expPartial q n - expPartial q Mk ∣
absEq = cong ∣_∣ (cong₂ (λ p r → p - r) eL eR)
in subst (λ z → z < ε k) (sym absEq)
(<-≤-trans h (ε-mono (K≥k k))))
expq-nonNeg : (q : ℚ) (0≤q : 0ℚ ≤ q) → 0ℝ ≤ℝ expq q 0≤q
expq-nonNeg q 0≤q (n , w) =
let a : ℚ
a = expPartial q (M (expSeq q 0≤q) n)
uEq : u (expq q 0≤q) n ≡ a + δ n
uEq = u-cauchy→realI (expSeq q 0≤q) n
lEq : l 0ℝ n ≡ neg (δ n) + 0ℚ
lEq = l-dyadic 0ℚ n
w1 : a + δ n < l 0ℝ n
w1 = subst (λ z → z < l 0ℝ n) uEq w
w2 : a + δ n < neg (δ n) + 0ℚ
w2 = subst (λ z → a + δ n < z) lEq w1
step : 0ℚ + 0ℚ < a + δ n
step = +-mono-≤-< (expPartial-nonNeg q 0≤q (M (expSeq q 0≤q) n)) (δ-pos n)
pos-ad : 0ℚ < a + δ n
pos-ad = subst (λ z → z < a + δ n) (+-identityˡ 0ℚ) step
pos-negδ : 0ℚ < neg (δ n)
pos-negδ =
subst (λ z → 0ℚ < z) (+-identityʳ (neg (δ n)))
(<-trans pos-ad w2)
shifted : 0ℚ + δ n < neg (δ n) + δ n
shifted = +-monoˡ-< (δ n) pos-negδ
delta-lt-0 : δ n < 0ℚ
delta-lt-0 =
subst (λ z → z < 0ℚ) (+-identityˡ (δ n))
(subst (λ z → 0ℚ + δ n < z) (+-inverseˡ (δ n)) shifted)
in <-asym (δ-pos n) delta-lt-0
expPartial-suc-ge : (q : ℚ) (0≤q : 0ℚ ≤ q) (m : ℕ)
→ 1ℚ ≤ expPartial q (suc m)
expPartial-suc-ge q 0≤q zero =
subst (λ z → 1ℚ ≤ z) (+-identityˡ 1ℚ) (≤-refl {1ℚ})
expPartial-suc-ge q 0≤q (suc m) =
let step = +-mono-≤ (expPartial-suc-ge q 0≤q m) (term-nonNeg q 0≤q (suc m))
step' = subst (λ z → z ≤ expPartial q (suc m) + term q (suc m))
(+-identityʳ 1ℚ) step
in subst (λ z → 1ℚ ≤ z) (sym (expPartial-suc q (suc m))) step'
expPartial-ge-one : (q : ℚ) (0≤q : 0ℚ ≤ q) (m : ℕ) → 1 ≤ℕ m
→ 1ℚ ≤ expPartial q m
expPartial-ge-one q 0≤q zero ()
expPartial-ge-one q 0≤q (suc m) _ = expPartial-suc-ge q 0≤q m
delta1<half : δ 1 < half
delta1<half =
let step : 0ℚ + δ 1 < δ 1 + δ 1
step = +-monoˡ-< (δ 1) (δ-pos 1)
step' : δ 1 < δ 1 + δ 1
step' = subst (λ z → z < δ 1 + δ 1) (+-identityˡ (δ 1)) step
twoDelta : δ 1 + δ 1 ≡ half
twoDelta = trans (δ-half 0) δ0≡half
in subst (λ z → δ 1 < z) twoDelta step'
eps2≤half : ε 2 ≤ half
eps2≤half = ε-mono {1} {2} (s≤s z≤n)
oneMinusHalf : 1ℚ + neg half ≡ half
oneMinusHalf =
trans (cong (_+ neg half) (sym half+half≡1))
(trans (+-assoc half half (neg half))
(trans (cong (half +_) (+-inverseʳ half)) (+-identityʳ half)))
half≤one-minus-ε2 : half ≤ 1ℚ - ε 2
half≤one-minus-ε2 =
let add1 : 1ℚ + neg half ≤ 1ℚ + neg (ε 2)
add1 = +-monoʳ-≤ 1ℚ (neg-antimono-≤ eps2≤half)
in subst (λ z → z ≤ 1ℚ + neg (ε 2)) (sym oneMinusHalf) add1
expq-pos : (q : ℚ) (0≤q : 0ℚ ≤ q) → 0ℝ <ℝ expq q 0≤q
expq-pos q 0≤q =
let cs = expSeq q 0≤q
x = cauchy→realI cs
N = proj₁ (expq-approx q 0≤q 2)
h = proj₂ (expq-approx q 0≤q 2)
a : ℚ
a = expPartial q (suc N)
h0 : ∣ centre (point a) 2 - centre x 2 ∣ < ε 2
h0 = h (suc N) (NatP.n≤1+n N)
h1 : ∣ a - centre x 2 ∣ < ε 2
h1 = subst₂ (λ p q → ∣ p - q ∣ < ε 2) (centre-point a 2) refl h0
h1' : ∣ centre x 2 - a ∣ < ε 2
h1' = subst (λ z → z < ε 2) (abs-swap a (centre x 2)) h1
low : a - ε 2 < centre x 2
low = abs<⇒lower h1'
one≤a : 1ℚ ≤ a
one≤a = expPartial-ge-one q 0≤q (suc N) (s≤s z≤n)
ε2≤a : 1ℚ - ε 2 ≤ a - ε 2
ε2≤a = +-monoˡ-≤ (neg (ε 2)) one≤a
twoDelta : δ 2 + δ 2 ≡ δ 1
twoDelta = δ-half 1
deltaLtHalf : δ 2 + δ 2 < half
deltaLtHalf = subst (λ z → z < half) twoDelta delta1<half
c = CauchySeq.f cs (M cs 2)
ceq : centre x 2 ≡ c
ceq = centre-cauchy→realI cs 2
deltaLtCentre : δ 2 + δ 2 < centre x 2
deltaLtCentre = <-≤-trans deltaLtHalf
(≤-trans half≤one-minus-ε2 (≤-trans ε2≤a (<⇒≤ low)))
deltaLt : δ 2 + δ 2 < c
deltaLt = subst (λ z → δ 2 + δ 2 < z) ceq deltaLtCentre
shifted : (δ 2 + δ 2) + neg (δ 2) < c + neg (δ 2)
shifted = +-monoˡ-< (neg (δ 2)) deltaLt
cancel : (δ 2 + δ 2) + neg (δ 2) ≡ δ 2 + 0ℚ
cancel = trans (+-assoc (δ 2) (δ 2) (neg (δ 2)))
(cong (δ 2 +_) (+-inverseʳ (δ 2)))
w : δ 2 + 0ℚ < c + neg (δ 2)
w = subst (λ z → z < c + neg (δ 2)) cancel shifted
uEq : u 0ℝ 2 ≡ δ 2 + 0ℚ
uEq = u-dyadic 0ℚ 2
lEq : l x 2 ≡ c + neg (δ 2)
lEq = l-cauchy→realI cs 2
in 2 , subst (λ y → u 0ℝ 2 < y) lEq
(subst (λ x' → x' < l x 2) uEq w)