バイナリ検索と比較のeps

Question

バイナリ検索で2つの比較がありますが、2つの下線の間に正確な優先順位を付けることはできません。私は、以下の2つのサンプルで間で振動：小さなEPSで、二分探索パラメータに対応するエラーがなるという危険がありますので

for (int step = 0; step < 100; ++step) { 
    double middle = (left + right)/2; 
    if (f(middle) > 0) right = middle; else left = middle; 
} 

と

for (int step = 0; step < 100; ++step) { 
    double middle = (left + right)/2; 
    if (f(middle) > eps) right = middle; else left = middle; 
} 

fは、単調増加関数でありますずっと大きい。一方、丸め誤差のために同じ値の比較が正しくない場合でも、等しい値が1つの点にしか現れず、すべてが非常に近い点で正しいので、バイナリ検索は依然として正確に収束します。私はそれについて考えてみたいです。

Answer 1

コードから判断すると、関数の値がゼロになるタイミングを決定しようとしています。最初の方法はすでに十分です。それはあなたの意図と一致しているからです。 2番目の方法を使う必要はないようです。