Processing math: 3%
スキップしてメイン コンテンツに移動

ロルの定理

Introduction

今回はロルの定理について書いていきます・
ロルの定理は平均値の定理の証明に使われる定理です。
平均値の定理についてはまた、今度書こうと思います。
ロルの定理の前に最大値原理というものを紹介しておきます。(後で証明に使います。)

最大値原理

fが閉区間上で連続な関数
\implies
fは最大値を持つ(有限値)

証明

最大値原理の証明は難しいです。この投稿で書いてしまうのは大変なので、また、別の投稿で書きたいと思います。
Maximum Principle

ロルの定理

fは区間[a,b]で連続で、(a,b)で微分可能とします。
この時
f(a) = f(b) \implies \exists ~~c ~~s.t~~ f'(c) = 0 , a<c<b

証明

  • f(x) が定数関数の時、
    \forall c \in (a,b) , f'(c) = 0
  • f(x)が定数関数でない時、
\exists t ~~s.t~~f(a) < f(t), \exists c ~~s.t~~ \max f(x) = f(c) by Maximum principle
I proof f'(c)=0
f はx = c で微分可能で、f(c) >= f(c+h).
よって
f'(c) = \lim_{h \rightarrow +0} \frac{f(c+h) - f(c)}{h} \leq 0
f'(c) = \lim_{h \rightarrow -0} \frac{f(c+h) - f(c)}{h} \geq 0
よって 0 \leq \lim_{h \rightarrow -0} \frac{f(c+h) - f(c)}{h} =f'(c) = \lim_{h \rightarrow +0} \frac{f(c+h) - f(c)}{h} \leq 0
f'(c)=0
\exists t ~~s.t f(a)>f(t) の時も同様です。

イメージ

enter image description here
f(3)=f(5) の時、関数には折り返し地点が存在します。(出ないと戻ってこれない。)
この折り返し地点がcとなります。

結論

ロルの定理は平均値の定理に使われる定理です。
平均値の定理は別の投稿で紹介しようと思います。
Mean-Value Theorem

Reference

コメント

このブログの人気の投稿

カーネルK-means 理論編

Introduction English ver 今日は、カーネルK-meansの理論について書きます。カーネルK-meansは通常のK-meansの欠点を補うことができます。通常のK-meansの欠点とカーネルK-meansの強みも説明します。もし、まだ御覧になられていなければ、通常の K-means 理論編 の記事を見ていただけるとよいのではないかと思います。 カーネルK-meansの実装編 も併せてご覧ください。 概要 K-meansの弱点 カーネルトリック カーネルK-means アルゴリズム K-meansの弱点 例えば、次のようなデータを用意します。 このデータはK-meansによってうまく分類することはできません。なぜなら通常のK-meansでは、データとプロトタイプのユークリッド距離に依存しているからです。そのため、このような円状に分布しているデータはうまく分類することができません。 プロトタイプとはそれぞれのクラスにあり、そのクラスを代表するようなもののことです。K-meansでは各クラスの平均ベクトルとなります。それゆえ、以下のような分類になってしまいます。 このようなデータではK-meansはうまくいきません。 K-meansで分類できるデータセットは次のように各クラスで固まっている必要があります。 カーネルK-meansはK-meansの弱点を補います。 カーネルトリック 初めに、カーネルトリックを説明します。 線形分離できないようなデータXを例えば次のように線形分離できるように\phi(x)に送る写像\phiを考えます。 カーネルは次のように定義されます。 K(x,y) = \phi(x)^T \phi(y) \phiを具体的に計算することは難しいですが、K(x,y)を計算することなら簡単です。 この手法をカーネルトリックと呼ばれます。 カーネルK means K-meansの目的関数を復習しておきます。 J = \sum_{n=1}^{N} \sum_{k=1}^{K} r_{nk} ||x_n-\mu_k||^2 ここで、 プロトタイプは\mu_i ~\forall k \in Kとしま...

ダイクストラ法

Introduction English ver 今日は、ダイクストラ法について書きます。ダイクストラ法とは最短距離を求めるアルゴリズムです。地図はグラフで表されます。もし、まだ this page を見ていない方は先にこちらをご覧ください。今回はこの記事を前提としています。このページでは、グラフの定義と、ヒープ構造について書いています。ダイクストラ法ではヒープ構造を使って、かなりの計算量を落とします。 この スライド はダイクストラ法を説明したスライドです。 Overview アルゴリズム 実装 アルゴリズム このアルゴリズムは スタート始点のノードを決める。そして、それをAと名付ける。 各ノードにd=\inftyを割り当てる。ただし、スタート地点はd=0 Aの隣接ノードのリストをadj_listと名付ける。  For adj in adj_list:  If d of adj > d of A + weight to adj -> d = A + weight to adj. グラフnetworkからAを取り除く グラフnetworkの中で最初のdを持っているノードをAとし、4に戻る。 となっています。 このアルゴリズムを図を用いて説明します。  このグラフを使って説明します。  初めに、スタート地点を決めます。そして、各ノードにd=\inftyを割り当てます。  Aから始まります。Aの隣接ノードであるBのdを更新します。もし、現在のBよりもAのdとA->Bへの重みを足したもののほうが小さいならdをその値に更新します。同じようにCnのdを更新します。 次にAを取り除きます。  次はBから始まります。Aと同じことをやります。 このダイクストラ法では今のような操作をグラフの全てのノードに×がつくまで続きます。 実装 このアルゴリズムではO(log(|V|^2))という計算量を持っています。最小のdを持つノードを探すのに時間がかかります。 しかし、ヒープ構造を使えばO((E+V)log(V))に減らせます。ヒープ構造で現時点での...

Kullback-Leibler divergence

Introduction sorry, this page is Japanese only.   今日がダイバージェンスについて書いていきます。 ちなみにエントロピーの知識を使うのでエントロピーの記事も見てあげてください。 エントロピーの記事はこちら Kullback-Leibler Divergence 二つの確率分布の平均エントロピーの差を表す値をKLダイバージェンスといいます。 式では次のように定義されます。 KL(P||Q) = \int_{-\infty}^{\infty} P(X) log \frac{P(X)}{Q(X)} 離散の場合は KL(P||Q) = \sum_{i} P(X_i) log \frac{P(X_i)}{Q(X)} なぜ二つの分布間の距離をこのように定義できるのでしょうか。 式の解釈 真の分布P(X)が存在するとします。しかし、有限のデータから真の分布P(X)を求めるのは難しいです。そこで、有限のデータから推定して得られた確率分布をQ(X)とします。では真の分布P(X)と推定した分布Q(X)はどれだけ違っているのでしょうか。 ここで登場するのがエントロピーです。エントロピーはその分布の不確実性を示す値でした。 エントロピーが高いほど不確かなことが起こるとゆうことです。 P(X)のエントロピーとは-\int_{-\infty}^{\infty} logP(X)でした。 では推定した確率分布Q(X)は確率分布P(X)に対してどれだけ不確実性を持っているのでしょうか。エントロピーとは情報量の期待値でした。確率分布Q(X)が持つ情報量は-logQ(X)です。この情報量を確率P(X)で期待値をとります。 式は以下のようになります。 -\int_{-\infty}^{\infty} P(X) logQ(X) この値と真の分布のエントロピーとの差を二つの分布間の差として定義します。式では以下のようになります。 -\int_{-\infty}^{\infty} P(X) logQ(X) - (--\int_{-\infty}^{\infty} P(X) logP(X))) これを式変形すると $$-\int_{-\infty}^...