| 1 |
(* |
| 2 |
Copyright © 2006-2008 Russell O’Connor |
| 3 |
|
| 4 |
Permission is hereby granted, free of charge, to any person obtaining a copy of |
| 5 |
this proof and associated documentation files (the "Proof"), to deal in |
| 6 |
the Proof without restriction, including without limitation the rights to |
| 7 |
use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of |
| 8 |
the Proof, and to permit persons to whom the Proof is furnished to do so, |
| 9 |
subject to the following conditions: |
| 10 |
|
| 11 |
The above copyright notice and this permission notice shall be included in all |
| 12 |
copies or substantial portions of the Proof. |
| 13 |
|
| 14 |
THE PROOF IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
| 15 |
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS |
| 16 |
FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR |
| 17 |
COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER |
| 18 |
IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN |
| 19 |
CONNECTION WITH THE PROOF OR THE USE OR OTHER DEALINGS IN THE PROOF. |
| 20 |
*) |
| 21 |
|
| 22 |
Require Import CoRN.algebra.RSetoid. |
| 23 |
Require Import CoRN.metric2.Metric. |
| 24 |
Require Import CoRN.metric2.UniformContinuity. |
| 25 |
Require Export CoRN.model.metric2.IntegrableFunction. |
| 26 |
Require Export CoRN.model.metric2.BoundedFunction. |
| 27 |
Require Export CoRN.model.metric2.CRmetric. |
| 28 |
Require Export CoRN.reals.fast.CRArith. |
| 29 |
Require Import CoRN.reals.fast.CRIR. |
| 30 |
Require Import CoRN.ftc.Integral. |
| 31 |
Require Import CoRN.model.structures.StepQsec. |
| 32 |
Require Import CoRN.model.structures.OpenUnit. |
| 33 |
Require Import CoRN.model.totalorder.QMinMax. |
| 34 |
Require Import CoRN.model.totalorder.QposMinMax. |
| 35 |
From Coq Require Import Qabs. |
| 36 |
Require Import CoRN.tactics.Qauto. |
| 37 |
From Coq Require Import Qround. |
| 38 |
Require Import CoRN.model.metric2.L1metric. |
| 39 |
Require Import CoRN.model.metric2.LinfMetric. |
| 40 |
Require Import CoRN.model.ordfields.Qordfield. |
| 41 |
Require Import CoRN.algebra.COrdFields2. |
| 42 |
Require Import CoRN.model.metric2.Qmetric. |
| 43 |
Require Import CoRN.reals.fast.ContinuousCorrect. |
| 44 |
Require Import CoRN.ftc.IntegrationRules. |
| 45 |
Require Import CoRN.ftc.MoreIntegrals. |
| 46 |
Require Import CoRN.tactics.CornTac. |
| 47 |
Require Import CoRN.model.metric2.LinfDistMonad. |
| 48 |
|
| 49 |
Set Implicit Arguments. |
| 50 |
|
| 51 |
Opaque Qmax Qabs inj_Q. |
| 52 |
|
| 53 |
Local Open Scope Q_scope. |
| 54 |
|
| 55 |
(** |
| 56 |
* Effective Integration |
| 57 |
** stepSample |
| 58 |
The first step in defining integration is to define the unit function on |
| 59 |
[[0,1]] as a [Bounded Function]. This is defined to be the limit of |
| 60 |
step functions approximating the unit function. |
| 61 |
|
| 62 |
For efficenty reasons we want this approximation to be as good as we can muster because the number of steps this approximation returns will be |
| 63 |
the number of samples that we will take of the function we want to |
| 64 |
integrate. Furthermore, we want the tree structure defining the step |
| 65 |
function to be as balanced as possible. |
| 66 |
|
| 67 |
First we create a step function with n steps that appoximates the |
| 68 |
identity function, [stepSample]. *) |
| 69 |
|
| 70 |
Lemma oddGluePoint (p:positive) : 0 < Pos.succ p # xI p /\ Pos.succ p # xI p < 1. |
| 71 |
Proof. |
| 72 |
split; unfold Qlt. |
| 73 |
constructor. |
| 74 |
simpl. |
| 75 |
rewrite Pmult_comm. |
| 76 |
simpl. |
| 77 |
apply Zlt_left_rev. |
| 78 |
rewrite Zpos_succ_morphism, Zpos_xI. |
| 79 |
unfold Z.succ. |
| 80 |
ring_simplify. |
| 81 |
auto with *. |
| 82 |
Qed. |
| 83 |
|
| 84 |
Local Open Scope setoid_scope. |
| 85 |
Local Open Scope sfstscope. |
| 86 |
Local Open Scope StepQ_scope. |
| 87 |
|
| 88 |
Definition stepSample : positive -> StepQ := positive_rect2 |
| 89 |
(fun _ => StepQ) |
| 90 |
(fun p rec1 rec2 => glue (Build_OpenUnit (oddGluePoint p)) (constStepF (Pos.succ p#xI p:QS) * rec1) ((constStepF (1#(xI p):QS))*(constStepF (Pos.succ p:QS) + constStepF (p:QS)*rec2))) |
| 91 |
(fun p rec => glue (ou (1#2)) (constStepF (1#2:QS) * rec) (constStepF (1#2:QS) * (constStepF (1:QS) + rec))) |
| 92 |
(constStepF (1#2:QS)). |
| 93 |
|
| 94 |
(** We want to prove that [stepSample n] is within (1/(2*n)) of the |
| 95 |
identity function, but the identity function doesn't exist yet. |
| 96 |
Instead we define the [SupDistanceToLinear] which computes what would |
| 97 |
the distance to a linear function on [[0,1]]. This distance function |
| 98 |
is transitive in the sense that if a step function x is within e1 of |
| 99 |
a linear function, and a step function y is within e2 of the same |
| 100 |
linear function, then x and y are really within (e1+e2) of each other |
| 101 |
(in Linf).*) |
| 102 |
Section id01. |
| 103 |
|
| 104 |
Lemma SupDistanceToLinearBase_pos : forall (l r:Q) (H:l<r) (x:Q), 0 < Qmax (x-l) (r-x). |
| 105 |
Proof. |
| 106 |
intros l r H x. |
| 107 |
destruct (Qlt_le_dec_fast l x) as [H0|H0]. |
| 108 |
rewrite -> Qlt_minus_iff in H0. |
| 109 |
unfold Qminus. |
| 110 |
eapply Qlt_le_trans; [|apply Qmax_ub_l]. |
| 111 |
assumption. |
| 112 |
rewrite -> Qlt_minus_iff in H. |
| 113 |
eapply Qlt_le_trans; [|apply Qmax_ub_r]. |
| 114 |
eapply Qlt_le_trans. |
| 115 |
apply H. |
| 116 |
unfold Qminus. |
| 117 |
apply: plus_resp_leEq_lft;simpl;auto with *. |
| 118 |
Qed. |
| 119 |
|
| 120 |
Definition SupDistanceToLinear := StepFfold |
| 121 |
(fun (x:QS) (l r:Q) (H:l < r) => exist (Qlt 0) _ (SupDistanceToLinearBase_pos H x)) |
| 122 |
(fun b f g l r H => |
| 123 |
(Qpos_max (f _ _ (affineCombo_gt (OpenUnitDual b) H)) (g _ _ (affineCombo_lt (OpenUnitDual b) H)))). |
| 124 |
|
| 125 |
(** Various properties of [SupDistanceToLinear] *) |
| 126 |
Lemma SupDistanceToLinear_glue : forall o l r a b (H:a < b), |
| 127 |
(proj1_sig (SupDistanceToLinear (glue o l r) H) == |
| 128 |
Qmax (proj1_sig (SupDistanceToLinear l (affineCombo_gt (OpenUnitDual o) H))) |
| 129 |
(proj1_sig (SupDistanceToLinear r (affineCombo_lt (OpenUnitDual o) H))))%Q. |
| 130 |
Proof. |
| 131 |
intros o l r a b H. |
| 132 |
unfold SupDistanceToLinear at 1. |
| 133 |
simpl. |
| 134 |
autorewrite with QposElim. |
| 135 |
reflexivity. |
| 136 |
Qed. |
| 137 |
|
| 138 |
Lemma SupDistanceToLinear_wd1 : forall x l1 r1 (H1:l1 < r1) l2 r2 (H2:l2 < r2), |
| 139 |
(l1 == l2 -> r1 == r2 -> |
| 140 |
QposEq (SupDistanceToLinear x H1) (SupDistanceToLinear x H2))%Q. |
| 141 |
Proof. |
| 142 |
induction x; intros l1 r1 H1 l2 r2 H2 Hl Hr. |
| 143 |
- unfold SupDistanceToLinear. |
| 144 |
unfold QposEq. simpl. |
| 145 |
rewrite -> Hl. |
| 146 |
rewrite -> Hr. |
| 147 |
reflexivity. |
| 148 |
- unfold QposEq. do 2 rewrite -> SupDistanceToLinear_glue. |
| 149 |
assert (X:(affineCombo (OpenUnitDual o) l1 r1==affineCombo (OpenUnitDual o) l2 r2)%Q). |
| 150 |
rewrite -> Hl. |
| 151 |
rewrite -> Hr. |
| 152 |
reflexivity. |
| 153 |
apply Qmax_compat. |
| 154 |
apply IHx1; auto. |
| 155 |
apply IHx2; auto. |
| 156 |
Qed. |
| 157 |
|
| 158 |
Lemma Qmax_affineCombo : forall x a b o, a < b -> (Qmax (Qmax (x - a) (affineCombo o a b - x)) |
| 159 |
(Qmax (x - affineCombo o a b) (b - x)) == Qmax (x - a) (b - x))%Q. |
| 160 |
Proof. |
| 161 |
intros x a b o H. |
| 162 |
rewrite <- Qmax_assoc. |
| 163 |
rewrite -> (Qmax_assoc (affineCombo o a b - x)). |
| 164 |
rewrite -> (Qmax_comm (affineCombo o a b - x)). |
| 165 |
rewrite <- (Qmax_assoc (x - affineCombo o a b)). |
| 166 |
rewrite -> Qmax_assoc. |
| 167 |
apply Qmax_compat. |
| 168 |
rewrite <- Qle_max_l. |
| 169 |
apply: plus_resp_leEq_lft;simpl; auto with *. |
| 170 |
rewrite <- Qle_max_r. |
| 171 |
apply: plus_resp_leEq;simpl;auto with *. |
| 172 |
Qed. |
| 173 |
|
| 174 |
Lemma SupDistanceToLinear_split : |
| 175 |
forall x o a b c (H0:a < c) (H1:c < b), |
| 176 |
(c == affineCombo (OpenUnitDual o) a b)%Q -> |
| 177 |
(Qmax (proj1_sig (SupDistanceToLinear (SplitL x o) H0)) |
| 178 |
(proj1_sig (SupDistanceToLinear (SplitR x o) H1)) == |
| 179 |
proj1_sig (SupDistanceToLinear x (Qlt_trans _ _ _ H0 H1)))%Q. |
| 180 |
Proof. |
| 181 |
induction x. |
| 182 |
intros o a b c H0 H1 Hc. |
| 183 |
unfold SupDistanceToLinear. |
| 184 |
simpl. |
| 185 |
autorewrite with QposElim. |
| 186 |
rewrite -> Hc. |
| 187 |
apply Qmax_affineCombo; auto with *. |
| 188 |
apply Qlt_trans with c; assumption. |
| 189 |
intros p a b c H0 H1 Hc. |
| 190 |
apply SplitLR_glue_ind; intros H. |
| 191 |
do 2 rewrite -> SupDistanceToLinear_glue. |
| 192 |
rewrite -> Qmax_assoc. |
| 193 |
rewrite -> IHx1. |
| 194 |
apply Qmax_compat; apply SupDistanceToLinear_wd1; try reflexivity; rewrite -> Hc; unfold affineCombo; |
| 195 |
simpl; field; auto with *. |
| 196 |
rewrite -> Hc. |
| 197 |
unfold affineCombo. |
| 198 |
simpl. |
| 199 |
field; auto with *. |
| 200 |
do 2 rewrite -> SupDistanceToLinear_glue. |
| 201 |
rewrite <- Qmax_assoc. |
| 202 |
rewrite -> IHx2. |
| 203 |
apply Qmax_compat; apply SupDistanceToLinear_wd1; try reflexivity; rewrite -> Hc; unfold affineCombo; |
| 204 |
simpl; field; auto with *. |
| 205 |
rewrite -> Hc. |
| 206 |
unfold affineCombo. |
| 207 |
simpl. |
| 208 |
field; auto with *. |
| 209 |
rewrite -> SupDistanceToLinear_glue. |
| 210 |
apply Qmax_compat; apply SupDistanceToLinear_wd1; try reflexivity; rewrite -> Hc; unfold affineCombo; |
| 211 |
simpl; rewrite -> H; field; auto with *. |
| 212 |
Qed. |
| 213 |
|
| 214 |
Lemma SupDistanceToLinear_wd2 : forall x1 x2 a b (H: a < b), x1 == x2 -> |
| 215 |
QposEq (SupDistanceToLinear x1 H) (SupDistanceToLinear x2 H). |
| 216 |
Proof. |
| 217 |
induction x1. |
| 218 |
induction x2. |
| 219 |
intros a b H Hx. |
| 220 |
unfold SupDistanceToLinear. |
| 221 |
simpl in *. |
| 222 |
autorewrite with QposElim. |
| 223 |
change (x == x0)%Q in Hx. |
| 224 |
unfold QposEq. simpl. rewrite -> Hx. |
| 225 |
reflexivity. |
| 226 |
intros a b H Hx. |
| 227 |
destruct Hx as [H0 H1] using (eq_glue_ind x2_1). |
| 228 |
unfold QposEq. simpl. rewrite -> SupDistanceToLinear_glue. |
| 229 |
unfold QposEq in IHx2_1. |
| 230 |
rewrite <- IHx2_1; auto with *. |
| 231 |
unfold QposEq in IHx2_2. |
| 232 |
rewrite <- IHx2_2; auto with *. |
| 233 |
unfold SupDistanceToLinear. |
| 234 |
simpl. |
| 235 |
autorewrite with QposElim. |
| 236 |
rewrite <- Qmax_assoc. |
| 237 |
rewrite -> (Qmax_assoc (affineCombo (OpenUnitDual o) a b - x)). |
| 238 |
rewrite -> (Qmax_comm (affineCombo (OpenUnitDual o) a b - x)). |
| 239 |
rewrite <- (Qmax_assoc (x - affineCombo (OpenUnitDual o) a b)). |
| 240 |
rewrite -> Qmax_assoc. |
| 241 |
symmetry. |
| 242 |
apply Qmax_compat. |
| 243 |
rewrite <- Qle_max_l. |
| 244 |
apply: plus_resp_leEq_lft;simpl;auto with *. |
| 245 |
rewrite <- Qle_max_r. |
| 246 |
apply: plus_resp_leEq;simpl; auto with *. |
| 247 |
intros x2 a b H Hx. |
| 248 |
destruct Hx as [H0 H1] using (glue_eq_ind x1_1). |
| 249 |
unfold QposEq. rewrite -> SupDistanceToLinear_glue. |
| 250 |
unfold QposEq in IHx1_1. |
| 251 |
rewrite -> (IHx1_1 _ _ _ (affineCombo_gt (OpenUnitDual o) H) H0). |
| 252 |
unfold QposEq in IHx1_2. |
| 253 |
rewrite -> (IHx1_2 _ _ _ (affineCombo_lt (OpenUnitDual o) H) H1). |
| 254 |
rewrite -> SupDistanceToLinear_split; [|reflexivity]. |
| 255 |
apply SupDistanceToLinear_wd1; try reflexivity. |
| 256 |
Qed. |
| 257 |
|
| 258 |
Lemma SupDistanceToLinear_translate : |
| 259 |
forall x c a b (H:a < b) (H0:a+c < b + c), |
| 260 |
(proj1_sig (SupDistanceToLinear x H) |
| 261 |
== proj1_sig (SupDistanceToLinear (constStepF (c:QS) + x) H0))%Q. |
| 262 |
Proof. |
| 263 |
induction x. |
| 264 |
intros; unfold SupDistanceToLinear; simpl. |
| 265 |
autorewrite with QposElim. |
| 266 |
apply Qmax_compat; ring. |
| 267 |
intros c a b H H0. |
| 268 |
change (constStepF (X:=QS) c + glue o x1 x2) |
| 269 |
with (glue o (constStepF (c:QS) + x1) (constStepF (c:QS) + x2)). |
| 270 |
do 2 rewrite -> SupDistanceToLinear_glue. |
| 271 |
set (A:=(affineCombo_gt (OpenUnitDual o) H)). |
| 272 |
apply Qmax_compat. |
| 273 |
eapply Seq_trans. |
| 274 |
apply Q_Setoid. |
| 275 |
apply (IHx1 c _ _ A (proj2 (Qplus_lt_l _ _ c) A)). |
| 276 |
apply SupDistanceToLinear_wd1; try reflexivity. |
| 277 |
unfold affineCombo; ring. |
| 278 |
set (B:=(affineCombo_lt (OpenUnitDual o) H)). |
| 279 |
eapply Seq_trans. |
| 280 |
apply Q_Setoid. |
| 281 |
apply (IHx2 c _ _ B (proj2 (Qplus_lt_l _ _ c) B)). |
| 282 |
apply SupDistanceToLinear_wd1; try reflexivity. |
| 283 |
unfold affineCombo; ring. |
| 284 |
Qed. |
| 285 |
|
| 286 |
Lemma SupDistanceToLinear_scale : |
| 287 |
forall x c a b (H:a < b) (H0:c*a < c*b), |
| 288 |
(c*proj1_sig (SupDistanceToLinear x H) |
| 289 |
== proj1_sig (SupDistanceToLinear (constStepF (c:QS) * x) H0))%Q. |
| 290 |
Proof. |
| 291 |
intros x c a b H H0. |
| 292 |
assert (X:0 < c). |
| 293 |
rewrite -> Qlt_minus_iff in *|-. |
| 294 |
apply: (mult_cancel_less _ 0 c (b + - a))%Q; simpl; auto with *. |
| 295 |
replace LHS with 0 by simpl; ring. |
| 296 |
replace RHS with (c* b + - (c*a))%Q by simpl; ring. |
| 297 |
assumption. |
| 298 |
revert c a b H H0 X. |
| 299 |
induction x. |
| 300 |
intros; unfold SupDistanceToLinear; simpl. |
| 301 |
autorewrite with QposElim. |
| 302 |
rewrite -> Qmax_mult_pos_distr_r; auto with *. |
| 303 |
apply Qmax_compat; ring. |
| 304 |
intros c a b H H0 X. |
| 305 |
change (constStepF (X:=QS) c * glue o x1 x2) |
| 306 |
with (glue o (constStepF (c:QS) * x1) (constStepF (c:QS) * x2)). |
| 307 |
do 2 rewrite -> SupDistanceToLinear_glue. |
| 308 |
eapply Seq_trans. |
| 309 |
apply Q_Setoid. |
| 310 |
apply Qmax_mult_pos_distr_r; auto with *. |
| 311 |
set (A:=(affineCombo_gt (OpenUnitDual o) H)). |
| 312 |
apply Qmax_compat. |
| 313 |
eapply Seq_trans. |
| 314 |
apply Q_Setoid. |
| 315 |
apply (IHx1 c _ _ A (mult_resp_less_lft _ _ _ _ A X)); auto with *. |
| 316 |
apply SupDistanceToLinear_wd1; try reflexivity. |
| 317 |
unfold affineCombo; ring. |
| 318 |
set (B:=(affineCombo_lt (OpenUnitDual o) H)). |
| 319 |
eapply Seq_trans. |
| 320 |
apply Q_Setoid. |
| 321 |
apply (IHx2 c _ _ B (mult_resp_less_lft _ _ _ _ B X)); auto with *. |
| 322 |
apply SupDistanceToLinear_wd1; try reflexivity. |
| 323 |
unfold affineCombo; ring. |
| 324 |
Qed. |
| 325 |
|
| 326 |
(** This is the "transitivity" of the [SupDistanceToLinear] function. *) |
| 327 |
Lemma SupDistanceToLinear_trans : |
| 328 |
forall x y a b (H:a < b), StepFSupBall (proj1_sig (SupDistanceToLinear x H + SupDistanceToLinear y H)%Qpos) x y. |
| 329 |
Proof. |
| 330 |
apply: StepF_ind2. |
| 331 |
intros s s0 t t0 Hs Ht H a b Hab. |
| 332 |
apply StepF_eq_change_base_setoid in Hs. |
| 333 |
apply StepF_eq_change_base_setoid in Ht. |
| 334 |
rewrite <- Hs, <- Ht at 2. |
| 335 |
setoid_replace (proj1_sig (SupDistanceToLinear s0 Hab + SupDistanceToLinear t0 Hab)%Qpos) |
| 336 |
with (proj1_sig (SupDistanceToLinear s Hab + SupDistanceToLinear t Hab)%Qpos). |
| 337 |
apply H. |
| 338 |
unfold QposEq. |
| 339 |
apply Qplus_wd; apply SupDistanceToLinear_wd2. |
| 340 |
apply StepF_eq_change_base_setoid in Hs. |
| 341 |
symmetry. exact Hs. |
| 342 |
apply StepF_eq_change_base_setoid in Ht. |
| 343 |
symmetry. exact Ht. |
| 344 |
intros x x0 a b H. |
| 345 |
unfold StepFSupBall, StepFfoldProp. |
| 346 |
simpl. |
| 347 |
rewrite -> Qball_Qabs. |
| 348 |
unfold SupDistanceToLinear. |
| 349 |
simpl. |
| 350 |
apply Qabs_case; intros H0. |
| 351 |
setoid_replace (x - x0)%Q with ((x - a) + (a - b) + (b - x0))%Q; [| now simpl; ring]. |
| 352 |
apply: plus_resp_leEq_both; simpl; auto with *. |
| 353 |
replace RHS with (Qmax (x-a) (b-x) + 0)%Q by simpl; ring. |
| 354 |
apply: plus_resp_leEq_both; simpl; auto with *. |
| 355 |
apply Qlt_le_weak. |
| 356 |
rewrite -> Qlt_minus_iff in *. |
| 357 |
replace RHS with (b + -a)%Q by simpl; ring. |
| 358 |
assumption. |
| 359 |
setoid_replace (-(x - x0))%Q with ((b - x) + - (b - a) + (x0 - a))%Q; [| now simpl; ring]. |
| 360 |
apply: plus_resp_leEq_both; simpl; auto with *. |
| 361 |
replace RHS with (Qmax (x-a) (b-x) + 0)%Q by simpl; ring. |
| 362 |
apply: plus_resp_leEq_both; simpl; auto with *. |
| 363 |
apply Qlt_le_weak. |
| 364 |
rewrite -> Qlt_minus_iff in *. |
| 365 |
replace RHS with (b + -a)%Q by simpl; ring. |
| 366 |
assumption. |
| 367 |
intros o s s0 t t0 H0 H1 a b H. |
| 368 |
assert (X:forall (o : OpenUnit) (l r : StepQ) (a b : Q) (H : a < b), |
| 369 |
QposEq (SupDistanceToLinear (glue o l r) H) |
| 370 |
(Qpos_max (SupDistanceToLinear l (affineCombo_gt (OpenUnitDual o) H)) |
| 371 |
(SupDistanceToLinear r (affineCombo_lt (OpenUnitDual o) H)))%Q). |
| 372 |
{ intros. |
| 373 |
unfold QposEq. |
| 374 |
autorewrite with QposElim. |
| 375 |
apply SupDistanceToLinear_glue. } |
| 376 |
assert (QposEq (SupDistanceToLinear (glue o s s0) H |
| 377 |
+ SupDistanceToLinear (glue o t t0) H) |
| 378 |
(Qpos_max (SupDistanceToLinear s (affineCombo_gt (OpenUnitDual o) H)) |
| 379 |
(SupDistanceToLinear s0 (affineCombo_lt (OpenUnitDual o) H)) |
| 380 |
+ Qpos_max (SupDistanceToLinear t (affineCombo_gt (OpenUnitDual o) H)) |
| 381 |
(SupDistanceToLinear t0 (affineCombo_lt (OpenUnitDual o) H)))) |
| 382 |
as balleq. |
| 383 |
{ unfold QposEq. unfold QposEq in X. simpl. |
| 384 |
do 2 rewrite X. reflexivity. } |
| 385 |
apply (@StepFSupBall_wd |
| 386 |
_ _ _ balleq _ _ (reflexivity _) _ _ (reflexivity _)). clear balleq. |
| 387 |
rewrite -> (StepFSupBallGlueGlue _ _ o s s0 t t0). |
| 388 |
split. |
| 389 |
- eapply ball_weak_le;[|simpl; apply H0]. |
| 390 |
simpl. do 2 rewrite Q_Qpos_max. |
| 391 |
apply Qplus_le_compat; apply Qmax_ub_l. |
| 392 |
- eapply ball_weak_le;[|simpl; apply H1]. |
| 393 |
simpl. do 2 rewrite Q_Qpos_max. |
| 394 |
apply Qplus_le_compat; apply Qmax_ub_r. |
| 395 |
Qed. |
| 396 |
|
| 397 |
(** The [stepSample p] is as close to the virtual identity function as |
| 398 |
we expect. *) |
| 399 |
Lemma stepSampleDistanceToId : (forall p, QposEq (@SupDistanceToLinear (stepSample p) 0 1 (@pos_one _)) (1#(2*p))). |
| 400 |
Proof. |
| 401 |
unfold QposEq. |
| 402 |
induction p using positive_rect2. |
| 403 |
replace (stepSample (xI p)) |
| 404 |
with (glue (Build_OpenUnit (oddGluePoint p)) (constStepF (Pos.succ p#xI p:QS) * (stepSample (Pos.succ p))) ((constStepF (1#(xI p):QS))*(constStepF (Pos.succ p:QS) + constStepF (p:QS)*(stepSample p)))) |
| 405 |
by (symmetry;apply: positive_rect2_red1). |
| 406 |
rewrite -> SupDistanceToLinear_glue. |
| 407 |
generalize (@affineCombo_gt (OpenUnitDual (Build_OpenUnit (oddGluePoint p))) 0 1 (pos_one Q_as_COrdField)) |
| 408 |
(@affineCombo_lt (OpenUnitDual (Build_OpenUnit (oddGluePoint p))) 0 1 (pos_one Q_as_COrdField)). |
| 409 |
intros A B. |
| 410 |
set (C:=(pos_one Q_as_COrdField)) in *. |
| 411 |
transitivity (Qmax (1#2*xI p) (1#2*xI p))%Q;[|apply Qmax_idem]. |
| 412 |
apply Qmax_compat. |
| 413 |
set (LHS := (SupDistanceToLinear (constStepF (X:=QS) (Pos.succ p # xI p) * stepSample (Pos.succ p)) A)). |
| 414 |
transitivity ((Pos.succ p#xI p)*proj1_sig (SupDistanceToLinear (stepSample (Pos.succ p)) C))%Q; [|rewrite -> IHp; |
| 415 |
change ((Pos.succ p * 1 * (2 * (2* p + 1)) = 2* (Pos.succ p + p * (2* (Pos.succ p))))%Z); |
| 416 |
repeat rewrite Zpos_succ_morphism; ring]. |
| 417 |
assert (X:(Pos.succ p # xI p) *0 < (Pos.succ p # xI p) *1). |
| 418 |
constructor. |
| 419 |
rewrite -> (fun a => SupDistanceToLinear_scale a C X). |
| 420 |
apply SupDistanceToLinear_wd1. |
| 421 |
simpl; ring. |
| 422 |
unfold affineCombo; simpl; ring. |
| 423 |
set (LHS := (SupDistanceToLinear (constStepF (X:=QS) (1 # xI p) * |
| 424 |
(constStepF (X:=QS) (Pos.succ p) + constStepF (X:=QS) p * stepSample p)) B)%Q). |
| 425 |
transitivity ((1#xI p)*(p*proj1_sig (SupDistanceToLinear (stepSample (p)) C)))%Q; [|rewrite -> IHp0; |
| 426 |
change ((p * 1 * (2 * (2* p + 1)) = 2* (p + p * (2* p)))%Z); ring]. |
| 427 |
assert (X0:(p *0 < p *1)). |
| 428 |
constructor. |
| 429 |
rewrite -> (fun a => SupDistanceToLinear_scale a C X0). |
| 430 |
assert (X1:(p*0 + Pos.succ p < p*1 + Pos.succ p)). |
| 431 |
apply: plus_resp_less_rht. |
| 432 |
assumption. |
| 433 |
rewrite -> (fun a => SupDistanceToLinear_translate a X0 X1). |
| 434 |
assert (X2:((1# xI p)*(p*0 + Pos.succ p) < (1#xI p)*(p*1 + Pos.succ p))). |
| 435 |
apply: mult_resp_less_lft;simpl; auto with *. |
| 436 |
rewrite -> (fun a => SupDistanceToLinear_scale a X1 X2). |
| 437 |
apply SupDistanceToLinear_wd1. |
| 438 |
unfold affineCombo; simpl. |
| 439 |
repeat rewrite -> Zpos_succ_morphism; repeat rewrite -> Qmake_Qdiv; repeat rewrite -> Zpos_xI; |
| 440 |
field; auto with *. |
| 441 |
change (2*(p*1) + 1 = ((p*1*1 + Pos.succ p*1)*1))%Z. |
| 442 |
rewrite Zpos_succ_morphism; ring. |
| 443 |
change (1#2*xO p)%Q with ((1#2)*(1#(2*p)))%Q. |
| 444 |
replace (stepSample (xO p)) with (glue (ou (1#2)) (constStepF (1#2:QS) * (stepSample p)) |
| 445 |
(constStepF (1#2:QS) * (constStepF (1:QS) + (stepSample p)))) |
| 446 |
by (symmetry;apply: positive_rect2_red2). |
| 447 |
rewrite -> SupDistanceToLinear_glue. |
| 448 |
generalize (@affineCombo_gt (OpenUnitDual (ou (1#2))) 0 1 (pos_one Q_as_COrdField)) |
| 449 |
(@affineCombo_lt (OpenUnitDual (ou (1#2))) 0 1 (pos_one Q_as_COrdField)). |
| 450 |
intros A B. |
| 451 |
set (C:=(pos_one Q_as_COrdField)) in *. |
| 452 |
transitivity (Qmax ((1#2)*(1#2 * p)) ((1#2)*(1#2 * p)))%Q;[|apply Qmax_idem]. |
| 453 |
set (D1:=(SupDistanceToLinear (constStepF (X:=QS) (1 # 2) * stepSample p) A)). |
| 454 |
set (D2:=(SupDistanceToLinear |
| 455 |
(constStepF (X:=QS) (1 # 2) * (constStepF (X:=QS) 1 + stepSample p)) B)). |
| 456 |
rewrite <- IHp. |
| 457 |
apply Qmax_compat. |
| 458 |
assert (X:((1#2) *0 < (1#2) *1)). |
| 459 |
constructor. |
| 460 |
rewrite -> (fun a c => SupDistanceToLinear_scale a c X). |
| 461 |
apply SupDistanceToLinear_wd1; constructor. |
| 462 |
assert (X0:0 + 1 < 1 +1). |
| 463 |
constructor. |
| 464 |
rewrite -> (fun a c => SupDistanceToLinear_translate a c X0). |
| 465 |
assert (X1:(1#2)*(0 + 1) < (1#2)*(1 +1)). |
| 466 |
constructor. |
| 467 |
rewrite -> (fun a => SupDistanceToLinear_scale a X0 X1). |
| 468 |
apply SupDistanceToLinear_wd1; constructor. |
| 469 |
reflexivity. |
| 470 |
Qed. |
| 471 |
|
| 472 |
(** Given a requested error of q, what is smallest n for [stepSample n] |
| 473 |
that will satifiy this error requirement. *) |
| 474 |
|
| 475 |
Definition id01_raw_help (q:QposInf) : positive := |
| 476 |
match q with |
| 477 |
|QposInfinity => 1%positive |
| 478 |
|Qpos2QposInf q => Qpos_ceiling ((1#2) * Qpos_inv q) |
| 479 |
end. |
| 480 |
|
| 481 |
Lemma id01_raw_help_le : forall (q:Qpos), |
| 482 |
((1#2*id01_raw_help q) <= proj1_sig q)%Q. |
| 483 |
Proof with auto with *. |
| 484 |
intros q. |
| 485 |
unfold id01_raw_help, Qpos_ceiling. |
| 486 |
simpl. |
| 487 |
generalize (Qle_ceiling ((1#2)*/proj1_sig q)). |
| 488 |
generalize (Qceiling ((1#2)*/proj1_sig q)). |
| 489 |
intros [|p|p] H. |
| 490 |
elim (Qle_not_lt _ _ H). |
| 491 |
apply Q.Qmult_lt_0_compat... |
| 492 |
apply Qinv_lt_0_compat... |
| 493 |
autorewrite with QposElim in *. |
| 494 |
rewrite -> Qmake_Qdiv in *. |
| 495 |
rewrite Zpos_xO. |
| 496 |
rewrite -> Qle_minus_iff in *. |
| 497 |
change ((2%positive * p)%Z:Q) with (2%positive * p)%Q. |
| 498 |
replace RHS with (((2*proj1_sig q)/(2*p)) |
| 499 |
*(p - 1%positive/2%positive*/proj1_sig q))%Q. |
| 500 |
apply: mult_resp_nonneg; simpl; auto with *. |
| 501 |
apply Qlt_le_weak. |
| 502 |
apply Q.Qmult_lt_0_compat... |
| 503 |
simpl. field. split... |
| 504 |
elim (Qle_not_lt _ _ H). |
| 505 |
apply Qlt_trans with 0... |
| 506 |
apply Q.Qmult_lt_0_compat... |
| 507 |
apply Qinv_lt_0_compat... |
| 508 |
Qed. |
| 509 |
|
| 510 |
(** Now define id01, the identity funciton on [[0,1]] as a bounded function, |
| 511 |
to be the limit of these [stepSample] functions. *) |
| 512 |
Definition id01_raw (q:QposInf) : StepQ := stepSample (id01_raw_help q). |
| 513 |
|
| 514 |
Lemma id01_prf : is_RegularFunction (@ball LinfStepQ) (id01_raw:QposInf -> LinfStepQ). |
| 515 |
Proof. |
| 516 |
intros a b. |
| 517 |
unfold id01_raw. |
| 518 |
apply ball_weak_le with (proj1_sig ((1#2*(id01_raw_help a)) + (1#2*(id01_raw_help b)))%Qpos). |
| 519 |
apply: plus_resp_leEq_both; apply id01_raw_help_le. |
| 520 |
simpl (ball (m:=LinfStepQ)). |
| 521 |
pose proof stepSampleDistanceToId. |
| 522 |
assert (QposEq ((1 # 2 * id01_raw_help a) + (1 # 2 * id01_raw_help b)) |
| 523 |
((SupDistanceToLinear (stepSample (id01_raw_help a)) (pos_one Q_as_COrdField)) |
| 524 |
+ (SupDistanceToLinear (stepSample (id01_raw_help b)) (pos_one Q_as_COrdField)))). |
| 525 |
{ unfold QposEq. simpl. unfold QposEq in H. simpl in H. |
| 526 |
do 2 rewrite H. reflexivity. } |
| 527 |
unfold QposEq in H0. rewrite H0. |
| 528 |
apply SupDistanceToLinear_trans. |
| 529 |
Qed. |
| 530 |
|
| 531 |
Definition id01 : BoundedFunction := |
| 532 |
Build_RegularFunction id01_prf. |
| 533 |
|
| 534 |
End id01. |
| 535 |
|
| 536 |
(** |
| 537 |
** StepFunctions distribute over Completion |
| 538 |
The distribution function maps StepF (Complete X) to Complete (StepF X). |
| 539 |
*) |
| 540 |
(* approximate z e is not a morphism, so we revert to using the pre-setoid version of StepF's map *) |
| 541 |
Definition distribComplete_raw (x:StepF (msp_as_RSetoid CR)) (e:QposInf) : LinfStepQ := |
| 542 |
StepFunction.Map (fun z => approximate z e) x. |
| 543 |
|
| 544 |
Lemma distribComplete_prf : forall (x:StepF (msp_as_RSetoid CR)), |
| 545 |
is_RegularFunction (@ball LinfStepQ) (distribComplete_raw x). |
| 546 |
Proof. |
| 547 |
unfold distribComplete_raw. |
| 548 |
intros x a b. |
| 549 |
induction x. |
| 550 |
apply (@regFun_prf _ Qball). |
| 551 |
simpl (ball (m:=LinfStepQ)). |
| 552 |
set (f:=(fun z : RegularFunction (@ball Q_as_MetricSpace) => approximate z a)) in *. |
| 553 |
set (g:=(fun z : RegularFunction (@ball Q_as_MetricSpace) => approximate z b)) in *. |
| 554 |
change (Map f (glue o x1 x2)) with (glue o (Map f x1:StepQ) (Map f x2)). |
| 555 |
change (Map g (glue o x1 x2)) with (glue o (Map g x1:StepQ) (Map g x2)). |
| 556 |
rewrite -> (StepFSupBallGlueGlue |
| 557 |
_ _ o (Map f x1 : StepQ) (Map f x2) |
| 558 |
(Map g x1 : StepQ) (Map g x2)). |
| 559 |
auto. |
| 560 |
Qed. |
| 561 |
|
| 562 |
Definition distribComplete (x:StepF (msp_as_RSetoid CR)) : BoundedFunction := |
| 563 |
Build_RegularFunction (distribComplete_prf x). |
| 564 |
|
| 565 |
Local Open Scope uc_scope. |
| 566 |
|
| 567 |
(** Given a uniformly continuous function f, and a step function g, |
| 568 |
the composition f o g is a bounded function. The map from g to f o g |
| 569 |
is uniformly continuous with modulus [mu f]. |
| 570 |
|
| 571 |
The same thing does not work for integrable functions becuase |
| 572 |
The map from g to f o g may not be uniformly continuous with modulus [mu f]. |
| 573 |
However, I have not found a counter example where f o g is not uniformly |
| 574 |
continuous. In fact, when f is lipschitz, then the map from g to |
| 575 |
f o g is Lipschitz. However Lipschitz functions haven't been |
| 576 |
formalized yet. *) |
| 577 |
|
| 578 |
Definition ComposeContinuous_raw (f:Q_as_MetricSpace-->CR) (z:LinfStepQ) : BoundedFunction := dist (uc_stdFun f ^@> z). |
| 579 |
(* begin hide *) |
| 580 |
Add Parametric Morphism f : (@ComposeContinuous_raw f) |
| 581 |
with signature (@msp_eq _) ==> (@msp_eq _) as ComposeContinuous_raw_wd. |
| 582 |
Proof. |
| 583 |
intros x1 x2 Hx. |
| 584 |
unfold ComposeContinuous_raw. |
| 585 |
apply uc_wd. |
| 586 |
apply StepF_eq_equiv in Hx. |
| 587 |
apply StepF_eq_equiv. |
| 588 |
rewrite -> Hx. |
| 589 |
reflexivity. |
| 590 |
Qed. |
| 591 |
(* end hide *) |
| 592 |
Lemma ComposeContinuous_prf (f:Q_as_MetricSpace --> CR) : |
| 593 |
is_UniformlyContinuousFunction (ComposeContinuous_raw f) (mu f). |
| 594 |
Proof. |
| 595 |
intros e a b. |
| 596 |
revert a b e. |
| 597 |
apply: StepF_ind2. |
| 598 |
intros s s0 t t0 Hs Ht H e H0. |
| 599 |
apply StepF_eq_equiv in Ht. rewrite <- Ht. |
| 600 |
apply StepF_eq_equiv in Hs. rewrite <- Hs. |
| 601 |
apply H. |
| 602 |
destruct (mu f e). 2: constructor. |
| 603 |
simpl. rewrite Hs, Ht. exact H0. |
| 604 |
intros x y e H. |
| 605 |
change (ball (proj1_sig e) (f x) (f y)). |
| 606 |
apply uc_prf. |
| 607 |
destruct (mu f e); try solve [constructor]. |
| 608 |
simpl. |
| 609 |
assumption. |
| 610 |
intros o s s0 t t0 H0 H1 e H. |
| 611 |
unfold ComposeContinuous_raw in *. |
| 612 |
repeat rewrite -> MapGlue, dist_glue. |
| 613 |
intros d1 d2. |
| 614 |
apply ball_weak_le with (proj1_sig (((1#2)*((1#2)*d1)) + e + ((1#2)*((1#2)*d2)))%Qpos). |
| 615 |
simpl. |
| 616 |
Qauto_le. |
| 617 |
simpl. |
| 618 |
unfold Cap_slow_raw. |
| 619 |
simpl. |
| 620 |
rewrite -> StepFSupBallGlueGlue. |
| 621 |
split. |
| 622 |
setoid_replace ((1 # 2) * ((1 # 2) * proj1_sig d1) + proj1_sig e + |
| 623 |
(1 # 2) * ((1 # 2) * proj1_sig d2))%Q |
| 624 |
with (proj1_sig ((1 # 2) * ((1 # 2) * d1) + e + (1 # 2) * ((1 # 2) * d2))%Qpos) |
| 625 |
by (simpl; ring). |
| 626 |
apply (H0 e). |
| 627 |
destruct (mu f e); try constructor. simpl in H. |
| 628 |
rewrite -> StepFSupBallGlueGlue in H; tauto. |
| 629 |
setoid_replace ((1 # 2) * ((1 # 2) * proj1_sig d1) + proj1_sig e + |
| 630 |
(1 # 2) * ((1 # 2) * proj1_sig d2))%Q |
| 631 |
with (proj1_sig ((1 # 2) * ((1 # 2) * d1) + e + (1 # 2) * ((1 # 2) * d2))%Qpos) |
| 632 |
by (simpl; ring). |
| 633 |
apply (H1 e). |
| 634 |
destruct (mu f e); try constructor. simpl in H. |
| 635 |
rewrite -> StepFSupBallGlueGlue in H; tauto. |
| 636 |
Qed. |
| 637 |
|
| 638 |
Definition ComposeContinuous (f:Q_as_MetricSpace --> CR) : LinfStepQ --> BoundedFunction := |
| 639 |
Build_UniformlyContinuousFunction (ComposeContinuous_prf f). |
| 640 |
|
| 641 |
(** |
| 642 |
** Riemann-Stieltjes Integral |
| 643 |
A measure on the reals is represented by the inverse of it's cumlative |
| 644 |
distribution function as a bounded function. So at the moment we |
| 645 |
can only integrate over bounded intervals. This effectively the |
| 646 |
Stieltjes integral [Integral f d(g^-1)]. *) |
| 647 |
Definition IntegrateWithMeasure (f:Q_as_MetricSpace --> CR) : BoundedFunction --> CR := |
| 648 |
(uc_compose IntegrableFunction.Integral |
| 649 |
(uc_compose BoundedAsIntegrable (Cbind (LinfStepQPrelengthSpace) (ComposeContinuous f)))). |
| 650 |
|
| 651 |
(** The Riemann Integral uses the uniform measure on [[0,1]]. The |
| 652 |
inverse of its cumlative distribution function is [id01]. *) |
| 653 |
Definition Integrate01 f := IntegrateWithMeasure f id01. |
| 654 |
|
| 655 |
Definition ContinuousSup01 f := |
| 656 |
(uc_compose sup (Cbind (LinfStepQPrelengthSpace) (ComposeContinuous f))) id01. |
| 657 |
|
| 658 |
(** Integrating a different range is just a matter of scaling and translating a little: *) |
| 659 |
Definition Integrate (f: Q_as_MetricSpace --> CR) (from width: Q): CR := |
| 660 |
(' width * Integrate01 (f ∘ Qplus_uc from ∘ Qscale_uc width))%CR. |
| 661 |
|
| 662 |
Lemma Integrate01_correct_generalize : |
| 663 |
forall (a b : Q) (F : PartFunct IR) |
| 664 |
(f : Q_as_MetricSpace --> CR) |
| 665 |
(e : Qpos), |
| 666 |
(forall (o : Q) (H : Dom F (inj_Q IR o)), |
| 667 |
a <= o <= b -> msp_eq (f o) (IRasCR (F (inj_Q IR o) H))) -> |
| 668 |
forall (H01 : inj_Q IR a [<=] inj_Q IR b) (HF : Continuous_I H01 F) |
| 669 |
(c : a < b) (s : StepQ), |
| 670 |
QposInf_le (Qpos2QposInf (SupDistanceToLinear s c)) (mu f ((1 # 2) * e)) -> |
| 671 |
@AbsSmall CRasCOrdField (' ((b - a) * proj1_sig e)%Q)%CR |
| 672 |
(IRasCR (integral (inj_Q IR a) (inj_Q IR b) H01 F HF) |
| 673 |
- (' ((b - a) * IntegralQ (dist_raw (uc_stdFun f ^@> s) ((1 # 2) * e)%Qpos))%Q))%CR. |
| 674 |
Proof. |
| 675 |
intros a b F f e Hf Hab HF Hab0 s Hs. |
| 676 |
destruct (Qpos_sub _ _ Hab0) as [ba Hba]. |
| 677 |
stepl ('proj1_sig (ba*e)%Qpos)%CR. |
| 678 |
2: simpl; rewrite Hba; |
| 679 |
rewrite Qplus_comm; unfold Qminus; |
| 680 |
rewrite <- Qplus_assoc, Qplus_opp_r, Qplus_0_r; reflexivity. |
| 681 |
revert a b Hab0 ba Hba F Hab HF Hf Hs. |
| 682 |
induction s; intros a b Hab0 ba Hba F Hab HF Hf Hs. |
| 683 |
- change (IntegralQ (dist_raw (constStepF (uc_stdFun f) <@^ x) ((1 # 2) * e)%Qpos)) |
| 684 |
with (approximate (f x) ((1 # 2) * e)%Qpos). |
| 685 |
rewrite <- (IR_inj_Q_as_CR ((b - a) * approximate (f x) ((1 # 2) * e)%Qpos)). |
| 686 |
unfold cg_minus. |
| 687 |
simpl. |
| 688 |
eapply AbsSmall_wdr;[|apply IR_minus_as_CR]. |
| 689 |
eapply AbsSmall_wdl;[|apply IR_inj_Q_as_CR]. |
| 690 |
rewrite <- IR_AbsSmall_as_CR. |
| 691 |
unfold SupDistanceToLinear in Hs. |
| 692 |
simpl in Hs. |
| 693 |
set (a0:=inj_Q IR (approximate (f x) ((1 # 2) * e)%Qpos)). |
| 694 |
set (e':=(inj_Q IR (proj1_sig e))). |
| 695 |
assert (X:forall y : IR, Compact Hab y -> forall Hy : Dom F y, AbsSmall e' ((F y Hy)[-]a0)). |
| 696 |
intros y Hy Hyf. |
| 697 |
rewrite -> IR_AbsSmall_as_CR. |
| 698 |
unfold e'. |
| 699 |
apply AbsSmall_wdr |
| 700 |
with (IRasCR (F y Hyf) - IRasCR a0)%CR;[|apply eq_symmetric; apply IR_minus_as_CR]. |
| 701 |
rewrite IR_inj_Q_as_CR. |
| 702 |
apply (CRAbsSmall_ball (IRasCR (F y Hyf))). |
| 703 |
unfold a0; rewrite -> IR_inj_Q_as_CR. |
| 704 |
assert (X0:(forall (q : Q) (Hq : Dom F (inj_Q IR q)), clcr (inj_Q IR a) (inj_Q IR b) (inj_Q IR q) -> |
| 705 |
(Cbind QPrelengthSpace f (' q) == IRasCR (F (inj_Q IR q) Hq))%CR)). |
| 706 |
intros q Hq [Hq0 H1]. |
| 707 |
pose proof (Cbind_correct QPrelengthSpace f). |
| 708 |
apply ucEq_equiv in H. |
| 709 |
rewrite -> (H (' q))%CR. clear H. |
| 710 |
rewrite -> (BindLaw1 f). |
| 711 |
apply Hf. |
| 712 |
split. |
| 713 |
apply (leEq_inj_Q IR). |
| 714 |
auto. |
| 715 |
apply (leEq_inj_Q IR). |
| 716 |
auto. |
| 717 |
assert (X:=@ContinuousCorrect (clcr (inj_Q IR a) (inj_Q IR b)) (inj_Q_less _ _ _ Hab0) F (Continuous_Int (clcr (inj_Q IR a) (inj_Q IR b)) Hab Hab F HF) |
| 718 |
(Cbind QPrelengthSpace f) X0 y Hyf Hy). |
| 719 |
set (z:=(' approximate (f x) ((1 # 2) * e)%Qpos)%CR). |
| 720 |
rewrite -> X. |
| 721 |
setoid_replace (proj1_sig e) |
| 722 |
with (proj1_sig ((1#2)*e + (1#2)*e)%Qpos) by (simpl; ring). |
| 723 |
apply ball_triangle with (f x); [|apply ball_approx_r]. |
| 724 |
rewrite <- (BindLaw1 f). |
| 725 |
pose proof (Cbind_correct QPrelengthSpace f) as H. |
| 726 |
apply ucEq_equiv in H. |
| 727 |
rewrite <- (H (Cunit_fun Q_as_MetricSpace x)). clear H. |
| 728 |
set (z0:=(Cbind QPrelengthSpace f (Cunit_fun Q_as_MetricSpace x))). |
| 729 |
apply: uc_prf. |
| 730 |
clear z X X0 Hyf. |
| 731 |
pose (mu f ((1#2)*e)%Qpos) as z. |
| 732 |
simpl. simpl in z. simpl in Hs. fold z in Hs. fold CR z. |
| 733 |
destruct z as [z|];[|constructor]. |
| 734 |
unfold ball_ex. |
| 735 |
eapply ball_weak_le. |
| 736 |
apply Hs. |
| 737 |
change (Cunit_fun Q_as_MetricSpace x) with ('x)%CR. |
| 738 |
rewrite <- IR_inj_Q_as_CR. |
| 739 |
rewrite <- CRAbsSmall_ball. |
| 740 |
autorewrite with QposElim. |
| 741 |
unfold cg_minus; simpl. |
| 742 |
eapply AbsSmall_wdr;[|apply IR_minus_as_CR]. |
| 743 |
eapply AbsSmall_wdl;[|apply IR_inj_Q_as_CR]. |
| 744 |
rewrite <- IR_AbsSmall_as_CR. |
| 745 |
apply AbsIR_imp_AbsSmall. |
| 746 |
assert(X:=leEq_or_leEq _ (inj_Q IR x) y). |
| 747 |
rewrite -> leEq_def. |
| 748 |
intros Y. |
| 749 |
apply X. |
| 750 |
clear X. |
| 751 |
intros X. |
| 752 |
revert Y. |
| 753 |
change (Not (inj_Q IR (Qmax (x - a) (b - x))[<]AbsIR (y[-]inj_Q IR x))). |
| 754 |
rewrite <- leEq_def. |
| 755 |
apply AbsSmall_imp_AbsIR. |
| 756 |
destruct X as [X|X]. |
| 757 |
apply leEq_imp_AbsSmall. |
| 758 |
apply shift_leEq_lft; assumption. |
| 759 |
apply leEq_transitive with (inj_Q IR (b - x)%Q). |
| 760 |
stepr ((inj_Q IR b)[-](inj_Q IR x)); [| now (apply eq_symmetric; apply inj_Q_minus)]. |
| 761 |
apply minus_resp_leEq. |
| 762 |
destruct Hy; assumption. |
| 763 |
apply inj_Q_leEq. |
| 764 |
apply Qmax_ub_r. |
| 765 |
apply AbsSmall_minus. |
| 766 |
apply leEq_imp_AbsSmall. |
| 767 |
apply shift_leEq_lft; assumption. |
| 768 |
apply leEq_transitive with (inj_Q IR (x - a)%Q). |
| 769 |
stepr ((inj_Q IR x)[-](inj_Q IR a)); [| now (apply eq_symmetric; apply inj_Q_minus)]. |
| 770 |
apply minus_resp_leEq_rht. |
| 771 |
destruct Hy; assumption. |
| 772 |
apply inj_Q_leEq. |
| 773 |
apply Qmax_ub_l. |
| 774 |
split. |
| 775 |
apply shift_leEq_minus. |
| 776 |
stepl (([--]e'[+]a0)[*](inj_Q IR b[-]inj_Q IR a)). |
| 777 |
apply lb_integral. |
| 778 |
intros y Hy Hyf. |
| 779 |
apply shift_plus_leEq. |
| 780 |
destruct (X y Hy Hyf); assumption. |
| 781 |
rstepl ([--]((inj_Q IR b[-]inj_Q IR a)[*]e') [+] (inj_Q IR b[-]inj_Q IR a)[*]a0). |
| 782 |
csetoid_replace (inj_Q IR b[-]inj_Q IR a) (inj_Q IR (b-a)%Q); |
| 783 |
[|apply eq_symmetric; apply inj_Q_minus]. |
| 784 |
apply bin_op_wd_unfolded. |
| 785 |
apply un_op_wd_unfolded. |
| 786 |
unfold e'. |
| 787 |
stepl (inj_Q IR ((b-a)*proj1_sig e)%Q); [| now apply inj_Q_mult]. |
| 788 |
apply: inj_Q_wd;simpl. |
| 789 |
autorewrite with QposElim. |
| 790 |
rewrite Hba. ring. |
| 791 |
apply eq_symmetric; apply inj_Q_mult. |
| 792 |
apply shift_minus_leEq. |
| 793 |
stepr ((e'[+]a0)[*](inj_Q IR b[-]inj_Q IR a)). |
| 794 |
apply ub_integral. |
| 795 |
intros y Hy Hyf. |
| 796 |
apply shift_leEq_plus. |
| 797 |
destruct (X y Hy Hyf); assumption. |
| 798 |
rstepl (((inj_Q IR b[-]inj_Q IR a)[*]e') [+] (inj_Q IR b[-]inj_Q IR a)[*]a0). |
| 799 |
csetoid_replace (inj_Q IR b[-]inj_Q IR a) (inj_Q IR (b-a)%Q); |
| 800 |
[|apply eq_symmetric; apply inj_Q_minus]. |
| 801 |
apply bin_op_wd_unfolded. |
| 802 |
unfold e'. |
| 803 |
stepl (inj_Q IR ((b-a)*proj1_sig e)%Q); [| now apply inj_Q_mult]. |
| 804 |
apply: inj_Q_wd;simpl. |
| 805 |
rewrite Hba. ring. |
| 806 |
apply eq_symmetric; apply inj_Q_mult. |
| 807 |
- set (z:=(IntegralQ (glue o (Map (fun z : RegularFunction Qball => |
| 808 |
approximate z ((1 # 2) * e)%Qpos) (Map f s1):StepQ) (Map |
| 809 |
(fun z : RegularFunction Qball => approximate z ((1 # 2) * e)%Qpos) (Map f s2))))). |
| 810 |
change (IntegralQ (dist_raw (uc_stdFun f ^@> glue o s1 s2) ((1 # 2) * e)%Qpos)) |
| 811 |
with z. |
| 812 |
apply (CRAbsSmall_ball (IRasCR (integral (inj_Q IR a) (inj_Q IR b) Hab F HF))). |
| 813 |
set (c:=(affineCombo (OpenUnitDual o) a b:Q)). |
| 814 |
assert (Hac:inj_Q IR a[<=]inj_Q IR c). |
| 815 |
unfold c. |
| 816 |
apply inj_Q_leEq. |
| 817 |
simpl; auto with *. |
| 818 |
assert (Hcb:inj_Q IR c[<=]inj_Q IR b). |
| 819 |
unfold c. |
| 820 |
apply inj_Q_leEq. |
| 821 |
simpl; auto with *. |
| 822 |
assert (HFl :Continuous_I Hac F). |
| 823 |
revert HF. |
| 824 |
apply included_imp_contin. |
| 825 |
intros x [Hxl Hxr]. |
| 826 |
split; auto. |
| 827 |
apply leEq_transitive with (inj_Q IR c); auto. |
| 828 |
assert (HFr :Continuous_I Hcb F). |
| 829 |
revert HF. |
| 830 |
apply included_imp_contin. |
| 831 |
intros x [Hxl Hxr]. |
| 832 |
split; auto. |
| 833 |
apply leEq_transitive with (inj_Q IR c); auto. |
| 834 |
setoid_replace (IRasCR (integral _ _ Hab F HF)) |
| 835 |
with (IRasCR (integral _ _ Hac F HFl)+IRasCR (integral _ _ Hcb F HFr))%CR; |
| 836 |
[| now (rewrite <- IR_plus_as_CR;apply IRasCR_wd; apply eq_symmetric; apply integral_plus_integral)]. |
| 837 |
unfold z. |
| 838 |
rewrite -> Integral_glue. |
| 839 |
clear z. |
| 840 |
set (zl:=IntegralQ (Map (fun z : RegularFunction Qball => |
| 841 |
approximate z ((1 # 2) * e)%Qpos) (Map f s1))). |
| 842 |
set (zr:=IntegralQ (Map (fun z : RegularFunction Qball => |
| 843 |
approximate z ((1 # 2) * e)%Qpos) (Map f s2))). |
| 844 |
setoid_replace ((b - a) * (o * zl + (1 - o) * zr))%Q with ((c - a)*zl + (b - c)*zr)%Q; |
| 845 |
[| now (unfold c, affineCombo, OpenUnitDual; simpl; ring)]. |
| 846 |
assert (Hac0: a < c). |
| 847 |
unfold c; auto with*. |
| 848 |
assert (Hcb0: c < b). |
| 849 |
unfold c; auto with*. |
| 850 |
destruct (Qpos_sub _ _ Hac0) as [ca Hca]. |
| 851 |
destruct (Qpos_sub _ _ Hcb0) as [bc Hbc]. |
| 852 |
assert (Z:(QposEq ba (ca + bc))%Qpos). |
| 853 |
unfold QposEq. |
| 854 |
rewrite -> Hba in Hbc. |
| 855 |
rewrite -> Hca in Hbc. |
| 856 |
replace LHS with (- a + (a + proj1_sig ba))%Q by simpl; ring. |
| 857 |
rewrite Hbc. simpl. ring. |
| 858 |
assert (QposEq (ba*e) ((ca+bc)*e)). |
| 859 |
{ unfold QposEq. simpl. unfold QposEq in Z. |
| 860 |
rewrite Z. reflexivity. } |
| 861 |
clear Z. unfold QposEq in H. rewrite H. clear H. |
| 862 |
assert (QposEq ((ca + bc)*e) (ca*e + bc*e)) |
| 863 |
by (unfold QposEq; simpl; ring). |
| 864 |
unfold QposEq in H. rewrite H. clear H. |
| 865 |
rewrite <- CRAbsSmall_ball. |
| 866 |
setoid_replace (@cg_minus CRasCGroup (IRasCR (integral (inj_Q IR a) (inj_Q IR c) Hac F HFl) + |
| 867 |
IRasCR (integral (inj_Q IR c) (inj_Q IR b) Hcb F HFr))%CR |
| 868 |
(' ((c - a) * zl + (b - c) * zr)%Q)%CR) |
| 869 |
with |
| 870 |
((IRasCR (integral (inj_Q IR a) (inj_Q IR c) Hac F HFl) - ('((c-a)*zl))%Q)+ |
| 871 |
((IRasCR (integral (inj_Q IR c) (inj_Q IR b) Hcb F HFr) - ('((b - c) * zr)%Q))))%CR. |
| 872 |
stepl ('proj1_sig (ca * e)%Qpos + 'proj1_sig (bc * e)%Qpos)%CR. |
| 873 |
apply: AbsSmall_plus. |
| 874 |
apply (IHs1 _ _ Hac0); auto. |
| 875 |
intros o0 H [H0 H1]. |
| 876 |
apply Hf. |
| 877 |
split; eauto with qarith. |
| 878 |
destruct (mu f ((1#2)*e)) as [q|];[|constructor]. |
| 879 |
simpl in Hs|-*. |
| 880 |
eapply Qle_trans;[|apply Hs]. |
| 881 |
rewrite -> SupDistanceToLinear_glue. |
| 882 |
replace LHS with (proj1_sig (SupDistanceToLinear s1 (affineCombo_gt (OpenUnitDual o) Hab0))). |
| 883 |
apply Qmax_ub_l. |
| 884 |
apply SupDistanceToLinear_wd1; reflexivity. |
| 885 |
apply (IHs2 _ _ Hcb0); auto. |
| 886 |
intros o0 H [H0 H1]. |
| 887 |
apply Hf. |
| 888 |
clear - H0 H1 Hac0. |
| 889 |
split; eauto with qarith. |
| 890 |
destruct (mu f ((1#2)*e)) as [q|];[|constructor]. |
| 891 |
simpl in Hs|-*. |
| 892 |
eapply Qle_trans;[|apply Hs]. |
| 893 |
rewrite -> SupDistanceToLinear_glue. |
| 894 |
replace LHS with (proj1_sig (SupDistanceToLinear s2 (affineCombo_lt (OpenUnitDual o) Hab0))). |
| 895 |
apply Qmax_ub_r. |
| 896 |
apply SupDistanceToLinear_wd1; reflexivity. |
| 897 |
change (' proj1_sig (ca * e)%Qpos + ' proj1_sig (bc * e)%Qpos |
| 898 |
==(' proj1_sig (ca * e + bc * e)%Qpos))%CR. |
| 899 |
unfold Qpos_mult, Qpos_plus, proj1_sig. ring. |
| 900 |
generalize (IRasCR (integral (inj_Q IR a) (inj_Q IR c) Hac F HFl)) |
| 901 |
(IRasCR (integral (inj_Q IR c) (inj_Q IR b) Hcb F HFr)). |
| 902 |
intros x y. |
| 903 |
clear - x y. |
| 904 |
change (@cg_minus CRasCGroup (x + y)%CR (' ((c - a) * zl + (b - c) * zr)%Q)%CR) |
| 905 |
with (x + y - ' ((c - a) * zl + (b - c) * zr)%Q)%CR. |
| 906 |
ring. |
| 907 |
Qed. |
| 908 |
|
| 909 |
|
| 910 |
(** Our integral on [[0,1]] is correct. *) |
| 911 |
Lemma Integrate01_correct : forall F (H01:[0][<=]([1]:IR)) (HF:Continuous_I H01 F) |
| 912 |
(f:Q_as_MetricSpace --> CR), |
| 913 |
(forall (o:Q) H, (0 <= o <= 1) -> (f o == IRasCR (F (inj_Q IR o) H)))%CR -> |
| 914 |
(IRasCR (integral [0] [1] H01 F HF)==Integrate01 f)%CR. |
| 915 |
Proof. |
| 916 |
intros F H01' HF' f Hf. |
| 917 |
assert (H01:(inj_Q IR 0)[<=](inj_Q IR 1)). |
| 918 |
{ apply inj_Q_leEq. discriminate. } |
| 919 |
assert (HF:Continuous_I H01 F). |
| 920 |
{ apply (included_imp_contin _ _ H01'). |
| 921 |
apply included_compact. |
| 922 |
apply (compact_wd _ _ H01' [0]). |
| 923 |
apply compact_inc_lft. |
| 924 |
apply eq_symmetric; apply (inj_Q_nring IR 0). |
| 925 |
apply (compact_wd _ _ H01' [1]). |
| 926 |
apply compact_inc_rht. |
| 927 |
rstepl (nring 1:IR). |
| 928 |
apply eq_symmetric; apply (inj_Q_nring IR 1). |
| 929 |
assumption. } |
| 930 |
transitivity (IRasCR (integral _ _ H01 F HF)). |
| 931 |
apply IRasCR_wd. |
| 932 |
apply integral_wd'. |
| 933 |
apply eq_symmetric; apply (inj_Q_nring IR 0). |
| 934 |
rstepl (nring 1:IR). |
| 935 |
apply eq_symmetric; apply (inj_Q_nring IR 1). |
| 936 |
clear H01' HF'. |
| 937 |
apply ball_eq. |
| 938 |
intros e epos. |
| 939 |
setoid_replace e with (proj1_sig ((1#2)*exist _ _ epos |
| 940 |
+ (1#2)*exist _ _ epos)%Qpos) |
| 941 |
by (simpl; ring). |
| 942 |
generalize ((1#2)*exist _ _ epos)%Qpos. |
| 943 |
clear epos e. |
| 944 |
intros e. |
| 945 |
eapply ball_triangle; [|apply (@ball_approx_l Q_as_MetricSpace)]. |
| 946 |
change (Cunit (approximate (Integrate01 f) e)) with ('(approximate (Integrate01 f) e))%CR. |
| 947 |
|
| 948 |
setoid_replace ('(approximate (Integrate01 f) e))%CR |
| 949 |
with ('((1-0)*(approximate (Integrate01 f) e))%Q)%CR. |
| 950 |
Focus 2. |
| 951 |
change (' approximate (Integrate01 f) e == ' ((1 - 0) * approximate (Integrate01 f) e)%Q)%CR. |
| 952 |
ring. |
| 953 |
rewrite <- CRAbsSmall_ball. |
| 954 |
stepl ('((1-0)*proj1_sig e)%Q)%CR; [| apply inject_Q_CR_wd; change ((1 - 0) * proj1_sig e == proj1_sig e)%Q; ring]. |
| 955 |
set (z:=(integral (inj_Q IR 0) (inj_Q IR 1) H01 F HF)). |
| 956 |
simpl. |
| 957 |
unfold Cjoin_raw. |
| 958 |
simpl. |
| 959 |
unfold distribComplete_raw. |
| 960 |
unfold id01_raw. |
| 961 |
assert (X:=stepSampleDistanceToId (id01_raw_help (mu f ((1 # 2) * e)))). |
| 962 |
revert X. |
| 963 |
remember (stepSample (id01_raw_help (mu f ((1 # 2) * e)))) as s. |
| 964 |
simpl in Heqs. rewrite <- Heqs. clear Heqs. |
| 965 |
intros Hs. |
| 966 |
assert (X:QposInf_le (Qpos2QposInf (SupDistanceToLinear s (pos_one Q_as_COrdField))) (mu f ((1 # 2) * e))). |
| 967 |
destruct (mu f ((1#2) *e)); try constructor. |
| 968 |
unfold QposEq in Hs. |
| 969 |
simpl. |
| 970 |
rewrite -> Hs. |
| 971 |
apply id01_raw_help_le. |
| 972 |
clear Hs. |
| 973 |
rename X into Hs. |
| 974 |
revert s Hs. |
| 975 |
generalize (pos_one Q_as_COrdField). |
| 976 |
intros c s Hs. |
| 977 |
simpl in c, Hs. |
| 978 |
revert c s Hs. |
| 979 |
unfold z. |
| 980 |
clear z. |
| 981 |
revert H01 HF. |
| 982 |
revert Hf. |
| 983 |
apply Integrate01_correct_generalize. |
| 984 |
Qed. |