サブロウ丸

主にプログラミングと数学

数学

Newtonの差分商補間(後編)

inarizuuuushi.hatenablog.com これの後編です。 実際に簡単な関数でいくつか補間による近似を行なってみたいと思います。 fが近似したい関数、gがデータ点(0, 0) (1, 1) (2, 2)から構成した差分商補間になります。 fは2次式でかつ、前編の最後の定理「剰余…

Newtonの差分商補間(前編)

Newtonの差分商補間の理論についてです。内容は高校レベルでしょうか。 最後の定理は強力ですね。 補間といえば、他にはLagrange補間が有名ですが、 Lagrange補間よりも計算量が少ないことが特徴です。 一番最後の証明は、「n点を補間するn-1次の多項式はLag…

線形計画問題における、とある条件を持つバイナリ変数の表現方法について

最近、線形計画問題に取り組んでいまして、以下のようなバイナリ変数xを定義する必要が出てきました。 バイナリ変数とは0と1の2値のみをとり得る変数のことです。 これがなかなか難しくて、いろいろ調べてみて、 2通りの定式化を行いました。 1つ目は以下の…

最短路問題を線形計画法で解く2

グラフの最短路問題はダイクストラ法等で解くのが普通ですが、 今回も線形計画法で解いてみたいと思います。(あえてね) が定式化となります。(とするとが続いているところは無視してください) 路の制約として、フロー整合条件を使用しました。 この定式化で…

最短路問題を線形計画法で解く (Python)

グラフの最短路問題はダイクストラ法等で解くのが普通ですが、 今回は線形計画法で解いてみたいと思います。(あえてね) 定式化は こうなります。 最短路を解く問題なのに目的関数が最大化になっているところが面白いですね。 ad(j)については、jの隣接ノード…

最短路計算における、楕円を用いたグラフの枝刈り

上記のグラフのstartからgoalまでの最短路を求めたいとします。 (グラフの枝の重みは枝の長さ) 直感的には、startとgoalから離れた点や枝を考える必要はない(i.e.最短路にそれらの点や枝が含まれることがない)ように思えますが、 それをどう厳密に表現するか…

【Python】 newton法(非線形計画)

newton法とは、目的関数の最小化元(或いは最大化元)を求める問題に対する反復法と呼ばれる解法の一つです。 関数fと勾配、初期点を問題に合わせて入力する必要があります。

【Python】 最急降下法(非線形計画)

最急降下法とは、目的関数の最小化元(或いは最大化元)を求める問題に対する反復法と呼ばれる解法の一つです。 目的関数fと勾配、初期点を問題に合わせて入力する必要があります。

三角形の合同条件と、それに対応する面積公式

ある二つの三角形について、その形と大きさが等しいとき、それらは「合同である」と言います。 この合同についてみなさん、中学校で以下の三つの合同条件を習ったと思います。 ・三辺相等 ・二辺狭角相等 ・二角狭辺相等 例えば三辺相等について、 三角形の…

対称グラフの完全マッチング数について

完全マッチングについて面白い定理を見つけたので、ご紹介します。 まず、完全マッチングについて、 グラフ理論においてマッチングとは、グラフ中の枝集合で、互いに端点を共有しないもののこと。特に、これ以上枝を追加できないもののことを極大マッチング…

劣モジュラ1

「劣モジュラ最適化と機械学習」という河原先生と永野先生が書かれた本を最近勉強しています。 https://www.amazon.co.jp/劣モジュラ最適化と機械学習-機械学習プロフェッショナルシリーズ-河原-吉伸/dp/4061529099/ref=sr_1_fkmr0_1?ie=UTF8&qid=1492411085…