2

如果我使用二分法找到多项式的根，并且在某些情况下取决于多项式，根可能是负数，也可能是正数。

我知道我可以根据评估多项式的​​结果来确定根是负数还是正数……但是我不确定我将使用什么作为 x。

任何人都可以在这里提供任何见解吗？

4

4 回答 4

2

根可以是负数或正数这一事实与二分法无关。根的存在可以用微积分的中间值定理来证明。

因此，您所要做的就是找到负面和x1正面的点。然后你从 IVT 中知道和之间有一个根。您可以通过在该间隔上进行二进制搜索来做到这一点。如果为负数，则在区间 上重复二分搜索。否则，如果是肯定的，则搜索区间。x2y(x1)y(x2)x1x2y(x3) = y((x1+x2)/2)[x3,x2][x1,x3]

根是负的还是正的都没有关系。我不确定这是否能回答你的问题，但我希望这能帮助你理解算法。

于 2012-01-14T23:09:13.923 回答
0

您可能会发现这很有帮助。

使用系统；

命名空间 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

于 2012-10-23T03:24:38.717 回答
0

许多根查找器允许用户提供一个或多个起点来开始搜索。这允许用户尝试“调整”结果以找到不同的根或允许查找器收敛到一个根。

如果允许用户提供起始值没有意义，您可以从探索几个点开始：

  • -1, 0, 1
  • -10, 0, 10
  • -100, 0, 100
  • 等等

如果输入是一个奇数多项式，这最终会发现一个合适的二分范围。如果输入是偶数多项式，您可能永远无法捕捉到符号变化（考虑 f(x)=x^2 - 它永远不会是负数），因此请准备好在经过一定（可配置？）量的探测后放弃。

我建议在这里将范围扩大 10 次方；由于二分法每次将范围减半，也许这太保守了。（它需要两到三次二等分迭代才能将范围缩小到下一个“更紧密”的括号。）也许更好的是更大的跳跃：

  • -10, 0, 1
  • -1000, 0, 1000
  • -100000, 0, 100000
  • 等等

这将执行更少的探测，但需要更多的二等分。尝试一些多项式并跟踪执行时间，以找到两个建议的根。

于 2012-01-15T02:36:10.267 回答
0

为了使用二分算法，您首先需要找到一个包含根的区间。标准算法在Sturm 定理中给出。

然而，标准二分算法期望端点中函数值的符号不同。这可能是个问题。最简单的例子是 x^2，它具有 2 阶的单个根 0。由于 x^2 对于所有非零 x 都是正数，因此您无法找到适合与二分算法一起使用的包含根的区间。

于 2012-05-14T07:52:33.910 回答