ORWiki - 利用者の投稿記録 [ja]

ガウス・ザイデル法

2007-07-11T08:30:12Z

131.112.125.102:

'''【がうすざいでるほう (Gauss-Seidel method)】'''

(線形)方程式系を数値的に解くための反復法の1つ. 例えば, <math>n \,</math> 次元ベクトル <math>\mathbf{b}=(b_1,\ldots,b_n) \,</math> と <math>n \,</math> 次の正方行列 <math>\mathbf{A}=( a_{ij} ) \,</math> に対して, <math>\mathbf{b}=\mathbf{x}\mathbf{A} \,</math> を満たす<math>\mathbf{x} =(x_1,\ldots,x_n) \,</math> を求める場合, 適当な <math>\mathbf{x}^{(0)} =(x_1^{(0)},\ldots,x_n^{(0)}) \,</math> から始めて

<math>
\displaystyle{ x_j^{(k)} = \frac{b_j - \sum_{i=1}^{j-1} x_i^{(k)} a_{ij}
- \sum_{i=j+1}^{n} x_i^{(k-1)} a_{ij}}{a_{jj}},}
\,</math>
<math>
\ \ \ \ \ j=1,\ldots,n
\, </math>

によって順次 <math>\mathbf{x}^{(k)} =(x_1^{(k)},\ldots,x_n^{(k)}) \,</math> を生成し, 収束した時点で <math>\mathbf{x}=\mathbf{x}^{(k)} \,</math> とする.

ガウス過程

2007-07-11T08:11:04Z

131.112.125.102:

'''【がうすかてい (Gaussian process)】'''

時間, 状態ともに連続な確率過程 <math>\{ X(t) \} \,</math> で, どのような時点の組 <math>(t_1, \ldots , t_n) \,</math> に対しても <math>(X(t_1), \cdots, X(t_n)) \,</math> の同時分布が<math>n \,</math> 次元正規分布となるもの.

階数関数

2007-07-11T08:06:51Z

131.112.125.102:

'''【かいすうかんすう (rank function)】'''

独立集合族<math>\mathcal{I} \,</math>をもつ<math>N \,</math>上のマトロイド <math>\mathbf{M}=(N,\mathcal{I}) \,</math> において, <math>\rho(X)=\max\{|I|\mid I\subseteq X,\, I \in\mathcal{I}\} \,</math> で定められる関数 <math>\rho:2^N\to \mathbf{Z} \,</math> を階数関数という. 階数関数 <math>\rho \,</math> は次の (R0)--(R3) を満たしている: (R0) <math>\rho(\emptyset)=0 \,</math>, (R1) <math>\forall X\subseteq N \,</math>: <math>\rho(X)\leq |X| \,</math>, (R2) <math>X\subseteq Y \Rightarrow \rho(X)\leq\rho(Y) \,</math>, (R3) <math>\forall X,Y\subseteq N \,</math>: <math>\rho(X)+\rho(Y)\geq\rho(X\cap Y)+\rho(X\cup Y) \,</math>. 逆に, (R0)-(R3) を満たす関数 <math>\rho \,</math> によってマトロイドを定義することもできる.

劣モジュラシステム

2007-07-11T08:00:22Z

131.112.125.102:

'''【れつもじゅらしすてむ (submodular system)】'''

有限集合 <math>N\,</math> の部分集合族 <math>\mathcal{D}\subseteq 2^{N}\,</math> に関して, <math>\emptyset,N\in \mathcal{D}\,</math> かつ <math>X,Y\in\mathcal{D}\Rightarrow X\cup Y, X\cap Y\in{\cal D}\,</math> が成り立つものとする. このとき, <math>{\cal D}\,</math> は分配束をなす. 劣モジュラ関数 <math>f:{\cal D}\to{\bf R}\,</math> が <math>f(\emptyset)=0\,</math> を満たすとき, <math>({\cal D},f)\,</math> を劣モジュラシステムという.

カーマーカー法

2007-07-11T07:56:09Z

131.112.125.102:

'''【かーまーかーほう (Karmarkar's algorithm)】'''

1984年にカーマーカーが提案した, 初めての内点法. 「<math>\mbox{min.} \ c^{\top}x \ \mbox{s. t.} \ Ax = 0, \ e^{\top}x = 1, \ x \geq 0 \,</math> (<math>A \,</math>は<math>m \times n \,</math>行列, <math>c \in \mathbf{R}^n \,</math>, <math>e \in \mathbf{R}^n \,</math>は要素がすべて<math>1 \,</math>のベクトル)」の線形計画問題に対して, 「(1) <math>A \,</math>の階数は<math>m \,</math>, (2)<math>A(e/n)=0 \,</math>, (iii)最適値は<math>0 \,</math>」の仮定の下で, 初期点 <math>x^0 =e/n \,</math> から最適解に収束する点列 <math>\{x^k: \ Ax^k=0, \ e^{\top}x =1, \ x^k > 0\} \,</math> を生成する多項式時間解法. 任意の線形計画問題から, 上記の仮定を満す人工問題が生成でき, 元の問題の最適性が判定できる.

カーネル (ゲーム理論における)

2007-07-11T07:52:34Z

131.112.125.102:

'''【かーねる (kernel)】'''

デイビス (M. Davis) とマシュラー (M. Maschler)が提唱した提携形ゲームの解概念で,配分<math>x=(x_1,x_2,...,x_n) \,</math>に対する提携<math>S \,</math>のもつ不満(超過要求)<math>e(S,x)=v(S) -\sum_{i \in S }x_i \,</math>に基づき定義される.2人のプレイヤー<math>i,j \,</math>について,

<math>
\max_{S: i \in S , j \in \!\!\!\backslash S} e(S,x) >
\max_{S: j \in S , i \in \!\!\!\backslash S} e(S,x) \,</math>
かつ

<math> x_j > v(\{ j \} )
\,</math>
が成り立つとき, 配分<math>x \,</math>において<math>i \,</math>は<math>j \,</math>より不満優位にあるという. いかなるぺアについても,互いに不満優位ではないような配分の集合をカーネルという.

オルンシュタイン・ウーレンベック過程

2007-07-11T07:50:58Z

131.112.125.102:

'''【おるんしゅたいんうーれんべっくかてい (Ornstein-Uhlenbeck process)】'''

<math>\{B(t)\}_{t\ge0} \,</math> をブラウン運動とするとき, ランジュバン (Langevin) の方程式と呼ばれる確率微分方程式~<math>\mathrm{d} U(t) = -\alpha\,U(t)\,\mathrm{d} t + \sigma\,\mathrm{d} B(t) \,</math>(<math>\alpha>0 \,</math>, <math>\sigma>0 \,</math>) の解

<math>
U(t) = \mathrm{e}^{-\alpha t}\,
\Bigl(U(0) + \sigma\int_0^t\mathrm{e}^{\alpha s}\,\mathrm{d} B(s)\Bigr)
\,</math>

によって表される確率過程~<math>\{U(t)\}_{t \ge 0} \,</math>. この確率過程は連続な標本路をもつマルコフ過程であり, <math>U(0)=x \,</math> のもとで正規型の定常分布~<math>\mbox{N}(x,\sigma^2/(2\,\alpha)) \,</math> をもつ.

重み最小三角形分割

2007-07-11T07:47:46Z

131.112.125.102:

'''【おもみさいしょうさんかくけいぶんかつ (minimum-weight triangulation)】'''

三角形分割の辺長の総和を最小にするものを, 重み最小三角形分割と呼ぶ. この問題の計算量クラスについてはまだよくわかっていない. 2次元の場合実用的に大規模な問題が解けるLMT--スケルトン法などが知られている. 点集合が凸 <math>n \,</math>角形の頂点集合の場合, 重み最小問題は動的計画法によって<math>{\rm O}(n^3) \,</math>時間で解ける. 整数計画によるアプローチもある.

L凸関数

2007-07-11T07:43:55Z

131.112.125.102:

'''【えるとつかんすう (L-convex function)】'''

[[ スタイル検討 ]]


整数格子点上で定義された関数

<math>g: \mathbf{Z} \sp{n} \to \mathbf{R} \cup \{ +\infty \} \,</math> が2条件:

<math>
\begin{array}{l}
g(p) + g(q) \geq g(p \vee q) + g(p \wedge q),
\: p, q \in {\bf Z}\sp{n}, \\
\exists r \in {\bf R}, \forall p \in {\bf Z}\sp{n}: \
g(p+{\bf 1}) = g(p) + r,
\end{array}
\,</math>

を満たすとき, L凸関数という. ここで, <math>p \vee q \,</math>, <math>p \wedge q \,</math>は, それぞれ, 成分毎に最大値, 最小値をとって得られるベクトル(\sloppy すなわち, <math>(p \vee q)_{i} = \max(p_{i}, q_{i}) \,</math>, <math>(p \wedge q)_{i} = \min(p_{i}, q_{i}) \,</math>)を表し, また, <math>{\bf 1}=(1,1,\ldots,1) \in {\bf Z}\sp{n} \,</math>である.

エルゴード的マルコフ連鎖

2007-07-11T07:37:53Z

131.112.125.102:

'''【えるごーどてきまるこふれんさ (ergodic Markov chain)】'''

既約で非周期的, 正再帰的なマルコフ連鎖のこと. 状態数が有限であれば, 既約ならば必ず正再帰的であるし, 連続時間マルコフ連鎖ならば必ず非周期的であるので, それぞれの条件は不要となる. エルゴード的マルコフ連鎖ではエルゴード定理が成り立ち, 定常分布が存在する. さらにどのような初期分布から出発しても, 時刻 <math>t \,</math> における分布は <math>t \to \infty \,</math> のとき定常分布に収束する.

エルゴード定理

2007-07-11T07:34:39Z

131.112.125.102:

'''【えるごーどていり (ergodic theorem)】'''

定常な離散時間確率過程 <math>\{ X_n \} \, </math>が有限な平均値をもつならば, 確率1で

<math>
\lim_{n\rightarrow\infty} \frac{1}{n} \sum_{i=1}^n X_i = \mbox{E}(X_1|\mathcal{G})
\,</math>

が成り立つ.
ここで,

<math>\mathcal{G} \, </math>は <math>\{ X_n \} \, </math> のずらしに関する不変事象の <math>\sigma \, </math>-集合体である. この結果を, (離散時間)エルゴード定理と呼ぶ. 特に、 <math>\{ X_n\} \, </math> がエルゴード的ならば右辺は <math>\mbox{E}(X_1) \, </math> となる。連続時間確率過程についても同様である。

エラーバウンド (数理計画における)

2007-07-11T07:31:22Z

131.112.125.102:

'''【えらーばうんど (error bound)】'''

数理計画問題に対して, 次の条件を満たす実数値関数 <math>r \,</math> と定数 <math>c>0 \,</math> が存在するとき, <math>r \,</math> をエラーバウンドと呼ぶ.

<math> \mathrm{dist} \, (x,S^*) \le c \, r(x) \quad \forall \, x \,</math>

ここで, <math>\mathrm{dist} \, (x, S^*) \,</math> は点 <math>x \,</math> と問題の解集合 <math>S^* \,</math> の距離を表す. エラーバウンドは反復法における収束判定条件の設定や反復法の収束性, 特に収束率の解析等において重要な役割を果たす.

M凸関数

2007-07-11T07:27:08Z

131.112.125.102:

'''【えむとつかんすう (M-convex function)】'''

[[ スタイル検討 ]]


整数格子点上で定義された関数
<math>f: {\bf Z}\sp{n} \to {\bf R} \cup \{ +\infty \}\,</math>が交換公理:
\begin{quote}
<math>f(x)\,</math>, <math>f(y)\,</math>が有限値であるような任意の <math>x, y \in {\bf Z}\sp{n}\,</math> と, <math>x_{i}>y_{i}\,</math>であるような任意の <math>i \,</math>
<math>(1 \leq i \leq n)\,</math> に対して, ある<math>j\,</math> <math>(1 \leq j \leq n)\,</math> が存在して, <math>x_{j}<y_{j}\,</math> かつ

<math>
\begin{array}{l}
f(x)+f(y) \geq \\
\ \ \ \ f(x-\chi_{i}+\chi_{j}) + f(y+\chi_{i}-\chi_{j})
\end{array}
\,</math>
\end{quote}

を満たすとき, M凸関数という. ここで, <math>\chi_{i}\,</math>は第<math>i\,</math>単位ベクトルである.

M凸関数

2007-07-11T07:25:12Z

131.112.125.102:

'''【えむとつかんすう (M-convex function)】'''

[[ スタイル検討 ]]

整数格子点上で定義された関数
<math>f: {\bf Z}\sp{n} \to {\bf R} \cup \{ +\infty \}\,</math>が交換公理:
\begin{quote}
<math>f(x)\,</math>, <math>f(y)\,</math>が有限値であるような任意の <math>x, y \in {\bf Z}\sp{n}\,</math> と, <math>x_{i}>y_{i}\,</math>であるような任意の <math>i \,</math>
<math>(1 \leq i \leq n)\,</math> に対して, ある<math>j\,</math> <math>(1 \leq j \leq n)\,</math> が存在して, <math>x_{j}<y_{j}\,</math> かつ

<math>
\begin{array}{l}
f(x)+f(y) \geq \\
\ \ \ \ f(x-\chi_{i}+\chi_{j}) + f(y+\chi_{i}-\chi_{j})
\end{array}
\,</math>
\end{quote}

を満たすとき, M凸関数という. ここで, <math>\chi_{i}\,</math>は第<math>i\,</math>単位ベクトルである.

MTTF

2007-07-11T06:58:38Z

131.112.125.102:

'''【えむてぃーてぃーえふ (MTTF (mean time to failure))】'''

MTTF(平均故障寿命) は JIS Z 8115 信頼性用語により, 「非修理アイテムの故障寿命の平均値」と定義され, システムの寿命特性を示す尺度の1つである. 故障寿命が連続型確率変数のときには, 故障寿命 <math>T \,</math> <math>(T \geq 0) \,</math> の平均 (期待値) <math>\mbox{E}[T] \,</math>, すなわち MTTF は, 確率密度関数 <math>f(t) \,</math> <math>(t \geq 0) \,</math> および信頼度 <math>R(t)=\int_t^\infty f(x) {\rm d}x \,</math> より,

<math>
{\rm MTTF} =\mbox{E}[T] = \int_0^\infty tf(t) {\rm d}t = \int_0^\infty R(t) {\rm d}t
\,</math>

と与えられる.

NBU

2007-07-11T06:53:13Z

131.112.125.102:

'''【えぬびぃーゆー (NBU (new better than used))】'''

寿命分布を <math>F(t) \; (t\ge0) \,</math>, その信頼度関数を <math>R(t)=1-F(t) \,</math> とする. 任意の <math>x, y \,</math> について <math>R(x+y) \le R(x)R(y) \,</math> ならば, 寿命分布は NBU, <math>R(x+y) \ge R(x)R(y) \,</math> ならば, 寿命分布は NWU (new worse than used) と呼ばれる.

(s,S)方策

2007-07-11T06:50:34Z

131.112.125.102:

'''【えすえすほうさく (<math>(s,S)\, </math> policy)】'''

在庫管理方式の一種. 在庫状況が時間軸上連続的に調査がされる前提下で, 現在の在庫量<math>x \,</math>が発注点<math>s \,</math>を下回ったときに, 補充点<math>S \,</math>(<math>S>s \,</math>)と現在の在庫量との差<math>(S-x) \,</math>を発注する方策.

AVL木

2007-07-11T06:47:19Z

131.112.125.102:

'''【えいぶいえるぎ (AVL (Adelson-Velskii and Landis) tree)】'''

平衡二分探索木の一種. 任意の頂点に対し, 片方の子供を根とする部分木の高さが, もう片方の子供のものと高々1しか違わないという条件を満たす. AVL は提案者である2人のロシア人アデルソンヴェルスキとランディスの頭文字. 木に対して変更が行われたとき, 回転 (rotation) と呼ばれる操作を連続して行い, 条件を満たすように木を変形する. これにより, 要素の挿入・削除・ある要素が含まれるかの確認を <math>O(\log n) \,</math> の時間で行うことができる.

影響力係数

2007-07-11T06:45:24Z

131.112.125.102:

'''【えいきょうりょくけいすう (power of dispersion)】'''

<math>A \,</math>を産業連関表の投入係数表とする. このとき, レオンティエフ逆行列<math>B=(I-A)^{-1} \,</math>の1つの列(<math>j \,</math>部門)の和はその列に対応する産業の需要に1単位の変化があった場合の, 全産業への影響を表していると考えることができる. そこで次式を<math>j \,</math>部門の影響力係数と呼んでいる.

<math>
\displaystyle \left. \sum_{i=1}^{n}b_{i,j} \right/
\displaystyle \sum_{i=1}^{n}\sum_{j=1}^{n}b_{i,j}
\,</math>

ウィーナー・ホップの方程式

2007-07-11T06:38:55Z

131.112.125.102:

'''【うぃーなーほっぷのほうていしき (Wiener-Hopf's integral equation)】'''

未知関数 <math>\varphi(t) \,</math> <math>(0 \leq t < +\infty) \,</math> の次の積分方程式を, ウィーナー・ホップの方程式という.

<math>
\varphi(t) = f(t) +\int_{0-}^{\infty} K(t-x) \varphi(x) \mathrm{d} x
\,</math>

ただし, 既知関数 <math>f(t) \,</math> <math>(0 \leq t < +\infty) \,</math> と核関数 (kernel function) <math>K(t) \,</math> <math>(-\infty < t < +\infty) \,</math> は, 連続である. ここで <math>f(t) \neq 0 \,</math> のとき非同次 (non-homogeneous), <math>f(t) = 0 \,</math> のとき同次 (homogeneous) の方程式という.

Ε-近似アルゴリズム

2007-07-11T06:35:08Z

131.112.125.102:

'''【いぷしろんきんじあるごりずむ (ε-approximation algorithm)】'''

最適化問題の近似解を求める近似アルゴリズムについて, 目的関数(適応度関数)を<math>f(x) \,</math>, 最適解を<math>x^* \,</math>, また近似アルゴリズムによって得られる近似解を<math>\widehat{x} \,</math>としたとき, どのような問題例であっても

<math>
\frac{|f(\widehat{x})-f(x^*)|}{f(x^*)} \leq \varepsilon
\,</math>

を満たすものを<math>\varepsilon \,</math>-近似アルゴリズムという. ただし, <math>f(x^*)>0 \,</math>を仮定しており, <math>0\leq \varepsilon \,</math>である. <math>\varepsilon \,</math>が<math>0 \,</math>に近いほど精度の高い近似アルゴリズムとなる.

移動平均モデル

2007-07-11T06:30:19Z

131.112.125.102:

'''【いどうへいきんもでる (moving average (MA) model)】'''

<math>x_{t} \,</math> を <math>\mbox{E}(x_{t})=0 \,</math> の弱定常過程とし, <math>\varepsilon_{t} \,</math> を <math>\mbox{E}(\varepsilon_{t})=0 \,</math>, <math>\mbox{V}(\varepsilon_{t})=\sigma^{2} \,</math>, <math>\mbox{E}(\varepsilon_{t}\varepsilon_{s})=0 \,</math> <math>(t \ne s) \,</math>のホワイトノイズとする. <math>x_{t} \,</math> が<math>x_{t}=\varepsilon_{t}+\theta_{1}\varepsilon_{t-1}+\cdots+\theta_{q}\varepsilon_{t-q} \,</math> と表現できるとき, このモデルを次数 <math>q \,</math> の移動平均モデルと呼び, <math>MA(q) \,</math> モデルと略記する. 移動平均モデルは定常過程の理論的性質を調べる上で重要な役割を果たすモデルである.

伊藤の補題

2007-07-11T06:27:10Z

131.112.125.102:

'''【いとうのほだい (Itôs lemma)】'''

拡散過程<math>X_t \,</math>の微小時間<math>dt \,</math>での平均が<math>\mu (t, X_t) {\mbox{d}}t \,</math>, 分散が<math>\sigma^2 (t,X_t) {\mbox{d}}t \,</math>で与えられるとき, 確率微分方程式では<math>{\mbox{d}}X_t=\mu(t,X_t){\mbox{d}}t +\sigma (t,X_t) {\mbox{d}}B_t \,</math>と表現する. ここで<math>B_t \,</math>はブラウン運動である. さらに<math>Y_t=g(t,X_t) \,</math>と変換すると, <math>Y_t \,</math>は伊藤の補題により,

<math> \mbox{d}Y_t = g_t(t, X_t) \mbox{d}t + g_x(t, X_t) \mbox{d}X_t

+ (1/2)g_{xx}(t, X_t)(\mbox{d} X_t)^2 \,</math>
を満たす.

ただし<math>({\mbox{d}}X_t)^2 \,</math>は, 計算規則

<math> {\mbox{d}}t \cdot {\mbox{d}}t = {\mbox{d}}t \cdot {\mbox{d}}B_t = {\mbox{d}}B_t \cdot {\mbox{d}}t = 0, \ \ {\mbox{d}}B_t \cdot {\mbox{d}}B_t={\mbox{d}}t \,</math>

により与えられる.

伊藤過程

2007-07-11T06:13:28Z

131.112.125.102:

'''【いとうかてい (Itô process)】'''

<math>\{B(t)\}_{t\ge0} \,</math> をブラウン運動, <math>\{\Phi(t)\}_{t\ge0} \,</math>, <math>\{\Psi(t)\}_{t\ge0} \,</math> をそれぞれ,

<math>
\begin{array}{ll}
\displaystyle{\mathrm{E}\Bigl( \int_0^t\Phi(s)^2\, \mathrm{d} s \Bigr) <\infty}, & t>0, \\
\displaystyle{\mathrm{E}\Bigl( \int_0^t\Psi(s)\,\mathrm{d} s \Bigr) <\infty}, & t>0,
\end{array}
\,</math>

を満たす確率過程としたとき,

<math>
X(t)
= X(0) + \int_0^t \Phi(s)\, \mathrm{d} B(s)
+ \int_0^t \Psi(s)\, \mathrm{d} s
\,</math>

と表される確率過程.