# Multivariate Bisection

cross post in StackOverflow

I need an algorithm to perform a 2D bisection method for solving a $2$x$2$ non-linear problem. Example: two equations $f(x,y)=0$ and $g(x,y)=0$ which I want to solve simultaneously. I have very familiar with the 1D bisection ( as well as other numerical methods ). Assume I already know the solution lies between the bounds $x_1 < x < x_2$ and $y_1 < y < y_2$.

In a grid the starting bounds are:

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


and I know the values at $f(A)$, $f(B)$, $f(C)$ and $f(D)$ as well as $g(A)$, $g(B)$, $g(C)$ and $g(D)$. I might even know for which edges $f=0$ and for which $g=0$.

To start the bisection I guess we need to divide the points out along the edges as well as the middle.

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


Now considering the possibilities of combinations such as checking if $f(G)*f(M)<0$ AND $g(G)*g(M)<0$ seems overwhelming. Maybe I am making this a little too complicated, but I think there should be a multidimensional version of the Bisection, just as Newton-Raphson can be easily be multidimed using gradient operators.

-
I suspect the "planar algebras" tag is not appropriate, although subfactor/quantum topology people would know better than I do. –  Yemon Choi Aug 18 '10 at 17:33
Almost always for simultaneous nonlinear equations, the best method to use depends on the nature of $f(x,y)$ and $g(x,y)$; without insight into the geometry of your functions near the roots, or even a way to come up with good starting points, you might end up chaotically exploring the plane (which is even more of a risk if the contours of your two bivariate functions have tangencies or near-tangencies to each other). That being said, I wish to direct your attention to Acton's "Numerical Methods that Work", most especially chapter 14. You might be able to pick up something useful there. –  J. M. Aug 18 '10 at 17:38
After some cursory searching: portal.acm.org/citation.cfm?id=2705 & springerlink.com/content/w72615872r512112 ; as to whether you might be able to use them, you'll have to experiment. –  J. M. Aug 18 '10 at 17:48
The functions are continuous, one-to-one and monotonic as far as each independent variable, but non-linear. Sometimes they are near linear with a $x^{10/9}$ behavior. –  ja72 Aug 19 '10 at 17:32
Have you looked at the papers I pointed out to you? –  J. M. Aug 19 '10 at 22:12

A remarkable generalization of bisection to multiple dimensions is the subgradient method from convex optimization theory. If $f$ and $g$ are convex then $h = f^2 + g^2$ is also convex, and a simultaneous zero of $f$ and $g$ is a minimum of $h$.

Unfortunately, the subgradient method has more theoretical than practical value. But in a two-dimensional problem, it might do okay.

-

You might want to consider the vector field

$\vec{F}(x,y) = (f(x,y), g(x,y))$

and look for sources and sinks of $\vec{F}$. I think this could be done by recursively dividing up the plane into squares and calculating the winding number of each square. If it is nonzero then you have a critical point within that square (cf Thm 2 this paper) and should divide further.

-