-1

理論的にはまったく同じ出力を返すはずの 2 つのコードがあります。ただし、これは起こりません。問題は、2 つのコードが 1e-100 程度の非常に小さな数値 (double) を処理することです。それに関連するいくつかの数値的な問題があり、理論的には同じであるはずの 2 つの出力が異なる可能性があると思います。

1e-100 程度の数値を扱うと、このような問題が発生するというのは本当に理にかなっていますか? ソースが数値の問題であると安全に想定できるのであれば、出力の違いは気にしません。このような順序で数値を処理するときにアルゴリズムの安定性に発生する問題について話している良いソース/リファレンスを誰かが持っていますか?

ありがとう。

4

3 に答える 3

1

このような順序で数値を処理するときにアルゴリズムの安定性に発生する問題について話している良いソース/リファレンスを誰かが持っていますか?

頭に浮かぶ最初の参考文献はWhat Every Computer Scientist Should Know About Floating-Point Arithmeticです。浮動小数点演算全般をカバーしています。

数値安定性に関する限り、最良の参考文献はおそらく問題の数値アルゴリズムに依存します。頭に浮かぶ2つの幅広い作品は次のとおりです。

于 2012-05-02T19:10:09.490 に答える
0

問題を引き起こしているのは、必ずしも数が少ないことではありません。

出力が「まったく同じ」かどうかをどのように確認しますか?

私は寛容で平等をチェックします。または のいずれかが成立する場合、浮動小数点数xとy等しいと見なすことができます。fabs(x-y) < 1.0e-6fabs(x-y) < fabs(x)*1.0e-6

通常、数値の問題がある場合、2 つのアルゴリズムには大きな違いがあります。アルゴリズムに数値的な問題がある場合、入力の小さな変化が出力の極端な変化につながることがよくあります。

「数字の問題」があると思う根拠は何ですか？

于 2012-05-02T20:03:47.383 に答える
0

可能であれば、アルゴリズムを変更して Kahan Summation (補償された合計) を使用します。ウィキペディアから:

function KahanSum(input)
    var sum = 0.0
    var c = 0.0          //A running compensation for lost low-order bits.
    for i = 1 to input.length do
        y = input[i] - c    //So far, so good: c is zero.
        t = sum + y         //Alas, sum is big, y small, so low-order digits of y are lost.
        c = (t - sum) - y   //(t - sum) recovers the high-order part of y; subtracting y recovers -(low part of y)
        sum = t             //Algebraically, c should always be zero. Beware eagerly optimising compilers!
        //Next time around, the lost low part will be added to y in a fresh attempt.
    return sum

これは、ブレゼンハムの線画アルゴリズムと同様に、累積誤差の 2 番目の実行中の合計を保持することによって機能します。最終結果は、データ型の公示精度のほぼ 2 倍の精度を取得することです。

私が使用するもう 1 つの手法は、数字を小さいものから大きいものへ (符号を無視してマニチュードで) 並べ替え、最初に小さい数字を加算または減算し、次に大きい数字を加算または減算することです。これには、同じ値を複数回加算および減算すると、そのような数値が完全にキャンセルされ、リストから削除される可能性があるという利点があります。

于 2012-10-01T22:03:14.533 に答える