| 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 |
From Coq Require Import ArithRing. |
| 23 |
From Coq Require Import Bool. |
| 24 |
From Coq Require Import ZArith. |
| 25 |
From Coq Require Import Qpower Qabs. |
| 26 |
Require Import CoRN.algebra.RSetoid. |
| 27 |
Require Import CoRN.metric2.Metric. |
| 28 |
Require Import CoRN.metric2.UniformContinuity. |
| 29 |
Require Export CoRN.reals.fast.CRArith. |
| 30 |
Require Export CoRN.model.metric2.Qmetric. |
| 31 |
Require Import CoRN.reals.fast.LazyNat. |
| 32 |
Require Import CoRN.reals.fast.CRstreams. |
| 33 |
Require Export CoRN.metric2.Limit. |
| 34 |
Require Import CoRN.model.totalorder.QposMinMax. |
| 35 |
Require Import CoRN.classes.Qclasses. |
| 36 |
Require Import MathClasses.interfaces.abstract_algebra. |
| 37 |
|
| 38 |
Opaque CR. |
| 39 |
|
| 40 |
(** |
| 41 |
** Computing Alternating Series. |
| 42 |
Alternating series are particularly nice to sum because each term is also |
| 43 |
a bound on the error of the partial sum. |
| 44 |
*) |
| 45 |
|
| 46 |
Section RationalStreamSum. |
| 47 |
Variable X : Type. |
| 48 |
|
| 49 |
(* The current rational value is part of the state. For example a^k/k! is |
| 50 |
used to produce a^(k+1)/(k+1)! by multiplying by a and dividing |
| 51 |
by k+1. *) |
| 52 |
Variable f : X*Q -> X*Q. |
| 53 |
|
| 54 |
Definition Str_pth (p : positive) (x:X*Q) : Q |
| 55 |
:= snd (CRstreams.iterate _ f p x). |
| 56 |
|
| 57 |
(* Decreasing and alternating stream. *) |
| 58 |
Definition Str_alt_decr (x:X*Q) : Prop |
| 59 |
:= forall p : positive, |
| 60 |
Qabs (Str_pth (Pos.succ p) x) <= Qabs (Str_pth p x) |
| 61 |
/\ (Str_pth (Pos.succ p) x)*(Str_pth p x) <= 0. |
| 62 |
|
| 63 |
Lemma Str_alt_decr_tl : forall x p, |
| 64 |
Str_alt_decr x -> Str_alt_decr (CRstreams.iterate _ f p x). |
| 65 |
Proof. |
| 66 |
assert (forall x, Str_alt_decr x -> Str_alt_decr (f x)). |
| 67 |
{ intros x H p. |
| 68 |
specialize (H (Pos.succ p)). |
| 69 |
unfold Str_pth. |
| 70 |
unfold Str_pth in H. |
| 71 |
rewrite <- iterate_shift, <- iterate_succ. |
| 72 |
rewrite <- iterate_shift, <- iterate_succ. |
| 73 |
apply H. } |
| 74 |
intros x p. revert p x. |
| 75 |
apply (Pos.peano_ind (fun p => forall (x : X * Q), |
| 76 |
Str_alt_decr x → Str_alt_decr (CRstreams.iterate (X * Q) f p x))). |
| 77 |
- intros. simpl. apply H, H0. |
| 78 |
- intros. rewrite iterate_succ. apply H, H0, H1. |
| 79 |
Qed. |
| 80 |
|
| 81 |
Lemma Str_alt_even_step : forall p x, |
| 82 |
Str_alt_decr x -> |
| 83 |
0 <= Str_pth p x * Str_pth (p+2) x. |
| 84 |
Proof. |
| 85 |
intros. pose proof (H p). pose proof (H (Pos.succ p)). |
| 86 |
destruct H0, H1. |
| 87 |
replace (p+2)%positive with (Pos.succ (Pos.succ p)). |
| 88 |
destruct (Str_pth p x). |
| 89 |
destruct (Str_pth (Pos.succ p) x). |
| 90 |
destruct (Str_pth (Pos.succ (Pos.succ p)) x). |
| 91 |
unfold Qmult, Qle; simpl. rewrite Z.mul_1_r. |
| 92 |
unfold Qmult, Qle in H2; simpl in H2. rewrite Z.mul_1_r in H2. |
| 93 |
unfold Qmult, Qle in H3; simpl in H3. rewrite Z.mul_1_r in H3. |
| 94 |
destruct Qnum, Qnum1; try discriminate. |
| 95 |
destruct Qnum0. |
| 96 |
exfalso; apply H1; reflexivity. |
| 97 |
exfalso; apply H2; reflexivity. |
| 98 |
exfalso; apply H3; reflexivity. |
| 99 |
destruct Qnum0. |
| 100 |
exfalso; apply H1; reflexivity. |
| 101 |
exfalso; apply H3; reflexivity. |
| 102 |
exfalso; apply H2; reflexivity. |
| 103 |
rewrite <- Pos.add_1_r, <- Pos.add_1_r. |
| 104 |
rewrite <- Pos.add_assoc. reflexivity. |
| 105 |
Qed. |
| 106 |
|
| 107 |
Lemma Str_alt_zero : forall p x, |
| 108 |
Str_alt_decr x -> |
| 109 |
Str_pth p x == 0 -> Str_pth (Pos.succ p) x == 0. |
| 110 |
Proof. |
| 111 |
intros. pose proof (H p) as [H1 _]. |
| 112 |
rewrite H0 in H1. |
| 113 |
apply Qabs_Qle_condition in H1. destruct H1. |
| 114 |
apply (Qle_antisym _ _ H2) in H1. exact H1. |
| 115 |
Qed. |
| 116 |
|
| 117 |
Lemma Str_alt_neg : forall p x, |
| 118 |
Str_alt_decr x -> 0 <= snd (f x) -> Str_pth (p~0) x <= 0. |
| 119 |
Proof. |
| 120 |
apply (Pos.peano_ind (fun p => forall (x : X * Q), |
| 121 |
Str_alt_decr x → 0 <= snd (f x) → |
| 122 |
Str_pth (p~0) x <= 0)). |
| 123 |
- intros. simpl. specialize (H xH). |
| 124 |
unfold Str_pth in H. simpl in H. destruct H. |
| 125 |
destruct (Q_dec (snd (f x)) 0). |
| 126 |
destruct s. |
| 127 |
exfalso; exact (Qlt_not_le _ _ q H0). |
| 128 |
rewrite <- (Qmult_0_l (snd (f x))) in H1. |
| 129 |
apply Qmult_le_r in H1. exact H1. exact q. |
| 130 |
rewrite q in H. |
| 131 |
exact (Qle_trans _ _ _ (Qle_Qabs _) H). |
| 132 |
- intros. pose proof (Str_alt_even_step (p~0) x H0). |
| 133 |
specialize (H x H0 H1). |
| 134 |
replace (p~0+2)%positive with ((Pos.succ p)~0)%positive in H2. |
| 135 |
apply Qnot_lt_le. intro abs. |
| 136 |
rewrite <- (Qmult_0_l (Str_pth ((Pos.succ p)~0) x)) in H2. |
| 137 |
apply Qmult_le_r in H2. 2: exact abs. |
| 138 |
apply (Qle_antisym _ _ H) in H2. clear H. |
| 139 |
apply (Str_alt_zero _ _ H0) in H2. |
| 140 |
apply (Str_alt_zero _ _ H0) in H2. |
| 141 |
rewrite <- Pos.double_succ in H2. |
| 142 |
rewrite H2 in abs. exact (Qlt_irrefl 0 abs). |
| 143 |
rewrite Pos.double_succ. |
| 144 |
rewrite <- Pos.add_1_r, <- Pos.add_1_r, <- Pos.add_assoc. reflexivity. |
| 145 |
Qed. |
| 146 |
|
| 147 |
Lemma Str_alt_pos : forall p x, |
| 148 |
Str_alt_decr x -> |
| 149 |
0 <= snd (f x) -> |
| 150 |
0 <= snd (CRstreams.iterate (X * Q) f p~1 x). |
| 151 |
Proof. |
| 152 |
intros. |
| 153 |
rewrite Pos.xI_succ_xO. |
| 154 |
pose proof (Str_alt_neg p x H H0). |
| 155 |
specialize (H (p~0))%positive. |
| 156 |
unfold Str_pth in H. destruct H. |
| 157 |
destruct (Q_dec 0 (snd (CRstreams.iterate (X * Q) f p~0 x))). |
| 158 |
destruct s. |
| 159 |
exfalso; exact (Qlt_not_le _ _ q H1). |
| 160 |
apply Qopp_le_compat in H2. |
| 161 |
change (-0)%Q with 0%Q in H2. |
| 162 |
setoid_replace (- (snd (CRstreams.iterate (X * Q) f (Pos.succ p~0) x) * |
| 163 |
snd (CRstreams.iterate (X * Q) f p~0 x)))%Q |
| 164 |
with ( (snd (CRstreams.iterate (X * Q) f (Pos.succ p~0) x) * |
| 165 |
-snd (CRstreams.iterate (X * Q) f p~0 x)))%Q in H2 |
| 166 |
by (unfold equiv, Q_eq; ring). |
| 167 |
rewrite <- (Qmult_0_l (-snd (CRstreams.iterate (X * Q) f p~0 x))) in H2. |
| 168 |
apply Qmult_le_r in H2. exact H2. |
| 169 |
rewrite <- (Qplus_0_l (- snd (CRstreams.iterate (X * Q) f p~0 x))). |
| 170 |
rewrite <- Qlt_minus_iff. exact q. |
| 171 |
rewrite <- q in H. |
| 172 |
apply Qabs_Qle_condition in H. apply H. |
| 173 |
Qed. |
| 174 |
|
| 175 |
Definition Limit_zero x (cvmod : Qpos -> positive) : Prop |
| 176 |
:= forall q:Qpos, Qabs (Str_pth (cvmod q) x) <= proj1_sig q. |
| 177 |
|
| 178 |
Lemma Limit_zero_tl : forall x (cvmod : Qpos -> positive) (p : positive), |
| 179 |
Str_alt_decr x -> |
| 180 |
Limit_zero x cvmod -> Limit_zero (CRstreams.iterate _ f p x) |
| 181 |
(fun e => cvmod e - p)%positive. |
| 182 |
Proof. |
| 183 |
intros. intro e. |
| 184 |
unfold Str_pth. |
| 185 |
rewrite <- iterate_add. |
| 186 |
assert (forall q:positive, |
| 187 |
Qabs (snd (CRstreams.iterate (X * Q) f (q+cvmod e) x)) <= ` e). |
| 188 |
{ apply Pos.peano_ind. |
| 189 |
- intros. rewrite Pos.add_1_l. |
| 190 |
apply (Qle_trans _ (Qabs (snd (CRstreams.iterate (X * Q) f (cvmod e) x)))). |
| 191 |
apply H. apply H0. |
| 192 |
- intros. |
| 193 |
rewrite <- Pos.add_1_l, <- Pos.add_assoc, Pos.add_1_l. |
| 194 |
refine (Qle_trans _ _ _ _ H1). |
| 195 |
apply H. } |
| 196 |
destruct (Pos.lt_total p (cvmod e)). |
| 197 |
2: destruct H2. |
| 198 |
- rewrite Pos.sub_add. apply H0. exact H2. |
| 199 |
- subst p. rewrite Pos.sub_diag. apply H1. |
| 200 |
- rewrite Pos.sub_lt. 2: exact H2. |
| 201 |
replace (1+p)%positive with (1+(p-cvmod e)+cvmod e)%positive. |
| 202 |
apply H1. rewrite <- Pos.add_assoc. |
| 203 |
apply f_equal. rewrite Pos.sub_add. reflexivity. exact H2. |
| 204 |
Qed. |
| 205 |
|
| 206 |
Definition SumStream x (p : positive) (e : Qpos) : Q |
| 207 |
:= snd (iterate_stop |
| 208 |
_ |
| 209 |
(fun y:X*Q*Q => |
| 210 |
let (z,r) := f (fst y) in |
| 211 |
(z, r, Qred (r + snd y))) |
| 212 |
(fun y:X*Q*Q => Qle_bool (Qabs (snd (fst y))) (proj1_sig e)) |
| 213 |
p (x, 0)). |
| 214 |
|
| 215 |
Lemma SumStream_fst : forall p z, |
| 216 |
fst (CRstreams.iterate _ |
| 217 |
(fun y:X*Q*Q => |
| 218 |
let (z,r) := f (fst y) in |
| 219 |
(z, r, r + snd y)) |
| 220 |
p z) |
| 221 |
≡ CRstreams.iterate _ f p (fst z). |
| 222 |
Proof. |
| 223 |
apply (Pos.peano_ind (fun p => forall z : X * Q * Q, |
| 224 |
fst |
| 225 |
(CRstreams.iterate (X * Q * Q) |
| 226 |
(fun y : X * Q * Q => let (z0, r) := f (fst y) in (z0, r, r + snd y)) p z) |
| 227 |
≡ CRstreams.iterate (X * Q) f p (fst z))). |
| 228 |
- intro z. simpl. destruct (f (fst z)); reflexivity. |
| 229 |
- intros. rewrite iterate_succ, H. |
| 230 |
rewrite iterate_succ. |
| 231 |
destruct (f (CRstreams.iterate (X * Q) f p (fst z))). reflexivity. |
| 232 |
Qed. |
| 233 |
|
| 234 |
Lemma SumStream_fst_red : forall p z, |
| 235 |
fst (CRstreams.iterate _ |
| 236 |
(fun y:X*Q*Q => |
| 237 |
let (z,r) := f (fst y) in |
| 238 |
(z, r, Qred (r + snd y))) |
| 239 |
p z) |
| 240 |
≡ CRstreams.iterate _ f p (fst z). |
| 241 |
Proof. |
| 242 |
apply (Pos.peano_ind (fun p => forall z : X * Q * Q, |
| 243 |
fst |
| 244 |
(CRstreams.iterate (X * Q * Q) |
| 245 |
(fun y : X * Q * Q => let (z0, r) := f (fst y) in (z0, r, Qred (r + snd y))) p z) |
| 246 |
≡ CRstreams.iterate (X * Q) f p (fst z))). |
| 247 |
- intro z. simpl. destruct (f (fst z)); reflexivity. |
| 248 |
- intros. rewrite iterate_succ, H. |
| 249 |
rewrite iterate_succ. |
| 250 |
destruct (f (CRstreams.iterate (X * Q) f p (fst z))). reflexivity. |
| 251 |
Qed. |
| 252 |
|
| 253 |
Lemma SumStream_red : forall (p:positive) z, |
| 254 |
snd (CRstreams.iterate _ |
| 255 |
(fun y : X * Q * Q => let (z0, r1) := f (fst y) in (z0, r1, Qred (r1 + snd y))) |
| 256 |
p z) |
| 257 |
== snd (CRstreams.iterate _ |
| 258 |
(fun y : X * Q * Q => let (z0, r1) := f (fst y) in (z0, r1, r1 + snd y)) p z). |
| 259 |
Proof. |
| 260 |
apply (Pos.peano_ind |
| 261 |
(fun p => forall z, snd (CRstreams.iterate _ |
| 262 |
(fun y : X * Q * Q => let (z0, r1) := f (fst y) in (z0, r1, Qred (r1 + snd y))) |
| 263 |
p z) == snd (CRstreams.iterate _ |
| 264 |
(fun y : X * Q * Q => let (z0, r1) := f (fst y) in (z0, r1, r1 + snd y)) p z))). |
| 265 |
- intros. rewrite iterate_one, iterate_one. |
| 266 |
destruct (f (fst z)). apply Qred_correct. |
| 267 |
- intros. rewrite iterate_succ, SumStream_fst_red. |
| 268 |
rewrite iterate_succ, SumStream_fst. |
| 269 |
destruct (f (CRstreams.iterate (X * Q) f p (fst z))). |
| 270 |
unfold snd at 1 4. |
| 271 |
rewrite Qred_correct. |
| 272 |
rewrite H. reflexivity. |
| 273 |
Qed. |
| 274 |
|
| 275 |
Lemma SumStream_init : forall (p:positive) z (r:Q), |
| 276 |
snd (CRstreams.iterate _ |
| 277 |
(fun y : X * Q * Q => let (z0, r1) := f (fst y) in (z0, r1, r1 + snd y)) p |
| 278 |
(z, r)) == |
| 279 |
r + |
| 280 |
snd (CRstreams.iterate _ |
| 281 |
(fun y : X * Q * Q => let (z0, r1) := f (fst y) in (z0, r1, r1 + snd y)) p |
| 282 |
(z, 0)). |
| 283 |
Proof. |
| 284 |
apply (Pos.peano_ind (fun p => forall (z : X * Q) (r : Q), |
| 285 |
snd (CRstreams.iterate (X * Q * Q) |
| 286 |
(fun y : X * Q * Q => let (z0, r1) := f (fst y) in (z0, r1, r1 + snd y)) p |
| 287 |
(z, r)) == r + snd |
| 288 |
(CRstreams.iterate (X * Q * Q) |
| 289 |
(fun y : X * Q * Q => let (z0, r1) := f (fst y) in (z0, r1, r1 + snd y)) p |
| 290 |
(z, 0)))). |
| 291 |
- intros. rewrite iterate_one, iterate_one. |
| 292 |
unfold fst. destruct (f z). unfold snd. |
| 293 |
rewrite Qplus_0_r. apply Qplus_comm. |
| 294 |
- intros. rewrite iterate_succ, SumStream_fst. |
| 295 |
rewrite iterate_succ, SumStream_fst. |
| 296 |
change (fst (z,r)) with z. |
| 297 |
change (fst (z,0)) with z. |
| 298 |
destruct (f (CRstreams.iterate (X * Q) f p z)). |
| 299 |
unfold snd at 1 4. |
| 300 |
rewrite H. |
| 301 |
rewrite (Qplus_comm q), <- Qplus_assoc. |
| 302 |
rewrite <- (Qplus_comm q). reflexivity. |
| 303 |
Qed. |
| 304 |
|
| 305 |
Lemma SumStream_assoc : forall x (p q : positive), |
| 306 |
snd (CRstreams.iterate _ |
| 307 |
(fun y : X * Q * Q => |
| 308 |
let (z, r0) := f (fst y) in (z, r0, r0 + snd y)) |
| 309 |
(p+q) (x,0)) |
| 310 |
== snd (CRstreams.iterate _ |
| 311 |
(fun y : X * Q * Q => |
| 312 |
let (z, r0) := f (fst y) in (z, r0, r0 + snd y)) |
| 313 |
p (x,0)) |
| 314 |
+ snd (CRstreams.iterate _ |
| 315 |
(fun y : X * Q * Q => |
| 316 |
let (z, r0) := f (fst y) in (z, r0, r0 + snd y)) |
| 317 |
q (CRstreams.iterate _ f p x, 0)). |
| 318 |
Proof. |
| 319 |
intros x p. revert p x. |
| 320 |
apply (Pos.peano_ind (fun p => forall x q, |
| 321 |
snd (CRstreams.iterate (X * Q * Q) |
| 322 |
(fun y : X * Q * Q => let (z, r0) := f (fst y) in (z, r0, r0 + snd y)) |
| 323 |
(p + q) (x, 0)) == |
| 324 |
snd (CRstreams.iterate (X * Q * Q) |
| 325 |
(fun y : X * Q * Q => let (z, r0) := f (fst y) in (z, r0, r0 + snd y)) p |
| 326 |
(x, 0)) + |
| 327 |
snd |
| 328 |
(CRstreams.iterate (X * Q * Q) |
| 329 |
(fun y : X * Q * Q => let (z, r0) := f (fst y) in (z, r0, r0 + snd y)) q |
| 330 |
(CRstreams.iterate _ f p x, 0)))). |
| 331 |
- intros x q. |
| 332 |
rewrite Pos.add_comm, iterate_add. |
| 333 |
simpl. |
| 334 |
destruct (f x) as [z r0]. |
| 335 |
rewrite SumStream_init. reflexivity. |
| 336 |
- intros. |
| 337 |
rewrite <- Pos.add_1_r, <- Pos.add_assoc, Pos.add_1_l. |
| 338 |
rewrite H, H. simpl. |
| 339 |
rewrite <- Qplus_assoc. |
| 340 |
apply Qplus_comp. reflexivity. clear H. |
| 341 |
rewrite iterate_add. simpl. |
| 342 |
rewrite <- iterate_shift. |
| 343 |
rewrite <- Pos.add_1_r, iterate_add. simpl. |
| 344 |
destruct (f (CRstreams.iterate (X * Q) f p x)). |
| 345 |
simpl. rewrite SumStream_init. reflexivity. |
| 346 |
Qed. |
| 347 |
|
| 348 |
|
| 349 |
(* Using AltSumF_stop is faster than AltSumF. *) |
| 350 |
Definition AltSeries_raw x (cvmod : Qpos -> positive) (e : QposInf) : Q |
| 351 |
:= match e with |
| 352 |
| Qpos2QposInf d => SumStream x (cvmod d) d |
| 353 |
| QposInfinity => 0 |
| 354 |
end. |
| 355 |
|
| 356 |
Lemma AltSeries_small_pos_even : forall p x, |
| 357 |
Str_alt_decr x -> |
| 358 |
0 <= snd (f x) -> |
| 359 |
0 <= snd |
| 360 |
(CRstreams.iterate (X * Q * Q) |
| 361 |
(fun y : X * Q * Q => let (z, r0) := f (fst y) in (z, r0, r0 + snd y)) |
| 362 |
(p~0) (x, 0)). |
| 363 |
Proof. |
| 364 |
(* Sum of positive terms. *) |
| 365 |
assert (forall x, Str_alt_decr x -> 0 <= snd (f x) -> |
| 366 |
0 <= snd (CRstreams.iterate (X * Q * Q) |
| 367 |
(fun y : X * Q * Q => let (z, r0) := f (fst y) in (z, r0, r0 + snd y)) |
| 368 |
(1 + 1) (x, 0))). |
| 369 |
{ intros. |
| 370 |
pose proof (Str_alt_neg 1 x H H0) as H1. |
| 371 |
unfold Str_pth in H1. simpl in H1. |
| 372 |
specialize (H xH). |
| 373 |
simpl. unfold Str_pth in H. simpl in H. |
| 374 |
destruct (f x); simpl. simpl in H. unfold snd in H0. |
| 375 |
destruct (f (x0,q)); simpl. rewrite Qplus_0_r. |
| 376 |
simpl in H. unfold snd in H1. |
| 377 |
destruct H. |
| 378 |
rewrite Qabs_neg in H. 2: exact H1. |
| 379 |
rewrite Qabs_pos in H. 2: exact H0. |
| 380 |
apply Qle_minus_iff in H. |
| 381 |
rewrite Qopp_involutive, Qplus_comm in H. exact H. } |
| 382 |
apply (Pos.peano_ind (fun p => forall x, Str_alt_decr x -> 0 <= snd (f x) -> |
| 383 |
0 <= snd (CRstreams.iterate (X * Q * Q) |
| 384 |
(fun y : X * Q * Q => let (z, r0) := f (fst y) in (z, r0, r0 + snd y)) |
| 385 |
(p~0) (x, 0)))). |
| 386 |
- intros. exact (H x H0 H1). |
| 387 |
- intros. |
| 388 |
rewrite <- Qplus_0_r. |
| 389 |
rewrite Pos.double_succ, <- Pos.add_1_l, <- Pos.add_1_l. |
| 390 |
rewrite Pos.add_assoc, SumStream_assoc. |
| 391 |
apply Qplus_le_compat. exact (H x H1 H2). |
| 392 |
apply H0. exact (Str_alt_decr_tl x 2 H1). |
| 393 |
rewrite <- iterate_succ. |
| 394 |
exact (Str_alt_pos _ x H1 H2). |
| 395 |
Qed. |
| 396 |
|
| 397 |
Lemma AltSeries_small_neg_even : forall p x, |
| 398 |
Str_alt_decr x -> |
| 399 |
snd (f x) <= 0 -> |
| 400 |
snd (CRstreams.iterate (X * Q * Q) |
| 401 |
(fun y : X * Q * Q => let (z, r0) := f (fst y) in (z, r0, r0 + snd y)) |
| 402 |
(p~0) (x, 0)) <= 0. |
| 403 |
Proof. |
| 404 |
(* Sum of negative terms. *) |
| 405 |
assert (forall x, Str_alt_decr x -> snd (f x) <= 0 -> |
| 406 |
snd (CRstreams.iterate (X * Q * Q) |
| 407 |
(fun y : X * Q * Q => let (z, r0) := f (fst y) in (z, r0, r0 + snd y)) |
| 408 |
(1 + 1) (x, 0)) <= 0). |
| 409 |
{ intros. |
| 410 |
specialize (H xH). |
| 411 |
simpl. unfold Str_pth in H. simpl in H. |
| 412 |
destruct (f x); simpl. simpl in H. unfold snd in H0. |
| 413 |
destruct (f (x0,q)); simpl. rewrite Qplus_0_r. |
| 414 |
simpl in H. destruct H. |
| 415 |
apply (Qplus_le_l _ _ (-q)). |
| 416 |
rewrite <- Qplus_assoc, Qplus_opp_r, Qplus_0_r. |
| 417 |
apply (Qle_trans _ _ _ (Qle_Qabs _)). |
| 418 |
apply (Qle_trans _ _ _ H). |
| 419 |
rewrite Qplus_0_l, Qabs_neg. |
| 420 |
apply Qle_refl. exact H0. } |
| 421 |
apply (Pos.peano_ind (fun p => forall x, Str_alt_decr x -> snd (f x) <= 0 -> |
| 422 |
snd (CRstreams.iterate (X * Q * Q) |
| 423 |
(fun y : X * Q * Q => let (z, r0) := f (fst y) in (z, r0, r0 + snd y)) |
| 424 |
(p~0) (x, 0)) <= 0)). |
| 425 |
- intros. exact (H x H0 H1). |
| 426 |
- intros. |
| 427 |
rewrite <- (Qplus_0_r 0). |
| 428 |
rewrite Pos.double_succ, <- Pos.add_1_l, <- Pos.add_1_l. |
| 429 |
rewrite Pos.add_assoc, SumStream_assoc. |
| 430 |
apply Qplus_le_compat. exact (H x H1 H2). |
| 431 |
apply H0. exact (Str_alt_decr_tl x 2 H1). |
| 432 |
simpl. pose proof (Str_alt_even_step 1 x H1). |
| 433 |
unfold Str_pth in H3. simpl in H3. |
| 434 |
apply Qnot_lt_le. intro abs. |
| 435 |
rewrite <- (Qmult_0_l (snd (f (f (f x))))) in H3. |
| 436 |
apply Qmult_le_r in H3. 2: exact abs. |
| 437 |
apply (Qle_antisym _ _ H2) in H3. clear H2. |
| 438 |
apply (Str_alt_zero 1 _ H1) in H3. |
| 439 |
apply (Str_alt_zero 2 _ H1) in H3. |
| 440 |
unfold Str_pth in H3. simpl in H3. |
| 441 |
rewrite H3 in abs. exact (Qlt_irrefl 0 abs). |
| 442 |
Qed. |
| 443 |
|
| 444 |
Lemma AltSeries_small_pos : forall x (p : positive), |
| 445 |
Str_alt_decr x -> |
| 446 |
0 <= snd (f x) -> |
| 447 |
0 <= snd (CRstreams.iterate (X * Q * Q) |
| 448 |
(fun y : X * Q * Q => let (z, r0) := f (fst y) in (z, r0, r0 + snd y)) |
| 449 |
p (x, 0)) <= snd (f x). |
| 450 |
Proof. |
| 451 |
(* This truncated sum starts at 0, and oscillates around 0 |
| 452 |
while staying in [-e,e]. *) |
| 453 |
(* TODO remove induction. *) |
| 454 |
intros x p. revert p x. |
| 455 |
apply (Pos.peano_ind (fun p => forall x, |
| 456 |
Str_alt_decr x -> |
| 457 |
0 <= snd (f x) -> |
| 458 |
0 <= snd (CRstreams.iterate (X * Q * Q) |
| 459 |
(fun y : X * Q * Q => let (z, r0) := f (fst y) in (z, r0, r0 + snd y)) |
| 460 |
p (x, 0)) <= snd (f x))). |
| 461 |
- intros. simpl. destruct (f x). simpl. |
| 462 |
rewrite Qplus_0_r. split. exact H0. apply Qle_refl. |
| 463 |
- intros. destruct p. |
| 464 |
+ split. rewrite Pos.xI_succ_xO, <- Pos.double_succ. |
| 465 |
exact (AltSeries_small_pos_even _ x H0 H1). |
| 466 |
rewrite <- Pos.add_1_r. |
| 467 |
rewrite SumStream_assoc, iterate_one. |
| 468 |
specialize (H x H0 H1) as [_ H]. |
| 469 |
apply (Qle_trans _ (snd (CRstreams.iterate _ |
| 470 |
(fun y : X * Q * Q => let (z, r0) := f (fst y) in (z, r0, r0 + snd y)) p~1 |
| 471 |
(x, 0)) + 0)). |
| 472 |
2: rewrite Qplus_0_r; exact H. |
| 473 |
apply Qplus_le_r. unfold fst. |
| 474 |
apply (Qle_trans _ (snd (f (CRstreams.iterate (X * Q) f p~1 x)))). |
| 475 |
destruct (f (CRstreams.iterate (X * Q) f p~1 x)). |
| 476 |
simpl. rewrite Qplus_0_r. apply Qle_refl. |
| 477 |
rewrite <- iterate_succ. |
| 478 |
pose proof (Str_alt_neg (Pos.succ p) x H0 H1). |
| 479 |
specialize (H0 (p~1)%positive) as [_ H0]. |
| 480 |
unfold Str_pth in H0. |
| 481 |
exact H2. |
| 482 |
+ split. |
| 483 |
rewrite <- Pos.add_1_r. |
| 484 |
rewrite SumStream_assoc, iterate_one. |
| 485 |
rewrite <- (Qplus_0_r 0). |
| 486 |
apply Qplus_le_compat. |
| 487 |
exact (AltSeries_small_pos_even _ x H0 H1). |
| 488 |
apply (Qle_trans _ (snd (f (CRstreams.iterate (X * Q) f p~0 x)))). |
| 489 |
rewrite <- iterate_succ, <- Pos.xI_succ_xO. |
| 490 |
exact (Str_alt_pos _ x H0 H1). |
| 491 |
unfold fst. |
| 492 |
destruct (f (CRstreams.iterate (X * Q) f p~0 x)). |
| 493 |
simpl. rewrite Qplus_0_r. apply Qle_refl. |
| 494 |
rewrite <- Pos.add_1_l, SumStream_assoc, iterate_one. |
| 495 |
simpl (fst (x,0)). |
| 496 |
rewrite <- (Qplus_0_r (snd (f x))). |
| 497 |
setoid_replace (snd (let (z, r0) := f x in (z, r0, r0 + snd (x, 0)))) |
| 498 |
with (snd (f x)) |
| 499 |
by (destruct (f x); apply Qplus_0_r). |
| 500 |
apply Qplus_le_r. |
| 501 |
apply AltSeries_small_neg_even. |
| 502 |
apply (Str_alt_decr_tl x _ H0). |
| 503 |
rewrite <- iterate_succ. |
| 504 |
apply (Str_alt_neg _ x H0 H1). |
| 505 |
+ pose proof (Str_alt_neg 1 x H0 H1) as sndNeg. |
| 506 |
unfold Str_pth in sndNeg. simpl in sndNeg. |
| 507 |
specialize (H0 xH). |
| 508 |
unfold Str_pth in H0. simpl in H0. |
| 509 |
simpl. destruct (f x). simpl. simpl in H0. |
| 510 |
unfold snd in H1. |
| 511 |
destruct (f (x0,q)). simpl. simpl in H0. |
| 512 |
rewrite Qplus_0_r. |
| 513 |
destruct H0. rewrite (Qabs_pos q) in H0. |
| 514 |
2: exact H1. unfold snd in sndNeg. |
| 515 |
split. |
| 516 |
rewrite Qabs_neg in H0. 2: exact sndNeg. |
| 517 |
rewrite Qle_minus_iff, Qopp_involutive, Qplus_comm in H0. |
| 518 |
exact H0. |
| 519 |
apply (Qle_trans _ (0 + q)). |
| 520 |
apply Qplus_le_l. exact sndNeg. |
| 521 |
rewrite Qplus_0_l. apply Qle_refl. |
| 522 |
Qed. |
| 523 |
|
| 524 |
Lemma AltSeries_small : forall x (p : positive), |
| 525 |
Str_alt_decr x -> |
| 526 |
Qabs (snd |
| 527 |
(CRstreams.iterate (X * Q * Q) |
| 528 |
(fun y : X * Q * Q => let (z, r0) := f (fst y) in (z, r0, r0 + snd y)) |
| 529 |
p (x, 0))) <= Qabs (snd (f x)). |
| 530 |
Proof. |
| 531 |
intros. destruct (Qlt_le_dec (snd (f x)) 0). |
| 532 |
- apply (Pos.peano_case (fun p => Qabs (snd |
| 533 |
(CRstreams.iterate (X * Q * Q) |
| 534 |
(fun y : X * Q * Q => let (z, r0) := f (fst y) in (z, r0, r0 + snd y)) p |
| 535 |
(x, 0))) <= Qabs (snd (f x)))). |
| 536 |
+ simpl. destruct (f x). unfold snd. |
| 537 |
rewrite Qplus_0_r. apply Qle_refl. |
| 538 |
+ assert (0 <= snd (f (f x))) as sndPos. |
| 539 |
{ specialize (H xH) as [_ H]. |
| 540 |
unfold Str_pth in H. simpl in H. |
| 541 |
rewrite <- (Qmult_0_l (-snd (f x))) in H. |
| 542 |
setoid_replace (snd (f (f x)) * snd (f x))%Q |
| 543 |
with (-snd (f (f x)) * -snd (f x))%Q in H. |
| 544 |
apply Qmult_le_r in H. apply (Qopp_le_compat _ 0) in H. |
| 545 |
rewrite Qopp_involutive in H. exact H. |
| 546 |
apply (Qplus_lt_l _ _ (snd (f x))). |
| 547 |
ring_simplify. exact q. |
| 548 |
unfold equiv, Q_eq. simpl. ring. } |
| 549 |
intro n. rewrite <- Pos.add_1_l, SumStream_assoc, iterate_one. |
| 550 |
setoid_replace (snd (let (z, r0) := f (fst (x, 0)) in (z, r0, r0 + snd (x, 0)))) |
| 551 |
with (snd (f x)) |
| 552 |
by (simpl; destruct (f x); apply Qplus_0_r). |
| 553 |
rewrite Qabs_neg, Qabs_neg. |
| 554 |
apply Qopp_le_compat. |
| 555 |
rewrite <- (Qplus_0_r (snd (f x))) at 1. |
| 556 |
apply Qplus_le_r. |
| 557 |
apply AltSeries_small_pos. |
| 558 |
exact (Str_alt_decr_tl x _ H). |
| 559 |
exact sndPos. |
| 560 |
apply Qlt_le_weak, q. |
| 561 |
apply (Qle_trans _ (snd (f x) + snd (f (f x)))). |
| 562 |
apply Qplus_le_r. |
| 563 |
apply AltSeries_small_pos. |
| 564 |
exact (Str_alt_decr_tl x 1 H). |
| 565 |
exact sndPos. |
| 566 |
specialize (H xH) as [H _]. |
| 567 |
unfold Str_pth in H. simpl in H. |
| 568 |
rewrite (Qabs_pos _ sndPos) in H. |
| 569 |
rewrite Qabs_neg in H. |
| 570 |
apply (Qplus_le_r _ _ (snd (f x))) in H. |
| 571 |
rewrite Qplus_opp_r in H. exact H. |
| 572 |
apply Qlt_le_weak, q. |
| 573 |
- pose proof (AltSeries_small_pos x p H q). |
| 574 |
rewrite (Qabs_pos (snd (f x)) q). |
| 575 |
rewrite Qabs_pos. apply H0. apply H0. |
| 576 |
Qed. |
| 577 |
|
| 578 |
Lemma AltSeries_further : forall x (p q : positive) (d1 d2 ε1 ε2 : Qpos), |
| 579 |
Str_alt_decr x |
| 580 |
-> Qabs (Str_pth p x) <= proj1_sig ε1 |
| 581 |
-> Qabs (Str_pth q x) <= proj1_sig ε2 |
| 582 |
-> proj1_sig d1 <= proj1_sig ε1 |
| 583 |
-> proj1_sig d2 <= proj1_sig ε2 |
| 584 |
-> Qball (proj1_sig ε1 + proj1_sig ε2) (SumStream x p d1) (SumStream x q d2). |
| 585 |
Proof. |
| 586 |
(* Because the stopping conditions are satisfied at p and q, |
| 587 |
those positive bounds are useless and the sums will stop at |
| 588 |
prior indices where the terms are less than ε1 and ε2. *) |
| 589 |
intros. |
| 590 |
unfold SumStream. |
| 591 |
(* Replace p by its stopping index r. *) |
| 592 |
pose proof (iterate_stop_correct |
| 593 |
_ |
| 594 |
(fun y : X * Q * Q => let (z, r) := f (fst y) in (z, r, Qred (r + snd y))) |
| 595 |
(fun y : X * Q * Q => Qle_bool (Qabs (snd (fst y))) (` d1)) |
| 596 |
p (x,0)) as [r [req [_ H4]]]. |
| 597 |
rewrite req. clear req. |
| 598 |
assert (Qabs (Str_pth r x) <= proj1_sig ε1) as rstop. |
| 599 |
{ destruct H4. rewrite <- H4. exact H0. |
| 600 |
destruct H4. |
| 601 |
rewrite SumStream_fst_red in H5. |
| 602 |
unfold fst in H5. |
| 603 |
apply Qle_bool_iff in H5. |
| 604 |
exact (Qle_trans _ _ _ H5 H2). } |
| 605 |
clear H4 H2 d1 H0 p. |
| 606 |
rewrite SumStream_red. |
| 607 |
(* Replace q by its stopping index s. *) |
| 608 |
pose proof (iterate_stop_correct |
| 609 |
_ |
| 610 |
(fun y : X * Q * Q => let (z, r) := f (fst y) in (z, r, Qred (r + snd y))) |
| 611 |
(fun y : X * Q * Q => Qle_bool (Qabs (snd (fst y))) (` d2)) |
| 612 |
q (x,0)) as [s [seq [_ H2]]]. |
| 613 |
rewrite seq. clear seq. |
| 614 |
assert (Qabs (Str_pth s x) <= proj1_sig ε2) as sstop. |
| 615 |
{ destruct H2. rewrite <- H0. exact H1. |
| 616 |
destruct H0. |
| 617 |
rewrite SumStream_fst_red in H2. |
| 618 |
unfold fst in H2. |
| 619 |
apply Qle_bool_iff in H2. |
| 620 |
exact (Qle_trans _ _ _ H2 H3). } |
| 621 |
clear H2 H3 d2 H1 q. |
| 622 |
rewrite SumStream_red. |
| 623 |
destruct (Pos.lt_total r s). |
| 624 |
- (* r < s *) |
| 625 |
unfold Qball. |
| 626 |
rewrite <- (Pplus_minus s r). |
| 627 |
2: apply Pos.lt_gt, H0. |
| 628 |
apply AbsSmall_Qabs. |
| 629 |
rewrite (SumStream_assoc x r (s-r)). |
| 630 |
unfold Qminus. |
| 631 |
assert (forall a b : Q, -(a+b) == -a+-b). |
| 632 |
{ intros. ring. } |
| 633 |
rewrite H1, Qplus_assoc, Qplus_opp_r, Qplus_0_l. |
| 634 |
clear H1. rewrite Qabs_opp. |
| 635 |
refine (Qle_trans _ _ _ (AltSeries_small _ _ _) _). |
| 636 |
apply Str_alt_decr_tl, H. |
| 637 |
rewrite <- iterate_succ. |
| 638 |
destruct (H r). |
| 639 |
apply (Qle_trans _ _ _ H1). |
| 640 |
apply (Qle_trans _ (` ε1 + 0)). |
| 641 |
rewrite Qplus_0_r. exact rstop. |
| 642 |
apply Qplus_le_r, Qpos_nonneg. |
| 643 |
- destruct H0. rewrite H0. apply ball_refl, (Qpos_nonneg (ε1 + ε2)). |
| 644 |
(* Now s < r. *) |
| 645 |
unfold Qball. |
| 646 |
rewrite <- (Pplus_minus r s). |
| 647 |
2: apply Pos.lt_gt, H0. |
| 648 |
apply AbsSmall_Qabs. |
| 649 |
rewrite (SumStream_assoc x s (r-s)). |
| 650 |
rewrite Qplus_comm. |
| 651 |
unfold Qminus. |
| 652 |
rewrite <- Qplus_assoc, Qplus_opp_r, Qplus_0_r. |
| 653 |
refine (Qle_trans _ _ _ (AltSeries_small _ _ _) _). |
| 654 |
apply Str_alt_decr_tl, H. |
| 655 |
rewrite <- iterate_succ. |
| 656 |
destruct (H s). |
| 657 |
apply (Qle_trans _ _ _ H1). |
| 658 |
apply (Qle_trans _ (0 + ` ε2)). |
| 659 |
rewrite Qplus_0_l. exact sstop. |
| 660 |
apply Qplus_le_l, Qpos_nonneg. |
| 661 |
Qed. |
| 662 |
|
| 663 |
Lemma AltSeries_raw_prf : forall x cvmod, |
| 664 |
Str_alt_decr x -> Limit_zero x cvmod -> |
| 665 |
is_RegularFunction Qball (AltSeries_raw x cvmod). |
| 666 |
Proof. |
| 667 |
intros x cvmod decr lz ε1 ε2. |
| 668 |
apply AltSeries_further. exact decr. |
| 669 |
apply lz. apply lz. apply Qle_refl. apply Qle_refl. |
| 670 |
Qed. |
| 671 |
|
| 672 |
Definition AltSeries (x:X*Q) cvmod (decr : Str_alt_decr x) lz : CR |
| 673 |
:= Build_RegularFunction (AltSeries_raw_prf x cvmod decr lz). |
| 674 |
|
| 675 |
Lemma SumStream_shift : forall p x e, |
| 676 |
` e < Qabs (snd (f x)) |
| 677 |
-> snd (f x) + SumStream (f x) p e == SumStream x (Pos.succ p) e. |
| 678 |
Proof. |
| 679 |
intros. unfold SumStream. |
| 680 |
pose proof (iterate_stop_correct |
| 681 |
_ |
| 682 |
(fun y : X * Q * Q => let (z, r) := f (fst y) in (z, r, Qred (r + snd y))) |
| 683 |
(fun y : X * Q * Q => Qle_bool (Qabs (snd (fst y))) (` e)) |
| 684 |
p (f x,0)) as [s [seq [H0 H1]]]. |
| 685 |
rewrite seq, SumStream_red. |
| 686 |
pose proof (SumStream_assoc x 1 s) as H2. |
| 687 |
rewrite iterate_one, iterate_one in H2. |
| 688 |
setoid_replace (snd (f x)) |
| 689 |
with (snd (let (z, r0) := f (fst (x, 0)) in (z, r0, r0 + snd (x, 0)))) |
| 690 |
by (simpl; destruct (f x); simpl; rewrite Qplus_0_r; reflexivity). |
| 691 |
rewrite <- H2. clear H2. |
| 692 |
rewrite Pos.add_1_l. |
| 693 |
pose proof (iterate_stop_correct |
| 694 |
_ |
| 695 |
(fun y : X * Q * Q => let (z, r) := f (fst y) in (z, r, Qred (r + snd y))) |
| 696 |
(fun y : X * Q * Q => Qle_bool (Qabs (snd (fst y))) (` e)) |
| 697 |
(Pos.succ p) (x,0)) as [r [req [H2 H3]]]. |
| 698 |
rewrite req, SumStream_red. |
| 699 |
clear req seq. |
| 700 |
assert (r ≢ 1%positive) as rone. |
| 701 |
{ intro abs. clear H2 H0 H1. subst r. |
| 702 |
destruct H3. |
| 703 |
pose proof (Pos.lt_1_succ p). |
| 704 |
rewrite H0 in H1. inversion H1. destruct H0. |
| 705 |
rewrite SumStream_fst_red in H1. |
| 706 |
simpl in H1. apply Qle_bool_iff in H1. |
| 707 |
exact (Qlt_not_le _ _ H H1). } |
| 708 |
destruct H1 as [finish|stop]. |
| 709 |
- subst s. destruct H3. subst r. reflexivity. |
| 710 |
exfalso. destruct H1. |
| 711 |
apply Qle_bool_iff in H3. (* 1 < r by hypothesis. *) |
| 712 |
rewrite SumStream_fst_red in H3. |
| 713 |
unfold fst in H3. |
| 714 |
rewrite <- (Pos.succ_pred r) in H1. 2: exact rone. |
| 715 |
apply Pos.succ_lt_mono in H1. |
| 716 |
specialize (H0 (Pos.pred r) H1). |
| 717 |
rewrite SumStream_fst_red in H0. |
| 718 |
unfold fst in H0. |
| 719 |
rewrite <- iterate_shift, <- iterate_succ, Pos.succ_pred in H0. |
| 720 |
apply Qle_bool_iff in H3. |
| 721 |
rewrite H0 in H3. discriminate. exact rone. |
| 722 |
- destruct stop. |
| 723 |
rewrite SumStream_fst_red in H4. unfold fst in H4. |
| 724 |
rewrite <- iterate_shift, <- iterate_succ in H4. |
| 725 |
destruct H3. exfalso. subst r. |
| 726 |
apply Pos.succ_lt_mono in H1. |
| 727 |
specialize (H2 (Pos.succ s) H1). |
| 728 |
rewrite SumStream_fst_red in H2. |
| 729 |
unfold fst in H2. |
| 730 |
rewrite H4 in H2. discriminate. |
| 731 |
destruct (Pos.lt_total r (Pos.succ s)). |
| 732 |
exfalso. |
| 733 |
destruct H3. |
| 734 |
rewrite SumStream_fst_red in H6. unfold fst in H6. |
| 735 |
rewrite <- (Pos.succ_pred r) in H5. 2: exact rone. |
| 736 |
apply Pos.succ_lt_mono in H5. |
| 737 |
specialize (H0 _ H5). |
| 738 |
rewrite SumStream_fst_red in H0. |
| 739 |
unfold fst in H0. |
| 740 |
rewrite <- iterate_shift, <- iterate_succ, Pos.succ_pred in H0. |
| 741 |
rewrite H0 in H6. discriminate. exact rone. |
| 742 |
destruct H5. |
| 743 |
rewrite H5. reflexivity. exfalso. |
| 744 |
specialize (H2 (Pos.succ s) H5). |
| 745 |
rewrite SumStream_fst_red in H2. |
| 746 |
unfold fst in H2. rewrite H4 in H2. discriminate. |
| 747 |
Qed. |
| 748 |
|
| 749 |
(* AltSeries makes an infinite sum in the real numbers. *) |
| 750 |
Lemma AltSeries_shift : forall x cvmod decr lz, |
| 751 |
(AltSeries x cvmod decr lz |
| 752 |
== '(snd (f x)) |
| 753 |
+ AltSeries (f x) _ (Str_alt_decr_tl x 1 decr) |
| 754 |
(Limit_zero_tl x cvmod 1 decr lz))%CR. |
| 755 |
Proof. |
| 756 |
intros. |
| 757 |
rewrite -> CRplus_translate. |
| 758 |
apply regFunEq_equiv, regFunEq_e. |
| 759 |
intros e. |
| 760 |
simpl. |
| 761 |
rewrite <- Pos.pred_sub. |
| 762 |
destruct (Qlt_le_dec (proj1_sig e) (Qabs (snd (f x)))). |
| 763 |
- (* The sum recombines after f x. *) |
| 764 |
rewrite SumStream_shift. 2: exact q. |
| 765 |
specialize (lz e). revert lz. |
| 766 |
generalize (cvmod e). |
| 767 |
apply (Pos.peano_case (fun p => Qabs (Str_pth p x) <= ` e |
| 768 |
→ Qball (` e + ` e) (SumStream x p e) (SumStream x (Pos.succ (Pos.pred p)) e))). |
| 769 |
+ intros. exfalso. unfold Str_pth in H. |
| 770 |
simpl in H. exact (Qlt_not_le _ _ q H). |
| 771 |
+ intros. rewrite Pos.pred_succ. apply ball_refl. |
| 772 |
apply (Qpos_nonneg (e+e)). |
| 773 |
- (* The sum stops at f x. *) |
| 774 |
unfold SumStream. |
| 775 |
rewrite (iterate_stop_indep _ _ _ (cvmod e) 1). |
| 776 |
rewrite (iterate_stop_indep _ _ _ (Pos.pred (cvmod e)) 1). |
| 777 |
+ rewrite iterate_stop_one, iterate_stop_one. |
| 778 |
unfold fst. |
| 779 |
setoid_replace (snd (let (z, r) := f x in (z, r, Qred (r + snd (x, 0))))) |
| 780 |
with (snd (f x)) |
| 781 |
by (destruct (f x); unfold snd; rewrite Qred_correct; apply Qplus_0_r). |
| 782 |
setoid_replace (snd (let (z, r) := f (f x) in (z, r, Qred (r + snd (x, 0))))) |
| 783 |
with (snd (f (f x))) |
| 784 |
by (destruct (f (f x)); unfold snd; rewrite Qred_correct; apply Qplus_0_r). |
| 785 |
apply AbsSmall_Qabs. |
| 786 |
rewrite Qabs_Qminus. unfold Qminus. |
| 787 |
rewrite (Qplus_comm (snd (f x))), <- Qplus_assoc. |
| 788 |
rewrite Qplus_opp_r, Qplus_0_r. |
| 789 |
specialize (decr xH) as [decr _]. |
| 790 |
apply (Qle_trans _ _ _ decr). |
| 791 |
apply (Qle_trans _ (proj1_sig e + 0)). |
| 792 |
rewrite Qplus_0_r. exact q. |
| 793 |
apply Qplus_le_r, Qpos_nonneg. |
| 794 |
+ rewrite SumStream_fst_red. unfold fst. |
| 795 |
apply Qle_bool_iff. |
| 796 |
rewrite <- iterate_shift, <- iterate_succ. |
| 797 |
specialize (lz e). revert lz. |
| 798 |
generalize (cvmod e). |
| 799 |
apply (Pos.peano_case (fun p => Qabs (Str_pth p x) <= ` e |
| 800 |
→ Qabs (snd (CRstreams.iterate (X * Q) f (Pos.succ (Pos.pred p)) x)) <= ` e)). |
| 801 |
intros _. |
| 802 |
simpl. specialize (decr xH) as [decr _]. |
| 803 |
unfold Str_pth in decr. simpl in decr. |
| 804 |
apply (Qle_trans _ _ _ decr q). |
| 805 |
intros. rewrite Pos.pred_succ. apply H. |
| 806 |
+ rewrite SumStream_fst_red. unfold fst. |
| 807 |
simpl. apply Qle_bool_iff. |
| 808 |
specialize (decr xH) as [decr _]. |
| 809 |
apply (Qle_trans _ _ _ decr). |
| 810 |
exact q. |
| 811 |
+ rewrite SumStream_fst_red. unfold fst. |
| 812 |
apply Qle_bool_iff. apply lz. |
| 813 |
+ rewrite SumStream_fst_red. unfold fst. |
| 814 |
apply Qle_bool_iff. exact q. |
| 815 |
Qed. |
| 816 |
|
| 817 |
End RationalStreamSum. |
| 818 |
|
| 819 |
Lemma Str_alt_decr_pos |
| 820 |
: forall (X:Type) (f : X*Q->X*Q) x |
| 821 |
(fdecr : Str_alt_decr X f x) (n:nat), |
| 822 |
0 <= Str_pth _ f 1 x -> |
| 823 |
0 <= (-1)^Z.of_nat n * Str_pth X f (Pos.of_nat (S n)) x. |
| 824 |
Proof. |
| 825 |
intros X f x fdecr. |
| 826 |
induction n. |
| 827 |
- intros. simpl. rewrite Qmult_1_l. exact H. |
| 828 |
- intro H. specialize (IHn H). |
| 829 |
specialize (fdecr (Pos.of_nat (S n))). |
| 830 |
rewrite Nat2Pos.inj_succ. 2: discriminate. |
| 831 |
destruct (Str_pth X f (Pos.of_nat (S n)) x) as [p q]. |
| 832 |
destruct p as [|p|p]. |
| 833 |
+ destruct fdecr. |
| 834 |
setoid_replace (Qabs (0#q)) with 0%Q in H0 by reflexivity. |
| 835 |
apply Qabs_Qle_condition in H0. change (-0) with 0 in H0. |
| 836 |
setoid_replace (Str_pth X f (Pos.succ (Pos.of_nat (S n))) x) with 0%Q. |
| 837 |
rewrite Qmult_0_r. apply Qle_refl. |
| 838 |
apply Qle_antisym; apply H0. |
| 839 |
+ destruct fdecr. clear H0. |
| 840 |
rewrite <- (Qmult_0_l (Z.pos p # q)) in H1. |
| 841 |
rewrite Qmult_le_r in H1. 2: reflexivity. |
| 842 |
rewrite <- (Qmult_0_l (Z.pos p # q)) in IHn. |
| 843 |
rewrite Qmult_le_r in IHn. 2: reflexivity. |
| 844 |
change (S n) with (1+n)%nat. |
| 845 |
rewrite (Nat2Z.inj_add 1 n). |
| 846 |
rewrite Qpower_plus. simpl ((-1)^Z.of_nat 1). rewrite (Qmult_comm (-1)). |
| 847 |
rewrite <- Qmult_assoc. |
| 848 |
rewrite Qmult_comm, <- (Qmult_0_l ((-1)^Z.of_nat n)). |
| 849 |
apply Qmult_le_compat_r. 2: exact IHn. |
| 850 |
change (S n) with (1+n)%nat in H1. |
| 851 |
destruct (Str_pth X f (Pos.succ (Pos.of_nat (1+ n))) x). |
| 852 |
destruct Qnum. apply Z.le_refl. |
| 853 |
unfold Qle, Z.le in H1. simpl in H1. |
| 854 |
exfalso; apply H1; reflexivity. |
| 855 |
discriminate. intro abs. discriminate. |
| 856 |
+ destruct fdecr. clear H0. |
| 857 |
assert ((Z.neg p # q) == (-1) * (Z.pos p#q)) by reflexivity. |
| 858 |
rewrite H0, Qmult_assoc in H1. rewrite H0, Qmult_assoc in IHn. |
| 859 |
rewrite <- (Qmult_0_l (Z.pos p # q)) in H1. |
| 860 |
rewrite Qmult_le_r in H1. 2: reflexivity. |
| 861 |
rewrite <- (Qmult_0_l (Z.pos p # q)) in IHn. |
| 862 |
rewrite Qmult_le_r in IHn. 2: reflexivity. |
| 863 |
change (S n) with (1+n)%nat. |
| 864 |
rewrite (Nat2Z.inj_add 1 n). |
| 865 |
rewrite Qpower_plus. simpl ((-1)^Z.of_nat 1%nat). rewrite (Qmult_comm (-1)). |
| 866 |
rewrite (Qmult_comm ((-1) ^ Z.of_nat n * -1)). |
| 867 |
rewrite <- (Qmult_0_l ((-1) ^ Z.of_nat n * -1)). |
| 868 |
apply Qmult_le_compat_r. 2: exact IHn. |
| 869 |
change (S n) with (1+n)%nat in H1. |
| 870 |
destruct (Str_pth X f (Pos.succ (Pos.of_nat (1+ n))) x). |
| 871 |
destruct Qnum. apply Z.le_refl. discriminate. |
| 872 |
unfold Qle, Z.le in H1. simpl in H1. |
| 873 |
exfalso; apply H1; reflexivity. |
| 874 |
discriminate. |
| 875 |
Qed. |
| 876 |
|
| 877 |
Lemma CRstream_opp_decr : forall (X:Type) (f : X*Q->X*Q) x, |
| 878 |
Str_alt_decr X f x |
| 879 |
-> Str_alt_decr X (CRstreams.CRstream_opp X f) (let (y, r) := x in (y, - r)). |
| 880 |
Proof. |
| 881 |
intros X f x H p. specialize (H p). |
| 882 |
pose proof (CRstreams.CRstream_opp_pth X f x p). |
| 883 |
pose proof (CRstreams.CRstream_opp_pth X f x (Pos.succ p)). |
| 884 |
unfold Str_pth. unfold Str_pth in H. |
| 885 |
destruct x as [x q]. |
| 886 |
unfold negate, Q_opp. |
| 887 |
destruct (CRstreams.iterate _ f p (x,q)). |
| 888 |
destruct (CRstreams.iterate _ f (Pos.succ p) (x,q)). |
| 889 |
unfold snd in H. |
| 890 |
destruct (CRstreams.iterate _ (CRstreams.CRstream_opp X f) |
| 891 |
(Pos.succ p) (x, (-q)%Q)). |
| 892 |
destruct (CRstreams.iterate _ (CRstreams.CRstream_opp X f) p (x, (-q)%Q)). |
| 893 |
unfold snd. |
| 894 |
destruct H1. subst q2. subst x2. |
| 895 |
destruct H0. subst q3. subst x3. |
| 896 |
destruct H. split. |
| 897 |
- rewrite Qabs_opp, Qabs_opp. exact H. |
| 898 |
- setoid_replace (- q1 * - q0)%Q with (q1*q0)%Q. |
| 899 |
exact H0. unfold equiv, Q_eq. ring. |
| 900 |
Qed. |
| 901 |
|
| 902 |
Lemma CRstream_opp_limit_zero : forall (X:Type) (f : X*Q->X*Q) x cvmod, |
| 903 |
Limit_zero X f x cvmod |
| 904 |
-> Limit_zero X (CRstreams.CRstream_opp X f) (let (y, r) := x in (y, - r)) cvmod. |
| 905 |
Proof. |
| 906 |
intros. intro e. |
| 907 |
specialize (H e). |
| 908 |
pose proof (CRstreams.CRstream_opp_pth X f x (cvmod e)). |
| 909 |
unfold Str_pth. unfold Str_pth in H. |
| 910 |
destruct (CRstreams.iterate (X * Q) f (cvmod e) x) as [y r]. |
| 911 |
destruct x as [x q]. |
| 912 |
unfold negate, Q_opp. |
| 913 |
destruct (CRstreams.iterate (X * Q) (CRstream_opp X f) (cvmod e) (x, (- q)%Q)). |
| 914 |
unfold snd. unfold snd in H. destruct H0. |
| 915 |
subst q0. rewrite Qabs_opp. exact H. |
| 916 |
Qed. |
| 917 |
|
| 918 |
Lemma SumStream_wd : forall (p:positive) |
| 919 |
(X Y:Type) (f : X*Q -> X*Q) (g : Y*Q -> Y*Q) |
| 920 |
(x : X*Q) (y : Y*Q), |
| 921 |
(forall p:positive, Str_pth _ f p x == Str_pth _ g p y) |
| 922 |
-> snd (CRstreams.iterate _ |
| 923 |
(fun y : X * Q * Q => let (z0, r1) := f (fst y) in (z0, r1, r1 + snd y)) p |
| 924 |
(x,0)) |
| 925 |
== snd (CRstreams.iterate _ |
| 926 |
(fun y : Y * Q * Q => let (z0, r1) := g (fst y) in (z0, r1, r1 + snd y)) p |
| 927 |
(y,0)). |
| 928 |
Proof. |
| 929 |
apply (Pos.peano_ind (fun p => forall (X Y:Type) (f : X*Q -> X*Q) (g : Y*Q -> Y*Q) |
| 930 |
(x : X*Q) (y : Y*Q), |
| 931 |
(forall p:positive, Str_pth _ f p x == Str_pth _ g p y) |
| 932 |
-> snd (CRstreams.iterate _ |
| 933 |
(fun y : X * Q * Q => let (z0, r1) := f (fst y) in (z0, r1, r1 + snd y)) p |
| 934 |
(x,0)) |
| 935 |
== snd (CRstreams.iterate _ |
| 936 |
(fun y : Y * Q * Q => let (z0, r1) := g (fst y) in (z0, r1, r1 + snd y)) p |
| 937 |
(y,0)))). |
| 938 |
- intros. simpl. specialize (H xH). |
| 939 |
unfold Str_pth in H. simpl in H. |
| 940 |
destruct (f x), (g y). simpl. simpl in H. |
| 941 |
rewrite H. reflexivity. |
| 942 |
- intros. |
| 943 |
pose proof (H0 (Pos.succ p)). |
| 944 |
unfold Str_pth in H1. |
| 945 |
rewrite iterate_succ, iterate_succ in H1. |
| 946 |
rewrite iterate_succ, iterate_succ, SumStream_fst, SumStream_fst. |
| 947 |
unfold fst. |
| 948 |
destruct (f (CRstreams.iterate (X * Q) f p x)). |
| 949 |
unfold snd at 1. |
| 950 |
destruct (g (CRstreams.iterate (Y * Q) g p y)). |
| 951 |
unfold snd at 3. |
| 952 |
specialize (H X Y f g x y H0). |
| 953 |
rewrite H. simpl in H1. |
| 954 |
rewrite H1. reflexivity. |
| 955 |
Qed. |
| 956 |
|
| 957 |
Lemma AltSeries_wd : forall (X Y:Type) (f : X*Q -> X*Q) (g : Y*Q -> Y*Q) |
| 958 |
(x : X*Q) (y : Y*Q) cvmod ccvmod |
| 959 |
(fdecr : Str_alt_decr X f x) (gdecr : Str_alt_decr Y g y) |
| 960 |
(flz : Limit_zero X f x cvmod) (glz : Limit_zero Y g y ccvmod), |
| 961 |
(forall p:positive, Str_pth _ f p x == Str_pth _ g p y) |
| 962 |
-> (forall e, cvmod e ≡ ccvmod e) |
| 963 |
-> (AltSeries X f x cvmod fdecr flz |
| 964 |
== AltSeries Y g y ccvmod gdecr glz)%CR. |
| 965 |
Proof. |
| 966 |
intros. |
| 967 |
apply regFunEq_equiv, regFunEq_e. intros e. |
| 968 |
simpl. |
| 969 |
setoid_replace (SumStream X f x (cvmod e) e) |
| 970 |
with (SumStream Y g y (cvmod e) e). |
| 971 |
rewrite H0. |
| 972 |
apply ball_refl. apply (Qpos_nonneg (e+e)). |
| 973 |
unfold SumStream. |
| 974 |
destruct (iterate_stop_correct |
| 975 |
_ |
| 976 |
(fun y0 : X * Q * Q => let (z, r) := f (fst y0) in (z, r, Qred (r + snd y0))) |
| 977 |
(fun y0 : X * Q * Q => Qle_bool (Qabs (snd (fst y0))) (` e)) |
| 978 |
(cvmod e) (x,0)) as [q [qeq [H1 H2]]]. |
| 979 |
rewrite qeq, SumStream_red. clear qeq. |
| 980 |
destruct (iterate_stop_correct |
| 981 |
_ |
| 982 |
(fun y0 : Y * Q * Q => let (z, r) := g (fst y0) in (z, r, Qred (r + snd y0))) |
| 983 |
(fun y0 : Y * Q * Q => Qle_bool (Qabs (snd (fst y0))) (` e)) |
| 984 |
(cvmod e) (y,0)) as [r [req [H3 H4]]]. |
| 985 |
rewrite req, SumStream_red. clear req. |
| 986 |
destruct H4 as [fuel|predicate]. |
| 987 |
- subst r. destruct H2. |
| 988 |
+ subst q. apply (SumStream_wd _ _ _ _ _ _ _ H). |
| 989 |
+ exfalso. destruct H2. |
| 990 |
specialize (H3 q H2). |
| 991 |
rewrite SumStream_fst_red in H3. |
| 992 |
unfold fst in H3. |
| 993 |
rewrite SumStream_fst_red in H4. |
| 994 |
unfold fst in H4. |
| 995 |
specialize (H q). unfold Str_pth in H. |
| 996 |
rewrite H in H4. |
| 997 |
rewrite H4 in H3. discriminate. |
| 998 |
- destruct predicate. |
| 999 |
rewrite SumStream_fst_red in H5. |
| 1000 |
unfold fst in H5. |
| 1001 |
destruct H2. |
| 1002 |
+ exfalso. subst q. |
| 1003 |
specialize (H1 r H4). |
| 1004 |
rewrite SumStream_fst_red in H1. |
| 1005 |
unfold fst in H1. |
| 1006 |
specialize (H r). unfold Str_pth in H. |
| 1007 |
rewrite <- H in H5. |
| 1008 |
rewrite H5 in H1. discriminate. |
| 1009 |
+ destruct H2. |
| 1010 |
rewrite SumStream_fst_red in H6. unfold fst in H6. |
| 1011 |
destruct (Pos.lt_total q r). |
| 1012 |
exfalso. specialize (H3 q H7). |
| 1013 |
rewrite SumStream_fst_red in H3; unfold fst in H3. |
| 1014 |
specialize (H q). unfold Str_pth in H. |
| 1015 |
rewrite H in H6. rewrite H6 in H3. discriminate. |
| 1016 |
destruct H7. rewrite H7. |
| 1017 |
exact (SumStream_wd _ _ _ _ _ _ _ H). |
| 1018 |
exfalso. specialize (H1 r H7). |
| 1019 |
rewrite SumStream_fst_red in H1; unfold fst in H1. |
| 1020 |
specialize (H r). unfold Str_pth in H. |
| 1021 |
rewrite H in H1. rewrite H1 in H5. discriminate. |
| 1022 |
Qed. |
| 1023 |
|
| 1024 |
Lemma sym_sub_add_distr (p q r:positive) : (p-(q+r) ≡ p-q-r)%positive. |
| 1025 |
Proof. |
| 1026 |
destruct (Pos.lt_total (q+r) p). |
| 1027 |
- apply Pos.sub_add_distr, H. |
| 1028 |
- destruct H. subst p. |
| 1029 |
rewrite Pos.sub_diag. |
| 1030 |
rewrite Pos.add_comm, Pos.add_sub. |
| 1031 |
rewrite Pos.sub_diag. reflexivity. |
| 1032 |
rewrite Pos.sub_lt. 2: exact H. |
| 1033 |
rewrite Pos.sub_le. reflexivity. |
| 1034 |
destruct (Pos.lt_total p q). |
| 1035 |
+ rewrite Pos.sub_lt. apply Pos.le_1_l. exact H0. |
| 1036 |
+ destruct H0. subst q. rewrite Pos.sub_diag. apply Pos.le_1_l. |
| 1037 |
change (Zpos (p-q) <= Zpos r)%Z. |
| 1038 |
rewrite Pos2Z.inj_sub. 2: exact H0. |
| 1039 |
apply (Z.add_le_mono_r _ _ (Zpos q)). |
| 1040 |
ring_simplify. |
| 1041 |
rewrite <- Pos2Z.inj_add. |
| 1042 |
apply Z.lt_le_incl, H. |
| 1043 |
Qed. |
| 1044 |
|
| 1045 |
Lemma AltSeries_shift_pth : forall (p:positive) (X : Type) f x cvmod decr lz, |
| 1046 |
(AltSeries X f x cvmod decr lz |
| 1047 |
== inject_Q_CR (snd (CRstreams.iterate _ |
| 1048 |
(fun y : (X * Q) * Q => |
| 1049 |
let (z0, r1) := f (fst y) in (z0, r1, Qred (r1 + snd y))) |
| 1050 |
p (x, 0%Q))) |
| 1051 |
+ AltSeries X f (CRstreams.iterate _ f p x) |
| 1052 |
_ (Str_alt_decr_tl X f x p decr) |
| 1053 |
(Limit_zero_tl X f x cvmod p decr lz))%CR. |
| 1054 |
Proof. |
| 1055 |
apply (Pos.peano_ind (fun p => forall X f x cvmod decr lz, |
| 1056 |
(AltSeries X f x cvmod decr lz |
| 1057 |
== inject_Q_CR (snd (CRstreams.iterate _ |
| 1058 |
(fun y : (X * Q) * Q => |
| 1059 |
let (z0, r1) := f (fst y) in (z0, r1, Qred (r1 + snd y))) |
| 1060 |
p (x, 0%Q))) |
| 1061 |
+ AltSeries X f _ _ (Str_alt_decr_tl X f x p decr) |
| 1062 |
(Limit_zero_tl X f x cvmod p decr lz))%CR)). |
| 1063 |
- intros. rewrite AltSeries_shift. |
| 1064 |
apply CRplus_eq_l. rewrite SumStream_red. |
| 1065 |
rewrite iterate_one. simpl. |
| 1066 |
destruct (f x). simpl. rewrite Qplus_0_r. reflexivity. |
| 1067 |
- intros. |
| 1068 |
setoid_replace (AltSeries X f (CRstreams.iterate (X * Q) f (Pos.succ p) x) |
| 1069 |
(fun e : Qpos => (cvmod e - Pos.succ p)%positive) |
| 1070 |
(Str_alt_decr_tl X f x (Pos.succ p) decr) |
| 1071 |
(Limit_zero_tl X f x cvmod (Pos.succ p) decr lz)) |
| 1072 |
with (AltSeries X f (CRstreams.iterate (X * Q) f p (f x)) |
| 1073 |
_ |
| 1074 |
(Str_alt_decr_tl X f (f x) p (Str_alt_decr_tl X f x 1 decr)) |
| 1075 |
(Limit_zero_tl X f (f x) _ p (Str_alt_decr_tl X f x 1 decr) |
| 1076 |
(Limit_zero_tl X f x _ 1 decr lz))). |
| 1077 |
+ setoid_replace (inject_Q_CR (snd |
| 1078 |
(CRstreams.iterate (X * Q * Q) |
| 1079 |
(fun y : X * Q * Q => let (z0, r1) := f (fst y) in (z0, r1, Qred (r1 + snd y))) |
| 1080 |
(Pos.succ p) (x, 0)))) |
| 1081 |
with (inject_Q_CR (snd (f x)) + inject_Q_CR (snd |
| 1082 |
(CRstreams.iterate (X * Q * Q) |
| 1083 |
(fun y : X * Q * Q => |
| 1084 |
let (z0, r1) := f (fst y) in (z0, r1, Qred (r1 + snd y))) p |
| 1085 |
(f x, 0%Q))))%CR. |
| 1086 |
rewrite <- CRplus_assoc, <- (H X f (f x)). |
| 1087 |
rewrite <- AltSeries_shift. reflexivity. |
| 1088 |
clear H. rewrite SumStream_red, SumStream_red. |
| 1089 |
rewrite iterate_succ. rewrite SumStream_fst. |
| 1090 |
simpl. |
| 1091 |
rewrite CRplus_Qplus. |
| 1092 |
apply inject_Q_CR_wd. |
| 1093 |
transitivity (snd (f (CRstreams.iterate (X * Q) f p x) ) |
| 1094 |
+ snd (CRstreams.iterate (X * Q * Q) |
| 1095 |
(fun y : X * Q * Q => let (z1, r0) := f (fst y) in (z1, r0, r0 + snd y)) p |
| 1096 |
(x, 0))). |
| 1097 |
destruct (f (CRstreams.iterate (X * Q) f p x)); reflexivity. |
| 1098 |
pose proof (SumStream_assoc X f x 1 p). |
| 1099 |
rewrite iterate_one, iterate_one in H. |
| 1100 |
setoid_replace (snd (let (z, r0) := f (fst (x, 0)) in (z, r0, r0 + snd (x, 0)))%Q) |
| 1101 |
with (snd (f x))%Q in H. |
| 1102 |
rewrite <- H. clear H. |
| 1103 |
rewrite Pos.add_1_l, iterate_succ, SumStream_fst. |
| 1104 |
unfold fst. |
| 1105 |
destruct (f (CRstreams.iterate (X * Q) f p x)). simpl. |
| 1106 |
reflexivity. |
| 1107 |
simpl. destruct (f x). simpl. |
| 1108 |
rewrite Qplus_0_r. reflexivity. |
| 1109 |
+ apply AltSeries_wd. |
| 1110 |
intros. rewrite iterate_succ, iterate_shift. |
| 1111 |
reflexivity. |
| 1112 |
intro e. rewrite <- Pos.add_1_l. |
| 1113 |
rewrite sym_sub_add_distr. reflexivity. |
| 1114 |
Qed. |