language-agnostic - 多元对分法

Question

我需要一种算法来执行2D二等分方法来解决2x2非线性问题。示例:我想同时求解的两个方程f(x,y)=0和g(x,y)=0。我对一维二等分(以及其他数值方法)非常熟悉。假设我已经知道解决方案在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

抱歉，虽然二等分在1-d中起作用，但在更高维度上失败。您仅使用区域拐角处和内部某点上的函数的信息就无法将二维区域划分为子区域。用米克·贾格尔(Mick Jagger)的话说，"You can't always get what you want"。