src/HOL/Analysis/Weierstrass_Theorems.thy
changeset 70817 dd675800469d
parent 70614 6a2c982363e9
child 71172 575b3a818de5
equal deleted inserted replaced
70816:5bc338cee4a0 70817:dd675800469d
   108         apply (simp add: algebra_simps power2_eq_square)
   108         apply (simp add: algebra_simps power2_eq_square)
   109         done
   109         done
   110       then have "(\<Sum>k\<le>n. (k - n * x)\<^sup>2 * Bernstein n k x)/n^2 = x * (1 - x) / n"
   110       then have "(\<Sum>k\<le>n. (k - n * x)\<^sup>2 * Bernstein n k x)/n^2 = x * (1 - x) / n"
   111         by (simp add: power2_eq_square)
   111         by (simp add: power2_eq_square)
   112       then show ?thesis
   112       then show ?thesis
   113         using n by (simp add: sum_divide_distrib divide_simps mult.commute power2_commute)
   113         using n by (simp add: sum_divide_distrib field_split_simps mult.commute power2_commute)
   114     qed
   114     qed
   115     { fix k
   115     { fix k
   116       assume k: "k \<le> n"
   116       assume k: "k \<le> n"
   117       then have kn: "0 \<le> k / n" "k / n \<le> 1"
   117       then have kn: "0 \<le> k / n" "k / n \<le> 1"
   118         by (auto simp: divide_simps)
   118         by (auto simp: field_split_simps)
   119       consider (lessd) "\<bar>x - k / n\<bar> < d" | (ged) "d \<le> \<bar>x - k / n\<bar>"
   119       consider (lessd) "\<bar>x - k / n\<bar> < d" | (ged) "d \<le> \<bar>x - k / n\<bar>"
   120         by linarith
   120         by linarith
   121       then have "\<bar>(f x - f (k/n))\<bar> \<le> e/2 + 2 * M / d\<^sup>2 * (x - k/n)\<^sup>2"
   121       then have "\<bar>(f x - f (k/n))\<bar> \<le> e/2 + 2 * M / d\<^sup>2 * (x - k/n)\<^sup>2"
   122       proof cases
   122       proof cases
   123         case lessd
   123         case lessd
   156       apply (simp add: divide_simps Mge0 mult_le_one mult_left_le)
   156       apply (simp add: divide_simps Mge0 mult_le_one mult_left_le)
   157       done
   157       done
   158     also have "... < e"
   158     also have "... < e"
   159       apply (simp add: field_simps)
   159       apply (simp add: field_simps)
   160       using \<open>d>0\<close> nbig e \<open>n>0\<close>
   160       using \<open>d>0\<close> nbig e \<open>n>0\<close>
   161       apply (simp add: divide_simps algebra_simps)
   161       apply (simp add: field_split_simps algebra_simps)
   162       using ed0 by linarith
   162       using ed0 by linarith
   163     finally have "\<bar>f x - (\<Sum>k\<le>n. f (real k / real n) * Bernstein n k x)\<bar> < e" .
   163     finally have "\<bar>f x - (\<Sum>k\<le>n. f (real k / real n) * Bernstein n k x)\<bar> < e" .
   164   }
   164   }
   165   then show ?thesis
   165   then show ?thesis
   166     by auto
   166     by auto
   280   have pt_pos: "p t > 0" if t: "t \<in> S-U" for t
   280   have pt_pos: "p t > 0" if t: "t \<in> S-U" for t
   281   proof -
   281   proof -
   282     obtain i where i: "i \<in> subU" "t \<in> Uf i" using subU t by blast
   282     obtain i where i: "i \<in> subU" "t \<in> Uf i" using subU t by blast
   283     show ?thesis
   283     show ?thesis
   284       using subU i t
   284       using subU i t
   285       apply (clarsimp simp: p_def divide_simps)
   285       apply (clarsimp simp: p_def field_split_simps)
   286       apply (rule sum_pos2 [OF \<open>finite subU\<close>])
   286       apply (rule sum_pos2 [OF \<open>finite subU\<close>])
   287       using Uf t pf01 apply auto
   287       using Uf t pf01 apply auto
   288       apply (force elim!: subsetCE)
   288       apply (force elim!: subsetCE)
   289       done
   289       done
   290   qed
   290   qed
   291   have p01: "p x \<in> {0..1}" if t: "x \<in> S" for x
   291   have p01: "p x \<in> {0..1}" if t: "x \<in> S" for x
   292   proof -
   292   proof -
   293     have "0 \<le> p x"
   293     have "0 \<le> p x"
   294       using subU cardp t
   294       using subU cardp t
   295       apply (simp add: p_def divide_simps sum_nonneg)
   295       apply (simp add: p_def field_split_simps sum_nonneg)
   296       apply (rule sum_nonneg)
   296       apply (rule sum_nonneg)
   297       using pf01 by force
   297       using pf01 by force
   298     moreover have "p x \<le> 1"
   298     moreover have "p x \<le> 1"
   299       using subU cardp t
   299       using subU cardp t
   300       apply (simp add: p_def divide_simps sum_nonneg)
   300       apply (simp add: p_def field_split_simps sum_nonneg)
   301       apply (rule sum_bounded_above [where 'a=real and K=1, simplified])
   301       apply (rule sum_bounded_above [where 'a=real and K=1, simplified])
   302       using pf01 by force
   302       using pf01 by force
   303     ultimately show ?thesis
   303     ultimately show ?thesis
   304       by auto
   304       by auto
   305   qed
   305   qed
   329   have "k-1 \<le> 1/\<delta>"
   329   have "k-1 \<le> 1/\<delta>"
   330     using \<delta>01 by (simp add: k_def)
   330     using \<delta>01 by (simp add: k_def)
   331   with \<delta>01 have "k \<le> (1+\<delta>)/\<delta>"
   331   with \<delta>01 have "k \<le> (1+\<delta>)/\<delta>"
   332     by (auto simp: algebra_simps add_divide_distrib)
   332     by (auto simp: algebra_simps add_divide_distrib)
   333   also have "... < 2/\<delta>"
   333   also have "... < 2/\<delta>"
   334     using \<delta>01 by (auto simp: divide_simps)
   334     using \<delta>01 by (auto simp: field_split_simps)
   335   finally have k2\<delta>: "k < 2/\<delta>" .
   335   finally have k2\<delta>: "k < 2/\<delta>" .
   336   have "1/\<delta> < k"
   336   have "1/\<delta> < k"
   337     using \<delta>01 unfolding k_def by linarith
   337     using \<delta>01 unfolding k_def by linarith
   338   with \<delta>01 k2\<delta> have k\<delta>: "1 < k*\<delta>" "k*\<delta> < 2"
   338   with \<delta>01 k2\<delta> have k\<delta>: "1 < k*\<delta>" "k*\<delta> < 2"
   339     by (auto simp: divide_simps)
   339     by (auto simp: field_split_simps)
   340   define q where [abs_def]: "q n t = (1 - p t ^ n) ^ (k^n)" for n t
   340   define q where [abs_def]: "q n t = (1 - p t ^ n) ^ (k^n)" for n t
   341   have qR: "q n \<in> R" for n
   341   have qR: "q n \<in> R" for n
   342     by (simp add: q_def const diff power pR)
   342     by (simp add: q_def const diff power pR)
   343   have q01: "\<And>n t. t \<in> S \<Longrightarrow> q n t \<in> {0..1}"
   343   have q01: "\<And>n t. t \<in> S \<Longrightarrow> q n t \<in> {0..1}"
   344     using p01 by (simp add: q_def power_le_one algebra_simps)
   344     using p01 by (simp add: q_def power_le_one algebra_simps)
   482   moreover
   482   moreover
   483   have pff01: "pff x \<in> {0..1}" if t: "x \<in> S" for x
   483   have pff01: "pff x \<in> {0..1}" if t: "x \<in> S" for x
   484   proof -
   484   proof -
   485     have "0 \<le> pff x"
   485     have "0 \<le> pff x"
   486       using subA cardp t
   486       using subA cardp t
   487       apply (simp add: pff_def divide_simps sum_nonneg)
   487       apply (simp add: pff_def field_split_simps sum_nonneg)
   488       apply (rule Groups_Big.linordered_semidom_class.prod_nonneg)
   488       apply (rule Groups_Big.linordered_semidom_class.prod_nonneg)
   489       using ff by fastforce
   489       using ff by fastforce
   490     moreover have "pff x \<le> 1"
   490     moreover have "pff x \<le> 1"
   491       using subA cardp t
   491       using subA cardp t
   492       apply (simp add: pff_def divide_simps sum_nonneg)
   492       apply (simp add: pff_def field_split_simps sum_nonneg)
   493       apply (rule prod_mono [where g = "\<lambda>x. 1", simplified])
   493       apply (rule prod_mono [where g = "\<lambda>x. 1", simplified])
   494       using ff by fastforce
   494       using ff by fastforce
   495     ultimately show ?thesis
   495     ultimately show ?thesis
   496       by auto
   496       by auto
   497   qed
   497   qed
   510       using atLeastAtMost_iff by blast
   510       using atLeastAtMost_iff by blast
   511     also have "... < e / card subA"
   511     also have "... < e / card subA"
   512       using ff [THEN conjunct2, THEN conjunct2, THEN conjunct1] v subA x
   512       using ff [THEN conjunct2, THEN conjunct2, THEN conjunct1] v subA x
   513       by auto
   513       by auto
   514     also have "... \<le> e"
   514     also have "... \<le> e"
   515       using cardp e by (simp add: divide_simps)
   515       using cardp e by (simp add: field_split_simps)
   516     finally have "pff x < e" .
   516     finally have "pff x < e" .
   517   }
   517   }
   518   then have "\<And>x. x \<in> A \<Longrightarrow> pff x < e"
   518   then have "\<And>x. x \<in> A \<Longrightarrow> pff x < e"
   519     using A Vf subA by (metis UN_E contra_subsetD)
   519     using A Vf subA by (metis UN_E contra_subsetD)
   520   moreover
   520   moreover
   530     also have "... < pff x"
   530     also have "... < pff x"
   531       apply (simp add: pff_def)
   531       apply (simp add: pff_def)
   532       apply (rule prod_mono_strict [where f = "\<lambda>x. 1 - e / card subA", simplified])
   532       apply (rule prod_mono_strict [where f = "\<lambda>x. 1 - e / card subA", simplified])
   533       apply (simp_all add: subA(2))
   533       apply (simp_all add: subA(2))
   534       apply (intro ballI conjI)
   534       apply (intro ballI conjI)
   535       using e apply (force simp: divide_simps)
   535       using e apply (force simp: field_split_simps)
   536       using ff [THEN conjunct2, THEN conjunct2, THEN conjunct2] subA B x
   536       using ff [THEN conjunct2, THEN conjunct2, THEN conjunct2] subA B x
   537       apply blast
   537       apply blast
   538       done
   538       done
   539     finally have "1 - e < pff x" .
   539     finally have "1 - e < pff x" .
   540   }
   540   }