Debian Codegraph @

reals/faster/ARAlternatingSum.v

raw
1 From Coq Require Import Qabs.
2 Require Import CoRN.util.Qdlog
3 CoRN.algebra.RSetoid
4 CoRN.model.totalorder.QposMinMax
5 CoRN.model.metric2.Qmetric
6 CoRN.model.reals.CRreal
7 CoRN.metric2.Metric
8 CoRN.metric2.UniformContinuity
9 CoRN.reals.fast.CRAlternatingSum
10 CoRN.reals.fast.CRstreams
11 CoRN.reals.faster.ApproximateRationals
12 CoRN.reals.faster.ARArith.
13
14
15 (**
16 The goal of this section is to compute the infinite alternating sum. Since
17 we do not have a precise division operation, we want to postpone divisions as
18 long as possible. Hence we parametrize our infinite sum by a stream [sN]
19 of numerators and a stream [sD] of denominators.
20
21 To compute an infinite series at precision epsilon, the finite number n of
22 terms to sum can be computed exactly, because sN n / sD n < epsilon/2 is
23 equivalent to sN n < (sD n) * epsilon/2, which does not involve the approximate
24 division. In the other epsilon/2, we can approximate the n divisions at
25 precision 2^k such as n*2^k < epsilon/2.
26 *)
27
28 Section RationalStreamSum.
29
30 Context `{AppRationals AQ}.
31
32 (* For exponential, f p n d := (n*a, d*p).
33 We might need to generalize positive to a more complicated
34 state type later. *)
35 Variable f : positive*(AQ*AQ) -> AQ*AQ.
36 Definition fS x : positive*(AQ*AQ) := (Pos.succ (fst x), f x).
37 Definition fSsum (k:Z) (x : positive*(AQ*AQ)*AQ) : positive*(AQ*AQ)*AQ
38 := let (y,s) := x in
39 let (a,b) := fS y in
40 (a, b, s + app_div (fst b) (snd b) k).
41
42 Hypothesis denomPos : forall x, 0 < snd (snd x) -> 0 < snd (f x).
43
44 Lemma denomPos_iter : forall p x,
45 0 < snd (snd x) ->
46 0 < snd (snd (CRstreams.iterate _ fS p x)).
47 Proof.
48 apply (Pos.peano_ind (fun p => forall x,
49 0 < snd (snd x) ->
50 0 < snd (snd (CRstreams.iterate _ fS p x)))).
51 - intros. simpl. apply denomPos, H5.
52 - intros. rewrite iterate_succ, iterate_shift.
53 apply H5. simpl.
54 apply denomPos, H6.
55 Qed.
56
57 (* Find first index where num/denom <= e. *)
58 Definition IsStopIndex x (e : AQ) (candidate : positive) : Prop
59 := let (_,v) := CRstreams.iterate _ fS candidate (xH,x) in
60 le (abs (fst v)) (snd v * e).
61 Definition StopIndex x (e : AQ) (candidate : positive) : positive
62 := Pos.pred (fst (iterate_stop
63 _ fS (fun y : positive*(AQ*AQ)
64 => bool_decide_rel le (abs (fst (snd y))) ((snd (snd y))*e))
65 candidate (xH, x))).
66
67 Lemma fS_fst : forall (p:positive) x,
68 fst (CRstreams.iterate (positive and AQ and AQ) fS p (1%positive, x))
69 ≡ Pos.succ p.
70 Proof.
71 apply (Pos.peano_ind (fun p => forall (x : AQ and AQ),
72 fst (CRstreams.iterate (positive and AQ and AQ) fS p (1%positive, x)) ≡ Pos.succ p)).
73 - reflexivity.
74 - intros. rewrite iterate_succ. simpl.
75 apply f_equal, H5.
76 Qed.
77
78 Lemma StopIndex_correct : forall x (e:AQ) (p r : positive),
79 IsStopIndex x e p
80 -> (forall q:positive, Pos.lt q p -> ~IsStopIndex x e q)
81 -> Pos.le p r
82 -> StopIndex x e r ≡ p.
83 Proof.
84 unfold IsStopIndex. intros.
85 unfold StopIndex.
86 destruct (iterate_stop_correct
87 _ fS (fun y : positive and AQ and AQ =>
88 bool_decide_rel
89 le (abs (fst (snd y))) (snd (snd y) * e0))
90 r (xH,x)) as [s [req [H8 H9]]].
91 rewrite req, fS_fst, Pos.pred_succ. clear req.
92 destruct H9.
93 - subst r. apply Pos.le_lteq in H7.
94 destruct H7. 2: symmetry; exact H7.
95 exfalso. specialize (H8 p H7).
96 apply bool_decide_rel_false in H8.
97 contradict H8.
98 destruct (CRstreams.iterate _ fS p (1%positive, x)).
99 exact H5.
100 - destruct H9.
101 apply bool_decide_rel_true in H10.
102 clear H7 H9 r.
103 destruct (Pos.lt_total s p).
104 + exfalso. specialize (H6 s H7).
105 contradict H6.
106 destruct (CRstreams.iterate _ fS s (1%positive, x)).
107 exact H10.
108 + destruct H7. exact H7. exfalso.
109 specialize (H8 p H7).
110 apply bool_decide_rel_false in H8.
111 contradict H8.
112 destruct (CRstreams.iterate _ fS p (1%positive, x)).
113 exact H5.
114 Qed.
115
116 Lemma StopIndex_stop_fuel : forall x (e:AQ) (candidate : positive),
117 (forall p:positive, Pos.lt p candidate -> ~IsStopIndex x e p)
118 -> StopIndex x e candidate ≡ candidate.
119 Proof.
120 intros. unfold StopIndex.
121 destruct (iterate_stop_correct
122 _ fS (fun y : positive and AQ and AQ =>
123 bool_decide_rel
124 le (abs (fst (snd y))) (snd (snd y) * e0))
125 candidate (xH,x)) as [r [req [H6 H7]]].
126 rewrite req, fS_fst, Pos.pred_succ. clear req.
127 destruct H7. symmetry. exact H7.
128 destruct H7. exfalso. clear H6.
129 specialize (H5 r H7).
130 apply bool_decide_rel_true in H8.
131 contradict H5.
132 unfold IsStopIndex.
133 destruct (CRstreams.iterate _ fS r (1%positive, x)).
134 exact H8.
135 Qed.
136
137 (* Approximate the infinite series at precision e.
138 The precision i:Z in fSum satisfies n*2^i <= e/2. *)
139 Definition app_inverse_below (q : Qpos) : AQ
140 := AppInverse0 ((3#4)*proj1_sig q) ((1#4)*q)%Qpos.
141
142 Lemma app_inverse_below_pos : forall q:Qpos, 0 < app_inverse_below q.
143 Proof.
144 intros. unfold app_inverse_below.
145 destruct aq_dense_embedding.
146 specialize (dense_inverse ((3 # 4) * ` q)%Q ((1#4)*q)%Qpos).
147 apply AbsSmall_Qabs, Qabs_Qle_condition in dense_inverse.
148 destruct dense_inverse as [H5 _].
149 simpl in H5.
150 apply (Qplus_le_r _ _ ((3 # 4) * ` q)) in H5.
151 ring_simplify in H5.
152 destruct aq_strict_order_embed.
153 apply strict_order_embedding_reflecting.
154 refine (Qlt_le_trans _ ((8 # 16) * ` q) _ _ H5).
155 rewrite rings.preserves_0.
156 apply (Qpos_ispos ((8#16)*q)).
157 Qed.
158
159 Lemma app_inverse_below_correct : forall q:Qpos,
160 AQtoQ (app_inverse_below q) <= proj1_sig q.
161 Proof.
162 intros. unfold app_inverse_below.
163 destruct aq_dense_embedding.
164 specialize (dense_inverse ((3 # 4) * ` q)%Q ((1#4)*q)%Qpos).
165 apply AbsSmall_Qabs, Qabs_Qle_condition in dense_inverse.
166 destruct dense_inverse as [_ H5].
167 simpl in H5.
168 apply (Qplus_le_r _ _ ((3 # 4) * ` q)) in H5.
169 ring_simplify in H5. exact H5.
170 Qed.
171
172 (* cvmod : AQ->positive would not improve this definition, because an
173 AQtoQ would be almost inevitable to produce a boxed positive.
174 Besides, Q will allow an easier interaction with fast reals streams. *)
175 Definition AltSeries_raw (x : AQ*AQ) (cvmod : Qpos -> positive) (e:QposInf) : AQ
176 := match e with
177 | Qpos2QposInf d
178 => let ae := app_inverse_below (d*(1#2)) in
179 let n := StopIndex x ae (cvmod (d * (1#2))%Qpos) in
180 snd (CRstreams.iterate _ (fSsum (Qdlog2 (proj1_sig d * (1#2*n)))) n (xH,x,0))
181 | QposInfinity => 0
182 end.
183
184 (* To prove the correctness of the limit, convert the stream f into
185 a stream g of exact rationals. g could be defined as the zip of
186 f with the exact divisions, but it's more flexible to take g from
187 outside, so that in addition we prove the equality of series. *)
188 Variable X : Type.
189 Variable g : X*Q -> X*Q.
190 Variable fInit : AQ*AQ.
191 Variable gInit : X*Q.
192
193 Hypothesis g_pth : forall p:positive,
194 Str_pth _ g p gInit
195 == let (y,r) := CRstreams.iterate _ fS p (xH, fInit) in
196 AQtoQ (fst r) / AQtoQ (snd r).
197
198 Lemma abs_div_aqtoq_shift : forall (q r s : AQ),
199 0 < r ->
200 (Qabs (AQtoQ q / AQtoQ r) <= AQtoQ s
201 <-> le (abs q) (r * s)).
202 Proof.
203 assert (forall q:AQ, Qabs (AQtoQ q) == AQtoQ (abs q)) as preserves_abs.
204 { intros. rewrite abs.preserves_abs. reflexivity. }
205 assert (forall q r:AQ, AQtoQ (q*r) == AQtoQ q*AQtoQ r) as preserves_mult.
206 { intros. rewrite rings.preserves_mult. reflexivity. }
207 intros.
208 assert (0 < AQtoQ r).
209 { rewrite <- rings.preserves_0.
210 destruct aq_strict_order_embed.
211 apply strict_order_embedding_preserving. exact H5. }
212 split.
213 - intros. unfold Qdiv in H7.
214 rewrite Qabs_Qmult, Q.Qabs_Qinv in H7.
215 rewrite (Qabs_pos (AQtoQ r)) in H7.
216 rewrite preserves_abs, Qmult_comm in H7.
217 apply (Qmult_le_l _ _ (AQtoQ r)) in H7.
218 2: exact H6.
219 rewrite Qmult_assoc, Qmult_inv_r, Qmult_1_l in H7.
220 rewrite <- preserves_mult in H7.
221 destruct aq_order_embed, order_embedding_reflecting.
222 apply order_reflecting in H7.
223 exact H7.
224 intro abs. rewrite abs in H6. exact (Qlt_irrefl 0 H6).
225 apply Qlt_le_weak, H6.
226 - intros. unfold Qdiv.
227 rewrite Qabs_Qmult, Q.Qabs_Qinv.
228 rewrite (Qabs_pos (AQtoQ r)).
229 rewrite preserves_abs.
230 rewrite Qmult_comm.
231 apply (Qmult_le_l _ _ (AQtoQ r)).
232 exact H6.
233 rewrite Qmult_assoc, Qmult_inv_r, Qmult_1_l.
234 rewrite <- preserves_mult.
235 destruct aq_order_embed.
236 apply order_embedding_preserving.
237 exact H7.
238 intro abs. rewrite abs in H6. exact (Qlt_irrefl 0 H6).
239 apply Qlt_le_weak, H6.
240 Qed.
241
242 Lemma fSsum_fst : forall p k,
243 fst (CRstreams.iterate _ (fSsum k) p (1%positive, fInit, 0))
244 ≡ CRstreams.iterate _ fS p (xH,fInit).
245 Proof.
246 apply (Pos.peano_ind (fun p => forall k,
247 fst (CRstreams.iterate _ (fSsum k) p (1%positive, fInit, 0))
248 ≡ CRstreams.iterate _ fS p (xH,fInit))).
249 - reflexivity.
250 - intros. rewrite iterate_succ, iterate_succ.
251 rewrite <- (H5 k). unfold fSsum at 1.
252 destruct (CRstreams.iterate ((positive and AQ and AQ) and AQ)
253 (fSsum k) p (1%positive, fInit, 0)).
254 reflexivity.
255 Qed.
256
257 (* Sum p terms, the error between each is below e. *)
258 Lemma div_approx_error : ∀ (p:positive) (e:Qpos),
259 Qball (` e * inject_Z (Zpos p))
260 (AQtoQ (snd (CRstreams.iterate
261 _ (fSsum (Qdlog2 (` e))) p (1%positive, fInit, 0))))
262 (snd (CRstreams.iterate
263 _ (fun y : X*Q*Q =>
264 let (z, r) := g (fst y) in (z, r, Qred (r + snd y))) p
265 (gInit, 0))).
266 Proof.
267 apply (Pos.peano_ind (fun p => forall (e:Qpos),
268 Qball (` e * inject_Z (Zpos p))
269 (AQtoQ (snd (CRstreams.iterate
270 _ (fSsum (Qdlog2 (` e))) p (1%positive, fInit, 0))))
271 (snd (CRstreams.iterate
272 _ (fun y : X*Q*Q =>
273 let (z, r) := g (fst y) in (z, r, Qred (r + snd y))) p
274 (gInit, 0))))).
275 - intros. rewrite iterate_one, iterate_one.
276 rewrite Qmult_1_r.
277 unfold fSsum, fS.
278 unfold snd at 1. unfold fst at 2.
279 pose proof (g_pth 1).
280 unfold Str_pth in H5. simpl in H5.
281 unfold snd at 3.
282 replace (snd (let (z, r) := g gInit in (z, r, Qred (r + zero))))
283 with (Qred (snd (g gInit) + 0))
284 by (destruct (g gInit); reflexivity).
285 rewrite Qred_correct, Qplus_0_r, H5.
286 clear H5.
287 destruct (f (1%positive, fInit)) as [u v].
288 unfold snd, fst.
289 rewrite rings.plus_0_l.
290 apply ball_weak_le with (e:= (2 ^ Qdlog2 (` e0))%Q).
291 apply Qdlog2_spec, Qpos_ispos.
292 apply aq_div.
293 - intros.
294 rewrite iterate_succ.
295 unfold fSsum at 1.
296 specialize (H5 e0).
297 pose proof (fSsum_fst p (Qdlog2 (` e0))).
298 destruct (CRstreams.iterate _ (fSsum (Qdlog2 (` e0))) p (1%positive, fInit, 0))
299 as [u approx_sum].
300 unfold snd in H5 at 1.
301 unfold fst in H6.
302 change (snd
303 (let (a, b) := fS u in (a, b, approx_sum + app_div (fst b) (snd b) (Qdlog2 (` e0)))))
304 with (approx_sum + app_div (fst (snd (fS u))) (snd (snd (fS u))) (Qdlog2 (` e0))).
305 rewrite iterate_succ, SumStream_fst_red.
306 unfold fst at 2.
307 rewrite <- iterate_succ.
308 pose proof (g_pth (Pos.succ p)) as H7.
309 unfold Str_pth in H7.
310 destruct (CRstreams.iterate (X and Q) g (Pos.succ p) gInit).
311 unfold snd at 4. unfold snd in H7 at 1.
312 rewrite Qred_correct, H7. clear H7 q x.
313 rewrite iterate_succ.
314 rewrite <- H6. clear H6.
315 destruct (fS u) as [v w].
316 change (snd (v,w)) with w.
317 clear v.
318 destruct (CRstreams.iterate _
319 (fun y : (X and Q) and Q =>
320 let (z, r) := g (fst y) in (z, r, Qred (r + snd y))) p
321 (gInit, 0))
322 as [v exact_sum].
323 unfold snd in H5.
324 unfold snd at 3. clear v.
325 destruct w as [v w].
326 unfold fst, snd.
327 rewrite rings.preserves_plus.
328 apply AbsSmall_Qabs.
329 apply AbsSmall_Qabs in H5.
330 setoid_replace ((AQtoQ approx_sum + AQtoQ (app_div v w (Qdlog2 (` e0)))) -
331 (AQtoQ v / AQtoQ w + exact_sum))%Q
332 with (AQtoQ approx_sum - exact_sum
333 + (AQtoQ (app_div v w (Qdlog2 (` e0))) - (AQtoQ v / AQtoQ w)))%Q
334 by ring.
335 apply (Qle_trans _ _ _ (Qabs_triangle _ _)).
336 rewrite <- Pos.add_1_r, Pos2Z.inj_add, inject_Z_plus.
337 rewrite Qmult_plus_distr_r, Qmult_1_r.
338 apply Qplus_le_compat. exact H5.
339 apply AbsSmall_Qabs.
340 change (Qball (` e0) (AQtoQ (app_div v w (Qdlog2 (` e0)))) (AQtoQ v / AQtoQ w)).
341 apply ball_weak_le with (e:= (2 ^ Qdlog2 (` e0))%Q).
342 apply Qdlog2_spec, Qpos_ispos.
343 apply aq_div.
344 Qed.
345
346 (* SumStream is the implementation of CRAlternatingSum.AltSeries_raw.
347 Errors only come from approximate divisions here. *)
348 Lemma AltSeries_raw_correct : forall (e:Qpos) (cvmod : Qpos -> positive),
349 0 < snd fInit ->
350 Qball (` e * (1 # 2))
351 (AQtoQ (AltSeries_raw fInit cvmod (Qpos2QposInf e)))
352 (SumStream
353 _ g gInit
354 (cvmod (e * (1 # 2))%Qpos) (* fuel *)
355 (AQposAsQpos (exist _ _ (app_inverse_below_pos (e * (1 # 2))%Qpos)))).
356 Proof.
357 intros e0 cvmod xpos.
358 unfold SumStream.
359 change (` (AQposAsQpos
360 (app_inverse_below (e0 * (1 # 2))%Qpos
361 ↾ app_inverse_below_pos (e0 * (1 # 2))%Qpos)))
362 with (AQtoQ (app_inverse_below (e0 * (1 # 2))%Qpos)).
363 pose proof (iterate_stop_correct
364 _ (fun y : (X and Q) and Q =>
365 let (z, r) := g (fst y) in (z, r, Qred (r + snd y)))
366 (fun y : (X and Q) and Q =>
367 Qle_bool (Qabs (snd (fst y)))
368 (AQtoQ (app_inverse_below (e0 * (1 # 2) ↾ eq_refl))))
369 (cvmod (e0 * (1 # 2))%Qpos) (gInit,0))
370 as [p [qeq [H5 H6]]].
371 rewrite qeq. clear qeq.
372 unfold AltSeries_raw.
373 replace (StopIndex fInit (app_inverse_below (e0 * (1 # 2) ↾ eq_refl))
374 (cvmod (e0 * (1 # 2))%Qpos))
375 with p.
376 setoid_replace (` e0 * (1 # 2))%Q
377 with (` e0 * (1 # 2 * p) * inject_Z (Zpos p))%Q.
378 apply (div_approx_error p (e0*(1#2*p))).
379 rewrite <- Qmult_assoc. apply Qmult_comp. reflexivity.
380 unfold Qmult, Qeq; simpl.
381 rewrite Pos.mul_1_r, Pos.mul_comm. reflexivity.
382 rewrite SumStream_fst_red in H6.
383 destruct H6 as [fuel | predicate].
384 - (* The sum consumes all the fuel. *)
385 subst p.
386 symmetry. apply StopIndex_stop_fuel.
387 intros. specialize (H5 p H6).
388 rewrite SumStream_fst_red in H5.
389 unfold fst in H5.
390 unfold IsStopIndex. intro abs.
391 pose proof (g_pth p). unfold Str_pth in H7.
392 rewrite H7 in H5. clear H7.
393 pose proof (denomPos_iter p (xH,fInit) xpos).
394 destruct (CRstreams.iterate _ fS p (1%positive, fInit))
395 as [u v].
396 apply abs_div_aqtoq_shift in abs.
397 apply Qle_bool_iff in abs.
398 rewrite abs in H5. discriminate.
399 exact H7.
400 - (* The sum stops before the fuel, because of the predicate. *)
401 assert (IsStopIndex fInit (app_inverse_below (e0 * (1 # 2))%Qpos) p) as pstop.
402 { destruct predicate as [_ predicate]. unfold IsStopIndex.
403 apply Qle_bool_iff in predicate.
404 simpl in predicate.
405 pose proof (g_pth p).
406 unfold Str_pth in H6. rewrite H6 in predicate. clear H6.
407 pose proof (denomPos_iter p (xH,fInit) xpos).
408 destruct (CRstreams.iterate _ fS p (1%positive, fInit)).
409 apply abs_div_aqtoq_shift. exact H6.
410 exact predicate. }
411 symmetry. apply StopIndex_correct.
412 exact pstop. intros.
413 unfold IsStopIndex.
414 specialize (H5 q H6).
415 rewrite SumStream_fst_red in H5. unfold fst in H5.
416 pose proof (g_pth q).
417 unfold Str_pth in H7. rewrite H7 in H5. clear H7.
418 pose proof (denomPos_iter q (xH,fInit) xpos).
419 destruct (CRstreams.iterate _ fS q (1%positive, fInit)).
420 intro abs.
421 apply abs_div_aqtoq_shift in abs.
422 apply Qle_bool_iff in abs.
423 rewrite abs in H5. discriminate.
424 exact H7. apply Pos.lt_le_incl, predicate.
425 Qed.
426
427 Lemma AltSeries_raw_prf : forall (cvmod : Qpos -> positive),
428 Str_alt_decr _ g gInit
429 -> 0 < snd fInit
430 -> Limit_zero _ g gInit cvmod ->
431 is_RegularFunction (@ball AQ_as_MetricSpace) (AltSeries_raw fInit cvmod).
432 Proof.
433 intros cvmod g_decr xpos lz e1 e2.
434 setoid_replace (`e1 + `e2)%Q
435 with (`e1*(1#2) + (`e1*(1#2) + `e2*(1#2) + `e2*(1#2)))%Q by ring.
436 apply (ball_triangle Q_as_MetricSpace _ _ _
437 (SumStream
438 _ g gInit
439 (cvmod (e1 * (1 # 2))%Qpos)
440 (AQposAsQpos (exist _ _ (app_inverse_below_pos (e1 * (1 # 2))%Qpos))))).
441 2: apply (ball_triangle Q_as_MetricSpace _ _ _
442 (SumStream
443 _ g gInit
444 (cvmod (e2 * (1 # 2))%Qpos)
445 (AQposAsQpos (exist _ _ (app_inverse_below_pos (e2 * (1 # 2))%Qpos))))).
446 - exact (AltSeries_raw_correct _ _ xpos).
447 - apply (AltSeries_further
448 _ g gInit _ _ _ _
449 (e1 * (1 # 2))%Qpos (e2 * (1 # 2))%Qpos g_decr).
450 apply lz. apply lz.
451 apply app_inverse_below_correct.
452 apply app_inverse_below_correct.
453 - apply ball_sym, (AltSeries_raw_correct _ _ xpos).
454 Qed.
455
456 Definition AltSeries (cvmod : Qpos -> positive)
457 (decr : Str_alt_decr _ g gInit)
458 (xpos : 0 < snd fInit)
459 (lz : Limit_zero _ g gInit cvmod) : msp_car AR
460 := Build_RegularFunction (AltSeries_raw_prf cvmod decr xpos lz).
461
462 Lemma AltSeries_correct : forall (cvmod : Qpos -> positive)
463 (decr : Str_alt_decr _ g gInit)
464 (xpos : 0 < snd fInit)
465 (lz : Limit_zero _ g gInit cvmod),
466 (ARtoCR (AltSeries cvmod decr xpos lz)
467 == CRAlternatingSum.AltSeries _ g gInit cvmod decr lz)%CR.
468 Proof.
469 intros.
470 apply regFunEq_equiv, regFunEq_e.
471 intro d.
472 setoid_replace (` d + ` d)%Q with (`d*(1#2) + (`d*(1#2)+` d))%Q by ring.
473 apply (ball_triangle _ _ _ _ _ _ (AltSeries_raw_correct d cvmod xpos)).
474 apply (AltSeries_further
475 _ g gInit
476 (cvmod (d * (1 # 2))%Qpos) (cvmod d)
477 _ _ (d*(1#2))%Qpos d decr).
478 apply lz. apply lz.
479 apply app_inverse_below_correct.
480 apply Qle_refl.
481 Qed.
482
483 End RationalStreamSum.