2

I have a continuous function from $R$ to $R^2$, which I want to find a root of. I tried finding a root of the sum of squares, but since that function is always positive I can't use bisection, and any other method I tried didn't converge.

What root finding methods could work on a function from $R$ to $R^2$?

Alternatively, are there methods which always converge but don't require $f(a)f(b) \le 0$?

Command Master
  • 1,270

1 Answers1

2

A function $t \mapsto C(t) = (x(t), y(t))$ mapping $\mathbb R$ to $\mathbb R^2$ is a parametric curve in the $xy$ plane. If you are looking for a “root”, you are seeking a value of $t$ at which this curve passes through the origin. In floating-point arithmetic, it’s highly unlikely that a general curve will pass through the origin, so direct root-finding is not a good approach.

At the point you are seeking, the distance from the curve to the origin is a local minimum. So, you can find the point using a standard minimization algorithm.

If you really want to solve the problem by root-finding, instead, note that the curve tangent at the desired point will be perpendicular to the vector pointing to the origin. In other words $C(t)\cdot C’(t) = 0$. You can solve this equation by root-finding. Of course, not all solutions will correspond to local minima, so you’ll need some checking.

Alternatively, you can use your favorite algorithm to find the roots of $t \mapsto x(t)$ and $t \mapsto y(t)$, and then check to see if there are any roots in common.

bubba
  • 43,483
  • 3
  • 61
  • 122
  • I have two comments; first, I guess that the "distance from the origin" is exactly the "sum of squares" the OP mentions in the question. Second, I don't really understand what you mean by $f(t)\cdot f'(t)=0$. This will produce a lot of non-zeros. Say, if $f(t)=e^{i\theta}$, every $t$ solves this. I am a bit confused. – Giuseppe Negro May 09 '21 at 07:40
  • 1
    Yes, distance to origin is sum of squares. But I suggested doing minimization, not root-finding. – bubba May 09 '21 at 08:36
  • 1
    Yes, $C(t) = (\cos t, \sin t)$ is going to be problematic for any method, because every point of this circle is equally close to the origin. – bubba May 09 '21 at 08:38
  • When you write $C(t)⋅C′(t)=0$, how do you multiply two values in $R^2$? – Command Master May 09 '21 at 09:33
  • It's a dot product of two 2D vectors. The dot product is zero when the vectors are perpendicular. – bubba May 09 '21 at 09:40
  • Oh I see, then I totally agree with the minimization idea. For the other one, I don't really get what you mean by "the curve tangent at the desired point will be perpendicular to the vector pointing to the origin", since the desired point IS the origin. Anyway, it's a +1 – Giuseppe Negro May 09 '21 at 10:23
  • By the "desired point" I meant the point on the curve that's closest to the origin. – bubba May 09 '21 at 12:20