changeset 70136 | f03a01a18c6e |
parent 69683 | 8b3458ca0762 |
child 70688 | 3d894e1cfc75 |
70135:ad6d4a14adb5 | 70136:f03a01a18c6e |
---|---|
102 then have "x \<in> ((\<lambda>x. a+x) ` S)" by auto |
102 then have "x \<in> ((\<lambda>x. a+x) ` S)" by auto |
103 } |
103 } |
104 then show ?thesis by auto |
104 then show ?thesis by auto |
105 qed |
105 qed |
106 |
106 |
107 subsection%unimportant \<open>More interesting properties of the norm\<close> |
107 subsection\<^marker>\<open>tag unimportant\<close> \<open>More interesting properties of the norm\<close> |
108 |
108 |
109 unbundle inner_syntax |
109 unbundle inner_syntax |
110 |
110 |
111 text\<open>Equality of vectors in terms of \<^term>\<open>(\<bullet>)\<close> products.\<close> |
111 text\<open>Equality of vectors in terms of \<^term>\<open>(\<bullet>)\<close> products.\<close> |
112 |
112 |
228 qed simp |
228 qed simp |
229 |
229 |
230 |
230 |
231 subsection \<open>Orthogonality\<close> |
231 subsection \<open>Orthogonality\<close> |
232 |
232 |
233 definition%important (in real_inner) "orthogonal x y \<longleftrightarrow> x \<bullet> y = 0" |
233 definition\<^marker>\<open>tag important\<close> (in real_inner) "orthogonal x y \<longleftrightarrow> x \<bullet> y = 0" |
234 |
234 |
235 context real_inner |
235 context real_inner |
236 begin |
236 begin |
237 |
237 |
238 lemma orthogonal_self: "orthogonal x x \<longleftrightarrow> x = 0" |
238 lemma orthogonal_self: "orthogonal x x \<longleftrightarrow> x = 0" |
297 qed |
297 qed |
298 |
298 |
299 |
299 |
300 subsection \<open>Orthogonality of a transformation\<close> |
300 subsection \<open>Orthogonality of a transformation\<close> |
301 |
301 |
302 definition%important "orthogonal_transformation f \<longleftrightarrow> linear f \<and> (\<forall>v w. f v \<bullet> f w = v \<bullet> w)" |
302 definition\<^marker>\<open>tag important\<close> "orthogonal_transformation f \<longleftrightarrow> linear f \<and> (\<forall>v w. f v \<bullet> f w = v \<bullet> w)" |
303 |
303 |
304 lemma%unimportant orthogonal_transformation: |
304 lemma\<^marker>\<open>tag unimportant\<close> orthogonal_transformation: |
305 "orthogonal_transformation f \<longleftrightarrow> linear f \<and> (\<forall>v. norm (f v) = norm v)" |
305 "orthogonal_transformation f \<longleftrightarrow> linear f \<and> (\<forall>v. norm (f v) = norm v)" |
306 unfolding orthogonal_transformation_def |
306 unfolding orthogonal_transformation_def |
307 apply auto |
307 apply auto |
308 apply (erule_tac x=v in allE)+ |
308 apply (erule_tac x=v in allE)+ |
309 apply (simp add: norm_eq_sqrt_inner) |
309 apply (simp add: norm_eq_sqrt_inner) |
310 apply (simp add: dot_norm linear_add[symmetric]) |
310 apply (simp add: dot_norm linear_add[symmetric]) |
311 done |
311 done |
312 |
312 |
313 lemma%unimportant orthogonal_transformation_id [simp]: "orthogonal_transformation (\<lambda>x. x)" |
313 lemma\<^marker>\<open>tag unimportant\<close> orthogonal_transformation_id [simp]: "orthogonal_transformation (\<lambda>x. x)" |
314 by (simp add: linear_iff orthogonal_transformation_def) |
314 by (simp add: linear_iff orthogonal_transformation_def) |
315 |
315 |
316 lemma%unimportant orthogonal_orthogonal_transformation: |
316 lemma\<^marker>\<open>tag unimportant\<close> orthogonal_orthogonal_transformation: |
317 "orthogonal_transformation f \<Longrightarrow> orthogonal (f x) (f y) \<longleftrightarrow> orthogonal x y" |
317 "orthogonal_transformation f \<Longrightarrow> orthogonal (f x) (f y) \<longleftrightarrow> orthogonal x y" |
318 by (simp add: orthogonal_def orthogonal_transformation_def) |
318 by (simp add: orthogonal_def orthogonal_transformation_def) |
319 |
319 |
320 lemma%unimportant orthogonal_transformation_compose: |
320 lemma\<^marker>\<open>tag unimportant\<close> orthogonal_transformation_compose: |
321 "\<lbrakk>orthogonal_transformation f; orthogonal_transformation g\<rbrakk> \<Longrightarrow> orthogonal_transformation(f \<circ> g)" |
321 "\<lbrakk>orthogonal_transformation f; orthogonal_transformation g\<rbrakk> \<Longrightarrow> orthogonal_transformation(f \<circ> g)" |
322 by (auto simp: orthogonal_transformation_def linear_compose) |
322 by (auto simp: orthogonal_transformation_def linear_compose) |
323 |
323 |
324 lemma%unimportant orthogonal_transformation_neg: |
324 lemma\<^marker>\<open>tag unimportant\<close> orthogonal_transformation_neg: |
325 "orthogonal_transformation(\<lambda>x. -(f x)) \<longleftrightarrow> orthogonal_transformation f" |
325 "orthogonal_transformation(\<lambda>x. -(f x)) \<longleftrightarrow> orthogonal_transformation f" |
326 by (auto simp: orthogonal_transformation_def dest: linear_compose_neg) |
326 by (auto simp: orthogonal_transformation_def dest: linear_compose_neg) |
327 |
327 |
328 lemma%unimportant orthogonal_transformation_scaleR: "orthogonal_transformation f \<Longrightarrow> f (c *\<^sub>R v) = c *\<^sub>R f v" |
328 lemma\<^marker>\<open>tag unimportant\<close> orthogonal_transformation_scaleR: "orthogonal_transformation f \<Longrightarrow> f (c *\<^sub>R v) = c *\<^sub>R f v" |
329 by (simp add: linear_iff orthogonal_transformation_def) |
329 by (simp add: linear_iff orthogonal_transformation_def) |
330 |
330 |
331 lemma%unimportant orthogonal_transformation_linear: |
331 lemma\<^marker>\<open>tag unimportant\<close> orthogonal_transformation_linear: |
332 "orthogonal_transformation f \<Longrightarrow> linear f" |
332 "orthogonal_transformation f \<Longrightarrow> linear f" |
333 by (simp add: orthogonal_transformation_def) |
333 by (simp add: orthogonal_transformation_def) |
334 |
334 |
335 lemma%unimportant orthogonal_transformation_inj: |
335 lemma\<^marker>\<open>tag unimportant\<close> orthogonal_transformation_inj: |
336 "orthogonal_transformation f \<Longrightarrow> inj f" |
336 "orthogonal_transformation f \<Longrightarrow> inj f" |
337 unfolding orthogonal_transformation_def inj_on_def |
337 unfolding orthogonal_transformation_def inj_on_def |
338 by (metis vector_eq) |
338 by (metis vector_eq) |
339 |
339 |
340 lemma%unimportant orthogonal_transformation_surj: |
340 lemma\<^marker>\<open>tag unimportant\<close> orthogonal_transformation_surj: |
341 "orthogonal_transformation f \<Longrightarrow> surj f" |
341 "orthogonal_transformation f \<Longrightarrow> surj f" |
342 for f :: "'a::euclidean_space \<Rightarrow> 'a::euclidean_space" |
342 for f :: "'a::euclidean_space \<Rightarrow> 'a::euclidean_space" |
343 by (simp add: linear_injective_imp_surjective orthogonal_transformation_inj orthogonal_transformation_linear) |
343 by (simp add: linear_injective_imp_surjective orthogonal_transformation_inj orthogonal_transformation_linear) |
344 |
344 |
345 lemma%unimportant orthogonal_transformation_bij: |
345 lemma\<^marker>\<open>tag unimportant\<close> orthogonal_transformation_bij: |
346 "orthogonal_transformation f \<Longrightarrow> bij f" |
346 "orthogonal_transformation f \<Longrightarrow> bij f" |
347 for f :: "'a::euclidean_space \<Rightarrow> 'a::euclidean_space" |
347 for f :: "'a::euclidean_space \<Rightarrow> 'a::euclidean_space" |
348 by (simp add: bij_def orthogonal_transformation_inj orthogonal_transformation_surj) |
348 by (simp add: bij_def orthogonal_transformation_inj orthogonal_transformation_surj) |
349 |
349 |
350 lemma%unimportant orthogonal_transformation_inv: |
350 lemma\<^marker>\<open>tag unimportant\<close> orthogonal_transformation_inv: |
351 "orthogonal_transformation f \<Longrightarrow> orthogonal_transformation (inv f)" |
351 "orthogonal_transformation f \<Longrightarrow> orthogonal_transformation (inv f)" |
352 for f :: "'a::euclidean_space \<Rightarrow> 'a::euclidean_space" |
352 for f :: "'a::euclidean_space \<Rightarrow> 'a::euclidean_space" |
353 by (metis (no_types, hide_lams) bijection.inv_right bijection_def inj_linear_imp_inv_linear orthogonal_transformation orthogonal_transformation_bij orthogonal_transformation_inj) |
353 by (metis (no_types, hide_lams) bijection.inv_right bijection_def inj_linear_imp_inv_linear orthogonal_transformation orthogonal_transformation_bij orthogonal_transformation_inj) |
354 |
354 |
355 lemma%unimportant orthogonal_transformation_norm: |
355 lemma\<^marker>\<open>tag unimportant\<close> orthogonal_transformation_norm: |
356 "orthogonal_transformation f \<Longrightarrow> norm (f x) = norm x" |
356 "orthogonal_transformation f \<Longrightarrow> norm (f x) = norm x" |
357 by (metis orthogonal_transformation) |
357 by (metis orthogonal_transformation) |
358 |
358 |
359 |
359 |
360 subsection \<open>Bilinear functions\<close> |
360 subsection \<open>Bilinear functions\<close> |
361 |
361 |
362 definition%important |
362 definition\<^marker>\<open>tag important\<close> |
363 bilinear :: "('a::real_vector \<Rightarrow> 'b::real_vector \<Rightarrow> 'c::real_vector) \<Rightarrow> bool" where |
363 bilinear :: "('a::real_vector \<Rightarrow> 'b::real_vector \<Rightarrow> 'c::real_vector) \<Rightarrow> bool" where |
364 "bilinear f \<longleftrightarrow> (\<forall>x. linear (\<lambda>y. f x y)) \<and> (\<forall>y. linear (\<lambda>x. f x y))" |
364 "bilinear f \<longleftrightarrow> (\<forall>x. linear (\<lambda>y. f x y)) \<and> (\<forall>y. linear (\<lambda>x. f x y))" |
365 |
365 |
366 lemma bilinear_ladd: "bilinear h \<Longrightarrow> h (x + y) z = h x z + h y z" |
366 lemma bilinear_ladd: "bilinear h \<Longrightarrow> h (x + y) z = h x z + h y z" |
367 by (simp add: bilinear_def linear_iff) |
367 by (simp add: bilinear_def linear_iff) |
415 qed |
415 qed |
416 |
416 |
417 |
417 |
418 subsection \<open>Adjoints\<close> |
418 subsection \<open>Adjoints\<close> |
419 |
419 |
420 definition%important adjoint :: "(('a::real_inner) \<Rightarrow> ('b::real_inner)) \<Rightarrow> 'b \<Rightarrow> 'a" where |
420 definition\<^marker>\<open>tag important\<close> adjoint :: "(('a::real_inner) \<Rightarrow> ('b::real_inner)) \<Rightarrow> 'b \<Rightarrow> 'a" where |
421 "adjoint f = (SOME f'. \<forall>x y. f x \<bullet> y = x \<bullet> f' y)" |
421 "adjoint f = (SOME f'. \<forall>x y. f x \<bullet> y = x \<bullet> f' y)" |
422 |
422 |
423 lemma adjoint_unique: |
423 lemma adjoint_unique: |
424 assumes "\<forall>x y. inner (f x) y = inner x (g y)" |
424 assumes "\<forall>x y. inner (f x) y = inner x (g y)" |
425 shows "adjoint f = g" |
425 shows "adjoint f = g" |
577 apply auto |
577 apply auto |
578 apply (metis Suc_pred of_nat_Suc) |
578 apply (metis Suc_pred of_nat_Suc) |
579 done |
579 done |
580 |
580 |
581 |
581 |
582 subsection%unimportant \<open>Euclidean Spaces as Typeclass\<close> |
582 subsection\<^marker>\<open>tag unimportant\<close> \<open>Euclidean Spaces as Typeclass\<close> |
583 |
583 |
584 lemma independent_Basis: "independent Basis" |
584 lemma independent_Basis: "independent Basis" |
585 by (rule independent_Basis) |
585 by (rule independent_Basis) |
586 |
586 |
587 lemma span_Basis [simp]: "span Basis = UNIV" |
587 lemma span_Basis [simp]: "span Basis = UNIV" |
589 |
589 |
590 lemma in_span_Basis: "x \<in> span Basis" |
590 lemma in_span_Basis: "x \<in> span Basis" |
591 unfolding span_Basis .. |
591 unfolding span_Basis .. |
592 |
592 |
593 |
593 |
594 subsection%unimportant \<open>Linearity and Bilinearity continued\<close> |
594 subsection\<^marker>\<open>tag unimportant\<close> \<open>Linearity and Bilinearity continued\<close> |
595 |
595 |
596 lemma linear_bounded: |
596 lemma linear_bounded: |
597 fixes f :: "'a::euclidean_space \<Rightarrow> 'b::real_normed_vector" |
597 fixes f :: "'a::euclidean_space \<Rightarrow> 'b::real_normed_vector" |
598 assumes lf: "linear f" |
598 assumes lf: "linear f" |
599 shows "\<exists>B. \<forall>x. norm (f x) \<le> B * norm x" |
599 shows "\<exists>B. \<forall>x. norm (f x) \<le> B * norm x" |
771 fixes f :: "'a::euclidean_space \<Rightarrow> 'b::real_normed_vector" |
771 fixes f :: "'a::euclidean_space \<Rightarrow> 'b::real_normed_vector" |
772 shows "linear f \<Longrightarrow> f differentiable net" |
772 shows "linear f \<Longrightarrow> f differentiable net" |
773 by (metis linear_imp_has_derivative differentiable_def) |
773 by (metis linear_imp_has_derivative differentiable_def) |
774 |
774 |
775 |
775 |
776 subsection%unimportant \<open>We continue\<close> |
776 subsection\<^marker>\<open>tag unimportant\<close> \<open>We continue\<close> |
777 |
777 |
778 lemma independent_bound: |
778 lemma independent_bound: |
779 fixes S :: "'a::euclidean_space set" |
779 fixes S :: "'a::euclidean_space set" |
780 shows "independent S \<Longrightarrow> finite S \<and> card S \<le> DIM('a)" |
780 shows "independent S \<Longrightarrow> finite S \<and> card S \<le> DIM('a)" |
781 by (metis dim_subset_UNIV finiteI_independent dim_span_eq_card_independent) |
781 by (metis dim_subset_UNIV finiteI_independent dim_span_eq_card_independent) |
1035 using bilinear_eq[OF bf bg equalityD2[OF span_Basis] equalityD2[OF span_Basis]] fg by blast |
1035 using bilinear_eq[OF bf bg equalityD2[OF span_Basis] equalityD2[OF span_Basis]] fg by blast |
1036 |
1036 |
1037 |
1037 |
1038 subsection \<open>Infinity norm\<close> |
1038 subsection \<open>Infinity norm\<close> |
1039 |
1039 |
1040 definition%important "infnorm (x::'a::euclidean_space) = Sup {\<bar>x \<bullet> b\<bar> |b. b \<in> Basis}" |
1040 definition\<^marker>\<open>tag important\<close> "infnorm (x::'a::euclidean_space) = Sup {\<bar>x \<bullet> b\<bar> |b. b \<in> Basis}" |
1041 |
1041 |
1042 lemma infnorm_set_image: |
1042 lemma infnorm_set_image: |
1043 fixes x :: "'a::euclidean_space" |
1043 fixes x :: "'a::euclidean_space" |
1044 shows "{\<bar>x \<bullet> i\<bar> |i. i \<in> Basis} = (\<lambda>i. \<bar>x \<bullet> i\<bar>) ` Basis" |
1044 shows "{\<bar>x \<bullet> i\<bar> |i. i \<in> Basis} = (\<lambda>i. \<bar>x \<bullet> i\<bar>) ` Basis" |
1045 by blast |
1045 by blast |
1225 qed |
1225 qed |
1226 |
1226 |
1227 |
1227 |
1228 subsection \<open>Collinearity\<close> |
1228 subsection \<open>Collinearity\<close> |
1229 |
1229 |
1230 definition%important collinear :: "'a::real_vector set \<Rightarrow> bool" |
1230 definition\<^marker>\<open>tag important\<close> collinear :: "'a::real_vector set \<Rightarrow> bool" |
1231 where "collinear S \<longleftrightarrow> (\<exists>u. \<forall>x \<in> S. \<forall> y \<in> S. \<exists>c. x - y = c *\<^sub>R u)" |
1231 where "collinear S \<longleftrightarrow> (\<exists>u. \<forall>x \<in> S. \<forall> y \<in> S. \<exists>c. x - y = c *\<^sub>R u)" |
1232 |
1232 |
1233 lemma collinear_alt: |
1233 lemma collinear_alt: |
1234 "collinear S \<longleftrightarrow> (\<exists>u v. \<forall>x \<in> S. \<exists>c. x = u + c *\<^sub>R v)" (is "?lhs = ?rhs") |
1234 "collinear S \<longleftrightarrow> (\<exists>u v. \<forall>x \<in> S. \<exists>c. x = u + c *\<^sub>R v)" (is "?lhs = ?rhs") |
1235 proof |
1235 proof |
1563 using assms pairwise_orthogonal_imp_finite by auto |
1563 using assms pairwise_orthogonal_imp_finite by auto |
1564 with \<open>span B = span T\<close> show ?thesis |
1564 with \<open>span B = span T\<close> show ?thesis |
1565 by (rule_tac U=U in that) (auto simp: span_Un) |
1565 by (rule_tac U=U in that) (auto simp: span_Un) |
1566 qed |
1566 qed |
1567 |
1567 |
1568 corollary%unimportant orthogonal_extension_strong: |
1568 corollary\<^marker>\<open>tag unimportant\<close> orthogonal_extension_strong: |
1569 fixes S :: "'a::euclidean_space set" |
1569 fixes S :: "'a::euclidean_space set" |
1570 assumes S: "pairwise orthogonal S" |
1570 assumes S: "pairwise orthogonal S" |
1571 obtains U where "U \<inter> (insert 0 S) = {}" "pairwise orthogonal (S \<union> U)" |
1571 obtains U where "U \<inter> (insert 0 S) = {}" "pairwise orthogonal (S \<union> U)" |
1572 "span (S \<union> U) = span (S \<union> T)" |
1572 "span (S \<union> U) = span (S \<union> T)" |
1573 proof - |
1573 proof - |
1646 show ?thesis |
1646 show ?thesis |
1647 by (rule that [OF 1 2 3 4 5 6]) |
1647 by (rule that [OF 1 2 3 4 5 6]) |
1648 qed |
1648 qed |
1649 |
1649 |
1650 |
1650 |
1651 proposition%unimportant orthogonal_to_subspace_exists_gen: |
1651 proposition\<^marker>\<open>tag unimportant\<close> orthogonal_to_subspace_exists_gen: |
1652 fixes S :: "'a :: euclidean_space set" |
1652 fixes S :: "'a :: euclidean_space set" |
1653 assumes "span S \<subset> span T" |
1653 assumes "span S \<subset> span T" |
1654 obtains x where "x \<noteq> 0" "x \<in> span T" "\<And>y. y \<in> span S \<Longrightarrow> orthogonal x y" |
1654 obtains x where "x \<noteq> 0" "x \<in> span T" "\<And>y. y \<in> span S \<Longrightarrow> orthogonal x y" |
1655 proof - |
1655 proof - |
1656 obtain B where "B \<subseteq> span S" and orthB: "pairwise orthogonal B" |
1656 obtain B where "B \<subseteq> span S" and orthB: "pairwise orthogonal B" |
1692 ultimately show ?thesis |
1692 ultimately show ?thesis |
1693 using \<open>x \<noteq> 0\<close> that \<open>span B = span S\<close> by auto |
1693 using \<open>x \<noteq> 0\<close> that \<open>span B = span S\<close> by auto |
1694 qed |
1694 qed |
1695 qed |
1695 qed |
1696 |
1696 |
1697 corollary%unimportant orthogonal_to_subspace_exists: |
1697 corollary\<^marker>\<open>tag unimportant\<close> orthogonal_to_subspace_exists: |
1698 fixes S :: "'a :: euclidean_space set" |
1698 fixes S :: "'a :: euclidean_space set" |
1699 assumes "dim S < DIM('a)" |
1699 assumes "dim S < DIM('a)" |
1700 obtains x where "x \<noteq> 0" "\<And>y. y \<in> span S \<Longrightarrow> orthogonal x y" |
1700 obtains x where "x \<noteq> 0" "\<And>y. y \<in> span S \<Longrightarrow> orthogonal x y" |
1701 proof - |
1701 proof - |
1702 have "span S \<subset> UNIV" |
1702 have "span S \<subset> UNIV" |
1704 mem_Collect_eq top.extremum_strict top.not_eq_extremum) |
1704 mem_Collect_eq top.extremum_strict top.not_eq_extremum) |
1705 with orthogonal_to_subspace_exists_gen [of S UNIV] that show ?thesis |
1705 with orthogonal_to_subspace_exists_gen [of S UNIV] that show ?thesis |
1706 by (auto simp: span_UNIV) |
1706 by (auto simp: span_UNIV) |
1707 qed |
1707 qed |
1708 |
1708 |
1709 corollary%unimportant orthogonal_to_vector_exists: |
1709 corollary\<^marker>\<open>tag unimportant\<close> orthogonal_to_vector_exists: |
1710 fixes x :: "'a :: euclidean_space" |
1710 fixes x :: "'a :: euclidean_space" |
1711 assumes "2 \<le> DIM('a)" |
1711 assumes "2 \<le> DIM('a)" |
1712 obtains y where "y \<noteq> 0" "orthogonal x y" |
1712 obtains y where "y \<noteq> 0" "orthogonal x y" |
1713 proof - |
1713 proof - |
1714 have "dim {x} < DIM('a)" |
1714 have "dim {x} < DIM('a)" |
1715 using assms by auto |
1715 using assms by auto |
1716 then show thesis |
1716 then show thesis |
1717 by (rule orthogonal_to_subspace_exists) (simp add: orthogonal_commute span_base that) |
1717 by (rule orthogonal_to_subspace_exists) (simp add: orthogonal_commute span_base that) |
1718 qed |
1718 qed |
1719 |
1719 |
1720 proposition%unimportant orthogonal_subspace_decomp_exists: |
1720 proposition\<^marker>\<open>tag unimportant\<close> orthogonal_subspace_decomp_exists: |
1721 fixes S :: "'a :: euclidean_space set" |
1721 fixes S :: "'a :: euclidean_space set" |
1722 obtains y z |
1722 obtains y z |
1723 where "y \<in> span S" |
1723 where "y \<in> span S" |
1724 and "\<And>w. w \<in> span S \<Longrightarrow> orthogonal z w" |
1724 and "\<And>w. w \<in> span S \<Longrightarrow> orthogonal z w" |
1725 and "x = y + z" |
1725 and "x = y + z" |