src/HOL/Multivariate_Analysis/Linear_Algebra.thy
changeset 61609 77b453bd616f
parent 61520 8f85bb443d33
child 61808 fc1556774cfe
equal deleted inserted replaced
61553:933eb9e6a1cc 61609:77b453bd616f
   568 
   568 
   569 
   569 
   570 subsection \<open>Archimedean properties and useful consequences\<close>
   570 subsection \<open>Archimedean properties and useful consequences\<close>
   571 
   571 
   572 lemma real_arch_simple: "\<exists>n::nat. x \<le> real n"
   572 lemma real_arch_simple: "\<exists>n::nat. x \<le> real n"
   573   unfolding real_of_nat_def by (rule ex_le_of_nat)
   573   by (rule ex_le_of_nat)
   574 
   574 
   575 lemma real_arch_inv: "0 < e \<longleftrightarrow> (\<exists>n::nat. n \<noteq> 0 \<and> 0 < inverse (real n) \<and> inverse (real n) < e)"
   575 lemma real_arch_inv: "0 < e \<longleftrightarrow> (\<exists>n::nat. n \<noteq> 0 \<and> 0 < inverse (real n) \<and> inverse (real n) < e)"
   576   using reals_Archimedean[of e] less_trans[of 0 "1 / real n" e for n::nat]
   576   using reals_Archimedean[of e] less_trans[of 0 "1 / real n" e for n::nat]
   577   by (auto simp add: field_simps cong: conj_cong simp del: real_of_nat_Suc)
   577   by (auto simp add: field_simps cong: conj_cong simp del: of_nat_Suc)
   578 
   578 
   579 text\<open>Bernoulli's inequality\<close>
   579 text\<open>Bernoulli's inequality\<close>
   580 lemma Bernoulli_inequality:
   580 lemma Bernoulli_inequality:
   581   fixes x :: real
   581   fixes x :: real
   582   assumes "-1 \<le> x"
   582   assumes "-1 \<le> x"
   587 next
   587 next
   588   case (Suc n)
   588   case (Suc n)
   589   have "1 + Suc n * x \<le> 1 + (Suc n)*x + n * x^2"
   589   have "1 + Suc n * x \<le> 1 + (Suc n)*x + n * x^2"
   590     by (simp add: algebra_simps)
   590     by (simp add: algebra_simps)
   591   also have "... = (1 + x) * (1 + n*x)"
   591   also have "... = (1 + x) * (1 + n*x)"
   592     by (auto simp: power2_eq_square algebra_simps  real_of_nat_Suc)
   592     by (auto simp: power2_eq_square algebra_simps  of_nat_Suc)
   593   also have "... \<le> (1 + x) ^ Suc n"
   593   also have "... \<le> (1 + x) ^ Suc n"
   594     using Suc.hyps assms mult_left_mono by fastforce
   594     using Suc.hyps assms mult_left_mono by fastforce
   595   finally show ?case .
   595   finally show ?case .
   596 qed
   596 qed
   597 
   597 
   666 lemma forall_pos_mono_1:
   666 lemma forall_pos_mono_1:
   667   "(\<And>d e::real. d < e \<Longrightarrow> P d \<Longrightarrow> P e) \<Longrightarrow>
   667   "(\<And>d e::real. d < e \<Longrightarrow> P d \<Longrightarrow> P e) \<Longrightarrow>
   668     (\<And>n. P (inverse (real (Suc n)))) \<Longrightarrow> 0 < e \<Longrightarrow> P e"
   668     (\<And>n. P (inverse (real (Suc n)))) \<Longrightarrow> 0 < e \<Longrightarrow> P e"
   669   apply (rule forall_pos_mono)
   669   apply (rule forall_pos_mono)
   670   apply auto
   670   apply auto
   671   apply (metis Suc_pred real_of_nat_Suc)
   671   apply (metis Suc_pred of_nat_Suc)
   672   done
   672   done
   673 
   673 
   674 lemma real_archimedian_rdiv_eq_0:
   674 lemma real_archimedian_rdiv_eq_0:
   675   assumes x0: "x \<ge> 0"
   675   assumes x0: "x \<ge> 0"
   676     and c: "c \<ge> 0"
   676     and c: "c \<ge> 0"
  1459     also have "\<dots> \<le> e + e"
  1459     also have "\<dots> \<le> e + e"
  1460       unfolding real_norm_def
  1460       unfolding real_norm_def
  1461       by (intro add_mono norm_bound_Basis_le i fPs) auto
  1461       by (intro add_mono norm_bound_Basis_le i fPs) auto
  1462     finally show "(\<Sum>x\<in>P. \<bar>f x \<bullet> i\<bar>) \<le> 2*e" by simp
  1462     finally show "(\<Sum>x\<in>P. \<bar>f x \<bullet> i\<bar>) \<le> 2*e" by simp
  1463   qed
  1463   qed
  1464   also have "\<dots> = 2 * real DIM('n) * e"
  1464   also have "\<dots> = 2 * real DIM('n) * e" by simp
  1465     by (simp add: real_of_nat_def)
       
  1466   finally show ?thesis .
  1465   finally show ?thesis .
  1467 qed
  1466 qed
  1468 
  1467 
  1469 
  1468 
  1470 subsection \<open>Linearity and Bilinearity continued\<close>
  1469 subsection \<open>Linearity and Bilinearity continued\<close>
  1627 lemma independent_bound:
  1626 lemma independent_bound:
  1628   fixes S :: "'a::euclidean_space set"
  1627   fixes S :: "'a::euclidean_space set"
  1629   shows "independent S \<Longrightarrow> finite S \<and> card S \<le> DIM('a)"
  1628   shows "independent S \<Longrightarrow> finite S \<and> card S \<le> DIM('a)"
  1630   using independent_span_bound[OF finite_Basis, of S] by auto
  1629   using independent_span_bound[OF finite_Basis, of S] by auto
  1631 
  1630 
  1632 corollary 
  1631 corollary
  1633   fixes S :: "'a::euclidean_space set"
  1632   fixes S :: "'a::euclidean_space set"
  1634   assumes "independent S"
  1633   assumes "independent S"
  1635   shows independent_imp_finite: "finite S" and independent_card_le:"card S \<le> DIM('a)"
  1634   shows independent_imp_finite: "finite S" and independent_card_le:"card S \<le> DIM('a)"
  1636 using assms independent_bound by auto
  1635 using assms independent_bound by auto
  1637   
  1636 
  1638 lemma dependent_biggerset:
  1637 lemma dependent_biggerset:
  1639   fixes S :: "'a::euclidean_space set"
  1638   fixes S :: "'a::euclidean_space set"
  1640   shows "(finite S \<Longrightarrow> card S > DIM('a)) \<Longrightarrow> dependent S"
  1639   shows "(finite S \<Longrightarrow> card S > DIM('a)) \<Longrightarrow> dependent S"
  1641   by (metis independent_bound not_less)
  1640   by (metis independent_bound not_less)
  1642 
  1641 
  2854     by (auto intro: real_sqrt_pow2)
  2853     by (auto intro: real_sqrt_pow2)
  2855   have th: "sqrt (real ?d) * infnorm x \<ge> 0"
  2854   have th: "sqrt (real ?d) * infnorm x \<ge> 0"
  2856     by (simp add: zero_le_mult_iff infnorm_pos_le)
  2855     by (simp add: zero_le_mult_iff infnorm_pos_le)
  2857   have th1: "x \<bullet> x \<le> (sqrt (real ?d) * infnorm x)\<^sup>2"
  2856   have th1: "x \<bullet> x \<le> (sqrt (real ?d) * infnorm x)\<^sup>2"
  2858     unfolding power_mult_distrib d2
  2857     unfolding power_mult_distrib d2
  2859     unfolding real_of_nat_def
       
  2860     apply (subst euclidean_inner)
  2858     apply (subst euclidean_inner)
  2861     apply (subst power2_abs[symmetric])
  2859     apply (subst power2_abs[symmetric])
  2862     apply (rule order_trans[OF setsum_bounded_above[where K="\<bar>infnorm x\<bar>\<^sup>2"]])
  2860     apply (rule order_trans[OF setsum_bounded_above[where K="\<bar>infnorm x\<bar>\<^sup>2"]])
  2863     apply (auto simp add: power2_eq_square[symmetric])
  2861     apply (auto simp add: power2_eq_square[symmetric])
  2864     apply (subst power2_abs[symmetric])
  2862     apply (subst power2_abs[symmetric])