1
$\begingroup$

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.

Improve this question
$\endgroup$
3
$\begingroup$

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).

Improve this answer
$\endgroup$
  • $\begingroup$ This solution involves nested root finding (to get $x_f(y)$ and $x_g(f)$). I have the intuition that something more efficient could be done. In fact, you don't need a precise value of $x_f(y)$ or $x_g(y)$ at the beginning, when the initial value of $y$ is far off from the root. Ideally, one could "bracket" with rectangles directly in 2-dimensions. I worked out something that I will post as an answer later, that I think should be more efficient. $\endgroup$ – becko Sep 8 '16 at 16:35
  • $\begingroup$ @becko Sure. The point of my answer was to reduce the problem to a known solved elementary problem. In fact, once you have such one-dimensional problems, the bisection method can be replaced by far more efficient standard methods (especially, since, as you say, the functions are well-behaved). $\endgroup$ – Kirill Sep 8 '16 at 18:49
  • $\begingroup$ @becko BTW, I'm not sure intuition is necessarily a good guide here: it may well be one of those cases where reducing the problem to a known problem is perfectly sufficient. $\endgroup$ – Kirill Sep 8 '16 at 19:43
0
$\begingroup$

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).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.