Debian Codegraph @

reals/fast/CRGeometricSum.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 From Coq Require Import ZArith.
22 Require Import CoRN.metric2.Metric.
23 Require Import CoRN.metric2.UniformContinuity.
24 Require Import CoRN.reals.fast.CRAlternatingSum.
25 Require Import CoRN.reals.fast.CRstreams.
26 Require Import CoRN.model.totalorder.QposMinMax.
27 Require Import CoRN.model.totalorder.QMinMax.
28 From Coq Require Import Qpower.
29 From Coq Require Import Qabs.
30 From Coq Require Import Zdiv.
31
32 Set Implicit Arguments.
33
34 Opaque Qabs.
35
36 Local Open Scope Q_scope.
37
38 Import MathClasses.theory.CoqStreams.
39
40 (** [InfiniteSum] approximates the limit of the series s within err_prop. *)
41 (* This Fixpoint is fat because the fuel is a unary nat,
42 which can waste a lot of memory in normal form inside vm_compute. *)
43 Fixpoint InfiniteSum_fat (filter:Stream Q -> bool) (s:Stream Q) (q : Q) (fuel:nat) : Q
44 := if filter s
45 then q
46 else match fuel with
47 | O => q
48 | S p => InfiniteSum_fat filter (tl s) (Qplus' q (hd s)) p
49 end.
50
51 Definition InfiniteSum_raw_F (cont: Stream Q -> Q -> Q)
52 (err_prop:Stream Q -> bool) (s:Stream Q) (q : Q) : Q :=
53 if (err_prop s)
54 then q (* the error is small enough, stop the sum *)
55 else cont (tl s) (Qplus' q (hd s)). (* continue the calculations *)
56
57 (** Sum a rational stream up to the first index at which the filter
58 Stream Q -> bool equals true, or 2^n.
59 n is intended as a termination proof (fuel). It is otherwise useless
60 for the calculations and we want it as small as possible in memory,
61 because vm_compute will start by computing its normal form.
62 By choosing 2^n we make the fuel logarithmic in the actual number of iterations.
63 cont is a continuation that holds the rest of the computations
64 to do in the recursion, it starts with fun _ q => q.
65 This has the same calculation speed as InfiniteSum_fat, and
66 should take less memory. *)
67 Fixpoint InfiniteSum_raw_N (n:nat) (filter: Stream Q -> bool)
68 (cont: Stream Q -> Q -> Q) {struct n}
69 : Stream Q -> Q -> Q :=
70 match n with
71 | O => InfiniteSum_raw_F cont filter
72 | S p => InfiniteSum_raw_N p filter (fun s => InfiniteSum_raw_N p filter cont s)
73 end.
74
75 (*
76 Remark : the eta expension here is important, else the virtual machine will
77 compute the value of (InfiniteGeometricSum_raw_N n') before
78 reducing the call of InfiniteGeometricSum_raw_F.*)
79
80 (* Get an idea of how the recursion goes. The continuation will
81 unfold n layers deep, before being folded by additions. *)
82 Lemma InfiniteSum_raw_N_unfold : forall n cont (filter : Stream Q -> bool) s,
83 InfiniteSum_raw_N (S (S n)) filter cont s
84 = InfiniteSum_raw_N
85 n filter (fun s0 => InfiniteSum_raw_N
86 n filter (fun s1 => InfiniteSum_raw_N
87 (S n) filter cont s1) s0) s.
88 Proof.
89 reflexivity.
90 Qed.
91
92 Lemma InfiniteSum_fat_plus
93 : forall (fuel:nat) (filter:Stream Q -> bool) (s:Stream Q) (q : Q),
94 InfiniteSum_fat filter s q fuel == q + InfiniteSum_fat filter s 0 fuel.
95 Proof.
96 induction fuel.
97 - intros. simpl. destruct (filter s); rewrite Qplus_0_r; reflexivity.
98 - intros. simpl. destruct (filter s). symmetry. apply Qplus_0_r.
99 rewrite IHfuel.
100 rewrite (IHfuel filter (tl s) (Qplus' 0 (hd s))).
101 rewrite Qplus_assoc. apply Qplus_comp. 2: reflexivity.
102 rewrite Qplus'_correct, Qplus'_correct, Qplus_0_l. reflexivity.
103 Qed.
104
105 Lemma InfiniteSum_fat_remove_filter
106 : forall (fuel:nat) (filter:Stream Q -> bool) (s:Stream Q) (q : Q),
107 filter (Str_nth_tl fuel s) = true
108 -> exists n:nat,
109 InfiniteSum_fat filter s q fuel
110 = InfiniteSum_fat (fun _ => false) s q n
111 /\ (forall p:nat, lt p n -> filter (Str_nth_tl p s) = false)
112 /\ filter (Str_nth_tl n s) = true.
113 Proof.
114 induction fuel.
115 - intros. exists O.
116 split. 2: split. simpl. destruct (filter s); reflexivity.
117 intros. exfalso; inversion H0. exact H.
118 - intros. destruct (filter s) eqn:des.
119 + exists O. split. 2: split. simpl. rewrite des. reflexivity.
120 intros. exfalso; inversion H0. exact des.
121 + specialize (IHfuel filter (tl s) (Qplus' q (hd s)) H) as [n [H1 H2]].
122 exists (S n). split. 2: split.
123 simpl. rewrite des. rewrite H1. reflexivity.
124 intros. destruct p. exact des.
125 simpl. apply H2. apply le_S_n in H0. exact H0.
126 apply H2.
127 Qed.
128
129 Lemma InfiniteSum_fat_add_stop
130 : forall (p n : nat) (s : Stream Q) (filter : Stream Q -> bool) (q : Q),
131 le n p
132 -> filter (Str_nth_tl n s) = true
133 -> InfiniteSum_fat filter s q p
134 = InfiniteSum_fat filter s q n.
135 Proof.
136 induction p.
137 - intros n s filter q H H0.
138 inversion H. reflexivity.
139 - intros n s filter q H H0.
140 destruct n.
141 + simpl in H0. simpl. rewrite H0. reflexivity.
142 + specialize (IHp n (tl s) filter).
143 simpl.
144 destruct (filter s) eqn:des. reflexivity.
145 rewrite IHp. reflexivity. apply le_S_n, H. exact H0.
146 Qed.
147
148 Lemma InfiniteSum_fat_extend
149 : forall (n : nat) (s : Stream Q) (filter : Stream Q -> bool) (q : Q),
150 filter (Str_nth_tl n s) = true
151 -> InfiniteSum_fat filter s q n
152 = InfiniteSum_fat filter s q (S n).
153 Proof.
154 intros. symmetry. apply InfiniteSum_fat_add_stop.
155 apply le_S, Nat.le_refl. exact H.
156 Qed.
157
158 Lemma InfiniteSum_fat_add_pass
159 : forall (n p : nat) (s : Stream Q) (filter : Stream Q -> bool) (q : Q),
160 (forall k:nat, lt k n -> filter (Str_nth_tl k s) = false)
161 -> InfiniteSum_fat filter s q (n+p)
162 = InfiniteSum_fat
163 filter (Str_nth_tl n s) (InfiniteSum_fat filter s q n) p.
164 Proof.
165 induction n.
166 - intros. simpl.
167 destruct (filter s); reflexivity.
168 - intros.
169 pose proof (H O (le_n_S 0 n (Nat.le_0_l _))) as zeroFalse.
170 simpl in zeroFalse.
171 simpl. rewrite zeroFalse.
172 rewrite IHn. reflexivity.
173 intros k H0. destruct n. exfalso; inversion H0.
174 apply Nat.le_succ_r in H0. destruct H0.
175 apply (H (S k)), le_n_S, le_S, H0.
176 inversion H0. subst k.
177 apply (H (S n) (Nat.le_refl _)).
178 Qed.
179
180 Lemma decide_filter_before_n
181 : forall (n : nat) (filter : Stream Q -> bool) (s : Stream Q),
182 (exists p:nat, lt p n /\ filter (Str_nth_tl p s) = true)
183 \/ (forall p:nat, lt p n -> filter (Str_nth_tl p s) = false).
184 Proof.
185 induction n.
186 - intros. right.
187 intros. exfalso. inversion H.
188 - intros. destruct (filter (Str_nth_tl n s)) eqn:des.
189 left. exists n. split. apply Nat.le_refl. exact des.
190 destruct (IHn filter s).
191 + left. destruct H as [p [H H0]]. exists p.
192 split. apply le_S, H. exact H0.
193 + right. intros.
194 apply Nat.le_succ_r in H0. destruct H0.
195 apply H, H0. inversion H0. subst p. exact des.
196 Qed.
197
198 Lemma InfiniteSum_raw_N_step
199 : forall (fuel : nat) c (filter : Stream Q -> bool) (s : Stream Q) (q : Q),
200 (forall p:nat, p < 2 ^ fuel -> filter (Str_nth_tl p s) = false)%nat
201 -> InfiniteSum_raw_N fuel filter c s q
202 = c (Str_nth_tl (2^fuel) s)
203 (InfiniteSum_raw_N fuel filter (fun _ r => r) s q).
204 Proof.
205 induction fuel.
206 - intros. simpl. unfold InfiniteSum_raw_F.
207 destruct (filter s) eqn:des. 2: reflexivity.
208 exfalso. specialize (H O (Nat.le_refl _)). simpl in H.
209 rewrite H in des. discriminate.
210 - intros. simpl.
211 assert (forall p : nat, (p < 2 ^ fuel)%nat -> filter (Str_nth_tl p s) = false) as firstHalf.
212 { intros. apply (H p).
213 simpl. rewrite Nat.add_0_r.
214 apply (Nat.lt_le_trans _ (0+2^fuel)).
215 exact H0. apply Nat.add_le_mono_r, Nat.le_0_l. }
216 rewrite IHfuel, IHfuel.
217 3: exact firstHalf.
218 rewrite Nat.add_0_r, Str_nth_tl_plus.
219 apply f_equal. symmetry. apply IHfuel.
220 exact firstHalf.
221 intros. rewrite Str_nth_tl_plus. apply H.
222 simpl. rewrite Nat.add_0_r.
223 apply Nat.add_lt_mono_r, H0.
224 Qed.
225
226 (* The initial continuation is not reached when
227 the filter is triggered before. *)
228 Lemma InfiniteSum_raw_N_cont_invariant
229 : forall (fuel p : nat) c d (filter : Stream Q -> bool) (s : Stream Q) (q : Q),
230 (p < 2 ^ fuel)%nat
231 -> filter (Str_nth_tl p s) = true
232 -> InfiniteSum_raw_N fuel filter c s q
233 = InfiniteSum_raw_N fuel filter d s q.
234 Proof.
235 induction fuel.
236 - intros. simpl in H. simpl.
237 unfold InfiniteSum_raw_F.
238 destruct (filter s) eqn:des. reflexivity.
239 apply le_S_n in H. inversion H.
240 exfalso. subst p. simpl in H0.
241 rewrite H0 in des. discriminate.
242 - intros. simpl. simpl in H. rewrite Nat.add_0_r in H.
243 destruct (decide_filter_before_n (2^fuel) filter s).
244 destruct H1 as [k [H1 H2]]. apply (IHfuel k).
245 exact H1. exact H2.
246 (* Now 2^fuel <= p *)
247 destruct (Nat.lt_ge_cases p (2^fuel)).
248 exfalso. specialize (H1 p H2). rewrite H0 in H1. discriminate.
249 apply Nat.le_exists_sub in H2.
250 destruct H2 as [k [H2 _]]. subst p.
251 rewrite <- Str_nth_tl_plus in H0.
252 rewrite (InfiniteSum_raw_N_step
253 fuel (fun s0 : Stream Q => InfiniteSum_raw_N fuel filter c s0)).
254 2: exact H1.
255 rewrite (InfiniteSum_raw_N_step
256 fuel (fun s0 : Stream Q => InfiniteSum_raw_N fuel filter d s0)).
257 2: exact H1.
258 apply (IHfuel k).
259 apply Nat.add_lt_mono_r in H. exact H. exact H0.
260 Qed.
261
262 Lemma InfiniteSum_raw_N_correct
263 : forall (fuel : nat) (s : Stream Q) (filter : Stream Q -> bool) (q : Q),
264 InfiniteSum_raw_N fuel filter (fun _ r => r) s q
265 = InfiniteSum_fat filter s q (2 ^ fuel)%nat.
266 Proof.
267 induction fuel.
268 - intros. simpl. unfold InfiniteSum_raw_F.
269 destruct (filter s). reflexivity. simpl.
270 destruct (filter (tl s)); reflexivity.
271 - intros s filter q. simpl. rewrite Nat.add_0_r.
272 destruct (decide_filter_before_n (2^fuel)%nat filter s).
273 + destruct H as [p [H H0]].
274 rewrite (@InfiniteSum_fat_add_stop _ p).
275 3: exact H0.
276 rewrite <- (@InfiniteSum_fat_add_stop (2^fuel)).
277 2: apply (Nat.le_trans _ (S p) _ (le_S _ _ (Nat.le_refl p)) H).
278 2: exact H0.
279 rewrite <- IHfuel.
280 apply (@InfiniteSum_raw_N_cont_invariant fuel p).
281 exact H. exact H0.
282 apply (Nat.le_trans _ (2^fuel + 0)).
283 rewrite Nat.add_0_r.
284 apply (Nat.le_trans _ (S p) _ (le_S _ _ (Nat.le_refl p)) H).
285 apply Nat.add_le_mono_l, Nat.le_0_l.
286 + rewrite InfiniteSum_fat_add_pass. 2: exact H.
287 rewrite <- IHfuel. rewrite <- IHfuel.
288 rewrite InfiniteSum_raw_N_step. reflexivity. exact H.
289 Qed.
290
291 Lemma InfiniteSum_raw_N_extend : forall (p q:nat) s (err : Stream Q -> bool) (r:Q),
292 (Is_true (err (Str_nth_tl (2^p) s))) -> (p <= q)%nat ->
293 InfiniteSum_raw_N p err (fun _ r => r) s r
294 = InfiniteSum_raw_N q err (fun _ r => r) s r.
295 Proof.
296 intros.
297 rewrite InfiniteSum_raw_N_correct, InfiniteSum_raw_N_correct.
298 symmetry. apply InfiniteSum_fat_add_stop.
299 apply Nat.pow_le_mono_r. discriminate. exact H0.
300 unfold Is_true in H.
301 destruct (err (Str_nth_tl (2 ^ p) s)).
302 reflexivity. contradiction.
303 Qed.
304
305 Lemma InfiniteSum_fat_minus
306 : forall (i p : nat) (s : Stream Q) (q : Q),
307 InfiniteSum_fat (fun _ => false) s q (p + i) -
308 InfiniteSum_fat (fun _ => false) s q i
309 == InfiniteSum_fat (fun _ => false) (Str_nth_tl i s) 0 p.
310 Proof.
311 induction i.
312 - intros. simpl. rewrite Nat.add_0_r.
313 unfold Qminus. rewrite InfiniteSum_fat_plus.
314 ring.
315 - intros. rewrite Nat.add_succ_r. simpl.
316 rewrite IHi. reflexivity.
317 Qed.
318
319 Lemma InfiniteSum_fat_wd
320 : forall (fuel:nat) (filter:Stream Q -> bool) (s:Stream Q) (q r : Q),
321 q == r
322 -> InfiniteSum_fat filter s q fuel
323 == InfiniteSum_fat filter s r fuel.
324 Proof.
325 induction fuel.
326 - intros. simpl. destruct (filter s); exact H.
327 - intros. simpl. destruct (filter s). exact H.
328 apply IHfuel. rewrite Qplus'_correct, Qplus'_correct.
329 apply Qplus_comp. exact H. reflexivity.
330 Qed.
331
332 (**
333 ** Geometric Series
334 A geometric series is simple to sum. However we do something slightly
335 more general. We sum a series that satifies the ratio test. *)
336
337 Section GeometricSeries.
338 Variable a : Q.
339
340 Hypothesis Ha0 : 0 <= a.
341 Hypothesis Ha1 : a < 1.
342
343 (** The definition of what we are calling a [GeometricSeries]: a series
344 that satifies the ratio test. *)
345 Definition GeometricSeries := ForAll (fun s => Qabs ((hd (tl s))) <= a*(Qabs(hd s))).
346
347 (** [err_bound] majorates the distance between
348 the head of the series and its limit. *)
349 Let err_bound (s:Stream Q) : Q := Qabs (hd s)/(1-a).
350
351 (** [err_prop]: is err a bound on the series s? *)
352 Let err_prop (err:Q) (s:Stream Q) : bool :=
353 match ((err_bound s) ?= err) with
354 Gt => false
355 |_ => true
356 end.
357
358 Lemma err_prop_prop : forall e s, err_prop e s = true <-> err_bound s <= e.
359 Proof.
360 intros e s.
361 unfold err_prop, err_bound, Qcompare, Qle, Z.le.
362 destruct (Qnum (Qabs (hd s) / (1 - a))%Q * Zpos (Qden e) ?= Qnum e * Zpos (Qden (Qabs (hd s) / (1 - a))%Q))%Z;
363 split; auto with *.
364 Qed.
365
366 Lemma err_prop_nonneg : forall e s, err_prop e s = true -> 0 <= e.
367 Proof.
368 intros. apply err_prop_prop in H.
369 refine (Qle_trans _ _ _ _ H).
370 apply Qmult_le_0_compat. apply Qabs_nonneg.
371 apply Qlt_le_weak, Qinv_lt_0_compat.
372 unfold Qminus. rewrite <- Qlt_minus_iff. exact Ha1.
373 Qed.
374
375 (** The key lemma about error bounds. *)
376 Lemma err_prop_key : forall (e:Q) (s: Stream Q) (x:Q),
377 err_prop e s = true -> Qabs x <= a*e -> Qabs (Qplus' (hd s) x) <= e.
378 Proof.
379 intros e s x Hs Hx.
380 rewrite -> Qplus'_correct.
381 eapply Qle_trans.
382 apply Qabs_triangle.
383 setoid_replace e with (e*(1-a) + a*e)
384 by (unfold canonical_names.equiv, stdlib_rationals.Q_eq; simpl; ring).
385 assert (X:0 < 1 - a).
386 change (0 < 1 + - a).
387 rewrite <- Qlt_minus_iff.
388 assumption.
389 apply Qplus_le_compat; try assumption.
390 rewrite -> err_prop_prop in Hs.
391 unfold err_bound in Hs.
392 apply Qmult_lt_0_le_reg_r with (/(1-a)).
393 apply Qinv_lt_0_compat; assumption.
394 rewrite <- Qmult_assoc, Qmult_inv_r, Qmult_1_r.
395 assumption.
396 auto with *.
397 Qed.
398
399 Lemma err_prop_key' : forall (e:Q) (s: Stream Q),
400 GeometricSeries s -> err_prop e s = true -> err_prop (a*e) (tl s) = true.
401 Proof.
402 intros e s [H _] Hs.
403 rewrite -> err_prop_prop in *.
404 unfold err_bound in *.
405 rewrite -> Qle_minus_iff in H, Hs |- *.
406 rewrite -> Qlt_minus_iff in Ha1.
407 setoid_replace (a * e + - (Qabs (hd (tl s)) / (1 - a)))
408 with (a * (e + - (Qabs (hd s)/(1-a)))+ (a * Qabs (hd s) + - Qabs (hd (tl s)))/(1+-a))
409 by (unfold canonical_names.equiv, stdlib_rationals.Q_eq; simpl; field).
410 rewrite <- Qplus_0_r.
411 apply Qplus_le_compat.
412 apply Qmult_le_0_compat. exact Ha0. exact Hs.
413 apply Qmult_le_0_compat. exact H.
414 apply Qlt_le_weak, Qinv_lt_0_compat, Ha1.
415 intro abs. rewrite abs in Ha1. exact (Qlt_irrefl 0 Ha1).
416 Qed.
417
418 Lemma err_prop_monotone : forall (e0 e1:Q) (s: Stream Q),
419 (e0 <= e1) -> err_prop e0 s = true -> err_prop e1 s = true.
420 Proof.
421 intros e0 e1 s He H.
422 rewrite -> err_prop_prop in *.
423 apply Qle_trans with e0; assumption.
424 Qed.
425
426 Lemma err_prop_monotone' : forall (e:Q) (s: Stream Q),
427 GeometricSeries s -> err_prop e s = true -> err_prop e (tl s) = true.
428 Proof.
429 intros e s Hs H.
430 rewrite -> err_prop_prop in *.
431 eapply Qle_trans;[|apply H].
432 unfold err_bound.
433 apply Qmult_le_r.
434 - apply Qinv_lt_0_compat. unfold Qminus.
435 rewrite <- Qlt_minus_iff. exact Ha1.
436 - destruct Hs as [H0 _].
437 eapply Qle_trans;[apply H0|].
438 rewrite <- (Qmult_1_l (Qabs(hd s))) at 2.
439 apply Qmult_le_compat_r.
440 apply Qlt_le_weak, Ha1. apply Qabs_nonneg.
441 Qed.
442
443 (** If a geometric sum s is bounded by e,
444 summing s to any index p is within bound e. *)
445 Lemma err_prop_correct : forall (p:nat) (e:Q) (s : Stream Q) (e':Stream Q -> bool),
446 GeometricSeries s
447 -> err_prop e s = true
448 -> Qabs (InfiniteSum_fat e' s 0%Q p) <= e.
449 Proof.
450 induction p.
451 - intros. simpl. apply err_prop_nonneg in H0.
452 destruct (e' s); exact H0.
453 - intros. simpl.
454 destruct (e' s). apply err_prop_nonneg in H0. exact H0.
455 rewrite InfiniteSum_fat_plus.
456 rewrite Qplus'_correct, Qplus_0_l.
457 rewrite <- Qplus'_correct.
458 apply err_prop_key. exact H0.
459 apply (IHp (a*e)). apply H.
460 apply err_prop_key'; assumption.
461 Qed.
462
463 (** This lemma tells us how to compute an upper bound on the number of
464 terms we will need to compute. It is okay for this error to be loose
465 because the partial sums will bail out early when it sees that its
466 estimate of the error is small enough. *)
467 Lemma GeometricCovergenceLemma : forall (n:positive) (e:Qpos),
468 /(proj1_sig e*(1 - a)) <= inject_Z (Zpos n) -> a^Zpos n <= proj1_sig e.
469 Proof.
470 destruct (Qle_lt_or_eq _ _ Ha0) as [Ha0'|Ha0'].
471 - intros n e H.
472 assert (0 < a^Zpos n).
473 { assert (X:0 < proj1_sig (Qpos_power (exist _ _ Ha0') (Zpos n))%Qpos)
474 by auto with *.
475 exact X. }
476 apply Qmult_lt_0_le_reg_r with ((/proj1_sig e)*/(a^Zpos n)).
477 apply (Qle_lt_trans _ (0 * (/a^Zpos n))).
478 rewrite Qmult_0_l. apply Qle_refl.
479 apply Qmult_lt_r.
480 apply Qinv_lt_0_compat; exact H0.
481 apply Qinv_lt_0_compat, Qpos_ispos.
482 assert (0 < proj1_sig e) by (apply Qpos_ispos).
483 rewrite (Qmult_assoc (proj1_sig e)), Qmult_inv_r, Qmult_1_l.
484 2: apply Qpos_nonzero.
485 setoid_replace (a ^ Zpos n * (/ proj1_sig e * / a ^ Zpos n))
486 with (/proj1_sig e)
487 by (unfold canonical_names.equiv, stdlib_rationals.Q_eq; simpl; field).
488 2: split. 2: apply Qpos_nonzero. 2: auto with *.
489 rewrite -> Qlt_minus_iff in Ha1.
490 change (0<1-a) in Ha1.
491 rewrite -> Qle_minus_iff in H.
492 apply Qle_trans with (1 + inject_Z (Zpos n) * (/a -1)).
493 + rewrite -> Qle_minus_iff.
494 setoid_replace (1 + inject_Z (Zpos n) * (/ a - 1) + - / proj1_sig e)
495 with (1+(1 - a)*((inject_Z (Zpos n)*(1-a)*/a + (inject_Z (Zpos n) +-(/(proj1_sig e*(1 - a)))))))
496 by (unfold canonical_names.equiv, stdlib_rationals.Q_eq; simpl; field).
497 2: split; auto with *.
498 apply (Qle_trans _ (1+0)).
499 discriminate. apply Qplus_le_r.
500 repeat apply Qmult_le_0_compat; simpl; auto with *.
501 assert (0 <= 1-a) by auto with *.
502 apply (Qle_trans _ (0+0)). discriminate.
503 apply Qplus_le_compat. 2: exact H.
504 apply Qmult_le_0_compat.
505 apply Qmult_le_0_compat. discriminate.
506 exact H2. apply Qlt_le_weak, Qinv_lt_0_compat, Ha0'.
507 + clear -n Ha0'.
508 induction n using Pind.
509 simpl.
510 setoid_replace (1 + inject_Z 1 * (/ a - 1)) with (/a)
511 by (unfold canonical_names.equiv, stdlib_rationals.Q_eq; simpl; ring).
512 apply Qle_refl.
513 rewrite Zpos_succ_morphism.
514 unfold Z.succ.
515 rewrite -> Qpower_plus;[|auto with *].
516 rewrite -> Qinv_mult_distr.
517 rewrite -> Q.Zplus_Qplus.
518 apply Qle_trans with ((1 + inject_Z (Zpos n) * (/ a - 1))*/a).
519 rewrite -> Qle_minus_iff.
520 setoid_replace ( (1 + inject_Z (Z.pos n) * (/ a - 1)) * / a +
521 - (1 + (inject_Z (Z.pos n) + inject_Z 1) * (/ a - 1)))
522 with (inject_Z (Zpos n)*(/a -1)^2)
523 by (unfold canonical_names.equiv, stdlib_rationals.Q_eq; simpl; ring).
524 apply Qmult_le_0_compat. discriminate.
525 unfold Qle. rewrite Z.mul_0_l. simpl.
526 rewrite Z.mul_1_r. apply Z.square_nonneg.
527 apply Qmult_le_compat_r.
528 assumption.
529 apply Qinv_le_0_compat; auto with *.
530 - intros n e _.
531 rewrite <- Ha0'.
532 rewrite -> Qpower_0; auto with *.
533 Qed.
534
535 Definition InfiniteGeometricSum_maxIter series (err:Qpos) : positive :=
536 let x := (1-a) in
537 let (n,d) := (Qabs (hd series))/(proj1_sig err*x*x) in
538 match Z.succ (Z.div n (Zpos d)) with
539 | Zpos p => p
540 | _ => 1%positive
541 end.
542
543 Lemma InfiniteGeometricSum_maxIter_monotone : forall series (err:Qpos),
544 GeometricSeries series ->
545 (InfiniteGeometricSum_maxIter (tl series) err
546 <= InfiniteGeometricSum_maxIter series err)%positive.
547 Proof.
548 intros series err Gs.
549 unfold InfiniteGeometricSum_maxIter.
550 cut ((Qabs (hd (tl series)) / (proj1_sig err * (1 - a) * (1 - a))) <=
551 (Qabs (hd series) / (proj1_sig err * (1 - a) * (1 - a)))).
552 - generalize (Qabs (hd (tl series)) / (proj1_sig err * (1 - a) * (1 - a)))
553 (Qabs (hd series) / (proj1_sig err * (1 - a) * (1 - a))).
554 intros [na da] [nb db] H.
555 cut (Z.succ (na/Zpos da) <= Z.succ (nb/Zpos db))%Z.
556 generalize (Z.succ (na / Zpos da)) (Z.succ (nb/Zpos db)).
557 intros [|x|x] [|y|y] Hxy;
558 try solve [apply Hxy | apply Qle_refl | elim Hxy; constructor
559 | unfold Qle; simpl; repeat rewrite Pmult_1_r].
560 apply Pos.le_1_l. discriminate.
561 apply Pos.le_1_l. discriminate.
562 apply Zsucc_le_compat.
563 unfold Qle in H.
564 simpl in H.
565 rewrite <- (Zdiv_mult_cancel_r na (Zpos da) (Zpos db)).
566 2: discriminate.
567 rewrite <- (Zdiv_mult_cancel_r nb (Zpos db) (Zpos da)).
568 2: discriminate.
569 rewrite (Zmult_comm (Zpos db) (Zpos da)).
570 apply Z_div_le. reflexivity. exact H.
571 - assert (X:0 < 1 - a).
572 change (0 < 1 + - a).
573 rewrite <- Qlt_minus_iff.
574 assumption.
575 apply Qle_shift_div_l.
576 apply (Qpos_ispos (err * (exist _ _ X) * (exist _ _ X))).
577 unfold Qdiv. rewrite <- Qmult_assoc.
578 rewrite <- (Qmult_comm (proj1_sig err * (1 - a) * (1 - a))).
579 rewrite Qmult_inv_r, Qmult_1_r.
580 destruct Gs as [H _].
581 eapply Qle_trans.
582 apply H.
583 rewrite <- (Qmult_1_l (Qabs (hd series))) at 2.
584 apply Qmult_le_compat_r.
585 apply Qlt_le_weak, Ha1. apply Qabs_nonneg.
586 apply (Qpos_nonzero (err * (exist _ _ X) * (exist _ _ X))).
587 Qed.
588
589 Lemma InfiniteGeometricSum_maxIter_correct
590 : forall series (err:Qpos),
591 GeometricSeries series ->
592 err_prop (proj1_sig err) (Str_nth_tl (nat_of_P (InfiniteGeometricSum_maxIter series err)) series) = true.
593 Proof.
594 intros series err H.
595 rewrite -> err_prop_prop.
596 unfold err_bound.
597 assert (X:0 < 1 - a).
598 change (0 < 1 + - a).
599 rewrite <- Qlt_minus_iff.
600 assumption.
601 apply Qle_shift_div_r; try assumption.
602 assert (Y:(Qabs (hd series) * a ^ Zpos (InfiniteGeometricSum_maxIter series err)
603 <= proj1_sig err * (1 - a))).
604 { destruct (Qlt_le_dec 0 (Qabs (hd series))).
605 apply Qmult_lt_0_le_reg_r with (/Qabs (hd series)).
606 apply Qinv_lt_0_compat; assumption.
607 rewrite (Qmult_comm (Qabs (hd series))), <- Qmult_assoc.
608 rewrite Qmult_inv_r, Qmult_1_r.
609 2: auto with *.
610 cut (a ^ Zpos (InfiniteGeometricSum_maxIter series err)
611 <= proj1_sig (err * exist _ _ X * Qpos_inv (exist _ _ q))%Qpos).
612 autorewrite with QposElim; auto.
613 apply GeometricCovergenceLemma.
614 autorewrite with QposElim.
615 unfold InfiniteGeometricSum_maxIter.
616 simpl (/ (proj1_sig
617 (err * exist (Qlt 0) (1 - a) X * Qpos_inv (exist (Qlt 0) (Qabs (hd series)) q))%Qpos * (1 - a))).
618 setoid_replace (/ (proj1_sig err * (1 - a) * / Qabs (hd series) * (1 - a)))
619 with (Qabs (hd series) / (proj1_sig err * (1 - a) * (1 - a)))
620 by (unfold canonical_names.equiv, stdlib_rationals.Q_eq; simpl; field).
621 2: repeat split;auto with *;apply Qpos_nonzero.
622 cut (0 < (Qabs (hd series) / (proj1_sig err * (1 - a) * (1 - a)))).
623 generalize (Qabs (hd series) / (proj1_sig err * (1 - a) * (1 - a))).
624 intros [n d] Hnd.
625 apply Qle_trans with (inject_Z (Z.succ (n/Zpos d))).
626 unfold Qle.
627 simpl.
628 unfold Z.succ.
629 apply Zle_0_minus_le.
630 replace ((n / Zpos d + 1) * Zpos d - n * 1)%Z
631 with (Zpos d*(n/Zpos d) + n mod (Zpos d) - n mod (Zpos d) - n + Zpos d)%Z
632 by ring.
633 rewrite <- Z_div_mod_eq_full.
634 replace (n - n mod (Zpos d) - n + Zpos d)%Z
635 with (Zpos d - n mod (Zpos d))%Z by ring.
636 apply Zle_minus_le_0.
637 destruct (Z_mod_lt n (Zpos d)); auto with *.
638 generalize (Z.succ (n/Zpos d)).
639 intros [|z|z].
640 discriminate.
641 apply Qle_refl.
642 discriminate.
643 cut (0 < proj1_sig ((exist _ _ q) * Qpos_inv(err * (exist _ _ X)*(exist _ _ X)))%Qpos).
644 simpl; auto.
645 apply Q.Qmult_lt_0_compat; auto with *.
646 setoid_replace (Qabs (hd series)) with 0.
647 rewrite Qmult_0_l.
648 apply (Qpos_nonneg (err * (exist _ _ X))).
649 apply Qle_antisym; try assumption.
650 apply Qabs_nonneg. }
651 apply Qle_trans with (Qabs (hd series)*a^Zpos (InfiniteGeometricSum_maxIter series err)); try assumption.
652 clear Y.
653 generalize (InfiniteGeometricSum_maxIter series err).
654 intros p.
655 revert series H.
656 induction p using Pind; intros series H.
657 simpl.
658 destruct H.
659 rewrite -> Qmult_comm.
660 assumption.
661 rewrite nat_of_P_succ_morphism.
662 rewrite Zpos_succ_morphism.
663 unfold Z.succ.
664 rewrite -> Qpower_plus';[|discriminate].
665 rewrite Qmult_assoc.
666 apply Qle_trans with (Qabs (hd (Str_nth_tl (nat_of_P p) series))*a).
667 change (S (nat_of_P p)) with (1+(nat_of_P p))%nat.
668 rewrite <- Str_nth_tl_plus.
669 cut (GeometricSeries (Str_nth_tl (nat_of_P p) series)).
670 generalize (Str_nth_tl (nat_of_P p) series).
671 intros s [H0 _].
672 rewrite -> Qmult_comm.
673 assumption.
674 clear -H.
675 induction (nat_of_P p).
676 auto.
677 change (S n) with (1+n)%nat.
678 rewrite <- Str_nth_tl_plus.
679 simpl.
680 destruct IHn; assumption.
681 apply Qmult_le_compat_r; try assumption.
682 apply IHp; assumption.
683 Qed.
684
685 (** The implemenation of [InfiniteGeometricSum]. *)
686 Definition InfiniteGeometricSum_fat series (e:QposInf) : Q :=
687 match e with
688 | QposInfinity => 0
689 | Qpos2QposInf err => InfiniteSum_fat
690 (err_prop (proj1_sig err))
691 series 0%Q
692 (Pos.to_nat (InfiniteGeometricSum_maxIter series err))
693 end.
694
695 Definition InfiniteGeometricSum_raw series (e:QposInf) : Q :=
696 match e with
697 | QposInfinity => 0
698 | Qpos2QposInf err => InfiniteSum_raw_N
699 (Pos.to_nat (Pos.size (InfiniteGeometricSum_maxIter series err)))
700 (err_prop (proj1_sig err))
701 (fun _ r => r) series 0%Q
702 end.
703
704 Lemma InfiniteGeometricSum_raw_correct
705 : forall (series : Stream Q) (e : QposInf),
706 GeometricSeries series
707 -> InfiniteGeometricSum_raw series e = InfiniteGeometricSum_fat series e.
708 Proof.
709 assert (forall n:nat,
710 lt 0 n -> Pos.of_nat (2 ^ n) = (2 ^ Pos.of_nat n)%positive) as inj_pow.
711 { induction n.
712 - intros. exfalso; inversion H.
713 - intros _. destruct n. reflexivity.
714 rewrite Nat2Pos.inj_succ. 2: discriminate.
715 rewrite Pos.pow_succ_r.
716 rewrite <- IHn. 2: apply le_n_S, Nat.le_0_l. clear IHn.
717 generalize (S n). intro k.
718 change (2 ^ S k)%nat with (2 * 2 ^ k)%nat.
719 rewrite Nat2Pos.inj_mul. reflexivity. discriminate.
720 apply Nat.pow_nonzero. discriminate. }
721 intros. destruct e. 2: reflexivity.
722 simpl. rewrite InfiniteSum_raw_N_correct.
723 apply InfiniteSum_fat_add_stop.
724 2: apply InfiniteGeometricSum_maxIter_correct, H.
725 specialize (inj_pow (Pos.to_nat (Pos.size (InfiniteGeometricSum_maxIter series q)))
726 (Pos2Nat.is_pos _)).
727 rewrite Pos2Nat.id in inj_pow.
728 rewrite <- Nat2Pos.id. rewrite inj_pow.
729 apply Pos2Nat.inj_le.
730 apply Pos.lt_le_incl, Pos.size_gt.
731 apply Nat.pow_nonzero. discriminate.
732 Qed.
733
734 (* Now we prove that bounds are correct when applied to tails
735 of a geometric series at indexes p and p0. *)
736 Lemma err_prop_tail_correct :
737 forall (series : Stream Q) (e0 e1:Q) (p p0 : nat),
738 GeometricSeries series
739 -> e1 <= e0
740 -> err_prop e0 (Str_nth_tl p series) = true
741 -> err_prop e1 (Str_nth_tl p0 series) = true
742 -> Qball e0
743 (InfiniteSum_fat (err_prop e0) series 0%Q p)
744 (InfiniteSum_fat (err_prop e1) series 0%Q p0).
745 Proof.
746 intros series e0 e1 p0 p1 H He H0 H1.
747 (* err_prop e1 implies err_prop e0 so the e1 sum is longer.
748 Replace by the first indexes where the filters are triggered,
749 the one of e1 being higher.
750 The subtraction is a tail sum of e0 after the convergence index,
751 so it is below e0. *)
752 pose proof (@InfiniteSum_fat_remove_filter p0 (err_prop e0) series 0%Q)
753 as [i [H2 H3]].
754 exact H0. rewrite H2.
755 pose proof (@InfiniteSum_fat_remove_filter p1 (err_prop e1) series 0%Q)
756 as [j [H4 H5]].
757 exact H1. rewrite H4.
758 clear H4 H2 H1 H0 p0 p1. destruct H3. destruct H5.
759 destruct (Nat.lt_ge_cases j i).
760 - exfalso.
761 specialize (H0 j H4).
762 pose proof (err_prop_monotone (Str_nth_tl j series) He H3) as mon.
763 rewrite mon in H0. discriminate.
764 - unfold Qball.
765 rewrite <- AbsSmall_Qabs, Qabs_Qminus.
766 apply Nat.le_exists_sub in H4. destruct H4 as [p [H4 _]].
767 subst j. clear H3 H2 He e1.
768 rewrite InfiniteSum_fat_minus.
769 apply err_prop_correct.
770 2: exact H1.
771 apply ForAll_Str_nth_tl, H.
772 Qed.
773
774 Lemma InfiniteGeometricSum_raw_prf : forall series,
775 GeometricSeries series ->
776 is_RegularFunction Qball (InfiniteGeometricSum_raw series).
777 Proof.
778 intros series H e0 e1.
779 rewrite InfiniteGeometricSum_raw_correct.
780 rewrite InfiniteGeometricSum_raw_correct.
781 2: exact H. 2: exact H.
782 pose proof (InfiniteGeometricSum_maxIter_correct e0 H) as H0.
783 pose proof (InfiniteGeometricSum_maxIter_correct e1 H) as H1.
784 destruct (Qle_total (proj1_sig e1) (proj1_sig e0)).
785 - apply ball_weak. apply Qpos_nonneg.
786 apply (err_prop_tail_correct _ _ H q H0 H1).
787 - rewrite Qplus_comm.
788 apply ball_weak. apply Qpos_nonneg.
789 apply ball_sym.
790 apply (err_prop_tail_correct _ _ H q H1 H0).
791 Qed.
792
793 Definition InfiniteGeometricSum series (Gs:GeometricSeries series) : CR :=
794 Build_RegularFunction (InfiniteGeometricSum_raw_prf Gs).
795
796 (** The [InfiniteGeometricSum] is correct. *)
797 Lemma InfiniteGeometricSum_step : forall series (Gs:GeometricSeries series),
798 (InfiniteGeometricSum Gs ==
799 ('(hd series))+(InfiniteGeometricSum (ForAll_Str_nth_tl 1%nat Gs)))%CR.
800 Proof.
801 intros series Gs.
802 rewrite -> CRplus_translate.
803 apply regFunEq_equiv, regFunEq_e.
804 intros e.
805 change (approximate (InfiniteGeometricSum Gs) e)
806 with (InfiniteGeometricSum_raw series e).
807 rewrite InfiniteGeometricSum_raw_correct. 2: exact Gs.
808 simpl (InfiniteGeometricSum (ForAll_Str_nth_tl 1 Gs)).
809 change (approximate
810 (translate (hd series) (InfiniteGeometricSum (ForAll_Str_nth_tl 1 Gs))) e)
811 with (hd series
812 + (InfiniteGeometricSum_raw (tl series) e)).
813 rewrite InfiniteGeometricSum_raw_correct. 2: apply Gs.
814 simpl.
815 rewrite InfiniteSum_fat_extend.
816 2: apply InfiniteGeometricSum_maxIter_correct, Gs.
817 simpl.
818 case_eq (err_prop (proj1_sig e) series); intros He.
819 - apply ball_sym.
820 simpl.
821 unfold Qball.
822 rewrite <- AbsSmall_Qabs.
823 unfold Qminus. rewrite Qplus_0_r.
824 eapply Qle_trans.
825 apply Qabs_triangle.
826 apply Qplus_le_compat; simpl.
827 rewrite -> err_prop_prop in He.
828 unfold err_bound in He.
829 assert (X:0 < 1 - a).
830 change (0 < 1 + - a).
831 rewrite <- Qlt_minus_iff.
832 assumption.
833 clear - He Ha0 X.
834 setoid_replace (Qabs (hd series))
835 with ((Qabs (hd series)/(1-a))*(1-a))
836 by (unfold canonical_names.equiv, stdlib_rationals.Q_eq; simpl; field).
837 2: auto with *.
838 apply (Qle_trans _ ((proj1_sig e) * (1-a))).
839 apply Qmult_le_compat_r. exact He.
840 apply Qlt_le_weak, X.
841 rewrite <- (Qmult_1_r (proj1_sig e)) at 2.
842 apply Qmult_le_l. apply Qpos_ispos.
843 rewrite <- (Qplus_0_r 1) at 2. apply Qplus_le_r.
844 apply (Qopp_le_compat 0), Ha0.
845 apply err_prop_correct.
846 destruct Gs; assumption.
847 apply err_prop_monotone'; assumption.
848 - assert (Qplus' 0 (hd series) == hd series).
849 { rewrite Qplus'_correct. apply Qplus_0_l. }
850 rewrite (InfiniteSum_fat_wd _ _ _ H).
851 rewrite InfiniteSum_fat_plus.
852 rewrite (@InfiniteSum_fat_add_stop
853 (Pos.to_nat (InfiniteGeometricSum_maxIter series e))
854 (Pos.to_nat (InfiniteGeometricSum_maxIter (tl series) e))).
855 apply Qball_Reflexive.
856 apply (Qpos_nonneg (e+e)).
857 apply Pos2Nat.inj_le.
858 apply (@InfiniteGeometricSum_maxIter_monotone series e), Gs.
859 apply InfiniteGeometricSum_maxIter_correct, Gs.
860 Qed.
861
862 Lemma InfiniteGeometricSum_bound : forall series
863 (Gs:GeometricSeries series),
864 (-'(err_bound series) <= InfiniteGeometricSum Gs
865 /\ InfiniteGeometricSum Gs <= '(err_bound series))%CR.
866 Proof.
867 intros series Gs.
868 assert (Y:0 < 1 - a).
869 { change (0 < 1 + - a).
870 rewrite <- Qlt_minus_iff.
871 assumption. }
872 destruct (Qeq_dec (err_bound series) 0) as [Hq|Hq].
873 - setoid_replace (InfiniteGeometricSum Gs) with 0%CR.
874 split; simpl; rewrite -> Hq; try apply CRle_refl.
875 rewrite CRopp_0. apply CRle_refl.
876 apply regFunEq_equiv, regFunEq_e.
877 intros e.
878 apply ball_sym.
879 change (approximate (InfiniteGeometricSum Gs) e)
880 with (InfiniteGeometricSum_raw series e).
881 rewrite InfiniteGeometricSum_raw_correct. 2: exact Gs.
882 simpl.
883 unfold Qball.
884 unfold QAbsSmall.
885 setoid_replace (0 - InfiniteSum_fat (err_prop (proj1_sig e)) series 0
886 (Pos.to_nat (InfiniteGeometricSum_maxIter series e)))%Q
887 with 0.
888 split. apply (Qopp_le_compat 0), (Qpos_nonneg (e+e)).
889 apply (Qpos_nonneg (e+e)).
890 unfold canonical_names.equiv, stdlib_rationals.Q_eq.
891 unfold Qminus. rewrite Qplus_0_l.
892 assert (X:err_prop (proj1_sig e) series = true).
893 rewrite -> err_prop_prop.
894 rewrite -> Hq.
895 apply Qpos_nonneg.
896 destruct (InfiniteGeometricSum_maxIter series e) using Pind.
897 simpl.
898 destruct (err_prop (proj1_sig e) series).
899 reflexivity. discriminate.
900 rewrite Pos2Nat.inj_succ.
901 simpl.
902 destruct (err_prop (proj1_sig e) series).
903 reflexivity. discriminate.
904 - cut (-(' err_bound series) <= InfiniteGeometricSum Gs
905 /\ InfiniteGeometricSum Gs <= 'err_bound series)%CR.
906 + intros [H0 H1].
907 split; assumption.
908 + setoid_replace (InfiniteGeometricSum Gs)
909 with (InfiniteGeometricSum Gs - 0)%CR
910 by (unfold canonical_names.equiv, msp_Equiv; ring).
911 apply CRAbsSmall_ball.
912 apply regFunBall_e.
913 intros d.
914 change (approximate (InfiniteGeometricSum Gs) d)
915 with (InfiniteGeometricSum_raw series d).
916 rewrite InfiniteGeometricSum_raw_correct. 2: exact Gs.
917 simpl.
918 set (p:=(InfiniteGeometricSum_maxIter series d)).
919 unfold Qball.
920 rewrite <- AbsSmall_Qabs.
921 unfold Qminus. rewrite Qplus_0_r.
922 apply (err_prop_correct _ (proj1_sig d+err_bound series+proj1_sig d));
923 try assumption.
924 apply err_prop_monotone with (err_bound series).
925 simpl.
926 apply (Qle_trans _ (0 + err_bound series + 0)).
927 rewrite Qplus_0_l, Qplus_0_r. apply Qle_refl.
928 apply Qplus_le_compat. apply Qplus_le_compat.
929 apply Qpos_nonneg. apply Qle_refl. apply Qpos_nonneg.
930 rewrite -> err_prop_prop.
931 apply Qle_refl.
932 Qed.
933
934 Lemma InfiniteGeometricSum_small_tail : forall series (e : Qpos),
935 GeometricSeries series ->
936 {n : nat & forall Gs : GeometricSeries (Str_nth_tl n series),
937 (- ' proj1_sig e <= InfiniteGeometricSum Gs
938 /\ InfiniteGeometricSum Gs <= 'proj1_sig e)%CR }.
939 Proof.
940 intros series e.
941 exists (nat_of_P (InfiniteGeometricSum_maxIter series e)).
942 intros Gs.
943 pose proof (InfiniteGeometricSum_bound Gs) as [H0 H1].
944 split.
945 refine (CRle_trans _ H0). apply CRopp_le_compat.
946 rewrite -> CRle_Qle.
947 rewrite <- err_prop_prop.
948 apply InfiniteGeometricSum_maxIter_correct.
949 assumption.
950 apply (CRle_trans H1).
951 rewrite -> CRle_Qle.
952 rewrite <- err_prop_prop.
953 apply InfiniteGeometricSum_maxIter_correct.
954 assumption.
955 Qed.
956
957 End GeometricSeries.
958
959 (** If one stream is [DecreasingNonNegative] and the other is
960 a [GeometricSeries], then the result is a [GeometricSeries]. *)
961 Lemma mult_Streams_Gs : forall a (x y : Stream Q),
962 (DecreasingNonNegative x) ->
963 (GeometricSeries a y) ->
964 (GeometricSeries a (mult_Streams x y)).
965 Proof.
966 cofix mult_Streams_Gs.
967 intros a x y Hx Hy.
968 constructor.
969 destruct Hy as [Hy _].
970 apply dnn_alt in Hx.
971 destruct Hx as [[[Hx2 _] [[Hx0 Hx1] _]] _].
972 simpl.
973 rewrite -> Qabs_Qmult.
974 apply Qle_trans
975 with (Qabs (CoqStreams.hd x) * Qabs (CoqStreams.hd (CoqStreams.tl y))).
976 apply Qmult_le_compat_r.
977 do 2 (rewrite -> Qabs_pos; try assumption).
978 apply Qabs_nonneg.
979 rewrite -> Qabs_Qmult.
980 rewrite Qmult_comm.
981 rewrite (Qmult_comm (Qabs (CoqStreams.hd x))), Qmult_assoc.
982 apply Qmult_le_compat_r; try assumption.
983 apply Qabs_nonneg.
984 destruct Hy.
985 apply mult_Streams_Gs. 2: exact Hy.
986 apply Hx.
987 Qed.
988
989 (** [powers] is a [GeometricSeries]. *)
990 Lemma powers_help_Gs (a : Q) : (0 <= a) -> forall c,
991 (GeometricSeries a (powers_help a c)).
992 Proof.
993 intros Ha.
994 cofix powers_help_Gs.
995 intros c.
996 constructor.
997 simpl.
998 rewrite -> Qmult_comm.
999 rewrite -> Qabs_Qmult.
1000 rewrite -> (Qabs_pos a); try assumption.
1001 apply Qle_refl.
1002 apply powers_help_Gs.
1003 Qed.
1004
1005 Lemma powers_Gs (a : Q) : (0 <= a) -> (GeometricSeries a (powers a)).
1006 Proof.
1007 intros Ha.
1008 apply (powers_help_Gs Ha).
1009 Qed.
1010
1011 Definition InfiniteGeometricSum_shift_raw
1012 (s : Stream Q) (n : nat) {a : Q}
1013 (Gs : GeometricSeries a (Str_nth_tl n s))
1014 (e : QposInf) : Q
1015 := take s n Qplus' 0
1016 + InfiniteGeometricSum_raw a (Str_nth_tl n s) e.
1017
1018 Lemma InfiniteGeometricSum_raw_shift_prf
1019 : forall (s : Stream Q) (n : nat) {a : Q}
1020 (Gs : GeometricSeries a (Str_nth_tl n s)),
1021 0 <= a -> a < 1 ->
1022 is_RegularFunction Qball (InfiniteGeometricSum_shift_raw s n Gs).
1023 Proof.
1024 intros. intros e1 e2.
1025 apply AbsSmall_Qabs.
1026 unfold InfiniteGeometricSum_shift_raw.
1027 setoid_replace (take s n Qplus' 0 + InfiniteGeometricSum_raw a (Str_nth_tl n s) e1 -
1028 (take s n Qplus' 0 + InfiniteGeometricSum_raw a (Str_nth_tl n s) e2))
1029 with (InfiniteGeometricSum_raw a (Str_nth_tl n s) e1
1030 - InfiniteGeometricSum_raw a (Str_nth_tl n s) e2)
1031 by (unfold canonical_names.equiv, stdlib_rationals.Q_eq; ring).
1032 apply AbsSmall_Qabs.
1033 apply (InfiniteGeometricSum_raw_prf H H0 Gs).
1034 Qed.
1035
1036 Definition InfiniteGeometricSum_shift (s : Stream Q) (n : nat) (a : Q)
1037 (Gs : GeometricSeries a (Str_nth_tl n s))
1038 (apos : 0 <= a) (aone : a < 1) : CR
1039 := Build_RegularFunction (InfiniteGeometricSum_raw_shift_prf s n Gs apos aone).
1040
1041 (* Proof of correctness : the limit of the geometric series does not depend
1042 on the geometric ratio. *)
1043 Lemma InfiniteGeometricSum_wd : forall (s : Stream Q) (a b : Q)
1044 (Gsa : GeometricSeries a s)
1045 (Gsb : GeometricSeries b s)
1046 (apos : 0 <= a) (aone : a < 1)
1047 (bpos : 0 <= b) (bone : b < 1),
1048 msp_eq (InfiniteGeometricSum apos aone Gsa)
1049 (InfiniteGeometricSum bpos bone Gsb).
1050 Proof.
1051 assert (forall (s : Stream Q) (a b : Q)
1052 (Gsa : GeometricSeries a s)
1053 (Gsb : GeometricSeries b s)
1054 (apos : 0 <= a) (aone : a < 1)
1055 (bpos : 0 <= b) (bone : b < 1),
1056 a <= b ->
1057 msp_eq (InfiniteGeometricSum apos aone Gsa)
1058 (InfiniteGeometricSum bpos bone Gsb)).
1059 { intros.
1060 (* The same series is summed up to 2 different indexes,
1061 the distance is the sum between the lower and upper index.
1062 The upper index is associated to b, which corresponds to a
1063 slower geometric series. *)
1064 intros e1 e2.
1065 change (approximate (InfiniteGeometricSum apos aone Gsa) e1)
1066 with (InfiniteGeometricSum_raw a s e1).
1067 rewrite (InfiniteGeometricSum_raw_correct apos aone _ Gsa).
1068 change (approximate (InfiniteGeometricSum bpos bone Gsb) e2)
1069 with (InfiniteGeometricSum_raw b s e2).
1070 rewrite (InfiniteGeometricSum_raw_correct bpos bone _ Gsb).
1071 simpl.
1072 pose proof (@InfiniteSum_fat_remove_filter
1073 (Pos.to_nat (InfiniteGeometricSum_maxIter a s e1))
1074 (fun s0 : Stream Q =>
1075 match Qabs (hd s0) / (1 - a) ?= proj1_sig e1 with
1076 | Gt => false
1077 | _ => true
1078 end)
1079 s 0%Q)
1080 as [i [H2 H3]].
1081 apply (InfiniteGeometricSum_maxIter_correct apos aone _ Gsa).
1082 rewrite H2.
1083 pose proof (@InfiniteSum_fat_remove_filter
1084 (Pos.to_nat (InfiniteGeometricSum_maxIter b s e2))
1085 (fun s0 : Stream Q =>
1086 match Qabs (hd s0) / (1 - b) ?= proj1_sig e2 with
1087 | Gt => false
1088 | _ => true
1089 end)
1090 s 0%Q)
1091 as [j [H4 H5]].
1092 apply (InfiniteGeometricSum_maxIter_correct bpos bone _ Gsb).
1093 rewrite H4.
1094 destruct (Nat.lt_ge_cases i j) as [H0|H0].
1095 - rewrite Qplus_0_r.
1096 apply Nat.le_exists_sub in H0.
1097 destruct H0 as [k [H0 _]]. subst j.
1098 unfold Qball. clear H5.
1099 rewrite <- AbsSmall_Qabs, Qabs_Qminus.
1100 replace (k + S i)%nat with (S k + i)%nat
1101 by (rewrite Nat.add_succ_r; reflexivity).
1102 rewrite InfiniteSum_fat_minus.
1103 apply (Qle_trans _ (proj1_sig e1 + 0)).
1104 rewrite Qplus_0_r.
1105 apply (err_prop_correct apos aone).
1106 apply ForAll_Str_nth_tl, Gsa. apply H3.
1107 apply Qplus_le_r, Qpos_nonneg.
1108 - rewrite Qplus_0_r.
1109 apply Nat.le_exists_sub in H0.
1110 destruct H0 as [k [H0 _]]. subst i.
1111 unfold Qball. clear H3.
1112 rewrite <- AbsSmall_Qabs, Qabs_Qminus.
1113 rewrite Qabs_Qminus.
1114 rewrite InfiniteSum_fat_minus.
1115 apply (Qle_trans _ (0 + proj1_sig e2)).
1116 rewrite Qplus_0_l.
1117 apply (err_prop_correct bpos bone).
1118 apply ForAll_Str_nth_tl, Gsb. apply H5.
1119 apply Qplus_le_l, Qpos_nonneg. }
1120 intros. destruct (Qle_total a b).
1121 apply H, q. symmetry. apply H, q.
1122 Qed.