Debian Codegraph @

reals/fast/Integration.v

raw
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.