離散ラプラス演算子

数学において、離散ラプラス演算子は連続ラプラス演算子の類似物であり、グラフまたは離散グリッド上で意味を持つように定義されます。有限次元グラフ（有限個の辺と頂点を持つグラフ）の場合、離散ラプラス演算子は一般的にラプラシアン行列と呼ばれます。

離散ラプラス演算子は、イジングモデルやループ量子重力などの物理問題、および離散力学系の研究に現れます。また、数値解析では連続ラプラス演算子の代わりとして使用されます。一般的な応用例としては、画像処理^{[ 1 ]} （ラプラスフィルタとして知られています）、および近傍グラフ上のクラスタリングや半教師あり学習のための機械学習などがあります。

定義

グラフ・ラプラシアン

グラフの離散ラプラシアンには、符号やスケール係数によって異なる様々な定義が存在する（隣接する頂点の平均を取る場合もあれば、単に合計する場合もある。正則グラフの場合は違いはない）。以下に示すグラフ・ラプラシアンの伝統的な定義は、自由境界を持つ領域における負の連続ラプラシアンに対応する。

させて $G=(V,E)$ 頂点を持つグラフである $V$ エッジ $E$ 。させて $\phi \colon V\to \mathbb {R}$ は、リング内の値を取る頂点の関数である。すると、離散ラプラシアンは $\Delta$ 行動する $\phi$ 定義される

(\Delta \phi )(v)=\sum _{w:\,d(w,v)=1}\left[\phi (v)-\phi (w)\right]

どこ $d(w,v)$ は頂点 w と v の間のグラフ距離です。したがって、この和は頂点vの最近傍について取られます。辺と頂点の数が有限のグラフの場合、この定義はラプラシアン行列の定義と同一です。つまり、 $\phi$ 列ベクトルとして記述できます。 $\Delta \phi$ は列ベクトルとラプラシアン行列の積であり、 $(\Delta \phi )(v)$ それはただ $v$ 積ベクトルの番目の要素。

グラフに重み付きエッジがある場合、つまり重み関数が $\gamma \colon E\to \mathbb {R}$ が与えられれば、定義は次のように一般化できる。

(\Delta _{\gamma }\phi )(v)=\sum _{w:\,d(w,v)=1}\gamma _{wv}\left[\phi (v)-\phi (w)\right]

どこ $\gamma _{wv}$ エッジの重み値 $wv\in E$ 。

離散ラプラシアンと密接に関連しているのが平均化演算子である。

(M\phi )(v)={\frac {1}{\deg v}}\sum _{w:\,d(w,v)=1}\phi (w).

メッシュラプラシアン

グラフ内のノードとエッジの接続性を考慮することに加えて、メッシュラプラス演算子は表面の形状（例えば、ノードでの角度）も考慮します。2次元多様体三角形メッシュの場合、スカラー関数のラプラス・ベルトラミ演算子は次のようになります。 $u$ 頂点で $i$ 近似すると次のようになる

(\Delta u)_{i}\equiv {\frac {1}{2A_{i}}}\sum _{j\in N(i)}(\cot \alpha _{ij}+\cot \beta _{ij})(u_{j}-u_{i}),

どこ $N(i)$ の近隣を表します $i$ （除く） $i$ ) $\alpha _{ij}$ そして $\beta _{ij}$ 辺の反対側の2つの角は $ij$ 、そして $A_{i}$ 頂点面積は $i$ つまり、例えば、 $i$ 離散ラプラス・ベルトラミ演算子の符号は、慣例的に通常のラプラス演算子の符号と逆になります。上記の余接公式は、区分的線形有限要素法、有限体積法、離散外微分法など、さまざまな方法を使用して導出できます。^{[ 2 ]}

計算を容易にするため、ラプラシアンは行列に符号化される。 $L\in \mathbb {R} ^{|V|\times |V|}$ そのため $Lu=(\Delta u)_{i}$ 。させて $C$ 要素が（疎な）余接行列である。

$C_{ij}={\begin{cases}{\frac {1}{2}}(\cot \alpha _{ij}+\cot \beta _{ij})&ij{\text{ is an edge, that is }}j\in N(i),\\-\sum \limits _{k\in N(i)}C_{ik}&i=j,\\0&{\text{otherwise}}\end{cases}}$

どこ $N(i)$ の近隣を表します $i$ 、そして $M$ 対角質量行列とする $M$ だれの $i$ 対角線上の番目のエントリは頂点領域です $A_{i}$ 。それから $L=M^{-1}C$ これは、ラプラシアンの求められている離散化である。

メッシュ演算子のより一般的な概要は^{[ 3 ]}に示されています。

有限差分法

有限差分法または有限要素法によって得られるラプラシアンの近似値も、離散ラプラシアンと呼ぶことができます。たとえば、2 次元のラプラシアンは、5 点ステンシル有限差分法を使用して近似することができ、その結果は次のようになります。

\Delta f(x,y)\approx {\frac {f(x-h,y)+f(x+h,y)+f(x,y-h)+f(x,y+h)-4f(x,y)}{h^{2}}},

ここで、グリッドサイズは両次元ともhであり、グリッド内の点( x , y )の5点ステンシルは次のようになる。

\{(x-h,y),(x,y),(x+h,y),(x,y-h),(x,y+h)\}.

グリッドサイズh = 1 の場合、結果はグラフ上の負の離散ラプラシアンであり、これは正方格子グリッドです。ここでは、格子グリッドの境界上の関数f ( x , y )の値に制約がないため、境界にソースがない場合、つまり無流束境界条件 (別名、絶縁、または同次ノイマン境界条件) となります。境界での状態変数の制御、つまりグリッドの境界でf ( x , y ) が与えられる (別名、ディリクレ境界条件) は、グラフラプラシアンではほとんど使用されませんが、他のアプリケーションでは一般的です。

長方形の正方格子上の多次元離散ラプラシアンは非常に特別な性質を持ち、例えば、1次元離散ラプラシアンのクロネッカー和になります（離散ラプラシアンのクロネッカー和を参照）。この場合、すべての固有値と固有ベクトルを明示的に計算できます。

有限要素法

この手法では、領域をより小さな要素（多くの場合、三角形や四面体、ただし長方形や直方体など）に離散化します。次に、解空間を、あらかじめ定義された次数を持ついわゆる形状関数を用いて近似します。ラプラス演算子を含む微分方程式は、変分形式に変換され、連立方程式（線形問題または固有値問題）が構築されます。得られる行列は通常非常に疎行列であり、反復法で解くことができます。

画像処理

離散ラプラス演算子は、画像処理、例えばエッジ検出や動き推定アプリケーションでよく使用されます。^{[ 4 ]}離散ラプラシアンは、2 階微分の合計として定義され、中心ピクセルの最近傍ピクセル間の差分の合計として計算されます。微分フィルタは画像のノイズに敏感な場合が多いため、ラプラス演算子の前には、微分を計算する前にノイズを除去するために平滑化フィルタ (ガウスフィルタなど) が置かれることがよくあります。平滑化フィルタとラプラスフィルタは、多くの場合、単一のフィルタに統合されます。^{[ 5 ]}

演算子の離散化による実装

1次元、2次元、3次元信号の場合、離散ラプラシアンは、以下のカーネルとの畳み込みとして表すことができます。

1Dフィルター：

{\vec {D}}_{x}^{2}={\begin{bmatrix}1&-2&1\end{bmatrix}}

、

2Dフィルター：

\mathbf {D} _{xy}^{2}={\begin{bmatrix}0&1&0\\1&-4&1\\0&1&0\end{bmatrix}}

。

$\mathbf {D} _{xy}^{2}$ これは、以前に見た（5点ステンシル）有限差分公式に対応します。非常に滑らかに変化する場に対しては安定していますが、急速に変化する解を持つ方程式には、より安定で等方的なラプラシアン演算子の形式が必要です^{[ 6 ]。}例えば、対角線を含む9点ステンシルなどです。

2Dフィルター：

\mathbf {D} _{xy}^{2}={\begin{bmatrix}0.25&0.5&0.25\\0.5&-3&0.5\\0.25&0.5&0.25\end{bmatrix}}

、

3Dフィルター：

\mathbf {D} _{xyz}^{2}

7点ステンシルを使用した場合、以下のようになります。

最初の飛行機 =

{\begin{bmatrix}0&0&0\\0&1&0\\0&0&0\end{bmatrix}}

; 2 つ目の平面 =

{\begin{bmatrix}0&1&0\\1&-6&1\\0&1&0\end{bmatrix}}

; 3 つ目の平面 =

{\begin{bmatrix}0&0&0\\0&1&0\\0&0&0\end{bmatrix}}

。

そして27ポイントステンシルを使用して：^{[ 7 ]}

最初の飛行機 =

{\frac {1}{26}}{\begin{bmatrix}2&3&2\\3&6&3\\2&3&2\end{bmatrix}}

; 2 つ目の平面 =

{\frac {1}{26}}{\begin{bmatrix}3&6&3\\6&-88&6\\3&6&3\end{bmatrix}}

; 3 つ目の平面 =

{\frac {1}{26}}{\begin{bmatrix}2&3&2\\3&6&3\\2&3&2\end{bmatrix}}

。

n D フィルタ: 要素の場合

a_{x_{1},x_{2},\dots ,x_{n}}

カーネルの

\mathbf {D} _{x_{1},x_{2},\dots ,x_{n}}^{2},

a_{x_{1},x_{2},\dots ,x_{n}}=\left\{{\begin{array}{ll}-2n&{\text{if }}s=n,\\1&{\text{if }}s=n-1,\\0&{\text{otherwise,}}\end{array}}\right.

ここで、x i はカーネル内の要素の i 番目の方向における位置 (−1、0 または

1)

であり、

s

は

x

i

=

0

と

なる

方向

i

の

数である。

なお、ラプラシアンのグラフ一般化に基づくnDバージョンは、すべての隣接ノードが等距離にあると仮定するため、上記のバージョンではなく、対角線を含む以下の2Dフィルタになります。

2Dフィルター：

\mathbf {D} _{xy}^{2}={\begin{bmatrix}1&1&1\\1&-8&1\\1&1&1\end{bmatrix}}.

これらのカーネルは、離散微分商を用いることによって導出される。

2次元ラプラシアン演算子の以下の離散近似は、差分演算子の凸結合として表されることが示されています^{[ 8 ]}^{[ 9 ]。}

\nabla _{\gamma }^{2}=(1-\gamma )\nabla _{5}^{2}+\gamma \nabla _{\times }^{2}=(1-\gamma ){\begin{bmatrix}0&1&0\\1&-4&1\\0&1&0\end{bmatrix}}+\gamma {\begin{bmatrix}1/2&0&1/2\\0&-2&0\\1/2&0&1/2\end{bmatrix}}

γ ∈ [0, 1] は離散スケール空間特性と互換性があり、特に γ = 1/3 の値が回転対称性の最良の近似を与える。^{[ 8 ]}^{[ 9 ]}^{[ 10 ]} 3 次元信号に関しては、ラプラシアン演算子は 2 パラメータ族の差分演算子で近似できることが示されている^{[ 9 ]}

\nabla _{\gamma _{1},\gamma _{2}}^{2}=(1-\gamma _{1}-\gamma _{2})\,\nabla _{7}^{2}+\gamma _{1}\,\nabla _{+^{3}}^{2}+\gamma _{2}\,\nabla _{\times ^{3}}^{2}),

どこ

(\nabla _{7}^{2}f)_{0,0,0}=f_{-1,0,0}+f_{+1,0,0}+f_{0,-1,0}+f_{0,+1,0}+f_{0,0,-1}+f_{0,0,+1}-6f_{0,0,0},

(\nabla _{+^{3}}^{2}f)_{0,0,0}={\frac {1}{4}}(f_{-1,-1,0}+f_{-1,+1,0}+f_{+1,-1,0}+f_{+1,+1,0}+f_{-1,0,-1}+f_{-1,0,+1}+f_{+1,0,-1}+f_{+1,0,+1}+f_{0,-1,-1}+f_{0,-1,+1}+f_{0,+1,-1}+f_{0,+1,+1}-12f_{0,0,0}),

(\nabla _{\times ^{3}}^{2}f)_{0,0,0}={\frac {1}{4}}(f_{-1,-1,-1}+f_{-1,-1,+1}+f_{-1,+1,-1}+f_{-1,+1,+1}+f_{+1,-1,-1}+f_{+1,-1,+1}+f_{+1,+1,-1}+f_{+1,+1,+1}-8f_{0,0,0}).

テイラー級数解析により、値の組み合わせが $\gamma _{1}$ そして $\gamma _{2}$ そのために $3\gamma _{1}+6\gamma _{2}=2$ 回転対称性の最良の近似値を与える。

継続的な再構築による実装

画像などの離散信号は、連続関数の離散表現とみなすことができる。 $f({\bar {r}})$ 座標ベクトル ${\bar {r}}\in R^{n}$ そして値域は実数である $f\in R$ したがって、微分演算は連続関数に直接適用可能であり、 $f$ 特に、離散化プロセスに関する妥当な仮定（例えば、帯域制限関数やウェーブレット拡張関数などを仮定する）があれば、任意の離散画像は、再構成定式化の基礎となる良好な挙動を示す補間関数によって再構成することができる。^{[ 11 ]}

f({\bar {r}})=\sum _{k\in K}f_{k}\mu _{k}({\bar {r}})

どこ $f_{k}\in R$ 離散表現 $f$ グリッド上 $K$ そして $\mu _{k}$ 補間関数はグリッドに固有のものです $K$ 均一なグリッド（画像など）では、帯域制限関数の場合、補間関数はシフト不変であり、 $\mu _{k}({\bar {r}})=\mu ({\bar {r}}-{\bar {r}}_{k})$ と $\mu$ 適切に拡張されたsinc関数は、 $n$ -次元、つまり ${\bar {r}}=(x_{1},x_{2}...x_{n})^{T}$ .その他の近似値 $\mu$ 均一なグリッド上では、適切に拡大されたガウス関数は $n$ 次元。したがって、離散ラプラシアンは連続ラプラシアンの離散版となる。 $f({\bar {r}})$

\nabla ^{2}f({\bar {r}}_{k})=\sum _{k'\in K}f_{k'}(\nabla ^{2}\mu ({\bar {r}}-{\bar {r}}_{k'}))|_{{\bar {r}}={\bar {r}}_{k}}

これは、均一な（画像）グリッド上の補間関数のラプラシアンとの畳み込みである。 $K$ ガウス関数を補間関数として使用する利点は、座標系の回転アーティファクトのないラプラシアンを含む線形演算子が得られることです。 $f$ は $f_{k}$ 、で $n$ 次元であり、定義上周波数を考慮します。線形演算子は、 ${\bar {r}}$ ドメインだけでなく、周波数領域（またはガウススケール空間）における有効範囲も、原理的にガウス分布の分散を介して明示的に制御できます。結果として得られるフィルタリングは、分離可能なフィルタと、さらなる計算効率のためにデシメーション（信号処理） /ピラミッド（画像処理）表現によって実装できます。 $n$ 次元。言い換えれば、任意のサイズの離散ラプラシアンフィルタは、分散によって制御される特定のアプリケーションのニーズに適した空間サイズを持つガウスのラプラシアンのサンプリングとして簡単に生成できます。信号が十分にオーバーサンプリングされている場合、非線形演算子である単項式も同様の再構成および近似アプローチを使用して実装できます。これにより、パターン認識で方向推定における最小二乗最適性のために使用される構造テンソルや一般化構造テンソルなどの非線形演算子を実現できます。

スペクトラム

無限格子上の離散ラプラシアンのスペクトルは非常に重要です。自己共役作用素であるため、実スペクトルを持ちます。慣例として、 $\Delta =I-M$ の上 $Z$ スペクトルは $[0,2]$ （平均化演算子のスペクトル値は $[-1,1]$ これはフーリエ変換を適用することによっても確認できます。無限格子上の離散ラプラシアンは純粋に絶対連続なスペクトルを持つため、固有値や固有関数は存在しないことに注意してください。

定理

グラフが無限の正方格子である場合、このラプラシアンの定義は、無限に細かい格子の極限において連続ラプラシアンに対応することが示されます。したがって、例えば、1次元格子では次のようになります。

{\frac {\partial ^{2}F}{\partial x^{2}}}=\lim _{\epsilon \rightarrow 0}{\frac {[F(x+\epsilon )-F(x)]-[F(x)-F(x-\epsilon )]}{\epsilon ^{2}}}.

このラプラシアンの定義は、数値解析や画像処理において一般的に用いられています。画像処理においては、ラプラシアンはデジタルフィルタの一種、より具体的にはエッジフィルタの一種とみなされ、ラプラスフィルタと呼ばれています。

離散熱方程式

仮定する ${\textstyle \phi }$ グラフ上の温度分布を表す。 ${\textstyle \phi _{i}}$ 頂点の温度は ${\textstyle i}$ ニュートンの冷却法則によれば、節点から伝達される熱は ${\textstyle i}$ ノードへ ${\textstyle j}$ に比例する ${\textstyle \phi _{i}-\phi _{j}}$ ノードの場合 ${\textstyle i}$ そして ${\textstyle j}$ 接続されている（接続されていない場合は熱は伝達されない）。次に、熱伝導率 ${\textstyle k}$ 、

{\begin{aligned}{\frac {d\phi _{i}}{dt}}&=-k\sum _{j}A_{ij}\left(\phi _{i}-\phi _{j}\right)\\&=-k\left(\phi _{i}\sum _{j}A_{ij}-\sum _{j}A_{ij}\phi _{j}\right)\\&=-k\left(\phi _{i}\ \deg(v_{i})-\sum _{j}A_{ij}\phi _{j}\right)\\&=-k\sum _{j}\left(\delta _{ij}\ \deg(v_{i})-A_{ij}\right)\phi _{j}\\&=-k\sum _{j}\left(L_{ij}\right)\phi _{j}.\end{aligned}}

行列ベクトル表記では、

{\begin{aligned}{\frac {d\phi }{dt}}&=-k(D-A)\phi \\&=-kL\phi ,\end{aligned}}

これにより

{\frac {d\phi }{dt}}+kL\phi =0.

この方程式は熱方程式と同じ形式であることに注目してください。ここで、行列 − Lはラプラシアン演算子を置き換えています。 ${\textstyle \nabla ^{2}}$ そのため、「グラフ・ラプラシアン」と呼ばれる。

この微分方程式の解を求めるには、1階行列微分方程式を解くための標準的な手法を適用します。つまり、次のように記述します。 ${\textstyle \phi }$ 固有ベクトルの線形結合として ${\textstyle \mathbf {v} _{i}}$ Lの(そのため ${\textstyle L\mathbf {v} _{i}=\lambda _{i}\mathbf {v} _{i}}$ ）時間依存係数を持つ、 ${\textstyle \phi (t)=\sum _{i}c_{i}(t)\mathbf {v} _{i}.}$

元の式に代入すると（Lは対称行列なので、その単位ノルム固有ベクトルは ${\textstyle \mathbf {v} _{i}}$ （直交している）：

{\begin{aligned}0={}&{\frac {d\left(\sum _{i}c_{i}(t)\mathbf {v} _{i}\right)}{dt}}+kL\left(\sum _{i}c_{i}(t)\mathbf {v} _{i}\right)\\{}={}&\sum _{i}\left[{\frac {dc_{i}(t)}{dt}}\mathbf {v} _{i}+kc_{i}(t)L\mathbf {v} _{i}\right]\\{}={}&\sum _{i}\left[{\frac {dc_{i}(t)}{dt}}\mathbf {v} _{i}+kc_{i}(t)\lambda _{i}\mathbf {v} _{i}\right]\\\Rightarrow 0={}&{\frac {dc_{i}(t)}{dt}}+k\lambda _{i}c_{i}(t),\\\end{aligned}}

その解決策は

c_{i}(t)=c_{i}(0)e^{-k\lambda _{i}t}.

前述のように、固有値は ${\textstyle \lambda _{i}}$ Lの値は非負であり、拡散方程式の解が指数関数的に減少するか一定のままであるため、平衡に近づくことを示しています。これはまた、与えられた場合、 ${\textstyle \lambda _{i}}$ そして初期条件 ${\textstyle c_{i}(0)}$ 任意の時刻tにおける解を求めることができる。^{[ 12 ]}

見つける ${\textstyle c_{i}(0)}$ 各 ${\textstyle i}$ 全体的な初期条件に関して ${\textstyle \phi (0)}$ 単純にプロジェクト ${\textstyle \phi (0)}$ 単位ノルム固有ベクトルへ ${\textstyle \mathbf {v} _{i}}$ ;

c_{i}(0)=\left\langle \phi (0),\mathbf {v} _{i}\right\rangle .

このアプローチは、非構造格子上の定量的熱伝達モデリングに適用されてきた。^{[ 13 ]}^{[ 14 ]}

無向グラフの場合、これは以下の理由で機能します。 ${\textstyle L}$ は対称であり、スペクトル定理により、その固有ベクトルはすべて直交します。したがって、の固有ベクトルへの射影は ${\textstyle L}$ これは、初期条件を、指数関数的に減衰し、かつ互いに独立している一連の座標に変換する、単なる直交座標変換である。

平衡挙動

理解するために ${\textstyle \lim _{t\to \infty }\phi (t)}$ 唯一の条件 ${\textstyle c_{i}(t)=c_{i}(0)e^{-k\lambda _{i}t}}$ 残っているのは、 ${\textstyle \lambda _{i}=0}$ 、以来

\lim _{t\to \infty }e^{-k\lambda _{i}t}={\begin{cases}0,&{\text{if}}&\lambda _{i}>0\\1,&{\text{if}}&\lambda _{i}=0\end{cases}}

言い換えれば、システムの平衡状態はカーネルによって完全に決定される。 ${\textstyle L}$ 。

定義により、 ${\textstyle \sum _{j}L_{ij}=0}$ ベクトル ${\textstyle \mathbf {v} ^{1}}$ すべての 1 がカーネルに含まれている場合。 ${\textstyle k}$ グラフ内の互いに素な連結成分の場合、このすべて 1 のベクトルは、 ${\textstyle k}$ 独立した ${\textstyle \lambda =0}$ 1と0からなる固有ベクトル。各連結成分は、その連結成分内の要素が1で、それ以外の要素が0である固有ベクトルに対応する。

その結果、与えられた初期条件に対して ${\textstyle \phi (0)}$ グラフの場合 ${\textstyle N}$ 頂点

\lim _{t\to \infty }\phi (t)=\left\langle \phi (0),\mathbf {v^{1}} \right\rangle \mathbf {v^{1}}

どこ

\mathbf {v^{1}} ={\frac {1}{\sqrt {N}}}[1,1,\ldots ,1]

各要素について ${\textstyle \phi _{j}}$ の ${\textstyle \phi }$ つまり、各頂点について ${\textstyle j}$ グラフでは、次のように書き換えることができます。

\lim _{t\to \infty }\phi _{j}(t)={\frac {1}{N}}\sum _{i=1}^{N}\phi _{i}(0).

言い換えれば、定常状態では、 ${\textstyle \phi }$ グラフの各頂点において、値は同じ値に収束します。これは、すべての頂点における初期値の平均です。これは熱拡散方程式の解であるため、直感的にも全く理にかなっています。グラフ内の隣接する要素間でエネルギーが交換され、最終的にエネルギーが互いに接続されているすべての要素に均等に分散されると予想されます。

グリッド上の演算子の例

このセクションでは関数の例を示します ${\textstyle \phi }$ グラフを通して時間とともに拡散していく様子。この例のグラフは2次元離散グリッド上に構築されており、グリッド上の点は8つの隣接点と接続されています。初期状態では3つの点に正の値が割り当てられ、グリッド内の残りの点の値はすべてゼロです。時間の経過とともに、指数関数的な減衰作用によって、これらの点の値がグリッド全体に均等に分布していきます。

このアニメーションを生成するために使用された完全なMATLABソースコードを以下に示します。このコードは、初期条件の指定、これらの初期条件をラプラシアン行列の固有ベクトルに投影する処理、および投影された初期条件の指数関数的減衰のシミュレーションを示しています。

N = 20 ; % 画像の次元に沿ったピクセル数A = zeros ( N , N ); % 画像Adj = zeros ( N * N , N * N ); % 隣接行列% 8 つの隣接点を使用し、隣接行列を埋めますdx = [ - 1 , 0 , 1 , - 1 , 1 , - 1 , 0 , 1 ]; dy = [ - 1 , - 1 , - 1 , 0 , 0 , 1 , 1 , 1 ]; for x = 1 : N for y = 1 : N index = ( x - 1 ) * N + y ; for ne = 1 : length ( dx ) newx = x + dx ( ne ); newy = y + dy ( ne ); if newx > 0 && newx <= N && newy > 0 && newy <= N index2 = ( newx - 1 ) * N + newy ; Adj ( index , index2 ) = 1 ; end end end end% 以下は微分方程式の解を計算するキーコードですDeg = diag ( sum ( Adj , 2 )); % 次数行列を計算しますL = Deg - Adj ; % 次数行列と隣接行列を使用してラプラシアン行列を計算します[ V , D ] = eig ( L ); % ラプラシアン行列の固有値/ベクトルを計算しますD = diag ( D );% 初期条件 (周囲にいくつかの大きな正の値を配置し、% それ以外はすべてゼロにする) C0 = zeros ( N , N ); C0 ( 2 : 5 , 2 : 5 ) = 5 ; C0 ( 10 : 15 , 10 : 15 ) = 10 ; C0 ( 2 : 5 , 8 : 13 ) = 7 ; C0 = C0 (:);C0V = V '* C0 ; % 初期条件を固有ベクトルの座標系に変換します % for t = 0 : 0.05 : 5 % 時間をループして各初期成分を減衰しますPhi = C0V .* exp ( - D * t ); % 各成分の指数関数的減衰Phi = V * Phi ; % 固有ベクトル座標系から元の座標系に変換しますPhi = reshape ( Phi , N , N ); % 結果を表示して GIF ファイルに書き込みますimagesc ( Phi ); caxis ([ 0 , 10 ]); title ( sprintf ( 'Diffusion t = %3f' , t )); frame = getframe ( 1 ); im = frame2im ( frame ); [ imind , cm ] = rgb2ind ( im , 256 ); if t == 0 imwrite ( imind , cm , 'out.gif' , 'gif' , 'Loopcount' , inf , 'DelayTime' , 0.1 ); else imwrite ( imind , cm , 'out.gif' , 'gif' , 'WriteMode' , 'append' , 'DelayTime' , 0.1 ); end end

離散シュレーディンガー演算子

させて $P\colon V\rightarrow R$ グラフ上で定義されたポテンシャル関数とする。Pは、グラフ上で対角線上に作用する乗法演算子とみなせることに注意する。 $\phi$

(P\phi )(v)=P(v)\phi (v).

それから $H=\Delta +P$ は離散シュレーディンガー演算子であり、連続シュレーディンガー演算子の類似物である。

頂点で交わる辺の数が一様に制限され、ポテンシャルが制限されている場合、Hは制限され、自己共役である。

このハミルトニアンのスペクトル特性はストーンの定理を用いて調べることができる。これは半順序集合とブール代数の双対性の結果である。

規則的な格子においては、ポテンシャルが周期的かランダムかによって、演算子は通常、進行波解とアンダーソン局在解の両方を持つ。

離散シュレーディンガー演算子のグリーン関数は、レゾルベント形式で次のように与えられる。

G(v,w;\lambda )=\left\langle \delta _{v}\left|{\frac {1}{H-\lambda }}\right|\delta _{w}\right\rangle

どこ $\delta _{w}$ これは、グラフ上のクロネッカーのデルタ関数であると理解されています。 $\delta _{w}(v)=\delta _{wv}$ つまり、v = wの場合は1 、それ以外の場合は0となる。

固定の場合 $w\in V$ そして $\lambda$ 複素数であるグリーン関数は、vの関数とみなされ、次の唯一の解である。

(H-\lambda )G(v,w;\lambda )=\delta _{w}(v).

ADE分類

離散ラプラシアンを含む特定の方程式は、単純なレース付きディンキン図（すべてのエッジの多重度が 1）にのみ解を持ち、ADE 分類の一例です。具体的には、同次方程式の唯一の正の解は次のとおりです。

\Delta \phi =\phi ,

言葉で言うと、

「任意のラベルの2倍は、隣接する頂点のラベルの合計である。」

これらは拡張（アフィン）ADEディンキン図上にあり、無限族が2つ（AとD）、例外が3つ（E）存在します。結果として得られる番号はスケールまで一意であり、最小値を1に設定すると、他の数値は6までの整数になります。

通常のADEグラフは、以下の性質を持つ正のラベル付けを許容する唯一のグラフである。

任意のラベルの2倍から2を引いた値は、隣接する頂点のラベルの合計値に等しい。

ラプラシアンの観点から、非同次方程式の正の解は次のようになる。

\Delta \phi =\phi -2.

結果として得られる番号付けは一意であり（スケールは「2」で指定される）、整数で構成されています。E ₈の場合、その範囲は 58 から 270 であり、1968 年という早い時期から観測されています。^{[ 15 ]}

参考文献

↑ Leventhal, Daniel (2011年秋). 「画像処理」(PDF) .ワシントン大学. 2019年12月1日取得.
↑ Crane, K.; de Goes, F.; Desbrun, M.; Schröder, P. (2013). "離散外積分によるデジタル幾何処理" . ACM SIGGRAPH 2013 Courses . SIGGRAPH '13. Vol. 7. pp. 1– 126. doi : 10.1145/2504435.2504442 .
↑ Reuter, M.; Biasotti, S.; Giorgi, D.; Patane, G.; Spagnuolo, M. (2009). "形状解析とセグメンテーションのための離散ラプラス・ベルトラミ演算子". Computers & Graphics . 33 (3): 381–390df. CiteSeerX 10.1.1.157.757 . doi : 10.1016/j.cag.2009.03.005 .
↑ Forsyth, DA; Ponce, J. (2003). "Computer Vision". Computers & Graphics . 33 (3): 381–390 . CiteSeerX 10.1.1.157.757 . doi : 10.1016/j.cag.2009.03.005 .
↑ Matthys, Don (2001年2月14日). "LoGフィルター" .マルケット大学. 2019年12月1日取得.
↑ Provatas, Nikolas; Elder, Ken (2010-10-13). Phase-Field Methods in Materials Science and Engineering (PDF) . Weinheim, Germany: Wiley-VCH Verlag GmbH & Co. KGaA. p. 219. doi : 10.1002/9783527631520 . ISBN 978-3-527-63152-0。
↑ O'Reilly, H.; Beck, Jeffrey M. (2006). "3次元における大規模ステンシル離散ラプラシアン近似のファミリー" (PDF) . International Journal for Numerical Methods in Engineering : 1– 16.
1 2 Lindeberg, T.、「離散信号のためのスケール空間」、PAMI(12)、第3号、1990年3月、pp. 234–254。
1 2 3 Lindeberg, T., Scale-Space Theory in Computer Vision, Kluwer Academic Publishers, 1994 , ISBN 0-7923-9418-6。
↑ Patra, Michael; Karttunen, Mikko (2006). "微分演算子に対する等方性離散化誤差を持つステンシル". Numerical Methods for Partial Differential Equations . 22 (4): 936–953 . doi : 10.1002/num.20129 . ISSN 0749-159X . S2CID 123145969 .
↑ Bigun, J. (2006). Vision with Direction . Springer. doi : 10.1007/b138918 . ISBN 978-3-540-27322-6。
↑ニューマン、マーク（2010）。ネットワーク入門。オックスフォード大学出版局。ISBN 978-0-19-920665-0。
↑ Yavari, R.; Cole, KD; Rao, PK (2020). "スペクトルグラフ理論を用いた計算熱伝達：定量的検証" . International Journal of Thermal Sciences . 153 106383. Bibcode : 2020IJTS..15306383C . doi : 10.1016/j.ijthermalsci.2020.106383 .
↑ Cole, KD; Riensche, A.; Rao, PK (2022). "Discrete Green's functions and spectral graph theory for computationally efficient thermal modeling" . International Journal of Heat and Mass Transfer . 183 122112. Bibcode : 2022IJHMT.18322112C . doi : 10.1016/j.ijheatmasstransfer.2021.122112 . S2CID 244652819 .
↑ブルバキ、ニコラ(2002) [1968]、『群とリー代数：第4章～第6章』、数学の基礎、アンドリュー・プレスリー訳、シュプリンガー、ISBN 978-3-540-69171-6

砂田哲也(2008). 「離散幾何解析」 .グラフ解析とその応用. 純粋数学シンポジウム論文集. 第 77巻. アメリカ数学会. pp. 51–86 . ISBN 978-0-8218-9384-5。

外部リンク

Ollivier, Yann (2004). 「グラフのスペクトルギャップ」。2007年5月23日にオリジナルからアーカイブされました。

[1] Leventhal, Daniel (2011年秋). 「画像処理」(PDF) .ワシントン大学. 2019年12月1日取得.

[crane13-2] Crane, K.; de Goes, F.; Desbrun, M.; Schröder, P. (2013). "離散外積分によるデジタル幾何処理" . ACM SIGGRAPH 2013 Courses . SIGGRAPH '13. Vol. 7. pp. 1– 126. doi : 10.1145/2504435.2504442 .

[reuter06-3] Reuter, M.; Biasotti, S.; Giorgi, D.; Patane, G.; Spagnuolo, M. (2009). "形状解析とセグメンテーションのための離散ラプラス・ベルトラミ演算子". Computers & Graphics . 33 (3): 381–390df. CiteSeerX 10.1.1.157.757 . doi : 10.1016/j.cag.2009.03.005 .

[forsyth03-4] Forsyth, DA; Ponce, J. (2003). "Computer Vision". Computers & Graphics . 33 (3): 381–390 . CiteSeerX 10.1.1.157.757 . doi : 10.1016/j.cag.2009.03.005 .

[5] Matthys, Don (2001年2月14日). "LoGフィルター" .マルケット大学. 2019年12月1日取得.

[Provatas_Elder_p.-6] Provatas, Nikolas; Elder, Ken (2010-10-13). Phase-Field Methods in Materials Science and Engineering (PDF) . Weinheim, Germany: Wiley-VCH Verlag GmbH & Co. KGaA. p. 219. doi : 10.1002/9783527631520 . ISBN 978-3-527-63152-0。

[OReilly2006-7] O'Reilly, H.; Beck, Jeffrey M. (2006). "3次元における大規模ステンシル離散ラプラシアン近似のファミリー" (PDF) . International Journal for Numerical Methods in Engineering : 1– 16.

[lin90-8] 1 2 Lindeberg, T.、「離散信号のためのスケール空間」、PAMI(12)、第3号、1990年3月、pp. 234–254。

[lin94-9] 1 2 3 Lindeberg, T., Scale-Space Theory in Computer Vision, Kluwer Academic Publishers, 1994 , ISBN 0-7923-9418-6。

[PatraKarttunen2006-10] Patra, Michael; Karttunen, Mikko (2006). "微分演算子に対する等方性離散化誤差を持つステンシル". Numerical Methods for Partial Differential Equations . 22 (4): 936–953 . doi : 10.1002/num.20129 . ISSN 0749-159X . S2CID 123145969 .

[bigun06vd-11] Bigun, J. (2006). Vision with Direction . Springer. doi : 10.1007/b138918 . ISBN 978-3-540-27322-6。

[12] ニューマン、マーク（2010）。ネットワーク入門。オックスフォード大学出版局。ISBN 978-0-19-920665-0。

[Yavari2020-13] Yavari, R.; Cole, KD; Rao, PK (2020). "スペクトルグラフ理論を用いた計算熱伝達：定量的検証" . International Journal of Thermal Sciences . 153 106383. Bibcode : 2020IJTS..15306383C . doi : 10.1016/j.ijthermalsci.2020.106383 .

[Cole2022-14] Cole, KD; Riensche, A.; Rao, PK (2022). "Discrete Green's functions and spectral graph theory for computationally efficient thermal modeling" . International Journal of Heat and Mass Transfer . 183 122112. Bibcode : 2022IJHMT.18322112C . doi : 10.1016/j.ijheatmasstransfer.2021.122112 . S2CID 244652819 .

[Bourbaki-15] ブルバキ、ニコラ(2002) [1968]、『群とリー代数：第4章～第6章』、数学の基礎、アンドリュー・プレスリー訳、シュプリンガー、ISBN 978-3-540-69171-6

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]。

[ 7 ]

[ 8 ]

[ 9 ]。

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

離散ラプラス演算子

定義

グラフ・ラプラシアン

メッシュラプラシアン

有限差分法

有限要素法

画像処理

演算子の離散化による実装

継続的な再構築による実装

スペクトラム

定理

離散熱方程式

平衡挙動

グリッド上の演算子の例

離散シュレーディンガー演算子

ADE分類

関連項目

参考文献

外部リンク

関連するトピック

ラプラス演算子

グラフ

離散グリッド

ラプラシアン行列