Debian Codegraph @

reals/fast/CRartanh_slow.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.iso_CReals.
26 Require Import CoRN.reals.fast.CRAlternatingSum.
27 Require Import CoRN.reals.fast.CRGeometricSum.
28 Require Import CoRN.reals.fast.CRstreams.
29 Require Export CoRN.reals.fast.CRArith.
30 Require Import CoRN.reals.fast.CRIR.
31 From Coq Require Import Qabs.
32 From Coq Require Import Qpower.
33 Require Import CoRN.model.ordfields.Qordfield.
34 Require Import CoRN.reals.Q_in_CReals.
35 Require Import CoRN.model.metric2.Qmetric.
36 Require Import CoRN.model.totalorder.QMinMax.
37 Require Import CoRN.transc.ArTanH.
38 Require Import CoRN.reals.fast.CRarctan_small.
39 Require Import CoRN.tactics.Qauto.
40 Require Import CoRN.tactics.CornTac.
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 (**
50 ** Area Tangens Hyperbolicus (artanh)
51 [artanh] is implemented by as the [GeometricSum] of it's taylor series.
52 The Taylor series of arctan is the alternation of arctanh's, so we cannot
53 use alternating series here.
54 *)
55
56 Definition artanhSequence (a:Q) : Stream Q
57 := mult_Streams (everyOther Qrecip_positives) (powers_help (a^2) a).
58
59 Lemma Str_nth_artanhSequence n :
60 forall a, (Str_nth n (artanhSequence a) == (1#P_of_succ_nat (2*n))*a^(1+2*n)%nat)%Q.
61 Proof.
62 intro a.
63 unfold artanhSequence.
64 unfold mult_Streams.
65 rewrite Str_nth_zipWith.
66 rewrite Str_nth_everyOther.
67 rewrite Str_nth_Qrecip_positives.
68 rewrite -> (Str_nth_powers_help_int_pow _ Z.of_nat).
69 rewrite <- Qpower_mult.
70 rewrite inj_plus.
71 rewrite -> (Qpower_plus' a 1 (2*n)%nat); auto with *.
72 rewrite inj_mult.
73 reflexivity.
74 Qed.
75
76 Lemma arctanSequence_Gs : forall a, GeometricSeries (a^2) (artanhSequence a).
77 Proof.
78 intros a.
79 apply mult_Streams_Gs.
80 apply _.
81 apply powers_help_Gs.
82 apply Qsqr_nonneg.
83 Qed.
84
85 Lemma Qsqr_lt_one : forall (a:Q), (-(1) < a) -> a < 1 -> (a^2 < 1).
86 Proof.
87 intros a H0 H1.
88 rewrite -> Qlt_minus_iff in *.
89 replace RHS with ((1 + - a)*(a + - -(1))) by simpl; ring.
90 Qauto_pos.
91 Qed.
92
93 Lemma artanh_DomArTanH : forall a, (a^2 < 1) -> DomArTanH (inj_Q IR a).
94 Proof.
95 intros a Ha.
96 split.
97 stepl (inj_Q IR (-(1))%Q).
98 apply inj_Q_less; simpl.
99 apply Qnot_le_lt.
100 intros H.
101 apply (Qlt_not_le _ _ Ha).
102 rewrite -> Qle_minus_iff in *.
103 replace RHS with ((- (1) + - a + 2)*(-(1) +- a)) by simpl; ring.
104 Qauto_nonneg.
105 stepr ([--](inj_Q IR 1)).
106 apply inj_Q_inv.
107 apply un_op_wd_unfolded.
108 rstepr (nring 1:IR).
109 apply (inj_Q_nring IR 1).
110 stepr (inj_Q IR (1)).
111 apply inj_Q_less; simpl.
112 apply Qnot_le_lt.
113 intros H.
114 apply (Qlt_not_le _ _ Ha).
115 rewrite -> Qle_minus_iff in *.
116 replace RHS with ((a + - (1) + 2)*(a +- (1))) by simpl; ring.
117 Qauto_nonneg.
118 rstepr (nring 1:IR).
119 apply (inj_Q_nring IR 1).
120 Qed.
121
122 (** Although this function works on the entire domain of [artanh], it is
123 only reasonably fast for values close to 0, say [[-(2/3), 2/3]]. *)
124 Definition rational_artanh_slow (a:Q) (p1: a^2 < 1) : CR :=
125 InfiniteGeometricSum (Qsqr_nonneg a) p1 (arctanSequence_Gs a).
126
127 Lemma GeometricSeries_convergent
128 : forall (a : Q) (apos : 0 <= a) (aone : a < 1) (series:Stream Q),
129 GeometricSeries a series ->
130 convergent (fun n => inj_Q IR (Str_nth n series)).
131 Proof.
132 intros a apos aone series H.
133 apply ratio_test_conv.
134 exists 0%nat.
135 exists (inj_Q IR a).
136 rstepr (nring 1:IR).
137 stepr (inj_Q IR (nring 1)); [| now apply (inj_Q_nring IR 1)].
138 apply inj_Q_less.
139 assumption.
140 assert (Ha0':[0][<=]inj_Q IR a).
141 rstepl (nring 0:IR).
142 stepl (inj_Q IR (nring 0)); [| now apply (inj_Q_nring IR 0)].
143 apply inj_Q_leEq.
144 assumption.
145 split.
146 assumption.
147 intros n _.
148 destruct (ForAll_Str_nth_tl n H) as [H0 _].
149 stepr (inj_Q IR a[*](inj_Q IR (Qabs (Str_nth n series)))); [| now
150 apply mult_wdr; apply eq_symmetric; apply AbsIR_Qabs].
151 stepl (inj_Q IR (Qabs (Str_nth (S n) series))); [| now apply eq_symmetric; apply AbsIR_Qabs].
152 rewrite <- inj_Q_mult.
153 apply inj_Q_leEq.
154 replace (S n) with (1+n)%nat by auto with *.
155 rewrite <- Str_nth_plus.
156 assumption.
157 Qed.
158
159 (* This is a horrendous proof. I'm sure half of it isn't needed, but I don't care to make it better
160 all proofs of this are extensionally equivalent anyway *)
161 Lemma InfiniteGeometricSum_correct
162 : forall (a : Q) (apos : 0 <= a) (aone : a < 1) (series:Stream Q) (x:nat -> IR),
163 (forall n:nat, inj_Q IR (Str_nth n series)%Q[=]x n) ->
164 forall (Gs:GeometricSeries a series) H,
165 (InfiniteGeometricSum apos aone Gs==IRasCR (series_sum x H))%CR.
166 Proof.
167 intros a apos aone seq x Hx Gs H.
168 unfold series_sum.
169 rewrite -> IR_Lim_as_CR.
170 apply (SeqLimit_unique CRasCReals).
171 intros e He.
172 generalize (IR_Cauchy_prop_as_CR (Build_CauchySeq IR (seq_part_sum x) H)).
173 intros C.
174 destruct (C _ (pos_div_two _ _ He)) as [n Hn].
175 exists n.
176 intros m Hm.
177 unfold CS_seq in *.
178 clear C.
179 unfold seq_part_sum in *.
180 setoid_replace (@cg_minus CRasCGroup (IRasCR (Sum0 m x)) (InfiniteGeometricSum apos aone Gs))
181 with (((IRasCR (Sum0 (G:=IR) m x) - (IRasCR (Sum0 (G:=IR) n x))) +
182 ((IRasCR (Sum0 (G:=IR) n x) - InfiniteGeometricSum apos aone Gs))))%CR
183 by (unfold cg_minus; simpl; ring).
184 apply (AbsSmall_eps_div_two CRasCOrdField
185 e (IRasCR (Sum0 m x) - IRasCR (Sum0 n x))
186 (IRasCR (Sum0 n x) - InfiniteGeometricSum apos aone Gs))%CR.
187 exact (Hn m Hm).
188 clear m Hm.
189 setoid_replace (IRasCR (Sum0 n x))
190 with ('(@Sum0 Q_as_CAbGroup n (fun n => (Str_nth n seq))%Q))%CR.
191 revert seq x H Hx Gs Hn.
192 induction n.
193 intros seq x H Hx Gs Hn.
194 simpl (Sum0 0 (fun n : nat => Str_nth n seq)).
195 apply (AbsSmall_minus CRasCOrdField (e [/]TwoNZ) (InfiniteGeometricSum apos aone Gs) 0%CR).
196 setoid_replace (@cg_minus CRasCOrdField (InfiniteGeometricSum apos aone Gs) 0%CR)
197 with (InfiniteGeometricSum apos aone Gs)
198 by (unfold cg_minus; simpl; ring).
199 assert (Hn' : forall m : nat, (0 <= m)%nat -> AbsSmall (R:=CRasCOrdField) (e [/]TwoNZ)
200 (IRasCR (Sum0 (G:=IR) m x))).
201 { intros m Hm.
202 setoid_replace (IRasCR (Sum0 m x))
203 with (@cg_minus CRasCOrdField (IRasCR (Sum0 (G:=IR) m x)) (IRasCR (Sum0 (G:=IR) 0 x))).
204 apply Hn; assumption.
205 unfold cg_minus.
206 simpl.
207 rewrite -> IR_Zero_as_CR.
208 ring. }
209 stepl (IRasCR (CRasIR (e[/]TwoNZ)))%CR; [| now apply CRasIRasCR_id].
210 stepr (IRasCR (CRasIR (InfiniteGeometricSum apos aone Gs)))%CR; [| now apply CRasIRasCR_id].
211 rewrite <- IR_AbsSmall_as_CR.
212 apply AbsSmall_approach.
213 intros d Hd.
214 rewrite -> IR_AbsSmall_as_CR.
215 stepr (InfiniteGeometricSum apos aone Gs); [| now apply eq_symmetric; apply CRasIRasCR_id].
216 destruct (Q_dense_in_CReals IR d) as [q Hq0 Hq].
217 assumption.
218 assert (Hq0': 0 < q).
219 apply (less_inj_Q IR).
220 stepl ([0]:IR).
221 assumption.
222 apply eq_symmetric; apply (inj_Q_nring IR 0).
223 destruct (InfiniteGeometricSum_small_tail apos aone (exist _ _ Hq0') Gs) as [m Hm].
224 setoid_replace (InfiniteGeometricSum apos aone Gs)
225 with ((IRasCR (Sum0 (G:=IR) m x)) + ((InfiniteGeometricSum apos aone Gs) - (IRasCR (Sum0 (G:=IR) m x))))%CR by ring.
226 stepl (IRasCR (CRasIR (e [/]TwoNZ)) + (IRasCR d))%CR; [| now apply eq_symmetric; apply IR_plus_as_CR].
227 apply (AbsSmall_plus CRasCOrdField (IRasCR (CRasIR (e [/]TwoNZ))) (IRasCR d)
228 (IRasCR (Sum0 m x))
229 (InfiniteGeometricSum apos aone Gs - IRasCR (Sum0 m x)))%CR.
230 stepl (e [/]TwoNZ); [| now apply eq_symmetric; apply CRasIRasCR_id].
231 apply Hn'; auto with *.
232 apply AbsSmall_leEq_trans with ('q)%CR.
233 stepl (IRasCR (inj_Q IR q)); [| now apply IR_inj_Q_as_CR].
234 rewrite <- IR_leEq_as_CR.
235 apply less_leEq.
236 assumption.
237 simpl in Hm.
238 clear - Hm Hx.
239 revert seq x Hx Gs Hm.
240 induction m.
241 intros seq x Hx Gs Hm.
242 stepr (InfiniteGeometricSum apos aone Gs).
243 apply Hm.
244 unfold cg_minus.
245 simpl.
246 rewrite -> IR_Zero_as_CR.
247 unfold msp_Equiv; ring.
248 intros seq x Hx Gs Hm.
249 setoid_replace (InfiniteGeometricSum apos aone Gs - IRasCR (Sum0 (S m) x))%CR
250 with (InfiniteGeometricSum apos aone (ForAll_Str_nth_tl 1 Gs) - IRasCR (Sum0 (G:=IR) m (fun n => (x (S n)))))%CR.
251 apply IHm.
252 intros n.
253 stepl ((inj_Q IR (Str_nth (S n) seq)%Q)).
254 apply Hx.
255 apply eq_reflexive.
256 intros.
257 apply Hm.
258 rewrite -> InfiniteGeometricSum_step.
259 setoid_replace (IRasCR (Sum0 (G:=IR) (S m) x))
260 with (IRasCR (inj_Q _ (CoqStreams.hd seq) [+](Sum0 (G:=IR) m (fun n0 : nat => (x (S n0)))%Q))).
261 rewrite -> (IR_plus_as_CR).
262 rewrite -> IR_inj_Q_as_CR.
263 ring.
264 apply IRasCR_wd.
265 apply eq_symmetric.
266 stepl (x O[+]Sum0 (G:=IR) m (fun n0 : nat => (x (S n0)))).
267 apply Sum0_shift.
268 intros i.
269 apply eq_reflexive.
270 apply bin_op_wd_unfolded.
271 apply eq_symmetric.
272 apply (Hx O).
273 apply eq_reflexive.
274 intros seq x H Hx Gs Hn.
275 set (y:=(fun n => (x (n + 1)%nat))).
276 setoid_replace (' Sum0 (S n) (fun n0 : nat => Str_nth n0 seq) -
277 InfiniteGeometricSum apos aone Gs)%CR
278 with (('(((Sum0 (G:=Q_as_CAbGroup) n (fun n0 : nat => Str_nth n0 (CoqStreams.tl seq))%Q)))%CR) - InfiniteGeometricSum apos aone (ForAll_Str_nth_tl 1 Gs))%CR.
279 apply (IHn (CoqStreams.tl seq) y ).
280 apply tail_series with x.
281 assumption.
282 exists 1%nat.
283 exists 0%nat.
284 intros; apply eq_reflexive.
285 intros m.
286 unfold y.
287 stepr ((inj_Q IR (Str_nth (m+1) seq))); [| now apply (Hx (m + 1)%nat)].
288 rewrite <- Str_nth_plus.
289 apply eq_reflexive.
290 intros m Hm.
291 setoid_replace (@cg_minus CRasCOrdField (IRasCR (Sum0 m y)) (IRasCR (Sum0 n y)))
292 with (IRasCR (Sum0 (G:=IR) (S m) x) - IRasCR (Sum0 (G:=IR) (S n) x))%CR.
293 apply (Hn (S m)).
294 apply le_n_S, Hm.
295 symmetry.
296 change (@cg_minus CRasCOrdField (IRasCR (Sum0 m y)) (IRasCR (Sum0 n y)))
297 with (IRasCR (Sum0 m y) - IRasCR (Sum0 n y))%CR.
298 do 2 rewrite <- IR_minus_as_CR.
299 apply IRasCR_wd.
300 stepr ((x O[+]Sum0 (G:=IR) m y[-](x O[+]Sum0 (G:=IR) n y))).
301 apply bin_op_wd_unfolded;[|apply un_op_wd_unfolded]; apply eq_symmetric; apply Sum0_shift;
302 intros; unfold y;rewrite Nat.add_comm; apply eq_reflexive.
303 rational.
304 rewrite -> InfiniteGeometricSum_step.
305 set (z:=(fun n0 : nat => (Str_nth n0 seq)%Q)).
306 setoid_replace ((Sum0 (G:=Q_as_CAbGroup) (S n) z):Q) with ((z O + (Sum0 (G:=Q_as_CAbGroup) n
307 (fun n0 : nat => (Str_nth n0 (CoqStreams.tl seq))%Q)))).
308 rewrite <- (CRplus_Qplus (z O)).
309 unfold z, Str_nth.
310 simpl.
311 ring.
312 symmetry.
313 apply (@Sum0_shift Q_as_CAbGroup).
314 intros i.
315 reflexivity.
316 clear - Hx.
317 induction n.
318 exact IR_Zero_as_CR.
319 simpl.
320 rewrite IR_plus_as_CR, IHn.
321 rewrite <- CRplus_Qplus.
322 apply CRplus_eq_r.
323 transitivity (IRasCR (inj_Q IR (Str_nth n seq)%Q)).
324 apply IRasCR_wd; symmetry; apply Hx.
325 apply IR_inj_Q_as_CR.
326 Qed.
327
328 Lemma InfiniteGeometricSum_correct'
329 : forall (series:Stream Q) (a : Q) (apos : 0 <= a) (aone : a < 1),
330 forall (Gs:GeometricSeries a series),
331 (InfiniteGeometricSum apos aone Gs
332 == IRasCR (series_sum _ (GeometricSeries_convergent apos aone Gs)))%CR.
333 Proof.
334 intros series a apos aone Gs.
335 apply InfiniteGeometricSum_correct.
336 intros; apply eq_reflexive.
337 Qed.
338
339 Lemma rational_artanh_slow_correct : forall (a:Q) Ha Ha0,
340 (@rational_artanh_slow a Ha == IRasCR (ArTanH (inj_Q IR a) Ha0))%CR.
341 Proof.
342 intros a Ha Ha0.
343 unfold rational_artanh_slow.
344 rewrite InfiniteGeometricSum_correct'.
345 apply IRasCR_wd.
346 eapply eq_transitive_unfolded;
347 [|apply (ArTanH_series (inj_Q IR a) (ArTanH_series_convergent_IR) (artanh_DomArTanH Ha) Ha0)].
348 simpl.
349 unfold series_sum.
350 apply Lim_seq_eq_Lim_subseq with Nat.double.
351 unfold Nat.double; auto with *.
352 intros n.
353 exists (S n).
354 unfold Nat.double; auto with *.
355 intros n.
356 simpl.
357 clear - n.
358 induction n.
359 apply eq_reflexive.
360 simpl.
361 set (A:=nexp IR (Nat.add n (S n)) (inj_Q IR a[-][0])).
362 rewrite Nat.add_comm.
363 simpl.
364 fold (Nat.double n).
365 csetoid_rewrite_rev IHn.
366 clear IHn.
367 csetoid_replace (ArTanH_series_coef (Nat.double n)[*]nexp IR (Nat.double n) (inj_Q IR a[-][0])) ([0]:IR).
368 csetoid_replace (ArTanH_series_coef (S (Nat.double n))[*]A)
369 (inj_Q IR (Str_nth n (artanhSequence a))).
370 rational.
371 unfold ArTanH_series_coef.
372 case_eq (CLogic.Even_Odd_dec (S (Nat.double n))); intros H.
373 elim (Nat.Even_Odd_False _ H).
374 now rewrite <-Nat.add_1_r, Nat.double_twice; exists n.
375 intros _.
376 eapply eq_transitive;
377 [|apply inj_Q_wd; simpl;symmetry;apply Str_nth_artanhSequence].
378 eapply eq_transitive;
379 [|apply eq_symmetric; apply inj_Q_mult].
380 apply mult_wd.
381 assert (X:(inj_Q IR (nring (S (Nat.double n))))[#][0]).
382 stepr (inj_Q IR [0]).
383 apply inj_Q_ap.
384 apply nringS_ap_zero.
385 apply (inj_Q_nring IR 0).
386 stepr (inj_Q IR (nring 1)[/]_[//]X).
387 apply div_wd.
388 rstepl (nring 1:IR).
389 apply eq_symmetric.
390 apply (inj_Q_nring IR 1).
391 apply eq_symmetric.
392 apply (inj_Q_nring).
393 assert (X0:inj_Q IR (inject_Z (P_of_succ_nat (2 * n)))[#][0]).
394 stepr (inj_Q IR [0]).
395 apply inj_Q_ap.
396 discriminate.
397 apply (inj_Q_nring IR 0).
398 eapply eq_transitive;
399 [|apply inj_Q_wd; symmetry; apply Qmake_Qdiv].
400 eapply eq_transitive;
401 [|apply eq_symmetric; apply (fun b => inj_Q_div _ b _ X0)].
402 apply div_wd.
403 apply eq_reflexive.
404 apply inj_Q_wd.
405 rewrite <- POS_anti_convert.
406 eapply eq_transitive;[apply nring_Q|].
407 unfold Nat.double.
408 simpl.
409 replace (n+0)%nat with n by ring.
410 reflexivity.
411 unfold A; clear A.
412 eapply eq_transitive;[|apply eq_symmetric; apply inj_Q_power].
413 change ((inj_Q IR a[-][0])[^](n+S n)[=]inj_Q IR a[^](1 + 2 * n)).
414 replace (n + S n)%nat with (1 + 2*n)%nat by ring.
415 apply nexp_wd.
416 rational.
417 unfold ArTanH_series_coef.
418 case_eq (CLogic.Even_Odd_dec (Nat.double n)).
419 intros _ _.
420 rational.
421 intros o.
422 elim (fun x=> Nat.Even_Odd_False _ x o).
423 apply even_plus_n_n.
424 Qed.
425
426 (* This development is incomplete. At the moment only what is needed
427 for logorithm has been developed. *)