How many points to find a polynomial?

Question

I would like to fit a formula $ax^b + cx^d+ e$ to a set of points. I have two questions.

1. If my data were perfect, how many points do I need in the worst case to get $a,b,c,d,e$ exactly?
2. If my data aren't perfect, but the underlying unknown function is really something like $a\sqrt{x} + cx^{0.2} + 5000$, say, what's a good way to estimate $a,b,c,d,e$ from the data?

Update. Following answers/comments below, if we treat 2. as a least squares minimisation problem, is it convex? Asked separately at Is $ \sum_{1 \le k \le n} (y_k - a x_k^b + c x_k^d + e)^2 $ convex? .

Answer 1

$\def\sgn{\mathrm{sgn}}$Answer to 1: Assuming that all the variables are real, $5$ positive values of $x$ is enough.

Proof: Suppose to the contrary that there were two different polynomials $a x^b+c x^d + e$ and $A x^B + C x^D + E$ interpolating through data points $(x_1, y_1)$, $(x_2, y_2)$, ..., $(x_5, y_5)$. Then all the $x_i$ are zeroes of the polynomial $$A x^B - a x^b + C x^D - c x^d + (E-e).$$ This polynomial has only $5$ nonzero terms so, by Descartes' rule of signs, it can only have $4$ positive real roots. $\square$.

Although I, like you, have been referring to polynomials, I understand that you want your exponents to be real. Fortunately, Descartes' rule of signs works with real exponents. I can supply a proof if needed; it seems to be tricky to find a reference to this fact online.

I don't know the answer to the (much more interesting) question 2.

---

$\def\sgn{\mathrm{sgn}}$ Descartes' Rule of Signs for real exponents: Let $\lambda_1 < \lambda_2 < \cdots < \lambda_n$ be real numbers, and let $a_1$, $a_2$, ..., $a_n$ be $n$ other real numbers. Let there be $m$ indices $i$ for which $a_i$ and $a_{i+1}$ have different signs. Then the function $f(x) := \sum a_i x^{\lambda_i}$ has at most $m$ positive real roots.

Proof by induction on $m$: If $m=0$, then all the $a_i$ have the same sign, say without loss of generality all the $a_i$ are positive. Then $f(x)$ is positive for all $x>0$, and has no roots.

Now consider $m>0$. Let $f(x)$ have $r$ positive real roots, and let $\sgn(a_1) = \sgn(a_2) = \cdots = \sgn(a_i) = - \sgn(a_{i+1})$. Set $g(x) = x^{- \lambda_i} f(x)$. So $g(x)$ also has $r$ positive real roots and, by Rolle's theorem, $g'(x)$ has at least $r-1$ real roots.

We have $$g'(x) = \sum_{j=1}^{i-1} (\lambda_j-\lambda_i) a_j x^{\lambda_j-1} + \sum_{j=i+1}^{n} (\lambda_j-\lambda_i) a_j x^{\lambda_j-1}.$$

We have $$\sgn( (\lambda_1-\lambda_i) a_1) = \sgn( (\lambda_2-\lambda_i) a_2) = \cdots = \sgn( (\lambda_{i-1}-\lambda_i) a_{i-1}) = \sgn( (\lambda_{i+1}-\lambda_i) a_{i+1})$$ and, for $j \geq i+1$, we have $\sgn( (\lambda_j-\lambda_i) a_i) = \sgn(a_i)$. So $g'(x)$ has one fewer sign alternation than $f$ did. By induction, $g'$ has at most $m-1$ positive real roots.

Combining this with the Rolle's theorem bound, $r-1 \leq m-1$, so $r \leq m$, as desired. $\square$.

Answer 2

You have 5 unknowns, so 5 points are enough to set up a set of 5 equations in the 5 unknowns. Solving it will require numerical methods.

A "good method" would be to (ab)use least squares: You can define for your $n$ data points $(x_k, y_k)$: $$ f(a, b, c, d, e) = \sum_{1 \le k \le n} (y_k - a x_k^b + c x_k^d + e)^2 $$ and try to find (again, numerically) the values of the unknowns. Many times such systems turn out to be such that the value of $f$ is rather insensitive to the unknowns, specially if the data don't align very well.