| 1 |
(* |
| 2 |
Copyright © 2006-2008 Russell O’Connor |
| 3 |
|
| 4 |
Permission is hereby granted, free of charge, to any person obtaining a copy of |
| 5 |
this proof and associated documentation files (the "Proof"), to deal in |
| 6 |
the Proof without restriction, including without limitation the rights to |
| 7 |
use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of |
| 8 |
the Proof, and to permit persons to whom the Proof is furnished to do so, |
| 9 |
subject to the following conditions: |
| 10 |
|
| 11 |
The above copyright notice and this permission notice shall be included in all |
| 12 |
copies or substantial portions of the Proof. |
| 13 |
|
| 14 |
THE PROOF IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
| 15 |
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS |
| 16 |
FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR |
| 17 |
COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER |
| 18 |
IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN |
| 19 |
CONNECTION WITH THE PROOF OR THE USE OR OTHER DEALINGS IN THE PROOF. |
| 20 |
*) |
| 21 |
|
| 22 |
Require Import CoRN.algebra.RSetoid. |
| 23 |
Require Import CoRN.metric2.Metric. |
| 24 |
Require Import CoRN.metric2.UniformContinuity. |
| 25 |
Require Import CoRN.reals.fast.CRAlternatingSum. |
| 26 |
Require Import CoRN.reals.fast.CRAlternatingSum_alg. |
| 27 |
Require Import CoRN.reals.fast.CRstreams. |
| 28 |
Require Import CoRN.reals.fast.CRexp. |
| 29 |
Require Export CoRN.reals.fast.CRArith. |
| 30 |
Require Import CoRN.reals.fast.CRIR. |
| 31 |
From Coq Require Import Qpower Qabs Qround. |
| 32 |
Require Import CoRN.model.ordfields.Qordfield. |
| 33 |
Require Import CoRN.reals.Q_in_CReals. |
| 34 |
Require Import CoRN.model.metric2.Qmetric. |
| 35 |
Require Import CoRN.model.totalorder.QMinMax. |
| 36 |
Require Import CoRN.model.totalorder.QposMinMax. |
| 37 |
Require Import CoRN.transc.MoreArcTan. |
| 38 |
Require Import CoRN.tactics.CornTac. |
| 39 |
Require Import MathClasses.interfaces.abstract_algebra. |
| 40 |
Require Import CoRN.stdlib_omissions.Q. |
| 41 |
Require Import Coq.Init.Datatypes. |
| 42 |
|
| 43 |
Set Implicit Arguments. |
| 44 |
|
| 45 |
Local Open Scope Q_scope. |
| 46 |
Local Open Scope uc_scope. |
| 47 |
|
| 48 |
Opaque inj_Q CR. |
| 49 |
|
| 50 |
Lemma Qmult_pos_neg : forall (a b : Q), |
| 51 |
0 <= a -> b <= 0 -> a*b <= 0. |
| 52 |
Proof. |
| 53 |
intros. rewrite Qmult_comm. |
| 54 |
rewrite <- (Qmult_0_l a). |
| 55 |
apply Qmult_le_compat_r; assumption. |
| 56 |
Qed. |
| 57 |
|
| 58 |
Lemma Qmult_opp_1 : forall q : Q, |
| 59 |
eq (-q) (-1 * q). |
| 60 |
Proof. |
| 61 |
reflexivity. |
| 62 |
Qed. |
| 63 |
|
| 64 |
(** |
| 65 |
** Arctangent (small) |
| 66 |
For values between in [[-1,1]], arctangent is computed by it's alternating |
| 67 |
taylor series. |
| 68 |
*) |
| 69 |
Section ArcTanSeries. |
| 70 |
Variable a:Q. |
| 71 |
|
| 72 |
(* (1,a) -> (3, -a^3/3) -> ... |
| 73 |
With a bigger state type, 1/(2i+1) could be set directly. It will be |
| 74 |
done in faster reals with a stream of positive*AQ*AQ. *) |
| 75 |
Definition arctanStream (px : prod positive Q) : prod positive Q |
| 76 |
:= let d := Pos.add 2 (fst px) in |
| 77 |
(d, Qred (- snd px * a * a * (fst px#d))). |
| 78 |
|
| 79 |
Lemma arctanStream_fst : forall p, |
| 80 |
fst (iterate _ arctanStream p (1%positive, a)) ≡ Pos.succ (2*p). |
| 81 |
Proof. |
| 82 |
apply Pos.peano_ind. |
| 83 |
- reflexivity. |
| 84 |
- intros p H. rewrite iterate_succ. |
| 85 |
destruct (iterate (positive and Q) arctanStream p (1%positive, a)). |
| 86 |
simpl in H. subst p0. |
| 87 |
transitivity (Pos.add 2 (p~1)). reflexivity. |
| 88 |
clear q a. rewrite Pos.mul_succ_r. |
| 89 |
rewrite <- Pos.add_1_l, (Pos.add_comm 1). |
| 90 |
rewrite <- Pos.add_assoc. apply f_equal. reflexivity. |
| 91 |
Qed. |
| 92 |
|
| 93 |
Lemma Str_pth_arctanStream : forall p, |
| 94 |
Str_pth _ arctanStream p (xH, a) |
| 95 |
== (1#(1+2*p)) * ((-1)^p*a^(1+2*p))%Q. |
| 96 |
Proof. |
| 97 |
apply Pos.peano_ind. |
| 98 |
- unfold arctanStream, Str_pth, iterate, snd. |
| 99 |
rewrite Qred_correct. simpl. |
| 100 |
rewrite (Qmult_comm (1#3)), Qmult_assoc, Qmult_assoc. |
| 101 |
reflexivity. |
| 102 |
- intros p pInd. unfold Str_pth. |
| 103 |
rewrite iterate_succ. unfold Str_pth in pInd. |
| 104 |
pose proof (arctanStream_fst p) as H0. |
| 105 |
destruct (iterate _ arctanStream p (1%positive, a)) as [p0 q]. |
| 106 |
simpl in H0. subst p0. unfold snd in pInd. |
| 107 |
unfold arctanStream, snd, fst. |
| 108 |
rewrite Qred_correct. rewrite pInd. clear pInd q. |
| 109 |
(* Get rid of (-1)^p *) |
| 110 |
rewrite <- (Qmult_comm ((-1) ^ Pos.succ p * a ^ (1 + 2 * Pos.succ p))). |
| 111 |
rewrite <- (Pos.add_1_l p). |
| 112 |
rewrite Pos2Z.inj_add, (Qpower_plus (-1)%Q). |
| 113 |
simpl ((-1)^1). |
| 114 |
rewrite Qmult_opp_1. |
| 115 |
do 5 rewrite <- (Qmult_assoc (-1)). |
| 116 |
apply (Qmult_comp (-1)). reflexivity. |
| 117 |
rewrite (Qmult_comm (1 # (1 + 2 * p))). |
| 118 |
do 5 rewrite <- (Qmult_assoc ((-1)^p)). |
| 119 |
apply (Qmult_comp ((-1)^p)). reflexivity. |
| 120 |
(* Get rid of a *) |
| 121 |
setoid_replace (a ^ (1 + 2 * (1 + p))) with (a ^ (1 + 2 * p) * (a * a)). |
| 122 |
do 4 rewrite <- (Qmult_assoc (a ^ (1 + 2 * p))). |
| 123 |
apply Qmult_comp. reflexivity. |
| 124 |
rewrite <- (Qmult_assoc _ a a). |
| 125 |
rewrite (Qmult_comm (1 # (1 + 2 * p))). |
| 126 |
rewrite <- (Qmult_assoc (a*a)). |
| 127 |
apply Qmult_comp. reflexivity. |
| 128 |
(* Finish equalities *) |
| 129 |
unfold Qeq, Qmult, Qnum, Qden. |
| 130 |
rewrite Z.mul_1_l, Z.mul_1_l. |
| 131 |
reflexivity. |
| 132 |
rewrite <- (Qpower_plus_positive a 1 1). |
| 133 |
rewrite <- (Qpower_plus_positive a (1+2*p)). |
| 134 |
apply Qpower_positive_comp. reflexivity. |
| 135 |
rewrite <- Pos.add_assoc. |
| 136 |
apply f_equal. rewrite (Pos.add_comm 1 p). |
| 137 |
reflexivity. |
| 138 |
intro abs. discriminate. |
| 139 |
Qed. |
| 140 |
|
| 141 |
Hypothesis Ha: (-1 <= a <= 1). |
| 142 |
|
| 143 |
Lemma arctanStream_alt : Str_alt_decr _ arctanStream (1%positive,a). |
| 144 |
Proof. |
| 145 |
split. |
| 146 |
- (* Replace a by Qabs a *) |
| 147 |
rewrite Str_pth_arctanStream, Str_pth_arctanStream. |
| 148 |
rewrite Qabs_Qmult, Qabs_Qmult, Qabs_Qmult, Qabs_Qmult. |
| 149 |
rewrite Qabs_Qpower, Qabs_Qpower. |
| 150 |
change (Qabs (-1)) with 1. |
| 151 |
rewrite Qpower_1, Qpower_1, Qmult_1_l, Qmult_1_l. |
| 152 |
rewrite (Qabs_Qpower a (1+2*Pos.succ p)), (Qabs_Qpower a (1+2*p)). |
| 153 |
(* Finish inequality *) |
| 154 |
setoid_replace (Qabs a ^ (1 + 2 * Pos.succ p)%positive) |
| 155 |
with (Qabs a * Qabs a * Qabs a ^ (1 + 2 * p)%positive). |
| 156 |
rewrite Qmult_assoc. |
| 157 |
apply Qmult_le_compat_r. |
| 158 |
2: rewrite <- Qabs_Qpower; apply Qabs_nonneg. |
| 159 |
+ rewrite Qmult_comm. |
| 160 |
apply (Qabs_Qle_condition a 1) in Ha. |
| 161 |
apply (Qle_trans _ (1* (1 # (1 + 2 * (Pos.succ p))))). |
| 162 |
apply Qmult_le_compat_r. 2: discriminate. |
| 163 |
apply (Qle_trans _ (1*Qabs a)). |
| 164 |
apply Qmult_le_compat_r. exact Ha. |
| 165 |
apply Qabs_nonneg. rewrite Qmult_1_l. exact Ha. |
| 166 |
rewrite Qmult_1_l. unfold Qabs, Z.abs. |
| 167 |
unfold Qle, Qnum, Qden. |
| 168 |
rewrite Z.mul_1_l, Z.mul_1_l. |
| 169 |
change (p <= Pos.succ p)%positive. |
| 170 |
apply Pos.lt_le_incl, Pos.lt_succ_r, Pos.le_refl. |
| 171 |
+ replace (1 + 2 * Pos.succ p)%positive with (2 + (1 + 2 * p))%positive. |
| 172 |
generalize (1 + 2 * p)%positive. clear p. intro p. |
| 173 |
unfold Qpower. |
| 174 |
rewrite Qpower_plus_positive. reflexivity. |
| 175 |
rewrite Pos.add_comm, <- Pos.add_assoc. apply f_equal. |
| 176 |
rewrite <- Pos.add_1_l. |
| 177 |
rewrite Pos.mul_add_distr_l, Pos.mul_1_r. |
| 178 |
apply Pos.add_comm. |
| 179 |
- rewrite Str_pth_arctanStream, Str_pth_arctanStream. |
| 180 |
rewrite Qmult_comm, <- Qmult_assoc. apply Qmult_pos_neg. |
| 181 |
discriminate. rewrite Qmult_comm, <- Qmult_assoc. |
| 182 |
apply Qmult_pos_neg. discriminate. |
| 183 |
rewrite <- Pos.add_1_l. |
| 184 |
change ((-1) ^ (1 + p)%positive) with (Qpower_positive (-1) (1 + p)). |
| 185 |
rewrite Qpower_plus_positive. simpl (Qpower_positive (-1) 1). |
| 186 |
rewrite <- Qmult_assoc, <- Qmult_assoc. |
| 187 |
apply (Qopp_le_compat 0). |
| 188 |
rewrite (Qmult_comm (a ^ (1 + 2 * (1 + p)%positive))). |
| 189 |
rewrite Qmult_assoc, Qmult_assoc. |
| 190 |
rewrite <- Qmult_assoc. |
| 191 |
apply Qmult_le_0_compat. |
| 192 |
simpl. |
| 193 |
destruct (Qpower_positive (-1) p), Qnum; discriminate. |
| 194 |
setoid_replace (a ^ (1 + 2 * (1 + p))) with (a ^ (1 + 2 * p) * (a * a)). |
| 195 |
rewrite Qmult_assoc. |
| 196 |
apply Qmult_le_0_compat. |
| 197 |
destruct (a ^ (1 + 2 * p)), Qnum; discriminate. |
| 198 |
destruct a, Qnum; discriminate. |
| 199 |
change (a*a) with (Qpower_positive a 2). |
| 200 |
rewrite <- (Qpower_plus_positive a (1+2*p)). |
| 201 |
change (a ^ (1 + 2 * (1 + p))) with (Qpower_positive a (1 + 2 * (1 + p))). |
| 202 |
replace (1 + 2 * (1 + p))%positive with (1 + 2 * p + 2)%positive. |
| 203 |
reflexivity. |
| 204 |
rewrite <- Pos.add_assoc. apply f_equal. |
| 205 |
rewrite Pos.mul_add_distr_l, Pos.mul_1_r. |
| 206 |
apply Pos.add_comm. |
| 207 |
Qed. |
| 208 |
|
| 209 |
Lemma arctanStream_zl |
| 210 |
: Limit_zero _ arctanStream (xH,a) |
| 211 |
(fun e:Qpos => Z.to_pos (Qceiling (/ (proj1_sig e)))). |
| 212 |
Proof. |
| 213 |
intros [e epos]. rewrite Str_pth_arctanStream, Qabs_Qmult, Qabs_Qmult. |
| 214 |
rewrite Qabs_Qpower. change (Qabs (-1)) with 1. |
| 215 |
rewrite Qpower_1, Qmult_1_l. |
| 216 |
rewrite Qmult_comm. |
| 217 |
apply (Qle_trans _ (1 * Qabs (1 # 1 + 2 * Z.to_pos (Qceiling (/ ` (e ↾ epos)))))). |
| 218 |
apply Qmult_le_compat_r. 2: apply Qabs_nonneg. |
| 219 |
- rewrite (Qabs_Qpower a (1 + 2 * Z.to_pos (Qceiling (/ ` (e ↾ epos))))). |
| 220 |
apply Qpower_le_1. split. |
| 221 |
apply Qabs_nonneg. |
| 222 |
apply Qabs_Qle_condition, Ha. |
| 223 |
- clear Ha a. |
| 224 |
rewrite Qmult_1_l. unfold Qabs, Z.abs, proj1_sig. |
| 225 |
rewrite <- (Qinv_involutive e) at 2. |
| 226 |
assert (0 < /e) as H. |
| 227 |
{ apply Qinv_lt_0_compat, epos. } |
| 228 |
apply (@Qinv_le_compat (/e) (Zpos (1 + 2 * Z.to_pos (Qceiling (/ e))) # 1)). |
| 229 |
exact H. |
| 230 |
apply (Qle_trans _ _ _ (Qle_ceiling (/e))). |
| 231 |
generalize (Qceiling (/ e)). |
| 232 |
clear H epos e. intros [|p|p]. |
| 233 |
discriminate. 2: discriminate. |
| 234 |
pose proof (Zle_Qle p (Z.pos (1 + 2 * Z.to_pos p))). |
| 235 |
unfold inject_Z. |
| 236 |
unfold inject_Z in H. |
| 237 |
rewrite <- H. clear H. |
| 238 |
change (p <= 1 + 2*p)%positive. |
| 239 |
rewrite <- Pplus_one_succ_l. |
| 240 |
apply Pos.lt_le_incl, Pos.lt_succ_r. |
| 241 |
apply (Pos.mul_le_mono_r p 1 2). discriminate. |
| 242 |
Qed. |
| 243 |
|
| 244 |
End ArcTanSeries. |
| 245 |
|
| 246 |
Definition rational_arctan_small (a:Q) (p: -1 <= a <= 1) : CR := |
| 247 |
(inject_Q_CR a + AltSeries _ (arctanStream a) (xH,a) _ |
| 248 |
(arctanStream_alt p) (arctanStream_zl p))%CR. |
| 249 |
|
| 250 |
Lemma rational_arctan_small_wd : forall (a1 a2 : Q) (p1 : -1 <= a1 <= 1) (p2 : -1 <= a2 <= 1), |
| 251 |
a1 = a2 → rational_arctan_small p1 = rational_arctan_small p2. |
| 252 |
Proof. |
| 253 |
intros. unfold rational_arctan_small. |
| 254 |
apply ucFun2_wd. rewrite H. reflexivity. |
| 255 |
apply AltSeries_wd. |
| 256 |
2: reflexivity. intro p. |
| 257 |
rewrite Str_pth_arctanStream, Str_pth_arctanStream, H. reflexivity. |
| 258 |
Qed. |
| 259 |
|
| 260 |
Lemma widen_interval : forall a:Q, -1 < a < 1 -> -1 <= a <= 1. |
| 261 |
Proof. |
| 262 |
intros a [H H0]. split; apply Qlt_le_weak; assumption. |
| 263 |
Qed. |
| 264 |
|
| 265 |
Lemma rational_arctan_small_correct : forall (a:Q) (Ha : -1 < a < 1), |
| 266 |
(@rational_arctan_small a (widen_interval Ha) == IRasCR (ArcTan (inj_Q IR a)))%CR. |
| 267 |
Proof. |
| 268 |
intros a Ha. |
| 269 |
unfold rational_arctan_small. |
| 270 |
rewrite <- (IR_inj_Q_as_CR a). |
| 271 |
rewrite |
| 272 |
(AltSeries_correct |
| 273 |
_ _ _ _ (arctanStream_alt (widen_interval Ha)) |
| 274 |
(arctanStream_zl (widen_interval Ha)) |
| 275 |
_ (AltSeries_convergent_0 _ _ _ _ (inj_Q IR a) |
| 276 |
(arctanStream_alt (widen_interval Ha)) (arctanStream_zl (widen_interval Ha)))). |
| 277 |
- apply IRasCR_wd. |
| 278 |
assert (olor ([--][1]) [1] (inj_Q IR a)) as X. |
| 279 |
{ split. |
| 280 |
stepl (inj_Q IR (-1)). apply inj_Q_less, Ha. |
| 281 |
rewrite (inj_Q_inv IR 1), inj_Q_One. reflexivity. |
| 282 |
stepr (inj_Q IR 1); [| now apply inj_Q_One]. |
| 283 |
apply inj_Q_less, Ha. } |
| 284 |
eapply eq_transitive_unfolded; |
| 285 |
[|apply (arctan_series (inj_Q IR a) (arctan_series_convergent_IR) X)]. |
| 286 |
apply series_sum_wd. |
| 287 |
intros n. |
| 288 |
transitivity (inj_Q IR (((-1)^n)%Q *(a^(1+2*Z.of_nat n) * (1#(Pos.of_nat (1+2*n)))))). |
| 289 |
+ destruct n. apply inj_Q_wd. simpl. |
| 290 |
rewrite Qmult_1_l, Qmult_1_r. reflexivity. |
| 291 |
apply inj_Q_wd. |
| 292 |
rewrite Str_pth_arctanStream. |
| 293 |
rewrite (Qmult_assoc ((-1)^S n)). |
| 294 |
rewrite (Qmult_comm ((-1) ^ S n * a ^ (1 + 2 * S n))). apply Qmult_comp. |
| 295 |
unfold Qeq, Qnum, Qden. |
| 296 |
rewrite Z.mul_1_l, Z.mul_1_l. |
| 297 |
change 2%positive with (Pos.of_nat 2). |
| 298 |
rewrite <- (Nat2Pos.inj_mul 2 (S n)). |
| 299 |
2: discriminate. 2: discriminate. |
| 300 |
rewrite <- (Nat2Pos.inj_add 1). reflexivity. |
| 301 |
discriminate. discriminate. |
| 302 |
apply Qmult_comp. |
| 303 |
rewrite <- Pos.of_nat_succ, POS_anti_convert. |
| 304 |
reflexivity. |
| 305 |
replace (1 + 2 * Z.pos (Pos.of_nat (S n)))%Z with (1 + 2 * S n)%Z. |
| 306 |
reflexivity. |
| 307 |
rewrite <- Pos.of_nat_succ, POS_anti_convert. |
| 308 |
reflexivity. |
| 309 |
+ transitivity (([--][1][^]n[/]nring (R:=IR) (S (2 * n))[//]nringS_ap_zero IR (2 * n))[*] |
| 310 |
(inj_Q IR a)[^](2 * n + 1)). |
| 311 |
2: reflexivity. |
| 312 |
rstepr (([--][1][^]n)[*]((inj_Q IR a)[^](2*n+1)[/]nring (R:=IR) (S (2 * n))[//]nringS_ap_zero IR (2 * n))). |
| 313 |
rewrite inj_Q_mult. |
| 314 |
apply mult_wd. |
| 315 |
rewrite inj_Q_power. |
| 316 |
apply nexp_wd. |
| 317 |
rewrite (inj_Q_inv IR 1), inj_Q_One. |
| 318 |
reflexivity. |
| 319 |
apply mult_cancel_lft with (nring (R:=IR) (S (2 * n))). |
| 320 |
apply nringS_ap_zero. |
| 321 |
rstepr (inj_Q IR a[^](2 * n + 1)). |
| 322 |
stepr (inj_Q IR (a^(2*n+1)%nat)); [| now apply inj_Q_power]. |
| 323 |
stepl ((inj_Q IR (nring (S (2*n))))[*]inj_Q IR (a ^ (1 + 2 * n) * (1 # Pos.of_nat (1 + 2 * n)))); |
| 324 |
[| now apply mult_wdl; apply inj_Q_nring]. |
| 325 |
rewrite <- inj_Q_mult. |
| 326 |
apply inj_Q_wd. |
| 327 |
setoid_rewrite (nring_Q (S (2*n))). |
| 328 |
change (S (2 * n) * (a ^ (1 + 2 * n) * (1 # Pos.of_nat (1 + 2 * n))) |
| 329 |
== a ^ (2 * n + 1)%nat)%Q. |
| 330 |
rewrite Qmult_comm. |
| 331 |
rewrite <- Qmult_assoc. |
| 332 |
setoid_replace ((1 # Pos.of_nat (1 + 2 * n)) * S (2 * n)) with 1%Q. |
| 333 |
rewrite Qmult_1_r, Nat.add_comm. |
| 334 |
rewrite Nat2Z.inj_add, Nat2Z.inj_mul. reflexivity. |
| 335 |
unfold Qeq, inject_Z, Qmult, Qnum, Qden. |
| 336 |
rewrite Z.mul_1_l, Z.mul_1_l, Z.mul_1_r, Pos.mul_1_r. |
| 337 |
unfold Z.of_nat. |
| 338 |
rewrite Pos.of_nat_succ. reflexivity. |
| 339 |
- intro p. destruct (Pos.to_nat p) eqn:des. |
| 340 |
exfalso. pose proof (Pos2Nat.is_pos p). rewrite des in H. |
| 341 |
inversion H. |
| 342 |
apply inj_Q_wd. |
| 343 |
rewrite <- des, Pos2Nat.id. reflexivity. |
| 344 |
Qed. |