誰よりも速くNumpy数値計算のコードを最適化しろ！

• Python 3.8.2
• numpy 1.18.2
• ipython 7.13.0 （計測用）

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

ヤコビ法(Jacobi Method)は対称な行列の固有値と固有ベクトルを求める(固有値問題を解く)方法。線形方程式の反復解法としてのヤコビ法もあるがここでのヤコビ法はそっちのヤコビ法じゃない。

\(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\)の解であることは前のページで説明した。

\(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}\]

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