スキップしてメイン コンテンツに移動

変分法の可視化

Introduction


今日は、変分法の可視化を実装しました。変分法は、汎関数を最小化させるために使われます。汎関数とは、関数の関数のようなものです。変分法については、 [1],[2],[3],[5], [6]などを参考にしてください。

概要

  • 汎関数
  • 実装
  • 可視化

汎関数
今回は、次のような汎関数を使います。
$$F(x) = \sqrt{1+(\frac{du}{dx}(x))^2}$$
$$l(u) = \int_{0}^{1} \sqrt{1+(\frac{du}{dx}(x))^2} dx$$

l(u)はu(x)という曲線の長さです。. 
$u(0)=a$ and $u(1)=b$という制約のもと、$l(u)$を最小化したいといます。
最適な$l(u)$は
$$u(x) = (b-a)x+a$$
となります。

(0,a) から (1,b)への直線になっているのがわかります。
これは、$l(u)$は$u$の曲線の長さなので、これを最小化するためには直線が一番であることが直観的にわかります。

変分法での導出は、[5]を参考にしてください。

実装
変分法における最適な曲線とそうでない曲線の違いを可視化する実装をしました。
$u_A$を
$$u_A = (b-a)x+a + A sin(8t)$$
とします。
$A sin(8t)$ は$u$から話す役割を持ちます。. $A \in [0,0.5]$であり、もし$A=0$であれば、$u_A=u$です。

githubでcodeを公開しています。



可視化
上側の画像は$u_A(x)$を表しています。下側の画像は$l(u_A)$の値を表しています。
$u_A(x)$が$u$に近づくほど、$l(u_A)$が小さくなることがわかります。







Reference
[1]http://www2.kaiyodai.ac.jp/~takenawa/optimization/resume10-4.pdf
[2]http://hooktail.sub.jp/mathInPhys/brachisto/
[3]http://eman-physics.net/math/differential21.html
[4]http://bicycle1885.hatenablog.com/entry/2014/02/14/023734
[5]http://www2.kaiyodai.ac.jp/~yoshi-s/Lectures/Optimization/2013/lecture_6.pdf
[6]http://www.qi.mp.es.osaka-u.ac.jp/personal/imoto/index-j/jugyou/Kaiseki170427.pdf
Labels:

コメント

コメントを投稿

このブログの人気の投稿

カーネルk-meansの実装

Introduction   English ver 今日はカーネルk-meansの実装をしました。k-menasアルゴリズムはクラスタリングのためのアルゴリズムです。僕がカーネルk-meansを実装しようと思ったのには一つ理由があります。それは僕の友人がk-meansのプレゼンを、僕がカーネルのプレゼンをしていた時に、k-meansにカーネルを適応できないかと思ったからです。そこで、カーネルk-meansについての論文を探しました。 ここのpdf を主に参考にさせていただきました。うまくカーネルk-meansを実装できたと思います。ここでは、普通のk-meansとカーネルを用いた,kernel k-meansについての実装の結果を紹介します。 また、この記事では実装結果のみ書きますが、理論のほうも別の記事で書くつもりです。書き終えたらリンクをこの記事にも貼っておきます。 #  理論編書きました。K-means 理論編 概要 dataset   ちょっとだけ理論の説明  k-means    kernel k-means   Dataset   English ver 今回使うのは二つのデータセットです。一つ目は、普通のk-means用のデータです。二つ目はkernel k-means用のデータセットです。 一つ目のデータは、三つのグループで構成されており、次元は2で、サンプル数は300です。以下のような分布になっています。 二つ目のデータは二つのグループで構成されており、次元は2でサンプル数は300です。   this page にデータセットを作ったコードを載せています。 ちょっとだけ理論の説明 k-meansとは、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))に減らせます。ヒープ構造で現時点での...
コメントを投稿
続きを読む

Discrete Fourier transform

Introduction 日本語 ver I will write about Discrete Fourier transform. Discrete Fourier transform is Abbreviated DFT. I am making pdf about Audio Signal Processing. I publish pdf at  github . However, I write tex in Japanese. I take a lecture about the signal processing. There is lecture at  thie page . I update this pdf.
コメントを投稿
続きを読む