Multivariate bisection method

Question

I need an algorithm to perform two-dimensional halving to solve a 2x2 nonlinear problem. Example: two equations f(x,y)=0 and g(x,y)=0 , which I want to solve simultaneously. I am very familiar with the 1D case (as well as other numerical methods). Suppose that I already know that the solution lies between the boundaries x1 < x < x2 and y1 < y < y2 .

In the grid, the initial boundaries are:

  ^ | CD y2 -+ o-------o | | | | | | | | | y1 -+ o-------o | AB o--+------+----> x1 x2 

and I know the values ​​of f(A), f(B), f(C) and f(D) , as well as g(A), g(B), g(C) and g(D) . To start halving, I think we need to divide the dots along the edges, as well as in the middle.

  ^ | CFD y2 -+ o---o---o | | | |G oo M o H | | | y1 -+ o---o---o | AEB o--+------+----> x1 x2 

Now consider the possibilities of combinations, such as checking if f(G)*f(M)<0 AND g(G)*g(M)<0 seems overwhelming. Maybe I'm making it too complicated, but I think there must be a multi-dimensional version of Bisection, just as Newton-Raphson can easily be multi-faceted using gradient operators.

Any hints, comments or links are welcome.

Answer 1

I just stumbled upon the answer to this question from geometrictools.com and C ++ code .

edit: the code is now on github .

Answer 2

Sorry, but while dividing in half works in 1st, it is not performed in higher dimensions. You simply cannot break the 2nd region into subregions, using only information about the function in the corners of the region and the point in the interior. According to Mick Jagger, "You can't always get what you want . "

Answer 3

I would divide the area into only one size, variable sizes. The condition that you have for the existence of zero of one function will be "you have two points of different signs on the border of the region", so I just check this for two functions. However, I don’t think this will work well, because the zeros of both functions in a certain region do not guarantee a common zero (this may even exist in another area that does not meet the criterion).

For example, look at this image:

It is impossible to distinguish the squares ABED and EFIH given only for f() and g() behavior on their boundary. However, ABED does not contain a common zero and EFIH does.

It will be similar to regional requests, for example, for example. kD-trees, if you can positively determine that the region does not contain zero, for example. f . However, this can be slow in some circumstances.

Answer 4

If you can assume (for your comment on wood chips) that f (x, y) = 0 defines a continuous monotonic function y = f2 (x), i.e. for each x1 <= x <= x2 there is a unique solution for y (you simply cannot express it analytically due to the random form f), and similarly, y = g2 (x) is a continuous monotonic function, that is, a way to find a joint solution.

If you could calculate f2 and g2, you can use the 1st halving method by [x1, x2] to solve f2 (x) -g2 (x) = 0. And you can do this using 1-bit division in half on [y1, y2] again to solve f (x, y) = 0 for y for any given fixed x that you need to consider (x1, x2, (x1 + x2) / 2, etc.) - then where continuous monotonicity is useful - and similarly for g. You must definitely update x1-x2 and y1-y2 after each step.

This approach may be ineffective, but should work. Of course, many functions with two variables do not intersect the z plane as continuous monotonic functions.

Answer 5

This is a similar problem for finding critical points in vector fields (see http://alglobus.net/NASAwork/topology/Papers/alsVugraphs93.ps ).

If you have the values ​​f (x, y) and g (x, y) at the vertices of your quadrangle and you are in the discrete problem (so that you do not have an analytic expression for f (x, y) and g (x, y ), as well as values ​​in other places inside the quadrangle), you can use bilinear interpolation to get two equations (for f and g). For the two-dimensional case, the analytical solution will be a quadratic equation, which according to the solution (1 root, 2 real roots, 2 imaginary roots) you can have 1 solution, 2 solutions, solutions without solutions inside or outside your quadrangle.

If instead you have analytic functions of f (x, y) and g (x, y) and you want to use them, this is not useful. Instead, you can split the quadrangle recursively, however, as jpalecek ( 2nd post ) already pointed out, you will need a way to stop your units by finding out a test that would assure that you will not have zeros inside the quadrangle.

Answer 6

There is a method based on the Poincaré-Miranda theorem, https://arxiv.org/pdf/1702.05542.pdf