Debian Codegraph @

reals/fast/CRarctan.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.reals.fast.CRArith.
26 Require Import CoRN.reals.fast.CRIR.
27 Require Import CoRN.reals.Q_in_CReals.
28 Require Import CoRN.model.totalorder.QMinMax.
29 Require Import CoRN.reals.fast.CRarctan_small.
30 Require Import CoRN.reals.fast.CRpi.
31 Require Import CoRN.transc.MoreArcTan.
32 Require Import CoRN.reals.fast.ModulusDerivative.
33 Require Import CoRN.reals.fast.ContinuousCorrect.
34 Require Import CoRN.tactics.CornTac.
35 Require Import CoRN.stdlib_omissions.Q.
36 Require Import MathClasses.interfaces.abstract_algebra.
37 From Coq Require Import Psatz.
38
39 (* Backwards compatibility for Hint Rewrite locality attributes *)
40 Set Warnings "-unsupported-attributes".
41
42 Set Implicit Arguments.
43
44 Local Open Scope Q_scope.
45 Local Open Scope uc_scope.
46
47 Opaque inj_Q CR.
48 (**
49 ** Arctangent
50 Using pi and properties of arctangent, we define arctangent from 1 to
51 infinity.
52 *)
53
54 Lemma Qinv_one_lt : forall (a:Q),
55 1 < a -> -1 < /a < 1.
56 Proof.
57 split.
58 apply (Qlt_le_trans _ 0). reflexivity.
59 apply Qinv_le_0_compat; apply Qle_trans with 1; auto with qarith.
60 change (/a < /1); apply Q.Qdiv_flip_lt; auto with qarith.
61 Qed.
62
63 Definition rational_arctan_big_pos (a:Q) (Ha:1 < a) : CR :=
64 (r_pi (1#2) - @rational_arctan_small (/a) (widen_interval (Qinv_one_lt Ha)))%CR.
65
66 Lemma rational_arctan_big_pos_correct_aux (a : Q) :
67 0 < a → (r_pi (1 # 2) - IRasCR (ArcTan (inj_Q IR (/ a))))%CR = IRasCR (ArcTan (inj_Q IR a)).
68 Proof.
69 intros Ha.
70 rewrite -> r_pi_correct.
71 assert (H1:(inj_Q IR a)[#][0]).
72 stepr (inj_Q IR [0]); [| now apply (inj_Q_nring IR 0)].
73 apply inj_Q_ap.
74 apply (Greater_imp_ap _ a 0); assumption.
75 rewrite <- IR_minus_as_CR.
76 apply IRasCR_wd.
77 stepl (Pi[/]TwoNZ[-](ArcTan ([1][/]_[//]H1))).
78 assert (H2:[0][<]inj_Q IR a).
79 stepl (inj_Q IR [0]); [| now apply (inj_Q_nring IR 0)].
80 apply inj_Q_less; assumption.
81 unfold cg_minus.
82 csetoid_rewrite (ArcTan_recip _ H1 H2).
83 rational.
84 apply bin_op_wd_unfolded.
85 rstepl (((nring 1)[/]TwoNZ)[*]Pi).
86 apply mult_wdl.
87 change (1#2) with (1/2).
88 assert (H2:(inj_Q IR (2#1))[#][0]).
89 stepr (inj_Q IR [0]); [| now apply (inj_Q_nring IR 0)].
90 apply inj_Q_ap; discriminate.
91 apply eq_transitive with ((inj_Q IR 1)[/]_[//]H2).
92 apply div_wd.
93 apply eq_symmetric; apply (inj_Q_nring IR 1).
94 apply eq_symmetric; apply (inj_Q_nring IR 2).
95 apply eq_symmetric; apply inj_Q_div.
96 apply un_op_wd_unfolded.
97 apply ArcTan_wd.
98 apply eq_transitive with ((inj_Q IR 1)[/]_[//]H1).
99 apply div_wd.
100 rstepl (nring 1:IR).
101 apply eq_symmetric; apply (inj_Q_nring IR 1).
102 apply eq_reflexive.
103 eapply eq_transitive.
104 apply eq_symmetric; apply inj_Q_div.
105 apply inj_Q_wd.
106 simpl.
107 unfold Qdiv.
108 ring.
109 Qed.
110
111 Lemma rational_arctan_big_pos_correct : forall a (Ha: 1 < a),
112 (rational_arctan_big_pos Ha == IRasCR (ArcTan (inj_Q IR a)))%CR.
113 Proof.
114 intros a Ha.
115 unfold rational_arctan_big_pos.
116 rewrite -> rational_arctan_small_correct.
117 apply rational_arctan_big_pos_correct_aux.
118 now apply Qlt_trans with 1.
119 Qed.
120
121 Lemma rational_arctan_mid_pos_prf a : 0 < a → - (1) < (a - 1) / (a + 1) < 1.
122 Proof.
123 split;(try apply Qlt_shift_div_l; try apply Qlt_shift_div_r; psatzl Q).
124 Qed.
125
126 (** Because we have slow convergence near 1, we have another computation
127 that works for nonnegative numbers, and is particularly fast near 1. *)
128 Definition rational_arctan_mid_pos (a:Q) (Ha : 0 < a) : CR :=
129 (r_pi (1#4) + (rational_arctan_small (widen_interval (rational_arctan_mid_pos_prf Ha))))%CR.
130
131 Lemma rational_arctan_mid_pos_correct_aux (a : Q) :
132 0 < a → (r_pi (1#4) + IRasCR (ArcTan (inj_Q IR ((a - 1) / (a + 1)))))%CR = IRasCR (ArcTan (inj_Q IR a)).
133 Proof.
134 intros Ha.
135 rewrite r_pi_correct.
136 rewrite <-IR_plus_as_CR.
137 apply IRasCR_wd.
138 stepl (Pi[/]FourNZ[+]ArcTan (inj_Q IR ((a - 1) / (a + 1)))).
139 csetoid_rewrite_rev (ArcTan_one).
140 set (y:= (inj_Q IR ((a - 1) / (a + 1)))).
141 assert (Y:[0][<][1][-][1][*]y).
142 apply shift_zero_less_minus.
143 rstepl y.
144 rstepr (nring 1:IR).
145 stepr (inj_Q IR 1); [| now apply (inj_Q_nring IR 1)].
146 apply inj_Q_less.
147 now apply rational_arctan_mid_pos_prf.
148 apply eq_transitive with (ArcTan ([1][+]y[/]_[//](Greater_imp_ap _ _ _ Y))).
149 apply ArcTan_plus_ArcTan.
150 apply shift_zero_leEq_minus'.
151 rstepr (Two:IR).
152 apply nring_nonneg.
153 apply leEq_reflexive.
154 rstepl ([--](nring 1:IR)).
155 stepl (inj_Q IR ([--](1))).
156 apply inj_Q_leEq.
157 apply less_leEq. now apply rational_arctan_mid_pos_prf.
158 csetoid_rewrite_rev (inj_Q_nring IR 1).
159 apply inj_Q_inv.
160 rstepr (nring 1:IR).
161 stepr (inj_Q IR 1); [| now apply (inj_Q_nring IR 1)].
162 apply inj_Q_leEq.
163 apply less_leEq. now apply rational_arctan_mid_pos_prf.
164 apply ArcTan_wd.
165 apply mult_cancel_lft with ([1][-][1][*]y).
166 apply Greater_imp_ap; assumption.
167 rstepl ([1][+]y).
168 rstepr (inj_Q IR a[-]y[*]inj_Q IR a).
169 csetoid_replace ([1]:IR) (inj_Q IR 1).
170 unfold y.
171 set (y' := ((a - 1) / (a + 1))).
172 unfold cg_minus.
173 csetoid_rewrite_rev (inj_Q_mult IR y' a).
174 eapply eq_transitive.
175 apply eq_symmetric; apply inj_Q_plus.
176 apply eq_transitive with (inj_Q IR (a[+][--](y'[*]a)));[| apply inj_Q_minus].
177 apply inj_Q_wd.
178 simpl.
179 unfold y'.
180 field.
181 intros E. destruct (Qlt_irrefl 0). transitivity a; auto.
182 rewrite <-E, Qlt_minus_iff. now ring_simplify.
183 rstepl (nring 1:IR).
184 apply eq_symmetric; apply (inj_Q_nring IR 1).
185 apply bin_op_wd_unfolded;[|apply eq_reflexive].
186 apply mult_cancel_lft with Four.
187 apply four_ap_zero.
188 rstepl ((nring 1:IR)[*]Pi).
189 rstepr ((Four[*]inj_Q IR (1 # 4))[*]Pi).
190 apply mult_wdl.
191 stepl (inj_Q IR 1); [| now apply (inj_Q_nring IR 1)].
192 stepr (inj_Q IR (4*(1#4))).
193 apply inj_Q_wd.
194 simpl.
195 reflexivity.
196 eapply eq_transitive.
197 apply inj_Q_mult.
198 apply mult_wdl.
199 apply (inj_Q_nring IR 4).
200 Qed.
201
202 Lemma rational_arctan_mid_pos_correct : forall a (Ha: 0 < a),
203 (rational_arctan_mid_pos Ha == IRasCR (ArcTan (inj_Q IR a)))%CR.
204 Proof.
205 intros.
206 unfold rational_arctan_mid_pos.
207 rewrite rational_arctan_small_correct.
208 now apply rational_arctan_mid_pos_correct_aux.
209 Qed.
210
211 (** We glue all of are different methods of computing arctangent into
212 a nice fast one that works for nonnegative numbers. *)
213 Definition rational_arctan_pos (a:Q) (Ha:0 <= a) : CR.
214 Proof.
215 revert Ha.
216 destruct (Qle_total (2#5) a) as [A|A].
217 destruct (Qle_total (5#2) a) as [B|_]; intros _.
218 apply (@rational_arctan_big_pos a).
219 abstract (eapply Qlt_le_trans;[|apply B];auto with qarith).
220 apply (@rational_arctan_mid_pos a).
221 abstract (eapply Qlt_le_trans;[|apply A];auto with qarith).
222 intros H.
223 apply (@rational_arctan_small a).
224 apply widen_interval.
225 abstract ( split;[refine (Qlt_le_trans _ 0 a _ H); reflexivity| eapply Qle_lt_trans;[apply A|auto with qarith]]).
226 Defined.
227
228 Lemma rational_arctan_pos_correct : forall a (Ha: 0 <= a),
229 (rational_arctan_pos Ha == IRasCR (ArcTan (inj_Q IR a)))%CR.
230 Proof.
231 intros a Ha.
232 unfold rational_arctan_pos.
233 destruct (Qle_total (2 # 5) a).
234 destruct (Qle_total (5 # 2) a).
235 apply rational_arctan_big_pos_correct.
236 apply rational_arctan_mid_pos_correct.
237 apply rational_arctan_small_correct.
238 Qed.
239
240 (** By symmetry we get arctangent for all numbers. *)
241 Definition rational_arctan (a:Q) : CR.
242 Proof.
243 destruct (Qle_total a 0) as [H|H].
244 refine (-(@rational_arctan_pos (-a)%Q _))%CR.
245 abstract ( change (-0 <= -a); apply: (inv_resp_leEq); assumption).
246 apply (rational_arctan_pos H).
247 Defined.
248
249 Lemma rational_arctan_small_correct_aux (a : Q) :
250 (- IRasCR (ArcTan (inj_Q IR (- a)%Q)))%CR = IRasCR (ArcTan (inj_Q IR a)).
251 Proof.
252 rewrite <- IR_opp_as_CR.
253 apply IRasCR_wd.
254 csetoid_rewrite_rev (ArcTan_inv (inj_Q IR (-a))).
255 apply ArcTan_wd.
256 eapply eq_transitive.
257 apply eq_symmetric; apply (inj_Q_inv IR (-a)).
258 apply inj_Q_wd.
259 simpl.
260 ring.
261 Qed.
262
263 Lemma rational_arctan_correct : forall (a:Q),
264 (rational_arctan a == IRasCR (ArcTan (inj_Q IR a)))%CR.
265 Proof.
266 intros a.
267 unfold rational_arctan.
268 destruct (Qle_total a 0); rewrite -> rational_arctan_pos_correct.
269 apply rational_arctan_small_correct_aux.
270 reflexivity.
271 Qed.
272
273 Lemma rational_arctan_opp (a : Q) :
274 (-rational_arctan (-a) = rational_arctan a)%CR.
275 Proof.
276 do 2 rewrite rational_arctan_correct.
277 now apply rational_arctan_small_correct_aux.
278 Qed.
279
280 Lemma rational_arctan_half_pi (a : Q) :
281 0 < a → (r_pi (1 # 2) - rational_arctan (/ a) = rational_arctan a)%CR.
282 Proof.
283 intros.
284 do 2 rewrite rational_arctan_correct.
285 now apply rational_arctan_big_pos_correct_aux.
286 Qed.
287
288 Lemma rational_arctan_fourth_pi (a : Q) :
289 0 < a → (r_pi (1 # 4) + rational_arctan ((a - 1) / (a + 1)) = rational_arctan a)%CR.
290 Proof.
291 intros.
292 do 2 rewrite rational_arctan_correct.
293 now apply rational_arctan_mid_pos_correct_aux.
294 Qed.
295
296 (** Lift arctangent on the rationals to the reals. *)
297 Lemma arctan_uc_prf : @is_UniformlyContinuousFunction
298 Q_as_MetricSpace CR rational_arctan Qpos2QposInf.
299 Proof.
300 apply (is_UniformlyContinuousFunction_wd) with rational_arctan (Qscale_modulus (1#1)).
301 reflexivity.
302 intros x.
303 simpl.
304 autorewrite with QposElim.
305 change (/1) with 1.
306 replace RHS with (proj1_sig x) by simpl; ring.
307 apply Qle_refl.
308 apply (is_UniformlyContinuousD None None I _ _ (Derivative_ArcTan I) rational_arctan).
309 intros q [] _.
310 apply rational_arctan_correct.
311 intros x Hx _.
312 assert (X:[0][<][1][+][1][*]x[*]x).
313 apply plus_resp_pos_nonneg.
314 apply pos_one.
315 rstepr (x[^]2).
316 apply sqr_nonneg.
317 stepr ([1]:IR).
318 simpl.
319 apply AbsSmall_imp_AbsIR.
320 apply leEq_imp_AbsSmall.
321 apply shift_leEq_div.
322 assumption.
323 rstepl ([0]:IR).
324 apply less_leEq; apply pos_one.
325 apply shift_div_leEq.
326 assumption.
327 rstepr ([1][+]x[^]2).
328 apply shift_leEq_plus'.
329 rstepl ([0]:IR).
330 apply sqr_nonneg.
331 rstepl (nring 1:IR).
332 apply eq_symmetric; apply (inj_Q_nring IR 1).
333 Qed.
334
335 Definition arctan_uc : Q_as_MetricSpace --> CR :=
336 Build_UniformlyContinuousFunction arctan_uc_prf.
337
338 Definition arctan : CR --> CR := Cbind QPrelengthSpace arctan_uc.
339
340 Lemma arctan_correct : forall x,
341 (IRasCR (ArcTan x) == arctan (IRasCR x))%CR.
342 Proof.
343 intros x.
344 apply (ContinuousCorrect (I:proper realline)); [apply Continuous_ArcTan | | constructor].
345 intros q [] _.
346 transitivity (rational_arctan q);[|apply rational_arctan_correct].
347 unfold arctan.
348 pose proof (Cbind_correct QPrelengthSpace arctan_uc).
349 apply ucEq_equiv in H.
350 rewrite -> (H (' q))%CR.
351 apply BindLaw1.
352 Qed.
353 (* begin hide *)
354 #[global]
355 Hint Rewrite arctan_correct : IRtoCR.
356 (* end hide *)
357 Lemma arctan_Qarctan : forall x : Q, (arctan (' x) == rational_arctan x)%CR.
358 Proof.
359 intros x.
360 unfold arctan.
361 pose proof (Cbind_correct QPrelengthSpace arctan_uc).
362 apply ucEq_equiv in H.
363 rewrite -> (H (' x))%CR.
364 apply BindLaw1.
365 Qed.
366 (* begin hide *)
367 #[global]
368 Hint Rewrite arctan_Qarctan : CRfast_compute.
369 (* end hide *)
370
371 #[global]
372 Instance: Proper ((=) ==> (=)) rational_arctan.
373 Proof.
374 intros x1 x2 E.
375 rewrite <-2!arctan_Qarctan.
376 now rewrite E.
377 Qed.