精度の低下を避けるための最適なアルゴリズムは?

StackOverflow https://stackoverflow.com/questions/502122

  •  20-08-2019
  •  | 
  •  

質問

私が最近受け取った宿題では、コンピュータで実行すると精度が失われる可能性がある表現を取り上げ、この損失が回避されるように変更するように求められています。

残念ながら、これを行うための指示はあまり明確になっていません。実行されているさまざまな例を観察したところ、これを行うには特定の方法があることがわかりました。テイラー級数を使用したり、平方根が関係する場合は共役を使用したり、2 つの分数が引き算される場合に共通の分母を見つけたりします。

ただし、精度の低下がいつ発生するかを正確に認識するのに苦労しています。これまでのところ、私が確かに知っている唯一のことは、同じに近い 2 つの数値を減算すると、上位の桁が重要であるため精度の低下が発生し、四捨五入により上位の桁が失われるということです。

私の質問は、他にどのような一般的な状況に注意する必要があるのか​​、また、それらに対処するための「良い」方法は何であると考えられるのかということです。

たとえば、次のような問題があります。

f(x) = tan(x) − sin(x)  when x ~ 0

これを評価するための最適なアルゴリズムと最悪のアルゴリズムは次の 3 つの選択肢のうちどれですか:

(a) (1/ cos(x) − 1) sin(x),
(b) (x^3)/2
(c) tan(x)*(sin(x)^2)/(cos(x) + 1).

x がゼロに近い場合、tan(x) と sin(x) はほぼ同じになることがわかりました。これらのアルゴリズムが問題を解決するのにどのように、またなぜ優れているのか、劣っているのか、私にはわかりません。

役に立ちましたか？

解決

通常使用される親指のもう一つのルールはこれです：数字の長いシリーズを追加する場合は、ゼロと最大の数字で終わりに近い数字から追加を開始します。

。

これは良いですが、なぜ説明することはabitは注意が必要です。あなたが大量に小さな数字を追加しているとき、彼らは多数の現在の仮数で最も低い数字よりも小さいので、彼らは完全に破棄されます可能性があります。例えば、このような状況を取るます：

a = 1,000,000;
do 100,000,000 time:
   a += 0.01;
0.01最低の仮数の桁よりも小さい場合、

、その後、ループは何もせず、最終結果は== 1,000,000あります しかし、あなたはこのようにこれを行う場合：

a = 0;
do 100,000,000 time:
   a += 0.01;
a += 1,000,000;

低数よりもゆっくりと成長し、あなたは正しい答えです== 2,000,000に近いものになってしまう可能性が高くなります。
これは、ofcourseの極端な例ですが、私はあなたのアイデアを得る願っています。

他のヒント

私は学部時代に数値の授業を受けなければならなかったのですが、とても苦痛でした。とにかく、 IEEE 754 これは、最新の CPU によって通常実装される浮動小数点標準です。基本を理解すると、何をしてはいけないのかについて多くの直感が得られるため、役に立ちます。これを簡単に説明すると、コンピュータは浮動小数点数を、指数と仮数の桁数 (ビット) が固定された 2 進数の科学表記法のような形式で格納するということです。これは、数値の絶対値が大きいほど、数値を正確に表現できないことを意味します。IEEE 754 の 32 ビット浮動小数点の場合、最大約 10^38 の数値が 32 ビット浮動小数点で表現可能であっても、可能なビット パターンの半分は -1 から 1 の間を表します。2^24 (約 1,670 万) より大きい値の場合、32 ビット浮動小数点数はすべての整数を正確に表すことができません。

これが意味するのは、一般に次のことは避けたいということです。

  1. 最終的な答えが小さいと予想される場合は、中間値を大きくします。

  2. 大きな数値に小さな数値を加算/減算する。たとえば、次のように書いたとします。

    for(float インデックス = 17000000;インデックス < 17000001;インデックス++) {}

17,000,000 + 1 は 17,000,000 に切り捨てられるため、このループは終了しません。次のようなものがあった場合:

float foo = 10000000 - 10000000.0001

丸め誤差により、foo の値は -0.0001 ではなく 0 になります。

  

私の質問には、いくつかの他のあるものです   私が探している必要があり一般的な状況   ため、どのような「良い」と考えられています   それらにアプローチする方法？

あなたは精度の厳しいあるいは壊滅的な損失を持つことができるいくつかの方法があります。

最も重要な理由は、浮動小数点数の桁の数が限られているということである、e.g..doublesは53ビットを有します。それはあなたが解決策の一部ではないが、保存されている必要があり、「役に立たない」の数字を持っている場合、あなたは精度を失うことを意味します。

たとえば、（私たちは、デモの小数点タイプを使用している）：

2.598765000000000000000000000100 -

2.598765000000000000000000000099

興味深い部分は100から99 = 1答えです。 2.598765としては、両方の場合で同じです 結果を変更するが、8桁の数字を無駄にしません。コンピュータにはないので、ずっと悪いです 数字は無用であることを知って、それを格納することを強制し、それの後に21個のゼロをザ・クランプスされ、 すべての29桁の数字で無駄。残念ながら違いのためにそれを回避する方法はありません、 しかし、他の例は、例えば、ありますEXP（X）-1物理学に非常に頻繁にoccuring機能です。

0に近いEXP関数は、ほぼ線形であるが、それは主要な数字として1を適用します。 12を持つので、 有効数字 EXP（0.001）-1 = 1.00100050017から1 = 1.00050017e-3

私たちが代わりに関数expm1を使用する場合は（）、テイラーシリーズを使用します：

1 + X + X ^ 2/2 + X ^ 3月6日... -1 =

X + X ^ 2/2 + X ^ 3/6 =：expm1（X）

expm1（0.001）= 1.00500166667e-3

はるかに良い。

第二の問題は、π/ 2付近のxの正接のような非常に急勾配の関数です。 （11）日焼けは、任意の小さな偏差は丸め誤差によって引き起こされることを意味50000の傾きを有しています 前因子50000によって増幅されます！例えば場合それとも、特異点を持っています結果は、それが任意の値を持つことができることを意味し、0/0に近づいています。

両方のケースでは、本来の機能をsimplying、代替機能を作成します。それはトレーニングなしあなたは、単に最初の場所で問題を「見る」はありませんので、別の解決策が近づい強調するために役に立たない。

学び、訓練するために非常に良い本：フォアマンS.アクトンを：リアル作っリアルタイムコンピューティング

これはまた、丸め誤差に対する感受性の増加につながる可能性として

回避するために、もう一つは、ほぼ等しい数字を引いています。 0に近い値については、COS（x）が1に近くなるので、1 / COS（X） - 1を使用して、可能な場合は避けたいのですが、それらの減算の一つですので、私は（a）は避けるべきであると言うでしょうます。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top