/

ハウスホルダ―変換(Householder transform)は繰り返し繰り返すことで対称行列を三重対角行列に、また非対称行列をヘッセンベルク行列に変換する相似変換の一種。相似変換は行列の固有値を変えないので、主に行列の固有値を求める問題で利用される。

/

\(n\times n\)の正定値対象行列\(A\)\(x\in\mathbb{R}^n\)\(b\in\mathbb{R}^n\)について関数

\[ f(x)=\frac12x^\mathrm{T}Ax-b^\mathrm{T}x\tag{1}\]

を反復法によって最小化するとき、互いに\(A\)共役な方向について探索を行えば高々\(n\)回の反復で最小値に収束する。このときの\(x\)が線形方程式\(Ax=b\)の解であることは前のページで説明した。

/

確率分布\(f(x)\)に従う乱数を生成したいとする。このとき、次のように一様乱数を用いて目的の乱数を生成する方法を棄却法という。

  1. \(u_1\)\(f(x)\)の定義域\([a,b]\)上の一様分布とする。
  2. \(u_2\)\(f(x)\)の値域\([0,c]\)上の一様分布とする。
  3. \(u_2\lt f(u_1)\)でなければ棄却して以上の手順を繰り返し行う。
  4. \(u_1,u_2\)が上の条件を満たしたとき\(u_1\)を生成した乱数\(x\)とする。

棄却法ではこのようにして条件を満たすまで何度も一様分布に従う乱数を生成する。直観的にも採用された乱数列は目的の確率分布\(f(x)\)に従う。

/

\(U\)を一様分布\(U(0,1)\)に従う乱数とする。このとき、ある確率密度関数\(f(x)\)に対する累積分布関数\(F(x)\)の逆関数\(F^{-1}\)を用いて、乱数\(X\)\(X=F^{-1}(U)\)と定義すると\(X\)は分布\(f(x)\)に従う。

/

\(A\)\(n\times n\)の正方行列で正定値対称行列とする。\(x\in\mathbb{R}^n\)を変数ベクトル、\(b\in\mathbb{R}^n\)を定数ベクトルとする線形方程式

\[ Ax=b\tag{1}\]

は共役勾配法(Conjugate Gradient Method: CG法)によって解くことができる。共役勾配法ではまず、この問題を次の関数\(f(x)\)の最小化問題に取り換える。

\[ f(x)=\frac12x^\mathrm{T}Ax-b^\mathrm{T}x\tag{2}\]

このページではこの部分について詳細に説明する。