Multivariate Bisection - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T16:03:24Z http://mathoverflow.net/feeds/question/35987 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/35987/multivariate-bisection Multivariate Bisection ja72 2010-08-18T17:08:33Z 2010-10-29T04:22:14Z <p><em>cross post in <a href="http://stackoverflow.com/questions/3513660/multivariate-bisection-method">StackOverflow</a></em></p> <p>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 somultaneously. 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 &lt; x &lt; x_2$ and $y_1 &lt; y &lt; y_2$.</p> <p>In a grid the starting bounds are:</p> <pre><code> ^ | C D y2 -+ o-------o | | | | | | | | | y1 -+ o-------o | A B o--+------+----&gt; x1 x2 </code></pre> <p>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$.</p> <p>To start the bisection I guess we need to divide the points out along the edges as well as the middle.</p> <pre><code> ^ | C F D y2 -+ o---o---o | | | |G o o M o H | | | y1 -+ o---o---o | A E B o--+------+----&gt; x1 x2 </code></pre> <p>Now considering the possibilities of combinations such as checking if $f(G)*f(M)&lt;0$ <code>AND</code> $g(G)*g(M)&lt;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.</p> <p>Any clues, comments, or links are welcomed.</p> http://mathoverflow.net/questions/35987/multivariate-bisection/36102#36102 Answer by KalEl for Multivariate Bisection KalEl 2010-08-19T17:42:06Z 2010-08-19T17:42:06Z <ol> <li><p>Check the pair of <em>opposite</em> corners to determine if zeroes lie within each of the four subdivided rectangles (zeroes can be there in more than one of them). Eg. if f(M)>0 and f(A)&lt;0, then AEMG contains zeroes of f. Same is true also if f(G)>0 and f(E)&lt;0.</p></li> <li><p>Do this for all the four sub rectangles, and for both f and g.</p></li> <li><p>There will be atleast one which contains zeroes for both f and g. Zoom into that and repeat.</p></li> </ol> http://mathoverflow.net/questions/35987/multivariate-bisection/36103#36103 Answer by Per Vognsen for Multivariate Bisection Per Vognsen 2010-08-19T17:57:01Z 2010-08-19T17:57:01Z <p>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$.</p> <p>Unfortunately, the subgradient method has more theoretical than practical value. But in a two-dimensional problem, it might do okay.</p> http://mathoverflow.net/questions/35987/multivariate-bisection/40703#40703 Answer by rcompton for Multivariate Bisection rcompton 2010-10-01T02:37:38Z 2010-10-01T02:37:38Z <p>You might want to consider the vector field</p> <p>$\vec{F}(x,y) = (f(x,y), g(x,y))$</p> <p>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 <a href="http://www.mpi-inf.mpg.de/~ag4-gm/handouts/06gm_top3.pdf" rel="nofollow">this paper</a>) and should divide further.</p>