Debian Codegraph @

reals/fast/CRAlternatingSum_alg.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.Q_in_CReals.
27 From Coq Require Import ArithRing.
28 Require Export CoRN.reals.fast.CRArith.
29 Require Import CoRN.reals.fast.CRIR.
30 Require Import CoRN.reals.fast.CRabs.
31 From Coq Require Import Bool.
32 Require Import CoRN.algebra.COrdAbs.
33 Require Import CoRN.model.ordfields.Qordfield.
34 Require Export CoRN.model.metric2.Qmetric.
35 Require Import CoRN.reals.fast.LazyNat.
36 Require Export CoRN.metric2.Limit.
37 Require Import CoRN.model.totalorder.QposMinMax.
38 From Coq Require Import Qpower.
39 From Coq Require Import Qabs.
40 Require Export MathClasses.theory.CoqStreams.
41 Require Import CoRN.transc.PowerSeries.
42 Require Import CoRN.tactics.CornTac.
43 Require Import CoRN.classes.Qclasses.
44 Require Import MathClasses.interfaces.abstract_algebra MathClasses.interfaces.orders MathClasses.theory.series MathClasses.theory.streams.
45 Require Import CoRN.reals.fast.CRAlternatingSum.
46
47 Opaque CR.
48
49 Local Open Scope Q_scope.
50
51 Lemma abs_power_neg_one : forall n:nat, Qabs ((-1)^n) == 1.
52 Proof.
53 induction n. reflexivity.
54 change (S n) with (1+n)%nat. rewrite Nat2Z.inj_add, Qpower_plus.
55 rewrite Qabs_Qmult, IHn. reflexivity.
56 intro abs. discriminate.
57 Qed.
58
59 Lemma Str_alt_decr_decr
60 : forall (X:Type) (f : X*Q->X*Q) x
61 (fdecr : Str_alt_decr X f x) (n : nat),
62 0 <= Str_pth _ f 1 x ->
63 (-1) ^ S n * Str_pth X f (Pos.of_nat (S (S n))) x
64 <= (-1) ^ n [*] Str_pth X f (Pos.of_nat (S n)) x.
65 Proof.
66 intros.
67 pose proof (Str_alt_decr_pos X f x fdecr).
68 specialize (fdecr (Pos.of_nat (S n))) as [fdecr _].
69 rewrite <- Qmult_1_l in fdecr.
70 rewrite <- (abs_power_neg_one (S n)) in fdecr.
71 rewrite <- (Qmult_1_l (Qabs (Str_pth X f (Pos.of_nat (S n)) x))) in fdecr.
72 rewrite <- (abs_power_neg_one n) in fdecr.
73 rewrite <- Qabs_Qmult, <- Qabs_Qmult in fdecr.
74 rewrite Qabs_pos, Qabs_pos in fdecr.
75 rewrite Nat2Pos.inj_succ. 2: discriminate.
76 exact fdecr. apply H0, H. apply H0, H.
77 Qed.
78
79 Lemma AltSeries_convergent_pos
80 : forall (X:Type) (f : X*Q->X*Q) x cvmod
81 (fdecr : Str_alt_decr X f x)
82 (flz : Limit_zero X f x cvmod),
83 0 <= Str_pth _ f 1 x ->
84 convergent (fun n:nat => inj_Q IR (Str_pth _ f (Pos.of_nat (S n)) x)).
85 Proof.
86 intros.
87 assert (forall n:nat, [--] [1] [^] n [=] (inj_Q IR ((-1)^n))) as power_neg_one.
88 { intro n.
89 rewrite inj_Q_power. apply nexp_wd.
90 rewrite (inj_Q_inv IR 1), inj_Q_One. reflexivity. }
91 apply (convergent_wd (fun n : nat => [--][1][^]n[*]([--][1][^]n[*]inj_Q IR (Str_pth _ f (Pos.of_nat (S n)) x)))).
92 - intro n.
93 rewrite power_neg_one.
94 rewrite <- inj_Q_mult, <- inj_Q_mult. apply inj_Q_wd.
95 rewrite Qmult_assoc. rewrite <- Qpower_plus.
96 replace (n+n)%Z with (2* Z.of_nat n)%Z.
97 rewrite Qpower_mult. replace ((-1)^2) with 1%Q by reflexivity.
98 rewrite Qpower_1, Qmult_1_l. reflexivity. ring.
99 intro abs. discriminate.
100 - apply alternate_series_conv.
101 + (* positivity *)
102 clear flz. intro n.
103 pose proof (Str_alt_decr_pos X f x fdecr n).
104 rewrite power_neg_one.
105 rewrite <- inj_Q_mult, <- inj_Q_Zero.
106 apply inj_Q_leEq, H0, H.
107 + (* f tends to zero. *)
108 intros e epos.
109 destruct (Q_dense_in_CReals IR e epos) as [q qpos qmaj].
110 apply (less_wdl IR [0] _ (inj_Q IR 0)) in qpos.
111 apply less_inj_Q in qpos.
112 specialize (flz (exist _ _ qpos)).
113 exists (Pos.to_nat (cvmod (exist _ _ qpos))). intros m H1.
114 apply (AbsSmall_wdr _ _ (inj_Q IR ((-1)^m * Str_pth X f (Pos.of_nat (S m)) x))).
115 2: rewrite inj_Q_mult, power_neg_one; rational.
116 apply (AbsSmall_trans _ (inj_Q IR q) _ _ qmaj).
117 apply inj_Q_AbsSmall.
118 apply AbsSmall_Qabs.
119 refine (Qle_trans _ _ _ _ flz). clear flz.
120 rewrite Qabs_pos. 2: apply (Str_alt_decr_pos X f x fdecr), H.
121 rewrite <- (Pos2Nat.id (cvmod (q ↾ qpos))).
122 pose proof (Pos2Nat.is_pos (cvmod (q ↾ qpos))).
123 destruct (Pos.to_nat (cvmod (q ↾ qpos))). exfalso; inversion H0.
124 clear H0.
125 rewrite <- (Qmult_1_l (Qabs (Str_pth X f (Pos.of_nat (S n)) x))).
126 rewrite <- (abs_power_neg_one n).
127 rewrite <- Qabs_Qmult, Qabs_pos.
128 2: apply (Str_alt_decr_pos X f x fdecr), H.
129 revert m n H1. induction m.
130 intros. exfalso; inversion H1.
131 intros. apply Nat.le_succ_r in H1. destruct H1.
132 specialize (IHm n H0).
133 apply (Qle_trans _ _ _ (Str_alt_decr_decr X f x fdecr m H) IHm).
134 inversion H0. subst n. apply Str_alt_decr_decr.
135 exact fdecr. exact H.
136 rewrite inj_Q_Zero. reflexivity.
137 + (* Decreasing *)
138 intro n. rewrite power_neg_one, power_neg_one.
139 rewrite <- inj_Q_mult, <- inj_Q_mult.
140 apply inj_Q_leEq.
141 apply Str_alt_decr_decr; assumption.
142 Qed.
143
144 Lemma AltSeries_convergent
145 : forall (X:Type) (f : X*Q->X*Q) x cvmod
146 (fdecr : Str_alt_decr X f x)
147 (flz : Limit_zero X f x cvmod),
148 convergent (fun n:nat => inj_Q IR (Str_pth _ f (Pos.of_nat (S n)) x)).
149 Proof.
150 (* Test whether the first term is positive or negative. *)
151 intros.
152 destruct (Qlt_le_dec (Str_pth _ f 1 x) 0).
153 2: exact (AltSeries_convergent_pos X f x cvmod fdecr flz q).
154 apply (convergent_wd
155 (fun n : nat => [--][1][*]inj_Q IR (Str_pth _ (CRstreams.CRstream_opp X f) (Pos.of_nat (S n))
156 (let (y,r):=x in (y,-r))))).
157 - (* the sequences are pointwise equal *)
158 intro n.
159 pose proof (CRstreams.CRstream_opp_pth X f x (Pos.of_nat (S n))).
160 unfold Str_pth.
161 destruct (CRstreams.iterate
162 _ (CRstreams.CRstream_opp X f)
163 (Pos.of_nat (S n)) (let (y, r) := x in (y, - r))),
164 (CRstreams.iterate (X and Q) f (Pos.of_nat (S n)) x).
165 unfold snd. destruct H as [_ H]. subst q0.
166 rewrite (inj_Q_inv IR q1), inv_mult_invol.
167 rewrite <- inj_Q_One, <- inj_Q_mult.
168 apply inj_Q_wd, Qmult_1_l.
169 - apply conv_series_mult_scal.
170 apply (AltSeries_convergent_pos X (CRstreams.CRstream_opp X f)
171 (let (y, r) := x in (y, - r)) cvmod).
172 apply CRstream_opp_decr, fdecr.
173 apply CRstream_opp_limit_zero, flz.
174 unfold CRstreams.CRstream_opp, Str_pth; simpl.
175 destruct x. unfold Str_pth in q; simpl in q.
176 replace (--q0) with q0.
177 destruct (f (x,q0)). unfold snd. unfold snd in q.
178 apply (Qopp_le_compat q1 0), Qlt_le_weak, q.
179 destruct q0. unfold Qopp; simpl.
180 rewrite Z.opp_involutive. reflexivity.
181 Qed.
182
183 Lemma AltSeries_convergent_0
184 : forall (X:Type) (f : X*Q->X*Q) x cvmod q
185 (fdecr : Str_alt_decr X f x)
186 (flz : Limit_zero X f x cvmod),
187 convergent (fun n:nat => match n with
188 | O => q
189 | S _ => inj_Q IR (Str_pth _ f (Pos.of_nat n) x) end).
190 Proof.
191 intros.
192 (* Get rid of the initial zero. *)
193 apply (join_series (fun n : nat => inj_Q IR (Str_pth _ f (Pos.of_nat (S n)) x))).
194 - exact (AltSeries_convergent X f x cvmod fdecr flz).
195 - exists 1%nat. exists O. intros n _.
196 rewrite Nat.add_comm. reflexivity.
197 Qed.
198
199 Lemma AltSeries_small_inf : forall (X : Type) (f : X * Q → X * Q)
200 (x : X * Q)
201 (cvmod : Qpos → positive)
202 (fdecr : Str_alt_decr X f x)
203 (flz : Limit_zero X f x cvmod)
204 (e : CRasCReals),
205 AbsSmall e (' snd (f x))%CR
206 -> AbsSmall e (AltSeries X f x cvmod fdecr flz)%CR.
207 Proof.
208 intros.
209 apply CRabs_AbsSmall.
210 apply CRabs_AbsSmall in H.
211 rewrite inject_Q_CR_abs in H.
212 refine (CRle_trans _ H).
213 clear H e. intro e. simpl.
214 unfold Cap_raw; simpl.
215 apply (Qle_trans _ 0%Q).
216 apply (Qopp_le_compat 0), Qpos_nonneg.
217 unfold Qminus. rewrite <- Qle_minus_iff.
218 generalize (Qpos_mult
219 (@exist Q (Qlt {| Qnum := Z0; Qden := xH |})
220 {| Qnum := Zpos xH; Qden := xO xH |}
221 (@eq_refl Datatypes.comparison Datatypes.Lt)) e).
222 clear e. intro e.
223 unfold SumStream.
224 pose proof (CRstreams.iterate_stop_correct
225 _
226 (λ y : X * Q * Q, let (z, r) := f (fst y) in (z, r, Qred (r + snd y)))
227 (λ y : X * Q * Q, Qle_bool (Qabs (snd (fst y))) (proj1_sig e))
228 (cvmod e) (x,0%Q)) as [s [seq [_ H4]]].
229 unfold zero, Q_0.
230 rewrite seq. clear seq.
231 rewrite SumStream_red.
232 apply (AltSeries_small X f x s).
233 exact fdecr.
234 Qed.
235
236 Lemma AltSeries_remainder : forall (X : Type) (f : X * Q → X * Q)
237 (x : X * Q)
238 (cvmod : Qpos → positive)
239 (fdecr : Str_alt_decr X f x)
240 (flz : Limit_zero X f x cvmod)
241 (e : CRasCReals) (p : positive),
242 AbsSmall e (' Str_pth X f p x)%CR
243 -> AbsSmall e (inject_Q_CR (snd
244 (CRstreams.iterate ((X and Q) and Q)
245 (λ y : (X and Q) and Q,
246 let (z0, r1) := f (fst y) in (z0, r1, Qred (r1 + snd y)))
247 p (x, 0%Q))) - AltSeries X f x cvmod fdecr flz)%CR.
248 Proof.
249 intros.
250 rewrite (AltSeries_shift_pth p).
251 rewrite CRopp_plus_distr, CRplus_assoc.
252 rewrite CRplus_opp.
253 apply (AbsSmall_minus CRasCOrdField e _ 0%CR).
254 unfold cg_minus. simpl.
255 rewrite CRopp_0, CRplus_0_r.
256 apply AltSeries_small_inf.
257 specialize (fdecr p) as [fdecr _].
258 unfold Str_pth in fdecr.
259 rewrite <- CRstreams.iterate_succ.
260 apply CRabs_AbsSmall.
261 rewrite inject_Q_CR_abs.
262 apply (@CRle_trans _ (inject_Q_CR (Qabs (snd (CRstreams.iterate (X and Q) f p x))))).
263 apply (order_embedding_preserving inject_Q_CR), fdecr.
264 rewrite <- inject_Q_CR_abs.
265 apply CRabs_AbsSmall.
266 apply H.
267 Qed.
268
269 Lemma AltSeries_correct : forall (X:Type) (f : X*Q->X*Q) x cvmod
270 (fdecr : Str_alt_decr X f x)
271 (flz : Limit_zero X f x cvmod)
272 (g:nat -> IR) (H : convergent g),
273 (forall n:positive, inj_Q IR (Str_pth _ f n x)%Q [=] g (Pos.to_nat n))
274 -> (IRasCR (g O) + AltSeries _ f x cvmod fdecr flz == IRasCR (series_sum g H))%CR.
275 Proof.
276 (* z equals to limit, means the sequence converges towards z. *)
277 intros.
278 unfold series_sum.
279 rewrite -> IR_Lim_as_CR.
280 apply (SeqLimit_unique CRasCReals).
281 (* then prove convergence. Apply the Cauchy proof as C at e/2 to get an index n. *)
282 intros e He.
283 generalize (IR_Cauchy_prop_as_CR (Build_CauchySeq IR (seq_part_sum g) H)).
284 intro C.
285 destruct (C _ (pos_div_two CRasCOrdField _ He)) as [n Hn].
286 exists (S (S n)).
287 (* prove that the partial sum of g until m >= 2+n minus the infinite sum of f
288 is less than e. It is equal to the remaining infinite sum of g after m. *)
289 intros m Hm.
290 unfold CS_seq in *.
291 clear C.
292 unfold seq_part_sum in *.
293 destruct m. exfalso; inversion Hm.
294 apply le_S_n in Hm.
295 (* Replace g by f. *)
296 assert (forall k:positive, le n (Pos.to_nat k)
297 -> AbsSmall e (inject_Q_CR (Str_pth _ f k x)))
298 as kSmall.
299 { intros.
300 stepr (IRasCR (g (Pos.to_nat k))).
301 setoid_replace (IRasCR (g (Pos.to_nat k)))
302 with (@Sum CRasCAbGroup (Pos.to_nat k) (Pos.to_nat k) (fun n => IRasCR (g n)))
303 by (rewrite Sum_one; reflexivity).
304 unfold Sum, Sum1.
305 rewrite <- IR_Sum0_as_CR, <- IR_Sum0_as_CR.
306 (* Triangle inequality with the sum until n. *)
307 stepr ((IRasCR (Sum0 (G:=IR) (S (Pos.to_nat k)) g) - (IRasCR (Sum0 (G:=IR) n g))) +
308 (IRasCR (Sum0 (G:=IR) n g) - IRasCR (Sum0 (G:=IR) (Pos.to_nat k) g)))%CR
309 by (unfold cg_minus; simpl; unfold msp_Equiv; ring).
310 apply (AbsSmall_eps_div_two CRasCOrdField e
311 (IRasCR (Sum0 (S (Pos.to_nat k)) g) - IRasCR (Sum0 n g))
312 (IRasCR (Sum0 n g) - IRasCR (Sum0 (Pos.to_nat k) g)))%CR.
313 apply (Hn (S (Pos.to_nat k))).
314 apply le_S, H1.
315 apply (AbsSmall_minus CRasCOrdField (e [/]TwoNZ)
316 (IRasCR (Sum0 (Pos.to_nat k) g)) (IRasCR (Sum0 n g))).
317 apply Hn.
318 exact H1.
319 rewrite <- IR_inj_Q_as_CR.
320 apply IRasCR_wd.
321 symmetry.
322 apply H0. }
323 stepr (IRasCR (Sum0 (S m) g) - IRasCR (g 0%nat) - AltSeries X f x cvmod fdecr flz)%CR
324 by (unfold cg_minus; simpl; unfold msp_Equiv; ring).
325 setoid_replace (IRasCR (Sum0 (S m) g) - IRasCR (g 0%nat))%CR
326 with (inject_Q_CR
327 (snd (CRstreams.iterate
328 _ (λ y : X * Q * Q, let (z0, r1) := f (fst y) in (z0, r1, Qred (r1 + snd y)))
329 (Pos.of_nat m) (x,0%Q)))).
330 - apply AltSeries_remainder.
331 apply kSmall.
332 rewrite Nat2Pos.id. apply (Nat.le_trans _ (S n)).
333 apply le_S, Nat.le_refl. exact Hm.
334 destruct m. inversion Hm. discriminate.
335 - clear kSmall.
336 replace (S m) with (S (Pos.to_nat (Pos.of_nat m))).
337 generalize (Pos.of_nat m).
338 clear Hm m.
339 apply Pos.peano_ind.
340 + rewrite SumStream_red.
341 rewrite CRstreams.iterate_one.
342 specialize (H0 xH).
343 unfold Str_pth, Pos.to_nat in H0. simpl in H0.
344 simpl.
345 destruct (f x).
346 simpl. simpl in H0.
347 rewrite <- IR_minus_as_CR, <- IR_inj_Q_as_CR.
348 apply IRasCR_wd.
349 rewrite cm_lft_unit, cag_commutes.
350 unfold cg_minus.
351 rewrite <- CSemiGroups.plus_assoc.
352 rewrite cg_rht_inv_unfolded, cm_rht_unit.
353 rewrite <- H0.
354 apply inj_Q_wd. rewrite Qplus_0_r. reflexivity.
355 + intros p IHp.
356 simpl (Sum0 (S (Pos.to_nat (Pos.succ p))) g).
357 rewrite IR_plus_as_CR.
358 rewrite (CRplus_comm (IRasCR (Sum0 (Pos.to_nat (Pos.succ p)) g))).
359 rewrite Pos2Nat.inj_succ.
360 rewrite <- CRplus_assoc, IHp. clear IHp.
361 rewrite SumStream_red.
362 rewrite SumStream_red.
363 rewrite CRstreams.iterate_succ.
364 rewrite SumStream_fst.
365 simpl.
366 rewrite <- CRstreams.iterate_succ.
367 specialize (H0 (Pos.succ p)).
368 unfold Str_pth in H0.
369 destruct (CRstreams.iterate (X and Q) f (Pos.succ p) x).
370 simpl.
371 simpl in H0.
372 rewrite Pos2Nat.inj_succ in H0.
373 rewrite <- CRplus_Qplus.
374 apply CRplus_eq_l.
375 rewrite <- IR_inj_Q_as_CR.
376 apply IRasCR_wd.
377 symmetry. exact H0.
378 + rewrite Nat2Pos.id. reflexivity.
379 destruct m. inversion Hm. discriminate.
380 Qed.
381