| 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;; |