Debian Codegraph @

Formal_ineqs/taylor/m_taylor.hl

raw
1 (* ========================================================================== *)
2 (* Formal verification of nonlinear inequalities in HOL Light *)
3 (* *)
4 (* Copyright (c) 2012 Alexey Solovyev *)
5 (* *)
6 (* This file is distributed under the terms of the MIT licence *)
7 (* ========================================================================== *)
8
9 (* -------------------------------------------------------------------------- *)
10 (* 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;;