Debian Codegraph @

reals/fast/ModulusDerivative.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 Require Import CoRN.algebra.RSetoid.
22 Require Import CoRN.metric2.Metric.
23 Require Import CoRN.metric2.UniformContinuity.
24 Require Export CoRN.reals.Q_in_CReals.
25 Require Export CoRN.reals.fast.CRIR.
26 Require Export CoRN.ftc.Rolle.
27 Require Import CoRN.tactics.CornTac.
28 Require Export CoRN.model.metric2.Qmetric.
29 Require Import CoRN.model.totalorder.QposMinMax.
30 Require Export CoRN.model.totalorder.QMinMax.
31
32 Opaque Qmin Qmax.
33 Opaque CR inj_Q.
34
35 Section Modulus.
36 (**
37 ** Modulus of continity and derivatives.
38 If two functions, one defined on IR and the other defined on CR, agree
39 on rational valued inside a closed non-trival interval, and the
40 function on IR is differentiable on that interval, then the function on
41 CR is uniformly continuous with modulus [fun e => e/M] where M is
42 some upper bound on the absolute value of the derivative.
43 *)
44 Variable l r : option Q.
45 Hypothesis Hlr :
46 match l,r with
47 | None, _ => True
48 | _, None => True
49 | Some l', Some r' => (l'<r')%Q
50 end.
51
52 Let I :=
53 match l,r with
54 | None, None => realline
55 | Some l', None => closel (inj_Q _ l')
56 | None, Some r' => closer (inj_Q _ r')
57 | Some l', Some r' => clcr (inj_Q _ l') (inj_Q _ r')
58 end.
59
60 Let properI : proper I.
61 Proof.
62 destruct l; destruct r; try constructor.
63 simpl.
64 apply inj_Q_less.
65 assumption.
66 Qed.
67
68 Let clamp (q:Q) :=
69 match l,r with
70 | None, None => q
71 | Some l', None => QboundBelow_uc l' q
72 | None, Some r' => QboundAbove_uc r' q
73 | Some l', Some r' => (uc_compose (QboundBelow_uc l') (QboundAbove_uc r') q)
74 end.
75
76 Lemma ball_clamp : forall (e:Qpos) (a b : Q),
77 @ball Q_as_MetricSpace (proj1_sig e) a b
78 -> ball (proj1_sig e) (clamp a) (clamp b).
79 Proof.
80 destruct l; destruct r; unfold clamp; intros e a b Hab; try apply uc_prf; apply Hab.
81 Qed.
82
83 Variable f f' : PartFunct IR.
84 Hypothesis Hf : Derivative I properI f f'.
85
86 Section GeneralCase.
87
88 Variable g : Q_as_MetricSpace -> CR.
89 Hypothesis Hg : forall (q:Q) Hq,
90 I (inj_Q _ q) -> (g q == IRasCR (f (inj_Q _ q) Hq))%CR.
91
92 Variable c : Q.
93 Hypothesis Hc : forall x Hx, I x -> (AbsIR (f' x Hx)[<=](inj_Q _ (c:Q))).
94
95 Lemma is_UniformlyContinuousD
96 : @is_UniformlyContinuousFunction
97 Q_as_MetricSpace CR (fun x => g (clamp x)) (Qscale_modulus c).
98 Proof.
99 intros e a b Hab.
100 assert (X:forall x, I (inj_Q _ (clamp x))).
101 clear -I Hlr.
102 intros x.
103 destruct l; destruct r; try split; unfold clamp; apply: inj_Q_leEq; simpl;
104 auto with *.
105 assert (Y:=(fun a=> (Hg _ (Derivative_imp_inc _ _ _ _ Hf _ (X a)) (X a)))).
106 do 2 rewrite -> Y.
107 rewrite <- CRAbsSmall_ball.
108 unfold cg_minus.
109 simpl.
110 stepl (IRasCR (inj_Q IR (proj1_sig e))); [| now simpl; apply IR_inj_Q_as_CR].
111 stepr (IRasCR ((f (inj_Q IR (clamp a))
112 (Derivative_imp_inc I properI f f' Hf (inj_Q IR (clamp a)) (X a)))[-] (f (inj_Q IR (clamp b))
113 (Derivative_imp_inc I properI f f' Hf (inj_Q IR (clamp b)) (X b)))))
114 ; [| now simpl; apply IR_minus_as_CR].
115 rewrite <- IR_AbsSmall_as_CR.
116 apply AbsIR_imp_AbsSmall.
117 eapply leEq_transitive;[eapply Law_of_the_Mean_Abs_ineq;try apply Hf;try apply X|].
118 intros x H Hx.
119 apply Hc.
120 eapply included_interval;[| |apply H];apply X.
121 revert Hab.
122 apply Qscale_modulus_elim.
123 intros Hc0 _.
124 stepl (inj_Q IR (nring 0)).
125 apply inj_Q_leEq.
126 simpl; auto with *.
127 setoid_replace (inj_Q IR c) with (inj_Q IR (nring 0)).
128 rewrite -> inj_Q_nring.
129 rational.
130 apply inj_Q_wd.
131 auto.
132 intros y Hyc Hab.
133 stepr ((inj_Q IR (proj1_sig e/proj1_sig y)%Q[*](inj_Q _ (proj1_sig y)))).
134 apply mult_resp_leEq_both.
135 eapply leEq_transitive.
136 apply AbsIR_nonneg.
137 apply (Hc _ (Derivative_imp_inc' I properI f f' Hf (inj_Q IR (clamp a)) (X a))).
138 apply X.
139 apply AbsIR_nonneg.
140 apply inj_Q_leEq.
141 destruct Hyc; auto.
142 apply AbsSmall_imp_AbsIR.
143 stepr (inj_Q IR (clamp a - clamp b)%Q); [| now apply inj_Q_minus].
144 apply inj_Q_AbsSmall.
145 change (ball (proj1_sig y) (clamp a) (clamp b)).
146 apply ball_clamp.
147 auto.
148 assert (Z:[0][<]inj_Q IR (proj1_sig y)).
149 (stepl (inj_Q IR ([0]:Q)); [| now apply (inj_Q_nring IR 0)]); apply inj_Q_less; apply Qpos_ispos.
150 eapply eq_transitive.
151 apply mult_wdl.
152 apply (inj_Q_div IR (proj1_sig e) _ (pos_ap_zero _ _ Z)).
153 apply div_1.
154 Qed.
155
156 End GeneralCase.
157
158 Lemma is_UniformlyContinuousD_Q
159 : forall g : Q_as_MetricSpace -> Q,
160 (forall (q : Q) (Hq : Dom f (inj_Q IR q)),
161 I (inj_Q IR q) -> (inj_Q IR (g q) [=] (f (inj_Q IR q) Hq))) ->
162 forall c : Q,
163 (forall (x : Q) (Hx : Dom f' (inj_Q IR x)), I (inj_Q IR x) -> AbsIR (f' (inj_Q IR x) Hx)[<=]inj_Q IR (c:Q)) ->
164 @is_UniformlyContinuousFunction
165 Q_as_MetricSpace Q_as_MetricSpace
166 (fun x : Q_as_MetricSpace => g (clamp x)) (Qscale_modulus c).
167 Proof.
168 intros g Hg c Hc.
169 intros e a b Hab.
170 rewrite <- ball_Cunit.
171 generalize e a b Hab; clear e a b Hab.
172 change (is_UniformlyContinuousFunction
173 (fun x : Q_as_MetricSpace => ((fun y => '(g y)) (clamp x)))%CR (Qscale_modulus c)).
174 apply is_UniformlyContinuousD.
175 intros q Hq H.
176 rewrite <- IR_inj_Q_as_CR.
177 apply IRasCR_wd.
178 apply Hg.
179 assumption.
180 intros x Hx HI.
181 rstepr ([0][+]inj_Q IR c).
182 apply shift_leEq_plus.
183 apply approach_zero_weak.
184 intros e He.
185 assert (X:Derivative_I (proper_compact_in_interval' I properI x HI
186 (compact_compact_in_interval I properI x HI)) f f').
187 apply (included_imp_Derivative) with I properI; try assumption.
188 eapply included_trans.
189 apply iprop_compact_in_interval_inc1.
190 apply included_compact_in_interval.
191 set (LI' := (Lend (compact_compact_in_interval I properI x HI))).
192 set (RI' := (Rend (compact_compact_in_interval I properI x HI))).
193 set (I':=(less_leEq IR LI' RI' (proper_compact_in_interval' I properI x HI
194 (compact_compact_in_interval I properI x HI)))).
195 assert (X':Continuous_I I' (FAbs f')).
196 apply Continuous_I_abs.
197 apply (deriv_imp_contin'_I _ _ _ _ _ (less_leEq _ _ _ (proper_compact_in_interval' I properI x HI
198 (compact_compact_in_interval I properI x HI))) X).
199 clear X.
200 destruct (contin_prop _ _ _ _ X' _ (pos_div_two _ _ He)) as [d Hd Hd0].
201 destruct (iprop_compact_in_interval' _ properI x HI _ I') as [c0 c1].
202 assert (Z:~((LI'[<]x or x[<]RI')->False)).
203 intro H.
204 fold LI' in c0.
205 fold RI' in c1.
206 apply (leEq_less_or_equal _ _ _ c0).
207 intros [H0|H0];[tauto|].
208 apply (leEq_less_or_equal _ _ _ c1).
209 intros [H1|H1];[tauto|].
210 generalize (proper_compact_in_interval' I properI x HI (compact_compact_in_interval I properI x HI)).
211 change (Not (LI'[<]RI')).
212 rewrite <- leEq_def.
213 rewrite -> H0, <- H1.
214 apply leEq_reflexive.
215 rewrite -> leEq_def.
216 intros Z0.
217 apply Z.
218 intros Z'.
219 revert Z0.
220 change (Not (e[<]AbsIR (f' x Hx)[-]inj_Q IR c)).
221 rewrite <- leEq_def.
222 clear Z.
223 assert (J:Max LI' (x[-]d)[<]Min RI' (x[+]d)).
224 destruct Z' as [Z'|Z'].
225 apply less_leEq_trans with x.
226 apply Max_less; auto.
227 rstepr (x[-][0]).
228 apply minus_resp_less_rht.
229 auto.
230 apply leEq_Min; auto with *.
231 rstepl (x[+][0]).
232 apply plus_resp_leEq_lft.
233 apply less_leEq.
234 auto with *.
235 apply leEq_less_trans with x.
236 apply Max_leEq; auto.
237 rstepr (x[-][0]).
238 apply minus_resp_leEq_rht.
239 apply less_leEq.
240 auto.
241 apply less_Min; auto with *.
242 rstepl (x[+][0]).
243 apply plus_resp_less_lft.
244 auto with *.
245 destruct (Q_dense_in_CReals' _ _ _ J) as [q Hq0 Hq1].
246 rstepr (e[/]TwoNZ [+] e[/]TwoNZ).
247 assert (HI0 : Compact I' (inj_Q IR q)).
248 split; apply less_leEq.
249 eapply leEq_less_trans;[|apply Hq0].
250 apply lft_leEq_Max.
251 eapply less_leEq_trans;[apply Hq1|].
252 apply Min_leEq_lft.
253 assert (Hq:Dom f' (inj_Q IR q)).
254 apply (Derivative_imp_inc' _ _ _ _ Hf).
255 apply (included_compact_in_interval _ properI x HI).
256 apply (iprop_compact_in_interval_inc1 _ _ _ _ _ I').
257 auto.
258 rstepl ((AbsIR (f' x Hx)[-]AbsIR (f' _ Hq))[+](AbsIR (f' _ Hq)[-]inj_Q IR c)).
259 apply plus_resp_leEq_both.
260 eapply leEq_transitive.
261 apply leEq_AbsIR.
262 assert (Z : Dom (FAbs f') x).
263 split;auto.
264 assert (Y : Dom (FAbs f') (inj_Q IR q)).
265 split;auto.
266 rewrite <- (FAbs_char _ _ Z).
267 rewrite <- (FAbs_char _ _ Y).
268 apply Hd0; auto.
269 apply iprop_compact_in_interval'.
270 apply AbsSmall_imp_AbsIR.
271 split.
272 apply shift_leEq_minus'.
273 rstepl (inj_Q IR q[-]d).
274 apply shift_minus_leEq.
275 apply less_leEq.
276 eapply less_leEq_trans;[apply Hq1|].
277 apply Min_leEq_rht.
278 apply shift_minus_leEq.
279 apply shift_leEq_plus'.
280 apply less_leEq.
281 eapply leEq_less_trans;[|apply Hq0].
282 apply rht_leEq_Max.
283 eapply leEq_transitive;[|apply nonneg_div_two;apply less_leEq; auto].
284 clear - Hc HI0.
285 apply shift_minus_leEq.
286 rstepr (inj_Q IR c).
287 apply Hc.
288 apply (included_compact_in_interval _ properI x HI).
289 apply (iprop_compact_in_interval_inc1 _ properI x HI _ I').
290 auto.
291 Qed.
292
293 End Modulus.