Debian Codegraph @

Formal_ineqs/trig/sin_cos.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 functions: sin, cos (theory) *)
11 (* -------------------------------------------------------------------------- *)
12
13 module Sin_cos = struct
14
15 prioritize_real();;
16
17 (* cos *)
18
19 let cos_pi_2 = prove(`!x. cos (x + pi / &2) = --sin x`,
20 REWRITE_TAC[COS_SIN; REAL_ARITH `a - (b + a) = --b:real`; SIN_NEG]);;
21
22 let cos_derivatives = prove(`!x n. ((\x. cos (x + &n * pi / &2))
23 has_real_derivative cos (x + &(n + 1) * pi / &2)) (atreal x)`,
24 REPEAT GEN_TAC THEN REAL_DIFF_TAC THEN
25 REWRITE_TAC[REAL_ARITH `(&1 + &0) * --a = --a`] THEN
26 REWRITE_TAC[GSYM REAL_OF_NUM_ADD] THEN
27 REWRITE_TAC[REAL_ARITH `x + (a + &1) * t = (x + a * t) + t`] THEN
28 REWRITE_TAC[cos_pi_2]);;
29
30 let taylor_cos_raw = prove(`!x n.
31 abs (cos x - sum (0..n) (\k. if (EVEN k) then ((-- &1) pow (k DIV 2) * x pow k) / &(FACT k) else &0))
32 <= abs x pow (n + 1) / &(FACT (n + 1))`,
33 REPEAT GEN_TAC THEN
34 MP_TAC (SPECL [`(\i x. cos (x + &i * pi / &2))`; `n:num`; `(:real)`; `&1`] REAL_TAYLOR) THEN
35 ANTS_TAC THENL
36 [
37 REWRITE_TAC[is_realinterval; IN_UNIV; WITHINREAL_UNIV; cos_derivatives; COS_BOUND];
38 ALL_TAC
39 ] THEN
40 REWRITE_TAC[IN_UNIV] THEN
41 DISCH_THEN (MP_TAC o SPECL [`&0`; `x:real`]) THEN
42 REWRITE_TAC[REAL_MUL_LZERO; REAL_ADD_RID; REAL_ADD_LID; REAL_SUB_RZERO; REAL_MUL_LID] THEN
43 SUBGOAL_THEN `!i. cos (&i * pi / &2) * x pow i / &(FACT i) = if EVEN i then (-- &1 pow (i DIV 2) * x pow i) / &(FACT i) else &0` (fun th -> SIMP_TAC[th]) THEN
44 GEN_TAC THEN
45 ASM_CASES_TAC `EVEN i` THEN ASM_REWRITE_TAC[] THENL
46 [
47 POP_ASSUM MP_TAC THEN
48 REWRITE_TAC[EVEN_EXISTS] THEN
49 STRIP_TAC THEN ASM_REWRITE_TAC[] THEN
50 SUBGOAL_THEN `(2 * m) DIV 2 = m` (fun th -> REWRITE_TAC[th]) THENL
51 [
52 MATCH_MP_TAC DIV_MULT THEN
53 ARITH_TAC;
54 ALL_TAC
55 ] THEN
56 REWRITE_TAC[GSYM REAL_OF_NUM_MUL] THEN
57 REWRITE_TAC[REAL_ARITH `(&2 * a) * b / &2 = a * b`] THEN
58 REWRITE_TAC[COS_NPI] THEN
59 REAL_ARITH_TAC;
60 ALL_TAC
61 ] THEN
62 SUBGOAL_THEN `cos (&i * pi / &2) = &0` (fun th -> REWRITE_TAC[th]) THENL
63 [
64 REWRITE_TAC[COS_ZERO] THEN
65 DISJ1_TAC THEN EXISTS_TAC `i:num` THEN
66 ASM_REWRITE_TAC[];
67 ALL_TAC
68 ] THEN
69 REWRITE_TAC[REAL_MUL_LZERO]);;
70
71
72 let sum_pair_from_0 = prove(`!f n. sum (0..2 * n + 1) f = sum(0..n) (\i. f (2 * i) + f (2 * i + 1))`,
73 REPEAT GEN_TAC THEN
74 MP_TAC (SPECL [`f:num->real`; `0`; `n:num`] SUM_PAIR) THEN
75 REWRITE_TAC[ARITH_RULE `2 * 0 = 0`]);;
76
77 let taylor_cos = prove(`!x n. abs (cos x -
78 sum (0..n) (\i. ((-- &1) pow i / &(FACT (2 * i))) * x pow (2 * i)))
79 <= abs x pow (2*n + 2) / &(FACT (2*n + 2))`,
80 REPEAT GEN_TAC THEN
81 MP_TAC (SPECL [`x:real`; `2 * n + 1`] taylor_cos_raw) THEN
82 REWRITE_TAC[sum_pair_from_0; EVEN_DOUBLE; ARITH_RULE `(2 * n + 1) + 1 = 2 *n + 2`] THEN
83 SUBGOAL_THEN `!i. ~(EVEN (2 * i + 1))` MP_TAC THENL
84 [
85 GEN_TAC THEN REWRITE_TAC[NOT_EVEN] THEN
86 REWRITE_TAC[ARITH_ODD; ODD_ADD; ODD_MULT];
87 ALL_TAC
88 ] THEN
89 DISCH_THEN (fun th -> SIMP_TAC[th]) THEN
90 SUBGOAL_THEN `!i. (2 * i) DIV 2 = i` MP_TAC THENL
91 [
92 GEN_TAC THEN
93 MATCH_MP_TAC DIV_MULT THEN
94 REWRITE_TAC[ARITH];
95 ALL_TAC
96 ] THEN
97 DISCH_THEN (fun th -> REWRITE_TAC[th; REAL_ADD_RID]) THEN
98 REWRITE_TAC[REAL_ARITH `(a * b) / c = (a / c) * b:real`]);;
99
100
101 let cos_poly_upper_bound = prove(`!x n. EVEN n ==>
102 cos x <= sum(0..n) (\i. ((-- &1) pow i / &(FACT (2 * i))) * x pow (2 * i))`,
103 REPEAT STRIP_TAC THEN
104 ASM_CASES_TAC `n = 0` THENL [
105 ASM_REWRITE_TAC[SUM_SING_NUMSEG] THEN
106 CONV_TAC NUM_REDUCE_CONV THEN REWRITE_TAC[real_pow] THEN
107 CONV_TAC REAL_RAT_REDUCE_CONV THEN REWRITE_TAC[COS_BOUNDS];
108 ALL_TAC
109 ] THEN
110 ASM_SIMP_TAC[ARITH_RULE `~(n = 0) ==> 0 < n`; ARITH_RULE `0 <= n`; SUM_CLAUSES_RIGHT] THEN
111 MP_TAC (SPECL[`x:real`; `n - 1`] taylor_cos) THEN
112 SUBGOAL_THEN `-- &1 pow n = &1` (fun th -> REWRITE_TAC[th]) THENL [
113 ASM_REWRITE_TAC[REAL_POW_NEG; REAL_POW_ONE];
114 ALL_TAC
115 ] THEN
116 ASM_SIMP_TAC[ARITH_RULE `~(n = 0) ==> 2 * (n - 1) + 2 = 2 * n`] THEN
117 REWRITE_TAC[REAL_ARITH `&1 / a * b = b / a`] THEN
118 SUBGOAL_THEN `abs x pow (2 * n) = x pow (2 * n)` (fun th -> REWRITE_TAC[th]) THENL [
119 REWRITE_TAC[REAL_POW_EQ_EQ; EVEN_DOUBLE; REAL_ABS_ABS];
120 ALL_TAC
121 ] THEN
122 REAL_ARITH_TAC);;
123
124
125 let cos_poly_lower_bound = prove(`!x n. ODD n ==>
126 sum(0..n) (\i. ((-- &1) pow i / &(FACT (2 * i))) * x pow (2 * i)) <= cos x`,
127 REWRITE_TAC[GSYM NOT_EVEN] THEN REPEAT STRIP_TAC THEN
128 ASM_CASES_TAC `n = 0` THENL [
129 UNDISCH_TAC `~EVEN n` THEN ASM_REWRITE_TAC[EVEN];
130 ALL_TAC
131 ] THEN
132 ASM_SIMP_TAC[ARITH_RULE `~(n = 0) ==> 0 < n`; ARITH_RULE `0 <= n`; SUM_CLAUSES_RIGHT] THEN
133 MP_TAC (SPECL[`x:real`; `n - 1`] taylor_cos) THEN
134 SUBGOAL_THEN `-- &1 pow n = -- &1` (fun th -> REWRITE_TAC[th]) THENL [
135 ASM_REWRITE_TAC[REAL_POW_NEG; REAL_POW_ONE];
136 ALL_TAC
137 ] THEN
138 ASM_SIMP_TAC[ARITH_RULE `~(n = 0) ==> 2 * (n - 1) + 2 = 2 * n`] THEN
139 REWRITE_TAC[REAL_ARITH `-- &1 / a * b = -- b / a`] THEN
140 SUBGOAL_THEN `abs x pow (2 * n) = x pow (2 * n)` (fun th -> REWRITE_TAC[th]) THENL [
141 REWRITE_TAC[REAL_POW_EQ_EQ; EVEN_DOUBLE; REAL_ABS_ABS];
142 ALL_TAC
143 ] THEN
144 REAL_ARITH_TAC);;
145
146
147 (* sin *)
148
149 let sin_pi_2 = prove(`!x. sin (x + pi / &2) = cos x`,
150 REWRITE_TAC[SIN_COS; REAL_ARITH `a - (b + a) = --b:real`; COS_NEG]);;
151
152 let sin_derivatives = prove(`!x n. ((\x. sin (x + &n * pi / &2))
153 has_real_derivative sin (x + &(n + 1) * pi / &2)) (atreal x)`,
154 REPEAT GEN_TAC THEN REAL_DIFF_TAC THEN
155 REWRITE_TAC[REAL_ARITH `(&1 + &0) * a = a`] THEN
156 REWRITE_TAC[GSYM REAL_OF_NUM_ADD] THEN
157 REWRITE_TAC[REAL_ARITH `x + (a + &1) * t = (x + a * t) + t`] THEN
158 REWRITE_TAC[sin_pi_2]);;
159
160 let taylor_sin_raw = prove(`!x n.
161 abs (sin x - sum (0..n) (\k. if (ODD k) then ((-- &1) pow (k DIV 2) * x pow k) / &(FACT k) else &0))
162 <= abs x pow (n + 1) / &(FACT (n + 1))`,
163 REPEAT GEN_TAC THEN
164 MP_TAC (SPECL [`(\i x. sin (x + &i * pi / &2))`; `n:num`; `(:real)`; `&1`] REAL_TAYLOR) THEN
165 ANTS_TAC THENL
166 [
167 REWRITE_TAC[is_realinterval; IN_UNIV; WITHINREAL_UNIV; sin_derivatives; SIN_BOUND];
168 ALL_TAC
169 ] THEN
170 REWRITE_TAC[IN_UNIV] THEN
171 DISCH_THEN (MP_TAC o SPECL [`&0`; `x:real`]) THEN
172 REWRITE_TAC[REAL_MUL_LZERO; REAL_ADD_RID; REAL_ADD_LID; REAL_SUB_RZERO; REAL_MUL_LID] THEN
173 SUBGOAL_THEN `!i. sin (&i * pi / &2) * x pow i / &(FACT i) = if ODD i then (-- &1 pow (i DIV 2) * x pow i) / &(FACT i) else &0` (fun th -> SIMP_TAC[th]) THEN
174 GEN_TAC THEN
175 ASM_CASES_TAC `ODD i` THEN ASM_REWRITE_TAC[] THENL
176 [
177 POP_ASSUM MP_TAC THEN
178 REWRITE_TAC[ODD_EXISTS] THEN STRIP_TAC THEN ASM_REWRITE_TAC[] THEN
179 SUBGOAL_THEN `(SUC (2 * m)) DIV 2 = m` (fun th -> REWRITE_TAC[th]) THENL [
180 REWRITE_TAC[ADD1; ARITH_RULE `2 * m = m * 2`] THEN
181 SIMP_TAC[DIV_MULT_ADD; ARITH_RULE `~(2 = 0)`; DIV_LT; ARITH_RULE `1 < 2`; ADD_0];
182 ALL_TAC
183 ] THEN
184 REWRITE_TAC[GSYM REAL_OF_NUM_MUL; GSYM REAL_OF_NUM_SUC] THEN
185 REWRITE_TAC[REAL_ARITH `(&2 * a + &1) * b / &2 = a * b + b / &2`; sin_pi_2] THEN
186 REWRITE_TAC[COS_NPI] THEN
187 REAL_ARITH_TAC;
188 ALL_TAC
189 ] THEN
190 SUBGOAL_THEN `sin (&i * pi / &2) = &0` (fun th -> REWRITE_TAC[th]) THENL
191 [
192 REWRITE_TAC[SIN_ZERO] THEN
193 DISJ1_TAC THEN EXISTS_TAC `i:num` THEN
194 ASM_REWRITE_TAC[GSYM NOT_ODD];
195 ALL_TAC
196 ] THEN
197 REWRITE_TAC[REAL_MUL_LZERO]);;
198
199
200 let taylor_sin = prove(`!x n. abs (sin x -
201 sum (0..n) (\i. ((-- &1) pow i / &(FACT (2 * i + 1))) * x pow (2 * i + 1)))
202 <= abs x pow (2 * n + 3) / &(FACT (2 * n + 3))`,
203 REPEAT GEN_TAC THEN
204 MP_TAC (SPECL [`x:real`; `2 * n + 2`] taylor_sin_raw) THEN
205 SUBGOAL_THEN `!f. sum (0..2 * n + 2) (\k. if ODD k then f k else &0) = sum (0..2 * n + 1) (\k. if ODD k then f k else &0)` (fun th -> REWRITE_TAC[th]) THENL [
206 GEN_TAC THEN REWRITE_TAC[ARITH_RULE `a + 2 = SUC (a + 1)`] THEN
207 REWRITE_TAC[SUM_CLAUSES_NUMSEG; ARITH_RULE `0 <= SUC k`] THEN
208 SUBGOAL_THEN `~(ODD (SUC (2 * n + 1)))` (fun th -> REWRITE_TAC[th; REAL_ADD_RID]) THEN
209 REWRITE_TAC[ODD; ODD_EXISTS] THEN
210 EXISTS_TAC `n:num` THEN ARITH_TAC;
211 ALL_TAC
212 ] THEN
213 REWRITE_TAC[sum_pair_from_0; ARITH_RULE `2 * i + 1 = SUC (2 * i)`; ODD_DOUBLE] THEN
214 SUBGOAL_THEN `!i. ~(ODD (2 * i))` (fun th -> SIMP_TAC[th]) THENL [
215 REWRITE_TAC[NOT_ODD; EVEN_DOUBLE];
216 ALL_TAC
217 ] THEN
218 SUBGOAL_THEN `!i. SUC (2 * i) DIV 2 = i` MP_TAC THENL
219 [
220 REWRITE_TAC[ADD1; ARITH_RULE `2 * m = m * 2`] THEN
221 SIMP_TAC[DIV_MULT_ADD; ARITH_RULE `~(2 = 0)`; DIV_LT; ARITH_RULE `1 < 2`; ADD_0];
222 ALL_TAC
223 ] THEN
224 DISCH_THEN (fun th -> REWRITE_TAC[th; REAL_ADD_LID]) THEN
225 REWRITE_TAC[REAL_ARITH `(a * b) / c = (a / c) * b:real`] THEN
226 REWRITE_TAC[ARITH_RULE `(2 * n + 2) + 1 = 2 * n + 3`]);;
227
228
229 let sin_pos_poly_upper_bound = prove(`!x n. &0 <= x /\ EVEN n ==>
230 sin x <= sum(0..n) (\i. ((-- &1) pow i / &(FACT (2 * i + 1))) * x pow (2 * i + 1))`,
231 REPEAT STRIP_TAC THEN
232 ASM_CASES_TAC `n = 0` THENL [
233 MP_TAC (SPECL[`x:real`; `0`] taylor_sin_raw) THEN
234 ASM_REWRITE_TAC[SUM_SING_NUMSEG; ODD] THEN
235 CONV_TAC NUM_REDUCE_CONV THEN REWRITE_TAC[real_pow; REAL_POW_1] THEN
236 CONV_TAC REAL_RAT_REDUCE_CONV THEN REWRITE_TAC[REAL_MUL_LID; REAL_DIV_1] THEN
237 UNDISCH_TAC `&0 <= x` THEN REAL_ARITH_TAC;
238 ALL_TAC
239 ] THEN
240 ASM_SIMP_TAC[ARITH_RULE `~(n = 0) ==> 0 < n`; ARITH_RULE `0 <= n`; SUM_CLAUSES_RIGHT] THEN
241 MP_TAC (SPECL[`x:real`; `n - 1`] taylor_sin) THEN
242 SUBGOAL_THEN `-- &1 pow n = &1` (fun th -> REWRITE_TAC[th]) THENL [
243 ASM_REWRITE_TAC[REAL_POW_NEG; REAL_POW_ONE];
244 ALL_TAC
245 ] THEN
246 ASM_SIMP_TAC[ARITH_RULE `~(n = 0) ==> 2 * (n - 1) + 3 = 2 * n + 1`] THEN
247 REWRITE_TAC[REAL_ARITH `&1 / a * b = b / a`] THEN
248 SUBGOAL_THEN `abs x pow (2 * n + 1) = x pow (2 * n + 1)` (fun th -> REWRITE_TAC[th]) THENL [
249 ASM_REWRITE_TAC[REAL_POW_EQ_EQ; GSYM ADD1; EVEN; EVEN_DOUBLE; REAL_ABS_REFL];
250 ALL_TAC
251 ] THEN
252 REAL_ARITH_TAC);;
253
254
255 let sin_pos_poly_lower_bound = prove(`!x n. &0 <= x /\ ODD n ==>
256 sum(0..n) (\i. ((-- &1) pow i / &(FACT (2 * i + 1))) * x pow (2 * i + 1)) <= sin x`,
257 REWRITE_TAC[GSYM NOT_EVEN] THEN REPEAT STRIP_TAC THEN
258 ASM_CASES_TAC `n = 0` THENL [
259 UNDISCH_TAC `~EVEN n` THEN ASM_REWRITE_TAC[EVEN];
260 ALL_TAC
261 ] THEN
262 ASM_SIMP_TAC[ARITH_RULE `~(n = 0) ==> 0 < n`; ARITH_RULE `0 <= n`; SUM_CLAUSES_RIGHT] THEN
263 MP_TAC (SPECL[`x:real`; `n - 1`] taylor_sin) THEN
264 SUBGOAL_THEN `-- &1 pow n = -- &1` (fun th -> REWRITE_TAC[th]) THENL [
265 ASM_REWRITE_TAC[REAL_POW_NEG; REAL_POW_ONE];
266 ALL_TAC
267 ] THEN
268 ASM_SIMP_TAC[ARITH_RULE `~(n = 0) ==> 2 * (n - 1) + 3 = 2 * n + 1`] THEN
269 REWRITE_TAC[REAL_ARITH `-- &1 / a * b = -- b / a`] THEN
270 SUBGOAL_THEN `abs x pow (2 * n + 1) = x pow (2 * n + 1)` (fun th -> REWRITE_TAC[th]) THENL [
271 ASM_REWRITE_TAC[REAL_POW_EQ_EQ; GSYM ADD1; EVEN; EVEN_DOUBLE; REAL_ABS_REFL];
272 ALL_TAC
273 ] THEN
274 REAL_ARITH_TAC);;
275
276
277 let sin_neg_poly_upper_bound = prove(`!x n. x <= &0 /\ ODD n ==>
278 sin x <= sum(0..n) (\i. ((-- &1) pow i / &(FACT (2 * i + 1))) * x pow (2 * i + 1))`,
279 REPEAT STRIP_TAC THEN
280 SUBGOAL_THEN `&0 <= --x` ASSUME_TAC THENL [
281 POP_ASSUM MP_TAC THEN POP_ASSUM MP_TAC THEN REAL_ARITH_TAC;
282 ALL_TAC
283 ] THEN
284 MP_TAC (SPECL[`--x`; `n:num`] sin_pos_poly_lower_bound) THEN
285 ASM_REWRITE_TAC[SIN_NEG] THEN
286 SUBGOAL_THEN `!x i. --x pow (2 * i + 1) = --(x pow (2 * i + 1))` (fun th -> REWRITE_TAC[th]) THENL [
287 REWRITE_TAC[REAL_POW_NEG; GSYM ADD1; EVEN; EVEN_DOUBLE];
288 ALL_TAC
289 ] THEN
290 REWRITE_TAC[REAL_ARITH `a * (--b) = --(a * b)`] THEN
291 REWRITE_TAC[SUM_NEG; REAL_LE_NEG2]);;
292
293
294 let sin_neg_poly_lower_bound = prove(`!x n. x <= &0 /\ EVEN n ==>
295 sum(0..n) (\i. ((-- &1) pow i / &(FACT (2 * i + 1))) * x pow (2 * i + 1)) <= sin x`,
296 REPEAT STRIP_TAC THEN
297 SUBGOAL_THEN `&0 <= --x` ASSUME_TAC THENL [
298 POP_ASSUM MP_TAC THEN POP_ASSUM MP_TAC THEN REAL_ARITH_TAC;
299 ALL_TAC
300 ] THEN
301 MP_TAC (SPECL[`--x`; `n:num`] sin_pos_poly_upper_bound) THEN
302 ASM_REWRITE_TAC[SIN_NEG] THEN
303 SUBGOAL_THEN `!x i. --x pow (2 * i + 1) = --(x pow (2 * i + 1))` (fun th -> REWRITE_TAC[th]) THENL [
304 REWRITE_TAC[REAL_POW_NEG; GSYM ADD1; EVEN; EVEN_DOUBLE];
305 ALL_TAC
306 ] THEN
307 REWRITE_TAC[REAL_ARITH `a * (--b) = --(a * b)`] THEN
308 REWRITE_TAC[SUM_NEG; REAL_LE_NEG2]);;
309
310 end;;