複数の根を見つける二等分アルゴリズム

Question

二分アルゴリズムの線で何かを使って関数のすべての根を見つける方法はありますか？

ある範囲で中点の両側をチェックすることを考えましたが、新しく生成された範囲に根があるかどうかを知るためにはどれだけ深く進まなければならないかはまだ分かりません。また、関数を適用する際の対応する値が反対の符号であることがわかっていても、与えられた範囲にいくつの根があるかをどのように知ることができますか？

ありがとうございました。

Answer 1

二分法アルゴリズムを使用して、関数が単調である範囲の根を見つけることができます。このようなセグメントは、微分関数を調べることで見つけることができますが、一般的なケースでは、任意の範囲の関数の単調性については仮定することはできません。

たとえば、関数f(x) = sin(1/x)は、-1と1の間に無限数のルートを持ちます。これらのルーツを列挙するには、まず単調な範囲を決定し、xが0に近づくにつれて、これらの範囲が消えて小さくなる必要があります。