src/HOL/Analysis/Derivative.thy
changeset 68239 0764ee22a4d1
parent 68095 4fa3e63ecc7e
child 68241 39a311f50344
equal deleted inserted replaced
68223:88dd06301dd3 68239:0764ee22a4d1
     1 (*  Title:      HOL/Analysis/Derivative.thy
     1 (*  Title:      HOL/Analysis/Derivative.thy
     2     Author:     John Harrison
     2     Author:     John Harrison
     3     Author:     Robert Himmelmann, TU Muenchen (translation from HOL Light)
     3     Author:     Robert Himmelmann, TU Muenchen (translation from HOL Light); tidied by LCP
     4 *)
     4 *)
     5 
     5 
     6 section \<open>Multivariate calculus in Euclidean space\<close>
     6 section \<open>Multivariate calculus in Euclidean space\<close>
     7 
     7 
     8 theory Derivative
     8 theory Derivative
    13 
    13 
    14 declare has_derivative_bounded_linear[dest]
    14 declare has_derivative_bounded_linear[dest]
    15 
    15 
    16 subsection \<open>Derivatives\<close>
    16 subsection \<open>Derivatives\<close>
    17 
    17 
    18 subsubsection \<open>Combining theorems\<close>
       
    19 
       
    20 lemmas has_derivative_id = has_derivative_ident
       
    21 lemmas has_derivative_neg = has_derivative_minus
       
    22 lemmas has_derivative_sub = has_derivative_diff
       
    23 lemmas scaleR_right_has_derivative = has_derivative_scaleR_right
       
    24 lemmas scaleR_left_has_derivative = has_derivative_scaleR_left
       
    25 lemmas inner_right_has_derivative = has_derivative_inner_right
       
    26 lemmas inner_left_has_derivative = has_derivative_inner_left
       
    27 lemmas mult_right_has_derivative = has_derivative_mult_right
       
    28 lemmas mult_left_has_derivative = has_derivative_mult_left
       
    29 
       
    30 lemma has_derivative_add_const:
    18 lemma has_derivative_add_const:
    31   "(f has_derivative f') net \<Longrightarrow> ((\<lambda>x. f x + c) has_derivative f') net"
    19   "(f has_derivative f') net \<Longrightarrow> ((\<lambda>x. f x + c) has_derivative f') net"
    32   by (intro derivative_eq_intros) auto
    20   by (intro derivative_eq_intros) auto
    33 
    21 
    34 
    22 
    35 subsection \<open>Derivative with composed bilinear function\<close>
    23 subsection \<open>Derivative with composed bilinear function\<close>
    36 
       
    37 lemma has_derivative_bilinear_within:
       
    38   assumes "(f has_derivative f') (at x within s)"
       
    39     and "(g has_derivative g') (at x within s)"
       
    40     and "bounded_bilinear h"
       
    41   shows "((\<lambda>x. h (f x) (g x)) has_derivative (\<lambda>d. h (f x) (g' d) + h (f' d) (g x))) (at x within s)"
       
    42   using bounded_bilinear.FDERIV[OF assms(3,1,2)] .
       
    43 
       
    44 lemma has_derivative_bilinear_at:
       
    45   assumes "(f has_derivative f') (at x)"
       
    46     and "(g has_derivative g') (at x)"
       
    47     and "bounded_bilinear h"
       
    48   shows "((\<lambda>x. h (f x) (g x)) has_derivative (\<lambda>d. h (f x) (g' d) + h (f' d) (g x))) (at x)"
       
    49   using has_derivative_bilinear_within[of f f' x UNIV g g' h] assms by simp
       
    50 
    24 
    51 text \<open>More explicit epsilon-delta forms.\<close>
    25 text \<open>More explicit epsilon-delta forms.\<close>
    52 
    26 
    53 lemma has_derivative_within':
    27 lemma has_derivative_within':
    54   "(f has_derivative f')(at x within s) \<longleftrightarrow>
    28   "(f has_derivative f')(at x within s) \<longleftrightarrow>
    55     bounded_linear f' \<and>
    29     bounded_linear f' \<and>
    56     (\<forall>e>0. \<exists>d>0. \<forall>x'\<in>s. 0 < norm (x' - x) \<and> norm (x' - x) < d \<longrightarrow>
    30     (\<forall>e>0. \<exists>d>0. \<forall>x'\<in>s. 0 < norm (x' - x) \<and> norm (x' - x) < d \<longrightarrow>
    57       norm (f x' - f x - f'(x' - x)) / norm (x' - x) < e)"
    31       norm (f x' - f x - f'(x' - x)) / norm (x' - x) < e)"
    58   unfolding has_derivative_within Lim_within dist_norm
    32   unfolding has_derivative_within Lim_within dist_norm
    59   unfolding diff_0_right
       
    60   by (simp add: diff_diff_eq)
    33   by (simp add: diff_diff_eq)
    61 
    34 
    62 lemma has_derivative_at':
    35 lemma has_derivative_at':
    63   "(f has_derivative f') (at x) \<longleftrightarrow> bounded_linear f' \<and>
    36   "(f has_derivative f') (at x) 
    64     (\<forall>e>0. \<exists>d>0. \<forall>x'. 0 < norm (x' - x) \<and> norm (x' - x) < d \<longrightarrow>
    37    \<longleftrightarrow> bounded_linear f' \<and>
    65       norm (f x' - f x - f'(x' - x)) / norm (x' - x) < e)"
    38        (\<forall>e>0. \<exists>d>0. \<forall>x'. 0 < norm (x' - x) \<and> norm (x' - x) < d \<longrightarrow>
    66   using has_derivative_within' [of f f' x UNIV]
    39         norm (f x' - f x - f'(x' - x)) / norm (x' - x) < e)"
    67   by simp
    40   using has_derivative_within' [of f f' x UNIV] by simp
    68 
    41 
    69 lemma has_derivative_at_withinI:
    42 lemma has_derivative_at_withinI:
    70   "(f has_derivative f') (at x) \<Longrightarrow> (f has_derivative f') (at x within s)"
    43   "(f has_derivative f') (at x) \<Longrightarrow> (f has_derivative f') (at x within s)"
    71   unfolding has_derivative_within' has_derivative_at'
    44   unfolding has_derivative_within' has_derivative_at'
    72   by blast
    45   by blast
    78 
    51 
    79 lemma has_derivative_right:
    52 lemma has_derivative_right:
    80   fixes f :: "real \<Rightarrow> real"
    53   fixes f :: "real \<Rightarrow> real"
    81     and y :: "real"
    54     and y :: "real"
    82   shows "(f has_derivative (( * ) y)) (at x within ({x <..} \<inter> I)) \<longleftrightarrow>
    55   shows "(f has_derivative (( * ) y)) (at x within ({x <..} \<inter> I)) \<longleftrightarrow>
    83     ((\<lambda>t. (f x - f t) / (x - t)) \<longlongrightarrow> y) (at x within ({x <..} \<inter> I))"
    56          ((\<lambda>t. (f x - f t) / (x - t)) \<longlongrightarrow> y) (at x within ({x <..} \<inter> I))"
    84 proof -
    57 proof -
    85   have "((\<lambda>t. (f t - (f x + y * (t - x))) / \<bar>t - x\<bar>) \<longlongrightarrow> 0) (at x within ({x<..} \<inter> I)) \<longleftrightarrow>
    58   have "((\<lambda>t. (f t - (f x + y * (t - x))) / \<bar>t - x\<bar>) \<longlongrightarrow> 0) (at x within ({x<..} \<inter> I)) \<longleftrightarrow>
    86     ((\<lambda>t. (f t - f x) / (t - x) - y) \<longlongrightarrow> 0) (at x within ({x<..} \<inter> I))"
    59     ((\<lambda>t. (f t - f x) / (t - x) - y) \<longlongrightarrow> 0) (at x within ({x<..} \<inter> I))"
    87     by (intro Lim_cong_within) (auto simp add: diff_divide_distrib add_divide_distrib)
    60     by (intro Lim_cong_within) (auto simp add: diff_divide_distrib add_divide_distrib)
    88   also have "\<dots> \<longleftrightarrow> ((\<lambda>t. (f t - f x) / (t - x)) \<longlongrightarrow> y) (at x within ({x<..} \<inter> I))"
    61   also have "\<dots> \<longleftrightarrow> ((\<lambda>t. (f t - f x) / (t - x)) \<longlongrightarrow> y) (at x within ({x<..} \<inter> I))"
    92   finally show ?thesis
    65   finally show ?thesis
    93     by (simp add: bounded_linear_mult_right has_derivative_within)
    66     by (simp add: bounded_linear_mult_right has_derivative_within)
    94 qed
    67 qed
    95 
    68 
    96 subsubsection \<open>Caratheodory characterization\<close>
    69 subsubsection \<open>Caratheodory characterization\<close>
    97 
       
    98 lemmas DERIV_within_iff = has_field_derivative_iff
       
    99 
    70 
   100 lemma DERIV_caratheodory_within:
    71 lemma DERIV_caratheodory_within:
   101   "(f has_field_derivative l) (at x within S) \<longleftrightarrow>
    72   "(f has_field_derivative l) (at x within S) \<longleftrightarrow>
   102    (\<exists>g. (\<forall>z. f z - f x = g z * (z - x)) \<and> continuous (at x within S) g \<and> g x = l)"
    73    (\<exists>g. (\<forall>z. f z - f x = g z * (z - x)) \<and> continuous (at x within S) g \<and> g x = l)"
   103       (is "?lhs = ?rhs")
    74       (is "?lhs = ?rhs")
   106   show ?rhs
    77   show ?rhs
   107   proof (intro exI conjI)
    78   proof (intro exI conjI)
   108     let ?g = "(%z. if z = x then l else (f z - f x) / (z-x))"
    79     let ?g = "(%z. if z = x then l else (f z - f x) / (z-x))"
   109     show "\<forall>z. f z - f x = ?g z * (z-x)" by simp
    80     show "\<forall>z. f z - f x = ?g z * (z-x)" by simp
   110     show "continuous (at x within S) ?g" using \<open>?lhs\<close>
    81     show "continuous (at x within S) ?g" using \<open>?lhs\<close>
   111       by (auto simp add: continuous_within DERIV_within_iff cong: Lim_cong_within)
    82       by (auto simp add: continuous_within has_field_derivative_iff cong: Lim_cong_within)
   112     show "?g x = l" by simp
    83     show "?g x = l" by simp
   113   qed
    84   qed
   114 next
    85 next
   115   assume ?rhs
    86   assume ?rhs
   116   then obtain g where
    87   then obtain g where
   117     "(\<forall>z. f z - f x = g z * (z-x))" and "continuous (at x within S) g" and "g x = l" by blast
    88     "(\<forall>z. f z - f x = g z * (z-x))" and "continuous (at x within S) g" and "g x = l" by blast
   118   thus ?lhs
    89   thus ?lhs
   119     by (auto simp add: continuous_within DERIV_within_iff cong: Lim_cong_within)
    90     by (auto simp add: continuous_within has_field_derivative_iff cong: Lim_cong_within)
   120 qed
    91 qed
   121 
    92 
   122 subsection \<open>Differentiability\<close>
    93 subsection \<open>Differentiability\<close>
   123 
    94 
   124 definition
    95 definition
   171   by (simp add: differentiable_on_def)
   142   by (simp add: differentiable_on_def)
   172 
   143 
   173 lemma differentiable_on_mult [simp, derivative_intros]:
   144 lemma differentiable_on_mult [simp, derivative_intros]:
   174   fixes f :: "'M::real_normed_vector \<Rightarrow> 'a::real_normed_algebra"
   145   fixes f :: "'M::real_normed_vector \<Rightarrow> 'a::real_normed_algebra"
   175   shows "\<lbrakk>f differentiable_on S; g differentiable_on S\<rbrakk> \<Longrightarrow> (\<lambda>z. f z * g z) differentiable_on S"
   146   shows "\<lbrakk>f differentiable_on S; g differentiable_on S\<rbrakk> \<Longrightarrow> (\<lambda>z. f z * g z) differentiable_on S"
   176   apply (simp add: differentiable_on_def differentiable_def)
   147   unfolding differentiable_on_def differentiable_def
   177   using differentiable_def differentiable_mult by blast
   148   using differentiable_def differentiable_mult by blast
   178 
   149 
   179 lemma differentiable_on_compose:
   150 lemma differentiable_on_compose:
   180    "\<lbrakk>g differentiable_on S; f differentiable_on (g ` S)\<rbrakk> \<Longrightarrow> (\<lambda>x. f (g x)) differentiable_on S"
   151    "\<lbrakk>g differentiable_on S; f differentiable_on (g ` S)\<rbrakk> \<Longrightarrow> (\<lambda>x. f (g x)) differentiable_on S"
   181 by (simp add: differentiable_in_compose differentiable_on_def)
   152 by (simp add: differentiable_in_compose differentiable_on_def)
   209    "\<lbrakk>f differentiable_on S; g differentiable_on S\<rbrakk> \<Longrightarrow> (\<lambda>x. f x *\<^sub>R g x) differentiable_on S"
   180    "\<lbrakk>f differentiable_on S; g differentiable_on S\<rbrakk> \<Longrightarrow> (\<lambda>x. f x *\<^sub>R g x) differentiable_on S"
   210   unfolding differentiable_on_def
   181   unfolding differentiable_on_def
   211   by (blast intro: differentiable_scaleR)
   182   by (blast intro: differentiable_scaleR)
   212 
   183 
   213 lemma has_derivative_sqnorm_at [derivative_intros, simp]:
   184 lemma has_derivative_sqnorm_at [derivative_intros, simp]:
   214    "((\<lambda>x. (norm x)\<^sup>2) has_derivative (\<lambda>x. 2 *\<^sub>R (a \<bullet> x))) (at a)"
   185   "((\<lambda>x. (norm x)\<^sup>2) has_derivative (\<lambda>x. 2 *\<^sub>R (a \<bullet> x))) (at a)"
   215 using has_derivative_bilinear_at [of id id a id id "(\<bullet>)"]
   186   using bounded_bilinear.FDERIV  [of "(\<bullet>)" id id a _ id id]
   216 by (auto simp: inner_commute dot_square_norm bounded_bilinear_inner)
   187   by (auto simp: inner_commute dot_square_norm bounded_bilinear_inner)
   217 
   188 
   218 lemma differentiable_sqnorm_at [derivative_intros, simp]:
   189 lemma differentiable_sqnorm_at [derivative_intros, simp]:
   219   fixes a :: "'a :: {real_normed_vector,real_inner}"
   190   fixes a :: "'a :: {real_normed_vector,real_inner}"
   220   shows "(\<lambda>x. (norm x)\<^sup>2) differentiable (at a)"
   191   shows "(\<lambda>x. (norm x)\<^sup>2) differentiable (at a)"
   221 by (force simp add: differentiable_def intro: has_derivative_sqnorm_at)
   192 by (force simp add: differentiable_def intro: has_derivative_sqnorm_at)
   376  limit point from any direction. But OK for nontrivial intervals etc.
   347  limit point from any direction. But OK for nontrivial intervals etc.
   377 \<close>
   348 \<close>
   378 
   349 
   379 lemma frechet_derivative_unique_within:
   350 lemma frechet_derivative_unique_within:
   380   fixes f :: "'a::euclidean_space \<Rightarrow> 'b::real_normed_vector"
   351   fixes f :: "'a::euclidean_space \<Rightarrow> 'b::real_normed_vector"
   381   assumes "(f has_derivative f') (at x within S)"
   352   assumes 1: "(f has_derivative f') (at x within S)"
   382     and "(f has_derivative f'') (at x within S)"
   353     and 2: "(f has_derivative f'') (at x within S)"
   383     and "\<forall>i\<in>Basis. \<forall>e>0. \<exists>d. 0 < \<bar>d\<bar> \<and> \<bar>d\<bar> < e \<and> (x + d *\<^sub>R i) \<in> S"
   354     and S: "\<And>i e. \<lbrakk>i\<in>Basis; e>0\<rbrakk> \<Longrightarrow> \<exists>d. 0 < \<bar>d\<bar> \<and> \<bar>d\<bar> < e \<and> (x + d *\<^sub>R i) \<in> S"
   384   shows "f' = f''"
   355   shows "f' = f''"
   385 proof -
   356 proof -
   386   note as = assms(1,2)[unfolded has_derivative_def]
   357   note as = assms(1,2)[unfolded has_derivative_def]
   387   then interpret f': bounded_linear f' by auto
   358   then interpret f': bounded_linear f' by auto
   388   from as interpret f'': bounded_linear f'' by auto
   359   from as interpret f'': bounded_linear f'' by auto
   389   have "x islimpt S" unfolding islimpt_approachable
   360   have "x islimpt S" unfolding islimpt_approachable
   390   proof (rule, rule)
   361   proof (intro allI impI)
   391     fix e :: real
   362     fix e :: real
   392     assume "e > 0"
   363     assume "e > 0"
   393     obtain d where "0 < \<bar>d\<bar>" and "\<bar>d\<bar> < e" and "x + d *\<^sub>R (SOME i. i \<in> Basis) \<in> S"
   364     obtain d where "0 < \<bar>d\<bar>" and "\<bar>d\<bar> < e" and "x + d *\<^sub>R (SOME i. i \<in> Basis) \<in> S"
   394       using assms(3) SOME_Basis \<open>e>0\<close> by blast
   365       using assms(3) SOME_Basis \<open>e>0\<close> by blast
   395     then show "\<exists>x'\<in>S. x' \<noteq> x \<and> dist x' x < e"
   366     then show "\<exists>x'\<in>S. x' \<noteq> x \<and> dist x' x < e"
   396       apply (rule_tac x="x + d *\<^sub>R (SOME i. i \<in> Basis)" in bexI)
   367       by (rule_tac x="x + d *\<^sub>R (SOME i. i \<in> Basis)" in bexI) (auto simp: dist_norm SOME_Basis nonzero_Basis)  qed
   397       unfolding dist_norm
       
   398       apply (auto simp: SOME_Basis nonzero_Basis)
       
   399       done
       
   400   qed
       
   401   then have *: "netlimit (at x within S) = x"
   368   then have *: "netlimit (at x within S) = x"
   402     apply (auto intro!: netlimit_within)
   369     by (simp add: Lim_ident_at trivial_limit_within)
   403     by (metis trivial_limit_within)
       
   404   show ?thesis
   370   show ?thesis
   405   proof (rule linear_eq_stdbasis)
   371   proof (rule linear_eq_stdbasis)
   406     show "linear f'" "linear f''"
   372     show "linear f'" "linear f''"
   407       unfolding linear_conv_bounded_linear using as by auto
   373       unfolding linear_conv_bounded_linear using as by auto
   408   next
   374   next
   448   qed
   414   qed
   449 qed
   415 qed
   450 
   416 
   451 lemma frechet_derivative_unique_within_closed_interval:
   417 lemma frechet_derivative_unique_within_closed_interval:
   452   fixes f::"'a::euclidean_space \<Rightarrow> 'b::real_normed_vector"
   418   fixes f::"'a::euclidean_space \<Rightarrow> 'b::real_normed_vector"
   453   assumes "\<forall>i\<in>Basis. a\<bullet>i < b\<bullet>i"
   419   assumes ab: "\<And>i. i\<in>Basis \<Longrightarrow> a\<bullet>i < b\<bullet>i"
   454     and "x \<in> cbox a b"
   420     and x: "x \<in> cbox a b"
   455     and "(f has_derivative f' ) (at x within cbox a b)"
   421     and "(f has_derivative f' ) (at x within cbox a b)"
   456     and "(f has_derivative f'') (at x within cbox a b)"
   422     and "(f has_derivative f'') (at x within cbox a b)"
   457   shows "f' = f''"
   423   shows "f' = f''"
   458   apply(rule frechet_derivative_unique_within)
   424 proof (rule frechet_derivative_unique_within)
   459   apply(rule assms(3,4))+
       
   460 proof (rule, rule, rule)
       
   461   fix e :: real
   425   fix e :: real
   462   fix i :: 'a
   426   fix i :: 'a
   463   assume "e > 0" and i: "i \<in> Basis"
   427   assume "e > 0" and i: "i \<in> Basis"
   464   then show "\<exists>d. 0 < \<bar>d\<bar> \<and> \<bar>d\<bar> < e \<and> x + d *\<^sub>R i \<in> cbox a b"
   428   then show "\<exists>d. 0 < \<bar>d\<bar> \<and> \<bar>d\<bar> < e \<and> x + d *\<^sub>R i \<in> cbox a b"
   465   proof (cases "x\<bullet>i = a\<bullet>i")
   429   proof (cases "x\<bullet>i = a\<bullet>i")
   466     case True
   430     case True
   467     then show ?thesis
   431     with ab[of i] \<open>e>0\<close> x i show ?thesis
   468       apply (rule_tac x="(min (b\<bullet>i - a\<bullet>i)  e) / 2" in exI)
   432       by (rule_tac x="(min (b\<bullet>i - a\<bullet>i) e) / 2" in exI)
   469       using assms(1)[THEN bspec[where x=i]] and \<open>e>0\<close> and assms(2)
   433          (auto simp add: mem_box field_simps inner_simps inner_Basis)
   470       unfolding mem_box
       
   471       using i
       
   472       apply (auto simp add: field_simps inner_simps inner_Basis)
       
   473       done
       
   474   next
   434   next
   475     note * = assms(2)[unfolded mem_box, THEN bspec, OF i]
       
   476     case False
   435     case False
   477     moreover have "a \<bullet> i < x \<bullet> i"
   436     moreover have "a \<bullet> i < x \<bullet> i"
   478       using False * by auto
   437       using False i mem_box(2) x by force
   479     moreover {
   438     moreover {
   480       have "a \<bullet> i * 2 + min (x \<bullet> i - a \<bullet> i) e \<le> a\<bullet>i *2 + x\<bullet>i - a\<bullet>i"
   439       have "a \<bullet> i * 2 + min (x \<bullet> i - a \<bullet> i) e \<le> a\<bullet>i *2 + x\<bullet>i - a\<bullet>i"
   481         by auto
   440         by auto
   482       also have "\<dots> = a\<bullet>i + x\<bullet>i"
   441       also have "\<dots> = a\<bullet>i + x\<bullet>i"
   483         by auto
   442         by auto
   484       also have "\<dots> \<le> 2 * (x\<bullet>i)"
   443       also have "\<dots> \<le> 2 * (x\<bullet>i)"
   485         using * by auto
   444         using \<open>a \<bullet> i < x \<bullet> i\<close> by auto
   486       finally have "a \<bullet> i * 2 + min (x \<bullet> i - a \<bullet> i) e \<le> x \<bullet> i * 2"
   445       finally have "a \<bullet> i * 2 + min (x \<bullet> i - a \<bullet> i) e \<le> x \<bullet> i * 2"
   487         by auto
   446         by auto
   488     }
   447     }
   489     moreover have "min (x \<bullet> i - a \<bullet> i) e \<ge> 0"
   448     moreover have "min (x \<bullet> i - a \<bullet> i) e \<ge> 0"
   490       using * and \<open>e>0\<close> by auto
   449       by (simp add: \<open>0 < e\<close> \<open>a \<bullet> i < x \<bullet> i\<close> less_eq_real_def)
   491     then have "x \<bullet> i * 2 \<le> b \<bullet> i * 2 + min (x \<bullet> i - a \<bullet> i) e"
   450     then have "x \<bullet> i * 2 \<le> b \<bullet> i * 2 + min (x \<bullet> i - a \<bullet> i) e"
   492       using * by auto
   451       using i mem_box(2) x by force
   493     ultimately show ?thesis
   452     ultimately show ?thesis
   494       apply (rule_tac x="- (min (x\<bullet>i - a\<bullet>i) e) / 2" in exI)
   453     using ab[of i] \<open>e>0\<close> x i 
   495       using assms(1)[THEN bspec, OF i] and \<open>e>0\<close> and assms(2)
   454       by (rule_tac x="- (min (x\<bullet>i - a\<bullet>i) e) / 2" in exI)
   496       unfolding mem_box
   455          (auto simp add: mem_box field_simps inner_simps inner_Basis)
   497       using i
       
   498       apply (auto simp add: field_simps inner_simps inner_Basis)
       
   499       done
       
   500   qed
   456   qed
   501 qed
   457 qed (use assms in auto)
   502 
   458 
   503 lemma frechet_derivative_unique_within_open_interval:
   459 lemma frechet_derivative_unique_within_open_interval:
   504   fixes f::"'a::euclidean_space \<Rightarrow> 'b::real_normed_vector"
   460   fixes f::"'a::euclidean_space \<Rightarrow> 'b::real_normed_vector"
   505   assumes "x \<in> box a b"
   461   assumes x: "x \<in> box a b"
   506     and "(f has_derivative f' ) (at x within box a b)"
   462     and f: "(f has_derivative f' ) (at x within box a b)" "(f has_derivative f'') (at x within box a b)"
   507     and "(f has_derivative f'') (at x within box a b)"
       
   508   shows "f' = f''"
   463   shows "f' = f''"
   509 proof -
   464 proof -
   510   from assms(1) have *: "at x within box a b = at x"
   465   have "at x within box a b = at x"
   511     by (metis at_within_interior interior_open open_box)
   466     by (metis x at_within_interior interior_open open_box)
   512   from assms(2,3) [unfolded *] show "f' = f''"
   467   with f show "f' = f''"
   513     by (rule has_derivative_unique)
   468     by (simp add: has_derivative_unique)
   514 qed
   469 qed
   515 
   470 
   516 lemma frechet_derivative_at:
   471 lemma frechet_derivative_at:
   517   "(f has_derivative f') (at x) \<Longrightarrow> f' = frechet_derivative f (at x)"
   472   "(f has_derivative f') (at x) \<Longrightarrow> f' = frechet_derivative f (at x)"
   518   apply (rule has_derivative_unique[of f])
   473   using differentiable_def frechet_derivative_works has_derivative_unique by blast
   519   apply assumption
       
   520   unfolding frechet_derivative_works[symmetric]
       
   521   using differentiable_def
       
   522   apply auto
       
   523   done
       
   524 
   474 
   525 lemma frechet_derivative_within_cbox:
   475 lemma frechet_derivative_within_cbox:
   526   fixes f :: "'a::euclidean_space \<Rightarrow> 'b::real_normed_vector"
   476   fixes f :: "'a::euclidean_space \<Rightarrow> 'b::real_normed_vector"
   527   assumes "\<forall>i\<in>Basis. a\<bullet>i < b\<bullet>i"
   477   assumes "\<And>i. i\<in>Basis \<Longrightarrow> a\<bullet>i < b\<bullet>i"
   528     and "x \<in> cbox a b"
   478     and "x \<in> cbox a b"
   529     and "(f has_derivative f') (at x within cbox a b)"
   479     and "(f has_derivative f') (at x within cbox a b)"
   530   shows "frechet_derivative f (at x within cbox a b) = f'"
   480   shows "frechet_derivative f (at x within cbox a b) = f'"
   531   using assms
   481   using assms
   532   by (metis Derivative.differentiableI frechet_derivative_unique_within_closed_interval frechet_derivative_works)
   482   by (metis Derivative.differentiableI frechet_derivative_unique_within_closed_interval frechet_derivative_works)
   545   fix h :: 'a
   495   fix h :: 'a
   546   interpret f': bounded_linear f'
   496   interpret f': bounded_linear f'
   547     using deriv by (rule has_derivative_bounded_linear)
   497     using deriv by (rule has_derivative_bounded_linear)
   548   show "f' h = 0"
   498   show "f' h = 0"
   549   proof (cases "h = 0")
   499   proof (cases "h = 0")
   550     assume "h \<noteq> 0"
   500     case False
   551     from min obtain d where d1: "0 < d" and d2: "\<forall>y\<in>ball x d. f x \<le> f y"
   501     from min obtain d where d1: "0 < d" and d2: "\<forall>y\<in>ball x d. f x \<le> f y"
   552       unfolding eventually_at by (force simp: dist_commute)
   502       unfolding eventually_at by (force simp: dist_commute)
   553     have "FDERIV (\<lambda>r. x + r *\<^sub>R h) 0 :> (\<lambda>r. r *\<^sub>R h)"
   503     have "FDERIV (\<lambda>r. x + r *\<^sub>R h) 0 :> (\<lambda>r. r *\<^sub>R h)"
   554       by (intro derivative_eq_intros) auto
   504       by (intro derivative_eq_intros) auto
   555     then have "FDERIV (\<lambda>r. f (x + r *\<^sub>R h)) 0 :> (\<lambda>k. f' (k *\<^sub>R h))"
   505     then have "FDERIV (\<lambda>r. f (x + r *\<^sub>R h)) 0 :> (\<lambda>k. f' (k *\<^sub>R h))"
   559     moreover have "0 < d / norm h" using d1 and \<open>h \<noteq> 0\<close> by simp
   509     moreover have "0 < d / norm h" using d1 and \<open>h \<noteq> 0\<close> by simp
   560     moreover have "\<forall>y. \<bar>0 - y\<bar> < d / norm h \<longrightarrow> f (x + 0 *\<^sub>R h) \<le> f (x + y *\<^sub>R h)"
   510     moreover have "\<forall>y. \<bar>0 - y\<bar> < d / norm h \<longrightarrow> f (x + 0 *\<^sub>R h) \<le> f (x + y *\<^sub>R h)"
   561       using \<open>h \<noteq> 0\<close> by (auto simp add: d2 dist_norm pos_less_divide_eq)
   511       using \<open>h \<noteq> 0\<close> by (auto simp add: d2 dist_norm pos_less_divide_eq)
   562     ultimately show "f' h = 0"
   512     ultimately show "f' h = 0"
   563       by (rule DERIV_local_min)
   513       by (rule DERIV_local_min)
   564   qed (simp add: f'.zero)
   514   qed simp
   565 qed
   515 qed
   566 
   516 
   567 lemma has_derivative_local_max:
   517 lemma has_derivative_local_max:
   568   fixes f :: "'a::real_normed_vector \<Rightarrow> real"
   518   fixes f :: "'a::real_normed_vector \<Rightarrow> real"
   569   assumes "(f has_derivative f') (at x)"
   519   assumes "(f has_derivative f') (at x)"
   572   using has_derivative_local_min [of "\<lambda>x. - f x" "\<lambda>h. - f' h" "x"]
   522   using has_derivative_local_min [of "\<lambda>x. - f x" "\<lambda>h. - f' h" "x"]
   573   using assms unfolding fun_eq_iff by simp
   523   using assms unfolding fun_eq_iff by simp
   574 
   524 
   575 lemma differential_zero_maxmin:
   525 lemma differential_zero_maxmin:
   576   fixes f::"'a::real_normed_vector \<Rightarrow> real"
   526   fixes f::"'a::real_normed_vector \<Rightarrow> real"
   577   assumes "x \<in> s"
   527   assumes "x \<in> S"
   578     and "open s"
   528     and "open S"
   579     and deriv: "(f has_derivative f') (at x)"
   529     and deriv: "(f has_derivative f') (at x)"
   580     and mono: "(\<forall>y\<in>s. f y \<le> f x) \<or> (\<forall>y\<in>s. f x \<le> f y)"
   530     and mono: "(\<forall>y\<in>S. f y \<le> f x) \<or> (\<forall>y\<in>S. f x \<le> f y)"
   581   shows "f' = (\<lambda>v. 0)"
   531   shows "f' = (\<lambda>v. 0)"
   582   using mono
   532   using mono
   583 proof
   533 proof
   584   assume "\<forall>y\<in>s. f y \<le> f x"
   534   assume "\<forall>y\<in>S. f y \<le> f x"
   585   with \<open>x \<in> s\<close> and \<open>open s\<close> have "eventually (\<lambda>y. f y \<le> f x) (at x)"
   535   with \<open>x \<in> S\<close> and \<open>open S\<close> have "eventually (\<lambda>y. f y \<le> f x) (at x)"
   586     unfolding eventually_at_topological by auto
   536     unfolding eventually_at_topological by auto
   587   with deriv show ?thesis
   537   with deriv show ?thesis
   588     by (rule has_derivative_local_max)
   538     by (rule has_derivative_local_max)
   589 next
   539 next
   590   assume "\<forall>y\<in>s. f x \<le> f y"
   540   assume "\<forall>y\<in>S. f x \<le> f y"
   591   with \<open>x \<in> s\<close> and \<open>open s\<close> have "eventually (\<lambda>y. f x \<le> f y) (at x)"
   541   with \<open>x \<in> S\<close> and \<open>open S\<close> have "eventually (\<lambda>y. f x \<le> f y) (at x)"
   592     unfolding eventually_at_topological by auto
   542     unfolding eventually_at_topological by auto
   593   with deriv show ?thesis
   543   with deriv show ?thesis
   594     by (rule has_derivative_local_min)
   544     by (rule has_derivative_local_min)
   595 qed
   545 qed
   596 
   546 
   611     using ball(2) by (rule differential_zero_maxmin)
   561     using ball(2) by (rule differential_zero_maxmin)
   612   then show ?thesis
   562   then show ?thesis
   613     unfolding fun_eq_iff by simp
   563     unfolding fun_eq_iff by simp
   614 qed
   564 qed
   615 
   565 
   616 lemma rolle:
   566 theorem Rolle:
   617   fixes f :: "real \<Rightarrow> real"
   567   fixes f :: "real \<Rightarrow> real"
   618   assumes "a < b"
   568   assumes "a < b"
   619     and "f a = f b"
   569     and fab: "f a = f b"
   620     and "continuous_on {a .. b} f"
   570     and contf: "continuous_on {a..b} f"
   621     and "\<forall>x\<in>{a <..< b}. (f has_derivative f' x) (at x)"
   571     and derf: "\<And>x. \<lbrakk>a < x; x < b\<rbrakk> \<Longrightarrow> (f has_derivative f' x) (at x)"
   622   shows "\<exists>x\<in>{a <..< b}. f' x = (\<lambda>v. 0)"
   572   shows "\<exists>x\<in>{a <..< b}. f' x = (\<lambda>v. 0)"
   623 proof -
   573 proof -
   624   have "\<exists>x\<in>box a b. (\<forall>y\<in>box a b. f x \<le> f y) \<or> (\<forall>y\<in>box a b. f y \<le> f x)"
   574   have "\<exists>x\<in>box a b. (\<forall>y\<in>box a b. f x \<le> f y) \<or> (\<forall>y\<in>box a b. f y \<le> f x)"
   625   proof -
   575   proof -
   626     have "(a + b) / 2 \<in> {a .. b}"
   576     have "(a + b) / 2 \<in> {a..b}"
   627       using assms(1) by auto
   577       using assms(1) by auto
   628     then have *: "{a .. b} \<noteq> {}"
   578     then have *: "{a..b} \<noteq> {}"
   629       by auto
   579       by auto
   630     obtain d where d:
   580     obtain d where d: "d \<in>cbox a b" "\<forall>y\<in>cbox a b. f y \<le> f d"
   631         "d \<in>cbox a b"
   581       using continuous_attains_sup[OF compact_Icc * contf] by auto
   632         "\<forall>y\<in>cbox a b. f y \<le> f d"
   582     obtain c where c: "c \<in> cbox a b" "\<forall>y\<in>cbox a b. f c \<le> f y"
   633       using continuous_attains_sup[OF compact_Icc * assms(3)] by auto
   583       using continuous_attains_inf[OF compact_Icc * contf] by auto
   634     obtain c where c:
       
   635         "c \<in> cbox a b"
       
   636         "\<forall>y\<in>cbox a b. f c \<le> f y"
       
   637       using continuous_attains_inf[OF compact_Icc * assms(3)] by auto
       
   638     show ?thesis
   584     show ?thesis
   639     proof (cases "d \<in> box a b \<or> c \<in> box a b")
   585     proof (cases "d \<in> box a b \<or> c \<in> box a b")
   640       case True
   586       case True
   641       then show ?thesis
   587       then show ?thesis
   642         by (metis c(2) d(2) box_subset_cbox subset_iff)
   588         by (metis c(2) d(2) box_subset_cbox subset_iff)
   643     next
   589     next
   644       define e where "e = (a + b) /2"
   590       define e where "e = (a + b) /2"
   645       case False
   591       case False
   646       then have "f d = f c"
   592       then have "f d = f c"
   647         using d c assms(2) by auto
   593         using d c fab by auto
   648       then have "\<And>x. x \<in> {a..b} \<Longrightarrow> f x = f d"
   594       with c d have "\<And>x. x \<in> {a..b} \<Longrightarrow> f x = f d"
   649         using c d
       
   650         by force
   595         by force
   651       then show ?thesis
   596       then show ?thesis
   652         apply (rule_tac x=e in bexI)
   597         by (rule_tac x=e in bexI) (auto simp: e_def \<open>a < b\<close>)
   653         unfolding e_def
       
   654         using assms(1)
       
   655         apply auto
       
   656         done
       
   657     qed
   598     qed
   658   qed
   599   qed
   659   then obtain x where x: "x \<in> {a <..< b}" "(\<forall>y\<in>{a <..< b}. f x \<le> f y) \<or> (\<forall>y\<in>{a <..< b}. f y \<le> f x)"
   600   then obtain x where x: "x \<in> {a <..< b}" "(\<forall>y\<in>{a <..< b}. f x \<le> f y) \<or> (\<forall>y\<in>{a <..< b}. f y \<le> f x)"
   660     by auto
   601     by auto
   661   then have "f' x = (\<lambda>v. 0)"
   602   then have "f' x = (\<lambda>v. 0)"
   671 subsection \<open>One-dimensional mean value theorem\<close>
   612 subsection \<open>One-dimensional mean value theorem\<close>
   672 
   613 
   673 lemma mvt:
   614 lemma mvt:
   674   fixes f :: "real \<Rightarrow> real"
   615   fixes f :: "real \<Rightarrow> real"
   675   assumes "a < b"
   616   assumes "a < b"
   676     and "continuous_on {a..b} f"
   617     and contf: "continuous_on {a..b} f"
   677   assumes "\<forall>x\<in>{a<..<b}. (f has_derivative (f' x)) (at x)"
   618     and derf: "\<And>x. \<lbrakk>a < x; x < b\<rbrakk> \<Longrightarrow> (f has_derivative f' x) (at x)"
   678   shows "\<exists>x\<in>{a<..<b}. f b - f a = (f' x) (b - a)"
   619   shows "\<exists>x\<in>{a<..<b}. f b - f a = (f' x) (b - a)"
   679 proof -
   620 proof -
   680   have "\<exists>x\<in>{a <..< b}. (\<lambda>xa. f' x xa - (f b - f a) / (b - a) * xa) = (\<lambda>v. 0)"
   621   have "\<exists>x\<in>{a <..< b}. (\<lambda>xa. f' x xa - (f b - f a) / (b - a) * xa) = (\<lambda>v. 0)"
   681   proof (intro rolle[OF assms(1), of "\<lambda>x. f x - (f b - f a) / (b - a) * x"] ballI)
   622   proof (intro Rolle[OF \<open>a < b\<close>, of "\<lambda>x. f x - (f b - f a) / (b - a) * x"] ballI)
   682     fix x
   623     fix x
   683     assume x: "x \<in> {a <..< b}"
   624     assume x: "a < x" "x < b"
   684     show "((\<lambda>x. f x - (f b - f a) / (b - a) * x) has_derivative
   625     show "((\<lambda>x. f x - (f b - f a) / (b - a) * x) has_derivative
   685         (\<lambda>xa. f' x xa - (f b - f a) / (b - a) * xa)) (at x)"
   626         (\<lambda>xa. f' x xa - (f b - f a) / (b - a) * xa)) (at x)"
   686       by (intro derivative_intros assms(3)[rule_format,OF x])
   627       by (intro derivative_intros derf[OF x])
   687   qed (insert assms(1,2), auto intro!: continuous_intros simp: field_simps)
   628   qed (use assms in \<open>auto intro!: continuous_intros simp: field_simps\<close>)
   688   then obtain x where
   629   then obtain x where
   689     "x \<in> {a <..< b}"
   630     "x \<in> {a <..< b}"
   690     "(\<lambda>xa. f' x xa - (f b - f a) / (b - a) * xa) = (\<lambda>v. 0)" ..
   631     "(\<lambda>xa. f' x xa - (f b - f a) / (b - a) * xa) = (\<lambda>v. 0)" ..
   691   then show ?thesis
   632   then show ?thesis
   692     by (metis (hide_lams) assms(1) diff_gt_0_iff_gt eq_iff_diff_eq_0
   633     by (metis (hide_lams) assms(1) diff_gt_0_iff_gt eq_iff_diff_eq_0
   695 qed
   636 qed
   696 
   637 
   697 lemma mvt_simple:
   638 lemma mvt_simple:
   698   fixes f :: "real \<Rightarrow> real"
   639   fixes f :: "real \<Rightarrow> real"
   699   assumes "a < b"
   640   assumes "a < b"
   700     and "\<forall>x\<in>{a..b}. (f has_derivative f' x) (at x within {a..b})"
   641     and derf: "\<And>x. \<lbrakk>a \<le> x; x \<le> b\<rbrakk> \<Longrightarrow> (f has_derivative f' x) (at x)"
   701   shows "\<exists>x\<in>{a<..<b}. f b - f a = f' x (b - a)"
   642   shows "\<exists>x\<in>{a<..<b}. f b - f a = f' x (b - a)"
   702 proof (rule mvt)
   643 proof (rule mvt)
   703   have "f differentiable_on {a..b}"
   644   have "f differentiable_on {a..b}"
   704     using assms(2) unfolding differentiable_on_def differentiable_def by fast
   645     by (meson atLeastAtMost_iff derf differentiable_at_imp_differentiable_on differentiable_def)
   705   then show "continuous_on {a..b} f"
   646   then show "continuous_on {a..b} f"
   706     by (rule differentiable_imp_continuous_on)
   647     by (rule differentiable_imp_continuous_on)
   707   show "\<forall>x\<in>{a<..<b}. (f has_derivative f' x) (at x)"
   648   show "(f has_derivative f' x) (at x)" if "a < x" "x < b" for x
   708   proof
   649     by (metis derf not_less order.asym that)
   709     fix x
   650 qed (rule assms)
   710     assume x: "x \<in> {a <..< b}"
       
   711     show "(f has_derivative f' x) (at x)"
       
   712       unfolding at_within_open[OF x open_greaterThanLessThan,symmetric]
       
   713       apply (rule has_derivative_within_subset)
       
   714       apply (rule assms(2)[rule_format])
       
   715       using x
       
   716       apply auto
       
   717       done
       
   718   qed
       
   719 qed (rule assms(1))
       
   720 
   651 
   721 lemma mvt_very_simple:
   652 lemma mvt_very_simple:
   722   fixes f :: "real \<Rightarrow> real"
   653   fixes f :: "real \<Rightarrow> real"
   723   assumes "a \<le> b"
   654   assumes "a \<le> b"
   724     and "\<forall>x\<in>{a .. b}. (f has_derivative f' x) (at x within {a .. b})"
   655     and derf: "\<And>x. \<lbrakk>a \<le> x; x \<le> b\<rbrakk> \<Longrightarrow> (f has_derivative f' x) (at x)"
   725   shows "\<exists>x\<in>{a .. b}. f b - f a = f' x (b - a)"
   656   shows "\<exists>x\<in>{a..b}. f b - f a = f' x (b - a)"
   726 proof (cases "a = b")
   657 proof (cases "a = b")
   727   interpret bounded_linear "f' b"
   658   interpret bounded_linear "f' b"
   728     using assms(2) assms(1) by auto
   659     using assms(2) assms(1) by auto
   729   case True
   660   case True
   730   then show ?thesis
   661   then show ?thesis
   731     apply (rule_tac x=a in bexI)
   662     by force
   732     using assms(2)[THEN bspec[where x=a]]
       
   733     unfolding has_derivative_def
       
   734     unfolding True
       
   735     using zero
       
   736     apply auto
       
   737     done
       
   738 next
   663 next
   739   case False
   664   case False
   740   then show ?thesis
   665   then show ?thesis
   741     using mvt_simple[OF _ assms(2)]
   666     using mvt_simple[OF _ derf]
   742     using assms(1)
   667     by (metis \<open>a \<le> b\<close> atLeastAtMost_iff dual_order.order_iff_strict greaterThanLessThan_iff)
   743     by auto
       
   744 qed
   668 qed
   745 
   669 
   746 text \<open>A nice generalization (see Havin's proof of 5.19 from Rudin's book).\<close>
   670 text \<open>A nice generalization (see Havin's proof of 5.19 from Rudin's book).\<close>
   747 
   671 
   748 lemma mvt_general:
   672 lemma mvt_general:
   749   fixes f :: "real \<Rightarrow> 'a::real_inner"
   673   fixes f :: "real \<Rightarrow> 'a::real_inner"
   750   assumes "a < b"
   674   assumes "a < b"
   751     and "continuous_on {a .. b} f"
   675     and contf: "continuous_on {a..b} f"
   752     and "\<forall>x\<in>{a<..<b}. (f has_derivative f'(x)) (at x)"
   676     and derf: "\<And>x. \<lbrakk>a < x; x < b\<rbrakk> \<Longrightarrow> (f has_derivative f' x) (at x)"
   753   shows "\<exists>x\<in>{a<..<b}. norm (f b - f a) \<le> norm (f' x (b - a))"
   677   shows "\<exists>x\<in>{a<..<b}. norm (f b - f a) \<le> norm (f' x (b - a))"
   754 proof -
   678 proof -
   755   have "\<exists>x\<in>{a<..<b}. (f b - f a) \<bullet> f b - (f b - f a) \<bullet> f a = (f b - f a) \<bullet> f' x (b - a)"
   679   have "\<exists>x\<in>{a<..<b}. (f b - f a) \<bullet> f b - (f b - f a) \<bullet> f a = (f b - f a) \<bullet> f' x (b - a)"
   756     apply (rule mvt)
   680     apply (rule mvt [OF \<open>a < b\<close>])
   757     apply (rule assms(1))
   681     apply (intro continuous_intros contf)
   758     apply (intro continuous_intros assms(2))
   682     using derf apply (blast intro: has_derivative_inner_right)
   759     using assms(3)
       
   760     apply (fast intro: has_derivative_inner_right)
       
   761     done
   683     done
   762   then obtain x where x:
   684   then obtain x where x: "x \<in> {a<..<b}"
   763     "x \<in> {a<..<b}"
       
   764     "(f b - f a) \<bullet> f b - (f b - f a) \<bullet> f a = (f b - f a) \<bullet> f' x (b - a)" ..
   685     "(f b - f a) \<bullet> f b - (f b - f a) \<bullet> f a = (f b - f a) \<bullet> f' x (b - a)" ..
   765   show ?thesis
   686   show ?thesis
   766   proof (cases "f a = f b")
   687   proof (cases "f a = f b")
   767     case False
   688     case False
   768     have "norm (f b - f a) * norm (f b - f a) = (norm (f b - f a))\<^sup>2"
   689     have "norm (f b - f a) * norm (f b - f a) = (norm (f b - f a))\<^sup>2"
   777       using False x(1)
   698       using False x(1)
   778       by (auto simp add: mult_left_cancel)
   699       by (auto simp add: mult_left_cancel)
   779   next
   700   next
   780     case True
   701     case True
   781     then show ?thesis
   702     then show ?thesis
   782       using assms(1)
   703       using \<open>a < b\<close> by (rule_tac x="(a + b) /2" in bexI) auto
   783       apply (rule_tac x="(a + b) /2" in bexI)
       
   784       apply auto
       
   785       done
       
   786   qed
   704   qed
   787 qed
   705 qed
   788 
   706 
   789 
   707 
   790 subsection \<open>More general bound theorems\<close>
   708 subsection \<open>More general bound theorems\<close>
   791 
   709 
   792 lemma differentiable_bound_general:
   710 proposition differentiable_bound_general:
   793   fixes f :: "real \<Rightarrow> 'a::real_normed_vector"
   711   fixes f :: "real \<Rightarrow> 'a::real_normed_vector"
   794   assumes "a < b"
   712   assumes "a < b"
   795     and f_cont: "continuous_on {a .. b} f"
   713     and f_cont: "continuous_on {a..b} f"
   796     and phi_cont: "continuous_on {a .. b} \<phi>"
   714     and phi_cont: "continuous_on {a..b} \<phi>"
   797     and f': "\<And>x. a < x \<Longrightarrow> x < b \<Longrightarrow> (f has_vector_derivative f' x) (at x)"
   715     and f': "\<And>x. a < x \<Longrightarrow> x < b \<Longrightarrow> (f has_vector_derivative f' x) (at x)"
   798     and phi': "\<And>x. a < x \<Longrightarrow> x < b \<Longrightarrow> (\<phi> has_vector_derivative \<phi>' x) (at x)"
   716     and phi': "\<And>x. a < x \<Longrightarrow> x < b \<Longrightarrow> (\<phi> has_vector_derivative \<phi>' x) (at x)"
   799     and bnd: "\<And>x. a < x \<Longrightarrow> x < b \<Longrightarrow> norm (f' x) \<le> \<phi>' x"
   717     and bnd: "\<And>x. a < x \<Longrightarrow> x < b \<Longrightarrow> norm (f' x) \<le> \<phi>' x"
   800   shows "norm (f b - f a) \<le> \<phi> b - \<phi> a"
   718   shows "norm (f b - f a) \<le> \<phi> b - \<phi> a"
   801 proof -
   719 proof -
   811     fix e::real assume "e > 0"
   729     fix e::real assume "e > 0"
   812     define e2 where "e2 = e / 2"
   730     define e2 where "e2 = e / 2"
   813     with \<open>e > 0\<close> have "e2 > 0" by simp
   731     with \<open>e > 0\<close> have "e2 > 0" by simp
   814     let ?le = "\<lambda>x1. norm (f x1 - f a) \<le> \<phi> x1 - \<phi> a + e * (x1 - a) + e"
   732     let ?le = "\<lambda>x1. norm (f x1 - f a) \<le> \<phi> x1 - \<phi> a + e * (x1 - a) + e"
   815     define A where "A = {x2. a \<le> x2 \<and> x2 \<le> b \<and> (\<forall>x1\<in>{a ..< x2}. ?le x1)}"
   733     define A where "A = {x2. a \<le> x2 \<and> x2 \<le> b \<and> (\<forall>x1\<in>{a ..< x2}. ?le x1)}"
   816     have A_subset: "A \<subseteq> {a .. b}" by (auto simp: A_def)
   734     have A_subset: "A \<subseteq> {a..b}" by (auto simp: A_def)
   817     {
   735     {
   818       fix x2
   736       fix x2
   819       assume a: "a \<le> x2" "x2 \<le> b" and le: "\<forall>x1\<in>{a..<x2}. ?le x1"
   737       assume a: "a \<le> x2" "x2 \<le> b" and le: "\<forall>x1\<in>{a..<x2}. ?le x1"
   820       have "?le x2" using \<open>e > 0\<close>
   738       have "?le x2" using \<open>e > 0\<close>
   821       proof cases
   739       proof cases
   826         moreover
   744         moreover
   827         have "((\<lambda>x1. (\<phi> x1 - \<phi> a) + e * (x1 - a) + e) \<longlongrightarrow> (\<phi> x2 - \<phi> a) + e * (x2 - a) + e) (at x2 within {a <..<x2})"
   745         have "((\<lambda>x1. (\<phi> x1 - \<phi> a) + e * (x1 - a) + e) \<longlongrightarrow> (\<phi> x2 - \<phi> a) + e * (x2 - a) + e) (at x2 within {a <..<x2})"
   828           "((\<lambda>x1. norm (f x1 - f a)) \<longlongrightarrow> norm (f x2 - f a)) (at x2 within {a <..<x2})"
   746           "((\<lambda>x1. norm (f x1 - f a)) \<longlongrightarrow> norm (f x2 - f a)) (at x2 within {a <..<x2})"
   829           using a
   747           using a
   830           by (auto intro!: tendsto_eq_intros f_tendsto phi_tendsto
   748           by (auto intro!: tendsto_eq_intros f_tendsto phi_tendsto
   831             intro: tendsto_within_subset[where S="{a .. b}"])
   749             intro: tendsto_within_subset[where S="{a..b}"])
   832         moreover
   750         moreover
   833         have "eventually (\<lambda>x. x > a) (at x2 within {a <..<x2})"
   751         have "eventually (\<lambda>x. x > a) (at x2 within {a <..<x2})"
   834           by (auto simp: eventually_at_filter)
   752           by (auto simp: eventually_at_filter)
   835         hence "eventually ?le (at x2 within {a <..<x2})"
   753         hence "eventually ?le (at x2 within {a <..<x2})"
   836           unfolding eventually_at_filter
   754           unfolding eventually_at_filter
   858       by (metis \<open>a \<in> A\<close> \<open>bdd_above A\<close> cSup_upper y_def)
   776       by (metis \<open>a \<in> A\<close> \<open>bdd_above A\<close> cSup_upper y_def)
   859     have "y \<in> A"
   777     have "y \<in> A"
   860       using y_all_le \<open>a \<le> y\<close> \<open>y \<le> b\<close>
   778       using y_all_le \<open>a \<le> y\<close> \<open>y \<le> b\<close>
   861       by (auto simp: A_def)
   779       by (auto simp: A_def)
   862     hence "A = {a .. y}"
   780     hence "A = {a .. y}"
   863       using A_subset
   781       using A_subset by (auto simp: subset_iff y_def cSup_upper intro: A_ivl)
   864       by (auto simp: subset_iff y_def cSup_upper intro: A_ivl)
       
   865     from le_cont[OF \<open>a \<le> y\<close> \<open>y \<le> b\<close> y_all_le] have le_y: "?le y" .
   782     from le_cont[OF \<open>a \<le> y\<close> \<open>y \<le> b\<close> y_all_le] have le_y: "?le y" .
   866     {
   783     have "y = b"
   867       assume "a \<noteq> y" with \<open>a \<le> y\<close> have "a < y" by simp
   784     proof (cases "a = y")
   868       have "y = b"
   785       case True
   869       proof (rule ccontr)
       
   870         assume "y \<noteq> b"
       
   871         hence "y < b" using \<open>y \<le> b\<close> by simp
       
   872         let ?F = "at y within {y..<b}"
       
   873         from f' phi'
       
   874         have "(f has_vector_derivative f' y) ?F"
       
   875           and "(\<phi> has_vector_derivative \<phi>' y) ?F"
       
   876           using \<open>a < y\<close> \<open>y < b\<close>
       
   877           by (auto simp add: at_within_open[of _ "{a<..<b}"] has_vector_derivative_def
       
   878             intro!: has_derivative_subset[where s="{a<..<b}" and t="{y..<b}"])
       
   879         hence "\<forall>\<^sub>F x1 in ?F. norm (f x1 - f y - (x1 - y) *\<^sub>R f' y) \<le> e2 * \<bar>x1 - y\<bar>"
       
   880             "\<forall>\<^sub>F x1 in ?F. norm (\<phi> x1 - \<phi> y - (x1 - y) *\<^sub>R \<phi>' y) \<le> e2 * \<bar>x1 - y\<bar>"
       
   881           using \<open>e2 > 0\<close>
       
   882           by (auto simp: has_derivative_within_alt2 has_vector_derivative_def)
       
   883         moreover
       
   884         have "\<forall>\<^sub>F x1 in ?F. y \<le> x1" "\<forall>\<^sub>F x1 in ?F. x1 < b"
       
   885           by (auto simp: eventually_at_filter)
       
   886         ultimately
       
   887         have "\<forall>\<^sub>F x1 in ?F. norm (f x1 - f y) \<le> (\<phi> x1 - \<phi> y) + e * \<bar>x1 - y\<bar>"
       
   888           (is "\<forall>\<^sub>F x1 in ?F. ?le' x1")
       
   889         proof eventually_elim
       
   890           case (elim x1)
       
   891           from norm_triangle_ineq2[THEN order_trans, OF elim(1)]
       
   892           have "norm (f x1 - f y) \<le> norm (f' y) * \<bar>x1 - y\<bar> + e2 * \<bar>x1 - y\<bar>"
       
   893             by (simp add: ac_simps)
       
   894           also have "norm (f' y) \<le> \<phi>' y" using bnd \<open>a < y\<close> \<open>y < b\<close> by simp
       
   895           also
       
   896           from elim have "\<phi>' y * \<bar>x1 - y\<bar> \<le> \<phi> x1 - \<phi> y + e2 * \<bar>x1 - y\<bar>"
       
   897             by (simp add: ac_simps)
       
   898           finally
       
   899           have "norm (f x1 - f y) \<le> \<phi> x1 - \<phi> y + e2 * \<bar>x1 - y\<bar> + e2 * \<bar>x1 - y\<bar>"
       
   900             by (auto simp: mult_right_mono)
       
   901           thus ?case by (simp add: e2_def)
       
   902         qed
       
   903         moreover have "?le' y" by simp
       
   904         ultimately obtain S
       
   905         where S: "open S" "y \<in> S" "\<And>x. x\<in>S \<Longrightarrow> x \<in> {y..<b} \<Longrightarrow> ?le' x"
       
   906           unfolding eventually_at_topological
       
   907           by metis
       
   908         from \<open>open S\<close> obtain d where d: "\<And>x. dist x y < d \<Longrightarrow> x \<in> S" "d > 0"
       
   909           by (force simp: dist_commute open_dist ball_def dest!: bspec[OF _ \<open>y \<in> S\<close>])
       
   910         define d' where "d' = min ((y + b)/2) (y + (d/2))"
       
   911         have "d' \<in> A"
       
   912           unfolding A_def
       
   913         proof safe
       
   914           show "a \<le> d'" using \<open>a < y\<close> \<open>0 < d\<close> \<open>y < b\<close> by (simp add: d'_def)
       
   915           show "d' \<le> b" using \<open>y < b\<close> by (simp add: d'_def min_def)
       
   916           fix x1
       
   917           assume x1: "x1 \<in> {a..<d'}"
       
   918           {
       
   919             assume "x1 < y"
       
   920             hence "?le x1"
       
   921               using \<open>x1 \<in> {a..<d'}\<close> y_all_le by auto
       
   922           } moreover {
       
   923             assume "x1 \<ge> y"
       
   924             hence x1': "x1 \<in> S" "x1 \<in> {y..<b}" using x1
       
   925               by (auto simp: d'_def dist_real_def intro!: d)
       
   926             have "norm (f x1 - f a) \<le> norm (f x1 - f y) + norm (f y - f a)"
       
   927               by (rule order_trans[OF _ norm_triangle_ineq]) simp
       
   928             also note S(3)[OF x1']
       
   929             also note le_y
       
   930             finally have "?le x1"
       
   931               using \<open>x1 \<ge> y\<close> by (auto simp: algebra_simps)
       
   932           } ultimately show "?le x1" by arith
       
   933         qed
       
   934         hence "d' \<le> y"
       
   935           unfolding y_def
       
   936           by (rule cSup_upper) simp
       
   937         thus False using \<open>d > 0\<close> \<open>y < b\<close>
       
   938           by (simp add: d'_def min_def split: if_split_asm)
       
   939       qed
       
   940     } moreover {
       
   941       assume "a = y"
       
   942       with \<open>a < b\<close> have "y < b" by simp
   786       with \<open>a < b\<close> have "y < b" by simp
   943       with \<open>a = y\<close> f_cont phi_cont \<open>e2 > 0\<close>
   787       with \<open>a = y\<close> f_cont phi_cont \<open>e2 > 0\<close>
   944       have 1: "\<forall>\<^sub>F x in at y within {y..b}. dist (f x) (f y) < e2"
   788       have 1: "\<forall>\<^sub>F x in at y within {y..b}. dist (f x) (f y) < e2"
   945        and 2: "\<forall>\<^sub>F x in at y within {y..b}. dist (\<phi> x) (\<phi> y) < e2"
   789        and 2: "\<forall>\<^sub>F x in at y within {y..b}. dist (\<phi> x) (\<phi> y) < e2"
   946         by (auto simp: continuous_on_def tendsto_iff)
   790         by (auto simp: continuous_on_def tendsto_iff)
   964         also have "\<dots> = \<phi> x1 - \<phi> a + e * (x1 - a) + e"
   808         also have "\<dots> = \<phi> x1 - \<phi> a + e * (x1 - a) + e"
   965           by (simp add: e2_def)
   809           by (simp add: e2_def)
   966         finally show "?le x1" .
   810         finally show "?le x1" .
   967       qed
   811       qed
   968       from this[unfolded eventually_at_topological] \<open>?le y\<close>
   812       from this[unfolded eventually_at_topological] \<open>?le y\<close>
   969       obtain S
   813       obtain S where S: "open S" "y \<in> S" "\<And>x. x\<in>S \<Longrightarrow> x \<in> {y..b} \<Longrightarrow> ?le x"
   970       where S: "open S" "y \<in> S" "\<And>x. x\<in>S \<Longrightarrow> x \<in> {y..b} \<Longrightarrow> ?le x"
       
   971         by metis
   814         by metis
   972       from \<open>open S\<close> obtain d where d: "\<And>x. dist x y < d \<Longrightarrow> x \<in> S" "d > 0"
   815       from \<open>open S\<close> obtain d where d: "\<And>x. dist x y < d \<Longrightarrow> x \<in> S" "d > 0"
   973         by (force simp: dist_commute open_dist ball_def dest!: bspec[OF _ \<open>y \<in> S\<close>])
   816         by (force simp: dist_commute open_dist ball_def dest!: bspec[OF _ \<open>y \<in> S\<close>])
   974       define d' where "d' = min b (y + (d/2))"
   817       define d' where "d' = min b (y + (d/2))"
   975       have "d' \<in> A"
   818       have "d' \<in> A"
   985           by (rule S)
   828           by (rule S)
   986       qed
   829       qed
   987       hence "d' \<le> y"
   830       hence "d' \<le> y"
   988         unfolding y_def
   831         unfolding y_def
   989         by (rule cSup_upper) simp
   832         by (rule cSup_upper) simp
   990       hence "y = b" using \<open>d > 0\<close> \<open>y < b\<close>
   833       then show "y = b" using \<open>d > 0\<close> \<open>y < b\<close>
   991         by (simp add: d'_def)
   834         by (simp add: d'_def)
   992     } ultimately have "y = b"
   835     next
   993       by auto
   836       case False
       
   837       with \<open>a \<le> y\<close> have "a < y" by simp
       
   838       show "y = b"
       
   839       proof (rule ccontr)
       
   840         assume "y \<noteq> b"
       
   841         hence "y < b" using \<open>y \<le> b\<close> by simp
       
   842         let ?F = "at y within {y..<b}"
       
   843         from f' phi'
       
   844         have "(f has_vector_derivative f' y) ?F"
       
   845           and "(\<phi> has_vector_derivative \<phi>' y) ?F"
       
   846           using \<open>a < y\<close> \<open>y < b\<close>
       
   847           by (auto simp add: at_within_open[of _ "{a<..<b}"] has_vector_derivative_def
       
   848             intro!: has_derivative_subset[where s="{a<..<b}" and t="{y..<b}"])
       
   849         hence "\<forall>\<^sub>F x1 in ?F. norm (f x1 - f y - (x1 - y) *\<^sub>R f' y) \<le> e2 * \<bar>x1 - y\<bar>"
       
   850             "\<forall>\<^sub>F x1 in ?F. norm (\<phi> x1 - \<phi> y - (x1 - y) *\<^sub>R \<phi>' y) \<le> e2 * \<bar>x1 - y\<bar>"
       
   851           using \<open>e2 > 0\<close>
       
   852           by (auto simp: has_derivative_within_alt2 has_vector_derivative_def)
       
   853         moreover
       
   854         have "\<forall>\<^sub>F x1 in ?F. y \<le> x1" "\<forall>\<^sub>F x1 in ?F. x1 < b"
       
   855           by (auto simp: eventually_at_filter)
       
   856         ultimately
       
   857         have "\<forall>\<^sub>F x1 in ?F. norm (f x1 - f y) \<le> (\<phi> x1 - \<phi> y) + e * \<bar>x1 - y\<bar>"
       
   858           (is "\<forall>\<^sub>F x1 in ?F. ?le' x1")
       
   859         proof eventually_elim
       
   860           case (elim x1)
       
   861           from norm_triangle_ineq2[THEN order_trans, OF elim(1)]
       
   862           have "norm (f x1 - f y) \<le> norm (f' y) * \<bar>x1 - y\<bar> + e2 * \<bar>x1 - y\<bar>"
       
   863             by (simp add: ac_simps)
       
   864           also have "norm (f' y) \<le> \<phi>' y" using bnd \<open>a < y\<close> \<open>y < b\<close> by simp
       
   865           also have "\<phi>' y * \<bar>x1 - y\<bar> \<le> \<phi> x1 - \<phi> y + e2 * \<bar>x1 - y\<bar>"
       
   866             using elim by (simp add: ac_simps)
       
   867           finally
       
   868           have "norm (f x1 - f y) \<le> \<phi> x1 - \<phi> y + e2 * \<bar>x1 - y\<bar> + e2 * \<bar>x1 - y\<bar>"
       
   869             by (auto simp: mult_right_mono)
       
   870           thus ?case by (simp add: e2_def)
       
   871         qed
       
   872         moreover have "?le' y" by simp
       
   873         ultimately obtain S
       
   874         where S: "open S" "y \<in> S" "\<And>x. x\<in>S \<Longrightarrow> x \<in> {y..<b} \<Longrightarrow> ?le' x"
       
   875           unfolding eventually_at_topological
       
   876           by metis
       
   877         from \<open>open S\<close> obtain d where d: "\<And>x. dist x y < d \<Longrightarrow> x \<in> S" "d > 0"
       
   878           by (force simp: dist_commute open_dist ball_def dest!: bspec[OF _ \<open>y \<in> S\<close>])
       
   879         define d' where "d' = min ((y + b)/2) (y + (d/2))"
       
   880         have "d' \<in> A"
       
   881           unfolding A_def
       
   882         proof safe
       
   883           show "a \<le> d'" using \<open>a < y\<close> \<open>0 < d\<close> \<open>y < b\<close> by (simp add: d'_def)
       
   884           show "d' \<le> b" using \<open>y < b\<close> by (simp add: d'_def min_def)
       
   885           fix x1
       
   886           assume x1: "x1 \<in> {a..<d'}"
       
   887           show "?le x1"
       
   888           proof (cases "x1 < y")
       
   889             case True
       
   890             then show ?thesis
       
   891               using \<open>y \<in> A\<close> local.leI x1 by auto
       
   892           next
       
   893             case False
       
   894             hence x1': "x1 \<in> S" "x1 \<in> {y..<b}" using x1
       
   895               by (auto simp: d'_def dist_real_def intro!: d)
       
   896             have "norm (f x1 - f a) \<le> norm (f x1 - f y) + norm (f y - f a)"
       
   897               by (rule order_trans[OF _ norm_triangle_ineq]) simp
       
   898             also note S(3)[OF x1']
       
   899             also note le_y
       
   900             finally show "?le x1"
       
   901               using False by (auto simp: algebra_simps)
       
   902           qed
       
   903         qed
       
   904         hence "d' \<le> y"
       
   905           unfolding y_def by (rule cSup_upper) simp
       
   906         thus False using \<open>d > 0\<close> \<open>y < b\<close>
       
   907           by (simp add: d'_def min_def split: if_split_asm)
       
   908       qed
       
   909     qed
   994     with le_y have "norm (f b - f a) \<le> \<phi> b - \<phi> a + e * (b - a + 1)"
   910     with le_y have "norm (f b - f a) \<le> \<phi> b - \<phi> a + e * (b - a + 1)"
   995       by (simp add: algebra_simps)
   911       by (simp add: algebra_simps)
   996   } note * = this
   912   } note * = this
   997   {
   913   show ?thesis
       
   914   proof (rule field_le_epsilon)
   998     fix e::real assume "e > 0"
   915     fix e::real assume "e > 0"
   999     hence "norm (f b - f a) \<le> \<phi> b - \<phi> a + e"
   916     then show "norm (f b - f a) \<le> \<phi> b - \<phi> a + e"
  1000       using *[of "e / (b - a + 1)"] \<open>a < b\<close> by simp
   917       using *[of "e / (b - a + 1)"] \<open>a < b\<close> by simp
  1001   } thus ?thesis
   918   qed
  1002     by (rule field_le_epsilon)
       
  1003 qed
   919 qed
  1004 
   920 
  1005 lemma differentiable_bound:
   921 lemma differentiable_bound:
  1006   fixes f :: "'a::real_normed_vector \<Rightarrow> 'b::real_normed_vector"
   922   fixes f :: "'a::real_normed_vector \<Rightarrow> 'b::real_normed_vector"
  1007   assumes "convex s"
   923   assumes "convex S"
  1008     and "\<forall>x\<in>s. (f has_derivative f' x) (at x within s)"
   924     and derf: "\<And>x. x\<in>S \<Longrightarrow> (f has_derivative f' x) (at x within S)"
  1009     and "\<forall>x\<in>s. onorm (f' x) \<le> B"
   925     and B: "\<And>x. x \<in> S \<Longrightarrow> onorm (f' x) \<le> B"
  1010     and x: "x \<in> s"
   926     and x: "x \<in> S"
  1011     and y: "y \<in> s"
   927     and y: "y \<in> S"
  1012   shows "norm (f x - f y) \<le> B * norm (x - y)"
   928   shows "norm (f x - f y) \<le> B * norm (x - y)"
  1013 proof -
   929 proof -
  1014   let ?p = "\<lambda>u. x + u *\<^sub>R (y - x)"
   930   let ?p = "\<lambda>u. x + u *\<^sub>R (y - x)"
  1015   let ?\<phi> = "\<lambda>h. h * B * norm (x - y)"
   931   let ?\<phi> = "\<lambda>h. h * B * norm (x - y)"
  1016   have *: "\<And>u. u\<in>{0..1} \<Longrightarrow> x + u *\<^sub>R (y - x) \<in> s"
   932   have *: "x + u *\<^sub>R (y - x) \<in> S" if "u \<in> {0..1}" for u
  1017     using assms(1)[unfolded convex_alt,rule_format,OF x y]
   933   proof -
  1018     unfolding scaleR_left_diff_distrib scaleR_right_diff_distrib
   934     have "u *\<^sub>R y = u *\<^sub>R (y - x) + u *\<^sub>R x"
  1019     by (auto simp add: algebra_simps)
   935       by (simp add: scale_right_diff_distrib)
  1020   have 0: "continuous_on (?p ` {0..1}) f"
   936     then show "x + u *\<^sub>R (y - x) \<in> S"
  1021     using *
   937       using that \<open>convex S\<close> unfolding convex_alt by (metis (no_types) atLeastAtMost_iff linordered_field_class.sign_simps(2) pth_c(3) scaleR_collapse x y)
       
   938   qed
       
   939   have "\<And>z. z \<in> (\<lambda>u. x + u *\<^sub>R (y - x)) ` {0..1} \<Longrightarrow>
       
   940           (f has_derivative f' z) (at z within (\<lambda>u. x + u *\<^sub>R (y - x)) ` {0..1})"
       
   941     by (auto intro: * has_derivative_within_subset [OF derf])
       
   942   then have "continuous_on (?p ` {0..1}) f"
  1022     unfolding continuous_on_eq_continuous_within
   943     unfolding continuous_on_eq_continuous_within
  1023     apply -
   944     by (meson has_derivative_continuous)
  1024     apply rule
   945   with * have 1: "continuous_on {0 .. 1} (f \<circ> ?p)"
  1025     apply (rule differentiable_imp_continuous_within)
   946     by (intro continuous_intros)+
  1026     unfolding differentiable_def
       
  1027     apply (rule_tac x="f' xa" in exI)
       
  1028     apply (rule has_derivative_within_subset)
       
  1029     apply (rule assms(2)[rule_format])
       
  1030     apply auto
       
  1031     done
       
  1032   from * have 1: "continuous_on {0 .. 1} (f \<circ> ?p)"
       
  1033     by (intro continuous_intros 0)+
       
  1034   {
   947   {
  1035     fix u::real assume u: "u \<in>{0 <..< 1}"
   948     fix u::real assume u: "u \<in>{0 <..< 1}"
  1036     let ?u = "?p u"
   949     let ?u = "?p u"
  1037     interpret linear "(f' ?u)"
   950     interpret linear "(f' ?u)"
  1038       using u by (auto intro!: has_derivative_linear assms(2)[rule_format] *)
   951       using u by (auto intro!: has_derivative_linear derf *)
  1039     have "(f \<circ> ?p has_derivative (f' ?u) \<circ> (\<lambda>u. 0 + u *\<^sub>R (y - x))) (at u within box 0 1)"
   952     have "(f \<circ> ?p has_derivative (f' ?u) \<circ> (\<lambda>u. 0 + u *\<^sub>R (y - x))) (at u within box 0 1)"
  1040       apply (rule diff_chain_within)
   953       by (intro derivative_intros has_derivative_within_subset [OF derf]) (use u * in auto)
  1041       apply (rule derivative_intros)+
       
  1042       apply (rule has_derivative_within_subset)
       
  1043       apply (rule assms(2)[rule_format])
       
  1044       using u *
       
  1045       apply auto
       
  1046       done
       
  1047     hence "((f \<circ> ?p) has_vector_derivative f' ?u (y - x)) (at u)"
   954     hence "((f \<circ> ?p) has_vector_derivative f' ?u (y - x)) (at u)"
  1048       by (simp add: has_derivative_within_open[OF u open_greaterThanLessThan]
   955       by (simp add: has_derivative_within_open[OF u open_greaterThanLessThan]
  1049         scaleR has_vector_derivative_def o_def)
   956         scaleR has_vector_derivative_def o_def)
  1050   } note 2 = this
   957   } note 2 = this
  1051   {
   958   have 3: "continuous_on {0..1} ?\<phi>"
  1052     have "continuous_on {0..1} ?\<phi>"
   959     by (rule continuous_intros)+
  1053       by (rule continuous_intros)+
   960   have 4: "(?\<phi> has_vector_derivative B * norm (x - y)) (at u)" for u
  1054   } note 3 = this
   961     by (auto simp: has_vector_derivative_def intro!: derivative_eq_intros)
  1055   {
       
  1056     fix u::real assume u: "u \<in>{0 <..< 1}"
       
  1057     have "(?\<phi> has_vector_derivative B * norm (x - y)) (at u)"
       
  1058       by (auto simp: has_vector_derivative_def intro!: derivative_eq_intros)
       
  1059   } note 4 = this
       
  1060   {
   962   {
  1061     fix u::real assume u: "u \<in>{0 <..< 1}"
   963     fix u::real assume u: "u \<in>{0 <..< 1}"
  1062     let ?u = "?p u"
   964     let ?u = "?p u"
  1063     interpret bounded_linear "(f' ?u)"
   965     interpret bounded_linear "(f' ?u)"
  1064       using u by (auto intro!: has_derivative_bounded_linear assms(2)[rule_format] *)
   966       using u by (auto intro!: has_derivative_bounded_linear derf *)
  1065     have "norm (f' ?u (y - x)) \<le> onorm (f' ?u) * norm (y - x)"
   967     have "norm (f' ?u (y - x)) \<le> onorm (f' ?u) * norm (y - x)"
  1066       by (rule onorm) (rule bounded_linear)
   968       by (rule onorm) (rule bounded_linear)
  1067     also have "onorm (f' ?u) \<le> B"
   969     also have "onorm (f' ?u) \<le> B"
  1068       using u by (auto intro!: assms(3)[rule_format] *)
   970       using u by (auto intro!: assms(3)[rule_format] *)
  1069     finally have "norm ((f' ?u) (y - x)) \<le> B * norm (x - y)"
   971     finally have "norm ((f' ?u) (y - x)) \<le> B * norm (x - y)"
  1081 lemma
   983 lemma
  1082   differentiable_bound_segment:
   984   differentiable_bound_segment:
  1083   fixes f::"'a::real_normed_vector \<Rightarrow> 'b::real_normed_vector"
   985   fixes f::"'a::real_normed_vector \<Rightarrow> 'b::real_normed_vector"
  1084   assumes "\<And>t. t \<in> {0..1} \<Longrightarrow> x0 + t *\<^sub>R a \<in> G"
   986   assumes "\<And>t. t \<in> {0..1} \<Longrightarrow> x0 + t *\<^sub>R a \<in> G"
  1085   assumes f': "\<And>x. x \<in> G \<Longrightarrow> (f has_derivative f' x) (at x within G)"
   987   assumes f': "\<And>x. x \<in> G \<Longrightarrow> (f has_derivative f' x) (at x within G)"
  1086   assumes B: "\<forall>x\<in>{0..1}. onorm (f' (x0 + x *\<^sub>R a)) \<le> B"
   988   assumes B: "\<And>x. x \<in> {0..1} \<Longrightarrow> onorm (f' (x0 + x *\<^sub>R a)) \<le> B"
  1087   shows "norm (f (x0 + a) - f x0) \<le> norm a * B"
   989   shows "norm (f (x0 + a) - f x0) \<le> norm a * B"
  1088 proof -
   990 proof -
  1089   let ?G = "(\<lambda>x. x0 + x *\<^sub>R a) ` {0..1}"
   991   let ?G = "(\<lambda>x. x0 + x *\<^sub>R a) ` {0..1}"
  1090   have "?G = (+) x0 ` (\<lambda>x. x *\<^sub>R a) ` {0..1}" by auto
   992   have "?G = (+) x0 ` (\<lambda>x. x *\<^sub>R a) ` {0..1}" by auto
  1091   also have "convex \<dots>"
   993   also have "convex \<dots>"
  1093   finally have "convex ?G" .
   995   finally have "convex ?G" .
  1094   moreover have "?G \<subseteq> G" "x0 \<in> ?G" "x0 + a \<in> ?G" using assms by (auto intro: image_eqI[where x=1])
   996   moreover have "?G \<subseteq> G" "x0 \<in> ?G" "x0 + a \<in> ?G" using assms by (auto intro: image_eqI[where x=1])
  1095   ultimately show ?thesis
   997   ultimately show ?thesis
  1096     using has_derivative_subset[OF f' \<open>?G \<subseteq> G\<close>] B
   998     using has_derivative_subset[OF f' \<open>?G \<subseteq> G\<close>] B
  1097       differentiable_bound[of "(\<lambda>x. x0 + x *\<^sub>R a) ` {0..1}" f f' B "x0 + a" x0]
   999       differentiable_bound[of "(\<lambda>x. x0 + x *\<^sub>R a) ` {0..1}" f f' B "x0 + a" x0]
  1098     by (auto simp: ac_simps)
  1000     by (force simp: ac_simps)
  1099 qed
  1001 qed
  1100 
  1002 
  1101 lemma differentiable_bound_linearization:
  1003 lemma differentiable_bound_linearization:
  1102   fixes f::"'a::real_normed_vector \<Rightarrow> 'b::real_normed_vector"
  1004   fixes f::"'a::real_normed_vector \<Rightarrow> 'b::real_normed_vector"
  1103   assumes "\<And>t. t \<in> {0..1} \<Longrightarrow> a + t *\<^sub>R (b - a) \<in> S"
  1005   assumes S: "\<And>t. t \<in> {0..1} \<Longrightarrow> a + t *\<^sub>R (b - a) \<in> S"
  1104   assumes f'[derivative_intros]: "\<And>x. x \<in> S \<Longrightarrow> (f has_derivative f' x) (at x within S)"
  1006   assumes f'[derivative_intros]: "\<And>x. x \<in> S \<Longrightarrow> (f has_derivative f' x) (at x within S)"
  1105   assumes B: "\<forall>x\<in>S. onorm (f' x - f' x0) \<le> B"
  1007   assumes B: "\<And>x. x \<in> S \<Longrightarrow> onorm (f' x - f' x0) \<le> B"
  1106   assumes "x0 \<in> S"
  1008   assumes "x0 \<in> S"
  1107   shows "norm (f b - f a - f' x0 (b - a)) \<le> norm (b - a) * B"
  1009   shows "norm (f b - f a - f' x0 (b - a)) \<le> norm (b - a) * B"
  1108 proof -
  1010 proof -
  1109   define g where [abs_def]: "g x = f x - f' x0 x" for x
  1011   define g where [abs_def]: "g x = f x - f' x0 x" for x
  1110   have g: "\<And>x. x \<in> S \<Longrightarrow> (g has_derivative (\<lambda>i. f' x i - f' x0 i)) (at x within S)"
  1012   have g: "\<And>x. x \<in> S \<Longrightarrow> (g has_derivative (\<lambda>i. f' x i - f' x0 i)) (at x within S)"
  1111     unfolding g_def using assms
  1013     unfolding g_def using assms
  1112     by (auto intro!: derivative_eq_intros
  1014     by (auto intro!: derivative_eq_intros
  1113       bounded_linear.has_derivative[OF has_derivative_bounded_linear, OF f'])
  1015       bounded_linear.has_derivative[OF has_derivative_bounded_linear, OF f'])
  1114   from B have B: "\<forall>x\<in>{0..1}. onorm (\<lambda>i. f' (a + x *\<^sub>R (b - a)) i - f' x0 i) \<le> B"
  1016   from B have "\<forall>x\<in>{0..1}. onorm (\<lambda>i. f' (a + x *\<^sub>R (b - a)) i - f' x0 i) \<le> B"
  1115      using assms by (auto simp: fun_diff_def)
  1017     using assms by (auto simp: fun_diff_def)
  1116   from differentiable_bound_segment[OF assms(1) g B] \<open>x0 \<in> S\<close>
  1018   with differentiable_bound_segment[OF S g] \<open>x0 \<in> S\<close>
  1117   show ?thesis
  1019   show ?thesis
  1118     by (simp add: g_def field_simps linear_diff[OF has_derivative_linear[OF f']])
  1020     by (simp add: g_def field_simps linear_diff[OF has_derivative_linear[OF f']])
  1119 qed
  1021 qed
  1120 
  1022 
  1121 lemma vector_differentiable_bound_linearization:
  1023 lemma vector_differentiable_bound_linearization:
  1122   fixes f::"real \<Rightarrow> 'b::real_normed_vector"
  1024   fixes f::"real \<Rightarrow> 'b::real_normed_vector"
  1123   assumes f': "\<And>x. x \<in> S \<Longrightarrow> (f has_vector_derivative f' x) (at x within S)"
  1025   assumes f': "\<And>x. x \<in> S \<Longrightarrow> (f has_vector_derivative f' x) (at x within S)"
  1124   assumes "closed_segment a b \<subseteq> S"
  1026   assumes "closed_segment a b \<subseteq> S"
  1125   assumes B: "\<forall>x\<in>S. norm (f' x - f' x0) \<le> B"
  1027   assumes B: "\<And>x. x \<in> S \<Longrightarrow> norm (f' x - f' x0) \<le> B"
  1126   assumes "x0 \<in> S"
  1028   assumes "x0 \<in> S"
  1127   shows "norm (f b - f a - (b - a) *\<^sub>R f' x0) \<le> norm (b - a) * B"
  1029   shows "norm (f b - f a - (b - a) *\<^sub>R f' x0) \<le> norm (b - a) * B"
  1128   using assms
  1030   using assms
  1129   by (intro differentiable_bound_linearization[of a b S f "\<lambda>x h. h *\<^sub>R f' x" x0 B])
  1031   by (intro differentiable_bound_linearization[of a b S f "\<lambda>x h. h *\<^sub>R f' x" x0 B])
  1130     (force simp: closed_segment_real_eq has_vector_derivative_def
  1032     (force simp: closed_segment_real_eq has_vector_derivative_def
  1344   fixes f :: "'a::real_normed_vector \<Rightarrow> 'b::real_normed_vector"
  1246   fixes f :: "'a::real_normed_vector \<Rightarrow> 'b::real_normed_vector"
  1345   assumes "compact S"
  1247   assumes "compact S"
  1346     and "x \<in> S"
  1248     and "x \<in> S"
  1347     and fx: "f x \<in> interior (f ` S)"
  1249     and fx: "f x \<in> interior (f ` S)"
  1348     and "continuous_on S f"
  1250     and "continuous_on S f"
  1349     and "\<And>y. y \<in> S \<Longrightarrow> g (f y) = y"
  1251     and gf: "\<And>y. y \<in> S \<Longrightarrow> g (f y) = y"
  1350     and "(f has_derivative f') (at x)"
  1252     and "(f has_derivative f') (at x)"
  1351     and "bounded_linear g'"
  1253     and "bounded_linear g'"
  1352     and "g' \<circ> f' = id"
  1254     and "g' \<circ> f' = id"
  1353   shows "(g has_derivative g') (at (f x))"
  1255   shows "(g has_derivative g') (at (f x))"
  1354 proof -
  1256 proof -
  1355   {
  1257   have *: "\<And>y. y \<in> interior (f ` S) \<Longrightarrow> f (g y) = y"
  1356     fix y
  1258     by (metis gf image_iff interior_subset subsetCE)
  1357     assume "y \<in> interior (f ` S)"
       
  1358     then obtain x where "x \<in> S" and *: "y = f x"
       
  1359       by (meson imageE interior_subset subsetCE)
       
  1360     have "f (g y) = y"
       
  1361       unfolding * and assms(5)[rule_format,OF \<open>x\<in>S\<close>] ..
       
  1362   } note * = this
       
  1363   show ?thesis
  1259   show ?thesis
  1364     apply (rule has_derivative_inverse_basic_x[OF assms(6-8), where T = "interior (f ` S)"])
  1260     apply (rule has_derivative_inverse_basic_x[OF assms(6-8), where T = "interior (f ` S)"])
  1365     apply (rule continuous_on_interior[OF _ fx])
  1261     apply (rule continuous_on_interior[OF _ fx])
  1366     apply (rule continuous_on_inv)
  1262     apply (rule continuous_on_inv)
  1367     apply (simp_all add: assms *)
  1263     apply (simp_all add: assms *)
  1384   have *: "\<And>x y. f y = x \<longleftrightarrow> x + (y - f y) = y"
  1280   have *: "\<And>x y. f y = x \<longleftrightarrow> x + (y - f y) = y"
  1385     by (auto simp add: algebra_simps)
  1281     by (auto simp add: algebra_simps)
  1386   show ?thesis
  1282   show ?thesis
  1387     unfolding *
  1283     unfolding *
  1388     apply (rule brouwer[OF assms(1-3), of "\<lambda>y. x + (y - f y)"])
  1284     apply (rule brouwer[OF assms(1-3), of "\<lambda>y. x + (y - f y)"])
  1389     apply (rule continuous_intros assms)+
  1285     apply (intro continuous_intros)
  1390     using assms(4-6)
  1286     using assms
  1391     apply auto
  1287     apply auto
  1392     done
  1288     done
  1393 qed
  1289 qed
  1394 
  1290 
  1395 lemma brouwer_surjective_cball:
  1291 lemma brouwer_surjective_cball:
  1409 text \<open>See Sussmann: "Multidifferential calculus", Theorem 2.1.1\<close>
  1305 text \<open>See Sussmann: "Multidifferential calculus", Theorem 2.1.1\<close>
  1410 
  1306 
  1411 lemma sussmann_open_mapping:
  1307 lemma sussmann_open_mapping:
  1412   fixes f :: "'a::real_normed_vector \<Rightarrow> 'b::euclidean_space"
  1308   fixes f :: "'a::real_normed_vector \<Rightarrow> 'b::euclidean_space"
  1413   assumes "open S"
  1309   assumes "open S"
  1414     and "continuous_on S f"
  1310     and contf: "continuous_on S f"
  1415     and "x \<in> S"
  1311     and "x \<in> S"
  1416     and "(f has_derivative f') (at x)"
  1312     and derf: "(f has_derivative f') (at x)"
  1417     and "bounded_linear g'" "f' \<circ> g' = id"
  1313     and "bounded_linear g'" "f' \<circ> g' = id"
  1418     and "T \<subseteq> S"
  1314     and "T \<subseteq> S"
  1419     and "x \<in> interior T"
  1315     and x: "x \<in> interior T"
  1420   shows "f x \<in> interior (f ` T)"
  1316   shows "f x \<in> interior (f ` T)"
  1421 proof -
  1317 proof -
  1422   interpret f': bounded_linear f'
  1318   interpret f': bounded_linear f'
  1423     using assms
  1319     using assms unfolding has_derivative_def by auto
  1424     unfolding has_derivative_def
       
  1425     by auto
       
  1426   interpret g': bounded_linear g'
  1320   interpret g': bounded_linear g'
  1427     using assms
  1321     using assms by auto
  1428     by auto
       
  1429   obtain B where B: "0 < B" "\<forall>x. norm (g' x) \<le> norm x * B"
  1322   obtain B where B: "0 < B" "\<forall>x. norm (g' x) \<le> norm x * B"
  1430     using bounded_linear.pos_bounded[OF assms(5)] by blast
  1323     using bounded_linear.pos_bounded[OF assms(5)] by blast
  1431   hence *: "1 / (2 * B) > 0" by auto
  1324   hence *: "1 / (2 * B) > 0" by auto
  1432   obtain e0 where e0:
  1325   obtain e0 where e0:
  1433       "0 < e0"
  1326       "0 < e0"
  1434       "\<forall>y. norm (y - x) < e0 \<longrightarrow> norm (f y - f x - f' (y - x)) \<le> 1 / (2 * B) * norm (y - x)"
  1327       "\<forall>y. norm (y - x) < e0 \<longrightarrow> norm (f y - f x - f' (y - x)) \<le> 1 / (2 * B) * norm (y - x)"
  1435     using assms(4)
  1328     using derf unfolding has_derivative_at_alt
  1436     unfolding has_derivative_at_alt
       
  1437     using * by blast
  1329     using * by blast
  1438   obtain e1 where e1: "0 < e1" "cball x e1 \<subseteq> T"
  1330   obtain e1 where e1: "0 < e1" "cball x e1 \<subseteq> T"
  1439     using assms(8)
  1331     using mem_interior_cball x by blast
  1440     unfolding mem_interior_cball
       
  1441     by blast
       
  1442   have *: "0 < e0 / B" "0 < e1 / B" using e0 e1 B by auto
  1332   have *: "0 < e0 / B" "0 < e1 / B" using e0 e1 B by auto
  1443   obtain e where e: "0 < e" "e < e0 / B" "e < e1 / B"
  1333   obtain e where e: "0 < e" "e < e0 / B" "e < e1 / B"
  1444     using real_lbound_gt_zero[OF *] by blast
  1334     using real_lbound_gt_zero[OF *] by blast
  1445   have lem: "\<exists>y\<in>cball (f x) e. f (x + g' (y - f x)) = z" if "z\<in>cball (f x) (e / 2)" for z
  1335   have lem: "\<exists>y\<in>cball (f x) e. f (x + g' (y - f x)) = z" if "z\<in>cball (f x) (e / 2)" for z
  1446   proof (rule brouwer_surjective_cball)
  1336   proof (rule brouwer_surjective_cball)
  1447     have z: "z \<in> S" if as: "y \<in>cball (f x) e" "z = x + (g' y - g' (f x))" for y z
  1337     have z: "z \<in> S" if as: "y \<in>cball (f x) e" "z = x + (g' y - g' (f x))" for y z
  1448     proof-
  1338     proof-
  1449       have "dist x z = norm (g' (f x) - g' y)"
  1339       have "dist x z = norm (g' (f x) - g' y)"
  1450         unfolding as(2) and dist_norm by auto
  1340         unfolding as(2) and dist_norm by auto
  1451       also have "\<dots> \<le> norm (f x - y) * B"
  1341       also have "\<dots> \<le> norm (f x - y) * B"
  1452         unfolding g'.diff[symmetric]
  1342         by (metis B(2) g'.diff)
  1453         using B
       
  1454         by auto
       
  1455       also have "\<dots> \<le> e * B"
  1343       also have "\<dots> \<le> e * B"
  1456         using as(1)[unfolded mem_cball dist_norm]
  1344         by (metis B(1) dist_norm mem_cball real_mult_le_cancel_iff1 that(1))
  1457         using B
       
  1458         by auto
       
  1459       also have "\<dots> \<le> e1"
  1345       also have "\<dots> \<le> e1"
  1460         using e
  1346         using B(1) e(3) pos_less_divide_eq by fastforce
  1461         unfolding less_divide_eq
       
  1462         using B
       
  1463         by auto
       
  1464       finally have "z \<in> cball x e1"
  1347       finally have "z \<in> cball x e1"
  1465         unfolding mem_cball
       
  1466         by force
  1348         by force
  1467       then show "z \<in> S"
  1349       then show "z \<in> S"
  1468         using e1 assms(7) by auto
  1350         using e1 assms(7) by auto
  1469     qed
  1351     qed
  1470     show "continuous_on (cball (f x) e) (\<lambda>y. f (x + g' (y - f x)))"
  1352     show "continuous_on (cball (f x) e) (\<lambda>y. f (x + g' (y - f x)))"
  1471       unfolding g'.diff
  1353       unfolding g'.diff
  1472       apply (rule continuous_on_compose[of _ _ f, unfolded o_def])
  1354     proof (rule continuous_on_compose2 [OF _ _ order_refl, of _ _ f])
  1473        apply (rule continuous_intros linear_continuous_on[OF assms(5)])+
  1355       show "continuous_on ((\<lambda>y. x + (g' y - g' (f x))) ` cball (f x) e) f"
  1474       apply (rule continuous_on_subset[OF assms(2)])
  1356         by (rule continuous_on_subset[OF contf]) (use z in blast)
  1475       using z
  1357       show "continuous_on (cball (f x) e) (\<lambda>y. x + (g' y - g' (f x)))"
  1476       by blast
  1358         by (intro continuous_intros linear_continuous_on[OF \<open>bounded_linear g'\<close>])
       
  1359     qed
  1477   next
  1360   next
  1478     fix y z
  1361     fix y z
  1479     assume as: "y \<in> cball (f x) (e / 2)" "z \<in> cball (f x) e"
  1362     assume y: "y \<in> cball (f x) (e / 2)" and z: "z \<in> cball (f x) e"
  1480     have "norm (g' (z - f x)) \<le> norm (z - f x) * B"
  1363     have "norm (g' (z - f x)) \<le> norm (z - f x) * B"
  1481       using B by auto
  1364       using B by auto
  1482     also have "\<dots> \<le> e * B"
  1365     also have "\<dots> \<le> e * B"
  1483       apply (rule mult_right_mono)
  1366       by (metis B(1) z dist_norm mem_cball norm_minus_commute real_mult_le_cancel_iff1)
  1484       using as(2)[unfolded mem_cball dist_norm] and B
       
  1485       unfolding norm_minus_commute
       
  1486        apply auto
       
  1487       done
       
  1488     also have "\<dots> < e0"
  1367     also have "\<dots> < e0"
  1489       using e and B
  1368       using B(1) e(2) pos_less_divide_eq by blast
  1490       unfolding less_divide_eq
       
  1491       by auto
       
  1492     finally have *: "norm (x + g' (z - f x) - x) < e0"
  1369     finally have *: "norm (x + g' (z - f x) - x) < e0"
  1493       by auto
  1370       by auto
  1494     have **: "f x + f' (x + g' (z - f x) - x) = z"
  1371     have **: "f x + f' (x + g' (z - f x) - x) = z"
  1495       using assms(6)[unfolded o_def id_def,THEN cong]
  1372       using assms(6)[unfolded o_def id_def,THEN cong]
  1496       by auto
  1373       by auto
  1497     have "norm (f x - (y + (z - f (x + g' (z - f x))))) \<le>
  1374     have "norm (f x - (y + (z - f (x + g' (z - f x))))) \<le>
  1498         norm (f (x + g' (z - f x)) - z) + norm (f x - y)"
  1375           norm (f (x + g' (z - f x)) - z) + norm (f x - y)"
  1499       using norm_triangle_ineq[of "f (x + g'(z - f x)) - z" "f x - y"]
  1376       using norm_triangle_ineq[of "f (x + g'(z - f x)) - z" "f x - y"]
  1500       by (auto simp add: algebra_simps)
  1377       by (auto simp add: algebra_simps)
  1501     also have "\<dots> \<le> 1 / (B * 2) * norm (g' (z - f x)) + norm (f x - y)"
  1378     also have "\<dots> \<le> 1 / (B * 2) * norm (g' (z - f x)) + norm (f x - y)"
  1502       using e0(2)[rule_format, OF *]
  1379       using e0(2)[rule_format, OF *]
  1503       by (simp only: algebra_simps **) auto
  1380       by (simp only: algebra_simps **) auto
  1504     also have "\<dots> \<le> 1 / (B * 2) * norm (g' (z - f x)) + e/2"
  1381     also have "\<dots> \<le> 1 / (B * 2) * norm (g' (z - f x)) + e/2"
  1505       using as(1)[unfolded mem_cball dist_norm]
  1382       using y by (auto simp: dist_norm)
  1506       by auto
       
  1507     also have "\<dots> \<le> 1 / (B * 2) * B * norm (z - f x) + e/2"
  1383     also have "\<dots> \<le> 1 / (B * 2) * B * norm (z - f x) + e/2"
  1508       using * and B
  1384       using * B by (auto simp add: field_simps)
  1509       by (auto simp add: field_simps)
       
  1510     also have "\<dots> \<le> 1 / 2 * norm (z - f x) + e/2"
  1385     also have "\<dots> \<le> 1 / 2 * norm (z - f x) + e/2"
  1511       by auto
  1386       by auto
  1512     also have "\<dots> \<le> e/2 + e/2"
  1387     also have "\<dots> \<le> e/2 + e/2"
  1513       apply (rule add_right_mono)
  1388       using B(1) \<open>norm (z - f x) * B \<le> e * B\<close> by auto
  1514       using as(2)[unfolded mem_cball dist_norm]
       
  1515       unfolding norm_minus_commute
       
  1516       apply auto
       
  1517       done
       
  1518     finally show "y + (z - f (x + g' (z - f x))) \<in> cball (f x) e"
  1389     finally show "y + (z - f (x + g' (z - f x))) \<in> cball (f x) e"
  1519       unfolding mem_cball dist_norm
  1390       by (auto simp: dist_norm)
  1520       by auto
       
  1521   qed (use e that in auto) 
  1391   qed (use e that in auto) 
  1522   show ?thesis
  1392   show ?thesis
  1523     unfolding mem_interior
  1393     unfolding mem_interior
  1524     apply (rule_tac x="e/2" in exI)
  1394   proof (intro exI conjI subsetI)
  1525     apply rule
       
  1526     apply (rule divide_pos_pos)
       
  1527     prefer 3
       
  1528   proof
       
  1529     fix y
  1395     fix y
  1530     assume "y \<in> ball (f x) (e / 2)"
  1396     assume "y \<in> ball (f x) (e / 2)"
  1531     then have *: "y \<in> cball (f x) (e / 2)"
  1397     then have *: "y \<in> cball (f x) (e / 2)"
  1532       by auto
  1398       by auto
  1533     obtain z where z: "z \<in> cball (f x) e" "f (x + g' (z - f x)) = y"
  1399     obtain z where z: "z \<in> cball (f x) e" "f (x + g' (z - f x)) = y"
  1534       using lem * by blast
  1400       using lem * by blast
  1535     then have "norm (g' (z - f x)) \<le> norm (z - f x) * B"
  1401     then have "norm (g' (z - f x)) \<le> norm (z - f x) * B"
  1536       using B
  1402       using B
  1537       by (auto simp add: field_simps)
  1403       by (auto simp add: field_simps)
  1538     also have "\<dots> \<le> e * B"
  1404     also have "\<dots> \<le> e * B"
  1539       apply (rule mult_right_mono)
  1405       by (metis B(1) dist_norm mem_cball norm_minus_commute real_mult_le_cancel_iff1 z(1))
  1540       using z(1)
       
  1541       unfolding mem_cball dist_norm norm_minus_commute
       
  1542       using B
       
  1543       apply auto
       
  1544       done
       
  1545     also have "\<dots> \<le> e1"
  1406     also have "\<dots> \<le> e1"
  1546       using e B unfolding less_divide_eq by auto
  1407       using e B unfolding less_divide_eq by auto
  1547     finally have "x + g'(z - f x) \<in> T"
  1408     finally have "x + g'(z - f x) \<in> T"
  1548       apply -
  1409       by (metis add_diff_cancel diff_diff_add dist_norm e1(2) mem_cball norm_minus_commute subset_eq)
  1549       apply (rule e1(2)[unfolded subset_eq,rule_format])
       
  1550       unfolding mem_cball dist_norm
       
  1551       apply auto
       
  1552       done
       
  1553     then show "y \<in> f ` T"
  1410     then show "y \<in> f ` T"
  1554       using z by auto
  1411       using z by auto
  1555   qed (insert e, auto)
  1412   qed (use e in auto)
  1556 qed
  1413 qed
  1557 
  1414 
  1558 text \<open>Hence the following eccentric variant of the inverse function theorem.
  1415 text \<open>Hence the following eccentric variant of the inverse function theorem.
  1559   This has no continuity assumptions, but we do need the inverse function.
  1416   This has no continuity assumptions, but we do need the inverse function.
  1560   We could put \<open>f' \<circ> g = I\<close> but this happens to fit with the minimal linear
  1417   We could put \<open>f' \<circ> g = I\<close> but this happens to fit with the minimal linear
  1561   algebra theory I've set up so far.\<close>
  1418   algebra theory I've set up so far.\<close>
  1562 
  1419 
  1563 lemma has_derivative_inverse_strong:
  1420 lemma has_derivative_inverse_strong:
  1564   fixes f :: "'n::euclidean_space \<Rightarrow> 'n"
  1421   fixes f :: "'n::euclidean_space \<Rightarrow> 'n"
  1565   assumes "open s"
  1422   assumes "open S"
  1566     and "x \<in> s"
  1423     and "x \<in> S"
  1567     and "continuous_on s f"
  1424     and contf: "continuous_on S f"
  1568     and "\<forall>x\<in>s. g (f x) = x"
  1425     and gf: "\<And>x. x \<in> S \<Longrightarrow> g (f x) = x"
  1569     and "(f has_derivative f') (at x)"
  1426     and derf: "(f has_derivative f') (at x)"
  1570     and "f' \<circ> g' = id"
  1427     and id: "f' \<circ> g' = id"
  1571   shows "(g has_derivative g') (at (f x))"
  1428   shows "(g has_derivative g') (at (f x))"
  1572 proof -
  1429 proof -
  1573   have linf: "bounded_linear f'"
  1430   have linf: "bounded_linear f'"
  1574     using assms(5) unfolding has_derivative_def by auto
  1431     using derf unfolding has_derivative_def by auto
  1575   then have ling: "bounded_linear g'"
  1432   then have ling: "bounded_linear g'"
  1576     unfolding linear_conv_bounded_linear[symmetric]
  1433     unfolding linear_conv_bounded_linear[symmetric]
  1577     apply -
  1434     using id right_inverse_linear by blast
  1578     apply (rule right_inverse_linear)
       
  1579     using assms(6)
       
  1580     apply auto
       
  1581     done
       
  1582   moreover have "g' \<circ> f' = id"
  1435   moreover have "g' \<circ> f' = id"
  1583     using assms(6) linf ling
  1436     using id linf ling
  1584     unfolding linear_conv_bounded_linear[symmetric]
  1437     unfolding linear_conv_bounded_linear[symmetric]
  1585     using linear_inverse_left
  1438     using linear_inverse_left
  1586     by auto
  1439     by auto
  1587   moreover have *:"\<forall>t\<subseteq>s. x \<in> interior t \<longrightarrow> f x \<in> interior (f ` t)"
  1440   moreover have *: "\<And>T. \<lbrakk>T \<subseteq> S; x \<in> interior T\<rbrakk> \<Longrightarrow> f x \<in> interior (f ` T)"
  1588     apply clarify
       
  1589     apply (rule sussmann_open_mapping)
  1441     apply (rule sussmann_open_mapping)
  1590     apply (rule assms ling)+
  1442     apply (rule assms ling)+
  1591     apply auto
  1443     apply auto
  1592     done
  1444     done
  1593   have "continuous (at (f x)) g"
  1445   have "continuous (at (f x)) g"
  1594     unfolding continuous_at Lim_at
  1446     unfolding continuous_at Lim_at
  1595   proof (rule, rule)
  1447   proof (rule, rule)
  1596     fix e :: real
  1448     fix e :: real
  1597     assume "e > 0"
  1449     assume "e > 0"
  1598     then have "f x \<in> interior (f ` (ball x e \<inter> s))"
  1450     then have "f x \<in> interior (f ` (ball x e \<inter> S))"
  1599       using *[rule_format,of "ball x e \<inter> s"] \<open>x \<in> s\<close>
  1451       using *[rule_format,of "ball x e \<inter> S"] \<open>x \<in> S\<close>
  1600       by (auto simp add: interior_open[OF open_ball] interior_open[OF assms(1)])
  1452       by (auto simp add: interior_open[OF open_ball] interior_open[OF assms(1)])
  1601     then obtain d where d: "0 < d" "ball (f x) d \<subseteq> f ` (ball x e \<inter> s)"
  1453     then obtain d where d: "0 < d" "ball (f x) d \<subseteq> f ` (ball x e \<inter> S)"
  1602       unfolding mem_interior by blast
  1454       unfolding mem_interior by blast
  1603     show "\<exists>d>0. \<forall>y. 0 < dist y (f x) \<and> dist y (f x) < d \<longrightarrow> dist (g y) (g (f x)) < e"
  1455     show "\<exists>d>0. \<forall>y. 0 < dist y (f x) \<and> dist y (f x) < d \<longrightarrow> dist (g y) (g (f x)) < e"
  1604       apply (rule_tac x=d in exI)
  1456     proof (intro exI allI impI conjI)
  1605       apply rule
       
  1606       apply (rule d(1))
       
  1607       apply rule
       
  1608       apply rule
       
  1609     proof -
       
  1610       fix y
  1457       fix y
  1611       assume "0 < dist y (f x) \<and> dist y (f x) < d"
  1458       assume "0 < dist y (f x) \<and> dist y (f x) < d"
  1612       then have "g y \<in> g ` f ` (ball x e \<inter> s)"
  1459       then have "g y \<in> g ` f ` (ball x e \<inter> S)"
  1613         using d(2)[unfolded subset_eq,THEN bspec[where x=y]]
  1460         by (metis d(2) dist_commute mem_ball rev_image_eqI subset_iff)
  1614         by (auto simp add: dist_commute)
       
  1615       then have "g y \<in> ball x e \<inter> s"
       
  1616         using assms(4) by auto
       
  1617       then show "dist (g y) (g (f x)) < e"
  1461       then show "dist (g y) (g (f x)) < e"
  1618         using assms(4)[rule_format,OF \<open>x \<in> s\<close>]
  1462         using gf[OF \<open>x \<in> S\<close>]
  1619         by (auto simp add: dist_commute)
  1463         by (simp add: assms(4) dist_commute image_iff)
  1620     qed
  1464     qed (use d in auto)
  1621   qed
  1465   qed
  1622   moreover have "f x \<in> interior (f ` s)"
  1466   moreover have "f x \<in> interior (f ` S)"
  1623     apply (rule sussmann_open_mapping)
  1467     apply (rule sussmann_open_mapping)
  1624     apply (rule assms ling)+
  1468     apply (rule assms ling)+
  1625     using interior_open[OF assms(1)] and \<open>x \<in> s\<close>
  1469     using interior_open[OF assms(1)] and \<open>x \<in> S\<close>
  1626     apply auto
  1470     apply auto
  1627     done
  1471     done
  1628   moreover have "f (g y) = y" if "y \<in> interior (f ` s)" for y
  1472   moreover have "f (g y) = y" if "y \<in> interior (f ` S)" for y
  1629   proof -
  1473     by (metis gf imageE interiorE set_mp that)
  1630     from that have "y \<in> f ` s"
       
  1631       using interior_subset by auto
       
  1632     then obtain z where "z \<in> s" "y = f z" unfolding image_iff ..
       
  1633     then show ?thesis
       
  1634       using assms(4) by auto
       
  1635   qed
       
  1636   ultimately show ?thesis using assms
  1474   ultimately show ?thesis using assms
  1637     by (metis has_derivative_inverse_basic_x open_interior)
  1475     by (metis has_derivative_inverse_basic_x open_interior)
  1638 qed
  1476 qed
  1639 
  1477 
  1640 text \<open>A rewrite based on the other domain.\<close>
  1478 text \<open>A rewrite based on the other domain.\<close>
  1641 
  1479 
  1642 lemma has_derivative_inverse_strong_x:
  1480 lemma has_derivative_inverse_strong_x:
  1643   fixes f :: "'a::euclidean_space \<Rightarrow> 'a"
  1481   fixes f :: "'a::euclidean_space \<Rightarrow> 'a"
  1644   assumes "open s"
  1482   assumes "open S"
  1645     and "g y \<in> s"
  1483     and "g y \<in> S"
  1646     and "continuous_on s f"
  1484     and "continuous_on S f"
  1647     and "\<forall>x\<in>s. g (f x) = x"
  1485     and "\<And>x. x \<in> S \<Longrightarrow> g (f x) = x"
  1648     and "(f has_derivative f') (at (g y))"
  1486     and "(f has_derivative f') (at (g y))"
  1649     and "f' \<circ> g' = id"
  1487     and "f' \<circ> g' = id"
  1650     and "f (g y) = y"
  1488     and "f (g y) = y"
  1651   shows "(g has_derivative g') (at y)"
  1489   shows "(g has_derivative g') (at y)"
  1652   using has_derivative_inverse_strong[OF assms(1-6)]
  1490   using has_derivative_inverse_strong[OF assms(1-6)]
  1655 
  1493 
  1656 text \<open>On a region.\<close>
  1494 text \<open>On a region.\<close>
  1657 
  1495 
  1658 lemma has_derivative_inverse_on:
  1496 lemma has_derivative_inverse_on:
  1659   fixes f :: "'n::euclidean_space \<Rightarrow> 'n"
  1497   fixes f :: "'n::euclidean_space \<Rightarrow> 'n"
  1660   assumes "open s"
  1498   assumes "open S"
  1661     and "\<forall>x\<in>s. (f has_derivative f'(x)) (at x)"
  1499     and derf: "\<And>x. x \<in> S \<Longrightarrow> (f has_derivative f'(x)) (at x)"
  1662     and "\<forall>x\<in>s. g (f x) = x"
  1500     and "\<And>x. x \<in> S \<Longrightarrow> g (f x) = x"
  1663     and "f' x \<circ> g' x = id"
  1501     and "f' x \<circ> g' x = id"
  1664     and "x \<in> s"
  1502     and "x \<in> S"
  1665   shows "(g has_derivative g'(x)) (at (f x))"
  1503   shows "(g has_derivative g'(x)) (at (f x))"
  1666   apply (rule has_derivative_inverse_strong[where g'="g' x" and f=f])
  1504 proof (rule has_derivative_inverse_strong[where g'="g' x" and f=f])
  1667   apply (rule assms)+
  1505   show "continuous_on S f"
  1668   unfolding continuous_on_eq_continuous_at[OF assms(1)]
  1506   unfolding continuous_on_eq_continuous_at[OF \<open>open S\<close>]
  1669   apply rule
  1507   using derf has_derivative_continuous by blast
  1670   apply (rule differentiable_imp_continuous_within)
  1508 qed (use assms in auto)
  1671   unfolding differentiable_def
  1509 
  1672   using assms
       
  1673   apply auto
       
  1674   done
       
  1675 
  1510 
  1676 text \<open>Invertible derivative continous at a point implies local
  1511 text \<open>Invertible derivative continous at a point implies local
  1677 injectivity. It's only for this we need continuity of the derivative,
  1512 injectivity. It's only for this we need continuity of the derivative,
  1678 except of course if we want the fact that the inverse derivative is
  1513 except of course if we want the fact that the inverse derivative is
  1679 also continuous. So if we know for some other reason that the inverse
  1514 also continuous. So if we know for some other reason that the inverse
  1680 function exists, it's OK.\<close>
  1515 function exists, it's OK.\<close>
  1681 
  1516 
  1682 proposition has_derivative_locally_injective:
  1517 proposition has_derivative_locally_injective:
  1683   fixes f :: "'n::euclidean_space \<Rightarrow> 'm::euclidean_space"
  1518   fixes f :: "'n::euclidean_space \<Rightarrow> 'm::euclidean_space"
  1684   assumes "a \<in> s"
  1519   assumes "a \<in> S"
  1685       and "open s"
  1520       and "open S"
  1686       and bling: "bounded_linear g'"
  1521       and bling: "bounded_linear g'"
  1687       and "g' \<circ> f' a = id"
  1522       and "g' \<circ> f' a = id"
  1688       and derf: "\<And>x. x \<in> s \<Longrightarrow> (f has_derivative f' x) (at x)"
  1523       and derf: "\<And>x. x \<in> S \<Longrightarrow> (f has_derivative f' x) (at x)"
  1689       and "\<And>e. e > 0 \<Longrightarrow> \<exists>d>0. \<forall>x. dist a x < d \<longrightarrow> onorm (\<lambda>v. f' x v - f' a v) < e"
  1524       and "\<And>e. e > 0 \<Longrightarrow> \<exists>d>0. \<forall>x. dist a x < d \<longrightarrow> onorm (\<lambda>v. f' x v - f' a v) < e"
  1690   obtains r where "r > 0" "ball a r \<subseteq> s" "inj_on f (ball a r)"
  1525   obtains r where "r > 0" "ball a r \<subseteq> S" "inj_on f (ball a r)"
  1691 proof -
  1526 proof -
  1692   interpret bounded_linear g'
  1527   interpret bounded_linear g'
  1693     using assms by auto
  1528     using assms by auto
  1694   note f'g' = assms(4)[unfolded id_def o_def,THEN cong]
  1529   note f'g' = assms(4)[unfolded id_def o_def,THEN cong]
  1695   have "g' (f' a (\<Sum>Basis)) = (\<Sum>Basis)" "(\<Sum>Basis) \<noteq> (0::'n)"
  1530   have "g' (f' a (\<Sum>Basis)) = (\<Sum>Basis)" "(\<Sum>Basis) \<noteq> (0::'n)"
  1702     unfolding k_def using * by auto
  1537     unfolding k_def using * by auto
  1703   obtain d1 where d1:
  1538   obtain d1 where d1:
  1704       "0 < d1"
  1539       "0 < d1"
  1705       "\<And>x. dist a x < d1 \<Longrightarrow> onorm (\<lambda>v. f' x v - f' a v) < k"
  1540       "\<And>x. dist a x < d1 \<Longrightarrow> onorm (\<lambda>v. f' x v - f' a v) < k"
  1706     using assms(6) * by blast
  1541     using assms(6) * by blast
  1707   from \<open>open s\<close> obtain d2 where "d2 > 0" "ball a d2 \<subseteq> s"
  1542   from \<open>open S\<close> obtain d2 where "d2 > 0" "ball a d2 \<subseteq> S"
  1708     using \<open>a\<in>s\<close> ..
  1543     using \<open>a\<in>S\<close> ..
  1709   obtain d2 where "d2 > 0" "ball a d2 \<subseteq> s"
  1544   obtain d2 where d2: "0 < d2" "ball a d2 \<subseteq> S"
  1710     using assms(2,1) ..
  1545     using \<open>0 < d2\<close> \<open>ball a d2 \<subseteq> S\<close> by blast
  1711   obtain d2 where d2: "0 < d2" "ball a d2 \<subseteq> s"
       
  1712     using assms(2)
       
  1713     unfolding open_contains_ball
       
  1714     using \<open>a\<in>s\<close> by blast
       
  1715   obtain d where d: "0 < d" "d < d1" "d < d2"
  1546   obtain d where d: "0 < d" "d < d1" "d < d2"
  1716     using real_lbound_gt_zero[OF d1(1) d2(1)] by blast
  1547     using real_lbound_gt_zero[OF d1(1) d2(1)] by blast
  1717   show ?thesis
  1548   show ?thesis
  1718   proof
  1549   proof
  1719     show "0 < d" by (fact d)
  1550     show "0 < d" by (fact d)
  1720     show "ball a d \<subseteq> s"
  1551     show "ball a d \<subseteq> S"
  1721       using \<open>d < d2\<close> \<open>ball a d2 \<subseteq> s\<close> by auto
  1552       using \<open>d < d2\<close> \<open>ball a d2 \<subseteq> S\<close> by auto
  1722     show "inj_on f (ball a d)"
  1553     show "inj_on f (ball a d)"
  1723     unfolding inj_on_def
  1554     unfolding inj_on_def
  1724     proof (intro strip)
  1555     proof (intro strip)
  1725       fix x y
  1556       fix x y
  1726       assume as: "x \<in> ball a d" "y \<in> ball a d" "f x = f y"
  1557       assume as: "x \<in> ball a d" "y \<in> ball a d" "f x = f y"
  1727       define ph where [abs_def]: "ph w = w - g' (f w - f x)" for w
  1558       define ph where [abs_def]: "ph w = w - g' (f w - f x)" for w
  1728       have ph':"ph = g' \<circ> (\<lambda>w. f' a w - (f w - f x))"
  1559       have ph':"ph = g' \<circ> (\<lambda>w. f' a w - (f w - f x))"
  1729         unfolding ph_def o_def
  1560         unfolding ph_def o_def  by (simp add: diff f'g')
  1730         unfolding diff
       
  1731         using f'g'
       
  1732         by (auto simp: algebra_simps)
       
  1733       have "norm (ph x - ph y) \<le> (1 / 2) * norm (x - y)"
  1561       have "norm (ph x - ph y) \<le> (1 / 2) * norm (x - y)"
  1734         apply (rule differentiable_bound[OF convex_ball _ _ as(1-2), where f'="\<lambda>x v. v - g'(f' x v)"])
  1562       proof (rule differentiable_bound[OF convex_ball _ _ as(1-2)])
  1735         apply (rule_tac[!] ballI)
       
  1736       proof -
       
  1737         fix u
  1563         fix u
  1738         assume u: "u \<in> ball a d"
  1564         assume u: "u \<in> ball a d"
  1739         then have "u \<in> s"
  1565         then have "u \<in> S"
  1740           using d d2 by auto
  1566           using d d2 by auto
  1741         have *: "(\<lambda>v. v - g' (f' u v)) = g' \<circ> (\<lambda>w. f' a w - f' u w)"
  1567         have *: "(\<lambda>v. v - g' (f' u v)) = g' \<circ> (\<lambda>w. f' a w - f' u w)"
  1742           unfolding o_def and diff
  1568           unfolding o_def and diff
  1743           using f'g' by auto
  1569           using f'g' by auto
  1744         have blin: "bounded_linear (f' a)"
  1570         have blin: "bounded_linear (f' a)"
  1745           using \<open>a \<in> s\<close> derf by blast
  1571           using \<open>a \<in> S\<close> derf by blast
  1746         show "(ph has_derivative (\<lambda>v. v - g' (f' u v))) (at u within ball a d)"
  1572         show "(ph has_derivative (\<lambda>v. v - g' (f' u v))) (at u within ball a d)"
  1747           unfolding ph' * comp_def
  1573           unfolding ph' * comp_def
  1748           by (rule \<open>u \<in> s\<close> derivative_eq_intros has_derivative_at_withinI [OF derf] bounded_linear.has_derivative [OF blin]  bounded_linear.has_derivative [OF bling] |simp)+
  1574           by (rule \<open>u \<in> S\<close> derivative_eq_intros has_derivative_at_withinI [OF derf] bounded_linear.has_derivative [OF blin]  bounded_linear.has_derivative [OF bling] |simp)+
  1749         have **: "bounded_linear (\<lambda>x. f' u x - f' a x)" "bounded_linear (\<lambda>x. f' a x - f' u x)"
  1575         have **: "bounded_linear (\<lambda>x. f' u x - f' a x)" "bounded_linear (\<lambda>x. f' a x - f' u x)"
  1750           apply (rule_tac[!] bounded_linear_sub)
  1576           using \<open>u \<in> S\<close> blin bounded_linear_sub derf by auto
  1751           apply (rule_tac[!] has_derivative_bounded_linear)
  1577         then have "onorm (\<lambda>v. v - g' (f' u v)) \<le> onorm g' * onorm (\<lambda>w. f' a w - f' u w)"
  1752           using assms(5) \<open>u \<in> s\<close> \<open>a \<in> s\<close>
  1578           by (simp add: "*" bounded_linear_axioms onorm_compose)
  1753           apply auto
       
  1754           done
       
  1755         have "onorm (\<lambda>v. v - g' (f' u v)) \<le> onorm g' * onorm (\<lambda>w. f' a w - f' u w)"
       
  1756           unfolding *
       
  1757           apply (rule onorm_compose)
       
  1758           apply (rule assms(3) **)+
       
  1759           done
       
  1760         also have "\<dots> \<le> onorm g' * k"
  1579         also have "\<dots> \<le> onorm g' * k"
  1761           apply (rule mult_left_mono)
  1580           apply (rule mult_left_mono)
  1762           using d1(2)[of u]
  1581           using d1(2)[of u]
  1763           using onorm_neg[where f="\<lambda>x. f' u x - f' a x"]
  1582           using onorm_neg[where f="\<lambda>x. f' u x - f' a x"] d u onorm_pos_le[OF bling] apply (auto simp: algebra_simps)
  1764           using d and u and onorm_pos_le[OF assms(3)]
       
  1765           apply (auto simp: algebra_simps)
       
  1766           done
  1583           done
  1767         also have "\<dots> \<le> 1 / 2"
  1584         also have "\<dots> \<le> 1 / 2"
  1768           unfolding k_def by auto
  1585           unfolding k_def by auto
  1769         finally show "onorm (\<lambda>v. v - g' (f' u v)) \<le> 1 / 2" .
  1586         finally show "onorm (\<lambda>v. v - g' (f' u v)) \<le> 1 / 2" .
  1770       qed
  1587       qed
  1771       moreover have "norm (ph y - ph x) = norm (y - x)"
  1588       moreover have "norm (ph y - ph x) = norm (y - x)"
  1772         apply (rule arg_cong[where f=norm])
  1589         by (simp add: as(3) ph_def)
  1773         unfolding ph_def
       
  1774         using diff
       
  1775         unfolding as
       
  1776         apply auto
       
  1777         done
       
  1778       ultimately show "x = y"
  1590       ultimately show "x = y"
  1779         unfolding norm_minus_commute by auto
  1591         unfolding norm_minus_commute by auto
  1780     qed
  1592     qed
  1781   qed
  1593   qed
  1782 qed
  1594 qed
  1784 
  1596 
  1785 subsection \<open>Uniformly convergent sequence of derivatives\<close>
  1597 subsection \<open>Uniformly convergent sequence of derivatives\<close>
  1786 
  1598 
  1787 lemma has_derivative_sequence_lipschitz_lemma:
  1599 lemma has_derivative_sequence_lipschitz_lemma:
  1788   fixes f :: "nat \<Rightarrow> 'a::real_normed_vector \<Rightarrow> 'b::real_normed_vector"
  1600   fixes f :: "nat \<Rightarrow> 'a::real_normed_vector \<Rightarrow> 'b::real_normed_vector"
  1789   assumes "convex s"
  1601   assumes "convex S"
  1790     and "\<forall>n. \<forall>x\<in>s. ((f n) has_derivative (f' n x)) (at x within s)"
  1602     and derf: "\<And>n x. x \<in> S \<Longrightarrow> ((f n) has_derivative (f' n x)) (at x within S)"
  1791     and "\<forall>n\<ge>N. \<forall>x\<in>s. \<forall>h. norm (f' n x h - g' x h) \<le> e * norm h"
  1603     and nle: "\<And>n x h. \<lbrakk>n\<ge>N; x \<in> S\<rbrakk> \<Longrightarrow> norm (f' n x h - g' x h) \<le> e * norm h"
  1792     and "0 \<le> e"
  1604     and "0 \<le> e"
  1793   shows "\<forall>m\<ge>N. \<forall>n\<ge>N. \<forall>x\<in>s. \<forall>y\<in>s. norm ((f m x - f n x) - (f m y - f n y)) \<le> 2 * e * norm (x - y)"
  1605   shows "\<forall>m\<ge>N. \<forall>n\<ge>N. \<forall>x\<in>S. \<forall>y\<in>S. norm ((f m x - f n x) - (f m y - f n y)) \<le> 2 * e * norm (x - y)"
  1794 proof rule+
  1606 proof clarify
  1795   fix m n x y
  1607   fix m n x y
  1796   assume as: "N \<le> m" "N \<le> n" "x \<in> s" "y \<in> s"
  1608   assume as: "N \<le> m" "N \<le> n" "x \<in> S" "y \<in> S"
  1797   show "norm ((f m x - f n x) - (f m y - f n y)) \<le> 2 * e * norm (x - y)"
  1609   show "norm ((f m x - f n x) - (f m y - f n y)) \<le> 2 * e * norm (x - y)"
  1798     apply (rule differentiable_bound[where f'="\<lambda>x h. f' m x h - f' n x h", OF assms(1) _ _ as(3-4)])
  1610   proof (rule differentiable_bound[where f'="\<lambda>x h. f' m x h - f' n x h", OF \<open>convex S\<close> _ _ as(3-4)])
  1799     apply (rule_tac[!] ballI)
       
  1800   proof -
       
  1801     fix x
  1611     fix x
  1802     assume "x \<in> s"
  1612     assume "x \<in> S"
  1803     show "((\<lambda>a. f m a - f n a) has_derivative (\<lambda>h. f' m x h - f' n x h)) (at x within s)"
  1613     show "((\<lambda>a. f m a - f n a) has_derivative (\<lambda>h. f' m x h - f' n x h)) (at x within S)"
  1804       by (rule derivative_intros assms(2)[rule_format] \<open>x\<in>s\<close>)+
  1614       by (rule derivative_intros derf \<open>x\<in>S\<close>)+
  1805     show "onorm (\<lambda>h. f' m x h - f' n x h) \<le> 2 * e"
  1615     show "onorm (\<lambda>h. f' m x h - f' n x h) \<le> 2 * e"
  1806     proof (rule onorm_bound)
  1616     proof (rule onorm_bound)
  1807       fix h
  1617       fix h
  1808       have "norm (f' m x h - f' n x h) \<le> norm (f' m x h - g' x h) + norm (f' n x h - g' x h)"
  1618       have "norm (f' m x h - f' n x h) \<le> norm (f' m x h - g' x h) + norm (f' n x h - g' x h)"
  1809         using norm_triangle_ineq[of "f' m x h - g' x h" "- f' n x h + g' x h"]
  1619         using norm_triangle_ineq[of "f' m x h - g' x h" "- f' n x h + g' x h"]
  1810         unfolding norm_minus_commute
  1620         by (auto simp add: algebra_simps norm_minus_commute)
  1811         by (auto simp add: algebra_simps)
       
  1812       also have "\<dots> \<le> e * norm h + e * norm h"
  1621       also have "\<dots> \<le> e * norm h + e * norm h"
  1813         using assms(3)[rule_format,OF \<open>N \<le> m\<close> \<open>x \<in> s\<close>, of h]
  1622         using nle[OF \<open>N \<le> m\<close> \<open>x \<in> S\<close>, of h] nle[OF \<open>N \<le> n\<close> \<open>x \<in> S\<close>, of h]
  1814         using assms(3)[rule_format,OF \<open>N \<le> n\<close> \<open>x \<in> s\<close>, of h]
       
  1815         by (auto simp add: field_simps)
  1623         by (auto simp add: field_simps)
  1816       finally show "norm (f' m x h - f' n x h) \<le> 2 * e * norm h"
  1624       finally show "norm (f' m x h - f' n x h) \<le> 2 * e * norm h"
  1817         by auto
  1625         by auto
  1818     qed (simp add: \<open>0 \<le> e\<close>)
  1626     qed (simp add: \<open>0 \<le> e\<close>)
  1819   qed
  1627   qed
  1821 
  1629 
  1822 lemma has_derivative_sequence_Lipschitz:
  1630 lemma has_derivative_sequence_Lipschitz:
  1823   fixes f :: "nat \<Rightarrow> 'a::real_normed_vector \<Rightarrow> 'b::real_normed_vector"
  1631   fixes f :: "nat \<Rightarrow> 'a::real_normed_vector \<Rightarrow> 'b::real_normed_vector"
  1824   assumes "convex S"
  1632   assumes "convex S"
  1825     and "\<And>n x. x \<in> S \<Longrightarrow> ((f n) has_derivative (f' n x)) (at x within S)"
  1633     and "\<And>n x. x \<in> S \<Longrightarrow> ((f n) has_derivative (f' n x)) (at x within S)"
  1826     and "\<And>e. e > 0 \<Longrightarrow> \<exists>N. \<forall>n\<ge>N. \<forall>x\<in>S. \<forall>h. norm (f' n x h - g' x h) \<le> e * norm h"
  1634     and nle: "\<And>e. e > 0 \<Longrightarrow> \<forall>\<^sub>F n in sequentially. \<forall>x\<in>S. \<forall>h. norm (f' n x h - g' x h) \<le> e * norm h"
  1827     and "e > 0"
  1635     and "e > 0"
  1828   shows "\<exists>N. \<forall>m\<ge>N. \<forall>n\<ge>N. \<forall>x\<in>S. \<forall>y\<in>S.
  1636   shows "\<exists>N. \<forall>m\<ge>N. \<forall>n\<ge>N. \<forall>x\<in>S. \<forall>y\<in>S.
  1829     norm ((f m x - f n x) - (f m y - f n y)) \<le> e * norm (x - y)"
  1637     norm ((f m x - f n x) - (f m y - f n y)) \<le> e * norm (x - y)"
  1830 proof -
  1638 proof -
  1831   have *: "2 * (1/2* e) = e" "1/2 * e >0"
  1639   have *: "2 * (e/2) = e"
  1832     using \<open>e>0\<close> by auto
  1640     using \<open>e > 0\<close> by auto
  1833   obtain N where "\<forall>n\<ge>N. \<forall>x\<in>S. \<forall>h. norm (f' n x h - g' x h) \<le> 1 / 2 * e * norm h"
  1641   obtain N where "\<forall>n\<ge>N. \<forall>x\<in>S. \<forall>h. norm (f' n x h - g' x h) \<le> (e/2) * norm h"
  1834     using assms(3) *(2) by blast
  1642     using nle \<open>e > 0\<close>
       
  1643     unfolding eventually_sequentially
       
  1644     by (metis less_divide_eq_numeral1(1) mult_zero_left)
  1835   then show "\<exists>N. \<forall>m\<ge>N. \<forall>n\<ge>N. \<forall>x\<in>S. \<forall>y\<in>S. norm (f m x - f n x - (f m y - f n y)) \<le> e * norm (x - y)"
  1645   then show "\<exists>N. \<forall>m\<ge>N. \<forall>n\<ge>N. \<forall>x\<in>S. \<forall>y\<in>S. norm (f m x - f n x - (f m y - f n y)) \<le> e * norm (x - y)"
  1836     apply (rule_tac x=N in exI)
  1646     apply (rule_tac x=N in exI)
  1837     apply (rule has_derivative_sequence_lipschitz_lemma[where e="1/2 *e", unfolded *])
  1647     apply (rule has_derivative_sequence_lipschitz_lemma[where e="e/2", unfolded *])
  1838     using assms \<open>e > 0\<close>
  1648     using assms \<open>e > 0\<close>
  1839     apply auto
  1649     apply auto
  1840     done
  1650     done
  1841 qed
  1651 qed
  1842 
  1652 
  1843 lemma has_derivative_sequence:
  1653 lemma has_derivative_sequence:
  1844   fixes f :: "nat \<Rightarrow> 'a::real_normed_vector \<Rightarrow> 'b::banach"
  1654   fixes f :: "nat \<Rightarrow> 'a::real_normed_vector \<Rightarrow> 'b::banach"
  1845   assumes "convex S"
  1655   assumes "convex S"
  1846     and "\<And>n x. x \<in> S \<Longrightarrow> ((f n) has_derivative (f' n x)) (at x within S)"
  1656     and derf: "\<And>n x. x \<in> S \<Longrightarrow> ((f n) has_derivative (f' n x)) (at x within S)"
  1847     and "\<And>e. e > 0 \<Longrightarrow> \<exists>N. \<forall>n\<ge>N. \<forall>x\<in>S. \<forall>h. norm (f' n x h - g' x h) \<le> e * norm h"
  1657     and nle: "\<And>e. e > 0 \<Longrightarrow> \<forall>\<^sub>F n in sequentially. \<forall>x\<in>S. \<forall>h. norm (f' n x h - g' x h) \<le> e * norm h"
  1848     and "x0 \<in> S"
  1658     and "x0 \<in> S"
  1849     and "((\<lambda>n. f n x0) \<longlongrightarrow> l) sequentially"
  1659     and lim: "((\<lambda>n. f n x0) \<longlongrightarrow> l) sequentially"
  1850   shows "\<exists>g. \<forall>x\<in>S. ((\<lambda>n. f n x) \<longlongrightarrow> g x) sequentially \<and> (g has_derivative g'(x)) (at x within S)"
  1660   shows "\<exists>g. \<forall>x\<in>S. (\<lambda>n. f n x) \<longlonglongrightarrow> g x \<and> (g has_derivative g'(x)) (at x within S)"
  1851 proof -
  1661 proof -
  1852   have lem1: "\<And>e. e > 0 \<Longrightarrow> \<exists>N. \<forall>m\<ge>N. \<forall>n\<ge>N. \<forall>x\<in>S. \<forall>y\<in>S.
  1662   have lem1: "\<And>e. e > 0 \<Longrightarrow> \<exists>N. \<forall>m\<ge>N. \<forall>n\<ge>N. \<forall>x\<in>S. \<forall>y\<in>S.
  1853       norm ((f m x - f n x) - (f m y - f n y)) \<le> e * norm (x - y)"
  1663       norm ((f m x - f n x) - (f m y - f n y)) \<le> e * norm (x - y)"
  1854     using assms(1,2,3) by (rule has_derivative_sequence_Lipschitz)
  1664     using assms(1,2,3) by (rule has_derivative_sequence_Lipschitz)
  1855   have "\<exists>g. \<forall>x\<in>S. ((\<lambda>n. f n x) \<longlongrightarrow> g x) sequentially"
  1665   have "\<exists>g. \<forall>x\<in>S. ((\<lambda>n. f n x) \<longlongrightarrow> g x) sequentially"
  1856     apply (rule bchoice)
  1666   proof (intro ballI bchoice)
  1857     unfolding convergent_eq_Cauchy
       
  1858   proof
       
  1859     fix x
  1667     fix x
  1860     assume "x \<in> S"
  1668     assume "x \<in> S"
  1861     show "Cauchy (\<lambda>n. f n x)"
  1669     show "\<exists>y. (\<lambda>n. f n x) \<longlonglongrightarrow> y"
       
  1670     unfolding convergent_eq_Cauchy
  1862     proof (cases "x = x0")
  1671     proof (cases "x = x0")
  1863       case True
  1672       case True
  1864       then show ?thesis
  1673       then show "Cauchy (\<lambda>n. f n x)"
  1865         using LIMSEQ_imp_Cauchy[OF assms(5)] by auto
  1674         using LIMSEQ_imp_Cauchy[OF lim] by auto
  1866     next
  1675     next
  1867       case False
  1676       case False
  1868       show ?thesis
  1677       show "Cauchy (\<lambda>n. f n x)"
  1869         unfolding Cauchy_def
  1678         unfolding Cauchy_def
  1870       proof (intro allI impI)
  1679       proof (intro allI impI)
  1871         fix e :: real
  1680         fix e :: real
  1872         assume "e > 0"
  1681         assume "e > 0"
  1873         hence *: "e / 2 > 0" "e / 2 / norm (x - x0) > 0" using False by auto
  1682         hence *: "e / 2 > 0" "e / 2 / norm (x - x0) > 0" using False by auto
  1874         obtain M where M: "\<forall>m\<ge>M. \<forall>n\<ge>M. dist (f m x0) (f n x0) < e / 2"
  1683         obtain M where M: "\<forall>m\<ge>M. \<forall>n\<ge>M. dist (f m x0) (f n x0) < e / 2"
  1875           using LIMSEQ_imp_Cauchy[OF assms(5)]
  1684           using LIMSEQ_imp_Cauchy[OF lim] * unfolding Cauchy_def by blast
  1876           unfolding Cauchy_def
       
  1877           using *(1) by blast
       
  1878         obtain N where N:
  1685         obtain N where N:
  1879           "\<forall>m\<ge>N. \<forall>n\<ge>N.
  1686           "\<forall>m\<ge>N. \<forall>n\<ge>N.
  1880             \<forall>xa\<in>S. \<forall>y\<in>S. norm (f m xa - f n xa - (f m y - f n y)) \<le>
  1687             \<forall>u\<in>S. \<forall>y\<in>S. norm (f m u - f n u - (f m y - f n y)) \<le>
  1881               e / 2 / norm (x - x0) * norm (xa - y)"
  1688               e / 2 / norm (x - x0) * norm (u - y)"
  1882         using lem1 *(2) by blast
  1689         using lem1 *(2) by blast
  1883         show "\<exists>M. \<forall>m\<ge>M. \<forall>n\<ge>M. dist (f m x) (f n x) < e"
  1690         show "\<exists>M. \<forall>m\<ge>M. \<forall>n\<ge>M. dist (f m x) (f n x) < e"
  1884         proof (intro exI allI impI)
  1691         proof (intro exI allI impI)
  1885           fix m n
  1692           fix m n
  1886           assume as: "max M N \<le>m" "max M N\<le>n"
  1693           assume as: "max M N \<le>m" "max M N\<le>n"
  1887           have "dist (f m x) (f n x) \<le>
  1694           have "dist (f m x) (f n x) \<le> norm (f m x0 - f n x0) + norm (f m x - f n x - (f m x0 - f n x0))"
  1888               norm (f m x0 - f n x0) + norm (f m x - f n x - (f m x0 - f n x0))"
       
  1889             unfolding dist_norm
  1695             unfolding dist_norm
  1890             by (rule norm_triangle_sub)
  1696             by (rule norm_triangle_sub)
  1891           also have "\<dots> \<le> norm (f m x0 - f n x0) + e / 2"
  1697           also have "\<dots> \<le> norm (f m x0 - f n x0) + e / 2"
  1892             using N[rule_format,OF _ _ \<open>x\<in>S\<close> \<open>x0\<in>S\<close>, of m n] and as and False
  1698             using N \<open>x\<in>S\<close> \<open>x0\<in>S\<close> as False by fastforce
  1893             by auto
       
  1894           also have "\<dots> < e / 2 + e / 2"
  1699           also have "\<dots> < e / 2 + e / 2"
  1895             apply (rule add_strict_right_mono)
  1700             by (rule add_strict_right_mono) (use as M in \<open>auto simp: dist_norm\<close>)
  1896             using as and M[rule_format]
       
  1897             unfolding dist_norm
       
  1898             apply auto
       
  1899             done
       
  1900           finally show "dist (f m x) (f n x) < e"
  1701           finally show "dist (f m x) (f n x) < e"
  1901             by auto
  1702             by auto
  1902         qed
  1703         qed
  1903       qed
  1704       qed
  1904     qed
  1705     qed
  1905   qed
  1706   qed
  1906   then obtain g where g: "\<forall>x\<in>S. (\<lambda>n. f n x) \<longlonglongrightarrow> g x" ..
  1707   then obtain g where g: "\<forall>x\<in>S. (\<lambda>n. f n x) \<longlonglongrightarrow> g x" ..
  1907   have lem2: "\<forall>e>0. \<exists>N. \<forall>n\<ge>N. \<forall>x\<in>S. \<forall>y\<in>S. norm ((f n x - f n y) - (g x - g y)) \<le> e * norm (x - y)"
  1708   have lem2: "\<exists>N. \<forall>n\<ge>N. \<forall>x\<in>S. \<forall>y\<in>S. norm ((f n x - f n y) - (g x - g y)) \<le> e * norm (x - y)" if "e > 0" for e
  1908   proof (rule, rule)
  1709   proof -
  1909     fix e :: real
       
  1910     assume *: "e > 0"
       
  1911     obtain N where
  1710     obtain N where
  1912       N: "\<forall>m\<ge>N. \<forall>n\<ge>N. \<forall>x\<in>S. \<forall>y\<in>S. norm (f m x - f n x - (f m y - f n y)) \<le> e * norm (x - y)"
  1711       N: "\<forall>m\<ge>N. \<forall>n\<ge>N. \<forall>x\<in>S. \<forall>y\<in>S. norm (f m x - f n x - (f m y - f n y)) \<le> e * norm (x - y)"
  1913       using lem1 * by blast
  1712       using lem1 \<open>e > 0\<close> by blast
  1914     show "\<exists>N. \<forall>n\<ge>N. \<forall>x\<in>S. \<forall>y\<in>S. norm (f n x - f n y - (g x - g y)) \<le> e * norm (x - y)"
  1713     show "\<exists>N. \<forall>n\<ge>N. \<forall>x\<in>S. \<forall>y\<in>S. norm (f n x - f n y - (g x - g y)) \<le> e * norm (x - y)"
  1915       apply (rule_tac x=N in exI)
  1714     proof (intro exI ballI allI impI)
  1916     proof rule+
       
  1917       fix n x y
  1715       fix n x y
  1918       assume as: "N \<le> n" "x \<in> S" "y \<in> S"
  1716       assume as: "N \<le> n" "x \<in> S" "y \<in> S"
  1919       have "((\<lambda>m. norm (f n x - f n y - (f m x - f m y))) \<longlongrightarrow> norm (f n x - f n y - (g x - g y))) sequentially"
  1717       have "((\<lambda>m. norm (f n x - f n y - (f m x - f m y))) \<longlongrightarrow> norm (f n x - f n y - (g x - g y))) sequentially"
  1920         by (intro tendsto_intros g[rule_format] as)
  1718         by (intro tendsto_intros g[rule_format] as)
  1921       moreover have "eventually (\<lambda>m. norm (f n x - f n y - (f m x - f m y)) \<le> e * norm (x - y)) sequentially"
  1719       moreover have "eventually (\<lambda>m. norm (f n x - f n y - (f m x - f m y)) \<le> e * norm (x - y)) sequentially"
  1922         unfolding eventually_sequentially
  1720         unfolding eventually_sequentially
  1923       proof (intro exI allI impI)
  1721       proof (intro exI allI impI)
  1924         fix m
  1722         fix m
  1925         assume "N \<le> m"
  1723         assume "N \<le> m"
  1926         then show "norm (f n x - f n y - (f m x - f m y)) \<le> e * norm (x - y)"
  1724         then show "norm (f n x - f n y - (f m x - f m y)) \<le> e * norm (x - y)"
  1927           using N[rule_format, of n m x y] and as
  1725           using N as by (auto simp add: algebra_simps)
  1928           by (auto simp add: algebra_simps)
       
  1929       qed
  1726       qed
  1930       ultimately show "norm (f n x - f n y - (g x - g y)) \<le> e * norm (x - y)"
  1727       ultimately show "norm (f n x - f n y - (g x - g y)) \<le> e * norm (x - y)"
  1931         by (simp add: tendsto_upperbound)
  1728         by (simp add: tendsto_upperbound)
  1932     qed
  1729     qed
  1933   qed
  1730   qed
  1934   have "\<forall>x\<in>S. ((\<lambda>n. f n x) \<longlongrightarrow> g x) sequentially \<and> (g has_derivative g' x) (at x within S)"
  1731   have "\<forall>x\<in>S. ((\<lambda>n. f n x) \<longlongrightarrow> g x) sequentially \<and> (g has_derivative g' x) (at x within S)"
  1935     unfolding has_derivative_within_alt2
  1732     unfolding has_derivative_within_alt2
  1936   proof (intro ballI conjI)
  1733   proof (intro ballI conjI allI impI)
  1937     fix x
  1734     fix x
  1938     assume "x \<in> S"
  1735     assume "x \<in> S"
  1939     then show "((\<lambda>n. f n x) \<longlongrightarrow> g x) sequentially"
  1736     then show "(\<lambda>n. f n x) \<longlonglongrightarrow> g x"
  1940       by (simp add: g)
  1737       by (simp add: g)
  1941     have lem3: "\<forall>u. ((\<lambda>n. f' n x u) \<longlongrightarrow> g' x u) sequentially"
  1738     have tog': "(\<lambda>n. f' n x u) \<longlonglongrightarrow> g' x u" for u
  1942       unfolding filterlim_def le_nhds_metric_le eventually_filtermap dist_norm
  1739       unfolding filterlim_def le_nhds_metric_le eventually_filtermap dist_norm
  1943     proof (intro allI impI)
  1740     proof (intro allI impI)
  1944       fix u
       
  1945       fix e :: real
  1741       fix e :: real
  1946       assume "e > 0"
  1742       assume "e > 0"
  1947       show "eventually (\<lambda>n. norm (f' n x u - g' x u) \<le> e) sequentially"
  1743       show "eventually (\<lambda>n. norm (f' n x u - g' x u) \<le> e) sequentially"
  1948       proof (cases "u = 0")
  1744       proof (cases "u = 0")
  1949         case True
  1745         case True
  1950         have "eventually (\<lambda>n. norm (f' n x u - g' x u) \<le> e * norm u) sequentially"
  1746         have "eventually (\<lambda>n. norm (f' n x u - g' x u) \<le> e * norm u) sequentially"
  1951           using assms(3)[folded eventually_sequentially] and \<open>0 < e\<close> and \<open>x \<in> S\<close>
  1747           using nle \<open>0 < e\<close> \<open>x \<in> S\<close> by (fast elim: eventually_mono)
  1952           by (fast elim: eventually_mono)
       
  1953         then show ?thesis
  1748         then show ?thesis
  1954           using \<open>u = 0\<close> and \<open>0 < e\<close> by (auto elim: eventually_mono)
  1749           using \<open>u = 0\<close> \<open>0 < e\<close> by (auto elim: eventually_mono)
  1955       next
  1750       next
  1956         case False
  1751         case False
  1957         with \<open>0 < e\<close> have "0 < e / norm u" by simp
  1752         with \<open>0 < e\<close> have "0 < e / norm u" by simp
  1958         then have "eventually (\<lambda>n. norm (f' n x u - g' x u) \<le> e / norm u * norm u) sequentially"
  1753         then have "eventually (\<lambda>n. norm (f' n x u - g' x u) \<le> e / norm u * norm u) sequentially"
  1959           using assms(3)[folded eventually_sequentially] and \<open>x \<in> S\<close>
  1754           using nle \<open>x \<in> S\<close> by (fast elim: eventually_mono)
  1960           by (fast elim: eventually_mono)
       
  1961         then show ?thesis
  1755         then show ?thesis
  1962           using \<open>u \<noteq> 0\<close> by simp
  1756           using \<open>u \<noteq> 0\<close> by simp
  1963       qed
  1757       qed
  1964     qed
  1758     qed
  1965     show "bounded_linear (g' x)"
  1759     show "bounded_linear (g' x)"
  1966     proof
  1760     proof
  1967       fix x' y z :: 'a
  1761       fix x' y z :: 'a
  1968       fix c :: real
  1762       fix c :: real
  1969       note lin = assms(2)[rule_format,OF \<open>x\<in>S\<close>,THEN has_derivative_bounded_linear]
  1763       note lin = assms(2)[rule_format,OF \<open>x\<in>S\<close>,THEN has_derivative_bounded_linear]
  1970       show "g' x (c *\<^sub>R x') = c *\<^sub>R g' x x'"
  1764       show "g' x (c *\<^sub>R x') = c *\<^sub>R g' x x'"
  1971         apply (rule tendsto_unique[OF trivial_limit_sequentially])
  1765         apply (rule tendsto_unique[OF trivial_limit_sequentially tog'])
  1972         apply (rule lem3[rule_format])
       
  1973         unfolding lin[THEN bounded_linear.linear, THEN linear_cmul]
  1766         unfolding lin[THEN bounded_linear.linear, THEN linear_cmul]
  1974         apply (intro tendsto_intros)
  1767         apply (intro tendsto_intros tog')
  1975         apply (rule lem3[rule_format])
       
  1976         done
  1768         done
  1977       show "g' x (y + z) = g' x y + g' x z"
  1769       show "g' x (y + z) = g' x y + g' x z"
  1978         apply (rule tendsto_unique[OF trivial_limit_sequentially])
  1770         apply (rule tendsto_unique[OF trivial_limit_sequentially tog'])
  1979         apply (rule lem3[rule_format])
       
  1980         unfolding lin[THEN bounded_linear.linear, THEN linear_add]
  1771         unfolding lin[THEN bounded_linear.linear, THEN linear_add]
  1981         apply (rule tendsto_add)
  1772         apply (rule tendsto_add)
  1982         apply (rule lem3[rule_format])+
  1773         apply (rule tog')+
  1983         done
  1774         done
  1984       obtain N where N: "\<forall>h. norm (f' N x h - g' x h) \<le> 1 * norm h"
  1775       obtain N where N: "\<forall>h. norm (f' N x h - g' x h) \<le> 1 * norm h"
  1985         using assms(3) \<open>x \<in> S\<close> by (fast intro: zero_less_one)
  1776         using nle \<open>x \<in> S\<close> unfolding eventually_sequentially by (fast intro: zero_less_one)
  1986       have "bounded_linear (f' N x)"
  1777       have "bounded_linear (f' N x)"
  1987         using assms(2) \<open>x \<in> S\<close> by fast
  1778         using derf \<open>x \<in> S\<close> by fast
  1988       from bounded_linear.bounded [OF this]
  1779       from bounded_linear.bounded [OF this]
  1989       obtain K where K: "\<forall>h. norm (f' N x h) \<le> norm h * K" ..
  1780       obtain K where K: "\<forall>h. norm (f' N x h) \<le> norm h * K" ..
  1990       {
  1781       {
  1991         fix h
  1782         fix h
  1992         have "norm (g' x h) = norm (f' N x h - (f' N x h - g' x h))"
  1783         have "norm (g' x h) = norm (f' N x h - (f' N x h - g' x h))"
  1998         finally have "norm (g' x h) \<le> norm h * (K + 1)"
  1789         finally have "norm (g' x h) \<le> norm h * (K + 1)"
  1999           by (simp add: ring_distribs)
  1790           by (simp add: ring_distribs)
  2000       }
  1791       }
  2001       then show "\<exists>K. \<forall>h. norm (g' x h) \<le> norm h * K" by fast
  1792       then show "\<exists>K. \<forall>h. norm (g' x h) \<le> norm h * K" by fast
  2002     qed
  1793     qed
  2003     show "\<forall>e>0. eventually (\<lambda>y. norm (g y - g x - g' x (y - x)) \<le> e * norm (y - x)) (at x within S)"
  1794     show "eventually (\<lambda>y. norm (g y - g x - g' x (y - x)) \<le> e * norm (y - x)) (at x within S)"
  2004     proof (rule, rule)
  1795       if "e > 0" for e
  2005       fix e :: real
  1796     proof -
  2006       assume "e > 0"
  1797       have *: "e / 3 > 0"
  2007       then have *: "e / 3 > 0"
  1798         using that by auto
  2008         by auto
       
  2009       obtain N1 where N1: "\<forall>n\<ge>N1. \<forall>x\<in>S. \<forall>h. norm (f' n x h - g' x h) \<le> e / 3 * norm h"
  1799       obtain N1 where N1: "\<forall>n\<ge>N1. \<forall>x\<in>S. \<forall>h. norm (f' n x h - g' x h) \<le> e / 3 * norm h"
  2010         using assms(3) * by blast
  1800         using nle * unfolding eventually_sequentially by blast
  2011       obtain N2 where
  1801       obtain N2 where
  2012           N2: "\<forall>n\<ge>N2. \<forall>x\<in>S. \<forall>y\<in>S. norm (f n x - f n y - (g x - g y)) \<le> e / 3 * norm (x - y)"
  1802           N2[rule_format]: "\<forall>n\<ge>N2. \<forall>x\<in>S. \<forall>y\<in>S. norm (f n x - f n y - (g x - g y)) \<le> e / 3 * norm (x - y)"
  2013         using lem2 * by blast
  1803         using lem2 * by blast
  2014       let ?N = "max N1 N2"
  1804       let ?N = "max N1 N2"
  2015       have "eventually (\<lambda>y. norm (f ?N y - f ?N x - f' ?N x (y - x)) \<le> e / 3 * norm (y - x)) (at x within S)"
  1805       have "eventually (\<lambda>y. norm (f ?N y - f ?N x - f' ?N x (y - x)) \<le> e / 3 * norm (y - x)) (at x within S)"
  2016         using assms(2)[unfolded has_derivative_within_alt2] and \<open>x \<in> S\<close> and * by fast
  1806         using derf[unfolded has_derivative_within_alt2] and \<open>x \<in> S\<close> and * by fast
  2017       moreover have "eventually (\<lambda>y. y \<in> S) (at x within S)"
  1807       moreover have "eventually (\<lambda>y. y \<in> S) (at x within S)"
  2018         unfolding eventually_at by (fast intro: zero_less_one)
  1808         unfolding eventually_at by (fast intro: zero_less_one)
  2019       ultimately show "\<forall>\<^sub>F y in at x within S. norm (g y - g x - g' x (y - x)) \<le> e * norm (y - x)"
  1809       ultimately show "\<forall>\<^sub>F y in at x within S. norm (g y - g x - g' x (y - x)) \<le> e * norm (y - x)"
  2020       proof (rule eventually_elim2)
  1810       proof (rule eventually_elim2)
  2021         fix y
  1811         fix y
  2022         assume "y \<in> S"
  1812         assume "y \<in> S"
  2023         assume "norm (f ?N y - f ?N x - f' ?N x (y - x)) \<le> e / 3 * norm (y - x)"
  1813         assume "norm (f ?N y - f ?N x - f' ?N x (y - x)) \<le> e / 3 * norm (y - x)"
  2024         moreover have "norm (g y - g x - (f ?N y - f ?N x)) \<le> e / 3 * norm (y - x)"
  1814         moreover have "norm (g y - g x - (f ?N y - f ?N x)) \<le> e / 3 * norm (y - x)"
  2025           using N2[rule_format, OF _ \<open>y \<in> S\<close> \<open>x \<in> S\<close>]
  1815           using N2[OF _ \<open>y \<in> S\<close> \<open>x \<in> S\<close>]
  2026           by (simp add: norm_minus_commute)
  1816           by (simp add: norm_minus_commute)
  2027         ultimately have "norm (g y - g x - f' ?N x (y - x)) \<le> 2 * e / 3 * norm (y - x)"
  1817         ultimately have "norm (g y - g x - f' ?N x (y - x)) \<le> 2 * e / 3 * norm (y - x)"
  2028           using norm_triangle_le[of "g y - g x - (f ?N y - f ?N x)" "f ?N y - f ?N x - f' ?N x (y - x)" "2 * e / 3 * norm (y - x)"]
  1818           using norm_triangle_le[of "g y - g x - (f ?N y - f ?N x)" "f ?N y - f ?N x - f' ?N x (y - x)" "2 * e / 3 * norm (y - x)"]
  2029           by (auto simp add: algebra_simps)
  1819           by (auto simp add: algebra_simps)
  2030         moreover
  1820         moreover
  2043 
  1833 
  2044 lemma has_antiderivative_sequence:
  1834 lemma has_antiderivative_sequence:
  2045   fixes f :: "nat \<Rightarrow> 'a::real_normed_vector \<Rightarrow> 'b::banach"
  1835   fixes f :: "nat \<Rightarrow> 'a::real_normed_vector \<Rightarrow> 'b::banach"
  2046   assumes "convex S"
  1836   assumes "convex S"
  2047     and der: "\<And>n x. x \<in> S \<Longrightarrow> ((f n) has_derivative (f' n x)) (at x within S)"
  1837     and der: "\<And>n x. x \<in> S \<Longrightarrow> ((f n) has_derivative (f' n x)) (at x within S)"
  2048     and no: "\<And>e. e > 0 \<Longrightarrow> \<exists>N. \<forall>n\<ge>N. \<forall>x\<in>S. \<forall>h. norm (f' n x h - g' x h) \<le> e * norm h"
  1838     and no: "\<And>e. e > 0 \<Longrightarrow> \<forall>\<^sub>F n in sequentially.
       
  1839        \<forall>x\<in>S. \<forall>h. norm (f' n x h - g' x h) \<le> e * norm h"
  2049   shows "\<exists>g. \<forall>x\<in>S. (g has_derivative g' x) (at x within S)"
  1840   shows "\<exists>g. \<forall>x\<in>S. (g has_derivative g' x) (at x within S)"
  2050 proof (cases "S = {}")
  1841 proof (cases "S = {}")
  2051   case False
  1842   case False
  2052   then obtain a where "a \<in> S"
  1843   then obtain a where "a \<in> S"
  2053     by auto
  1844     by auto
  2056   show ?thesis
  1847   show ?thesis
  2057     apply (rule *)
  1848     apply (rule *)
  2058     apply (rule has_derivative_sequence [OF \<open>convex S\<close> _ no, of "\<lambda>n x. f n x + (f 0 a - f n a)"])
  1849     apply (rule has_derivative_sequence [OF \<open>convex S\<close> _ no, of "\<lambda>n x. f n x + (f 0 a - f n a)"])
  2059        apply (metis assms(2) has_derivative_add_const)
  1850        apply (metis assms(2) has_derivative_add_const)
  2060     using \<open>a \<in> S\<close> 
  1851     using \<open>a \<in> S\<close> 
  2061     apply auto
  1852       apply auto
  2062     done
  1853     done
  2063 qed auto
  1854 qed auto
  2064 
  1855 
  2065 lemma has_antiderivative_limit:
  1856 lemma has_antiderivative_limit:
  2066   fixes g' :: "'a::real_normed_vector \<Rightarrow> 'a \<Rightarrow> 'b::banach"
  1857   fixes g' :: "'a::real_normed_vector \<Rightarrow> 'a \<Rightarrow> 'b::banach"
  2085   proof (rule has_antiderivative_sequence[OF \<open>convex S\<close>, of f f'])
  1876   proof (rule has_antiderivative_sequence[OF \<open>convex S\<close>, of f f'])
  2086     fix e :: real
  1877     fix e :: real
  2087     assume "e > 0"
  1878     assume "e > 0"
  2088     obtain N where N: "inverse (real (Suc N)) < e"
  1879     obtain N where N: "inverse (real (Suc N)) < e"
  2089       using reals_Archimedean[OF \<open>e>0\<close>] ..
  1880       using reals_Archimedean[OF \<open>e>0\<close>] ..
  2090     show "\<exists>N. \<forall>n\<ge>N. \<forall>x\<in>S. \<forall>h. norm (f' n x h - g' x h) \<le> e * norm h"
  1881     show "\<forall>\<^sub>F n in sequentially. \<forall>x\<in>S.  \<forall>h. norm (f' n x h - g' x h) \<le> e * norm h"
       
  1882         unfolding eventually_sequentially
  2091     proof (intro exI allI ballI impI)
  1883     proof (intro exI allI ballI impI)
  2092       fix n x h
  1884       fix n x h
  2093       assume n: "N \<le> n" and x: "x \<in> S"
  1885       assume n: "N \<le> n" and x: "x \<in> S"
  2094       have *: "inverse (real (Suc n)) \<le> e"
  1886       have *: "inverse (real (Suc n)) \<le> e"
  2095         apply (rule order_trans[OF _ N[THEN less_imp_le]])
  1887         apply (rule order_trans[OF _ N[THEN less_imp_le]])
  2096         using n
  1888         using n apply (auto simp add: field_simps)
  2097         apply (auto simp add: field_simps)
       
  2098         done
  1889         done
  2099       show "norm (f' n x h - g' x h) \<le> e * norm h"
  1890       show "norm (f' n x h - g' x h) \<le> e * norm h"
  2100         by (meson "*" mult_right_mono norm_ge_zero order.trans x f')
  1891         by (meson "*" mult_right_mono norm_ge_zero order.trans x f')
  2101     qed
  1892     qed
  2102   qed (use f' in auto)
  1893   qed (use f' in auto)
  2107 
  1898 
  2108 lemma has_derivative_series:
  1899 lemma has_derivative_series:
  2109   fixes f :: "nat \<Rightarrow> 'a::real_normed_vector \<Rightarrow> 'b::banach"
  1900   fixes f :: "nat \<Rightarrow> 'a::real_normed_vector \<Rightarrow> 'b::banach"
  2110   assumes "convex S"
  1901   assumes "convex S"
  2111     and "\<And>n x. x \<in> S \<Longrightarrow> ((f n) has_derivative (f' n x)) (at x within S)"
  1902     and "\<And>n x. x \<in> S \<Longrightarrow> ((f n) has_derivative (f' n x)) (at x within S)"
  2112     and "\<And>e. e>0 \<Longrightarrow> \<exists>N. \<forall>n\<ge>N. \<forall>x\<in>S. \<forall>h. norm (sum (\<lambda>i. f' i x h) {..<n} - g' x h) \<le> e * norm h"
  1903     and "\<And>e. e>0 \<Longrightarrow> \<forall>\<^sub>F n in sequentially. \<forall>x\<in>S. \<forall>h. norm (sum (\<lambda>i. f' i x h) {..<n} - g' x h) \<le> e * norm h"
  2113     and "x \<in> S"
  1904     and "x \<in> S"
  2114     and "(\<lambda>n. f n x) sums l"
  1905     and "(\<lambda>n. f n x) sums l"
  2115   shows "\<exists>g. \<forall>x\<in>S. (\<lambda>n. f n x) sums (g x) \<and> (g has_derivative g' x) (at x within S)"
  1906   shows "\<exists>g. \<forall>x\<in>S. (\<lambda>n. f n x) sums (g x) \<and> (g has_derivative g' x) (at x within S)"
  2116   unfolding sums_def
  1907   unfolding sums_def
  2117   apply (rule has_derivative_sequence[OF assms(1) _ assms(3)])
  1908   apply (rule has_derivative_sequence[OF assms(1) _ assms(3)])
  2128   assumes "uniform_limit S (\<lambda>n x. \<Sum>i<n. f' i x) g' sequentially"
  1919   assumes "uniform_limit S (\<lambda>n x. \<Sum>i<n. f' i x) g' sequentially"
  2129   assumes "x0 \<in> S" "summable (\<lambda>n. f n x0)"
  1920   assumes "x0 \<in> S" "summable (\<lambda>n. f n x0)"
  2130   shows   "\<exists>g. \<forall>x\<in>S. (\<lambda>n. f n x) sums g x \<and> (g has_field_derivative g' x) (at x within S)"
  1921   shows   "\<exists>g. \<forall>x\<in>S. (\<lambda>n. f n x) sums g x \<and> (g has_field_derivative g' x) (at x within S)"
  2131 unfolding has_field_derivative_def
  1922 unfolding has_field_derivative_def
  2132 proof (rule has_derivative_series)
  1923 proof (rule has_derivative_series)
  2133   show "\<exists>N. \<forall>n\<ge>N. \<forall>x\<in>S. \<forall>h. norm ((\<Sum>i<n. f' i x * h) - g' x * h) \<le> e * norm h" if "e > 0" for e
  1924   show "\<forall>\<^sub>F n in sequentially.
       
  1925        \<forall>x\<in>S. \<forall>h. norm ((\<Sum>i<n. f' i x * h) - g' x * h) \<le> e * norm h" if "e > 0" for e
       
  1926     unfolding eventually_sequentially
  2134   proof -
  1927   proof -
  2135     from that assms(3) obtain N where N: "\<And>n x. n \<ge> N \<Longrightarrow> x \<in> S \<Longrightarrow> norm ((\<Sum>i<n. f' i x) - g' x) < e"
  1928     from that assms(3) obtain N where N: "\<And>n x. n \<ge> N \<Longrightarrow> x \<in> S \<Longrightarrow> norm ((\<Sum>i<n. f' i x) - g' x) < e"
  2136       unfolding uniform_limit_iff eventually_at_top_linorder dist_norm by blast
  1929       unfolding uniform_limit_iff eventually_at_top_linorder dist_norm by blast
  2137     {
  1930     {
  2138       fix n :: nat and x h :: 'a assume nx: "n \<ge> N" "x \<in> S"
  1931       fix n :: nat and x h :: 'a assume nx: "n \<ge> N" "x \<in> S"
  2215     and f': "(f has_vector_derivative f') (at x within S)"
  2008     and f': "(f has_vector_derivative f') (at x within S)"
  2216     and f'': "(f has_vector_derivative f'') (at x within S)"
  2009     and f'': "(f has_vector_derivative f'') (at x within S)"
  2217   shows "f' = f''"
  2010   shows "f' = f''"
  2218 proof -
  2011 proof -
  2219   have "(\<lambda>x. x *\<^sub>R f') = (\<lambda>x. x *\<^sub>R f'')"
  2012   have "(\<lambda>x. x *\<^sub>R f') = (\<lambda>x. x *\<^sub>R f'')"
  2220   proof (rule frechet_derivative_unique_within)
  2013   proof (rule frechet_derivative_unique_within, simp_all)
  2221     show "\<forall>i\<in>Basis. \<forall>e>0. \<exists>d. 0 < \<bar>d\<bar> \<and> \<bar>d\<bar> < e \<and> x + d *\<^sub>R i \<in> S"
  2014     show "\<exists>d. d \<noteq> 0 \<and> \<bar>d\<bar> < e \<and> x + d \<in> S" if "0 < e"  for e
  2222     proof clarsimp
  2015     proof -
  2223       fix e :: real assume "0 < e"
  2016       from that
  2224       with islimpt_approachable_real[of x S] not_bot
       
  2225       obtain x' where "x' \<in> S" "x' \<noteq> x" "\<bar>x' - x\<bar> < e"
  2017       obtain x' where "x' \<in> S" "x' \<noteq> x" "\<bar>x' - x\<bar> < e"
       
  2018         using islimpt_approachable_real[of x S] not_bot
  2226         by (auto simp add: trivial_limit_within)
  2019         by (auto simp add: trivial_limit_within)
  2227       then show "\<exists>d. d \<noteq> 0 \<and> \<bar>d\<bar> < e \<and> x + d \<in> S"
  2020       then show ?thesis
  2228         by (intro exI[of _ "x' - x"]) auto
  2021         using eq_iff_diff_eq_0 by fastforce
  2229     qed
  2022     qed
  2230   qed (insert f' f'', auto simp: has_vector_derivative_def)
  2023   qed (use f' f'' in \<open>auto simp: has_vector_derivative_def\<close>)
  2231   then show ?thesis
  2024   then show ?thesis
  2232     unfolding fun_eq_iff by (metis scaleR_one)
  2025     unfolding fun_eq_iff by (metis scaleR_one)
  2233 qed
  2026 qed
  2234 
  2027 
  2235 lemma vector_derivative_unique_at:
  2028 lemma vector_derivative_unique_at:
  2414             vector_derivative_works[THEN iffD1] differentiableI_vector)
  2207             vector_derivative_works[THEN iffD1] differentiableI_vector)
  2415      fact
  2208      fact
  2416 
  2209 
  2417 lemma vector_derivative_within_closed_interval:
  2210 lemma vector_derivative_within_closed_interval:
  2418   fixes f::"real \<Rightarrow> 'a::euclidean_space"
  2211   fixes f::"real \<Rightarrow> 'a::euclidean_space"
  2419   assumes "a < b" and "x \<in> {a .. b}"
  2212   assumes "a < b" and "x \<in> {a..b}"
  2420   assumes "(f has_vector_derivative f') (at x within {a .. b})"
  2213   assumes "(f has_vector_derivative f') (at x within {a..b})"
  2421   shows "vector_derivative f (at x within {a .. b}) = f'"
  2214   shows "vector_derivative f (at x within {a..b}) = f'"
  2422   using assms vector_derivative_within_cbox
  2215   using assms vector_derivative_within_cbox
  2423   by fastforce
  2216   by fastforce
  2424 
  2217 
  2425 lemma has_vector_derivative_within_subset:
  2218 lemma has_vector_derivative_within_subset:
  2426   "(f has_vector_derivative f') (at x within s) \<Longrightarrow> t \<subseteq> s \<Longrightarrow> (f has_vector_derivative f') (at x within t)"
  2219   "(f has_vector_derivative f') (at x within S) \<Longrightarrow> T \<subseteq> S \<Longrightarrow> (f has_vector_derivative f') (at x within T)"
  2427   by (auto simp: has_vector_derivative_def intro: has_derivative_within_subset)
  2220   by (auto simp: has_vector_derivative_def intro: has_derivative_within_subset)
  2428 
  2221 
  2429 lemma has_vector_derivative_at_within:
  2222 lemma has_vector_derivative_at_within:
  2430   "(f has_vector_derivative f') (at x) \<Longrightarrow> (f has_vector_derivative f') (at x within s)"
  2223   "(f has_vector_derivative f') (at x) \<Longrightarrow> (f has_vector_derivative f') (at x within S)"
  2431   unfolding has_vector_derivative_def
  2224   unfolding has_vector_derivative_def
  2432   by (rule has_derivative_at_withinI)
  2225   by (rule has_derivative_at_withinI)
  2433 
  2226 
  2434 lemma has_vector_derivative_weaken:
  2227 lemma has_vector_derivative_weaken:
  2435   fixes x D and f g s t
  2228   fixes x D and f g S T
  2436   assumes f: "(f has_vector_derivative D) (at x within t)"
  2229   assumes f: "(f has_vector_derivative D) (at x within T)"
  2437     and "x \<in> s" "s \<subseteq> t"
  2230     and "x \<in> S" "S \<subseteq> T"
  2438     and "\<And>x. x \<in> s \<Longrightarrow> f x = g x"
  2231     and "\<And>x. x \<in> S \<Longrightarrow> f x = g x"
  2439   shows "(g has_vector_derivative D) (at x within s)"
  2232   shows "(g has_vector_derivative D) (at x within S)"
  2440 proof -
  2233 proof -
  2441   have "(f has_vector_derivative D) (at x within s) \<longleftrightarrow> (g has_vector_derivative D) (at x within s)"
  2234   have "(f has_vector_derivative D) (at x within S) \<longleftrightarrow> (g has_vector_derivative D) (at x within S)"
  2442     unfolding has_vector_derivative_def has_derivative_iff_norm
  2235     unfolding has_vector_derivative_def has_derivative_iff_norm
  2443     using assms by (intro conj_cong Lim_cong_within refl) auto
  2236     using assms by (intro conj_cong Lim_cong_within refl) auto
  2444   then show ?thesis
  2237   then show ?thesis
  2445     using has_vector_derivative_within_subset[OF f \<open>s \<subseteq> t\<close>] by simp
  2238     using has_vector_derivative_within_subset[OF f \<open>S \<subseteq> T\<close>] by simp
  2446 qed
  2239 qed
  2447 
  2240 
  2448 lemma has_vector_derivative_transform_within:
  2241 lemma has_vector_derivative_transform_within:
  2449   assumes "(f has_vector_derivative f') (at x within s)"
  2242   assumes "(f has_vector_derivative f') (at x within S)"
  2450     and "0 < d"
  2243     and "0 < d"
  2451     and "x \<in> s"
  2244     and "x \<in> S"
  2452     and "\<And>x'. \<lbrakk>x'\<in>s; dist x' x < d\<rbrakk> \<Longrightarrow> f x' = g x'"
  2245     and "\<And>x'. \<lbrakk>x'\<in>S; dist x' x < d\<rbrakk> \<Longrightarrow> f x' = g x'"
  2453     shows "(g has_vector_derivative f') (at x within s)"
  2246     shows "(g has_vector_derivative f') (at x within S)"
  2454   using assms
  2247   using assms
  2455   unfolding has_vector_derivative_def
  2248   unfolding has_vector_derivative_def
  2456   by (rule has_derivative_transform_within)
  2249   by (rule has_derivative_transform_within)
  2457 
  2250 
  2458 lemma has_vector_derivative_transform_within_open:
  2251 lemma has_vector_derivative_transform_within_open:
  2459   assumes "(f has_vector_derivative f') (at x)"
  2252   assumes "(f has_vector_derivative f') (at x)"
  2460     and "open s"
  2253     and "open S"
  2461     and "x \<in> s"
  2254     and "x \<in> S"
  2462     and "\<And>y. y\<in>s \<Longrightarrow> f y = g y"
  2255     and "\<And>y. y\<in>S \<Longrightarrow> f y = g y"
  2463   shows "(g has_vector_derivative f') (at x)"
  2256   shows "(g has_vector_derivative f') (at x)"
  2464   using assms
  2257   using assms
  2465   unfolding has_vector_derivative_def
  2258   unfolding has_vector_derivative_def
  2466   by (rule has_derivative_transform_within_open)
  2259   by (rule has_derivative_transform_within_open)
  2467 
  2260 
  2468 lemma has_vector_derivative_transform:
  2261 lemma has_vector_derivative_transform:
  2469   assumes "x \<in> s" "\<And>x. x \<in> s \<Longrightarrow> g x = f x"
  2262   assumes "x \<in> S" "\<And>x. x \<in> S \<Longrightarrow> g x = f x"
  2470   assumes f': "(f has_vector_derivative f') (at x within s)"
  2263   assumes f': "(f has_vector_derivative f') (at x within S)"
  2471   shows "(g has_vector_derivative f') (at x within s)"
  2264   shows "(g has_vector_derivative f') (at x within S)"
  2472   using assms
  2265   using assms
  2473   unfolding has_vector_derivative_def
  2266   unfolding has_vector_derivative_def
  2474   by (rule has_derivative_transform)
  2267   by (rule has_derivative_transform)
  2475 
  2268 
  2476 lemma vector_diff_chain_at:
  2269 lemma vector_diff_chain_at:
  2477   assumes "(f has_vector_derivative f') (at x)"
  2270   assumes "(f has_vector_derivative f') (at x)"
  2478     and "(g has_vector_derivative g') (at (f x))"
  2271     and "(g has_vector_derivative g') (at (f x))"
  2479   shows "((g \<circ> f) has_vector_derivative (f' *\<^sub>R g')) (at x)"
  2272   shows "((g \<circ> f) has_vector_derivative (f' *\<^sub>R g')) (at x)"
  2480   using assms(2)
  2273   using assms has_vector_derivative_at_within has_vector_derivative_def vector_derivative_diff_chain_within by blast
  2481   unfolding has_vector_derivative_def
       
  2482   apply -
       
  2483   apply (drule diff_chain_at[OF assms(1)[unfolded has_vector_derivative_def]])
       
  2484   apply (simp only: o_def real_scaleR_def scaleR_scaleR)
       
  2485   done
       
  2486 
  2274 
  2487 lemma vector_diff_chain_within:
  2275 lemma vector_diff_chain_within:
  2488   assumes "(f has_vector_derivative f') (at x within s)"
  2276   assumes "(f has_vector_derivative f') (at x within s)"
  2489     and "(g has_vector_derivative g') (at (f x) within f ` s)"
  2277     and "(g has_vector_derivative g') (at (f x) within f ` s)"
  2490   shows "((g \<circ> f) has_vector_derivative (f' *\<^sub>R g')) (at x within s)"
  2278   shows "((g \<circ> f) has_vector_derivative (f' *\<^sub>R g')) (at x within s)"
  2491   using assms(2)
  2279   using assms has_vector_derivative_def vector_derivative_diff_chain_within by blast
  2492   unfolding has_vector_derivative_def
       
  2493   apply -
       
  2494   apply (drule diff_chain_within[OF assms(1)[unfolded has_vector_derivative_def]])
       
  2495   apply (simp only: o_def real_scaleR_def scaleR_scaleR)
       
  2496   done
       
  2497 
  2280 
  2498 lemma vector_derivative_const_at [simp]: "vector_derivative (\<lambda>x. c) (at a) = 0"
  2281 lemma vector_derivative_const_at [simp]: "vector_derivative (\<lambda>x. c) (at a) = 0"
  2499   by (simp add: vector_derivative_at)
  2282   by (simp add: vector_derivative_at)
  2500 
  2283 
  2501 lemma vector_derivative_at_within_ivl:
  2284 lemma vector_derivative_at_within_ivl:
  2516 using diff_chain_at[OF Df[unfolded has_vector_derivative_def]
  2299 using diff_chain_at[OF Df[unfolded has_vector_derivative_def]
  2517                        Dg [unfolded has_field_derivative_def]]
  2300                        Dg [unfolded has_field_derivative_def]]
  2518  by (auto simp: o_def mult.commute has_vector_derivative_def)
  2301  by (auto simp: o_def mult.commute has_vector_derivative_def)
  2519 
  2302 
  2520 lemma vector_derivative_chain_within: 
  2303 lemma vector_derivative_chain_within: 
  2521   assumes "at x within s \<noteq> bot" "f differentiable (at x within s)" 
  2304   assumes "at x within S \<noteq> bot" "f differentiable (at x within S)" 
  2522     "(g has_derivative g') (at (f x) within f ` s)" 
  2305     "(g has_derivative g') (at (f x) within f ` S)" 
  2523   shows "vector_derivative (g \<circ> f) (at x within s) =
  2306   shows "vector_derivative (g \<circ> f) (at x within S) =
  2524         g' (vector_derivative f (at x within s)) "
  2307         g' (vector_derivative f (at x within S)) "
  2525   apply (rule vector_derivative_within [OF \<open>at x within s \<noteq> bot\<close>])
  2308   apply (rule vector_derivative_within [OF \<open>at x within S \<noteq> bot\<close>])
  2526   apply (rule vector_derivative_diff_chain_within)
  2309   apply (rule vector_derivative_diff_chain_within)
  2527   using assms(2-3) vector_derivative_works
  2310   using assms(2-3) vector_derivative_works
  2528   by auto
  2311   by auto
  2529 
  2312 
  2530 subsection\<open>The notion of being field differentiable\<close>
  2313 subsection\<open>The notion of being field differentiable\<close>
  2541 lemma field_differentiable_derivI:
  2324 lemma field_differentiable_derivI:
  2542     "f field_differentiable (at x) \<Longrightarrow> (f has_field_derivative deriv f x) (at x)"
  2325     "f field_differentiable (at x) \<Longrightarrow> (f has_field_derivative deriv f x) (at x)"
  2543 by (simp add: field_differentiable_def DERIV_deriv_iff_has_field_derivative)
  2326 by (simp add: field_differentiable_def DERIV_deriv_iff_has_field_derivative)
  2544 
  2327 
  2545 lemma field_differentiable_imp_continuous_at:
  2328 lemma field_differentiable_imp_continuous_at:
  2546     "f field_differentiable (at x within s) \<Longrightarrow> continuous (at x within s) f"
  2329     "f field_differentiable (at x within S) \<Longrightarrow> continuous (at x within S) f"
  2547   by (metis DERIV_continuous field_differentiable_def)
  2330   by (metis DERIV_continuous field_differentiable_def)
  2548 
  2331 
  2549 lemma field_differentiable_within_subset:
  2332 lemma field_differentiable_within_subset:
  2550     "\<lbrakk>f field_differentiable (at x within s); t \<subseteq> s\<rbrakk>
  2333     "\<lbrakk>f field_differentiable (at x within S); T \<subseteq> S\<rbrakk> \<Longrightarrow> f field_differentiable (at x within T)"
  2551      \<Longrightarrow> f field_differentiable (at x within t)"
       
  2552   by (metis DERIV_subset field_differentiable_def)
  2334   by (metis DERIV_subset field_differentiable_def)
  2553 
  2335 
  2554 lemma field_differentiable_at_within:
  2336 lemma field_differentiable_at_within:
  2555     "\<lbrakk>f field_differentiable (at x)\<rbrakk>
  2337     "\<lbrakk>f field_differentiable (at x)\<rbrakk>
  2556      \<Longrightarrow> f field_differentiable (at x within s)"
  2338      \<Longrightarrow> f field_differentiable (at x within S)"
  2557   unfolding field_differentiable_def
  2339   unfolding field_differentiable_def
  2558   by (metis DERIV_subset top_greatest)
  2340   by (metis DERIV_subset top_greatest)
  2559 
  2341 
  2560 lemma field_differentiable_linear [simp,derivative_intros]: "(( * ) c) field_differentiable F"
  2342 lemma field_differentiable_linear [simp,derivative_intros]: "(( * ) c) field_differentiable F"
  2561 proof -
  2343   unfolding field_differentiable_def has_field_derivative_def mult_commute_abs
  2562   show ?thesis
  2344   by (force intro: has_derivative_mult_right)
  2563     unfolding field_differentiable_def has_field_derivative_def mult_commute_abs
       
  2564     by (force intro: has_derivative_mult_right)
       
  2565 qed
       
  2566 
  2345 
  2567 lemma field_differentiable_const [simp,derivative_intros]: "(\<lambda>z. c) field_differentiable F"
  2346 lemma field_differentiable_const [simp,derivative_intros]: "(\<lambda>z. c) field_differentiable F"
  2568   unfolding field_differentiable_def has_field_derivative_def
  2347   unfolding field_differentiable_def has_field_derivative_def
  2569   using DERIV_const has_field_derivative_imp_has_derivative by blast
  2348   using DERIV_const has_field_derivative_imp_has_derivative by blast
  2570 
  2349 
  2600     shows "(\<lambda>z. f z - g z) field_differentiable F"
  2379     shows "(\<lambda>z. f z - g z) field_differentiable F"
  2601   using assms unfolding field_differentiable_def
  2380   using assms unfolding field_differentiable_def
  2602   by (metis field_differentiable_diff)
  2381   by (metis field_differentiable_diff)
  2603 
  2382 
  2604 lemma field_differentiable_inverse [derivative_intros]:
  2383 lemma field_differentiable_inverse [derivative_intros]:
  2605   assumes "f field_differentiable (at a within s)" "f a \<noteq> 0"
  2384   assumes "f field_differentiable (at a within S)" "f a \<noteq> 0"
  2606   shows "(\<lambda>z. inverse (f z)) field_differentiable (at a within s)"
  2385   shows "(\<lambda>z. inverse (f z)) field_differentiable (at a within S)"
  2607   using assms unfolding field_differentiable_def
  2386   using assms unfolding field_differentiable_def
  2608   by (metis DERIV_inverse_fun)
  2387   by (metis DERIV_inverse_fun)
  2609 
  2388 
  2610 lemma field_differentiable_mult [derivative_intros]:
  2389 lemma field_differentiable_mult [derivative_intros]:
  2611   assumes "f field_differentiable (at a within s)"
  2390   assumes "f field_differentiable (at a within S)"
  2612           "g field_differentiable (at a within s)"
  2391           "g field_differentiable (at a within S)"
  2613     shows "(\<lambda>z. f z * g z) field_differentiable (at a within s)"
  2392     shows "(\<lambda>z. f z * g z) field_differentiable (at a within S)"
  2614   using assms unfolding field_differentiable_def
  2393   using assms unfolding field_differentiable_def
  2615   by (metis DERIV_mult [of f _ a s g])
  2394   by (metis DERIV_mult [of f _ a S g])
  2616 
  2395 
  2617 lemma field_differentiable_divide [derivative_intros]:
  2396 lemma field_differentiable_divide [derivative_intros]:
  2618   assumes "f field_differentiable (at a within s)"
  2397   assumes "f field_differentiable (at a within S)"
  2619           "g field_differentiable (at a within s)"
  2398           "g field_differentiable (at a within S)"
  2620           "g a \<noteq> 0"
  2399           "g a \<noteq> 0"
  2621     shows "(\<lambda>z. f z / g z) field_differentiable (at a within s)"
  2400     shows "(\<lambda>z. f z / g z) field_differentiable (at a within S)"
  2622   using assms unfolding field_differentiable_def
  2401   using assms unfolding field_differentiable_def
  2623   by (metis DERIV_divide [of f _ a s g])
  2402   by (metis DERIV_divide [of f _ a S g])
  2624 
  2403 
  2625 lemma field_differentiable_power [derivative_intros]:
  2404 lemma field_differentiable_power [derivative_intros]:
  2626   assumes "f field_differentiable (at a within s)"
  2405   assumes "f field_differentiable (at a within S)"
  2627     shows "(\<lambda>z. f z ^ n) field_differentiable (at a within s)"
  2406     shows "(\<lambda>z. f z ^ n) field_differentiable (at a within S)"
  2628   using assms unfolding field_differentiable_def
  2407   using assms unfolding field_differentiable_def
  2629   by (metis DERIV_power)
  2408   by (metis DERIV_power)
  2630 
  2409 
  2631 lemma field_differentiable_transform_within:
  2410 lemma field_differentiable_transform_within:
  2632   "0 < d \<Longrightarrow>
  2411   "0 < d \<Longrightarrow>
  2633         x \<in> s \<Longrightarrow>
  2412         x \<in> S \<Longrightarrow>
  2634         (\<And>x'. x' \<in> s \<Longrightarrow> dist x' x < d \<Longrightarrow> f x' = g x') \<Longrightarrow>
  2413         (\<And>x'. x' \<in> S \<Longrightarrow> dist x' x < d \<Longrightarrow> f x' = g x') \<Longrightarrow>
  2635         f field_differentiable (at x within s)
  2414         f field_differentiable (at x within S)
  2636         \<Longrightarrow> g field_differentiable (at x within s)"
  2415         \<Longrightarrow> g field_differentiable (at x within S)"
  2637   unfolding field_differentiable_def has_field_derivative_def
  2416   unfolding field_differentiable_def has_field_derivative_def
  2638   by (blast intro: has_derivative_transform_within)
  2417   by (blast intro: has_derivative_transform_within)
  2639 
  2418 
  2640 lemma field_differentiable_compose_within:
  2419 lemma field_differentiable_compose_within:
  2641   assumes "f field_differentiable (at a within s)"
  2420   assumes "f field_differentiable (at a within S)"
  2642           "g field_differentiable (at (f a) within f`s)"
  2421           "g field_differentiable (at (f a) within f`S)"
  2643     shows "(g o f) field_differentiable (at a within s)"
  2422     shows "(g o f) field_differentiable (at a within S)"
  2644   using assms unfolding field_differentiable_def
  2423   using assms unfolding field_differentiable_def
  2645   by (metis DERIV_image_chain)
  2424   by (metis DERIV_image_chain)
  2646 
  2425 
  2647 lemma field_differentiable_compose:
  2426 lemma field_differentiable_compose:
  2648   "f field_differentiable at z \<Longrightarrow> g field_differentiable at (f z)
  2427   "f field_differentiable at z \<Longrightarrow> g field_differentiable at (f z)
  2649           \<Longrightarrow> (g o f) field_differentiable at z"
  2428           \<Longrightarrow> (g o f) field_differentiable at z"
  2650 by (metis field_differentiable_at_within field_differentiable_compose_within)
  2429 by (metis field_differentiable_at_within field_differentiable_compose_within)
  2651 
  2430 
  2652 lemma field_differentiable_within_open:
  2431 lemma field_differentiable_within_open:
  2653      "\<lbrakk>a \<in> s; open s\<rbrakk> \<Longrightarrow> f field_differentiable at a within s \<longleftrightarrow>
  2432      "\<lbrakk>a \<in> S; open S\<rbrakk> \<Longrightarrow> f field_differentiable at a within S \<longleftrightarrow>
  2654                           f field_differentiable at a"
  2433                           f field_differentiable at a"
  2655   unfolding field_differentiable_def
  2434   unfolding field_differentiable_def
  2656   by (metis at_within_open)
  2435   by (metis at_within_open)
  2657 
  2436 
  2658 lemma vector_derivative_chain_at_general: 
  2437 lemma vector_derivative_chain_at_general: 
  2690     by (rule Lim_eventually) (simp add: eventually_at_filter)
  2469     by (rule Lim_eventually) (simp add: eventually_at_filter)
  2691   have "((\<lambda>y. ((y - t) / abs (y - t)) *\<^sub>R ((\<Sum>n. ?e n y) - A)) \<longlongrightarrow> 0) (at t within T)"
  2470   have "((\<lambda>y. ((y - t) / abs (y - t)) *\<^sub>R ((\<Sum>n. ?e n y) - A)) \<longlongrightarrow> 0) (at t within T)"
  2692     unfolding *
  2471     unfolding *
  2693     by (rule tendsto_norm_zero_cancel) (auto intro!: tendsto_eq_intros)
  2472     by (rule tendsto_norm_zero_cancel) (auto intro!: tendsto_eq_intros)
  2694 
  2473 
  2695   moreover
  2474   moreover have "\<forall>\<^sub>F x in at t within T. x \<noteq> t"
  2696 
       
  2697   have "\<forall>\<^sub>F x in at t within T. x \<noteq> t"
       
  2698     by (simp add: eventually_at_filter)
  2475     by (simp add: eventually_at_filter)
  2699   then have "\<forall>\<^sub>F x in at t within T. ((x - t) / \<bar>x - t\<bar>) *\<^sub>R ((\<Sum>n. ?e n x) - A) =
  2476   then have "\<forall>\<^sub>F x in at t within T. ((x - t) / \<bar>x - t\<bar>) *\<^sub>R ((\<Sum>n. ?e n x) - A) =
  2700     (exp ((x - t) *\<^sub>R A) - 1 - (x - t) *\<^sub>R A) /\<^sub>R norm (x - t)"
  2477     (exp ((x - t) *\<^sub>R A) - 1 - (x - t) *\<^sub>R A) /\<^sub>R norm (x - t)"
  2701   proof eventually_elim
  2478   proof eventually_elim
  2702     case (elim x)
  2479     case (elim x)
  2719       by (simp add: algebra_simps)
  2496       by (simp add: algebra_simps)
  2720     finally show ?case
  2497     finally show ?case
  2721       by (simp add: divide_simps)
  2498       by (simp add: divide_simps)
  2722   qed
  2499   qed
  2723 
  2500 
  2724   ultimately
  2501   ultimately have "((\<lambda>y. (exp ((y - t) *\<^sub>R A) - 1 - (y - t) *\<^sub>R A) /\<^sub>R norm (y - t)) \<longlongrightarrow> 0) (at t within T)"
  2725 
       
  2726   have "((\<lambda>y. (exp ((y - t) *\<^sub>R A) - 1 - (y - t) *\<^sub>R A) /\<^sub>R norm (y - t)) \<longlongrightarrow> 0) (at t within T)"
       
  2727     by (rule Lim_transform_eventually[rotated])
  2502     by (rule Lim_transform_eventually[rotated])
  2728   from tendsto_mult_right_zero[OF this, where c="exp (t *\<^sub>R A)"]
  2503   from tendsto_mult_right_zero[OF this, where c="exp (t *\<^sub>R A)"]
  2729   show "((\<lambda>y. (exp (y *\<^sub>R A) - exp (t *\<^sub>R A) - (y - t) *\<^sub>R (exp (t *\<^sub>R A) * A)) /\<^sub>R norm (y - t)) \<longlongrightarrow> 0)
  2504   show "((\<lambda>y. (exp (y *\<^sub>R A) - exp (t *\<^sub>R A) - (y - t) *\<^sub>R (exp (t *\<^sub>R A) * A)) /\<^sub>R norm (y - t)) \<longlongrightarrow> 0)
  2730       (at t within T)"
  2505       (at t within T)"
  2731     by (rule Lim_transform_eventually[rotated])
  2506     by (rule Lim_transform_eventually[rotated])
  2754   let ?A' = "interior A \<inter> {c<..}"
  2529   let ?A' = "interior A \<inter> {c<..}"
  2755   from c have "c \<in> interior A \<inter> closure {c<..}" by auto
  2530   from c have "c \<in> interior A \<inter> closure {c<..}" by auto
  2756   also have "\<dots> \<subseteq> closure (interior A \<inter> {c<..})" by (intro open_Int_closure_subset) auto
  2531   also have "\<dots> \<subseteq> closure (interior A \<inter> {c<..})" by (intro open_Int_closure_subset) auto
  2757   finally have "at c within ?A' \<noteq> bot" by (subst at_within_eq_bot_iff) auto
  2532   finally have "at c within ?A' \<noteq> bot" by (subst at_within_eq_bot_iff) auto
  2758   moreover from deriv have "((\<lambda>y. (f y - f c) / (y - c)) \<longlongrightarrow> f') (at c within ?A')"
  2533   moreover from deriv have "((\<lambda>y. (f y - f c) / (y - c)) \<longlongrightarrow> f') (at c within ?A')"
  2759     unfolding DERIV_within_iff using interior_subset[of A] by (blast intro: tendsto_mono at_le)
  2534     unfolding has_field_derivative_iff using interior_subset[of A] by (blast intro: tendsto_mono at_le)
  2760   moreover from eventually_at_right_real[OF xc]
  2535   moreover from eventually_at_right_real[OF xc]
  2761     have "eventually (\<lambda>y. (f y - f c) / (y - c) \<le> (f x - f c) / (x - c)) (at_right c)"
  2536     have "eventually (\<lambda>y. (f y - f c) / (y - c) \<le> (f x - f c) / (x - c)) (at_right c)"
  2762   proof eventually_elim
  2537   proof eventually_elim
  2763     fix y assume y: "y \<in> {c<..<x}"
  2538     fix y assume y: "y \<in> {c<..<x}"
  2764     with convex connected x c have "f y \<le> (f x - f c) / (x - c) * (y - c) + f c"
  2539     with convex connected x c have "f y \<le> (f x - f c) / (x - c) * (y - c) + f c"
  2776   let ?A' = "interior A \<inter> {..<c}"
  2551   let ?A' = "interior A \<inter> {..<c}"
  2777   from c have "c \<in> interior A \<inter> closure {..<c}" by auto
  2552   from c have "c \<in> interior A \<inter> closure {..<c}" by auto
  2778   also have "\<dots> \<subseteq> closure (interior A \<inter> {..<c})" by (intro open_Int_closure_subset) auto
  2553   also have "\<dots> \<subseteq> closure (interior A \<inter> {..<c})" by (intro open_Int_closure_subset) auto
  2779   finally have "at c within ?A' \<noteq> bot" by (subst at_within_eq_bot_iff) auto
  2554   finally have "at c within ?A' \<noteq> bot" by (subst at_within_eq_bot_iff) auto
  2780   moreover from deriv have "((\<lambda>y. (f y - f c) / (y - c)) \<longlongrightarrow> f') (at c within ?A')"
  2555   moreover from deriv have "((\<lambda>y. (f y - f c) / (y - c)) \<longlongrightarrow> f') (at c within ?A')"
  2781     unfolding DERIV_within_iff using interior_subset[of A] by (blast intro: tendsto_mono at_le)
  2556     unfolding has_field_derivative_iff using interior_subset[of A] by (blast intro: tendsto_mono at_le)
  2782   moreover from eventually_at_left_real[OF xc]
  2557   moreover from eventually_at_left_real[OF xc]
  2783     have "eventually (\<lambda>y. (f y - f c) / (y - c) \<ge> (f x - f c) / (x - c)) (at_left c)"
  2558     have "eventually (\<lambda>y. (f y - f c) / (y - c) \<ge> (f x - f c) / (x - c)) (at_left c)"
  2784   proof eventually_elim
  2559   proof eventually_elim
  2785     fix y assume y: "y \<in> {x<..<c}"
  2560     fix y assume y: "y \<in> {x<..<c}"
  2786     with convex connected x c have "f y \<le> (f x - f c) / (c - x) * (c - y) + f c"
  2561     with convex connected x c have "f y \<le> (f x - f c) / (c - x) * (c - y) + f c"
  2814     by (auto intro!: exI[where x="S \<times> UNIV"] S open_Times)
  2589     by (auto intro!: exI[where x="S \<times> UNIV"] S open_Times)
  2815 qed
  2590 qed
  2816 
  2591 
  2817 lemma eventually_at_Pair_within_TimesI2:
  2592 lemma eventually_at_Pair_within_TimesI2:
  2818   fixes x::"'a::metric_space"
  2593   fixes x::"'a::metric_space"
  2819   assumes "\<forall>\<^sub>F y' in at y within Y. P y'"
  2594   assumes "\<forall>\<^sub>F y' in at y within Y. P y'" "P y"
  2820   assumes "P y"
       
  2821   shows "\<forall>\<^sub>F (x', y') in at (x, y) within X \<times> Y. P y'"
  2595   shows "\<forall>\<^sub>F (x', y') in at (x, y) within X \<times> Y. P y'"
  2822 proof -
  2596 proof -
  2823   from assms[unfolded eventually_at_topological]
  2597   from assms[unfolded eventually_at_topological]
  2824   obtain S where S: "open S" "y \<in> S" "\<And>y'. y' \<in> Y \<Longrightarrow> y' \<in> S \<Longrightarrow> P y'"
  2598   obtain S where S: "open S" "y \<in> S" "\<And>y'. y' \<in> Y \<Longrightarrow> y' \<in> S \<Longrightarrow> P y'"
  2825     by metis
  2599     by metis
  2905         by (auto simp: closed_segment_def algebra_simps intro!: exI[where x=t])
  2679         by (auto simp: closed_segment_def algebra_simps intro!: exI[where x=t])
  2906       also
  2680       also
  2907       have "\<dots> \<subseteq> ball y d \<inter> Y"
  2681       have "\<dots> \<subseteq> ball y d \<inter> Y"
  2908         using \<open>y \<in> Y\<close> \<open>0 < d\<close> dy y'
  2682         using \<open>y \<in> Y\<close> \<open>0 < d\<close> dy y'
  2909         by (intro \<open>convex ?S\<close>[unfolded convex_contains_segment, rule_format, of y y'])
  2683         by (intro \<open>convex ?S\<close>[unfolded convex_contains_segment, rule_format, of y y'])
  2910           (auto simp: dist_commute mem_ball)
  2684           (auto simp: dist_commute)
  2911       finally have "y + t *\<^sub>R (y' - y) \<in> ?S" .
  2685       finally have "y + t *\<^sub>R (y' - y) \<in> ?S" .
  2912     } note seg = this
  2686     } note seg = this
  2913 
  2687 
  2914     have "\<forall>x\<in>ball y d \<inter> Y. onorm (blinfun_apply (fy x' x) - blinfun_apply (fy x' y)) \<le> e + e"
  2688     have "\<And>x. x \<in> ball y d \<inter> Y \<Longrightarrow> onorm (blinfun_apply (fy x' x) - blinfun_apply (fy x' y)) \<le> e + e"
  2915       by (safe intro!: onorm less_imp_le \<open>x' \<in> X\<close> dx) (auto simp: mem_ball dist_commute \<open>0 < d\<close> \<open>y \<in> Y\<close>)
  2689       by (safe intro!: onorm less_imp_le \<open>x' \<in> X\<close> dx) (auto simp: dist_commute \<open>0 < d\<close> \<open>y \<in> Y\<close>)
  2916     with seg has_derivative_within_subset[OF assms(2)[OF \<open>x' \<in> X\<close>]]
  2690     with seg has_derivative_within_subset[OF assms(2)[OF \<open>x' \<in> X\<close>]]
  2917     show "norm (f x' y' - f x' y - (fy x' y) (y' - y)) \<le> norm (y' - y) * (e + e)"
  2691     show "norm (f x' y' - f x' y - (fy x' y) (y' - y)) \<le> norm (y' - y) * (e + e)"
  2918       by (rule differentiable_bound_linearization[where S="?S"])
  2692       by (rule differentiable_bound_linearization[where S="?S"])
  2919         (auto intro!: \<open>0 < d\<close> \<open>y \<in> Y\<close>)
  2693         (auto intro!: \<open>0 < d\<close> \<open>y \<in> Y\<close>)
  2920   qed
  2694   qed
  2921   moreover
  2695   moreover
  2922   let ?le = "\<lambda>x'. norm (f x' y - f x y - (fx) (x' - x)) \<le> norm (x' - x) * e"
  2696   let ?le = "\<lambda>x'. norm (f x' y - f x y - (fx) (x' - x)) \<le> norm (x' - x) * e"
  2923   from fx[unfolded has_derivative_within, THEN conjunct2, THEN tendstoD, OF \<open>0 < e\<close>]
  2697   from fx[unfolded has_derivative_within, THEN conjunct2, THEN tendstoD, OF \<open>0 < e\<close>]
  2924   have "\<forall>\<^sub>F x' in at x within X. ?le x'"
  2698   have "\<forall>\<^sub>F x' in at x within X. ?le x'"
  2925     by eventually_elim
  2699     by eventually_elim
  2926        (auto simp: dist_norm divide_simps blinfun.bilinear_simps field_simps fx.zero split: if_split_asm)
  2700        (auto simp: dist_norm divide_simps blinfun.bilinear_simps field_simps split: if_split_asm)
  2927   then have "\<forall>\<^sub>F (x', y') in at (x, y) within X \<times> Y. ?le x'"
  2701   then have "\<forall>\<^sub>F (x', y') in at (x, y) within X \<times> Y. ?le x'"
  2928     by (rule eventually_at_Pair_within_TimesI1)
  2702     by (rule eventually_at_Pair_within_TimesI1)
  2929        (simp add: blinfun.bilinear_simps fx.zero)
  2703        (simp add: blinfun.bilinear_simps)
  2930   moreover have "\<forall>\<^sub>F (x', y') in at (x, y) within X \<times> Y. norm ((x', y') - (x, y)) \<noteq> 0"
  2704   moreover have "\<forall>\<^sub>F (x', y') in at (x, y) within X \<times> Y. norm ((x', y') - (x, y)) \<noteq> 0"
  2931     unfolding norm_eq_zero right_minus_eq
  2705     unfolding norm_eq_zero right_minus_eq
  2932     by (auto simp: eventually_at intro!: zero_less_one)
  2706     by (auto simp: eventually_at intro!: zero_less_one)
  2933   moreover
  2707   moreover
  2934   from fy_cont[THEN tendstoD, OF \<open>0 < e\<close>]
  2708   from fy_cont[THEN tendstoD, OF \<open>0 < e\<close>]
  2994 
  2768 
  2995 
  2769 
  2996 subsection \<open>Differentiable case distinction\<close>
  2770 subsection \<open>Differentiable case distinction\<close>
  2997 
  2771 
  2998 lemma has_derivative_within_If_eq:
  2772 lemma has_derivative_within_If_eq:
  2999   "((\<lambda>x. if P x then f x else g x) has_derivative f') (at x within s) =
  2773   "((\<lambda>x. if P x then f x else g x) has_derivative f') (at x within S) =
  3000     (bounded_linear f' \<and>
  2774     (bounded_linear f' \<and>
  3001      ((\<lambda>y.(if P y then (f y - ((if P x then f x else g x) + f' (y - x)))/\<^sub>R norm (y - x)
  2775      ((\<lambda>y.(if P y then (f y - ((if P x then f x else g x) + f' (y - x)))/\<^sub>R norm (y - x)
  3002            else (g y - ((if P x then f x else g x) + f' (y - x)))/\<^sub>R norm (y - x)))
  2776            else (g y - ((if P x then f x else g x) + f' (y - x)))/\<^sub>R norm (y - x)))
  3003       \<longlongrightarrow> 0) (at x within s))"
  2777       \<longlongrightarrow> 0) (at x within S))"
  3004   (is "_ = (_ \<and> (?if \<longlongrightarrow> 0) _)")
  2778   (is "_ = (_ \<and> (?if \<longlongrightarrow> 0) _)")
  3005 proof -
  2779 proof -
  3006   have "(\<lambda>y. (1 / norm (y - x)) *\<^sub>R
  2780   have "(\<lambda>y. (1 / norm (y - x)) *\<^sub>R
  3007            ((if P y then f y else g y) -
  2781            ((if P y then f y else g y) -
  3008             ((if P x then f x else g x) + f' (y - x)))) = ?if"
  2782             ((if P x then f x else g x) + f' (y - x)))) = ?if"
  3009     by (auto simp: inverse_eq_divide)
  2783     by (auto simp: inverse_eq_divide)
  3010   thus ?thesis by (auto simp: has_derivative_within)
  2784   thus ?thesis by (auto simp: has_derivative_within)
  3011 qed
  2785 qed
  3012 
  2786 
  3013 lemma has_derivative_If_within_closures:
  2787 lemma has_derivative_If_within_closures:
  3014   assumes f': "x \<in> s \<union> (closure s \<inter> closure t) \<Longrightarrow>
  2788   assumes f': "x \<in> S \<union> (closure S \<inter> closure T) \<Longrightarrow>
  3015     (f has_derivative f' x) (at x within s \<union> (closure s \<inter> closure t))"
  2789     (f has_derivative f' x) (at x within S \<union> (closure S \<inter> closure T))"
  3016   assumes g': "x \<in> t \<union> (closure s \<inter> closure t) \<Longrightarrow>
  2790   assumes g': "x \<in> T \<union> (closure S \<inter> closure T) \<Longrightarrow>
  3017     (g has_derivative g' x) (at x within t \<union> (closure s \<inter> closure t))"
  2791     (g has_derivative g' x) (at x within T \<union> (closure S \<inter> closure T))"
  3018   assumes connect: "x \<in> closure s \<Longrightarrow> x \<in> closure t \<Longrightarrow> f x = g x"
  2792   assumes connect: "x \<in> closure S \<Longrightarrow> x \<in> closure T \<Longrightarrow> f x = g x"
  3019   assumes connect': "x \<in> closure s \<Longrightarrow> x \<in> closure t \<Longrightarrow> f' x = g' x"
  2793   assumes connect': "x \<in> closure S \<Longrightarrow> x \<in> closure T \<Longrightarrow> f' x = g' x"
  3020   assumes x_in: "x \<in> s \<union> t"
  2794   assumes x_in: "x \<in> S \<union> T"
  3021   shows "((\<lambda>x. if x \<in> s then f x else g x) has_derivative
  2795   shows "((\<lambda>x. if x \<in> S then f x else g x) has_derivative
  3022       (if x \<in> s then f' x else g' x)) (at x within (s \<union> t))"
  2796       (if x \<in> S then f' x else g' x)) (at x within (S \<union> T))"
  3023 proof -
  2797 proof -
  3024   from f' x_in interpret f': bounded_linear "if x \<in> s then f' x else (\<lambda>x. 0)"
  2798   from f' x_in interpret f': bounded_linear "if x \<in> S then f' x else (\<lambda>x. 0)"
  3025     by (auto simp add: has_derivative_within)
  2799     by (auto simp add: has_derivative_within)
  3026   from g' interpret g': bounded_linear "if x \<in> t then g' x else (\<lambda>x. 0)"
  2800   from g' interpret g': bounded_linear "if x \<in> T then g' x else (\<lambda>x. 0)"
  3027     by (auto simp add: has_derivative_within)
  2801     by (auto simp add: has_derivative_within)
  3028   have bl: "bounded_linear (if x \<in> s then f' x else g' x)"
  2802   have bl: "bounded_linear (if x \<in> S then f' x else g' x)"
  3029     using f'.scaleR f'.bounded f'.add g'.scaleR g'.bounded g'.add x_in
  2803     using f'.scaleR f'.bounded f'.add g'.scaleR g'.bounded g'.add x_in
  3030     by (unfold_locales; force)
  2804     by (unfold_locales; force)
  3031   show ?thesis
  2805   show ?thesis
  3032     using f' g' closure_subset[of t] closure_subset[of s]
  2806     using f' g' closure_subset[of T] closure_subset[of S]
  3033     unfolding has_derivative_within_If_eq
  2807     unfolding has_derivative_within_If_eq
  3034     by (intro conjI bl tendsto_If_within_closures x_in)
  2808     by (intro conjI bl tendsto_If_within_closures x_in)
  3035       (auto simp: has_derivative_within inverse_eq_divide connect connect' set_mp)
  2809       (auto simp: has_derivative_within inverse_eq_divide connect connect' set_mp)
  3036 qed
  2810 qed
  3037 
  2811 
  3038 lemma has_vector_derivative_If_within_closures:
  2812 lemma has_vector_derivative_If_within_closures:
  3039   assumes x_in: "x \<in> s \<union> t"
  2813   assumes x_in: "x \<in> S \<union> T"
  3040   assumes "u = s \<union> t"
  2814   assumes "u = S \<union> T"
  3041   assumes f': "x \<in> s \<union> (closure s \<inter> closure t) \<Longrightarrow>
  2815   assumes f': "x \<in> S \<union> (closure S \<inter> closure T) \<Longrightarrow>
  3042     (f has_vector_derivative f' x) (at x within s \<union> (closure s \<inter> closure t))"
  2816     (f has_vector_derivative f' x) (at x within S \<union> (closure S \<inter> closure T))"
  3043   assumes g': "x \<in> t \<union> (closure s \<inter> closure t) \<Longrightarrow>
  2817   assumes g': "x \<in> T \<union> (closure S \<inter> closure T) \<Longrightarrow>
  3044     (g has_vector_derivative g' x) (at x within t \<union> (closure s \<inter> closure t))"
  2818     (g has_vector_derivative g' x) (at x within T \<union> (closure S \<inter> closure T))"
  3045   assumes connect: "x \<in> closure s \<Longrightarrow> x \<in> closure t \<Longrightarrow> f x = g x"
  2819   assumes connect: "x \<in> closure S \<Longrightarrow> x \<in> closure T \<Longrightarrow> f x = g x"
  3046   assumes connect': "x \<in> closure s \<Longrightarrow> x \<in> closure t \<Longrightarrow> f' x = g' x"
  2820   assumes connect': "x \<in> closure S \<Longrightarrow> x \<in> closure T \<Longrightarrow> f' x = g' x"
  3047   shows "((\<lambda>x. if x \<in> s then f x else g x) has_vector_derivative
  2821   shows "((\<lambda>x. if x \<in> S then f x else g x) has_vector_derivative
  3048     (if x \<in> s then f' x else g' x)) (at x within u)"
  2822     (if x \<in> S then f' x else g' x)) (at x within u)"
  3049   unfolding has_vector_derivative_def assms
  2823   unfolding has_vector_derivative_def assms
  3050   using x_in
  2824   using x_in
  3051   apply (intro has_derivative_If_within_closures[where
  2825   apply (intro has_derivative_If_within_closures[where
  3052         ?f' = "\<lambda>x a. a *\<^sub>R f' x" and ?g' = "\<lambda>x a. a *\<^sub>R g' x",
  2826         ?f' = "\<lambda>x a. a *\<^sub>R f' x" and ?g' = "\<lambda>x a. a *\<^sub>R g' x",
  3053         THEN has_derivative_eq_rhs])
  2827         THEN has_derivative_eq_rhs])