Debian Codegraph @

Formal_ineqs/taylor/theory/taylor_interval.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 univariate 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/arith/interval_arith.hl\"".
18 "needs \"Formal_ineqs/trig/matan.hl\"".
19 "needs \"Multivariate/realanalysis.ml\"".
20
21 module Taylor_interval.
22
23 "open Ssrfun".
24 "open Ssrbool".
25 "open Ssrnat".
26 "open Interval_arith".
27 "open Matan".
28 "prioritize_real()".
29
30 "let derivative = new_definition `derivative f = \y. @d. (f has_real_derivative d) (atreal y)`".
31
32 "let nth_derivative = new_definition `nth_derivative n f = iter n derivative f`".
33
34
35 "let nth_differentiable = define `(nth_differentiable 0 f x <=> f real_continuous atreal x) /\
36 (nth_differentiable (SUC n) f x <=> nth_differentiable n f x /\
37 nth_derivative n f real_differentiable atreal x)`".
38
39 "let nth_differentiable_on = new_definition `nth_differentiable_on n s f <=>
40 !x. x IN s ==> nth_differentiable n f x`".
41
42 "let nth_differentiable_on_int = new_definition `nth_differentiable_on_int n int f <=>
43 !x. interval_arith x int ==> nth_differentiable n f x`".
44
45 "let nth_diff_weak = new_definition `nth_diff_weak n f x <=> f real_continuous atreal x /\
46 ?F. F 0 = f /\ !i. i < n ==> (F i has_real_derivative F (SUC i) x) (atreal x)`".
47
48
49 "let nth_diff_strong = new_definition `nth_diff_strong n f x <=>
50 ?s. real_open s /\ x IN s /\ nth_differentiable_on n s f`".
51
52 "let nth_diff_strong_int = new_definition `nth_diff_strong_int n int f <=>
53 !x. interval_arith x int ==> nth_diff_strong n f x`".
54
55
56 Section NthDerivatives.
57
58 Lemma derivative_eq_real_derivative: `derivative = real_derivative`.
59 Proof. by rewrite -eq_ext -eq_ext derivative real_derivative. Qed.
60
61 Lemma has_derivative_cond f x : `(?d. (f has_real_derivative d) (atreal x)) ==>
62 (f has_real_derivative (derivative f x)) (atreal x)`.
63 move => [d] df.
64 suff ->: `derivative f x = d`; first exact.
65 rewrite derivative /=; apply SELECT_UNIQUE => /= y; split => [df2 | -> //].
66 by apply: (REAL_DERIVATIVE_UNIQUE_ATREAL f x).
67 Qed.
68
69 Lemma has_derivative_alt f x : `f real_differentiable atreal x ==>
70 (f has_real_derivative (derivative f x)) (atreal x)`.
71 by rewrite real_differentiable => /has_derivative_cond. Qed.
72
73 Lemma derivative_unique f f' x :
74 `(f has_real_derivative f') (atreal x) ==> derivative f x = f'`.
75 move => df; apply: (REAL_DERIVATIVE_UNIQUE_ATREAL f x).
76 by rewrite df has_derivative_cond //; exists f'.
77 Qed.
78
79 Lemma derivative_unique_on s f f':
80 `(!x. x IN s ==> (f has_real_derivative f' x) (atreal x)) ==>
81 (!x. x IN s ==> f' x = derivative f x)`.
82 move => df x xs.
83 by rewrite (derivative_unique f `f' x`) // df.
84 Qed.
85
86 Lemma has_derivative_lemma f f' x : `f real_differentiable atreal x /\
87 derivative f x = f' ==>
88 (f has_real_derivative f') (atreal x)`.
89 by move => [diff <-]; rewrite has_derivative_alt. Qed.
90
91 Lemma nth_derivative0 f : `nth_derivative 0 f = f`.
92 by rewrite nth_derivative "GEN_ALL iter". Qed.
93
94 Lemma nth_derivativeS n f : `nth_derivative (SUC n) f = derivative (nth_derivative n f)`.
95 by rewrite !nth_derivative iterS. Qed.
96
97 Lemma nth_Sderivative n f : `nth_derivative (SUC n) f = nth_derivative n (derivative f)`.
98 by rewrite nth_derivative iterSr -nth_derivative. Qed.
99
100
101 Lemma nth_derivative1 f : `nth_derivative 1 f = derivative f`.
102 by rewrite ONE nth_derivativeS nth_derivative0. Qed.
103
104 Lemma nth_derivative2 f : `nth_derivative 2 f = derivative (derivative f)`.
105 by rewrite "ARITH_RULE `2 = SUC(SUC 0)`" nth_derivative !iterS "GEN_ALL iter". Qed.
106
107 Lemma nth_derivative_add n m f :
108 `nth_derivative n (nth_derivative m f) = nth_derivative (n + m) f`.
109 by rewrite !nth_derivative iter_add. Qed.
110
111 Lemma nth_diff_continuous n f x : `nth_differentiable n f x ==>
112 f real_continuous atreal x`.
113 elim: n => [|n IHn]; rewrite nth_differentiable //.
114 by move => [/IHn] /=.
115 Qed.
116
117 Lemma nth_differentiable_cond n f x : `nth_differentiable n f x ==>
118 !i. i < n ==> (nth_derivative i f has_real_derivative (nth_derivative (SUC i) f x)) (atreal x)`.
119 elim: n => [|n IHn]; first by rewrite ltn0.
120 rewrite nth_differentiable => [] [/IHn df_n dfn] i.
121 rewrite ltE leqSS leq_eqVlt; case => [-> | /df_n //].
122 by rewrite nth_derivativeS has_derivative_alt.
123 Qed.
124
125 Lemma nth_differentiable_on_cond n s f : `nth_differentiable_on n s f ==>
126 !x. x IN s ==>
127 !i. i < n ==> (nth_derivative i f has_real_derivative (nth_derivative (SUC i) f x)) (atreal x)`.
128 rewrite nth_differentiable_on => cond x.
129 by move/cond => /nth_differentiable_cond.
130 Qed.
131
132 Lemma nth_differentiable_eq n f x : `nth_differentiable n f x <=>
133 f real_continuous atreal x /\
134 !i. i < n ==> (nth_derivative i f has_real_derivative (nth_derivative (SUC i) f x)) (atreal x)`.
135 split => [dn_f | [f_cont]].
136 by rewrite (nth_diff_continuous dn_f) andTb; exact: nth_differentiable_cond.
137 elim: n => [|n IHn]; rewrite nth_differentiable // ltE leqSS leq_eqVlt => cond.
138 rewrite IHn ?andTb; first by move => i i_lt_n; apply: cond.
139 rewrite real_differentiable; exists `nth_derivative (SUC n) f x`.
140 exact: cond.
141 Qed.
142
143 Lemma nth_differentiable_on_int2 f int : `nth_differentiable_on_int 2 int f ==>
144 ?f' f''. f' = derivative f /\ f'' = nth_derivative 2 f /\
145 !x. interval_arith x int ==> (f has_real_derivative f' x) (atreal x) /\
146 (f' has_real_derivative f'' x) (atreal x)`.
147 rewrite nth_differentiable_on_int => h.
148 exists `derivative f` `nth_derivative 2 f` => /= x ineq.
149 rewrite -nth_derivative1 -{1}(nth_derivative0 f) {1}ONE "ARITH_RULE `2 = SUC 1`".
150 by rewrite !(nth_differentiable_cond `2`) // h //; arith.
151 Qed.
152
153
154 Lemma nth_mth_diff n m f x: `n <= m ==> nth_differentiable m f x ==> nth_differentiable n f x`.
155 Proof.
156 move => n_le_m; rewrite !nth_differentiable_eq => [] [-> cond]; rewrite andTb => i i_lt.
157 by apply: cond; apply: ltn_leq_trans n_le_m.
158 Qed.
159
160 Lemma nth_differentiable1 f x : `nth_differentiable 1 f x <=> f real_differentiable atreal x`.
161 rewrite ONE !"GEN_ALL nth_differentiable" nth_derivative0; split => [-> | df].
162 by rewrite REAL_DIFFERENTIABLE_IMP_CONTINUOUS_ATREAL.
163 Qed.
164
165 Lemma nth_diff_imp_diff n f x : `0 < n ==> nth_differentiable n f x ==>
166 f real_differentiable atreal x`.
167 by rewrite ltE -ONE => ineq df; rewrite -nth_differentiable1; apply: nth_mth_diff; exists n. Qed.
168
169 Lemma nth_derivative_continuous n f x i: `nth_differentiable n f x ==> i < n ==>
170 nth_derivative i f real_continuous atreal x`.
171 rewrite nth_differentiable_eq => [] [_] df.
172 move/df => cond; apply: REAL_DIFFERENTIABLE_IMP_CONTINUOUS_ATREAL.
173 by rewrite real_differentiable; exists `nth_derivative (SUC i) f x`.
174 Qed.
175
176 Lemma ith_derivative_differentiable i n f x: `nth_differentiable n f x ==> i < n ==>
177 nth_differentiable (n - i) (nth_derivative i f) x`.
178 move => dnf.
179 move: (dnf); rewrite !nth_differentiable_eq => [] [_] cond i_lt_n.
180 rewrite (nth_derivative_continuous dnf) // andTb => j j_lt_ni.
181 by rewrite !nth_derivative_add addSn cond; move: j_lt_ni; arith.
182 Qed.
183
184
185 Lemma nth_diff_strong_imp_diff n f x :
186 `nth_diff_strong n f x ==> nth_differentiable n f x`.
187 rewrite nth_diff_strong => [] [s] [_] [xs]; rewrite nth_differentiable_on => h.
188 exact: h.
189 Qed.
190
191
192 Section DerivativeArith.
193
194 (* Elementary derivatives *)
195 Section ElementaryDerivatives.
196
197 Lemma HAS_REAL_DERIVATIVE_ABS_POS x : `&0 < x ==> (abs has_real_derivative &1) (atreal x)`.
198 Proof.
199 move => x_pos.
200 apply: HAS_REAL_DERIVATIVE_TRANSFORM_ATREAL.
201 exists `\x. x` x; rewrite HAS_REAL_DERIVATIVE_ID x_pos /= => t.
202 by move: x_pos; arith.
203 Qed.
204
205 Lemma HAS_REAL_DERIVATIVE_ABS_NEG x : `x < &0 ==> (abs has_real_derivative (-- &1)) (atreal x)`.
206 Proof.
207 move => x_neg.
208 apply: HAS_REAL_DERIVATIVE_TRANSFORM_ATREAL.
209 exists `\x. --x` `--x`; rewrite HAS_REAL_DERIVATIVE_NEG ?HAS_REAL_DERIVATIVE_ID /=.
210 split; first by move: x_neg; arith.
211 by move => t; move: x_neg; arith.
212 Qed.
213
214 Lemma derivative_x : `derivative (\x. x) = (\x. &1)`.
215 rewrite -eq_ext => x /=.
216 by apply: derivative_unique; rewrite HAS_REAL_DERIVATIVE_ID.
217 Qed.
218
219 Lemma derivative_const c : `derivative (\x. c) = (\x. &0)`.
220 rewrite -eq_ext => x /=.
221 by apply: derivative_unique; rewrite HAS_REAL_DERIVATIVE_CONST.
222 Qed.
223
224 Lemma derivative_abs_pos x : `&0 < x ==> derivative abs x = &1`.
225 Proof.
226 move => x_pos.
227 by apply: derivative_unique; rewrite HAS_REAL_DERIVATIVE_ABS_POS.
228 Qed.
229
230 Lemma derivative_abs_neg x : `x < &0 ==> derivative abs x = -- &1`.
231 Proof.
232 move => x_neg.
233 by apply: derivative_unique; rewrite HAS_REAL_DERIVATIVE_ABS_NEG.
234 Qed.
235
236 Lemma derivative_pow_x n : `derivative (\x. x pow n) = (\x. &n * x pow (n - 1))`.
237 Proof.
238 rewrite -eq_ext => x /=; apply: derivative_unique.
239 rewrite -[`x pow (n - 1)`]REAL_MUL_RID HAS_REAL_DERIVATIVE_POW_ATREAL.
240 by rewrite HAS_REAL_DERIVATIVE_ID.
241 Qed.
242
243 Lemma derivative_pow2_x : `derivative (\x. x pow 2) = (\x. &2 * x)`.
244 Proof. by rewrite derivative_pow_x "ARITH_RULE `2 - 1 = 1`" REAL_POW_1. Qed.
245
246 Lemma derivative_pow3_x : `derivative (\x. x pow 3) = (\x. &3 * x pow 2)`.
247 Proof. by rewrite derivative_pow_x "ARITH_RULE `3 - 1 = 2`". Qed.
248
249 Lemma derivative_inv x : `~(x = &0) ==> derivative inv x = -- inv (x * x)`.
250 Proof.
251 move => xn0.
252 by apply: derivative_unique; rewrite -REAL_POW_2 HAS_REAL_DERIVATIVE_INV_BASIC.
253 Qed.
254
255 Lemma derivative_atn : `derivative atn = (\x. inv (&1 + x * x))`.
256 Proof.
257 rewrite -eq_ext -REAL_POW_2 => x /=.
258 by apply: derivative_unique; rewrite HAS_REAL_DERIVATIVE_ATN.
259 Qed.
260
261 Lemma derivative_exp : `derivative exp = exp`.
262 Proof.
263 rewrite -eq_ext => x /=.
264 by apply: derivative_unique; rewrite HAS_REAL_DERIVATIVE_EXP.
265 Qed.
266
267 Lemma derivative_log x : `&0 < x ==> derivative log x = inv x`.
268 Proof. by move => x_ineq; apply: derivative_unique; rewrite HAS_REAL_DERIVATIVE_LOG. Qed.
269
270 Lemma derivative_sin : `derivative sin = cos`.
271 Proof.
272 rewrite -eq_ext => x /=.
273 by apply: derivative_unique; rewrite HAS_REAL_DERIVATIVE_SIN.
274 Qed.
275
276 Lemma derivative_cos : `derivative cos = (\x. --sin x)`.
277 Proof.
278 rewrite -eq_ext => x /=.
279 by apply: derivative_unique; rewrite HAS_REAL_DERIVATIVE_COS.
280 Qed.
281
282 Lemma derivative_asn x : `abs x < &1 ==> derivative asn x = inv(sqrt(&1 - x * x))`.
283 Proof.
284 move => x_ineq.
285 by apply: derivative_unique; rewrite -REAL_POW_2 HAS_REAL_DERIVATIVE_ASN.
286 Qed.
287
288 Lemma derivative_acs x : `abs x < &1 ==> derivative acs x = --inv(sqrt(&1 - x * x))`.
289 Proof.
290 move => x_ineq.
291 by apply: derivative_unique; rewrite -REAL_POW_2 HAS_REAL_DERIVATIVE_ACS.
292 Qed.
293
294 Lemma derivative_sqrt x : `&0 < x ==> derivative sqrt x = inv (&2 * sqrt x)`.
295 Proof.
296 move => xg0.
297 by apply: derivative_unique; rewrite HAS_REAL_DERIVATIVE_SQRT.
298 Qed.
299
300 Lemma derivative_matan x : `derivative matan x = dmatan x`.
301 Proof. by rewrite derivative_eq_real_derivative dmatan. Qed.
302
303 Lemma matan_differentiable x : `-- &1 < x ==> matan real_differentiable atreal x`.
304 Proof.
305 move => x_ineq.
306 case: (EXCLUDED_MIDDLE `x < &1`) => x_ineq2.
307 by rewrite matan_real_derivative_abs1; move: x_ineq x_ineq2; arith.
308 rewrite real_differentiable.
309 have := matan_has_derivative_gt0 x.
310 set t := `inv _1 - _2`.
311 by move => h; exists t; apply: h; move: x_ineq2; arith.
312 Qed.
313
314 Lemma derivative_composition f g x: `f real_differentiable atreal x ==>
315 g real_differentiable atreal (f x) ==>
316 derivative (\x. g (f x)) x = derivative f x * derivative g (f x)`.
317 Proof.
318 move => /has_derivative_alt df /has_derivative_alt dg; apply: derivative_unique.
319 have := "GEN_ALL HAS_REAL_DERIVATIVE_CHAIN"
320 `derivative f x` `derivative g` `\y. y = f x` f g;
321 "ANTS_TAC"; first by move => y ->.
322 by move => [_]; apply.
323 Qed.
324
325
326 Section ElementaryCompose.
327
328 Lemma REAL_DIFFERENTIABLE_AT_INV x : `~(x = &0) ==> inv real_differentiable atreal x`.
329 Proof.
330 move => xn0.
331 have := REAL_DIFFERENTIABLE_INV_ATREAL `(\x. x:real)` x.
332 by rewrite /= REAL_DIFFERENTIABLE_ID xn0 /=; rewr ETA_AX.
333 Qed.
334
335 Lemma REAL_DIFFERENTIABLE_AT_ABS_POS x : `&0 < x ==> abs real_differentiable atreal x`.
336 Proof.
337 move => x_pos.
338 by rewrite real_differentiable; exists `&1`; rewrite HAS_REAL_DERIVATIVE_ABS_POS.
339 Qed.
340
341 Lemma REAL_DIFFERENTIABLE_AT_ABS_NEG x : `x < &0 ==> abs real_differentiable atreal x`.
342 Proof.
343 move => x_pos.
344 by rewrite real_differentiable; exists `-- &1`; rewrite HAS_REAL_DERIVATIVE_ABS_NEG.
345 Qed.
346
347 Variable f : `:real->real`.
348 Variable x : `:real`.
349 Hypothesis df : `f real_differentiable atreal x`.
350
351 Lemma derivative_compose_abs_pos : `&0 < f x ==> (\x. abs (f x)) real_differentiable atreal x /\
352 derivative (\x. abs (f x)) x = derivative f x`.
353 Proof.
354 move => f_ineq; split.
355 rewrite -(o_THM `abs`); rewr ETA_AX; apply: REAL_DIFFERENTIABLE_COMPOSE_ATREAL.
356 by rewrite df REAL_DIFFERENTIABLE_AT_ABS_POS.
357 rewrite derivative_composition ?df ?REAL_DIFFERENTIABLE_AT_ABS_POS //.
358 by rewrite derivative_abs_pos // REAL_MUL_RID.
359 Qed.
360
361 Lemma derivative_compose_abs_neg : `f x < &0 ==> (\x. abs (f x)) real_differentiable atreal x /\
362 derivative (\x. abs (f x)) x = --derivative f x`.
363 Proof.
364 move => f_ineq; split.
365 rewrite -(o_THM `abs`); rewr ETA_AX; apply: REAL_DIFFERENTIABLE_COMPOSE_ATREAL.
366 by rewrite df REAL_DIFFERENTIABLE_AT_ABS_NEG.
367 rewrite derivative_composition ?df ?REAL_DIFFERENTIABLE_AT_ABS_NEG //.
368 by rewrite derivative_abs_neg // REAL_MUL_RNEG REAL_MUL_RID.
369 Qed.
370
371 Lemma derivative_compose_pow n : `(\x. (f x) pow n) real_differentiable atreal x /\
372 derivative (\x. (f x) pow n) x = &n * (f x) pow (n - 1) * derivative f x`.
373 Proof.
374 split; first by rewrite REAL_DIFFERENTIABLE_POW_ATREAL.
375 apply: derivative_unique; rewrite HAS_REAL_DERIVATIVE_POW_ATREAL.
376 by rewrite has_derivative_alt.
377 Qed.
378
379 Lemma derivative_compose_pow2 : `(\x. (f x) pow 2) real_differentiable atreal x /\
380 derivative (\x. (f x) pow 2) x = &2 * f x * derivative f x`.
381 Proof. by rewrite !derivative_compose_pow andTb "ARITH_RULE `2 - 1 = 1`" REAL_POW_1. Qed.
382
383 Lemma derivative_compose_pow3 : `(\x. (f x) pow 3) real_differentiable atreal x /\
384 derivative (\x. (f x) pow 3) x = &3 * (f x pow 2) * derivative f x`.
385 Proof. by rewrite !derivative_compose_pow andTb "ARITH_RULE `3 - 1 = 2`". Qed.
386
387 Lemma derivative_compose_atn : `(\x. atn (f x)) real_differentiable atreal x /\
388 derivative (\x. atn (f x)) x = derivative f x / (&1 + f x * f x)`.
389 Proof.
390 split.
391 rewrite -(o_THM `atn`); rewr ETA_AX; apply: REAL_DIFFERENTIABLE_COMPOSE_ATREAL.
392 by rewrite REAL_DIFFERENTIABLE_AT_ATN df.
393 rewrite derivative_composition ?df ?REAL_DIFFERENTIABLE_AT_ATN //.
394 by rewrite derivative_atn /= real_div.
395 Qed.
396
397 Lemma derivative_compose_exp : `(\x. exp (f x)) real_differentiable atreal x /\
398 derivative (\x. exp (f x)) x = exp (f x) * derivative f x`.
399 Proof.
400 split.
401 rewrite -(o_THM `exp`); rewr ETA_AX; apply: REAL_DIFFERENTIABLE_COMPOSE_ATREAL.
402 by rewrite REAL_DIFFERENTIABLE_AT_EXP df.
403 rewrite derivative_composition ?df ?REAL_DIFFERENTIABLE_AT_EXP //.
404 by rewrite derivative_exp REAL_MUL_SYM.
405 Qed.
406
407 Lemma derivative_compose_log : `&0 < f x ==> (\x. log (f x)) real_differentiable atreal x /\
408 derivative (\x. log (f x)) x = derivative f x / f x`.
409 Proof.
410 move => f_ineq; split.
411 rewrite -(o_THM `log`); rewr ETA_AX; apply: REAL_DIFFERENTIABLE_COMPOSE_ATREAL.
412 by rewrite df REAL_DIFFERENTIABLE_AT_LOG.
413 rewrite derivative_composition ?df ?REAL_DIFFERENTIABLE_AT_LOG //.
414 by rewrite derivative_log // real_div.
415 Qed.
416
417 Lemma derivative_compose_cos : `(\x. cos (f x)) real_differentiable atreal x /\
418 derivative (\x. cos (f x)) x = --(sin (f x) * derivative f x)`.
419 Proof.
420 split.
421 rewrite -(o_THM `cos`); rewr ETA_AX; apply: REAL_DIFFERENTIABLE_COMPOSE_ATREAL.
422 by rewrite REAL_DIFFERENTIABLE_AT_COS df.
423 rewrite derivative_composition ?df ?REAL_DIFFERENTIABLE_AT_COS //.
424 by rewrite derivative_cos REAL_MUL_SYM REAL_NEG_LMUL.
425 Qed.
426
427 Lemma derivative_compose_sin : `(\x. sin (f x)) real_differentiable atreal x /\
428 derivative (\x. sin (f x)) x = cos (f x) * derivative f x`.
429 Proof.
430 split.
431 rewrite -(o_THM `sin`); rewr ETA_AX; apply: REAL_DIFFERENTIABLE_COMPOSE_ATREAL.
432 by rewrite REAL_DIFFERENTIABLE_AT_SIN df.
433 rewrite derivative_composition ?df ?REAL_DIFFERENTIABLE_AT_SIN //.
434 by rewrite derivative_sin REAL_MUL_SYM.
435 Qed.
436
437 Lemma derivative_compose_inv : `~(f x = &0) ==>
438 (\x. inv (f x)) real_differentiable atreal x /\
439 derivative (\x. inv (f x)) x = -- inv (f x * f x) * derivative f x`.
440 Proof.
441 move => fn0; split; first by apply: REAL_DIFFERENTIABLE_INV_ATREAL.
442 by rewrite derivative_composition ?derivative_inv ?REAL_MUL_SYM // df REAL_DIFFERENTIABLE_AT_INV.
443 Qed.
444
445 Lemma derivative_compose_sqrt : `&0 < f x ==>
446 (\x. sqrt (f x)) real_differentiable atreal x /\
447 derivative (\x. sqrt (f x)) x = derivative f x / (&2 * sqrt (f x))`.
448 Proof.
449 move => f_pos; split.
450 rewrite -(o_THM `sqrt`); rewr ETA_AX; apply: REAL_DIFFERENTIABLE_COMPOSE_ATREAL.
451 by rewrite df andTb; apply: REAL_DIFFERENTIABLE_AT_SQRT.
452 rewrite derivative_composition ?df ?REAL_DIFFERENTIABLE_AT_SQRT //.
453 by rewrite derivative_sqrt // real_div.
454 Qed.
455
456 Lemma derivative_compose_acs : `abs (f x) < &1 ==>
457 (\x. acs (f x)) real_differentiable atreal x /\
458 derivative (\x. acs (f x)) x = -- (derivative f x / sqrt (&1 - f x * f x))`.
459 Proof.
460 move => f_abs; split.
461 rewrite -(o_THM `acs`); rewr ETA_AX; apply: REAL_DIFFERENTIABLE_COMPOSE_ATREAL.
462 by rewrite df andTb REAL_DIFFERENTIABLE_AT_ACS.
463 rewrite derivative_composition ?df ?REAL_DIFFERENTIABLE_AT_ACS //.
464 by rewrite derivative_acs // REAL_MUL_RNEG real_div.
465 Qed.
466
467 Lemma derivative_compose_asn : `abs (f x) < &1 ==>
468 (\x. asn (f x)) real_differentiable atreal x /\
469 derivative (\x. asn (f x)) x = derivative f x / sqrt (&1 - f x * f x)`.
470 Proof.
471 move => f_abs; split.
472 rewrite -(o_THM `asn`); rewr ETA_AX; apply: REAL_DIFFERENTIABLE_COMPOSE_ATREAL.
473 by rewrite df andTb REAL_DIFFERENTIABLE_AT_ASN.
474 rewrite derivative_composition ?df ?REAL_DIFFERENTIABLE_AT_ASN //.
475 by rewrite derivative_asn // real_div.
476 Qed.
477
478 Lemma derivative_compose_matan : `-- &1 < f x ==>
479 (\x. matan (f x)) real_differentiable atreal x /\
480 derivative (\x. matan (f x)) x = dmatan (f x) * derivative f x`.
481 Proof.
482 move => f_ineq; split.
483 rewrite -(o_THM `matan`); rewr ETA_AX; apply: REAL_DIFFERENTIABLE_COMPOSE_ATREAL.
484 by rewrite df matan_differentiable.
485 rewrite derivative_composition ?df ?matan_differentiable //.
486 by rewrite derivative_matan REAL_MUL_SYM.
487 Qed.
488
489
490 End ElementaryCompose.
491
492
493 End ElementaryDerivatives.
494
495
496
497 Variables f g : `:real -> real`.
498 Variables x c : `:real`.
499
500
501 (* One function *)
502 Hypothesis df : `f real_differentiable atreal x`.
503
504 Lemma derivative_scale : `derivative (\x. c * f x) x = c * derivative f x`.
505 by apply: derivative_unique; rewrite HAS_REAL_DERIVATIVE_LMUL_ATREAL has_derivative_alt. Qed.
506
507 Lemma derivative_neg : `derivative (\x. -- f x) x = -- derivative f x`.
508 by apply: derivative_unique; rewrite HAS_REAL_DERIVATIVE_NEG has_derivative_alt. Qed.
509
510 Lemma derivative_pow n : `derivative (\x. f x pow n) x = &n * f x pow (n - 1) * derivative f x`.
511 by apply: derivative_unique; rewrite HAS_REAL_DERIVATIVE_POW_ATREAL has_derivative_alt. Qed.
512
513
514 (* The second function *)
515 Hypothesis dg : `g real_differentiable atreal x`.
516
517 Lemma derivative_add : `derivative (\x. f x + g x) x = derivative f x + derivative g x`.
518 by apply: derivative_unique; rewrite HAS_REAL_DERIVATIVE_ADD !has_derivative_alt. Qed.
519
520 Lemma derivative_mul :
521 `derivative (\x. f x * g x) x = f x * derivative g x + derivative f x * g x`.
522 by apply: derivative_unique; rewrite HAS_REAL_DERIVATIVE_MUL_ATREAL !has_derivative_alt. Qed.
523
524 Lemma derivative_sub : `derivative (\x. f x - g x) x = derivative f x - derivative g x`.
525 by apply: derivative_unique; rewrite HAS_REAL_DERIVATIVE_SUB !has_derivative_alt. Qed.
526
527 Lemma derivative_div : `~(g x = &0) ==>
528 derivative (\x. f x / g x) x = (derivative f x * g x - f x * derivative g x) / (g x * g x)`.
529 move => gn0; apply: derivative_unique; rewrite -REAL_POW_2 HAS_REAL_DERIVATIVE_DIV_ATREAL //.
530 by rewrite !has_derivative_alt.
531 Qed.
532
533
534 End DerivativeArith.
535
536
537 Section MoreDerivativeArith.
538
539 Lemma differentiable_sum_numseg G n m x :
540 `(!i. i IN n..m ==> G i real_differentiable atreal x) ==>
541 (\x. sum (n..m) (\i. G i x)) real_differentiable atreal x`.
542 elim: m => [|m IHm] dG; rewrite !"GEN_ALL SUM_CLAUSES_NUMSEG".
543 case: (EXCLUDED_MIDDLE `n = 0`) => /= n_eq_0; rewr ETA_AX REAL_DIFFERENTIABLE_CONST //.
544 by rewrite dG IN_NUMSEG n_eq_0 leqnn.
545 case: (EXCLUDED_MIDDLE `n <= SUC m`) => /= n_le_Sm; last first.
546 apply: IHm => i i_in; apply: dG.
547 by move: i_in; rewrite !IN_NUMSEG; arith.
548 rewrite REAL_DIFFERENTIABLE_ADD; rewr ETA_AX; rewrite dG ?IHm // IN_NUMSEG ?n_le_Sm ?leqnn //.
549 move => i ineq; apply: dG; rewrite IN_NUMSEG.
550 by move: ineq; arith.
551 Qed.
552
553 (* Sum *)
554 Lemma derivative_sum_numseg G n m x : `(!i. i IN n..m ==> G i real_differentiable atreal x) ==>
555 derivative (\x. sum (n..m) (\i. G i x)) x = sum (n..m) (\i. derivative (G i) x)`.
556 elim: m => [|m IHm] dG; rewrite !"GEN_ALL SUM_CLAUSES_NUMSEG".
557 by case: `n = 0` => /=; rewr ETA_AX // derivative_const.
558 case: (EXCLUDED_MIDDLE `n <= SUC m`) => /= n_le_Sm; last first.
559 apply: IHm => i i_in; apply: dG.
560 by move: i_in; rewrite !IN_NUMSEG; arith.
561 rewrite -IHm.
562 move => i i_in; apply: dG.
563 move: i_in; rewrite !IN_NUMSEG; arith.
564 rewrite derivative_add; rewr ETA_AX //.
565 rewrite dG ?IN_NUMSEG ?leqnn // andbT differentiable_sum_numseg => i i_in.
566 by apply: dG; move: i_in; rewrite !IN_NUMSEG; arith.
567 Qed.
568
569 End MoreDerivativeArith.
570
571
572 Lemma HAS_REAL_DERIVATIVE_LOCAL f g x g': `(g has_real_derivative g') (atreal x) /\
573 (?s. real_open s /\ x IN s /\ (!y. y IN s ==> f y = g y))
574 ==> (f has_real_derivative g') (atreal x)`.
575 Proof.
576 move => [dg] [s] [open_s] [xs] f_eq_g.
577 move: dg; rewrite -!(HAS_REAL_DERIVATIVE_WITHIN_REAL_OPEN open_s) // => dg.
578 apply: (HAS_REAL_DERIVATIVE_TRANSFORM_WITHIN dg).
579 by exists `&1`; rewrite REAL_LT_01 xs !andTb => y [] /f_eq_g ->.
580 Qed.
581
582
583 Lemma differentiable_local f g x s : `g real_differentiable atreal x /\ real_open s /\ x IN s /\
584 (!y. y IN s ==> f y = g y) ==> f real_differentiable atreal x`.
585 rewrite !real_differentiable => [] [] [f'] dg [open_s] [xs] eq.
586 exists f'; apply: HAS_REAL_DERIVATIVE_LOCAL.
587 by exists g; rewrite dg andTb; exists s.
588 Qed.
589
590
591
592 Section NthDerivativeArith.
593
594 Variables f g : `:real->real`.
595 Variable int : `:real#real`.
596 Variable n : `:num`.
597
598
599 (* Unary operation *)
600 Hypothesis df : `nth_diff_strong_int n int f`.
601
602 Lemma nth_derivative_scale_strong c i x : `interval_arith x int ==> i <= n ==>
603 ?s. real_open s /\ x IN s /\
604 !y. y IN s ==> nth_derivative i (\y. c * f y) y = c * nth_derivative i f y`.
605 move: df; rewrite nth_diff_strong_int nth_diff_strong => df.
606 move/df => [s] [open_s] [xs]; rewrite nth_differentiable_on nth_differentiable_eq => diff.
607 elim: i => [_|i IHi]; first by rewrite !nth_derivative0; exists s.
608 rewrite nth_derivativeS -ltE => i_lt_n.
609 move: (IHi (ltnW i_lt_n)) => [t] [open_t] [xt] eq; move: IHi => _.
610 exists `s INTER t`; rewrite REAL_OPEN_INTER // !IN_INTER xt xs !andTb => y [ys yt].
611 apply: derivative_unique.
612 apply: HAS_REAL_DERIVATIVE_LOCAL.
613 exists `\y. c * nth_derivative i f y`.
614 rewrite HAS_REAL_DERIVATIVE_LMUL_ATREAL ?andTb.
615 by rewr ETA_AX; rewrite (diff ys).
616 exists `s INTER t`; rewrite REAL_OPEN_INTER // !IN_INTER {1}yt {1}ys !andTb => z z_in /=.
617 by rewrite eq.
618 Qed.
619
620 Lemma nth_derivative_scale_strong_all c x : `interval_arith x int ==>
621 ?s. real_open s /\ x IN s /\
622 !i y. i <= n /\ y IN s ==> nth_derivative i (\y. c * f y) y = c * nth_derivative i f y`.
623 move => /(nth_derivative_scale_strong c) h.
624 set P := `\i s. real_open s /\ x IN s /\
625 (!y. y IN s ==> nth_derivative i (\y. c * f y) y = c * nth_derivative i f y)`.
626 have sel_P : `!i. i <= n:num ==> P i ((@) (P i))`.
627 move => i i_le_n; apply SELECT_AX.
628 move: (h i_le_n) => [s] cond.
629 by exists s; rewrite -P_def /=.
630 set S := `INTERS (IMAGE (\i. (@) (P i)) (0..n))`.
631 exists S.
632 rewrite -S_def REAL_OPEN_INTERS ?FINITE_IMAGE ?FINITE_NUMSEG ?IN_IMAGE ?andTb.
633 move => t [i] [->]; rewrite IN_NUMSEG_0 => /sel_P.
634 by rewrite -{1}P_def /=.
635 rewrite !IN_INTERS !IN_IMAGE; split.
636 move => t [i] [->]; rewrite IN_NUMSEG_0 => /sel_P.
637 by rewrite -{1}P_def /=.
638 move => i y [i_le_n].
639 move: (sel_P i_le_n); rewrite -{1}P_def /= => [] [_] [_] y_in /(_ `(@) (P i)`).
640 "ANTS_TAC"; first by exists i; rewrite IN_NUMSEG_0.
641 exact: y_in.
642 Qed.
643
644
645 Lemma nth_derivative_scale c i x : `interval_arith x int ==> i <= n ==>
646 nth_derivative i (\x. c * f x) x = c * nth_derivative i f x`.
647 move => ineq i_le_n.
648 have := nth_derivative_scale_strong c ineq i_le_n.
649 move => [s] [_] [xs] h.
650 exact: h.
651 Qed.
652
653
654 Lemma nth_diff_scale c : `nth_diff_strong_int n int (\x. c * f x)`.
655 move: (df); rewrite !nth_diff_strong_int !nth_diff_strong !nth_differentiable_on !nth_differentiable_eq.
656 move => df x ineq.
657 have := nth_derivative_scale_strong_all c ineq.
658 move => [s] [open_s] [xs] diff.
659 move: (df ineq) => [t] [open_t] [xt] diff2.
660 exists `s INTER t`; rewrite REAL_OPEN_INTER // IN_INTER {1}xs {1}xt !andTb => y [ys yt].
661 rewrite REAL_CONTINUOUS_LMUL ?diff2 // andTb => i i_lt_n.
662 rewrite diff ?ys -?ltE //.
663 apply: HAS_REAL_DERIVATIVE_LOCAL.
664 exists `(\y. c * nth_derivative i f y)`.
665 rewrite HAS_REAL_DERIVATIVE_LMUL_ATREAL ?andTb; first by rewr ETA_AX; rewrite (diff2 yt).
666 exists s; rewrite open_s {1}ys !andTb => z zs /=.
667 by apply: diff; rewrite ltnW.
668 Qed.
669
670
671 (* Binary operations *)
672 Hypothesis dg : `nth_diff_strong_int n int g`.
673
674 (* Addition *)
675 Lemma nth_derivative_add_strong i x : `interval_arith x int ==> i <= n ==>
676 ?s. real_open s /\ x IN s /\
677 !y. y IN s ==> nth_derivative i (\y. f y + g y) y = nth_derivative i f y + nth_derivative i g y`.
678 move: df dg; rewrite !nth_diff_strong_int !nth_diff_strong => df dg ineq.
679 move: (df ineq) => [sf] [open_sf] [xsf]; move: df => _.
680 move: (dg ineq) => [sg] [open_sg] [xsg]; move: dg => _.
681 rewrite !nth_differentiable_on !nth_differentiable_eq => diff_g diff_f.
682 elim: i => [_|i IHi]; first by rewrite !nth_derivative0; exists sf.
683 rewrite nth_derivativeS -ltE => i_lt_n.
684 move: (IHi (ltnW i_lt_n)) => [t] [open_t] [xt] eq; move: IHi => _.
685 exists `sf INTER sg INTER t`.
686 rewrite !REAL_OPEN_INTER // !IN_INTER xt xsf xsg !andTb => y [ysf] [ysg yt].
687 apply: derivative_unique.
688 apply: HAS_REAL_DERIVATIVE_LOCAL.
689 exists `(\y. nth_derivative i f y + nth_derivative i g y)`.
690 rewrite HAS_REAL_DERIVATIVE_ADD ?andTb.
691 by rewr ETA_AX; rewrite (diff_f ysf) // (diff_g ysg).
692 exists `sf INTER sg INTER t`; rewrite !REAL_OPEN_INTER // !IN_INTER {1}yt {1}ysf {1}ysg !andTb.
693 by move => z z_in /=; rewrite eq.
694 Qed.
695
696 Lemma nth_derivative_add_strong_all x : `interval_arith x int ==>
697 ?s. real_open s /\ x IN s /\
698 !i y. i <= n /\ y IN s ==>
699 nth_derivative i (\y. f y + g y) y = nth_derivative i f y + nth_derivative i g y`.
700 move => /(nth_derivative_add_strong) h.
701 set P := `\i s. real_open s /\ x IN s /\
702 (!y. y IN s ==> nth_derivative i (\y. f y + g y) y = nth_derivative i f y + nth_derivative i g y)`.
703 have sel_P : `!i. i <= n:num ==> P i ((@) (P i))`.
704 move => i i_le_n; apply SELECT_AX.
705 move: (h i_le_n) => [s] cond.
706 by exists s; rewrite -P_def /=.
707 set S := `INTERS (IMAGE (\i. (@) (P i)) (0..n))`.
708 exists S.
709 rewrite -S_def REAL_OPEN_INTERS ?FINITE_IMAGE ?FINITE_NUMSEG ?IN_IMAGE ?andTb.
710 move => t [i] [->]; rewrite IN_NUMSEG_0 => /sel_P.
711 by rewrite -{1}P_def /=.
712 rewrite !IN_INTERS !IN_IMAGE; split.
713 move => t [i] [->]; rewrite IN_NUMSEG_0 => /sel_P.
714 by rewrite -{1}P_def /=.
715 move => i y [i_le_n].
716 move: (sel_P i_le_n); rewrite -{1}P_def /= => [] [_] [_] y_in /(_ `(@) (P i)`).
717 "ANTS_TAC"; first by exists i; rewrite IN_NUMSEG_0.
718 exact: y_in.
719 Qed.
720
721
722 Lemma nth_derivative_add i x : `interval_arith x int ==> i <= n ==>
723 nth_derivative i (\x. f x + g x) x = nth_derivative i f x + nth_derivative i g x`.
724 move => ineq i_le_n.
725 have := nth_derivative_add_strong ineq i_le_n.
726 move => [s] [_] [xs] h.
727 exact: h.
728 Qed.
729
730
731 Lemma nth_diff_add : `nth_diff_strong_int n int (\x. f x + g x)`.
732 move: (df) (dg).
733 rewrite !nth_diff_strong_int !nth_diff_strong !nth_differentiable_on !nth_differentiable_eq.
734 move => df dg x ineq.
735 have := nth_derivative_add_strong_all ineq.
736 move => [s] [open_s] [xs] diff.
737 move: (df ineq) => [tf] [open_tf] [xtf] diff_f.
738 move: (dg ineq) => [tg] [open_tg] [xtg] diff_g.
739 exists `s INTER tf INTER tg`; rewrite !REAL_OPEN_INTER // !IN_INTER {1}xs {1}xtf {1}xtg !andTb.
740 move => y [ys [ytf ytg]].
741 rewrite REAL_CONTINUOUS_ADD ?diff_f ?diff_g // andTb => i i_lt_n.
742 rewrite diff ?ys -?ltE //.
743 apply: HAS_REAL_DERIVATIVE_LOCAL.
744 exists `(\y. nth_derivative i f y + nth_derivative i g y)`.
745 rewrite HAS_REAL_DERIVATIVE_ADD ?andTb; first by rewr ETA_AX; rewrite (diff_f ytf) // (diff_g ytg).
746 exists s; rewrite open_s {1}ys !andTb => z zs /=.
747 by apply: diff; rewrite ltnW.
748 Qed.
749
750
751 (* Subtraction *)
752 Lemma nth_derivative_sub_strong i x : `interval_arith x int ==> i <= n ==>
753 ?s. real_open s /\ x IN s /\
754 !y. y IN s ==> nth_derivative i (\y. f y - g y) y = nth_derivative i f y - nth_derivative i g y`.
755 move: df dg; rewrite !nth_diff_strong_int !nth_diff_strong => df dg ineq.
756 move: (df ineq) => [sf] [open_sf] [xsf]; move: df => _.
757 move: (dg ineq) => [sg] [open_sg] [xsg]; move: dg => _.
758 rewrite !nth_differentiable_on !nth_differentiable_eq => diff_g diff_f.
759 elim: i => [_|i IHi]; first by rewrite !nth_derivative0; exists sf.
760 rewrite nth_derivativeS -ltE => i_lt_n.
761 move: (IHi (ltnW i_lt_n)) => [t] [open_t] [xt] eq; move: IHi => _.
762 exists `sf INTER sg INTER t`.
763 rewrite !REAL_OPEN_INTER // !IN_INTER xt xsf xsg !andTb => y [ysf] [ysg yt].
764 apply: derivative_unique.
765 apply: HAS_REAL_DERIVATIVE_LOCAL.
766 exists `(\y. nth_derivative i f y - nth_derivative i g y)`.
767 rewrite HAS_REAL_DERIVATIVE_SUB ?andTb.
768 by rewr ETA_AX; rewrite (diff_f ysf) // (diff_g ysg).
769 exists `sf INTER sg INTER t`; rewrite !REAL_OPEN_INTER // !IN_INTER {1}yt {1}ysf {1}ysg !andTb.
770 by move => z z_in /=; rewrite eq.
771 Qed.
772
773 Lemma nth_derivative_sub_strong_all x : `interval_arith x int ==>
774 ?s. real_open s /\ x IN s /\
775 !i y. i <= n /\ y IN s ==>
776 nth_derivative i (\y. f y - g y) y = nth_derivative i f y - nth_derivative i g y`.
777 move => /(nth_derivative_sub_strong) h.
778 set P := `\i s. real_open s /\ x IN s /\
779 (!y. y IN s ==> nth_derivative i (\y. f y - g y) y = nth_derivative i f y - nth_derivative i g y)`.
780 have sel_P : `!i. i <= n:num ==> P i ((@) (P i))`.
781 move => i i_le_n; apply SELECT_AX.
782 move: (h i_le_n) => [s] cond.
783 by exists s; rewrite -P_def /=.
784 set S := `INTERS (IMAGE (\i. (@) (P i)) (0..n))`.
785 exists S.
786 rewrite -S_def REAL_OPEN_INTERS ?FINITE_IMAGE ?FINITE_NUMSEG ?IN_IMAGE ?andTb.
787 move => t [i] [->]; rewrite IN_NUMSEG_0 => /sel_P.
788 by rewrite -{1}P_def /=.
789 rewrite !IN_INTERS !IN_IMAGE; split.
790 move => t [i] [->]; rewrite IN_NUMSEG_0 => /sel_P.
791 by rewrite -{1}P_def /=.
792 move => i y [i_le_n].
793 move: (sel_P i_le_n); rewrite -{1}P_def /= => [] [_] [_] y_in /(_ `(@) (P i)`).
794 "ANTS_TAC"; first by exists i; rewrite IN_NUMSEG_0.
795 exact: y_in.
796 Qed.
797
798
799 Lemma nth_derivative_sub i x : `interval_arith x int ==> i <= n ==>
800 nth_derivative i (\x. f x - g x) x = nth_derivative i f x - nth_derivative i g x`.
801 move => ineq i_le_n.
802 have := nth_derivative_sub_strong ineq i_le_n.
803 move => [s] [_] [xs] h.
804 exact: h.
805 Qed.
806
807
808 Lemma nth_diff_sub : `nth_diff_strong_int n int (\x. f x - g x)`.
809 move: (df) (dg).
810 rewrite !nth_diff_strong_int !nth_diff_strong !nth_differentiable_on !nth_differentiable_eq.
811 move => df dg x ineq.
812 have := nth_derivative_sub_strong_all ineq.
813 move => [s] [open_s] [xs] diff.
814 move: (df ineq) => [tf] [open_tf] [xtf] diff_f.
815 move: (dg ineq) => [tg] [open_tg] [xtg] diff_g.
816 exists `s INTER tf INTER tg`; rewrite !REAL_OPEN_INTER // !IN_INTER {1}xs {1}xtf {1}xtg !andTb.
817 move => y [ys [ytf ytg]].
818 rewrite REAL_CONTINUOUS_SUB ?diff_f ?diff_g // andTb => i i_lt_n.
819 rewrite diff ?ys -?ltE //.
820 apply: HAS_REAL_DERIVATIVE_LOCAL.
821 exists `(\y. nth_derivative i f y - nth_derivative i g y)`.
822 rewrite HAS_REAL_DERIVATIVE_SUB ?andTb; first by rewr ETA_AX; rewrite (diff_f ytf) // (diff_g ytg).
823 exists s; rewrite open_s {1}ys !andTb => z zs /=.
824 by apply: diff; rewrite ltnW.
825 Qed.
826
827 (* Multiplication *)
828 Lemma nth_derivative_mul_strong i x : `interval_arith x int ==> i <= n ==>
829 ?s. real_open s /\ x IN s /\
830 !y. y IN s ==> nth_derivative i (\y. f y * g y) y =
831 sum (0..i) (\k. &(binom (i, k)) * nth_derivative k f y * nth_derivative (i - k) g y)`.
832 move: df dg; rewrite !nth_diff_strong_int !nth_diff_strong => df dg ineq.
833 move: (df ineq) => [sf] [open_sf] [xsf]; move: df => _.
834 move: (dg ineq) => [sg] [open_sg] [xsg]; move: dg => _.
835 rewrite !nth_differentiable_on !nth_differentiable_eq => diff_g diff_f.
836 elim: i => [_|i IHi].
837 exists sf; rewrite open_sf xsf !andTb !nth_derivative0 SUM_SING_NUMSEG => y _ /=.
838 by rewrite subn0 !nth_derivative0 binom REAL_MUL_LID.
839 rewrite nth_derivativeS -ltE => i_lt_n.
840 move: (IHi (ltnW i_lt_n)) => [t] [open_t] [xt] eq; move: IHi => _.
841 exists `sf INTER sg INTER t`.
842 rewrite !REAL_OPEN_INTER // !IN_INTER xt xsf xsg !andTb => y [ysf] [ysg yt].
843 apply: derivative_unique.
844 apply: HAS_REAL_DERIVATIVE_LOCAL.
845 exists `\y. sum (0..i) (\k. &(binom (i, k)) * nth_derivative k f y * nth_derivative (i - k) g y)`.
846 split; last first.
847 exists `sf INTER sg INTER t`; rewrite !REAL_OPEN_INTER // !IN_INTER {1}yt {1}ysf {1}ysg !andTb.
848 by move => z z_in /=; rewrite eq.
849 apply: has_derivative_lemma.
850 have diff_cond : `!k. k IN 0..i ==>
851 nth_derivative k f real_differentiable atreal y /\
852 nth_derivative (i - k) g real_differentiable atreal y`.
853 rewrite IN_NUMSEG => k ineq /=; rewrite !real_differentiable; split.
854 exists `nth_derivative (SUC k) f y`; rewrite (diff_f ysf).
855 by move: ineq i_lt_n; arith.
856 exists `nth_derivative (SUC (i - k)) g y`; rewrite (diff_g ysg).
857 by move: ineq i_lt_n; arith.
858 have diff_cond2 : `!k. k IN 0..i ==>
859 (\y. &(binom (i, k)) * nth_derivative k f y * nth_derivative (i - k) g y)
860 real_differentiable atreal y`.
861 move => k k_in /=.
862 by rewrite !REAL_DIFFERENTIABLE_MUL_ATREAL ?REAL_DIFFERENTIABLE_CONST; rewr ETA_AX; rewrite !diff_cond //.
863 rewrite differentiable_sum_numseg ?derivative_sum_numseg; rewr /= diff_cond2 //.
864 set lhs := `sum (0..i) _`.
865 set sum1 := `sum (0 + 1..i + 1) (\k. &(binom (i, k - 1)) * nth_derivative k f y * nth_derivative (SUC i - k) g y)`.
866 set sum2 := `sum (0..i + 1) (\k. &(binom (i, k)) * nth_derivative k f y * nth_derivative (SUC i - k) g y)`.
867 have ->: `lhs = sum1 + sum2`.
868 rewrite -sum1_def SUM_OFFSET /= addn1 succnK subSS.
869 rewrite -sum2_def addn1 "GEN_ALL SUM_CLAUSES_NUMSEG" "ARITH_RULE `0 <= SUC i`" /=.
870 have ->: `binom(i, SUC i) = 0`; first by rewrite BINOM_EQ_0; arith.
871 rewrite REAL_MUL_LZERO REAL_ADD_RID -SUM_ADD_NUMSEG /= -lhs_def.
872 apply SUM_EQ => k k_in /=.
873 rewrite derivative_scale ?REAL_DIFFERENTIABLE_MUL_ATREAL; rewr ETA_AX; rewrite ?diff_cond //.
874 rewrite -REAL_ADD_LDISTRIB REAL_EQ_MUL_LCANCEL; right.
875 rewrite derivative_mul; rewr ETA_AX; rewrite ?diff_cond //.
876 rewrite REAL_ADD_SYM -!nth_derivativeS.
877 suff ->: `SUC (i - k) = SUC i - k`; first by done.
878 by move: k_in; rewrite IN_NUMSEG; arith.
879 rewrite REAL_ADD_SYM SUM_CLAUSES_LEFT -?sum2_def 1?SUM_CLAUSES_LEFT /=; try arith.
880 rewrite !binom !REAL_MUL_LID -REAL_ADD_ASSOC REAL_EQ_ADD_LCANCEL.
881 rewrite -sum1_def -SUM_ADD_NUMSEG (addn1 i).
882 apply SUM_EQ => k k_in /=.
883 rewrite -REAL_ADD_RDISTRIB REAL_EQ_MUL_RCANCEL; left.
884 case: k k_in => [|k]; rewrite IN_NUMSEG; first by arith.
885 by rewrite binom ONE subSS subn0 REAL_OF_NUM_ADD.
886 Qed.
887
888
889 Lemma nth_derivative_mul_strong_all x : `interval_arith x int ==>
890 ?s. real_open s /\ x IN s /\
891 !i y. i <= n /\ y IN s ==>
892 nth_derivative i (\y. f y * g y) y =
893 sum (0..i) (\k. &(binom (i, k)) * nth_derivative k f y * nth_derivative (i - k) g y)`.
894 move => /(nth_derivative_mul_strong) h.
895 set P := `\i s. real_open s /\ x IN s /\
896 (!y. y IN s ==> nth_derivative i (\y. f y * g y) y =
897 sum (0..i) (\k. &(binom (i, k)) * nth_derivative k f y * nth_derivative (i - k) g y))`.
898 have sel_P : `!i. i <= n:num ==> P i ((@) (P i))`.
899 move => i i_le_n; apply SELECT_AX.
900 move: (h i_le_n) => [s] cond.
901 by exists s; rewrite -P_def /=.
902 set S := `INTERS (IMAGE (\i. (@) (P i)) (0..n))`.
903 exists S.
904 rewrite -S_def REAL_OPEN_INTERS ?FINITE_IMAGE ?FINITE_NUMSEG ?IN_IMAGE ?andTb.
905 move => t [i] [->]; rewrite IN_NUMSEG_0 => /sel_P.
906 by rewrite -{1}P_def /=.
907 rewrite !IN_INTERS !IN_IMAGE; split.
908 move => t [i] [->]; rewrite IN_NUMSEG_0 => /sel_P.
909 by rewrite -{1}P_def /=.
910 move => i y [i_le_n].
911 move: (sel_P i_le_n); rewrite -{1}P_def /= => [] [_] [_] y_in /(_ `(@) (P i)`).
912 "ANTS_TAC"; first by exists i; rewrite IN_NUMSEG_0.
913 exact: y_in.
914 Qed.
915
916
917 Lemma nth_derivative_mul i x : `interval_arith x int ==> i <= n ==>
918 nth_derivative i (\x. f x * g x) x =
919 sum (0..i) (\k. &(binom (i, k)) * nth_derivative k f x * nth_derivative (i - k) g x)`.
920 move => ineq i_le_n.
921 have := nth_derivative_mul_strong ineq i_le_n.
922 move => [s] [_] [xs] h.
923 exact: h.
924 Qed.
925
926
927 Lemma nth_diff_mul : `nth_diff_strong_int n int (\x. f x * g x)`.
928 move: (df) (dg).
929 rewrite !nth_diff_strong_int !nth_diff_strong !nth_differentiable_on !nth_differentiable_eq.
930 move => df dg x ineq.
931 have := nth_derivative_mul_strong_all ineq.
932 move => [s] [open_s] [xs] diff.
933 move: (df ineq) => [tf] [open_tf] [xtf] diff_f.
934 move: (dg ineq) => [tg] [open_tg] [xtg] diff_g.
935 exists `s INTER tf INTER tg`; rewrite !REAL_OPEN_INTER // !IN_INTER {1}xs {1}xtf {1}xtg !andTb.
936 move => y [ys [ytf ytg]].
937 rewrite REAL_CONTINUOUS_MUL ?diff_f ?diff_g // andTb => i i_lt_n.
938 rewrite nth_derivativeS has_derivative_alt.
939 apply: differentiable_local.
940 exists `\y. sum (0..i) (\k. &(binom(i, k)) * nth_derivative k f y * nth_derivative (i - k) g y)` s.
941 rewrite open_s {1}ys !andTb; split; last by move => z zs; rewrite diff // ltnW.
942 rewrite differentiable_sum_numseg IN_NUMSEG => k k_in /=.
943 rewrite !REAL_DIFFERENTIABLE_MUL_ATREAL ?REAL_DIFFERENTIABLE_CONST //; rewr ETA_AX.
944 rewrite !real_differentiable; split.
945 exists `nth_derivative (SUC k) f y`; rewrite (diff_f ytf).
946 by move: k_in i_lt_n; arith.
947 exists `nth_derivative (SUC (i - k)) g y`; rewrite (diff_g ytg).
948 by move: k_in i_lt_n; arith.
949 Qed.
950
951
952 End NthDerivativeArith.
953
954 End NthDerivatives.
955
956
957 (* Linear approximation and Taylor interval *)
958
959 "let lin_approx = new_definition `lin_approx f x f_bounds df_bounds <=>
960 interval_arith (f x) f_bounds /\
961 (?f'. (f has_real_derivative f') (atreal x) /\ interval_arith f' df_bounds)`".
962
963 "let has_bounded_second_derivative = new_definition `has_bounded_second_derivative f int dd_bounds <=>
964 nth_diff_strong_int 2 int f /\
965 bounded_on_int (nth_derivative 2 f) int dd_bounds`".
966
967
968 "let taylor_interval = new_definition
969 `taylor_interval f x y z w f_bounds df_bounds ddf_bounds <=>
970 x <= y /\ y <= z /\ y - x <= w /\ z - y <= w /\
971 lin_approx f y f_bounds df_bounds /\
972 has_bounded_second_derivative f (x, z) ddf_bounds`".
973
974
975
976 Lemma nth_diff_strong_imp_diff_int n int f: `nth_diff_strong_int n int f ==>
977 nth_differentiable_on_int n int f`.
978 rewrite nth_diff_strong_int nth_differentiable_on_int nth_diff_strong nth_differentiable_on.
979 move => h x ineq.
980 by move: (h ineq) => [s] [_] [xs]; exact.
981 Qed.
982
983
984 Lemma has_bounded_second_derivative_old f int dd_bounds :
985 `has_bounded_second_derivative f int dd_bounds ==>
986 ?f' f''. (!x. interval_arith x int ==> (f has_real_derivative f' x) (atreal x) /\
987 (f' has_real_derivative f'' x) (atreal x) /\ interval_arith (f'' x) dd_bounds)`.
988 rewrite has_bounded_second_derivative => [] [/nth_diff_strong_imp_diff_int].
989 move/nth_differentiable_on_int2 => [f'] [f''].
990 move => [eq1] [eq2] h b; exists f' f'' => x ineq.
991 move: b; rewrite bounded_on_int -eq2 => b.
992 by rewrite !h // b.
993 Qed.
994
995
996
997 Lemma exists_and_left P Q : `(?x. P x /\ Q x) ==> (?x. P x)`.
998 move => [x] [Px _].
999 by exists x.
1000 Qed.
1001
1002
1003 Lemma lim_ineq a b : `(!e. &0 < e ==> a <= b + e) <=> (a <= b)`.
1004 split => [| ineq e e0]; last first.
1005 by rewrite -(REAL_ADD_RID a) REAL_LE_ADD2 ineq REAL_LT_IMP_LE.
1006 apply: contraLR; rewrite NOT_FORALL_THM NOT_IMP !REAL_NOT_LE => ba.
1007 by exists `(a - b) / &2`; move: ba; arith.
1008 Qed.
1009
1010
1011 Lemma continuous_leq f c a: `(?b. a < b /\ !x. x IN real_interval (a, b) ==> f x <= c) /\
1012 f real_continuous atreal a ==> f a <= c`.
1013 move => [[b] [ab] ineq].
1014 rewrite REAL_CONTINUOUS_ATREAL REALLIM_ATREAL => f_cont.
1015 rewrite -lim_ineq => e /f_cont [d] [d0] cond.
1016 set r := `a + min (b - a) d / &2`.
1017 move: (cond r); "ANTS_TAC"; first by move: r_def d0 ab; arith.
1018 move: (ineq r); "ANTS_TAC"; last by arith.
1019 by rewrite IN_REAL_INTERVAL; move: r_def d0 ab; arith.
1020 Qed.
1021
1022
1023 Lemma continuous_reflection f x : `f real_continuous atreal x <=>
1024 (\x. f (--x)) real_continuous atreal (--x)`.
1025 rewrite !REAL_CONTINUOUS_ATREAL /= !REALLIM_ATREAL REAL_NEG_NEG /=; split => h e e0.
1026 move: (h e0) => [d] [d0] cond.
1027 exists d; rewrite d0 andTb => y ineqs; apply: cond.
1028 by move: ineqs; arith.
1029 move: (h e0) => [d] [d0] cond.
1030 exists d; rewrite d0 andTb => y ineqs.
1031 by move: (cond `--y`); rewrite REAL_NEG_NEG; apply; move: ineqs; arith.
1032 Qed.
1033
1034
1035 Lemma continuous_leq_segment f c a b :
1036 `a < b ==> f real_continuous atreal a ==> f real_continuous atreal b ==>
1037 (!x. x IN real_interval (a, b) ==> f x <= c) ==>
1038 (!x. x IN real_interval [a, b] ==> f x <= c)`.
1039 move => ab f_cont_a f_cont_b ineq x.
1040 rewrite IN_REAL_INTERVAL 2!"REAL_ARITH `!a b. a <= b <=> (a = b \/ a < b)`".
1041 case; case => [<- _| ax].
1042 by apply: continuous_leq; rewrite f_cont_a andbT; exists b.
1043 case => [-> | xb]; last by apply: ineq; rewrite IN_REAL_INTERVAL.
1044 set g := `\x. f (--x)`.
1045 have fg: `!x. f x = g (--x)`; first by rewrite -g_def /= REAL_NEG_NEG.
1046 rewrite fg; apply: continuous_leq; split.
1047 exists `--a`; rewrite REAL_LT_NEG2 ab andTb IN_REAL_INTERVAL => y.
1048 by move: (ineq `--y`); rewrite IN_REAL_INTERVAL fg REAL_NEG_NEG; arith.
1049 by rewrite -g_def -continuous_reflection.
1050 Qed.
1051
1052 Lemma pair_eq p : `p = (FST p, SND p)`. done. Qed.
1053
1054
1055
1056 (* Properties of taylor_interval *)
1057 Section Taylor.
1058
1059
1060 Lemma iabs_alt lo hi a : `interval_arith a (lo, hi) ==> iabs (lo, hi) = max (abs lo) (abs hi)`.
1061 by rewrite interval_arith iabs; arith. Qed.
1062
1063
1064 Lemma iabs_pos lo hi a : `interval_arith a (lo, hi) ==> &0 <= iabs (lo, hi)`.
1065 by rewrite interval_arith iabs; arith. Qed.
1066
1067
1068 Variable f : `:real -> real`.
1069 Variables x y z w : `:real`.
1070 Variables f_bounds df_bounds ddf_bounds : `:real#real`.
1071 Variable dd_bound : `:real`.
1072
1073
1074 Hypothesis dd_bound_eq : `dd_bound = iabs ddf_bounds`.
1075 Hypothesis tif : `taylor_interval f x y z w f_bounds df_bounds ddf_bounds`.
1076
1077
1078 Lemma f_continuous : `!t. t IN real_interval [x, z] ==> f real_continuous atreal t`.
1079 rewrite IN_REAL_INTERVAL -interval_arith => t t_in.
1080 apply: HAS_REAL_DERIVATIVE_IMP_CONTINUOUS_ATREAL.
1081 move: tif; rewrite taylor_interval !andbA => [] [_] /has_bounded_second_derivative_old.
1082 move => [f'] [f''] df.
1083 by exists `f' t`; rewrite df.
1084 Qed.
1085
1086
1087
1088 Lemma taylor_error t : `x <= t /\ t <= z ==>
1089 abs (f t - f y) <= w * iabs df_bounds + w * w * dd_bound / &2`.
1090 move => t_ineqs.
1091 have := tif; rewrite taylor_interval !andbA => [] [] [domain_ineqs] lin_app.
1092 move/has_bounded_second_derivative_old => [f'] [f''] df.
1093 have abs_ty : `abs (t - y) <= w`.
1094 by move: domain_ineqs t_ineqs; arith.
1095 have y_in : `interval_arith y (x, z)`; first by rewrite interval_arith.
1096 have dd_prop : `&0 <= dd_bound /\ !p. p IN real_interval [x, z] ==> abs (f'' p) <= dd_bound`.
1097 rewrite dd_bound_eq; split.
1098 by move: (df y_in); rewrite pair_eq interval_arith iabs; arith.
1099 by rewrite IN_REAL_INTERVAL -interval_arith; move => p /df; rewrite pair_eq interval_arith iabs; arith.
1100 suff: `abs (f t - (f y + f' y * (t - y) pow 1)) <= dd_bound * abs (t - y) pow (1 + 1) / &2`.
1101 set b1 := `f' y * _`; set b2 := `dd_bound * _` => ineq1.
1102 apply: REAL_LE_TRANS; exists `abs (f t - (f y + b1)) + abs b1`; split.
1103 by rewrite "REAL_ARITH `!a b. a - b = (a - (b + b1)) + b1`" REAL_ABS_TRIANGLE.
1104 rewrite REAL_ADD_SYM REAL_LE_ADD2 -{1}b1_def REAL_POW_1 REAL_ABS_MUL REAL_MUL_SYM REAL_LE_MUL2.
1105 rewrite !REAL_ABS_POS abs_ty !andTb pair_eq iabs.
1106 move: lin_app; rewrite lin_approx => [] [_] [ff] [df'].
1107 suff ->: `ff = f' y`; first by rewrite pair_eq interval_arith; arith.
1108 by apply: (REAL_DERIVATIVE_UNIQUE_ATREAL f y); rewrite df' df // IN_REAL_INTERVAL.
1109 rewrite andTb; apply: REAL_LE_TRANS; exists b2.
1110 rewrite ineq1 andTb -b2_def !real_div !REAL_MUL_ASSOC REAL_LE_MUL2 "ARITH_RULE `1 + 1 = 2`".
1111 rewrite REAL_LE_REFL REAL_LE_INV ?REAL_LE_MUL ?dd_prop ?REAL_LE_POW_2; try arith.
1112 rewrite andTb !andbT REAL_MUL_SYM -REAL_POW_2 REAL_LE_MUL2 REAL_LE_REFL dd_prop.
1113 by rewrite REAL_LE_POW_2 andTb !andbT -REAL_LE_SQUARE_ABS REAL_ABS_ABS; move: abs_ty; arith.
1114 set Df := `\i. if i = 0 then f else if i = 1 then f' else if i = 2 then f'' else I`.
1115 have arith := "ARITH_RULE `0 + 1 = 1 /\ ~(1 = 0) /\ 1 + 1 = 2 /\
1116 ~(2 = 1) /\ ~(2 = 1) /\ ~(2 = 0)`".
1117 have := REAL_TAYLOR Df `1` `real_interval [x, z]` dd_bound.
1118 "ANTS_TAC".
1119 rewrite IS_REALINTERVAL_INTERVAL andTb; split.
1120 rewrite IN_REAL_INTERVAL -interval_arith.
1121 move => i p [p_in]; rewrite "ARITH_RULE `i <= 1 <=> i = 0 \/ i = 1`".
1122 by case => ->; rewrite -Df_def /=; apply HAS_REAL_DERIVATIVE_ATREAL_WITHIN;
1123 rewrite !arith /= df.
1124 move => p p_in; rewrite -Df_def /=.
1125 by rewrite !arith /= dd_prop.
1126 move => /(_ y t); rewrite !IN_REAL_INTERVAL !domain_ineqs !t_ineqs /=.
1127 rewrite {1}ONE "GEN_ALL SUM_CLAUSES_NUMSEG" SUM_SING_NUMSEG /= -Df_def /= -ONE.
1128 rewrite !"ARITH_RULE `0 <= 1 /\ ~(1 = 0)`" /= "GEN_ALL real_pow" FACT.
1129 by rewrite !"ARITH_RULE `FACT 1 = 1 /\ FACT (1 + 1) = 2`" !REAL_DIV_1 REAL_MUL_RID.
1130 Qed.
1131
1132
1133 Lemma taylor_upper_bound : `!t. x <= t /\ t <= z ==>
1134 f t <= SND f_bounds + (w * iabs df_bounds + w * w * dd_bound / &2)`.
1135 move: (pair_eq f_bounds) => eq.
1136 move => t /taylor_error.
1137 move: tif; rewrite taylor_interval !andbA lin_approx => [] [] [_] [f_int] _ _.
1138 by move: f_int; rewrite {1}eq interval_arith; arith.
1139 Qed.
1140
1141 Lemma taylor_lower_bound : `!t. x <= t /\ t <= z ==>
1142 FST f_bounds - (w * iabs df_bounds + w * w * dd_bound / &2) <= f t`.
1143 have eq := pair_eq f_bounds.
1144 move => t /taylor_error.
1145 move: tif; rewrite {1}eq taylor_interval !andbA lin_approx => [] [] [_] [f_int] _ _.
1146 move: f_int; rewrite interval_arith; arith.
1147 Qed.
1148
1149 Lemma taylor_derivative_error : `!t. x <= t /\ t <= z ==>
1150 abs (derivative f t - derivative f y) <= w * dd_bound`.
1151 move => t t_ineqs.
1152 have := tif; rewrite taylor_interval !andbA => [] [] [domain_ineqs] _.
1153 move/has_bounded_second_derivative_old => [f'] [f''] df.
1154 have abs_ty : `abs (t - y) <= w`.
1155 by move: domain_ineqs t_ineqs; arith.
1156 have der_eq: `!p. x <= p /\ p <= z ==> derivative f p = f' p`.
1157 rewrite -IN_REAL_INTERVAL EQ_SYM_EQ; apply: derivative_unique_on.
1158 by rewrite IN_REAL_INTERVAL -interval_arith => p /df /=.
1159 rewrite !der_eq //.
1160 have dd_prop : `&0 <= dd_bound /\ !p. p IN real_interval [x, z] ==> abs (f'' p) <= dd_bound`.
1161 rewrite dd_bound_eq IN_REAL_INTERVAL -interval_arith; split.
1162 by move: (df y); rewrite (pair_eq ddf_bounds) !interval_arith iabs !domain_ineqs; arith.
1163 by move => p /df; rewrite pair_eq interval_arith iabs; arith.
1164 set Df := `\i. if i = 0 then f' else if i = 1 then f'' else I`.
1165 have arith := "ARITH_RULE `0 + 1 = 1 /\ ~(1 = 0) /\ 1 + 1 = 2 /\
1166 ~(2 = 1) /\ ~(2 = 1) /\ ~(2 = 0)`".
1167 have := REAL_TAYLOR Df `0` `real_interval [x, z]` dd_bound.
1168 "ANTS_TAC".
1169 rewrite IS_REALINTERVAL_INTERVAL andTb; split.
1170 move => i p [p_in]; rewrite "ARITH_RULE `i <= 0 <=> i = 0`" => ->.
1171 rewrite -Df_def /= !arith /=; apply: HAS_REAL_DERIVATIVE_ATREAL_WITHIN.
1172 by rewrite df interval_arith -IN_REAL_INTERVAL.
1173 move => p p_in; rewrite -Df_def /=.
1174 by rewrite !arith /= dd_prop.
1175 move => /(_ y t); rewrite !IN_REAL_INTERVAL !domain_ineqs !t_ineqs /=.
1176 rewrite {1}ONE SUM_SING_NUMSEG /= -Df_def /= -ONE.
1177 rewrite "GEN_ALL real_pow" !arith !FACT "ARITH_RULE `FACT 1 = 1`" !REAL_DIV_1 REAL_MUL_RID.
1178 rewrite REAL_POW_1 => ineq.
1179 apply: REAL_LE_TRANS; exists `dd_bound * abs (t - y)`.
1180 by rewrite ineq andTb REAL_MUL_SYM REAL_LE_RMUL dd_prop abs_ty.
1181 Qed.
1182
1183
1184 Lemma derivative_interval : `FST df_bounds <= derivative f y /\ derivative f y <= SND df_bounds`.
1185 have eq := pair_eq df_bounds.
1186 move: tif; rewrite taylor_interval lin_approx !andbA => [] [] [ineqs] [g] [fg g_int] _.
1187 suff ->: `derivative f y = g`; first by move: g_int; rewrite eq interval_arith.
1188 apply: (REAL_DERIVATIVE_UNIQUE_ATREAL f y).
1189 by rewrite fg has_derivative_cond //; exists g.
1190 Qed.
1191
1192 Lemma taylor_derivative_upper_bound : `!t. x <= t /\ t <= z ==>
1193 derivative f t <= SND df_bounds + w * dd_bound`.
1194 by move => t /taylor_derivative_error; move: derivative_interval; arith.
1195 Qed.
1196
1197 Lemma taylor_derivative_lower_bound : `!t. x <= t /\ t <= z ==>
1198 FST df_bounds - w * dd_bound <= derivative f t`.
1199 by move => t /taylor_derivative_error; move: derivative_interval; arith.
1200 Qed.
1201
1202
1203 End Taylor.
1204
1205
1206 Section LinearApproximation.
1207
1208 Variable f : `:real->real`.
1209 Variables f_bounds df_bounds : `:real#real`.
1210 Variable x : `:real`.
1211
1212
1213 Lemma lin_approx_eq : `lin_approx f x f_bounds df_bounds <=>
1214 (f real_differentiable atreal x /\ interval_arith (f x) f_bounds /\
1215 interval_arith (derivative f x) df_bounds)`.
1216 rewrite lin_approx real_differentiable; split => [[-> [f'] [df' int_f']] | [[f'] df] [-> df_int]].
1217 split; first by exists f'.
1218 by rewrite (derivative_unique f f').
1219 by rewrite andTb; exists f'; rewrite df -(derivative_unique f f' x).
1220 Qed.
1221
1222
1223
1224 Hypothesis approx_f : `lin_approx f x f_bounds df_bounds`.
1225
1226 Lemma lin_approx_imp_f_interval : `interval_arith (f x) f_bounds`.
1227 by move: approx_f; rewrite lin_approx_eq /=. Qed.
1228
1229 Lemma lin_approx_imp_df_interval : `interval_arith (derivative f x) df_bounds`.
1230 by move: approx_f; rewrite lin_approx_eq /=. Qed.
1231
1232 Lemma lin_approx_imp_f_diff : `f real_differentiable atreal x`.
1233 by move: approx_f; rewrite lin_approx_eq /=. Qed.
1234
1235 End LinearApproximation.
1236
1237
1238 Section MoreLinearApproximation.
1239
1240 (* f, g *)
1241 Variable f g : `:real->real`.
1242 Variable x : `:real`.
1243 Variables f_bounds df_bounds : `:real#real`.
1244 Variables g_bounds dg_bounds : `:real#real`.
1245
1246
1247 Lemma interval_arith_not_zero x int : `interval_arith x int ==> interval_not_zero int ==>
1248 ~(x = &0)`.
1249 by rewrite -(PAIR int) interval_arith interval_not_zero; arith. Qed.
1250
1251 Lemma interval_arith_pos x int : `interval_arith x int ==> interval_pos int ==> &0 < x`.
1252 by case: int; rewrite interval_arith interval_pos; arith. Qed.
1253
1254 Lemma interval_arith_neg x int : `interval_arith x int ==> interval_neg int ==> x < &0`.
1255 Proof. by case: int; rewrite interval_arith interval_neg; arith. Qed.
1256
1257 Lemma interval_arith_abs x int y : `interval_arith x int ==> iabs int < y ==> abs x < y`.
1258 by rewrite -(PAIR int) interval_arith iabs; arith. Qed.
1259
1260 Lemma lin_approx_x : `lin_approx (\x. x) x (x, x) (&1, &1)`.
1261 by rewrite lin_approx_eq derivative_x !interval_arith /= REAL_DIFFERENTIABLE_ID !REAL_LE_REFL.
1262 Qed.
1263
1264 Lemma lin_approx_const c : `lin_approx (\x. c) x (c, c) (&0, &0)`.
1265 rewrite lin_approx_eq derivative_const !interval_arith /= REAL_DIFFERENTIABLE_CONST.
1266 by rewrite !REAL_LE_REFL.
1267 Qed.
1268
1269
1270 Section LinearApproxUnivariateComposition.
1271
1272
1273 Hypothesis approx_f : `lin_approx f x f_bounds df_bounds`.
1274
1275
1276 Lemma lin_approx_compose_atn : `(\x. atn (f x)) real_differentiable atreal x /\
1277 derivative (\x. atn (f x)) x = derivative f x / (&1 + f x * f x)`.
1278 Proof. by apply: derivative_compose_atn; move: approx_f; rewrite lin_approx_eq => ->. Qed.
1279
1280 Lemma lin_approx_compose_exp : `(\x. exp (f x)) real_differentiable atreal x /\
1281 derivative (\x. exp (f x)) x = exp (f x) * derivative f x`.
1282 Proof. by apply: derivative_compose_exp; move: approx_f; rewrite lin_approx_eq => ->. Qed.
1283
1284 Lemma lin_approx_compose_log : `interval_pos f_bounds ==>
1285 (\x. log (f x)) real_differentiable atreal x /\
1286 derivative (\x. log (f x)) x = derivative f x / f x`.
1287 Proof.
1288 move: approx_f; rewrite lin_approx_eq => [] [df h] f_ineq.
1289 have f_pos : `&0 < f x`; first by apply: interval_arith_pos; exists f_bounds.
1290 exact: (derivative_compose_log df f_pos).
1291 Qed.
1292
1293 Lemma lin_approx_compose_cos : `(\x. cos (f x)) real_differentiable atreal x /\
1294 derivative (\x. cos (f x)) x = --(sin (f x) * derivative f x)`.
1295 Proof. by apply: derivative_compose_cos; move: approx_f; rewrite lin_approx_eq => ->. Qed.
1296
1297 Lemma lin_approx_compose_sin : `(\x. sin (f x)) real_differentiable atreal x /\
1298 derivative (\x. sin (f x)) x = cos (f x) * derivative f x`.
1299 Proof. by apply: derivative_compose_sin; move: approx_f; rewrite lin_approx_eq => ->. Qed.
1300
1301 Lemma lin_approx_compose_inv : `interval_not_zero f_bounds ==>
1302 (\x. inv (f x)) real_differentiable atreal x /\
1303 derivative (\x. inv (f x)) x = -- inv (f x * f x) * derivative f x`.
1304 Proof.
1305 move: approx_f; rewrite lin_approx_eq => [] [df h] f0.
1306 have fn0 : `~(f x = &0)`; first by apply: interval_arith_not_zero; exists f_bounds.
1307 exact: (derivative_compose_inv df fn0).
1308 Qed.
1309
1310 Lemma lin_approx_compose_sqrt : `interval_pos f_bounds ==>
1311 (\x. sqrt (f x)) real_differentiable atreal x /\
1312 derivative (\x. sqrt (f x)) x = derivative f x / (&2 * sqrt (f x))`.
1313 Proof.
1314 move: approx_f; rewrite lin_approx_eq => [] [df h] f_ineq.
1315 have f_pos : `&0 < f x`; first by apply: interval_arith_pos; exists f_bounds.
1316 exact: (derivative_compose_sqrt df f_pos).
1317 Qed.
1318
1319 Lemma lin_approx_compose_acs : `iabs f_bounds < &1 ==>
1320 (\x. acs (f x)) real_differentiable atreal x /\
1321 derivative (\x. acs (f x)) x = -- (derivative f x / sqrt (&1 - f x * f x))`.
1322 Proof.
1323 move: approx_f; rewrite lin_approx_eq => [] [df h] f_ineq.
1324 have f_abs : `abs (f x) < &1`; first by apply: interval_arith_abs; exists f_bounds.
1325 exact: (derivative_compose_acs df f_abs).
1326 Qed.
1327
1328 Lemma lin_approx_compose_asn : `iabs f_bounds < &1 ==>
1329 (\x. asn (f x)) real_differentiable atreal x /\
1330 derivative (\x. asn (f x)) x = derivative f x / sqrt (&1 - f x * f x)`.
1331 Proof.
1332 move: approx_f; rewrite lin_approx_eq => [] [df h] f_ineq.
1333 have f_abs : `abs (f x) < &1`; first by apply: interval_arith_abs; exists f_bounds.
1334 exact: (derivative_compose_asn df f_abs).
1335 Qed.
1336
1337 Lemma lin_approx_compose_matan : `interval_gt (-- &1) f_bounds ==>
1338 (\x. matan (f x)) real_differentiable atreal x /\
1339 derivative (\x. matan (f x)) x = dmatan (f x) * derivative f x`.
1340 Proof.
1341 move: approx_f; rewrite lin_approx_eq => [] [df h] f_ineq.
1342 have f_ineq2 : `-- &1 < f x`.
1343 by move: f_ineq h; rewrite (pair_eq f_bounds) interval_gt interval_arith; arith.
1344 exact: (derivative_compose_matan df f_ineq2).
1345 Qed.
1346
1347 End LinearApproxUnivariateComposition.
1348
1349
1350 Hypothesis approx_f : `lin_approx f x f_bounds df_bounds`.
1351 Hypothesis approx_g : `lin_approx g x g_bounds dg_bounds`.
1352
1353 Lemma lin_approx_imp_add_diff : `(\x. f x + g x) real_differentiable atreal x`.
1354 apply: REAL_DIFFERENTIABLE_ADD.
1355 by rewrite (lin_approx_imp_f_diff approx_f) (lin_approx_imp_f_diff approx_g).
1356 Qed.
1357
1358 Lemma lin_approx_imp_sub_diff : `(\x. f x - g x) real_differentiable atreal x`.
1359 apply: REAL_DIFFERENTIABLE_SUB.
1360 by rewrite (lin_approx_imp_f_diff approx_f) (lin_approx_imp_f_diff approx_g).
1361 Qed.
1362
1363 Lemma lin_approx_imp_mul_diff : `(\x. f x * g x) real_differentiable atreal x`.
1364 apply: REAL_DIFFERENTIABLE_MUL_ATREAL.
1365 by rewrite (lin_approx_imp_f_diff approx_f) (lin_approx_imp_f_diff approx_g).
1366 Qed.
1367
1368 Lemma lin_approx_imp_div_diff : `interval_not_zero g_bounds ==> (\x. f x / g x) real_differentiable atreal x`.
1369 move => gn0; apply: REAL_DIFFERENTIABLE_DIV_ATREAL.
1370 rewrite (lin_approx_imp_f_diff approx_f) (lin_approx_imp_f_diff approx_g) !andTb.
1371 apply: interval_arith_not_zero; exists g_bounds.
1372 by move: approx_g; rewrite lin_approx_eq => ->.
1373 Qed.
1374
1375
1376 End MoreLinearApproximation.
1377
1378
1379
1380 (* Arithmetic of linear approximations *)
1381 Section LinearApproxArith.
1382
1383 Variables f1 f2 : `:real->real`.
1384 Variables f1_bounds f2_bounds : `:real#real`.
1385 Variables df1_lo df1_hi df2_lo df2_hi : `:real`.
1386 Variables f_bounds : `:real#real`.
1387 Variables df_lo df_hi : `:real`.
1388 Variable x : `:real`.
1389
1390
1391 Hypothesis approx1 : `lin_approx f1 x f1_bounds (df1_lo, df1_hi)`.
1392
1393
1394 Lemma lin_approx_scale c : `&0 <= c ==> interval_arith (c * f1 x) f_bounds /\
1395 df_lo <= c * df1_lo /\ c * df1_hi <= df_hi ==>
1396 lin_approx (\x. c * f1 x) x f_bounds (df_lo, df_hi)`.
1397 rewrite pair_eq interval_arith => c0 ineqs.
1398 rewrite lin_approx /=; split.
1399 by rewrite pair_eq; move: approx1 ineqs; rewrite !lin_approx !interval_arith; arith.
1400 move: approx1; rewrite !lin_approx => [] [int_f1] [f1'] [df1 int_f1'].
1401 exists `c * f1'`; rewrite HAS_REAL_DERIVATIVE_LMUL_ATREAL // andTb.
1402 move: int_f1'; rewrite !interval_arith => ineqs2; split; apply: REAL_LE_TRANS.
1403 by exists `c * df1_lo`; rewrite ineqs REAL_LE_LMUL.
1404 by exists `c * df1_hi`; rewrite ineqs REAL_LE_LMUL.
1405 Qed.
1406
1407
1408
1409 Hypothesis approx2 : `lin_approx f2 x f2_bounds (df2_lo, df2_hi)`.
1410
1411
1412 Lemma lin_approx_add : `interval_arith (f1 x + f2 x) f_bounds /\
1413 df_lo <= df1_lo + df2_lo /\ df1_hi + df2_hi <= df_hi ==>
1414 lin_approx (\x. f1 x + f2 x) x f_bounds (df_lo, df_hi)`.
1415 rewrite pair_eq interval_arith => ineqs.
1416 rewrite lin_approx /=; split.
1417 by rewrite pair_eq; move: approx1 approx2 ineqs; rewrite !lin_approx !interval_arith; arith.
1418 move: approx1 approx2; rewrite !lin_approx => [] [int_f1] [f1'] [df1 int_f1'].
1419 move => [int_f2] [f2'] [df2 int_f2'].
1420 exists `f1' + f2':real`; rewrite HAS_REAL_DERIVATIVE_ADD // andTb.
1421 by move: ineqs int_f1' int_f2'; rewrite !interval_arith; arith.
1422 Qed.
1423
1424
1425
1426 End LinearApproxArith.
1427
1428
1429
1430 (* Bounds on the second derivative *)
1431 Section SecondDerivativeBound.
1432
1433 Variables f1 f2 : `:real->real`.
1434 Variable int : `:real#real`.
1435 Variables dd1 dd2 : `:real#real`.
1436
1437
1438 Lemma nth_diff_strong2_eq_alt f x : `nth_diff_strong 2 f x <=> ?s. real_open s /\ x IN s /\
1439 !y. y IN s ==> (f has_real_derivative derivative f y) (atreal y) /\
1440 (derivative f has_real_derivative nth_derivative 2 f y) (atreal y)`.
1441 rewrite nth_diff_strong nth_differentiable_on nth_differentiable_eq "ARITH_RULE `i < 2 <=> i = 0 \/ i = 1`".
1442 split => [] [s] [open_s] [xs] df.
1443 exists s; rewrite open_s xs !andTb => y /df [_] h.
1444 by move: (h `0`) (h `1`) => /=; rewrite -ONE nth_derivative1 nth_derivative0 -TWO => -> ->.
1445 exists s; rewrite open_s {1}xs !andTb => y /df h.
1446 rewrite REAL_DIFFERENTIABLE_IMP_CONTINUOUS_ATREAL ?andTb.
1447 by rewrite real_differentiable; exists `derivative f y`.
1448 by move => i; case => ->; rewrite -?ONE -?TWO !(nth_derivative0, nth_derivative1).
1449 Qed.
1450
1451
1452 Lemma nth_diff_strong2_eq f x : `nth_diff_strong 2 f x <=> ?s. real_open s /\ x IN s /\
1453 !y. y IN s ==> f real_differentiable atreal y /\ derivative f real_differentiable atreal y`.
1454 rewrite nth_diff_strong nth_differentiable_on TWO ONE !"GEN_ALL nth_differentiable".
1455 rewrite -ONE nth_derivative0 nth_derivative1.
1456 split => [] [s] [open_s] [xs] df.
1457 by exists s; rewrite open_s xs !andTb => y /df h.
1458 exists s; rewrite open_s {1}xs !andTb => y /df h.
1459 by rewrite !h REAL_DIFFERENTIABLE_IMP_CONTINUOUS_ATREAL.
1460 Qed.
1461
1462
1463 Lemma lin_approx_compose f g y g_bounds f_bounds d_bounds:
1464 `nth_diff_strong_int 2 g_bounds f ==>
1465 g real_differentiable atreal y ==>
1466 interval_arith (g y) g_bounds ==>
1467 bounded_on_int f g_bounds f_bounds ==>
1468 interval_arith (derivative g y * derivative f (g y)) d_bounds ==>
1469 lin_approx (\x. f (g x)) y f_bounds d_bounds`.
1470 rewrite nth_diff_strong_int nth_diff_strong2_eq bounded_on_int => df dg g_int f_int dfg_int.
1471 have dfgy : `f real_differentiable atreal (g y)`.
1472 by move: (df g_int) => [s] [open_s] [ys] ->.
1473 rewrite lin_approx_eq derivative_composition // dfg_int /= f_int // andbT.
1474 by rewrite -(o_THM f); rewr ETA_AX; exact: REAL_DIFFERENTIABLE_COMPOSE_ATREAL.
1475 Qed.
1476
1477 (* abs *)
1478
1479 Lemma second_derivative_abs_pos x : `&0 < x ==> nth_derivative 2 abs x = &0`.
1480 Proof.
1481 rewrite nth_derivative2 => x_pos.
1482 apply: derivative_unique; apply: HAS_REAL_DERIVATIVE_TRANSFORM_ATREAL.
1483 exists `\x. &1` x; rewrite HAS_REAL_DERIVATIVE_CONST x_pos /= => t t_ineq.
1484 rewrite derivative_abs_pos //.
1485 by move: x_pos t_ineq; arith.
1486 Qed.
1487
1488 Lemma second_derivative_abs_neg x : `x < &0 ==> nth_derivative 2 abs x = &0`.
1489 Proof.
1490 rewrite nth_derivative2 => x_neg.
1491 apply: derivative_unique; apply: HAS_REAL_DERIVATIVE_TRANSFORM_ATREAL.
1492 exists `\x. -- &1` `--x`; rewrite HAS_REAL_DERIVATIVE_CONST /=.
1493 split => [|t t_ineq]; first by move: x_neg; arith.
1494 rewrite derivative_abs_neg //.
1495 by move: x_neg t_ineq; arith.
1496 Qed.
1497
1498 Lemma diff2_abs_pos x : `&0 < x ==> nth_diff_strong 2 abs x`.
1499 Proof.
1500 rewrite nth_diff_strong2_eq => x_ineq.
1501 exists `real_interval (x - abs x, x + abs x)`.
1502 rewrite REAL_OPEN_REAL_INTERVAL andTb !IN_REAL_INTERVAL; split => [|y ineq].
1503 by move: x_ineq; arith.
1504 rewrite REAL_DIFFERENTIABLE_AT_ABS_POS ?andTb.
1505 by move: ineq x_ineq; arith.
1506 apply: differentiable_local; exists `\x. &1` `real_interval (y - abs y, y + abs y)`.
1507 rewrite REAL_OPEN_REAL_INTERVAL REAL_DIFFERENTIABLE_CONST !IN_REAL_INTERVAL !andTb.
1508 split => [|t t_ineq]; first by move: ineq x_ineq; arith.
1509 rewrite derivative_abs_pos //.
1510 by move: t_ineq ineq x_ineq; arith.
1511 Qed.
1512
1513 Lemma diff2_abs_neg x : `x < &0 ==> nth_diff_strong 2 abs x`.
1514 Proof.
1515 rewrite nth_diff_strong2_eq => x_ineq.
1516 exists `real_interval (x - abs x, x + abs x)`.
1517 rewrite REAL_OPEN_REAL_INTERVAL andTb !IN_REAL_INTERVAL; split => [|y ineq].
1518 by move: x_ineq; arith.
1519 rewrite REAL_DIFFERENTIABLE_AT_ABS_NEG ?andTb.
1520 by move: ineq x_ineq; arith.
1521 apply: differentiable_local; exists `\x. -- &1` `real_interval (y - abs y, y + abs y)`.
1522 rewrite REAL_OPEN_REAL_INTERVAL REAL_DIFFERENTIABLE_CONST !IN_REAL_INTERVAL !andTb.
1523 split => [|t t_ineq]; first by move: ineq x_ineq; arith.
1524 rewrite derivative_abs_neg //.
1525 by move: t_ineq ineq x_ineq; arith.
1526 Qed.
1527
1528 (* pow *)
1529
1530 Lemma pow_x_has_real_derivative n x :
1531 `((\x. x pow n) has_real_derivative &n * x pow (n - 1)) (atreal x)`.
1532 Proof.
1533 rewrite -[`x pow (n - 1)`]REAL_MUL_RID HAS_REAL_DERIVATIVE_POW_ATREAL.
1534 by rewrite HAS_REAL_DERIVATIVE_ID.
1535 Qed.
1536
1537 Lemma second_derivative_pow_x n :
1538 `derivative (derivative (\x. x pow n)) = (\x. &(n * (n - 1)) * x pow (n - 2))`.
1539 Proof.
1540 rewrite derivative_pow_x -eq_ext => x /=; apply: derivative_unique.
1541 rewrite -REAL_OF_NUM_MUL -REAL_MUL_ASSOC HAS_REAL_DERIVATIVE_LMUL_ATREAL.
1542 by rewrite "ARITH_RULE `n - 2 = (n - 1) - 1`" pow_x_has_real_derivative.
1543 Qed.
1544
1545 Lemma diff2_pow_x n x : `nth_diff_strong 2 (\x. x pow n) x`.
1546 Proof.
1547 rewrite nth_diff_strong2_eq_alt; exists `(:real)`.
1548 rewrite IN_UNIV REAL_OPEN_UNIV !andTb IN_UNIV => y /=.
1549 rewrite derivative_pow_x /= pow_x_has_real_derivative andTb.
1550 rewrite nth_derivative2 second_derivative_pow_x.
1551 rewrite -REAL_OF_NUM_MUL -REAL_MUL_ASSOC /= HAS_REAL_DERIVATIVE_LMUL_ATREAL.
1552 by rewrite "ARITH_RULE `n - 2 = (n - 1) - 1`" pow_x_has_real_derivative.
1553 Qed.
1554
1555 Lemma second_derivative_pow2_x :
1556 `derivative (derivative (\x. x pow 2)) = (\x. &2)`.
1557 Proof.
1558 rewrite second_derivative_pow_x subnn real_pow "ARITH_RULE `2 * (2 - 1) = 2`".
1559 by rewrite REAL_MUL_RID.
1560 Qed.
1561
1562 Lemma second_derivative_pow3_x :
1563 `derivative (derivative (\x. x pow 3)) = (\x. &6 * x)`.
1564 Proof.
1565 rewrite second_derivative_pow_x !"ARITH_RULE `3 * (3 - 1) = 6 /\ 3 - 2 = 1`".
1566 by rewrite REAL_POW_1.
1567 Qed.
1568
1569 (* atn *)
1570
1571 Lemma second_derivative_atn_eq x : `((\x. inv (&1 + x pow 2)) has_real_derivative
1572 (-- &2 * x) * inv (&1 + x pow 2) pow 2) (atreal x)`.
1573 Proof.
1574 rewrite REAL_POW_INV -real_div -REAL_NEG_LMUL HAS_REAL_DERIVATIVE_INV_ATREAL; split.
1575 rewrite -(REAL_ADD_LID `&2 * x`) HAS_REAL_DERIVATIVE_ADD HAS_REAL_DERIVATIVE_CONST andTb.
1576 rewrite REAL_POW_2 "REAL_ARITH `&2 * x = x * &1 + &1 * x`".
1577 by rewrite HAS_REAL_DERIVATIVE_MUL_ATREAL HAS_REAL_DERIVATIVE_ID.
1578 by rewrite REAL_LT_IMP_NZ // REAL_ADD_SYM REAL_LT_ADD1 REAL_LE_POW_2.
1579 Qed.
1580
1581 Lemma second_derivative_atn :
1582 `derivative (derivative atn) = (\x. (-- &2 * x) * inv (&1 + x pow 2) pow 2)`.
1583 Proof.
1584 rewrite derivative_atn -eq_ext => x /=; apply: derivative_unique.
1585 by rewrite -REAL_POW_2 second_derivative_atn_eq.
1586 Qed.
1587
1588 Lemma diff2_atn x : `nth_diff_strong 2 atn x`.
1589 Proof.
1590 rewrite nth_diff_strong2_eq_alt; exists `(:real)`.
1591 rewrite IN_UNIV REAL_OPEN_UNIV !andTb IN_UNIV => y /=.
1592 rewrite derivative_atn -REAL_POW_2 /= HAS_REAL_DERIVATIVE_ATN andTb.
1593 by rewrite nth_derivative2 second_derivative_atn /= second_derivative_atn_eq.
1594 Qed.
1595
1596 (* cos *)
1597
1598 Lemma second_derivative_cos : `nth_derivative 2 cos = (\x. --cos x)`.
1599 Proof.
1600 rewrite nth_derivative2 derivative_cos -eq_ext => x.
1601 by rewrite derivative_neg ?REAL_DIFFERENTIABLE_AT_SIN derivative_sin.
1602 Qed.
1603
1604 Lemma diff2_cos x : `nth_diff_strong 2 cos x`.
1605 Proof.
1606 rewrite nth_diff_strong2_eq_alt; exists `(:real)`.
1607 rewrite IN_UNIV REAL_OPEN_UNIV !andTb IN_UNIV => y /=.
1608 rewrite derivative_cos /= HAS_REAL_DERIVATIVE_COS andTb.
1609 by rewrite second_derivative_cos /= HAS_REAL_DERIVATIVE_NEG HAS_REAL_DERIVATIVE_SIN.
1610 Qed.
1611
1612 (* sin *)
1613
1614 Lemma second_derivative_sin : `nth_derivative 2 sin = (\x. --sin x)`.
1615 Proof. by rewrite nth_derivative2 derivative_sin -eq_ext derivative_cos. Qed.
1616
1617 Lemma diff2_sin x : `nth_diff_strong 2 sin x`.
1618 Proof.
1619 rewrite nth_diff_strong2_eq_alt; exists `(:real)`.
1620 rewrite IN_UNIV REAL_OPEN_UNIV !andTb IN_UNIV => y /=.
1621 rewrite derivative_sin /= HAS_REAL_DERIVATIVE_SIN andTb.
1622 by rewrite second_derivative_sin /= HAS_REAL_DERIVATIVE_COS.
1623 Qed.
1624
1625 (* exp *)
1626
1627 Lemma second_derivative_exp : `nth_derivative 2 exp = exp`.
1628 Proof. by rewrite nth_derivative2 !derivative_exp. Qed.
1629
1630 Lemma diff2_exp x : `nth_diff_strong 2 exp x`.
1631 Proof.
1632 rewrite nth_diff_strong2_eq_alt; exists `(:real)`.
1633 rewrite IN_UNIV REAL_OPEN_UNIV !andTb IN_UNIV => y /=.
1634 rewrite derivative_exp /= HAS_REAL_DERIVATIVE_EXP andTb.
1635 by rewrite second_derivative_exp /= HAS_REAL_DERIVATIVE_EXP.
1636 Qed.
1637
1638 (* log *)
1639
1640 Lemma second_derivative_log x : `&0 < x ==> nth_derivative 2 log x = --inv (x pow 2)`.
1641 Proof.
1642 rewrite nth_derivative2 => x_ineq.
1643 apply: derivative_unique; apply: HAS_REAL_DERIVATIVE_LOCAL.
1644 exists `(\x. inv x)`; split.
1645 move: "(DISCH_ALL o REAL_DIFF_CONV) `((\x. inv x) has_real_derivative f) (atreal x)`".
1646 by rewrite "REAL_ARITH `&0 < x ==> ~(x = &0)`" //= real_div "REAL_ARITH `!a. -- &1 * a = --a`".
1647 exists `real_interval (x - abs x, x + abs x)`.
1648 rewrite REAL_OPEN_REAL_INTERVAL andTb !IN_REAL_INTERVAL; split => [|y ineq].
1649 by move: x_ineq; arith.
1650 rewrite derivative_log //=.
1651 by move: ineq x_ineq; arith.
1652 Qed.
1653
1654 Lemma diff2_log x : `&0 < x ==> nth_diff_strong 2 log x`.
1655 Proof.
1656 rewrite nth_diff_strong2_eq => x_ineq.
1657 exists `real_interval (x - abs x, x + abs x)`.
1658 rewrite REAL_OPEN_REAL_INTERVAL andTb !IN_REAL_INTERVAL; split => [|y ineq].
1659 by move: x_ineq; arith.
1660 rewrite REAL_DIFFERENTIABLE_AT_LOG ?andTb; first by move: ineq x_ineq; arith.
1661 apply: differentiable_local; exists `\x. inv x` `real_interval (y - abs y, y + abs y)`.
1662 rewrite REAL_OPEN_REAL_INTERVAL !IN_REAL_INTERVAL andTb; split.
1663 rewrite REAL_DIFFERENTIABLE_INV_ATREAL REAL_DIFFERENTIABLE_ID.
1664 by move: ineq x_ineq; arith.
1665 split => [|z ineq2].
1666 by move: ineq x_ineq; arith.
1667 by rewrite derivative_log //; move: ineq ineq2 x_ineq; arith.
1668 Qed.
1669
1670
1671 (* inv *)
1672
1673 Lemma second_derivative_inv x : `~(x = &0) ==> nth_derivative 2 inv x = &2 * inv (x pow 3)`.
1674 Proof.
1675 rewrite nth_derivative2 => xn0.
1676 apply: derivative_unique; apply: HAS_REAL_DERIVATIVE_LOCAL.
1677 exists `(\x. -- inv (x * x))`; split.
1678 move: "(DISCH_ALL o REAL_DIFF_CONV) `((\x. -- inv(x * x)) has_real_derivative f) (atreal x)`".
1679 rewrite REAL_ENTIRE xn0 /= real_div REAL_MUL_LNEG REAL_NEG_NEG REAL_MUL_LID REAL_MUL_RID -REAL_MUL_2.
1680 rewrite "REAL_ARITH `(x * x) pow 2 = x * x pow 3`" !REAL_INV_MUL.
1681 by rewrite "REAL_ARITH `!a. (&2 * x) * inv x * a = &2 * (x * inv x) * a`" REAL_MUL_RINV ?REAL_MUL_LID.
1682 exists `real_interval (x - abs x, x + abs x)`.
1683 rewrite REAL_OPEN_REAL_INTERVAL andTb !IN_REAL_INTERVAL; split => [|y ineq].
1684 by move: xn0; arith.
1685 rewrite derivative_inv //=.
1686 by move: ineq xn0; arith.
1687 Qed.
1688
1689 Lemma diff2_inv x : `~(x = &0) ==> nth_diff_strong 2 inv x`.
1690 Proof.
1691 rewrite nth_diff_strong2_eq => xn0.
1692 exists `real_interval (x - abs x, x + abs x)`.
1693 rewrite REAL_OPEN_REAL_INTERVAL andTb !IN_REAL_INTERVAL; split => [|y ineq].
1694 by move: xn0; arith.
1695 rewrite REAL_DIFFERENTIABLE_AT_INV ?andTb; first by move: ineq xn0; arith.
1696 apply: differentiable_local; exists `\x. --inv (x * x)` `real_interval (y - abs y, y + abs y)`.
1697 rewrite REAL_OPEN_REAL_INTERVAL !IN_REAL_INTERVAL andTb; split.
1698 rewrite REAL_DIFFERENTIABLE_NEG REAL_DIFFERENTIABLE_INV_ATREAL.
1699 rewrite REAL_DIFFERENTIABLE_MUL_ATREAL ?REAL_DIFFERENTIABLE_ID // REAL_ENTIRE.
1700 by move: ineq xn0; arith.
1701 split => [|z ineq2].
1702 by move: ineq xn0; arith.
1703 by rewrite derivative_inv //; move: ineq ineq2 xn0; arith.
1704 Qed.
1705
1706
1707 (* sqrt *)
1708
1709 Lemma SQRT_POW x n : `sqrt x pow n = sqrt (x pow n)`.
1710 Proof.
1711 elim: n => [|n IHn]; rewrite !"GEN_ALL real_pow" ?SQRT_1 //.
1712 by rewrite IHn SQRT_MUL.
1713 Qed.
1714
1715
1716 Lemma second_derivative_sqrt x : `&0 < x ==> nth_derivative 2 sqrt x = -- inv(&4 * sqrt (x pow 3))`.
1717 Proof.
1718 rewrite nth_derivative2 => x_pos.
1719 apply: derivative_unique; apply: HAS_REAL_DERIVATIVE_LOCAL.
1720 exists `(\x. inv (&2 * sqrt x))`; split.
1721 move: "(DISCH_ALL o REAL_DIFF_CONV) `((\x. inv(&2 * sqrt x)) has_real_derivative f) (atreal x)`".
1722 have ineq : `~(&2 * sqrt x = &0)`.
1723 by rewrite REAL_ENTIRE negb_or SQRT_EQ_0 ?REAL_LT_IMP_LE //; move: x_pos; arith.
1724 rewrite x_pos ineq /= real_div REAL_INV_POW REAL_MUL_LID -REAL_MUL_LNEG -REAL_MUL_ASSOC.
1725 rewrite -"GEN_ALL real_pow" -REAL_INV_POW REAL_POW_MUL !REAL_INV_MUL SQRT_POW ?REAL_LT_IMP_LE //.
1726 rewrite REAL_MUL_ASSOC "GEN_ALL real_pow" REAL_MUL_LNEG REAL_INV_MUL REAL_MUL_ASSOC.
1727 rewrite REAL_MUL_RINV ?REAL_MUL_LID; first by arith.
1728 by rewrite REAL_MUL_LNEG "REAL_ARITH `&2 pow 2 = &4`" "ARITH_RULE `SUC 2 = 3`".
1729 exists `real_interval (&0, x + &1)`.
1730 rewrite REAL_OPEN_REAL_INTERVAL andTb !IN_REAL_INTERVAL; split => [|y ineq].
1731 by move: x_pos; arith.
1732 by rewrite derivative_sqrt.
1733 Qed.
1734
1735
1736 Lemma diff2_sqrt x : `&0 < x ==> nth_diff_strong 2 sqrt x`.
1737 Proof.
1738 rewrite nth_diff_strong2_eq => x_pos.
1739 exists `real_interval (&0, x + &1)`.
1740 rewrite REAL_OPEN_REAL_INTERVAL andTb !IN_REAL_INTERVAL; split => [|y ineq].
1741 by move: x_pos; arith.
1742 rewrite REAL_DIFFERENTIABLE_AT_SQRT ?andTb; first by move: ineq x_pos; arith.
1743 apply: differentiable_local; exists `\x. inv (&2 * sqrt x)` `real_interval (&0, y + &1)`.
1744 rewrite REAL_OPEN_REAL_INTERVAL !IN_REAL_INTERVAL andTb; split.
1745 rewrite REAL_DIFFERENTIABLE_INV_ATREAL REAL_DIFFERENTIABLE_MUL_ATREAL.
1746 by rewrite REAL_DIFFERENTIABLE_CONST REAL_DIFFERENTIABLE_AT_SQRT.
1747 by rewrite REAL_ENTIRE SQRT_EQ_0 ?REAL_LT_IMP_LE //; move: ineq; arith.
1748 split => [|z ineq2]; first by move: ineq x_pos; arith.
1749 by rewrite derivative_sqrt.
1750 Qed.
1751
1752 (* acs *)
1753
1754 Lemma real_powS x n : `x pow (SUC n) = x * x pow n`. by rewrite real_pow. Qed.
1755
1756 Lemma second_derivative_acs x : `abs x < &1 ==>
1757 nth_derivative 2 acs x = --(x / sqrt ((&1 - x * x) pow 3))`.
1758 Proof.
1759 rewrite nth_derivative2 => x_ineq.
1760 apply: derivative_unique; apply: HAS_REAL_DERIVATIVE_LOCAL.
1761 exists `\x. --inv (sqrt (&1 - x * x))`; split.
1762 move: "(DISCH_ALL o REAL_DIFF_CONV) `((\x. --inv (sqrt (&1 - x * x))) has_real_derivative f) (atreal x)`".
1763 have ineqs: `&0 < &1 - x * x /\ ~(sqrt(&1 - x * x) = &0)`.
1764 suff h: `&0 < &1 - x * x`.
1765 by rewrite SQRT_EQ_0 ?REAL_LT_IMP_LE //; move: h; arith.
1766 rewrite "REAL_ARITH `&1 - x * x = (&1 - x) * (&1 + x)`" REAL_LT_MUL.
1767 by move: x_ineq; arith.
1768 rewrite !ineqs /= !real_div REAL_INV_MUL REAL_SUB_LZERO !REAL_MUL_LNEG REAL_NEG_NEG -!REAL_MUL_ASSOC.
1769 rewrite -REAL_INV_MUL -real_powS SQRT_POW ?REAL_LT_IMP_LE //.
1770 rewrite REAL_MUL_LID REAL_MUL_RID -REAL_MUL_2.
1771 rewrite "REAL_ARITH `!a. (&2 * x) * inv (&2) * a = (&2 * inv (&2)) * x * a`" "ARITH_RULE `SUC 2 = 3`".
1772 by rewrite REAL_MUL_RINV ?REAL_MUL_LID; arith.
1773 set e := `&1 - abs x`.
1774 exists `real_interval (x - e, x + e)`.
1775 rewrite REAL_OPEN_REAL_INTERVAL andTb !IN_REAL_INTERVAL; split => [|y ineq].
1776 by move: x_ineq e_def; arith.
1777 rewrite derivative_acs //=.
1778 by move: ineq x_ineq e_def; arith.
1779 Qed.
1780
1781
1782 Lemma diff2_acs x : `abs x < &1 ==> nth_diff_strong 2 acs x`.
1783 Proof.
1784 rewrite nth_diff_strong2_eq => x_ineq.
1785 set e := `&1 - abs x`.
1786 exists `real_interval (x - e, x + e)`.
1787 rewrite REAL_OPEN_REAL_INTERVAL andTb !IN_REAL_INTERVAL; split => [|y ineq].
1788 by move: x_ineq e_def; arith.
1789 rewrite REAL_DIFFERENTIABLE_AT_ACS ?andTb; first by move: ineq x_ineq e_def; arith.
1790 set e2 := `&1 - abs y`.
1791 apply: differentiable_local; exists `\x. --inv (sqrt (&1 - x * x))` `real_interval (y - e2, y + e2)`.
1792 rewrite REAL_OPEN_REAL_INTERVAL !IN_REAL_INTERVAL andTb; split.
1793 rewrite REAL_DIFFERENTIABLE_NEG REAL_DIFFERENTIABLE_INV_ATREAL.
1794 have gt0 : `&0 < &1 - y * y`.
1795 by rewrite "REAL_ARITH `&1 - y * y = (&1 - y) * (&1 + y)`" REAL_LT_MUL; move: ineq e_def; arith.
1796 rewrite SQRT_EQ_0 ?REAL_LT_IMP_LE // REAL_LT_IMP_NZ //=.
1797 have ->: `(\x. sqrt (&1 - x * x)) = sqrt o (\x. &1 - x * x)`.
1798 by rewrite -eq_ext o_THM /=.
1799 rewrite REAL_DIFFERENTIABLE_COMPOSE_ATREAL REAL_DIFFERENTIABLE_AT_SQRT //.
1800 rewrite REAL_DIFFERENTIABLE_SUB // REAL_DIFFERENTIABLE_CONST REAL_DIFFERENTIABLE_MUL_ATREAL //.
1801 by rewrite REAL_DIFFERENTIABLE_ID.
1802 split => [|z ineq2].
1803 by move: ineq x_ineq e_def e2_def; arith.
1804 rewrite derivative_acs //=.
1805 by move: x_ineq ineq e_def e2_def ineq2; arith.
1806 Qed.
1807
1808 (* asn *)
1809
1810 Lemma second_derivative_asn x : `abs x < &1 ==>
1811 nth_derivative 2 asn x = x / sqrt ((&1 - x * x) pow 3)`.
1812 Proof.
1813 rewrite nth_derivative2 => x_ineq.
1814 apply: derivative_unique; apply: HAS_REAL_DERIVATIVE_LOCAL.
1815 exists `\x. inv (sqrt (&1 - x * x))`; split.
1816 move: "(DISCH_ALL o REAL_DIFF_CONV) `((\x. inv (sqrt (&1 - x * x))) has_real_derivative f) (atreal x)`".
1817 have ineqs: `&0 < &1 - x * x /\ ~(sqrt(&1 - x * x) = &0)`.
1818 suff h: `&0 < &1 - x * x`.
1819 by rewrite SQRT_EQ_0 ?REAL_LT_IMP_LE //; move: h; arith.
1820 rewrite "REAL_ARITH `&1 - x * x = (&1 - x) * (&1 + x)`" REAL_LT_MUL.
1821 by move: x_ineq; arith.
1822 rewrite !ineqs /= !real_div REAL_INV_MUL REAL_SUB_LZERO !REAL_MUL_LNEG REAL_NEG_NEG -!REAL_MUL_ASSOC.
1823 rewrite -REAL_INV_MUL -real_powS SQRT_POW ?REAL_LT_IMP_LE //.
1824 rewrite REAL_MUL_LID REAL_MUL_RID -REAL_MUL_2.
1825 rewrite "REAL_ARITH `!a. (&2 * x) * inv (&2) * a = (&2 * inv (&2)) * x * a`" "ARITH_RULE `SUC 2 = 3`".
1826 by rewrite REAL_MUL_RINV ?REAL_MUL_LID; arith.
1827 set e := `&1 - abs x`.
1828 exists `real_interval (x - e, x + e)`.
1829 rewrite REAL_OPEN_REAL_INTERVAL andTb !IN_REAL_INTERVAL; split => [|y ineq].
1830 by move: x_ineq e_def; arith.
1831 rewrite derivative_asn //=.
1832 by move: ineq x_ineq e_def; arith.
1833 Qed.
1834
1835
1836 Lemma diff2_asn x : `abs x < &1 ==> nth_diff_strong 2 asn x`.
1837 Proof.
1838 rewrite nth_diff_strong2_eq => x_ineq.
1839 set e := `&1 - abs x`.
1840 exists `real_interval (x - e, x + e)`.
1841 rewrite REAL_OPEN_REAL_INTERVAL andTb !IN_REAL_INTERVAL; split => [|y ineq].
1842 by move: x_ineq e_def; arith.
1843 rewrite REAL_DIFFERENTIABLE_AT_ASN ?andTb; first by move: ineq x_ineq e_def; arith.
1844 set e2 := `&1 - abs y`.
1845 apply: differentiable_local; exists `\x. inv (sqrt (&1 - x * x))` `real_interval (y - e2, y + e2)`.
1846 rewrite REAL_OPEN_REAL_INTERVAL !IN_REAL_INTERVAL andTb; split.
1847 rewrite REAL_DIFFERENTIABLE_INV_ATREAL.
1848 have gt0 : `&0 < &1 - y * y`.
1849 by rewrite "REAL_ARITH `&1 - y * y = (&1 - y) * (&1 + y)`" REAL_LT_MUL; move: ineq e_def; arith.
1850 rewrite SQRT_EQ_0 ?REAL_LT_IMP_LE // REAL_LT_IMP_NZ //=.
1851 have ->: `(\x. sqrt (&1 - x * x)) = sqrt o (\x. &1 - x * x)`.
1852 by rewrite -eq_ext o_THM /=.
1853 rewrite REAL_DIFFERENTIABLE_COMPOSE_ATREAL REAL_DIFFERENTIABLE_AT_SQRT //.
1854 rewrite REAL_DIFFERENTIABLE_SUB // REAL_DIFFERENTIABLE_CONST REAL_DIFFERENTIABLE_MUL_ATREAL //.
1855 by rewrite REAL_DIFFERENTIABLE_ID.
1856 split => [|z ineq2].
1857 by move: ineq x_ineq e_def e2_def; arith.
1858 rewrite derivative_asn //=.
1859 by move: x_ineq ineq e_def e2_def ineq2; arith.
1860 Qed.
1861
1862
1863 (* matan *)
1864
1865 Lemma second_derivative_matan x : `nth_derivative 2 matan x = ddmatan x`.
1866 Proof. by rewrite nth_derivative2 derivative_eq_real_derivative ddmatan. Qed.
1867
1868 Lemma diff2_matan x : `-- &1 < x ==> nth_diff_strong 2 matan x`.
1869 Proof.
1870 rewrite nth_diff_strong2_eq => x_ineq.
1871 exists `real_interval (-- &1, x + &1)`.
1872 rewrite REAL_OPEN_REAL_INTERVAL andTb !IN_REAL_INTERVAL; split => [|y ineq].
1873 by move: x_ineq; arith.
1874 rewrite matan_differentiable // andTb.
1875 apply: differentiable_local; exists `dmatan` `real_interval (-- &1, y + &1)`.
1876 rewrite REAL_OPEN_REAL_INTERVAL !IN_REAL_INTERVAL andTb; split; last first.
1877 split => [|z ineq2]; first by move: ineq x_ineq; arith.
1878 by rewrite derivative_matan.
1879 case: (EXCLUDED_MIDDLE `y < &1`) => y_ineq.
1880 rewrite dmatan matan_second_derivative_abs1.
1881 by move: y_ineq ineq; arith.
1882 rewrite dmatan; apply: differentiable_local.
1883 set f' := `\x. inv (&2 * x * (x + &1)) - atn (sqrt x) / (&2 * x * sqrt x)`.
1884 exists f' `real_interval (y - &1, y + &1)`.
1885 rewrite REAL_OPEN_REAL_INTERVAL !IN_REAL_INTERVAL andTb; split; last first.
1886 split; first by arith.
1887 move => t t_ineq; rewrite -f'_def matan_real_derivative_gt0 //.
1888 by move: t_ineq y_ineq; arith.
1889 rewrite real_differentiable.
1890 have := matan_has_derivative2_gt0 y; rewrite f'_def.
1891 set f'' := `_1 - _2`; move => h.
1892 by exists f''; rewrite h; move: y_ineq; arith.
1893 Qed.
1894
1895 Section SecondDerivativeCompose.
1896
1897 Lemma REAL_CONTINUOUS_OPEN_PREIMAGE f s t : `f real_continuous_on s ==> real_open s ==> real_open t ==>
1898 real_open {x | x IN s /\ f x IN t}`.
1899 move => f_cont open_s open_t.
1900 rewrite REAL_OPEN.
1901 suff ->: `IMAGE lift {x | x IN s /\ f x IN t} =
1902 {x | x IN (IMAGE lift s) /\ (lift o f o drop) x IN (IMAGE lift t)}`.
1903 by rewrite CONTINUOUS_OPEN_PREIMAGE -!REAL_OPEN; rewr ETA_AX; rewrite -REAL_CONTINUOUS_ON.
1904 rewrite EXTENSION IN_IMAGE_LIFT_DROP !IN_ELIM_THM !IN_IMAGE_LIFT_DROP => z /=; split.
1905 move => [x] [x_in] x_eq; exists `lift x`.
1906 by rewrite !o_THM !LIFT_DROP !x_in -x_eq LIFT_DROP.
1907 rewrite !o_THM LIFT_DROP => [] [x] [x_in] x_eq.
1908 by exists `drop x`.
1909 Qed.
1910
1911
1912 Lemma second_derivative_compose f g x : `nth_diff_strong 2 g x ==> nth_diff_strong 2 f (g x) ==>
1913 nth_derivative 2 (\x. f (g x)) x =
1914 nth_derivative 2 f (g x) * (derivative g x) pow 2 + derivative f (g x) * nth_derivative 2 g x`.
1915 move => dg df.
1916 rewrite nth_derivative2; apply: derivative_unique; apply: HAS_REAL_DERIVATIVE_LOCAL.
1917 exists `\x. derivative f (g x) * derivative g x`; split; last first.
1918 move: (df) (dg); rewrite !nth_diff_strong2_eq => [] [s] [open_s] [gxs] d_f [t] [open_t] [xt] d_g.
1919 set s' := `{z | z IN t /\ g z IN s}`.
1920 have open_s' : `real_open s'`.
1921 rewrite -s'_def REAL_CONTINUOUS_OPEN_PREIMAGE open_t open_s !andbT.
1922 rewrite REAL_CONTINUOUS_ON_EQ_REAL_CONTINUOUS_AT // => y yt.
1923 by rewrite REAL_DIFFERENTIABLE_IMP_CONTINUOUS_ATREAL d_g.
1924 exists `t INTER s'`; rewrite REAL_OPEN_INTER // !IN_INTER andTb; split.
1925 by rewrite -s'_def IN_ELIM_THM xt andTb /=; exists x.
1926 move => y [yt ys']; rewrite derivative_composition ?REAL_MUL_SYM //.
1927 by rewrite d_g // d_f //; move: ys'; rewrite -s'_def IN_ELIM_THM => [] [z] /=.
1928 move: df dg; rewrite !nth_diff_strong2_eq_alt => [] [_] d_f [_] d_g.
1929 rewrite REAL_ADD_SYM REAL_POW_2 REAL_MUL_ASSOC HAS_REAL_DERIVATIVE_MUL_ATREAL; split; last first.
1930 by rewr ETA_AX; rewrite d_g.
1931 rewrite -(o_THM `derivative f`); rewr ETA_AX; rewrite REAL_DIFF_CHAIN_ATREAL.
1932 by rewrite d_g // d_f.
1933 Qed.
1934
1935
1936 Lemma diff2_compose f g x : `nth_diff_strong 2 g x ==> nth_diff_strong 2 f (g x) ==>
1937 nth_diff_strong 2 (\x. f (g x)) x`.
1938 rewrite !nth_diff_strong2_eq => [] [s] [open_s] [xs] dg [t] [open_t] [gxt] df.
1939 set s' := `{z | z IN s /\ g z IN t}`.
1940 have open_s' : `real_open s'`.
1941 rewrite -s'_def REAL_CONTINUOUS_OPEN_PREIMAGE open_t open_s !andbT.
1942 rewrite REAL_CONTINUOUS_ON_EQ_REAL_CONTINUOUS_AT // => y yt.
1943 by rewrite REAL_DIFFERENTIABLE_IMP_CONTINUOUS_ATREAL dg.
1944 exists `s INTER s'`; rewrite REAL_OPEN_INTER // !IN_INTER andTb; split.
1945 by rewrite -s'_def IN_ELIM_THM xs andTb; exists x => /=.
1946 move => y [ys ys'].
1947 rewrite -{1}(o_THM f); rewr ETA_AX; rewrite REAL_DIFFERENTIABLE_COMPOSE_ATREAL ?dg ?df ?andTb //.
1948 by move: ys'; rewrite -s'_def; rewrite IN_ELIM_THM => [] [z] /=.
1949 apply: differentiable_local.
1950 exists `\x. derivative g x * derivative f (g x)` `s INTER s'`; split; last first.
1951 rewrite REAL_OPEN_INTER // !IN_INTER {1}ys {1}ys' !andTb => z z_in.
1952 rewrite derivative_composition // dg // df //.
1953 by move: z_in; rewrite -s'_def; rewrite IN_ELIM_THM => [] [_] [_] /=.
1954 rewrite REAL_DIFFERENTIABLE_MUL_ATREAL; rewr ETA_AX; rewrite dg // andTb.
1955 rewrite -(o_THM `derivative f`); rewr ETA_AX; rewrite REAL_DIFFERENTIABLE_COMPOSE_ATREAL dg // df //.
1956 by move: ys'; rewrite -s'_def; rewrite IN_ELIM_THM => [] [z] /=.
1957 Qed.
1958
1959
1960 (* Auxiliary results about open sets *)
1961
1962 Lemma continuous_not0_exists_open f x : `~(f x = &0) ==> f real_continuous atreal x ==>
1963 ?s. real_open s /\ x IN s /\ !y. y IN s ==> ~(f y = &0)`.
1964 rewrite real_continuous_atreal => fn0 /(_ `abs (f x)`).
1965 "ANTS_TAC"; first by move: fn0; arith.
1966 move => [d] [d0] ineq.
1967 exists `real_interval (x - d, x + d)`.
1968 rewrite REAL_OPEN_REAL_INTERVAL !IN_REAL_INTERVAL andTb; split => [|y]; first by move: d0; arith.
1969 by move: (ineq y) d0 fn0; arith.
1970 Qed.
1971
1972 Lemma continuous_gt_exists_open a f x : `a < f x ==> f real_continuous atreal x ==>
1973 ?s. real_open s /\ x IN s /\ !y. y IN s ==> a < f y`.
1974 move => f_ineq; rewrite real_continuous_atreal => /(_ `f x - a`).
1975 "ANTS_TAC"; first by move: f_ineq; arith.
1976 move => [d] [d0] ineq.
1977 exists `real_interval (x - d, x + d)`.
1978 rewrite REAL_OPEN_REAL_INTERVAL !IN_REAL_INTERVAL andTb; split => [|y]; first by move: d0; arith.
1979 by move: (ineq y) d0 f_ineq; arith.
1980 Qed.
1981
1982 Lemma continuous_lt_exists_open a f x : `f x < a ==> f real_continuous atreal x ==>
1983 ?s. real_open s /\ x IN s /\ !y. y IN s ==> f y < a`.
1984 move => f_ineq; rewrite real_continuous_atreal => /(_ `a - f x`).
1985 "ANTS_TAC"; first by move: f_ineq; arith.
1986 move => [d] [d0] ineq.
1987 exists `real_interval (x - d, x + d)`.
1988 rewrite REAL_OPEN_REAL_INTERVAL !IN_REAL_INTERVAL andTb; split => [|y]; first by move: d0; arith.
1989 by move: (ineq y) d0 f_ineq; arith.
1990 Qed.
1991
1992
1993 Variable f : `:real->real`.
1994 Variable x : `:real`.
1995 Hypothesis df : `nth_diff_strong 2 f x`.
1996
1997 (* abs *)
1998
1999 Lemma second_derivative_compose_abs_pos : `&0 < f x ==>
2000 nth_derivative 2 (\x. abs (f x)) x = nth_derivative 2 f x`.
2001 Proof.
2002 move => f_ineq.
2003 rewrite second_derivative_compose ?diff2_abs_pos // second_derivative_abs_pos // derivative_abs_pos //.
2004 by arith.
2005 Qed.
2006
2007 Lemma second_derivative_compose_abs_neg : `f x < &0 ==>
2008 nth_derivative 2 (\x. abs (f x)) x = --nth_derivative 2 f x`.
2009 Proof.
2010 move => f_ineq.
2011 rewrite second_derivative_compose ?diff2_abs_neg // second_derivative_abs_neg // derivative_abs_neg //.
2012 by arith.
2013 Qed.
2014
2015 (* pow *)
2016
2017 Lemma second_derivative_compose_pow n :
2018 `nth_derivative 2 (\x. f x pow n) x =
2019 &n * (nth_derivative 2 f x * f x pow (n - 1)
2020 + &(n - 1) * f x pow (n - 2) * derivative f x pow 2)`.
2021 Proof.
2022 set g := `\x. x pow n`.
2023 have ->: `(\x. f x pow n) = (\x. g (f x))` by rewrite -g_def.
2024 rewrite second_derivative_compose -g_def ?diff2_pow_x //.
2025 rewrite nth_derivative2 second_derivative_pow_x derivative_pow_x /=.
2026 by rewrite -REAL_OF_NUM_MUL; arith.
2027 Qed.
2028
2029 Lemma second_derivative_compose_pow2 :
2030 `nth_derivative 2 (\x. f x pow 2) x =
2031 &2 * (nth_derivative 2 f x * f x + derivative f x pow 2)`.
2032 Proof.
2033 rewrite second_derivative_compose_pow "ARITH_RULE `2 - 1 = 1`" subnn.
2034 by rewrite REAL_POW_1 "GEN_ALL real_pow"; arith.
2035 Qed.
2036
2037 Lemma second_derivative_compose_pow3 :
2038 `nth_derivative 2 (\x. f x pow 3) x =
2039 &3 * (nth_derivative 2 f x * f x pow 2 + &2 * f x * derivative f x pow 2)`.
2040 Proof.
2041 rewrite second_derivative_compose_pow !"ARITH_RULE `3 - 1 = 2 /\ 3 - 2 = 1`".
2042 by rewrite REAL_POW_1; arith.
2043 Qed.
2044
2045 (* atn *)
2046
2047 Lemma second_derivative_compose_atn :
2048 `nth_derivative 2 (\x. atn (f x)) x =
2049 (nth_derivative 2 f x * (&1 + f x * f x) - &2 * f x * derivative f x pow 2) / (&1 + f x * f x) pow 2`.
2050 Proof.
2051 rewrite second_derivative_compose ?diff2_atn //
2052 nth_derivative2 second_derivative_atn /= derivative_atn /=.
2053 rewrite REAL_ADD_SYM !REAL_MUL_LNEG -real_sub.
2054 set lhs1 := `_1 * _2`; set lhs2 := `_1 * _2`.
2055 rewrite real_div REAL_INV_POW REAL_SUB_RDISTRIB.
2056 set rhs1 := `_1 * _2`; set rhs2 := `_1 * _2`.
2057 apply: "REAL_ARITH `lhs1 = rhs1 /\ lhs2 = rhs2 ==> lhs1 - lhs2 = rhs1 - rhs2`".
2058 rewrite -lhs2_def -rhs2_def -!REAL_MUL_ASSOC [`_1 * _2 pow 2`]REAL_MUL_SYM -REAL_POW_2; split => //.
2059 rewrite -rhs1_def REAL_POW_2 -!REAL_MUL_ASSOC "REAL_ARITH `!a b c d. a * b * c * d = a * (b * c) * d`".
2060 rewrite REAL_MUL_RINV -?lhs1_def ?REAL_MUL_LID ?REAL_MUL_SYM //.
2061 by move: (REAL_LE_SQUARE `f x`); arith.
2062 Qed.
2063
2064 (* cos *)
2065 Lemma second_derivative_compose_cos :
2066 `nth_derivative 2 (\x. cos (f x)) x =
2067 --(nth_derivative 2 f x * sin (f x) + cos (f x) * derivative f x pow 2)`.
2068 Proof.
2069 rewrite second_derivative_compose ?diff2_cos // second_derivative_cos /= derivative_cos /=.
2070 by arith.
2071 Qed.
2072
2073 (* sin *)
2074 Lemma second_derivative_compose_sin :
2075 `nth_derivative 2 (\x. sin (f x)) x =
2076 nth_derivative 2 f x * cos (f x) - sin (f x) * derivative f x pow 2`.
2077 Proof.
2078 rewrite second_derivative_compose ?diff2_sin // second_derivative_sin /= derivative_sin /=.
2079 by arith.
2080 Qed.
2081
2082 (* exp *)
2083 Lemma second_derivative_compose_exp :
2084 `nth_derivative 2 (\x. exp (f x)) x =
2085 nth_derivative 2 f x * exp (f x) + exp (f x) * derivative f x pow 2`.
2086 Proof.
2087 rewrite second_derivative_compose ?diff2_exp // second_derivative_exp /= derivative_exp /=.
2088 by arith.
2089 Qed.
2090
2091 (* log *)
2092 Lemma second_derivative_compose_log : `&0 < f x ==>
2093 nth_derivative 2 (\x. log (f x)) x =
2094 nth_derivative 2 f x / f x - (derivative f x / f x) pow 2`.
2095 Proof.
2096 move => f_ineq.
2097 rewrite second_derivative_compose ?diff2_log // second_derivative_log // derivative_log //.
2098 by rewrite REAL_POW_DIV !real_div; arith.
2099 Qed.
2100
2101 (* inv *)
2102 Lemma second_derivative_compose_inv : `~(f x = &0) ==>
2103 nth_derivative 2 (\x. inv (f x)) x =
2104 (&2 * derivative f x pow 2 - nth_derivative 2 f x * f x) / (f x pow 3)`.
2105 Proof.
2106 move => fn0.
2107 rewrite second_derivative_compose ?diff2_inv // second_derivative_inv // derivative_inv //.
2108 rewrite REAL_MUL_LNEG -real_sub real_div REAL_SUB_RDISTRIB.
2109 apply: "REAL_ARITH `!a b c d. a = c /\ b = d ==> a - b = c - d`"; split; first by arith.
2110 rewrite REAL_INV_POW "ARITH_RULE `3 = SUC 2`" real_powS.
2111 rewrite "REAL_ARITH `!a b c d. (a * b) * c * d = a * (b * c) * d`" REAL_MUL_RINV // REAL_MUL_LID.
2112 by rewrite REAL_INV_MUL -REAL_POW_2 REAL_MUL_SYM.
2113 Qed.
2114
2115 (* sqrt *)
2116 Lemma second_derivative_compose_sqrt : `&0 < f x ==>
2117 nth_derivative 2 (\x. sqrt (f x)) x =
2118 (&2 * nth_derivative 2 f x * f x - derivative f x pow 2) / (&4 * sqrt (f x pow 3))`.
2119 Proof.
2120 move => f_pos.
2121 rewrite second_derivative_compose ?diff2_sqrt // second_derivative_sqrt // derivative_sqrt //.
2122 rewrite REAL_MUL_LNEG REAL_ADD_SYM -real_sub real_div REAL_SUB_RDISTRIB.
2123 apply: "REAL_ARITH `!a b c d. a = c /\ b = d ==> a - b = c - d`"; split; last by arith.
2124 have ->: `sqrt (f x pow 3) = sqrt (f x) * f x`.
2125 by rewrite -SQRT_POW ?REAL_LT_IMP_LE // "ARITH_RULE `3 = SUC 2`" real_powS SQRT_POW_2 ?REAL_LT_IMP_LE.
2126 rewrite !REAL_INV_MUL.
2127 rewrite "REAL_ARITH `!a b c d. (&2 * a * b) * inv (&4) * c * d = (inv (&2) * c) * a * (b * d)`".
2128 by rewrite REAL_MUL_RINV ?REAL_LT_IMP_NZ // REAL_MUL_RID.
2129 Qed.
2130
2131 (* acs *)
2132 Lemma second_derivative_compose_acs : `abs (f x) < &1 ==>
2133 nth_derivative 2 (\x. acs (f x)) x =
2134 -- ((nth_derivative 2 f x * (&1 - f x * f x) + f x * derivative f x pow 2) /
2135 sqrt ((&1 - f x * f x) pow 3))`.
2136 Proof.
2137 move => f_ineq.
2138 rewrite second_derivative_compose ?diff2_acs // second_derivative_acs // derivative_acs //.
2139 rewrite !REAL_MUL_LNEG -REAL_NEG_ADD REAL_EQ_NEG2 !real_div REAL_ADD_RDISTRIB REAL_ADD_SYM.
2140 apply: "REAL_ARITH `!a b c d. a = c /\ b = d ==> a + b = c + d`"; split; last by arith.
2141 set y := `&1 - f x * f x`.
2142 have y_ineq: `&0 <= y /\ &0 < y /\ ~(y = &0)`.
2143 rewrite -y_def "REAL_ARITH `!a. &1 - a * a = (&1 - a) * (&1 + a)`".
2144 by rewrite REAL_ENTIRE REAL_LE_MUL ?REAL_LT_MUL; move: f_ineq; arith.
2145 have ->: `sqrt (y pow 3) = sqrt y * y`.
2146 by rewrite -SQRT_POW // "ARITH_RULE `3 = SUC 2`" real_powS SQRT_POW_2.
2147 rewrite REAL_INV_MUL "REAL_ARITH `!a b c d. (a * b) * c * d = c * a * (b * d)`".
2148 by rewrite REAL_MUL_RINV // REAL_MUL_RID.
2149 Qed.
2150
2151 (* asn *)
2152 Lemma second_derivative_compose_asn : `abs (f x) < &1 ==>
2153 nth_derivative 2 (\x. asn (f x)) x =
2154 ((nth_derivative 2 f x * (&1 - f x * f x) + f x * derivative f x pow 2) /
2155 sqrt ((&1 - f x * f x) pow 3))`.
2156 Proof.
2157 move => f_ineq.
2158 rewrite second_derivative_compose ?diff2_asn // second_derivative_asn // derivative_asn //.
2159 rewrite !real_div REAL_ADD_RDISTRIB REAL_ADD_SYM.
2160 apply: "REAL_ARITH `!a b c d. a = c /\ b = d ==> a + b = c + d`"; split; last by arith.
2161 set y := `&1 - f x * f x`.
2162 have y_ineq: `&0 <= y /\ &0 < y /\ ~(y = &0)`.
2163 rewrite -y_def "REAL_ARITH `!a. &1 - a * a = (&1 - a) * (&1 + a)`".
2164 by rewrite REAL_ENTIRE REAL_LE_MUL ?REAL_LT_MUL; move: f_ineq; arith.
2165 have ->: `sqrt (y pow 3) = sqrt y * y`.
2166 by rewrite -SQRT_POW // "ARITH_RULE `3 = SUC 2`" real_powS SQRT_POW_2.
2167 rewrite REAL_INV_MUL "REAL_ARITH `!a b c d. (a * b) * c * d = c * a * (b * d)`".
2168 by rewrite REAL_MUL_RINV // REAL_MUL_RID.
2169 Qed.
2170
2171 (* matan *)
2172 Lemma second_derivative_compose_matan : `-- &1 < f x ==>
2173 nth_derivative 2 (\x. matan (f x)) x =
2174 nth_derivative 2 f x * dmatan (f x) + derivative f x pow 2 * ddmatan (f x)`.
2175 Proof.
2176 move => f_ineq.
2177 rewrite second_derivative_compose ?diff2_matan // second_derivative_matan // derivative_matan //.
2178 by arith.
2179 Qed.
2180
2181 (* abs *)
2182 Lemma diff2_compose_abs_pos : `&0 < f x ==> nth_diff_strong 2 (\x. abs (f x)) x`.
2183 Proof. by move => f_ineq; rewrite diff2_compose diff2_abs_pos. Qed.
2184
2185 Lemma diff2_compose_abs_neg : `f x < &0 ==> nth_diff_strong 2 (\x. abs (f x)) x`.
2186 Proof. by move => f_ineq; rewrite diff2_compose diff2_abs_neg. Qed.
2187
2188 (* pow *)
2189 Lemma diff2_compose_pow n : `nth_diff_strong 2 (\x. f x pow n) x`.
2190 Proof.
2191 set g := `\x. x pow n`.
2192 have ->: `(\x. f x pow n) = (\x. g (f x))` by rewrite -g_def.
2193 by rewrite diff2_compose -g_def diff2_pow_x.
2194 Qed.
2195
2196 (* atn *)
2197 Lemma diff2_compose_atn : `nth_diff_strong 2 (\x. atn (f x)) x`.
2198 Proof. by rewrite diff2_compose diff2_atn. Qed.
2199
2200 (* cos *)
2201 Lemma diff2_compose_cos : `nth_diff_strong 2 (\x. cos (f x)) x`.
2202 Proof. by rewrite diff2_compose diff2_cos. Qed.
2203
2204 (* sin *)
2205 Lemma diff2_compose_sin : `nth_diff_strong 2 (\x. sin (f x)) x`.
2206 Proof. by rewrite diff2_compose diff2_sin. Qed.
2207
2208 (* exp *)
2209 Lemma diff2_compose_exp : `nth_diff_strong 2 (\x. exp (f x)) x`.
2210 Proof. by rewrite diff2_compose diff2_exp. Qed.
2211
2212 (* log *)
2213 Lemma diff2_compose_log : `&0 < f x ==> nth_diff_strong 2 (\x. log (f x)) x`.
2214 Proof. by move => f_ineq; rewrite diff2_compose diff2_log. Qed.
2215
2216 (* inv *)
2217 Lemma diff2_compose_inv : `~(f x = &0) ==> nth_diff_strong 2 (\x. inv (f x)) x`.
2218 Proof. by move => fn0; rewrite diff2_compose diff2_inv. Qed.
2219
2220 (* sqrt *)
2221 Lemma diff2_compose_sqrt : `&0 < f x ==> nth_diff_strong 2 (\x. sqrt (f x)) x`.
2222 Proof. by move => f_pos; rewrite diff2_compose diff2_sqrt. Qed.
2223
2224 (* acs *)
2225 Lemma diff2_compose_acs : `abs (f x) < &1 ==> nth_diff_strong 2 (\x. acs (f x)) x`.
2226 Proof. by move => f_abs; rewrite diff2_compose diff2_acs. Qed.
2227
2228 (* asn *)
2229 Lemma diff2_compose_asn : `abs (f x) < &1 ==> nth_diff_strong 2 (\x. asn (f x)) x`.
2230 Proof. by move => f_abs; rewrite diff2_compose diff2_asn. Qed.
2231
2232 (* matan *)
2233 Lemma diff2_compose_matan : `-- &1 < f x ==> nth_diff_strong 2 (\x. matan (f x)) x`.
2234 Proof. by move => f_ineq; rewrite diff2_compose diff2_matan. Qed.
2235
2236
2237 End SecondDerivativeCompose.
2238
2239
2240
2241 (* mul *)
2242
2243 Lemma second_derivative_mul f g x : `nth_diff_strong 2 f x ==>
2244 nth_diff_strong 2 g x ==>
2245 nth_derivative 2 (\x. f x * g x) x =
2246 f x * nth_derivative 2 g x + &2 * derivative f x * derivative g x + nth_derivative 2 f x * g x`.
2247 move => df0 dg0; set int := `(x,x)`.
2248 have [ineq [df dg]]: `interval_arith x int /\ nth_diff_strong_int 2 int f /\ nth_diff_strong_int 2 int g`.
2249 rewrite -!int_def !nth_diff_strong_int CONST_INTERVAL andTb.
2250 by split => y; rewrite interval_arith REAL_LE_ANTISYM => <-.
2251 have := nth_derivative_mul df dg `2` ineq; rewrite leqnn => -> //.
2252 rewrite {1}TWO {1}ONE !"GEN_ALL SUM_CLAUSES_NUMSEG" !"ARITH_RULE `!n. 0 <= SUC n`" /= -ONE -TWO.
2253 rewrite subnn subn0 "ARITH_RULE `2 - 1 = 1`" !nth_derivative0 !nth_derivative1.
2254 by rewrite binom BINOM_1 BINOM_REFL !REAL_MUL_LID REAL_ADD_ASSOC.
2255 Qed.
2256
2257
2258 (* div *)
2259 Lemma second_derivative_div f g x : `~(g x = &0) ==>
2260 nth_diff_strong 2 f x ==>
2261 nth_diff_strong 2 g x ==>
2262 nth_derivative 2 (\x. f x / g x) x =
2263 ((nth_derivative 2 f x * g x - f x * nth_derivative 2 g x) * g x -
2264 &2 * derivative g x * (derivative f x * g x - f x * derivative g x)) / (g x pow 3)`.
2265 move => gn0 diff_f diff_g.
2266 set dg := `derivative g x`; set df := `derivative f x`.
2267 set ddg := `nth_derivative 2 g x`; set ddf := `nth_derivative 2 f x`.
2268 rewrite !real_div second_derivative_mul ?second_derivative_compose_inv ?diff2_compose_inv //.
2269 rewrite derivative_compose_inv.
2270 by move: diff_g; rewrite nth_diff_strong2_eq => [] [s] [open_s] [xs] -> //.
2271 rewrite ddf_def ddg_def df_def dg_def !real_div.
2272 set lhs := `_1 + _2`.
2273 rewrite "REAL_RING `!f g x. ((ddf * g x - f x * ddg) * g x - &2 * dg * (df * g x - f x * dg)) *
2274 inv (g x pow 3) =
2275 f x * (&2 * dg pow 2 - ddg * g x) * inv (g x pow 3) +
2276 &2 * df * --(g x * inv (g x pow 3)) * dg +
2277 ddf * (g x * g x * inv (g x pow 3))`".
2278 have ->: `g x * inv (g x pow 3) = inv (g x pow 2)`.
2279 by rewrite "ARITH_RULE `3 = SUC 2`" real_powS REAL_INV_MUL REAL_MUL_ASSOC REAL_MUL_RINV // REAL_MUL_LID.
2280 have ->: `g x * inv (g x pow 2) = inv (g x)`.
2281 by rewrite TWO real_powS REAL_INV_MUL REAL_MUL_ASSOC REAL_MUL_RINV // REAL_MUL_LID REAL_POW_1.
2282 by rewrite (REAL_POW_2 `g x`) lhs_def.
2283 Qed.
2284
2285 Lemma diff2_div f g x : `~(g x = &0) ==> nth_diff_strong 2 f x ==> nth_diff_strong 2 g x ==>
2286 nth_diff_strong 2 (\x. f x / g x) x`.
2287 move => gn0 df0 dg0; set int := `(x,x)`.
2288 have [ineq [df dg]]: `interval_arith x int /\ nth_diff_strong_int 2 int f /\ nth_diff_strong_int 2 int g`.
2289 rewrite -!int_def !nth_diff_strong_int CONST_INTERVAL andTb.
2290 by split => y; rewrite interval_arith REAL_LE_ANTISYM => <-.
2291 have := nth_diff_mul `2` int f `\x. inv (g x)` df.
2292 rewrite !nth_diff_strong_int /= real_div => ->; split => // y.
2293 rewrite -int_def interval_arith REAL_LE_ANTISYM => <-.
2294 by rewrite diff2_compose_inv.
2295 Qed.
2296
2297
2298 (* scale *)
2299
2300 Lemma second_derivative_scale f c x : `nth_diff_strong 2 f x ==>
2301 nth_derivative 2 (\x. c * f x) x = c * nth_derivative 2 f x`.
2302 move => df0; set int := `(x,x)`.
2303 have [ineq df]: `interval_arith x int /\ nth_diff_strong_int 2 int f`.
2304 rewrite -!int_def !nth_diff_strong_int CONST_INTERVAL andTb.
2305 by move => y; rewrite interval_arith REAL_LE_ANTISYM => <-.
2306 by have := nth_derivative_scale df c `2` ineq; rewrite leqnn => ->.
2307 Qed.
2308
2309
2310 (* add *)
2311
2312 Lemma second_derivative_add f g x : `nth_diff_strong 2 f x ==>
2313 nth_diff_strong 2 g x ==>
2314 nth_derivative 2 (\x. f x + g x) x = nth_derivative 2 f x + nth_derivative 2 g x`.
2315 move => df0 dg0; set int := `(x,x)`.
2316 have [ineq [df dg]]: `interval_arith x int /\ nth_diff_strong_int 2 int f /\ nth_diff_strong_int 2 int g`.
2317 rewrite -!int_def !nth_diff_strong_int CONST_INTERVAL andTb.
2318 by split => y; rewrite interval_arith REAL_LE_ANTISYM => <-.
2319 by have := nth_derivative_add df dg `2` ineq; rewrite leqnn => ->.
2320 Qed.
2321
2322
2323 (* sub *)
2324
2325 Lemma second_derivative_sub f g x : `nth_diff_strong 2 f x ==>
2326 nth_diff_strong 2 g x ==>
2327 nth_derivative 2 (\x. f x - g x) x = nth_derivative 2 f x - nth_derivative 2 g x`.
2328 move => df0 dg0; set int := `(x,x)`.
2329 have [ineq [df dg]]: `interval_arith x int /\ nth_diff_strong_int 2 int f /\ nth_diff_strong_int 2 int g`.
2330 rewrite -!int_def !nth_diff_strong_int CONST_INTERVAL andTb.
2331 by split => y; rewrite interval_arith REAL_LE_ANTISYM => <-.
2332 by have := nth_derivative_sub df dg `2` ineq; rewrite leqnn => ->.
2333 Qed.
2334
2335
2336 (*************************)
2337 (* Bounds *)
2338
2339
2340 (* Composition *)
2341 Lemma second_derivative_compose_bounds f g int g_bounds dd_bounds :
2342 `nth_diff_strong_int 2 int g ==>
2343 bounded_on_int g int g_bounds ==>
2344 nth_diff_strong_int 2 g_bounds f ==>
2345 bounded_on_int (\x. nth_derivative 2 f (g x) * derivative g x pow 2 +
2346 derivative f (g x) * nth_derivative 2 g x) int dd_bounds ==>
2347 has_bounded_second_derivative (\x. f (g x)) int dd_bounds`.
2348 rewrite has_bounded_second_derivative !bounded_on_int !nth_diff_strong_int /=.
2349 move => dg g_bounded df bounded; split => x ineq.
2350 by rewrite diff2_compose dg // df // g_bounded.
2351 by rewrite second_derivative_compose ?dg ?df ?g_bounded // bounded.
2352 Qed.
2353
2354 (* abs *)
2355
2356 Lemma second_derivative_abs_pos_bounds dd_bounds :
2357 `interval_pos int ==>
2358 bounded_on_int (\x. &0) int dd_bounds ==>
2359 has_bounded_second_derivative abs int dd_bounds`.
2360 Proof.
2361 rewrite has_bounded_second_derivative !bounded_on_int !nth_diff_strong_int /= => int_pos bounded.
2362 split => x ineq.
2363 by rewrite diff2_abs_pos (interval_arith_pos x int).
2364 rewrite second_derivative_abs_pos ?(interval_arith_pos x int) // (bounded ineq).
2365 Qed.
2366
2367 Lemma second_derivative_abs_neg_bounds dd_bounds :
2368 `interval_neg int ==>
2369 bounded_on_int (\x. &0) int dd_bounds ==>
2370 has_bounded_second_derivative abs int dd_bounds`.
2371 Proof.
2372 rewrite has_bounded_second_derivative !bounded_on_int !nth_diff_strong_int /= => int_neg bounded.
2373 split => x ineq.
2374 by rewrite diff2_abs_neg (interval_arith_neg x int).
2375 rewrite second_derivative_abs_neg ?(interval_arith_neg x int) // (bounded ineq).
2376 Qed.
2377
2378 Lemma second_derivative_compose_abs_pos_bounds f f_bounds dd_bounds :
2379 `bounded_on_int f int f_bounds ==> interval_pos f_bounds ==>
2380 nth_diff_strong_int 2 int f ==>
2381 bounded_on_int (\x. nth_derivative 2 f x) int dd_bounds ==>
2382 has_bounded_second_derivative (\x. abs (f x)) int dd_bounds`.
2383 Proof.
2384 rewrite has_bounded_second_derivative !bounded_on_int !nth_diff_strong_int /= => f_bounded f_int df bounded.
2385 have f_pos: `!x. interval_arith x int ==> &0 < f x`.
2386 by move => x ineq; rewrite (interval_arith_pos `f x` f_bounds) // f_bounded.
2387 split => x ineq.
2388 by rewrite diff2_compose_abs_pos df // f_pos.
2389 by rewrite second_derivative_compose_abs_pos ?df ?f_pos // bounded.
2390 Qed.
2391
2392 Lemma second_derivative_compose_abs_neg_bounds f f_bounds dd_bounds :
2393 `bounded_on_int f int f_bounds ==> interval_neg f_bounds ==>
2394 nth_diff_strong_int 2 int f ==>
2395 bounded_on_int (\x. --nth_derivative 2 f x) int dd_bounds ==>
2396 has_bounded_second_derivative (\x. abs (f x)) int dd_bounds`.
2397 Proof.
2398 rewrite has_bounded_second_derivative !bounded_on_int !nth_diff_strong_int /= => f_bounded f_int df bounded.
2399 have f_ineq: `!x. interval_arith x int ==> f x < &0`.
2400 by move => x ineq; rewrite (interval_arith_neg `f x` f_bounds) // f_bounded.
2401 split => x ineq.
2402 by rewrite diff2_compose_abs_neg df // f_ineq.
2403 by rewrite second_derivative_compose_abs_neg ?df ?f_ineq // bounded.
2404 Qed.
2405
2406 (* pow *)
2407
2408 Lemma second_derivative_pow_bounds n dd_bounds :
2409 `bounded_on_int (\x. &(n * (n - 1)) * x pow (n - 2)) int dd_bounds ==>
2410 has_bounded_second_derivative (\x. x pow n) int dd_bounds`.
2411 Proof.
2412 rewrite bounded_on_int has_bounded_second_derivative => ineq.
2413 split; last by rewrite nth_derivative2 second_derivative_pow_x bounded_on_int.
2414 by rewrite nth_diff_strong_int diff2_pow_x.
2415 Qed.
2416
2417 Lemma second_derivative_compose_pow_bounds n f dd_bounds :
2418 `nth_diff_strong_int 2 int f ==>
2419 bounded_on_int (\x. &n * (nth_derivative 2 f x * f x pow (n - 1) +
2420 &(n - 1) * f x pow (n - 2) * derivative f x pow 2)) int dd_bounds ==>
2421 has_bounded_second_derivative (\x. f x pow n) int dd_bounds`.
2422 Proof.
2423 rewrite has_bounded_second_derivative !bounded_on_int
2424 !nth_diff_strong_int /= => df bounded; split => x ineq.
2425 by rewrite diff2_compose_pow df.
2426 by rewrite second_derivative_compose_pow ?df // bounded.
2427 Qed.
2428
2429 Lemma second_derivative_pow2_bounds dd_bounds :
2430 `bounded_on_int (\x. &2) int dd_bounds ==>
2431 has_bounded_second_derivative (\x. x pow 2) int dd_bounds`.
2432 Proof.
2433 move => bounded; rewrite second_derivative_pow_bounds // subnn real_pow.
2434 by rewrite "ARITH_RULE `2 * (2 - 1) = 2`" REAL_MUL_RID.
2435 Qed.
2436
2437 Lemma second_derivative_compose_pow2_bounds f dd_bounds :
2438 `nth_diff_strong_int 2 int f ==>
2439 bounded_on_int (\x. &2 * (nth_derivative 2 f x * f x +
2440 derivative f x pow 2)) int dd_bounds ==>
2441 has_bounded_second_derivative (\x. f x pow 2) int dd_bounds`.
2442 Proof.
2443 move => df bounded; rewrite second_derivative_compose_pow_bounds df andTb.
2444 by rewrite "ARITH_RULE `2 - 1 = 1`" subnn "GEN_ALL real_pow" !REAL_MUL_LID REAL_POW_1.
2445 Qed.
2446
2447 Lemma second_derivative_pow3_bounds dd_bounds :
2448 `bounded_on_int (\x. &6 * x) int dd_bounds ==>
2449 has_bounded_second_derivative (\x. x pow 3) int dd_bounds`.
2450 Proof.
2451 move => bounded; rewrite second_derivative_pow_bounds //.
2452 by rewrite !"ARITH_RULE `3 * (3 - 1) = 6 /\ 3 - 2 = 1`" REAL_POW_1.
2453 Qed.
2454
2455 Lemma second_derivative_compose_pow3_bounds f dd_bounds :
2456 `nth_diff_strong_int 2 int f ==>
2457 bounded_on_int (\x. &3 * (nth_derivative 2 f x * f x pow 2 +
2458 &2 * f x * derivative f x pow 2)) int dd_bounds ==>
2459 has_bounded_second_derivative (\x. f x pow 3) int dd_bounds`.
2460 Proof.
2461 move => df bounded; rewrite second_derivative_compose_pow_bounds df andTb.
2462 by rewrite !"ARITH_RULE `3 - 1 = 2 /\ 3 - 2 = 1`" REAL_POW_1.
2463 Qed.
2464
2465 (* atn *)
2466
2467 Lemma second_derivative_atn_bounds dd_bounds :
2468 `bounded_on_int (\x. (-- &2 * x) * inv(&1 + x pow 2) pow 2) int dd_bounds ==>
2469 has_bounded_second_derivative atn int dd_bounds`.
2470 Proof.
2471 rewrite bounded_on_int has_bounded_second_derivative => ineq.
2472 split; last by rewrite nth_derivative2 second_derivative_atn bounded_on_int.
2473 by rewrite nth_diff_strong_int diff2_atn.
2474 Qed.
2475
2476 Lemma second_derivative_compose_atn_bounds f dd_bounds :
2477 `nth_diff_strong_int 2 int f ==>
2478 bounded_on_int (\x. (nth_derivative 2 f x * (&1 + f x * f x) - &2 * f x * derivative f x pow 2) /
2479 (&1 + f x * f x) pow 2) int dd_bounds ==>
2480 has_bounded_second_derivative (\x. atn (f x)) int dd_bounds`.
2481 Proof.
2482 rewrite has_bounded_second_derivative !bounded_on_int !nth_diff_strong_int /= => df bounded; split => x ineq.
2483 by rewrite diff2_compose_atn df.
2484 by rewrite second_derivative_compose_atn ?df // bounded.
2485 Qed.
2486
2487 (* cos *)
2488
2489 Lemma second_derivative_cos_bounds dd_bounds :
2490 `bounded_on_int (\x. -- cos x) int dd_bounds ==>
2491 has_bounded_second_derivative cos int dd_bounds`.
2492 Proof.
2493 rewrite bounded_on_int has_bounded_second_derivative => ineq.
2494 split; last by rewrite second_derivative_cos bounded_on_int.
2495 by rewrite nth_diff_strong_int diff2_cos.
2496 Qed.
2497
2498 Lemma second_derivative_compose_cos_bounds f dd_bounds :
2499 `nth_diff_strong_int 2 int f ==>
2500 bounded_on_int (\x. --(nth_derivative 2 f x * sin (f x)
2501 + cos (f x) * derivative f x pow 2)) int dd_bounds ==>
2502 has_bounded_second_derivative (\x. cos (f x)) int dd_bounds`.
2503 Proof.
2504 rewrite has_bounded_second_derivative !bounded_on_int !nth_diff_strong_int /= => df bounded; split => x ineq.
2505 by rewrite diff2_compose_cos df.
2506 by rewrite second_derivative_compose_cos ?df // bounded.
2507 Qed.
2508
2509 (* sin *)
2510
2511 Lemma second_derivative_sin_bounds dd_bounds :
2512 `bounded_on_int (\x. -- sin x) int dd_bounds ==>
2513 has_bounded_second_derivative sin int dd_bounds`.
2514 Proof.
2515 rewrite bounded_on_int has_bounded_second_derivative => ineq.
2516 split; last by rewrite second_derivative_sin bounded_on_int.
2517 by rewrite nth_diff_strong_int diff2_sin.
2518 Qed.
2519
2520 Lemma second_derivative_compose_sin_bounds f dd_bounds :
2521 `nth_diff_strong_int 2 int f ==>
2522 bounded_on_int (\x. nth_derivative 2 f x * cos (f x)
2523 - sin (f x) * derivative f x pow 2) int dd_bounds ==>
2524 has_bounded_second_derivative (\x. sin (f x)) int dd_bounds`.
2525 Proof.
2526 rewrite has_bounded_second_derivative !bounded_on_int !nth_diff_strong_int /= => df bounded; split => x ineq.
2527 by rewrite diff2_compose_sin df.
2528 by rewrite second_derivative_compose_sin ?df // bounded.
2529 Qed.
2530
2531 (* exp *)
2532
2533 Lemma second_derivative_exp_bounds dd_bounds :
2534 `bounded_on_int exp int dd_bounds ==>
2535 has_bounded_second_derivative exp int dd_bounds`.
2536 Proof.
2537 rewrite bounded_on_int has_bounded_second_derivative => ineq.
2538 split; last by rewrite second_derivative_exp bounded_on_int.
2539 by rewrite nth_diff_strong_int diff2_exp.
2540 Qed.
2541
2542 Lemma second_derivative_compose_exp_bounds f dd_bounds :
2543 `nth_diff_strong_int 2 int f ==>
2544 bounded_on_int (\x. nth_derivative 2 f x * exp (f x)
2545 + exp (f x) * derivative f x pow 2) int dd_bounds ==>
2546 has_bounded_second_derivative (\x. exp (f x)) int dd_bounds`.
2547 Proof.
2548 rewrite has_bounded_second_derivative !bounded_on_int !nth_diff_strong_int /= => df bounded; split => x ineq.
2549 by rewrite diff2_compose_exp df.
2550 by rewrite second_derivative_compose_exp ?df // bounded.
2551 Qed.
2552
2553
2554 (* log *)
2555
2556 Lemma second_derivative_log_bounds dd_bounds :
2557 `interval_pos int ==>
2558 bounded_on_int (\x. --inv (x pow 2)) int dd_bounds ==>
2559 has_bounded_second_derivative log int dd_bounds`.
2560 Proof.
2561 rewrite has_bounded_second_derivative !bounded_on_int !nth_diff_strong_int /= => int_pos bounded.
2562 split => x ineq.
2563 by rewrite diff2_log (interval_arith_pos x int).
2564 by rewrite second_derivative_log ?(interval_arith_pos x int) // bounded.
2565 Qed.
2566
2567 Lemma second_derivative_compose_log_bounds f f_bounds dd_bounds :
2568 `bounded_on_int f int f_bounds ==> interval_pos f_bounds ==>
2569 nth_diff_strong_int 2 int f ==>
2570 bounded_on_int (\x. nth_derivative 2 f x / f x - (derivative f x / f x) pow 2)
2571 int dd_bounds ==>
2572 has_bounded_second_derivative (\x. log (f x)) int dd_bounds`.
2573 Proof.
2574 rewrite has_bounded_second_derivative !bounded_on_int !nth_diff_strong_int /= => f_bounded f_int df bounded.
2575 have f_pos: `!x. interval_arith x int ==> &0 < f x`.
2576 by move => x ineq; rewrite (interval_arith_pos `f x` f_bounds) // f_bounded.
2577 split => x ineq.
2578 by rewrite diff2_compose_log df // f_pos.
2579 by rewrite second_derivative_compose_log ?df ?f_pos // bounded.
2580 Qed.
2581
2582
2583 (* inv *)
2584
2585 Lemma second_derivative_inv_bounds dd_bounds :
2586 `interval_not_zero int ==>
2587 bounded_on_int (\x. &2 * inv (x pow 3)) int dd_bounds ==>
2588 has_bounded_second_derivative inv int dd_bounds`.
2589 Proof.
2590 rewrite has_bounded_second_derivative !bounded_on_int !nth_diff_strong_int /= => int0 bounded; split => x ineq.
2591 by rewrite diff2_inv (interval_arith_not_zero x int).
2592 by rewrite second_derivative_inv ?(interval_arith_not_zero x int) // bounded.
2593 Qed.
2594
2595 Lemma second_derivative_compose_inv_bounds f f_bounds dd_bounds :
2596 `bounded_on_int f int f_bounds ==> interval_not_zero f_bounds ==>
2597 nth_diff_strong_int 2 int f ==>
2598 bounded_on_int (\x. (&2 * derivative f x pow 2 - nth_derivative 2 f x * f x) / f x pow 3)
2599 int dd_bounds ==>
2600 has_bounded_second_derivative (\x. inv (f x)) int dd_bounds`.
2601 Proof.
2602 rewrite has_bounded_second_derivative !bounded_on_int !nth_diff_strong_int /= => f_bounded f0 df bounded.
2603 have fn0: `!x. interval_arith x int ==> ~(f x = &0)`.
2604 by move => x ineq; rewrite (interval_arith_not_zero `f x` f_bounds) // f_bounded.
2605 split => x ineq.
2606 by rewrite diff2_compose_inv df // fn0.
2607 by rewrite second_derivative_compose_inv ?df ?fn0 // bounded.
2608 Qed.
2609
2610
2611 (* sqrt *)
2612
2613 Lemma second_derivative_sqrt_bounds dd_bounds :
2614 `interval_pos int ==>
2615 bounded_on_int (\x. --inv (&4 * sqrt (x pow 3))) int dd_bounds ==>
2616 has_bounded_second_derivative sqrt int dd_bounds`.
2617 Proof.
2618 rewrite has_bounded_second_derivative !bounded_on_int !nth_diff_strong_int /= => int_pos bounded.
2619 split => x ineq.
2620 by rewrite diff2_sqrt (interval_arith_pos x int).
2621 by rewrite second_derivative_sqrt ?(interval_arith_pos x int) // bounded.
2622 Qed.
2623
2624 Lemma second_derivative_compose_sqrt_bounds f f_bounds dd_bounds :
2625 `bounded_on_int f int f_bounds ==> interval_pos f_bounds ==>
2626 nth_diff_strong_int 2 int f ==>
2627 bounded_on_int (\x. (&2 * nth_derivative 2 f x * f x - derivative f x pow 2) /
2628 (&4 * sqrt (f x pow 3)))
2629 int dd_bounds ==>
2630 has_bounded_second_derivative (\x. sqrt (f x)) int dd_bounds`.
2631 Proof.
2632 rewrite has_bounded_second_derivative !bounded_on_int !nth_diff_strong_int /= => f_bounded f_int df bounded.
2633 have f_pos: `!x. interval_arith x int ==> &0 < f x`.
2634 by move => x ineq; rewrite (interval_arith_pos `f x` f_bounds) // f_bounded.
2635 split => x ineq.
2636 by rewrite diff2_compose_sqrt df // f_pos.
2637 by rewrite second_derivative_compose_sqrt ?df ?f_pos // bounded.
2638 Qed.
2639
2640 (* acs *)
2641
2642 Lemma second_derivative_acs_bounds dd_bounds :
2643 `iabs int < &1 ==>
2644 bounded_on_int (\x. --(x / sqrt ((&1 - x * x) pow 3))) int dd_bounds ==>
2645 has_bounded_second_derivative acs int dd_bounds`.
2646 Proof.
2647 rewrite has_bounded_second_derivative !bounded_on_int !nth_diff_strong_int /= => int_abs bounded.
2648 split => x ineq.
2649 by rewrite diff2_acs (interval_arith_abs x int).
2650 by rewrite second_derivative_acs ?(interval_arith_abs x int) // bounded.
2651 Qed.
2652
2653 Lemma second_derivative_compose_acs_bounds f f_bounds dd_bounds :
2654 `bounded_on_int f int f_bounds ==> iabs f_bounds < &1 ==>
2655 nth_diff_strong_int 2 int f ==>
2656 bounded_on_int (\x. --((nth_derivative 2 f x * (&1 - f x * f x) + f x * derivative f x pow 2) /
2657 sqrt ((&1 - f x * f x) pow 3))) int dd_bounds ==>
2658 has_bounded_second_derivative (\x. acs (f x)) int dd_bounds`.
2659 Proof.
2660 rewrite has_bounded_second_derivative !bounded_on_int !nth_diff_strong_int /= => f_bounded f_abs df bounded.
2661 have fabs: `!x. interval_arith x int ==> abs (f x) < &1`.
2662 by move => x ineq; rewrite (interval_arith_abs `f x` f_bounds) // f_bounded.
2663 split => x ineq.
2664 by rewrite diff2_compose_acs df // fabs.
2665 by rewrite second_derivative_compose_acs ?df ?fabs // bounded.
2666 Qed.
2667
2668 (* asn *)
2669
2670 Lemma second_derivative_asn_bounds dd_bounds :
2671 `iabs int < &1 ==>
2672 bounded_on_int (\x. x / sqrt ((&1 - x * x) pow 3)) int dd_bounds ==>
2673 has_bounded_second_derivative asn int dd_bounds`.
2674 Proof.
2675 rewrite has_bounded_second_derivative !bounded_on_int !nth_diff_strong_int /= => int_abs bounded.
2676 split => x ineq.
2677 by rewrite diff2_asn (interval_arith_abs x int).
2678 by rewrite second_derivative_asn ?(interval_arith_abs x int) // bounded.
2679 Qed.
2680
2681 Lemma second_derivative_compose_asn_bounds f f_bounds dd_bounds :
2682 `bounded_on_int f int f_bounds ==> iabs f_bounds < &1 ==>
2683 nth_diff_strong_int 2 int f ==>
2684 bounded_on_int (\x. (nth_derivative 2 f x * (&1 - f x * f x) + f x * derivative f x pow 2) /
2685 sqrt ((&1 - f x * f x) pow 3)) int dd_bounds ==>
2686 has_bounded_second_derivative (\x. asn (f x)) int dd_bounds`.
2687 Proof.
2688 rewrite has_bounded_second_derivative !bounded_on_int !nth_diff_strong_int /= => f_bounded f_abs df bounded.
2689 have fabs: `!x. interval_arith x int ==> abs (f x) < &1`.
2690 by move => x ineq; rewrite (interval_arith_abs `f x` f_bounds) // f_bounded.
2691 split => x ineq.
2692 by rewrite diff2_compose_asn df // fabs.
2693 by rewrite second_derivative_compose_asn ?df ?fabs // bounded.
2694 Qed.
2695
2696
2697 (* matan *)
2698
2699 Lemma interval_arith_gt x int f : `interval_arith x int /\ interval_gt f int ==> f < x`.
2700 Proof. by rewrite (pair_eq int) interval_arith interval_gt; arith. Qed.
2701
2702 Lemma second_derivative_matan_bounds dd_bounds :
2703 `interval_gt (-- &1) int ==>
2704 bounded_on_int ddmatan int dd_bounds ==>
2705 has_bounded_second_derivative matan int dd_bounds`.
2706 Proof.
2707 rewrite has_bounded_second_derivative !bounded_on_int !nth_diff_strong_int /= => int_gt bounded.
2708 split => x ineq.
2709 by rewrite diff2_matan (interval_arith_gt x int).
2710 by rewrite second_derivative_matan ?(interval_arith_gt x int) // bounded.
2711 Qed.
2712
2713 Lemma second_derivative_compose_matan_bounds f f_bounds dd_bounds :
2714 `bounded_on_int f int f_bounds ==> interval_gt (-- &1) f_bounds ==>
2715 nth_diff_strong_int 2 int f ==>
2716 bounded_on_int (\x. nth_derivative 2 f x * dmatan (f x) + derivative f x pow 2 * ddmatan (f x))
2717 int dd_bounds ==>
2718 has_bounded_second_derivative (\x. matan (f x)) int dd_bounds`.
2719 Proof.
2720 rewrite has_bounded_second_derivative !bounded_on_int !nth_diff_strong_int /= => f_bounded f_int df bounded.
2721 have f_ineq: `!x. interval_arith x int ==> -- &1 < f x`.
2722 by move => x ineq; rewrite (interval_arith_gt `f x` f_bounds) // f_bounded.
2723 split => x ineq.
2724 by rewrite diff2_compose_matan df // f_ineq.
2725 by rewrite second_derivative_compose_matan ?df ?f_ineq // bounded.
2726 Qed.
2727
2728
2729 (* scale *)
2730
2731 Lemma second_derivative_scale_bounds c f dd_bounds : `nth_diff_strong_int 2 int f ==>
2732 bounded_on_int (\x. c * nth_derivative 2 f x) int dd_bounds ==>
2733 has_bounded_second_derivative (\x. c * f x) int dd_bounds`.
2734 rewrite has_bounded_second_derivative !bounded_on_int => /= df b.
2735 rewrite nth_diff_scale // andTb => x ineq.
2736 rewrite second_derivative_scale ?b //.
2737 by move: df; rewrite nth_diff_strong_int; exact.
2738 Qed.
2739
2740
2741 (* add *)
2742
2743 Lemma second_derivative_add_bounds f g dd_bounds : `nth_diff_strong_int 2 int f ==>
2744 nth_diff_strong_int 2 int g ==>
2745 bounded_on_int (\x. nth_derivative 2 f x + nth_derivative 2 g x) int dd_bounds ==>
2746 has_bounded_second_derivative (\x. f x + g x) int dd_bounds`.
2747 rewrite has_bounded_second_derivative !bounded_on_int => /= df dg b.
2748 rewrite nth_diff_add // andTb => x ineq.
2749 rewrite second_derivative_add ?b //.
2750 by move: df dg; rewrite !nth_diff_strong_int => -> // ->.
2751 Qed.
2752
2753
2754 (* sub *)
2755
2756 Lemma second_derivative_sub_bounds f g dd_bounds : `nth_diff_strong_int 2 int f ==>
2757 nth_diff_strong_int 2 int g ==>
2758 bounded_on_int (\x. nth_derivative 2 f x - nth_derivative 2 g x) int dd_bounds ==>
2759 has_bounded_second_derivative (\x. f x - g x) int dd_bounds`.
2760 rewrite has_bounded_second_derivative !bounded_on_int => /= df dg b.
2761 rewrite nth_diff_sub // andTb => x ineq.
2762 rewrite second_derivative_sub ?b //.
2763 by move: df dg; rewrite !nth_diff_strong_int => -> // ->.
2764 Qed.
2765
2766
2767 (* mul *)
2768
2769 Lemma second_derivative_mul_bounds f g dd_bounds : `nth_diff_strong_int 2 int f ==>
2770 nth_diff_strong_int 2 int g ==>
2771 bounded_on_int (\x. f x * nth_derivative 2 g x + &2 * derivative f x * derivative g x +
2772 nth_derivative 2 f x * g x) int dd_bounds ==>
2773 has_bounded_second_derivative (\x. f x * g x) int dd_bounds`.
2774 rewrite has_bounded_second_derivative !bounded_on_int => /= df dg b.
2775 rewrite nth_diff_mul // andTb => x ineq.
2776 rewrite second_derivative_mul ?b //.
2777 by move: df dg; rewrite !nth_diff_strong_int => -> // ->.
2778 Qed.
2779
2780
2781 (* div *)
2782
2783 Lemma second_derivative_div_bounds f g g_bounds dd_bounds :
2784 `bounded_on_int g int g_bounds ==> interval_not_zero g_bounds ==>
2785 nth_diff_strong_int 2 int f ==>
2786 nth_diff_strong_int 2 int g ==>
2787 bounded_on_int (\x. ((nth_derivative 2 f x * g x - f x * nth_derivative 2 g x) * g x -
2788 &2 * derivative g x * (derivative f x * g x - f x * derivative g x)) / g x pow 3) int dd_bounds ==>
2789 has_bounded_second_derivative (\x. f x / g x) int dd_bounds`.
2790 rewrite has_bounded_second_derivative !bounded_on_int !nth_diff_strong_int => bg gn0 /= df dg b.
2791 have g0 : `!x. interval_arith x int ==> ~(g x = &0)`.
2792 by move => x ineq; apply: interval_arith_not_zero; exists `g_bounds`; rewrite bg.
2793 split => x ineq; first by rewrite diff2_div g0 // df ?dg.
2794 by rewrite second_derivative_div ?g0 ?df ?dg // b.
2795 Qed.
2796
2797
2798 End SecondDerivativeBound.
2799
2800
2801
2802 Section TaylorArith.
2803
2804
2805 "let cell_domain = new_definition `cell_domain x y z w <=>
2806 x <= y /\ y <= z /\ y - x <= w /\ z - y <= w`".
2807
2808
2809 Lemma taylor_x x y z w: `cell_domain x y z w ==>
2810 taylor_interval (\x. x) x y z w (y, y) (&1, &1) (&0, &0)`.
2811 rewrite cell_domain => ineqs.
2812 rewrite taylor_interval !ineqs lin_approx_x !andTb.
2813 rewrite has_bounded_second_derivative.
2814 rewrite nth_diff_strong_int nth_diff_strong nth_differentiable_on nth_differentiable_eq; split.
2815 move => p _; exists `(:real)`; rewrite REAL_OPEN_UNIV !IN_UNIV !andTb => q /=.
2816 rewrite REAL_CONTINUOUS_AT_ID andTb => i.
2817 rewrite "ARITH_RULE `i < 2 <=> i = 0 \/ i = 1`"; case => ->.
2818 by rewrite nth_derivative0 -ONE nth_derivative1 derivative_x /= HAS_REAL_DERIVATIVE_ID.
2819 rewrite nth_derivative1 -TWO nth_derivative2 derivative_x /= derivative_const /=.
2820 by rewrite HAS_REAL_DERIVATIVE_CONST.
2821 rewrite nth_derivative2 derivative_x /= derivative_const bounded_on_int /=.
2822 by rewrite !interval_arith REAL_LE_REFL.
2823 Qed.
2824
2825
2826 Lemma taylor_const c x y z w: `cell_domain x y z w ==>
2827 taylor_interval (\x. c) x y z w (c, c) (&0, &0) (&0, &0)`.
2828 rewrite cell_domain => ineqs.
2829 rewrite taylor_interval !ineqs lin_approx_const !andTb.
2830 rewrite has_bounded_second_derivative.
2831 rewrite nth_diff_strong_int nth_diff_strong nth_differentiable_on nth_differentiable_eq; split.
2832 move => p _; exists `(:real)`; rewrite REAL_OPEN_UNIV !IN_UNIV !andTb => q /=.
2833 rewrite REAL_CONTINUOUS_CONST andTb => i.
2834 rewrite "ARITH_RULE `i < 2 <=> i = 0 \/ i = 1`"; case => ->.
2835 by rewrite nth_derivative0 -ONE nth_derivative1 derivative_const /= HAS_REAL_DERIVATIVE_CONST.
2836 by rewrite nth_derivative1 -TWO nth_derivative2 !derivative_const /= HAS_REAL_DERIVATIVE_CONST.
2837 rewrite nth_derivative2 !derivative_const /= bounded_on_int /=.
2838 by rewrite !interval_arith REAL_LE_REFL.
2839 Qed.
2840
2841
2842 Variable f : `:real->real`.
2843 Variables x y z w : `:real`.
2844 Variables f_bounds df_bounds dd_bounds : `:real#real`.
2845 Variables f_lo f_hi df_lo df_hi : `:real`.
2846
2847
2848 Lemma taylor_f_bounds df dd lo hi t : `taylor_interval f x y z w (f_lo, f_hi) df_bounds dd_bounds ==>
2849 iabs df_bounds = df ==>
2850 iabs dd_bounds = dd ==>
2851 w * (df + w * dd * inv(&2)) <= t ==>
2852 f_hi + t <= hi ==> lo <= f_lo - t ==>
2853 bounded_on_int f (x, z) (lo, hi)`.
2854 move => taylor_f iabs_df iabs_dd t_ineq hi_ineq lo_ineq.
2855 rewrite bounded_on_int !interval_arith => p ineq.
2856 move: (taylor_lower_bound (EQ_SYM iabs_dd) taylor_f) (taylor_upper_bound (EQ_SYM iabs_dd) taylor_f).
2857 rewrite /= !real_div iabs_df => /(_ ineq) ineq1 /(_ ineq) ineq2.
2858 by move: ineq1 ineq2 lo_ineq hi_ineq t_ineq; arith.
2859 Qed.
2860
2861
2862 Lemma taylor_df_bounds dd lo hi: `taylor_interval f x y z w f_bounds (df_lo, df_hi) dd_bounds ==>
2863 iabs dd_bounds = dd ==>
2864 df_hi + w * dd <= hi ==>
2865 lo <= df_lo - w * dd ==>
2866 bounded_on_int (derivative f) (x, z) (lo, hi)`.
2867 move => taylor_f iabs_dd hi_ineq lo_ineq.
2868 rewrite bounded_on_int !interval_arith => p ineq.
2869 move: (taylor_derivative_lower_bound (EQ_SYM iabs_dd) taylor_f ineq).
2870 move: (taylor_derivative_upper_bound (EQ_SYM iabs_dd) taylor_f ineq).
2871 by move: lo_ineq hi_ineq; arith.
2872 Qed.
2873
2874
2875 Lemma bounded_on_int_compose g int g_bounds : `bounded_on_int g int g_bounds ==>
2876 bounded_on_int f g_bounds f_bounds ==>
2877 bounded_on_int (\x. f (g x)) int f_bounds`.
2878 rewrite !bounded_on_int => g_bounded f_bounded x ineq /=.
2879 by rewrite f_bounded g_bounded.
2880 Qed.
2881
2882
2883 Lemma bounded_on_int_imp_interval_arith int : `bounded_on_int f int f_bounds ==>
2884 interval_arith y int ==> interval_arith (f y) f_bounds`.
2885 rewrite bounded_on_int => bounded_f int_y.
2886 by rewrite bounded_f.
2887 Qed.
2888
2889
2890 Lemma taylor_interval_narrow x0 z0 w0: `taylor_interval f x y z w f_bounds df_bounds dd_bounds ==>
2891 cell_domain x0 y z0 w0 ==>
2892 x <= x0 ==> z0 <= z ==>
2893 taylor_interval f x0 y z0 w0 f_bounds df_bounds dd_bounds`.
2894 rewrite !taylor_interval cell_domain !andbA => [] [[ineq lin] dd] c i1 i2.
2895 rewrite lin andbT; split; first by move: c i1 i2; arith.
2896 move: dd; rewrite !has_bounded_second_derivative !nth_diff_strong_int !bounded_on_int => df.
2897 split => p int_p.
2898 by rewrite df; move: int_p i1 i2; rewrite !"GEN_ALL interval_arith"; arith.
2899 by rewrite df; move: int_p i1 i2; rewrite !"GEN_ALL interval_arith"; arith.
2900 Qed.
2901
2902
2903 End TaylorArith.
2904
2905
2906
2907
2908 (********************************)
2909
2910 (*
2911 Lemma second_derivative_scale a dd : `abs a * dd1 <= dd ==>
2912 has_bounded_second_derivative (\x. a * f1 x) s dd`.
2913 move => ineq; move: ddf1; rewrite !has_bounded_second_derivative.
2914 move => [dd1_pos] [f'] [f''] ddf; split.
2915 by apply: REAL_LE_TRANS; exists `abs a * dd1`; rewrite ineq REAL_LE_MUL // REAL_ABS_POS.
2916 exists `\x. a * f' x` `\x. a * f'' x` => x xs /=.
2917 rewrite !HAS_REAL_DERIVATIVE_LMUL_ATREAL ?ddf // !andTb.
2918 apply: REAL_LE_TRANS; exists `abs a * dd1`; rewrite ineq REAL_ABS_MUL REAL_LE_MUL2 //.
2919 by rewrite !REAL_ABS_POS REAL_LE_REFL ddf.
2920 Qed.
2921
2922
2923 Hypothesis ddf2 : `has_bounded_second_derivative f2 s dd2`.
2924
2925 Lemma second_derivative_add dd : `dd1 + dd2 <= dd ==>
2926 has_bounded_second_derivative (\x. f1 x + f2 x) s dd`.
2927 move => ineq; move: ddf1 ddf2; rewrite !has_bounded_second_derivative.
2928 move => [dd1_pos] [f1'] [f1''] ddf1 [dd2_pos] [f2'] [f2''] ddf2; split.
2929 by apply: REAL_LE_TRANS; exists `dd1 + dd2:real`; rewrite ineq REAL_LE_ADD.
2930 exists `\x. f1' x + f2' x:real` `\x. f1'' x + f2'' x:real` => x xs /=.
2931 rewrite !HAS_REAL_DERIVATIVE_ADD ?ddf1 ?ddf2 // !andTb.
2932 apply: REAL_LE_TRANS; exists `dd1 + dd2 : real`; rewrite ineq andbT.
2933 apply: REAL_LE_TRANS; exists `abs (f1'' x) + abs (f2'' x)`.
2934 by rewrite REAL_LE_ADD2 ?ddf1 ?ddf2 // REAL_ABS_TRIANGLE.
2935 Qed.
2936
2937
2938 Lemma second_derivative_sub dd : `dd1 + dd2 <= dd ==>
2939 has_bounded_second_derivative (\x. f1 x - f2 x) s dd`.
2940 move => ineq; move: ddf1 ddf2; rewrite !has_bounded_second_derivative.
2941 move => [dd1_pos] [f1'] [f1''] ddf1 [dd2_pos] [f2'] [f2''] ddf2; split.
2942 by apply: REAL_LE_TRANS; exists `dd1 + dd2:real`; rewrite ineq REAL_LE_ADD.
2943 exists `\x. f1' x - f2' x:real` `\x. f1'' x - f2'' x:real` => x xs /=.
2944 rewrite !HAS_REAL_DERIVATIVE_SUB ?ddf1 ?ddf2 // !andTb real_sub.
2945 apply: REAL_LE_TRANS; exists `dd1 + dd2 : real`; rewrite ineq andbT.
2946 apply: REAL_LE_TRANS; exists `abs (f1'' x) + abs (-- f2'' x)`.
2947 by rewrite {2}REAL_ABS_NEG REAL_LE_ADD2 ?ddf1 ?ddf2 // REAL_ABS_TRIANGLE.
2948 Qed.
2949
2950
2951 Lemma second_derivative_mul dd bf1 bf2 bdf1 bdf2 :
2952 `bounded_on f1 s bf1 ==> bounded_on f2 s bf2 ==>
2953 bounded_on (derivative f1) s bdf1 ==> bounded_on (derivative f2) s bdf2 ==>
2954 dd1 * bf2 + &2 * bdf1 * bdf2 + dd2 * bf1 <= dd ==>
2955 has_bounded_second_derivative (\x. f1 x * f2 x) s dd`.
2956 rewrite !bounded_on => b_f1 b_f2 b_df1 b_df2 ineq.
2957 move: ddf1 ddf2; rewrite !has_bounded_second_derivative.
2958 move => [dd1_pos] [f1'] [f1''] ddf1 [dd2_pos] [f2'] [f2''] ddf2; split.
2959 apply: REAL_LE_TRANS; exists `dd1 * bf2 + &2 * bdf1 * bdf2 + dd2 * bf1`.
2960 by rewrite ineq andbT !REAL_LE_ADD ?REAL_LE_MUL //; arith.
2961 have : `bounded_on f1' s bdf1`.
2962 rewrite bounded_on b_df1 andTb => x xs.
2963 suff ->: `f1' x = derivative f1 x`; first by rewrite b_df1.
2964 by rewrite EQ_SYM_EQ; apply: derivative_unique; rewrite ddf1.
2965 have : `bounded_on f2' s bdf2`.
2966 rewrite bounded_on b_df2 andTb => x xs.
2967 suff ->: `f2' x = derivative f2 x`; first by rewrite b_df2.
2968 by rewrite EQ_SYM_EQ; apply: derivative_unique; rewrite ddf2.
2969 rewrite !bounded_on => b_f2' b_f1'.
2970 exists `\x. f1 x * f2' x + f1' x * f2 x`.
2971 exists `\x. f1'' x * f2 x + &2 * f1' x * f2' x + f1 x * f2'' x` => x xs /=.
2972 rewrite HAS_REAL_DERIVATIVE_MUL_ATREAL ?ddf1 ?ddf2 // andTb; split; last first.
2973 apply: REAL_LE_TRANS; exists `dd1 * bf2 + &2 * bdf1 * bdf2 + dd2 * bf1`.
2974 rewrite ineq andbT.
2975 apply: REAL_LE_TRANS; exists `abs (f1'' x * f2 x) + abs (&2 * f1' x * f2' x + f1 x * f2'' x)`.
2976 rewrite REAL_ABS_TRIANGLE andTb REAL_LE_ADD2 REAL_ABS_MUL.
2977 rewrite REAL_LE_MUL2 ?REAL_ABS_POS ?ddf1 ?b_f2 // andTb.
2978 apply: REAL_LE_TRANS; exists `abs (&2 * f1' x * f2' x) + abs (f1 x * f2'' x)`.
2979 rewrite REAL_ABS_TRIANGLE andTb REAL_LE_ADD2 !REAL_ABS_MUL [`dd2 * _`]REAL_MUL_SYM.
2980 rewrite !REAL_LE_MUL2 ?REAL_ABS_POS ?b_f1' ?b_f2' ?b_f1 ?ddf2 // REAL_LE_MUL ?REAL_ABS_POS //.
2981 by arith.
2982 rewrite "REAL_ARITH `f1'' (x:real) * f2 x + &2 * f1' x * f2' x + f1 x * f2'' x =
2983 (f1 x * f2'' x + f1' x * f2' x) + (f1' x * f2' x + f1'' x * f2 x)`".
2984 by rewrite HAS_REAL_DERIVATIVE_ADD !HAS_REAL_DERIVATIVE_MUL_ATREAL ?ddf1 ?ddf2.
2985 Qed.
2986 *)