| 1 |
(* |
| 2 |
Copyright © 2006-2008 Russell O’Connor |
| 3 |
Copyright © 2020 Vincent Semeria |
| 4 |
|
| 5 |
Permission is hereby granted, free of charge, to any person obtaining a copy of |
| 6 |
this proof and associated documentation files (the "Proof"), to deal in |
| 7 |
the Proof without restriction, including without limitation the rights to |
| 8 |
use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of |
| 9 |
the Proof, and to permit persons to whom the Proof is furnished to do so, |
| 10 |
subject to the following conditions: |
| 11 |
|
| 12 |
The above copyright notice and this permission notice shall be included in all |
| 13 |
copies or substantial portions of the Proof. |
| 14 |
|
| 15 |
THE PROOF IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
| 16 |
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS |
| 17 |
FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR |
| 18 |
COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER |
| 19 |
IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN |
| 20 |
CONNECTION WITH THE PROOF OR THE USE OR OTHER DEALINGS IN THE PROOF. |
| 21 |
*) |
| 22 |
|
| 23 |
Require Import CoRN.metric2.Metric. |
| 24 |
Require Import CoRN.metric2.UniformContinuity. |
| 25 |
Require Import CoRN.model.totalorder.QposMinMax. |
| 26 |
Require Export CoRN.model.lattice.CRlattice. |
| 27 |
Require Import CoRN.model.totalorder.QMinMax. |
| 28 |
From Coq Require Import Qabs. |
| 29 |
Require Import CoRN.model.metric2.Qmetric. |
| 30 |
Require Import CoRN.metric2.ProductMetric. |
| 31 |
Require Import MathClasses.interfaces.canonical_names. |
| 32 |
|
| 33 |
(* Backwards compatibility for Hint Rewrite locality attributes *) |
| 34 |
Set Warnings "-unsupported-attributes". |
| 35 |
|
| 36 |
Set Implicit Arguments. |
| 37 |
|
| 38 |
Local Open Scope Q_scope. |
| 39 |
Local Open Scope uc_scope. |
| 40 |
Opaque Qmin Qmax Qred. |
| 41 |
|
| 42 |
(** |
| 43 |
** Strict Inequality |
| 44 |
First we defined positivity. We define positivity to contain a |
| 45 |
positive rational witness of a lower bound on x. This seems the best |
| 46 |
way because this witness contains exactly the information needed |
| 47 |
for functions (such as inverse and logorithm) that have domains |
| 48 |
restricted to the positive reals. |
| 49 |
*) |
| 50 |
Definition CRpos (x:CR) := sig (fun e:Qpos => ' proj1_sig e <= x)%CR. |
| 51 |
|
| 52 |
Lemma CRpos_wd : forall x y, (x==y)%CR -> (CRpos x) -> (CRpos y). |
| 53 |
Proof. |
| 54 |
intros x y Hxy [e H]. |
| 55 |
exists e. |
| 56 |
abstract ( rewrite <- Hxy; assumption ). |
| 57 |
Defined. |
| 58 |
|
| 59 |
(** This is a characterization closer to Bishop's definiton. If we |
| 60 |
replace [2*e] with [e], the theorem still holds, but it could be |
| 61 |
very expensive to call. We prefer to avoid that. *) |
| 62 |
|
| 63 |
Program Definition CRpos_char (e:Qpos) (x:CR) |
| 64 |
(H: (2#1)*proj1_sig e <= (approximate x e)) |
| 65 |
: CRpos x := e. |
| 66 |
|
| 67 |
Next Obligation. |
| 68 |
change (CRle (inject_Q_CR (proj1_sig e)) x). |
| 69 |
intros a. |
| 70 |
simpl. |
| 71 |
unfold Cap_raw. |
| 72 |
simpl. |
| 73 |
apply Qle_trans with (-(1#2)* proj1_sig a). |
| 74 |
rewrite -> Qle_minus_iff. |
| 75 |
ring_simplify. |
| 76 |
apply Qmult_le_0_compat; auto with *. |
| 77 |
rewrite -> Qle_minus_iff. |
| 78 |
destruct (regFun_prf x e ((1#2)*a)%Qpos) as [_ X]. |
| 79 |
apply (Qle_trans _ (approximate x ((1 # 2) * a)%Qpos + (1#2)*proj1_sig a |
| 80 |
+ proj1_sig e + - ((2#1)*proj1_sig e))). |
| 81 |
2: simpl; ring_simplify; apply Qle_refl. |
| 82 |
rewrite <- Qle_minus_iff; apply Qle_trans with (approximate x e); try assumption; simpl in X. |
| 83 |
rewrite -> Qle_minus_iff in X; rewrite -> Qle_minus_iff; autorewrite with QposElim in X. |
| 84 |
apply (Qle_trans _ _ _ X). |
| 85 |
ring_simplify. apply Qle_refl. |
| 86 |
Qed. |
| 87 |
|
| 88 |
(** Negative reals are defined similarly. *) |
| 89 |
Definition CRneg (x:CR) := sig (fun e:Qpos => x <= ' (-proj1_sig e)%Q)%CR. |
| 90 |
|
| 91 |
Lemma CRneg_wd : forall x y, (x==y)%CR -> (CRneg x) -> (CRneg y). |
| 92 |
Proof. |
| 93 |
intros x y Hxy [e H]. |
| 94 |
exists e. |
| 95 |
abstract ( rewrite <- Hxy; assumption ). |
| 96 |
Defined. |
| 97 |
|
| 98 |
Program Definition CRneg_char (e:Qpos) (x:CR) (H: (approximate x e) <= -(2#1)*e): CRneg x := e. |
| 99 |
|
| 100 |
Next Obligation. |
| 101 |
change (x <= '(-proj1_sig e)%Q)%CR. |
| 102 |
intros a; simpl; unfold Cap_raw; simpl; apply Qle_trans with (-(1#2)*proj1_sig a). |
| 103 |
rewrite -> Qle_minus_iff; ring_simplify. |
| 104 |
apply Qmult_le_0_compat; auto with *. |
| 105 |
rewrite -> Qle_minus_iff. |
| 106 |
destruct (regFun_prf x e ((1#2)*a)%Qpos) as [X _]. |
| 107 |
apply (Qle_trans _ ( - proj1_sig e + - approximate x ((1 # 2) * a)%Qpos |
| 108 |
+ (1 # 2) * proj1_sig a + approximate x e + - approximate x e)). |
| 109 |
2: simpl; ring_simplify; apply Qle_refl. |
| 110 |
rewrite <- Qle_minus_iff. |
| 111 |
apply Qle_trans with (-(2#1)*proj1_sig e); try assumption. |
| 112 |
simpl in X. rewrite -> Qle_minus_iff in X. |
| 113 |
rewrite -> Qle_minus_iff. |
| 114 |
apply (Qle_trans _ _ _ X). |
| 115 |
simpl. ring_simplify. apply Qle_refl. |
| 116 |
Qed. |
| 117 |
|
| 118 |
(** Strict inequality is defined in terms of positivity. *) |
| 119 |
Definition CRltT (x y:CR) := CRpos (y-x)%CR. |
| 120 |
|
| 121 |
Infix "<" := CRltT : CR_scope. |
| 122 |
|
| 123 |
Lemma CRltT_wd : forall x1 x2, (x1==x2 -> forall y1 y2, y1==y2 -> x1 < y1 -> x2 < y2)%CR. |
| 124 |
Proof. |
| 125 |
intros x1 x2 Hx y1 y2 Hy H. |
| 126 |
refine (CRpos_wd _ _). 2:apply H. |
| 127 |
abstract ( rewrite <- Hx; rewrite <- Hy; reflexivity ). |
| 128 |
Defined. |
| 129 |
|
| 130 |
(** |
| 131 |
** Apartness |
| 132 |
*) |
| 133 |
Definition CRapartT (x y:CR) := (sum (x < y) (y < x))%CR. |
| 134 |
|
| 135 |
Notation "x >< y" := (CRapartT x y) (at level 70, no associativity) : CR_scope. |
| 136 |
|
| 137 |
Lemma CRapartT_wd : forall x1 x2, (x1==x2 -> forall y1 y2, y1==y2 -> x1><y1 -> x2><y2)%CR. |
| 138 |
Proof. |
| 139 |
intros x1 x2 Hx y1 y2 Hy [H|H];[left;apply (CRltT_wd Hx Hy)|right;apply (CRltT_wd Hy Hx)];assumption. |
| 140 |
Defined. |
| 141 |
(** |
| 142 |
** Multiplication |
| 143 |
The modulus of continuity for multiplication by a constant. |
| 144 |
*) |
| 145 |
Definition Qscale_modulus (a:Q) (e:Qpos) : QposInf := |
| 146 |
match a with |
| 147 |
| 0 # _ => QposInfinity |
| 148 |
| (Zpos an) # ad => Qpos2QposInf ((ad # an) * e) |
| 149 |
| (Zneg an) # ad => Qpos2QposInf ((ad # an) * e) |
| 150 |
end. |
| 151 |
|
| 152 |
Lemma Qscale_modulus_elim : forall (P:QposInf -> Type) (x:Q) (e:Qpos), |
| 153 |
(x==0 -> P QposInfinity)%Q -> |
| 154 |
(forall y:Qpos, QAbsSmall (proj1_sig e/proj1_sig y)%Q (x)%Q -> (P y)) -> |
| 155 |
P (Qscale_modulus x e). |
| 156 |
Proof. |
| 157 |
intros P [xn xd] e H1. |
| 158 |
cut (forall xn:positive, (forall y : Qpos, QAbsSmall (proj1_sig e/proj1_sig y)%Q (Z.pos xn#xd)%Q -> P y) -> |
| 159 |
P (Qscale_modulus (Z.pos xn # xd) e)). |
| 160 |
intros H H2. |
| 161 |
destruct xn as [|xn|xn]. |
| 162 |
apply H1. |
| 163 |
constructor. |
| 164 |
apply H. |
| 165 |
assumption. |
| 166 |
apply H. |
| 167 |
intros y Hy. |
| 168 |
apply H2. |
| 169 |
change (Zneg xn # xd)%Q with (-(Zpos xn # xd))%Q. |
| 170 |
apply QAbsSmall_opp, Hy. |
| 171 |
clear xn H1. |
| 172 |
intros xn H2. |
| 173 |
simpl. |
| 174 |
apply H2. |
| 175 |
simpl. |
| 176 |
unfold QAbsSmall. |
| 177 |
setoid_replace (` e / ((Zpos xd # xn) * ` e)) with (Zpos xn # xd). |
| 178 |
split. 2: apply Qle_refl. |
| 179 |
apply (Qplus_le_l _ _ (Zpos xn # xd)). ring_simplify. |
| 180 |
apply (Qpos_nonneg ((2#1)*(xn#xd))). |
| 181 |
unfold Qdiv. rewrite Qinv_mult_distr. |
| 182 |
rewrite <- (Qmult_comm (/ `e)), Qmult_assoc. |
| 183 |
rewrite Qmult_inv_r, Qmult_1_l. reflexivity. |
| 184 |
apply Qpos_nonzero. |
| 185 |
Qed. |
| 186 |
|
| 187 |
Lemma Qscale_modulus_pos (a e: Qpos): exists P, |
| 188 |
Qscale_modulus (proj1_sig a) e |
| 189 |
≡ Qpos2QposInf (exist (Qlt 0) (/ proj1_sig a * proj1_sig e)%Q P). |
| 190 |
Proof. |
| 191 |
revert a. |
| 192 |
intros [[[] ad] P]; try discriminate. |
| 193 |
simpl. unfold Qpos_inv, Qpos_mult. |
| 194 |
eauto. |
| 195 |
Qed. |
| 196 |
|
| 197 |
Lemma Qscale_uc_prf (a:Q) : |
| 198 |
@is_UniformlyContinuousFunction |
| 199 |
Q_as_MetricSpace Q_as_MetricSpace (fun b:Q => a*b) (Qscale_modulus a). |
| 200 |
Proof. |
| 201 |
revert a. |
| 202 |
intros [[|an|an] ad] e b0 b1 H. |
| 203 |
- simpl in *. |
| 204 |
setoid_replace ((0 # ad)) with 0 by constructor. |
| 205 |
rewrite Qmult_0_l, Qmult_0_l. |
| 206 |
apply Qball_Reflexive, Qpos_nonneg. |
| 207 |
- simpl. |
| 208 |
simpl in *. |
| 209 |
unfold Qball in *. |
| 210 |
unfold QAbsSmall. |
| 211 |
setoid_replace ((Zpos an # ad) * b0 - (Zpos an # ad) * b1) |
| 212 |
with (b0 * (Zpos an # ad) - b1 * (Zpos an # ad)) |
| 213 |
by (unfold equiv, stdlib_rationals.Q_eq; ring). |
| 214 |
unfold QAbsSmall in H. |
| 215 |
setoid_replace ((Zpos ad # an) * ` e) |
| 216 |
with (` e / (Zpos an # ad)) in H. |
| 217 |
apply (Qball_Qmult_r e (an#ad)) in H. |
| 218 |
exact H. |
| 219 |
rewrite Qmult_comm. apply Qmult_comp; reflexivity. |
| 220 |
- simpl. |
| 221 |
setoid_replace ((Z.neg an # ad) * b0) |
| 222 |
with (-((Z.pos an # ad) * b0)). |
| 223 |
setoid_replace ((Z.neg an # ad) * b1) |
| 224 |
with (-((Z.pos an # ad) * b1)). |
| 225 |
apply Qball_opp. |
| 226 |
simpl in H. |
| 227 |
unfold Qball, QAbsSmall. |
| 228 |
setoid_replace ((Zpos an # ad) * b0 - (Zpos an # ad) * b1) |
| 229 |
with (b0*(Zpos an#ad)-b1*(Zpos an#ad)) |
| 230 |
by (unfold equiv, stdlib_rationals.Q_eq; ring). |
| 231 |
setoid_replace ((Zpos ad # an) * ` e) |
| 232 |
with (` e / (Zpos an # ad)) in H. |
| 233 |
apply (Qball_Qmult_r e (an#ad)) in H. simpl in H. |
| 234 |
apply H. |
| 235 |
rewrite Qmult_comm. apply Qmult_comp; reflexivity. |
| 236 |
destruct b1, Qnum; reflexivity. |
| 237 |
destruct b0, Qnum; reflexivity. |
| 238 |
Qed. |
| 239 |
|
| 240 |
(** Scaling by a constant is [Qmult] lifted on one parameter. *) |
| 241 |
Definition Qscale_uc (a:Q_as_MetricSpace) : Q_as_MetricSpace --> Q_as_MetricSpace := |
| 242 |
Build_UniformlyContinuousFunction (Qscale_uc_prf a). |
| 243 |
|
| 244 |
Definition scale (a:Q) : CR --> CR := Cmap QPrelengthSpace (Qscale_uc a). |
| 245 |
|
| 246 |
#[global] |
| 247 |
Instance Qscale_uc_Proper: Proper (Qeq ==> @msp_eq _) Qscale_uc. |
| 248 |
Proof. |
| 249 |
intros x y E. |
| 250 |
apply ucEq_equiv. |
| 251 |
intros q. simpl. |
| 252 |
apply Qball_0. |
| 253 |
rewrite E. reflexivity. |
| 254 |
Qed. |
| 255 |
|
| 256 |
#[global] |
| 257 |
Instance scale_Proper: Proper (Qeq ==> @msp_eq (UniformlyContinuousSpace CR CR)) scale. |
| 258 |
Proof. |
| 259 |
intros x y E. |
| 260 |
apply ucEq_equiv. |
| 261 |
intro z. simpl ucFun. rewrite E. |
| 262 |
reflexivity. |
| 263 |
Qed. |
| 264 |
|
| 265 |
(** [CRboundAbs] clamps a real number between -c and c where c is |
| 266 |
rational. *) |
| 267 |
Definition QboundAbs (c:Qpos) : Q_as_MetricSpace --> Q_as_MetricSpace |
| 268 |
:= uc_compose (QboundBelow_uc (-proj1_sig c)) (QboundAbove_uc (proj1_sig c)). |
| 269 |
|
| 270 |
Definition CRboundAbs (c:Qpos) : CR -> CR |
| 271 |
:= Cmap QPrelengthSpace (QboundAbs c). |
| 272 |
|
| 273 |
Lemma QboundAbs_absorb: forall (a b:Qpos) (c:Q), |
| 274 |
proj1_sig a <= proj1_sig b -> |
| 275 |
QboundAbs b (QboundAbs a c) == QboundAbs a c. |
| 276 |
Proof. |
| 277 |
intros a b c H. |
| 278 |
simpl. |
| 279 |
rewrite -> Qmin_max_distr_r. |
| 280 |
setoid_replace (Qmin (proj1_sig b) (-proj1_sig a)) with (-proj1_sig a). |
| 281 |
rewrite -> Qmax_assoc. |
| 282 |
rewrite <- Qmin_max_de_morgan. |
| 283 |
rewrite -> Qmin_assoc. |
| 284 |
setoid_replace (Qmin (proj1_sig b) (proj1_sig a)) with (proj1_sig a). |
| 285 |
reflexivity. |
| 286 |
rewrite <- Qle_min_r. |
| 287 |
assumption. |
| 288 |
rewrite <- Qle_min_r. |
| 289 |
rewrite -> Qle_minus_iff. |
| 290 |
ring_simplify. |
| 291 |
destruct a,b. simpl. rewrite <- (Qplus_0_l 0). |
| 292 |
apply Qplus_le_compat; apply Qlt_le_weak; assumption. |
| 293 |
Qed. |
| 294 |
|
| 295 |
(** Properties of CRboundAbs. *) |
| 296 |
Lemma CRboundAbs_Eq : forall (a:Qpos) (x:CR), |
| 297 |
('(-proj1_sig a)%Q <= x -> x <= ' proj1_sig a -> |
| 298 |
CRboundAbs a x == x)%CR. |
| 299 |
Proof. |
| 300 |
intros a x Ha Hb. |
| 301 |
unfold CRboundAbs. |
| 302 |
transitivity (uc_compose (Cmap QPrelengthSpace (QboundBelow_uc (-proj1_sig a))) (Cmap QPrelengthSpace (QboundAbove_uc (proj1_sig a))) x). |
| 303 |
simpl (Cmap QPrelengthSpace (QboundAbs a) x). |
| 304 |
simpl ((Cmap QPrelengthSpace (QboundBelow_uc (- ` a)) |
| 305 |
∘ Cmap QPrelengthSpace (QboundAbove_uc (` a))) x). |
| 306 |
repeat rewrite -> Cmap_fun_correct. |
| 307 |
apply MonadLaw2. |
| 308 |
simpl ((Cmap QPrelengthSpace (QboundBelow_uc (- ` a)) |
| 309 |
∘ Cmap QPrelengthSpace (QboundAbove_uc (` a))) x). |
| 310 |
change (boundBelow (-proj1_sig a) (boundAbove (proj1_sig a) x) == x)%CR. |
| 311 |
assert (X:(boundAbove (proj1_sig a) x==x)%CR). |
| 312 |
rewrite <- CRmin_boundAbove. |
| 313 |
rewrite <- CRle_min_r. |
| 314 |
assumption. |
| 315 |
rewrite -> X. |
| 316 |
rewrite <- CRmax_boundBelow. |
| 317 |
rewrite <- CRle_max_r. |
| 318 |
assumption. |
| 319 |
Qed. |
| 320 |
|
| 321 |
Lemma QboundAbs_elim : forall (z:Qpos) (a:Q) (P:Q->Prop), |
| 322 |
((proj1_sig z <= a)%Q -> P (proj1_sig z)) -> |
| 323 |
((a <= -proj1_sig z)%Q -> P (- proj1_sig z)%Q) -> |
| 324 |
(QAbsSmall (proj1_sig z) a -> P (a)) -> |
| 325 |
P (QboundAbs z a). |
| 326 |
Proof. |
| 327 |
intros z a P H1 H2 H3. |
| 328 |
simpl. |
| 329 |
apply Qmax_case; apply Qmin_case; intros Z0 Z1; try solve [apply H1;assumption|apply H2;assumption]. |
| 330 |
elim (Qle_not_lt _ _ Z1). |
| 331 |
rewrite -> Qlt_minus_iff. |
| 332 |
ring_simplify. |
| 333 |
apply (Qpos_ispos ((2#1)*z)). |
| 334 |
apply H3. |
| 335 |
split;assumption. |
| 336 |
Qed. |
| 337 |
|
| 338 |
Lemma QboundAbs_abs : forall (z:Qpos) (a:Q), |
| 339 |
Qabs (QboundAbs z a) == Qmin (Qabs a) (proj1_sig z). |
| 340 |
Proof. |
| 341 |
intros. apply QboundAbs_elim. |
| 342 |
- intros. symmetry. rewrite Qabs_pos, Qabs_pos. |
| 343 |
apply Qle_min_r, H. apply Qpos_nonneg. |
| 344 |
apply (Qle_trans _ (`z)). apply Qpos_nonneg. exact H. |
| 345 |
- intros. symmetry. rewrite Qabs_opp. |
| 346 |
rewrite (Qabs_pos (`z)). apply Qle_min_r. |
| 347 |
rewrite Qabs_neg, <- Qopp_involutive. |
| 348 |
apply Qopp_le_compat, H. |
| 349 |
apply (Qle_trans _ _ _ H). apply (Qopp_le_compat 0), Qpos_nonneg. |
| 350 |
apply Qpos_nonneg. |
| 351 |
- intros. symmetry. apply Qle_min_l. |
| 352 |
apply AbsSmall_Qabs in H. exact H. |
| 353 |
Qed. |
| 354 |
|
| 355 |
|
| 356 |
(** The modulus of continuity for multiplication depends on the |
| 357 |
bound, c, on the second argument. *) |
| 358 |
Definition Qmult_modulus (c:Qpos)(e:Qpos) : QposInf |
| 359 |
:= Qpos2QposInf (e * Qpos_inv c). |
| 360 |
|
| 361 |
Lemma Qmult_uc_prf (c:Qpos) |
| 362 |
: @is_UniformlyContinuousFunction |
| 363 |
Q_as_MetricSpace (Q_as_MetricSpace --> Q_as_MetricSpace) |
| 364 |
(fun a:Q => uc_compose (Qscale_uc a) (QboundAbs c)) (Qmult_modulus c). |
| 365 |
Proof with simpl in *; auto with *. |
| 366 |
intros e a0 a1 H. split. apply Qpos_nonneg. intro b. |
| 367 |
simpl in *. |
| 368 |
set (b' := Qmax (- proj1_sig c) (Qmin (proj1_sig c) b)). |
| 369 |
repeat rewrite -> (fun x => Qmult_comm x b'). |
| 370 |
apply Qscale_uc_prf. |
| 371 |
assert (QposEq (e * Qpos_inv c) (Qpos_inv c*e)%Qpos) |
| 372 |
by (unfold QposEq; simpl; ring). |
| 373 |
apply (ball_wd _ H0 _ _ (reflexivity _) _ _ (reflexivity _)) in H. clear H0. |
| 374 |
apply ball_ex_weak_le with (Qpos_inv c*e)%Qpos;[|assumption]. |
| 375 |
unfold b'. |
| 376 |
destruct c as [[cn cd] cpos]. |
| 377 |
destruct cn as [|cn|cn]. inversion cpos. 2: inversion cpos. |
| 378 |
apply Qmax_case. intros. apply Qle_refl. simpl. |
| 379 |
apply Qmin_case. intros. apply Qle_refl. |
| 380 |
intros H1 H2. |
| 381 |
destruct b as [[|bn|bn] bd]... |
| 382 |
- apply Qmult_le_r. destruct e; exact q. |
| 383 |
apply Qle_shift_inv_r. reflexivity. |
| 384 |
rewrite <- Qmult_1_l in H1. |
| 385 |
apply Qle_shift_div_l in H1. |
| 386 |
apply (Qle_trans _ _ _ H1). rewrite Qmult_comm. |
| 387 |
apply Qmult_le_l. reflexivity. apply Z.le_refl. reflexivity. |
| 388 |
- apply Qmult_le_r. destruct e; exact q. |
| 389 |
apply Qle_shift_inv_r. reflexivity. |
| 390 |
apply Qopp_le_compat in H2. rewrite Qopp_involutive in H2. |
| 391 |
rewrite <- Qmult_1_l in H2. |
| 392 |
apply Qle_shift_div_l in H2. 2: reflexivity. |
| 393 |
apply (Qle_trans _ _ _ H2). rewrite Qmult_comm. |
| 394 |
apply Qmult_le_l. reflexivity. apply Z.le_refl. |
| 395 |
Qed. |
| 396 |
|
| 397 |
(* begin hide *) |
| 398 |
Arguments Qmult_uc_prf : clear implicits. |
| 399 |
(* end hide *) |
| 400 |
Definition Qmult_uc (c:Qpos) |
| 401 |
: Q_as_MetricSpace --> Q_as_MetricSpace --> Q_as_MetricSpace |
| 402 |
:= Build_UniformlyContinuousFunction (Qmult_uc_prf c). |
| 403 |
|
| 404 |
(** This multiplication function is correct when yBound is a bound |
| 405 |
on the absolute value of the second CR argument. *) |
| 406 |
Definition CRmult_bounded (yBound : Qpos) : CR --> CR --> CR |
| 407 |
:= Cmap2 QPrelengthSpace QPrelengthSpace (Qmult_uc yBound). |
| 408 |
|
| 409 |
#[global] |
| 410 |
Instance: Proper (QposEq ==> @msp_eq _) Qmult_uc. |
| 411 |
Proof. |
| 412 |
intros e1 e2 E. |
| 413 |
simpl. split. discriminate. |
| 414 |
intro a. simpl. split. discriminate. |
| 415 |
intro b. simpl. |
| 416 |
apply Qball_0. |
| 417 |
unfold QposEq in E. rewrite E. |
| 418 |
reflexivity. |
| 419 |
Qed. |
| 420 |
|
| 421 |
#[global] |
| 422 |
Instance CRmult_bounded_wd : Proper (QposEq ==> @msp_eq _) CRmult_bounded. |
| 423 |
Proof. |
| 424 |
intros e1 e2 E. |
| 425 |
simpl. split. discriminate. |
| 426 |
intro x1. split. discriminate. |
| 427 |
intro x2. |
| 428 |
simpl (CRmult_bounded e1 x1 x2). |
| 429 |
simpl (CRmult_bounded e2 x1 x2). |
| 430 |
rewrite E. reflexivity. |
| 431 |
Qed. |
| 432 |
|
| 433 |
(** CR_b computes a rational bound on the absolute value of x *) |
| 434 |
|
| 435 |
Lemma CR_b_pos (e : Qpos) (x : CR) : 0 < Qabs (approximate x e) + proj1_sig e. |
| 436 |
Proof. |
| 437 |
apply (Qle_lt_trans _ (Qabs (approximate x e) + 0)). |
| 438 |
rewrite Qplus_0_r. apply Qabs_nonneg. |
| 439 |
apply Qplus_lt_r, Qpos_ispos. |
| 440 |
Qed. |
| 441 |
|
| 442 |
Definition CR_b (e:Qpos) (x:CR) : Qpos |
| 443 |
:= exist (Qlt 0) (Qabs (approximate x e) + proj1_sig e) |
| 444 |
(CR_b_pos _ _). |
| 445 |
|
| 446 |
Lemma CR_b_lowerBound : forall e x, (' (-proj1_sig (CR_b e x))%Q <= x)%CR. |
| 447 |
Proof. |
| 448 |
intros e x e'. |
| 449 |
unfold CR_b. |
| 450 |
simpl. |
| 451 |
unfold Cap_raw. |
| 452 |
simpl. |
| 453 |
rewrite -> Qle_minus_iff, Qopp_involutive, Qopp_involutive. |
| 454 |
destruct (regFun_prf x ((1#2)*e')%Qpos e) as [H _]. |
| 455 |
simpl in H. |
| 456 |
rewrite -> Qle_minus_iff in H. |
| 457 |
ring_simplify in H. |
| 458 |
apply (Qle_trans _ _ _ H). |
| 459 |
rewrite -> Qle_minus_iff. |
| 460 |
ring_simplify. |
| 461 |
clear H. |
| 462 |
apply Qabs_case; intros H. |
| 463 |
apply (Qle_trans _ (approximate x e + 0)). |
| 464 |
rewrite Qplus_0_r. exact H. rewrite <- Qplus_assoc. |
| 465 |
apply Qplus_le_r. |
| 466 |
apply (Qle_trans _ (0+approximate x e)). |
| 467 |
rewrite Qplus_0_l. exact H. |
| 468 |
apply Qplus_le_l. apply (Qpos_nonneg ((1#2)*e')). |
| 469 |
ring_simplify. apply (Qpos_nonneg ((1#2)*e')). |
| 470 |
Qed. |
| 471 |
|
| 472 |
Lemma CR_b_upperBound : forall e x, (x <= 'proj1_sig (CR_b e x))%CR. |
| 473 |
Proof. |
| 474 |
intros e x e'. |
| 475 |
unfold CR_b. |
| 476 |
simpl. |
| 477 |
unfold Cap_raw. |
| 478 |
simpl. |
| 479 |
rewrite -> Qle_minus_iff. |
| 480 |
ring_simplify. |
| 481 |
destruct (regFun_prf x ((1#2)*e')%Qpos e) as [_ H]. |
| 482 |
simpl in H. |
| 483 |
rewrite -> Qle_minus_iff in H. |
| 484 |
ring_simplify in H. |
| 485 |
eapply Qle_trans. |
| 486 |
apply H. |
| 487 |
rewrite -> Qle_minus_iff. |
| 488 |
ring_simplify. |
| 489 |
clear H. |
| 490 |
apply Qabs_case; intros H. |
| 491 |
ring_simplify. apply (Qpos_nonneg ((1#2)*e')). |
| 492 |
apply (Qplus_le_r _ _ ((2#1)*approximate x e)). |
| 493 |
simpl. ring_simplify. |
| 494 |
apply (Qle_trans _ 0). |
| 495 |
rewrite <- (Qmult_0_r (2#1)). apply Qmult_le_l. |
| 496 |
reflexivity. exact H. apply (Qpos_nonneg ((1#2)*e')). |
| 497 |
Qed. |
| 498 |
|
| 499 |
(** This version of multiply computes a bound on the second argument |
| 500 |
just in time. It should be avoided in favour of the bounded version |
| 501 |
whenever possible. *) |
| 502 |
#[global] |
| 503 |
Instance CRmult: Mult CR := λ x y, ucFun2 (CRmult_bounded (CR_b (1#1) y)) x y. |
| 504 |
|
| 505 |
Infix "*" := CRmult : CR_scope. |
| 506 |
|
| 507 |
Lemma CRmult_bounded_weaken : forall (c1 c2:Qpos) x y, |
| 508 |
((' (-proj1_sig c1)%Q <= y) -> (y <= ' proj1_sig c1) |
| 509 |
-> (proj1_sig c1 <= proj1_sig c2)%Q -> |
| 510 |
CRmult_bounded c1 x y == CRmult_bounded c2 x y)%CR. |
| 511 |
Proof. |
| 512 |
intros c1 c2 x y Hc1a Hc1b Hc2. |
| 513 |
assert (Hy:=CRboundAbs_Eq _ Hc1a Hc1b). |
| 514 |
set (y':= (CRboundAbs c1 y)) in *. |
| 515 |
transitivity (ucFun2 (CRmult_bounded c2) x y'); [|rewrite -> Hy;reflexivity]. |
| 516 |
assert (H:forall x:Qpos, proj1_sig (x*c1*Qpos_inv c2)%Qpos <= proj1_sig x). |
| 517 |
{ intros a. |
| 518 |
simpl. |
| 519 |
rewrite <- (Qmult_1_r (`a)), <- Qmult_assoc, <- Qmult_assoc. |
| 520 |
apply Qmult_le_l. destruct a; exact q. |
| 521 |
rewrite Qmult_1_l. apply Qle_shift_div_r. |
| 522 |
destruct c2; exact q. rewrite Qmult_1_l. exact Hc2. } |
| 523 |
change (ucFun2 (CRmult_bounded c1) x y == ucFun2 (CRmult_bounded c2) x y')%CR. |
| 524 |
rewrite <- (QreduceApprox_Eq x). |
| 525 |
set (x''':=(QreduceApprox x)). |
| 526 |
set (x':=faster x''' (fun x => (x * c1 * Qpos_inv c2)%Qpos) H). |
| 527 |
transitivity (ucFun2 (CRmult_bounded c1) x' y). |
| 528 |
unfold x'. |
| 529 |
rewrite -> fasterIsEq. |
| 530 |
reflexivity. |
| 531 |
apply regFunEq_equiv, regFunEq_e; intros e. |
| 532 |
intros. |
| 533 |
simpl. |
| 534 |
do 3 (unfold Cap_raw; simpl). |
| 535 |
assert (X:=fun c => QboundAbs_absorb _ _ c Hc2). |
| 536 |
unfold QboundAbs in X. |
| 537 |
simpl in X. |
| 538 |
rewrite -> X. |
| 539 |
clear X. |
| 540 |
assert (eq (Qpos_red ((1 # 2) * e * Qpos_inv c1 * c1 * Qpos_inv c2)) |
| 541 |
(Qpos_red ((1 # 2) * e * Qpos_inv c2))). |
| 542 |
{ apply Qpos_red_eq. unfold QposEq. simpl. field. |
| 543 |
split. intro abs. destruct c2. simpl in abs. |
| 544 |
apply (Qlt_not_le _ _ q). rewrite abs. apply Qle_refl. |
| 545 |
intro abs. destruct c1. simpl in abs. |
| 546 |
apply (Qlt_not_le _ _ q). rewrite abs. apply Qle_refl. } |
| 547 |
simpl. simpl in H0. rewrite H0. |
| 548 |
do 2 rewrite QposInf_bind_id. apply Qball_Reflexive. |
| 549 |
apply (Qpos_nonneg (e+e)). |
| 550 |
Qed. |
| 551 |
|
| 552 |
Lemma CRmult_bounded_mult : forall (c:Qpos) (x y:CR), |
| 553 |
(' (-proj1_sig c)%Q <= y -> y <= ' proj1_sig c -> |
| 554 |
CRmult_bounded c x y == x*y)%CR. |
| 555 |
Proof. |
| 556 |
intros c x y Hc1 Hc2. |
| 557 |
unfold CRmult. |
| 558 |
set (d:=(CR_b (1 # 1) y)). |
| 559 |
destruct (Qle_total (proj1_sig c) (proj1_sig d)). |
| 560 |
apply CRmult_bounded_weaken; assumption. |
| 561 |
symmetry. |
| 562 |
apply CRmult_bounded_weaken; try assumption. |
| 563 |
apply CR_b_lowerBound. |
| 564 |
apply CR_b_upperBound. |
| 565 |
Qed. |
| 566 |
(* begin hide *) |
| 567 |
Add Morphism CRmult with signature (@msp_eq _) ==> (@msp_eq _) ==> (@msp_eq _) |
| 568 |
as CRmult_wd. |
| 569 |
Proof. |
| 570 |
intros x1 x2 Hx y1 y2 Hy. |
| 571 |
unfold CRmult. |
| 572 |
set (c:=(CR_b (1 # 1) y1)). |
| 573 |
set (d:=(CR_b (1 # 1) y2)). |
| 574 |
rewrite -> Hx. |
| 575 |
rewrite -> Hy. |
| 576 |
unfold d. |
| 577 |
apply CRmult_bounded_mult; rewrite <- Hy. |
| 578 |
apply CR_b_lowerBound. |
| 579 |
apply CR_b_upperBound. |
| 580 |
Qed. |
| 581 |
(* end hide *) |
| 582 |
Lemma CRmult_scale : forall (a:Q) (y:CR), ((' a)*y==scale a y)%CR. |
| 583 |
Proof. |
| 584 |
intros a y. |
| 585 |
unfold CRmult. |
| 586 |
unfold CRmult_bounded. |
| 587 |
unfold ucFun2. |
| 588 |
unfold Cmap2. |
| 589 |
unfold inject_Q_CR. |
| 590 |
change (msp_eq |
| 591 |
(Cap_fun QPrelengthSpace |
| 592 |
(Cmap_fun QPrelengthSpace (Qmult_uc (CR_b (1 ↾ eq_refl) y)) |
| 593 |
(Cunit_fun Q_as_MetricSpace a)) y) |
| 594 |
(Cmap_fun QPrelengthSpace (Qscale_uc a) y)). |
| 595 |
rewrite -> Cap_fun_correct. |
| 596 |
repeat rewrite -> Cmap_fun_correct. |
| 597 |
rewrite -> MonadLaw3. |
| 598 |
rewrite -> StrongMonadLaw1. |
| 599 |
change (msp_eq (Cmap_slow_fun (Qscale_uc a ∘ QboundAbs (CR_b (1 ↾ eq_refl) y)) y) |
| 600 |
(Cmap_slow_fun (Qscale_uc a) y)). |
| 601 |
transitivity (uc_compose (Cmap QPrelengthSpace (Qscale_uc a)) |
| 602 |
(Cmap QPrelengthSpace (QboundAbs (CR_b (1#1) y))) y). |
| 603 |
simpl ((Cmap QPrelengthSpace (Qscale_uc a) |
| 604 |
∘ Cmap QPrelengthSpace (QboundAbs (CR_b (1 ↾ eq_refl) y))) y). |
| 605 |
repeat rewrite -> Cmap_fun_correct. |
| 606 |
apply MonadLaw2. |
| 607 |
simpl ((Cmap QPrelengthSpace (Qscale_uc a) |
| 608 |
∘ Cmap QPrelengthSpace (QboundAbs (CR_b (1 ↾ eq_refl) y))) y). |
| 609 |
repeat rewrite -> Cmap_fun_correct. |
| 610 |
change (Cmap_slow (Qscale_uc a) (Cmap_slow_fun (QboundAbs (CR_b (1 # 1) y)) y) == |
| 611 |
Cmap_slow (Qscale_uc a) y)%CR. |
| 612 |
apply uc_wd. |
| 613 |
rewrite <- (Cmap_fun_correct (Y:=Q_as_MetricSpace) QPrelengthSpace). |
| 614 |
apply CRboundAbs_Eq. |
| 615 |
apply CR_b_lowerBound. |
| 616 |
apply CR_b_upperBound. |
| 617 |
Qed. |
| 618 |
(* begin hide *) |
| 619 |
#[global] |
| 620 |
Hint Rewrite CRmult_scale : CRfast_compute. |
| 621 |
(* end hide *) |
| 622 |
Lemma scale_Qmult : forall a b:Q, (scale a ('b)=='(a*b)%Q)%CR. |
| 623 |
Proof. |
| 624 |
intros a b. |
| 625 |
unfold scale. |
| 626 |
change (msp_eq (Cmap_fun QPrelengthSpace (Qscale_uc a) (' b)%CR) (' (a * b)%Q)%CR). |
| 627 |
rewrite -> Cmap_fun_correct. |
| 628 |
apply MonadLaw3. |
| 629 |
Qed. |
| 630 |
(* begin hide *) |
| 631 |
#[global] |
| 632 |
Hint Rewrite scale_Qmult : CRfast_compute. |
| 633 |
(* end hide *) |
| 634 |
(** |
| 635 |
** Inverse |
| 636 |
The modulus of continuity for inverse depends on a rational bound |
| 637 |
away from 0 of x. *) |
| 638 |
Definition Qinv_modulus (c:Qpos) (e:Qpos) : Qpos := (c*c*e)%Qpos. |
| 639 |
|
| 640 |
Lemma Qpos_Qmax : forall (a:Qpos) (b:Q), 0<Qmax (proj1_sig a) b. |
| 641 |
Proof. |
| 642 |
intros a b. |
| 643 |
apply Qmax_case; intros H. |
| 644 |
destruct a; exact q. |
| 645 |
apply Qlt_le_trans with (proj1_sig a). |
| 646 |
destruct a; exact q. |
| 647 |
assumption. |
| 648 |
Qed. |
| 649 |
|
| 650 |
Lemma Qinv_pos_uc_prf (c:Qpos) : |
| 651 |
@is_UniformlyContinuousFunction |
| 652 |
Q_as_MetricSpace Q_as_MetricSpace |
| 653 |
(fun a:Q => /(Qmax (proj1_sig c) a) ) (Qinv_modulus c). |
| 654 |
Proof. |
| 655 |
intros e a0 a1 Ha. |
| 656 |
simpl in *. |
| 657 |
unfold Qball in *. |
| 658 |
assert (forall (a:Qpos) (b:Q), 0 < Qmax (`a) b) as max_pos. |
| 659 |
{ intros. apply (Qlt_le_trans _ (`a)). |
| 660 |
destruct a; exact q. apply Qmax_ub_l. } |
| 661 |
assert ( 0 < Qmax (` c) a0 * Qmax (` c) a1). |
| 662 |
{ apply (Qle_lt_trans _ (Qmax (`c) a0 * 0)). |
| 663 |
rewrite Qmult_0_r. apply Qle_refl. |
| 664 |
apply Qmult_lt_l. apply max_pos. apply max_pos. } |
| 665 |
apply AbsSmall_Qabs. |
| 666 |
setoid_replace (/ Qmax (` c) a0 - / Qmax (` c) a1) |
| 667 |
with ((Qmax (` c) a1 - Qmax (` c) a0) / (Qmax (` c) a0 * Qmax (` c) a1)). |
| 668 |
2: unfold equiv, stdlib_rationals.Q_eq; field. |
| 669 |
unfold Qdiv. rewrite Qabs_Qmult. |
| 670 |
rewrite (Qabs_pos (/ ( Qmax (` c) a0 * Qmax (` c) a1))). |
| 671 |
2: apply Qlt_le_weak, Qinv_lt_0_compat, H. |
| 672 |
apply Qle_shift_div_r. exact H. |
| 673 |
apply (Qle_trans _ _ _ (Qmax_contract _ _ _)). |
| 674 |
apply AbsSmall_Qabs in Ha. rewrite Qabs_Qminus. |
| 675 |
apply (Qle_trans _ _ _ Ha). |
| 676 |
rewrite (Qmult_comm (`e)). apply Qmult_le_r. |
| 677 |
apply Qpos_ispos. |
| 678 |
apply (Qle_trans _ (`c * Qmax (`c) a1)). |
| 679 |
apply Qmult_le_l. apply Qpos_ispos. apply Qmax_ub_l. |
| 680 |
apply Qmult_le_r. apply max_pos. apply Qmax_ub_l. |
| 681 |
split; intro abs. specialize (max_pos c a1). |
| 682 |
rewrite abs in max_pos. exact (Qlt_irrefl 0 max_pos). |
| 683 |
specialize (max_pos c a0). |
| 684 |
rewrite abs in max_pos. exact (Qlt_irrefl 0 max_pos). |
| 685 |
Qed. |
| 686 |
|
| 687 |
Arguments Qinv_pos_uc_prf : clear implicits. |
| 688 |
|
| 689 |
Definition Qinv_pos_uc (c:Qpos) : Q_as_MetricSpace --> Q_as_MetricSpace := |
| 690 |
Build_UniformlyContinuousFunction (Qinv_pos_uc_prf c). |
| 691 |
|
| 692 |
Lemma Qinv_pos_uc_wd : forall (c1 c2:Qpos), |
| 693 |
(proj1_sig c1 <= proj1_sig c2) |
| 694 |
-> forall x, (proj1_sig c2 <= x) -> msp_eq (Qinv_pos_uc c1 x) (Qinv_pos_uc c2 x). |
| 695 |
Proof. |
| 696 |
intros c1 c2 Hc x Hx. |
| 697 |
simpl. |
| 698 |
setoid_replace (Qmax (proj1_sig c2) x) with x by (rewrite <- Qle_max_r; assumption). |
| 699 |
setoid_replace (Qmax (proj1_sig c1) x) with x. |
| 700 |
apply Qball_Reflexive. discriminate. |
| 701 |
rewrite <- Qle_max_r. |
| 702 |
apply Qle_trans with (proj1_sig c2); assumption. |
| 703 |
Qed. |
| 704 |
|
| 705 |
(** [CRinv_pos] works for inputs greater than c *) |
| 706 |
Definition CRinv_pos (c:Qpos) : CR --> CR := (Cmap QPrelengthSpace (Qinv_pos_uc c)). |
| 707 |
|
| 708 |
Lemma CRinv_pos_weaken : forall (c1 c2:Qpos), |
| 709 |
proj1_sig c1 <= proj1_sig c2 |
| 710 |
-> forall (x:CR), (' proj1_sig c2 <= x -> CRinv_pos c1 x == CRinv_pos c2 x)%CR. |
| 711 |
Proof. |
| 712 |
intros c1 c2 Hc x Hx. |
| 713 |
assert (X:((boundBelow (proj1_sig c2) x)==x)%CR). |
| 714 |
rewrite <- CRmax_boundBelow. |
| 715 |
rewrite <- CRle_max_r. |
| 716 |
assumption. |
| 717 |
rewrite <- X. |
| 718 |
rewrite <- (QreduceApprox_Eq x). |
| 719 |
pose (f:=(fun e:Qpos => (c1*c1*Qpos_inv c2*Qpos_inv c2)*e)%Qpos). |
| 720 |
assert (Y:forall e:Qpos, proj1_sig (f e) <= proj1_sig e). |
| 721 |
{ intros e. |
| 722 |
unfold f. simpl. |
| 723 |
rewrite <- (Qmult_1_l (`e)) at 2. |
| 724 |
apply Qmult_le_r. apply Qpos_ispos. |
| 725 |
apply Qle_shift_div_r. apply Qpos_ispos. |
| 726 |
apply Qle_shift_div_r. apply Qpos_ispos. |
| 727 |
rewrite Qmult_1_l. |
| 728 |
apply (Qle_trans _ (`c1*`c2)). |
| 729 |
apply Qmult_le_l. apply Qpos_ispos. exact Hc. |
| 730 |
apply Qmult_le_r. apply Qpos_ispos. exact Hc. } |
| 731 |
transitivity (CRinv_pos c2 (boundBelow (proj1_sig c2) (faster (QreduceApprox x) f Y))). |
| 732 |
apply regFunEq_equiv, regFunEq_e. |
| 733 |
intros e. |
| 734 |
assert (Z:=Qinv_pos_uc_wd _ _ Hc). |
| 735 |
simpl in Z. |
| 736 |
simpl. |
| 737 |
rewrite -> Z;[|apply Qmax_ub_l]. |
| 738 |
unfold Qinv_modulus. |
| 739 |
replace (Qpos_red (c1 * c1 * e)) with (Qpos_red (f (c2 * c2 * e)%Qpos)); [apply ball_refl|]. |
| 740 |
apply (Qpos_nonneg (e+e)). |
| 741 |
apply Qpos_red_eq. |
| 742 |
unfold f. |
| 743 |
unfold QposEq. |
| 744 |
simpl. |
| 745 |
field. |
| 746 |
apply Qpos_nonzero. |
| 747 |
rewrite -> fasterIsEq. |
| 748 |
reflexivity. |
| 749 |
Qed. |
| 750 |
|
| 751 |
#[global] |
| 752 |
Instance CRinv_pos_uc_Proper : Proper (QposEq ==> @msp_eq _ ==> @msp_eq _) Qinv_pos_uc. |
| 753 |
Proof. |
| 754 |
intros [c1 ?] [c2 ?] E x1 x2 F. unfold QposEq in E. simpl in *. |
| 755 |
apply Qball_0. apply Qball_0 in F. |
| 756 |
rewrite E, F. reflexivity. |
| 757 |
Qed. |
| 758 |
|
| 759 |
#[global] |
| 760 |
Instance: Proper (QposEq ==> @msp_eq _) CRinv_pos. |
| 761 |
Proof. |
| 762 |
intros c1 c2 E. |
| 763 |
apply ucEq_equiv. intro x. |
| 764 |
simpl (CRinv_pos c1 x). |
| 765 |
simpl (CRinv_pos c2 x). |
| 766 |
setoid_replace (Qinv_pos_uc c1) with (Qinv_pos_uc c2). |
| 767 |
easy. |
| 768 |
apply ucEq_equiv. |
| 769 |
intros y. now apply CRinv_pos_uc_Proper. |
| 770 |
Qed. |
| 771 |
|
| 772 |
Lemma CRinv_pos_Qinv : forall (c:Qpos) x, |
| 773 |
(proj1_sig c <= x)%Q -> (CRinv_pos c (' x) == (' (/x)))%CR. |
| 774 |
Proof. |
| 775 |
intros c x H. |
| 776 |
apply regFunEq_equiv, regFunEq_e. |
| 777 |
intros e. |
| 778 |
simpl. |
| 779 |
setoid_replace (Qmax (proj1_sig c) x) with x. |
| 780 |
apply Qball_Reflexive. |
| 781 |
apply (Qpos_nonneg (e+e)). |
| 782 |
rewrite <- Qle_max_r. |
| 783 |
assumption. |
| 784 |
Qed. |
| 785 |
|
| 786 |
(** [CRinvT] works for inputs apart from 0 *) |
| 787 |
Definition CRinvT (x:CR)(x_: (x >< 0)%CR) : CR. |
| 788 |
Proof. |
| 789 |
revert x_. |
| 790 |
intros [[c H]|[c H]]. |
| 791 |
exact ((-(CRinv_pos c (-x)))%CR). |
| 792 |
exact (CRinv_pos c x). |
| 793 |
Defined. |
| 794 |
|
| 795 |
Arguments CRinvT : clear implicits. |
| 796 |
|
| 797 |
Lemma CRinvT_pos_inv : forall (c:Qpos) (x:CR) x_, |
| 798 |
('proj1_sig c <= x -> |
| 799 |
CRinv_pos c x == CRinvT x x_)%CR. |
| 800 |
Proof. |
| 801 |
intros c x [[e He]|[e He]] H. |
| 802 |
assert (X:(' proj1_sig e <= -x)%CR). |
| 803 |
rewrite <- (doubleSpeed_Eq x). |
| 804 |
intros d. |
| 805 |
eapply Qle_trans. |
| 806 |
apply He. |
| 807 |
simpl. |
| 808 |
do 2 (unfold Cap_raw;simpl). |
| 809 |
ring_simplify. |
| 810 |
apply Qle_refl. |
| 811 |
assert (' proj1_sig c <= ' (- proj1_sig e)%Q)%CR. |
| 812 |
eapply CRle_trans. |
| 813 |
apply H. |
| 814 |
intros d. |
| 815 |
eapply Qle_trans. |
| 816 |
apply X. |
| 817 |
simpl. |
| 818 |
do 2 (unfold Cap_raw;simpl). |
| 819 |
rewrite -> Qle_minus_iff. |
| 820 |
ring_simplify. |
| 821 |
apply Qle_refl. |
| 822 |
assert (0 < proj1_sig c) as cpos. |
| 823 |
{ destruct c; exact q. } |
| 824 |
elim (Qlt_not_le _ _ cpos). |
| 825 |
assert (Y:=H0 (e)%Qpos). |
| 826 |
simpl in Y. |
| 827 |
do 2 (unfold Cap_raw in Y ;simpl in Y). |
| 828 |
rewrite -> Qle_minus_iff in Y. |
| 829 |
ring_simplify in Y. |
| 830 |
rewrite -> Qle_minus_iff. |
| 831 |
ring_simplify;assumption. |
| 832 |
assert (' proj1_sig e <= x)%CR. |
| 833 |
rewrite <- (doubleSpeed_Eq x). |
| 834 |
intros d. |
| 835 |
eapply Qle_trans. |
| 836 |
apply He. |
| 837 |
simpl. |
| 838 |
do 2 (unfold Cap_raw;simpl). |
| 839 |
ring_simplify. |
| 840 |
apply Qle_refl. |
| 841 |
destruct (Qle_total (proj1_sig c) (proj1_sig e)); |
| 842 |
[|symmetry]; apply CRinv_pos_weaken; assumption. |
| 843 |
Qed. |
| 844 |
|
| 845 |
Lemma CRinvT_wd : forall (x y:CR) x_ y_, (x == y -> CRinvT x x_ == CRinvT y y_)%CR. |
| 846 |
Proof. |
| 847 |
assert (X:forall x, (0 + x == x)%CR). |
| 848 |
intros x. |
| 849 |
transitivity (doubleSpeed x);[|apply doubleSpeed_Eq]. |
| 850 |
apply regFunEq_equiv, regFunEq_e. |
| 851 |
intros e. |
| 852 |
simpl. |
| 853 |
unfold Cap_raw; simpl. |
| 854 |
rewrite Qplus_0_l. |
| 855 |
apply Qball_Reflexive. apply (Qpos_nonneg (e+e)). |
| 856 |
assert (Y:forall x, (x + - 0 == x)%CR). |
| 857 |
intros x. |
| 858 |
transitivity (doubleSpeed x);[|apply doubleSpeed_Eq]. |
| 859 |
apply regFunEq_equiv, regFunEq_e. |
| 860 |
intros e. |
| 861 |
simpl. |
| 862 |
unfold Cap_raw; simpl. |
| 863 |
rewrite Qplus_0_r. |
| 864 |
apply Qball_Reflexive. apply (Qpos_nonneg (e+e)). |
| 865 |
intros x y [[c x_]|[c x_]] [[d y_]|[d y_]] H. |
| 866 |
change (-(CRinv_pos c (-x))== (-(CRinv_pos d (-y))))%CR. |
| 867 |
rewrite -> H in *. |
| 868 |
rewrite -> X in *. intros. |
| 869 |
apply CRopp_wd. |
| 870 |
destruct (Qle_total (proj1_sig c) (proj1_sig d)); |
| 871 |
[|symmetry]; apply CRinv_pos_weaken; try assumption. |
| 872 |
assert (0 < proj1_sig c) as cpos. |
| 873 |
{ destruct c; exact q. } |
| 874 |
elim (Qlt_not_le _ _ cpos). |
| 875 |
rewrite -> X in *. |
| 876 |
rewrite -> Y in *. |
| 877 |
rewrite -> H in *. |
| 878 |
assert (Z:=Qplus_le_compat _ _ _ _ (x_ ((1#2)*d)%Qpos) (y_ ((1#2)*d)%Qpos)). |
| 879 |
simpl in Z. |
| 880 |
unfold Cap_raw in Z; simpl in Z. |
| 881 |
autorewrite with QposElim in Z. |
| 882 |
rewrite -> Qle_minus_iff in Z. |
| 883 |
ring_simplify in Z. |
| 884 |
rewrite -> Qle_minus_iff. |
| 885 |
ring_simplify. |
| 886 |
assumption. |
| 887 |
assert (0 < proj1_sig c) as cpos. |
| 888 |
{ destruct c; exact q. } |
| 889 |
elim (Qlt_not_le _ _ cpos). |
| 890 |
rewrite -> X in *. |
| 891 |
rewrite -> Y in *. |
| 892 |
rewrite -> H in *. |
| 893 |
assert (Z:=Qplus_le_compat _ _ _ _ (x_ ((1#2)*d)%Qpos) (y_ ((1#2)*d)%Qpos)). |
| 894 |
simpl in Z. |
| 895 |
unfold Cap_raw in Z; simpl in Z. |
| 896 |
autorewrite with QposElim in Z. |
| 897 |
rewrite -> Qle_minus_iff in Z. |
| 898 |
ring_simplify in Z. |
| 899 |
rewrite -> Qle_minus_iff. |
| 900 |
ring_simplify. |
| 901 |
assumption. |
| 902 |
change (CRinv_pos c x== (CRinv_pos d y))%CR. |
| 903 |
rewrite -> H in *. |
| 904 |
rewrite -> Y in *. |
| 905 |
destruct (Qle_total (proj1_sig c) (proj1_sig d)); |
| 906 |
[|symmetry]; apply CRinv_pos_weaken; try assumption. |
| 907 |
Qed. |
| 908 |
|
| 909 |
Lemma CRinvT_irrelevant : forall x x_ x__, (CRinvT x x_ == CRinvT x x__)%CR. |
| 910 |
Proof. |
| 911 |
intros. |
| 912 |
apply CRinvT_wd. |
| 913 |
reflexivity. |
| 914 |
Qed. |
| 915 |
|
| 916 |
(* Non-curried equivalent version of multiplication. *) |
| 917 |
|
| 918 |
Lemma QboundAbs_contract : forall (c : Qpos) (j k : Q), |
| 919 |
Qabs (QboundAbs c j - QboundAbs c k) <= Qabs (j-k). |
| 920 |
Proof. |
| 921 |
intros. apply QboundAbs_elim. |
| 922 |
- intros. apply QboundAbs_elim. |
| 923 |
+ intros. unfold Qminus. rewrite Qplus_opp_r. apply Qabs_nonneg. |
| 924 |
+ intros. unfold Qminus. rewrite Qopp_involutive. |
| 925 |
rewrite Qabs_pos, Qabs_pos. |
| 926 |
apply Qplus_le_compat. exact H. |
| 927 |
rewrite <- Qopp_involutive. apply Qopp_le_compat. exact H0. |
| 928 |
apply (Qle_trans _ (`c + `c)). |
| 929 |
apply (Qpos_nonneg (c+c)). |
| 930 |
apply Qplus_le_compat. exact H. |
| 931 |
rewrite <- Qopp_involutive. apply Qopp_le_compat. exact H0. |
| 932 |
apply (Qpos_nonneg (c+c)). |
| 933 |
+ intros [H0 H1]. rewrite Qabs_pos. |
| 934 |
2: unfold Qminus; rewrite <- Qle_minus_iff; exact H1. |
| 935 |
apply (Qle_trans _ (j-k)). |
| 936 |
apply Qplus_le_l. exact H. apply Qle_Qabs. |
| 937 |
- intros. apply QboundAbs_elim. |
| 938 |
+ intros. |
| 939 |
setoid_replace (- `c - `c) with (-(`c+`c)) |
| 940 |
by (unfold equiv, stdlib_rationals.Q_eq; ring). |
| 941 |
rewrite Qabs_opp. |
| 942 |
rewrite Qabs_pos. 2: apply (Qpos_nonneg (c+c)). |
| 943 |
rewrite Qabs_Qminus. rewrite Qabs_pos. |
| 944 |
apply Qplus_le_compat. exact H0. |
| 945 |
rewrite <- Qopp_involutive. apply Qopp_le_compat. exact H. |
| 946 |
apply (Qle_trans _ (`c + `c)). |
| 947 |
apply (Qpos_nonneg (c+c)). |
| 948 |
apply Qplus_le_compat. exact H0. |
| 949 |
rewrite <- Qopp_involutive. apply Qopp_le_compat. exact H. |
| 950 |
+ intros. unfold Qminus. |
| 951 |
rewrite Qopp_involutive, Qplus_comm, Qplus_opp_r. |
| 952 |
apply Qabs_nonneg. |
| 953 |
+ intros [H0 H1]. |
| 954 |
setoid_replace (- `c - k) with (-(`c+k)) |
| 955 |
by (unfold equiv, stdlib_rationals.Q_eq; ring). |
| 956 |
rewrite Qabs_opp. rewrite Qabs_pos, Qabs_Qminus. |
| 957 |
apply (Qle_trans _ (k-j)). |
| 958 |
rewrite Qplus_comm. |
| 959 |
apply Qplus_le_r. rewrite <- Qopp_involutive. |
| 960 |
apply Qopp_le_compat. exact H. apply Qle_Qabs. |
| 961 |
apply (Qplus_le_l _ _ (-`c)). ring_simplify. |
| 962 |
ring_simplify in H0. exact H0. |
| 963 |
- intros [H0 H1]. apply QboundAbs_elim. |
| 964 |
+ intros. rewrite Qabs_Qminus, Qabs_pos. |
| 965 |
rewrite Qabs_Qminus, Qabs_pos. apply Qplus_le_l, H. |
| 966 |
unfold Qminus. rewrite <- Qle_minus_iff. |
| 967 |
exact (Qle_trans _ _ _ H1 H). unfold Qminus. |
| 968 |
rewrite <- Qle_minus_iff. exact H1. |
| 969 |
+ intros. unfold Qminus. rewrite Qopp_involutive, Qabs_pos. |
| 970 |
apply (Qle_trans _ (j-k)). apply Qplus_le_r. |
| 971 |
rewrite <- Qopp_involutive. apply Qopp_le_compat. exact H. |
| 972 |
apply Qle_Qabs. apply (Qplus_le_l _ _ (`c)) in H0. |
| 973 |
ring_simplify in H0. rewrite Qplus_comm. exact H0. |
| 974 |
+ intros [H2 H3]. apply Qle_refl. |
| 975 |
Qed. |
| 976 |
|
| 977 |
Lemma Qmult_uc_uncurry (c:Qpos) |
| 978 |
: @is_UniformlyContinuousFunction |
| 979 |
(ProductMS Q_as_MetricSpace Q_as_MetricSpace) |
| 980 |
Q_as_MetricSpace |
| 981 |
(fun ab => QboundAbs c (fst ab) * QboundAbs c (snd ab)) |
| 982 |
(fun e => Qmult_modulus c ((1#2)*e)). |
| 983 |
Proof. |
| 984 |
assert (forall i j k l : Q, Qabs (i*j-k*l) <= Qabs j * Qabs(i-k) + Qabs(j-l)*Qabs k)%Q |
| 985 |
as multMaj. |
| 986 |
{ intros. |
| 987 |
setoid_replace (i*j-k*l)%Q with (j*(i-k)+ (j-l)*k)%Q |
| 988 |
by (unfold equiv, stdlib_rationals.Q_eq; ring). |
| 989 |
apply (Qle_trans _ _ _ (Qabs_triangle _ _)). |
| 990 |
rewrite Qabs_Qmult, Qabs_Qmult. apply Qle_refl. } |
| 991 |
assert (forall i:Q, Qabs (QboundAbs c i) <= ` c) as bound. |
| 992 |
{ intro i. apply Qabs_Qle_condition. split. |
| 993 |
apply Qmax_ub_l. apply Qmax_lub. |
| 994 |
apply (Qle_trans _ 0). apply (Qopp_le_compat 0). |
| 995 |
apply Qpos_nonneg. apply Qpos_nonneg. apply Qmin_lb_l. } |
| 996 |
simpl. unfold Qmult_modulus. |
| 997 |
intros e1 [i j] [k l] [H H0]. simpl. |
| 998 |
simpl in H, H0. |
| 999 |
apply AbsSmall_Qabs. |
| 1000 |
apply AbsSmall_Qabs in H. |
| 1001 |
apply AbsSmall_Qabs in H0. |
| 1002 |
apply (Qle_trans _ _ _ (multMaj _ _ _ _)). |
| 1003 |
apply (Qle_trans _ (`c * (Qabs (QboundAbs c i - QboundAbs c k)) |
| 1004 |
+ `c * (Qabs (QboundAbs c j - QboundAbs c l)))). |
| 1005 |
- apply Qplus_le_compat. |
| 1006 |
apply Qmult_le_compat_r. 2: apply Qabs_nonneg. |
| 1007 |
apply bound. |
| 1008 |
rewrite Qmult_comm. apply Qmult_le_compat_r. |
| 1009 |
2: apply Qabs_nonneg. apply bound. |
| 1010 |
- apply (Qle_trans _ ((1#2)*`e1+(1#2)*`e1)). |
| 1011 |
apply Qplus_le_compat. |
| 1012 |
apply (Qle_trans _ (`c * Qabs (i-k))). |
| 1013 |
apply Qmult_le_l. apply Qpos_ispos. apply QboundAbs_contract. |
| 1014 |
rewrite Qmult_comm. |
| 1015 |
apply (Qmult_le_r _ _ (/ `c)). |
| 1016 |
apply Qinv_lt_0_compat, Qpos_ispos. |
| 1017 |
rewrite <- Qmult_assoc, Qmult_inv_r, Qmult_1_r. |
| 1018 |
exact H. apply Qpos_nonzero. |
| 1019 |
apply (Qle_trans _ (`c * Qabs (j-l))). |
| 1020 |
apply Qmult_le_l. apply Qpos_ispos. apply QboundAbs_contract. |
| 1021 |
rewrite Qmult_comm. |
| 1022 |
apply (Qmult_le_r _ _ (/ `c)). |
| 1023 |
apply Qinv_lt_0_compat, Qpos_ispos. |
| 1024 |
rewrite <- Qmult_assoc, Qmult_inv_r, Qmult_1_r. |
| 1025 |
exact H0. apply Qpos_nonzero. |
| 1026 |
ring_simplify. apply Qle_refl. |
| 1027 |
Qed. |
| 1028 |
|
| 1029 |
Definition Qmult_uncurry (c : Qpos) |
| 1030 |
: (ProductMS Q_as_MetricSpace Q_as_MetricSpace) --> Q_as_MetricSpace |
| 1031 |
:= Build_UniformlyContinuousFunction (@Qmult_uc_uncurry c). |
| 1032 |
|
| 1033 |
Lemma CRmult_uncurry_eq : forall (c:Qpos) (x y : CR), |
| 1034 |
(' (-proj1_sig c)%Q <= x)%CR |
| 1035 |
-> (x <= ' (proj1_sig c)%Q)%CR |
| 1036 |
-> (CRmult_bounded c x y |
| 1037 |
== (Cmap (ProductMS_prelength QPrelengthSpace QPrelengthSpace) |
| 1038 |
(Qmult_uncurry c) (undistrib_Complete (x,y))))%CR. |
| 1039 |
Proof. |
| 1040 |
(* Cannot use Cmap2_curry, because CRmult_bounded is not |
| 1041 |
exactly Qmult_uc_uncurry, the first factor is not bounded. *) |
| 1042 |
intros. |
| 1043 |
transitivity (CRmult_bounded c (CRboundAbs c x) y). |
| 1044 |
apply (ucFun2_wd (CRmult_bounded c) x (CRboundAbs c x)). |
| 1045 |
symmetry. apply (CRboundAbs_Eq c H H0). reflexivity. |
| 1046 |
intros e1 e2. rewrite Qplus_0_r. simpl. |
| 1047 |
unfold Cap_raw; simpl. |
| 1048 |
assert (forall i, eq (QposInf_bind (λ e : Qpos, e) i) i) as bind_id. |
| 1049 |
{ intro i. destruct i; reflexivity. } |
| 1050 |
rewrite bind_id. clear bind_id. |
| 1051 |
assert (forall i j k l : Q, Qabs (i*j-k*l) <= Qabs i * Qabs(j-l) + Qabs(i-k)*Qabs l)%Q |
| 1052 |
as multMaj. |
| 1053 |
{ intros. |
| 1054 |
setoid_replace (i*j-k*l)%Q with (i*(j-l)+ (i-k)*l)%Q |
| 1055 |
by (unfold equiv, stdlib_rationals.Q_eq; ring). |
| 1056 |
apply (Qle_trans _ _ _ (Qabs_triangle _ _)). |
| 1057 |
rewrite Qabs_Qmult, Qabs_Qmult. apply Qle_refl. } |
| 1058 |
apply AbsSmall_Qabs. |
| 1059 |
apply (Qle_trans _ _ _ (multMaj _ _ _ _)). |
| 1060 |
apply (Qle_trans _ ((1#2)*`e1 + (1#2)*`e2 +((1#2)*`e1 +(1#2)*`e2))). |
| 1061 |
2: ring_simplify; apply Qle_refl. |
| 1062 |
apply Qplus_le_compat. |
| 1063 |
- apply (Qle_trans |
| 1064 |
_ ( Qabs |
| 1065 |
(approximate y |
| 1066 |
(Qscale_modulus |
| 1067 |
(QboundAbs c (approximate x (Qmult_modulus c ((1 # 2) * e1)))) |
| 1068 |
((1 # 2) * e1)) - |
| 1069 |
(approximate y (Qmult_modulus c ((1 # 2) * e2)))) |
| 1070 |
* Qabs (QboundAbs c (approximate x (Qmult_modulus c ((1 # 2) * e1)))))). |
| 1071 |
rewrite Qmult_comm. |
| 1072 |
apply Qmult_le_compat_r. |
| 1073 |
apply QboundAbs_contract. apply Qabs_nonneg. |
| 1074 |
unfold Qscale_modulus. |
| 1075 |
simpl (Qmult_modulus c ((1 # 2) * e1)). |
| 1076 |
destruct (QboundAbs c (approximate x (Qmult_modulus c ((1 # 2) ↾ @eq_refl comparison Datatypes.Lt * e1)))) eqn:des. |
| 1077 |
destruct Qnum. |
| 1078 |
+ setoid_replace (0#Qden) with (0#1) by reflexivity. |
| 1079 |
rewrite Qmult_0_r. apply (Qpos_nonneg ((1#2)*e1+(1#2)*e2)). |
| 1080 |
+ rewrite Qmult_comm, Qabs_pos. 2: discriminate. |
| 1081 |
apply (Qle_trans _ ((Zpos p#Qden) * |
| 1082 |
((Zpos Qden # p)%Q * ((1 # 2)%Q * `e1) |
| 1083 |
+ (1 # 2) * `e2 / `c))). |
| 1084 |
apply Qmult_le_l. reflexivity. |
| 1085 |
pose proof (regFun_prf y ((Zpos Qden # p)%Q ↾ eq_refl * ((1 # 2)%Q ↾ eq_refl * e1))%Qpos |
| 1086 |
((1 # 2) * e2 * Qpos_inv c)%Qpos) as H3. |
| 1087 |
apply AbsSmall_Qabs in H3. exact H3. |
| 1088 |
rewrite Qmult_plus_distr_r. |
| 1089 |
rewrite Qmult_assoc. |
| 1090 |
setoid_replace ((Zpos p # Qden) * (Zpos Qden # p))%Q with (1#1)%Q |
| 1091 |
by (unfold equiv, stdlib_rationals.Q_eq; unfold Qeq; simpl; rewrite Pos.mul_1_r, Pos.mul_comm; reflexivity). |
| 1092 |
rewrite Qmult_1_l. apply Qplus_le_r. |
| 1093 |
unfold Qdiv. rewrite Qmult_assoc. |
| 1094 |
apply Qle_shift_div_r. apply Qpos_ispos. |
| 1095 |
rewrite Qmult_comm. apply Qmult_le_l. |
| 1096 |
apply (Qpos_ispos ((1#2)*e2)). |
| 1097 |
rewrite <- des. apply Qmax_lub. |
| 1098 |
apply (Qle_trans _ 0). apply (Qopp_le_compat 0). |
| 1099 |
apply Qpos_nonneg. apply Qpos_nonneg. apply Qmin_lb_l. |
| 1100 |
+ rewrite Qmult_comm, Qabs_neg. 2: discriminate. |
| 1101 |
setoid_replace (- (Z.neg p # Qden)) with (Zpos p # Qden) by reflexivity. |
| 1102 |
apply (Qle_trans _ ((Zpos p#Qden) * |
| 1103 |
((Zpos Qden # p)%Q * ((1 # 2)%Q * `e1) |
| 1104 |
+ (1 # 2) * `e2 / `c))). |
| 1105 |
apply Qmult_le_l. reflexivity. |
| 1106 |
pose proof (regFun_prf y ((Zpos Qden # p)%Q ↾ eq_refl * ((1 # 2)%Q ↾ eq_refl * e1))%Qpos |
| 1107 |
((1 # 2) * e2 * Qpos_inv c)%Qpos) as H3. |
| 1108 |
apply AbsSmall_Qabs in H3. exact H3. |
| 1109 |
rewrite Qmult_plus_distr_r. |
| 1110 |
rewrite Qmult_assoc. |
| 1111 |
setoid_replace ((Zpos p # Qden) * (Zpos Qden # p))%Q with (1#1)%Q |
| 1112 |
by (unfold equiv, stdlib_rationals.Q_eq; unfold Qeq; simpl; rewrite Pos.mul_1_r, Pos.mul_comm; reflexivity). |
| 1113 |
rewrite Qmult_1_l. apply Qplus_le_r. |
| 1114 |
unfold Qdiv. rewrite Qmult_assoc. |
| 1115 |
apply Qle_shift_div_r. apply Qpos_ispos. |
| 1116 |
rewrite Qmult_comm. apply Qmult_le_l. |
| 1117 |
apply (Qpos_ispos ((1#2)*e2)). |
| 1118 |
rewrite <- (Qopp_involutive (`c)). |
| 1119 |
setoid_replace (Zpos p # Qden) with (-(Z.neg p # Qden)) by reflexivity. |
| 1120 |
apply Qopp_le_compat. |
| 1121 |
rewrite <- des. apply Qmax_ub_l. |
| 1122 |
- apply (Qle_trans _ (Qabs |
| 1123 |
(approximate x (Qmult_modulus c ((1 # 2) * e1)) - |
| 1124 |
approximate x (Qmult_modulus c ((1 # 2) * e2))) |
| 1125 |
* Qabs (QboundAbs c (approximate y (Qmult_modulus c ((1 # 2) ↾ eq_refl * e2)))))). |
| 1126 |
apply Qmult_le_compat_r. 2: apply Qabs_nonneg. |
| 1127 |
apply QboundAbs_contract. |
| 1128 |
rewrite QboundAbs_abs. |
| 1129 |
apply (Qle_trans _ (`c * Qabs |
| 1130 |
(approximate x (Qmult_modulus c ((1 # 2) * e1)) - |
| 1131 |
approximate x (Qmult_modulus c ((1 # 2) * e2))))). |
| 1132 |
rewrite Qmult_comm. |
| 1133 |
apply Qmult_le_compat_r. 2: apply Qabs_nonneg. |
| 1134 |
apply Qmin_lb_r. |
| 1135 |
apply (Qle_trans _ (`c * ((1#2)*`e1 / `c + (1#2)*`e2 / `c))). |
| 1136 |
apply Qmult_le_l. apply Qpos_ispos. |
| 1137 |
unfold Qmult_modulus. |
| 1138 |
pose proof (regFun_prf x ((1 # 2) * e1 * Qpos_inv c)%Qpos |
| 1139 |
((1 # 2) * e2 * Qpos_inv c)%Qpos) as H3. |
| 1140 |
apply AbsSmall_Qabs in H3. exact H3. |
| 1141 |
rewrite Qmult_plus_distr_r. |
| 1142 |
apply Qplus_le_compat. |
| 1143 |
unfold Qdiv. rewrite Qmult_assoc. |
| 1144 |
apply Qle_shift_div_r. apply Qpos_ispos. |
| 1145 |
rewrite Qmult_comm. apply Qle_refl. |
| 1146 |
unfold Qdiv. rewrite Qmult_assoc. |
| 1147 |
apply Qle_shift_div_r. apply Qpos_ispos. |
| 1148 |
rewrite Qmult_comm. apply Qle_refl. |
| 1149 |
Qed. |
| 1150 |
|
| 1151 |
(* Request bounds on all left factors : x and CRmult_bounded c x y. *) |
| 1152 |
Lemma CRmult_uncurry_eq_3 : forall (c:Qpos) (x y z : CR), |
| 1153 |
(' (- ` c)%Q <= x)%CR |
| 1154 |
-> (x <= 'proj1_sig c)%CR |
| 1155 |
-> (' (- ` c)%Q <= CRmult_bounded c x y)%CR |
| 1156 |
-> (CRmult_bounded c x y <= 'proj1_sig c)%CR |
| 1157 |
-> (CRmult_bounded c (CRmult_bounded c x y) z |
| 1158 |
== Cmap (ProductMS_prelength |
| 1159 |
(ProductMS_prelength QPrelengthSpace QPrelengthSpace) |
| 1160 |
QPrelengthSpace) |
| 1161 |
(uc_compose (Qmult_uncurry c) (together (Qmult_uncurry c) (uc_id Q_as_MetricSpace))) |
| 1162 |
(undistrib_Complete (undistrib_Complete (x,y), z)))%CR. |
| 1163 |
Proof. |
| 1164 |
intros. |
| 1165 |
assert (forall a, Qabs (QboundAbs c a) <= `c) as qbound_bound. |
| 1166 |
{ intros a. rewrite QboundAbs_abs. apply Qmin_lb_r. } |
| 1167 |
rewrite (@CRmult_uncurry_eq c (CRmult_bounded c x y) z); try assumption. |
| 1168 |
assert (msp_eq (undistrib_Complete (CRmult_bounded c x y, z)) |
| 1169 |
(undistrib_Complete ((Cmap (ProductMS_prelength QPrelengthSpace QPrelengthSpace) |
| 1170 |
(Qmult_uncurry c) (undistrib_Complete (x,y))), z))) as H4. |
| 1171 |
{ intros e1 e2. split. |
| 1172 |
apply (@CRmult_uncurry_eq c x y H H0). |
| 1173 |
rewrite Qplus_0_r. |
| 1174 |
apply regFun_prf. } |
| 1175 |
rewrite H4. clear H4. |
| 1176 |
rewrite fast_MonadLaw2. |
| 1177 |
apply Cmap_wd. reflexivity. |
| 1178 |
intros e1 e2. split. |
| 1179 |
- simpl. apply AbsSmall_Qabs. |
| 1180 |
assert (forall i j k l : Q, Qabs (i*j-k*l) <= Qabs i * Qabs(j-l) + Qabs(i-k)*Qabs l)%Q |
| 1181 |
as multMaj. |
| 1182 |
{ intros. |
| 1183 |
setoid_replace (i*j-k*l)%Q with (i*(j-l)+ (i-k)*l)%Q |
| 1184 |
by (unfold equiv, stdlib_rationals.Q_eq; ring). |
| 1185 |
apply (Qle_trans _ _ _ (Qabs_triangle _ _)). |
| 1186 |
rewrite Qabs_Qmult, Qabs_Qmult. apply Qle_refl. } |
| 1187 |
apply (Qle_trans _ ((1#2)*`e1 + (1#2)*`e2 +((1#2)*`e1 +(1#2)*`e2))). |
| 1188 |
2: ring_simplify; apply Qle_refl. |
| 1189 |
apply (Qle_trans _ _ _ (multMaj _ _ _ _)). clear multMaj. |
| 1190 |
apply Qplus_le_compat. |
| 1191 |
+ apply (Qle_trans _ (`c * |
| 1192 |
(Qabs |
| 1193 |
(Qmax (- ` c) |
| 1194 |
(Qmin (` c) (approximate y (Qmult_modulus c ((1 # 2) ↾ eq_refl * e1)))) - |
| 1195 |
Qmax (- ` c) |
| 1196 |
(Qmin (` c) |
| 1197 |
(approximate y (Qpos_min ((1 # 2) ↾ eq_refl * e2 * Qpos_inv c) e2))))))). |
| 1198 |
apply Qmult_le_compat_r. 2: apply Qabs_nonneg. |
| 1199 |
apply qbound_bound. |
| 1200 |
rewrite Qmult_comm. |
| 1201 |
apply (Qle_trans _ (Qabs (approximate y (Qmult_modulus c ((1 # 2) ↾ eq_refl * e1)) - approximate y (Qpos_min ((1 # 2) ↾ eq_refl * e2 * Qpos_inv c) e2)) * `c)). |
| 1202 |
apply Qmult_le_compat_r. 2: apply Qpos_nonneg. |
| 1203 |
apply QboundAbs_contract. |
| 1204 |
apply (Qle_trans _ (((1#2)*`e1 / `c + (1#2)*`e2 / `c) * `c)). |
| 1205 |
apply Qmult_le_r. apply Qpos_ispos. |
| 1206 |
unfold Qmult_modulus. |
| 1207 |
pose proof (regFun_prf y ((1 # 2) * e1 * Qpos_inv c)%Qpos |
| 1208 |
(Qpos_min ((1 # 2) * e2 * Qpos_inv c)%Qpos e2)) as H4. |
| 1209 |
apply AbsSmall_Qabs in H4. |
| 1210 |
apply (Qle_trans _ _ _ H4). clear H4. apply Qplus_le_r. |
| 1211 |
rewrite Q_Qpos_min. simpl. apply Qmin_lb_l. |
| 1212 |
rewrite Qmult_plus_distr_l. |
| 1213 |
apply Qplus_le_compat. |
| 1214 |
unfold Qdiv. rewrite Qmult_comm, Qmult_assoc. |
| 1215 |
apply Qle_shift_div_r. apply Qpos_ispos. |
| 1216 |
rewrite Qmult_comm. apply Qle_refl. |
| 1217 |
unfold Qdiv. rewrite Qmult_comm, Qmult_assoc. |
| 1218 |
apply Qle_shift_div_r. apply Qpos_ispos. |
| 1219 |
rewrite Qmult_comm. apply Qle_refl. |
| 1220 |
+ rewrite Qmult_comm. apply (Qle_trans _ (`c * |
| 1221 |
(Qabs |
| 1222 |
(Qmax (- ` c) |
| 1223 |
(Qmin (` c) (approximate x (Qmult_modulus c ((1 # 2) ↾ eq_refl * e1)))) - |
| 1224 |
Qmax (- ` c) |
| 1225 |
(Qmin (` c) |
| 1226 |
(approximate x (Qpos_min ((1 # 2) ↾ eq_refl * e2 * Qpos_inv c) e2))))))). |
| 1227 |
apply Qmult_le_compat_r. 2: apply Qabs_nonneg. |
| 1228 |
apply qbound_bound. |
| 1229 |
rewrite Qmult_comm. |
| 1230 |
apply (Qle_trans _ (Qabs (approximate x (Qmult_modulus c ((1 # 2) ↾ eq_refl * e1)) - approximate x (Qpos_min ((1 # 2) ↾ eq_refl * e2 * Qpos_inv c) e2)) * `c)). |
| 1231 |
apply Qmult_le_compat_r. 2: apply Qpos_nonneg. |
| 1232 |
apply QboundAbs_contract. |
| 1233 |
apply (Qle_trans _ (((1#2)*`e1 / `c + (1#2)*`e2 / `c) * `c)). |
| 1234 |
apply Qmult_le_r. apply Qpos_ispos. |
| 1235 |
unfold Qmult_modulus. |
| 1236 |
pose proof (regFun_prf x ((1 # 2) * e1 * Qpos_inv c)%Qpos |
| 1237 |
(Qpos_min ((1 # 2) * e2 * Qpos_inv c)%Qpos e2)) as H4. |
| 1238 |
apply AbsSmall_Qabs in H4. |
| 1239 |
apply (Qle_trans _ _ _ H4). clear H4. apply Qplus_le_r. |
| 1240 |
rewrite Q_Qpos_min. simpl. apply Qmin_lb_l. |
| 1241 |
rewrite Qmult_plus_distr_l. |
| 1242 |
apply Qplus_le_compat. |
| 1243 |
unfold Qdiv. rewrite Qmult_comm, Qmult_assoc. |
| 1244 |
apply Qle_shift_div_r. apply Qpos_ispos. |
| 1245 |
rewrite Qmult_comm. apply Qle_refl. |
| 1246 |
unfold Qdiv. rewrite Qmult_comm, Qmult_assoc. |
| 1247 |
apply Qle_shift_div_r. apply Qpos_ispos. |
| 1248 |
rewrite Qmult_comm. apply Qle_refl. |
| 1249 |
- simpl. |
| 1250 |
assert (`e1 + proj1_sig (Qpos_min ((1 # 2) ↾ eq_refl * e2 * Qpos_inv c) e2) |
| 1251 |
<= `e1 + `e2) as H4. |
| 1252 |
{ apply Qplus_le_r. apply Qpos_min_lb_r. } |
| 1253 |
rewrite Qplus_0_r. |
| 1254 |
apply (ball_weak_le _ _ _ H4). apply regFun_prf. |
| 1255 |
Qed. |
| 1256 |
|
| 1257 |
(* Request bounds on all left factors : x and y. *) |
| 1258 |
Lemma CRmult_uncurry_eq_3r : forall (c:Qpos) (x y z : CR), |
| 1259 |
(' (- ` c)%Q <= x)%CR |
| 1260 |
-> (x <= 'proj1_sig c)%CR |
| 1261 |
-> (' (- ` c)%Q <= y)%CR |
| 1262 |
-> (y <= 'proj1_sig c)%CR |
| 1263 |
-> (CRmult_bounded c x (CRmult_bounded c y z) |
| 1264 |
== Cmap (ProductMS_prelength |
| 1265 |
(ProductMS_prelength QPrelengthSpace QPrelengthSpace) |
| 1266 |
QPrelengthSpace) |
| 1267 |
(uc_compose (Qmult_uncurry c) |
| 1268 |
(uc_compose (together (uc_id Q_as_MetricSpace) (Qmult_uncurry c)) (uc_assoc _ _ _))) |
| 1269 |
(undistrib_Complete (undistrib_Complete (x,y), z)))%CR. |
| 1270 |
Proof. |
| 1271 |
intros. |
| 1272 |
assert (forall a, Qabs (QboundAbs c a) <= `c) as qbound_bound. |
| 1273 |
{ intros a. rewrite QboundAbs_abs. apply Qmin_lb_r. } |
| 1274 |
rewrite (@CRmult_uncurry_eq c x (CRmult_bounded c y z)); try assumption. |
| 1275 |
assert (msp_eq (undistrib_Complete (x, CRmult_bounded c y z)) |
| 1276 |
(undistrib_Complete |
| 1277 |
(x, Cmap (ProductMS_prelength QPrelengthSpace QPrelengthSpace) |
| 1278 |
(Qmult_uncurry c) (undistrib_Complete (y,z))))) as H4. |
| 1279 |
{ intros e1 e2. split. |
| 1280 |
rewrite Qplus_0_r. |
| 1281 |
apply regFun_prf. |
| 1282 |
apply (@CRmult_uncurry_eq c y z H1 H2). } |
| 1283 |
rewrite H4. clear H4. |
| 1284 |
rewrite fast_MonadLaw2. |
| 1285 |
apply Cmap_wd. reflexivity. |
| 1286 |
intros e1 e2. rewrite Qplus_0_r. split. |
| 1287 |
- simpl. |
| 1288 |
assert (`e1 + proj1_sig (Qpos_min e2 ((1 # 2) ↾ eq_refl * e2 * Qpos_inv c)) |
| 1289 |
<= `e1 + `e2) as H4. |
| 1290 |
{ apply Qplus_le_r. apply Qpos_min_lb_l. } |
| 1291 |
apply (ball_weak_le _ _ _ H4). apply regFun_prf. |
| 1292 |
- simpl. apply AbsSmall_Qabs. |
| 1293 |
assert (forall i j k l : Q, Qabs (i*j-k*l) <= Qabs i * Qabs(j-l) + Qabs(i-k)*Qabs l)%Q |
| 1294 |
as multMaj. |
| 1295 |
{ intros. |
| 1296 |
setoid_replace (i*j-k*l)%Q with (i*(j-l)+ (i-k)*l)%Q |
| 1297 |
by (unfold equiv, stdlib_rationals.Q_eq; ring). |
| 1298 |
apply (Qle_trans _ _ _ (Qabs_triangle _ _)). |
| 1299 |
rewrite Qabs_Qmult, Qabs_Qmult. apply Qle_refl. } |
| 1300 |
apply (Qle_trans _ ((1#2)*`e1 + (1#2)*`e2 +((1#2)*`e1 +(1#2)*`e2))). |
| 1301 |
2: ring_simplify; apply Qle_refl. |
| 1302 |
apply (Qle_trans _ _ _ (multMaj _ _ _ _)). clear multMaj. |
| 1303 |
apply Qplus_le_compat. |
| 1304 |
+ apply (Qle_trans _ (`c * |
| 1305 |
(Qabs |
| 1306 |
(Qmax (- ` c) |
| 1307 |
(Qmin (` c) (approximate z (Qmult_modulus c ((1 # 2) ↾ eq_refl * e1)))) - |
| 1308 |
Qmax (- ` c) |
| 1309 |
(Qmin (` c) |
| 1310 |
(approximate z (Qpos_min e2 ((1 # 2) ↾ eq_refl * e2 * Qpos_inv c)))))))). |
| 1311 |
apply Qmult_le_compat_r. 2: apply Qabs_nonneg. |
| 1312 |
apply qbound_bound. |
| 1313 |
rewrite Qmult_comm. |
| 1314 |
apply (Qle_trans _ (Qabs (approximate z (Qmult_modulus c ((1 # 2) ↾ eq_refl * e1)) - approximate z (Qpos_min e2 ((1 # 2) ↾ eq_refl * e2 * Qpos_inv c))) * `c)). |
| 1315 |
apply Qmult_le_compat_r. 2: apply Qpos_nonneg. |
| 1316 |
apply QboundAbs_contract. |
| 1317 |
apply (Qle_trans _ (((1#2)*`e1 / `c + (1#2)*`e2 / `c) * `c)). |
| 1318 |
apply Qmult_le_r. apply Qpos_ispos. |
| 1319 |
unfold Qmult_modulus. |
| 1320 |
pose proof (regFun_prf z ((1 # 2) * e1 * Qpos_inv c)%Qpos |
| 1321 |
(Qpos_min e2 ((1 # 2) * e2 * Qpos_inv c)%Qpos)) as H4. |
| 1322 |
apply AbsSmall_Qabs in H4. |
| 1323 |
apply (Qle_trans _ _ _ H4). clear H4. apply Qplus_le_r. |
| 1324 |
rewrite Q_Qpos_min. simpl. apply Qmin_lb_r. |
| 1325 |
rewrite Qmult_plus_distr_l. |
| 1326 |
apply Qplus_le_compat. |
| 1327 |
unfold Qdiv. rewrite Qmult_comm, Qmult_assoc. |
| 1328 |
apply Qle_shift_div_r. apply Qpos_ispos. |
| 1329 |
rewrite Qmult_comm. apply Qle_refl. |
| 1330 |
unfold Qdiv. rewrite Qmult_comm, Qmult_assoc. |
| 1331 |
apply Qle_shift_div_r. apply Qpos_ispos. |
| 1332 |
rewrite Qmult_comm. apply Qle_refl. |
| 1333 |
+ rewrite Qmult_comm. apply (Qle_trans _ (`c * |
| 1334 |
(Qabs |
| 1335 |
(Qmax (- ` c) |
| 1336 |
(Qmin (` c) (approximate y (Qmult_modulus c ((1 # 2) ↾ eq_refl * e1)))) - |
| 1337 |
Qmax (- ` c) |
| 1338 |
(Qmin (` c) |
| 1339 |
(approximate y (Qpos_min e2 ((1 # 2) ↾ eq_refl * e2 * Qpos_inv c)))))))). |
| 1340 |
apply Qmult_le_compat_r. 2: apply Qabs_nonneg. |
| 1341 |
apply qbound_bound. |
| 1342 |
rewrite Qmult_comm. |
| 1343 |
apply (Qle_trans _ (Qabs (approximate y (Qmult_modulus c ((1 # 2) ↾ eq_refl * e1)) - approximate y (Qpos_min e2 ((1 # 2) ↾ eq_refl * e2 * Qpos_inv c))) * `c)). |
| 1344 |
apply Qmult_le_compat_r. 2: apply Qpos_nonneg. |
| 1345 |
apply QboundAbs_contract. |
| 1346 |
apply (Qle_trans _ (((1#2)*`e1 / `c + (1#2)*`e2 / `c) * `c)). |
| 1347 |
apply Qmult_le_r. apply Qpos_ispos. |
| 1348 |
unfold Qmult_modulus. |
| 1349 |
pose proof (regFun_prf y ((1 # 2) * e1 * Qpos_inv c)%Qpos |
| 1350 |
(Qpos_min e2 ((1 # 2) * e2 * Qpos_inv c)%Qpos)) as H4. |
| 1351 |
apply AbsSmall_Qabs in H4. |
| 1352 |
apply (Qle_trans _ _ _ H4). clear H4. apply Qplus_le_r. |
| 1353 |
rewrite Q_Qpos_min. simpl. apply Qmin_lb_r. |
| 1354 |
rewrite Qmult_plus_distr_l. |
| 1355 |
apply Qplus_le_compat. |
| 1356 |
unfold Qdiv. rewrite Qmult_comm, Qmult_assoc. |
| 1357 |
apply Qle_shift_div_r. apply Qpos_ispos. |
| 1358 |
rewrite Qmult_comm. apply Qle_refl. |
| 1359 |
unfold Qdiv. rewrite Qmult_comm, Qmult_assoc. |
| 1360 |
apply Qle_shift_div_r. apply Qpos_ispos. |
| 1361 |
rewrite Qmult_comm. apply Qle_refl. |
| 1362 |
Qed. |
| 1363 |
|
| 1364 |
Lemma Qmult_uncurry_assoc : forall (i j k:Q) (b : Qpos), |
| 1365 |
Qabs i <= `b |
| 1366 |
-> Qabs j <= `b |
| 1367 |
-> Qabs k <= `b |
| 1368 |
-> Qabs (j*k) <= `b |
| 1369 |
-> Qabs (i*j) <= `b |
| 1370 |
-> Qmult_uncurry b (Qmult_uncurry b (i, j), k) |
| 1371 |
== Qmult_uncurry b (i, Qmult_uncurry b (j,k)). |
| 1372 |
Proof. |
| 1373 |
intros. simpl. |
| 1374 |
apply Qabs_Qle_condition in H. |
| 1375 |
destruct H as [ilower iupper]. |
| 1376 |
apply Qabs_Qle_condition in H0. |
| 1377 |
destruct H0 as [jlower jupper]. |
| 1378 |
apply Qabs_Qle_condition in H1. |
| 1379 |
destruct H1 as [klower kupper]. |
| 1380 |
apply Qabs_Qle_condition in H2. |
| 1381 |
destruct H2 as [jklower jkupper]. |
| 1382 |
apply Qabs_Qle_condition in H3. |
| 1383 |
destruct H3 as [ijlower ijupper]. |
| 1384 |
assert (forall a:Q, a <= `b -> Qmin (`b) a == a)%Q as elim_min. |
| 1385 |
{ apply Qle_min_r. } |
| 1386 |
assert (forall a:Q, -(`b) <= a -> Qmax (-(`b)) a == a)%Q as elim_max. |
| 1387 |
{ intros. apply Qle_max_r, H. } |
| 1388 |
rewrite (elim_min j jupper). |
| 1389 |
rewrite (elim_min i iupper). |
| 1390 |
rewrite (elim_min k kupper). |
| 1391 |
rewrite (elim_max j jlower). |
| 1392 |
rewrite (elim_max i ilower). |
| 1393 |
rewrite (elim_max k klower). |
| 1394 |
rewrite (elim_min (j*k) jkupper). |
| 1395 |
rewrite (elim_min (i*j) ijupper). |
| 1396 |
rewrite (elim_max (j*k) jklower). |
| 1397 |
rewrite (elim_max (i*j) ijlower). |
| 1398 |
rewrite Qmult_assoc. reflexivity. |
| 1399 |
Qed. |
| 1400 |
|
| 1401 |
Lemma quarter_approx_le_abs_1 : |
| 1402 |
forall (x : CR) (q : Q), |
| 1403 |
Qabs (q - approximate x (Qpos2QposInf (1 # 4))) <= (3#4) |
| 1404 |
-> Qabs q <= ` (CR_b (1 ↾ eq_refl) x + 1 ↾ eq_refl)%Qpos. |
| 1405 |
Proof. |
| 1406 |
intros. simpl. |
| 1407 |
apply (Qle_trans _ _ _ (Qabs_triangle_reverse _ _)) in H. |
| 1408 |
apply (Qplus_le_l _ _ (-Qabs (approximate x (Qpos2QposInf (1#4))))). |
| 1409 |
apply (Qle_trans _ _ _ H). clear H q. |
| 1410 |
pose proof (regFun_prf x (1#4)%Qpos (1#1)%Qpos). |
| 1411 |
apply AbsSmall_Qabs in H. |
| 1412 |
apply Qopp_le_compat in H. apply (Qplus_le_r _ _ (2#1)) in H. |
| 1413 |
setoid_replace (2 + - (` ((1 # 4) ↾ eq_refl) + ` (1 ↾ eq_refl))) |
| 1414 |
with (3#4) in H by reflexivity. |
| 1415 |
rewrite <- Qplus_assoc, <- Qplus_assoc, Qplus_comm, Qplus_assoc. |
| 1416 |
setoid_replace ((1#1)+(1#1)) with (2#1) by reflexivity. |
| 1417 |
apply (Qle_trans _ _ _ H). clear H. |
| 1418 |
rewrite <- Qplus_assoc. apply Qplus_le_r. |
| 1419 |
setoid_replace (- Qabs (approximate x (Qpos2QposInf (1 # 4))) |
| 1420 |
+ Qabs (approximate x (Qpos2QposInf (1#1))))%Q |
| 1421 |
with (- (Qabs (approximate x (Qpos2QposInf (1 # 4))) |
| 1422 |
- Qabs (approximate x (Qpos2QposInf (1#1))))) |
| 1423 |
by (unfold equiv, stdlib_rationals.Q_eq; ring). |
| 1424 |
apply Qopp_le_compat, Qabs_triangle_reverse. |
| 1425 |
Qed. |
| 1426 |
|
| 1427 |
Lemma QboundAbs_lowerBound_2 : forall (a b : Qpos) (c d : Q), |
| 1428 |
(- (`a * `b) <= QboundAbs a c * QboundAbs b d)%Q. |
| 1429 |
Proof. |
| 1430 |
intros. apply (Qle_trans _ (-Qabs (QboundAbs a c * QboundAbs b d))). |
| 1431 |
apply Qopp_le_compat. |
| 1432 |
rewrite Qabs_Qmult. rewrite QboundAbs_abs, QboundAbs_abs. |
| 1433 |
apply (Qle_trans _ (`a * Qmin (Qabs d) (`b))). |
| 1434 |
apply Qmult_le_compat_r. apply Qmin_lb_r. |
| 1435 |
apply Qmin_glb. apply Qabs_nonneg. apply Qpos_nonneg. |
| 1436 |
apply Qmult_le_l. apply Qpos_ispos. apply Qmin_lb_r. |
| 1437 |
rewrite <- (Qopp_involutive (QboundAbs a c * QboundAbs b d)) at 2. |
| 1438 |
apply Qopp_le_compat. rewrite <- Qabs_opp. |
| 1439 |
apply Qle_Qabs. |
| 1440 |
Qed. |
| 1441 |
|
| 1442 |
Lemma QboundAbs_upperBound_2 : forall (a b : Qpos) (c d : Q), |
| 1443 |
(QboundAbs a c * QboundAbs b d <= `a * `b)%Q. |
| 1444 |
Proof. |
| 1445 |
intros. apply (Qle_trans _ _ _ (Qle_Qabs _)). |
| 1446 |
rewrite Qabs_Qmult. rewrite QboundAbs_abs, QboundAbs_abs. |
| 1447 |
apply (Qle_trans _ (`a * Qmin (Qabs d) (`b))). |
| 1448 |
apply Qmult_le_compat_r. apply Qmin_lb_r. |
| 1449 |
apply Qmin_glb. apply Qabs_nonneg. apply Qpos_nonneg. |
| 1450 |
apply Qmult_le_l. apply Qpos_ispos. apply Qmin_lb_r. |
| 1451 |
Qed. |
| 1452 |
|
| 1453 |
Lemma CR_b_lowerBound_2 : forall x y : CR, |
| 1454 |
('(-proj1_sig ((CR_b (1#1) x) * CR_b (1#1) y)%Qpos)%Q <= x * y)%CR. |
| 1455 |
Proof. |
| 1456 |
intros. |
| 1457 |
rewrite <- (CRboundAbs_Eq (CR_b (1#1) x) |
| 1458 |
(CR_b_lowerBound (1#1) x) (CR_b_upperBound (1#1) x)) at 2. |
| 1459 |
unfold CRmult, ucFun2. |
| 1460 |
intros e. simpl. unfold Cap_raw; simpl. |
| 1461 |
unfold Cap_raw; simpl. |
| 1462 |
apply (Qle_trans _ 0). apply (Qopp_le_compat 0), Qpos_nonneg. |
| 1463 |
unfold Qminus. rewrite <- Qle_minus_iff. |
| 1464 |
apply (QboundAbs_lowerBound_2 (CR_b (1#1) x) (CR_b (1#1) y)). |
| 1465 |
Qed. |
| 1466 |
|
| 1467 |
Lemma CR_b_upperBound_2 : forall x y : CR, |
| 1468 |
(x * y <= 'proj1_sig ((CR_b (1#1) x) * CR_b (1#1) y)%Qpos)%CR. |
| 1469 |
Proof. |
| 1470 |
intros. |
| 1471 |
rewrite <- (CRboundAbs_Eq (CR_b (1#1) x) |
| 1472 |
(CR_b_lowerBound (1#1) x) (CR_b_upperBound (1#1) x)) at 1. |
| 1473 |
unfold CRmult, ucFun2. |
| 1474 |
intros e. simpl. unfold Cap_raw; simpl. |
| 1475 |
unfold Cap_raw; simpl. |
| 1476 |
apply (Qle_trans _ 0). apply (Qopp_le_compat 0), Qpos_nonneg. |
| 1477 |
unfold Qminus. rewrite <- Qle_minus_iff. |
| 1478 |
apply (QboundAbs_upperBound_2 (CR_b (1#1) x) (CR_b (1#1) y)). |
| 1479 |
Qed. |
| 1480 |
|
| 1481 |
Lemma CRle_Qle : forall (x y:Q), (inject_Q_CR x <= inject_Q_CR y)%CR <-> (x <= y)%Q. |
| 1482 |
Proof. |
| 1483 |
split. |
| 1484 |
intros H. |
| 1485 |
destruct (Qlt_le_dec y x) as [X|X];[|assumption]. |
| 1486 |
destruct (Qpos_sub _ _ X) as [c Hc]. |
| 1487 |
assert (Y:=(H ((1#2)*c)%Qpos)). |
| 1488 |
simpl in Y. |
| 1489 |
unfold Cap_raw in Y; simpl in Y. |
| 1490 |
rewrite -> Qle_minus_iff in Y. |
| 1491 |
rewrite -> Hc in Y. |
| 1492 |
autorewrite with QposElim in Y. |
| 1493 |
ring_simplify in Y. |
| 1494 |
elim (Qle_not_lt _ _ Y). |
| 1495 |
rewrite -> Qlt_minus_iff. |
| 1496 |
ring_simplify. |
| 1497 |
apply Q.Qmult_lt_0_compat; auto with *. |
| 1498 |
intros H e. |
| 1499 |
simpl. |
| 1500 |
unfold Cap_raw; simpl. |
| 1501 |
rewrite -> Qle_minus_iff in H. |
| 1502 |
apply Qle_trans with (0%Q);[|assumption]. |
| 1503 |
rewrite -> Qle_minus_iff; ring_simplify. |
| 1504 |
apply Qpos_nonneg. |
| 1505 |
Qed. |
| 1506 |
|
| 1507 |
Lemma CRmult_assoc_yfactor_le |
| 1508 |
: forall (x y z : CR), |
| 1509 |
let b := ((CR_b (1#1) x + (1#1)) |
| 1510 |
* (CR_b (1#1) y + (1#1)) * (CR_b (1#1) z + (1#1)))%Qpos in |
| 1511 |
(` (CR_b (1 ↾ eq_refl) y) + 1 <= ` b)%Q. |
| 1512 |
Proof. |
| 1513 |
intros. unfold b. simpl. |
| 1514 |
rewrite <- Qmult_assoc, (Qmult_comm (Qabs (approximate y (Qpos2QposInf (1#1))) + 1 + 1)). |
| 1515 |
rewrite Qmult_assoc. |
| 1516 |
rewrite <- Qmult_1_l, <- Qmult_1_l. |
| 1517 |
rewrite Qmult_assoc. |
| 1518 |
apply Qmult_le_compat_r. |
| 1519 |
apply (Qpos_mult_le_compat (1#1) (1#1)). |
| 1520 |
rewrite <- Qplus_0_l. apply Qplus_le_l, (Qpos_nonneg (CR_b (1#1) x)). |
| 1521 |
rewrite <- Qplus_0_l. apply Qplus_le_l, (Qpos_nonneg (CR_b (1#1) z)). |
| 1522 |
rewrite <- Qplus_assoc. apply (Qle_trans _ (0+2)). |
| 1523 |
discriminate. apply Qplus_le_l. apply Qabs_nonneg. |
| 1524 |
Qed. |
| 1525 |
|
| 1526 |
Lemma CRmult_assoc_xfactor_le |
| 1527 |
: forall (x y z : CR), |
| 1528 |
let b := ((CR_b (1#1) x + (1#1)) |
| 1529 |
* (CR_b (1#1) y + (1#1)) * (CR_b (1#1) z + (1#1)))%Qpos in |
| 1530 |
(` (CR_b (1 ↾ eq_refl) x) + 1 <= ` b)%Q. |
| 1531 |
Proof. |
| 1532 |
intros. unfold b. simpl. |
| 1533 |
rewrite <- Qmult_assoc, Qmult_comm. |
| 1534 |
rewrite <- Qmult_1_l, <- Qmult_1_l at 1. |
| 1535 |
rewrite Qmult_assoc. |
| 1536 |
apply Qmult_le_compat_r. |
| 1537 |
apply (Qpos_mult_le_compat (1#1) (1#1)). |
| 1538 |
rewrite <- Qplus_0_l. apply Qplus_le_l, (Qpos_nonneg (CR_b (1#1) y)). |
| 1539 |
rewrite <- Qplus_0_l. apply Qplus_le_l, (Qpos_nonneg (CR_b (1#1) z)). |
| 1540 |
rewrite <- Qplus_assoc. apply (Qle_trans _ (0+2)). |
| 1541 |
discriminate. apply Qplus_le_l. apply Qabs_nonneg. |
| 1542 |
Qed. |
| 1543 |
|
| 1544 |
Lemma CRmult_assoc_zfactor_le |
| 1545 |
: forall (x y z : CR), |
| 1546 |
let b := ((CR_b (1#1) x + (1#1)) |
| 1547 |
* (CR_b (1#1) y + (1#1)) * (CR_b (1#1) z + (1#1)))%Qpos in |
| 1548 |
(` (CR_b (1 ↾ eq_refl) z) + 1 <= ` b)%Q. |
| 1549 |
Proof. |
| 1550 |
intros. rewrite <- Qmult_1_l, <- Qmult_1_l, Qmult_assoc. |
| 1551 |
apply Qmult_le_compat_r. 2: apply Qpos_nonneg. |
| 1552 |
apply (Qpos_mult_le_compat (1#1) (1#1)). |
| 1553 |
rewrite <- Qplus_0_l. apply Qplus_le_l, Qpos_nonneg. |
| 1554 |
rewrite <- Qplus_0_l. apply Qplus_le_l, Qpos_nonneg. |
| 1555 |
Qed. |
| 1556 |
|
| 1557 |
(* Request bounds on all left factors : x, CRmult_bounded b x y, and y. *) |
| 1558 |
Lemma CRmult_assoc_bounded (x y z : CR) : |
| 1559 |
let b := ((CR_b (1#1) x + (1#1)) |
| 1560 |
* (CR_b (1#1) y + (1#1)) * (CR_b (1#1) z + (1#1)))%Qpos in |
| 1561 |
(CRmult_bounded b (CRmult_bounded b x y) z |
| 1562 |
== CRmult_bounded b x (CRmult_bounded b y z))%CR. |
| 1563 |
Proof. |
| 1564 |
intros. |
| 1565 |
assert (' (- ` b)%Q <= x)%CR as xlower. |
| 1566 |
{ apply (@CRle_trans _ (' (-proj1_sig (CR_b (1#1) x))%Q)). |
| 1567 |
2: apply (CR_b_lowerBound _ _). |
| 1568 |
apply CRle_Qle. apply Qopp_le_compat. |
| 1569 |
apply (Qle_trans _ ((` (CR_b (1#1)%Qpos x) + (1#1)))). |
| 1570 |
rewrite <- Qplus_0_r at 1. apply Qplus_le_r. discriminate. |
| 1571 |
apply CRmult_assoc_xfactor_le. } |
| 1572 |
assert (x <= ' (` b)%Q)%CR as xupper. |
| 1573 |
{ apply (@CRle_trans _ (' (proj1_sig (CR_b (1#1) x))%Q)). |
| 1574 |
apply CR_b_upperBound. |
| 1575 |
apply CRle_Qle. |
| 1576 |
apply (Qle_trans _ ((` (CR_b (1#1)%Qpos x) + (1#1)))). |
| 1577 |
rewrite <- Qplus_0_r at 1. apply Qplus_le_r. discriminate. |
| 1578 |
apply CRmult_assoc_xfactor_le. } |
| 1579 |
assert (' (- ` b)%Q <= y)%CR as ylower. |
| 1580 |
{ apply (@CRle_trans _ (' (-proj1_sig (CR_b (1#1) y))%Q)). |
| 1581 |
2: apply (CR_b_lowerBound _ _). |
| 1582 |
apply CRle_Qle. apply Qopp_le_compat. |
| 1583 |
apply (Qle_trans _ ((` (CR_b (1#1)%Qpos y) + (1#1)))). |
| 1584 |
rewrite <- Qplus_0_r at 1. apply Qplus_le_r. discriminate. |
| 1585 |
apply CRmult_assoc_yfactor_le. } |
| 1586 |
assert (y <= ' (` b)%Q)%CR as yupper. |
| 1587 |
{ apply (@CRle_trans _ (' (proj1_sig (CR_b (1#1) y))%Q)). |
| 1588 |
apply CR_b_upperBound. |
| 1589 |
apply CRle_Qle. |
| 1590 |
apply (Qle_trans _ ((` (CR_b (1#1)%Qpos y) + (1#1)))). |
| 1591 |
rewrite <- Qplus_0_r at 1. apply Qplus_le_r. discriminate. |
| 1592 |
apply CRmult_assoc_yfactor_le. } |
| 1593 |
assert (` (CR_b (1 ↾ eq_refl) x + 1 ↾ eq_refl)%Qpos * |
| 1594 |
` (CR_b (1 ↾ eq_refl) y + 1 ↾ eq_refl)%Qpos <= ` b) as xyfactor_le. |
| 1595 |
{ rewrite <- Qmult_1_l. |
| 1596 |
unfold b. simpl. |
| 1597 |
rewrite (Qmult_comm ((Qabs (approximate x (Qpos2QposInf (1 ↾ eq_refl))) + 1 + 1) * |
| 1598 |
(Qabs (approximate y (Qpos2QposInf (1 ↾ eq_refl))) + 1 + 1))). |
| 1599 |
apply Qmult_le_compat_r. |
| 1600 |
apply (Qle_trans _ (0+2)). discriminate. |
| 1601 |
rewrite <- Qplus_assoc. |
| 1602 |
apply Qplus_le_l, Qabs_nonneg. |
| 1603 |
apply Qmult_le_0_compat. |
| 1604 |
apply (Qle_trans _ (0+2)). discriminate. |
| 1605 |
rewrite <- Qplus_assoc. |
| 1606 |
apply Qplus_le_l, Qabs_nonneg. |
| 1607 |
apply (Qle_trans _ (0+2)). discriminate. |
| 1608 |
rewrite <- Qplus_assoc. |
| 1609 |
apply Qplus_le_l, Qabs_nonneg. } |
| 1610 |
rewrite CRmult_uncurry_eq_3r. |
| 1611 |
rewrite CRmult_uncurry_eq_3. |
| 1612 |
2: exact xlower. 2: exact xupper. |
| 1613 |
4: exact xlower. 4: exact xupper. |
| 1614 |
4: exact ylower. 4: exact yupper. |
| 1615 |
(* Qmult_uncurry is not associative everywhere, |
| 1616 |
so use Cmap_wd_loc. *) |
| 1617 |
apply Cmap_wd_loc with (e:=(1#4)%Qpos). intros [[i j] k]. |
| 1618 |
intros H. |
| 1619 |
specialize (H (1#4)%Qpos (1#4)%Qpos). |
| 1620 |
destruct H,H. |
| 1621 |
simpl in H1. simpl in H0. |
| 1622 |
apply Qball_0. |
| 1623 |
apply (@Qmult_uncurry_assoc i j k b). |
| 1624 |
- clear H0 H1. simpl in H. apply AbsSmall_Qabs in H. |
| 1625 |
apply (Qle_trans _ (proj1_sig (CR_b (1#1) x + (1#1))%Qpos)). |
| 1626 |
setoid_replace ((1#4)+(1#4)+(1#4)) with (3#4) in H by reflexivity. |
| 1627 |
apply quarter_approx_le_abs_1, H. clear H. |
| 1628 |
apply CRmult_assoc_xfactor_le. |
| 1629 |
- clear H H0. |
| 1630 |
apply (Qle_trans _ (proj1_sig (CR_b (1#1) y + (1#1))%Qpos)). |
| 1631 |
apply AbsSmall_Qabs in H1. |
| 1632 |
setoid_replace ((1#4)+(1#4)+(1#4)) with (3#4) in H1 by reflexivity. |
| 1633 |
apply quarter_approx_le_abs_1, H1. apply CRmult_assoc_yfactor_le. |
| 1634 |
- clear H H1. |
| 1635 |
apply (Qle_trans _ (proj1_sig (CR_b (1#1) z + (1#1))%Qpos)). |
| 1636 |
apply AbsSmall_Qabs in H0. |
| 1637 |
setoid_replace ((1#4)+(1#4)+(1#4)) with (3#4) in H0 by reflexivity. |
| 1638 |
apply quarter_approx_le_abs_1, H0. |
| 1639 |
apply CRmult_assoc_zfactor_le. |
| 1640 |
- apply (Qle_trans _ (proj1_sig (CR_b (1#1) y + (1#1))%Qpos |
| 1641 |
* proj1_sig (CR_b (1#1) z + (1#1))%Qpos)). |
| 1642 |
rewrite Qabs_Qmult. |
| 1643 |
apply (Qle_trans _ (proj1_sig (CR_b (1#1) y + (1#1))%Qpos * Qabs k)). |
| 1644 |
apply Qmult_le_compat_r. |
| 1645 |
apply AbsSmall_Qabs in H1. |
| 1646 |
setoid_replace ((1#4)+(1#4)+(1#4)) with (3#4) in H1 by reflexivity. |
| 1647 |
apply quarter_approx_le_abs_1, H1. apply Qabs_nonneg. |
| 1648 |
apply Qmult_le_l. apply Qpos_ispos. |
| 1649 |
apply AbsSmall_Qabs in H0. |
| 1650 |
setoid_replace ((1#4)+(1#4)+(1#4)) with (3#4) in H0 by reflexivity. |
| 1651 |
apply quarter_approx_le_abs_1, H0. |
| 1652 |
rewrite <- Qmult_1_l, Qmult_assoc. |
| 1653 |
apply Qmult_le_compat_r. 2: apply Qpos_nonneg. |
| 1654 |
apply Qmult_le_compat_r. 2: apply Qpos_nonneg. |
| 1655 |
simpl. rewrite <- Qplus_assoc. |
| 1656 |
apply (Qle_trans _ (0+2)). discriminate. |
| 1657 |
apply Qplus_le_l, Qabs_nonneg. |
| 1658 |
- apply (Qle_trans _ (proj1_sig (CR_b (1#1) x + (1#1))%Qpos |
| 1659 |
* proj1_sig (CR_b (1#1) y + (1#1))%Qpos)). |
| 1660 |
rewrite Qabs_Qmult. |
| 1661 |
apply (Qle_trans _ (proj1_sig (CR_b (1#1) x + (1#1))%Qpos * Qabs j)). |
| 1662 |
apply Qmult_le_compat_r. |
| 1663 |
simpl in H. |
| 1664 |
apply AbsSmall_Qabs in H. |
| 1665 |
setoid_replace ((1#4)+(1#4)+(1#4)) with (3#4) in H by reflexivity. |
| 1666 |
apply quarter_approx_le_abs_1, H. apply Qabs_nonneg. |
| 1667 |
apply Qmult_le_l. apply Qpos_ispos. |
| 1668 |
apply AbsSmall_Qabs in H1. |
| 1669 |
setoid_replace ((1#4)+(1#4)+(1#4)) with (3#4) in H1 by reflexivity. |
| 1670 |
apply quarter_approx_le_abs_1, H1. |
| 1671 |
exact xyfactor_le. |
| 1672 |
- rewrite (@CRmult_bounded_mult b). |
| 1673 |
2: exact ylower. 2: exact yupper. |
| 1674 |
apply (@CRle_trans _ ('(-proj1_sig ((CR_b (1#1) x) * CR_b (1#1) y)%Qpos)%Q)). |
| 1675 |
2: apply CR_b_lowerBound_2. |
| 1676 |
apply CRle_Qle, Qopp_le_compat. |
| 1677 |
apply (Qle_trans _ (proj1_sig (CR_b (1#1) x + (1#1))%Qpos |
| 1678 |
* proj1_sig ((CR_b (1#1) y) + (1#1))%Qpos)). |
| 1679 |
apply (Qpos_mult_le_compat (CR_b (1#1) x) (CR_b (1#1) y)). |
| 1680 |
rewrite <- Qplus_0_r at 1. apply Qplus_le_r. discriminate. |
| 1681 |
rewrite <- Qplus_0_r at 1. apply Qplus_le_r. discriminate. |
| 1682 |
exact xyfactor_le. |
| 1683 |
- rewrite (@CRmult_bounded_mult b). |
| 1684 |
2: exact ylower. 2: exact yupper. |
| 1685 |
apply (@CRle_trans _ ('(proj1_sig ((CR_b (1#1) x) * CR_b (1#1) y)%Qpos)%Q)). |
| 1686 |
apply CR_b_upperBound_2. |
| 1687 |
apply CRle_Qle. |
| 1688 |
apply (Qle_trans _ (proj1_sig (CR_b (1#1) x + (1#1))%Qpos |
| 1689 |
* proj1_sig ((CR_b (1#1) y) + (1#1))%Qpos)). |
| 1690 |
apply (Qpos_mult_le_compat (CR_b (1#1) x) (CR_b (1#1) y)). |
| 1691 |
rewrite <- Qplus_0_r at 1. apply Qplus_le_r. discriminate. |
| 1692 |
rewrite <- Qplus_0_r at 1. apply Qplus_le_r. discriminate. |
| 1693 |
exact xyfactor_le. |
| 1694 |
Qed. |
| 1695 |
|