Debian Codegraph @

Formal_ineqs/trig/poly.hl

raw
1 (* ========================================================================== *)
2 (* Formal verification of nonlinear inequalities in HOL Light *)
3 (* *)
4 (* Copyright (c) 2014 Alexey Solovyev *)
5 (* *)
6 (* This file is distributed under the terms of the MIT licence *)
7 (* ========================================================================== *)
8
9 (* -------------------------------------------------------------------------- *)
10 (* Formal interval evaluation of polynomials (theory) *)
11 (* -------------------------------------------------------------------------- *)
12
13 needs "Formal_ineqs/list/more_list.hl";;
14 needs "Formal_ineqs/arith/interval_arith.hl";;
15
16 module Poly = struct
17
18 open More_list;;
19 open Interval_arith;;
20
21 prioritize_real();;
22
23 (* Auxiliary definition: sometimes we want to change numerals in a theorem to
24 * floatint-point values but at the same time &0 should not be converted *)
25 let real_zero = new_definition `real_zero = &0`;;
26
27 (* Polynomial functions *)
28 let poly_f = new_definition `poly_f cs x = ITLIST (\c s. c + x * s) cs (&0)`;;
29
30 (* Even function *)
31 let poly_f_even = new_definition `poly_f_even cs x = poly_f cs (x * x)`;;
32
33 (* Odd function *)
34 let poly_f_odd = new_definition `poly_f_odd cs x = x * poly_f_even cs x`;;
35
36
37 let poly_f_empty = prove(`!x. poly_f [] x = &0`,
38 REWRITE_TAC[poly_f; ITLIST]);;
39
40 let poly_f_cons = prove(`!x h t. poly_f (CONS h t) x = h + x * poly_f t x`,
41 REWRITE_TAC[poly_f; ITLIST]);;
42
43 let poly_f_even_empty = prove(`!x. poly_f_even [] x = &0`,
44 REWRITE_TAC[poly_f_even; poly_f_empty]);;
45
46 let poly_f_even_cons = prove(`!x h t. poly_f_even (CONS h t) x = h + (x * x) * poly_f_even t x`,
47 REWRITE_TAC[poly_f_even; poly_f_cons]);;
48
49 let poly_f_odd_empty = prove(`!x. poly_f_odd [] x = &0`,
50 REWRITE_TAC[poly_f_odd; poly_f_even_empty; REAL_MUL_RZERO]);;
51
52 let poly_f_append = prove(`!x b a. poly_f (APPEND a b) x = poly_f a x + x pow (LENGTH a) * poly_f b x`,
53 GEN_TAC THEN GEN_TAC THEN
54 MATCH_MP_TAC list_INDUCT THEN
55 REPEAT STRIP_TAC THENL
56 [
57 REWRITE_TAC[APPEND; poly_f; ITLIST; LENGTH] THEN
58 REWRITE_TAC[real_pow; REAL_MUL_LID; REAL_ADD_LID];
59 ALL_TAC
60 ] THEN
61
62 REWRITE_TAC[APPEND; poly_f; ITLIST] THEN
63 ASM_REWRITE_TAC[GSYM poly_f] THEN
64 REWRITE_TAC[LENGTH; real_pow] THEN
65 REAL_ARITH_TAC);;
66
67 let poly_f_even_append = prove(`!x b a. poly_f_even (APPEND a b) x
68 = poly_f_even a x + x pow (2 * LENGTH a) * poly_f_even b x`,
69 REWRITE_TAC[poly_f_even; poly_f_append] THEN
70 REWRITE_TAC[GSYM REAL_POW_2; REAL_POW_POW]);;
71
72 let poly_f_odd_append = prove(`!x b a. poly_f_odd (APPEND a b) x
73 = poly_f_odd a x + x pow (2 * LENGTH a) * poly_f_odd b x`,
74 REPEAT GEN_TAC THEN
75 REWRITE_TAC[poly_f_odd] THEN
76 REWRITE_TAC[poly_f_even_append] THEN
77 REAL_ARITH_TAC);;
78
79 let poly_f_empty_interval = prove(`!x. interval_arith (poly_f [] x) (&0, &0)`,
80 REWRITE_TAC[interval_arith; poly_f_empty; REAL_LE_REFL]);;
81
82 let poly_f_sing = prove(`!c x. poly_f [c] x = c`,
83 REWRITE_TAC[poly_f; ITLIST; REAL_MUL_RZERO; REAL_ADD_RID]);;
84
85 let poly_f_even_sing = prove(`!c x. poly_f_even [c] x = c`,
86 REWRITE_TAC[poly_f_even; poly_f_sing]);;
87
88 let poly_f_odd_sing = prove(`!c x. poly_f_odd [c] x = c * x`,
89 REWRITE_TAC[poly_f_odd; poly_f_even_sing; REAL_MUL_AC]);;
90
91 (* bounds *)
92
93 let poly_f_empty_high_pos = prove(`!x. interval_arith (poly_f [] x) (real_zero, &0)`,
94 REWRITE_TAC[real_zero; interval_arith; poly_f_empty; REAL_LE_REFL]);;
95
96 let poly_f_sing_high_pos = prove(`!c x bounds. interval_arith c bounds
97 ==> interval_arith (poly_f [c] x) bounds`,
98 SIMP_TAC[poly_f_sing]);;
99
100 let poly_f_cons_high_pos_pos = prove(`!x h t a b c m r.
101 interval_arith (poly_f t x) (real_zero, a) /\
102 interval_arith h (real_zero, b) /\
103 interval_arith x (real_zero, c) /\
104 c * a <= m /\
105 b + m <= r
106 ==> interval_arith (poly_f (CONS h t) x) (real_zero, r)`,
107 REWRITE_TAC[poly_f_cons; interval_arith; real_zero] THEN REPEAT STRIP_TAC THENL [
108 MATCH_MP_TAC REAL_LE_ADD THEN ASM_REWRITE_TAC[] THEN
109 MATCH_MP_TAC REAL_LE_MUL THEN ASM_REWRITE_TAC[];
110 ALL_TAC
111 ] THEN
112 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `b + m:real` THEN ASM_REWRITE_TAC[] THEN
113 MATCH_MP_TAC REAL_LE_ADD2 THEN ASM_REWRITE_TAC[] THEN
114 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `c * a:real` THEN ASM_REWRITE_TAC[] THEN
115 MATCH_MP_TAC REAL_LE_MUL2 THEN ASM_REWRITE_TAC[]);;
116
117 let poly_f_empty_low_pos = prove(`!x. interval_arith (&0) (real_zero, poly_f [] x)`,
118 REWRITE_TAC[real_zero; interval_arith; poly_f_empty; REAL_LE_REFL]);;
119
120 let poly_f_sing_low_pos = prove(`!c b x. interval_arith b (real_zero, c)
121 ==> interval_arith b (real_zero, poly_f [c] x)`,
122 SIMP_TAC[poly_f_sing]);;
123
124 let poly_f_cons_low_pos_pos = prove(`!x h t a b c m r.
125 interval_arith a (real_zero, poly_f t x) /\
126 interval_arith b (real_zero, h) /\
127 interval_arith c (real_zero, x) /\
128 m <= c * a /\
129 r <= b + m /\
130 real_zero <= r
131 ==> interval_arith r (real_zero, poly_f (CONS h t) x)`,
132 REWRITE_TAC[poly_f_cons; interval_arith; real_zero] THEN
133 REPEAT STRIP_TAC THEN ASM_REWRITE_TAC[] THEN
134 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `b + m:real` THEN ASM_REWRITE_TAC[] THEN
135 MATCH_MP_TAC REAL_LE_ADD2 THEN ASM_REWRITE_TAC[] THEN
136 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `c * a:real` THEN ASM_REWRITE_TAC[] THEN
137 MATCH_MP_TAC REAL_LE_MUL2 THEN ASM_REWRITE_TAC[]);;
138
139
140 (* sum to poly *)
141
142 let sum_eq_poly_f = prove(`!a x n. sum (0..n) (\i. a i * x pow i) = poly_f (TABLE a (SUC n)) x`,
143 GEN_TAC THEN GEN_TAC THEN INDUCT_TAC THEN REWRITE_TAC[SUM_CLAUSES_NUMSEG; LE_0] THENL [
144 REWRITE_TAC[SUM_CLAUSES_NUMSEG; TABLE_SUC; TABLE_0; APPEND; poly_f_sing; real_pow; REAL_MUL_RID];
145 ALL_TAC
146 ] THEN
147 ONCE_REWRITE_TAC[TABLE_SUC] THEN
148 ASM_REWRITE_TAC[poly_f_append; LENGTH_TABLE; poly_f_sing; REAL_MUL_AC]);;
149
150 let sum_eq_poly_f_even = prove(`!a x n. sum (0..n) (\i. a i * x pow (2 * i))
151 = poly_f_even (TABLE a (SUC n)) x`,
152 REWRITE_TAC[GSYM REAL_POW_POW; sum_eq_poly_f; poly_f_even; REAL_POW_2]);;
153
154 let sum_eq_poly_f_odd = prove(`!a x n. sum (0..n) (\i. a i * x pow (2 * i + 1))
155 = poly_f_odd (TABLE a (SUC n)) x`,
156 REWRITE_TAC[REAL_POW_ADD; REAL_MUL_ASSOC; SUM_RMUL; REAL_POW_1] THEN
157 REWRITE_TAC[GSYM REAL_POW_POW; sum_eq_poly_f; poly_f_odd; poly_f_even] THEN
158 REWRITE_TAC[REAL_POW_2; REAL_MUL_AC]);;
159
160 let two_induct = prove(`!P. P 0 /\ P 1 /\ (!k. P k /\ P (k + 1) ==> P (k + 2)) ==> (!k. P k)`,
161 REPEAT STRIP_TAC THEN
162 SUBGOAL_THEN `!k. P k /\ P (k + 1)` (fun th -> REWRITE_TAC[th]) THEN
163 INDUCT_TAC THEN CONV_TAC NUM_REDUCE_CONV THEN ASM_REWRITE_TAC[ADD1] THEN
164 ASM_SIMP_TAC[ARITH_RULE `(k + 1) + 1 = k + 2`]);;
165
166
167 let alt_sum_eq_poly_f = prove(`!a x n. sum (0..n) (\i. ((-- &1) pow i * a i) * x pow i)
168 = poly_f_even (TABLE (\i. a (2 * i)) (n DIV 2 + 1)) x
169 - poly_f_odd (TABLE (\i. a (2 * i + 1)) (SUC n DIV 2)) x`,
170 GEN_TAC THEN GEN_TAC THEN MATCH_MP_TAC two_induct THEN REPEAT STRIP_TAC THENL [
171 REWRITE_TAC[SUM_SING_NUMSEG] THEN CONV_TAC NUM_REDUCE_CONV THEN
172 REWRITE_TAC[TABLE_0; ONE; TABLE_SUC; APPEND; poly_f_even; poly_f_odd_empty; poly_f_sing] THEN
173 REWRITE_TAC[MULT_0] THEN REAL_ARITH_TAC;
174 REWRITE_TAC[ONE; SUM_CLAUSES_NUMSEG; LE_0] THEN
175 CONV_TAC NUM_REDUCE_CONV THEN
176 REWRITE_TAC[ONE; TABLE_0; TABLE_SUC; APPEND] THEN
177 REWRITE_TAC[poly_f_even; poly_f_sing; poly_f_odd] THEN
178 CONV_TAC NUM_REDUCE_CONV THEN REAL_ARITH_TAC;
179 ALL_TAC
180 ] THEN
181 REWRITE_TAC[ARITH_RULE `n + 2 = SUC (SUC n)`] THEN
182 ASM_REWRITE_TAC[SUM_CLAUSES_NUMSEG; LE_0] THEN
183 SUBGOAL_THEN `SUC (SUC n) DIV 2 + 1 = SUC (n DIV 2 + 1)` (fun th -> REWRITE_TAC[th]) THENL [
184 REWRITE_TAC[ARITH_RULE `SUC (SUC n) = 1 * 2 + n`] THEN
185 ASM_SIMP_TAC[DIV_MULT_ADD; ARITH_RULE `~(2 = 0)`] THEN ARITH_TAC;
186 ALL_TAC
187 ] THEN
188 SUBGOAL_THEN `SUC (SUC (SUC n)) DIV 2 = SUC (SUC n DIV 2)` (fun th -> REWRITE_TAC[th]) THENL [
189 REWRITE_TAC[ARITH_RULE `SUC (SUC (SUC n)) = 1 * 2 + SUC n`] THEN
190 ASM_SIMP_TAC[DIV_MULT_ADD; ARITH_RULE `~(2 = 0)`] THEN ARITH_TAC;
191 ALL_TAC
192 ] THEN
193 REWRITE_TAC[TABLE_SUC; poly_f_even_append; poly_f_odd_append; LENGTH_TABLE] THEN
194 REWRITE_TAC[poly_f_even_sing; poly_f_odd_sing] THEN
195 SUBGOAL_THEN `~(2 = 0) /\ (!m. (2 * m) DIV 2 = m) /\ (!m. (2 * m + 1) DIV 2 = m)` ASSUME_TAC THENL [
196 SUBGOAL_THEN `~(2 = 0)` ASSUME_TAC THENL [ ARITH_TAC; ALL_TAC ] THEN
197 ASM_SIMP_TAC[DIV_MULT; ARITH_RULE `2 * m = m * 2`; DIV_MULT_ADD] THEN ARITH_TAC;
198 ALL_TAC
199 ] THEN
200 ASM_CASES_TAC `EVEN n` THENL [
201 POP_ASSUM MP_TAC THEN REWRITE_TAC[EVEN_EXISTS] THEN STRIP_TAC THEN ASM_REWRITE_TAC[] THEN
202 ASM_REWRITE_TAC[ADD1] THEN
203 REWRITE_TAC[REAL_POW_NEG] THEN
204 SUBGOAL_THEN `EVEN ((2 * m + 1) + 1) /\ ~(EVEN (2 * m + 1))` (fun th -> REWRITE_TAC[th]) THENL [
205 CONJ_TAC THENL [
206 REWRITE_TAC[EVEN_EXISTS] THEN EXISTS_TAC `m + 1` THEN ARITH_TAC;
207 ALL_TAC
208 ] THEN
209 REWRITE_TAC[NOT_EVEN; ODD_EXISTS] THEN EXISTS_TAC `m:num` THEN ARITH_TAC;
210 ALL_TAC
211 ] THEN
212 REWRITE_TAC[REAL_POW_ONE; ARITH_RULE `(2 * m + 1) + 1 = 2 * (m + 1)`] THEN
213 REWRITE_TAC[REAL_ARITH `x pow (2 * m) * a * x = (x pow (2 * m) * x pow 1) * a`] THEN
214 REWRITE_TAC[GSYM REAL_POW_ADD] THEN
215 REAL_ARITH_TAC;
216 ALL_TAC
217 ] THEN
218 POP_ASSUM MP_TAC THEN REWRITE_TAC[NOT_EVEN; ODD_EXISTS] THEN STRIP_TAC THEN ASM_REWRITE_TAC[] THEN
219 ASM_REWRITE_TAC[ADD1; ARITH_RULE `(2 * m + 1) + 1 = 2 * (m + 1)`] THEN
220 REWRITE_TAC[REAL_POW_NEG; EVEN_DOUBLE] THEN
221 SUBGOAL_THEN `~EVEN (2 * (m + 1) + 1)` (fun th -> REWRITE_TAC[th]) THENL [
222 REWRITE_TAC[NOT_EVEN; ODD_EXISTS] THEN EXISTS_TAC `m + 1` THEN ARITH_TAC;
223 ALL_TAC
224 ] THEN
225 REWRITE_TAC[REAL_POW_ONE] THEN
226 REWRITE_TAC[REAL_ARITH `x pow (2 * (m + 1)) * a * x = (x pow (2 * (m + 1)) * x pow 1) * a`] THEN
227 REWRITE_TAC[GSYM REAL_POW_ADD] THEN
228 REAL_ARITH_TAC);;
229
230
231 let alt_sum_eq_poly_f_even = prove(`!a x n. sum (0..n) (\i. ((-- &1) pow i * a i) * x pow (2 * i))
232 = poly_f_even (TABLE (\i. a (2 * i)) (n DIV 2 + 1)) (x * x)
233 - poly_f_odd (TABLE (\i. a (2 * i + 1)) (SUC n DIV 2)) (x * x)`,
234 REWRITE_TAC[GSYM REAL_POW_POW; alt_sum_eq_poly_f; REAL_POW_2]);;
235
236
237 let alt_sum_eq_poly_f_odd = prove(`!a x n. sum (0..n) (\i. ((-- &1) pow i * a i) * x pow (2 * i + 1))
238 = x * (poly_f_even (TABLE (\i. a (2 * i)) (n DIV 2 + 1)) (x * x)
239 - poly_f_odd (TABLE (\i. a (2 * i + 1)) (SUC n DIV 2)) (x * x))`,
240 REWRITE_TAC[REAL_POW_ADD; REAL_MUL_ASSOC; SUM_RMUL; alt_sum_eq_poly_f_even] THEN
241 REAL_ARITH_TAC);;
242
243 end;;