Debian Codegraph @

Formal_ineqs/taylor/theory/multivariate_taylor.vhl

raw
1 (* ========================================================================== *)
2 (* Formal verification of nonlinear inequalities in HOL Light *)
3 (* *)
4 (* Copyright (c) 2012 Alexey Solovyev *)
5 (* *)
6 (* This file is distributed under the terms of the MIT licence *)
7 (* ========================================================================== *)
8
9 (* -------------------------------------------------------------------------- *)
10 (* Theory of multivariate taylor intervals *)
11 (* Requires SSReflect/HOL Light for translation *)
12 (* See https://github.com/monadius/hol-ssreflect *)
13 (* -------------------------------------------------------------------------- *)
14
15 "needs \"Formal_ineqs/lib/ssrbool.hl\"".
16 "needs \"Formal_ineqs/lib/ssrnat.hl\"".
17 "needs \"Formal_ineqs/taylor/theory/taylor_interval-compiled.hl\"".
18
19 module Multivariate_taylor.
20
21 "open Ssrfun".
22 "open Ssrbool".
23 "open Ssrnat".
24 "open Taylor_interval".
25 "open Interval_arith".
26
27 "prioritize_overload `:real^N`".
28 "prioritize_real()".
29
30 "let IMAGE_DELETE_INJ_COMPAT = prove
31 (`!f s a. (!x. f(x) = f(a) ==> x = a)
32 ==> (IMAGE f (s DELETE a) = (IMAGE f s) DELETE (f a))`,
33 SET_TAC[])".
34
35 "let partial = new_definition `partial i f x = derivative (f o (\t. (x:real^N) + t % basis i)) (&0)`".
36
37 "let all_n = define `(all_n n [] s <=> T) /\ (all_n n (CONS h t) s <=> s n h /\ all_n (SUC n) t s)`".
38
39 "let m_lin_approx = new_definition `m_lin_approx (f:real^N->real) x f_bounds df_bounds_list <=>
40 (lift o f) differentiable at x /\
41 interval_arith (f x) f_bounds /\
42 all_n 1 df_bounds_list (\i int. interval_arith (partial i f x) int)`".
43
44
45
46 Section Misc.
47
48 Lemma f_lift_neg f : `lift o (\x. --f x) = (\x. --(lift o f) x)`.
49 by rewrite -eq_ext !o_THM /= LIFT_NEG. Qed.
50
51 Lemma f_lift_scale f c : `lift o (\x. c * f x) = (\x. c % (lift o f) x)`.
52 by rewrite -eq_ext !o_THM /= LIFT_CMUL. Qed.
53
54 Lemma f_lift_add f g : `lift o (\x. f x + g x) = (\x. (lift o f) x + (lift o g) x)`.
55 by rewrite -eq_ext !o_THM /= LIFT_ADD. Qed.
56
57 Lemma f_lift_sub f g : `lift o (\x. f x - g x) = (\x. (lift o f) x - (lift o g) x)`.
58 by rewrite -eq_ext !o_THM /= LIFT_SUB. Qed.
59
60 Lemma f_binary_drop op f g : `(\t. op (f t) (g t)) o drop = (\x. op (f (drop x)) (g (drop x)))`.
61 by rewrite -eq_ext !o_THM. Qed.
62
63 Lemma f_unary_drop op f : `(\t. op (f t)) o drop = (\x. op (f (drop x)))`.
64 by rewrite -eq_ext !o_THM. Qed.
65
66
67
68 Section MoreFrechet.
69
70 Variables f g : `:real^N -> real^M`.
71 Variables x y : `:real^N`.
72
73 Lemma frechet_compose f g x : `f differentiable at (g x) ==>
74 g differentiable at x ==>
75 frechet_derivative (f o g) (at x) = frechet_derivative f (at (g x)) o frechet_derivative g (at x)`.
76 move => df dg; rewrite EQ_SYM_EQ; apply FRECHET_DERIVATIVE_AT.
77 by apply DIFF_CHAIN_AT; rewrite -!FRECHET_DERIVATIVE_WORKS.
78 Qed.
79
80 Lemma frechet_const z : `frechet_derivative (\x. y) (at z) = (\x. vec 0)`.
81 by rewrite EQ_SYM_EQ; apply FRECHET_DERIVATIVE_AT; rewrite HAS_DERIVATIVE_CONST. Qed.
82
83
84 Lemma frechet_id : `frechet_derivative (\x. x) (at y) = (\x. x)`.
85 by rewrite EQ_SYM_EQ; apply FRECHET_DERIVATIVE_AT; rewrite HAS_DERIVATIVE_ID. Qed.
86
87
88 Lemma frechet_vmul z : `frechet_derivative (\x. drop x % y) (at z) = (\x. drop x % y)`.
89 rewrite EQ_SYM_EQ; apply FRECHET_DERIVATIVE_AT; apply HAS_DERIVATIVE_VMUL_DROP.
90 rewrite HAS_DERIVATIVE_ID.
91 Qed.
92
93
94 Hypothesis df : `f differentiable at x`.
95
96 Lemma frechet_neg : `frechet_derivative (\x. --f x) (at x) = (\y. --frechet_derivative f (at x) y)`.
97 rewrite EQ_SYM_EQ; apply FRECHET_DERIVATIVE_AT; apply HAS_DERIVATIVE_NEG.
98 by rewr ETA_AX; rewrite -FRECHET_DERIVATIVE_WORKS.
99 Qed.
100
101 Lemma frechet_scale c : `frechet_derivative (\x. c % f x) (at x) = (\y. c % frechet_derivative f (at x) y)`.
102 rewrite EQ_SYM_EQ; apply FRECHET_DERIVATIVE_AT; apply HAS_DERIVATIVE_CMUL.
103 by rewr ETA_AX; rewrite -FRECHET_DERIVATIVE_WORKS.
104 Qed.
105
106
107 Hypothesis dg : `g differentiable at x`.
108
109 Lemma frechet_add : `frechet_derivative (\x. f x + g x) (at x) =
110 (\y. frechet_derivative f (at x) y + frechet_derivative g (at x) y)`.
111 rewrite EQ_SYM_EQ; apply FRECHET_DERIVATIVE_AT; apply HAS_DERIVATIVE_ADD.
112 by rewr ETA_AX; rewrite -!FRECHET_DERIVATIVE_WORKS.
113 Qed.
114
115 Lemma frechet_sub : `frechet_derivative (\x. f x - g x) (at x) =
116 (\y. frechet_derivative f (at x) y - frechet_derivative g (at x) y)`.
117 rewrite EQ_SYM_EQ; apply FRECHET_DERIVATIVE_AT; apply HAS_DERIVATIVE_SUB.
118 by rewr ETA_AX; rewrite -!FRECHET_DERIVATIVE_WORKS.
119 Qed.
120
121 End MoreFrechet.
122
123
124 Lemma differentiable_compose_at f g x :
125 `f differentiable at (g x) ==>
126 g differentiable at x ==>
127 (f o g) differentiable at x`.
128 move => df dg; rewrite FRECHET_DERIVATIVE_WORKS.
129 by rewrite frechet_compose //; apply DIFF_CHAIN_AT; rewrite -!FRECHET_DERIVATIVE_WORKS.
130 Qed.
131
132
133 Lemma jacobian_compose f g x :
134 `f differentiable at (g x) ==>
135 g differentiable at x ==>
136 jacobian (f o g) (at x) = jacobian f (at (g x)) ** jacobian g (at x)`.
137 move => df dg.
138 by rewrite !jacobian frechet_compose // MATRIX_COMPOSE // !LINEAR_FRECHET_DERIVATIVE.
139 Qed.
140
141
142 Lemma frechet_eq_jacobian f x :
143 `f differentiable at x ==>
144 frechet_derivative f (at x) = (\h. jacobian f (at x) ** h)`.
145 move => df.
146 by rewrite EQ_SYM_EQ FRECHET_DERIVATIVE_AT // -JACOBIAN_WORKS.
147 Qed.
148
149
150 (* Product *)
151 Section Product.
152
153
154 Lemma REAL_LET_MUL2 w x y z: `&0 < w /\ w <= x /\ &0 <= y /\ y < z ==> w * y < x * z`.
155 move => ineq.
156 case: (EXCLUDED_MIDDLE `w = x`) => [w_eq_x | wnx].
157 by rewrite -w_eq_x REAL_LT_LMUL.
158 by rewrite REAL_LT_MUL2; move: ineq wnx; arith.
159 Qed.
160
161
162 Lemma has_derivative_x12 y :
163 `(lift o (\x:real^2. x$1 * x$2) has_derivative lift o (\x. y$2 * x$1 + y$1 * x$2)) (at y)`.
164 rewrite has_derivative_at; split.
165 rewrite linear !o_THM /= !VECTOR_ADD_COMPONENT !VECTOR_MUL_COMPONENT !LIFT_ADD !LIFT_CMUL !LIFT_ADD.
166 by "VECTOR_ARITH_TAC".
167 rewrite !o_THM /= -LIFT_ADD -LIFT_SUB -LIFT_CMUL.
168 rewrite LIM_AT /= !dist "GEN_ALL VECTOR_SUB_RZERO" NORM_LIFT !VECTOR_SUB_COMPONENT => e e0.
169 rewrite "REAL_ARITH `(x:real^2)$1 * x$2 - ((y:real^2)$1 * y$2 + y$2 * (x$1 - y$1) + y$1 * (x$2 - y$2)) =
170 (x$2 - y$2) * (x$1 - y$1)`".
171 exists e; rewrite e0 andTb => x [norm0 norm_e].
172 rewrite !REAL_ABS_MUL REAL_ABS_INV REAL_ABS_NORM.
173 rewrite -!VECTOR_SUB_COMPONENT; set p := `x - y:real^2`.
174 have ineq := (NORM_BOUND_COMPONENT_LT norm_e).
175 apply: REAL_LTE_TRANS; exists `inv (infnorm p) * infnorm p * e`.
176 have infnorm_0: `&0 < infnorm p`; first by rewrite INFNORM_POS_LT -NORM_POS_LT.
177 split; last first.
178 by rewrite REAL_MUL_ASSOC REAL_MUL_LINV ?REAL_MUL_LID ?REAL_LE_REFL // INFNORM_EQ_0 -NORM_POS_LT.
179 rewrite REAL_LET_MUL2 REAL_LT_INV // REAL_LE_INV2 ?INFNORM_LE_NORM // !andTb.
180 rewrite REAL_LE_MUL ?REAL_ABS_POS // andTb.
181 have: `infnorm p = abs (p$1) \/ infnorm p = abs (p$2)`.
182 by rewrite "GEN_ALL INFNORM_2"; arith.
183 by case => <-; first rewrite REAL_MUL_SYM; rewrite REAL_LT_LMUL ineq // DIMINDEX_2; arith.
184 Qed.
185
186
187 Lemma lambda_eq_vsum f : `(\x:A. lambda i. f i x) =
188 (\x. vsum (1..dimindex (:N)) (\i. f i x % (basis i:real^N)))`.
189 rewrite -eq_ext /= => x.
190 rewrite CART_EQ => i ineq; rewrite "GEN_ALL LAMBDA_BETA" // VSUM_COMPONENT //=.
191 set A := `1.. _`; set B := `A DIFF {i}`.
192 have cond: `DISJOINT B {i} /\ A = B UNION {i}`.
193 rewrite DISJOINT !EXTENSION -B_def -A_def IN_INTER IN_DIFF IN_SING NOT_IN_EMPTY /=.
194 split => x; first by rewrite !negb_and negbK -orbA EXCLUDED_MIDDLE.
195 rewrite IN_UNION IN_DIFF IN_SING.
196 by case: (EXCLUDED_MIDDLE `x = i`) => -> //; rewrite /= IN_NUMSEG.
197 rewrite cond SUM_UNION ?cond -B_def ?FINITE_DIFF -?A_def ?FINITE_NUMSEG ?FINITE_SING //.
198 rewrite SUM_SING /= !VECTOR_MUL_COMPONENT (BASIS_COMPONENT i i) //=.
199 rewrite "REAL_ARITH `!a b. a = b + a * &1 <=> b = &0`" SUM_EQ_0 // => j.
200 rewrite IN_DIFF IN_SING => ineq_j /=; rewrite BASIS_COMPONENT // (EQ_SYM_EQ i).
201 by rewrite ineq_j /= REAL_MUL_RZERO.
202 Qed.
203
204
205
206 Lemma has_derivative_lambda f f' y :
207 `(!i. i IN 1..dimindex (:M) ==> (lift o (f i) has_derivative lift o (f' i)) (at (y:real^N))) ==>
208 (((\x. lambda i. f i x):real^N->real^M) has_derivative (\x. lambda i. f' i x) ) (at y)`.
209 Proof.
210 move => df; rewrite !lambda_eq_vsum; apply HAS_DERIVATIVE_VSUM.
211 rewrite FINITE_NUMSEG andTb => i ineq /=.
212 have eq: `!f. (\x:real^N. f i x % (basis i:real^M)) = (\x. drop ((lift o f i) x) % basis i)`.
213 by move => g; rewrite -eq_ext /= o_THM LIFT_DROP.
214 by rewrite (eq f) (eq f') "GEN_ALL HAS_DERIVATIVE_VMUL_DROP"; rewr ETA_AX; rewrite df.
215 Qed.
216
217
218 Lemma vector2_eq_lambda x y : `(vector [x; y]:real^2) = (lambda i. if i = 1 then x else y)`.
219 Proof.
220 rewrite CART_EQ DIMINDEX_2 => i; rewrite "ARITH_RULE `1 <= i /\ i <= 2 <=> i = 1 \/ i = 2`".
221 by case => {1 3}->; rewrite "GEN_ALL VECTOR_2" "GEN_ALL LAMBDA_BETA" /= ?DIMINDEX_2; arith.
222 Qed.
223
224
225 Lemma has_derivative_vector2 f g f' g' y :
226 `(lift o f has_derivative lift o f') (at y) ==>
227 (lift o g has_derivative lift o g') (at y) ==>
228 ((\x. vector [f x; g x]:real^2) has_derivative (\x. vector [f' x; g' x]:real^2)) (at y)`.
229 Proof.
230 move => df dg; rewrite !vector2_eq_lambda.
231 apply has_derivative_lambda; rewrite DIMINDEX_2 IN_NUMSEG => i.
232 rewrite "ARITH_RULE `1 <= i /\ i <= 2 <=> i = 1 \/ i = 2`"; case => {2 4}-> /=; rewr ETA_AX //.
233 by rewrite "ARITH_RULE `~(2 = 1)`" /=; rewr ETA_AX.
234 Qed.
235
236
237 Lemma has_derivative_mul f g f' g' y :
238 `(lift o f has_derivative lift o f') (at y) ==>
239 (lift o g has_derivative lift o g') (at y) ==>
240 (lift o (\x. f x * g x) has_derivative lift o (\x. f' x * g y + f y * g' x)) (at y)`.
241 move => df dg.
242 have ->: `lift o (\x. f x * g x) = (lift o (\p. p$1 * p$2)) o (\x. vector [f x; g x]:real^2)`.
243 by rewrite -eq_ext !o_THM /= => x; rewrite !"GEN_ALL VECTOR_2".
244 set q := `vector [f y; g y]:real^2`.
245 have ->: `lift o (\x. f' x * g y + f y * g' x) =
246 (lift o (\x:real^2. q$2 * x$1 + q$1 * x$2)) o (\x. vector [f' x; g' x])`.
247 by rewrite -eq_ext !o_THM /= -q_def !"GEN_ALL VECTOR_2" REAL_MUL_SYM.
248 by apply DIFF_CHAIN_AT => /=; rewrite q_def has_derivative_x12 has_derivative_vector2.
249 Qed.
250
251
252 Lemma f_eq_lift_drop f : `f = lift o (drop o f)`.
253 Proof. by rewrite -eq_ext !o_THM LIFT_DROP. Qed.
254
255
256 Lemma differentiable_mul f g y :
257 `lift o f differentiable (at y) ==>
258 lift o g differentiable (at y) ==>
259 lift o (\x. f x * g x) differentiable (at y)`.
260 rewrite 2!differentiable => [] [f'] df [g'] dg.
261 move: df dg; rewrite (f_eq_lift_drop f') (f_eq_lift_drop g') => df dg.
262 have := has_derivative_mul df dg.
263 by apply HAS_DERIVATIVE_IMP_DIFFERENTIABLE.
264 Qed.
265
266
267 Lemma frechet_mul f g y :
268 `lift o f differentiable at y ==>
269 lift o g differentiable at y ==>
270 frechet_derivative (lift o (\x. f x * g x)) (at y) =
271 (\x. g y % frechet_derivative (lift o f) (at y) x +
272 f y % frechet_derivative (lift o g) (at y) x)`.
273 rewrite !FRECHET_DERIVATIVE_WORKS [`frechet_derivative _1 _2`]f_eq_lift_drop => df.
274 rewrite [`frechet_derivative _1 _2`]f_eq_lift_drop => dg.
275 have := has_derivative_mul df dg; move/FRECHET_DERIVATIVE_AT => <-.
276 rewrite -eq_ext !o_THM /= !LIFT_DROP => x.
277 by rewrite LIFT_ADD REAL_MUL_SYM !LIFT_CMUL !LIFT_DROP.
278 Qed.
279
280 End Product.
281
282
283
284 End Misc.
285
286
287 (* Properties of partial derivatives *)
288 Section Partial.
289
290
291 Lemma real_derivative_compose_frechet f h t :
292 `(lift o f) differentiable at (h t) ==>
293 (h o drop) differentiable at (lift t) ==>
294 ((f o h) has_real_derivative (drop o (frechet_derivative (lift o f) (at (h t)) o
295 frechet_derivative (h o drop) (at (lift t))) o lift) (&1)) (atreal t)`.
296 move => diff_f diff_h.
297 move: (diff_f) (diff_h); rewrite !FRECHET_DERIVATIVE_WORKS.
298 set f' := `frechet_derivative _1 _2`.
299 set h' := `frechet_derivative _1 _2`.
300 move => df dh.
301 rewrite "GEN_ALL HAS_REAL_FRECHET_DERIVATIVE_AT".
302 have ->: `lift o (f o h) o drop = (lift o f) o (h o drop)`; first by rewrite !o_ASSOC.
303 suff ->: `(\x. (drop o (f' o h') o lift) (&1) % x) = f' o h'`.
304 by rewrite DIFF_CHAIN_AT dh o_THM LIFT_DROP df.
305 rewrite -eq_ext !o_THM => x /=.
306 have lin: `linear f' /\ linear h'`.
307 by rewrite -h'_def -f'_def !LINEAR_FRECHET_DERIVATIVE.
308 have {2}->: `x = drop x % lift (&1)`.
309 by rewrite -DROP_EQ DROP_CMUL LIFT_DROP REAL_MUL_RID.
310 by rewrite !LINEAR_CMUL // -DROP_EQ !DROP_CMUL REAL_MUL_SYM.
311 Qed.
312
313
314
315 Lemma real_derivative_compose_jacobian f h t :
316 `(lift o f) differentiable at (h t) ==>
317 (h o drop) differentiable at (lift t) ==>
318 ((f o h) has_real_derivative (jacobian (lift o f) (at (h t)) **
319 jacobian (h o drop) (at (lift t)))$1$1) (atreal t)`.
320 move => df dh.
321 move: (real_derivative_compose_frechet df dh).
322 rewrite !frechet_eq_jacobian // !o_THM /=.
323 rewrite MATRIX_VECTOR_MUL_ASSOC matrix_vector_mul DROP_LAMBDA DIMINDEX_1 SUM_SING_NUMSEG /=.
324 by rewrite LIFT_COMPONENT REAL_MUL_RID.
325 Qed.
326
327
328
329 Lemma diff_imp_real_diff f h t :
330 `(lift o f) differentiable at (h t) ==>
331 (h o drop) differentiable at (lift t) ==>
332 (f o h) real_differentiable atreal t`.
333 move => diff_f diff_h.
334 move: (real_derivative_compose_frechet diff_f diff_h).
335 set fh' := `(drop o _ o lift) (&1)`.
336 by rewrite real_differentiable => dfh; exists fh'.
337 Qed.
338
339
340 Lemma diff_direction y e net : `((\t. y + t % e) o drop) differentiable net`.
341 have ->: `(\t. y + t % e) o drop = (\x. y + drop x % e)`; first by rewrite -eq_ext o_THM.
342 rewrite DIFFERENTIABLE_ADD DIFFERENTIABLE_CONST andTb.
343 apply HAS_DERIVATIVE_IMP_DIFFERENTIABLE.
344 by exists `\x. drop x % e`; apply HAS_DERIVATIVE_VMUL_DROP; rewrite HAS_DERIVATIVE_ID.
345 Qed.
346
347
348 Lemma frechet_direction y e t :
349 `frechet_derivative ((\t. y + t % e) o drop) (at (lift t)) = (\x. drop x % e)`.
350 rewrite f_unary_drop frechet_add.
351 rewrite DIFFERENTIABLE_CONST andTb; apply HAS_DERIVATIVE_IMP_DIFFERENTIABLE.
352 exists `\x. drop x % e`; apply HAS_DERIVATIVE_VMUL_DROP; rewrite HAS_DERIVATIVE_ID.
353 by rewrite frechet_vmul frechet_const /= VECTOR_ADD_LID.
354 Qed.
355
356
357 Lemma real_dir_derivative_frechet f y e t :
358 `(lift o f) differentiable at (y + t % e) ==>
359 ((f o (\t. y + t % e)) has_real_derivative
360 (drop (frechet_derivative (lift o f) (at (y + t % e)) e))) (atreal t)`.
361 move => df.
362 move: (real_derivative_compose_frechet f `\t. y + t % e` t).
363 by rewrite df diff_direction /= frechet_direction !o_THM /= LIFT_DROP VECTOR_MUL_LID.
364 Qed.
365
366
367 Lemma real_dir_derivative_jacobian f y e t : `(lift o f) differentiable at (y + t % e) ==>
368 ((f o (\t. y + t % e)) has_real_derivative
369 drop (jacobian (lift o f) (at (y + t % e)) ** e)) (atreal t)`.
370 move => df.
371 move: (real_dir_derivative_frechet f e df).
372 by rewrite frechet_eq_jacobian.
373 Qed.
374
375
376 Lemma partial_eq_frechet f y i : `(lift o f) differentiable at (y:real^N) ==>
377 partial i f y = drop (frechet_derivative (lift o f) (at y) (basis i))`.
378 move => df; rewrite partial.
379 move: (real_dir_derivative_frechet f y `basis i:real^N` `&0`); rewrite VECTOR_MUL_LZERO VECTOR_ADD_RID.
380 by move => /(_ df) /derivative_unique.
381 Qed.
382
383
384 Lemma partial_eq_jacobian f y i : `(lift o f) differentiable at y ==>
385 partial i f y = drop (jacobian (lift o f) (at y) ** basis i)`.
386 move => df.
387 by move: (df); rewrite partial_eq_frechet // JACOBIAN_WORKS => /FRECHET_DERIVATIVE_AT <-.
388 Qed.
389
390 Lemma partial_eq_jacobian_column f y i : `(lift o (f:real^N->real)) differentiable at y ==>
391 i IN 1..dimindex (:N) ==>
392 partial i f y = drop (column i (jacobian (lift o f) (at y)))`.
393 rewrite IN_NUMSEG => df ineq.
394 by rewrite partial_eq_jacobian // MATRIX_VECTOR_MUL_BASIS.
395 Qed.
396
397
398 Lemma partial_eq_jacobian_entry f y i : `(lift o (f:real^N->real)) differentiable at y ==>
399 i IN 1..dimindex (:N) ==>
400 partial i f y = (jacobian (lift o f) (at y))$1$i`.
401 by move => df ineq; rewrite partial_eq_jacobian_column // column DROP_LAMBDA. Qed.
402
403
404 Variable y : `:real^N`.
405 Variable i : `:num`.
406
407
408 Lemma partial_eq0 f : `~(i IN 1..dimindex (:N)) ==>
409 partial i f y = &0`.
410 move => ineq; rewrite partial.
411 have ->: `basis i = (vec 0):real^N`; first by rewrite BASIS_EQ_0.
412 (* TODO: rewrite doesn't work *)
413 rewr VECTOR_MUL_RZERO VECTOR_ADD_RID.
414 have ->: `derivative (f o (\t. y)) = derivative (\t. f y)`.
415 by "AP_TERM_TAC"; rewrite -eq_ext o_THM.
416 by rewrite derivative_const.
417 Qed.
418
419
420 Lemma derivative_compose f g x : `f real_differentiable atreal (g x) ==>
421 g real_differentiable atreal x ==>
422 derivative (f o g) x = derivative f (g x) * derivative g x`.
423 move => df dg.
424 have ->: `f o g = \x. f (g x)`; first by rewrite -eq_ext o_THM.
425 by rewrite derivative_composition // REAL_MUL_SYM.
426 Qed.
427
428
429 Lemma projection_has_derivative i net :
430 `i IN 1..dimindex (:N) ==>
431 (lift o (\x:real^N. x$i) has_derivative lift o (\x. x$i)) net`.
432 rewrite IN_NUMSEG => ineq.
433 have ->: `lift o (\x:real^N. x$i) = (\x. x$i % vec 1)`.
434 by rewrite -eq_ext o_THM /= => x; rewrite -DROP_EQ LIFT_DROP DROP_CMUL DROP_VEC REAL_MUL_RID.
435 by rewrite "GEN_ALL HAS_DERIVATIVE_VMUL_COMPONENT" HAS_DERIVATIVE_ID.
436 Qed.
437
438
439 Lemma projection_diff i net :
440 `i IN 1..dimindex (:N) ==>
441 (lift o (\x:real^N. x$i)) differentiable net`.
442 rewrite differentiable => /(projection_has_derivative i net) h.
443 by exists `lift o \x:real^N. x$i`.
444 Qed.
445
446
447 Lemma frechet_projection i x :
448 `i IN 1..dimindex (:N) ==>
449 frechet_derivative (lift o (\x:real^N. x$i)) (at x) = lift o (\x:real^N. x$i)`.
450 move => ineq; rewrite EQ_SYM_EQ; apply FRECHET_DERIVATIVE_AT.
451 by rewrite projection_has_derivative.
452 Qed.
453
454
455 Lemma has_derivative_vector_frechet h t i :
456 `i IN 1..dimindex (:N) ==>
457 (h o drop) differentiable at (lift t) ==>
458 ((\s. (h:real->real^N) s$i) has_real_derivative
459 (frechet_derivative (h o drop) (at (lift t)) (lift (&1)))$i) (atreal t)`.
460 move => ineq dh.
461 have ->: `(\s. h s$i) = (\x. x$i) o h`; first by rewrite -eq_ext o_THM.
462 move: (real_derivative_compose_frechet `\x:real^N. x$i` h t).
463 rewrite dh projection_diff //=.
464 set lhs := `(drop o _ o lift) (&1)`.
465 set rhs := `(frechet_derivative _1 _2 _3)$i`.
466 suff ->: `lhs = rhs`; first by done.
467 by rewrite -lhs_def !o_THM /= frechet_projection // o_THM /= -rhs_def LIFT_DROP.
468 Qed.
469
470
471 Lemma has_derivative_vector_jacobian h t i :
472 `i IN 1..dimindex (:N) ==>
473 (h o drop) differentiable at (lift t) ==>
474 ((\s. (h:real->real^N) s$i) has_real_derivative (jacobian (h o drop) (at (lift t)))$i$1) (atreal t)`.
475 move => ineq dh.
476 move: (has_derivative_vector_frechet ineq dh).
477 set lhs := `(frechet_derivative _1 _2 _3)$i`.
478 set rhs := `jacobian _1 _2$i$1`.
479 suff ->: `lhs = rhs`; first by done.
480 rewrite -lhs_def frechet_eq_jacobian //=.
481 have ->: `lift (&1) = basis 1`.
482 by rewrite -DROP_EQ LIFT_DROP basis DROP_LAMBDA.
483 by rewrite MATRIX_VECTOR_MUL_BASIS ?DIMINDEX_GE_1 ?leqnn // column "GEN_ALL LAMBDA_BETA" -?IN_NUMSEG.
484 Qed.
485
486
487 Lemma derivative_vector_jacobian h t i :
488 `i IN 1..dimindex (:N) ==>
489 ((h:real->real^N) o drop) differentiable at (lift t) ==>
490 derivative (\s. h s$i) t = jacobian (h o drop) (at (lift t))$i$1`.
491 by move => ineq dh; apply derivative_unique; rewrite has_derivative_vector_jacobian. Qed.
492
493
494
495
496 (* real_compose *)
497 Lemma real_derivative_compose_partial f h t :
498 `(lift o (f:real^N -> real)) differentiable at (h t) ==>
499 (h o drop) differentiable at (lift t) ==>
500 ((f o h) has_real_derivative
501 sum (1..dimindex (:N)) (\i. partial i f (h t) * derivative (\s. h s$i) t)) (atreal t)`.
502 move => df dh.
503 move: (real_derivative_compose_jacobian df dh).
504 set lhs := `_$1$1`; set rhs := `sum _ _2`.
505 suff ->: `lhs = rhs`; first by done.
506 rewrite -lhs_def.
507 rewrite matrix_mul "GEN_ALL LAMBDA_BETA" ?DIMINDEX_GE_1 ?leqnn //=.
508 rewrite "GEN_ALL LAMBDA_BETA" ?DIMINDEX_GE_1 ?leqnn //= -rhs_def.
509 apply SUM_EQ => i ineq /=.
510 by rewrite partial_eq_jacobian_entry // REAL_EQ_MUL_LCANCEL derivative_vector_jacobian.
511 Qed.
512
513
514 Lemma real_dir_derivative_partial f e t :
515 `(lift o f) differentiable at (y + t % e) ==>
516 ((f o (\t. y + t % e)) has_real_derivative
517 sum (1..dimindex (:N)) (\i. e$i * (partial i f o (\t. y + t % e)) t)) (atreal t)`.
518 move => df.
519 move: (real_dir_derivative_jacobian f y e df).
520 rewrite matrix_vector_mul DROP_LAMBDA.
521 set lhs := `sum _1 _2`; set rhs := `sum _1 _2`.
522 suff ->: `lhs = rhs`; first by done.
523 rewrite -lhs_def -rhs_def; apply SUM_EQ => i ineq /=.
524 by rewrite o_THM partial_eq_jacobian_entry //= REAL_MUL_SYM.
525 Qed.
526
527
528 Variables f g : `:real^N -> real`.
529
530 Hypothesis df : `(lift o f) differentiable at y`.
531
532 (* uni_compose *)
533 Lemma partial_uni_compose u : `u real_differentiable atreal (f y) ==>
534 partial i (u o f) y = derivative u (f y) * partial i f y`.
535 move => du; rewrite !partial -o_ASSOC derivative_compose !o_THM /=.
536 by rewrite diff_imp_real_diff /= VECTOR_MUL_LZERO VECTOR_ADD_RID // df diff_direction.
537 by rewrite VECTOR_MUL_LZERO VECTOR_ADD_RID.
538 Qed.
539
540
541 (* neg *)
542 Lemma partial_neg : `partial i (\x. --f x) y = --partial i f y`.
543 by rewrite !partial_eq_frechet ?f_lift_neg ?DIFFERENTIABLE_NEG // ?frechet_neg; rewr !ETA_AX // DROP_NEG. Qed.
544
545 (* scale *)
546 Lemma partial_scale c : `partial i (\x. c * f x) y = c * partial i f y`.
547 rewrite !partial_eq_frechet ?f_lift_scale ?DIFFERENTIABLE_CMUL // ?frechet_scale; rewr !ETA_AX //.
548 by rewrite DROP_CMUL.
549 Qed.
550
551
552 Hypothesis dg : `(lift o g) differentiable at y`.
553
554 (* add *)
555 Lemma partial_add : `partial i (\x. f x + g x) y = partial i f y + partial i g y`.
556 rewrite !partial_eq_frechet ?f_lift_add ?DIFFERENTIABLE_ADD // ?frechet_add; rewr !ETA_AX //.
557 by rewrite DROP_ADD.
558 Qed.
559
560 (* sub *)
561 Lemma partial_sub : `partial i (\x. f x - g x) y = partial i f y - partial i g y`.
562 rewrite !partial_eq_frechet ?f_lift_sub ?DIFFERENTIABLE_SUB // ?frechet_sub; rewr !ETA_AX //.
563 by rewrite DROP_SUB.
564 Qed.
565
566 (* mul *)
567 Lemma partial_mul : `partial i (\x. f x * g x) y = partial i f y * g y + f y * partial i g y`.
568 rewrite !partial; set h := `\t. y + t % basis i`.
569 have ->: `(\x. f x * g x) o h = (\t. (f o h) t * (g o h) t)`.
570 by rewrite -eq_ext !o_THM.
571 rewrite derivative_mul; last first.
572 rewrite -{1 4}h_def !o_THM /= VECTOR_MUL_LZERO VECTOR_ADD_RID -(o_THM f) -(o_THM g).
573 by rewrite REAL_ADD_SYM; rewr ETA_AX.
574 have h0: `h (&0) = y`; first by rewrite -h_def /= VECTOR_MUL_LZERO VECTOR_ADD_RID.
575 have dh: `(h o drop) differentiable at (lift (&0))`; first by rewrite -h_def diff_direction.
576 by rewr ETA_AX; rewrite !diff_imp_real_diff ?h0.
577 Qed.
578
579
580
581 End Partial.
582
583
584 Section PartialMonotone.
585
586 Lemma derivative_translation f x :
587 `f real_differentiable atreal x ==>
588 derivative f x = derivative (f o (\t. x + t)) (&0)`.
589 move => diff_f.
590 rewrite derivative_compose /= ?REAL_ADD_RID ?diff_f.
591 by rewrite REAL_DIFFERENTIABLE_ADD ?REAL_DIFFERENTIABLE_CONST ?REAL_DIFFERENTIABLE_ID.
592 rewrite derivative_add ?REAL_DIFFERENTIABLE_CONST ?REAL_DIFFERENTIABLE_ID //.
593 by rewrite derivative_const derivative_x /=; arith.
594 Qed.
595
596 Implicit Type f : `:real^N->real`.
597
598 Lemma partial_increasing_left f j u x z lo :
599 `(!i. i IN 1..dimindex (:N) ==> ~(i = j) ==> u$i = z$i) ==>
600 u$j = x$j ==>
601 (!y. y IN interval [x,z] ==> (lift o f) differentiable at y) ==>
602 (!y. y IN interval [x,z] ==> &0 <= partial j f y) ==>
603 (!y. y IN interval [x,u] ==> lo <= f y) ==>
604 (!y. y IN interval [x,z] ==> lo <= f y)`.
605 rewrite IN_NUMSEG !"GEN_ALL IN_INTERVAL" => uz_eq ux_eq diff_f partial_pos f_bound y y_in.
606 move: diff_f partial_pos; rewrite -!"GEN_ALL IN_INTERVAL" => diff_f partial_pos.
607 set y' := `(lambda i. if i = j then x$j else y$i):real^N`.
608 suff: `f y' <= f y`.
609 apply: "REWRITE_RULE[GSYM IMP_IMP] REAL_LE_TRANS"; apply: f_bound => i i_in.
610 rewrite -y'_def "GEN_ALL LAMBDA_BETA" //=.
611 case: (EXCLUDED_MIDDLE `i = j`) => /= ij; first by rewrite ux_eq REAL_LE_REFL.
612 by rewrite uz_eq // !y_in.
613 case: (EXCLUDED_MIDDLE `j IN 1..dimindex (:N)`); last first; rewrite IN_NUMSEG => j_in.
614 suff: `y' = y`; first by move => ->; rewrite REAL_LE_REFL.
615 rewrite CART_EQ => i i_in.
616 have inj: `~(i = j)`; first by move: j_in i_in; arith.
617 by rewrite -y'_def "GEN_ALL LAMBDA_BETA".
618 set g := `f o (\t. y' + t % basis j)`.
619 have ->: `f y' = g (&0)`.
620 by rewrite -g_def o_THM /= VECTOR_MUL_LZERO VECTOR_ADD_RID.
621 have ->: `f y = g (y$j - x$j)`.
622 rewrite -g_def o_THM /=; "AP_TERM_TAC".
623 rewrite CART_EQ => i i_in.
624 rewrite VECTOR_ADD_COMPONENT VECTOR_MUL_COMPONENT BASIS_COMPONENT //.
625 case: (EXCLUDED_MIDDLE `i = j`) => /= ij; rewrite -y'_def "GEN_ALL LAMBDA_BETA" //.
626 by arith.
627 by rewrite /= ij /=; arith.
628 set s := `real_interval [&0, y$j - x$j]`.
629 have in_s : `!t. t IN s ==> y' + t % basis j IN interval [x,z]`.
630 rewrite -s_def IN_REAL_INTERVAL "GEN_ALL IN_INTERVAL" => t t_ineq i i_ineq.
631 rewrite !VECTOR_ADD_COMPONENT VECTOR_MUL_COMPONENT BASIS_COMPONENT //.
632 rewrite -y'_def "GEN_ALL LAMBDA_BETA" //=.
633 case: (EXCLUDED_MIDDLE `i = j`) => /= ij; last first.
634 by rewrite REAL_MUL_RZERO REAL_ADD_RID !y_in.
635 by move: (y_in i_ineq) t_ineq; rewrite ij; arith.
636 have ds : `!t. t IN s ==> (g has_real_derivative (partial j f (y' + t % basis j))) (atreal t within s)`.
637 move => t /in_s p_in; apply: HAS_REAL_DERIVATIVE_ATREAL_WITHIN; rewrite partial.
638 set h := `f o _`.
639 have ->: `h = g o (\t'. t + t')`.
640 rewrite -eq_ext -h_def -g_def => r; rewrite !o_THM /=.
641 by rewrite "GEN_ALL VECTOR_ADD_RDISTRIB" "GEN_ALL VECTOR_ADD_ASSOC".
642 by rewrite -derivative_translation ?has_derivative_alt -g_def diff_imp_real_diff;
643 rewrite diff_f //= diff_direction.
644 have pos: `&0 <= y$j - x$j`; first by move: (y_in j_in); arith.
645 have := HAS_REAL_DERIVATIVE_INCREASING_IMP
646 g `\t. partial j f (y' + t % basis j)` s `&0` `y$j - x$j`.
647 rewrite -{1}s_def IS_REALINTERVAL_INTERVAL /=; rewr ds /=; apply.
648 rewrite -{2 3}s_def !IN_REAL_INTERVAL pos !REAL_LE_REFL /=.
649 by move => t /in_s /partial_pos.
650 Qed.
651
652
653 Lemma partial_decreasing_left f j u x z hi :
654 `(!i. i IN 1..dimindex (:N) ==> ~(i = j) ==> u$i = z$i) ==>
655 u$j = x$j ==>
656 (!y. y IN interval [x,z] ==> (lift o f) differentiable at y) ==>
657 (!y. y IN interval [x,z] ==> partial j f y <= &0) ==>
658 (!y. y IN interval [x,u] ==> f y <= hi) ==>
659 (!y. y IN interval [x,z] ==> f y <= hi)`.
660 move => u_eq_i u_eq_j diff_f partial_f f_bound y y_in.
661 have := partial_increasing_left `(\p. -- f p)` j u x z `--hi` u_eq_i u_eq_j.
662 "ANTS_TAC"; first by move => p /diff_f /DIFFERENTIABLE_NEG; rewrite f_lift_neg.
663 "ANTS_TAC".
664 by move => p p_in; rewrite partial_neg ?diff_f // REAL_NEG_GE0 partial_f.
665 "ANTS_TAC"; first by move => p /f_bound; arith.
666 by move/(_ y_in); arith.
667 Qed.
668
669
670 Lemma partial_translation f i p y: `lift o f differentiable at (p + y) ==>
671 partial i (f o (\x. p + x)) y = partial i f (p + y)`.
672 move => diff.
673 have diff_p : `!net. (\x. p + x) differentiable net`.
674 by move => net; rewrite DIFFERENTIABLE_ADD DIFFERENTIABLE_CONST DIFFERENTIABLE_ID.
675 rewrite partial_eq_frechet 1?o_ASSOC ?DIFFERENTIABLE_CHAIN_AT //.
676 rewrite frechet_compose // frechet_add ?DIFFERENTIABLE_ID ?DIFFERENTIABLE_CONST //.
677 rewrite frechet_const frechet_id /= VECTOR_ADD_LID -I_DEF I_O_ID.
678 by rewrite partial_eq_frechet.
679 Qed.
680
681 Lemma partial_rev_translation f i p y : `lift o f differentiable at (p - y) ==>
682 partial i (f o (\x. p - x)) y = --partial i f (p - y)`.
683 move => diff.
684 have diff_p : `!net. (\x. p - x) differentiable net`.
685 by move => net; rewrite DIFFERENTIABLE_SUB DIFFERENTIABLE_CONST DIFFERENTIABLE_ID.
686 rewrite partial_eq_frechet 1?o_ASSOC ?DIFFERENTIABLE_CHAIN_AT //.
687 rewrite frechet_compose // frechet_sub ?DIFFERENTIABLE_ID ?DIFFERENTIABLE_CONST //.
688 rewrite frechet_const frechet_id /= "GEN_ALL VECTOR_SUB_LZERO".
689 rewrite partial_eq_frechet // !o_THM /=.
690 by rewrite LINEAR_NEG ?LINEAR_FRECHET_DERIVATIVE // DROP_NEG.
691 Qed.
692
693
694 Lemma partial_increasing_right f j u x z hi :
695 `(!i. i IN 1..dimindex (:N) ==> ~(i = j) ==> u$i = x$i) ==>
696 u$j = z$j ==>
697 (!y. y IN interval [x,z] ==> (lift o f) differentiable at y) ==>
698 (!y. y IN interval [x,z] ==> &0 <= partial j f y) ==>
699 (!y. y IN interval [u,z] ==> f y <= hi) ==>
700 (!y. y IN interval [x,z] ==> f y <= hi)`.
701 move => u_eq_i u_eq_j diff_f partial_f f_bound y y_in.
702 case: (EXCLUDED_MIDDLE `j IN 1..dimindex (:N)`); last first; rewrite IN_NUMSEG => j_in.
703 apply: f_bound; move: y_in; rewrite !"GEN_ALL IN_INTERVAL" => y_ineq i i_in.
704 have inj: `~(i = j)`; first by move: j_in i_in; arith.
705 by rewrite u_eq_i ?IN_NUMSEG // !y_ineq.
706 have := partial_decreasing_left `f o (\p:real^N. x + (z - p))` j `x + (z - u):real^N` x z hi.
707 "ANTS_TAC".
708 move => i /u_eq_i eq1 inj; rewrite VECTOR_ADD_COMPONENT VECTOR_SUB_COMPONENT.
709 by rewrite eq1 //; arith.
710 "ANTS_TAC"; first by rewrite VECTOR_ADD_COMPONENT VECTOR_SUB_COMPONENT u_eq_j; arith.
711 have Hp : `!p. p IN interval [x,z] ==> x + (z - p) IN interval [x,z]`.
712 move => p; rewrite !"GEN_ALL IN_INTERVAL" => p_in i ineq.
713 by move: (p_in ineq); rewrite VECTOR_ADD_COMPONENT VECTOR_SUB_COMPONENT; arith.
714 set dP := `!y. _ y`.
715 have P: `dP`.
716 rewrite -dP_def; move => p p_in.
717 by rewrite o_ASSOC DIFFERENTIABLE_CHAIN_AT DIFFERENTIABLE_ADD ?DIFFERENTIABLE_SUB;
718 rewrite ?DIFFERENTIABLE_ID ?DIFFERENTIABLE_CONST // diff_f //= Hp.
719 move: P => /=; rewrite -dP_def => diff.
720 "ANTS_TAC".
721 move => p p_in.
722 have assoc := "VECTOR_ARITH `!x z p. x + z - p = (x + z) - p:real^N`".
723 rewrite assoc partial_rev_translation -assoc ?diff_f ?Hp //.
724 by rewrite REAL_NEG_LE0 partial_f Hp.
725 "ANTS_TAC".
726 move => p p_in; rewrite o_THM /= f_bound.
727 move: p_in; rewrite !"GEN_ALL IN_INTERVAL" => ineq i i_ineq.
728 by move: (ineq i_ineq); rewrite !VECTOR_ADD_COMPONENT !VECTOR_SUB_COMPONENT; arith.
729 move/(_ `x + z - y:real^N`); rewrite o_THM /=.
730 rewrite "VECTOR_ARITH `!x z y:real^N. x + z - (x + z - y) = y`"; apply.
731 by rewrite Hp.
732 Qed.
733
734
735 End PartialMonotone.
736
737
738
739 (* Taylor *)
740 Section Taylor.
741
742
743 Lemma real_taylor2_bound f dd_bound: `nth_diff_strong_int 2 (&0, &1) f ==>
744 (!t. interval_arith t (&0, &1) ==> abs (nth_derivative 2 f t) <= dd_bound) ==>
745 abs (f (&1) - (f (&0) + derivative f (&0))) <= dd_bound / &2`.
746 rewrite nth_diff_strong_int nth_diff_strong2_eq_alt => df dd.
747 set R := `\i. if i = 0 then f else if i = 1 then derivative f else nth_derivative 2 f`.
748 have arithH := "ARITH_RULE `0 + 1 = 1 /\ ~(1 = 0) /\ 1 + 1 = 2 /\ ~(2 = 1) /\ ~(2 = 0)`".
749 move: (REAL_TAYLOR R `1` `real_interval [&0, &1]` dd_bound); "ANTS_TAC".
750 rewrite IS_REALINTERVAL_INTERVAL andTb; split.
751 move => i x; rewrite IN_REAL_INTERVAL -interval_arith "ARITH_RULE `i <= 1 <=> i = 0 \/ i = 1`".
752 move => [] /df [s] d_f.
753 by case => ->; rewrite -R_def /= !arithH /=; apply HAS_REAL_DERIVATIVE_ATREAL_WITHIN; rewrite d_f.
754 move => x; rewrite IN_REAL_INTERVAL -interval_arith arithH => ineq.
755 by move: (df ineq) => [s] d_f; rewrite -R_def /= !arithH /= dd.
756 move/(_ `&0` `&1`); rewrite !IN_REAL_INTERVAL !REAL_LE_REFL REAL_LE_01 /=.
757 rewrite REAL_SUB_RZERO REAL_ABS_1 !REAL_POW_ONE "ARITH_RULE `FACT (1 + 1) = 2`" !real_div !REAL_MUL_LID.
758 rewrite {2}ONE "GEN_ALL SUM_CLAUSES_NUMSEG" SUM_SING_NUMSEG -ONE "ARITH_RULE `0 <= 1`" /=.
759 rewrite !"ARITH_RULE `FACT 0 = 1 /\ FACT 1 = 1`" REAL_INV_1 !REAL_MUL_RID.
760 by rewrite -R_def /= !arithH.
761 Qed.
762
763
764 Lemma real_taylor1_bound f d_bound:
765 `(!t. interval_arith t (&0, &1) ==> f real_differentiable atreal t /\
766 abs (derivative f t) <= d_bound) ==>
767 abs (f (&1) - f (&0)) <= d_bound`.
768 move => df.
769 set R := `\i. if i = 0 then f else derivative f`.
770 have arithH := "ARITH_RULE `0 + 1 = 1 /\ ~(1 = 0)`".
771 move: (REAL_TAYLOR R `0` `real_interval [&0, &1]` d_bound); "ANTS_TAC".
772 rewrite IS_REALINTERVAL_INTERVAL andTb; split.
773 move => i x; rewrite IN_REAL_INTERVAL -interval_arith leqn0.
774 move => [] /df [diff_f df_bound] ->.
775 by rewrite -R_def /= !arithH /=; apply HAS_REAL_DERIVATIVE_ATREAL_WITHIN; rewrite has_derivative_alt.
776 move => x; rewrite IN_REAL_INTERVAL -interval_arith arithH => ineq.
777 by move: (df ineq) => [s] d_f; rewrite -R_def /= !arithH /= df.
778 move/(_ `&0` `&1`); rewrite !IN_REAL_INTERVAL !REAL_LE_REFL REAL_LE_01 /=.
779 rewrite SUM_SING_NUMSEG /= REAL_SUB_RZERO arithH REAL_ABS_1 !REAL_POW_ONE.
780 rewrite !"ARITH_RULE `FACT 1 = 1 /\ FACT 0 = 1`" REAL_DIV_1 !REAL_MUL_RID.
781 by rewrite -R_def /= !arithH.
782 Qed.
783
784
785
786 (* m_taylor_error *)
787 "let m_taylor_error = new_definition `m_taylor_error f domain (w:real^N) error <=>
788 !x:real^N. x IN interval [domain] ==> sum (1..dimindex (:N)) (\i. w$i * sum (1..dimindex (:N))
789 (\j. w$j * abs (partial j (partial i f) x))) <= error`".
790
791 "let m_taylor_partial_error = new_definition `m_taylor_partial_error f i domain (w:real^N) error <=>
792 (!x:real^N. x IN interval[domain] ==>
793 sum (1..dimindex (:N)) (\j. w$j * abs (partial j (partial i f) x)) <= error)`".
794
795
796 Lemma taylor_error_eq_sum_partial_errors f domain w p_error error :
797 `(!i. i IN 1..dimindex (:N) ==> m_taylor_partial_error f i domain w (p_error i) /\ &0 <= w$i) ==>
798 sum (1..dimindex (:N)) (\i. w$i * p_error i) <= error ==>
799 m_taylor_error f domain (w:real^N) error`.
800 rewrite m_taylor_partial_error m_taylor_error => partialH ineq p p_in.
801 apply: "REWRITE_RULE[GSYM IMP_IMP] REAL_LE_TRANS" ineq.
802 apply SUM_LE; rewrite FINITE_NUMSEG andTb => i i_ineq /=.
803 by rewrite REAL_LE_LMUL !(partialH i_ineq).
804 Qed.
805
806
807
808 (* diff2 definition *)
809 "let partial2 = new_definition `partial2 j i f = partial j (partial i f)`".
810
811
812 "let diff2 = new_definition `diff2 f x <=>
813 ?s. open s /\ x IN s /\ (!y. y IN s ==> (lift o f) differentiable at y /\
814 (!i. (lift o partial i f) differentiable at y))`".
815
816
817 "let diff2c = new_definition `diff2c f x <=> diff2 f x /\
818 (!i j. (lift o partial2 j i f) continuous at x)`".
819
820 Lemma diff2c_imp_diff2 f x : `diff2c f x ==> diff2 f x`. by rewrite diff2c /=. Qed.
821
822
823 Lemma diff2_eq_diff2_on_open f x : `diff2 f x <=>
824 ?s. open s /\ x IN s /\ (!y. y IN s ==> diff2 f y)`.
825 rewrite !diff2; split => [] [s] [open_s] [xs] df.
826 by exists s; rewrite {1}open_s xs !andTb => y ys; exists s.
827 move: (df xs) => [t] [open_t] [xt] df2; move: df => _.
828 by exists t.
829 Qed.
830
831
832 Lemma diff2_imp_real_diff f x e t : `diff2 f (x + t % e) ==>
833 f o (\t. x + t % e) real_differentiable atreal t`.
834 rewrite diff2 => [] [s] [open_s] [xs] df.
835 by apply diff_imp_real_diff; rewrite /= df // diff_direction.
836 Qed.
837
838
839 Lemma diff2_dir_derivative f x e t : `diff2 f (x + t % e:real^N) ==>
840 derivative (f o (\t. x + t % e)) t =
841 sum (1..dimindex (:N)) (\i. e$i * (partial i f o (\t. x + t % e)) t)`.
842 rewrite diff2 => [] [s] [open_s] [xs] df.
843 by apply: derivative_unique; rewrite real_dir_derivative_partial df.
844 Qed.
845
846
847 Lemma diff2_partial_real_diff f i x e t : `diff2 f (x + t % e:real^N) ==>
848 partial i f o (\t. x + t % e) real_differentiable atreal t`.
849 rewrite diff2 => [] [s] [open_s] [xs] df.
850 by rewrite diff_imp_real_diff /= df // diff_direction.
851 Qed.
852
853
854 Lemma in_trans x s t : `t SUBSET s ==> x IN t ==> x IN s`.
855 rewrite SUBSET => sub xt.
856 exact: sub.
857 Qed.
858
859
860 Lemma open_contains_open_interval e s x : `open s ==> x IN s ==>
861 ?a b. &0 IN real_interval (a, b) /\ IMAGE (\t. x + t % e) (real_interval (a, b)) SUBSET s`.
862 rewrite OPEN_CONTAINS_BALL => open_s.
863 move/open_s => [d] [d0] ball_s; move: open_s => _.
864 case: (EXCLUDED_MIDDLE `norm e = &0`) => [|n0].
865 rewrite NORM_EQ_0 => ->; exists `--d` d.
866 split; first by rewrite IN_REAL_INTERVAL; move: d0; arith.
867 rewrite SUBSET IN_IMAGE => y [t] -> /=; rewrite "GEN_ALL VECTOR_MUL_RZERO" VECTOR_ADD_RID.
868 by rewrite (in_trans ball_s) CENTRE_IN_BALL.
869 set y := `((d / &2) * inv(norm e)) % e`.
870 have norm_y : `norm y = d / &2`.
871 rewrite -y_def -VECTOR_MUL_ASSOC !NORM_MUL REAL_ABS_INV REAL_ABS_NORM REAL_MUL_LINV //.
872 by move: d0; arith.
873 exists `-- (d / &2 * inv (norm e))` `d / &2 * inv (norm e)`; split.
874 rewrite IN_REAL_INTERVAL REAL_NEG_LT0 andbb REAL_LT_MUL REAL_LT_INV ?NORM_POS_LT -?NORM_EQ_0 //.
875 by move: d0; arith.
876 apply SUBSET_TRANS; exists `ball (x, d)`; rewrite ball_s andbT SUBSET IN_IMAGE => p [t] [->] t_in /=.
877 rewrite IN_BALL dist VECTOR_SUB_RADD NORM_NEG NORM_MUL.
878 apply: REAL_LET_TRANS; exists `d / &2`; split; last by move: d0; arith.
879 rewrite -(REAL_MUL_RID `d / &2`) -(REAL_MUL_LINV n0) REAL_MUL_ASSOC REAL_LE_RMUL NORM_POS_LE andbT.
880 by move: t_in; rewrite IN_REAL_INTERVAL; arith.
881 Qed.
882
883
884 Lemma diff2_dir f x e t : `diff2 f (x + t % e:real^N) ==>
885 nth_diff_strong 2 (f o (\t. x + t % e)) t`.
886 Proof.
887 rewrite diff2_eq_diff2_on_open nth_diff_strong2_eq => [] [s] [open_s] [xs] df.
888 move: (open_contains_open_interval e open_s xs) => [a] [b] [in0] sub.
889 exists `real_interval (a + t, b + t)`; rewrite REAL_OPEN_REAL_INTERVAL andTb; split.
890 by move: in0; rewrite !IN_REAL_INTERVAL; arith.
891 move => p p_int.
892 have xp_in : `x + p % e IN s`.
893 move: sub; rewrite SUBSET; apply; rewrite IN_IMAGE /=; exists `p - t`.
894 by split; ["VECTOR_ARITH_TAC" | move: p_int; rewrite !IN_REAL_INTERVAL; arith].
895 rewrite diff2_imp_real_diff ?df // andTb.
896 apply differentiable_local.
897 exists `\t. sum (1..dimindex(:N)) (\i. e$i * (partial i f o (\t. x + t % e)) t)`.
898 set d := `min (p - (a + t)) (b + t - p)`.
899 have d0: `&0 < d`; first by move: p_int; rewrite -d_def IN_REAL_INTERVAL; arith.
900 exists `real_interval (p - d, p + d)`; split.
901 rewrite differentiable_sum_numseg => i ineq /=.
902 rewrite REAL_DIFFERENTIABLE_MUL_ATREAL REAL_DIFFERENTIABLE_CONST andTb; rewr ETA_AX.
903 by rewrite diff2_partial_real_diff df.
904 rewrite REAL_OPEN_REAL_INTERVAL andTb; split.
905 by rewrite IN_REAL_INTERVAL; move: d0; arith.
906 move => y y_in; rewrite diff2_dir_derivative // df.
907 move: sub; rewrite SUBSET; apply; rewrite IN_IMAGE /=; exists `y - t`.
908 split; first by "VECTOR_ARITH_TAC".
909 by move: y_in d_def p_int; rewrite !IN_REAL_INTERVAL; arith.
910 Qed.
911
912
913
914 Lemma diff2_dir_derivative2 f x e t : `diff2 f (x + t % e:real^N) ==>
915 nth_derivative 2 (f o (\t. x + t % e)) t =
916 sum (1..dimindex (:N)) (\i. sum (1..dimindex (:N))
917 (\j. e$i * e$j * (partial j (partial i f) o (\t. x + t % e)) t))`.
918 Proof.
919 rewrite diff2_eq_diff2_on_open => [] [s] [open_s] [xs] df.
920 rewrite nth_derivative2; apply: derivative_unique.
921 apply: HAS_REAL_DERIVATIVE_LOCAL.
922 exists `\t. sum (1..dimindex(:N)) (\i. e$i * (partial i f o (\t. x + t % e)) t)`; split.
923 apply HAS_REAL_DERIVATIVE_SUM; rewrite FINITE_NUMSEG andTb => i ineq /=.
924 rewrite SUM_LMUL HAS_REAL_DERIVATIVE_LMUL_ATREAL; rewr ETA_AX.
925 rewrite real_dir_derivative_partial.
926 by move: (df xs); rewrite diff2 => [] [r] [_] [xr] ->.
927 move: (open_contains_open_interval e open_s xs) => [a] [b] [in0] sub.
928 exists `real_interval (a + t, b + t)`; rewrite REAL_OPEN_REAL_INTERVAL andTb; split.
929 by move: in0; rewrite !IN_REAL_INTERVAL; arith.
930 move => p p_in; rewrite diff2_dir_derivative // df.
931 move: sub; rewrite SUBSET; apply; rewrite IN_IMAGE /=; exists `p - t`.
932 split; first by "VECTOR_ARITH_TAC".
933 by move: p_in; rewrite !IN_REAL_INTERVAL; arith.
934 Qed.
935
936
937 Lemma diff2_has_derivative_partial f i x e t : `diff2 f (x + t % e:real^N) ==>
938 (partial i f o (\t. x + t % e) has_real_derivative
939 sum (1..dimindex (:N)) (\j. e$j * (partial j (partial i f) o (\t. x + t % e)) t)) (atreal t)`.
940 rewrite diff2 => [] [s] [open_s] [xs] df.
941 by rewrite real_dir_derivative_partial df.
942 Qed.
943
944
945 Lemma diff2_derivative_partial f i x e t : `diff2 f (x + t % e:real^N) ==>
946 derivative (partial i f o (\t. x + t % e)) t =
947 sum (1..dimindex (:N)) (\j. e$j * (partial j (partial i f) o (\t. x + t % e)) t)`.
948 by move => df; apply: derivative_unique; exact: diff2_has_derivative_partial. Qed.
949
950
951 Lemma diff2_real_diff_partial f i x e t : `diff2 f (x + t % e:real^N) ==>
952 partial i f o (\t. x + t % e) real_differentiable atreal t`.
953 move => df2.
954 move: (diff2_has_derivative_partial df2 i); set s := `sum _1 _2`.
955 by rewrite real_differentiable => df; exists s.
956 Qed.
957
958 (* const *)
959 Lemma partial_const i c : `partial i (\x:real^N. c) = (\x. &0)`.
960 rewrite -eq_ext partial => x /=.
961 suff ->: `(\x. c) o (\t. x + t % basis i) = (\x. c)`.
962 by rewrite derivative_const.
963 by rewrite -eq_ext o_THM.
964 Qed.
965
966 Lemma partial_eq0_alt i f : `~(i IN 1..dimindex (:N)) ==> partial i f = (\x:real^N. &0)`.
967 Proof. by move => ih; rewrite FUN_EQ_THM => x; rewrite partial_eq0. Qed.
968
969 Lemma real_mvt0 : `!f f' a. (!x. abs x <= abs a ==> (f has_real_derivative f' x) (atreal x)) ==>
970 (?t. abs t <= abs a /\ f a - f (&0) = f' t * a)`.
971 Proof.
972 move => f f' a h.
973 case: (EXCLUDED_MIDDLE `&0 <= a`) => a_ineq.
974 have := REAL_MVT_VERY_SIMPLE f f' `&0` a.
975 rewrite a_ineq andTb !IN_REAL_INTERVAL; "ANTS_TAC".
976 move => x x_ineq.
977 by rewrite HAS_REAL_DERIVATIVE_ATREAL_WITHIN h; move: x_ineq; arith.
978 move => [t] [t_ineq] eq.
979 by exists t; rewrite eq; move: t_ineq; arith.
980 have := REAL_MVT_VERY_SIMPLE f f' a `&0`.
981 rewrite !IN_REAL_INTERVAL; "ANTS_TAC".
982 split; first by move: a_ineq; arith.
983 move => x x_ineq; rewrite HAS_REAL_DERIVATIVE_ATREAL_WITHIN h.
984 by move: x_ineq; arith.
985 move => [t] [t_ineq] eq.
986 by exists t; rewrite -REAL_NEG_SUB eq REAL_NEG_RMUL; move: t_ineq; arith.
987 Qed.
988
989
990 (* Mixed second partial derivatives are equal *)
991 Lemma mixed_second_partials f x i j : `diff2c f x ==> partial2 i j f x = partial2 j i f (x:real^N)`.
992 Proof.
993 rewrite diff2c !partial2 => [] [d2f pc].
994 case: (EXCLUDED_MIDDLE `i IN 1..dimindex (:N)`) => ih; last first.
995 by rewrite !(partial_eq0_alt i) // partial_const.
996 case: (EXCLUDED_MIDDLE `j IN 1..dimindex (:N)`) => jh; last first.
997 by rewrite !(partial_eq0_alt j) // partial_const.
998 move: ih jh; rewrite !IN_NUMSEG => ih jh.
999 move: d2f; rewrite diff2_eq_diff2_on_open => [] [s] [open_s] [xs] d2f.
1000 set F1 := `\h k. f ((x + k % basis j) + h % basis i) - f (x + k % basis j)`.
1001 set F2 := `\k h. f ((x + h % basis i) + k % basis j) - f (x + h % basis i)`.
1002 set G := `\h k. F1 h k - F1 h (&0)`.
1003 have v_eq: `!h k. (x + k % basis j) + h % basis i = (x + h % basis i) + k % basis j`; first by "VECTOR_ARITH_TAC".
1004 have G_eq: `G = \h k. F2 k h - F2 k (&0)`.
1005 rewrite -2!eq_ext => h k.
1006 by rewrite -G_def -F2_def -F1_def /= !VECTOR_MUL_LZERO VECTOR_ADD_RID v_eq; arith.
1007 have [r [r0 rs]]: `?r. &0 < r /\ (!h k. abs h <= r /\ abs k <= r ==> (x + h % basis i) + k % basis j IN s)`.
1008 move: open_s; rewrite OPEN_CONTAINS_BALL SUBSET IN_BALL dist => /(_ xs) [e] [e0 de].
1009 exists `e / &3`; split; first by move: e0; arith.
1010 move => h k ineq.
1011 rewrite de -"GEN_ALL VECTOR_ADD_ASSOC" VECTOR_SUB_RADD NORM_NEG.
1012 apply: REAL_LET_TRANS; exists `e / &3 + e / &3`; split; last by move: e0; arith.
1013 apply: REAL_LE_TRANS; exists `abs h + abs k`; split; last by move: ineq; arith.
1014 have := NORM_TRIANGLE `h % basis i:real^N` `k % basis j:real^N`.
1015 by rewrite !NORM_MUL !NORM_BASIS // !REAL_MUL_RID.
1016 have in_s: `(!h. abs h <= r ==> x + h % basis i IN s) /\ (!k. abs k <= r ==> x + k % basis j IN s)`.
1017 split => [h h_ineq | k k_ineq].
1018 by move: (rs h `&0`); rewrite VECTOR_MUL_LZERO VECTOR_ADD_RID h_ineq => ->; move: r0; arith.
1019 by move: (rs `&0` k); rewrite VECTOR_MUL_LZERO VECTOR_ADD_RID k_ineq => ->; move: r0; arith.
1020 have F1h: `!h. F1 h = (\k. (f o (\k. (x + h % basis i) + k % basis j)) k - (f o (\k. x + k % basis j)) k)`.
1021 by rewrite -F1_def !o_THM /= v_eq.
1022 have dF1: `!h. abs h <= r ==> !k. abs k <= r ==> (F1 h) real_differentiable atreal k`.
1023 move => h h_ineq k k_ineq.
1024 rewrite F1h REAL_DIFFERENTIABLE_SUB; rewr ETA_AX.
1025 by rewrite !diff2_imp_real_diff ?d2f ?rs ?in_s.
1026 have F1_der : `!h k. abs h <= r /\ abs k <= r ==>
1027 derivative (F1 h) k = partial j f ((x + h % basis i) + k % basis j) - partial j f (x + k % basis j)`.
1028 move => h k ineq; rewrite F1h derivative_sub; rewr ETA_AX; rewrite ?diff2_imp_real_diff ?d2f ?rs ?in_s //.
1029 rewrite [`derivative (f o (\k. x + k % basis j)) k`]derivative_translation 1?derivative_translation;
1030 rewrite ?diff2_imp_real_diff ?d2f ?rs ?in_s //.
1031 have eq: `!y e. (f o (\k. y + k % e)) o (\t. k + t) = f o (\t. (y + k % e) + t % e)`.
1032 by rewrite -eq_ext !o_THM /= "GEN_ALL VECTOR_ADD_RDISTRIB" "GEN_ALL VECTOR_ADD_ASSOC".
1033 by rewrite !eq -!partial.
1034 have Gh: `!h k. abs h <= r /\ abs k <= r ==>
1035 (?t1. G h k = k * derivative (F1 h) t1 /\ abs t1 <= abs k)`.
1036 move => h k ineq; rewrite -G_def /=.
1037 have := real_mvt0 `F1 h` `derivative (F1 h)` k.
1038 "ANTS_TAC".
1039 move => t t_ineq; rewrite has_derivative_alt dF1.
1040 by move: ineq t_ineq; arith.
1041 move => [t1] [t1_ineq] eq.
1042 by exists t1; rewrite eq; move: t1_ineq ineq; arith.
1043 have Ghk: `!h k. abs h <= r /\ abs k <= r ==>
1044 (?t1 t2. G h k = h * k * partial i (partial j f) (x + t1 % basis j + t2 % basis i)
1045 /\ abs t1 <= abs k /\ abs t2 <= abs h)`.
1046 move => h k ineq.
1047 move: (Gh h k); rewrite !ineq /= => [] [t1] [eq t1k].
1048 move: eq; rewrite F1_der; [by move: t1k ineq; arith | move => eq].
1049 set g := `partial j f o (\h. (x + t1 % basis j) + h % basis i)`.
1050 have := real_mvt0 g `derivative g` h.
1051 "ANTS_TAC".
1052 move => t t_ineq; rewrite has_derivative_alt.
1053 rewrite -g_def diff2_partial_real_diff d2f v_eq rs.
1054 by move: t1k t_ineq ineq; arith.
1055 move => [t2] [t2_ineq] g_eq.
1056 exists t1 t2; rewrite eq; split; last by move: t1k t2_ineq ineq; arith.
1057 set p := `_1 - _2`.
1058 have ->: `p = g h - g (&0)`.
1059 by rewrite -p_def -g_def !o_THM /= VECTOR_MUL_LZERO VECTOR_ADD_RID v_eq.
1060 rewrite g_eq "REAL_ARITH `!a. k * a * h = h * k * a`" !REAL_MUL_ASSOC.
1061 rewrite REAL_EQ_MUL_LCANCEL -g_def; right.
1062 rewrite derivative_translation.
1063 by rewrite diff2_partial_real_diff d2f v_eq rs; move: t1k t2_ineq ineq; arith.
1064 rewrite partial; "AP_THM_TAC"; "AP_TERM_TAC".
1065 by rewrite -eq_ext !o_THM /= "GEN_ALL VECTOR_ADD_RDISTRIB" -!"GEN_ALL VECTOR_ADD_ASSOC".
1066 move: Gh F1_der dF1 F1h G_def F1_def => _ _ _ _ _ _.
1067 have F2h: `!k. F2 k = (\h. (f o (\h. (x + k % basis j) + h % basis i)) h - (f o (\h. x + h % basis i)) h)`.
1068 by rewrite -F2_def !o_THM /= v_eq.
1069 have dF2: `!k. abs k <= r ==> !h. abs h <= r ==> (F2 k) real_differentiable atreal h`.
1070 move => k k_ineq h h_ineq.
1071 rewrite F2h REAL_DIFFERENTIABLE_SUB; rewr ETA_AX.
1072 by rewrite !diff2_imp_real_diff ?d2f ?v_eq ?rs ?in_s.
1073 have F2_der : `!h k. abs h <= r /\ abs k <= r ==>
1074 derivative (F2 k) h = partial i f ((x + k % basis j) + h % basis i) - partial i f (x + h % basis i)`.
1075 move => h k ineq; rewrite F2h derivative_sub; rewr ETA_AX; rewrite ?diff2_imp_real_diff ?d2f ?v_eq ?rs ?in_s //.
1076 rewrite -v_eq [`derivative (f o (\h. x + h % basis i)) h`]derivative_translation 1?derivative_translation;
1077 rewrite ?diff2_imp_real_diff ?d2f ?v_eq ?rs ?in_s // -v_eq.
1078 have eq: `!y e. (f o (\h. y + h % e)) o (\t. h + t) = f o (\t. (y + h % e) + t % e)`.
1079 by rewrite -eq_ext !o_THM /= "GEN_ALL VECTOR_ADD_RDISTRIB" "GEN_ALL VECTOR_ADD_ASSOC".
1080 by rewrite !eq -!partial.
1081 have Gk: `!h k. abs h <= r /\ abs k <= r ==>
1082 (?t3. G h k = h * derivative (F2 k) t3 /\ abs t3 <= abs h)`.
1083 move => h k ineq; rewrite G_eq /=.
1084 have := real_mvt0 `F2 k` `derivative (F2 k)` h.
1085 "ANTS_TAC".
1086 move => t t_ineq; rewrite has_derivative_alt dF2.
1087 by move: ineq t_ineq; arith.
1088 move => [t3] [t3_ineq] eq.
1089 by exists t3; rewrite eq; move: t3_ineq ineq; arith.
1090 have Gkh: `!h k. abs h <= r /\ abs k <= r ==>
1091 (?t3 t4. G h k = h * k * partial j (partial i f) (x + t4 % basis j + t3 % basis i)
1092 /\ abs t3 <= abs h /\ abs t4 <= abs k)`.
1093 move => h k ineq.
1094 move: (Gk h k); rewrite !ineq /= => [] [t3] [eq t3h].
1095 move: eq; rewrite F2_der; [by move: t3h ineq; arith | move => eq].
1096 set g := `partial i f o (\k. (x + t3 % basis i) + k % basis j)`.
1097 have := real_mvt0 g `derivative g` k.
1098 "ANTS_TAC".
1099 move => t t_ineq; rewrite has_derivative_alt.
1100 rewrite -g_def diff2_partial_real_diff d2f rs.
1101 by move: t3h t_ineq ineq; arith.
1102 move => [t4] [t4_ineq] g_eq.
1103 exists t3 t4; rewrite eq; split; last by move: t3h t4_ineq ineq; arith.
1104 set p := `_1 - _2`.
1105 have ->: `p = g k - g (&0)`.
1106 by rewrite -p_def -g_def !o_THM /= VECTOR_MUL_LZERO VECTOR_ADD_RID v_eq.
1107 rewrite g_eq "REAL_ARITH `!a. h * a * k = h * k * a`" !REAL_MUL_ASSOC.
1108 rewrite REAL_EQ_MUL_LCANCEL -g_def; right.
1109 rewrite derivative_translation.
1110 by rewrite diff2_partial_real_diff d2f rs; move: t3h t4_ineq ineq; arith.
1111 rewrite partial; "AP_THM_TAC"; "AP_TERM_TAC".
1112 rewrite -eq_ext !o_THM /= "GEN_ALL VECTOR_ADD_RDISTRIB" -!"GEN_ALL VECTOR_ADD_ASSOC" => y.
1113 by "AP_TERM_TAC"; "VECTOR_ARITH_TAC".
1114 move: Gk F2_der dF2 F2h G_eq F2_def => _ _ _ _ _ _.
1115 have lim0: `(vec 0:real^2) limit_point_of {y | &0 < y$1 /\ &0 < y$2}`.
1116 rewrite limit_point_of OPEN_CONTAINS_BALL SUBSET IN_BALL dist => t [v0t].
1117 move/(_ v0t) => [e] [e0] in_t.
1118 set y := `e / &2 % (vec 1:real^2)`.
1119 have yc: `!i. y$i = e / (&2)`; first by rewrite -y_def VECTOR_MUL_COMPONENT VEC_COMPONENT REAL_MUL_RID.
1120 have ineq: `&0 < e / (&2)`; first by rewrite REAL_LT_DIV e0; arith.
1121 have inf_y: `infnorm y = e / &2`.
1122 by rewrite "GEN_ALL INFNORM_2" !yc "GEN_ALL (CONJUNCT2 REAL_MAX_ACI)" REAL_ABS_REFL REAL_LE_LT ineq.
1123 exists y; split; first by rewrite -INFNORM_EQ_0 inf_y; move: ineq; arith.
1124 split; first by rewrite IN_ELIM_THM /=; exists y; rewrite !yc ineq.
1125 rewrite in_t; apply: REAL_LET_TRANS; exists `e * inv(&2) * sqrt(&2)`; split.
1126 apply: REAL_LE_TRANS; exists `infnorm y * sqrt (&2)`; split.
1127 by rewrite "GEN_ALL REAL_MUL_AC" NORM_SUB "GEN_ALL VECTOR_SUB_RZERO" -DIMINDEX_2 NORM_LE_INFNORM.
1128 by rewrite inf_y real_div -REAL_MUL_ASSOC REAL_LE_REFL.
1129 rewrite -{2}(REAL_MUL_RID e) REAL_LT_LMUL e0 andTb.
1130 rewrite -(REAL_MUL_LINV `&2`) ?REAL_LT_LMUL ?REAL_LT_INV ?andTb; try arith.
1131 have {2}->: `&2 = sqrt (&2 * &2)`; first by rewrite -REAL_POW_2 POW_2_SQRT_ABS; arith.
1132 by rewrite SQRT_MONO_LT; arith.
1133 have lim_ji: `((\y:real^2. lift (G (y$1) (y$2) / (y$1 * y$2))) --> lift (partial j (partial i f) x))
1134 (at (vec 0) within {y | &0 < y$1 /\ &0 < y$2})`.
1135 rewrite LIM_WITHIN => e e_gt0.
1136 move: (pc i j); rewrite "GEN_ALL continuous_at" !dist !o_THM => /(_ e_gt0) [d] [d0] e_ineq.
1137 exists `min r (d / &2)`; rewrite REAL_LT_MIN; split; first by move: r0 d0; arith.
1138 rewrite /= "GEN_ALL VECTOR_SUB_RZERO" => y ineq.
1139 have y0: `&0 < abs (y$1) /\ &0 < abs (y$2)`.
1140 move: ineq; rewrite IN_ELIM_THM /= => [] [] [z] [z_ineq] -> _.
1141 by move: z_ineq; arith.
1142 have yr: `abs (y$1) <= r /\ abs (y$2) <= r /\ abs (y$1) < d / &2 /\ abs (y$2) < d / &2`.
1143 suff: `infnorm y < min r (d / &2)`; first by rewrite "GEN_ALL INFNORM_2"; arith.
1144 by apply: REAL_LET_TRANS; exists `norm y`; rewrite INFNORM_LE_NORM.
1145 have := Gkh `y$1` `y$2`.
1146 rewrite !yr /= => [] [t1] [t2] [G_eq] t_ineq.
1147 rewrite G_eq REAL_MUL_ASSOC "GEN_ALL REAL_MUL_AC" real_div -REAL_MUL_ASSOC REAL_MUL_RINV ?REAL_MUL_RID.
1148 by rewrite REAL_ENTIRE; move: y0; arith.
1149 apply: e_ineq; rewrite "GEN_ALL VECTOR_ADD_SUB".
1150 apply: REAL_LET_TRANS; exists `norm (t2 % basis j:real^N) + norm (t1 % basis i:real^N)`.
1151 rewrite NORM_TRIANGLE andTb !NORM_MUL !NORM_BASIS // !REAL_MUL_RID.
1152 by move: t_ineq yr; arith.
1153 have lim_ij: `((\y:real^2. lift (G (y$1) (y$2) / (y$1 * y$2))) --> lift (partial i (partial j f) x))
1154 (at (vec 0) within {y | &0 < y$1 /\ &0 < y$2})`.
1155 rewrite LIM_WITHIN => e e_gt0.
1156 move: (pc j i); rewrite "GEN_ALL continuous_at" !dist !o_THM => /(_ e_gt0) [d] [d0] e_ineq.
1157 exists `min r (d / &2)`; rewrite REAL_LT_MIN; split; first by move: r0 d0; arith.
1158 rewrite /= "GEN_ALL VECTOR_SUB_RZERO" => y ineq.
1159 have y0: `&0 < abs (y$1) /\ &0 < abs (y$2)`.
1160 move: ineq; rewrite IN_ELIM_THM /= => [] [] [z] [z_ineq] -> _.
1161 by move: z_ineq; arith.
1162 have yr: `abs (y$1) <= r /\ abs (y$2) <= r /\ abs (y$1) < d / &2 /\ abs (y$2) < d / &2`.
1163 suff: `infnorm y < min r (d / &2)`; first by rewrite "GEN_ALL INFNORM_2"; arith.
1164 by apply: REAL_LET_TRANS; exists `norm y`; rewrite INFNORM_LE_NORM.
1165 have := Ghk `y$1` `y$2`.
1166 rewrite !yr /= => [] [t1] [t2] [G_eq] t_ineq.
1167 rewrite G_eq REAL_MUL_ASSOC "GEN_ALL REAL_MUL_AC" real_div -REAL_MUL_ASSOC REAL_MUL_RINV ?REAL_MUL_RID.
1168 by rewrite REAL_ENTIRE; move: y0; arith.
1169 apply: e_ineq; rewrite "GEN_ALL VECTOR_ADD_SUB".
1170 apply: REAL_LET_TRANS; exists `norm (t1 % basis j:real^N) + norm (t2 % basis i:real^N)`.
1171 rewrite NORM_TRIANGLE andTb !NORM_MUL !NORM_BASIS // !REAL_MUL_RID.
1172 by move: t_ineq yr; arith.
1173 rewrite -LIFT_EQ; apply (LIM_UNIQUE `at (vec 0:real^2) within {y:real^2 | &0 < y$1 /\ &0 < y$2}`).
1174 exists `\y:real^2. lift (G (y$1) (y$2) / (y$1 * y$2))`.
1175 by rewrite "GEN_ALL TRIVIAL_LIMIT_WITHIN" negbK lim0 andTb.
1176 Qed.
1177
1178
1179
1180 (* m_cell_domain *)
1181 "let m_cell_domain = new_definition `m_cell_domain (x:real^N, z:real^N) (y:real^N) (w:real^N) <=>
1182 !i. i IN 1..dimindex (:N) ==> x$i <= y$i /\ y$i <= z$i /\ max (y$i - x$i) (z$i - y$i) <= w$i`".
1183
1184 "let m_bounded_on_int = new_definition `m_bounded_on_int (f:real^N->real) domain f_bounds <=>
1185 !x. x IN interval [domain] ==> interval_arith (f x) f_bounds`".
1186
1187 "let diff2_domain = new_definition `diff2_domain domain f <=>
1188 !x. x IN interval [domain] ==> diff2 f x`".
1189
1190 "let diff2c_domain = new_definition `diff2c_domain domain f <=>
1191 !x. x IN interval [domain] ==> diff2c f x`".
1192
1193 Lemma diff2c_domain_alt f domain : `diff2c_domain domain f <=> diff2_domain domain f /\
1194 (!x. x IN interval [domain] ==> !i j. (lift o partial2 j i f) continuous at x)`.
1195 Proof.
1196 rewrite diff2c_domain diff2c diff2_domain; split => [h1|[h1 h2] x h3].
1197 by split => x /h1 /=.
1198 by move: (h2 h3) (h1 h3) => /=.
1199 Qed.
1200
1201 Lemma y_in_domain domain y w : `m_cell_domain domain y w ==> y IN interval [domain]`.
1202 case: domain => x z; rewrite m_cell_domain "GEN_ALL IN_INTERVAL" IN_NUMSEG => ineqs i.
1203 by move/ineqs => /=.
1204 Qed.
1205
1206
1207 Lemma domain_width p domain y w : `m_cell_domain domain y (w:real^N) ==>
1208 p IN interval [domain] ==>
1209 !i. i IN 1..dimindex (:N) ==> abs (p$i - y$i) <= w$i`.
1210 case: domain => x z; rewrite m_cell_domain => ineqs p_in i i_in.
1211 by move: p_in (ineqs i_in); rewrite "GEN_ALL IN_INTERVAL" -IN_NUMSEG => /(_ i_in); arith.
1212 Qed.
1213
1214
1215 Lemma sum_swap1 g n : `sum (1..n) (\i. sum (i + 1..n) (\j. g i j)) =
1216 sum (1..n) (\i. sum (1..i - 1) (\j. g j i))`.
1217 Proof.
1218 rewrite !SUM_SUM_PRODUCT ?FINITE_NUMSEG //= !IN_NUMSEG.
1219 set s1 := `{i, j | (1 <= i /\ i <= n) /\ i + 1 <= j /\ j <= n}`.
1220 set s2 := `{i, j | (1 <= i /\ i <= n) /\ 1 <= j /\ j <= i - 1}`.
1221 set f := `\(i,j):num#num. j, i`.
1222 have ->: `s1 = IMAGE f s2`.
1223 rewrite -s1_def -s2_def -f_def EXTENSION IN_IMAGE !IN_ELIM_THM /= => p; split.
1224 move => [i] [j] [ineq] p_eq.
1225 by exists `j, i`; rewrite p_eq /=; exists j i; move: ineq; arith.
1226 move => [p1] [p_eq] [i] [j] [ineq] p1_eq.
1227 by exists j i; rewrite p_eq p1_eq /=; move: ineq; arith.
1228 have ->: `(\(i,j). g j i) = (\(i,j). g i j) o f`.
1229 by rewrite -eq_ext o_THM -f_def; case.
1230 apply SUM_IMAGE; case => i1 j1; case => i2 j2.
1231 by rewrite -f_def /= !PAIR_EQ => [] [_] [_] [-> ->].
1232 Qed.
1233
1234
1235 (* Computation of the taylor error *)
1236 Lemma m_taylor_error_eq f domain w error : `diff2c_domain domain f ==>
1237 (m_taylor_error f domain (w:real^N) error <=>
1238 (!x. x IN interval [domain] ==>
1239 sum (1..dimindex (:N)) (\i. w$i * (w$i * abs (partial2 i i f x)
1240 + &2 * sum (1..i - 1) (\j. w$j * abs (partial2 j i f x)))) <= error))`.
1241 Proof.
1242 rewrite diff2c_domain m_taylor_error => d2f.
1243 have eq: `!g1 g2. (!x. x IN interval [domain] ==> g1 x = g2 x) ==>
1244 ((!x. x IN interval [domain] ==> g1 x <= error) <=> (!x. x IN interval [domain] ==> g2 x <= error))`.
1245 move => g1 g2 eq; split => cond x Px.
1246 by rewrite -eq // cond.
1247 by rewrite eq // cond.
1248 apply: eq => x /d2f d2fx.
1249 set g := `\i j. w$i * w$j * abs (partial2 j i f x)`.
1250 set n := `dimindex (:N)`.
1251 set s1 := `sum _1 _2`.
1252 have s1_eq: `s1 = sum (1..n) (\i. sum (1..n) (\j. g i j))`.
1253 rewrite -s1_def; apply SUM_EQ => i /= i_in.
1254 by rewrite -SUM_LMUL /= -g_def partial2; apply SUM_EQ.
1255 rewrite REAL_MUL_2 !REAL_ADD_LDISTRIB -SUM_LMUL REAL_ADD_ASSOC SUM_ADD_NUMSEG /=.
1256 set s2 := `sum _1 _2`.
1257 have s2_eq: `s2 = sum (1..n) (\i. g i i + sum (1..i - 1) (\j. g i j))`; first by rewrite -s2_def -g_def.
1258 set s3 := `sum _1 _2`.
1259 have s3_eq: `s3 = sum (1..n) (\i. sum (1..i - 1) (\j. g i j))`; first by rewrite -s3_def -g_def.
1260 move: s1_def s2_def s3_def => _ _ _.
1261 suff ->: `s3 = sum (1..n) (\i. sum (i + 1..n) (\j. g i j))`.
1262 rewrite s2_eq -SUM_ADD_NUMSEG /= s1_eq; apply SUM_EQ => i /=; rewrite IN_NUMSEG => i_ineq.
1263 rewrite "REAL_ARITH `!a b c. (a + b) + c = (a + c) + b`" -(SUM_SING_NUMSEG `g i` i); rewr ETA_AX.
1264 rewrite SUM_COMBINE_R ?i_ineq; first by arith.
1265 by rewrite "GEN_ALL REAL_ADD_AC" SUM_COMBINE_L //; move: i_ineq; arith.
1266 rewrite s3_eq sum_swap1; apply SUM_EQ => i _ /=; apply SUM_EQ => j _ /=.
1267 rewrite -g_def /= "REAL_ARITH `!a b c. a * b * c = b * a * c`" !REAL_EQ_MUL_LCANCEL; right; right.
1268 by rewrite mixed_second_partials.
1269 Qed.
1270
1271
1272 (* Taylor bounds *)
1273 Lemma diff2_derivative2_bound domain y w p f dd_bound :
1274 `m_cell_domain domain y (w:real^N) ==>
1275 p IN interval [domain] ==>
1276 diff2_domain domain f ==>
1277 m_taylor_error f domain w dd_bound ==>
1278 (!t. interval_arith t (&0, &1) ==>
1279 abs (nth_derivative 2 (f o (\t. y + t % (p - y))) t) <= dd_bound)`.
1280 Proof.
1281 rewrite diff2_domain m_taylor_error => domainH p_in df boundedH t t_in.
1282 have pt_in : `y + t % (p - y) IN interval [domain]`.
1283 rewrite "VECTOR_ARITH `y + t % (p - y) = (&1 - t) % y + t % p:real^N`" IN_CONVEX_SET.
1284 by rewrite (y_in_domain domainH) p_in -interval_arith t_in pair_eq CONVEX_INTERVAL.
1285 rewrite diff2_dir_derivative2 ?df //.
1286 rewrite o_THM /=; move: (boundedH pt_in).
1287 set s1 := `sum _1 _2`; set s2 := `sum _1 _2` => i1.
1288 apply: REAL_LE_TRANS; exists s1; rewrite i1 andbT -s1_def -s2_def.
1289 rewrite SUM_ABS_LE FINITE_NUMSEG andTb => i i_ineq /=.
1290 rewrite -SUM_LMUL SUM_ABS_LE FINITE_NUMSEG andTb => j j_ineq /=.
1291 by rewrite !REAL_ABS_MUL !REAL_LE_MUL2 ?REAL_LE_MUL !REAL_ABS_POS // VECTOR_SUB_COMPONENT;
1292 rewrite (domain_width domainH p_in) // REAL_LE_REFL.
1293 Qed.
1294
1295
1296 Lemma m_taylor_error_lemma domain y w p f dd_bound :
1297 `m_cell_domain domain y (w:real^N) ==>
1298 p IN interval [domain] ==>
1299 diff2_domain domain f ==>
1300 m_taylor_error f domain w dd_bound ==>
1301 abs (f p - (f y + sum (1..dimindex (:N)) (\i. (p - y)$i * partial i f y))) <= dd_bound / &2`.
1302 rewrite diff2_domain; move => domainH p_in df taylor_error.
1303 have pt_in : `!t. interval_arith t (&0, &1) ==> y + t % (p - y) IN interval [domain]`.
1304 move => t t_in; rewrite "VECTOR_ARITH `y + t % (p - y) = (&1 - t) % y + t % p:real^N`" IN_CONVEX_SET.
1305 by rewrite (y_in_domain domainH) p_in -interval_arith t_in pair_eq CONVEX_INTERVAL.
1306 move: (real_taylor2_bound `f o (\t. y + t % (p - y))` dd_bound).
1307 "ANTS_TAC"; first by rewrite nth_diff_strong_int => t t_in; rewrite diff2_dir df pt_in.
1308 "ANTS_TAC"; first by apply: (diff2_derivative2_bound domainH); rewrite diff2_domain.
1309 rewrite !o_THM /= VECTOR_MUL_LID VECTOR_MUL_LZERO VECTOR_ADD_RID "GEN_ALL VECTOR_SUB_ADD2".
1310 rewrite diff2_dir_derivative ?df ?pt_in ?interval_arith; first by arith.
1311 by rewrite o_THM /= VECTOR_MUL_LZERO VECTOR_ADD_RID.
1312 Qed.
1313
1314
1315
1316 Lemma m_taylor_upper_bound domain y w f dd_bound hi hi_bound :
1317 `m_cell_domain domain y (w:real^N) ==>
1318 diff2_domain domain f ==>
1319 m_taylor_error f domain w dd_bound ==>
1320 f y <= hi ==>
1321 hi + sum(1..dimindex (:N)) (\i. w$i * abs (partial i f y)) + dd_bound / &2 <= hi_bound ==>
1322 !p. p IN interval [domain] ==> f p <= hi_bound`.
1323 move => domainH df errorH f_bound total_bound p p_in.
1324 move: (m_taylor_error_lemma domainH p_in df errorH).
1325 move/"REAL_ARITH `!x y e. abs (x - y) <= e ==> x <= y + e`".
1326 set s := `sum _1 _2` => ineq.
1327 apply: REAL_LE_TRANS; exists `(f y + s) + dd_bound / &2`; rewrite ineq andTb.
1328 apply: "REWRITE_RULE[GSYM IMP_IMP] REAL_LE_TRANS" total_bound.
1329 rewrite REAL_ADD_ASSOC REAL_LE_RADD REAL_LE_ADD2 f_bound andTb.
1330 apply: REAL_LE_TRANS; exists `abs s`; rewrite REAL_ABS_LE andTb.
1331 rewrite -s_def SUM_ABS_LE FINITE_NUMSEG andTb => i i_ineq /=.
1332 by rewrite REAL_ABS_MUL REAL_LE_MUL2 !REAL_ABS_POS REAL_LE_REFL VECTOR_SUB_COMPONENT (domain_width domainH).
1333 Qed.
1334
1335
1336 Lemma m_taylor_lower_bound domain y w f dd_bound lo lo_bound :
1337 `m_cell_domain domain y (w:real^N) ==>
1338 diff2_domain domain f ==>
1339 m_taylor_error f domain w dd_bound ==>
1340 lo <= f y ==>
1341 lo_bound <= lo - (sum(1..dimindex (:N)) (\i. w$i * abs (partial i f y)) + dd_bound / &2) ==>
1342 !p. p IN interval [domain] ==> lo_bound <= f p`.
1343 move => domainH df errorH f_bound total_bound p p_in.
1344 move: (m_taylor_error_lemma domainH p_in df errorH).
1345 move/"REAL_ARITH `!x y e. abs (x - y) <= e ==> y - e <= x`".
1346 set s := `sum _1 _2` => ineq.
1347 apply: REAL_LE_TRANS; exists `(f y + s) - dd_bound / &2`; rewrite ineq andbT.
1348 apply: ("REWRITE_RULE[GSYM IMP_IMP] REAL_LE_TRANS" total_bound).
1349 rewrite !real_sub REAL_NEG_ADD REAL_ADD_ASSOC REAL_LE_RADD REAL_LE_ADD2 f_bound andTb.
1350 apply: REAL_LE_TRANS; exists `--abs s`; rewrite REAL_LE_NEG2; split; last by arith.
1351 rewrite -s_def SUM_ABS_LE FINITE_NUMSEG andTb => i i_ineq /=.
1352 by rewrite REAL_ABS_MUL REAL_LE_MUL2 !REAL_ABS_POS REAL_LE_REFL VECTOR_SUB_COMPONENT (domain_width domainH).
1353 Qed.
1354
1355
1356 Lemma m_taylor_bounds domain y w f dd_bound lo hi err_bound lo_bound hi_bound :
1357 `m_cell_domain domain y (w:real^N) ==>
1358 diff2_domain domain f ==>
1359 m_taylor_error f domain w dd_bound ==>
1360 interval_arith (f y) (lo, hi) ==>
1361 sum(1..dimindex (:N)) (\i. w$i * abs(partial i f y)) + dd_bound / &2 <= err_bound ==>
1362 lo_bound <= lo - err_bound ==>
1363 hi + err_bound <= hi_bound ==>
1364 m_bounded_on_int f domain (lo_bound, hi_bound)`.
1365 rewrite m_bounded_on_int !interval_arith => domainH df errorH [f_lo f_hi] err lo_ineq hi_ineq p p_in.
1366 move: (m_taylor_lower_bound domainH df errorH f_lo lo_bound) => ->.
1367 rewrite p_in andbT; apply: REAL_LE_TRANS; exists `lo - err_bound`.
1368 by rewrite lo_ineq andTb !real_sub REAL_LE_ADD2 REAL_LE_REFL REAL_LE_NEG2.
1369 move: (m_taylor_upper_bound domainH df errorH f_hi hi_bound) => -> //.
1370 rewrite p_in andbT; apply: REAL_LE_TRANS; exists `hi + err_bound`.
1371 by rewrite hi_ineq andbT REAL_LE_LADD.
1372 Qed.
1373
1374
1375 (* Taylor partial derivative bounds *)
1376 Lemma diff2_derivative_partial_bound domain y w p f i d_bound :
1377 `m_cell_domain domain y (w:real^N) ==>
1378 p IN interval [domain] ==>
1379 diff2_domain domain f ==>
1380 m_taylor_partial_error f i domain w d_bound ==>
1381 (!t. interval_arith t (&0, &1) ==>
1382 abs (derivative (partial i f o (\t. y + t % (p - y))) t) <= d_bound)`.
1383 Proof.
1384 rewrite diff2_domain m_taylor_partial_error => domainH p_in df boundedH t t_in.
1385 have pt_in : `y + t % (p - y) IN interval [domain]`.
1386 rewrite "VECTOR_ARITH `y + t % (p - y) = (&1 - t) % y + t % p:real^N`" IN_CONVEX_SET.
1387 by rewrite (y_in_domain domainH) p_in -interval_arith t_in pair_eq CONVEX_INTERVAL.
1388 rewrite diff2_derivative_partial ?df //.
1389 apply: "REWRITE_RULE[GSYM IMP_IMP] REAL_LE_TRANS" (boundedH pt_in).
1390 rewrite SUM_ABS_LE FINITE_NUMSEG andTb => j j_ineq /=.
1391 rewrite REAL_ABS_MUL o_THM /= REAL_LE_MUL2 !REAL_ABS_POS REAL_LE_REFL VECTOR_SUB_COMPONENT.
1392 by rewrite (domain_width domainH).
1393 Qed.
1394
1395
1396 Lemma m_taylor_partial_error_lemma domain y w p f i dd_bound :
1397 `m_cell_domain domain y (w:real^N) ==>
1398 p IN interval [domain] ==>
1399 diff2_domain domain f ==>
1400 m_taylor_partial_error f i domain w dd_bound ==>
1401 abs (partial i f p - partial i f y) <= dd_bound`.
1402 Proof.
1403 rewrite diff2_domain; move => domainH p_in df partial_error.
1404 have pt_in : `!t. interval_arith t (&0, &1) ==> y + t % (p - y) IN interval [domain]`.
1405 move => t t_in; rewrite "VECTOR_ARITH `y + t % (p - y) = (&1 - t) % y + t % p:real^N`" IN_CONVEX_SET.
1406 by rewrite (y_in_domain domainH) p_in -interval_arith t_in pair_eq CONVEX_INTERVAL.
1407 move: (real_taylor1_bound `partial i f o (\t. y + t % (p - y))` dd_bound).
1408 "ANTS_TAC".
1409 move => t t_in; rewrite diff2_real_diff_partial ?df ?pt_in // (diff2_derivative_partial_bound domainH) //.
1410 by rewrite diff2_domain.
1411 by rewrite !o_THM /= VECTOR_MUL_LID VECTOR_MUL_LZERO VECTOR_ADD_RID "GEN_ALL VECTOR_SUB_ADD2".
1412 Qed.
1413
1414
1415
1416 Lemma m_taylor_upper_partial_bound domain y w f i dd_bound hi hi_bound :
1417 `m_cell_domain domain y (w:real^N) ==>
1418 diff2_domain domain f ==>
1419 m_taylor_partial_error f i domain w dd_bound ==>
1420 partial i f y <= hi ==>
1421 hi + dd_bound <= hi_bound ==>
1422 !p. p IN interval [domain] ==> partial i f p <= hi_bound`.
1423 Proof.
1424 move => domainH df errorH df_bound total_bound p p_in.
1425 move: (m_taylor_partial_error_lemma domainH p_in df errorH).
1426 move/"REAL_ARITH `!x y e. abs (x - y) <= e ==> x <= y + e`" => ineq.
1427 apply: ("REWRITE_RULE[GSYM IMP_IMP] REAL_LE_TRANS" ineq).
1428 apply: "REWRITE_RULE[GSYM IMP_IMP] REAL_LE_TRANS" total_bound.
1429 by rewrite REAL_LE_ADD2 REAL_LE_REFL.
1430 Qed.
1431
1432
1433 Lemma m_taylor_lower_partial_bound domain y w f i dd_bound lo lo_bound :
1434 `m_cell_domain domain y (w:real^N) ==>
1435 diff2_domain domain f ==>
1436 m_taylor_partial_error f i domain w dd_bound ==>
1437 lo <= partial i f y ==>
1438 lo_bound <= lo - dd_bound ==>
1439 !p. p IN interval [domain] ==> lo_bound <= partial i f p`.
1440 Proof.
1441 move => domainH df errorH df_bound total_bound p p_in.
1442 move: (m_taylor_partial_error_lemma domainH p_in df errorH).
1443 move/"REAL_ARITH `!x y e. abs (x - y) <= e ==> y - e <= x`" => ineq.
1444 apply: "REWRITE_RULE[GSYM IMP_IMP] REAL_LE_TRANS" ineq.
1445 apply: ("REWRITE_RULE[GSYM IMP_IMP] REAL_LE_TRANS" total_bound).
1446 by rewrite !real_sub REAL_LE_ADD2 REAL_LE_REFL.
1447 Qed.
1448
1449
1450 Lemma m_taylor_partial_bounds domain y w f i dd_bound lo hi lo_bound hi_bound :
1451 `m_cell_domain domain y (w:real^N) ==>
1452 diff2_domain domain f ==>
1453 m_taylor_partial_error f i domain w dd_bound ==>
1454 interval_arith (partial i f y) (lo, hi) ==>
1455 lo_bound <= lo - dd_bound ==>
1456 hi + dd_bound <= hi_bound ==>
1457 m_bounded_on_int (partial i f) domain (lo_bound, hi_bound)`.
1458 rewrite m_bounded_on_int !interval_arith => domainH df errorH [df_lo df_hi] lo_ineq hi_ineq p p_in.
1459 move: (m_taylor_lower_partial_bound domainH df errorH df_lo lo_bound) => -> //.
1460 by move: (m_taylor_upper_partial_bound domainH df errorH df_hi hi_bound) => ->.
1461 Qed.
1462
1463
1464 End Taylor.
1465
1466
1467
1468 (* diff2 arithmetic *)
1469 Section Diff2Arith.
1470
1471 Variables f g : `:real^N -> real`.
1472 Variable x : `:real^N`.
1473 Variable domain : `:real^N#real^N`.
1474
1475
1476 Lemma differentiable_local_at s f g x :
1477 `f differentiable at x ==> open s ==> x IN s ==> (!y. y IN s ==> g y = f y) ==>
1478 g differentiable at x`.
1479 rewrite OPEN_CONTAINS_BALL => df open_s xs eq.
1480 move: (open_s xs) => [d] [d0]; rewrite SUBSET IN_BALL => in_ball.
1481 apply: (DIFFERENTIABLE_TRANSFORM_AT f); rewrite df andbT.
1482 by exists d; rewrite d0 andTb => z dzx; rewrite eq // in_ball DIST_SYM.
1483 Qed.
1484
1485
1486 Section Point.
1487
1488 (* scale *)
1489 Lemma diff2_scale f c : `diff2 f x ==> diff2 (\x. c * f x) x`.
1490 Proof.
1491 rewrite !diff2 => [] [s] [open_s] [xs] df.
1492 exists s; rewrite open_s xs !andTb => z zs.
1493 rewrite f_lift_scale DIFFERENTIABLE_CMUL ?andTb; first by rewr ETA_AX; rewrite df.
1494 move => i; apply: (differentiable_local_at s `lift o (\x. c * partial i f x)`).
1495 rewrite open_s zs f_lift_scale DIFFERENTIABLE_CMUL ?andTb; first by rewr !ETA_AX; rewrite df.
1496 by move => y ys; rewrite !o_THM partial_scale ?df // LIFT_CMUL.
1497 Qed.
1498
1499 (* neg *)
1500 Lemma diff2_neg f : `diff2 f x ==> diff2 (\x. --f x) x`.
1501 Proof. by move/(diff2_scale f `--(&1)`); rewrite -REAL_NEG_MINUS1. Qed.
1502
1503
1504 (* Composite *)
1505 Section Composite.
1506
1507
1508 Lemma has_derivative_uni_compose u f u' f' x : `(lift o f has_derivative f') (at x) ==>
1509 (u has_real_derivative u') (atreal (f x)) ==>
1510 (lift o u o f has_derivative (\x. u' % f' x)) (at x)`.
1511 move => df du.
1512 have ->: `lift o u o f = (lift o u o drop) o (lift o f)`.
1513 by rewrite -eq_ext !o_THM LIFT_DROP.
1514 have ->: `(\x. u' % f' x) = (\x. u' % x) o f'`; first by rewrite -eq_ext !o_THM /=.
1515 by rewrite DIFF_CHAIN_AT o_THM -"GEN_ALL HAS_REAL_FRECHET_DERIVATIVE_AT".
1516 Qed.
1517
1518
1519 Lemma diff_uni_compose u f x : `lift o f differentiable at x ==>
1520 u real_differentiable atreal (f x) ==>
1521 lift o u o f differentiable at x`.
1522 rewrite !differentiable real_differentiable => [] [f'] df [u'] du.
1523 by exists `\x. u' % f' x`; apply has_derivative_uni_compose.
1524 Qed.
1525
1526
1527 Lemma diff2_uni_compose u f : `diff2 f x ==> nth_diff_strong 2 u (f x) ==> diff2 (u o f) x`.
1528 Proof.
1529 rewrite !diff2 nth_diff_strong2_eq => [] [s] [open_s] [xs] df [t] [open_t] [fxt] du.
1530 set r := `{z | z IN s /\ (lift o f) z IN (IMAGE lift t)}`.
1531 have open_r : `open r`.
1532 rewrite -r_def CONTINUOUS_OPEN_PREIMAGE -REAL_OPEN open_t open_s !andbT.
1533 apply DIFFERENTIABLE_IMP_CONTINUOUS_ON; rewrite differentiable_on => y ys; rewr ETA_AX.
1534 by rewrite DIFFERENTIABLE_AT_WITHIN df.
1535 exists r; rewrite open_r -r_def !IN_ELIM_THM /= o_THM LIFT_IN_IMAGE_LIFT; split; first by exists x.
1536 move => y [z] [[zs] fzt] ->.
1537 rewrite diff_uni_compose ?df ?du // andTb => i.
1538 apply differentiable_local_at; exists r `lift o (\y. derivative u (f y) * partial i f y)`.
1539 rewrite open_r differentiable_mul ?andTb.
1540 by rewrite -(o_THM `derivative u`); rewr !ETA_AX; rewrite diff_uni_compose ?df // du.
1541 rewrite -r_def !IN_ELIM_THM /= !o_THM !LIFT_IN_IMAGE_LIFT; split; first by exists z.
1542 move => y [p] [[ps] fpt] ->.
1543 by rewrite partial_uni_compose ?df ?du.
1544 Qed.
1545
1546 (* abs *)
1547 Lemma diff2_abs_pos_compose : `&0 < f x ==> diff2 f x ==> diff2 (abs o f) x`.
1548 Proof. by move => /diff2_abs_pos du df; rewrite diff2_uni_compose. Qed.
1549
1550 Lemma diff2_abs_neg_compose : `f x < &0 ==> diff2 f x ==> diff2 (abs o f) x`.
1551 Proof. by move => /diff2_abs_neg du df; rewrite diff2_uni_compose. Qed.
1552
1553 (* pow *)
1554 Lemma diff2_pow_compose n : `diff2 f x ==> diff2 ((\x. x pow n) o f) x`.
1555 Proof. by move => df; rewrite diff2_uni_compose diff2_pow_x. Qed.
1556
1557 (* inv *)
1558 Lemma diff2_inv_compose : `~(f x = &0) ==> diff2 f x ==> diff2 (inv o f) x`.
1559 Proof. by move => /diff2_inv du df; rewrite diff2_uni_compose. Qed.
1560
1561 (* sqrt *)
1562 Lemma diff2_sqrt_compose : `&0 < f x ==> diff2 f x ==> diff2 (sqrt o f) x`.
1563 Proof. by move => /diff2_sqrt du df; rewrite diff2_uni_compose. Qed.
1564
1565 (* atn *)
1566 Lemma diff2_atn_compose : `diff2 f x ==> diff2 (atn o f) x`.
1567 Proof. by move => df; rewrite diff2_uni_compose diff2_atn. Qed.
1568
1569 (* cos *)
1570 Lemma diff2_cos_compose : `diff2 f x ==> diff2 (cos o f) x`.
1571 Proof. by move => df; rewrite diff2_uni_compose diff2_cos. Qed.
1572
1573 (* sin *)
1574 Lemma diff2_sin_compose : `diff2 f x ==> diff2 (sin o f) x`.
1575 Proof. by move => df; rewrite diff2_uni_compose diff2_sin. Qed.
1576
1577 (* exp *)
1578 Lemma diff2_exp_compose : `diff2 f x ==> diff2 (exp o f) x`.
1579 Proof. by move => df; rewrite diff2_uni_compose diff2_exp. Qed.
1580
1581 (* log *)
1582 Lemma diff2_log_compose : `&0 < f x ==> diff2 f x ==> diff2 (log o f) x`.
1583 Proof. by move => /diff2_log du df; rewrite diff2_uni_compose. Qed.
1584
1585 (* acs *)
1586 Lemma diff2_acs_compose : `abs (f x) < &1 ==> diff2 f x ==> diff2 (acs o f) x`.
1587 Proof. by move => /diff2_acs du df; rewrite diff2_uni_compose. Qed.
1588
1589 (* asn *)
1590 Lemma diff2_asn_compose : `abs (f x) < &1 ==> diff2 f x ==> diff2 (asn o f) x`.
1591 Proof. by move => /diff2_asn du df; rewrite diff2_uni_compose. Qed.
1592
1593 (* matan *)
1594 Lemma diff2_matan_compose : `-- &1 < f x ==> diff2 f x ==> diff2 (matan o f) x`.
1595 Proof. by move => /diff2_matan du df; rewrite diff2_uni_compose. Qed.
1596
1597 End Composite.
1598
1599
1600 (* Binary operations *)
1601
1602 (* add *)
1603 Lemma diff2_add f g : `diff2 f x ==> diff2 g x ==> diff2 (\x. f x + g x) x`.
1604 Proof.
1605 rewrite !diff2 => [] [s] [open_s] [xs] df [t] [open_t] [ys] dg.
1606 exists `s INTER t`; rewrite OPEN_INTER // !IN_INTER xs ys !andTb => z [zs zt].
1607 rewrite f_lift_add DIFFERENTIABLE_ADD ?andTb.
1608 by rewr ETA_AX; rewrite df // dg.
1609 move => i; apply: (differentiable_local_at `s INTER t` `lift o (\x. partial i f x + partial i g x)`).
1610 rewrite OPEN_INTER // !IN_INTER zt zs f_lift_add DIFFERENTIABLE_ADD ?andTb.
1611 by rewr !ETA_AX; rewrite df // dg.
1612 by move => y [ys yt]; rewrite !o_THM partial_add ?df ?dg // LIFT_ADD.
1613 Qed.
1614
1615
1616 (* sub *)
1617 Lemma diff2_sub f g : `diff2 f x ==> diff2 g x ==> diff2 (\x. f x - g x) x`.
1618 Proof. by move => d2f d2g; rewrite real_sub diff2_add // diff2_neg. Qed.
1619
1620 (* mul *)
1621 Lemma diff2_mul f g : `diff2 f x ==> diff2 g x ==> diff2 (\x. f x * g x) x`.
1622 rewrite !diff2 => [] [s] [open_s] [xs] df [t] [open_t] [ys] dg.
1623 exists `s INTER t`; rewrite OPEN_INTER // !IN_INTER xs ys !andTb => z [zs zt].
1624 rewrite differentiable_mul ?df ?dg // andTb => i.
1625 apply: (differentiable_local_at `s INTER t` `lift o (\x. partial i f x * g x + f x * partial i g x)`).
1626 rewrite OPEN_INTER // !IN_INTER zt zs f_lift_add DIFFERENTIABLE_ADD ?andTb.
1627 by rewr !ETA_AX; rewrite !differentiable_mul; rewr ETA_AX; rewrite ?df ?dg.
1628 by move => y [ys yt]; rewrite !o_THM partial_mul ?df ?dg // LIFT_ADD.
1629 Qed.
1630
1631
1632 End Point.
1633
1634
1635 Section Domain.
1636
1637 Hypothesis d2f : `diff2_domain domain f`.
1638
1639 (* scale *)
1640 Lemma diff2_domain_scale c : `diff2_domain domain (\x. c * f x)`.
1641 Proof. by move: d2f; rewrite !diff2_domain => d2f x x_in; rewrite diff2_scale d2f. Qed.
1642
1643 (* neg *)
1644 Lemma diff2_domain_neg : `diff2_domain domain (\x. --f x)`.
1645 Proof. by move: d2f; rewrite !diff2_domain => d2f x x_in; rewrite diff2_neg d2f. Qed.
1646
1647 Variable bounds : `:real#real`.
1648
1649 (* inv *)
1650 Lemma diff2_domain_inv_compose : `m_bounded_on_int f domain bounds ==>
1651 interval_not_zero bounds ==> diff2_domain domain (inv o f)`.
1652 move: d2f; rewrite m_bounded_on_int !diff2_domain => d2f ineq n0 x x_in.
1653 by rewrite diff2_inv_compose d2f // andbT (interval_arith_not_zero (ineq x_in)).
1654 Qed.
1655
1656 (* sqrt *)
1657 Lemma diff2_domain_sqrt_compose : `m_bounded_on_int f domain bounds ==>
1658 interval_pos bounds ==> diff2_domain domain (sqrt o f)`.
1659 Proof.
1660 move: d2f; rewrite m_bounded_on_int !diff2_domain => d2f ineq n0 x x_in.
1661 by rewrite diff2_sqrt_compose d2f // andbT (interval_arith_pos (ineq x_in)).
1662 Qed.
1663
1664 (* abs *)
1665 Lemma diff2_domain_abs_pos_compose : `m_bounded_on_int f domain bounds ==>
1666 interval_pos bounds ==> diff2_domain domain (abs o f)`.
1667 Proof.
1668 move: d2f; rewrite m_bounded_on_int !diff2_domain => d2f ineq n0 x x_in.
1669 by rewrite diff2_abs_pos_compose d2f // andbT (interval_arith_pos (ineq x_in)).
1670 Qed.
1671
1672 Lemma diff2_domain_abs_neg_compose : `m_bounded_on_int f domain bounds ==>
1673 interval_neg bounds ==> diff2_domain domain (abs o f)`.
1674 Proof.
1675 move: d2f; rewrite m_bounded_on_int !diff2_domain => d2f ineq n0 x x_in.
1676 by rewrite diff2_abs_neg_compose d2f // andbT (interval_arith_neg (ineq x_in)).
1677 Qed.
1678
1679 (* pow *)
1680 Lemma diff2_domain_pow_compose n : `diff2_domain domain ((\x. x pow n) o f)`.
1681 Proof. by move: d2f; rewrite !diff2_domain => d2f x x_in; rewrite diff2_pow_compose d2f. Qed.
1682
1683 (* atn *)
1684 Lemma diff2_domain_atn_compose : `diff2_domain domain (atn o f)`.
1685 Proof. by move: d2f; rewrite !diff2_domain => d2f x x_in; rewrite diff2_atn_compose d2f. Qed.
1686
1687 (* cos *)
1688 Lemma diff2_domain_cos_compose : `diff2_domain domain (cos o f)`.
1689 Proof. by move: d2f; rewrite !diff2_domain => d2f x x_in; rewrite diff2_cos_compose d2f. Qed.
1690
1691 (* sin *)
1692 Lemma diff2_domain_sin_compose : `diff2_domain domain (sin o f)`.
1693 Proof. by move: d2f; rewrite !diff2_domain => d2f x x_in; rewrite diff2_sin_compose d2f. Qed.
1694
1695 (* exp *)
1696 Lemma diff2_domain_exp_compose : `diff2_domain domain (exp o f)`.
1697 Proof. by move: d2f; rewrite !diff2_domain => d2f x x_in; rewrite diff2_exp_compose d2f. Qed.
1698
1699 (* log *)
1700 Lemma diff2_domain_log_compose : `m_bounded_on_int f domain bounds ==>
1701 interval_pos bounds ==> diff2_domain domain (log o f)`.
1702 Proof.
1703 move: d2f; rewrite m_bounded_on_int !diff2_domain => d2f ineq n0 x x_in.
1704 by rewrite diff2_log_compose d2f // andbT (interval_arith_pos (ineq x_in)).
1705 Qed.
1706
1707 (* acs *)
1708 Lemma diff2_domain_acs_compose : `m_bounded_on_int f domain bounds ==>
1709 iabs bounds < &1 ==> diff2_domain domain (acs o f)`.
1710 Proof.
1711 move: d2f; rewrite m_bounded_on_int !diff2_domain => d2f ineq n0 x x_in.
1712 by rewrite diff2_acs_compose d2f // andbT (interval_arith_abs (ineq x_in)).
1713 Qed.
1714
1715 (* asn *)
1716 Lemma diff2_domain_asn_compose : `m_bounded_on_int f domain bounds ==>
1717 iabs bounds < &1 ==> diff2_domain domain (asn o f)`.
1718 Proof.
1719 move: d2f; rewrite m_bounded_on_int !diff2_domain => d2f ineq n0 x x_in.
1720 by rewrite diff2_asn_compose d2f // andbT (interval_arith_abs (ineq x_in)).
1721 Qed.
1722
1723 (* matan *)
1724 Lemma diff2_domain_matan_compose : `m_bounded_on_int f domain bounds ==>
1725 interval_gt (-- &1) bounds ==> diff2_domain domain (matan o f)`.
1726 Proof.
1727 move: d2f; rewrite m_bounded_on_int !diff2_domain => d2f ineq n0 x x_in.
1728 by rewrite diff2_matan_compose d2f // andbT (interval_arith_gt (ineq x_in)).
1729 Qed.
1730
1731
1732 (* Binary *)
1733 Hypothesis d2g : `diff2_domain domain g`.
1734
1735 (* add *)
1736 Lemma diff2_domain_add : `diff2_domain domain (\x. f x + g x)`.
1737 Proof. by move: d2f d2g; rewrite !diff2_domain => d2f d2g x x_in; rewrite diff2_add d2f ?d2g. Qed.
1738
1739 (* sub *)
1740 Lemma diff2_domain_sub : `diff2_domain domain (\x. f x - g x)`.
1741 Proof. by move: d2f d2g; rewrite !diff2_domain => d2f d2g x x_in; rewrite diff2_sub d2f ?d2g. Qed.
1742
1743 (* mul *)
1744 Lemma diff2_domain_mul : `diff2_domain domain (\x. f x * g x)`.
1745 Proof. by move: d2f d2g; rewrite !diff2_domain => d2f d2g x x_in; rewrite diff2_mul d2f ?d2g. Qed.
1746
1747 End Domain.
1748
1749
1750 Section SecondPartial.
1751
1752 Lemma diff2_imp_diff f x : `diff2 f x ==> (lift o f) differentiable at x`.
1753 by rewrite diff2 => [] [s] [open_s] [xs] ->. Qed.
1754
1755 Lemma diff2_imp_partial_diff f i x : `diff2 f x ==> (lift o partial i f) differentiable at x`.
1756 by rewrite diff2 => [] [s] [open_s] [xs] ->. Qed.
1757
1758 Lemma partial_local s f g i x : `(lift o f) differentiable at x ==>
1759 open s ==> x IN s ==> (!y:real^N. y IN s ==> f y = g y) ==>
1760 partial i f x = partial i g x`.
1761 move => df open_s xs eq; rewrite !partial.
1762 apply: derivative_unique; apply: HAS_REAL_DERIVATIVE_LOCAL.
1763 exists `g o (\t. x + t % basis i)`; split.
1764 apply: has_derivative_alt; apply diff_imp_real_diff; rewrite diff_direction andbT.
1765 apply (differentiable_local_at s `lift o f`).
1766 rewrite /= VECTOR_MUL_LZERO VECTOR_ADD_RID df open_s xs !andTb => y ys.
1767 by rewrite !o_THM eq.
1768 move: (open_contains_open_interval open_s xs `basis i:real^N`) => [a] [b] [ab0]; rewrite SUBSET => sub.
1769 exists `real_interval (a, b)`; rewrite ab0 REAL_OPEN_REAL_INTERVAL !andTb => y y_in.
1770 by rewrite !o_THM /= eq // sub IN_IMAGE /=; exists y.
1771 Qed.
1772
1773
1774 Variables i j : `:num`.
1775
1776 (* scale *)
1777 Lemma second_partial_scale f c : `diff2 f x ==> partial2 i j (\x. c * f x) x = c * partial2 i j f x`.
1778 Proof.
1779 move => d2f; rewrite !partial2 -partial_scale ?diff2_imp_partial_diff // EQ_SYM_EQ.
1780 move: d2f; rewrite diff2 => [] [s] [open_s] [xs] df.
1781 apply partial_local; exists s; rewrite open_s xs f_lift_scale DIFFERENTIABLE_CMUL ?andTb.
1782 by rewr !ETA_AX; rewrite df.
1783 by move => y ys; rewrite partial_scale ?df.
1784 Qed.
1785
1786 (* neg *)
1787 Lemma second_partial_neg f : `diff2 f x ==> partial2 i j (\x. --f x) x = --partial2 i j f x`.
1788 Proof. by move/(second_partial_scale f `--(&1)`); rewrite -!REAL_NEG_MINUS1. Qed.
1789
1790
1791 (* Binary operations *)
1792
1793 (* add *)
1794 Lemma second_partial_add f g : `diff2 f x ==> diff2 g x ==>
1795 partial2 i j (\x. f x + g x) x = partial2 i j f x + partial2 i j g x`.
1796 Proof.
1797 rewrite !diff2 => [] [s] [open_s] [xs] df [t] [open_t] [ys] dg.
1798 rewrite !partial2 -partial_add ?df ?dg // EQ_SYM_EQ; apply partial_local.
1799 exists `s INTER t`; rewrite OPEN_INTER // !IN_INTER xs ys.
1800 rewrite f_lift_add DIFFERENTIABLE_ADD ?andTb.
1801 by rewr !ETA_AX; rewrite df ?dg.
1802 by move => z [zs zt]; rewrite partial_add ?df ?dg.
1803 Qed.
1804
1805
1806 (* sub *)
1807 Lemma second_partial_sub f g : `diff2 f x ==> diff2 g x ==>
1808 partial2 i j (\x. f x - g x) x = partial2 i j f x - partial2 i j g x`.
1809 Proof.
1810 by move => d2f d2g; rewrite real_sub second_partial_add ?diff2_neg // second_partial_neg // -real_sub.
1811 Qed.
1812
1813 (* mul *)
1814 Lemma second_partial_mul f g : `diff2 f x ==> diff2 g x ==>
1815 partial2 i j (\x. f x * g x) x = (partial2 i j f x * g x + partial j f x * partial i g x) +
1816 (partial i f x * partial j g x + f x * partial2 i j g x)`.
1817 rewrite !diff2 => [] [s] [open_s] [xs] df [t] [open_t] [ys] dg.
1818 rewrite !partial2 -!partial_mul -?partial_add ?df ?dg // 1?EQ_SYM_EQ.
1819 by rewrite !differentiable_mul; rewr ETA_AX; rewrite ?df ?dg.
1820 apply partial_local.
1821 exists `s INTER t`; rewrite OPEN_INTER // !IN_INTER xs ys.
1822 rewrite f_lift_add DIFFERENTIABLE_ADD ?andTb.
1823 by rewr !ETA_AX; rewrite !differentiable_mul; rewr ETA_AX; rewrite ?df ?dg.
1824 by move => z [zs zt]; rewrite partial_mul ?df ?dg.
1825 Qed.
1826
1827
1828 (* uni_compose *)
1829 Lemma second_partial_uni_compose f u : `diff2 f x ==> nth_diff_strong 2 u (f x) ==>
1830 partial2 i j (u o f) x = (nth_derivative 2 u (f x) * partial i f x) * partial j f x +
1831 derivative u (f x) * partial2 i j f x`.
1832 rewrite !diff2 nth_diff_strong2_eq => [] [s] [open_s] [xs] df [t] [open_t] [fxt] du.
1833 set r := `{z | z IN s /\ (lift o f) z IN (IMAGE lift t)}`.
1834 have open_r : `open r`.
1835 rewrite -r_def CONTINUOUS_OPEN_PREIMAGE -REAL_OPEN open_t open_s !andbT.
1836 apply DIFFERENTIABLE_IMP_CONTINUOUS_ON; rewrite differentiable_on => y ys; rewr ETA_AX.
1837 by rewrite DIFFERENTIABLE_AT_WITHIN df.
1838 rewrite !partial2 nth_derivative2.
1839 rewrite -partial_uni_compose ?df ?du // -(o_THM `derivative u`) -partial_mul.
1840 by rewrite diff_uni_compose ?df ?du.
1841 apply partial_local; exists r; rewrite open_r andbT.
1842 rewrite -r_def !IN_ELIM_THM /= o_THM LIFT_IN_IMAGE_LIFT; split; last first.
1843 by move => y [z] [[zs] fpz] ->; rewrite partial_uni_compose ?df ?du // o_THM.
1844 split; last by exists x.
1845 apply differentiable_local_at; exists r `lift o (\y. derivative u (f y) * partial j f y)`.
1846 rewrite open_r differentiable_mul ?andTb.
1847 by rewrite -(o_THM `derivative u`); rewr !ETA_AX; rewrite diff_uni_compose ?df // du.
1848 rewrite -r_def !IN_ELIM_THM /= !o_THM !LIFT_IN_IMAGE_LIFT; split; first by exists x.
1849 by move => y [p] [[ps] fpt] ->; rewrite partial_uni_compose ?df ?du.
1850 Qed.
1851
1852
1853 End SecondPartial.
1854
1855 End Diff2Arith.
1856
1857 (* Diff2c *)
1858 Section Diff2c.
1859
1860 Lemma real_cont_at_local f g x s : `g real_continuous at x ==> open s ==> x IN s ==>
1861 (!y. y IN s ==> f y = g y) ==> f real_continuous at x`.
1862 Proof.
1863 rewrite !"GEN_ALL real_continuous_at" => g_cont open_s xs f_eq_g e e_gt0.
1864 have := OPEN_CONTAINS_BALL s; rewrite open_s /= ball SUBSET IN_ELIM_THM /=.
1865 move/(_ xs) => [d0] [d0_gt0] sub_s.
1866 move: (g_cont e_gt0) => [d1] [d1_gt0] dist_cond.
1867 exists `min d0 d1`.
1868 rewrite !REAL_LT_MIN d1_gt0 d0_gt0 /= => y [yd0 yd1].
1869 rewrite !f_eq_g //.
1870 by rewrite sub_s DIST_SYM; exists y.
1871 exact: dist_cond.
1872 Qed.
1873
1874
1875 Lemma real_cont_atreal_local v u t x : `v real_continuous atreal x ==> real_open t ==> x IN t ==>
1876 (!y. y IN t ==> u y = v y) ==> u real_continuous atreal x`.
1877 Proof.
1878 rewrite !"GEN_ALL REAL_CONTINUOUS_CONTINUOUS_ATREAL".
1879 rewrite -!"GEN_ALL REAL_CONTINUOUS_CONTINUOUS1" REAL_OPEN => vc open_t xt v_eq_u.
1880 apply real_cont_at_local.
1881 exists `v o drop` `IMAGE lift t`.
1882 by rewrite open_t vc /= LIFT_IN_IMAGE_LIFT xt /= IN_IMAGE_LIFT_DROP !o_THM => y /v_eq_u.
1883 Qed.
1884
1885
1886 Implicit Type f g : `:real^N -> real`.
1887 Variable x : `:real^N`.
1888 Variable domain : `:real^N#real^N`.
1889
1890
1891 Section Point.
1892
1893 (* scale *)
1894 Lemma diff2c_scale f c : `diff2c f x ==> diff2c (\x. c * f x) x`.
1895 Proof.
1896 rewrite !diff2c => [] [d2f p2c]; rewrite diff2_scale // andTb => i j.
1897 move: (p2c i j); rewrite -!"GEN_ALL REAL_CONTINUOUS_CONTINUOUS1" => p2ij.
1898 apply real_cont_at_local.
1899 move: d2f; rewrite diff2_eq_diff2_on_open => [] [s] [open_s] [xs] d2s.
1900 exists `(\x. c * partial2 j i f x)` s.
1901 rewrite REAL_CONTINUOUS_LMUL; first by rewr ETA_AX.
1902 rewrite open_s xs /= => y /d2s d2y.
1903 by rewrite second_partial_scale.
1904 Qed.
1905
1906 (* neg *)
1907 Lemma diff2c_neg f : `diff2c f x ==> diff2c (\x. --f x) x`.
1908 Proof. by move/(diff2c_scale f `--(&1)`); rewrite -REAL_NEG_MINUS1. Qed.
1909
1910
1911 (* Composite *)
1912 Section Composite.
1913
1914
1915 Lemma nth_diff_strong_eq_on_open n u x : `nth_diff_strong n u x ==>
1916 ?s. real_open s /\ x IN s /\ (!y. y IN s ==> nth_diff_strong n u y)`.
1917 Proof.
1918 rewrite !nth_diff_strong => [] [t] [open_t] [xt] dt.
1919 exists t; rewrite xt open_t /= => y yt.
1920 by exists t.
1921 Qed.
1922
1923
1924 Lemma diff2_imp_cont f x : `diff2 f x ==> f real_continuous at x`.
1925 Proof.
1926 rewrite diff2 => [] [s] [open_s] [xs] df.
1927 by rewrite "GEN_ALL REAL_CONTINUOUS_CONTINUOUS1" DIFFERENTIABLE_IMP_CONTINUOUS_AT df.
1928 Qed.
1929
1930
1931 Lemma diff2_imp_partial_cont f i x : `diff2 f x ==> (partial i f) real_continuous at x`.
1932 Proof.
1933 rewrite diff2 => [] [s] [open_s] [xs] df.
1934 by rewrite "GEN_ALL REAL_CONTINUOUS_CONTINUOUS1" DIFFERENTIABLE_IMP_CONTINUOUS_AT df.
1935 Qed.
1936
1937
1938 Lemma diff2c_uni_compose u f x : `diff2c f x ==> nth_diff_strong 2 u (f x) ==>
1939 (nth_derivative 2 u) real_continuous atreal (f x) ==> diff2c (u o f) x`.
1940 Proof.
1941 rewrite !diff2c => [] [d2f] p2c d2u u2c.
1942 rewrite diff2_uni_compose ?d2f ?d2u // andTb => i j.
1943 move: (p2c i j); rewrite -!"GEN_ALL REAL_CONTINUOUS_CONTINUOUS1" => p2ij.
1944 apply real_cont_at_local.
1945 move: d2f; rewrite diff2_eq_diff2_on_open => [] [s] [open_s] [xs] d2s.
1946 move: (nth_diff_strong_eq_on_open d2u) => [t] [open_t] [fxt] d2t.
1947 set r := `{z | z IN s /\ (lift o f) z IN (IMAGE lift t)}`.
1948 have open_r : `open r`.
1949 rewrite -r_def CONTINUOUS_OPEN_PREIMAGE -REAL_OPEN open_t open_s !andbT.
1950 apply DIFFERENTIABLE_IMP_CONTINUOUS_ON; rewrite differentiable_on => y ys; rewr ETA_AX.
1951 rewrite DIFFERENTIABLE_AT_WITHIN.
1952 move: (d2s ys); rewrite diff2 => [] [s'] [_] [ys'].
1953 by move/(_ ys') => /=.
1954 exists `(\x. (nth_derivative 2 u (f x) * partial j f x) * partial i f x + derivative u (f x) * partial2 j i f x)` r.
1955 rewrite open_r -r_def !IN_ELIM_THM /= o_THM LIFT_IN_IMAGE_LIFT; split; last first.
1956 move => y [z] [] [zs] fzt yz.
1957 by rewrite second_partial_uni_compose // yz d2s // d2t.
1958 split; last by exists x.
1959 rewrite REAL_CONTINUOUS_ADD !REAL_CONTINUOUS_MUL //=; rewr ETA_AX;
1960 rewrite ?(diff2_imp_partial_cont, d2s) //.
1961 rewrite andbT -[`nth_derivative 2 u _1`]o_THM; rewr ETA_AX.
1962 rewrite "GEN_ALL REAL_CONTINUOUS_CONTINUOUS1".
1963 rewrite o_ASSOC CONTINUOUS_REAL_CONTINUOUS_AT_COMPOSE diff2_imp_cont ?d2s // andTb.
1964 by rewrite -"GEN_ALL REAL_CONTINUOUS_CONTINUOUS1" REAL_CONTINUOUS_ATREAL_WITHINREAL.
1965 rewrite p2ij andbT -[`derivative u _`]o_THM; rewr ETA_AX.
1966 rewrite "GEN_ALL REAL_CONTINUOUS_CONTINUOUS1".
1967 rewrite o_ASSOC CONTINUOUS_REAL_CONTINUOUS_AT_COMPOSE diff2_imp_cont ?d2s // andTb.
1968 rewrite -"GEN_ALL REAL_CONTINUOUS_CONTINUOUS1" REAL_CONTINUOUS_ATREAL_WITHINREAL.
1969 rewrite -nth_derivative1; apply nth_derivative_continuous.
1970 exists `2`; split; last by arith.
1971 by move: (d2t fxt); rewrite nth_diff_strong nth_differentiable_on => [] [t'] [_] [fxt'] ->.
1972 Qed.
1973
1974
1975 Lemma real_open_delete s x : `real_open s ==> real_open (s DELETE x)`.
1976 Proof.
1977 rewrite !REAL_OPEN => /OPEN_DELETE /(_ `lift x`).
1978 by rewrite IMAGE_DELETE_INJ_COMPAT ?LIFT_EQ.
1979 Qed.
1980
1981
1982 (* inv *)
1983 Lemma diff2c_inv_compose f : `~(f x = &0) ==> diff2c f x ==> diff2c (inv o f) x`.
1984 Proof.
1985 move => fn0 d2f; rewrite diff2c_uni_compose.
1986 rewrite (diff2_inv fn0) d2f /=.
1987 apply: real_cont_atreal_local.
1988 exists `\x. &2 * inv (x pow 3)` `UNIV DELETE (&0)`.
1989 rewrite real_open_delete ?REAL_OPEN_UNIV /= !IN_DELETE !IN_UNIV fn0 /=; split; last first.
1990 by move => y yn0; rewrite second_derivative_inv.
1991 rewrite REAL_CONTINUOUS_LMUL REAL_CONTINUOUS_INV_ATREAL REAL_CONTINUOUS_POW ?REAL_CONTINUOUS_AT_ID.
1992 by rewrite REAL_POW_NZ.
1993 Qed.
1994
1995
1996 (* sqrt *)
1997 Lemma diff2c_sqrt_compose f : `&0 < f x ==> diff2c f x ==> diff2c (sqrt o f) x`.
1998 Proof.
1999 move => fn0 d2f; rewrite diff2c_uni_compose.
2000 rewrite (diff2_sqrt fn0) d2f /=.
2001 apply: real_cont_atreal_local.
2002 exists `\x. -- inv (&4 * sqrt (x pow 3))` `{x | x > &0}`.
2003 rewrite REAL_OPEN_HALFSPACE_GT !IN_ELIM_THM /= !real_gt; split; last first.
2004 by move => y [z] [z0] ->; rewrite second_derivative_sqrt.
2005 split; last by exists `f x`.
2006 rewrite REAL_CONTINUOUS_NEG REAL_CONTINUOUS_INV_ATREAL REAL_CONTINUOUS_LMUL; last first.
2007 rewrite REAL_ENTIRE negb_or andTb; split; first by arith.
2008 by rewrite SQRT_EQ_0 ?REAL_POW_NZ ?REAL_LT_IMP_NZ.
2009 have ->: `(\x. sqrt (x pow 3)) = (sqrt o (\x. x pow 3))`.
2010 by rewrite FUN_EQ_THM o_THM.
2011 rewrite REAL_CONTINUOUS_ATREAL_COMPOSE /= REAL_CONTINUOUS_POW ?REAL_CONTINUOUS_AT_ID andTb.
2012 by rewrite REAL_CONTINUOUS_AT_SQRT REAL_POW_LT.
2013 Qed.
2014
2015 (* abs *)
2016
2017 Lemma diff2c_abs_pos_compose f : `&0 < f x ==> diff2c f x ==> diff2c (abs o f) x`.
2018 Proof.
2019 move => fn0 d2f; rewrite diff2c_uni_compose.
2020 rewrite (diff2_abs_pos fn0) d2f /=.
2021 apply: real_cont_atreal_local.
2022 exists `\x. &0` `{x | x > &0}`.
2023 rewrite REAL_OPEN_HALFSPACE_GT !IN_ELIM_THM /= !real_gt; split; last first.
2024 by move => y [z] [z0] ->; rewrite second_derivative_abs_pos.
2025 rewrite REAL_CONTINUOUS_CONST andTb.
2026 by exists `f x`.
2027 Qed.
2028
2029 Lemma diff2c_abs_neg_compose f : `f x < &0 ==> diff2c f x ==> diff2c (abs o f) x`.
2030 Proof.
2031 move => fn0 d2f; rewrite diff2c_uni_compose.
2032 rewrite (diff2_abs_neg fn0) d2f /=.
2033 apply: real_cont_atreal_local.
2034 exists `\x. &0` `{x | x < &0}`.
2035 rewrite REAL_OPEN_HALFSPACE_LT !IN_ELIM_THM /=; split; last first.
2036 by move => y [z] [z0] ->; rewrite second_derivative_abs_neg.
2037 rewrite REAL_CONTINUOUS_CONST andTb.
2038 by exists `f x`.
2039 Qed.
2040
2041 (* pow *)
2042
2043 Lemma diff2c_pow_compose n f : `diff2c f x ==> diff2c ((\x. x pow n) o f) x`.
2044 Proof.
2045 move => d2f; rewrite diff2c_uni_compose.
2046 rewrite diff2_pow_x d2f /= nth_derivative2 second_derivative_pow_x.
2047 by rewrite REAL_CONTINUOUS_LMUL REAL_CONTINUOUS_POW REAL_CONTINUOUS_AT_ID.
2048 Qed.
2049
2050 (* atn *)
2051
2052 Lemma diff2c_atn_compose f : `diff2c f x ==> diff2c (atn o f) x`.
2053 Proof.
2054 move => d2f; rewrite diff2c_uni_compose.
2055 rewrite diff2_atn d2f /= nth_derivative2 second_derivative_atn.
2056 rewrite !REAL_CONTINUOUS_MUL ?REAL_CONTINUOUS_CONST ?REAL_CONTINUOUS_AT_ID //=.
2057 rewrite REAL_CONTINUOUS_POW REAL_CONTINUOUS_INV_ATREAL REAL_CONTINUOUS_ADD ?andTb.
2058 by rewrite REAL_CONTINUOUS_CONST REAL_CONTINUOUS_POW ?REAL_CONTINUOUS_AT_ID.
2059 rewrite REAL_RNEG_UNIQ.
2060 have := REAL_LE_POW_2 `f x`.
2061 by arith.
2062 Qed.
2063
2064 (* cos *)
2065 Lemma diff2c_cos_compose f : `diff2c f x ==> diff2c (cos o f) x`.
2066 Proof.
2067 move => d2f; rewrite diff2c_uni_compose.
2068 rewrite diff2_cos d2f /= second_derivative_cos.
2069 by rewrite REAL_CONTINUOUS_NEG REAL_CONTINUOUS_AT_COS.
2070 Qed.
2071
2072 (* sin *)
2073 Lemma diff2c_sin_compose f : `diff2c f x ==> diff2c (sin o f) x`.
2074 Proof.
2075 move => d2f; rewrite diff2c_uni_compose.
2076 rewrite diff2_sin d2f /= second_derivative_sin.
2077 by rewrite REAL_CONTINUOUS_NEG REAL_CONTINUOUS_AT_SIN.
2078 Qed.
2079
2080 (* exp *)
2081 Lemma diff2c_exp_compose f : `diff2c f x ==> diff2c (exp o f) x`.
2082 Proof.
2083 move => d2f; rewrite diff2c_uni_compose.
2084 rewrite diff2_exp d2f /= second_derivative_exp.
2085 by rewrite REAL_CONTINUOUS_AT_EXP.
2086 Qed.
2087
2088 (* log *)
2089 Lemma diff2c_log_compose f : `&0 < f x ==> diff2c f x ==> diff2c (log o f) x`.
2090 Proof.
2091 move => fn0 d2f; rewrite diff2c_uni_compose.
2092 rewrite (diff2_log fn0) d2f /=.
2093 apply: real_cont_atreal_local.
2094 exists `\x. -- inv (x pow 2)` `{x | x > &0}`.
2095 rewrite REAL_OPEN_HALFSPACE_GT !IN_ELIM_THM /= !real_gt; split; last first.
2096 by move => y [z] [z0] ->; rewrite second_derivative_log.
2097 split; last by exists `f x`.
2098 rewrite REAL_CONTINUOUS_NEG REAL_CONTINUOUS_INV_ATREAL REAL_CONTINUOUS_POW ?REAL_CONTINUOUS_AT_ID.
2099 by rewrite REAL_POW_2 REAL_ENTIRE; move: fn0; arith.
2100 Qed.
2101
2102 (* acs *)
2103 Lemma diff2c_acs_compose f : `abs (f x) < &1 ==> diff2c f x ==> diff2c (acs o f) x`.
2104 Proof.
2105 move => fn1 d2f; rewrite diff2c_uni_compose.
2106 rewrite (diff2_acs fn1) d2f /=.
2107 apply: real_cont_atreal_local.
2108 exists `\x. --(x / sqrt ((&1 - x * x) pow 3))` `{x | x < &1} INTER {x | x > -- &1}`.
2109 rewrite REAL_OPEN_INTER ?REAL_OPEN_HALFSPACE_GT ?REAL_OPEN_HALFSPACE_LT //.
2110 rewrite !IN_INTER !IN_ELIM_THM /= !real_gt; split; last first.
2111 move => y [] [a] [a1] -> [b] [b1] ab; rewrite second_derivative_acs //.
2112 by move: ab b1 a1; arith.
2113 split; last by split; exists `f x`; move: fn1; arith.
2114 rewrite REAL_CONTINUOUS_NEG.
2115 apply REAL_CONTINUOUS_DIV_ATREAL.
2116 have h: `&0 < (&1 - f x * f x) pow 3`.
2117 rewrite REAL_POW_LT.
2118 rewrite "REAL_ARITH `!a. &1 - a * a = (&1 - a) * (&1 + a)`" REAL_LT_MUL.
2119 by move: fn1; arith.
2120 rewrite REAL_CONTINUOUS_AT_ID /=; split; last first.
2121 by rewrite SQRT_EQ_0 ?REAL_LE_LT // REAL_LT_IMP_NZ.
2122 have ->: `(\x. sqrt ((&1 - x * x) pow 3)) = sqrt o (\x. (&1 - x * x) pow 3)`.
2123 by rewrite FUN_EQ_THM o_THM.
2124 rewrite REAL_CONTINUOUS_ATREAL_COMPOSE REAL_CONTINUOUS_AT_SQRT //=.
2125 rewrite REAL_CONTINUOUS_POW REAL_CONTINUOUS_SUB REAL_CONTINUOUS_CONST.
2126 by rewrite REAL_CONTINUOUS_MUL ?REAL_CONTINUOUS_AT_ID.
2127 Qed.
2128
2129 (* asn *)
2130 Lemma diff2c_asn_compose f : `abs (f x) < &1 ==> diff2c f x ==> diff2c (asn o f) x`.
2131 Proof.
2132 move => fn1 d2f; rewrite diff2c_uni_compose.
2133 rewrite (diff2_asn fn1) d2f /=.
2134 apply: real_cont_atreal_local.
2135 exists `\x. x / sqrt ((&1 - x * x) pow 3)` `{x | x < &1} INTER {x | x > -- &1}`.
2136 rewrite REAL_OPEN_INTER ?REAL_OPEN_HALFSPACE_GT ?REAL_OPEN_HALFSPACE_LT //.
2137 rewrite !IN_INTER !IN_ELIM_THM /= !real_gt; split; last first.
2138 move => y [] [a] [a1] -> [b] [b1] ab; rewrite second_derivative_asn //.
2139 by move: ab b1 a1; arith.
2140 split; last by split; exists `f x`; move: fn1; arith.
2141 apply REAL_CONTINUOUS_DIV_ATREAL.
2142 have h: `&0 < (&1 - f x * f x) pow 3`.
2143 rewrite REAL_POW_LT.
2144 rewrite "REAL_ARITH `!a. &1 - a * a = (&1 - a) * (&1 + a)`" REAL_LT_MUL.
2145 by move: fn1; arith.
2146 rewrite REAL_CONTINUOUS_AT_ID /=; split; last first.
2147 by rewrite SQRT_EQ_0 ?REAL_LE_LT // REAL_LT_IMP_NZ.
2148 have ->: `(\x. sqrt ((&1 - x * x) pow 3)) = sqrt o (\x. (&1 - x * x) pow 3)`.
2149 by rewrite FUN_EQ_THM o_THM.
2150 rewrite REAL_CONTINUOUS_ATREAL_COMPOSE REAL_CONTINUOUS_AT_SQRT //=.
2151 rewrite REAL_CONTINUOUS_POW REAL_CONTINUOUS_SUB REAL_CONTINUOUS_CONST.
2152 by rewrite REAL_CONTINUOUS_MUL ?REAL_CONTINUOUS_AT_ID.
2153 Qed.
2154
2155 (* matan *)
2156 Lemma diff2c_matan_compose f : `-- &1 < f x ==> diff2c f x ==> diff2c (matan o f) x`.
2157 Proof.
2158 move => fn1 d2f; rewrite diff2c_uni_compose.
2159 rewrite (diff2_matan fn1) d2f /=.
2160 case: (EXCLUDED_MIDDLE `f x < &1`) => fn2; last first.
2161 apply: real_cont_atreal_local; rewrite nth_derivative2 derivative_eq_real_derivative.
2162 set g := `\x. (&3 / &4 * atn (sqrt x) / (x pow 2 * sqrt x) - &3 / &4 * inv (x pow 2 * (x + &1))) - &1 / &2 * inv (x * (x + &1) pow 2)`.
2163 exists g `real_interval (&0, f x + &1)`.
2164 rewrite REAL_OPEN_REAL_INTERVAL !IN_REAL_INTERVAL andbT; split; last first.
2165 by move => y y_ineq; rewrite Matan.matan_second_derivative_gt0 // -g_def.
2166 split; last by move: fn2; arith.
2167 rewrite -g_def REAL_CONTINUOUS_SUB REAL_CONTINUOUS_LMUL.
2168 rewrite REAL_CONTINUOUS_INV_ATREAL REAL_CONTINUOUS_MUL ?REAL_CONTINUOUS_AT_ID ?andTb.
2169 by rewrite REAL_CONTINUOUS_POW // REAL_CONTINUOUS_ADD REAL_CONTINUOUS_AT_ID REAL_CONTINUOUS_CONST.
2170 by rewrite REAL_POW_2 !REAL_ENTIRE; move: fn2; arith.
2171 rewrite REAL_CONTINUOUS_SUB // !REAL_CONTINUOUS_LMUL //.
2172 rewrite "GEN_ALL REAL_CONTINUOUS_DIV_ATREAL" REAL_CONTINUOUS_MUL.
2173 by rewrite REAL_CONTINUOUS_POW ?REAL_CONTINUOUS_AT_ID // REAL_CONTINUOUS_AT_SQRT.
2174 rewrite andTb REAL_POW_2 !REAL_ENTIRE SQRT_EQ_0; split; last by move: fn2; arith.
2175 rewrite -(o_THM `atn`); rewr ETA_AX; rewrite REAL_CONTINUOUS_ATREAL_COMPOSE.
2176 by rewrite REAL_CONTINUOUS_AT_ATN REAL_CONTINUOUS_AT_SQRT //; move: fn2; arith.
2177 rewrite REAL_CONTINUOUS_INV_ATREAL REAL_CONTINUOUS_MUL ?andTb.
2178 by rewrite REAL_CONTINUOUS_POW ?REAL_CONTINUOUS_ADD ?REAL_CONTINUOUS_AT_ID ?REAL_CONTINUOUS_CONST.
2179 by rewrite REAL_POW_2 !REAL_ENTIRE; move: fn2; arith.
2180 rewrite nth_derivative2 derivative_eq_real_derivative -Matan.ddmatan.
2181 apply: HAS_REAL_DERIVATIVE_IMP_CONTINUOUS_ATREAL.
2182 have := Matan.matan_second_derivative_abs1; rewrite -Matan.ddmatan => d2.
2183 set a := `\i. -- &1 pow (i + 2) * &((i + 1) * (i + 2)) / &(2 * i + 5)`.
2184 have := Series.power_series_has_derivative `ddmatan` a `from 0` `&1`; "ANTS_TAC".
2185 by move => t t_ineq; rewrite -a_def /= d2.
2186 move => [h] h_diff.
2187 by exists `h (f x)`; rewrite h_diff; move: fn2 fn1; arith.
2188 Qed.
2189
2190
2191 End Composite.
2192
2193 (* add *)
2194 Lemma diff2c_add f g : `diff2c f x ==> diff2c g x ==> diff2c (\x. f x + g x) x`.
2195 Proof.
2196 rewrite !diff2c => [] [d2f p2f] [d2g p2g]; rewrite diff2_add // andTb => i j.
2197 move: (p2f i j) (p2g i j); rewrite -!"GEN_ALL REAL_CONTINUOUS_CONTINUOUS1" => p2fij p2gij.
2198 apply real_cont_at_local.
2199 move: d2f d2g; rewrite diff2_eq_diff2_on_open => [] [s] [open_s] [xs] d2f.
2200 rewrite diff2_eq_diff2_on_open => [] [t] [open_t] [xt] d2g.
2201 exists `(\x. partial2 j i f x + partial2 j i g x)` `s INTER t`.
2202 rewrite !IN_INTER xs xt OPEN_INTER //= REAL_CONTINUOUS_ADD /=; first by rewr ETA_AX.
2203 by move => y [ys yt]; rewrite second_partial_add ?d2f ?d2g.
2204 Qed.
2205
2206 (* sub *)
2207 Lemma diff2c_sub f g : `diff2c f x ==> diff2c g x ==> diff2c (\x. f x - g x) x`.
2208 Proof. by move => d2f d2g; rewrite real_sub diff2c_add // diff2c_neg. Qed.
2209
2210 (* mul *)
2211 Lemma diff2c_mul f g : `diff2c f x ==> diff2c g x ==> diff2c (\x. f x * g x) x`.
2212 rewrite !diff2c => [] [d2f p2f] [d2g p2g]; rewrite diff2_mul // andTb => i j.
2213 move: (p2f i j) (p2g i j); rewrite -!"GEN_ALL REAL_CONTINUOUS_CONTINUOUS1" => p2fij p2gij.
2214 apply real_cont_at_local.
2215 move: d2f d2g; rewrite diff2_eq_diff2_on_open => [] [s] [open_s] [xs] d2f.
2216 rewrite diff2_eq_diff2_on_open => [] [t] [open_t] [xt] d2g.
2217 exists `(\x. (partial2 j i f x * g x + partial i f x * partial j g x) +
2218 partial j f x * partial i g x + f x * partial2 j i g x)` `s INTER t`.
2219 rewrite !IN_INTER xs xt OPEN_INTER //=; split; last first.
2220 by move => y [ys yt]; rewrite second_partial_mul ?d2f ?d2g.
2221 by rewrite !REAL_CONTINUOUS_ADD // !REAL_CONTINUOUS_MUL; rewr ETA_AX //;
2222 rewrite ?p2gij ?p2fij /= ?diff2_imp_partial_cont ?diff2_imp_cont ?d2f ?d2g.
2223 Qed.
2224
2225 End Point.
2226
2227 (* Domain *)
2228 Section Domain.
2229
2230 Variables f g : `:real^N -> real`.
2231 Hypothesis d2f : `diff2c_domain domain f`.
2232
2233 (* scale *)
2234 Lemma diff2c_domain_scale c : `diff2c_domain domain (\x. c * f x)`.
2235 Proof. by move: d2f; rewrite !diff2c_domain => d2f x x_in; rewrite diff2c_scale d2f. Qed.
2236
2237 (* neg *)
2238 Lemma diff2c_domain_neg : `diff2c_domain domain (\x. --f x)`.
2239 Proof. by move: d2f; rewrite !diff2c_domain => d2f x x_in; rewrite diff2c_neg d2f. Qed.
2240
2241 Variable bounds : `:real#real`.
2242
2243 (* inv *)
2244 Lemma diff2c_domain_inv_compose : `m_bounded_on_int f domain bounds ==>
2245 interval_not_zero bounds ==> diff2c_domain domain (inv o f)`.
2246 Proof.
2247 move: d2f; rewrite m_bounded_on_int !diff2c_domain => d2f ineq n0 x x_in.
2248 by rewrite diff2c_inv_compose d2f // andbT (interval_arith_not_zero (ineq x_in)).
2249 Qed.
2250
2251 (* sqrt *)
2252 Lemma diff2c_domain_sqrt_compose : `m_bounded_on_int f domain bounds ==>
2253 interval_pos bounds ==> diff2c_domain domain (sqrt o f)`.
2254 Proof.
2255 move: d2f; rewrite m_bounded_on_int !diff2c_domain => d2f ineq n0 x x_in.
2256 by rewrite diff2c_sqrt_compose d2f // andbT (interval_arith_pos (ineq x_in)).
2257 Qed.
2258
2259 (* abs *)
2260 Lemma diff2c_domain_abs_pos_compose : `m_bounded_on_int f domain bounds ==>
2261 interval_pos bounds ==> diff2c_domain domain (abs o f)`.
2262 Proof.
2263 move: d2f; rewrite m_bounded_on_int !diff2c_domain => d2f ineq n0 x x_in.
2264 by rewrite diff2c_abs_pos_compose d2f // andbT (interval_arith_pos (ineq x_in)).
2265 Qed.
2266
2267 Lemma diff2c_domain_abs_neg_compose : `m_bounded_on_int f domain bounds ==>
2268 interval_neg bounds ==> diff2c_domain domain (abs o f)`.
2269 Proof.
2270 move: d2f; rewrite m_bounded_on_int !diff2c_domain => d2f ineq n0 x x_in.
2271 by rewrite diff2c_abs_neg_compose d2f // andbT (interval_arith_neg (ineq x_in)).
2272 Qed.
2273
2274 (* pow *)
2275 Lemma diff2c_domain_pow_compose n : `diff2c_domain domain ((\x. x pow n) o f)`.
2276 Proof. by move: d2f; rewrite !diff2c_domain => d2f x x_in; rewrite diff2c_pow_compose d2f. Qed.
2277
2278 (* atn *)
2279 Lemma diff2c_domain_atn_compose : `diff2c_domain domain (atn o f)`.
2280 Proof. by move: d2f; rewrite !diff2c_domain => d2f x x_in; rewrite diff2c_atn_compose d2f. Qed.
2281
2282 (* cos *)
2283 Lemma diff2c_domain_cos_compose : `diff2c_domain domain (cos o f)`.
2284 Proof. by move: d2f; rewrite !diff2c_domain => d2f x x_in; rewrite diff2c_cos_compose d2f. Qed.
2285
2286 (* sin *)
2287 Lemma diff2c_domain_sin_compose : `diff2c_domain domain (sin o f)`.
2288 Proof. by move: d2f; rewrite !diff2c_domain => d2f x x_in; rewrite diff2c_sin_compose d2f. Qed.
2289
2290 (* exp *)
2291 Lemma diff2c_domain_exp_compose : `diff2c_domain domain (exp o f)`.
2292 Proof. by move: d2f; rewrite !diff2c_domain => d2f x x_in; rewrite diff2c_exp_compose d2f. Qed.
2293
2294 (* log *)
2295 Lemma diff2c_domain_log_compose : `m_bounded_on_int f domain bounds ==>
2296 interval_pos bounds ==> diff2c_domain domain (log o f)`.
2297 move: d2f; rewrite m_bounded_on_int !diff2c_domain => d2f ineq n0 x x_in.
2298 by rewrite diff2c_log_compose d2f // andbT (interval_arith_pos (ineq x_in)).
2299 Qed.
2300
2301 (* acs *)
2302 Lemma diff2c_domain_acs_compose : `m_bounded_on_int f domain bounds ==>
2303 iabs bounds < &1 ==> diff2c_domain domain (acs o f)`.
2304 Proof.
2305 move: d2f; rewrite m_bounded_on_int !diff2c_domain => d2f ineq n0 x x_in.
2306 by rewrite diff2c_acs_compose d2f // andbT (interval_arith_abs (ineq x_in)).
2307 Qed.
2308
2309 (* asn *)
2310 Lemma diff2c_domain_asn_compose : `m_bounded_on_int f domain bounds ==>
2311 iabs bounds < &1 ==> diff2c_domain domain (asn o f)`.
2312 Proof.
2313 move: d2f; rewrite m_bounded_on_int !diff2c_domain => d2f ineq n0 x x_in.
2314 by rewrite diff2c_asn_compose d2f // andbT (interval_arith_abs (ineq x_in)).
2315 Qed.
2316
2317 (* matan *)
2318 Lemma diff2c_domain_matan_compose : `m_bounded_on_int f domain bounds ==>
2319 interval_gt (-- &1) bounds ==> diff2c_domain domain (matan o f)`.
2320 Proof.
2321 move: d2f; rewrite m_bounded_on_int !diff2c_domain => d2f ineq n0 x x_in.
2322 by rewrite diff2c_matan_compose d2f // andbT (interval_arith_gt (ineq x_in)).
2323 Qed.
2324
2325 (* Binary *)
2326 Hypothesis d2g : `diff2c_domain domain g`.
2327
2328 (* add *)
2329 Lemma diff2c_domain_add : `diff2c_domain domain (\x. f x + g x)`.
2330 Proof. by move: d2f d2g; rewrite !diff2c_domain => d2f d2g x x_in; rewrite diff2c_add d2f ?d2g. Qed.
2331
2332 (* sub *)
2333 Lemma diff2c_domain_sub : `diff2c_domain domain (\x. f x - g x)`.
2334 Proof. by move: d2f d2g; rewrite !diff2c_domain => d2f d2g x x_in; rewrite diff2c_sub d2f ?d2g. Qed.
2335
2336 (* mul *)
2337 Lemma diff2c_domain_mul : `diff2c_domain domain (\x. f x * g x)`.
2338 Proof. by move: d2f d2g; rewrite !diff2c_domain => d2f d2g x x_in; rewrite diff2c_mul d2f ?d2g. Qed.
2339
2340 End Domain.
2341
2342 End Diff2c.
2343
2344
2345
2346 (* m_lin_approx lemmas *)
2347 Section M_LinApprox.
2348
2349 Variables f g : `:real^N -> real`.
2350 Variables bounds : `:real#real`.
2351 Variables d_bounds_list : `:(real#real)list`.
2352 Variable x : `:real^N`.
2353
2354 (* neg *)
2355 Lemma m_lin_approx_neg : `(lift o f) differentiable at x ==>
2356 interval_arith (--f x) bounds ==>
2357 all_n 1 d_bounds_list (\i int. interval_arith (--partial i f x) int) ==>
2358 m_lin_approx (\x. --f x) x bounds d_bounds_list`.
2359 move => df b db.
2360 rewrite m_lin_approx /= b f_lift_neg DIFFERENTIABLE_NEG ?andTb; first by rewr ETA_AX.
2361 by "ASM_SIMP_TAC[partial_neg]".
2362 Qed.
2363
2364 (* scale *)
2365 Lemma m_lin_approx_scale c : `(lift o f) differentiable at x ==>
2366 interval_arith (c * f x) bounds ==>
2367 all_n 1 d_bounds_list (\i int. interval_arith (c * partial i f x) int) ==>
2368 m_lin_approx (\x. c * f x) x bounds d_bounds_list`.
2369 move => df bH dbH.
2370 rewrite m_lin_approx /= bH f_lift_scale DIFFERENTIABLE_CMUL ?andTb; first by rewr ETA_AX.
2371 by "ASM_SIMP_TAC[partial_scale]".
2372 Qed.
2373
2374 (* add *)
2375 Lemma m_lin_approx_add : `(lift o f) differentiable at x ==>
2376 (lift o g) differentiable at x ==>
2377 interval_arith (f x + g x) bounds ==>
2378 all_n 1 d_bounds_list (\i int. interval_arith (partial i f x + partial i g x) int) ==>
2379 m_lin_approx (\x. f x + g x) x bounds d_bounds_list`.
2380 move => df dg bH dbH.
2381 rewrite m_lin_approx /= bH f_lift_add DIFFERENTIABLE_ADD ?andTb; first by rewr ETA_AX.
2382 by "ASM_SIMP_TAC[partial_add]".
2383 Qed.
2384
2385 (* sub *)
2386 Lemma m_lin_approx_sub : `(lift o f) differentiable at x ==>
2387 (lift o g) differentiable at x ==>
2388 interval_arith (f x - g x) bounds ==>
2389 all_n 1 d_bounds_list (\i int. interval_arith (partial i f x - partial i g x) int) ==>
2390 m_lin_approx (\x. f x - g x) x bounds d_bounds_list`.
2391 move => df dg bH dbH.
2392 rewrite m_lin_approx /= bH f_lift_sub DIFFERENTIABLE_SUB ?andTb; first by rewr ETA_AX.
2393 by "ASM_SIMP_TAC[partial_sub]".
2394 Qed.
2395
2396 (* mul *)
2397 Lemma m_lin_approx_mul : `(lift o f) differentiable at x ==>
2398 (lift o g) differentiable at x ==>
2399 interval_arith (f x * g x) bounds ==>
2400 all_n 1 d_bounds_list (\i int. interval_arith (partial i f x * g x + f x * partial i g x) int) ==>
2401 m_lin_approx (\x. f x * g x) x bounds d_bounds_list`.
2402 move => df dg bH dbH.
2403 rewrite m_lin_approx /= bH differentiable_mul // !andTb.
2404 by "ASM_SIMP_TAC[partial_mul]".
2405 Qed.
2406
2407
2408 End M_LinApprox.
2409
2410
2411
2412 (* m_taylor_interval *)
2413 "let second_bounded = new_definition `second_bounded f domain dd_bounds_list <=>
2414 !x. x IN interval [domain] ==> all_n 1 dd_bounds_list
2415 (\i list_i. all_n 1 list_i (\j int. interval_arith (partial2 j i f x) int))`".
2416
2417 "let m_taylor_interval =
2418 new_definition `m_taylor_interval f domain y w f_bounds d_bounds_list dd_bounds_list <=>
2419 m_cell_domain domain y w /\
2420 diff2c_domain domain f /\
2421 m_lin_approx f y f_bounds d_bounds_list /\
2422 second_bounded f domain dd_bounds_list`".
2423
2424
2425 (* Arithmetic of m_taylor_interval *)
2426 Section M_TaylorIntervalArith.
2427
2428 Variables f g : `:real^N -> real`.
2429 Variables x z y w : `:real^N`.
2430 Variable domain : `:real^N#real^N`.
2431 Variables f_bounds g_bounds bounds : `:real#real`.
2432 Variables df_bounds_list dg_bounds_list d_bounds_list : `:(real#real)list`.
2433 Variables ddf_bounds_list ddg_bounds_list dd_bounds_list : `:((real#real)list)list`.
2434
2435
2436 Hypothesis domainH : `m_cell_domain domain y w`.
2437
2438
2439 (* Unary operations *)
2440 Hypothesis d2f : `diff2c_domain domain f`.
2441
2442 (* inv *)
2443 Lemma m_taylor_inv_compose :
2444 `m_bounded_on_int f domain f_bounds ==> interval_not_zero f_bounds ==>
2445 m_lin_approx (inv o f) y bounds d_bounds_list ==>
2446 second_bounded (inv o f) domain dd_bounds_list ==>
2447 m_taylor_interval (inv o f) domain y w bounds d_bounds_list dd_bounds_list`.
2448 Proof.
2449 move => bf fn0 lin second; rewrite m_taylor_interval.
2450 by rewrite (diff2c_domain_inv_compose d2f bf).
2451 Qed.
2452
2453 (* sqrt *)
2454 Lemma m_taylor_sqrt_compose :
2455 `m_bounded_on_int f domain f_bounds ==> interval_pos f_bounds ==>
2456 m_lin_approx (sqrt o f) y bounds d_bounds_list ==>
2457 second_bounded (sqrt o f) domain dd_bounds_list ==>
2458 m_taylor_interval (sqrt o f) domain y w bounds d_bounds_list dd_bounds_list`.
2459 Proof.
2460 move => bf fn0 lin second; rewrite m_taylor_interval.
2461 by rewrite (diff2c_domain_sqrt_compose d2f bf).
2462 Qed.
2463
2464 (* abs *)
2465 Lemma m_taylor_abs_pos_compose :
2466 `m_bounded_on_int f domain f_bounds ==> interval_pos f_bounds ==>
2467 m_lin_approx (abs o f) y bounds d_bounds_list ==>
2468 second_bounded (abs o f) domain dd_bounds_list ==>
2469 m_taylor_interval (abs o f) domain y w bounds d_bounds_list dd_bounds_list`.
2470 Proof.
2471 move => bf fn0 lin second; rewrite m_taylor_interval.
2472 by rewrite (diff2c_domain_abs_pos_compose d2f bf).
2473 Qed.
2474
2475 Lemma m_taylor_abs_neg_compose :
2476 `m_bounded_on_int f domain f_bounds ==> interval_neg f_bounds ==>
2477 m_lin_approx (abs o f) y bounds d_bounds_list ==>
2478 second_bounded (abs o f) domain dd_bounds_list ==>
2479 m_taylor_interval (abs o f) domain y w bounds d_bounds_list dd_bounds_list`.
2480 Proof.
2481 move => bf fn0 lin second; rewrite m_taylor_interval.
2482 by rewrite (diff2c_domain_abs_neg_compose d2f bf).
2483 Qed.
2484
2485 (* pow *)
2486 Lemma m_taylor_pow_compose n :
2487 `m_lin_approx ((\x. x pow n) o f) y bounds d_bounds_list ==>
2488 second_bounded ((\x. x pow n) o f) domain dd_bounds_list ==>
2489 m_taylor_interval ((\x. x pow n) o f) domain y w bounds d_bounds_list dd_bounds_list`.
2490 Proof. by move => lin second; rewrite m_taylor_interval diff2c_domain_pow_compose. Qed.
2491
2492 (* atn *)
2493 Lemma m_taylor_atn_compose :
2494 `m_lin_approx (atn o f) y bounds d_bounds_list ==>
2495 second_bounded (atn o f) domain dd_bounds_list ==>
2496 m_taylor_interval (atn o f) domain y w bounds d_bounds_list dd_bounds_list`.
2497 Proof. by move => lin second; rewrite m_taylor_interval diff2c_domain_atn_compose. Qed.
2498
2499 (* cos *)
2500 Lemma m_taylor_cos_compose :
2501 `m_lin_approx (cos o f) y bounds d_bounds_list ==>
2502 second_bounded (cos o f) domain dd_bounds_list ==>
2503 m_taylor_interval (cos o f) domain y w bounds d_bounds_list dd_bounds_list`.
2504 Proof. by move => lin second; rewrite m_taylor_interval diff2c_domain_cos_compose. Qed.
2505
2506 (* sin *)
2507 Lemma m_taylor_sin_compose :
2508 `m_lin_approx (sin o f) y bounds d_bounds_list ==>
2509 second_bounded (sin o f) domain dd_bounds_list ==>
2510 m_taylor_interval (sin o f) domain y w bounds d_bounds_list dd_bounds_list`.
2511 Proof. by move => lin second; rewrite m_taylor_interval diff2c_domain_sin_compose. Qed.
2512
2513 (* exp *)
2514 Lemma m_taylor_exp_compose :
2515 `m_lin_approx (exp o f) y bounds d_bounds_list ==>
2516 second_bounded (exp o f) domain dd_bounds_list ==>
2517 m_taylor_interval (exp o f) domain y w bounds d_bounds_list dd_bounds_list`.
2518 Proof. by move => lin second; rewrite m_taylor_interval diff2c_domain_exp_compose. Qed.
2519
2520 (* log *)
2521 Lemma m_taylor_log_compose :
2522 `m_bounded_on_int f domain f_bounds ==> interval_pos f_bounds ==>
2523 m_lin_approx (log o f) y bounds d_bounds_list ==>
2524 second_bounded (log o f) domain dd_bounds_list ==>
2525 m_taylor_interval (log o f) domain y w bounds d_bounds_list dd_bounds_list`.
2526 Proof.
2527 move => bf fn0 lin second; rewrite m_taylor_interval.
2528 by rewrite (diff2c_domain_log_compose d2f bf).
2529 Qed.
2530
2531 (* acs *)
2532 Lemma m_taylor_acs_compose :
2533 `m_bounded_on_int f domain f_bounds ==> iabs f_bounds < &1 ==>
2534 m_lin_approx (acs o f) y bounds d_bounds_list ==>
2535 second_bounded (acs o f) domain dd_bounds_list ==>
2536 m_taylor_interval (acs o f) domain y w bounds d_bounds_list dd_bounds_list`.
2537 Proof.
2538 move => bf fn0 lin second; rewrite m_taylor_interval.
2539 by rewrite (diff2c_domain_acs_compose d2f bf).
2540 Qed.
2541
2542 (* asn *)
2543 Lemma m_taylor_asn_compose :
2544 `m_bounded_on_int f domain f_bounds ==> iabs f_bounds < &1 ==>
2545 m_lin_approx (asn o f) y bounds d_bounds_list ==>
2546 second_bounded (asn o f) domain dd_bounds_list ==>
2547 m_taylor_interval (asn o f) domain y w bounds d_bounds_list dd_bounds_list`.
2548 Proof.
2549 move => bf fn0 lin second; rewrite m_taylor_interval.
2550 by rewrite (diff2c_domain_asn_compose d2f bf).
2551 Qed.
2552
2553 (* matan *)
2554 Lemma m_taylor_matan_compose :
2555 `m_bounded_on_int f domain f_bounds ==> interval_gt (-- &1) f_bounds ==>
2556 m_lin_approx (matan o f) y bounds d_bounds_list ==>
2557 second_bounded (matan o f) domain dd_bounds_list ==>
2558 m_taylor_interval (matan o f) domain y w bounds d_bounds_list dd_bounds_list`.
2559 Proof.
2560 move => bf fn0 lin second; rewrite m_taylor_interval.
2561 by rewrite (diff2c_domain_matan_compose d2f bf).
2562 Qed.
2563
2564
2565 (* neg *)
2566 Lemma m_taylor_neg :
2567 `m_lin_approx (\x. --f x) y bounds d_bounds_list ==>
2568 second_bounded (\x. --f x) domain dd_bounds_list ==>
2569 m_taylor_interval (\x. --f x) domain y w bounds d_bounds_list dd_bounds_list`.
2570 Proof. by move => lin second; rewrite m_taylor_interval diff2c_domain_neg. Qed.
2571
2572 (* scale *)
2573 Lemma m_taylor_scale c :
2574 `m_lin_approx (\x. c * f x) y bounds d_bounds_list ==>
2575 second_bounded (\x. c * f x) domain dd_bounds_list ==>
2576 m_taylor_interval (\x. c * f x) domain y w bounds d_bounds_list dd_bounds_list`.
2577 Proof. by move => lin second; rewrite m_taylor_interval diff2c_domain_scale. Qed.
2578
2579
2580 (* Binary operations *)
2581 Hypothesis d2g : `diff2c_domain domain g`.
2582
2583 (* add *)
2584 Lemma m_taylor_add :
2585 `m_lin_approx (\x. f x + g x) y bounds d_bounds_list ==>
2586 second_bounded (\x. f x + g x) domain dd_bounds_list ==>
2587 m_taylor_interval (\x. f x + g x) domain y w bounds d_bounds_list dd_bounds_list`.
2588 Proof. by move => lin second; rewrite m_taylor_interval diff2c_domain_add. Qed.
2589
2590 (* sub *)
2591 Lemma m_taylor_sub :
2592 `m_lin_approx (\x. f x - g x) y bounds d_bounds_list ==>
2593 second_bounded (\x. f x - g x) domain dd_bounds_list ==>
2594 m_taylor_interval (\x. f x - g x) domain y w bounds d_bounds_list dd_bounds_list`.
2595 Proof. by move => lin second; rewrite m_taylor_interval diff2c_domain_sub. Qed.
2596
2597 (* mul *)
2598 Lemma m_taylor_mul :
2599 `m_lin_approx (\x. f x * g x) y bounds d_bounds_list ==>
2600 second_bounded (\x. f x * g x) domain dd_bounds_list ==>
2601 m_taylor_interval (\x. f x * g x) domain y w bounds d_bounds_list dd_bounds_list`.
2602 Proof. by move => lin second; rewrite m_taylor_interval diff2c_domain_mul. Qed.
2603
2604
2605 End M_TaylorIntervalArith.
2606
2607
2608 (* Partial convex *)
2609 Section PartialConvex.
2610
2611
2612 Implicit Type f : `:real^N->real`.
2613
2614 Lemma REAL_LE_DIV_1 a b: `&0 < b ==> (a / b <= &1 <=> a <= b)`.
2615 Proof. by move => b_gt; rewrite REAL_LE_LDIV_EQ // REAL_MUL_LID. Qed.
2616
2617 Lemma partial_convex_max f j x z u v hi :
2618 `(!i. i IN 1..dimindex (:N) ==> ~(i = j) ==> u$i = z$i /\ v$i = x$i) ==>
2619 u$j = x$j ==> v$j = z$j ==>
2620 diff2_domain (x,z) f ==>
2621 (!y. y IN interval [x,z] ==> &0 <= partial2 j j f y) ==>
2622 (!y. y IN interval [x,u] ==> f y <= hi) ==>
2623 (!y. y IN interval [v,z] ==> f y <= hi) ==>
2624 (!y. y IN interval [x,z] ==> f y <= hi)`.
2625 rewrite IN_NUMSEG => uv_eq ux_eq vz_eq.
2626 rewrite diff2_domain => diff2_f partial2_pos bound1 bound2 y y_in.
2627 set y1 := `(lambda i. if i = j then x$j else y$i):real^N`.
2628 set y2 := `(lambda i. if i = j then z$j else y$i):real^N`.
2629 move: y_in; rewrite "GEN_ALL IN_INTERVAL" => y_in.
2630 have [y1_in y2_in] :`y1 IN interval [x,u] /\ y2 IN interval [v,z]`.
2631 rewrite -y1_def -y2_def !"GEN_ALL IN_INTERVAL".
2632 by split => i i_ineq; rewrite "GEN_ALL LAMBDA_BETA" //;
2633 case: (EXCLUDED_MIDDLE `i = j`) => /= ij; rewrite ?(ux_eq, vz_eq) ?REAL_LE_REFL //;
2634 rewrite uv_eq // !y_in.
2635 case: (EXCLUDED_MIDDLE `j IN 1..dimindex (:N)`); last first; rewrite IN_NUMSEG => j_in.
2636 suff: `y1 = y`; first by move => <-; apply: bound1.
2637 rewrite CART_EQ => i i_in.
2638 have inj: `~(i = j)`; first by move: j_in i_in; arith.
2639 by rewrite -y1_def "GEN_ALL LAMBDA_BETA".
2640 suff: `f y <= max (f y1) (f y2)`.
2641 move => cond.
2642 apply: ("REWRITE_RULE[GSYM IMP_IMP] REAL_LE_TRANS" cond).
2643 by move: (bound1 y1_in) (bound2 y2_in); arith.
2644 set g := `f o (\t. y1 + t % basis j)`.
2645 have ->: `f y1 = g (&0)`.
2646 by rewrite -g_def o_THM /= VECTOR_MUL_LZERO VECTOR_ADD_RID.
2647 have y_eq : `y = y1 + (y$j - x$j) % basis j /\ y2 = y1 + (z$j - x$j) % basis j`.
2648 rewrite !CART_EQ; split => i i_in;
2649 rewrite VECTOR_ADD_COMPONENT VECTOR_MUL_COMPONENT BASIS_COMPONENT //;
2650 case: (EXCLUDED_MIDDLE `i = j`) => /= ij;
2651 rewrite -?(y1_def, y2_def) !"GEN_ALL LAMBDA_BETA" //= ?REAL_MUL_RID ?REAL_SUB_ADD2 //.
2652 by rewrite ij /=; arith.
2653 by rewrite ij /=; arith.
2654 have ->: `f y = g (y$j - x$j)`; first by rewrite -g_def o_THM /= -y_eq.
2655 have ->: `f y2 = g (z$j - x$j)`; first by rewrite -g_def o_THM /= -y_eq.
2656 case: (EXCLUDED_MIDDLE `z$j = x$j`) => zx_j.
2657 suff: `y$j = x$j`; first by move => ->; rewrite zx_j REAL_SUB_REFL; arith.
2658 by move: (y_in j_in); rewrite zx_j; arith.
2659 set t := `(y$j - x$j) / (z$j - x$j)`.
2660 have zx_pos : `&0 < z$j - x$j`.
2661 rewrite "REAL_ARITH `!a b. &0 < a - b <=> ~(a = b) /\ b <= a`" zx_j /=.
2662 by apply: REAL_LE_TRANS; exists `y$j`; rewrite !y_in.
2663 have t_props : `&0 <= t /\ t <= &1 /\ y$j - x$j = (&1 - t) * &0 + t * (z$j - x$j)`.
2664 rewrite -t_def REAL_LE_DIV_1 // REAL_MUL_RZERO REAL_ADD_LID.
2665 rewrite real_div -"GEN_ALL REAL_MUL_ASSOC".
2666 rewrite REAL_MUL_LINV ?REAL_SUB_0 // REAL_MUL_RID /=.
2667 rewrite !real_sub REAL_LE_RADD y_in // andbT -!real_sub.
2668 rewrite REAL_LE_MUL REAL_LE_INV; first by rewrite "REAL_ARITH `!a. &0 < a ==> &0 <= a`".
2669 by rewrite REAL_SUB_LE y_in.
2670 rewrite t_props; apply: "GEN_ALL REAL_CONVEX_LOWER".
2671 exists `real_interval [&0, z$j - x$j]`.
2672 rewrite REAL_SUB_ADD REAL_SUB_LE !t_props !IN_REAL_INTERVAL !REAL_LE_REFL /=.
2673 rewrite "REAL_ARITH `!a. &0 < a ==> &0 <= a`" // andbT.
2674 set s := `real_interval _`; move: t_def t_props => _ _.
2675 have in_s : `!t. t IN s ==> y1 + t % basis j IN interval [x,z]`.
2676 rewrite -s_def IN_REAL_INTERVAL "GEN_ALL IN_INTERVAL" => t t_ineq i i_ineq.
2677 rewrite !VECTOR_ADD_COMPONENT VECTOR_MUL_COMPONENT BASIS_COMPONENT //.
2678 rewrite -y1_def "GEN_ALL LAMBDA_BETA" //=.
2679 case: (EXCLUDED_MIDDLE `i = j`) => /= ij; last first.
2680 by rewrite REAL_MUL_RZERO REAL_ADD_RID !y_in.
2681 by move: (y_in i_ineq) t_ineq; rewrite ij; arith.
2682 have diff2_g : `!t. t IN s ==> nth_diff_strong 2 g t`.
2683 by move => t ts; rewrite -g_def; rewrite diff2_dir diff2_f in_s.
2684 have dg : `!t. t IN s ==> derivative g t = partial j f (y1 + t % basis j)`.
2685 move => t ts; rewrite partial.
2686 move: (in_s ts) => p_in; set h := `f o _`.
2687 have ->: `h = g o (\t'. t + t')`.
2688 rewrite -eq_ext -h_def -g_def => r; rewrite !o_THM /=.
2689 by rewrite "GEN_ALL VECTOR_ADD_RDISTRIB" "GEN_ALL VECTOR_ADD_ASSOC".
2690 rewrite -derivative_translation //.
2691 by move: (diff2_g ts); rewrite nth_diff_strong2_eq => [] [e] [_] [te] ->.
2692 have d2g : `!t. t IN s ==> nth_derivative 2 g t = partial2 j j f (y1 + t % basis j)`.
2693 move => t ts; rewrite -g_def diff2_dir_derivative2 ?diff2_f ?in_s //.
2694 have s_eq: `1..dimindex (:N) = ((1..dimindex (:N)) DELETE j) UNION {j}`.
2695 rewrite EXTENSION IN_UNION IN_SING IN_DELETE => i; split.
2696 by move => ->; rewrite andTb orNb.
2697 by case => /=; rewrite IN_NUMSEG.
2698 have disj: `DISJOINT ((1..dimindex (:N)) DELETE j) {j}`.
2699 rewrite DISJOINT EXTENSION IN_INTER IN_SING NOT_IN_EMPTY IN_DELETE => i.
2700 by rewrite -andbA andNb andbF.
2701 rewrite {1}s_eq SUM_UNION ?FINITE_DELETE ?FINITE_NUMSEG ?FINITE_SING // SUM_SING /=.
2702 rewrite SUM_EQ_0 ?IN_DELETE ?REAL_ADD_LID.
2703 move => i i_in; apply SUM_EQ_0 => k k_in /=.
2704 by rewrite BASIS_COMPONENT -?IN_NUMSEG // i_in /= REAL_MUL_LZERO.
2705 rewrite s_eq SUM_UNION ?FINITE_DELETE ?FINITE_NUMSEG ?FINITE_SING // SUM_SING /=.
2706 rewrite SUM_EQ_0 ?IN_DELETE ?REAL_ADD_LID.
2707 move => i i_in /=; rewrite REAL_ENTIRE; right.
2708 by rewrite BASIS_COMPONENT -?IN_NUMSEG // i_in /= REAL_MUL_LZERO.
2709 by rewrite BASIS_COMPONENT ?j_in //= !REAL_MUL_LID partial2 o_THM.
2710 have := REAL_CONVEX_ON_SECOND_DERIVATIVE g `derivative g` `nth_derivative 2 g` s.
2711 rewrite -{1 2}s_def IS_REALINTERVAL_INTERVAL andTb NOT_EXISTS_THM => ->; last first.
2712 by move => t ts; rewrite d2g // partial2_pos in_s.
2713 split.
2714 move => t; apply: contraT; rewrite negbK EXTENSION IN_SING => eq.
2715 move: (eq `&0`) (eq `z$j - x$j`) zx_pos; rewrite !IN_REAL_INTERVAL !REAL_LE_REFL.
2716 by arith.
2717 split => t ts.
2718 move: (diff2_g ts); rewrite nth_diff_strong2_eq_alt => [] [e] [_] [te] H.
2719 by rewrite HAS_REAL_DERIVATIVE_ATREAL_WITHIN H.
2720 move: (diff2_g ts); rewrite nth_diff_strong2_eq_alt => [] [e] [_] [te] H.
2721 by rewrite HAS_REAL_DERIVATIVE_ATREAL_WITHIN H.
2722 Qed.
2723
2724
2725 End PartialConvex.
2726
2727
2728
2729 (* Elementary functions and their taylor intervals *)
2730 Section ElementaryFunctions.
2731
2732 Lemma f_lift_const c : `lift o (\x. c) = (\x. lift c)`.
2733 by rewrite -eq_ext o_THM. Qed.
2734
2735 Lemma f_lift_unary f : `lift o (\x. f x) = (\x. lift (f x))`.
2736 by rewrite -eq_ext o_THM. Qed.
2737
2738
2739 (* const *)
2740 Lemma diff2_const c x : `diff2 (\x:real^N. c) x`.
2741 rewrite diff2; exists `(:real^N)`; rewrite OPEN_UNIV IN_UNIV !andTb => y _.
2742 by rewrite partial_const !f_lift_const !DIFFERENTIABLE_CONST.
2743 Qed.
2744
2745 Lemma diff2_domain_const c domain : `diff2_domain domain (\x:real^N. c)`.
2746 by rewrite diff2_domain diff2_const. Qed.
2747
2748 Lemma partial2_const i j c : `partial2 i j (\x:real^N. c) = (\x. &0)`.
2749 by rewrite partial2 !partial_const. Qed.
2750
2751 Lemma diff2c_const c x : `diff2c (\x:real^N. c) x`.
2752 by rewrite diff2c diff2_const partial2_const -"GEN_ALL REAL_CONTINUOUS_CONTINUOUS1" REAL_CONTINUOUS_CONST. Qed.
2753
2754 Lemma diff2c_domain_const c domain : `diff2c_domain domain (\x:real^N. c)`.
2755 Proof. by rewrite diff2c_domain diff2c_const. Qed.
2756
2757
2758 (* x$k *)
2759 Lemma partial_x_lemma k i : `partial i (\x:real^N. x$k) = (\x. (basis i:real^N)$k)`.
2760 rewrite -eq_ext partial => x /=.
2761 have ->: `(\x. x$k) o (\t. x + t % basis i) = (\t. x$k + t * (basis i:real^N)$k)`.
2762 by rewrite -eq_ext o_THM /= VECTOR_ADD_COMPONENT VECTOR_MUL_COMPONENT.
2763 rewrite derivative_add ?REAL_DIFFERENTIABLE_MUL_ATREAL ?REAL_DIFFERENTIABLE_CONST //.
2764 by rewrite REAL_DIFFERENTIABLE_ID REAL_DIFFERENTIABLE_CONST.
2765 rewrite derivative_const /= derivative_mul ?REAL_DIFFERENTIABLE_ID ?REAL_DIFFERENTIABLE_CONST //.
2766 by rewrite derivative_x derivative_const; arith.
2767 Qed.
2768
2769 Lemma partial_x k i : `k IN 1..dimindex (:N) ==>
2770 partial i (\x:real^N. x$k) = (\x. if i = k then &1 else &0)`.
2771 by move => k_ineq; rewrite partial_x_lemma BASIS_COMPONENT -?IN_NUMSEG //; arith. Qed.
2772
2773 Lemma partial2_x k i j : `partial2 i j (\x:real^N. x$k) = (\x. &0)`.
2774 by rewrite partial2 partial_x_lemma partial_const. Qed.
2775
2776 Lemma diff2_x k x : `k IN 1..dimindex (:N) ==> diff2 (\x:real^N. x$k) x`.
2777 move => k_ineq; rewrite diff2; exists `(:real^N)`; rewrite OPEN_UNIV IN_UNIV !andTb => y _.
2778 by rewrite projection_diff // partial_x_lemma !f_lift_unary DIFFERENTIABLE_CONST.
2779 Qed.
2780
2781 Lemma diff2_domain_x k domain : `k IN 1..dimindex (:N) ==> diff2_domain domain (\x:real^N. x$k)`.
2782 by move/diff2_x; rewrite diff2_domain => ->. Qed.
2783
2784 Lemma diff2c_x k x : `k IN 1..dimindex (:N) ==> diff2c (\x:real^N. x$k) x`.
2785 Proof.
2786 move => k_ineq; rewrite diff2c diff2_x //.
2787 by rewrite -"GEN_ALL REAL_CONTINUOUS_CONTINUOUS1" partial2_x REAL_CONTINUOUS_CONST.
2788 Qed.
2789
2790 Lemma diff2c_domain_x k domain : `k IN 1..dimindex (:N) ==> diff2c_domain domain (\x:real^N. x$k)`.
2791 Proof. by move/diff2c_x; rewrite diff2c_domain => ->. Qed.
2792
2793
2794 End ElementaryFunctions.
2795
2796