algorithm - 多項式の評価精度、乗算と除算

Question

x の累乗で割った x に多項式があるとします。

p = (a + x(b + x(c + ..)))/(x**n)

効率はさておき、これは数値的により正確な計算であり、上記または除算を使用します。

p = (((a/x + b)/x + c)/x + ...)

ありがとう

Answer 1

理論的には、値が「無限」の精度で正確に計算されている場合、違いはないはずです。

Kernighan と Plauger は、古いが優れた著書「Elements of Programming Style」で次のように述べています。

賢明なプログラマーはかつて、「浮動小数点数は小さな砂の山のようなものです。1 つを移動するたびに、少し砂が減り、少し汚れが増えます」と言いました。

この師団は全体的に操作数がわずかに少ないため、砂を失って汚れを得る機会がわずかに少なくなります。

詳細な分析では、おそらく係数 (a、b、c など) と x の値を確認する必要があります。x が大きい場合に機能することは、x がゼロに近い場合には機能しない可能性があり、その逆も同様です。

Answer 2

x**nオーバーフローまたはアンダーフローの可能性がない限り、違いは最小限だと思います。その場合は、2番目の式を使用する必要があります。

2つの式は2つの場所で異なります。

1. 評価の順序は、最初の式では逆になり（...、c、b、a）、2番目の式では（a、b、c、...）になります。どちらが最適かは、係数の値によって異なります。
2. 最初の式.../x**nの最後にがあります。ジョナサンが説明するように、そのため、2番目の式は操作が少ないため、より正確であると予想される場合があります。ただし、オーバーフローやアンダーフローが発生.../x**nしない限り、（精度が低下する他の場所と比較して）精度の低下はごくわずかであると思います。x**n

Answer 3

提供された回答は、残念ながら間違っています。

2 番目の方程式 p = (((a/x + b)/x + c)/x + ...) は、精度がわずかに悪く、速度がはるかに悪いです。

なんで ？乗算の相対誤差には、主要な線形項と小さな 2 次項のみがあります。対照的に除算では、より高いが非常に小さい項 (3 次、4 次) が導入されます。

e = 相対誤差、両方の項が一定であると仮定

a*b = a(1+e) b(1+e) = a b (1+2e+e^2) // 乗算

a/b = a(1+e)/b(1+e) = a/b (1+e)(1+e+e^2+e^3+...幾何級数) // 除算

したがって、除算は常に乗算よりも少し悪いです。速度に関する考慮事項: 除算は常に乗算よりも遅く、通常の係数は 3x ～ 10x の範囲で変化します。したがって、pow() ではなくネストされた乗算によって最後の因数 x^n を計算しない場合、ネストされた除算はネストされた乗算よりもはるかに遅くなります。

x^n は、結果の double power = x; を乗算するループによって簡単に計算できます。(n-1) 乗 *= x;

pow() を使用する場合は、ほとんどの場合、指数関数と対数によって便利に計算され、必要以上に (100 倍) 時間がかかることに注意してください。

double と正確な結果の間の誤差は小さいままですが、多項式の結果はn が大きくなると x の変化に非常に敏感になることをご存知ですか?! したがって、より高い n を使用する場合は、x の小さなエラーが天文学的に増幅されるため、答えが完全に的外れになる可能性があることに注意してください。