author | hoelzl |
Fri, 14 Dec 2012 15:46:01 +0100 | |
changeset 50526 | 899c9c4e4a4c |
parent 44133 | 691c52e900ca |
child 51475 | ebf9d4fd00ba |
permissions | -rw-r--r-- |
41959 | 1 |
(* Title: HOL/Multivariate_Analysis/Operator_Norm.thy |
36581 | 2 |
Author: Amine Chaieb, University of Cambridge |
3 |
*) |
|
4 |
||
5 |
header {* Operator Norm *} |
|
6 |
||
7 |
theory Operator_Norm |
|
44133
691c52e900ca
split Linear_Algebra.thy from Euclidean_Space.thy
huffman
parents:
41959
diff
changeset
|
8 |
imports Linear_Algebra |
36581 | 9 |
begin |
10 |
||
11 |
definition "onorm f = Sup {norm (f x)| x. norm x = 1}" |
|
12 |
||
13 |
lemma norm_bound_generalize: |
|
37489
44e42d392c6e
Introduce a type class for euclidean spaces, port most lemmas from real^'n to this type class.
hoelzl
parents:
36593
diff
changeset
|
14 |
fixes f:: "'a::euclidean_space \<Rightarrow> 'b::euclidean_space" |
36581 | 15 |
assumes lf: "linear f" |
16 |
shows "(\<forall>x. norm x = 1 \<longrightarrow> norm (f x) \<le> b) \<longleftrightarrow> (\<forall>x. norm (f x) \<le> b * norm x)" (is "?lhs \<longleftrightarrow> ?rhs") |
|
17 |
proof- |
|
18 |
{assume H: ?rhs |
|
37489
44e42d392c6e
Introduce a type class for euclidean spaces, port most lemmas from real^'n to this type class.
hoelzl
parents:
36593
diff
changeset
|
19 |
{fix x :: "'a" assume x: "norm x = 1" |
36581 | 20 |
from H[rule_format, of x] x have "norm (f x) \<le> b" by simp} |
21 |
then have ?lhs by blast } |
|
22 |
||
23 |
moreover |
|
24 |
{assume H: ?lhs |
|
50526
899c9c4e4a4c
Remove the indexed basis from the definition of euclidean spaces and only use the set of Basis vectors
hoelzl
parents:
44133
diff
changeset
|
25 |
have bp: "b \<ge> 0" |
899c9c4e4a4c
Remove the indexed basis from the definition of euclidean spaces and only use the set of Basis vectors
hoelzl
parents:
44133
diff
changeset
|
26 |
apply - |
899c9c4e4a4c
Remove the indexed basis from the definition of euclidean spaces and only use the set of Basis vectors
hoelzl
parents:
44133
diff
changeset
|
27 |
apply(rule order_trans [OF norm_ge_zero]) |
899c9c4e4a4c
Remove the indexed basis from the definition of euclidean spaces and only use the set of Basis vectors
hoelzl
parents:
44133
diff
changeset
|
28 |
apply(rule H[rule_format, of "SOME x::'a. x \<in> Basis"]) |
899c9c4e4a4c
Remove the indexed basis from the definition of euclidean spaces and only use the set of Basis vectors
hoelzl
parents:
44133
diff
changeset
|
29 |
by (auto intro: SOME_Basis norm_Basis) |
37489
44e42d392c6e
Introduce a type class for euclidean spaces, port most lemmas from real^'n to this type class.
hoelzl
parents:
36593
diff
changeset
|
30 |
{fix x :: "'a" |
36581 | 31 |
{assume "x = 0" |
32 |
then have "norm (f x) \<le> b * norm x" by (simp add: linear_0[OF lf] bp)} |
|
33 |
moreover |
|
34 |
{assume x0: "x \<noteq> 0" |
|
35 |
hence n0: "norm x \<noteq> 0" by (metis norm_eq_zero) |
|
36 |
let ?c = "1/ norm x" |
|
36593
fb69c8cd27bd
define linear algebra concepts using scaleR instead of (op *s); generalized many lemmas, though a few theorems that used to work on type int^'n are a bit less general
huffman
parents:
36581
diff
changeset
|
37 |
have "norm (?c *\<^sub>R x) = 1" using x0 by (simp add: n0) |
fb69c8cd27bd
define linear algebra concepts using scaleR instead of (op *s); generalized many lemmas, though a few theorems that used to work on type int^'n are a bit less general
huffman
parents:
36581
diff
changeset
|
38 |
with H have "norm (f (?c *\<^sub>R x)) \<le> b" by blast |
36581 | 39 |
hence "?c * norm (f x) \<le> b" |
40 |
by (simp add: linear_cmul[OF lf]) |
|
41 |
hence "norm (f x) \<le> b * norm x" |
|
42 |
using n0 norm_ge_zero[of x] by (auto simp add: field_simps)} |
|
43 |
ultimately have "norm (f x) \<le> b * norm x" by blast} |
|
44 |
then have ?rhs by blast} |
|
45 |
ultimately show ?thesis by blast |
|
46 |
qed |
|
37489
44e42d392c6e
Introduce a type class for euclidean spaces, port most lemmas from real^'n to this type class.
hoelzl
parents:
36593
diff
changeset
|
47 |
|
36581 | 48 |
lemma onorm: |
37489
44e42d392c6e
Introduce a type class for euclidean spaces, port most lemmas from real^'n to this type class.
hoelzl
parents:
36593
diff
changeset
|
49 |
fixes f:: "'a::euclidean_space \<Rightarrow> 'b::euclidean_space" |
36581 | 50 |
assumes lf: "linear f" |
51 |
shows "norm (f x) <= onorm f * norm x" |
|
52 |
and "\<forall>x. norm (f x) <= b * norm x \<Longrightarrow> onorm f <= b" |
|
53 |
proof- |
|
54 |
{ |
|
55 |
let ?S = "{norm (f x) |x. norm x = 1}" |
|
50526
899c9c4e4a4c
Remove the indexed basis from the definition of euclidean spaces and only use the set of Basis vectors
hoelzl
parents:
44133
diff
changeset
|
56 |
have "norm (f (SOME i. i \<in> Basis)) \<in> ?S" |
899c9c4e4a4c
Remove the indexed basis from the definition of euclidean spaces and only use the set of Basis vectors
hoelzl
parents:
44133
diff
changeset
|
57 |
by (auto intro!: exI[of _ "SOME i. i \<in> Basis"] norm_Basis SOME_Basis) |
37489
44e42d392c6e
Introduce a type class for euclidean spaces, port most lemmas from real^'n to this type class.
hoelzl
parents:
36593
diff
changeset
|
58 |
hence Se: "?S \<noteq> {}" by auto |
36581 | 59 |
from linear_bounded[OF lf] have b: "\<exists> b. ?S *<= b" |
60 |
unfolding norm_bound_generalize[OF lf, symmetric] by (auto simp add: setle_def) |
|
61 |
{from Sup[OF Se b, unfolded onorm_def[symmetric]] |
|
62 |
show "norm (f x) <= onorm f * norm x" |
|
63 |
apply - |
|
64 |
apply (rule spec[where x = x]) |
|
65 |
unfolding norm_bound_generalize[OF lf, symmetric] |
|
66 |
by (auto simp add: isLub_def isUb_def leastP_def setge_def setle_def)} |
|
67 |
{ |
|
68 |
show "\<forall>x. norm (f x) <= b * norm x \<Longrightarrow> onorm f <= b" |
|
69 |
using Sup[OF Se b, unfolded onorm_def[symmetric]] |
|
70 |
unfolding norm_bound_generalize[OF lf, symmetric] |
|
71 |
by (auto simp add: isLub_def isUb_def leastP_def setge_def setle_def)} |
|
72 |
} |
|
73 |
qed |
|
74 |
||
37489
44e42d392c6e
Introduce a type class for euclidean spaces, port most lemmas from real^'n to this type class.
hoelzl
parents:
36593
diff
changeset
|
75 |
lemma onorm_pos_le: assumes lf: "linear (f::'n::euclidean_space \<Rightarrow> 'm::euclidean_space)" shows "0 <= onorm f" |
50526
899c9c4e4a4c
Remove the indexed basis from the definition of euclidean spaces and only use the set of Basis vectors
hoelzl
parents:
44133
diff
changeset
|
76 |
using order_trans[OF norm_ge_zero onorm(1)[OF lf, of "SOME i. i \<in> Basis"]] |
899c9c4e4a4c
Remove the indexed basis from the definition of euclidean spaces and only use the set of Basis vectors
hoelzl
parents:
44133
diff
changeset
|
77 |
by (simp add: SOME_Basis) |
36581 | 78 |
|
37489
44e42d392c6e
Introduce a type class for euclidean spaces, port most lemmas from real^'n to this type class.
hoelzl
parents:
36593
diff
changeset
|
79 |
lemma onorm_eq_0: assumes lf: "linear (f::'a::euclidean_space \<Rightarrow> 'b::euclidean_space)" |
36581 | 80 |
shows "onorm f = 0 \<longleftrightarrow> (\<forall>x. f x = 0)" |
81 |
using onorm[OF lf] |
|
82 |
apply (auto simp add: onorm_pos_le) |
|
83 |
apply atomize |
|
84 |
apply (erule allE[where x="0::real"]) |
|
85 |
using onorm_pos_le[OF lf] |
|
86 |
apply arith |
|
87 |
done |
|
88 |
||
37489
44e42d392c6e
Introduce a type class for euclidean spaces, port most lemmas from real^'n to this type class.
hoelzl
parents:
36593
diff
changeset
|
89 |
lemma onorm_const: "onorm(\<lambda>x::'a::euclidean_space. (y::'b::euclidean_space)) = norm y" |
36581 | 90 |
proof- |
37489
44e42d392c6e
Introduce a type class for euclidean spaces, port most lemmas from real^'n to this type class.
hoelzl
parents:
36593
diff
changeset
|
91 |
let ?f = "\<lambda>x::'a. (y::'b)" |
36581 | 92 |
have th: "{norm (?f x)| x. norm x = 1} = {norm y}" |
50526
899c9c4e4a4c
Remove the indexed basis from the definition of euclidean spaces and only use the set of Basis vectors
hoelzl
parents:
44133
diff
changeset
|
93 |
by (auto simp: SOME_Basis intro!: exI[of _ "SOME i. i \<in> Basis"]) |
36581 | 94 |
show ?thesis |
95 |
unfolding onorm_def th |
|
96 |
apply (rule Sup_unique) by (simp_all add: setle_def) |
|
97 |
qed |
|
98 |
||
37489
44e42d392c6e
Introduce a type class for euclidean spaces, port most lemmas from real^'n to this type class.
hoelzl
parents:
36593
diff
changeset
|
99 |
lemma onorm_pos_lt: assumes lf: "linear (f::'a::euclidean_space \<Rightarrow> 'b::euclidean_space)" |
36581 | 100 |
shows "0 < onorm f \<longleftrightarrow> ~(\<forall>x. f x = 0)" |
101 |
unfolding onorm_eq_0[OF lf, symmetric] |
|
102 |
using onorm_pos_le[OF lf] by arith |
|
103 |
||
104 |
lemma onorm_compose: |
|
37489
44e42d392c6e
Introduce a type class for euclidean spaces, port most lemmas from real^'n to this type class.
hoelzl
parents:
36593
diff
changeset
|
105 |
assumes lf: "linear (f::'n::euclidean_space \<Rightarrow> 'm::euclidean_space)" |
44e42d392c6e
Introduce a type class for euclidean spaces, port most lemmas from real^'n to this type class.
hoelzl
parents:
36593
diff
changeset
|
106 |
and lg: "linear (g::'k::euclidean_space \<Rightarrow> 'n::euclidean_space)" |
36581 | 107 |
shows "onorm (f o g) <= onorm f * onorm g" |
108 |
apply (rule onorm(2)[OF linear_compose[OF lg lf], rule_format]) |
|
109 |
unfolding o_def |
|
110 |
apply (subst mult_assoc) |
|
111 |
apply (rule order_trans) |
|
112 |
apply (rule onorm(1)[OF lf]) |
|
38642
8fa437809c67
dropped type classes mult_mono and mult_mono1; tuned names of technical rule duplicates
haftmann
parents:
37489
diff
changeset
|
113 |
apply (rule mult_left_mono) |
36581 | 114 |
apply (rule onorm(1)[OF lg]) |
115 |
apply (rule onorm_pos_le[OF lf]) |
|
116 |
done |
|
117 |
||
37489
44e42d392c6e
Introduce a type class for euclidean spaces, port most lemmas from real^'n to this type class.
hoelzl
parents:
36593
diff
changeset
|
118 |
lemma onorm_neg_lemma: assumes lf: "linear (f::'a::euclidean_space \<Rightarrow> 'b::euclidean_space)" |
36581 | 119 |
shows "onorm (\<lambda>x. - f x) \<le> onorm f" |
120 |
using onorm[OF linear_compose_neg[OF lf]] onorm[OF lf] |
|
121 |
unfolding norm_minus_cancel by metis |
|
122 |
||
37489
44e42d392c6e
Introduce a type class for euclidean spaces, port most lemmas from real^'n to this type class.
hoelzl
parents:
36593
diff
changeset
|
123 |
lemma onorm_neg: assumes lf: "linear (f::'a::euclidean_space \<Rightarrow> 'b::euclidean_space)" |
36581 | 124 |
shows "onorm (\<lambda>x. - f x) = onorm f" |
125 |
using onorm_neg_lemma[OF lf] onorm_neg_lemma[OF linear_compose_neg[OF lf]] |
|
126 |
by simp |
|
127 |
||
128 |
lemma onorm_triangle: |
|
37489
44e42d392c6e
Introduce a type class for euclidean spaces, port most lemmas from real^'n to this type class.
hoelzl
parents:
36593
diff
changeset
|
129 |
assumes lf: "linear (f::'n::euclidean_space \<Rightarrow> 'm::euclidean_space)" and lg: "linear g" |
36581 | 130 |
shows "onorm (\<lambda>x. f x + g x) <= onorm f + onorm g" |
131 |
apply(rule onorm(2)[OF linear_compose_add[OF lf lg], rule_format]) |
|
132 |
apply (rule order_trans) |
|
133 |
apply (rule norm_triangle_ineq) |
|
134 |
apply (simp add: distrib) |
|
135 |
apply (rule add_mono) |
|
136 |
apply (rule onorm(1)[OF lf]) |
|
137 |
apply (rule onorm(1)[OF lg]) |
|
138 |
done |
|
139 |
||
37489
44e42d392c6e
Introduce a type class for euclidean spaces, port most lemmas from real^'n to this type class.
hoelzl
parents:
36593
diff
changeset
|
140 |
lemma onorm_triangle_le: "linear (f::'n::euclidean_space \<Rightarrow> 'm::euclidean_space) \<Longrightarrow> linear g \<Longrightarrow> onorm(f) + onorm(g) <= e |
36581 | 141 |
\<Longrightarrow> onorm(\<lambda>x. f x + g x) <= e" |
142 |
apply (rule order_trans) |
|
143 |
apply (rule onorm_triangle) |
|
144 |
apply assumption+ |
|
145 |
done |
|
146 |
||
37489
44e42d392c6e
Introduce a type class for euclidean spaces, port most lemmas from real^'n to this type class.
hoelzl
parents:
36593
diff
changeset
|
147 |
lemma onorm_triangle_lt: "linear (f::'n::euclidean_space \<Rightarrow> 'm::euclidean_space) \<Longrightarrow> linear g \<Longrightarrow> onorm(f) + onorm(g) < e |
36581 | 148 |
==> onorm(\<lambda>x. f x + g x) < e" |
149 |
apply (rule order_le_less_trans) |
|
150 |
apply (rule onorm_triangle) |
|
151 |
by assumption+ |
|
152 |
||
153 |
end |