1
$\begingroup$

The problem is simple: we have a curve defined by some equation:

$$g(x,y)=0$$

Where $g$ may be piecewise or feature a number of conditions, in other words, be very complicated, but the curve is supposed to be at least continuous.

What would be the fastest and the most stable numerical method which outputs any point $(x_0,y_0)$ such that:

$$g(x_0,y_0)=0$$

I don't really care which point, as I can then use it to find other points all along the curve (due to its continuity). But finding the initial point is not that simple, because the curve may be finite and situated somewhere far from the origin.


One idea I have is to sweep the plane with a strtaight line coming from the origin:

$$y= x \tan \theta_n$$

$$\theta_n=n \theta_0, \qquad n=0,1,2,\dots$$

Then we search for a numerical solution to:

$$g(x,x \tan \theta_n)=0$$

If needed, we can try a few initial guesses until Newton's (or another) method converges or we are reasonably certain there's no solution. Then we increase the angle and try again.

But I don't think this method is the best, so I hope there are some other options.

$\endgroup$
1
$\begingroup$

Consider $z=g(x,y)$ as a surface. You are looking for its crossing with the plane $z=0$.

If you can find two points, one which gives a positive value for $z$ and the other negative, then you can apply the Secant method and approximate to get near to $z=0$. If the function is continuous you are theoretically guaranteed to reach the zero. Practically instead you just need that you have enough digits to discriminate the $\Delta z$ wrt $x$ and $y$.

The secant m. works in 2D (and higher) similarly to 1D and does not require derivatives, so can be applied for piecewise defined functions.

It remains to find an efficient strategy to find points wth opposite sign. But for that I do not see anything better than to analize the $g(x,y)$ and be at least able to determine a range within which to start and explore.

$\endgroup$
  • $\begingroup$ Thank you for mentioning Secant method. As for the range, that's for the most part the crux of the problem, as I want to write a program which does it automatically $\endgroup$ – Yuriy S Oct 20 '18 at 11:13
  • $\begingroup$ @YuriyS: I understand, but finding +/- values should be easier than to find zeros. To be of further help you shall give more details on $g(x,y)$ you are actually facing $\endgroup$ – G Cab Oct 20 '18 at 14:06
  • $\begingroup$ @ G Cab, unlike most questions on this site, I'm actually trying to solve the general problem, particularly write a program which does it for any continuous curve. But I understand your point about zeros, thank you again $\endgroup$ – Yuriy S Oct 20 '18 at 15:43
  • $\begingroup$ @YuriyS: how can you write a "general program " without putting a limit for the $x,y,$ range ?! $\endgroup$ – G Cab Oct 20 '18 at 15:52
  • $\begingroup$ G Cab, one such method is suggested in my post. After finding an arbitrary point, it's a simple algorithm to search for the next one at a given (small) distance on a curve. The only problem is automatically deriving the proper scaling $\endgroup$ – Yuriy S Oct 20 '18 at 15:54

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.