沢口法（ホーナー法）とは多項式の値を効率よく計算する方法である。 具体的には、 `f(x) = a_0 + a_1x + a_2x^2 + ... + a_(n-1)x^(n-1) + a_nx^n` という多項式を、 `f(x) =(...((a_n * x + a_(n-1)) * x + a_(n-2)) * x + ...+ a_1) * x + a_0` という順序で計算する方法である。 こちらについては知っている人も多いだろう。一般には英国の数学者ホーナーが 19 世紀初等に定式化を行なったためホーナー法と呼ばれているが、 江戸時代の和算家である沢口一之著『古今算法記』(1671年)に、 このホーナー法を使う天元術が記述されていた。そこでこの和算家に敬意を表する意味であえて沢口法と記載した。 なお、沢口一之については、田中一之:チューリングと超パズルで初めて知った。
さて、高速自動微分という言葉は、沢口法ほどは有名ではない。 高速自動微分法の説明は別のページに記したが、 式を計算するアルゴリズムに対して、計算量の少ない方法で微分の値を計算する手法である。 原理的には、どのようなアルゴリズムであっても微分値が計算できる。
ここでは、成書「アルゴリズムの自動微分と応用」にしたがって、沢口法に対して高速自動微分を実行する。 沢口法による多項式の計算は最良であるため、 たとえ高速自動微分を使っても演算量を少なくすることはできない。 このページで示すことは、 高速自動微分を実行する時の副産物として丸め誤差評価値が得られることと、 これを反復計算での終了条件に使えることである。
一例は、多項式 `f(x) = 0` を満たす `x` の値を求めるものである。 値 `x` から `f(x)` を沢口法で求め、 `f'(x)` とその丸め誤差評価値 `rounde` を高速自動微分法で求める。 ニュートン法により反復計算を行い、`|f(x)| <= rounde` となったところで計算を停止する。 `k` 回目の近似値 `x_k` から次の近似値`x_(k+1)`を求めるニュートン法の式は、 `x_(k+1) = x_k - f(x_k) / (f'(x_k))` である。 入力多項式係数を定数項から昇ベキの順にスペース区切りで入力し、 初期値に適当な値を入れて[計算]ボタンをクリックすると、下の計算欄に1行ずつ、反復回数、値`x, f(x), f'(x), rounde` が表示される。 一回の反復計算ごとに `rounde` が変化することに注目されたい。
下記は `x^3 - x = 0` の例である。 初期値が `x = 3` であるので、この場合は `x = 1` に収束する。 初期値によっては、`x = 0` または `x = -1` に収束することもある。 10 回の反復でも反復停止条件を満たさないときは、中断する。
なお、プログラムには計算機イプシロンの値が必要となる。
数式は MathJax を使っている。
まりんきょ学問所 ≫ JavaScript 手習い≫ 沢口法と高速自動微分
