| 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 functions: matan (theory) *) |
| 11 |
(* -------------------------------------------------------------------------- *) |
| 12 |
|
| 13 |
needs "Formal_ineqs/trig/series.hl";; |
| 14 |
|
| 15 |
module Matan = struct |
| 16 |
|
| 17 |
open Series;; |
| 18 |
|
| 19 |
prioritize_real();; |
| 20 |
|
| 21 |
(* matan *) |
| 22 |
|
| 23 |
let matan = new_definition `matan x = |
| 24 |
if (x = &0) then &1 |
| 25 |
else if (x > &0) then atn (sqrt x) / (sqrt x) |
| 26 |
else (log ((&1 + sqrt( -- x))/(&1 - sqrt( -- x)))) / (&2 * sqrt (-- x))`;; |
| 27 |
|
| 28 |
(* Auxiliary definitions for matan derivatives *) |
| 29 |
|
| 30 |
let dmatan = new_definition `dmatan = real_derivative matan`;; |
| 31 |
|
| 32 |
let ddmatan = new_definition `ddmatan = real_derivative (real_derivative matan)`;; |
| 33 |
|
| 34 |
|
| 35 |
let log_matan_series = prove(`!x. abs x < &1 /\ ~(x = &0) |
| 36 |
==> ((\k. x pow (2 * k) / &(2 * k + 1)) |
| 37 |
real_sums log ((&1 + x) / (&1 - x)) / (&2 * x)) (:num)`, |
| 38 |
REPEAT STRIP_TAC THEN |
| 39 |
MATCH_MP_TAC REAL_SUMS_EQ THEN REWRITE_TAC[IN_UNIV] THEN |
| 40 |
EXISTS_TAC `\k. x pow (2 * k + 1) / &(2 * k + 1) * inv x` THEN |
| 41 |
CONJ_TAC THENL [ |
| 42 |
X_GEN_TAC `k:num` THEN REWRITE_TAC[REAL_POW_ADD; REAL_POW_1] THEN |
| 43 |
ONCE_REWRITE_TAC[REAL_ARITH `(a * x) / b * inv x = (x * inv x) * a / b:real`] THEN |
| 44 |
ASM_SIMP_TAC[REAL_MUL_RINV; REAL_MUL_LID]; |
| 45 |
ALL_TAC |
| 46 |
] THEN |
| 47 |
REWRITE_TAC[real_div; REAL_INV_MUL; REAL_MUL_ASSOC] THEN |
| 48 |
MATCH_MP_TAC REAL_SERIES_RMUL THEN REWRITE_TAC[GSYM real_div] THEN |
| 49 |
ABBREV_TAC `f = \x:real. log ((&1 + x) / (&1 - x)) / &2` THEN |
| 50 |
MP_TAC (SPECL[`f:real->real`; `\x:real. inv (&1 - x pow 2)`; `\i. if EVEN i then &1 else &0`; `(:num)`; `&1`] power_series_integral2) THEN |
| 51 |
ANTS_TAC THENL [ |
| 52 |
CONJ_TAC THEN X_GEN_TAC `t:real` THEN DISCH_TAC THEN REWRITE_TAC[] THENL [ |
| 53 |
EXPAND_TAC "f" THEN REAL_DIFF_TAC THEN |
| 54 |
CONJ_TAC THENL [ |
| 55 |
ASM_SIMP_TAC[REAL_ARITH `abs t < &1 ==> ~(&1 - t = &0)`] THEN |
| 56 |
MATCH_MP_TAC REAL_LT_DIV THEN POP_ASSUM MP_TAC THEN REAL_ARITH_TAC; |
| 57 |
ALL_TAC |
| 58 |
] THEN |
| 59 |
POP_ASSUM MP_TAC THEN CONV_TAC REAL_FIELD; |
| 60 |
ALL_TAC |
| 61 |
] THEN |
| 62 |
REWRITE_TAC[COND_RAND; COND_RATOR; REAL_MUL_LZERO; real_sums_image_even; FROM_0] THEN |
| 63 |
MP_TAC (SPECL[`0`; `t:real pow 2`] REAL_SUMS_GP) THEN |
| 64 |
ANTS_TAC THENL [ |
| 65 |
REWRITE_TAC[REAL_ABS_MUL; REAL_ABS_POW; REAL_ARITH `abs (-- &1) = &1`; REAL_MUL_LID] THEN |
| 66 |
ASM_REWRITE_TAC[ABS_SQUARE_LT_1; REAL_ABS_ABS]; |
| 67 |
ALL_TAC |
| 68 |
] THEN |
| 69 |
REWRITE_TAC[real_pow; real_div; REAL_MUL_LID; REAL_POW_POW; FROM_0; MULT_0]; |
| 70 |
ALL_TAC |
| 71 |
] THEN |
| 72 |
DISCH_THEN (MP_TAC o SPEC `x:real`) THEN ASM_REWRITE_TAC[] THEN |
| 73 |
REWRITE_TAC[COND_RAND; COND_RATOR; REAL_MUL_LZERO; real_sums_image_even; REAL_MUL_LID] THEN |
| 74 |
SUBGOAL_THEN `f (&0) = &0` (fun th -> REWRITE_TAC[th; REAL_SUB_RZERO]) THENL [ |
| 75 |
EXPAND_TAC "f" THEN REWRITE_TAC[REAL_ADD_RID; REAL_SUB_RZERO; real_div; REAL_MUL_LID; REAL_INV_1; LOG_1; REAL_MUL_LZERO]; |
| 76 |
ALL_TAC |
| 77 |
] THEN |
| 78 |
EXPAND_TAC "f" THEN REWRITE_TAC[]);; |
| 79 |
|
| 80 |
|
| 81 |
(* matan power series *) |
| 82 |
|
| 83 |
let matan_power_series = prove(`!x. abs x < &1 |
| 84 |
==> ((\k. ((-- &1) pow k / &(2 * k + 1)) * x pow k) |
| 85 |
real_sums matan x) (:num)`, |
| 86 |
REPEAT STRIP_TAC THEN REWRITE_TAC[matan] THEN |
| 87 |
ASM_CASES_TAC `x = &0` THEN ASM_REWRITE_TAC[] THENL [ |
| 88 |
ABBREV_TAC `h = \k. -- &1 pow k / &(2 * k + 1) * &0 pow k` THEN |
| 89 |
SUBGOAL_THEN `h 0 = &1 /\ (!i. 1 <= i ==> h i = &0)` ASSUME_TAC THENL [ |
| 90 |
EXPAND_TAC "h" THEN REWRITE_TAC[REAL_POW_ZERO; real_pow; MULT_0; ADD] THEN |
| 91 |
CONJ_TAC THENL [ REAL_ARITH_TAC; ALL_TAC ] THEN |
| 92 |
GEN_TAC THEN COND_CASES_TAC THEN ASM_SIMP_TAC[ARITH_RULE `1 <= i ==> ~(i = 0)`; ARITH_RULE `~(1 <= 0)`; REAL_MUL_RZERO]; |
| 93 |
ALL_TAC |
| 94 |
] THEN |
| 95 |
SUBGOAL_THEN `&1 = &0 + sum(0..1 - 1) h` (fun th -> REWRITE_TAC[th]) THENL [ |
| 96 |
ASM_REWRITE_TAC[SUB_REFL; SUM_SING_NUMSEG; REAL_ADD_LID]; |
| 97 |
ALL_TAC |
| 98 |
] THEN |
| 99 |
REWRITE_TAC[GSYM FROM_0] THEN MATCH_MP_TAC REAL_SUMS_OFFSET_REV THEN |
| 100 |
REWRITE_TAC[ARITH_RULE `0 < 1`] THEN |
| 101 |
MATCH_MP_TAC REAL_SUMS_EQ THEN |
| 102 |
EXISTS_TAC `\i:num. &0` THEN |
| 103 |
ASM_SIMP_TAC[REAL_SERIES_0; IN_FROM]; |
| 104 |
ALL_TAC |
| 105 |
] THEN |
| 106 |
ASM_CASES_TAC `x > &0` THENL [ |
| 107 |
ASM_REWRITE_TAC[] THEN |
| 108 |
SUBGOAL_THEN `!y. y > &0 /\ y < &1 ==> ((\k. -- &1 pow k / &(2 * k + 1) * (y pow 2) pow k) real_sums atn y / y) (:num)` MP_TAC THENL [ |
| 109 |
REPEAT STRIP_TAC THEN |
| 110 |
MATCH_MP_TAC REAL_SUMS_EQ THEN REWRITE_TAC[IN_UNIV] THEN |
| 111 |
EXISTS_TAC `\k. (-- &1 pow k / &(2 * k + 1) * y pow (2 * k + 1)) * inv y` THEN |
| 112 |
CONJ_TAC THENL [ |
| 113 |
X_GEN_TAC `k:num` THEN REWRITE_TAC[REAL_POW_ADD; REAL_POW_1; GSYM REAL_MUL_ASSOC; REAL_POW_POW] THEN |
| 114 |
ASM_SIMP_TAC[REAL_ARITH `y > &0 ==> ~(y = &0)`; REAL_MUL_RINV; REAL_MUL_RID]; |
| 115 |
ALL_TAC |
| 116 |
] THEN |
| 117 |
REWRITE_TAC[real_div] THEN |
| 118 |
MATCH_MP_TAC REAL_SERIES_RMUL THEN REWRITE_TAC[GSYM real_div] THEN |
| 119 |
MATCH_MP_TAC atn_series THEN POP_ASSUM MP_TAC THEN POP_ASSUM MP_TAC THEN REAL_ARITH_TAC; |
| 120 |
ALL_TAC |
| 121 |
] THEN |
| 122 |
DISCH_THEN (MP_TAC o SPEC `sqrt x`) THEN ANTS_TAC THENL [ |
| 123 |
ASM_REWRITE_TAC[real_gt; SQRT_LT_0; REAL_ARITH `&0 < x <=> x > &0`] THEN |
| 124 |
MATCH_MP_TAC REAL_LT_LSQRT THEN |
| 125 |
REPEAT (POP_ASSUM MP_TAC) THEN REAL_ARITH_TAC; |
| 126 |
ALL_TAC |
| 127 |
] THEN |
| 128 |
SUBGOAL_THEN `sqrt x pow 2 = x` (fun th -> REWRITE_TAC[th]) THEN |
| 129 |
ASM_REWRITE_TAC[SQRT_POW2] THEN POP_ASSUM MP_TAC THEN REAL_ARITH_TAC; |
| 130 |
ALL_TAC |
| 131 |
] THEN |
| 132 |
ASM_REWRITE_TAC[] THEN |
| 133 |
MP_TAC (SPEC `sqrt (--x:real)` log_matan_series) THEN ANTS_TAC THENL [ |
| 134 |
ASM_REWRITE_TAC[SQRT_EQ_0; REAL_NEG_EQ_0] THEN |
| 135 |
ONCE_REWRITE_TAC[REAL_ARITH `&1 = abs(&1)`] THEN REWRITE_TAC[REAL_LT_SQUARE_ABS] THEN |
| 136 |
REWRITE_TAC[REAL_SQRT_POW_2] THEN REPEAT (POP_ASSUM MP_TAC) THEN REAL_ARITH_TAC; |
| 137 |
ALL_TAC |
| 138 |
] THEN |
| 139 |
REWRITE_TAC[GSYM REAL_POW_POW; REAL_SQRT_POW_2] THEN |
| 140 |
ASM_SIMP_TAC[REAL_ARITH `~(x > &0) ==> abs (--x) = --x`] THEN |
| 141 |
ONCE_REWRITE_TAC[REAL_NEG_MINUS1] THEN |
| 142 |
REWRITE_TAC[REAL_POW_MUL; REAL_POW_ONE; REAL_MUL_RID; real_div; REAL_MUL_AC]);; |
| 143 |
|
| 144 |
|
| 145 |
(* matan bounds *) |
| 146 |
|
| 147 |
let matan_abs1_bound = prove(`!m x. abs x < &1 ==> |
| 148 |
abs (matan x - sum (0..m) (\k. ((-- &1) pow k / &(2 * k + 1)) * x pow k)) |
| 149 |
<= abs x pow (SUC m) / (&(2 * m + 3) * (&1 - abs x))`, |
| 150 |
REPEAT STRIP_TAC THEN |
| 151 |
REWRITE_TAC[real_div; REAL_INV_MUL; REAL_ARITH `a * inv(c) * b = inv(c) * (a * b)`] THEN |
| 152 |
REWRITE_TAC[GSYM real_div] THEN |
| 153 |
SUBGOAL_THEN `!f. sum (0..m) f = sum (0..SUC m - 1) f` (fun th -> ONCE_REWRITE_TAC[th]) THENL [ |
| 154 |
REWRITE_TAC[ARITH_RULE `SUC m - 1 = m`]; |
| 155 |
ALL_TAC |
| 156 |
] THEN |
| 157 |
SUBGOAL_THEN `inv (&(2 * m + 3)) = abs ((\k. ((-- &1) pow k / &(2 * k + 1))) (SUC m))` (fun th -> ONCE_REWRITE_TAC[th]) THENL [ |
| 158 |
REWRITE_TAC[real_div; REAL_ABS_MUL; REAL_POW_NEG; REAL_POW_ONE] THEN |
| 159 |
REWRITE_TAC[COND_RAND; REAL_ARITH `abs (-- &1) = &1`; REAL_ABS_NUM; COND_ID] THEN |
| 160 |
REWRITE_TAC[REAL_MUL_LID; REAL_ABS_INV; REAL_ABS_NUM; ARITH_RULE `2 * SUC m + 1 = 2 * m + 3`]; |
| 161 |
ALL_TAC |
| 162 |
] THEN |
| 163 |
MP_TAC (SPECL[`\k. -- &1 pow k / &(2 * k + 1)`; `matan x`; `x:real`; `0`; `SUC m`] real_sums_simple_bound2) THEN |
| 164 |
ASM_REWRITE_TAC[ARITH_RULE `0 < SUC m`] THEN |
| 165 |
DISCH_THEN MATCH_MP_TAC THEN |
| 166 |
CONJ_TAC THENL [ |
| 167 |
ASM_SIMP_TAC[matan_power_series; FROM_0]; |
| 168 |
ALL_TAC |
| 169 |
] THEN |
| 170 |
REPEAT STRIP_TAC THEN |
| 171 |
REWRITE_TAC[real_div; REAL_ABS_MUL; REAL_POW_NEG; REAL_POW_ONE] THEN |
| 172 |
REWRITE_TAC[COND_RAND; REAL_ARITH `abs (-- &1) = &1`; REAL_ABS_NUM; COND_ID] THEN |
| 173 |
REWRITE_TAC[REAL_MUL_LID; REAL_ABS_INV; REAL_ABS_NUM; ARITH_RULE `2 * SUC m + 1 = 2 * m + 3`] THEN |
| 174 |
MATCH_MP_TAC REAL_LE_INV2 THEN |
| 175 |
REWRITE_TAC[REAL_OF_NUM_LT; REAL_OF_NUM_LE] THEN |
| 176 |
ARITH_TAC);; |
| 177 |
|
| 178 |
|
| 179 |
(* matan first derivative *) |
| 180 |
|
| 181 |
let matan_has_derivative_gt0 = prove(`!x. &0 < x ==> |
| 182 |
(matan has_real_derivative (inv (&2 * x * (x + &1)) - atn(sqrt(x)) / (&2 * x * sqrt(x)))) |
| 183 |
(atreal x)`, |
| 184 |
REPEAT STRIP_TAC THEN |
| 185 |
MATCH_MP_TAC HAS_REAL_DERIVATIVE_TRANSFORM_ATREAL THEN |
| 186 |
MAP_EVERY EXISTS_TAC [`\x. atn(sqrt(x)) / sqrt(x)`; `x:real`] THEN |
| 187 |
REPEAT CONJ_TAC THEN ASM_REWRITE_TAC[] THENL [ |
| 188 |
REPEAT STRIP_TAC THEN |
| 189 |
SUBGOAL_THEN `~(x' = &0) /\ x' > &0` ASSUME_TAC THENL [ |
| 190 |
REPEAT (POP_ASSUM MP_TAC) THEN REAL_ARITH_TAC; |
| 191 |
ALL_TAC |
| 192 |
] THEN |
| 193 |
ASM_REWRITE_TAC[matan]; |
| 194 |
ALL_TAC |
| 195 |
] THEN |
| 196 |
REAL_DIFF_TAC THEN |
| 197 |
SUBGOAL_THEN `~(sqrt x = &0)` ASSUME_TAC THENL [ |
| 198 |
ASM_SIMP_TAC[SQRT_EQ_0; REAL_ARITH `&0 < x ==> ~(x = &0)`]; |
| 199 |
ALL_TAC |
| 200 |
] THEN |
| 201 |
ASM_SIMP_TAC[SQRT_POW_2; REAL_ARITH `&0 < x ==> &0 <= x`] THEN |
| 202 |
REPEAT (POP_ASSUM MP_TAC) THEN |
| 203 |
CONV_TAC REAL_FIELD);; |
| 204 |
|
| 205 |
|
| 206 |
let matan_real_derivative_gt0 = prove(`!x. &0 < x ==> |
| 207 |
real_derivative matan x = inv (&2 * x * (x + &1)) - atn(sqrt(x)) / (&2 * x * sqrt(x))`, |
| 208 |
REPEAT STRIP_TAC THEN |
| 209 |
MATCH_MP_TAC HAS_REAL_DERIVATIVE_DERIVATIVE THEN |
| 210 |
ASM_SIMP_TAC[matan_has_derivative_gt0]);; |
| 211 |
|
| 212 |
|
| 213 |
let matan_real_derivative_abs1 = prove(`!x. abs x < &1 ==> |
| 214 |
matan real_differentiable atreal x |
| 215 |
/\ ((\i. ((-- &1) pow (SUC i) * &(SUC i) / &(2 * i + 3)) * x pow i) |
| 216 |
real_sums (real_derivative matan x)) (from 0)`, |
| 217 |
GEN_TAC THEN DISCH_TAC THEN |
| 218 |
MP_TAC (MATCH_MP power_series_has_derivative2 matan_power_series) THEN |
| 219 |
STRIP_TAC THEN POP_ASSUM (MP_TAC o SPEC `x:real`) THEN ASM_REWRITE_TAC[] THEN STRIP_TAC THEN |
| 220 |
CONJ_TAC THENL [ |
| 221 |
REWRITE_TAC[real_differentiable] THEN |
| 222 |
EXISTS_TAC `(f':real->real) x` THEN ASM_REWRITE_TAC[]; |
| 223 |
ALL_TAC |
| 224 |
] THEN |
| 225 |
SUBGOAL_THEN `real_derivative matan x = f' x` (fun th -> REWRITE_TAC[th]) THENL [ |
| 226 |
MATCH_MP_TAC HAS_REAL_DERIVATIVE_DERIVATIVE THEN ASM_REWRITE_TAC[]; |
| 227 |
ALL_TAC |
| 228 |
] THEN |
| 229 |
REWRITE_TAC[FROM_0; ARITH_RULE `2 * i + 3 = 2 * SUC i + 1`] THEN |
| 230 |
ONCE_REWRITE_TAC[REAL_ARITH `a * b / c = b * a / c`] THEN |
| 231 |
ASM_REWRITE_TAC[]);; |
| 232 |
|
| 233 |
|
| 234 |
let matan_real_derivative_abs1_bound = prove(`!x m. abs x < &1 ==> |
| 235 |
abs (real_derivative matan x |
| 236 |
- sum (0..m) (\i. ((-- &1) pow (SUC i) * &(SUC i) / &(2 * i + 3)) * x pow i)) |
| 237 |
<= abs x pow (SUC m) / (&2 * (&1 - abs x))`, |
| 238 |
REPEAT STRIP_TAC THEN |
| 239 |
REWRITE_TAC[real_div; REAL_INV_MUL; REAL_ARITH `a * inv(&2) * b = inv(&2) * (a * b)`] THEN |
| 240 |
REWRITE_TAC[GSYM real_div] THEN |
| 241 |
SUBGOAL_THEN `!f. sum (0..m) f = sum (0..SUC m - 1) f` (fun th -> ONCE_REWRITE_TAC[th]) THENL [ |
| 242 |
REWRITE_TAC[ARITH_RULE `SUC m - 1 = m`]; |
| 243 |
ALL_TAC |
| 244 |
] THEN |
| 245 |
MATCH_MP_TAC real_sums_simple_bound THEN |
| 246 |
ASM_REWRITE_TAC[ARITH_RULE `0 < SUC m`] THEN CONJ_TAC THENL [ |
| 247 |
ASM_SIMP_TAC[matan_real_derivative_abs1]; |
| 248 |
ALL_TAC |
| 249 |
] THEN |
| 250 |
REPEAT STRIP_TAC THEN |
| 251 |
REWRITE_TAC[REAL_ABS_MUL; REAL_POW_NEG; REAL_POW_ONE; COND_RAND; REAL_ABS_DIV] THEN |
| 252 |
REWRITE_TAC[REAL_ARITH `abs (-- &1) = &1 /\ abs (&1) = &1`; COND_ID; REAL_MUL_LID] THEN |
| 253 |
SUBGOAL_THEN `&0 < abs (&(2 * i + 3))` ASSUME_TAC THENL [ |
| 254 |
REWRITE_TAC[REAL_ABS_NUM; REAL_OF_NUM_LT] THEN ARITH_TAC; |
| 255 |
ALL_TAC |
| 256 |
] THEN |
| 257 |
ASM_SIMP_TAC[REAL_LE_LDIV_EQ; REAL_ABS_NUM; GSYM REAL_OF_NUM_ADD; GSYM REAL_OF_NUM_MUL] THEN |
| 258 |
REWRITE_TAC[REAL_FIELD `inv (&2) * (&2 * a + b) = a + inv(&2) * b`] THEN |
| 259 |
REWRITE_TAC[ADD1; GSYM REAL_OF_NUM_ADD; REAL_LE_LADD] THEN |
| 260 |
REAL_ARITH_TAC);; |
| 261 |
|
| 262 |
|
| 263 |
(* matan second derivative *) |
| 264 |
|
| 265 |
let matan_has_derivative2_gt0 = prove(`!x. &0 < x ==> |
| 266 |
((\x. inv (&2 * x * (x + &1)) - atn(sqrt(x)) / (&2 * x * sqrt(x))) has_real_derivative |
| 267 |
(&3 / &4) * (atn(sqrt(x)) / (x pow 2 * sqrt(x))) |
| 268 |
- (&3 / &4) * inv(x pow 2 * (x + &1)) |
| 269 |
- (&1 / &2) * inv(x * (x + &1) pow 2)) (atreal x)`, |
| 270 |
REPEAT STRIP_TAC THEN |
| 271 |
MP_TAC (REAL_ARITH `&0 < x ==> ~(x = &0)`) THEN ASM_REWRITE_TAC[] THEN DISCH_TAC THEN |
| 272 |
REAL_DIFF_TAC THEN |
| 273 |
SUBGOAL_THEN `~(sqrt x = &0)` ASSUME_TAC THENL [ ASM_SIMP_TAC[SQRT_EQ_0]; ALL_TAC ] THEN |
| 274 |
ASM_SIMP_TAC[SQRT_POW_2; REAL_ARITH `&0 < x ==> &0 <= x`; REAL_POW_MUL] THEN |
| 275 |
REPEAT CONJ_TAC THEN ASM_REWRITE_TAC[REAL_ENTIRE] THENL [ |
| 276 |
REPEAT (POP_ASSUM MP_TAC) THEN REAL_ARITH_TAC; |
| 277 |
REAL_ARITH_TAC; |
| 278 |
ALL_TAC |
| 279 |
] THEN |
| 280 |
REWRITE_TAC[REAL_ADD_RID; REAL_MUL_LID; REAL_MUL_RID] THEN |
| 281 |
SUBGOAL_THEN `x * inv (&2 * sqrt x) + sqrt x = (&3 / &2) * x / sqrt x` (fun th -> REWRITE_TAC[th]) THENL [ |
| 282 |
MATCH_MP_TAC REAL_EQ_LCANCEL_IMP THEN EXISTS_TAC `sqrt x` THEN |
| 283 |
ASM_REWRITE_TAC[REAL_ARITH `s * (x * inv t + s) = s * x * inv t + s pow 2`] THEN |
| 284 |
ASM_SIMP_TAC[SQRT_POW_2; REAL_ARITH `&0 < x ==> &0 <= x`] THEN |
| 285 |
REPEAT (POP_ASSUM MP_TAC) THEN CONV_TAC REAL_FIELD; |
| 286 |
ALL_TAC |
| 287 |
] THEN |
| 288 |
REPEAT (POP_ASSUM MP_TAC) THEN CONV_TAC REAL_FIELD);; |
| 289 |
|
| 290 |
let matan_second_derivative_gt0 = prove(`!x. &0 < x ==> |
| 291 |
real_derivative (real_derivative matan) x = |
| 292 |
(&3 / &4) * (atn(sqrt(x)) / (x pow 2 * sqrt(x))) |
| 293 |
- (&3 / &4) * inv(x pow 2 * (x + &1)) |
| 294 |
- (&1 / &2) * inv(x * (x + &1) pow 2)`, |
| 295 |
REPEAT STRIP_TAC THEN |
| 296 |
MATCH_MP_TAC HAS_REAL_DERIVATIVE_DERIVATIVE THEN |
| 297 |
MATCH_MP_TAC HAS_REAL_DERIVATIVE_TRANSFORM_ATREAL THEN |
| 298 |
MAP_EVERY EXISTS_TAC [`\x. inv (&2 * x * (x + &1)) - atn(sqrt(x)) / (&2 * x * sqrt(x))`; `x:real`] THEN |
| 299 |
REPEAT CONJ_TAC THEN ASM_REWRITE_TAC[] THENL [ |
| 300 |
REPEAT STRIP_TAC THEN |
| 301 |
SUBGOAL_THEN `&0 < x'` ASSUME_TAC THENL [ |
| 302 |
REPEAT (POP_ASSUM MP_TAC) THEN REAL_ARITH_TAC; |
| 303 |
ALL_TAC |
| 304 |
] THEN |
| 305 |
ASM_SIMP_TAC[matan_real_derivative_gt0]; |
| 306 |
ALL_TAC |
| 307 |
] THEN |
| 308 |
ASM_SIMP_TAC[matan_has_derivative2_gt0]);; |
| 309 |
|
| 310 |
|
| 311 |
let matan_second_derivative_abs1 = prove(`!x. abs x < &1 ==> |
| 312 |
(real_derivative matan) real_differentiable atreal x |
| 313 |
/\ ((\i. ((-- &1) pow (i + 2) * &((i + 1) * (i + 2)) / &(2 * i + 5)) * x pow i) |
| 314 |
real_sums (real_derivative (real_derivative matan) x)) (from 0)`, |
| 315 |
GEN_TAC THEN DISCH_TAC THEN |
| 316 |
MP_TAC (SPECL[`real_derivative matan`; `\i. -- &1 pow SUC i * &(SUC i) / &(2 * i + 3)`; `&1`] power_series_has_derivative2) THEN |
| 317 |
ANTS_TAC THENL [ |
| 318 |
REPEAT STRIP_TAC THEN |
| 319 |
MP_TAC (SPECL[`x':real`] matan_real_derivative_abs1) THEN |
| 320 |
ASM_SIMP_TAC[FROM_0]; |
| 321 |
ALL_TAC |
| 322 |
] THEN |
| 323 |
STRIP_TAC THEN POP_ASSUM (MP_TAC o SPEC `x:real`) THEN ASM_REWRITE_TAC[] THEN STRIP_TAC THEN |
| 324 |
CONJ_TAC THENL [ |
| 325 |
REWRITE_TAC[real_differentiable] THEN |
| 326 |
EXISTS_TAC `(f':real->real) x` THEN ASM_REWRITE_TAC[]; |
| 327 |
ALL_TAC |
| 328 |
] THEN |
| 329 |
SUBGOAL_THEN `real_derivative (real_derivative matan) x = f' x` (fun th -> REWRITE_TAC[th]) THENL [ |
| 330 |
MATCH_MP_TAC HAS_REAL_DERIVATIVE_DERIVATIVE THEN ASM_REWRITE_TAC[]; |
| 331 |
ALL_TAC |
| 332 |
] THEN |
| 333 |
REWRITE_TAC[FROM_0; ARITH_RULE `i + 2 = SUC (SUC i) /\ 2 * i + 5 = 2 * SUC i + 3 /\ i + 1 = SUC i`] THEN |
| 334 |
REWRITE_TAC[GSYM REAL_OF_NUM_MUL] THEN |
| 335 |
ONCE_REWRITE_TAC[REAL_ARITH `a * (b * d) / c = b * a * d / c`] THEN |
| 336 |
ASM_REWRITE_TAC[]);; |
| 337 |
|
| 338 |
|
| 339 |
let matan_second_derivative_abs1_alt = prove(`!x. abs x < &1 ==> |
| 340 |
real_derivative (real_derivative matan) x = (&1 - x) / (&4 * (&1 + x) pow 2) |
| 341 |
+ (&3 / &4) * real_infsum (:num) (\i. ((-- &1) pow i / &(2 * i + 5)) * x pow i) |
| 342 |
/\ real_summable (:num) (\i. ((-- &1) pow i / &(2 * i + 5)) * x pow i)`, |
| 343 |
GEN_TAC THEN DISCH_TAC THEN |
| 344 |
FIRST_ASSUM (MP_TAC o MATCH_MP matan_second_derivative_abs1) THEN STRIP_TAC THEN |
| 345 |
FIRST_ASSUM ((fun th -> REWRITE_TAC[GSYM th; FROM_0]) o MATCH_MP REAL_INFSUM_UNIQUE) THEN |
| 346 |
SUBGOAL_THEN `!i. -- &1 pow (i + 2) = -- &1 pow i` (fun th -> REWRITE_TAC[th]) THENL [ |
| 347 |
REWRITE_TAC[REAL_POW_ADD; REAL_ARITH `-- &1 pow 2 = &1`; REAL_MUL_RID]; |
| 348 |
ALL_TAC |
| 349 |
] THEN |
| 350 |
ASM_SIMP_TAC[REAL_FIELD `abs x < &1 ==> (&1 - x) / (&4 * (&1 + x) pow 2) = (&1 / &4) * (&1 / (&1 + x)) - (&1 / &2) * (x / (&1 + x) pow 2)`] THEN |
| 351 |
ABBREV_TAC `f = \i. -- &1 pow i * x pow i` THEN |
| 352 |
ABBREV_TAC `g = \i. (-- &1 pow i * &i) * x pow i` THEN |
| 353 |
ABBREV_TAC `h = \i. (-- &1 pow i * (&1 / &(2 * i + 5))) * x pow i` THEN |
| 354 |
SUBGOAL_THEN `!i. (-- &1 pow i * &((i + 1) * (i + 2)) / &(2 * i + 5)) * x pow i = &1 / &4 * f i + &1 / &2 * g i + &3 / &4 * h i` (fun th -> REWRITE_TAC[th]) THENL [ |
| 355 |
GEN_TAC THEN MAP_EVERY EXPAND_TAC ["f"; "g"; "h"] THEN |
| 356 |
REWRITE_TAC[GSYM REAL_OF_NUM_MUL; GSYM REAL_OF_NUM_ADD] THEN |
| 357 |
CONV_TAC REAL_FIELD; |
| 358 |
ALL_TAC |
| 359 |
] THEN |
| 360 |
SUBGOAL_THEN `!i. -- &1 pow i / &(2 * i + 5) * x pow i = h i` (fun th -> REWRITE_TAC[th]) THENL [ |
| 361 |
EXPAND_TAC "h" THEN REWRITE_TAC[real_div; REAL_MUL_LID]; |
| 362 |
ALL_TAC |
| 363 |
] THEN |
| 364 |
MP_TAC (SPEC `x:real` real_sums_neg_xi) THEN |
| 365 |
MP_TAC (SPEC `x:real` real_sums_neg_i_xi) THEN |
| 366 |
ASM_REWRITE_TAC[] THEN DISCH_THEN (LABEL_TAC "a") THEN DISCH_THEN (LABEL_TAC "b") THEN |
| 367 |
SUBGOAL_THEN `real_summable (:num) f /\ real_summable (:num) g /\ real_summable (:num) h` STRIP_ASSUME_TAC THENL [ |
| 368 |
REPEAT STRIP_TAC THEN REWRITE_TAC[real_summable] THENL [ |
| 369 |
EXISTS_TAC `&1 / (&1 + x)` THEN ASM_REWRITE_TAC[]; |
| 370 |
EXISTS_TAC `--(x / (&1 + x) pow 2)` THEN ASM_REWRITE_TAC[]; |
| 371 |
ALL_TAC |
| 372 |
] THEN |
| 373 |
REWRITE_TAC[GSYM real_summable] THEN EXPAND_TAC "h" THEN |
| 374 |
MATCH_MP_TAC REAL_SUMMABLE_COMPARISON THEN |
| 375 |
EXISTS_TAC `\i. abs x pow i` THEN |
| 376 |
CONJ_TAC THENL [ |
| 377 |
MATCH_MP_TAC REAL_SUMMABLE_GP THEN ASM_REWRITE_TAC[REAL_ABS_ABS]; |
| 378 |
ALL_TAC |
| 379 |
] THEN |
| 380 |
EXISTS_TAC `0` THEN REPEAT STRIP_TAC THEN |
| 381 |
REWRITE_TAC[REAL_ABS_MUL; abs_neg_one_pow; REAL_ABS_POW; REAL_MUL_LID] THEN |
| 382 |
ONCE_REWRITE_TAC[REAL_ARITH `a <= b <=> a <= &1 * b`] THEN |
| 383 |
MATCH_MP_TAC REAL_LE_RMUL THEN |
| 384 |
CONJ_TAC THENL [ ALL_TAC; MATCH_MP_TAC REAL_POW_LE THEN REAL_ARITH_TAC ] THEN |
| 385 |
REWRITE_TAC[REAL_ABS_DIV; REAL_ABS_1] THEN |
| 386 |
REWRITE_TAC[REAL_ARITH `&1 / a <= &1 <=> inv a <= inv (&1)`] THEN |
| 387 |
MATCH_MP_TAC REAL_LE_INV2 THEN |
| 388 |
REWRITE_TAC[GSYM REAL_OF_NUM_ADD; GSYM REAL_OF_NUM_MUL] THEN |
| 389 |
REAL_ARITH_TAC; |
| 390 |
ALL_TAC |
| 391 |
] THEN |
| 392 |
ASM_SIMP_TAC[REAL_INFSUM_ADD; REAL_SUMMABLE_ADD; REAL_SUMMABLE_LMUL; ETA_AX] THEN |
| 393 |
ASM_SIMP_TAC[REAL_INFSUM_LMUL] THEN |
| 394 |
REMOVE_THEN "a" (MP_TAC o MATCH_MP REAL_INFSUM_UNIQUE) THEN |
| 395 |
REMOVE_THEN "b" (MP_TAC o MATCH_MP REAL_INFSUM_UNIQUE) THEN |
| 396 |
ASM_SIMP_TAC[] THEN REAL_ARITH_TAC);; |
| 397 |
|
| 398 |
|
| 399 |
|
| 400 |
(* matan second derivative bound *) |
| 401 |
|
| 402 |
let matan_d2_bound_ge1_high = prove(`!x. &1 <= x ==> |
| 403 |
real_derivative (real_derivative matan) x <= #0.65`, |
| 404 |
REPEAT STRIP_TAC THEN |
| 405 |
ASM_SIMP_TAC[REAL_ARITH `&1 <= x ==> &0 < x`; matan_second_derivative_gt0] THEN |
| 406 |
MATCH_MP_TAC REAL_LE_TRANS THEN |
| 407 |
EXISTS_TAC `(&3 / &4) * atn(sqrt x) / (x pow 2 * sqrt x)` THEN |
| 408 |
CONJ_TAC THENL [ |
| 409 |
REWRITE_TAC[REAL_ARITH `a - b - c <= a <=> &0 <= b + c`] THEN |
| 410 |
MATCH_MP_TAC REAL_LE_ADD THEN |
| 411 |
CONJ_TAC THEN MATCH_MP_TAC REAL_LE_MUL THEN CONJ_TAC THEN TRY REAL_ARITH_TAC THENL [ |
| 412 |
MATCH_MP_TAC REAL_LE_INV THEN MATCH_MP_TAC REAL_LE_MUL THEN |
| 413 |
REWRITE_TAC[REAL_LE_POW_2] THEN POP_ASSUM MP_TAC THEN REAL_ARITH_TAC; |
| 414 |
MATCH_MP_TAC REAL_LE_INV THEN MATCH_MP_TAC REAL_LE_MUL THEN |
| 415 |
REWRITE_TAC[REAL_LE_POW_2] THEN POP_ASSUM MP_TAC THEN REAL_ARITH_TAC; |
| 416 |
]; |
| 417 |
ALL_TAC |
| 418 |
] THEN |
| 419 |
ABBREV_TAC `y = sqrt x` THEN |
| 420 |
SUBGOAL_THEN `x pow 2 * y = y pow 5` (fun th -> REWRITE_TAC[th]) THENL [ |
| 421 |
MP_TAC (SPEC `x:real` SQRT_POW_2) THEN |
| 422 |
ASM_SIMP_TAC[REAL_ARITH `&1 <= x ==> &0 <= x`] THEN |
| 423 |
CONV_TAC REAL_RING; |
| 424 |
ALL_TAC |
| 425 |
] THEN |
| 426 |
ONCE_REWRITE_TAC[REAL_ARITH `#0.65 = (&3 / &4) * (#0.65 * &4 / &3)`] THEN |
| 427 |
MATCH_MP_TAC REAL_LE_LMUL THEN CONJ_TAC THENL [ REAL_ARITH_TAC; ALL_TAC ] THEN |
| 428 |
SUBGOAL_THEN `&1 <= y` ASSUME_TAC THENL [ |
| 429 |
EXPAND_TAC "y" THEN MATCH_MP_TAC REAL_LE_RSQRT THEN ASM_REWRITE_TAC[REAL_POW_ONE]; |
| 430 |
ALL_TAC |
| 431 |
] THEN |
| 432 |
MATCH_MP_TAC REAL_LE_TRANS THEN |
| 433 |
EXISTS_TAC `atn (&1) / (&1 pow 5)` THEN CONJ_TAC THENL [ |
| 434 |
ONCE_REWRITE_TAC[GSYM REAL_LE_NEG2] THEN |
| 435 |
ABBREV_TAC `f = \y. --(atn y / y pow 5)` THEN |
| 436 |
SUBGOAL_THEN `!x. --(atn x / x pow 5) = f x` (fun th -> REWRITE_TAC[th]) THENL [ |
| 437 |
EXPAND_TAC "f" THEN REWRITE_TAC[]; |
| 438 |
ALL_TAC |
| 439 |
] THEN |
| 440 |
MATCH_MP_TAC HAS_REAL_DERIVATIVE_INCREASING_IMP THEN |
| 441 |
EXISTS_TAC `\y. &5 * atn(y) / y pow 6 - inv(y pow 5 * (y pow 2 + &1))` THEN |
| 442 |
EXISTS_TAC `real_interval [&1, y]` THEN |
| 443 |
ASM_REWRITE_TAC[IS_REALINTERVAL_INTERVAL; IN_REAL_INTERVAL; REAL_LE_REFL] THEN |
| 444 |
CONJ_TAC THENL [ |
| 445 |
REPEAT STRIP_TAC THEN |
| 446 |
MATCH_MP_TAC HAS_REAL_DERIVATIVE_ATREAL_WITHIN THEN |
| 447 |
EXPAND_TAC "f" THEN REAL_DIFF_TAC THEN |
| 448 |
ASM_SIMP_TAC[REAL_ARITH `&1 <= x' ==> ~(x' = &0)`; REAL_POW_NZ] THEN |
| 449 |
REWRITE_TAC[ARITH_RULE `5 - 1 = 4 /\ 5 * 2 = 10`; REAL_POW_POW] THEN |
| 450 |
SUBGOAL_THEN `!n. ~(x' pow n = &0)` ASSUME_TAC THENL [ |
| 451 |
GEN_TAC THEN MATCH_MP_TAC REAL_POW_NZ THEN |
| 452 |
UNDISCH_TAC `&1 <= x'` THEN REAL_ARITH_TAC; |
| 453 |
ALL_TAC |
| 454 |
] THEN |
| 455 |
MATCH_MP_TAC REAL_EQ_RCANCEL_IMP THEN EXISTS_TAC `x' pow 10` THEN |
| 456 |
ASM_REWRITE_TAC[real_div; GSYM REAL_MUL_LNEG; GSYM REAL_MUL_ASSOC] THEN |
| 457 |
ASM_SIMP_TAC[REAL_MUL_LINV; REAL_INV_MUL; REAL_INV_POW] THEN |
| 458 |
REWRITE_TAC[REAL_ARITH `(&5 * a * p6 - ip5 * t) * p10 = &5 * a * (p6 * p10) - (ip5 * p10) * t`] THEN |
| 459 |
REWRITE_TAC[REAL_FIELD `inv x' pow 6 * x' pow 10 = x' pow 4`] THEN |
| 460 |
REWRITE_TAC[REAL_FIELD `inv x' pow 5 * x' pow 10 = x' pow 5`] THEN |
| 461 |
REAL_ARITH_TAC; |
| 462 |
ALL_TAC |
| 463 |
] THEN |
| 464 |
X_GEN_TAC `t:real` THEN REPEAT STRIP_TAC THEN |
| 465 |
REWRITE_TAC[REAL_ARITH `&0 <= a - b <=> b <= a`] THEN |
| 466 |
SUBGOAL_THEN `!n. &0 < t pow n` ASSUME_TAC THENL [ |
| 467 |
GEN_TAC THEN MATCH_MP_TAC REAL_POW_LT THEN |
| 468 |
ASM_SIMP_TAC[REAL_ARITH `&1 <= t ==> &0 < t`]; |
| 469 |
ALL_TAC |
| 470 |
] THEN |
| 471 |
MATCH_MP_TAC REAL_LE_RCANCEL_IMP THEN |
| 472 |
EXISTS_TAC `t pow 6` THEN ASM_REWRITE_TAC[] THEN |
| 473 |
REWRITE_TAC[real_div; REAL_INV_MUL; GSYM REAL_MUL_ASSOC] THEN |
| 474 |
ASM_SIMP_TAC[REAL_MUL_LINV; REAL_ARITH `&0 < a ==> ~(a = &0)`; REAL_MUL_RID] THEN |
| 475 |
ONCE_REWRITE_TAC[REAL_ARITH `a * b * c = (a * c) * b:real`] THEN |
| 476 |
REWRITE_TAC[REAL_FIELD `inv (t pow 5) * t pow 6 = t`] THEN |
| 477 |
MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `&1` THEN CONJ_TAC THENL [ |
| 478 |
SUBGOAL_THEN `&0 < t pow 2 + &1` ASSUME_TAC THENL [ |
| 479 |
MATCH_MP_TAC REAL_LT_ADD THEN REWRITE_TAC[REAL_LT_POW_2] THEN |
| 480 |
UNDISCH_TAC `&1 <= t` THEN REAL_ARITH_TAC; |
| 481 |
ALL_TAC |
| 482 |
] THEN |
| 483 |
ASM_SIMP_TAC[REAL_LE_LDIV_EQ; GSYM real_div; REAL_MUL_LID] THEN |
| 484 |
MATCH_MP_TAC (REAL_ARITH `&1 <= t /\ &0 <= (t - &1) pow 2 ==> t <= t pow 2 + &1`) THEN |
| 485 |
ASM_REWRITE_TAC[REAL_LE_POW_2]; |
| 486 |
ALL_TAC |
| 487 |
] THEN |
| 488 |
REWRITE_TAC[REAL_ARITH `&1 <= &5 * x <=> (&1 / &5) <= x`] THEN |
| 489 |
MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `pi / &4` THEN |
| 490 |
CONJ_TAC THENL [ MP_TAC PI_APPROX_32 THEN REAL_ARITH_TAC; ALL_TAC ] THEN |
| 491 |
ASM_REWRITE_TAC[GSYM ATN_1; ATN_MONO_LE_EQ]; |
| 492 |
ALL_TAC |
| 493 |
] THEN |
| 494 |
REWRITE_TAC[ATN_1] THEN MP_TAC PI_APPROX_32 THEN |
| 495 |
REAL_ARITH_TAC);; |
| 496 |
|
| 497 |
|
| 498 |
let matan_d2_bound_ge1_low = prove(`!x. &1 <= x ==> |
| 499 |
-- #0.65 <= real_derivative (real_derivative matan) x`, |
| 500 |
REPEAT STRIP_TAC THEN |
| 501 |
ASM_SIMP_TAC[REAL_ARITH `&1 <= x ==> &0 < x`; matan_second_derivative_gt0] THEN |
| 502 |
MATCH_MP_TAC REAL_LE_TRANS THEN |
| 503 |
EXISTS_TAC `-- (&3 / &4) * inv (x pow 2 * (x + &1)) - (&1 / &2) * inv (x * (x + &1) pow 2)` THEN |
| 504 |
CONJ_TAC THENL [ |
| 505 |
REWRITE_TAC[REAL_ARITH `-- #0.65 <= --(&3 / &4) * a - (&1 / &2) * b <=> &3 * a + &2 * b <= #2.6`] THEN |
| 506 |
MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `&3 * inv(&2) + &2 * inv(&2)` THEN |
| 507 |
CONJ_TAC THENL [ ALL_TAC; REAL_ARITH_TAC ] THEN |
| 508 |
MATCH_MP_TAC REAL_LE_ADD2 THEN |
| 509 |
CONJ_TAC THEN MATCH_MP_TAC REAL_LE_LMUL THEN REWRITE_TAC[REAL_POS] THEN MATCH_MP_TAC REAL_LE_INV2 THEN REWRITE_TAC[REAL_ARITH `&0 < &2`] THEN ONCE_REWRITE_TAC[REAL_ARITH `&2 = &1 * &2`] THEN MATCH_MP_TAC REAL_LE_MUL2 THEN ASM_REWRITE_TAC[REAL_POS] THENL [ |
| 510 |
ASM_SIMP_TAC[REAL_POW_LE_1] THEN POP_ASSUM MP_TAC THEN REAL_ARITH_TAC; |
| 511 |
ALL_TAC |
| 512 |
] THEN |
| 513 |
ONCE_REWRITE_TAC[REAL_ARITH `&2 = &2 * &1`] THEN REWRITE_TAC[REAL_POW_2] THEN |
| 514 |
MATCH_MP_TAC REAL_LE_MUL2 THEN POP_ASSUM MP_TAC THEN REAL_ARITH_TAC; |
| 515 |
ALL_TAC |
| 516 |
] THEN |
| 517 |
REWRITE_TAC[REAL_ARITH `--(&3 / &4) * a - b <= c - (&3 / &4) * a - b <=> &0 <= c`] THEN |
| 518 |
MATCH_MP_TAC REAL_LE_MUL THEN CONJ_TAC THENL [ REAL_ARITH_TAC; ALL_TAC ] THEN |
| 519 |
MATCH_MP_TAC REAL_LE_DIV THEN |
| 520 |
ASM_SIMP_TAC[ATN_POS_LE; SQRT_POS_LE; REAL_ARITH `&1 <= x ==> &0 <= x`] THEN |
| 521 |
MATCH_MP_TAC REAL_LE_MUL THEN |
| 522 |
ASM_SIMP_TAC[REAL_LE_POW_2; SQRT_POS_LE; REAL_ARITH `&1 <= x ==> &0 <= x`]);; |
| 523 |
|
| 524 |
|
| 525 |
let matan_d2_bound_01 = prove(`!x. &0 <= x /\ x < &1 ==> |
| 526 |
abs (real_derivative (real_derivative matan) x) <= #0.65`, |
| 527 |
GEN_TAC THEN DISCH_TAC THEN |
| 528 |
MP_TAC (SPEC `x:real` matan_second_derivative_abs1_alt) THEN ANTS_TAC THENL [ |
| 529 |
POP_ASSUM MP_TAC THEN REAL_ARITH_TAC; |
| 530 |
ALL_TAC |
| 531 |
] THEN |
| 532 |
STRIP_TAC THEN ASM_REWRITE_TAC[] THEN |
| 533 |
MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `&1 / &4 + &3 / &20` THEN |
| 534 |
CONJ_TAC THEN TRY REAL_ARITH_TAC THEN |
| 535 |
ABBREV_TAC `f = (&1 - x) / (&4 * (&1 + x) pow 2)` THEN |
| 536 |
ABBREV_TAC `r = real_infsum (:num) (\i. -- &1 pow i / &(2 * i + 5) * x pow i)` THEN |
| 537 |
MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `abs f + abs (&3 / &4 * r)` THEN |
| 538 |
REWRITE_TAC[REAL_ABS_TRIANGLE] THEN |
| 539 |
MATCH_MP_TAC REAL_LE_ADD2 THEN CONJ_TAC THENL [ |
| 540 |
EXPAND_TAC "f" THEN REWRITE_TAC[REAL_ABS_DIV; REAL_ABS_MUL; REAL_ABS_NUM] THEN |
| 541 |
SUBGOAL_THEN `&0 < &4 /\ &0 < &4 * abs ((&1 + x) pow 2)` ASSUME_TAC THENL [ |
| 542 |
CONJ_TAC THEN TRY REAL_ARITH_TAC THEN |
| 543 |
MATCH_MP_TAC REAL_LT_MUL THEN CONJ_TAC THEN TRY REAL_ARITH_TAC THEN |
| 544 |
MATCH_MP_TAC (REAL_ARITH `&0 < x ==> &0 < abs x`) THEN |
| 545 |
REWRITE_TAC[REAL_LT_POW_2] THEN |
| 546 |
UNDISCH_TAC `&0 <= x /\ x < &1` THEN REAL_ARITH_TAC; |
| 547 |
ALL_TAC |
| 548 |
] THEN |
| 549 |
ASM_SIMP_TAC[RAT_LEMMA4; REAL_MUL_LID] THEN |
| 550 |
REWRITE_TAC[REAL_MUL_AC] THEN |
| 551 |
MATCH_MP_TAC REAL_LE_RMUL THEN CONJ_TAC THEN TRY REAL_ARITH_TAC THEN |
| 552 |
MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `&1` THEN |
| 553 |
UNDISCH_TAC `&0 <= x /\ x < &1` THEN DISCH_THEN (LABEL_TAC "h") THEN |
| 554 |
CONJ_TAC THENL [ POP_ASSUM MP_TAC THEN REAL_ARITH_TAC; ALL_TAC ] THEN |
| 555 |
MATCH_MP_TAC (REAL_ARITH `&1 <= a ==> &1 <= abs a`) THEN |
| 556 |
MATCH_MP_TAC REAL_LSQRT_LE THEN REWRITE_TAC[SQRT_1] THEN |
| 557 |
POP_ASSUM MP_TAC THEN REAL_ARITH_TAC; |
| 558 |
ALL_TAC |
| 559 |
] THEN |
| 560 |
REWRITE_TAC[REAL_ABS_MUL; REAL_ARITH `&3 / &20 = abs (&3 / &4) * (&1 / &5)`] THEN |
| 561 |
MATCH_MP_TAC REAL_LE_LMUL THEN CONJ_TAC THENL [ REAL_ARITH_TAC; ALL_TAC ] THEN |
| 562 |
EXPAND_TAC "r" THEN |
| 563 |
SUBGOAL_THEN `&1 / &5 = abs ((\i. -- &1 pow i / &(2 * i + 5) * x pow i) 0)` (fun th -> ONCE_REWRITE_TAC[th]) THENL [ |
| 564 |
REWRITE_TAC[real_pow; MULT_0; ADD; REAL_ABS_DIV; REAL_ABS_NUM; REAL_MUL_RID]; |
| 565 |
ALL_TAC |
| 566 |
] THEN |
| 567 |
PURE_REWRITE_TAC[GSYM FROM_0] THEN |
| 568 |
MATCH_MP_TAC alt_sign_bound THEN |
| 569 |
CONJ_TAC THENL [ |
| 570 |
REWRITE_TAC[REAL_ABS_MUL; REAL_ABS_DIV; abs_neg_one_pow; real_div; REAL_MUL_LID] THEN |
| 571 |
REPEAT STRIP_TAC THENL [ |
| 572 |
MATCH_MP_TAC REAL_LE_MUL2 THEN REWRITE_TAC[REAL_ABS_POS] THEN |
| 573 |
CONJ_TAC THENL [ |
| 574 |
REWRITE_TAC[REAL_ABS_INV] THEN MATCH_MP_TAC REAL_LE_INV2 THEN |
| 575 |
REWRITE_TAC[REAL_ABS_NUM; REAL_OF_NUM_LT; REAL_OF_NUM_LE] THEN |
| 576 |
ARITH_TAC; |
| 577 |
ALL_TAC |
| 578 |
] THEN |
| 579 |
REWRITE_TAC[GSYM ADD1; real_pow; REAL_ABS_MUL] THEN |
| 580 |
ONCE_REWRITE_TAC[REAL_ARITH `x * y <= y <=> x * y <= &1 * y`] THEN |
| 581 |
MATCH_MP_TAC REAL_LE_RMUL THEN REWRITE_TAC[REAL_ABS_POS] THEN |
| 582 |
UNDISCH_TAC `&0 <= x /\ x < &1` THEN REAL_ARITH_TAC; |
| 583 |
ALL_TAC |
| 584 |
] THEN |
| 585 |
REWRITE_TAC[REAL_ARITH `((a * b) * c) * (d * e) * f = (a * d) * ((c * f) * b * e)`] THEN |
| 586 |
REWRITE_TAC[REAL_ARITH `a * b <= &0 <=> &0 <= (-- &1 * a) * b`] THEN |
| 587 |
REWRITE_TAC[GSYM REAL_POW_ADD; GSYM real_pow] THEN |
| 588 |
MATCH_MP_TAC REAL_LE_MUL THEN CONJ_TAC THENL [ |
| 589 |
REWRITE_TAC[ARITH_RULE `SUC ((n + 1) + n) = 2 * (n + 1)`] THEN |
| 590 |
REWRITE_TAC[real_pow; REAL_POW_NEG; EVEN_DOUBLE; REAL_POW_ONE; REAL_LE_01]; |
| 591 |
ALL_TAC |
| 592 |
] THEN |
| 593 |
MATCH_MP_TAC REAL_LE_MUL THEN CONJ_TAC THENL [ |
| 594 |
MATCH_MP_TAC REAL_POW_LE THEN ASM_REWRITE_TAC[]; |
| 595 |
ALL_TAC |
| 596 |
] THEN |
| 597 |
REWRITE_TAC[GSYM REAL_INV_MUL] THEN MATCH_MP_TAC REAL_LE_INV THEN |
| 598 |
REWRITE_TAC[REAL_OF_NUM_MUL; REAL_OF_NUM_LE; LE_0]; |
| 599 |
ALL_TAC |
| 600 |
] THEN |
| 601 |
ONCE_REWRITE_TAC[GSYM REALLIM_NULL_ABS] THEN |
| 602 |
REWRITE_TAC[REAL_ABS_MUL; real_div; REAL_ABS_INV; abs_neg_one_pow; REAL_ABS_NUM; REAL_MUL_LID] THEN |
| 603 |
MATCH_MP_TAC REALLIM_NULL_COMPARISON THEN |
| 604 |
EXISTS_TAC `\n. inv (&n)` THEN CONJ_TAC THENL [ |
| 605 |
REWRITE_TAC[EVENTUALLY_SEQUENTIALLY] THEN |
| 606 |
EXISTS_TAC `1` THEN REPEAT STRIP_TAC THEN |
| 607 |
ONCE_REWRITE_TAC[REAL_ARITH `inv (&n) = inv (&n) * &1`] THEN |
| 608 |
REWRITE_TAC[REAL_ABS_MUL; REAL_ABS_ABS] THEN |
| 609 |
MATCH_MP_TAC REAL_LE_MUL2 THEN REWRITE_TAC[REAL_ABS_POS; REAL_ABS_1; REAL_MUL_RID] THEN |
| 610 |
CONJ_TAC THENL [ |
| 611 |
REWRITE_TAC[REAL_ABS_INV; REAL_ABS_NUM] THEN |
| 612 |
MATCH_MP_TAC REAL_LE_INV2 THEN |
| 613 |
REWRITE_TAC[REAL_OF_NUM_LT; REAL_OF_NUM_LE] THEN |
| 614 |
POP_ASSUM MP_TAC THEN ARITH_TAC; |
| 615 |
ALL_TAC |
| 616 |
] THEN |
| 617 |
REWRITE_TAC[REAL_ABS_POW] THEN |
| 618 |
MATCH_MP_TAC REAL_POW_1_LE THEN |
| 619 |
UNDISCH_TAC `&0 <= x /\ x < &1` THEN REAL_ARITH_TAC; |
| 620 |
ALL_TAC |
| 621 |
] THEN |
| 622 |
REWRITE_TAC[REALLIM_1_OVER_N]);; |
| 623 |
|
| 624 |
|
| 625 |
let matan_d2_bound_neg_low = prove(`!x. -- &1 < x /\ x < &0 ==> |
| 626 |
&0 <= real_derivative (real_derivative matan) x`, |
| 627 |
GEN_TAC THEN DISCH_THEN (LABEL_TAC "x") THEN |
| 628 |
MP_TAC (SPEC `x:real` matan_second_derivative_abs1) THEN ANTS_TAC THENL [ |
| 629 |
POP_ASSUM MP_TAC THEN REAL_ARITH_TAC; |
| 630 |
ALL_TAC |
| 631 |
] THEN |
| 632 |
STRIP_TAC THEN |
| 633 |
MATCH_MP_TAC REAL_SERIES_POS THEN |
| 634 |
MAP_EVERY EXISTS_TAC [`\i. (-- &1 pow (i + 2) * &((i + 1) * (i + 2)) / &(2 * i + 5)) * x pow i`; `from 0`] THEN |
| 635 |
ASM_REWRITE_TAC[] THEN REPEAT STRIP_TAC THEN |
| 636 |
REWRITE_TAC[REAL_ARITH `(a * b) * x pow i = (a * x pow i) * b`] THEN |
| 637 |
MATCH_MP_TAC REAL_LE_MUL THEN CONJ_TAC THENL [ |
| 638 |
SUBGOAL_THEN `x pow i = (-- &1) pow i * (--x) pow i` (fun th -> REWRITE_TAC[th]) THENL [ |
| 639 |
REWRITE_TAC[GSYM REAL_POW_MUL; REAL_ARITH `-- &1 * --x = x`]; |
| 640 |
ALL_TAC |
| 641 |
] THEN |
| 642 |
REWRITE_TAC[REAL_MUL_ASSOC; GSYM REAL_POW_ADD; ARITH_RULE `(i + 2) + i = 2 * (i + 1)`] THEN |
| 643 |
MATCH_MP_TAC REAL_LE_MUL THEN CONJ_TAC THENL [ |
| 644 |
REWRITE_TAC[REAL_POW_NEG; EVEN_DOUBLE; REAL_POW_ONE; REAL_LE_01]; |
| 645 |
ALL_TAC |
| 646 |
] THEN |
| 647 |
MATCH_MP_TAC REAL_POW_LE THEN REMOVE_THEN "x" MP_TAC THEN REAL_ARITH_TAC; |
| 648 |
ALL_TAC |
| 649 |
] THEN |
| 650 |
MATCH_MP_TAC REAL_LE_DIV THEN REWRITE_TAC[REAL_POS]);; |
| 651 |
|
| 652 |
|
| 653 |
let matan_d2_bound_neg_high = prove(`!x. -- #0.2 <= x /\ x < &0 ==> |
| 654 |
real_derivative (real_derivative matan) x <= #0.65`, |
| 655 |
GEN_TAC THEN DISCH_THEN (LABEL_TAC "x") THEN |
| 656 |
MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `real_derivative (real_derivative matan) (-- #0.2)` THEN |
| 657 |
CONJ_TAC THENL [ |
| 658 |
MATCH_MP_TAC REAL_SERIES_LE THEN |
| 659 |
MAP_EVERY EXISTS_TAC [`\i. (-- &1 pow (i + 2) * &((i + 1) * (i + 2)) / &(2 * i + 5)) * x pow i`; `\i. (-- &1 pow (i + 2) * &((i + 1) * (i + 2)) / &(2 * i + 5)) * (-- #0.2) pow i`; `from 0`] THEN |
| 660 |
ASM_SIMP_TAC[matan_second_derivative_abs1; REAL_ARITH `-- #0.2 <= x /\ x < &0 ==> abs x < &1`; REAL_ARITH `abs (-- #0.2) < &1`] THEN |
| 661 |
REPEAT STRIP_TAC THEN |
| 662 |
REWRITE_TAC[REAL_ARITH `(a * b) * x pow i = (a * x pow i) * b`] THEN |
| 663 |
SUBGOAL_THEN `!y. -- &1 pow (i + 2) * y pow i = (-- y) pow i` (fun th -> REWRITE_TAC[th]) THENL [ |
| 664 |
REWRITE_TAC[REAL_POW_ADD; REAL_ARITH `-- &1 pow 2 = &1`; REAL_MUL_RID] THEN |
| 665 |
REWRITE_TAC[GSYM REAL_POW_MUL; REAL_ARITH `-- &1 * y = --y`]; |
| 666 |
ALL_TAC |
| 667 |
] THEN |
| 668 |
MATCH_MP_TAC REAL_LE_MUL2 THEN REPEAT STRIP_TAC THENL [ |
| 669 |
MATCH_MP_TAC REAL_POW_LE THEN REMOVE_THEN "x" MP_TAC THEN REAL_ARITH_TAC; |
| 670 |
MATCH_MP_TAC REAL_POW_LE2 THEN REMOVE_THEN "x" MP_TAC THEN REAL_ARITH_TAC; |
| 671 |
MATCH_MP_TAC REAL_LE_DIV THEN REWRITE_TAC[REAL_OF_NUM_LE] THEN ARITH_TAC; |
| 672 |
ALL_TAC |
| 673 |
] THEN |
| 674 |
REWRITE_TAC[REAL_LE_REFL]; |
| 675 |
ALL_TAC |
| 676 |
] THEN |
| 677 |
MP_TAC (SPEC `-- #0.2` matan_second_derivative_abs1_alt) THEN ANTS_TAC THENL [ |
| 678 |
REAL_ARITH_TAC; |
| 679 |
ALL_TAC |
| 680 |
] THEN |
| 681 |
STRIP_TAC THEN ASM_REWRITE_TAC[] THEN |
| 682 |
MATCH_MP_TAC (REAL_ARITH `a <= &15 / &32 /\ b <= (&1 / &5 + &1 / &28) ==> a + (&3 / &4) * b <= #0.65`) THEN |
| 683 |
CONJ_TAC THENL [ REAL_ARITH_TAC; ALL_TAC ] THEN |
| 684 |
MP_TAC (SPECL[`0`; `1`; `\i. -- &1 pow i / &(2 * i + 5) * -- #0.2 pow i`] real_infsum_offset_alt) THEN |
| 685 |
ASM_REWRITE_TAC[ARITH_RULE `0 < 1`; FROM_0] THEN |
| 686 |
DISCH_THEN (fun th -> REWRITE_TAC[th; SUB_REFL; SUM_SING_NUMSEG]) THEN |
| 687 |
REWRITE_TAC[real_pow; MULT_0; ADD; REAL_MUL_RID; REAL_LE_LADD] THEN |
| 688 |
MP_TAC (SPECL[`\i. -- &1 pow i / &(2 * i + 5)`; `-- #0.2`; `1`] power_series_simple_bound2) THEN |
| 689 |
ANTS_TAC THENL [ |
| 690 |
REPEAT STRIP_TAC THEN REWRITE_TAC[] THENL [ |
| 691 |
MATCH_MP_TAC REAL_SUMMABLE_FROM_ELSEWHERE THEN |
| 692 |
EXISTS_TAC `0` THEN ASM_REWRITE_TAC[FROM_0]; |
| 693 |
REWRITE_TAC[REAL_ABS_MUL; abs_neg_one_pow; real_div; REAL_MUL_LID; REAL_ABS_INV] THEN |
| 694 |
MATCH_MP_TAC REAL_LE_INV2 THEN REWRITE_TAC[REAL_ABS_NUM] THEN |
| 695 |
REWRITE_TAC[REAL_OF_NUM_LT; REAL_OF_NUM_LE] THEN ARITH_TAC; |
| 696 |
ALL_TAC |
| 697 |
] THEN |
| 698 |
REAL_ARITH_TAC; |
| 699 |
ALL_TAC |
| 700 |
] THEN |
| 701 |
REWRITE_TAC[ARITH_RULE `2 * 1 + 5 = 7`] THEN |
| 702 |
REAL_ARITH_TAC);; |
| 703 |
|
| 704 |
(* The main bound result *) |
| 705 |
|
| 706 |
let matan_d2_bound = prove(`!x. -- #0.2 <= x ==> |
| 707 |
abs (real_derivative (real_derivative matan) x) <= #0.65`, |
| 708 |
REPEAT STRIP_TAC THEN |
| 709 |
ASM_CASES_TAC `x < &0` THENL [ |
| 710 |
MP_TAC (SPEC `x:real` matan_d2_bound_neg_low) THEN |
| 711 |
MP_TAC (SPEC `x:real` matan_d2_bound_neg_high) THEN |
| 712 |
REPEAT (POP_ASSUM MP_TAC) THEN REAL_ARITH_TAC; |
| 713 |
ALL_TAC |
| 714 |
] THEN |
| 715 |
ASM_CASES_TAC `x < &1` THENL [ |
| 716 |
MP_TAC (SPEC `x:real` matan_d2_bound_01) THEN |
| 717 |
REPEAT (POP_ASSUM MP_TAC) THEN REAL_ARITH_TAC; |
| 718 |
ALL_TAC |
| 719 |
] THEN |
| 720 |
MP_TAC (SPEC `x:real` matan_d2_bound_ge1_low) THEN |
| 721 |
MP_TAC (SPEC `x:real` matan_d2_bound_ge1_high) THEN |
| 722 |
REPEAT (POP_ASSUM MP_TAC) THEN REAL_ARITH_TAC);; |
| 723 |
|
| 724 |
end;; |