| 1 |
Require Import CoRN.algebra.RSetoid. |
| 2 |
Require Import CoRN.metric2.Metric. |
| 3 |
Require Import CoRN.metric2.UniformContinuity. |
| 4 |
From Coq Require Import Qabs. |
| 5 |
Require Import CoRN.model.metric2.Qmetric |
| 6 |
CoRN.model.totalorder.QposMinMax |
| 7 |
CoRN.model.totalorder.QMinMax |
| 8 |
CoRN.reals.fast.CRabs |
| 9 |
CoRN.reals.faster.ARArith. |
| 10 |
|
| 11 |
(** Absolute Value *) |
| 12 |
|
| 13 |
Section ARabs. |
| 14 |
Context `{AppRationals AQ}. |
| 15 |
|
| 16 |
Definition AQabs : AQ -> AQ |
| 17 |
:= fun q => proj1_sig (abs_sig q). |
| 18 |
|
| 19 |
Lemma aq_abs : forall q:AQ, '(proj1_sig (abs_sig q)) == Qabs ('q). |
| 20 |
Proof. |
| 21 |
intro q. destruct (abs_sig q). unfold proj1_sig. |
| 22 |
destruct a. |
| 23 |
destruct aq_ring_morphism. |
| 24 |
destruct aq_order_embed. |
| 25 |
destruct semiringmor_plus_mor. |
| 26 |
destruct monmor_sgmor. |
| 27 |
destruct sgmor_setmor. |
| 28 |
assert (AQtoQ 0 == 0) by (apply rings.preserves_0). |
| 29 |
destruct (Qlt_le_dec ('q) 0). |
| 30 |
- rewrite Qabs_neg. rewrite <- aq_opp. |
| 31 |
apply sm_proper, H6. |
| 32 |
apply order_embedding_reflecting. |
| 33 |
rewrite H7. |
| 34 |
apply Qlt_le_weak, q0. |
| 35 |
apply Qlt_le_weak, q0. |
| 36 |
- rewrite Qabs_pos. 2: exact q0. |
| 37 |
apply sm_proper, H5. |
| 38 |
apply order_embedding_reflecting. |
| 39 |
rewrite H7. exact q0. |
| 40 |
Qed. |
| 41 |
|
| 42 |
Lemma AQabs_triangle_reverse |
| 43 |
: forall a b : AQ, Qabs (' AQabs a - ' AQabs b) <= Qabs ('a - 'b). |
| 44 |
Proof. |
| 45 |
intros a b. unfold AQabs. |
| 46 |
rewrite aq_abs, aq_abs. |
| 47 |
apply Qabs_case. |
| 48 |
- intros _. apply Qabs_triangle_reverse. |
| 49 |
- intros. |
| 50 |
apply (Qle_trans _ (Qabs ('b) - Qabs ('a))). |
| 51 |
ring_simplify; apply Qle_refl. |
| 52 |
rewrite <- (Qabs_opp (' a - ' b)). |
| 53 |
setoid_replace (- (' a - ' b))%Q with (' b - ' a)%Q. |
| 54 |
apply Qabs_triangle_reverse. |
| 55 |
unfold equiv, stdlib_rationals.Q_eq. |
| 56 |
ring. |
| 57 |
Qed. |
| 58 |
|
| 59 |
Lemma AQabs_uc_prf |
| 60 |
: is_UniformlyContinuousFunction |
| 61 |
(AQabs : AQ_as_MetricSpace -> AQ_as_MetricSpace) Qpos2QposInf. |
| 62 |
Proof. |
| 63 |
intros d a b Hab. |
| 64 |
simpl in Hab. |
| 65 |
unfold Qball in Hab. |
| 66 |
rewrite <- AbsSmall_Qabs in Hab. |
| 67 |
simpl. unfold Qball. |
| 68 |
rewrite <- AbsSmall_Qabs. |
| 69 |
exact (Qle_trans _ _ _ (AQabs_triangle_reverse _ _) Hab). |
| 70 |
Qed. |
| 71 |
|
| 72 |
Local Open Scope uc_scope. |
| 73 |
|
| 74 |
Definition AQabs_uc : AQ_as_MetricSpace --> AQ_as_MetricSpace |
| 75 |
:= Build_UniformlyContinuousFunction AQabs_uc_prf. |
| 76 |
|
| 77 |
Definition ARabs : AR --> AR := Cmap AQPrelengthSpace AQabs_uc. |
| 78 |
|
| 79 |
(* The approximations of the absolute value are what we expect. *) |
| 80 |
Lemma ARabs_approx : forall (e:Qpos) (x:AR), |
| 81 |
approximate (ARabs x) e = AQabs (approximate x e). |
| 82 |
Proof. |
| 83 |
reflexivity. |
| 84 |
Qed. |
| 85 |
|
| 86 |
Lemma ARtoCR_preserves_abs |
| 87 |
: forall x : AR, cast AR CR (ARabs x) = CRabs (cast AR CR x). |
| 88 |
Proof. |
| 89 |
intro x. |
| 90 |
unfold cast, ARtoCR, ARtoCR_uc. |
| 91 |
unfold MetricMorphisms.Eembed. |
| 92 |
unfold ARabs, CRabs. |
| 93 |
rewrite <- (fast_MonadLaw2 |
| 94 |
AQPrelengthSpace |
| 95 |
(MetricMorphisms.EPrelengthSpace QPrelengthSpace (cast AQ Q_as_MetricSpace)) |
| 96 |
(MetricMorphisms.metric_embed_uc (cast AQ Q_as_MetricSpace)) |
| 97 |
AQabs_uc). |
| 98 |
rewrite <- (fast_MonadLaw2 |
| 99 |
(MetricMorphisms.EPrelengthSpace QPrelengthSpace (cast AQ Q_as_MetricSpace)) |
| 100 |
QPrelengthSpace Qabs_uc |
| 101 |
(MetricMorphisms.metric_embed_uc (cast AQ Q_as_MetricSpace)) x). |
| 102 |
apply Cmap_wd. 2: reflexivity. |
| 103 |
apply ucEq_equiv. |
| 104 |
intro d. simpl. apply Qball_0, aq_abs. |
| 105 |
Qed. |
| 106 |
|
| 107 |
Lemma ARabs_AbsSmall : forall a b : AR, ARle (ARabs b) a <-> (ARle (-a) b /\ ARle b a). |
| 108 |
Proof. |
| 109 |
intros a b. pose proof CRabs_AbsSmall. split. |
| 110 |
- intro H6. |
| 111 |
assert ((CRabs (cast AR CR b) <= (cast AR CR a))%CR). |
| 112 |
{ apply ARtoCR_preserves_le in H6. |
| 113 |
rewrite ARtoCR_preserves_abs in H6. exact H6. } |
| 114 |
specialize (H5 ('a) ('b)) as [H5 _]. |
| 115 |
specialize (H5 H7). |
| 116 |
split; apply ARtoCR_preserves_le. |
| 117 |
rewrite ARtoCR_preserves_opp. |
| 118 |
apply H5. apply H5. |
| 119 |
- intros [H6 H7]. |
| 120 |
apply (ARtoCR_preserves_le (-a) b) in H6. |
| 121 |
apply (ARtoCR_preserves_le b a) in H7. |
| 122 |
specialize (H5 ('a) ('b)) as [_ H5]. |
| 123 |
apply ARtoCR_preserves_le. |
| 124 |
rewrite ARtoCR_preserves_abs. apply H5. |
| 125 |
split. rewrite <- ARtoCR_preserves_opp. |
| 126 |
exact H6. exact H7. |
| 127 |
Qed. |
| 128 |
|
| 129 |
Lemma ARle_abs : forall x:AR, ARle x (ARabs x). |
| 130 |
Proof. |
| 131 |
intro x. apply ARtoCR_preserves_le. |
| 132 |
rewrite ARtoCR_preserves_abs. |
| 133 |
apply CRle_abs. |
| 134 |
Qed. |
| 135 |
|
| 136 |
Lemma ARabs_opp : forall x:AR, ARabs (-x) = ARabs x. |
| 137 |
Proof. |
| 138 |
intro x. |
| 139 |
apply (injective ARtoCR). |
| 140 |
pose proof (ARtoCR_preserves_abs (-x)). |
| 141 |
unfold cast in H5. rewrite H5. clear H5. |
| 142 |
pose proof (ARtoCR_preserves_abs x). |
| 143 |
unfold cast in H5. rewrite H5. |
| 144 |
rewrite (ARtoCR_preserves_opp x). |
| 145 |
apply CRabs_opp. |
| 146 |
Qed. |
| 147 |
|
| 148 |
Lemma ARabs_pos : forall x:AR, ARle 0 x -> ARabs x = x. |
| 149 |
Proof. |
| 150 |
intros x xpos. |
| 151 |
apply (injective ARtoCR). |
| 152 |
pose proof (ARtoCR_preserves_abs x). |
| 153 |
unfold cast in H5. rewrite H5. clear H5. |
| 154 |
apply CRabs_pos. |
| 155 |
rewrite <- ARtoCR_preserves_0. |
| 156 |
apply (ARtoCR_preserves_le AR0 x), xpos. |
| 157 |
Qed. |
| 158 |
|
| 159 |
Lemma ARabs_neg : forall x:AR, ARle x 0 -> ARabs x = -x. |
| 160 |
Proof. |
| 161 |
intros x xneg. |
| 162 |
apply (injective ARtoCR). |
| 163 |
pose proof (ARtoCR_preserves_abs x). |
| 164 |
unfold cast in H5. rewrite H5. clear H5. |
| 165 |
rewrite CRabs_neg. |
| 166 |
symmetry. apply ARtoCR_preserves_opp. |
| 167 |
rewrite <- ARtoCR_preserves_0. |
| 168 |
apply (ARtoCR_preserves_le x AR0), xneg. |
| 169 |
Qed. |
| 170 |
|
| 171 |
End ARabs. |