カハンの加算アルゴリズムが最強な件(修正版)

いつものように，流体や機械学習の数値計算のプログラミングを書いているときの話である．

実行中，数値計算が破綻していることに気がついた．

検証の結果，約数千の数値の総和をとるコードの誤差が異常に大きくなることを発見した．

これは，数値の大きさに幅があり，大きい数値が小さい数値の精度を奪ってしまうことに基づく．

すなわち，

1+0.0000000001+0.0000000001+…(1000000000回)..+0.000000001

が，１になってしまうのと同様の現象である（本来は２が正しいが，精度の問題で1+0.0000000001=1となるため）．

この誤差をどうにかできないかと調べた結果，有名な方法があるらしい（知らなかった）．

それは，カハンの加算アルゴリズムである．

カハンの方法では，誤差を保持することにより，総和による誤差の累積を防ぐようになっている．

擬似コードは以下．

</p>
<p>ARR = 総和を求めたい数値の列<br />
SUM = 0　//総和<br />
ERR = 0　//誤差<br />
for num in ARR:<br />
    y = num &#8211; ERR　//誤差の反映<br />
    t = SUM + y  //試しに加算<br />
    ERR = (t &#8211; SUM) &#8211; y  //誤差の算出<br />
    SUM = t<br />

このように，ある計算を行いたい場合，適切なアルゴリズムを用いるなど，十分な精度を持つ方法で実装を行う必要がある．

そうでないと，数値計算で特異な現象を発見したと思ったら，じつは計算誤差のせいでしたということになりかねない（というか，よくなる）．

数値計算についてもっと学ばなければいけないと思った．

Posted on: 2016年4月3日, by : UMU
Exit mobile version