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