3
$\begingroup$

When constructing minimax (sup-norm) polynomial approximations of real-valued functions, well-known results say (roughly speaking) that optimal solutions are characterized by the fact that they have equi-oscillatory errors.

Can this be generalised to cover approximation of 2D or 3D curves?

The simplest example is the first quadrant of the circle $x^2 + y^2 = 1$. I have constructed very good approximations using polynomials $P(t) = (u(t), v(t))$, and I find that they are equi-oscillatory, in the sense that the error function $u(t)^2 + v(t)^2 -1$ oscillates equally about zero. I'd like to know if there's any theory that supports this experimental finding.

Of course, I could just write the circle quadrant as $x=\cos t$, $y=\sin t$, and approximate the sine and cosine functions by polynomials on $[0, \tfrac12 \pi]$. But this is a different problem, and this approach gives circle approximations that are significantly inferior to the ones I constructed. So, decomposing the 2D problem into two 1D ones is not what I'm after.

In three dimensions, my "curve" would be given by a pair of equations $f(x,y,z)=0$ and $g(x,y,z)=0$. In this case, I don't even know how to define "equi-oscillatory" or even "oscillation".

I asked this question on Math.Stackexchange, and got zero response.

For circles, specifically, there are some good results in the answers to this related question, but no progress on more general curves or any underlying theory.

Edit: Here is a more formal/rigorous statement of the 2D problem. We are given a function $f:\mathbf{R}^2 \to \mathbf{R}$, and we are considering the set $F = \{(x,y) \in \mathbf{R}^2 : f(x,y)=0\}$ to be a planar curve. Let $P_0 = (x_0, y_0)$ and $P_1 = (x_1, y_1)$ be two points in $F$ (i.e. two point on our curve). We can assume that $P_0$ and $P_1$ belong to the same connected component of $F$. For each $(x,y) \in \mathbf{R}^2$, let $d(x,y)$ denote the Euclidean distance from $(x,y)$ to the set $F$. I want to find polynomials $u:[0,1] \to \mathbf{R}$ and $v:[0,1] \to \mathbf{R}$ such that $$ u(0) = x_0 \quad ; \quad u(1) = x_1 \\ v(0) = y_0 \quad ; \quad v(1) = y_1 $$ and such that $$ \max\big\{ d\big(u(t),v(t)\big) : t \in [0,1]\big\} $$ is minimised. In other words, I want the curve $t \mapsto \big( u(t), v(t) \big)$ to be an optimal approximation of the portion of my original curve lying between the points $P_0$ and $P_1$. And I'm interested in knowing if this optimal solution is equi-oscillatory, in some sense.

A simple concrete example is $f(x,y) = x^2y^2 + (x-1)(x-2)$, with $P_0 = (0,0)$ and $P_1=(2,0)$. I want an optimal approximation of the piece where $y \ge 0$. It looks like this: egg

$\endgroup$
  • $\begingroup$ You could look up best approximation by non-decreasing functions. A similar phenomenon occurs and maybe the added perspective would help. So this is the $L_{\infty}$ norm? You could look at $L_1$ and $L_p$ as well. $\endgroup$ – Aaron Meyerowitz May 1 '14 at 12:09
  • $\begingroup$ Thanks. I'm interested only in the $L_\infty$ norm (in some sense). I want minimize the maximum Euclidean distance between the original curve and the polynomial approximation. $\endgroup$ – bubba May 1 '14 at 12:27
  • $\begingroup$ Congratulations on asking the Nth question, where N is the 12th positive integer for which there are precisely five distinct integer triangles having hypotenuse N. oeis.org/A084649 $\endgroup$ – Steve Huntsman May 1 '14 at 12:33
  • $\begingroup$ Could you clarify a bit why Euler-Lagrange didn't work for you? For example, turning the 2D plane into 3D surface with $z=e^\frac{x^2+y^2-1}{\epsilon}$ and finding a geodesic between (0,1,1) and (1,0,1), or an equivalent classical mechanical problem? $\endgroup$ – Michael May 1 '14 at 14:34
  • $\begingroup$ @Michael -- well, it didn't work because I didn't try it :-). It doesn't seem like a very promising approach, to me. Finding geodesics is typically difficult, and I don't really see why a geodesic would be a solution, and I don't see how to represent a geodesic as a polynomial. $\endgroup$ – bubba May 2 '14 at 9:19
2
$\begingroup$

This is an extended comment. What exactly you are trying to minimize?

First version: given an algebraic curve with equation $F(x,y)=0$, and two points on this curve $M,N$, find the polynomials $p,q$ of degree at most $d$ such that $(p(0),q(0))=M$, $(p(1),q(1))=N$, and $$\max_{t\in[0,1]}|F(p(t),q(t))|$$ is minimal. Some condition about two points is necessary here, otherwise you will have a trivial constant solution $(p(t),q(t))=X$ where $X$ is any point on your curve. But of course you may consider various conditions at the ends.

Second version. Given two functions $x(t),y(t)$ on $[0,1]$, to minimize $$\max_{t\in[0,1]}(|p(t)-x(t)|^2+|q(t)-y(t)|^2).$$

These are two completely different problems.

The solution for the circle you refer to seems to be related to the first problem. If this is what you ask, there are several possible generalizations to higher dimension, using any norm. For example, if the curve is given by two polynomials $F$ and $G$ of three variables, you may want to minimize $\max\{|P(p,q,r)|,|Q(p,q,r)|\}$. But again some additional condition is necessary to avoid the trivial constant solution.

EDIT. However, there are additional difficulties with the First formulation. An algebraic curve $F(x,y)=0$ may consist of several pieces, and if we really want to approximate it, one has an additional requirement that the two points $M,N$ are on one piece. Moreover, there can be several ways along the curve $F(x,y)$ from $M$ to $N$ (always more than one way!) and this is not reflected in the precise formulation. So it is possible to have $F(p(t),q(t))$ uniformly small on $[0,1]$ but the curve $(p(t),q(t))$ does not approximate $F(x,y)$ in any reasonable way: the curve $F(x,y)=0$ may have a loop between $M$ and $N$, while the curve $(p(t),q(t))$ cheat and skip this loop.

All this shows that there is no meaningful precise statement of the problem yet.

$\endgroup$
  • $\begingroup$ Thanks. I'm interested in the first problem, almost. A minor quibble -- you are using the value of $|F(p(t),q(t))|$ to measure the distance from the point $(p(t), q(t))$ to the curve $F$. What I'd really like to minimize is $\max_{t \in [0,]} d(t)$ where $d(t)$ is the Euclidean distance from the point $(p(t), q(t))$ to the curve with equation $F(x,y)=0$. But the problem you described is closely related, and probably easier, so solving it would be useful to me. $\endgroup$ – bubba May 2 '14 at 9:08
  • $\begingroup$ I'm not interested in generalising to higher dimensions or different norms. I'm only interested in minimizing maximum Euclidean distance in two or three-dimensional space. The generalization that interests me is going from circles (which I understand fairly well) to more general curves. $\endgroup$ – bubba May 2 '14 at 9:13
  • $\begingroup$ Read my edit carefully. So far, I do not see any exact statement of what you want to minimize and under what conditions. And what are you willing to assume about $F$. What you stated in your "edit" may NOT approximate your curve in any sense! $\endgroup$ – Alexandre Eremenko May 2 '14 at 16:44
  • $\begingroup$ What am I willing to assume about $F$? Anything that corresponds to the intuitive notion of "smooth curve". In the typical cases I deal with in real life, $F$ is often a polynomial. Are there any restrictions on $F$ that you had in mind that would make it easier to get useful results? $\endgroup$ – bubba May 2 '14 at 23:58
  • $\begingroup$ It's OK with me if the resulting approximation is not useful in cases where the curve $F$ has a loop or self-intersection. $\endgroup$ – bubba May 3 '14 at 0:04
1
$\begingroup$

In response to a previous answer of you mentioned the Remez exchange algorithm. Looking into that makes me suggest the following comments and conjectures:

Consider for now the 2D case

  1. Let's just say that you have a connected curve $F$ (since you could always define $f$ as "distance from $F$").

  2. The notion of distance still seems a bit unspecified. I'll take this as the definition: Given The curve $F$ with points $P_0,P_1$ and a candidate approximation $Q(t)=(u(t),v(t))$ defined on $[0,1]$ consider all "acceptable" parametrizations $P(t)=(x(t),y(t))$ of $F$ with $P(0)=P_0$,$P(1)=P_1$ and look at $\max_t d(P(t),Q(t))$. I'll not require $Q(0)=P_0$ and $Q(1)=P_1$. although one could. Some pathological $F$ could create various problems but I'll ignore that and also assume that the degree of the approximation is high enough to handle the twists and turns of $F$. Then (if all goes well) the set of points at distance $\delta$ from $F$ form a simple closed curve $F^*$

  3. I'll guess that the best approximation $Q$ is unique and has some number $M$ of points $Q_1,Q_2,\cdots,Q_M$ occurring in order on $Q$ and all lying on the closed curve $F^*$ and on "alternating sides" of $F.$ I'd like to define that by saying that each segment $Q_i,Q_{i+1}$ crosses $F$ ($\cdots$ an odd number of times) but instead I'll say that $F^*$ can be traversed so that they occur in order $Q_1,Q_3,Q_5,\cdots Q_6,Q_4,Q_2.$

  4. What $M$ should be (depending on the allowed degree) I'm not quite sure. Just enough that passing through those points (with gradient directed away from $F$) determines $Q(t)$.

  5. For 3D the best I can do is say that something similar is true with the condition that for each three consecutive $Q_{i-1},Q_i,Q_{i+1}$ the disk $D$ they determine is cut by $F$.

  6. What we can say is this: If $Q,Q'$ are two curves both at distance $\delta$ from $F$ then the curve $\frac{Q+Q'}{2}$ is at distance no more than $\delta$ and equality requires at least one value of $t$ such that $Q(t),Q'(t)$ are the same point and that point is at the maximum distance , $\delta$ from $F$. Furthermore, if $\delta$ is optimal then there must be at least one point at maximum distance from $F$ which is common to all $\delta$-good approximants (otherwise take enough of them and average).

  7. More should be true (I'd guess) namely that the best approximation is unique and determined by the $M$ points mentioned before. (I'm not giving an algorithm to find $Q$, just a test to determine that you have it). If we have a curve $Q$ which achieves a distance $\delta$ but only at a few places (relative to the degree allowed), say $M'$ at $t_1,t_2,\cdots,t_{M'}$ then it should be possible to find $M'$ polynomial pairs of the appropriate degrees the $i$th of which is $(0,0)$ at all but one of these $t$ values except at $t_i$ it is not only non-zero, it is also not orthogonal to $P(t_i).$ If so then adding any small enough linear combination (with appropriate signs) of these to $Q(t)$ will decrease the distance at each of the maximally distant points and in some neighborhood of each without creating any new problems.

$\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.