【Python】5000×5000直交行列の対角化【線形代数】

巨大なランダム直交行列

各成分が $[-1/2,1/2]$ の一様乱数で決定される5000×5000行列を近似的に対角化してみた。

手法

規格化したベクトルを用意し、各成分が $e^{i\theta}$ という位相だけを持つとして、 $\theta$ をモンテカルロ法により最適化し、対角化を行った。

プログラム

github.com

gistc1a016e8bd86d10e898655f2ac6a979f

結果

行列が大きくなると、適当に作った固有ベクトルでも、偶然固有ベクトルに一致する個数の期待値が上がる。そのため、今回のようなかなり雑な近似でも良い結果が得られる。

固有ベクトルの誤差の期待値は、 $\frac{|Av/||Av||-v|}{5000}\approx 0.0181$ で、平均の直交すべきベクトルの内積の値は、 $5.0967\times10^{-6}$ であった。肝心の計算時間は、対角化自体は12秒。誤差のチェックに1分40秒、直交性のチェックに5分25秒で、残りの下準備の計算時間も合わせて、合計7分48秒となった。