多元对分法

Question

我需要一种算法来执行2D二分法来解决2x2非线性问题。例如：两个方程f(x,y)=0和g(x,y)=0我想somultaneously解决。我对一维二等分（以及其他数值方法）非常熟悉。假设我已经知道解决方案介于边界x1 < x < x2和之间y1 < y < y2。

在网格中，起始范围是：

    ^
    |   C       D
y2 -+  o-------o
    |  |       |
    |  |       |
    |  |       |
y1 -+  o-------o
    |   A       B
    o--+------+---->
       x1     x2

我知道的价值观f(A), f(B), f(C) and f(D)，以及g(A), g(B), g(C) and g(D)。为了开始二等分，我想我们需要沿着边缘以及中间将点分开。

    ^
    |   C   F   D
y2 -+  o---o---o
    |  |       |
    |G o   o M o H
    |  |       |
y1 -+  o---o---o
    |   A   E   B
    o--+------+---->
       x1     x2

现在考虑组合的可能性，例如检查是否f(G)*f(M)<0 AND g(G)*g(M)<0似乎势不可挡。也许我使这一过程有些复杂，但是我认为应该存在Bisection的多维版本，就像使用梯度算子可以轻松地将Newton-Raphson进行多维化一样。

欢迎任何线索，评论或链接。

Answer 1

我只是从geometrytools.com和C ++代码中无意中找到了答案。

编辑：代码现在在github上。

Answer 2

我只会沿着一个维度分割区域，交替维度。单个函数存在零的条件是“在该区域的边界上有两个不同符号的点”，所以我只是检查这两个函数。但是，我认为它不会很好地工作，因为特定区域中两个函数的零并不能保证共同的零（这甚至可能存在于不符合标准的不同区域中）。

例如，看看这张图片：

您无法区分正方形ABED和EFIH仅给出的f()和g()在其边界上的行为。但是，ABED不包含公共零并且包含EFIH。

这类似于使用例如的区域查询。kD-trees，如果您可以肯定地确定一个区域不包含零，例如。f. 尽管如此，在某些情况下这可能会很慢。

Answer 3

抱歉，虽然等分在1-d中起作用，但在较大尺寸上失败。您仅使用区域拐角处和内部某点上的函数的信息就无法将二维区域划分为子区域。用米克·贾格尔（Mick Jagger）的话说，“您不能总是得到想要的东西”。