ネットワーク上の微分方程式とその初期値問題について。
対象のネットワークでは、各ノードが重みつきのエッジを通して影響を与えあう。
この状況で各ノードの値がどのように時間発展していくかを求める。
ネットワーク上の拡散方程式もこの問題として扱える。この場合、エッジで接続された二つのノードは両者の値の差とエッジの重みに比例して、互いを平均化する方向に値を移動させる。これは集団での金銭の助け合いや、物理での熱交換のモデルにもなる。
なおこの場合、片方のノードへの加算量がもう片方のノードへの減算量となるよう、エッジとその逆方向のエッジの重みは等しくなる。また、ノードの値は他のノードとのやり取り以外では増減しないので、ノードの自身へのエッジは 0 になる。
これはネットワークの各エッジについての重みを記載した正方行列である。
行列の
これはネットワークの各ノードの次数を記載した対角行列である。
ここで次数 (入次数) はノードを終点とするエッジの重みの総量である。
これは隣接行列から次数行列を引いてできる正方行列である。
拡散方程式では、この行列とノードの値からなるベクトルの積をとると、各ノードの値の単位時間あたりの変化量のベクトルが得られる。これが可能となるのは、拡散方程式が比例関係のみを扱っていて、時間発展が線形操作となるためである。つまり、拡散方程式での微分方程式は以下のように表せる。
代表的な初期値問題の解法『Runge-Kutta 法』を使った場合について。
以下の特徴があるため、拡散方程式のような問題とはやや相性が悪い。
陽解法では、真の解の勾配が大きいと数値解が不安定になる (硬い方程式)。
陰解法では、密なネットワークにも対応しようとすると遅くなる。
なぜなら、連立線形方程式の行列が密になり、反復法でなく直接法が必要となる。
精度が低い。次数を上げれば改善されるが、アルゴリズムも複雑になる。
後述の例では 1 次と 2 次で全体の傾向を示しているが、高次でもこの傾向は変わらない。
現時点からの傾きを延長して次時点の値を求める。
つまり、
以下は、2 個のノードの拡散方程式における 1 ステップの計算イメージ。
以下は、2 個のノードの拡散方程式における複数ステップの計算イメージ。勾配がステップ幅に対して大きすぎると、誤差が発振して不安定になる。
次時点からの傾きが現時点に繋がるよう、次時点の値を調整する。
つまり、次の連立線形方程式を
以下は、2 個のノードの拡散方程式における 1 ステップの計算イメージ。
以下は、2 個のノードの拡散方程式における複数ステップの計算イメージ。勾配とステップ幅の大きさによらず、無条件安定となる。
現時点と次時点の傾きの平均が、次時点に繋がるよう次時点を調整する。
つまり、次の連立線形方程式を
以下は、2 個のノードの拡散方程式における 1 ステップの計算イメージ。
以下は、2 個のノードの拡散方程式における複数ステップの計算イメージ。勾配が大きいと振動することもあるが、その振幅はステップごとに減衰していく。
系の線形成分を分離して計算し、それについての誤差をほぼなくす。
なお、拡散方程式は線形操作のみで構成されるため、この手法は特に有効である。
以下は、2 個のノードの拡散方程式における 1 ステップの計算イメージ。ステップ幅を巨大にしているにも関わらず、誤差がほぼないのが特徴的である。
線形成分と非線形成分の分離について。
微分方程式の線形成分と非線形成分を分けて以下のように記述する。
ここで、右辺の第一項は拡散方程式と同じ形式となる。
そして、右辺の第二項では非線形成分をまとめておく。
上記の微分方程式の特殊解から (解法は後述)、時刻
ここで、右辺の第一項と第二項は以下の特徴を持つ。
第一項: 線形成分のみで表される。厳密解を計算可能。
第二項: 非線形成分がないとゼロになる。近似解は計算可能。
上記の微分方程式は以下の手順で解ける。
両辺に
右辺の第一項を左辺へ移行。
左辺を積の微分として解釈。
両辺を積分 (
式を整理 (右辺の積分変数は
一般解より
式を簡単化して
導出した
『行列指数関数とベクトルの積』で紹介する方法を使うと、
TODO: 追記予定？