多項式根発見二分法

Question

二分法を使って多項式の根を見つけた場合、場合によっては多項式に応じて根が負であるか、正である可能性があります。

多項式を評価した結果に基づいて、根が負であるか正であるかを判断することができますが、私はxとして何を使用するのかは不明です。

誰でもここに洞察力を与えることはできますか？

Answer 1

根が負である可能性があるという事実は、二分法とは何の関係もありません。微積分からのintermediate value theoremを使って根の存在を証明することができます。

x1とx2のように、y(x1)が負でy(x2)が正であるようにするだけでいいです。次に、IVTから、x1とx2の間に根があることがわかります。あなたは、その間隔でバイナリ検索を行うことでそれを行います。 y(x3) = y((x1+x2)/2)が負の場合、区間[x3,x2]で二等分検索を繰り返します。さもなければ、それが肯定的である場合、間隔[x1,x3]で検索してください。

根が負であるか正であるかは関係ありません。それがあなたの質問に答えるかどうかはわかりませんが、アルゴリズムを理解するのに役立つことを願っています。

Answer 2

ルートファインダの多くは、ユーザーが開始点を指定して検索を開始できるようにします。これにより、ユーザーは結果を「仕上げ」して別のルーツを見つけたり、ファインダーをルートに収束させたりすることができます。

それは、ユーザがポイントの一握りをプロービングすることにより、あなたが始めることができるの開始値を提供することを可能にしても意味がない場合は、次の

-1

、0、1
• -10、0、10
• -100、0、100
• 等

入力が奇数多項式である場合、これは、最終的に二等分するのに適した範囲を発見します。入力が偶数多項式の場合は、符号の変更を捕まえることはできません（f（x）= x^2 - 負ではありません）ので、特定の（設定可能な）量のプロービングの後にあきらめる準備をしてください。

ここでは、範囲を10の累乗で大きくすることを提案しました。二分法では毎回半分の範囲をカットするので、おそらくこれはあまりにも控えめです。 （これは、次の「タイト」ブラケットに範囲を減らすために二分の2と3回の反復の間でお願いします。）たぶん、より良い、より大きなジャンプのようになります。

• -10、0、1
• -1000 、0、1000年
• -100000、0、100000
• など

これは、少数のプローブを実行するが、より多くの二分が必要になります。いくつかの多項式を試してみて、両方の提案で根を見つけるために実行時間を追跡してください。

Answer 3

二分アルゴリズムを使用するには、まずルートを含む区間を見つける必要があります。これに対する標準アルゴリズムはSturm's Theoremで与えられている。

しかし、標準的な二分法アルゴリズムでは、端点の関数値の符号が異なることが予想されます。これは問題になる可能性があります。最も簡単な例は、2次の単一根0を持つx^2です。x^2はすべての非ゼロのxに対して正であるため、二分アルゴリズムでの使用に適したルートを囲む間隔を見つけることはできません。

Answer 4

おそらくこれは役に立ちます。

using System;

名前空間Bisection_Method

{

class Program 

{ 

    public double midPoint (double xl, double xu) 

{ 

    return (xl + xu)/2; 

} 

    public double function(double x) 

    { 

     return (x*x-2); 

    } 

    static void Main(string[] args) 

    { 

     Program root = new Program(); 

     double xm=0, xl=1, xu=2, check=0; 

     for (int x = 0; x < 20; x++) 

     { 

      xm = (xl + xu)/2; 

      check = root.function(xl) * root.function(xm); 

      if (check < 0) 

       xu = xm; 

      else if (check > 0) 

       xl = xm; 

      else if (check == 0) 

      { 

       break; 

      } 

     } 

     Console.WriteLine("The Approximate of the Root is {0}", xm); 

    } 

} 

}

http://mustafa.amnbytes.com/2012/09/bisection-method-program-in-c.html