1

次の計算で数値浮動小数点エラーを減らしたいと思います。

次の形式の方程式があります。

b_3+w_3*(b_2+w_2*(b_1+w_1*(b_0+w_0)))

ここで、変数wは範囲内の浮動小数点数[0,1]をb表し、範囲内の浮動小数点定数を表します[1,~1000000]。b添え字で単調に増加します (これは重要ではないかもしれませんが)。当然、これは任意の数の用語に拡張できます。

b_4+w_4*(c_3+w_3*(b_2+w_2*(b_1+w_1*(b_0+w_0))))

これは次のように再帰的に定義できます。

func(x,n):
   if(n==MAX)
      return x
   else
      return func(b[n]+x*w[n],n+1)

func(1,0)

もし私がオンラインの総和を行っていたなら、Kahan Summation Algorithm (Kahan 1965)、または Higham 1993 や McNamee 2004 などのいくつかの他の方法の 1 つを使用して、エラーのサイズを制限することができました。もし私がオンラインで反復積を行っていたら、ある種の変換技術を使って問題を総和に減らすことができました。

現状では、この特定の問題にアプローチする方法がわかりません。誰かが考えを持っていますか（そしてそれらと一緒に引用されていますか）？

ありがとう！

Higham 1993.「浮動小数点合計の精度」。サイエンティフィック コンピューティングに関する SIAM ジャーナル。

Kahan 1965年。CACM。「10.1145/363707.363723」。

McNamee 2004年。「正確な合計のための方法の比較」。SIGSAMブル。「10.1145/980175.980177」。

4

2 に答える 2

3

計算はホーナー スキームに似ていますが、単一の変数 x の代わりに、各段階で異なる重み w[i] が使用される点が異なります。

補償されたホーナースキームのアルゴリズムがあり、目的に合わせて適応できると思います。たとえば、次の論文の定理 3 とアルゴリズム 2 を参照してください。

P. Langlois 著、補正ホーナー アルゴリズムを使用して忠実な多項式評価を保証する方法。コンピュータ演算に関する第 18 回 IEEE シンポジウム、2007 年 6 月 25 ～ 27 日、ARITH '07、pp. 141-149、 http: //www.acsel-lab.com/arithmetic/papers/ARITH18/ARITH18_Langlois.pdf

アルゴリズム 2 で TwoProd (s[i+1], x) を TwoProd (s[i+1], w[i+1]) に置き換えると、目的の結果が得られるように見えますが、試したことはありません。

于 2012-06-12T03:29:19.580 に答える
0

を定義funcした方法では、次の式に評価されます。

For MAX = n+1, func(1,0) ==

     n     n
   \---  -----
1 + >     | |  w[j]
   /---   | | 
    i=0  j=n-i

したがって、合計を解決する方法は次のようになります。

double s = 0.0;
double a = 1.0;
for (int i = 1; i <= MAX; ++i) {
    a *= w[MAX-i];
    s += a;
}
return 1.0 + s;

x入力値を変数として扱ってもfunc、最終項にしか影響しません。ただし、範囲が広いため、計算には注意が必要です。

double s = 0.0;
double a = 1.0;
double ax = x;
for (int i = 1; i < MAX; ++i) {
    a *= w[MAX-i];
    ax *= w[MAX-i];
    s += a;
}
ax *= w[0];
s += ax;
return 1.0 + s;
于 2012-06-12T02:43:37.720 に答える