代码之家 › 专栏 › 技术社区 › John Alexiou

多元对分法

bisection numerical-methods linear-algebra math language-agnostic

John Alexiou · 技术社区 · 14 年前

我需要一个算法来执行一个二维平分方法来解决一个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 似乎势不可挡。也许我把它做得有点太复杂了,但我认为应该有一个多维的二分法版本,就像牛顿·拉斐逊可以很容易地用梯度算子来进行多维化一样。

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

5 回复 | 直到 8 年前

user85109 14 年前

对不起,虽然对分在一维中有效,但在更高的维度中失败了。仅使用区域角和内部点的函数信息,无法将二维区域划分为子区域。用米克·贾格尔的话来说, "You can't always get what you want" .

ThreeStarProgrammer57 8 年前

我只是偶然发现了这个答案,从一个HRFF=“HTTP/CON/TrimeToStudio/BaseNo.PDF”Re=“NoFoLoLoNeFror”> GooTrimoToC.com < /a>和 C++代码

编辑:代码现在位于 github 。

和 C++ code .

编辑:代码现在打开 github .

Title

jpalecek 14 年前

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

例如,查看此图像:

您无法区分方块 abed 和 efih given only f()和 g()上的行为。但是, abed does't contain a common zero and efih does.

这将类似于使用例如kd树的区域查询,前提是您可以肯定地确定某个区域不包含eg. f的零。不过,在某些情况下,这可能会很慢。

外部尺寸。一个函数零点存在的条件是“在区域边界上有两个符号不同的点”,所以我只检查这两个函数。但是,我不认为它能很好地工作,因为这两个函数在一个特定的区域都是零。不要保证一个共同的零(这甚至可能存在于一个不符合标准的不同区域)。


   
    
     
      
       
        
         
          
           
            
             
              例如,查看此图像:
             
             
              
             
             
             
             
              你不可能区分这些方块
              
               ABED
              
              和
              
               EFIH
              
              仅给出
              
               f()
              
              和
              
               g()
              
              他们边界上的行为。然而,
              
               阿贝德
              
              不包含公共零和
              
               埃菲特
              
              做。
             
             
              这类似于使用例如kd树的区域查询,前提是您可以确定某个区域不包含eg的零。
              
               f
              
              . 不过,在某些情况下,这可能会很慢。

Aniko 14 年前

如果你可以假设(根据你对Woodchips的评论)f(x,y)=0定义了一个连续单调函数y=f2(x),也就是说,对于每个x1<=x<=x2,y都有一个唯一的解(由于f的混乱形式,你不能解析地表达它),同样y=g2(x)是一个连续单调函数,那么有一种方法找到联合解。

如果可以计算F2和G2,那么可以在[x1,x2]上使用一维平分法求解F2(x)-G2(x)=0。你可以通过在[y1,y2]上使用1-d平分来解决f(x,y)=0,对于你需要考虑的任何给定的固定x(x1,x2,(x1+x2)/2等),这就是连续单调性有帮助的地方,同样对于g,你必须确保在每一步之后更新x1-x2和y1-y2。

这种方法可能不高效,但应该有效。当然,许多双变量函数不相交的Z平面作为连续单调函数。

Community THelper 7 年前

这与在向量场中寻找临界点类似(请参见 http://alglobus.net/NASAwork/topology/Papers/alsVugraphs93.ps )

如果在四边形的顶点处有f(x,y)和g(x,y)的值,并且处于离散问题中(这样您就没有f(x,y)和g(x,y)的解析表达式,也没有四边形内其他位置的值),那么可以使用双线性插值来得到两个方程(f和g)。对于二维情况,解析解将是一个二次方程,根据解(1根,2实根,2虚根),你可能有1个解,2个解,没有解,你四边形内外的解。

相反,如果你有f(x,y)和g(x,y)的分析函数并想使用它们,那么这是没有用的。相反,你可以递归地划分你的四边形,但是正如前面已经指出的那样 jpalecek ( 2nd post ,你需要一种方法来阻止你的分裂,通过计算一个测试来确保你在四边形中没有零。