Iterative root finding of 2-dimensional system of non-linear equations with monotonicity properties

Question

Let $f(x,y)$ and $g(x,y)$ be two $\mathbb{R}^2\rightarrow\mathbb{R}$ functions, both strictly increasing in both arguments. Assume that they are well-behaved functions (continuous, differentiable, etc.)

Given these properties, I want to find a root to the following system of equations:

$$f(x,y)=f_0$$ $$g(x,y)=g_0$$

assuming that a solution exists and that it is unique.

Is there an efficient algorithm to iteratively bracket the root in increasingly smaller regions $\mathbb{R}^2$? That is, I am looking for a derivative free method that is an extension of the bisection method, for 2 variables, with convergence guaranteed.

Answer 1

Because the functions are strictly increasing, this can be reduced to the one-dimensional case. In each one-dimensional problem there are more efficient standard methods available, more efficient than bisection, and it also means one doesn't have to come up with a non-standard method oneself. After all, one-dimensional root-finding is a "solved" standard problem.

Without loss of generality, assume $f_0=g_0=0$, and define $x_f=x_f(y)$ and $x_g=x_g(y)$ to be the solutions of $f(x_f(y), y) = 0$, and $g(x_g(y), y)=0$, respectively. Both $x_f, x_g$ are well-defined strictly decreasing functions of $y$, and can be evaluated numerically by one-dimensional root-finding, even bisection. Then the common root of $f=g=0$ corresponds to a solution of $x_f(y)-x_g(y) = 0$, which is again a one-dimensional problem.

The initial bracket has to be chosen appropriately so that the roots of each of the one-dimensional problems are bracketed correctly. Geometrically speaking, one can choose a rectangle with vertices $(x_-, y_-), (x_+, y_+)$ such that the curves $x=x_f(y)$ and $x=x_g(y)$ cross the rectangle at the $y=\mathrm{const}$ boundaries only (it's easier to draw this), and cross each other inside the rectangle (necessarily only once).

Answer 2

Suppose you can initially "bracket" the root, which means you have four points $(x_i,y_i), i=1,...,4$ such that:

$$f(x_1,y_1) < f_0 \textrm{ and } g(x_1,y_1) < g_0,$$ $$f(x_2,y_2) < f_0 \textrm{ and } g(x_2,y_2) > g_0,$$ $$f(x_3,y_3) > f_0 \textrm{ and } g(x_3,y_3) < g_0,$$ $$f(x_4,y_4) > f_0 \textrm{ and } g(x_4,y_4) > g_0.$$

Then we can guarantee that a root of the system of equation is contained in the convex hull of the four points.

An algorithm could iterate the following two steps:

1. Compute the centroid of the four points.
2. Replace one of the four points by the centroid. The point replaced is chosen so that the eight inequalities above still hold with the new set of four points.

The area of the convex-hull of the four points will eventually shrink, locating the root to arbitrary precision.

I have not been able to give an analysis of the speed at which the area of the convex-hull decreases. Also, a robust way to find the initial four points would be useful. Additionally, I claim that the convex hull of the four points contains a root, but I have not been able to give a rigorous proof of this statement (I think it is true intuitively, but I could be wrong).