Finding Numerically the solution line for an equation

[LayMuon]

I have a function which depends say upon two variables: $f(x,y)$.

I need to find numerically the solution line $y(x)$ of the equation $f(x,y) = 0$. The function itself for arbitrary set of {x,y} may evaluate to some complex number (it involves lots of square roots) but for the solution I am seeking the imaginary part on the solution line should be zero. I understand that one in principal can scan through the whole region of {x,y} to get the curve but I need numerically efficient way to write the code.

Thanks.

 

[haruspex]

Is f(x,y) differentiable analytically? I'll assume not, but I will assume it's continuous.
If you can feed in a feasible range for y(x₀) then you could program a binary chop on the values. (Do I need to explain that?) Having found one point on the line, (x₀, y₀), you could then search for solutions of f(x,y) = 0 where the |(x,y)-(x₀, y₀)| = some small r. Again, you could do a binary chop on the direction from (x₀, y₀) to (x,y).

 

[LayMuon]

What is "binary chop"?

 

[HallsofIvy]

If $f(x_0, y_0)> 0$ and $f(x_1, y_1)< 0$ then, because f is continuous, there must be a point between $(x_0, y_0)$ and $(x_1, y_1)$ where f is 0. We have no idea where so checking one point is as good as another- use the midpoint, $(x_2, y_2)= ((x_0+ x_1)/2, (y_0+ y_1)/2)$. Now look at $f(x_2, y_2)$. If it is 0, we are done! If not, it is either positive or negative. If it is positive, then, since $f(x_1, y_1)< 0$, there must be a solution between them. If it is negative, then, since $f(x_0, y_0)> 0$, there be a solution between them. In either case, define $(x_3, y_3)$ to be the mid point of that interval.

That is, I think, what haruspex is calling a "binary chop". I would call it a "binary search".

 

[LayMuon]

My concern is that f(x,y) does not evaluate necessarily to real value, it might as well be complex, so it being positive or negative is not well defined.

 

[haruspex]

My concern is that f(x,y) does not evaluate necessarily to real value, it might as well be complex, so it being positive or negative is not well defined.

That's not a problem. 0 is 0, and the modulus of f is zero if and only if f is 0.

 

[LayMuon]

That's not a problem. 0 is 0, and the modulus of f is zero if and only if f is 0.

But then if you are taking |f(x,y)| how do you implement the comparisons of where it is positive and where negative?

 

[haruspex]

But then if you are taking |f(x,y)| how do you implement the comparisons of where it is positive and where negative?

Ooops! Yes, you're right, sorry. Let me think some more.

 

[haruspex]

OK, instead of doing the binary chop based on the sign of f, you can look for local minima of |f|. This is a bit trickier because you need to track three 'current' points. E.g. if |f(x,y₀)| > |f(x,y₁)| < |f(x,y₂)|, y₀ < y₁ < y₂, then you know there is a min between y₀ and y₂. So next pick y₃ = (y₀ + y₂). If |f(x,y₃)| > |f(x,y₁)| then you know there's one between y₃ and y₂. But it might turn out to be > 0, and there could be a min between y₀ and y₃.

 

[LayMuon]

OK, instead of doing the binary chop based on the sign of f, you can look for local minima of |f|. This is a bit trickier because you need to track three 'current' points. E.g. if |f(x,y₀)| > |f(x,y₁)| < |f(x,y₂)|, y₀ < y₁ < y₂, then you know there is a min between y₀ and y₂. So next pick y₃ = (y₀ + y₂). If |f(x,y₃)| > |f(x,y₁)| then you know there's one between y₃ and y₂. But it might turn out to be > 0, and there could be a min between y₀ and y₃.

but in that case you would just find local minima of the function, not zeros.

 

[haruspex]

but in that case you would just find local minima of the function, not zeros.

Since |f| ≥ 0, every zero will be a local minimum. So if you find all the minima you will find all the zeroes.

 

[LayMuon]

But not all local minima are the zeros

 

[LayMuon]

And another problematic thing with what you suggest is that you have to literally scan all x values, the problem is like for single variable case. I was more looking to be able to dispense with scanning x fully.

 

[haruspex]

But not all local minima are the zeros

Quite so.

And another problematic thing with what you suggest is that you have to literally scan all x values, the problem is like for single variable case. I was more looking to be able to dispense with scanning x fully.

As I understood it, you want to plot y as a function of x. So you would choose whatever set of x values then for each one try to find that y for which f(x,y)=0. All I can offer is some way to find those corresponding y values.