離散化

数学において、離散化 (discretization) 連続関数、モデル、変数、方程式を離散的な対応する物へ移す過程のこと。この過程は普通、それらをデジタルコンピュータ上での数値評価および実装に適したものにするために最初に行われるステップである。二分化 (dichotomization) は離散クラスの数が2である離散化の特別な場合であり、これにより連続変数を2値変数として近似することができる（2項分類のようにモデリングの目的で2分法を作成する）。 離散化は離散数学にも関係しており、グラニュラーコンピューティング（英語版）の重要な成分である。この文脈において、離散化は、複数の離散変数が集約されるもしくは複数の離散圏が融合する場合のときのように、変数もしくは圏のグラニュラリティの変更をさすこともある。 連続的なデータが離散化されるときは常にある程度の離散化誤差がある。目標は手元のモデル化の目的では無視できると考えられるレベルまでその量を減らすことである。 離散化と量子化 (quantization) という用語はしばしば同じ意味を持つが、必ずしも同じ意味というわけではない（具体的には2つの用語は意味領域を共有している）。離散化誤差と量子化誤差についても同様である。 離散化に関する数学的方法にはオイラー・丸山法（英語版）とゼロ次ホールド（英語版）がある。 離散化は連続微分方程式を数値解析に適した離散差分方程式に変換することにも関係する。 次に連続時間状態空間モデルを示す。 x ˙ ( t ) = A x ( t ) + B u ( t ) + w ( t ) {\displaystyle {\dot {\mathbf {x} }}(t)=\mathbf {A} \mathbf {x} (t)+\mathbf {B} \mathbf {u} (t)+\mathbf {w} (t)} y ( t ) = C x ( t ) + D u ( t ) + v ( t ) {\displaystyle \mathbf {y} (t)=\mathbf {C} \mathbf {x} (t)+\mathbf {D} \mathbf {u} (t)+\mathbf {v} (t)} ここで v と w はパワースペクトル密度を有する連続ゼロ平均ホワイトノイズ源である。 w ( t ) ∼ N ( 0 , Q ) {\displaystyle \mathbf {w} (t)\sim N(0,\mathbf {Q} )} v ( t ) ∼ N ( 0 , R ) {\displaystyle \mathbf {v} (t)\sim N(0,\mathbf {R} )} 入力 u に対するゼロ次ホールドとノイズ v に対する連続積分を仮定することで離散化することができる。 x [ k + 1 ] = A d x [ k ] + B d u [ k ] + w [ k ] {\displaystyle \mathbf {x} [k+1]=\mathbf {A} _{d}\mathbf {x} [k]+\mathbf {B} _{d}\mathbf {u} [k]+\mathbf {w} [k]} y [ k ] = C d x [ k ] + D d u [ k ] + v [ k ] {\displaystyle \mathbf {y} [k]=\mathbf {C} _{d}\mathbf {x} [k]+\mathbf {D} _{d}\mathbf {u} [k]+\mathbf {v} [k]} 共分散は以下となる。 w [ k ] ∼ N ( 0 , Q d ) {\displaystyle \mathbf {w} [k]\sim N(0,\mathbf {Q} _{d})} v [ k ] ∼ N ( 0 , R d ) {\displaystyle \mathbf {v} [k]\sim N(0,\mathbf {R} _{d})} ここで A d = e A T = L − 1 { ( s I − A ) − 1 } t = T {\displaystyle \mathbf {A} _{d}=e^{\mathbf {A} T}={\mathcal {L}}^{-1}\{(s\mathbf {I} -\mathbf {A} )^{-1}\}_{t=T}} B d = ( ∫ τ = 0 T e A τ d τ ) B = A − 1 ( A d − I ) B {\displaystyle \mathbf {B} _{d}=\left(\int _{\tau =0}^{T}e^{\mathbf {A} \tau }d\tau \right)\mathbf {B} =\mathbf {A} ^{-1}(\mathbf {A} _{d}-I)\mathbf {B} } （もし A {\displaystyle \mathbf {A} } が正則行列であれば） C d = C {\displaystyle \mathbf {C} _{d}=\mathbf {C} } D d = D {\displaystyle \mathbf {D} _{d}=\mathbf {D} } Q d = ∫ τ = 0 T e A τ Q e A ⊤ τ d τ {\displaystyle \mathbf {Q} _{d}=\int _{\tau =0}^{T}e^{\mathbf {A} \tau }\mathbf {Q} e^{\mathbf {A} ^{\top }\tau }d\tau } R d = 1 T R {\displaystyle \mathbf {R} _{d}={\frac {1}{T}}\mathbf {R} } である。 T {\displaystyle T}  はサンプル時間、 A ⊤ {\displaystyle \mathbf {A} ^{\top }}  は A {\displaystyle \mathbf {A} } 行列である。 1つのステップで Ad と Bd を計算するための巧妙な手段は次の特性を使うことである e [ A B 0 0 ] T = [ M 11 M 12 0 I ] {\displaystyle e^{{\begin{bmatrix}\mathbf {A} &\mathbf {B} \\\mathbf {0} &\mathbf {0} \end{bmatrix}}T}={\begin{bmatrix}\mathbf {M_{11}} &\mathbf {M_{12}} \\\mathbf {0} &\mathbf {I} \end{bmatrix}}} ここで A d = M 11 {\displaystyle \mathbf {A} _{d}=\mathbf {M} _{11}} B d = M 12 {\displaystyle \mathbf {B} _{d}=\mathbf {M} _{12}} Q d {\displaystyle \mathbf {Q} _{d}}  の数値評価は行列の指数積分を用いるためやや扱いにくい。しかし、はじめに行列を構築し、その指数関数を計算することにより処理することができる。 F = [ − A Q 0 A ⊤ ] T {\displaystyle \mathbf {F} ={\begin{bmatrix}-\mathbf {A} &\mathbf {Q} \\\mathbf {0} &\mathbf {A} ^{\top }\end{bmatrix}}T} G = e F = [ … A d − 1 Q d 0 A d ⊤ ] . {\displaystyle \mathbf {G} =e^{\mathbf {F} }={\begin{bmatrix}\dots &\mathbf {A} _{d}^{-1}\mathbf {Q} _{d}\\\mathbf {0} &\mathbf {A} _{d}^{\top }\end{bmatrix}}.} 離散化された駆動雑音は G の右下の区画の転置行列を G の右上の区画にかけあわせることで得られる。 Q d = ( A d ⊤ ) ⊤ ( A d − 1 Q d ) = A d ( A d − 1 Q d ) . {\displaystyle \mathbf {Q} _{d}=(\mathbf {A} _{d}^{\top })^{\top }(\mathbf {A} _{d}^{-1}\mathbf {Q} _{d})=\mathbf {A} _{d}(\mathbf {A} _{d}^{-1}\mathbf {Q} _{d}).} 連続モデルから始める x ˙ ( t ) = A x ( t ) + B u ( t ) {\displaystyle \mathbf {\dot {x}} (t)=\mathbf {A} \mathbf {x} (t)+\mathbf {B} \mathbf {u} (t)} 行列指数関数は以下のようであり d d t e A t = A e A t = e A t A {\displaystyle {\frac {d}{dt}}e^{\mathbf {A} t}=\mathbf {A} e^{\mathbf {A} t}=e^{\mathbf {A} t}\mathbf {A} } モデルを左から掛けることで以下の式を得る。 e − A t x ˙ ( t ) = e − A t A x ( t ) + e − A t B u ( t ) {\displaystyle e^{-\mathbf {A} t}\mathbf {\dot {x}} (t)=e^{-\mathbf {A} t}\mathbf {A} \mathbf {x} (t)+e^{-\mathbf {A} t}\mathbf {B} \mathbf {u} (t)} ここで d d t ( e − A t x ( t ) ) = e − A t B u ( t ) {\displaystyle {\frac {d}{dt}}(e^{-\mathbf {A} t}\mathbf {x} (t))=e^{-\mathbf {A} t}\mathbf {B} \mathbf {u} (t)} であり、積分することで e − A t x ( t ) − e 0 x ( 0 ) = ∫ 0 t e − A τ B u ( τ ) d τ {\displaystyle e^{-\mathbf {A} t}\mathbf {x} (t)-e^{0}\mathbf {x} (0)=\int _{0}^{t}e^{-\mathbf {A} \tau }\mathbf {B} \mathbf {u} (\tau )d\tau } x ( t ) = e A t x ( 0 ) + ∫ 0 t e A ( t − τ ) B u ( τ ) d τ {\displaystyle \mathbf {x} (t)=e^{\mathbf {A} t}\mathbf {x} (0)+\int _{0}^{t}e^{\mathbf {A} (t-\tau )}\mathbf {B} \mathbf {u} (\tau )d\tau } となる。これが連続モデルに対する解析的解法である。 ここで、上の式を離散する。各時間ステップの定数 u は一定とする。 x [ k ]   = d e f   x ( k T ) {\displaystyle \mathbf {x} [k]\ {\stackrel {\mathrm {def} }{=}}\ \mathbf {x} (kT)} x [ k ] = e A k T x ( 0 ) + ∫ 0 k T e A ( k T − τ ) B u ( τ ) d τ {\displaystyle \mathbf {x} [k]=e^{\mathbf {A} kT}\mathbf {x} (0)+\int _{0}^{kT}e^{\mathbf {A} (kT-\tau )}\mathbf {B} \mathbf {u} (\tau )d\tau } x [ k + 1 ] = e A ( k + 1 ) T x ( 0 ) + ∫ 0 ( k + 1 ) T e A ( ( k + 1 ) T − τ ) B u ( τ ) d τ {\displaystyle \mathbf {x} [k+1]=e^{\mathbf {A} (k+1)T}\mathbf {x} (0)+\int _{0}^{(k+1)T}e^{\mathbf {A} ((k+1)T-\tau )}\mathbf {B} \mathbf {u} (\tau )d\tau } x [ k + 1 ] = e A T [ e A k T x ( 0 ) + ∫ 0 k T e A ( k T − τ ) B u ( τ ) d τ ] + ∫ k T ( k + 1 ) T e A ( k T + T − τ ) B u ( τ ) d τ {\displaystyle \mathbf {x} [k+1]=e^{\mathbf {A} T}\left[e^{\mathbf {A} kT}\mathbf {x} (0)+\int _{0}^{kT}e^{\mathbf {A} (kT-\tau )}\mathbf {B} \mathbf {u} (\tau )d\tau \right]+\int _{kT}^{(k+1)T}e^{\mathbf {A} (kT+T-\tau )}\mathbf {B} \mathbf {u} (\tau )d\tau } これが x [ k ] {\displaystyle \mathbf {x} [k]} のカッコで囲まれた表現であり、第2項は関数  v ( τ ) = k T + T − τ {\displaystyle v(\tau )=kT+T-\tau } で置き換えることで簡略にすることができる。  d τ = − d v {\displaystyle d\tau =-dv} である。また、積分中、  u {\displaystyle \mathbf {u} }  が定数であるとすると次のようになる。 x [ k + 1 ] = e A T x [ k ] − ( ∫ v ( k T ) v ( ( k + 1 ) T ) e A v d v ) B u [ k ] = e A T x [ k ] − ( ∫ T 0 e A v d v ) B u [ k ] = e A T x [ k ] + ( ∫ 0 T e A v d v ) B u [ k ] = e A T x [ k ] + A − 1 ( e A T − I ) B u [ k ] {\displaystyle {\begin{matrix}\mathbf {x} [k+1]&=&e^{\mathbf {A} T}\mathbf {x} [k]-\left(\int _{v(kT)}^{v((k+1)T)}e^{\mathbf {A} v}dv\right)\mathbf {B} \mathbf {u} [k]\\&=&e^{\mathbf {A} T}\mathbf {x} [k]-\left(\int _{T}^{0}e^{\mathbf {A} v}dv\right)\mathbf {B} \mathbf {u} [k]\\&=&e^{\mathbf {A} T}\mathbf {x} [k]+\left(\int _{0}^{T}e^{\mathbf {A} v}dv\right)\mathbf {B} \mathbf {u} [k]\\&=&e^{\mathbf {A} T}\mathbf {x} [k]+\mathbf {A} ^{-1}\left(e^{\mathbf {A} T}-\mathbf {I} \right)\mathbf {B} \mathbf {u} [k]\end{matrix}}} これが離散化問題の厳密解である。 厳密な離散化には重い行列の指数関数や積分操作が含まれているため、処理が難しいことがある。小さな時間ステップに基づき、  e A T ≈ I + A T {\displaystyle e^{\mathbf {A} T}\approx \mathbf {I} +\mathbf {A} T} と近似した離散モデルで計算するほうがはるかに簡単である。近似解は以下のようになる。 x [ k + 1 ] ≈ ( I + A T ) x [ k ] + T B u [ k ] {\displaystyle \mathbf {x} [k+1]\approx (\mathbf {I} +\mathbf {A} T)\mathbf {x} [k]+T\mathbf {B} \mathbf {u} [k]} 他の可能な近似としては e A T ≈ ( I − A T ) − 1 {\displaystyle e^{\mathbf {A} T}\approx \left(\mathbf {I} -\mathbf {A} T\right)^{-1}}  や  e A T ≈ ( I + 1 2 A T ) ( I − 1 2 A T ) − 1 {\displaystyle e^{\mathbf {A} T}\approx \left(\mathbf {I} +{\frac {1}{2}}\mathbf {A} T\right)\left(\mathbf {I} -{\frac {1}{2}}\mathbf {A} T\right)^{-1}} がある。各々異なる安定特性を持っており、最後の近似は双一次変換やTustin変換と呼ばれ、連続時間系の安定性を持っている。 統計や機械学習において、離散化は連続特徴や変数を離散や名目特徴に変換する過程をさす。これは確率質量関数を作成する際に便利である。 離散空間 時間スケール微積分学 離散事象シミュレーション（英語版） 確率シミュレーション（英語版） 非定常流有限体積法（英語版） 離散時間と連続時間（英語版）