Debian Codegraph @

reals/fast/MultivariatePolynomials.v

raw
1 Require Import CoRN.algebra.RSetoid.
2 Require Import CoRN.metric2.Metric.
3 Require Import CoRN.metric2.UniformContinuity.
4 Require Import CoRN.algebra.Bernstein.
5 Require Import CoRN.algebra.CRing_Homomorphisms.
6 Require Import CoRN.algebra.COrdFields2.
7 Require Export CoRN.model.ordfields.Qordfield.
8 Require Import CoRN.model.totalorder.QMinMax.
9 Require Import CoRN.tactics.CornTac.
10 Require Import CoRN.tactics.Qauto.
11 Require Import CoRN.model.metric2.Qmetric.
12 From Coq Require Import Qabs.
13 Require Import CoRN.reals.fast.CRabs.
14 Require Import CoRN.reals.fast.ModulusDerivative.
15 Require Import CoRN.reals.fast.CRArith.
16 Require Import CoRN.reals.fast.CRArith_alg.
17
18 Set Implicit Arguments.
19
20 Opaque cpoly_cring.
21 Opaque cpoly_apply_fun.
22 Opaque polyconst.
23
24 Section MultivariatePolynomial.
25
26 (**
27 ** Multivariable polynomails
28
29 Here we prove that multivariable polynomials over the rationals are uniformly continuous
30 on the unit hyperinterval. Hence they can be lifted to apply to real numbers.
31 This allows real numbers to be used in polynomial expressions so that each variable
32 is only approximated once.
33 *)
34
35 Variable F : CRing.
36
37 (** Define the type of multivariable polynomials with [n] variables *)
38 Fixpoint MultivariatePolynomial (n:nat) : CRing :=
39 match n with
40 | O => F
41 | S n' => cpoly_cring (MultivariatePolynomial n')
42 end.
43
44 (** The constant multivariable polynomial *)
45 Fixpoint MVP_C_ (n:nat) : RingHom F (MultivariatePolynomial n) :=
46 match n return RingHom F (MultivariatePolynomial n) with
47 | O => RHid _
48 | S n' => RHcompose _ _ _ _C_ (MVP_C_ n')
49 end.
50
51 (** Apply a multivariable polynomial to a vector of input values *)
52 Fixpoint MVP_apply (n:nat) : MultivariatePolynomial n -> (Vector.t F n) -> F :=
53 match n return MultivariatePolynomial n -> Vector.t F n -> F with
54 | O => fun x _ => x
55 | (S n') => fun p v => (MVP_apply (p ! (MVP_C_ _ (Vector.hd v))) (Vector.tl v))
56 end.
57
58 End MultivariatePolynomial.
59
60 (* begin hide *)
61 Add Parametric Morphism F n : (@MVP_apply F n) with signature (@st_eq (MultivariatePolynomial F n)) ==> (@eq _) ==> (@st_eq _) as MVP_apply_wd.
62 Proof.
63 induction n; intros x y Hxy z.
64 assumption.
65 simpl.
66 apply IHn.
67 rewrite -> Hxy.
68 reflexivity.
69 Qed.
70 (* end hide *)
71
72 (* Multivariable polynomial application by a constant set of inputs is a ring homomorphism. *)
73
74 Lemma zero_MVP_apply : forall F n v, MVP_apply F ([0]:MultivariatePolynomial F n) v[=][0].
75 Proof.
76 induction v.
77 reflexivity.
78 simpl.
79 rewrite <- IHv.
80 reflexivity.
81 Qed.
82
83 Lemma one_MVP_apply : forall F n v, MVP_apply F ([1]:MultivariatePolynomial F n) v[=][1].
84 Proof.
85 induction v.
86 reflexivity.
87 simpl.
88 rewrite <- IHv.
89 rewrite -> one_apply.
90 reflexivity.
91 Qed.
92
93 Lemma C_MVP_apply : forall F n q v, MVP_apply F (MVP_C_ F n q) v[=]q.
94 Proof.
95 induction v.
96 reflexivity.
97 simpl.
98 rewrite -> c_apply.
99 assumption.
100 Qed.
101
102 Lemma MVP_plus_apply: forall F n (p q : MultivariatePolynomial F n) v,
103 MVP_apply F (p[+]q) v [=] MVP_apply F p v[+]MVP_apply F q v.
104 Proof.
105 induction v.
106 reflexivity.
107 simpl.
108 rewrite -> plus_apply.
109 apply IHv.
110 Qed.
111
112 Lemma MVP_mult_apply: forall F n (p q : MultivariatePolynomial F n) v,
113 MVP_apply F (p[*]q) v [=] MVP_apply F p v[*]MVP_apply F q v.
114 Proof.
115 induction v.
116 reflexivity.
117 simpl.
118 rewrite -> mult_apply.
119 apply IHv.
120 Qed.
121
122 Lemma MVP_c_mult_apply: forall F n (p : MultivariatePolynomial F n) c v,
123 MVP_apply F (MVP_C_ _ _ c[*]p) v[=]c[*]MVP_apply F p v.
124 Proof.
125 induction v.
126 reflexivity.
127 simpl.
128 rewrite <- IHv.
129 rewrite -> c_mult_apply.
130 reflexivity.
131 Qed.
132
133 Lemma MVP_apply_hom_strext : forall (F:CRing) n (v:Vector.t F n), fun_strext (fun (p:MultivariatePolynomial F n) => MVP_apply _ p v).
134 Proof.
135 induction n.
136 intros v x y.
137 simpl.
138 auto with *.
139 intros v x y H.
140 simpl in H.
141 destruct (csbf_strext _ _ _ _ _ _ _ _ (IHn _ _ _ H)) as [H0 | H0].
142 assumption.
143 elim (ap_irreflexive _ _ H0).
144 Defined.
145
146 Definition MVP_apply_hom_csf (F:CRing) n (v:Vector.t F n) :=
147 Build_CSetoid_fun _ _ _ (MVP_apply_hom_strext F v).
148
149 Definition MVP_apply_hom (F:CRing) n (v:Vector.t F n) : RingHom (MultivariatePolynomial F n) F.
150 Proof.
151 exists (MVP_apply_hom_csf F v).
152 intros x y; apply: MVP_plus_apply.
153 intros x y; apply: MVP_mult_apply.
154 apply: one_MVP_apply.
155 Defined.
156
157 (** [MVP_map] applies a ring homomorphism to the coefficents of a multivariable polynomial *)
158 Fixpoint MVP_map R S (f:RingHom R S) (n:nat) : RingHom (MultivariatePolynomial R n) (MultivariatePolynomial S n) :=
159 match n return RingHom (MultivariatePolynomial R n) (MultivariatePolynomial S n) with
160 | O => f
161 | (S n') => cpoly_map (MVP_map f n')
162 end.
163
164 Lemma MVP_map_C_ : forall R S (f:RingHom R S) n c,
165 MVP_map f n (MVP_C_ _ _ c)[=]MVP_C_ _ _ (f c).
166 Proof.
167 induction n.
168 intros c; reflexivity.
169 intros c.
170 simpl.
171 change (cpoly_map (MVP_map f n) (_C_ (MVP_C_ R n c))[=]_C_ (MVP_C_ S n (f c))).
172 rewrite -> cpoly_map_C.
173 rewrite -> IHn.
174 reflexivity.
175 Qed.
176
177 (* In practice we use the Bernstein coeffecients to bound the polynomials *)
178 (** Some upper bound on the polynomial on [0,1] *)
179 Fixpoint MVP_upperBound (n:nat) : MultivariatePolynomial Q_as_CRing n -> Q :=
180 match n return MultivariatePolynomial Q_as_CRing n -> Q with
181 | O => fun x => x
182 | (S n') => fun p => let (m,b) := BernsteinCoefficents (MVP_C_ Q_as_CRing n') p
183 in Vector.t_rec _ (fun _ _ => Q) 0%Q
184 (fun c _ _ rec => Qmax (MVP_upperBound n' c) rec) m b
185 end.
186
187 (** Some lower bound on the polynomial on [0,1] *)
188 Fixpoint MVP_lowerBound (n:nat) : MultivariatePolynomial Q_as_CRing n -> Q :=
189 match n return MultivariatePolynomial Q_as_CRing n -> Q with
190 | O => fun x => x
191 | (S n') => fun p => let (m,b) := BernsteinCoefficents (MVP_C_ Q_as_CRing n') p
192 in Vector.t_rec _ (fun _ _ => Q) 0%Q
193 (fun c _ _ rec => Qmin (MVP_lowerBound n' c) rec) m b
194 end.
195
196 Local Open Scope Q_scope.
197
198 (** Definition of the unit hyperinterval of n dimensions *)
199 Fixpoint UnitHyperInterval (n:nat) (v:Vector.t Q n) : Prop :=
200 match v with
201 | Vector.nil _ => True
202 | Vector.cons _ a _ v' => 0 <= a <= 1 /\ UnitHyperInterval v'
203 end.
204
205 (* begin hide *)
206 Lemma BernsteinApplyRingHom : forall R F (eta: RingHom R F) n i (H:(i <= n)%nat) a,
207 (Bernstein F H) ! (eta a)[=](eta (Bernstein R H) ! a).
208 Proof.
209 induction n.
210 simpl.
211 intros _ _ a.
212 do 2 rewrite -> one_apply.
213 auto with *.
214 intros [|i] H a; simpl;[|destruct (le_lt_eq_dec (S i) (S n) H)]; autorewrite with apply ringHomPush;
215 repeat rewrite -> IHn; reflexivity.
216 Qed.
217
218 Lemma MVP_BernsteinNonNeg : forall m n i (H:(i <= n)%nat) v (a:Q), 0 <= a -> a <= 1 ->
219 0 <= @MVP_apply Q_as_CRing m ((Bernstein _ H)!(MVP_C_ _ _ a)) v.
220 Proof.
221 intros m n i H v a Ha0 Ha1.
222 induction v.
223 apply: BernsteinNonNeg; auto.
224 simpl.
225 replace RHS with (MVP_apply Q_as_CRing (Bernstein _ H) ! (MVP_C_ Q_as_CRing n0 a) v).
226 apply IHv.
227 apply: MVP_apply_wd; try reflexivity.
228 rewrite -> BernsteinApplyRingHom.
229 auto with *.
230 Qed.
231 (* end hide *)
232
233 (** Return the ith entry of a vector *)
234 Fixpoint Vector_ix A (n i:nat) (H:(i < n)%nat) (v:Vector.t A n) : A :=
235 match v in Vector.t _ m return (i < m)%nat -> A with
236 | Vector.nil _ => fun p => False_rect _ (Nat.nlt_0_r _ p)
237 | Vector.cons _ c n' v' => fun _ => match lt_le_dec i n' with
238 | left p => Vector_ix p v'
239 | right _ => c
240 end
241 end H.
242
243 (** The upper and lower bounds are correct. *)
244 Lemma MVP_upperBound_correct : forall n p v, UnitHyperInterval v -> MVP_apply _ p v[<=]MVP_upperBound n p.
245 Proof.
246 induction n; intros p v H.
247 apply Qle_refl.
248 revert p H.
249 dependent inversion v as [|a n0 v0].
250 clear H.
251 intros p [[Ha0 Ha1] Hv].
252 stepl (@MVP_apply Q_as_CRing (S n) (let (n0, b) := BernsteinCoefficents (MVP_C_ Q_as_CRing n) p in
253 evalBernsteinBasis (MultivariatePolynomial Q_as_CRing n) b) (@Vector.cons Q a n v0));
254 [|apply MVP_apply_wd;[apply evalBernsteinCoefficents|reflexivity]].
255 simpl (MVP_upperBound (S n) p).
256 destruct (BernsteinCoefficents (MVP_C_ Q_as_CRing n) p) as [m b].
257 apply Qle_trans with (Vector.t_rec (MultivariatePolynomial Q_as_CRing n)
258 (fun (n1 : nat) (_ : Vector.t (MultivariatePolynomial Q_as_CRing n) n1) => Q) 0
259 (fun (c : MultivariatePolynomial Q_as_CRing n) (n1 : nat)
260 (_ : Vector.t (MultivariatePolynomial Q_as_CRing n) n1) (rec : Q) =>
261 Qmax (MVP_apply _ c v0) rec) m b).
262 clear IHn Hv.
263 destruct m as [|m].
264 rewrite (V0_eq b).
265 unfold evalBernsteinBasis.
266 simpl.
267 rewrite -> zero_MVP_apply.
268 apply Qle_refl.
269 unfold evalBernsteinBasis.
270 match goal with |- (?A <= ?B) => set (L:=A); set (R:=B) end.
271 change (L[<=]R).
272 rstepr (R[*][1]).
273 rewrite <- (@one_MVP_apply Q_as_CRing _ (Vector.cons _ a _ v0)).
274 stepr (R[*](@MVP_apply Q_as_CRing (S n) (@Sumx (cpoly_cring _) _ (fun i H => Bernstein _ (proj1 (Nat.lt_succ_r i m) (Nat.lt_le_trans _ _ _ H (Nat.le_refl _))))) (Vector.cons _ a _ v0))).
275 fold (MultivariatePolynomial Q_as_CRing n).
276 unfold L, R; clear L R.
277 generalize (Nat.le_refl (S m)).
278 revert b.
279 generalize (S m) at 1 2 5 6 7 8 11.
280 induction b as [| a0]; intros l.
281 simpl.
282 rewrite -> zero_MVP_apply.
283 apply Qle_refl.
284 simpl (Vector.t_rec (MultivariatePolynomial Q_as_CRing n)
285 (fun (n2 : nat) (_ : Vector.t (MultivariatePolynomial Q_as_CRing n) n2) => Q) 0
286 (fun (c : MultivariatePolynomial Q_as_CRing n) (n2 : nat)
287 (_ : Vector.t (MultivariatePolynomial Q_as_CRing n) n2) (rec : Q) =>
288 Qmax (MVP_apply Q_as_CRing c v0) rec) (S n1)
289 (Vector.cons _ a0 _ b)).
290 simpl (evalBernsteinBasisH (MultivariatePolynomial Q_as_CRing n)
291 (Vector.cons (MultivariatePolynomial Q_as_CRing n) a0 n1 b) l).
292 simpl (Sumx (fun (i : nat) (H : (i < S n1)%nat) => Bernstein (MultivariatePolynomial Q_as_CRing n)
293 (proj1 (Nat.lt_succ_r i m) (Nat.lt_le_trans i (S n1) (S m) H l)))).
294 do 2 rewrite -> MVP_plus_apply.
295 rewrite -> (Qplus_comm (@MVP_apply Q_as_CRing (S n) (Sumx (fun (i : nat) (l0 : (i < n1)%nat) =>
296 Bernstein (MultivariatePolynomial Q_as_CRing n)
297 (proj1 (Nat.lt_succ_r i m) (Nat.lt_le_trans i (S n1) (S m) (Nat.lt_lt_succ_r i n1 l0) l)))) (Vector.cons Q a n v0))).
298 rewrite -> Qmult_comm.
299 rewrite -> Qmult_plus_distr_l.
300 apply Qplus_le_compat; rewrite -> Qmult_comm; rewrite -> Qmax_mult_pos_distr_l.
301 replace LHS with (MVP_apply Q_as_CRing a0 v0 * @MVP_apply Q_as_CRing (S n)
302 (Bernstein (MultivariatePolynomial Q_as_CRing n)
303 (proj1 (Nat.lt_succ_r n1 m) (Nat.lt_le_trans n1 (S n1) (S m) (Nat.lt_succ_diag_r n1) l))) (Vector.cons _ a _ v0)).
304 apply Qmax_ub_l.
305 simpl.
306 rewrite <- (MVP_mult_apply Q_as_CRing).
307 apply: MVP_apply_wd; try reflexivity.
308 replace (proj1 (Nat.lt_succ_r n1 m) (Nat.lt_le_trans n1 (S n1) (S m) (Nat.lt_succ_diag_r n1) l))
309 with (proj2 (Nat.succ_le_mono n1 m) l) by apply le_irrelevent.
310 replace (le_S_n n1 m l) with (proj2 (Nat.succ_le_mono n1 m) l) by apply le_irrelevent.
311 apply c_mult_apply.
312 apply MVP_BernsteinNonNeg; auto.
313 eapply Qle_trans;[|apply Qmax_ub_r].
314 set (R:=Vector.t_rec (MultivariatePolynomial Q_as_CRing n)
315 (fun (n2 : nat) (_ : Vector.t (MultivariatePolynomial Q_as_CRing n) n2) => Q) 0
316 (fun (c : MultivariatePolynomial Q_as_CRing n) (n2 : nat)
317 (_ : Vector.t (MultivariatePolynomial Q_as_CRing n) n2) (rec : Q) =>
318 Qmax (MVP_apply Q_as_CRing c v0) rec) n1 b) in *.
319 replace RHS with (R*@MVP_apply Q_as_CRing (S n) (Sumx (fun (i : nat) (l0 : (i < n1)%nat) =>
320 Bernstein (MultivariatePolynomial Q_as_CRing n)
321 (proj1 (Nat.lt_succ_r i m) (Nat.lt_le_trans i n1 (S m) l0 (Nat.lt_le_incl _ _ l))))) (Vector.cons _ a _ v0)).
322 apply IHb.
323 apply: mult_wdr.
324 apply MVP_apply_wd; try reflexivity.
325 apply Sumx_wd.
326 intros i H.
327 replace (proj1 (Nat.lt_succ_r i m) (Nat.lt_le_trans i (S n1) (S m) (Nat.lt_lt_succ_r i n1 H) l))
328 with (proj1 (Nat.lt_succ_r i m) (Nat.lt_le_trans i n1 (S m) H (Nat.lt_le_incl n1 (S m) l))) by apply le_irrelevent.
329 reflexivity.
330 clear - Ha0 Ha1.
331 induction n1.
332 rewrite -> zero_MVP_apply.
333 auto with *.
334 simpl (Sumx (fun (i : nat) (l0 : (i < S n1)%nat) => Bernstein (MultivariatePolynomial Q_as_CRing n)
335 (proj1 (Nat.lt_succ_r i m) (Nat.lt_le_trans i (S (S n1)) (S m) (Nat.lt_lt_succ_r i (S n1) l0) l)))).
336 rewrite -> MVP_plus_apply.
337 apply: plus_resp_nonneg.
338 stepr (@MVP_apply Q_as_CRing (S n) (Sumx (fun (i : nat) (l0 : (i < n1)%nat) =>
339 Bernstein (MultivariatePolynomial Q_as_CRing n)
340 (proj1 (Nat.lt_succ_r i m) (Nat.lt_le_trans i (S n1) (S m) (Nat.lt_lt_succ_r i n1 l0) (Nat.lt_le_incl _ _ l))))) (Vector.cons _ a _ v0)).
341 apply IHn1.
342 apply MVP_apply_wd; try reflexivity.
343 apply Sumx_wd.
344 intros i H.
345 replace (proj1 (Nat.lt_succ_r i m) (Nat.lt_le_trans i (S n1) (S m) (Nat.lt_lt_succ_r i n1 H) (Nat.lt_le_incl (S n1) (S m) l)))
346 with (proj1 (Nat.lt_succ_r i m) (Nat.lt_le_trans i (S (S n1)) (S m) (Nat.lt_lt_succ_r i (S n1) (Nat.lt_lt_succ_r i n1 H)) l))
347 by apply le_irrelevent.
348 reflexivity.
349 apply MVP_BernsteinNonNeg; auto with *.
350 apply mult_wdr.
351 apply MVP_apply_wd; try reflexivity.
352 simpl (MultivariatePolynomial Q_as_CRing (S n)).
353 rewrite <- (fun X => partitionOfUnity X m).
354 apply Sumx_wd.
355 intros i H.
356 replace (proj1 (Nat.lt_succ_r i m) (Nat.lt_le_trans i (S m) (S m) H (Nat.le_refl (S m))))
357 with (proj1 (Nat.lt_succ_r i m) H) by apply le_irrelevent.
358 reflexivity.
359 clear - IHn Hv.
360 induction b.
361 auto with *.
362 apply Qmax_le_compat.
363 apply IHn; apply Hv.
364 auto.
365 Qed.
366
367 Lemma MVP_lowerBound_correct : forall n p v, UnitHyperInterval v -> MVP_lowerBound n p[<=]MVP_apply _ p v.
368 Proof.
369 induction n; intros p v H.
370 apply Qle_refl.
371 revert p H.
372 dependent inversion v as [| a n0 v0 ].
373 clear H.
374 intros p [[Ha0 Ha1] Hv].
375 stepr (@MVP_apply Q_as_CRing (S n) (let (n0, b) := BernsteinCoefficents (MVP_C_ Q_as_CRing n) p in
376 evalBernsteinBasis (MultivariatePolynomial Q_as_CRing n) b) (Vector.cons _ a _ v0));
377 [|apply MVP_apply_wd;[apply evalBernsteinCoefficents|reflexivity]].
378 simpl (MVP_lowerBound (S n) p).
379 destruct (BernsteinCoefficents (MVP_C_ Q_as_CRing n) p) as [m b].
380 apply Qle_trans with (Vector.t_rec (MultivariatePolynomial Q_as_CRing n)
381 (fun (n1 : nat) (_ : Vector.t (MultivariatePolynomial Q_as_CRing n) n1) => Q) 0
382 (fun (c : MultivariatePolynomial Q_as_CRing n) (n1 : nat)
383 (_ : Vector.t (MultivariatePolynomial Q_as_CRing n) n1) (rec : Q) =>
384 Qmin (MVP_apply _ c v0) rec) m b).
385 clear - IHn Hv.
386 induction b.
387 auto with *.
388 apply Qmin_le_compat.
389 apply IHn; apply Hv.
390 auto.
391 clear IHn Hv.
392 destruct m as [|m].
393 rewrite (V0_eq b).
394 unfold evalBernsteinBasis.
395 simpl.
396 rewrite -> zero_MVP_apply.
397 apply Qle_refl.
398 unfold evalBernsteinBasis.
399 match goal with |- (?A <= ?B) => set (R:=A); set (L:=B) end.
400 change (R[<=]L).
401 rstepl (R[*][1]).
402 rewrite <- (@one_MVP_apply Q_as_CRing _ (Vector.cons _ a _ v0)).
403 stepl (R[*](@MVP_apply Q_as_CRing (S n) (@Sumx (cpoly_cring _) _ (fun i H => Bernstein _ (proj1 (Nat.lt_succ_r i m) (Nat.lt_le_trans _ _ _ H (Nat.le_refl _))))) (Vector.cons _ a _ v0))).
404 fold (MultivariatePolynomial Q_as_CRing n).
405 unfold L, R; clear L R.
406 generalize (Nat.le_refl (S m)).
407 revert b.
408 generalize (S m) at 1 2 4 5 6 9 12.
409 induction b as [| a0]; intros l.
410 simpl.
411 rewrite -> zero_MVP_apply.
412 apply Qle_refl.
413 simpl (Vector.t_rec (MultivariatePolynomial Q_as_CRing n)
414 (fun (n2 : nat) (_ : Vector.t (MultivariatePolynomial Q_as_CRing n) n2) => Q) 0
415 (fun (c : MultivariatePolynomial Q_as_CRing n) (n2 : nat)
416 (_ : Vector.t (MultivariatePolynomial Q_as_CRing n) n2) (rec : Q) =>
417 Qmin (MVP_apply Q_as_CRing c v0) rec) (S n1)
418 (Vector.cons _ a0 _ b)).
419 simpl (evalBernsteinBasisH (MultivariatePolynomial Q_as_CRing n)
420 (Vector.cons _ a0 _ b) l).
421 simpl (Sumx (fun (i : nat) (H : (i < S n1)%nat) => Bernstein (MultivariatePolynomial Q_as_CRing n)
422 (proj1 (Nat.lt_succ_r i m) (Nat.lt_le_trans i (S n1) (S m) H l)))).
423 do 2 rewrite -> MVP_plus_apply.
424 rewrite -> (Qplus_comm (@MVP_apply Q_as_CRing (S n) (Sumx (fun (i : nat) (l0 : (i < n1)%nat) =>
425 Bernstein (MultivariatePolynomial Q_as_CRing n)
426 (proj1 (Nat.lt_succ_r i m) (Nat.lt_le_trans i (S n1) (S m) (Nat.lt_lt_succ_r i n1 l0) l)))) (Vector.cons _ a _ v0))).
427 rewrite -> Qmult_comm.
428 rewrite -> Qmult_plus_distr_l.
429 apply Qplus_le_compat; rewrite -> Qmult_comm; rewrite -> Qmin_mult_pos_distr_l.
430 replace RHS with (MVP_apply Q_as_CRing a0 v0 * @MVP_apply Q_as_CRing (S n)
431 (Bernstein (MultivariatePolynomial Q_as_CRing n)
432 (proj1 (Nat.lt_succ_r n1 m) (Nat.lt_le_trans n1 (S n1) (S m) (Nat.lt_succ_diag_r n1) l))) (Vector.cons _ a _ v0)).
433 apply Qmin_lb_l.
434 simpl.
435 rewrite <- (MVP_mult_apply Q_as_CRing).
436 apply: MVP_apply_wd; try reflexivity.
437 replace (proj1 (Nat.lt_succ_r n1 m) (Nat.lt_le_trans n1 (S n1) (S m) (Nat.lt_succ_diag_r n1) l))
438 with (proj2 (Nat.succ_le_mono n1 m) l) by apply le_irrelevent.
439 replace (le_S_n n1 m l) with (proj2 (Nat.succ_le_mono n1 m) l) by apply le_irrelevent.
440 apply c_mult_apply.
441 apply MVP_BernsteinNonNeg; auto.
442 eapply Qle_trans;[apply Qmin_lb_r|].
443 set (R:=Vector.t_rec (MultivariatePolynomial Q_as_CRing n)
444 (fun (n2 : nat) (_ : Vector.t (MultivariatePolynomial Q_as_CRing n) n2) => Q) 0
445 (fun (c : MultivariatePolynomial Q_as_CRing n) (n2 : nat)
446 (_ : Vector.t (MultivariatePolynomial Q_as_CRing n) n2) (rec : Q) =>
447 Qmin (MVP_apply Q_as_CRing c v0) rec) n1 b) in *.
448 replace LHS with (R*@MVP_apply Q_as_CRing (S n) (Sumx (fun (i : nat) (l0 : (i < n1)%nat) =>
449 Bernstein (MultivariatePolynomial Q_as_CRing n)
450 (proj1 (Nat.lt_succ_r i m) (Nat.lt_le_trans i n1 (S m) l0 (Nat.lt_le_incl _ _ l))))) (Vector.cons _ a _ v0)).
451 apply IHb.
452 apply: mult_wdr.
453 apply MVP_apply_wd; try reflexivity.
454 apply Sumx_wd.
455 intros i H.
456 replace (proj1 (Nat.lt_succ_r i m) (Nat.lt_le_trans i (S n1) (S m) (Nat.lt_lt_succ_r i n1 H) l))
457 with (proj1 (Nat.lt_succ_r i m) (Nat.lt_le_trans i n1 (S m) H (Nat.lt_le_incl n1 (S m) l))) by apply le_irrelevent.
458 reflexivity.
459 clear - Ha0 Ha1.
460 induction n1.
461 rewrite -> zero_MVP_apply.
462 auto with *.
463 simpl (Sumx (fun (i : nat) (l0 : (i < S n1)%nat) => Bernstein (MultivariatePolynomial Q_as_CRing n)
464 (proj1 (Nat.lt_succ_r i m) (Nat.lt_le_trans i (S (S n1)) (S m) (Nat.lt_lt_succ_r i (S n1) l0) l)))).
465 rewrite -> MVP_plus_apply.
466 apply: plus_resp_nonneg.
467 stepr (@MVP_apply Q_as_CRing (S n) (Sumx (fun (i : nat) (l0 : (i < n1)%nat) =>
468 Bernstein (MultivariatePolynomial Q_as_CRing n)
469 (proj1 (Nat.lt_succ_r i m) (Nat.lt_le_trans i (S n1) (S m) (Nat.lt_lt_succ_r i n1 l0) (Nat.lt_le_incl _ _ l))))) (Vector.cons _ a _ v0)).
470 apply IHn1.
471 apply MVP_apply_wd; try reflexivity.
472 apply Sumx_wd.
473 intros i H.
474 replace (proj1 (Nat.lt_succ_r i m) (Nat.lt_le_trans i (S n1) (S m) (Nat.lt_lt_succ_r i n1 H) (Nat.lt_le_incl (S n1) (S m) l)))
475 with (proj1 (Nat.lt_succ_r i m) (Nat.lt_le_trans i (S (S n1)) (S m) (Nat.lt_lt_succ_r i (S n1) (Nat.lt_lt_succ_r i n1 H)) l))
476 by apply le_irrelevent.
477 reflexivity.
478 apply MVP_BernsteinNonNeg; auto with *.
479 apply mult_wdr.
480 apply MVP_apply_wd; try reflexivity.
481 simpl (MultivariatePolynomial Q_as_CRing (S n)).
482 rewrite <- (fun X => partitionOfUnity X m).
483 apply Sumx_wd.
484 intros i H.
485 replace (proj1 (Nat.lt_succ_r i m) (Nat.lt_le_trans i (S m) (S m) H (Nat.le_refl (S m))))
486 with (proj1 (Nat.lt_succ_r i m) H) by apply le_irrelevent.
487 reflexivity.
488 Qed.
489
490 Local Open Scope Q_scope.
491
492 (** Use the upper and lower bounds of the derivative of a polynomial to
493 define its modulus of continuity. *)
494 Definition MVP_apply_modulus n (p:MultivariatePolynomial Q_as_CRing (S n)) :=
495 let p' := (_D_ p) in
496 Qscale_modulus (Qmax (MVP_upperBound (S n) p') (-(MVP_lowerBound (S n) p'))).
497
498 Lemma MVP_apply_modulus_correct
499 : forall n (p:MultivariatePolynomial Q_as_CRing (S n)) x y e,
500 (0 <= x) -> (x <= 1) -> (0 <= y) -> (y <= 1) ->
501 @ball_ex Q_as_MetricSpace (MVP_apply_modulus p e) x y ->
502 forall (v:Vector.t Q n), UnitHyperInterval v ->
503 @ball Q_as_MetricSpace (proj1_sig e) (MVP_apply _ p (Vector.cons _ x _ v):Q) (MVP_apply _ p (Vector.cons _ y _ v)).
504 Proof.
505 intros n p x y e Hx0 Hx1 Hy0 Hy1 Hxy v Hv.
506 assert (Hx : (Qmax 0 (Qmin 1 x))==x).
507 rewrite -> Qle_min_r in Hx1.
508 rewrite -> Hx1.
509 rewrite -> Qle_max_r in Hx0.
510 rewrite -> Hx0.
511 reflexivity.
512 assert (Hy : (Qmax 0 (Qmin 1 y))==y).
513 rewrite -> Qle_min_r in Hy1.
514 rewrite -> Hy1.
515 rewrite -> Qle_max_r in Hy0.
516 rewrite -> Hy0.
517 reflexivity.
518 simpl.
519 rewrite <- Hx.
520 rewrite <- Hy.
521 unfold MVP_apply_modulus in Hxy.
522 set (c:=(Qmax (MVP_upperBound (S n) (_D_ p)) (- MVP_lowerBound (S n) (_D_ p)))) in *.
523 set (fp:=cpoly_map (RHcompose _ _ _ (inj_Q_hom IR) (MVP_apply_hom _ v)) p).
524 apply (fun A B e => is_UniformlyContinuousD_Q (Some 0) (Some 1) refl_equal (FPoly _ fp) (FPoly _ (_D_ fp)) (Derivative_poly _ _ _)
525 (fun x => (MVP_apply _ p (Vector.cons _ x _ v))) A c B e x y); try assumption.
526 unfold fp.
527 simpl.
528 intros q _ _.
529 clear - p.
530 change (inj_Q_hom IR (MVP_apply_hom Q_as_CRing v p ! (MVP_C_ Q_as_CRing n q))[=]
531 (cpoly_map (RHcompose (MultivariatePolynomial Q_as_CRing n) Q_as_CRing IR
532 (inj_Q_hom IR) (MVP_apply_hom Q_as_CRing v)) p) ! (inj_Q_hom IR q)).
533 rewrite -> cpoly_map_compose.
534 rewrite <- cpoly_map_apply.
535 apply inj_Q_wd.
536 rewrite -> cpoly_map_apply.
537 apply csbf_wd; try reflexivity.
538 apply: C_MVP_apply.
539 simpl.
540 clear - c Hv.
541 intros x _ [H0x Hx1].
542 change (AbsIR (_D_ (cpoly_map (RHcompose (MultivariatePolynomial Q_as_CRing n) Q_as_CRing IR
543 (inj_Q_hom IR) (MVP_apply_hom Q_as_CRing v)) p)) ! (inj_Q_hom IR x)[<=] inj_Q IR c).
544 rewrite <- cpoly_map_diff.
545 rewrite -> cpoly_map_compose.
546 rewrite <- cpoly_map_apply.
547 change (AbsIR (inj_Q IR (cpoly_map (MVP_apply_hom Q_as_CRing v) (_D_ p)) ! x)[<=]inj_Q IR c).
548 rewrite -> AbsIR_Qabs.
549 apply inj_Q_leEq.
550 assert (Hx: 0 <= x <= 1).
551 split; apply (leEq_inj_Q IR).
552 rewrite -> inj_Q_Zero.
553 rstepl ([0][/][0][+][1][//]den_is_nonzero IR 0); auto.
554 rewrite -> inj_Q_One.
555 rstepr ([1][/][0][+][1][//]den_is_nonzero IR 1); auto.
556 setoid_replace ((cpoly_map (MVP_apply_hom Q_as_CRing v) (_D_ p)) ! x)
557 with (@MVP_apply Q_as_CRing (S n) (_D_ p) (Vector.cons _ x _ v)).
558 apply Qabs_case; intros H.
559 eapply Qle_trans;[|apply Qmax_ub_l].
560 apply MVP_upperBound_correct.
561 split; auto.
562 eapply Qle_trans;[|apply Qmax_ub_r].
563 apply Qopp_le_compat.
564 apply MVP_lowerBound_correct.
565 split; auto.
566 generalize (_D_ p).
567 intros s; clear -s.
568 simpl.
569 change ((cpoly_map_fun (MultivariatePolynomial Q_as_CRing n) Q_as_CRing
570 (MVP_apply_hom Q_as_CRing v) s) ! x == MVP_apply_hom Q_as_CRing v (s ! (MVP_C_ Q_as_CRing n x))).
571 rewrite -> cpoly_map_apply.
572 simpl.
573 rewrite -> C_MVP_apply.
574 reflexivity.
575 Qed.
576
577 Local Open Scope uc_scope.
578
579 (** Clamp a value to the unit interval *)
580 Definition Qclamp01 := QboundBelow_uc (0) ∘ QboundAbove_uc 1.
581
582 Lemma Qclamp01_clamped : forall x, 0 <= Qclamp01 x <= 1.
583 Proof.
584 intros x.
585 unfold Qclamp01.
586 split; simpl.
587 apply Qmax_ub_l.
588 rewrite -> Qmax_min_distr_r.
589 apply Qmin_lb_l.
590 Qed.
591
592 Lemma Qclamp01_le : forall x y, x <= y -> Qclamp01 x <= Qclamp01 y.
593 Proof.
594 intros x y H.
595 simpl.
596 apply Qmax_le_compat; auto with *.
597 apply Qmin_le_compat; auto with *.
598 Qed.
599
600 Lemma Qclamp01_close : forall e x y, Qabs (x-y) <= e -> Qabs (Qclamp01 x - Qclamp01 y) <= e.
601 Proof.
602 intros e.
603 cut (forall x y : Q, y <= x -> x - y <= e -> Qclamp01 x - Qclamp01 y <= e).
604 intros H x y.
605 destruct (Qle_total x y).
606 rewrite -> Qabs_neg.
607 intros He.
608 rewrite -> Qabs_neg.
609 replace LHS with (Qclamp01 y - Qclamp01 x) by simpl; ring.
610 apply H; auto.
611 replace LHS with (- (x-y)) by simpl; ring.
612 auto.
613 apply (shift_minus_leEq Q_as_COrdField).
614 stepr (Qclamp01 y); [| now (simpl; ring)].
615 apply Qclamp01_le.
616 auto.
617 apply (shift_minus_leEq Q_as_COrdField).
618 stepr y; [| now (simpl; ring)].
619 auto.
620 rewrite -> Qabs_pos.
621 intros He.
622 rewrite -> Qabs_pos.
623 apply H; auto.
624 apply: shift_zero_leEq_minus.
625 apply Qclamp01_le.
626 auto.
627 apply: shift_zero_leEq_minus.
628 auto.
629 intros x y Hxy He.
630 simpl.
631 apply (Qmin_case 1 y).
632 intros Hy.
633 assert (Hx:=Qle_trans _ _ _ Hy Hxy).
634 rewrite -> Qle_min_l in Hx.
635 rewrite -> Hx.
636 replace LHS with 0 by simpl; ring.
637 eapply Qle_trans;[|apply He].
638 apply: shift_zero_leEq_minus; auto.
639 apply (Qmin_case 1 x).
640 intros Hx Hy.
641 eapply Qle_trans;[|apply He].
642 apply Qplus_le_compat; auto.
643 apply Qopp_le_compat.
644 apply Qmax_ub_r.
645 intros _ _.
646 apply (Qmax_case 0 x); intros Hx.
647 assert (Hy:=Qle_trans _ _ _ Hxy Hx).
648 rewrite -> Qle_max_l in Hy.
649 rewrite -> Hy.
650 eapply Qle_trans;[|apply He].
651 apply: shift_zero_leEq_minus; auto.
652 apply (Qmax_case 0 y); intros Hy.
653 eapply Qle_trans;[|apply He].
654 apply Qplus_le_compat; auto with *.
655 auto.
656 Qed.
657
658 Require Import CoRN.algebra.RSetoid.
659
660 (** Definition of a setoid function type of n parameters *)
661 Fixpoint n_Function X Y (n:nat) :=
662 match n with
663 |O => Y
664 |S n' => extSetoid X (n_Function X Y n')
665 end.
666
667 (** Definition of a uniformly continuous function type of n parameters *)
668 Fixpoint n_UniformlyContinuousFunction (X Y:MetricSpace) (n:nat) :=
669 match n with
670 |O => Y
671 |S n' => X --> (n_UniformlyContinuousFunction X Y n')
672 end.
673
674 (** [MVP_uc_sig] is a recursive type definition that is needed for part of the definition of
675 of a multivariable polynomial as a uniformly continuous function. *)
676 Fixpoint MVP_uc_sig (n:nat) :MultivariatePolynomial Q_as_CRing n -> n_UniformlyContinuousFunction Q_as_MetricSpace Q_as_MetricSpace n -> Type :=
677 match n return MultivariatePolynomial Q_as_CRing n -> n_UniformlyContinuousFunction Q_as_MetricSpace Q_as_MetricSpace n -> Type with
678 | O => fun p x => p==x
679 | (S n') => fun p f => forall v, MVP_uc_sig n' (p ! (MVP_C_ Q_as_CRing _ (Qclamp01 v))) (f v)
680 end.
681
682 Lemma MVP_uc_rec (n : nat)
683 (IHn : forall p : MultivariatePolynomial Q_as_CRing n,
684 {f : n_UniformlyContinuousFunction Q_as_MetricSpace Q_as_MetricSpace n &
685 MVP_uc_sig n p f})
686 (p : MultivariatePolynomial Q_as_CRing (S n))
687 : @is_UniformlyContinuousFunction
688 Q_as_MetricSpace (n_UniformlyContinuousFunction Q_as_MetricSpace Q_as_MetricSpace n)
689 (fun (x:Q_as_CRing) => ProjT1 (IHn (p ! (MVP_C_ Q_as_CRing _ (Qclamp01 x))))) (MVP_apply_modulus p).
690 Proof.
691 intros e x y Hxy.
692 assert (Hxy' : ball_ex (MVP_apply_modulus p e) (Qclamp01 x) (Qclamp01 y)) by
693 (destruct (MVP_apply_modulus p e); auto; simpl; rewrite -> Qball_Qabs; apply: Qclamp01_close;
694 rewrite <- Qball_Qabs; auto).
695 destruct (Qclamp01_clamped x) as [Hx0 Hx1].
696 destruct (Qclamp01_clamped y) as [Hy0 Hy1].
697 assert (X:=@MVP_apply_modulus_correct _ p (Qclamp01 x) (Qclamp01 y) e Hx0 Hx1 Hy0 Hy1 Hxy').
698 clear Hxy Hxy'; generalize (proj2_sigT _ _ (IHn p ! (MVP_C_ Q_as_CRing n (Qclamp01 x))))
699 (proj2_sigT _ _ (IHn p ! (MVP_C_ Q_as_CRing n (Qclamp01 y)))).
700 set (x':=Qclamp01 x) in *; set (y':=Qclamp01 y) in *; simpl in X; revert X.
701 generalize (ProjT1 (IHn p ! (MVP_C_ Q_as_CRing n x')))
702 (ProjT1 (IHn p ! (MVP_C_ Q_as_CRing n y'))).
703 change (Q_as_CSetoid) with (csg_crr Q_as_CRing).
704 generalize (p ! (MVP_C_ Q_as_CRing n x')) (p ! (MVP_C_ Q_as_CRing n y')).
705 clear - e.
706 induction n.
707 - simpl; intros p q s t H Hs Ht;
708 rewrite <- Hs, <- Ht; apply (H (Vector.nil _)); constructor.
709 - simpl.
710 intros p q s t H Hs Ht. split.
711 apply Qpos_nonneg.
712 intro v; apply (fun H => IHn _ _ _ _ H (Hs v) (Ht v));
713 intros v0 Hv0; apply (H (Vector.cons _ (Qclamp01 v) _ v0)); split; auto;
714 apply Qclamp01_clamped.
715 Qed.
716
717 (** Multivariable polynomials are uniformly continuous on the unit hyper interval *)
718 Definition MVP_uc : forall n (p:MultivariatePolynomial Q_as_CRing n),
719 {f:n_UniformlyContinuousFunction Q_as_MetricSpace Q_as_MetricSpace n
720 |MVP_uc_sig _ p f}.
721 Proof.
722 induction n.
723 intros x.
724 exists x.
725 simpl.
726 reflexivity.
727 intros p.
728 exists (Build_UniformlyContinuousFunction (MVP_uc_rec IHn p)).
729 simpl.
730 intros v.
731 exact (ProjT2 (IHn p ! (MVP_C_ Q_as_CRing n (Qclamp01 v)))).
732 Defined.
733
734 Definition MVP_uc_Q := (fun n p => ProjT1 (MVP_uc n p)).
735
736 Add Parametric Morphism n : (@MVP_uc_Q n)
737 with signature (@st_eq _) ==> (@msp_eq _) as MVP_uc_Q_wd.
738 Proof.
739 induction n.
740 simpl.
741 unfold MVP_uc_Q.
742 simpl.
743 intros. apply Qball_0,H.
744 intros x y Hxy.
745 apply ucEq_equiv. intro a.
746 apply IHn.
747 rewrite -> Hxy.
748 reflexivity.
749 Qed.
750
751 Fixpoint n_Cap X Y (plX : PrelengthSpace X) n : Complete (n_UniformlyContinuousFunction X Y n) -->
752 n_UniformlyContinuousFunction (Complete X) (Complete Y) n :=
753 match n return Complete (n_UniformlyContinuousFunction X Y n) -->
754 n_UniformlyContinuousFunction (Complete X) (Complete Y) n with
755 | O => uc_id _
756 | (S n') => (uc_compose_uc _ _ _ (@n_Cap X Y plX n')) ∘ (@Cap X _ plX)
757 end.
758
759 (** A [Cmap] for an n parameter function. *)
760 Definition n_Cmap X Y (plX : PrelengthSpace X) n : n_UniformlyContinuousFunction X Y n -->
761 n_UniformlyContinuousFunction (Complete X) (Complete Y) n :=
762 (@n_Cap X Y plX n) ∘ (@Cunit _).
763
764 Add Parametric Morphism X Y plX n : (@n_Cap X Y plX n)
765 with signature (@msp_eq _) ==> (@msp_eq _) as n_Cap_wd.
766 Proof.
767 induction n.
768 simpl.
769 auto.
770 intros x y Hxy.
771 apply ucEq_equiv. intro z.
772 apply IHn.
773 apply Cap_wd; auto.
774 reflexivity.
775 Qed.
776
777 Add Parametric Morphism X Y plX n : (@n_Cmap X Y plX n)
778 with signature (@msp_eq _) ==> (@msp_eq _) as n_Cmap_wd.
779 Proof.
780 intros x y Hxy.
781 unfold n_Cmap.
782 simpl.
783 rewrite -> Hxy.
784 reflexivity.
785 Qed.
786
787 (** Multivariable polynomials on the unit hyper interval can be applied to real numbers *)
788 Definition MVP_uc_fun n (p:MultivariatePolynomial _ n) :
789 n_UniformlyContinuousFunction CR CR n :=
790 n_Cmap _ QPrelengthSpace n (MVP_uc_Q n p).
791
792 Add Parametric Morphism n : (@MVP_uc_fun n)
793 with signature (@st_eq _) ==> (@msp_eq _) as MVP_uc_fun_wd.
794 Proof.
795 intros x y Hxy.
796 unfold MVP_uc_fun.
797 rewrite -> Hxy.
798 reflexivity.
799 Qed.
800
801 Section MVP_correct.
802
803 (** Correctness lemmas for [MVP_uc_fun]. *)
804 Lemma MVP_uc_fun_sub_Q : forall n (p:MultivariatePolynomial _ (S n)) x,
805 0 <= x -> x <= 1 ->
806 msp_eq (MVP_uc_fun (S n) p ('x)%CR) (MVP_uc_fun n (p!(MVP_C_ _ _ x))).
807 Proof.
808 intros n p x Hx0 Hx1.
809 unfold MVP_uc_fun.
810 apply: n_Cap_wd.
811 intros e1 e2.
812 simpl.
813 unfold Cap_raw.
814 simpl.
815 rewrite Qplus_0_r.
816 change (ball (proj1_sig e1 + proj1_sig e2) (MVP_uc_Q n p ! (MVP_C_ Q_as_CRing n (Qmax 0 (Qmin 1 x))))
817 (MVP_uc_Q n p ! (MVP_C_ Q_as_CRing n x))).
818 rewrite -> Qle_min_r in Hx1.
819 rewrite -> Hx1.
820 rewrite -> Qle_max_r in Hx0.
821 rewrite -> Hx0.
822 apply ball_refl.
823 apply (Qpos_nonneg (e1+e2)).
824 Qed.
825
826 Lemma MVP_CR_apply_prf
827 : forall n (morph : MultivariatePolynomial CRasCRing n ->
828 n_Function (msp_as_RSetoid CR) (msp_as_RSetoid CR) n)
829 (morph_prf : forall x1 x2 : MultivariatePolynomial CRasCRing n,
830 x1 [=] x2 -> morph x1 [=] morph x2)
831 p (x y : CR),
832 msp_eq x y -> st_eq (morph (p!(MVP_C_ CRasCRing n x)))
833 (morph (p!(MVP_C_ CRasCRing n y))).
834 Proof.
835 intros.
836 apply morph_prf.
837 apply cpoly_apply_wd. reflexivity.
838 apply csf_wd. apply H.
839 Qed.
840
841 Lemma MVP_CR_apply_prf_2 :
842 forall n (morph : MultivariatePolynomial CRasCRing n ->
843 n_Function (msp_as_RSetoid CR) (msp_as_RSetoid CR) n)
844 (morph_prf : forall x1 x2 : MultivariatePolynomial CRasCRing n,
845 x1 [=] x2 -> morph x1 [=] morph x2)
846 (p1 p2 : cpoly_cring (MultivariatePolynomial CRasCRing n)),
847 p1 [=] p2 ->
848 extEq (n_Function (msp_as_RSetoid CR) (msp_as_RSetoid CR) n)
849 (fun x : RegularFunction Qball => morph p1 ! (MVP_C_ CRasCRing n x))
850 (fun x : RegularFunction Qball => morph p2 ! (MVP_C_ CRasCRing n x)).
851 Proof.
852 intros. intro x.
853 simpl.
854 apply morph_prf, cpoly_apply_wd.
855 exact H.
856 apply csf_wd. reflexivity.
857 Qed.
858
859 (* The induction couples both the apply function
860 and the proof that it is a morphism. *)
861 Fixpoint MVP_CR_apply (n : nat)
862 : extSetoid (MultivariatePolynomial CRasCRing n)
863 (n_Function (msp_as_RSetoid CR) (msp_as_RSetoid CR) n).
864 Proof.
865 destruct n as [|n'].
866 - exact id.
867 - exact (Build_Morphism
868 (MultivariatePolynomial CRasCRing (S n'))
869 (n_Function (msp_as_RSetoid CR) (msp_as_RSetoid CR) (S n'))
870 (fun p => Build_Morphism
871 _ _ (fun x => (MVP_CR_apply n') (p!(MVP_C_ CRasCRing n' x)))
872 (MVP_CR_apply_prf n' (MVP_CR_apply n') (Morphism_prf (MVP_CR_apply n')) p))
873 (fun p1 p2 H => MVP_CR_apply_prf_2 n' (MVP_CR_apply n') (Morphism_prf (MVP_CR_apply n')) p1 p2 H)).
874 Defined.
875
876 Fixpoint MVP_uc_fun_correct_sig_Q n
877 : n_UniformlyContinuousFunction CR CR n
878 -> n_Function (msp_as_RSetoid CR) (msp_as_RSetoid CR) n -> Prop :=
879 match n return n_UniformlyContinuousFunction CR CR n
880 -> n_Function (msp_as_RSetoid CR) (msp_as_RSetoid CR) n -> Prop with
881 | O => fun a b => msp_eq a b
882 | S n' => fun f g => forall x, (0 <= x)%Q -> (x <= 1)%Q -> MVP_uc_fun_correct_sig_Q n' (f ('x)%CR) (g ('x)%CR)
883 end.
884
885 Add Parametric Morphism n :
886 (@MVP_uc_fun_correct_sig_Q n)
887 with signature (@msp_eq _) ==> (@st_eq _) ==> iff as MVP_uc_fun_correct_sig_Q_wd.
888 Proof.
889 induction n; intros x y Hxy a b Hab.
890 change (x==a <-> y==b)%CR.
891 rewrite -> Hxy, Hab.
892 reflexivity.
893 simpl.
894 split; intros H c.
895 apply ucEq_equiv in Hxy.
896 rewrite <- (IHn _ _ (Hxy (' c)%CR) _ _ (Hab ('c)%CR)).
897 auto.
898 apply ucEq_equiv in Hxy.
899 rewrite -> (IHn _ _ (Hxy ('c)%CR) _ _ (Hab ('c)%CR)).
900 auto.
901 Qed.
902
903 Lemma MVP_uc_fun_correct_Q : forall n (p:MultivariatePolynomial Q_as_CRing n),
904 MVP_uc_fun_correct_sig_Q n (MVP_uc_fun n p) (MVP_CR_apply n (MVP_map inject_Q_hom n p)).
905 Proof.
906 induction n; intros p.
907 change ('p=='p)%CR.
908 reflexivity.
909 intros x Hx0 Hx1.
910 change (MVP_uc_fun_correct_sig_Q
911 n (MVP_uc_fun (S n) p ('x)%CR)
912 (MVP_CR_apply n ((MVP_map inject_Q_hom (S n) p)!(MVP_C_ CRasCRing _ ('x)%CR)))).
913 eapply MVP_uc_fun_correct_sig_Q_wd;[apply MVP_uc_fun_sub_Q; auto| |apply IHn].
914 apply Morphism_prf.
915 simpl.
916 setoid_replace (MVP_C_ CRasCRing n (' x)%CR) with ((MVP_map inject_Q_hom n) (MVP_C_ Q_as_CRing n x)).
917 symmetry.
918 apply cpoly_map_apply.
919 clear - n.
920 induction n.
921 reflexivity.
922 simpl.
923 refine (csf_wd _ _ _ _ _ _).
924 apply IHn.
925 Qed.
926
927 Fixpoint MVP_uc_fun_close_sig n e
928 : n_UniformlyContinuousFunction CR CR n
929 -> n_Function (msp_as_RSetoid CR) (msp_as_RSetoid CR) n -> Prop :=
930 match n return n_UniformlyContinuousFunction CR CR n -> n_Function (msp_as_RSetoid CR) (msp_as_RSetoid CR) n -> Prop with
931 | O => fun a b => ball e a b
932 | S n' => fun f g => forall x, (0 <= x)%CR -> (x <= 1)%CR -> MVP_uc_fun_close_sig n' e (f x) (g x)
933 end.
934
935 Add Parametric Morphism n :
936 (@MVP_uc_fun_close_sig n)
937 with signature Qeq ==> (@msp_eq _) ==> (@st_eq _) ==> iff as MVP_uc_fun_close_sig_wd.
938 Proof.
939 induction n; intros e1 e2 He x y Hxy a b Hab.
940 change (ball e1 x a <-> ball e2 y b).
941 rewrite -> He, Hxy, Hab.
942 reflexivity.
943 simpl.
944 split; intros H c.
945 apply ucEq_equiv in Hxy.
946 rewrite <- (IHn _ _ He _ _ (Hxy c) _ _ (Hab c)).
947 auto.
948 apply ucEq_equiv in Hxy.
949 rewrite -> (IHn _ _ He _ _ (Hxy c) _ _ (Hab c)).
950 auto.
951 Qed.
952
953 Lemma MVP_uc_fun_close_weaken : forall n (e1 e2:Qpos) f g, (proj1_sig e1 <= proj1_sig e2) ->
954 MVP_uc_fun_close_sig n (proj1_sig e1) f g ->
955 MVP_uc_fun_close_sig n (proj1_sig e2) f g.
956 Proof.
957 induction n; intros e1 e2 f g He H.
958 eapply ball_weak_le.
959 apply He.
960 apply H.
961 intros x Hx0 Hx1.
962 eapply IHn.
963 apply He.
964 apply H; auto.
965 Qed.
966
967 Fixpoint n_Function_ball01 n e : n_Function (msp_as_RSetoid CR) (msp_as_RSetoid CR) n
968 -> n_Function (msp_as_RSetoid CR) (msp_as_RSetoid CR) n -> Prop :=
969 match n return n_Function (msp_as_RSetoid CR) (msp_as_RSetoid CR) n
970 -> n_Function (msp_as_RSetoid CR) (msp_as_RSetoid CR) n -> Prop with
971 | O => ball e
972 | S n' => fun f g => forall x, (0 <= x)%CR -> (x <= 1)%CR -> n_Function_ball01 n' e (f x) (g x)
973 end.
974
975 Add Parametric Morphism n :
976 (@n_Function_ball01 n) with signature Qeq ==> (@st_eq _) ==> (@st_eq _) ==> iff as n_Function_ball01_wd.
977 induction n; intros e1 e2 He x y Hxy a b Hab.
978 Proof.
979 change (ball e1 x a <-> ball e2 y b).
980 rewrite -> He, Hxy, Hab.
981 reflexivity.
982 simpl.
983 split; intros H c.
984 rewrite <- (IHn _ _ He _ _ (Hxy c) _ _ (Hab c)).
985 auto.
986 rewrite -> (IHn _ _ He _ _ (Hxy c) _ _ (Hab c)).
987 auto.
988 Qed.
989
990
991 Lemma MVP_uc_fun_close_left : forall n (e1 e2:Qpos) f1 f2 g,
992 ball (proj1_sig e1) f1 f2 ->
993 MVP_uc_fun_close_sig n (proj1_sig e2) f2 g ->
994 MVP_uc_fun_close_sig n (proj1_sig e1+proj1_sig e2) f1 g.
995 Proof.
996 induction n; intros e1 e2 f g1 g2 H0 H1.
997 eapply ball_triangle.
998 apply H0.
999 apply H1.
1000 intros x Hx0 Hx1.
1001 eapply IHn.
1002 apply H0; auto.
1003 apply H1; auto.
1004 Qed.
1005
1006 Lemma MVP_uc_fun_close_right : forall n (e1 e2:Qpos) f g1 g2,
1007 MVP_uc_fun_close_sig n (proj1_sig e1) f g1 ->
1008 n_Function_ball01 n (proj1_sig e2) g1 g2 ->
1009 MVP_uc_fun_close_sig n (proj1_sig e1+proj1_sig e2) f g2.
1010 Proof.
1011 induction n; intros e1 e2 f g1 g2 H0 H1.
1012 eapply ball_triangle.
1013 apply H0.
1014 apply H1.
1015 intros x Hx0 Hx1.
1016 eapply IHn.
1017 apply H0; auto.
1018 apply H1; auto.
1019 Qed.
1020
1021 Lemma n_Function_ball01_sym : forall n e f g,
1022 (n_Function_ball01 n e f g) ->
1023 (n_Function_ball01 n e g f).
1024 Proof.
1025 induction n.
1026 apply ball_sym.
1027 intros e f g H x Hx0 Hx1.
1028 apply IHn.
1029 apply H; auto.
1030 Qed.
1031
1032 Lemma n_Function_ball01_triangle : forall n e1 e2 f g h,
1033 (n_Function_ball01 n e1 f g) ->
1034 (n_Function_ball01 n e2 g h) ->
1035 (n_Function_ball01 n (e1+e2)%Q f h).
1036 Proof.
1037 induction n.
1038 apply ball_triangle.
1039 intros e1 e2 f g h H0 H1 x Hx0 Hx1.
1040 eapply IHn.
1041 apply H0; auto.
1042 apply H1; auto.
1043 Qed.
1044
1045 Lemma n_Function_ball01_plus : forall n e p1 p2 p3,
1046 (n_Function_ball01 n e (MVP_CR_apply n p2) (MVP_CR_apply n p3)) ->
1047 (n_Function_ball01 n e (MVP_CR_apply n (p1[+]p2)) (MVP_CR_apply n (p1[+]p3))).
1048 Proof.
1049 induction n; intros e p1 p2 p3 H.
1050 intros d1 d2.
1051 simpl.
1052 unfold Qball.
1053 unfold Cap_raw.
1054 simpl.
1055 replace RHS with ((approximate p1 ((1 # 2) * d1)%Qpos - approximate p1 ((1 # 2) * d2)%Qpos)
1056 +(approximate p2 ((1 # 2) * d1)%Qpos - approximate p3 ((1 # 2) * d2)%Qpos))
1057 by simpl; ring.
1058 replace LHS with (((1 # 2) * proj1_sig d1 + (1 # 2) * proj1_sig d2)%Q
1059 +(proj1_sig ((1 # 2) * d1)%Qpos + e
1060 + proj1_sig ((1 # 2) * d2)%Qpos))%Q
1061 by simpl; ring.
1062 (*
1063 replace LHS with (proj1_sig ((1 # 2) * d1 + (1 # 2) * d2)%Qpos
1064 +proj1_sig ((1 # 2) * d1 + e + (1 # 2) * d2)%Qpos)
1065 by simpl; ring. *)
1066 apply AbsSmall_plus.
1067 change (ball (proj1_sig ((1 # 2) * d1 + (1 # 2) * d2)%Qpos)
1068 (approximate p1 ((1 # 2) * d1)%Qpos) (approximate p1 ((1 # 2) * d2)%Qpos)).
1069 generalize ((1#2)*d1)%Qpos ((1#2)*d2)%Qpos.
1070 change (regFunEq p1 p1).
1071 apply regFunEq_equiv. reflexivity.
1072 generalize ((1#2)*d1)%Qpos ((1#2)*d2)%Qpos.
1073 apply H.
1074 intros x Hx0 Hx1.
1075 change (n_Function_ball01 n e (MVP_CR_apply _ (p1[+]p2) ! (MVP_C_ CRasCRing _ x))
1076 (MVP_CR_apply _ (p1[+]p3) ! (MVP_C_ CRasCRing _ x))).
1077 eapply n_Function_ball01_wd;[| | |apply IHn].
1078 reflexivity.
1079 apply Morphism_prf.
1080 apply plus_apply.
1081 apply Morphism_prf.
1082 apply plus_apply.
1083 apply: H; auto.
1084 Qed.
1085
1086 Lemma n_Function_ball01_mult_C : forall n (e:Qpos) c q1 q2,
1087 (0 <= c)%CR -> (c <= 1)%CR ->
1088 (n_Function_ball01 n (proj1_sig e) (MVP_CR_apply n q1) (MVP_CR_apply n q2)) ->
1089 (n_Function_ball01 n (proj1_sig e) (MVP_CR_apply n ((MVP_C_ CRasCRing _ c)[*]q1))
1090 (MVP_CR_apply n ((MVP_C_ CRasCRing _ c)[*]q2))).
1091 Proof.
1092 induction n; intros e c q1 q2 Hc0 Hc1 H.
1093 change (ball (proj1_sig e) (c * q1)%CR (c * q2)%CR).
1094 rewrite <- CRAbsSmall_ball.
1095 (* change (AbsSmall (' proj1_sig e)%CR (c[*]q1[-]c[*]q2)). *)
1096 change (@cg_minus CRasCOrdField (c * q1)%CR (c * q2)%CR)
1097 with (c*q1 - c*q2)%CR.
1098 setoid_replace (c*q1 - c*q2)%CR
1099 with (c * (q1 - q2))%CR by ring.
1100 (* rstepr (c[*](q1[-]q2)). *)
1101 apply AbsSmall_leEq_trans with (c * 'proj1_sig e)%CR.
1102 rewrite <- (CRmult_1_l ('proj1_sig e)%CR) at 2.
1103 apply mult_resp_leEq_rht; auto.
1104 simpl. apply CRle_Qle, Qpos_nonneg.
1105 apply mult_resp_AbsSmall; auto.
1106 apply (CRAbsSmall_ball q1 q2).
1107 exact H.
1108 intros x Hx0 Hx1.
1109 change (n_Function_ball01 n (proj1_sig e) (MVP_CR_apply _ (MVP_C_ CRasCRing _ c[*]q1) ! (MVP_C_ CRasCRing _ x))
1110 (MVP_CR_apply _ (MVP_C_ CRasCRing _ c[*]q2) ! (MVP_C_ CRasCRing _ x))).
1111 eapply n_Function_ball01_wd.
1112 reflexivity.
1113 apply Morphism_prf.
1114 eapply eq_transitive.
1115 apply mult_apply.
1116 apply mult_wdl.
1117 simpl.
1118 apply c_apply.
1119 apply Morphism_prf.
1120 eapply eq_transitive.
1121 apply mult_apply.
1122 apply mult_wdl.
1123 simpl.
1124 apply c_apply.
1125 apply IHn; auto.
1126 apply: H; auto.
1127 Qed.
1128
1129 Fixpoint MVP_is_Bound01 n (M:CR) : MultivariatePolynomial CRasCRing n -> Prop :=
1130 match n return MultivariatePolynomial CRasCRing n -> Prop with
1131 | O => fun a => @AbsSmall CRasCOrdField M a
1132 | S n' => fun p => forall x, (0 <= x)%CR -> (x <= 1)%CR ->
1133 MVP_is_Bound01 n' M (p ! (MVP_C_ CRasCRing _ x))
1134 end.
1135
1136 Add Parametric Morphism n :
1137 (@MVP_is_Bound01 n)
1138 with signature (@msp_eq _) ==> (@st_eq _) ==> iff as MVP_is_Bound01_wd.
1139 Proof.
1140 induction n; intros x y Hxy a b Hab.
1141 simpl.
1142 rewrite -> Hxy.
1143 rewrite -> Hab.
1144 reflexivity.
1145 split; intros H c Hc0 Hc1.
1146 change (MVP_is_Bound01 n y b ! (MVP_C_ CRasCRing n c)).
1147 rewrite <- (IHn _ _ Hxy (a!(MVP_C_ CRasCRing n c)) (b!(MVP_C_ CRasCRing n c))).
1148 apply H; auto.
1149 rewrite -> Hab.
1150 reflexivity.
1151 change (MVP_is_Bound01 n x a ! (MVP_C_ CRasCRing n c)).
1152 rewrite <- (fun A => IHn y x A (b!(MVP_C_ CRasCRing n c)) (a!(MVP_C_ CRasCRing n c))).
1153 apply H; auto.
1154 symmetry; auto.
1155 rewrite -> Hab.
1156 reflexivity.
1157 Qed.
1158
1159 Lemma MVP_is_Bound01_plus : forall n M N p q,
1160 MVP_is_Bound01 n M p -> MVP_is_Bound01 n N q ->
1161 MVP_is_Bound01 n (M+N)%CR (p[+]q).
1162 Proof.
1163 induction n; intros M N p q Hp Hq.
1164 apply: AbsSmall_plus; auto.
1165 simpl.
1166 intros x Hx0 Hx1.
1167 rewrite -> plus_apply.
1168 auto.
1169 Qed.
1170
1171 Lemma MVP_is_Bound01_mult01 : forall n M p x,
1172 (0 <= x)%CR -> (x <= 1)%CR ->
1173 MVP_is_Bound01 n M p ->
1174 MVP_is_Bound01 n M (MVP_C_ CRasCRing n x[*]p).
1175 Proof.
1176 induction n; intros M p x Hx0 Hx1 H.
1177 simpl.
1178 change (msp_car CR) in p.
1179 eapply AbsSmall_leEq_trans;[|apply mult_resp_AbsSmall;[|apply H]]; auto.
1180 rewrite <- (CRmult_1_l M) at 2.
1181 apply mult_resp_leEq_rht; auto.
1182 simpl in H. unfold AbsSmall in H.
1183 rewrite <- CRabs_AbsSmall in H.
1184 eapply leEq_transitive;[|apply H].
1185 apply CRabs_nonneg.
1186 simpl.
1187 intros y Hy0 Hy1.
1188 rewrite -> mult_apply.
1189 rewrite -> c_apply.
1190 apply IHn; auto.
1191 Qed.
1192
1193 Lemma n_Function_ball01_mult : forall n e x y p M,
1194 MVP_is_Bound01 n ('M)%CR p ->
1195 ball_ex (Qscale_modulus M e) x y ->
1196 n_Function_ball01 n (proj1_sig e)
1197 (MVP_CR_apply n (MVP_C_ CRasCRing n x[*]p))
1198 (MVP_CR_apply n (MVP_C_ CRasCRing n y[*]p)).
1199 Proof.
1200 induction n; intros e x y p b Hb Hxy.
1201 change (ball (proj1_sig e) (x*p) (y*p))%CR.
1202 rewrite <- CRAbsSmall_ball.
1203 change (@cg_minus CRasCOrdField (x * p)%CR (y * p)%CR)
1204 with (x*p-y*p)%CR.
1205 setoid_replace (x*p-y*p)%CR with (p*(x-y))%CR by ring.
1206 simpl in Hb.
1207 case_eq (Qscale_modulus b e).
1208 intros q Hq.
1209 apply AbsSmall_leEq_trans with (CRabs p * 'proj1_sig q)%CR.
1210 destruct b as [[|nb|nb] db].
1211 discriminate Hq.
1212 simpl in Hq.
1213 injection Hq; clear Hq; intros Hq; rewrite <- Hq.
1214 assert (' proj1_sig ((db # nb) * e)%Qpos >< 0)%CR as Z.
1215 { apply Qap_CRap, Qpos_nonzero. }
1216 apply shift_mult_leEq with Z.
1217 apply: CRlt_Qlt; auto with *.
1218 unfold AbsSmall in Hb.
1219 rewrite <- CRabs_AbsSmall in Hb.
1220 stepr ('(nb#db))%CR; auto.
1221 change ((' (nb # db)) == (' proj1_sig e)%CR * CRinvT (' proj1_sig ((db # nb) * e)%Qpos) Z)%CR.
1222 rewrite -> CRinv_Qinv.
1223 rewrite -> CRmult_Qmult.
1224 rewrite -> CReq_Qeq.
1225 simpl.
1226 rewrite -> Qinv_mult_distr.
1227 replace RHS with ((/(db#nb) * proj1_sig e) * /proj1_sig e) by simpl; ring.
1228 change (nb#db == ((nb#db)*proj1_sig e/proj1_sig e)).
1229 rewrite -> Qdiv_mult_l.
1230 reflexivity.
1231 apply Qpos_nonzero.
1232 elim (Qle_not_lt 0 (Zneg nb # db)); auto with *.
1233 rewrite <- CRle_Qle.
1234 eapply AbsSmall_nonneg.
1235 apply Hb.
1236 cut (Not (Not (@AbsSmall CRasCOrdField (CRabs p * (' proj1_sig q))%CR (p * (x - y))%CR))).
1237 { unfold Not, AbsSmall.
1238 repeat rewrite -> leEq_def.
1239 unfold Not; tauto. }
1240 generalize (leEq_or_leEq CRasCOrdField [0] p).
1241 unfold Not.
1242 intros H abs.
1243 contradict H; intro H. contradict abs.
1244 destruct H as [Hp|Hp].
1245 - rewrite -> CRabs_pos; auto.
1246 apply mult_resp_AbsSmall;auto.
1247 rewrite Hq in Hxy.
1248 apply (CRAbsSmall_ball x y).
1249 auto.
1250 - rewrite -> CRabs_neg; auto.
1251 setoid_replace (p * (x - y))%CR with (-p * (y - x))%CR by ring.
1252 apply mult_resp_AbsSmall.
1253 rewrite <- CRopp_0.
1254 apply inv_resp_leEq.
1255 auto.
1256 rewrite Hq in Hxy.
1257 apply (CRAbsSmall_ball y x).
1258 apply ball_sym.
1259 apply Hxy.
1260 - intros Hq.
1261 destruct b as [[|nb|nb] db]; try discriminate Hq.
1262 setoid_replace p with 0%CR.
1263 rewrite CRmult_comm, CRmult_0_r.
1264 apply zero_AbsSmall.
1265 simpl.
1266 rewrite -> CRle_Qle; auto with *.
1267 destruct Hb as [Hb0 Hb1].
1268 apply CRle_antisym. split.
1269 stepr ((' (0 # db)))%CR; auto.
1270 change ('(0#db)==0)%CR.
1271 rewrite -> CReq_Qeq.
1272 unfold Qeq; reflexivity.
1273 stepl (-(' (0 # db)))%CR; auto.
1274 rewrite -> CRopp_Qopp.
1275 change ('(0#db)==0)%CR.
1276 rewrite -> CReq_Qeq.
1277 unfold Qeq; reflexivity.
1278 - simpl.
1279 intros a Ha0 Ha1.
1280 eapply n_Function_ball01_wd.
1281 reflexivity.
1282 apply Morphism_prf.
1283 eapply eq_transitive.
1284 apply mult_apply.
1285 apply csbf_wd.
1286 apply c_apply.
1287 reflexivity.
1288 apply Morphism_prf.
1289 eapply eq_transitive.
1290 apply mult_apply.
1291 apply csbf_wd.
1292 apply c_apply.
1293 reflexivity.
1294 apply: IHn; auto.
1295 Qed.
1296
1297 Fixpoint MVP_poor_Bound01 n : MultivariatePolynomial Q_as_CRing n -> Q :=
1298 match n return MultivariatePolynomial Q_as_CRing n -> Q with
1299 | O => Qabs
1300 | S n' => fix MVP_poor_Bound01_H p : Q :=
1301 match p with
1302 | cpoly_zero _ => 0
1303 | cpoly_linear _ s p' => MVP_poor_Bound01 n' s + MVP_poor_Bound01_H p'
1304 end
1305 end.
1306
1307 Lemma MVP_poor_Bound01_zero : forall n, MVP_poor_Bound01 n ([0])==0.
1308 Proof.
1309 induction n.
1310 reflexivity.
1311 reflexivity.
1312 Qed.
1313
1314 Add Parametric Morphism n :
1315 (@MVP_poor_Bound01 n) with signature (@st_eq _) ==> Qeq as MVP_poor_Bound01_wd.
1316 Proof.
1317 induction n.
1318 intros x y Hxy.
1319 simpl in *.
1320 rewrite -> Hxy.
1321 reflexivity.
1322 induction x.
1323 induction y.
1324 reflexivity.
1325 intros [H0 H1].
1326 simpl in *.
1327 change 0 with (0+0).
1328 apply Qplus_comp.
1329 rewrite <- (MVP_poor_Bound01_zero n).
1330 apply IHn.
1331 symmetry; auto.
1332 apply IHy.
1333 apply H1.
1334 intros [|t y] [H0 H1].
1335 simpl.
1336 change 0 with (0+0).
1337 apply Qplus_comp.
1338 rewrite <- (MVP_poor_Bound01_zero n).
1339 apply IHn.
1340 auto.
1341 change (MVP_poor_Bound01 (S n) x==0).
1342 rewrite <- (MVP_poor_Bound01_zero (S n)).
1343 apply IHx.
1344 apply eq_symmetric.
1345 apply H1.
1346 simpl.
1347 apply Qplus_comp.
1348 apply IHn.
1349 auto.
1350 apply IHx.
1351 auto.
1352 Qed.
1353
1354 Lemma MVP_poor_is_Bound01 : forall n p,
1355 MVP_is_Bound01 n ('(MVP_poor_Bound01 n p))%CR (MVP_map inject_Q_hom n p).
1356 Proof.
1357 induction n.
1358 split.
1359 change (-('Qabs p)<='p)%CR.
1360 rewrite -> CRopp_Qopp.
1361 rewrite -> CRle_Qle.
1362 simpl in p.
1363 replace RHS with (- (- p)) by simpl; ring.
1364 apply Qopp_le_compat.
1365 rewrite <- Qabs_opp.
1366 apply Qle_Qabs.
1367 change ('p<=('Qabs p))%CR.
1368 rewrite -> CRle_Qle.
1369 apply Qle_Qabs.
1370 simpl.
1371 induction p; intros x Hx0 Hx1.
1372 change (MVP_is_Bound01 n 0%CR ([0])).
1373 clear - n.
1374 induction n.
1375 apply AbsSmall_reflexive.
1376 apply leEq_reflexive.
1377 intros y _ _.
1378 apply IHn.
1379 change (MVP_is_Bound01 n (' (MVP_poor_Bound01 n s + (fix MVP_poor_Bound01_H (p0 : cpoly
1380 (MultivariatePolynomial Q_as_CRing n)) : Q := match p0 with | cpoly_zero _ => 0
1381 | cpoly_linear _ s0 p' => (MVP_poor_Bound01 n s0 + MVP_poor_Bound01_H p')%Q end) p)%Q)%CR
1382 (MVP_map inject_Q_hom n s[+]MVP_C_ CRasCRing n x[*](cpoly_map (MVP_map inject_Q_hom n) p) ! (MVP_C_ CRasCRing n x))).
1383 rewrite <- CRplus_Qplus.
1384 apply MVP_is_Bound01_plus.
1385 apply IHn.
1386 apply MVP_is_Bound01_mult01; auto.
1387 Qed.
1388
1389 Lemma MVP_CR_apply_cont : forall n (e : Qpos) (p:MultivariatePolynomial Q_as_CRing (S n)),
1390 {d | forall x y,
1391 (0 <= x)%CR -> (x <= 1)%CR ->
1392 (0 <= 'y)%CR -> ('y <= 1)%CR ->
1393 ball_ex d x ('y)%CR ->
1394 n_Function_ball01 n (proj1_sig e) (MVP_CR_apply _ (MVP_map inject_Q_hom _ p) x)
1395 (MVP_CR_apply _ (MVP_map inject_Q_hom _ p) ('y)%CR)}.
1396 Proof.
1397 intros n e p.
1398 revert e.
1399 induction p; intros e.
1400 exists QposInfinity.
1401 intros x y _ _ _ _ _.
1402 change (n_Function_ball01 n (proj1_sig e) (MVP_CR_apply n [0]) (MVP_CR_apply n [0])).
1403 generalize (MVP_CR_apply n [0]).
1404 induction n.
1405 intros. apply ball_refl, Qpos_nonneg.
1406 intros s a _ _.
1407 apply IHn.
1408 simpl.
1409 destruct (IHp ((1#2)*e)%Qpos) as [d0 Hd0].
1410 set (b:=MVP_poor_Bound01 (S n) p).
1411 set (d1:=(Qscale_modulus b ((1 # 2) * e))).
1412 exists (QposInf_min d0 d1).
1413 intros x y Hx0 Hx1 Hy0 Hy1 Hxy.
1414 change (n_Function_ball01 n (proj1_sig e) (MVP_CR_apply n
1415 ((MVP_map inject_Q_hom n s)[+](MVP_C_ CRasCRing n x)[*]((cpoly_map (MVP_map inject_Q_hom n) p))
1416 ! (MVP_C_ CRasCRing n x))) (MVP_CR_apply n
1417 ((MVP_map inject_Q_hom n s)[+](MVP_C_ CRasCRing n ('y)%CR)[*]((cpoly_map (MVP_map inject_Q_hom n) p))
1418 ! (MVP_C_ CRasCRing n (inject_Q_hom y)%CR)))).
1419 apply n_Function_ball01_plus.
1420 setoid_replace (proj1_sig e)
1421 with (proj1_sig ((1#2)*e + (1#2)*e)%Qpos) by (simpl; ring).
1422 apply n_Function_ball01_triangle with (MVP_CR_apply n (MVP_C_ CRasCRing n x[*]
1423 (cpoly_map (MVP_map inject_Q_hom n) p) ! (MVP_C_ CRasCRing n (inject_Q_hom y)%CR))).
1424 apply n_Function_ball01_mult_C; auto.
1425 change (n_Function_ball01 n ((1 # 2) * proj1_sig e) (MVP_CR_apply (S n) (MVP_map inject_Q_hom (S n) p) x)
1426 (MVP_CR_apply (S n) (MVP_map inject_Q_hom (S n) p) ('y)%CR)).
1427 apply Hd0; auto with *.
1428 eapply ball_ex_weak_le;[|apply Hxy].
1429 apply QposInf_min_lb_l.
1430 eapply n_Function_ball01_wd.
1431 reflexivity.
1432 apply Morphism_prf.
1433 apply mult_wdr.
1434 eapply eq_transitive.
1435 apply csbf_wd;[apply eq_reflexive|].
1436 symmetry.
1437 apply MVP_map_C_.
1438 symmetry.
1439 apply cpoly_map_apply.
1440 apply Morphism_prf.
1441 apply mult_wdr.
1442 eapply eq_transitive.
1443 apply csbf_wd;[apply eq_reflexive|].
1444 symmetry.
1445 apply MVP_map_C_.
1446 symmetry.
1447 apply cpoly_map_apply.
1448 apply n_Function_ball01_mult with b.
1449 assert (Z:=MVP_poor_is_Bound01 (S n) p _ Hy0 Hy1).
1450 unfold b.
1451 change (MVP_is_Bound01 n (' MVP_poor_Bound01 (S n) p)%CR
1452 (MVP_map inject_Q_hom (S n) p) ! (MVP_C_ CRasCRing n (' y)%CR)) in Z.
1453 eapply MVP_is_Bound01_wd;[| |apply Z].
1454 reflexivity.
1455 simpl.
1456 change (MVP_map inject_Q_hom n p ! (MVP_C_ Q_as_CRing n y)[=] (cpoly_map (MVP_map inject_Q_hom n) p)
1457 ! (MVP_C_ CRasCRing n (inject_Q_hom y)%CR)).
1458 rewrite <- MVP_map_C_.
1459 apply cpoly_map_apply.
1460 eapply ball_ex_weak_le;[|apply Hxy].
1461 apply QposInf_min_lb_r.
1462 Qed.
1463
1464 Lemma MVP_uc_fun_close : forall n (e:Qpos) (p:MultivariatePolynomial Q_as_CRing n),
1465 MVP_uc_fun_close_sig n (proj1_sig e) (MVP_uc_fun n p) (MVP_CR_apply n (MVP_map inject_Q_hom n p)).
1466 Proof.
1467 induction n; intros e p.
1468 apply ball_refl, Qpos_nonneg.
1469 intros x Hx0 Hx1.
1470 change (MVP_uc_fun_close_sig n (proj1_sig e) (MVP_uc_fun (S n) p x)
1471 (MVP_CR_apply (S n) (MVP_map inject_Q_hom (S n) p) x)).
1472 setoid_replace (proj1_sig e)
1473 with (proj1_sig ((((1#3)*e)+(1#3)*e)+(1#3)*e)%Qpos) by (simpl; ring).
1474 set (e3:=((1#3)*e)%Qpos).
1475 destruct (MVP_CR_apply_cont e3 p) as [d0 Hd].
1476 set (d1:=mu (MVP_uc_fun (S n) p) e3).
1477 set (d:=QposInf_min d0 d1).
1478 set (y:=Qclamp01 (approximate x d)).
1479 destruct (Qclamp01_clamped (approximate x d)) as [Hy0 Hy1].
1480 rewrite <- CRle_Qle in Hy0.
1481 rewrite <- CRle_Qle in Hy1.
1482 pose proof (Hd _ _ Hx0 Hx1 Hy0 Hy1) as Hd0.
1483 assert (ball_ex d x (' Qclamp01 (approximate x d))%CR) as Z.
1484 { clear - Hx0 Hx1.
1485 destruct d as [d|];[|constructor].
1486 change (ball (proj1_sig d) x (' Qclamp01 (approximate x d))%CR).
1487 rewrite <- CRAbsSmall_ball.
1488 pose proof (ball_approx_r x d) as Z.
1489 rewrite <- CRAbsSmall_ball in Z.
1490 revert Z.
1491 generalize (approximate x d).
1492 clear - Hx0 Hx1.
1493 intros s [Z0 Z1].
1494 simpl.
1495 split.
1496 apply Qmax_case.
1497 intros _.
1498 apply leEq_transitive with 0%CR.
1499 rewrite <- CRopp_0.
1500 apply inv_resp_leEq.
1501 change (0<='proj1_sig d)%CR.
1502 rewrite -> CRle_Qle.
1503 apply Qpos_nonneg.
1504 change (@cg_minus CRasCGroup x (inject_Q_CR 0)) with (x-0)%CR.
1505 rewrite CRopp_0, CRplus_0_r.
1506 exact Hx0.
1507 intros H.
1508 apply (CRle_trans Z0).
1509 apply (minus_resp_leEq_rht CRasCOrdField (Cunit s) (' Qmin 1 s)%CR x).
1510 rewrite -> CRle_Qle.
1511 apply Qmin_lb_r.
1512 rewrite -> Qmax_min_distr_r.
1513 apply Qmin_case.
1514 intros _.
1515 apply (@CRle_trans _ (1-1)%CR).
1516 apply (CRplus_le_r x 1%CR (CRopp 1%CR)).
1517 assumption.
1518 rewrite CRplus_opp.
1519 rewrite -> CRle_Qle.
1520 exact (Qpos_nonneg d).
1521 intros H.
1522 refine (CRle_trans _ Z1).
1523 apply (minus_resp_leEq_rht CRasCOrdField _ _ x).
1524 rewrite -> CRle_Qle.
1525 apply Qmax_ub_r. }
1526 eapply MVP_uc_fun_close_right; [|apply n_Function_ball01_sym;apply Hd0].
1527 eapply MVP_uc_fun_close_left.
1528 apply uc_prf.
1529 eapply ball_ex_weak_le;[|apply Z].
1530 apply QposInf_min_lb_r.
1531 rewrite -> CRle_Qle in Hy0.
1532 rewrite -> CRle_Qle in Hy1.
1533 rewrite -> MVP_uc_fun_sub_Q;auto.
1534 eapply MVP_uc_fun_close_sig_wd.
1535 reflexivity.
1536 reflexivity.
1537 simpl.
1538 apply Morphism_prf.
1539 eapply eq_transitive.
1540 apply csbf_wd.
1541 reflexivity.
1542 symmetry.
1543 apply (MVP_map_C_ inject_Q_hom).
1544 symmetry.
1545 change (cpoly_map_fun (MultivariatePolynomial Q_as_CRing n)
1546 (MultivariatePolynomial CRasCRing n) (MVP_map inject_Q_hom n) p)
1547 with (cpoly_map (MVP_map inject_Q_hom n) p).
1548 apply cpoly_map_apply.
1549 apply IHn.
1550 eapply ball_ex_weak_le;[|apply Z].
1551 apply QposInf_min_lb_l.
1552 Qed.
1553
1554 Fixpoint MVP_uc_fun_correct_sig n
1555 : n_UniformlyContinuousFunction CR CR n -> n_Function (msp_as_RSetoid CR) (msp_as_RSetoid CR) n -> Prop :=
1556 match n return n_UniformlyContinuousFunction CR CR n -> n_Function (msp_as_RSetoid CR) (msp_as_RSetoid CR) n -> Prop with
1557 | O => fun a b => msp_eq a b
1558 | S n' => fun f g => forall x, (0 <= x)%CR -> (x <= 1)%CR -> MVP_uc_fun_correct_sig n' (f x) (g x)
1559 end.
1560
1561 (** Finally, the correctness lemma. *)
1562 Lemma MVP_uc_fun_correct : forall n (p:MultivariatePolynomial Q_as_CRing n),
1563 MVP_uc_fun_correct_sig n (MVP_uc_fun n p) (MVP_CR_apply n (MVP_map inject_Q_hom n p)).
1564 Proof.
1565 intros n p.
1566 generalize (fun e => MVP_uc_fun_close n e p).
1567 generalize (MVP_uc_fun n p) (MVP_CR_apply n (MVP_map inject_Q_hom n p)).
1568 clear p.
1569 induction n; intros a b H.
1570 apply ball_eq.
1571 intros. apply (H (exist _ _ H0)).
1572 intros x Hx0 Hx1.
1573 apply IHn.
1574 intros e.
1575 apply H; auto.
1576 Qed.
1577
1578 End MVP_correct.