| 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.metric2.ProductMetric |
| 7 |
CoRN.model.totalorder.QposMinMax |
| 8 |
CoRN.model.totalorder.QMinMax |
| 9 |
CoRN.reals.faster.ARabs |
| 10 |
CoRN.reals.faster.ARroot |
| 11 |
CoRN.reals.faster.ARArith. |
| 12 |
|
| 13 |
(** Basic definitions for the complex numbers. *) |
| 14 |
|
| 15 |
Section ACcomplex. |
| 16 |
Context `{AppRationals AQ}. |
| 17 |
|
| 18 |
(* The instance of Setoid AR*AR is already in scope, |
| 19 |
with u = v iff (fst u = fst v /\ snd u = snd v). *) |
| 20 |
|
| 21 |
Definition ACball (u v : AR*AR) (e : Q) : Prop |
| 22 |
:= 0 <= e |
| 23 |
/\ ARle ((fst u - fst v)*(fst u - fst v) + (snd u - snd v)*(snd u - snd v)) |
| 24 |
(inject_Q_AR (e*e)). |
| 25 |
|
| 26 |
(* TODO the distance of ACball would be better. *) |
| 27 |
Definition AC : MetricSpace := ProductMS AR AR. |
| 28 |
|
| 29 |
Instance: Plus AC |
| 30 |
:= fun xy uv => pair (fst xy + fst uv) (snd xy + snd uv). |
| 31 |
|
| 32 |
Instance: Mult AC |
| 33 |
:= fun xy uv => pair (fst xy*fst uv - snd xy*snd uv) |
| 34 |
(fst xy*snd uv + snd xy*fst uv). |
| 35 |
|
| 36 |
(* The square root of -1, imaginary number i. *) |
| 37 |
Definition ACi : AC := pair 0 1. |
| 38 |
|
| 39 |
Definition ACmodulus : AC -> AR |
| 40 |
:= fun z => ARsqrt (fst z*fst z + snd z*snd z). |
| 41 |
|
| 42 |
Lemma ACplus_comm : forall u v : AC, u + v = v + u. |
| 43 |
Proof. |
| 44 |
intros u v. split; apply ARplus_comm. |
| 45 |
Qed. |
| 46 |
|
| 47 |
Lemma ACplus_assoc : forall u v w : AC, |
| 48 |
(u + v) + w = u + (v + w). |
| 49 |
Proof. |
| 50 |
intros u v w. split; apply ARplus_assoc. |
| 51 |
Qed. |
| 52 |
|
| 53 |
Definition ACsqrt (z : AC) (yDec : {ARle 0 (snd z)} + {ARle (snd z) 0}) : AC |
| 54 |
:= pair (ARsqrt ((ACmodulus z + fst z) * inject_Q_AR (1#2))) |
| 55 |
((if yDec then 1 else -1) |
| 56 |
* (ARsqrt ((ACmodulus z - fst z) * inject_Q_AR (1#2)))). |
| 57 |
|
| 58 |
Add Ring AR : (rings.stdlib_ring_theory AR). |
| 59 |
|
| 60 |
Lemma ARdouble : forall x : AR, x + x = 2*x. |
| 61 |
Proof. |
| 62 |
intro x. ring. |
| 63 |
Qed. |
| 64 |
|
| 65 |
Lemma ARmult_neg_one : forall x : AR, -1 * x = -x. |
| 66 |
Proof. |
| 67 |
intros. ring. |
| 68 |
Qed. |
| 69 |
|
| 70 |
Lemma ACsqrt_correct : forall (z : AC) (yDec : {ARle 0 (snd z)} + {ARle (snd z) 0}), |
| 71 |
ACsqrt z yDec * ACsqrt z yDec = z. |
| 72 |
Proof. |
| 73 |
intros [x y] yDec. |
| 74 |
assert (2 * inject_Q_AR (1 # 2) = 1) as twoHalf. |
| 75 |
{ unfold one. |
| 76 |
pose proof inject_Q_AR_1. |
| 77 |
unfold one in H5. |
| 78 |
rewrite <- H5. |
| 79 |
rewrite <- inject_Q_AR_plus, <- inject_Q_AR_mult. |
| 80 |
apply inject_Q_AR_wd. reflexivity. } |
| 81 |
assert (ARle 0 (ACmodulus (x, y) - x)) as modMinus. |
| 82 |
{ unfold ACmodulus, fst, snd. |
| 83 |
rewrite <- (ARplus_opp_r x). |
| 84 |
apply ARplus_le_compat_r. |
| 85 |
apply (ARle_trans _ (ARsqrt (x*x))). |
| 86 |
rewrite (ARsqrt_srq_abs x). |
| 87 |
apply ARle_abs. |
| 88 |
apply ARsqrt_inc. |
| 89 |
apply ARsquare_pos. |
| 90 |
rewrite <- (ARplus_0_r (x*x)) at 1. |
| 91 |
apply ARplus_le_compat_l. |
| 92 |
apply ARsquare_pos. } |
| 93 |
assert (ARle 0 (ACmodulus (x, y) + x)) as modPlus. |
| 94 |
{ unfold ACmodulus, fst, snd. |
| 95 |
rewrite <- (ARplus_opp_r x). |
| 96 |
rewrite ARplus_comm. |
| 97 |
apply ARplus_le_compat_r. |
| 98 |
apply (ARle_trans _ (ARsqrt (x*x))). |
| 99 |
rewrite (ARsqrt_srq_abs x). |
| 100 |
rewrite <- ARabs_opp. |
| 101 |
apply ARle_abs. |
| 102 |
apply ARsqrt_inc. |
| 103 |
apply ARsquare_pos. |
| 104 |
rewrite <- (ARplus_0_r (x*x)) at 1. |
| 105 |
apply ARplus_le_compat_l. |
| 106 |
apply ARsquare_pos. } |
| 107 |
assert (ARle 0 (inject_Q_AR (1 # 2))) as halfPos. |
| 108 |
{ rewrite <- inject_Q_AR_0. |
| 109 |
apply inject_Q_AR_le. |
| 110 |
discriminate. } |
| 111 |
split. |
| 112 |
- unfold mult, Mult_instance_0, ACsqrt, fst, snd. |
| 113 |
rewrite (ARsqrt_correct ((ACmodulus (x, y) + x) * inject_Q_AR (1 # 2))). |
| 114 |
rewrite (ARmult_comm (if yDec then 1 else -1) |
| 115 |
(ARsqrt ((ACmodulus (x, y) - x) * inject_Q_AR (1 # 2)))). |
| 116 |
rewrite ARmult_assoc. |
| 117 |
rewrite <- (ARmult_comm (if yDec then 1 else -1)). |
| 118 |
rewrite <- (ARmult_assoc (if yDec then 1 else -1)). |
| 119 |
setoid_replace (ARmult (if yDec then 1 else -1) (if yDec then 1 else -1)) |
| 120 |
with AR1. |
| 121 |
rewrite ARmult_1_l. |
| 122 |
rewrite (ARsqrt_correct ((ACmodulus (x, y) - x) * inject_Q_AR (1 # 2))). |
| 123 |
+ setoid_replace ((ACmodulus (x, y) + x) * inject_Q_AR (1 # 2) - |
| 124 |
(ACmodulus (x, y) - x) * inject_Q_AR (1 # 2)) |
| 125 |
with (x*(2*inject_Q_AR (1#2))) by ring. |
| 126 |
rewrite twoHalf. |
| 127 |
apply ARmult_1_r. |
| 128 |
+ apply AR_mult_0_le_compat. exact modMinus. |
| 129 |
exact halfPos. |
| 130 |
+ destruct yDec. exact (ARmult_1_l AR1). |
| 131 |
pose proof (ARmult_neg_one (-1)). |
| 132 |
simpl in H5. rewrite H5. clear H5. |
| 133 |
apply ARopp_involutive. |
| 134 |
+ apply AR_mult_0_le_compat. exact modPlus. |
| 135 |
exact halfPos. |
| 136 |
- unfold mult, Mult_instance_0, ACsqrt, fst, snd. |
| 137 |
rewrite ARmult_comm, ARmult_assoc, ARdouble. |
| 138 |
rewrite ARsqrt_mult, ARsqrt_mult. |
| 139 |
assert (forall a b c : AR, a * c * (b * c) = c * c * (a * b)). |
| 140 |
{ intros. ring. } |
| 141 |
rewrite H5. clear H5. |
| 142 |
pose proof (ARsqrt_correct (inject_Q_AR (1 # 2))). |
| 143 |
simpl in H5. rewrite H5. clear H5. |
| 144 |
rewrite <- (ARsqrt_mult (ACmodulus (x, y) - x)). |
| 145 |
setoid_replace ((ACmodulus (x, y) - x) * (ACmodulus (x, y) + x)) |
| 146 |
with (ACmodulus (x, y) * ACmodulus (x, y) - x*x) |
| 147 |
by ring. |
| 148 |
unfold ACmodulus, fst, snd. |
| 149 |
rewrite (ARsqrt_correct (x*x+y*y)). |
| 150 |
setoid_replace (x * x + y * y - x * x) |
| 151 |
with (y*y) by ring. |
| 152 |
rewrite ARsqrt_srq_abs. |
| 153 |
setoid_replace (2 * ((if yDec then 1 else -1) * (inject_Q_AR (1 # 2) * ARabs y))) |
| 154 |
with (2 * inject_Q_AR (1 # 2) * ((if yDec then 1 else -1) * ARabs y)) |
| 155 |
by ring. |
| 156 |
rewrite twoHalf, ARmult_1_l. |
| 157 |
simpl in yDec. destruct yDec. |
| 158 |
rewrite ARmult_1_l. |
| 159 |
rewrite ARabs_pos. reflexivity. exact a. |
| 160 |
rewrite ARabs_neg. |
| 161 |
rewrite ARmult_neg_one. |
| 162 |
apply ARopp_involutive. |
| 163 |
exact a. |
| 164 |
apply (ARle_trans _ (x*x + 0)). |
| 165 |
rewrite ARplus_0_r. |
| 166 |
apply ARsquare_pos. |
| 167 |
apply ARplus_le_compat_l, ARsquare_pos. |
| 168 |
exact modMinus. |
| 169 |
exact modPlus. |
| 170 |
exact halfPos. |
| 171 |
exact modPlus. |
| 172 |
exact halfPos. |
| 173 |
exact modMinus. |
| 174 |
exact halfPos. |
| 175 |
Qed. |
| 176 |
|
| 177 |
End ACcomplex. |