Debian Codegraph @

reals/fast/CRarctan_small.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 Import CoRN.reals.fast.CRAlternatingSum.
26 Require Import CoRN.reals.fast.CRAlternatingSum_alg.
27 Require Import CoRN.reals.fast.CRstreams.
28 Require Import CoRN.reals.fast.CRexp.
29 Require Export CoRN.reals.fast.CRArith.
30 Require Import CoRN.reals.fast.CRIR.
31 From Coq Require Import Qpower Qabs Qround.
32 Require Import CoRN.model.ordfields.Qordfield.
33 Require Import CoRN.reals.Q_in_CReals.
34 Require Import CoRN.model.metric2.Qmetric.
35 Require Import CoRN.model.totalorder.QMinMax.
36 Require Import CoRN.model.totalorder.QposMinMax.
37 Require Import CoRN.transc.MoreArcTan.
38 Require Import CoRN.tactics.CornTac.
39 Require Import MathClasses.interfaces.abstract_algebra.
40 Require Import CoRN.stdlib_omissions.Q.
41 Require Import Coq.Init.Datatypes.
42
43 Set Implicit Arguments.
44
45 Local Open Scope Q_scope.
46 Local Open Scope uc_scope.
47
48 Opaque inj_Q CR.
49
50 Lemma Qmult_pos_neg : forall (a b : Q),
51 0 <= a -> b <= 0 -> a*b <= 0.
52 Proof.
53 intros. rewrite Qmult_comm.
54 rewrite <- (Qmult_0_l a).
55 apply Qmult_le_compat_r; assumption.
56 Qed.
57
58 Lemma Qmult_opp_1 : forall q : Q,
59 eq (-q) (-1 * q).
60 Proof.
61 reflexivity.
62 Qed.
63
64 (**
65 ** Arctangent (small)
66 For values between in [[-1,1]], arctangent is computed by it's alternating
67 taylor series.
68 *)
69 Section ArcTanSeries.
70 Variable a:Q.
71
72 (* (1,a) -> (3, -a^3/3) -> ...
73 With a bigger state type, 1/(2i+1) could be set directly. It will be
74 done in faster reals with a stream of positive*AQ*AQ. *)
75 Definition arctanStream (px : prod positive Q) : prod positive Q
76 := let d := Pos.add 2 (fst px) in
77 (d, Qred (- snd px * a * a * (fst px#d))).
78
79 Lemma arctanStream_fst : forall p,
80 fst (iterate _ arctanStream p (1%positive, a)) ≡ Pos.succ (2*p).
81 Proof.
82 apply Pos.peano_ind.
83 - reflexivity.
84 - intros p H. rewrite iterate_succ.
85 destruct (iterate (positive and Q) arctanStream p (1%positive, a)).
86 simpl in H. subst p0.
87 transitivity (Pos.add 2 (p~1)). reflexivity.
88 clear q a. rewrite Pos.mul_succ_r.
89 rewrite <- Pos.add_1_l, (Pos.add_comm 1).
90 rewrite <- Pos.add_assoc. apply f_equal. reflexivity.
91 Qed.
92
93 Lemma Str_pth_arctanStream : forall p,
94 Str_pth _ arctanStream p (xH, a)
95 == (1#(1+2*p)) * ((-1)^p*a^(1+2*p))%Q.
96 Proof.
97 apply Pos.peano_ind.
98 - unfold arctanStream, Str_pth, iterate, snd.
99 rewrite Qred_correct. simpl.
100 rewrite (Qmult_comm (1#3)), Qmult_assoc, Qmult_assoc.
101 reflexivity.
102 - intros p pInd. unfold Str_pth.
103 rewrite iterate_succ. unfold Str_pth in pInd.
104 pose proof (arctanStream_fst p) as H0.
105 destruct (iterate _ arctanStream p (1%positive, a)) as [p0 q].
106 simpl in H0. subst p0. unfold snd in pInd.
107 unfold arctanStream, snd, fst.
108 rewrite Qred_correct. rewrite pInd. clear pInd q.
109 (* Get rid of (-1)^p *)
110 rewrite <- (Qmult_comm ((-1) ^ Pos.succ p * a ^ (1 + 2 * Pos.succ p))).
111 rewrite <- (Pos.add_1_l p).
112 rewrite Pos2Z.inj_add, (Qpower_plus (-1)%Q).
113 simpl ((-1)^1).
114 rewrite Qmult_opp_1.
115 do 5 rewrite <- (Qmult_assoc (-1)).
116 apply (Qmult_comp (-1)). reflexivity.
117 rewrite (Qmult_comm (1 # (1 + 2 * p))).
118 do 5 rewrite <- (Qmult_assoc ((-1)^p)).
119 apply (Qmult_comp ((-1)^p)). reflexivity.
120 (* Get rid of a *)
121 setoid_replace (a ^ (1 + 2 * (1 + p))) with (a ^ (1 + 2 * p) * (a * a)).
122 do 4 rewrite <- (Qmult_assoc (a ^ (1 + 2 * p))).
123 apply Qmult_comp. reflexivity.
124 rewrite <- (Qmult_assoc _ a a).
125 rewrite (Qmult_comm (1 # (1 + 2 * p))).
126 rewrite <- (Qmult_assoc (a*a)).
127 apply Qmult_comp. reflexivity.
128 (* Finish equalities *)
129 unfold Qeq, Qmult, Qnum, Qden.
130 rewrite Z.mul_1_l, Z.mul_1_l.
131 reflexivity.
132 rewrite <- (Qpower_plus_positive a 1 1).
133 rewrite <- (Qpower_plus_positive a (1+2*p)).
134 apply Qpower_positive_comp. reflexivity.
135 rewrite <- Pos.add_assoc.
136 apply f_equal. rewrite (Pos.add_comm 1 p).
137 reflexivity.
138 intro abs. discriminate.
139 Qed.
140
141 Hypothesis Ha: (-1 <= a <= 1).
142
143 Lemma arctanStream_alt : Str_alt_decr _ arctanStream (1%positive,a).
144 Proof.
145 split.
146 - (* Replace a by Qabs a *)
147 rewrite Str_pth_arctanStream, Str_pth_arctanStream.
148 rewrite Qabs_Qmult, Qabs_Qmult, Qabs_Qmult, Qabs_Qmult.
149 rewrite Qabs_Qpower, Qabs_Qpower.
150 change (Qabs (-1)) with 1.
151 rewrite Qpower_1, Qpower_1, Qmult_1_l, Qmult_1_l.
152 rewrite (Qabs_Qpower a (1+2*Pos.succ p)), (Qabs_Qpower a (1+2*p)).
153 (* Finish inequality *)
154 setoid_replace (Qabs a ^ (1 + 2 * Pos.succ p)%positive)
155 with (Qabs a * Qabs a * Qabs a ^ (1 + 2 * p)%positive).
156 rewrite Qmult_assoc.
157 apply Qmult_le_compat_r.
158 2: rewrite <- Qabs_Qpower; apply Qabs_nonneg.
159 + rewrite Qmult_comm.
160 apply (Qabs_Qle_condition a 1) in Ha.
161 apply (Qle_trans _ (1* (1 # (1 + 2 * (Pos.succ p))))).
162 apply Qmult_le_compat_r. 2: discriminate.
163 apply (Qle_trans _ (1*Qabs a)).
164 apply Qmult_le_compat_r. exact Ha.
165 apply Qabs_nonneg. rewrite Qmult_1_l. exact Ha.
166 rewrite Qmult_1_l. unfold Qabs, Z.abs.
167 unfold Qle, Qnum, Qden.
168 rewrite Z.mul_1_l, Z.mul_1_l.
169 change (p <= Pos.succ p)%positive.
170 apply Pos.lt_le_incl, Pos.lt_succ_r, Pos.le_refl.
171 + replace (1 + 2 * Pos.succ p)%positive with (2 + (1 + 2 * p))%positive.
172 generalize (1 + 2 * p)%positive. clear p. intro p.
173 unfold Qpower.
174 rewrite Qpower_plus_positive. reflexivity.
175 rewrite Pos.add_comm, <- Pos.add_assoc. apply f_equal.
176 rewrite <- Pos.add_1_l.
177 rewrite Pos.mul_add_distr_l, Pos.mul_1_r.
178 apply Pos.add_comm.
179 - rewrite Str_pth_arctanStream, Str_pth_arctanStream.
180 rewrite Qmult_comm, <- Qmult_assoc. apply Qmult_pos_neg.
181 discriminate. rewrite Qmult_comm, <- Qmult_assoc.
182 apply Qmult_pos_neg. discriminate.
183 rewrite <- Pos.add_1_l.
184 change ((-1) ^ (1 + p)%positive) with (Qpower_positive (-1) (1 + p)).
185 rewrite Qpower_plus_positive. simpl (Qpower_positive (-1) 1).
186 rewrite <- Qmult_assoc, <- Qmult_assoc.
187 apply (Qopp_le_compat 0).
188 rewrite (Qmult_comm (a ^ (1 + 2 * (1 + p)%positive))).
189 rewrite Qmult_assoc, Qmult_assoc.
190 rewrite <- Qmult_assoc.
191 apply Qmult_le_0_compat.
192 simpl.
193 destruct (Qpower_positive (-1) p), Qnum; discriminate.
194 setoid_replace (a ^ (1 + 2 * (1 + p))) with (a ^ (1 + 2 * p) * (a * a)).
195 rewrite Qmult_assoc.
196 apply Qmult_le_0_compat.
197 destruct (a ^ (1 + 2 * p)), Qnum; discriminate.
198 destruct a, Qnum; discriminate.
199 change (a*a) with (Qpower_positive a 2).
200 rewrite <- (Qpower_plus_positive a (1+2*p)).
201 change (a ^ (1 + 2 * (1 + p))) with (Qpower_positive a (1 + 2 * (1 + p))).
202 replace (1 + 2 * (1 + p))%positive with (1 + 2 * p + 2)%positive.
203 reflexivity.
204 rewrite <- Pos.add_assoc. apply f_equal.
205 rewrite Pos.mul_add_distr_l, Pos.mul_1_r.
206 apply Pos.add_comm.
207 Qed.
208
209 Lemma arctanStream_zl
210 : Limit_zero _ arctanStream (xH,a)
211 (fun e:Qpos => Z.to_pos (Qceiling (/ (proj1_sig e)))).
212 Proof.
213 intros [e epos]. rewrite Str_pth_arctanStream, Qabs_Qmult, Qabs_Qmult.
214 rewrite Qabs_Qpower. change (Qabs (-1)) with 1.
215 rewrite Qpower_1, Qmult_1_l.
216 rewrite Qmult_comm.
217 apply (Qle_trans _ (1 * Qabs (1 # 1 + 2 * Z.to_pos (Qceiling (/ ` (e ↾ epos)))))).
218 apply Qmult_le_compat_r. 2: apply Qabs_nonneg.
219 - rewrite (Qabs_Qpower a (1 + 2 * Z.to_pos (Qceiling (/ ` (e ↾ epos))))).
220 apply Qpower_le_1. split.
221 apply Qabs_nonneg.
222 apply Qabs_Qle_condition, Ha.
223 - clear Ha a.
224 rewrite Qmult_1_l. unfold Qabs, Z.abs, proj1_sig.
225 rewrite <- (Qinv_involutive e) at 2.
226 assert (0 < /e) as H.
227 { apply Qinv_lt_0_compat, epos. }
228 apply (@Qinv_le_compat (/e) (Zpos (1 + 2 * Z.to_pos (Qceiling (/ e))) # 1)).
229 exact H.
230 apply (Qle_trans _ _ _ (Qle_ceiling (/e))).
231 generalize (Qceiling (/ e)).
232 clear H epos e. intros [|p|p].
233 discriminate. 2: discriminate.
234 pose proof (Zle_Qle p (Z.pos (1 + 2 * Z.to_pos p))).
235 unfold inject_Z.
236 unfold inject_Z in H.
237 rewrite <- H. clear H.
238 change (p <= 1 + 2*p)%positive.
239 rewrite <- Pplus_one_succ_l.
240 apply Pos.lt_le_incl, Pos.lt_succ_r.
241 apply (Pos.mul_le_mono_r p 1 2). discriminate.
242 Qed.
243
244 End ArcTanSeries.
245
246 Definition rational_arctan_small (a:Q) (p: -1 <= a <= 1) : CR :=
247 (inject_Q_CR a + AltSeries _ (arctanStream a) (xH,a) _
248 (arctanStream_alt p) (arctanStream_zl p))%CR.
249
250 Lemma rational_arctan_small_wd : forall (a1 a2 : Q) (p1 : -1 <= a1 <= 1) (p2 : -1 <= a2 <= 1),
251 a1 = a2 → rational_arctan_small p1 = rational_arctan_small p2.
252 Proof.
253 intros. unfold rational_arctan_small.
254 apply ucFun2_wd. rewrite H. reflexivity.
255 apply AltSeries_wd.
256 2: reflexivity. intro p.
257 rewrite Str_pth_arctanStream, Str_pth_arctanStream, H. reflexivity.
258 Qed.
259
260 Lemma widen_interval : forall a:Q, -1 < a < 1 -> -1 <= a <= 1.
261 Proof.
262 intros a [H H0]. split; apply Qlt_le_weak; assumption.
263 Qed.
264
265 Lemma rational_arctan_small_correct : forall (a:Q) (Ha : -1 < a < 1),
266 (@rational_arctan_small a (widen_interval Ha) == IRasCR (ArcTan (inj_Q IR a)))%CR.
267 Proof.
268 intros a Ha.
269 unfold rational_arctan_small.
270 rewrite <- (IR_inj_Q_as_CR a).
271 rewrite
272 (AltSeries_correct
273 _ _ _ _ (arctanStream_alt (widen_interval Ha))
274 (arctanStream_zl (widen_interval Ha))
275 _ (AltSeries_convergent_0 _ _ _ _ (inj_Q IR a)
276 (arctanStream_alt (widen_interval Ha)) (arctanStream_zl (widen_interval Ha)))).
277 - apply IRasCR_wd.
278 assert (olor ([--][1]) [1] (inj_Q IR a)) as X.
279 { split.
280 stepl (inj_Q IR (-1)). apply inj_Q_less, Ha.
281 rewrite (inj_Q_inv IR 1), inj_Q_One. reflexivity.
282 stepr (inj_Q IR 1); [| now apply inj_Q_One].
283 apply inj_Q_less, Ha. }
284 eapply eq_transitive_unfolded;
285 [|apply (arctan_series (inj_Q IR a) (arctan_series_convergent_IR) X)].
286 apply series_sum_wd.
287 intros n.
288 transitivity (inj_Q IR (((-1)^n)%Q *(a^(1+2*Z.of_nat n) * (1#(Pos.of_nat (1+2*n)))))).
289 + destruct n. apply inj_Q_wd. simpl.
290 rewrite Qmult_1_l, Qmult_1_r. reflexivity.
291 apply inj_Q_wd.
292 rewrite Str_pth_arctanStream.
293 rewrite (Qmult_assoc ((-1)^S n)).
294 rewrite (Qmult_comm ((-1) ^ S n * a ^ (1 + 2 * S n))). apply Qmult_comp.
295 unfold Qeq, Qnum, Qden.
296 rewrite Z.mul_1_l, Z.mul_1_l.
297 change 2%positive with (Pos.of_nat 2).
298 rewrite <- (Nat2Pos.inj_mul 2 (S n)).
299 2: discriminate. 2: discriminate.
300 rewrite <- (Nat2Pos.inj_add 1). reflexivity.
301 discriminate. discriminate.
302 apply Qmult_comp.
303 rewrite <- Pos.of_nat_succ, POS_anti_convert.
304 reflexivity.
305 replace (1 + 2 * Z.pos (Pos.of_nat (S n)))%Z with (1 + 2 * S n)%Z.
306 reflexivity.
307 rewrite <- Pos.of_nat_succ, POS_anti_convert.
308 reflexivity.
309 + transitivity (([--][1][^]n[/]nring (R:=IR) (S (2 * n))[//]nringS_ap_zero IR (2 * n))[*]
310 (inj_Q IR a)[^](2 * n + 1)).
311 2: reflexivity.
312 rstepr (([--][1][^]n)[*]((inj_Q IR a)[^](2*n+1)[/]nring (R:=IR) (S (2 * n))[//]nringS_ap_zero IR (2 * n))).
313 rewrite inj_Q_mult.
314 apply mult_wd.
315 rewrite inj_Q_power.
316 apply nexp_wd.
317 rewrite (inj_Q_inv IR 1), inj_Q_One.
318 reflexivity.
319 apply mult_cancel_lft with (nring (R:=IR) (S (2 * n))).
320 apply nringS_ap_zero.
321 rstepr (inj_Q IR a[^](2 * n + 1)).
322 stepr (inj_Q IR (a^(2*n+1)%nat)); [| now apply inj_Q_power].
323 stepl ((inj_Q IR (nring (S (2*n))))[*]inj_Q IR (a ^ (1 + 2 * n) * (1 # Pos.of_nat (1 + 2 * n))));
324 [| now apply mult_wdl; apply inj_Q_nring].
325 rewrite <- inj_Q_mult.
326 apply inj_Q_wd.
327 setoid_rewrite (nring_Q (S (2*n))).
328 change (S (2 * n) * (a ^ (1 + 2 * n) * (1 # Pos.of_nat (1 + 2 * n)))
329 == a ^ (2 * n + 1)%nat)%Q.
330 rewrite Qmult_comm.
331 rewrite <- Qmult_assoc.
332 setoid_replace ((1 # Pos.of_nat (1 + 2 * n)) * S (2 * n)) with 1%Q.
333 rewrite Qmult_1_r, Nat.add_comm.
334 rewrite Nat2Z.inj_add, Nat2Z.inj_mul. reflexivity.
335 unfold Qeq, inject_Z, Qmult, Qnum, Qden.
336 rewrite Z.mul_1_l, Z.mul_1_l, Z.mul_1_r, Pos.mul_1_r.
337 unfold Z.of_nat.
338 rewrite Pos.of_nat_succ. reflexivity.
339 - intro p. destruct (Pos.to_nat p) eqn:des.
340 exfalso. pose proof (Pos2Nat.is_pos p). rewrite des in H.
341 inversion H.
342 apply inj_Q_wd.
343 rewrite <- des, Pos2Nat.id. reflexivity.
344 Qed.