| 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 |
(* Formal taylor intervals *) |
| 11 |
(* -------------------------------------------------------------------------- *) |
| 12 |
|
| 13 |
needs "Formal_ineqs/arith/more_float.hl";; |
| 14 |
needs "Formal_ineqs/arith/eval_interval.hl";; |
| 15 |
needs "Formal_ineqs/list/list_conversions.hl";; |
| 16 |
needs "Formal_ineqs/list/list_float.hl";; |
| 17 |
needs "Formal_ineqs/list/more_list.hl";; |
| 18 |
needs "Formal_ineqs/misc/misc_vars.hl";; |
| 19 |
|
| 20 |
needs "Formal_ineqs/taylor/theory/taylor_interval-compiled.hl";; |
| 21 |
needs "Formal_ineqs/taylor/theory/multivariate_taylor-compiled.hl";; |
| 22 |
|
| 23 |
|
| 24 |
module M_taylor = struct |
| 25 |
|
| 26 |
open Ssreflect;; |
| 27 |
open Ssrfun;; |
| 28 |
open Ssrbool;; |
| 29 |
open Ssrnat;; |
| 30 |
open Taylor_interval;; |
| 31 |
open Multivariate_taylor;; |
| 32 |
open Misc_functions;; |
| 33 |
open Arith_float;; |
| 34 |
open More_float;; |
| 35 |
open Float_theory;; |
| 36 |
open Eval_interval;; |
| 37 |
open List_conversions;; |
| 38 |
open List_float;; |
| 39 |
open More_list;; |
| 40 |
open Interval_arith;; |
| 41 |
open Misc_vars;; |
| 42 |
|
| 43 |
let MY_RULE = UNDISCH_ALL o PURE_REWRITE_RULE[GSYM IMP_IMP] o SPEC_ALL;; |
| 44 |
let MY_RULE_NUM = UNDISCH_ALL o Arith_nat.NUMERALS_TO_NUM o PURE_REWRITE_RULE[GSYM IMP_IMP] o SPEC_ALL;; |
| 45 |
let MY_RULE_FLOAT = UNDISCH_ALL o Arith_nat.NUMERALS_TO_NUM o |
| 46 |
PURE_REWRITE_RULE[FLOAT_OF_NUM; min_exp_def; GSYM IMP_IMP] o SPEC_ALL;; |
| 47 |
|
| 48 |
|
| 49 |
|
| 50 |
let max_dim = 8;; |
| 51 |
|
| 52 |
let inst_first_type_var ty th = |
| 53 |
let ty_vars = type_vars_in_term (concl th) in |
| 54 |
if ty_vars = [] then |
| 55 |
failwith "inst_first_type: no type variables in the theorem" |
| 56 |
else |
| 57 |
INST_TYPE [ty, hd ty_vars] th;; |
| 58 |
|
| 59 |
|
| 60 |
let float0 = mk_float 0 0 and |
| 61 |
interval0 = mk_float_interval_small_num 0;; |
| 62 |
|
| 63 |
|
| 64 |
let has_size_array = Array.init (max_dim + 1) |
| 65 |
(fun i -> match i with |
| 66 |
| 0 -> TRUTH |
| 67 |
| 1 -> HAS_SIZE_1 |
| 68 |
| _ -> HAS_SIZE_DIMINDEX_RULE(mk_finty(Num.num_of_int i)));; |
| 69 |
|
| 70 |
let dimindex_array = Array.init (max_dim + 1) |
| 71 |
(fun i -> if i < 1 then TRUTH else MATCH_MP DIMINDEX_UNIQUE has_size_array.(i));; |
| 72 |
|
| 73 |
let n_type_array = Array.init (max_dim + 1) |
| 74 |
(fun i -> if i < 1 then bool_ty else |
| 75 |
let dimindex_th = dimindex_array.(i) in |
| 76 |
(hd o snd o dest_type o snd o dest_const o rand o lhand o concl) dimindex_th);; |
| 77 |
|
| 78 |
let n_vector_type_array = Array.init (max_dim + 1) |
| 79 |
(fun i -> if i < 1 then bool_ty else mk_type ("cart", [real_ty; n_type_array.(i)]));; |
| 80 |
|
| 81 |
|
| 82 |
let x_var_names = Array.init (max_dim + 1) (fun i -> "x"^(string_of_int i)) and |
| 83 |
y_var_names = Array.init (max_dim + 1) (fun i -> "y"^(string_of_int i)) and |
| 84 |
z_var_names = Array.init (max_dim + 1) (fun i -> "z"^(string_of_int i)) and |
| 85 |
w_var_names = Array.init (max_dim + 1) (fun i -> "w"^(string_of_int i));; |
| 86 |
|
| 87 |
let x_vars_array = Array.init (max_dim + 1) (fun i -> mk_var(x_var_names.(i), real_ty)) and |
| 88 |
y_vars_array = Array.init (max_dim + 1) (fun i -> mk_var(y_var_names.(i), real_ty)) and |
| 89 |
z_vars_array = Array.init (max_dim + 1) (fun i -> mk_var(z_var_names.(i), real_ty)) and |
| 90 |
w_vars_array = Array.init (max_dim + 1) (fun i -> mk_var(w_var_names.(i), real_ty));; |
| 91 |
|
| 92 |
let df_vars_array = Array.init (max_dim + 1) (fun i -> mk_var ("df"^(string_of_int i), real_pair_ty));; |
| 93 |
let dd_vars_array = Array.init (max_dim + 1) (fun i -> |
| 94 |
Array.init (max_dim + 1) (fun j -> mk_var ("dd"^(string_of_int i)^(string_of_int j), real_pair_ty)));; |
| 95 |
|
| 96 |
let dest_vector = dest_list o rand;; |
| 97 |
|
| 98 |
let mk_vector list_tm = |
| 99 |
let n = (length o dest_list) list_tm in |
| 100 |
let ty = (hd o snd o dest_type o type_of) list_tm in |
| 101 |
let vec = mk_const ("vector", [ty, aty; n_type_array.(n), nty]) in |
| 102 |
mk_comb (vec, list_tm);; |
| 103 |
|
| 104 |
let mk_vector_list list = |
| 105 |
mk_vector (mk_list (list, type_of (hd list)));; |
| 106 |
|
| 107 |
let el_thms_array = |
| 108 |
let el_tm = `EL : num->(A)list->A` in |
| 109 |
let gen0 n = |
| 110 |
let e_list = mk_list (map (fun i -> mk_var ("e"^(string_of_int i), aty)) (1--n), aty) in |
| 111 |
let el0_th = REWRITE_CONV[EL; HD] (mk_binop el_tm `0` e_list) in |
| 112 |
Array.make n el0_th in |
| 113 |
let array = Array.init (max_dim + 1) gen0 in |
| 114 |
let gen_i n i = |
| 115 |
let e_list = (rand o lhand o concl) array.(n).(i) in |
| 116 |
let prev_thm = array.(n - 1).(i - 1) in |
| 117 |
let i_tm = mk_small_numeral i in |
| 118 |
let prev_i = num_CONV i_tm in |
| 119 |
let el_th = REWRITE_CONV[prev_i; EL; HD; TL; prev_thm] (mk_binop el_tm i_tm e_list) in |
| 120 |
array.(n).(i) <- el_th in |
| 121 |
let _ = map (fun n -> map (fun i -> gen_i n i) (1--(n - 1))) (2--max_dim) in |
| 122 |
array;; |
| 123 |
|
| 124 |
|
| 125 |
let VECTOR_COMPONENT = prove(`!l i. i IN 1..dimindex (:N) ==> |
| 126 |
(vector l:A^N)$i = EL (i - 1) l`, |
| 127 |
REWRITE_TAC[IN_NUMSEG] THEN REPEAT GEN_TAC THEN DISCH_TAC THEN REWRITE_TAC[vector] THEN |
| 128 |
MATCH_MP_TAC LAMBDA_BETA THEN ASM_REWRITE_TAC[]);; |
| 129 |
|
| 130 |
let gen_comp_thm n i = |
| 131 |
let i_tm = mk_small_numeral i and |
| 132 |
x_list = mk_list (map (fun i -> mk_var("x"^(string_of_int i), aty)) (1--n), aty) in |
| 133 |
let th0 = (ISPECL [x_list; i_tm] o inst_first_type_var (n_type_array.(n))) VECTOR_COMPONENT in |
| 134 |
let th1 = (CONV_RULE NUM_REDUCE_CONV o REWRITE_RULE[IN_NUMSEG; dimindex_array.(n)]) th0 in |
| 135 |
REWRITE_RULE[el_thms_array.(n).(i - 1)] th1;; |
| 136 |
|
| 137 |
let comp_thms_array = Array.init (max_dim + 1) |
| 138 |
(fun n -> Array.init (n + 1) |
| 139 |
(fun i -> if i < 1 || n < 1 then TRUTH else gen_comp_thm n i));; |
| 140 |
|
| 141 |
|
| 142 |
(************************************) |
| 143 |
(* m_cell_domain *) |
| 144 |
|
| 145 |
let ALL2_ALL_ZIP = prove(`!(P:A->B->bool) l1 l2. LENGTH l1 = LENGTH l2 ==> |
| 146 |
(ALL2 P l1 l2 <=> ALL (\p. P (FST p) (SND p)) (ZIP l1 l2))`, |
| 147 |
GEN_TAC THEN LIST_INDUCT_TAC THENL |
| 148 |
[ |
| 149 |
GEN_TAC THEN REWRITE_TAC[LENGTH; EQ_SYM_EQ; LENGTH_EQ_NIL] THEN |
| 150 |
DISCH_THEN (fun th -> REWRITE_TAC[th]) THEN |
| 151 |
REWRITE_TAC[ZIP; ALL2; ALL]; |
| 152 |
ALL_TAC |
| 153 |
] THEN |
| 154 |
|
| 155 |
LIST_INDUCT_TAC THEN REWRITE_TAC[LENGTH] THENL [ARITH_TAC; ALL_TAC] THEN |
| 156 |
REWRITE_TAC[eqSS] THEN DISCH_TAC THEN |
| 157 |
REWRITE_TAC[ALL2; ZIP; ALL] THEN |
| 158 |
FIRST_X_ASSUM (new_rewrite [] []) THEN ASM_REWRITE_TAC[]);; |
| 159 |
|
| 160 |
let EL_ZIP = prove(`!(l1:(A)list) (l2:(B)list) i. LENGTH l1 = LENGTH l2 /\ i < LENGTH l1 ==> |
| 161 |
EL i (ZIP l1 l2) = (EL i l1, EL i l2)`, |
| 162 |
LIST_INDUCT_TAC THEN LIST_INDUCT_TAC THEN REWRITE_TAC[ZIP; LENGTH] THEN TRY ARITH_TAC THEN |
| 163 |
case THEN REWRITE_TAC[EL; HD; TL] THEN GEN_TAC THEN |
| 164 |
REWRITE_TAC[eqSS; ARITH_RULE `SUC n < SUC x <=> n < x`] THEN STRIP_TAC THEN |
| 165 |
FIRST_X_ASSUM MATCH_MP_TAC THEN ASM_REWRITE_TAC[]);; |
| 166 |
|
| 167 |
let LENGTH_ZIP = prove(`!l1 l2. LENGTH l1 = LENGTH l2 ==> LENGTH (ZIP l1 l2) = LENGTH l1`, |
| 168 |
LIST_INDUCT_TAC THEN LIST_INDUCT_TAC THEN REWRITE_TAC[ZIP; LENGTH] THEN TRY ARITH_TAC THEN |
| 169 |
REWRITE_TAC[eqSS] THEN DISCH_TAC THEN FIRST_X_ASSUM MATCH_MP_TAC THEN ASM_REWRITE_TAC[]);; |
| 170 |
|
| 171 |
|
| 172 |
|
| 173 |
let test_domain_xi = new_definition |
| 174 |
`test_domain_xi xz yw <=> FST xz <= FST yw /\ FST yw <= SND xz /\ |
| 175 |
FST yw - FST xz <= SND yw /\ SND xz - FST yw <= SND yw`;; |
| 176 |
|
| 177 |
|
| 178 |
let MK_CELL_DOMAIN = prove(`!xz (yw:(real#real)list) x z y w. |
| 179 |
LENGTH x = dimindex (:N) /\ LENGTH z = dimindex (:N) /\ |
| 180 |
LENGTH y = dimindex (:N) /\ LENGTH w = dimindex (:N) /\ |
| 181 |
ZIP y w = yw /\ ZIP x z = xz /\ |
| 182 |
ALL2 test_domain_xi xz yw ==> |
| 183 |
m_cell_domain (vector x, vector z:real^N) (vector y) (vector w)`, |
| 184 |
REPEAT GEN_TAC THEN STRIP_TAC THEN POP_ASSUM MP_TAC THEN |
| 185 |
SUBGOAL_THEN `LENGTH (xz:(real#real)list) = dimindex (:N) /\ LENGTH (yw:(real#real)list) = dimindex (:N)` ASSUME_TAC THENL |
| 186 |
[ |
| 187 |
EXPAND_TAC "yw" THEN EXPAND_TAC "xz" THEN |
| 188 |
REPEAT (new_rewrite [] [] LENGTH_ZIP) THEN ASM_REWRITE_TAC[]; |
| 189 |
ALL_TAC |
| 190 |
] THEN |
| 191 |
rewrite [] [] ALL2_ALL_ZIP THEN ASM_REWRITE_TAC[m_cell_domain; GSYM ALL_EL] THEN DISCH_TAC THEN |
| 192 |
REWRITE_TAC[m_cell_domain] THEN GEN_TAC THEN DISCH_TAC THEN |
| 193 |
REPEAT (new_rewrite [] [] VECTOR_COMPONENT) THEN ASM_REWRITE_TAC[] THEN |
| 194 |
ABBREV_TAC `j = i - 1` THEN |
| 195 |
SUBGOAL_THEN `j < dimindex (:N)` ASSUME_TAC THENL |
| 196 |
[ |
| 197 |
POP_ASSUM MP_TAC THEN POP_ASSUM MP_TAC THEN REWRITE_TAC[IN_NUMSEG] THEN ARITH_TAC; |
| 198 |
ALL_TAC |
| 199 |
] THEN |
| 200 |
FIRST_X_ASSUM (MP_TAC o SPEC `j:num`) THEN REWRITE_TAC[test_domain_xi] THEN |
| 201 |
rewrite [] [] LENGTH_ZIP THEN ASM_REWRITE_TAC[] THEN |
| 202 |
rewrite [] [] EL_ZIP THEN ASM_REWRITE_TAC[] THEN |
| 203 |
EXPAND_TAC "xz" THEN EXPAND_TAC "yw" THEN |
| 204 |
REPEAT (new_rewrite [] [] EL_ZIP) THEN ASM_REWRITE_TAC[] THEN |
| 205 |
ARITH_TAC);; |
| 206 |
|
| 207 |
|
| 208 |
|
| 209 |
(* array of theorems *) |
| 210 |
let mk_m_domain_array = |
| 211 |
let mk_m_domain n = |
| 212 |
let dimindex_th = dimindex_array.(n) in |
| 213 |
let n_ty = (hd o snd o dest_type o snd o dest_const o rand o lhand o concl) dimindex_th in |
| 214 |
let nty = `:N` in |
| 215 |
(UNDISCH_ALL o REWRITE_RULE[float0_eq] o DISCH_ALL o RULE o |
| 216 |
REWRITE_RULE[dimindex_th] o INST_TYPE[n_ty, nty]) MK_CELL_DOMAIN in |
| 217 |
Array.init (max_dim + 1) (fun i -> if i < 1 then TRUTH else mk_m_domain i);; |
| 218 |
|
| 219 |
|
| 220 |
let TEST_DOMAIN_XI' = (EQT_INTRO o RULE o prove)(`xz = (x,z) /\ yw = (y,w) /\ |
| 221 |
x <= y /\ y <= z /\ y - x <= w1 /\ z - y <= w2 /\ w1 <= w /\ w2 <= w ==> test_domain_xi xz yw`, |
| 222 |
SIMP_TAC[test_domain_xi] THEN REAL_ARITH_TAC);; |
| 223 |
|
| 224 |
|
| 225 |
let eval_test_domain_xi pp test_domain_tm = |
| 226 |
let ltm, yw = dest_comb test_domain_tm in |
| 227 |
let xz = rand ltm in |
| 228 |
let x, z = dest_pair xz and |
| 229 |
y, w = dest_pair yw in |
| 230 |
let (<=) = (fun t1 t2 -> EQT_ELIM (float_le t1 t2)) and |
| 231 |
(-) = float_sub_hi pp in |
| 232 |
let x_le_y = x <= y and |
| 233 |
y_le_z = y <= z and |
| 234 |
yx_le_w1 = y - x and |
| 235 |
zy_le_w2 = z - y in |
| 236 |
let w1 = (rand o concl) yx_le_w1 and |
| 237 |
w2 = (rand o concl) zy_le_w2 in |
| 238 |
let w1_le_w = w1 <= w and |
| 239 |
w2_le_w = w2 <= w in |
| 240 |
(MY_PROVE_HYP (REFL xz) o MY_PROVE_HYP (REFL yw) o |
| 241 |
MY_PROVE_HYP x_le_y o MY_PROVE_HYP y_le_z o |
| 242 |
MY_PROVE_HYP yx_le_w1 o MY_PROVE_HYP zy_le_w2 o |
| 243 |
MY_PROVE_HYP w1_le_w o MY_PROVE_HYP w2_le_w o |
| 244 |
INST[x, x_var_real; y, y_var_real; z, z_var_real; w, w_var_real; |
| 245 |
w1, w1_var_real; w2, w2_var_real; |
| 246 |
xz, xz_pair_var; yw, yw_pair_var]) TEST_DOMAIN_XI';; |
| 247 |
|
| 248 |
|
| 249 |
(* mk_m_center_domain *) |
| 250 |
let mk_m_center_domain n pp x_list_tm z_list_tm = |
| 251 |
let x_list = dest_list x_list_tm and |
| 252 |
z_list = dest_list z_list_tm in |
| 253 |
let y_list = |
| 254 |
let ( * ) = (fun t1 t2 -> (rand o concl) (float_mul_eq t1 t2)) and |
| 255 |
(+) = (fun t1 t2 -> (rand o concl) (float_add_hi pp t1 t2)) in |
| 256 |
map2 (fun x y -> if x = y then x else float_inv2 * (x + y)) x_list z_list in |
| 257 |
|
| 258 |
let w_list = |
| 259 |
let (-) = (fun t1 t2 -> (rand o concl) (float_sub_hi pp t1 t2)) and |
| 260 |
max = (fun t1 t2 -> (rand o concl) (float_max t1 t2)) in |
| 261 |
let w1 = map2 (-) y_list x_list and |
| 262 |
w2 = map2 (-) z_list y_list in |
| 263 |
map2 max w1 w2 in |
| 264 |
|
| 265 |
let y_list_tm = mk_list (y_list, real_ty) and |
| 266 |
w_list_tm = mk_list (w_list, real_ty) in |
| 267 |
|
| 268 |
let yw_zip_th = eval_zip y_list_tm w_list_tm and |
| 269 |
xz_zip_th = eval_zip x_list_tm z_list_tm in |
| 270 |
|
| 271 |
let yw_list_tm = (rand o concl) yw_zip_th and |
| 272 |
xz_list_tm = (rand o concl) xz_zip_th in |
| 273 |
|
| 274 |
let len_x_th = eval_length x_list_tm and |
| 275 |
len_z_th = eval_length z_list_tm and |
| 276 |
len_y_th = eval_length y_list_tm and |
| 277 |
len_w_th = eval_length w_list_tm in |
| 278 |
let th0 = (MY_PROVE_HYP len_x_th o MY_PROVE_HYP len_z_th o |
| 279 |
MY_PROVE_HYP len_y_th o MY_PROVE_HYP len_w_th o |
| 280 |
MY_PROVE_HYP yw_zip_th o MY_PROVE_HYP xz_zip_th o |
| 281 |
INST[x_list_tm, x_var_real_list; z_list_tm, z_var_real_list; |
| 282 |
y_list_tm, y_var_real_list; w_list_tm, w_var_real_list; |
| 283 |
yw_list_tm, yw_var; xz_list_tm, xz_var]) mk_m_domain_array.(n) in |
| 284 |
let all_th = (EQT_ELIM o all2_conv_univ (eval_test_domain_xi pp) o hd o hyp) th0 in |
| 285 |
MY_PROVE_HYP all_th th0;; |
| 286 |
|
| 287 |
|
| 288 |
|
| 289 |
(***********************) |
| 290 |
|
| 291 |
let MK_M_TAYLOR_INTERVAL' = (RULE o MATCH_MP iffRL o SPEC_ALL) m_taylor_interval;; |
| 292 |
|
| 293 |
|
| 294 |
let get_types_and_vars n = |
| 295 |
let ty = n_type_array.(n) and |
| 296 |
xty = n_vector_type_array.(n) in |
| 297 |
let x_var = mk_var ("x", xty) and |
| 298 |
f_var = mk_var ("f", mk_fun_ty xty real_ty) and |
| 299 |
y_var = mk_var ("y", xty) and |
| 300 |
w_var = mk_var ("w", xty) and |
| 301 |
domain_var = mk_var ("domain", mk_type ("prod", [xty; xty])) in |
| 302 |
ty, xty, x_var, f_var, y_var, w_var, domain_var;; |
| 303 |
|
| 304 |
|
| 305 |
|
| 306 |
let dest_m_cell_domain domain_tm = |
| 307 |
let lhs, w_tm = dest_comb domain_tm in |
| 308 |
let lhs2, y_tm = dest_comb lhs in |
| 309 |
rand lhs2, y_tm, w_tm;; |
| 310 |
|
| 311 |
|
| 312 |
(**************************************************) |
| 313 |
|
| 314 |
(* Given a variable of the type `:real^N`, returns the number N *) |
| 315 |
let get_dim = Num.int_of_num o dest_finty o hd o tl o snd o dest_type o type_of;; |
| 316 |
|
| 317 |
|
| 318 |
(**********************) |
| 319 |
(* eval_m_taylor_poly *) |
| 320 |
|
| 321 |
let partial_pow = prove(`!i f n (y:real^N). lift o f differentiable at y ==> |
| 322 |
partial i (\x. f x pow n) y = &n * f y pow (n - 1) * partial i f y`, |
| 323 |
REPEAT STRIP_TAC THEN |
| 324 |
SUBGOAL_THEN `(\x:real^N. f x pow n) = (\t. t pow n) o f` (fun th -> REWRITE_TAC[th]) THENL |
| 325 |
[ |
| 326 |
ONCE_REWRITE_TAC[GSYM eq_ext] THEN REWRITE_TAC[o_THM]; |
| 327 |
ALL_TAC |
| 328 |
] THEN |
| 329 |
new_rewrite [] [] partial_uni_compose THENL |
| 330 |
[ |
| 331 |
ASM_REWRITE_TAC[] THEN |
| 332 |
new_rewrite [] [] REAL_DIFFERENTIABLE_POW_ATREAL THEN REWRITE_TAC[REAL_DIFFERENTIABLE_ID]; |
| 333 |
ALL_TAC |
| 334 |
] THEN |
| 335 |
new_rewrite [] [] derivative_pow THEN REWRITE_TAC[REAL_DIFFERENTIABLE_ID; derivative_x] THEN |
| 336 |
REAL_ARITH_TAC);; |
| 337 |
|
| 338 |
|
| 339 |
let nth_diff2_pow = prove(`!n y. nth_diff_strong 2 (\x. x pow n) y`, |
| 340 |
REWRITE_TAC[nth_diff_strong2_eq] THEN REPEAT GEN_TAC THEN |
| 341 |
EXISTS_TAC `(:real)` THEN REWRITE_TAC[REAL_OPEN_UNIV; IN_UNIV] THEN GEN_TAC THEN |
| 342 |
new_rewrite [] [] REAL_DIFFERENTIABLE_POW_ATREAL THEN REWRITE_TAC[REAL_DIFFERENTIABLE_ID] THEN |
| 343 |
MATCH_MP_TAC differentiable_local THEN |
| 344 |
EXISTS_TAC `\x. &n * x pow (n - 1)` THEN EXISTS_TAC `(:real)` THEN |
| 345 |
REWRITE_TAC[REAL_OPEN_UNIV; IN_UNIV] THEN |
| 346 |
new_rewrite [] [] REAL_DIFFERENTIABLE_MUL_ATREAL THEN REWRITE_TAC[REAL_DIFFERENTIABLE_CONST] THENL |
| 347 |
[ |
| 348 |
new_rewrite [] [] REAL_DIFFERENTIABLE_POW_ATREAL THEN REWRITE_TAC[REAL_DIFFERENTIABLE_ID]; |
| 349 |
ALL_TAC |
| 350 |
] THEN |
| 351 |
GEN_TAC THEN new_rewrite [] [] derivative_pow THEN REWRITE_TAC[REAL_DIFFERENTIABLE_ID] THEN |
| 352 |
REWRITE_TAC[derivative_x; REAL_MUL_RID]);; |
| 353 |
|
| 354 |
|
| 355 |
let diff2c_pow = prove(`!f n (x:real^N). diff2c f x ==> diff2c (\x. f x pow n) x`, |
| 356 |
REPEAT STRIP_TAC THEN |
| 357 |
SUBGOAL_THEN `(\x:real^N. f x pow n) = (\t. t pow n) o f` (fun th -> REWRITE_TAC[th]) THENL |
| 358 |
[ |
| 359 |
ONCE_REWRITE_TAC[GSYM eq_ext] THEN REWRITE_TAC[o_THM]; |
| 360 |
ALL_TAC |
| 361 |
] THEN |
| 362 |
apply_tac diff2c_uni_compose THEN ASM_REWRITE_TAC[nth_diff2_pow] THEN |
| 363 |
REWRITE_TAC[nth_derivative2] THEN |
| 364 |
SUBGOAL_THEN `!n. derivative (\t. t pow n) = (\t. &n * t pow (n - 1))` ASSUME_TAC THENL |
| 365 |
[ |
| 366 |
GEN_TAC THEN REWRITE_TAC[FUN_EQ_THM] THEN GEN_TAC THEN |
| 367 |
new_rewrite [] [] derivative_pow THEN REWRITE_TAC[REAL_DIFFERENTIABLE_ID] THEN |
| 368 |
REWRITE_TAC[derivative_x; REAL_MUL_RID]; |
| 369 |
ALL_TAC |
| 370 |
] THEN |
| 371 |
ASM_REWRITE_TAC[] THEN |
| 372 |
SUBGOAL_THEN `!n. derivative (\t. &n * t pow (n - 1)) = (\t. &n * derivative (\t. t pow (n - 1)) t)` ASSUME_TAC THENL |
| 373 |
[ |
| 374 |
GEN_TAC THEN REWRITE_TAC[FUN_EQ_THM] THEN GEN_TAC THEN |
| 375 |
new_rewrite [] [] derivative_scale THEN REWRITE_TAC[] THEN |
| 376 |
MATCH_MP_TAC REAL_DIFFERENTIABLE_POW_ATREAL THEN REWRITE_TAC[REAL_DIFFERENTIABLE_ID]; |
| 377 |
ALL_TAC |
| 378 |
] THEN |
| 379 |
ASM_REWRITE_TAC[] THEN |
| 380 |
REPEAT (MATCH_MP_TAC REAL_CONTINUOUS_LMUL) THEN |
| 381 |
MATCH_MP_TAC REAL_CONTINUOUS_POW THEN |
| 382 |
REWRITE_TAC[REAL_CONTINUOUS_AT_ID]);; |
| 383 |
|
| 384 |
|
| 385 |
let diff2c_domain_pow = prove(`!f n domain. diff2c_domain domain f ==> |
| 386 |
diff2c_domain domain (\x. f x pow n)`, |
| 387 |
REWRITE_TAC[diff2c_domain] THEN REPEAT STRIP_TAC THEN ASM_SIMP_TAC[diff2c_pow]);; |
| 388 |
|
| 389 |
|
| 390 |
let diff2c_domain_tm = `diff2c_domain domain`;; |
| 391 |
|
| 392 |
let rec gen_diff2c_domain_poly poly_tm = |
| 393 |
let x_var, expr = dest_abs poly_tm in |
| 394 |
let n = get_dim x_var in |
| 395 |
let diff2c_tm = mk_icomb (diff2c_domain_tm, poly_tm) in |
| 396 |
if frees expr = [] then |
| 397 |
(* const *) |
| 398 |
(SPEC_ALL o ISPEC expr o inst_first_type_var (n_type_array.(n))) diff2c_domain_const |
| 399 |
else |
| 400 |
let lhs, r_tm = dest_comb expr in |
| 401 |
if lhs = neg_op_real then |
| 402 |
(* -- *) |
| 403 |
let r_th = gen_diff2c_domain_poly (mk_abs (x_var, r_tm)) in |
| 404 |
prove(diff2c_tm, MATCH_MP_TAC diff2c_domain_neg THEN REWRITE_TAC[r_th]) |
| 405 |
else |
| 406 |
let op, l_tm = dest_comb lhs in |
| 407 |
let name = (fst o dest_const) op in |
| 408 |
if name = "$" then |
| 409 |
(* x$k *) |
| 410 |
let dim_th = dimindex_array.(n) in |
| 411 |
prove(diff2c_tm, MATCH_MP_TAC diff2c_domain_x THEN |
| 412 |
REWRITE_TAC[IN_NUMSEG; dim_th] THEN ARITH_TAC) |
| 413 |
else |
| 414 |
let l_th = gen_diff2c_domain_poly (mk_abs (x_var, l_tm)) in |
| 415 |
if name = "real_pow" then |
| 416 |
(* f pow n *) |
| 417 |
prove(diff2c_tm, MATCH_MP_TAC diff2c_domain_pow THEN REWRITE_TAC[l_th]) |
| 418 |
else |
| 419 |
let r_th = gen_diff2c_domain_poly (mk_abs (x_var, r_tm)) in |
| 420 |
prove(diff2c_tm, |
| 421 |
MAP_FIRST apply_tac [diff2c_domain_add; diff2c_domain_sub; diff2c_domain_mul] THEN |
| 422 |
REWRITE_TAC[l_th; r_th]);; |
| 423 |
|
| 424 |
|
| 425 |
let gen_diff2c_poly = |
| 426 |
let th_imp = prove(`!f. (!domain. diff2c_domain domain f) ==> !x:real^N. diff2c f x`, |
| 427 |
REWRITE_TAC[diff2c_domain] THEN REPEAT STRIP_TAC THEN FIRST_X_ASSUM MATCH_MP_TAC THEN |
| 428 |
EXISTS_TAC `(x:real^N, x:real^N)` THEN |
| 429 |
REWRITE_TAC[INTERVAL_SING; IN_SING]) in |
| 430 |
fun poly_tm -> |
| 431 |
(MATCH_MP th_imp o GEN_ALL o gen_diff2c_domain_poly) poly_tm;; |
| 432 |
|
| 433 |
|
| 434 |
let gen_diff_poly = |
| 435 |
let th_imp = prove(`!f. (!domain. diff2c_domain domain f) ==> !x:real^N. lift o f differentiable at x`, |
| 436 |
REWRITE_TAC[diff2c_domain; diff2c; diff2] THEN REPEAT STRIP_TAC THEN |
| 437 |
FIRST_X_ASSUM (MP_TAC o SPECL [`x:real^N, x:real^N`; `x:real^N`]) THEN |
| 438 |
REWRITE_TAC[INTERVAL_SING; IN_SING] THEN case THEN REPEAT STRIP_TAC THEN |
| 439 |
FIRST_X_ASSUM (MP_TAC o SPEC `x:real^N`) THEN ASM_SIMP_TAC[]) in |
| 440 |
fun poly_tm -> |
| 441 |
(MATCH_MP th_imp o GEN_ALL o gen_diff2c_domain_poly) poly_tm;; |
| 442 |
|
| 443 |
|
| 444 |
let in_tm = `IN`;; |
| 445 |
|
| 446 |
let add_to_hash tbl max_size key value = |
| 447 |
let _ = if Hashtbl.length tbl >= max_size then Hashtbl.clear tbl else () in |
| 448 |
Hashtbl.add tbl key value;; |
| 449 |
|
| 450 |
(* Formally computes partial derivatives of a polynomial *) |
| 451 |
let gen_partial_poly = |
| 452 |
let max_hash = 1000 in |
| 453 |
let hash = Hashtbl.create max_hash in |
| 454 |
fun i poly_tm -> |
| 455 |
let key = (i, poly_tm) in |
| 456 |
try Hashtbl.find hash (i, poly_tm) |
| 457 |
with Not_found -> |
| 458 |
let i_tm = mk_small_numeral i in |
| 459 |
let rec gen_rec poly_tm = |
| 460 |
let x_var, expr = dest_abs poly_tm in |
| 461 |
let n = get_dim x_var in |
| 462 |
if frees expr = [] then |
| 463 |
(* const *) |
| 464 |
(SPECL [i_tm; expr] o inst_first_type_var (n_type_array.(n))) partial_const |
| 465 |
else |
| 466 |
let lhs, r_tm = dest_comb expr in |
| 467 |
if lhs = neg_op_real then |
| 468 |
(* -- *) |
| 469 |
let r_poly = mk_abs (x_var, r_tm) in |
| 470 |
let r_diff = (SPEC_ALL o gen_diff_poly) r_poly and |
| 471 |
r_partial = gen_rec r_poly in |
| 472 |
let th0 = SPEC i_tm (MATCH_MP partial_neg r_diff) in |
| 473 |
REWRITE_RULE[r_partial] th0 |
| 474 |
else |
| 475 |
let op, l_tm = dest_comb lhs in |
| 476 |
let name = (fst o dest_const) op in |
| 477 |
if name = "$" then |
| 478 |
(* comp *) |
| 479 |
let dim_th = dimindex_array.(n) in |
| 480 |
let dim_tm = (lhand o concl) dim_th in |
| 481 |
let i_eq_k = NUM_EQ_CONV (mk_eq (i_tm, r_tm)) in |
| 482 |
let int_tm = mk_binop `..` `1` dim_tm in |
| 483 |
let k_in_dim = prove(mk_comb (mk_icomb(in_tm, r_tm), int_tm), |
| 484 |
REWRITE_TAC[IN_NUMSEG; dim_th] THEN ARITH_TAC) in |
| 485 |
(REWRITE_RULE[i_eq_k] o MATCH_MP (SPECL [r_tm; i_tm] partial_x)) k_in_dim |
| 486 |
else |
| 487 |
let l_poly = mk_abs (x_var, l_tm) in |
| 488 |
let l_partial = gen_rec l_poly in |
| 489 |
let l_diff = (SPEC_ALL o gen_diff_poly) l_poly in |
| 490 |
if name = "real_pow" then |
| 491 |
(* f pow n *) |
| 492 |
let th0 = SPECL [i_tm; r_tm] (MATCH_MP partial_pow l_diff) in |
| 493 |
REWRITE_RULE[l_partial] th0 |
| 494 |
else |
| 495 |
let r_poly = mk_abs (x_var, r_tm) in |
| 496 |
let r_partial = gen_rec r_poly in |
| 497 |
let r_diff = (SPEC_ALL o gen_diff_poly) r_poly in |
| 498 |
let imp_th = assoc op [add_op_real, partial_add; |
| 499 |
sub_op_real, partial_sub; |
| 500 |
mul_op_real, partial_mul] in |
| 501 |
let th0 = SPEC i_tm (MATCH_MP (MATCH_MP imp_th l_diff) r_diff) in |
| 502 |
REWRITE_RULE[l_partial; r_partial] th0 in |
| 503 |
|
| 504 |
let th1 = gen_rec poly_tm in |
| 505 |
let th2 = ((NUM_REDUCE_CONV THENC REWRITE_CONV[DECIMAL] THENC REAL_POLY_CONV) o rand o concl) th1 in |
| 506 |
let th3 = (REWRITE_RULE[ETA_AX] o ONCE_REWRITE_RULE[eq_ext] o GEN_ALL) (TRANS th1 th2) in |
| 507 |
let _ = add_to_hash hash max_hash key th3 in |
| 508 |
th3;; |
| 509 |
|
| 510 |
|
| 511 |
let gen_partial2_poly i j poly_tm = |
| 512 |
let partial_j = gen_partial_poly j poly_tm in |
| 513 |
let partial_ij = gen_partial_poly i (rand (concl partial_j)) in |
| 514 |
let pi = (rator o lhand o concl) partial_ij in |
| 515 |
REWRITE_RULE[GSYM partial2] (TRANS (AP_TERM pi partial_j) partial_ij);; |
| 516 |
|
| 517 |
|
| 518 |
(********************************************) |
| 519 |
|
| 520 |
let eval_diff2_poly diff2_domain_th = |
| 521 |
fun xx zz -> |
| 522 |
let domain_tm = mk_pair (xx, zz) in |
| 523 |
INST[domain_tm, mk_var ("domain", type_of domain_tm)] diff2_domain_th;; |
| 524 |
|
| 525 |
|
| 526 |
(*****************************) |
| 527 |
(* m_lin_approx *) |
| 528 |
|
| 529 |
let CONST_INTERVAL' = RULE CONST_INTERVAL;; |
| 530 |
|
| 531 |
let dest_lin_approx approx_tm = |
| 532 |
let lhs, df_bounds = dest_comb approx_tm in |
| 533 |
let lhs2, f_bounds = dest_comb lhs in |
| 534 |
let lhs3, x_tm = dest_comb lhs2 in |
| 535 |
let f_tm = rand lhs3 in |
| 536 |
f_tm, x_tm, f_bounds, df_bounds;; |
| 537 |
|
| 538 |
let gen_lin_approx_eq_thm n = |
| 539 |
let ty = n_type_array.(n) in |
| 540 |
let df_vars = map (fun i -> df_vars_array.(i)) (1--n) in |
| 541 |
let df_bounds_list = mk_list (df_vars, real_pair_ty) in |
| 542 |
let th0 = (SPECL[f_bounds_var; df_bounds_list] o inst_first_type_var ty) m_lin_approx in |
| 543 |
let th1 = (CONV_RULE NUM_REDUCE_CONV o REWRITE_RULE[all_n]) th0 in |
| 544 |
th1;; |
| 545 |
|
| 546 |
|
| 547 |
let gen_lin_approx_poly_thm poly_tm diff_th partials = |
| 548 |
let x_var, _ = dest_abs poly_tm in |
| 549 |
let n = get_dim x_var in |
| 550 |
let lin_eq = (REWRITE_RULE partials o SPECL [poly_tm]) (gen_lin_approx_eq_thm n) in |
| 551 |
let x_vec = mk_vector_list (map (fun i -> x_vars_array.(i)) (1--n)) in |
| 552 |
let th1 = (REWRITE_RULE (Array.to_list comp_thms_array.(n)) o SPEC x_vec o REWRITE_RULE[diff_th]) lin_eq in |
| 553 |
th1;; |
| 554 |
|
| 555 |
|
| 556 |
let gen_lin_approx_poly_thm0 poly_tm = |
| 557 |
let x_var, _ = dest_abs poly_tm in |
| 558 |
let n = get_dim x_var in |
| 559 |
let partials = map (fun i -> gen_partial_poly i poly_tm) (1--n) in |
| 560 |
let diff_th = gen_diff_poly poly_tm in |
| 561 |
gen_lin_approx_poly_thm poly_tm diff_th partials;; |
| 562 |
|
| 563 |
|
| 564 |
let eval_lin_approx pp0 lin_approx_th = |
| 565 |
let poly_tm, _, _, _ = (dest_lin_approx o lhand o concl) lin_approx_th in |
| 566 |
let x_var, _ = dest_abs poly_tm in |
| 567 |
let n = get_dim x_var in |
| 568 |
let th0 = lin_approx_th in |
| 569 |
let th1 = (UNDISCH_ALL o REWRITE_RULE[GSYM IMP_IMP] o MATCH_MP iffRL) th0 in |
| 570 |
let build_eval int_hyp = |
| 571 |
let expr, b_var = dest_binary "interval_arith" int_hyp in |
| 572 |
(eval_constants pp0 o build_interval_fun) expr, b_var in |
| 573 |
let int_fs = map build_eval (hyp th1) in |
| 574 |
|
| 575 |
let rec split_rules i_list = |
| 576 |
match i_list with |
| 577 |
| [] -> ([], []) |
| 578 |
| ((i_fun, var_tm) :: es) -> |
| 579 |
let th_list, i_list' = split_rules es in |
| 580 |
match i_fun with |
| 581 |
| Int_const th -> (var_tm, th) :: th_list, i_list' |
| 582 |
| Int_var v -> (var_tm, INST[v, x_var_real] CONST_INTERVAL') :: th_list, i_list' |
| 583 |
| _ -> th_list, (var_tm, i_fun) :: i_list' in |
| 584 |
|
| 585 |
let const_th_list, i_list0 = split_rules int_fs in |
| 586 |
let th2 = itlist (fun (var_tm, th) th0 -> |
| 587 |
let b_tm = rand (concl th) in |
| 588 |
(MY_PROVE_HYP th o INST[b_tm, var_tm]) th0) const_th_list th1 in |
| 589 |
let v_list, i_list' = unzip i_list0 in |
| 590 |
let i_list = find_and_replace_all i_list' [] in |
| 591 |
fun pp vector_tm -> |
| 592 |
let x_vals = dest_vector vector_tm in |
| 593 |
if length x_vals <> n then failwith (sprintf "Wrong vector size; expected size: %d" n) |
| 594 |
else |
| 595 |
let x_ints = map mk_const_interval x_vals in |
| 596 |
let vars = map (fun i -> x_vars_array.(i)) (1--n) in |
| 597 |
let th3 = INST (zip x_vals vars) th2 in |
| 598 |
let i_vals = eval_interval_fun_list pp i_list (zip vars x_ints) in |
| 599 |
itlist2 (fun var_tm th th0 -> |
| 600 |
let b_tm = rand (concl th) in |
| 601 |
(MY_PROVE_HYP th o INST[b_tm, var_tm]) th0) v_list i_vals th3;; |
| 602 |
|
| 603 |
|
| 604 |
let eval_lin_approx_poly0 pp0 poly_tm = |
| 605 |
eval_lin_approx pp0 (gen_lin_approx_poly_thm0 poly_tm);; |
| 606 |
|
| 607 |
|
| 608 |
|
| 609 |
(*************************************) |
| 610 |
|
| 611 |
(* 1 <= i /\ i <= n <=> i = 1 \/ i = 2 \/ ... \/ i = n *) |
| 612 |
let i_int_array = |
| 613 |
let i_tm = `i:num` in |
| 614 |
let i_th0 = prove(`1 <= i /\ i <= SUC n <=> (1 <= i /\ i <= n) \/ i = SUC n`, ARITH_TAC) in |
| 615 |
let th1 = prove(`1 <= i /\ i <= 1 <=> i = 1`, ARITH_TAC) in |
| 616 |
let array = Array.make (max_dim + 1) th1 in |
| 617 |
let prove_next n = |
| 618 |
let n_tm = mk_small_numeral n in |
| 619 |
let prev_n = num_CONV n_tm in |
| 620 |
let tm = mk_conj (`1 <= i`, mk_binop le_op_num i_tm n_tm) in |
| 621 |
let th = REWRITE_CONV[prev_n; i_th0; array.(n - 1)] tm in |
| 622 |
array.(n) <- REWRITE_RULE[SYM prev_n; GSYM DISJ_ASSOC] th in |
| 623 |
let _ = map prove_next (2--max_dim) in |
| 624 |
array;; |
| 625 |
|
| 626 |
|
| 627 |
(* (!i. 1 <= i /\ i <= n ==> P i) <=> P 1 /\ P 2 /\ ... /\ P n *) |
| 628 |
let gen_in_interval = |
| 629 |
let th0 = prove(`(!i:num. (i = k \/ Q i) ==> P i) <=> (P k /\ (!i. Q i ==> P i))`, MESON_TAC[]) in |
| 630 |
let th1 = prove(`(!i:num. (i = k ==> P i)) <=> P k`, MESON_TAC[]) in |
| 631 |
fun n -> |
| 632 |
let n_tm = mk_small_numeral n and |
| 633 |
i_tm = `i:num` in |
| 634 |
let lhs1 = mk_conj (`1 <= i`, mk_binop le_op_num i_tm n_tm) in |
| 635 |
let lhs = mk_forall (i_tm, mk_imp (lhs1, `(P:num->bool) i`)) in |
| 636 |
REWRITE_CONV[i_int_array.(n); th0; th1] lhs;; |
| 637 |
|
| 638 |
|
| 639 |
let gen_second_bounded_eq_thm n = |
| 640 |
let ty, _, x_var, _, _, _, domain_var = get_types_and_vars n in |
| 641 |
let dd_vars = map (fun i -> map (fun j -> dd_vars_array.(j).(i)) (1--i)) (1--n) in |
| 642 |
let dd_bounds_list = mk_list (map (fun l -> mk_list (l, real_pair_ty)) dd_vars, real_pair_list_ty) in |
| 643 |
let th0 = (SPECL[domain_var; dd_bounds_list] o inst_first_type_var ty) second_bounded in |
| 644 |
let th1 = (CONV_RULE NUM_REDUCE_CONV o REWRITE_RULE[all_n]) th0 in |
| 645 |
th1;; |
| 646 |
|
| 647 |
|
| 648 |
let gen_second_bounded_poly_thm poly_tm partials2 = |
| 649 |
let x_var, _ = dest_abs poly_tm in |
| 650 |
let n = get_dim x_var in |
| 651 |
let partials2' = List.flatten partials2 in |
| 652 |
let second_th = (REWRITE_RULE partials2' o SPECL [poly_tm]) (gen_second_bounded_eq_thm n) in |
| 653 |
second_th;; |
| 654 |
|
| 655 |
|
| 656 |
let gen_second_bounded_poly_thm0 poly_tm = |
| 657 |
let x_var, _ = dest_abs poly_tm in |
| 658 |
let n = get_dim x_var in |
| 659 |
let partials = map (fun i -> gen_partial_poly i poly_tm) (1--n) in |
| 660 |
let get_partial i eq_th = |
| 661 |
let partial_i = gen_partial_poly i (rand (concl eq_th)) in |
| 662 |
let pi = (rator o lhand o concl) partial_i in |
| 663 |
REWRITE_RULE[GSYM partial2] (TRANS (AP_TERM pi eq_th) partial_i) in |
| 664 |
let partials2 = map (fun th, i -> map (fun j -> get_partial j th) (1--i)) (zip partials (1--n)) in |
| 665 |
gen_second_bounded_poly_thm poly_tm partials2;; |
| 666 |
|
| 667 |
(* let eq_th = TAUT `(P ==> Q /\ R) <=> ((P ==> Q) /\ (P ==> R))` in |
| 668 |
REWRITE_RULE[eq_th; FORALL_AND_THM; GSYM m_bounded_on_int] second_th;;*) |
| 669 |
|
| 670 |
|
| 671 |
(* eval_second_bounded *) |
| 672 |
let eval_second_bounded pp0 second_bounded_th = |
| 673 |
let poly_tm = (lhand o rator o lhand o concl) second_bounded_th in |
| 674 |
let th0 = second_bounded_th in |
| 675 |
let n = (get_dim o fst o dest_abs) poly_tm in |
| 676 |
let x_vector = mk_vector_list (map (fun i -> x_vars_array.(i)) (1--n)) and |
| 677 |
z_vector = mk_vector_list (map (fun i -> z_vars_array.(i)) (1--n)) in |
| 678 |
let _, _, _, _, _, _, domain_var = get_types_and_vars n in |
| 679 |
|
| 680 |
let th1 = INST[mk_pair (x_vector, z_vector), domain_var] th0 in |
| 681 |
let th2 = REWRITE_RULE[IN_INTERVAL; dimindex_array.(n)] th1 in |
| 682 |
let th3 = REWRITE_RULE[gen_in_interval n; GSYM interval_arith] th2 in |
| 683 |
let th4 = (REWRITE_RULE[CONJ_ACI] o REWRITE_RULE (Array.to_list comp_thms_array.(n))) th3 in |
| 684 |
let final_th0 = (UNDISCH_ALL o MATCH_MP iffRL) th4 in |
| 685 |
|
| 686 |
let x_var, h_tm = (dest_forall o hd o hyp) final_th0 in |
| 687 |
let _, h2 = dest_imp h_tm in |
| 688 |
let concl_ints = striplist dest_conj h2 in |
| 689 |
|
| 690 |
let i_funs = map (fun int -> |
| 691 |
let expr, var = dest_interval_arith int in |
| 692 |
(eval_constants pp0 o build_interval_fun) expr, var) concl_ints in |
| 693 |
|
| 694 |
let rec split_rules i_list = |
| 695 |
match i_list with |
| 696 |
| [] -> ([], []) |
| 697 |
| ((i_fun, var_tm) :: es) -> |
| 698 |
let th_list, i_list' = split_rules es in |
| 699 |
match i_fun with |
| 700 |
| Int_const th -> (var_tm, th) :: th_list, i_list' |
| 701 |
(* | Int_var v -> (var_tm, INST[v, x_var_real] CONST_INTERVAL') :: th_list, i_list' *) |
| 702 |
| _ -> th_list, (var_tm, i_fun) :: i_list' in |
| 703 |
|
| 704 |
let const_th_list, i_list0 = split_rules i_funs in |
| 705 |
let th5 = itlist (fun (var_tm, th) th0 -> |
| 706 |
let b_tm = rand (concl th) in |
| 707 |
(REWRITE_RULE[th] o INST[b_tm, var_tm]) th0) const_th_list (SYM th4) in |
| 708 |
let final_th = REWRITE_RULE[GSYM IMP_IMP] th5 in |
| 709 |
let v_list, i_list' = unzip i_list0 in |
| 710 |
let i_list = find_and_replace_all i_list' [] in |
| 711 |
|
| 712 |
fun pp x_vector_tm z_vector_tm -> |
| 713 |
let x_vals = dest_vector x_vector_tm and |
| 714 |
z_vals = dest_vector z_vector_tm in |
| 715 |
if length x_vals <> n || length z_vals <> n then |
| 716 |
failwith (sprintf "Wrong vector size; expected size: %d" n) |
| 717 |
else |
| 718 |
let x_vars = map (fun i -> x_vars_array.(i)) (1--n) and |
| 719 |
z_vars = map (fun i -> z_vars_array.(i)) (1--n) in |
| 720 |
|
| 721 |
let inst_th = (INST (zip x_vals x_vars) o INST (zip z_vals z_vars)) final_th in |
| 722 |
if (not o is_eq) (concl inst_th) then inst_th |
| 723 |
else |
| 724 |
let x_var, lhs = (dest_forall o lhand o concl) inst_th in |
| 725 |
let hs = (butlast o striplist dest_imp) lhs in |
| 726 |
let vars = map (rand o rator) hs in |
| 727 |
let int_vars = zip vars (map ASSUME hs) in |
| 728 |
|
| 729 |
let dd_ints = eval_interval_fun_list pp i_list int_vars in |
| 730 |
let inst_dd = map2 (fun var th -> (rand o concl) th, var) v_list dd_ints in |
| 731 |
let inst_th2 = INST inst_dd inst_th in |
| 732 |
|
| 733 |
let conj_th = end_itlist CONJ dd_ints in |
| 734 |
let lhs_th = GEN x_var (itlist DISCH hs conj_th) in |
| 735 |
EQ_MP inst_th2 lhs_th;; |
| 736 |
|
| 737 |
|
| 738 |
|
| 739 |
let eval_second_bounded_poly0 pp0 poly_tm = |
| 740 |
eval_second_bounded pp0 (gen_second_bounded_poly_thm0 poly_tm);; |
| 741 |
|
| 742 |
|
| 743 |
|
| 744 |
(*************************************) |
| 745 |
(* eval_m_taylor *) |
| 746 |
|
| 747 |
let eval_m_taylor pp0 diff2c_th lin_th second_th = |
| 748 |
let poly_tm = (rand o concl) diff2c_th in |
| 749 |
let n = (get_dim o fst o dest_abs) poly_tm in |
| 750 |
let eval_lin = eval_lin_approx pp0 lin_th and |
| 751 |
eval_second = eval_second_bounded pp0 second_th in |
| 752 |
|
| 753 |
let ty, _, x_var, f_var, y_var, w_var, domain_var = get_types_and_vars n in |
| 754 |
let th0 = (SPEC_ALL o inst_first_type_var ty) m_taylor_interval in |
| 755 |
let th1 = INST[poly_tm, f_var] th0 in |
| 756 |
let th2 = (UNDISCH_ALL o REWRITE_RULE[GSYM IMP_IMP] o MATCH_MP iffRL o REWRITE_RULE[diff2c_th]) th1 in |
| 757 |
|
| 758 |
fun p_lin p_second domain_th -> |
| 759 |
let domain_tm, y_tm, w_tm = dest_m_cell_domain (concl domain_th) in |
| 760 |
let x_tm, z_tm = dest_pair domain_tm in |
| 761 |
|
| 762 |
let lin_th = eval_lin p_lin y_tm and |
| 763 |
second_th = eval_second p_second x_tm z_tm in |
| 764 |
|
| 765 |
let _, _, f_bounds, df_bounds_list = dest_lin_approx (concl lin_th) in |
| 766 |
let dd_bounds_list = (rand o concl) second_th in |
| 767 |
let df_var = mk_var ("d_bounds_list", type_of df_bounds_list) and |
| 768 |
dd_var = mk_var ("dd_bounds_list", type_of dd_bounds_list) in |
| 769 |
|
| 770 |
(MY_PROVE_HYP domain_th o MY_PROVE_HYP lin_th o MY_PROVE_HYP second_th o |
| 771 |
INST[domain_tm, domain_var; y_tm, y_var; w_tm, w_var; |
| 772 |
f_bounds, f_bounds_var; df_bounds_list, df_var; dd_bounds_list, dd_var]) th2;; |
| 773 |
|
| 774 |
|
| 775 |
let eval_m_taylor_poly0 pp0 poly_tm = |
| 776 |
let diff2_th = gen_diff2c_domain_poly poly_tm in |
| 777 |
let x_var, _ = dest_abs poly_tm in |
| 778 |
let n = get_dim x_var in |
| 779 |
let partials = map (fun i -> gen_partial_poly i poly_tm) (1--n) in |
| 780 |
let get_partial i eq_th = |
| 781 |
let partial_i = gen_partial_poly i (rand (concl eq_th)) in |
| 782 |
let pi = (rator o lhand o concl) partial_i in |
| 783 |
REWRITE_RULE[GSYM partial2] (TRANS (AP_TERM pi eq_th) partial_i) in |
| 784 |
let partials2 = map2 (fun th i -> map (fun j -> get_partial j th) (1--i)) partials (1--n) in |
| 785 |
let second_th = gen_second_bounded_poly_thm poly_tm partials2 in |
| 786 |
let diff_th = gen_diff_poly poly_tm in |
| 787 |
let lin_th = gen_lin_approx_poly_thm poly_tm diff_th partials in |
| 788 |
eval_m_taylor pp0 diff2_th lin_th second_th;; |
| 789 |
|
| 790 |
|
| 791 |
|
| 792 |
(******************************************) |
| 793 |
(* mk_eval_function *) |
| 794 |
|
| 795 |
let mk_eval_function_eq pp0 eq_th = |
| 796 |
let expr_tm = (rand o concl) eq_th in |
| 797 |
let tm0 = `!x:real^N. x IN interval [domain] ==> interval_arith (f x) f_bounds` in |
| 798 |
let n = (get_dim o fst o dest_abs) expr_tm in |
| 799 |
let x_vector = mk_vector_list (map (fun i -> x_vars_array.(i)) (1--n)) and |
| 800 |
z_vector = mk_vector_list (map (fun i -> z_vars_array.(i)) (1--n)) in |
| 801 |
let ty, _, _, _, _, _, domain_var = get_types_and_vars n and |
| 802 |
f_var = mk_var ("f", type_of expr_tm) in |
| 803 |
let th1 = (REWRITE_CONV[IN_INTERVAL] o subst[mk_pair(x_vector,z_vector), domain_var] o inst[ty, nty]) tm0 in |
| 804 |
let th2 = REWRITE_RULE [dimindex_array.(n)] th1 in |
| 805 |
let th3 = REWRITE_RULE [gen_in_interval n; GSYM interval_arith] th2 in |
| 806 |
let th4 = (REWRITE_RULE[GSYM IMP_IMP; CONJ_ACI] o REWRITE_RULE (Array.to_list comp_thms_array.(n))) th3 in |
| 807 |
let final_th0 = (CONV_RULE ((RAND_CONV o ONCE_DEPTH_CONV) BETA_CONV) o INST[expr_tm, f_var]) th4 in |
| 808 |
let x_var, h_tm = (dest_forall o rand o concl) final_th0 in |
| 809 |
let f_tm = (fst o dest_interval_arith o last o striplist dest_imp) h_tm in |
| 810 |
let i_fun = (eval_constants pp0 o build_interval_fun) f_tm in |
| 811 |
let i_list = find_and_replace_all [i_fun] [] in |
| 812 |
let final_th = (PURE_REWRITE_RULE[SYM eq_th] o SYM) final_th0 in |
| 813 |
fun pp x_vector_tm z_vector_tm -> |
| 814 |
let x_vals = dest_vector x_vector_tm and |
| 815 |
z_vals = dest_vector z_vector_tm in |
| 816 |
if length x_vals <> n || length z_vals <> n then |
| 817 |
failwith (sprintf "Wrong vector size; expected size: %d" n) |
| 818 |
else |
| 819 |
let x_vars = map (fun i -> x_vars_array.(i)) (1--n) and |
| 820 |
z_vars = map (fun i -> z_vars_array.(i)) (1--n) in |
| 821 |
|
| 822 |
let inst_th = (INST (zip x_vals x_vars) o INST (zip z_vals z_vars)) final_th in |
| 823 |
let x_var, lhs = (dest_forall o lhand o concl) inst_th in |
| 824 |
let hs = (butlast o striplist dest_imp) lhs in |
| 825 |
let vars = map (rand o rator) hs in |
| 826 |
let int_vars = zip vars (map ASSUME hs) in |
| 827 |
let eval_th = hd (eval_interval_fun_list pp i_list int_vars) in |
| 828 |
let f_bounds = (rand o concl) eval_th in |
| 829 |
let inst_th2 = INST[f_bounds, f_bounds_var] inst_th in |
| 830 |
let lhs_th = GEN x_var (itlist DISCH hs eval_th) in |
| 831 |
EQ_MP inst_th2 lhs_th;; |
| 832 |
|
| 833 |
|
| 834 |
let mk_eval_function pp0 expr_tm = mk_eval_function_eq pp0 (REFL expr_tm);; |
| 835 |
|
| 836 |
|
| 837 |
|
| 838 |
(********************************) |
| 839 |
(* m_taylor_error *) |
| 840 |
|
| 841 |
(* Sum of the list elements *) |
| 842 |
let ITLIST2_EQ_SUM = prove(`!(f:A->B->real) l1 l2. LENGTH l1 <= LENGTH l2 ==> |
| 843 |
ITLIST2 (\x y z. f x y + z) l1 l2 (&0) = |
| 844 |
sum (1..(LENGTH l1)) (\i. f (EL (i - 1) l1) (EL (i - 1) l2))`, |
| 845 |
GEN_TAC THEN |
| 846 |
LIST_INDUCT_TAC THEN LIST_INDUCT_TAC THEN REWRITE_TAC[LENGTH; ITLIST2_DEF] THEN TRY ARITH_TAC THENL |
| 847 |
[ |
| 848 |
REWRITE_TAC[SUM_CLAUSES_NUMSEG; ARITH]; |
| 849 |
REWRITE_TAC[SUM_CLAUSES_NUMSEG; ARITH]; |
| 850 |
ALL_TAC |
| 851 |
] THEN |
| 852 |
REWRITE_TAC[leqSS] THEN DISCH_TAC THEN |
| 853 |
FIRST_X_ASSUM (MP_TAC o SPEC `t':(B)list`) THEN ASM_REWRITE_TAC[] THEN |
| 854 |
DISCH_THEN (fun th -> REWRITE_TAC[TL; th]) THEN |
| 855 |
REWRITE_TAC[GSYM add1n] THEN |
| 856 |
new_rewrite [] [] SUM_ADD_SPLIT THEN REWRITE_TAC[ARITH] THEN |
| 857 |
REWRITE_TAC[TWO; add1n; SUM_SING_NUMSEG; subnn; EL; HD] THEN |
| 858 |
REWRITE_TAC[GSYM addn1; SUM_OFFSET; REAL_EQ_ADD_LCANCEL] THEN |
| 859 |
MATCH_MP_TAC SUM_EQ THEN move ["i"] THEN REWRITE_TAC[IN_NUMSEG] THEN DISCH_TAC THEN |
| 860 |
ASM_SIMP_TAC[ARITH_RULE `1 <= i ==> (i + 1) - 1 = SUC (i - 1)`; EL; TL]);; |
| 861 |
|
| 862 |
|
| 863 |
let interval_arith_abs_le = prove(`!x int y. interval_arith x int ==> iabs int <= y ==> abs x <= y`, |
| 864 |
GEN_TAC THEN case THEN REWRITE_TAC[interval_arith; IABS'] THEN REAL_ARITH_TAC);; |
| 865 |
|
| 866 |
|
| 867 |
let ALL_N_ALL2 = prove(`!P (l:(A)list) i0. |
| 868 |
(all_n i0 l P <=> if l = [] then T else ALL2 P (l_seq i0 ((i0 + LENGTH l) - 1)) l)`, |
| 869 |
GEN_TAC THEN LIST_INDUCT_TAC THEN GEN_TAC THEN REWRITE_TAC[all_n; NOT_CONS_NIL] THEN |
| 870 |
new_rewrite [] [] L_SEQ_CONS THEN REWRITE_TAC[LENGTH; ALL2] THEN TRY ARITH_TAC THEN |
| 871 |
FIRST_X_ASSUM (new_rewrite [] []) THEN TRY ARITH_TAC THEN |
| 872 |
REWRITE_TAC[addSn; addnS; addn1] THEN |
| 873 |
SPEC_TAC (`t:(A)list`, `t:(A)list`) THEN case THEN SIMP_TAC[NOT_CONS_NIL] THEN |
| 874 |
REWRITE_TAC[LENGTH; addn0] THEN |
| 875 |
MP_TAC (SPECL [`SUC i0`; `SUC i0 - 1`] L_SEQ_NIL) THEN |
| 876 |
REWRITE_TAC[ARITH_RULE `SUC i0 - 1 < SUC i0`] THEN DISCH_THEN (fun th -> REWRITE_TAC[th; ALL2]));; |
| 877 |
|
| 878 |
|
| 879 |
let ALL_N_EL = prove(`!P (l:(A)list) i0. all_n i0 l P <=> (!i. i < LENGTH l ==> P (i0 + i) (EL i l))`, |
| 880 |
REPEAT GEN_TAC THEN REWRITE_TAC[ALL_N_ALL2] THEN |
| 881 |
SPEC_TAC (`l:(A)list`, `l:(A)list`) THEN case THEN SIMP_TAC[NOT_CONS_NIL; LENGTH; ltn0] THEN |
| 882 |
REPEAT GEN_TAC THEN |
| 883 |
new_rewrite [] [] ALL2_ALL_ZIP THENL |
| 884 |
[ |
| 885 |
REWRITE_TAC[LENGTH_L_SEQ; LENGTH] THEN ARITH_TAC; |
| 886 |
ALL_TAC |
| 887 |
] THEN |
| 888 |
REWRITE_TAC[GSYM ALL_EL] THEN |
| 889 |
new_rewrite [] [] LENGTH_ZIP THENL |
| 890 |
[ |
| 891 |
REWRITE_TAC[LENGTH_L_SEQ; LENGTH] THEN ARITH_TAC; |
| 892 |
ALL_TAC |
| 893 |
] THEN |
| 894 |
REWRITE_TAC[LENGTH_L_SEQ; ARITH_RULE `((i0 + SUC a) - 1 + 1) - i0 = SUC a`] THEN |
| 895 |
EQ_TAC THEN REPEAT STRIP_TAC THENL |
| 896 |
[ |
| 897 |
FIRST_X_ASSUM (MP_TAC o SPEC `i:num`) THEN ASM_REWRITE_TAC[] THEN |
| 898 |
new_rewrite [] [] EL_ZIP THENL |
| 899 |
[ |
| 900 |
REWRITE_TAC[LENGTH_L_SEQ; LENGTH] THEN ASM_ARITH_TAC; |
| 901 |
ALL_TAC |
| 902 |
] THEN |
| 903 |
REWRITE_TAC[] THEN new_rewrite [] [] EL_L_SEQ THEN ASM_ARITH_TAC; |
| 904 |
ALL_TAC |
| 905 |
] THEN |
| 906 |
new_rewrite [] [] EL_ZIP THENL |
| 907 |
[ |
| 908 |
REWRITE_TAC[LENGTH_L_SEQ; LENGTH] THEN ASM_ARITH_TAC; |
| 909 |
ALL_TAC |
| 910 |
] THEN |
| 911 |
REWRITE_TAC[] THEN new_rewrite [] [] EL_L_SEQ THEN TRY ASM_ARITH_TAC THEN |
| 912 |
FIRST_X_ASSUM MATCH_MP_TAC THEN ASM_REWRITE_TAC[]);; |
| 913 |
|
| 914 |
|
| 915 |
let M_TAYLOR_ERROR_ITLIST2 = prove(`!f domain y w dd_bounds_list error. |
| 916 |
m_cell_domain domain y (vector w) ==> |
| 917 |
diff2c_domain domain f ==> |
| 918 |
second_bounded (f:real^N->real) domain dd_bounds_list ==> |
| 919 |
LENGTH w = dimindex (:N) ==> |
| 920 |
LENGTH dd_bounds_list = dimindex (:N) ==> |
| 921 |
all_n 1 dd_bounds_list (\i list. LENGTH list = i) ==> |
| 922 |
ITLIST2 (\list x z. x * (x * iabs (LAST list) |
| 923 |
+ &2 * ITLIST2 (\a b c. b * iabs a + c) (BUTLAST list) w (&0)) + z) |
| 924 |
dd_bounds_list w (&0) <= error ==> |
| 925 |
m_taylor_error f domain (vector w) error`, |
| 926 |
REPEAT GEN_TAC THEN REWRITE_TAC[second_bounded] THEN |
| 927 |
set_tac "s" `ITLIST2 _1 _2 _3 _4` THEN |
| 928 |
move ["domain"; "d2f"; "second"; "lw"; "ldd"; "ldd_all"; "s_le"] THEN |
| 929 |
ASM_SIMP_TAC[m_taylor_error_eq] THEN move ["x"; "x_in"] THEN |
| 930 |
SUBGOAL_THEN `!i. i IN 1..dimindex (:N) ==> &0 <= EL (i - 1) w` (LABEL_TAC "w_ge0") THENL |
| 931 |
[ |
| 932 |
GEN_TAC THEN DISCH_TAC THEN REMOVE_THEN "domain" MP_TAC THEN new_rewrite [] [] pair_eq THEN |
| 933 |
REWRITE_TAC[m_cell_domain] THEN |
| 934 |
DISCH_THEN (MP_TAC o SPEC `i:num`) THEN ASM_REWRITE_TAC[] THEN |
| 935 |
ASM_SIMP_TAC[VECTOR_COMPONENT] THEN REAL_ARITH_TAC; |
| 936 |
ALL_TAC |
| 937 |
] THEN |
| 938 |
MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `s:real` THEN ASM_REWRITE_TAC[] THEN |
| 939 |
EXPAND_TAC "s" THEN |
| 940 |
new_rewrite [] [] ITLIST2_EQ_SUM THEN ASM_REWRITE_TAC[LE_REFL] THEN |
| 941 |
MATCH_MP_TAC SUM_LE THEN REWRITE_TAC[FINITE_NUMSEG] THEN |
| 942 |
move ["i"; "i_in"] THEN ASM_SIMP_TAC[VECTOR_COMPONENT] THEN |
| 943 |
USE_THEN "i_in" (ASSUME_TAC o REWRITE_RULE[IN_NUMSEG]) THEN |
| 944 |
MATCH_MP_TAC REAL_LE_LMUL THEN ASM_SIMP_TAC[] THEN |
| 945 |
SUBGOAL_THEN `LENGTH (EL (i - 1) dd_bounds_list:(real#real)list) = i` (LABEL_TAC "len_i") THENL |
| 946 |
[ |
| 947 |
REMOVE_THEN "ldd_all" MP_TAC THEN |
| 948 |
REWRITE_TAC[ALL_N_EL] THEN DISCH_THEN (MP_TAC o SPEC `i - 1`) THEN |
| 949 |
ANTS_TAC THENL |
| 950 |
[ |
| 951 |
ASM_REWRITE_TAC[] THEN POP_ASSUM MP_TAC THEN ARITH_TAC; |
| 952 |
ALL_TAC |
| 953 |
] THEN |
| 954 |
DISCH_THEN (fun th -> REWRITE_TAC[th]) THEN POP_ASSUM MP_TAC THEN ARITH_TAC; |
| 955 |
ALL_TAC |
| 956 |
] THEN |
| 957 |
new_rewrite [] [] ITLIST2_EQ_SUM THEN ASM_REWRITE_TAC[] THENL |
| 958 |
[ |
| 959 |
REWRITE_TAC[LENGTH_BUTLAST] THEN POP_ASSUM MP_TAC THEN POP_ASSUM MP_TAC THEN ARITH_TAC; |
| 960 |
ALL_TAC |
| 961 |
] THEN |
| 962 |
MATCH_MP_TAC REAL_LE_ADD2 THEN CONJ_TAC THENL |
| 963 |
[ |
| 964 |
new_rewrite [] [] LAST_EL THENL |
| 965 |
[ |
| 966 |
ASM_REWRITE_TAC[GSYM LENGTH_EQ_NIL] THEN |
| 967 |
REMOVE_THEN "i_in" MP_TAC THEN REWRITE_TAC[IN_NUMSEG] THEN ARITH_TAC; |
| 968 |
ALL_TAC |
| 969 |
] THEN |
| 970 |
MATCH_MP_TAC REAL_LE_LMUL THEN ASM_SIMP_TAC[] THEN |
| 971 |
FIRST_X_ASSUM (MP_TAC o SPEC `x:real^N`) THEN ASM_REWRITE_TAC[ALL_N_EL] THEN |
| 972 |
DISCH_THEN (MP_TAC o SPEC `i - 1`) THEN |
| 973 |
ANTS_TAC THENL |
| 974 |
[ |
| 975 |
REMOVE_THEN "i_in" MP_TAC THEN REWRITE_TAC[IN_NUMSEG] THEN ARITH_TAC; |
| 976 |
ALL_TAC |
| 977 |
] THEN |
| 978 |
DISCH_THEN (MP_TAC o SPEC `i - 1`) THEN ANTS_TAC THENL |
| 979 |
[ |
| 980 |
UNDISCH_TAC `1 <= i /\ i <= dimindex (:N)` THEN ASM_REWRITE_TAC[] THEN ARITH_TAC; |
| 981 |
ALL_TAC |
| 982 |
] THEN |
| 983 |
SUBGOAL_THEN `1 + i - 1 = i /\ 1 + i - 1 = i` (fun th -> REWRITE_TAC[th]) THENL |
| 984 |
[ |
| 985 |
REPLICATE_TAC 3 (POP_ASSUM MP_TAC) THEN ARITH_TAC; |
| 986 |
ALL_TAC |
| 987 |
] THEN |
| 988 |
REWRITE_TAC[partial2] THEN |
| 989 |
DISCH_THEN (MP_TAC o MATCH_MP interval_arith_abs_le) THEN |
| 990 |
DISCH_THEN MATCH_MP_TAC THEN REWRITE_TAC[REAL_LE_REFL]; |
| 991 |
ALL_TAC |
| 992 |
] THEN |
| 993 |
MATCH_MP_TAC REAL_LE_LMUL THEN CONJ_TAC THENL [ REAL_ARITH_TAC; ALL_TAC ] THEN |
| 994 |
ASM_REWRITE_TAC[LENGTH_BUTLAST] THEN |
| 995 |
MATCH_MP_TAC SUM_LE THEN REWRITE_TAC[FINITE_NUMSEG] THEN |
| 996 |
move ["j"; "j_in"] THEN |
| 997 |
SUBGOAL_THEN `j IN 1..dimindex (:N)` (LABEL_TAC "j_in2") THENL |
| 998 |
[ |
| 999 |
REMOVE_THEN "i_in" MP_TAC THEN REMOVE_THEN "j_in" MP_TAC THEN |
| 1000 |
REWRITE_TAC[IN_NUMSEG] THEN ARITH_TAC; |
| 1001 |
ALL_TAC |
| 1002 |
] THEN |
| 1003 |
ASM_SIMP_TAC[VECTOR_COMPONENT] THEN |
| 1004 |
USE_THEN "j_in" (ASSUME_TAC o REWRITE_RULE[IN_NUMSEG]) THEN |
| 1005 |
MATCH_MP_TAC REAL_LE_LMUL THEN ASM_SIMP_TAC[] THEN |
| 1006 |
FIRST_X_ASSUM (MP_TAC o SPEC `x:real^N`) THEN ASM_REWRITE_TAC[ALL_N_EL] THEN |
| 1007 |
DISCH_THEN (MP_TAC o SPEC `i - 1`) THEN ANTS_TAC THENL |
| 1008 |
[ |
| 1009 |
REMOVE_THEN "i_in" MP_TAC THEN REWRITE_TAC[IN_NUMSEG] THEN ARITH_TAC; |
| 1010 |
ALL_TAC |
| 1011 |
] THEN |
| 1012 |
DISCH_THEN (MP_TAC o SPEC `j - 1`) THEN ANTS_TAC THENL |
| 1013 |
[ |
| 1014 |
ASM_REWRITE_TAC[] THEN POP_ASSUM MP_TAC THEN ARITH_TAC; |
| 1015 |
ALL_TAC |
| 1016 |
] THEN |
| 1017 |
SUBGOAL_THEN `1 + j - 1 = j /\ 1 + i - 1 = i` (fun th -> REWRITE_TAC[th]) THENL |
| 1018 |
[ |
| 1019 |
REPLICATE_TAC 3 (POP_ASSUM MP_TAC) THEN ARITH_TAC; |
| 1020 |
ALL_TAC |
| 1021 |
] THEN |
| 1022 |
REWRITE_TAC[partial2] THEN |
| 1023 |
DISCH_THEN (MP_TAC o MATCH_MP interval_arith_abs_le) THEN |
| 1024 |
DISCH_THEN MATCH_MP_TAC THEN |
| 1025 |
new_rewrite [] [] EL_BUTLAST THENL |
| 1026 |
[ |
| 1027 |
ASM_REWRITE_TAC[] THEN REMOVE_THEN "j_in" MP_TAC THEN REMOVE_THEN "i_in" MP_TAC THEN |
| 1028 |
REWRITE_TAC[IN_NUMSEG] THEN ARITH_TAC; |
| 1029 |
ALL_TAC |
| 1030 |
] THEN |
| 1031 |
REWRITE_TAC[REAL_LE_REFL]);; |
| 1032 |
|
| 1033 |
|
| 1034 |
let M_TAYLOR_ERROR_ITLIST2_ALT = prove(`!f domain y w f_lo f_hi d_bounds_list dd_bounds_list error. |
| 1035 |
m_taylor_interval f domain y (vector w:real^N) (f_lo, f_hi) d_bounds_list dd_bounds_list ==> |
| 1036 |
LENGTH w = dimindex (:N) ==> |
| 1037 |
LENGTH dd_bounds_list = dimindex (:N) ==> |
| 1038 |
all_n 1 dd_bounds_list (\i list. LENGTH list = i) ==> |
| 1039 |
ITLIST2 (\list x z. x * (x * iabs (LAST list) |
| 1040 |
+ &2 * ITLIST2 (\a b c. b * iabs a + c) (BUTLAST list) w (&0)) + z) |
| 1041 |
dd_bounds_list w (&0) <= error ==> |
| 1042 |
m_taylor_error f domain (vector w) error`, |
| 1043 |
REWRITE_TAC[m_taylor_interval] THEN REPEAT STRIP_TAC THEN |
| 1044 |
MP_TAC (SPEC_ALL M_TAYLOR_ERROR_ITLIST2) THEN ASM_REWRITE_TAC[]);; |
| 1045 |
|
| 1046 |
|
| 1047 |
|
| 1048 |
(****************************) |
| 1049 |
|
| 1050 |
let M_TAYLOR_INTERVAL' = MY_RULE m_taylor_interval;; |
| 1051 |
|
| 1052 |
let dest_m_taylor m_taylor_tm = |
| 1053 |
let ltm1, dd_bounds_list = dest_comb m_taylor_tm in |
| 1054 |
let ltm2, d_bounds_list = dest_comb ltm1 in |
| 1055 |
let ltm3, f_bounds = dest_comb ltm2 in |
| 1056 |
let ltm4, w = dest_comb ltm3 in |
| 1057 |
let ltm5, y = dest_comb ltm4 in |
| 1058 |
let ltm6, domain = dest_comb ltm5 in |
| 1059 |
rand ltm6, domain, y, w, f_bounds, d_bounds_list, dd_bounds_list;; |
| 1060 |
|
| 1061 |
let dest_m_taylor_thms n = |
| 1062 |
let ty, xty, x_var, f_var, y_var, w_var, domain_var = get_types_and_vars n in |
| 1063 |
fun m_taylor_th -> |
| 1064 |
let f, domain, y, w, f_bounds, d_bounds_list, dd_bounds_list = dest_m_taylor (concl m_taylor_th) in |
| 1065 |
let th0 = (INST[f, f_var; domain, domain_var; y, y_var; w, w_var; f_bounds, f_bounds_var; |
| 1066 |
d_bounds_list, d_bounds_list_var; dd_bounds_list, dd_bounds_list_var] o |
| 1067 |
inst_first_type_var ty) M_TAYLOR_INTERVAL' in |
| 1068 |
let th1 = EQ_MP th0 m_taylor_th in |
| 1069 |
match (CONJUNCTS th1) with |
| 1070 |
| [domain_th; d2_th; lin_th; second_th] -> |
| 1071 |
domain_th, d2_th, lin_th, second_th |
| 1072 |
| _ -> failwith "dest_m_taylor_thms";; |
| 1073 |
|
| 1074 |
|
| 1075 |
(**********************) |
| 1076 |
|
| 1077 |
(* bound *) |
| 1078 |
let M_TAYLOR_BOUND' = |
| 1079 |
prove(`m_taylor_interval f domain y (vector w:real^N) (f_lo, f_hi) d_bounds_list dd_bounds_list /\ |
| 1080 |
m_taylor_error f domain (vector w) error /\ |
| 1081 |
ITLIST2 (\a b c. b * iabs a + c) d_bounds_list w (&0) <= b /\ |
| 1082 |
b + inv(&2) * error <= a /\ |
| 1083 |
lo <= f_lo - a /\ |
| 1084 |
f_hi + a <= hi /\ |
| 1085 |
LENGTH w = dimindex (:N) /\ LENGTH d_bounds_list = dimindex (:N) ==> |
| 1086 |
(!x. x IN interval [domain] ==> interval_arith (f x) (lo, hi))`, |
| 1087 |
REWRITE_TAC[GSYM m_bounded_on_int; m_taylor_interval; m_lin_approx; ALL_N_EL] THEN |
| 1088 |
set_tac "s" `ITLIST2 _1 _2 _3 _4` THEN STRIP_TAC THEN |
| 1089 |
SUBGOAL_THEN `diff2_domain domain (f:real^N->real)` ASSUME_TAC THENL |
| 1090 |
[ |
| 1091 |
UNDISCH_TAC `diff2c_domain domain (f:real^N->real)` THEN |
| 1092 |
SIMP_TAC[diff2_domain; diff2c_domain; diff2c]; |
| 1093 |
ALL_TAC |
| 1094 |
] THEN |
| 1095 |
apply_tac m_taylor_bounds THEN |
| 1096 |
MAP_EVERY EXISTS_TAC [`y:real^N`; `vector w:real^N`; `error:real`; `f_lo:real`; `f_hi:real`; `a:real`] THEN |
| 1097 |
ASM_REWRITE_TAC[] THEN |
| 1098 |
MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `b + inv (&2) * error` THEN ASM_REWRITE_TAC[] THEN |
| 1099 |
REWRITE_TAC[real_div; REAL_MUL_AC] THEN |
| 1100 |
MATCH_MP_TAC REAL_LE_ADD2 THEN REWRITE_TAC[REAL_LE_REFL] THEN |
| 1101 |
MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `s:real` THEN ASM_REWRITE_TAC[] THEN |
| 1102 |
EXPAND_TAC "s" THEN new_rewrite [] [] ITLIST2_EQ_SUM THEN ASM_REWRITE_TAC[LE_REFL] THEN |
| 1103 |
MATCH_MP_TAC SUM_LE THEN REWRITE_TAC[FINITE_NUMSEG] THEN REPEAT STRIP_TAC THEN |
| 1104 |
MATCH_MP_TAC REAL_LE_MUL2 THEN ASM_SIMP_TAC[VECTOR_COMPONENT; REAL_LE_REFL; REAL_ABS_POS] THEN |
| 1105 |
CONJ_TAC THENL |
| 1106 |
[ |
| 1107 |
UNDISCH_TAC `m_cell_domain domain (y:real^N) (vector w)` THEN |
| 1108 |
new_rewrite [] [] pair_eq THEN REWRITE_TAC[m_cell_domain] THEN |
| 1109 |
DISCH_THEN (MP_TAC o SPEC `x:num`) THEN ASM_REWRITE_TAC[] THEN |
| 1110 |
ASM_SIMP_TAC[VECTOR_COMPONENT] THEN REAL_ARITH_TAC; |
| 1111 |
ALL_TAC |
| 1112 |
] THEN |
| 1113 |
FIRST_X_ASSUM (MP_TAC o SPEC `x - 1`) THEN |
| 1114 |
ANTS_TAC THENL |
| 1115 |
[ |
| 1116 |
POP_ASSUM MP_TAC THEN ASM_REWRITE_TAC[IN_NUMSEG] THEN ARITH_TAC; |
| 1117 |
ALL_TAC |
| 1118 |
] THEN |
| 1119 |
DISCH_THEN (MP_TAC o MATCH_MP interval_arith_abs_le) THEN |
| 1120 |
SUBGOAL_THEN `1 + x - 1 = x` (fun th -> REWRITE_TAC[th]) THENL |
| 1121 |
[ |
| 1122 |
POP_ASSUM MP_TAC THEN REWRITE_TAC[IN_NUMSEG] THEN ARITH_TAC; |
| 1123 |
ALL_TAC |
| 1124 |
] THEN |
| 1125 |
DISCH_THEN MATCH_MP_TAC THEN REWRITE_TAC[REAL_LE_REFL]);; |
| 1126 |
|
| 1127 |
|
| 1128 |
(* upper *) |
| 1129 |
let M_TAYLOR_UPPER_BOUND' = prove(`m_taylor_interval f domain y (vector w) (f_lo, f_hi) |
| 1130 |
d_bounds_list dd_bounds_list /\ |
| 1131 |
m_taylor_error f domain (vector w:real^N) error /\ |
| 1132 |
ITLIST2 (\a b c. b * iabs a + c) d_bounds_list w (&0) <= b /\ |
| 1133 |
b + inv(&2) * error <= a /\ |
| 1134 |
f_hi + a <= hi /\ |
| 1135 |
LENGTH w = dimindex (:N) /\ LENGTH d_bounds_list = dimindex (:N) ==> |
| 1136 |
(!p. p IN interval [domain] ==> f p <= hi)`, |
| 1137 |
STRIP_TAC THEN |
| 1138 |
MP_TAC (INST[`f_lo - a:real`, `lo:real`] M_TAYLOR_BOUND') THEN |
| 1139 |
ASM_SIMP_TAC[interval_arith; REAL_LE_REFL]);; |
| 1140 |
|
| 1141 |
|
| 1142 |
(* lower *) |
| 1143 |
let M_TAYLOR_LOWER_BOUND' = prove(`m_taylor_interval f domain y (vector w:real^N) (f_lo, f_hi) |
| 1144 |
d_bounds_list dd_bounds_list /\ |
| 1145 |
m_taylor_error f domain (vector w) error /\ |
| 1146 |
ITLIST2 (\a b c. b * iabs a + c) d_bounds_list w (&0) <= b /\ |
| 1147 |
b + inv(&2) * error <= a /\ |
| 1148 |
lo <= f_lo - a /\ |
| 1149 |
LENGTH w = dimindex (:N) /\ LENGTH d_bounds_list = dimindex (:N) ==> |
| 1150 |
(!p. p IN interval [domain] ==> lo <= f p)`, |
| 1151 |
STRIP_TAC THEN |
| 1152 |
MP_TAC (INST[`f_hi + a:real`, `hi:real`] M_TAYLOR_BOUND') THEN |
| 1153 |
ASM_SIMP_TAC[interval_arith; REAL_LE_REFL]);; |
| 1154 |
|
| 1155 |
|
| 1156 |
|
| 1157 |
(* arrays *) |
| 1158 |
let gen_taylor_bound_th bound_th n = |
| 1159 |
let th0 = (DISCH_ALL o MY_RULE o REWRITE_RULE[MY_RULE M_TAYLOR_ERROR_ITLIST2_ALT]) bound_th in |
| 1160 |
let ns = 1--n in |
| 1161 |
let mk_list_hd l = mk_list (l, type_of (hd l)) in |
| 1162 |
let w_list = mk_list_hd (map (fun i -> w_vars_array.(i)) ns) in |
| 1163 |
let d_bounds_list = mk_list_hd (map (fun i -> df_vars_array.(i)) ns) in |
| 1164 |
let dd_bounds_list = mk_list_hd (map (fun i -> mk_list_hd (map (fun j -> dd_vars_array.(i).(j)) (1--i))) ns) in |
| 1165 |
let th1 = (INST[w_list, w_var_real_list; d_bounds_list, d_bounds_list_var; |
| 1166 |
dd_bounds_list, dd_bounds_list_var] o INST_TYPE[n_type_array.(n), nty]) th0 in |
| 1167 |
let th2 = REWRITE_RULE[LAST; NOT_CONS_NIL; BUTLAST; all_n; ITLIST2_DEF; LENGTH; ARITH; dimindex_array.(n)] th1 in |
| 1168 |
let th3 = REWRITE_RULE[HD; TL; REAL_MUL_RZERO; REAL_ADD_RID; GSYM error_mul_f2] th2 in |
| 1169 |
(MY_RULE o REWRITE_RULE[float_inv2_th; SYM float2_eq]) th3;; |
| 1170 |
|
| 1171 |
|
| 1172 |
let m_taylor_upper_array = Array.init (max_dim + 1) |
| 1173 |
(fun i -> if i < 1 then TRUTH else gen_taylor_bound_th M_TAYLOR_UPPER_BOUND' i);; |
| 1174 |
|
| 1175 |
let m_taylor_lower_array = Array.init (max_dim + 1) |
| 1176 |
(fun i -> if i < 1 then TRUTH else gen_taylor_bound_th M_TAYLOR_LOWER_BOUND' i);; |
| 1177 |
|
| 1178 |
let m_taylor_bound_array = Array.init (max_dim + 1) |
| 1179 |
(fun i -> if i < 1 then TRUTH else gen_taylor_bound_th M_TAYLOR_BOUND' i);; |
| 1180 |
|
| 1181 |
|
| 1182 |
(***************************) |
| 1183 |
(* eval_m_taylor_bounds0 *) |
| 1184 |
|
| 1185 |
let eval_m_taylor_bounds0 mode n pp m_taylor_th = |
| 1186 |
let bound_th = |
| 1187 |
if mode = "upper" then |
| 1188 |
m_taylor_upper_array.(n) |
| 1189 |
else if mode = "bound" then |
| 1190 |
m_taylor_bound_array.(n) |
| 1191 |
else |
| 1192 |
m_taylor_lower_array.(n) in |
| 1193 |
|
| 1194 |
let f_tm, domain_tm, y_tm, w_tm, f_bounds, d_bounds_list, dd_bounds_list = dest_m_taylor (concl m_taylor_th) in |
| 1195 |
let f_lo, f_hi = dest_pair f_bounds and |
| 1196 |
ws = dest_list (rand w_tm) and |
| 1197 |
dfs = dest_list d_bounds_list and |
| 1198 |
dds = map dest_list (dest_list dd_bounds_list) in |
| 1199 |
let ns = 1--n in |
| 1200 |
let df_vars = map (fun i -> df_vars_array.(i)) ns and |
| 1201 |
dd_vars = map (fun i -> map (fun j -> dd_vars_array.(i).(j)) (1--i)) ns and |
| 1202 |
w_vars = map (fun i -> w_vars_array.(i)) ns and |
| 1203 |
y_var = mk_var ("y", type_of y_tm) and |
| 1204 |
f_var = mk_var ("f", type_of f_tm) and |
| 1205 |
domain_var = mk_var ("domain", type_of domain_tm) in |
| 1206 |
|
| 1207 |
(* sum of first partials *) |
| 1208 |
let d_th = |
| 1209 |
let mul_wd = map2 (error_mul_f2_le_conv2 pp) ws dfs in |
| 1210 |
end_itlist (add_ineq_hi pp) mul_wd in |
| 1211 |
|
| 1212 |
let b_tm = (rand o concl) d_th in |
| 1213 |
|
| 1214 |
(* sum of second partials *) |
| 1215 |
let dd_th = |
| 1216 |
let ( * ), ( + ) = mul_ineq_pos_const_hi pp, add_ineq_hi pp in |
| 1217 |
let mul_wdd = map2 (fun list i -> my_map2 (error_mul_f2_le_conv2 pp) ws list) dds ns in |
| 1218 |
let sums1 = map (end_itlist ( + ) o butlast) (tl mul_wdd) in |
| 1219 |
let sums2 = (hd o hd) mul_wdd :: map2 (fun list th1 -> last list + two_float * th1) (tl mul_wdd) sums1 in |
| 1220 |
let sums = map2 ( * ) ws sums2 in |
| 1221 |
end_itlist ( + ) sums in |
| 1222 |
|
| 1223 |
let error_tm = (rand o concl) dd_th in |
| 1224 |
|
| 1225 |
(* additional inequalities *) |
| 1226 |
let ineq1_th = |
| 1227 |
let ( * ), ( + ) = float_mul_hi pp, add_ineq_hi pp in |
| 1228 |
mk_refl_ineq b_tm + float_inv2 * error_tm in |
| 1229 |
|
| 1230 |
let a_tm = (rand o concl) ineq1_th in |
| 1231 |
|
| 1232 |
let prove_ineq2, bounds_inst = |
| 1233 |
if mode = "upper" then |
| 1234 |
let ineq2 = float_add_hi pp f_hi a_tm in |
| 1235 |
MY_PROVE_HYP ineq2, [(rand o concl) ineq2, hi_var_real] |
| 1236 |
else if mode = "bound" then |
| 1237 |
let ineq2 = float_add_hi pp f_hi a_tm in |
| 1238 |
let ineq3 = float_sub_lo pp f_lo a_tm in |
| 1239 |
MY_PROVE_HYP ineq2 o MY_PROVE_HYP ineq3, |
| 1240 |
[(rand o concl) ineq2, hi_var_real; (lhand o concl) ineq3, lo_var_real] |
| 1241 |
else |
| 1242 |
let ineq2 = float_sub_lo pp f_lo a_tm in |
| 1243 |
MY_PROVE_HYP ineq2, [(lhand o concl) ineq2, lo_var_real] in |
| 1244 |
|
| 1245 |
(* final step *) |
| 1246 |
let inst_list = |
| 1247 |
let inst1 = zip dfs df_vars in |
| 1248 |
let inst2 = zip (List.flatten dds) (List.flatten dd_vars) in |
| 1249 |
let inst3 = zip ws w_vars in |
| 1250 |
inst1 @ inst2 @ inst3 in |
| 1251 |
|
| 1252 |
(MY_PROVE_HYP m_taylor_th o MY_PROVE_HYP dd_th o MY_PROVE_HYP d_th o |
| 1253 |
MY_PROVE_HYP ineq1_th o prove_ineq2 o |
| 1254 |
INST ([f_hi, f_hi_var; f_lo, f_lo_var; error_tm, error_var; |
| 1255 |
a_tm, a_var_real; b_tm, b_var_real; |
| 1256 |
y_tm, y_var; domain_tm, domain_var; |
| 1257 |
f_tm, f_var] @ bounds_inst @ inst_list)) bound_th;; |
| 1258 |
|
| 1259 |
|
| 1260 |
(* upper *) |
| 1261 |
let eval_m_taylor_upper_bound = eval_m_taylor_bounds0 "upper";; |
| 1262 |
|
| 1263 |
(* lower *) |
| 1264 |
let eval_m_taylor_lower_bound = eval_m_taylor_bounds0 "lower";; |
| 1265 |
|
| 1266 |
(* bound *) |
| 1267 |
let eval_m_taylor_bound = eval_m_taylor_bounds0 "bound";; |
| 1268 |
|
| 1269 |
|
| 1270 |
|
| 1271 |
|
| 1272 |
(******************************) |
| 1273 |
(* taylor_upper_partial_bound *) |
| 1274 |
(* taylor_lower_partial_bound *) |
| 1275 |
|
| 1276 |
|
| 1277 |
(* bound *) |
| 1278 |
let M_TAYLOR_PARTIAL_BOUND' = |
| 1279 |
prove(`m_taylor_interval f domain (y:real^N) (vector w) f_bounds d_bounds_list dd_bounds_list /\ |
| 1280 |
i IN 1..dimindex (:N) /\ |
| 1281 |
EL (i - 1) d_bounds_list = (df_lo, df_hi) /\ |
| 1282 |
(!x. x IN interval [domain] ==> all_n 1 dd_list |
| 1283 |
(\j int. interval_arith (if j <= i then partial2 j i f x else partial2 i j f x) int)) /\ |
| 1284 |
LENGTH dd_list = dimindex (:N) /\ |
| 1285 |
LENGTH d_bounds_list = dimindex (:N) /\ |
| 1286 |
LENGTH w = dimindex (:N) /\ |
| 1287 |
ITLIST2 (\a b c. b * iabs a + c) dd_list w (&0) <= error /\ |
| 1288 |
df_hi + error <= hi ==> |
| 1289 |
lo <= df_lo - error ==> |
| 1290 |
(!x. x IN interval [domain] ==> interval_arith (partial i f x) (lo, hi))`, |
| 1291 |
REWRITE_TAC[m_taylor_interval; m_lin_approx; ALL_N_EL; GSYM m_bounded_on_int] THEN |
| 1292 |
set_tac "s" `ITLIST2 _1 _2 _3 _4` THEN REPEAT STRIP_TAC THEN |
| 1293 |
SUBGOAL_THEN `1 <= i /\ i <= dimindex (:N)` (LABEL_TAC "i_in") THENL |
| 1294 |
[ |
| 1295 |
ASM_REWRITE_TAC[GSYM IN_NUMSEG]; |
| 1296 |
ALL_TAC |
| 1297 |
] THEN |
| 1298 |
SUBGOAL_THEN `diff2_domain domain (f:real^N->real)` ASSUME_TAC THENL |
| 1299 |
[ |
| 1300 |
UNDISCH_TAC `diff2c_domain domain (f:real^N->real)` THEN |
| 1301 |
SIMP_TAC[diff2_domain; diff2c_domain; diff2c]; |
| 1302 |
ALL_TAC |
| 1303 |
] THEN |
| 1304 |
REWRITE_TAC[ETA_AX] THEN apply_tac m_taylor_partial_bounds THEN |
| 1305 |
MAP_EVERY EXISTS_TAC [`y:real^N`; `vector w:real^N`; `error:real`; `df_lo:real`; `df_hi:real`] THEN |
| 1306 |
ASM_REWRITE_TAC[] THEN |
| 1307 |
FIRST_X_ASSUM (MP_TAC o SPEC `i - 1`) THEN |
| 1308 |
ASM_SIMP_TAC[ARITH_RULE `1 <= i /\ i <= n ==> i - 1 < n`] THEN |
| 1309 |
ASM_SIMP_TAC[ARITH_RULE `1 <= i ==> 1 + i - 1 = i`; interval_arith] THEN |
| 1310 |
DISCH_THEN (fun th -> ALL_TAC) THEN |
| 1311 |
REWRITE_TAC[m_taylor_partial_error] THEN REPEAT STRIP_TAC THEN |
| 1312 |
MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `s:real` THEN ASM_REWRITE_TAC[] THEN |
| 1313 |
EXPAND_TAC "s" THEN new_rewrite [] [] ITLIST2_EQ_SUM THEN ASM_REWRITE_TAC[LE_REFL] THEN |
| 1314 |
MATCH_MP_TAC SUM_LE THEN REWRITE_TAC[FINITE_NUMSEG] THEN |
| 1315 |
move ["j"; "j_in"] THEN |
| 1316 |
ASM_SIMP_TAC[VECTOR_COMPONENT] THEN |
| 1317 |
MATCH_MP_TAC REAL_LE_LMUL THEN CONJ_TAC THENL |
| 1318 |
[ |
| 1319 |
UNDISCH_TAC `m_cell_domain domain (y:real^N) (vector w)` THEN |
| 1320 |
new_rewrite [] [] pair_eq THEN REWRITE_TAC[m_cell_domain] THEN |
| 1321 |
DISCH_THEN (MP_TAC o SPEC `j:num`) THEN ASM_REWRITE_TAC[] THEN |
| 1322 |
ASM_SIMP_TAC[VECTOR_COMPONENT] THEN REAL_ARITH_TAC; |
| 1323 |
ALL_TAC |
| 1324 |
] THEN |
| 1325 |
FIRST_X_ASSUM (MP_TAC o SPEC `x:real^N`) THEN ASM_REWRITE_TAC[] THEN |
| 1326 |
DISCH_THEN (MP_TAC o SPEC `j - 1`) THEN |
| 1327 |
POP_ASSUM MP_TAC THEN REWRITE_TAC[IN_NUMSEG] THEN DISCH_TAC THEN |
| 1328 |
ASM_SIMP_TAC[ARITH_RULE `1 <= j /\ j <= n ==> j - 1 < n`] THEN |
| 1329 |
ASM_SIMP_TAC[ARITH_RULE `!i. 1 <= i ==> 1 + i - 1 = i`; GSYM partial2] THEN |
| 1330 |
DISCH_THEN (MP_TAC o MATCH_MP interval_arith_abs_le) THEN |
| 1331 |
COND_CASES_TAC THEN TRY (DISCH_THEN MATCH_MP_TAC THEN REWRITE_TAC[REAL_LE_REFL]) THEN |
| 1332 |
new_rewrite [] [] mixed_second_partials THENL |
| 1333 |
[ |
| 1334 |
UNDISCH_TAC `diff2c_domain domain (f:real^N->real)` THEN |
| 1335 |
ASM_SIMP_TAC[diff2c_domain]; |
| 1336 |
ALL_TAC |
| 1337 |
] THEN |
| 1338 |
DISCH_THEN MATCH_MP_TAC THEN REWRITE_TAC[REAL_LE_REFL]);; |
| 1339 |
|
| 1340 |
|
| 1341 |
(* upper *) |
| 1342 |
let M_TAYLOR_PARTIAL_UPPER' = |
| 1343 |
prove(`m_taylor_interval f domain (y:real^N) (vector w) f_bounds d_bounds_list dd_bounds_list /\ |
| 1344 |
i IN 1..dimindex (:N) /\ |
| 1345 |
EL (i - 1) d_bounds_list = (df_lo, df_hi) /\ |
| 1346 |
(!x. x IN interval [domain] ==> all_n 1 dd_list |
| 1347 |
(\j int. interval_arith (if j <= i then partial2 j i f x else partial2 i j f x) int)) /\ |
| 1348 |
LENGTH dd_list = dimindex (:N) /\ |
| 1349 |
LENGTH d_bounds_list = dimindex (:N) /\ |
| 1350 |
LENGTH w = dimindex (:N) /\ |
| 1351 |
ITLIST2 (\a b c. b * iabs a + c) dd_list w (&0) <= error /\ |
| 1352 |
df_hi + error <= hi ==> |
| 1353 |
(!x. x IN interval [domain] ==> partial i f x <= hi)`, |
| 1354 |
REPEAT STRIP_TAC THEN |
| 1355 |
MP_TAC (INST[`df_lo - error`, `lo:real`] M_TAYLOR_PARTIAL_BOUND') THEN ASM_REWRITE_TAC[REAL_LE_REFL] THEN |
| 1356 |
ASM_SIMP_TAC[interval_arith]);; |
| 1357 |
|
| 1358 |
|
| 1359 |
(* lower *) |
| 1360 |
let M_TAYLOR_PARTIAL_LOWER' = |
| 1361 |
prove(`m_taylor_interval f domain (y:real^N) (vector w) f_bounds d_bounds_list dd_bounds_list /\ |
| 1362 |
i IN 1..dimindex (:N) /\ |
| 1363 |
EL (i - 1) d_bounds_list = (df_lo, df_hi) /\ |
| 1364 |
(!x. x IN interval [domain] ==> all_n 1 dd_list |
| 1365 |
(\j int. interval_arith (if j <= i then partial2 j i f x else partial2 i j f x) int)) /\ |
| 1366 |
LENGTH dd_list = dimindex (:N) /\ |
| 1367 |
LENGTH d_bounds_list = dimindex (:N) /\ |
| 1368 |
LENGTH w = dimindex (:N) /\ |
| 1369 |
ITLIST2 (\a b c. b * iabs a + c) dd_list w (&0) <= error /\ |
| 1370 |
lo <= df_lo - error ==> |
| 1371 |
(!x. x IN interval [domain] ==> lo <= partial i f x)`, |
| 1372 |
REPEAT STRIP_TAC THEN |
| 1373 |
MP_TAC (INST[`df_hi + error`, `hi:real`] M_TAYLOR_PARTIAL_BOUND') THEN ASM_REWRITE_TAC[REAL_LE_REFL] THEN |
| 1374 |
ASM_SIMP_TAC[interval_arith]);; |
| 1375 |
|
| 1376 |
|
| 1377 |
|
| 1378 |
|
| 1379 |
(* arrays *) |
| 1380 |
let gen_taylor_partial_bound_th = |
| 1381 |
let imp_and_eq = TAUT `((P ==> Q) /\ (P ==> R)) <=> (P ==> Q /\ R)` in |
| 1382 |
let mk_list_hd l = mk_list (l, type_of (hd l)) in |
| 1383 |
let dd_list_var = `dd_list : (real#real)list` in |
| 1384 |
fun bound_th n i -> |
| 1385 |
let ns = 1--n in |
| 1386 |
let i_tm = mk_small_numeral i in |
| 1387 |
let w_list = mk_list_hd (map (fun i -> w_vars_array.(i)) ns) in |
| 1388 |
let d_bounds_list = mk_list_hd (map (fun i -> df_vars_array.(i)) ns) in |
| 1389 |
let dd_bounds_list = mk_list_hd |
| 1390 |
(map (fun i -> mk_list_hd (map (fun j -> dd_vars_array.(i).(j)) (1--i))) ns) in |
| 1391 |
let dd_list = mk_list_hd |
| 1392 |
(map (fun j -> if j <= i then dd_vars_array.(i).(j) else dd_vars_array.(j).(i)) ns) in |
| 1393 |
|
| 1394 |
let th1 = (INST[w_list, w_var_real_list; d_bounds_list, d_bounds_list_var; dd_list, dd_list_var; i_tm, `i:num`; |
| 1395 |
dd_bounds_list, dd_bounds_list_var] o INST_TYPE[n_type_array.(n), nty]) bound_th in |
| 1396 |
let th2 = REWRITE_RULE[REAL_ADD_RID; HD; TL; ITLIST2_DEF; LENGTH; ARITH; dimindex_array.(n)] th1 in |
| 1397 |
let th3 = REWRITE_RULE[IN_NUMSEG; ARITH; el_thms_array.(n).(i - 1)] th2 in |
| 1398 |
let th4 = (REWRITE_RULE[] o INST[`df_lo:real, df_hi:real`, df_vars_array.(i)]) th3 in |
| 1399 |
let th5 = (MY_RULE o REWRITE_RULE[GSYM imp_and_eq; GSYM AND_FORALL_THM; all_n; ARITH]) th4 in |
| 1400 |
|
| 1401 |
let m_taylor_hyp = find (can dest_m_taylor) (hyp th5) in |
| 1402 |
let t_th0 = (REWRITE_RULE[ARITH; all_n; second_bounded; m_taylor_interval] o ASSUME) m_taylor_hyp in |
| 1403 |
let t_th1 = REWRITE_RULE[GSYM imp_and_eq; GSYM AND_FORALL_THM] t_th0 in |
| 1404 |
(MY_RULE_NUM o REWRITE_RULE[GSYM error_mul_f2; t_th1] o DISCH_ALL) th5;; |
| 1405 |
|
| 1406 |
|
| 1407 |
(* The (n, i)-th element is the theorem |- i IN 1..dimindex (:n) *) |
| 1408 |
let i_in_array = Array.init (max_dim + 1) |
| 1409 |
(fun i -> Array.init (i + 1) |
| 1410 |
(fun j -> |
| 1411 |
if j < 1 then TRUTH else |
| 1412 |
let j_tm = mk_small_numeral j in |
| 1413 |
let tm0 = `j IN 1..dimindex (:N)` in |
| 1414 |
let tm1 = (subst [j_tm, `j:num`] o inst [n_type_array.(i), nty]) tm0 in |
| 1415 |
prove(tm1, REWRITE_TAC[dimindex_array.(i); IN_NUMSEG] THEN ARITH_TAC)));; |
| 1416 |
|
| 1417 |
let m_taylor_partial_upper_array, m_taylor_partial_lower_array, m_taylor_partial_bound_array = |
| 1418 |
let gen_array bound_th = Array.init (max_dim + 1) |
| 1419 |
(fun i -> Array.init (i + 1) |
| 1420 |
(fun j -> if j < 1 then TRUTH else gen_taylor_partial_bound_th bound_th i j)) in |
| 1421 |
gen_array M_TAYLOR_PARTIAL_UPPER', gen_array M_TAYLOR_PARTIAL_LOWER', gen_array M_TAYLOR_PARTIAL_BOUND';; |
| 1422 |
|
| 1423 |
|
| 1424 |
(***************************) |
| 1425 |
|
| 1426 |
|
| 1427 |
let eval_m_taylor_partial_bounds0 mode n pp i m_taylor_th = |
| 1428 |
let bound_th = |
| 1429 |
if mode = "upper" then |
| 1430 |
m_taylor_partial_upper_array.(n).(i) |
| 1431 |
else if mode = "bound" then |
| 1432 |
m_taylor_partial_bound_array.(n).(i) |
| 1433 |
else |
| 1434 |
m_taylor_partial_lower_array.(n).(i) in |
| 1435 |
|
| 1436 |
let f_tm, domain_tm, y_tm, w_tm, f_bounds, d_bounds_list, dd_bounds_list = dest_m_taylor (concl m_taylor_th) in |
| 1437 |
let ws = dest_list (rand w_tm) and |
| 1438 |
dfs = dest_list d_bounds_list and |
| 1439 |
dds = map dest_list (dest_list dd_bounds_list) in |
| 1440 |
let ns = 1--n in |
| 1441 |
let df_lo, df_hi = dest_pair (List.nth dfs (i - 1)) and |
| 1442 |
df_vars = map (fun i -> df_vars_array.(i)) ns and |
| 1443 |
dd_vars = map (fun i -> map (fun j -> dd_vars_array.(i).(j)) (1--i)) ns and |
| 1444 |
w_vars = map (fun i -> w_vars_array.(i)) ns and |
| 1445 |
y_var = mk_var ("y", type_of y_tm) and |
| 1446 |
f_var = mk_var ("f", type_of f_tm) and |
| 1447 |
domain_var = mk_var ("domain", type_of domain_tm) in |
| 1448 |
|
| 1449 |
(* sum of second partials *) |
| 1450 |
let dd_list = map |
| 1451 |
(fun j -> if j <= i then List.nth (List.nth dds (i-1)) (j-1) else List.nth (List.nth dds (j-1)) (i-1)) ns in |
| 1452 |
|
| 1453 |
let dd_th = |
| 1454 |
let mul_dd = map2 (error_mul_f2_le_conv2 pp) ws dd_list in |
| 1455 |
end_itlist (add_ineq_hi pp) mul_dd in |
| 1456 |
|
| 1457 |
let error_tm = (rand o concl) dd_th in |
| 1458 |
|
| 1459 |
(* additional inequalities *) |
| 1460 |
let prove_ineq, bounds_inst = |
| 1461 |
if mode = "upper" then |
| 1462 |
let ineq2 = float_add_hi pp df_hi error_tm in |
| 1463 |
MY_PROVE_HYP ineq2, [(rand o concl) ineq2, hi_var_real] |
| 1464 |
else if mode = "bound" then |
| 1465 |
let ineq2 = float_add_hi pp df_hi error_tm in |
| 1466 |
let ineq3 = float_sub_lo pp df_lo error_tm in |
| 1467 |
MY_PROVE_HYP ineq2 o MY_PROVE_HYP ineq3, |
| 1468 |
[(rand o concl) ineq2, hi_var_real; (lhand o concl) ineq3, lo_var_real] |
| 1469 |
else |
| 1470 |
let ineq2 = float_sub_lo pp df_lo error_tm in |
| 1471 |
MY_PROVE_HYP ineq2, [(lhand o concl) ineq2, lo_var_real] in |
| 1472 |
|
| 1473 |
(* final step *) |
| 1474 |
let inst_list = |
| 1475 |
let inst1 = zip dfs df_vars in |
| 1476 |
let inst2 = zip (List.flatten dds) (List.flatten dd_vars) in |
| 1477 |
let inst3 = zip ws w_vars in |
| 1478 |
inst1 @ inst2 @ inst3 in |
| 1479 |
|
| 1480 |
(MY_PROVE_HYP m_taylor_th o MY_PROVE_HYP dd_th o prove_ineq o |
| 1481 |
INST ([df_hi, df_hi_var; df_lo, df_lo_var; error_tm, error_var; |
| 1482 |
y_tm, y_var; domain_tm, domain_var; f_bounds, f_bounds_var; |
| 1483 |
f_tm, f_var] @ bounds_inst @ inst_list)) bound_th;; |
| 1484 |
|
| 1485 |
|
| 1486 |
(* upper *) |
| 1487 |
let eval_m_taylor_partial_upper = eval_m_taylor_partial_bounds0 "upper";; |
| 1488 |
|
| 1489 |
(* lower *) |
| 1490 |
let eval_m_taylor_partial_lower = eval_m_taylor_partial_bounds0 "lower";; |
| 1491 |
|
| 1492 |
(* bound *) |
| 1493 |
let eval_m_taylor_partial_bound = eval_m_taylor_partial_bounds0 "bound";; |
| 1494 |
|
| 1495 |
|
| 1496 |
|
| 1497 |
end;; |