1

Consider two continuous real valued functions $f$, and $g$ over the interval $[a,b]$. For a given $\epsilon > 0$, for each function the we can use the Weierstrass approximation theorem to express the function as polynomials $f \approx \mathcal{P}_f$ and $g \approx \mathcal{P}_g$, such that $\lvert f - \mathcal{P}_f\lvert < \epsilon$ and $\lvert g - \mathcal{P}_g\lvert < \epsilon$, over the interval $[a,b]$. Is there anything we can say about the approximating the composition of the two functions $f \circ g$, i.e., $\mathcal{P}_{f\circ g}$ where $\lvert f\circ g - \mathcal{P}_{f\circ g}\rvert < \epsilon$ on the interval $[a,b]$. In other words, is there any relation between $\mathcal{P}_{f\circ g}$, $\mathcal{P}_f$, and $\mathcal{P}_g$?

In particular, I am interested if from $\deg(\mathcal{P}_f)$ and $\deg(\mathcal{P}_g)$ we can say anything about $\deg(\mathcal{P}_{f\circ g})$. I can appreciate that $\deg(\mathcal{P}_f) + \deg(\mathcal{P}_g)$ may be greater than $\deg(\mathcal{P}_{f\circ g})$; as the composition may conspire to cancel out higher terms (e.g., $g \ll f$, such that $\mathcal{P}_f$ has ''overfit'' $f$ to achieve $\epsilon$ in the composition.) However, I cannot see if one can guarantee that this is the upper limit, i.e., $$\deg(\mathcal{P}_{f\circ g}) \leq \deg(\mathcal{P}_f) + \deg(\mathcal{P}_g)?$$

Edit: An example that the component degree sum is larger can be seen from $f(x) = 1+x$, and $g(x) = (1+x)^{-1}$. Both have approximating polynomials greater than degree zero, while the composition's approximating polynomial is trivially degree zero.

Is there a counter-example to the suggestion inequality, i.e., where

$$deg(\mathcal{P}_{f\circ g}) > \deg(\mathcal{P}_f) + \deg(\mathcal{P}_g)?$$

Novice C
  • 303
  • 1
    Also, I think you probably meant $f(x)=1+x$ and $g(x)=-1$ so that $f(g(x))=0$, or perhaps just $g(x)=C$ for any constant $C$ so that $f(g(x))$ is just a constant. – Ian Jun 19 '21 at 18:42
  • Anyway, you have to say something about the scheme that maps $f$ to $\mathcal{P}_f$ for this to mean anything. One way to do that is to unpack the Bernstein polynomial proof of Weierstrass's theorem and thus define $\mathcal{P}_f$ to be the Bernstein polynomial of the lowest possible degree such that your estimates prove that it is uniformly within $\epsilon$ of $f$. Then the degree that you will use is related to the modulus of continuity of $f$ as well as the uniform bound on $f$. – Ian Jun 19 '21 at 18:48
  • And as you seem to have noticed, the modulus of continuity and bound on $f \circ g$ are only rather loosely related to those of $f$ and $g$. As a crude place to start, if $f$ is Lipschitz with constant $L_f$, $g$ is Lipschitz with constant $L_g$, and $|f| \leq M$, then $f \circ g$ is Lipschitz with constant $L_f L_g$ and $|f \circ g| \leq M$. – Ian Jun 19 '21 at 18:48
  • Well this is embarrassing to say the least. I used the word composition and the composition symbol, which you've correctly suggested means f(g(x)), when I meant to say the multiplication of two functions... I almost have to imagine $f(x) = e^x$, and $g(x) = e^x$ would be a counter example to the composition statement I unwitting proposed. Sorry for wasting your time. – Novice C Jun 19 '21 at 19:13
  • Oh, you wanted multiplication. That's a very different question...actually I am not sure that you can realistically expect multiplication to do any better than the sum of the degrees except in very unusual situations. – Ian Jun 19 '21 at 19:13
  • Yes extremely... I'm not sure the etiquette for when the OP has no idea what he is asking. I will ask my real question in a separate post as it is "off" topic. I can delete the post, or since it's probably a valid question and you've offered some insight for others who may stumble upon this post, to leave it up. – Novice C Jun 19 '21 at 19:17
  • 1
    I was actually writing an answer to this question already but it isn't super straightforward to port over to your desired question. So I'd suggest leaving it here. – Ian Jun 19 '21 at 19:18

1 Answers1

3

Here's an example of something you might try in this general direction. Assume WLOG $[a,b]=[0,1]$.

Consider the Bernstein polynomial proof of Weierstrass's theorem. The estimates say that the Bernstein polynomial of degree $d$ corresponding to $f$ evaluated at $x$ will differ from $f(x)$ by no more than $\varepsilon' + R g(\delta,d)$, where

  • $R$ is a bound on the length of the range of $f$. (You could take to be $2M$ where $M$ is a bound on $|f|$ if you want).
  • $\delta$ and $\varepsilon'$ are related so that $|f(x)-f(y)|<\varepsilon'$ whenever $|x-y|<\delta$, i.e. $\delta(\varepsilon')$ is a uniform modulus of continuity for $f$
  • $g(\delta,d)$ is any upper bound on the probability that a binomial random variable with $d$ trials differs from its mean by more than $d\delta$, which must hold for all possible success probabilities in $[0,1]$.

One such bound is the Hoeffding inequality which gives you $g(\delta,d)=2e^{-2\delta^2 d}$.

If you now further assume that $f$ is Lipschitz with constant $L$, then

$$\varepsilon' + 2R e^{-2 \frac{\varepsilon'^2}{L^2} d}$$

is an error bound for any $\varepsilon'>0$. Thus to have an error no more than $\varepsilon$, it suffices to have $d \geq \frac{L^2}{2 \varepsilon'^2} \log \left ( \frac{2R}{\varepsilon-\varepsilon'} \right )$ for some $\varepsilon' \in (0,\varepsilon)$. In particular by taking $\varepsilon'=\varepsilon/2$ you find that $d \geq \frac{2L^2}{\varepsilon^2} \log \left ( \frac{4R}{\varepsilon} \right )$ is sufficient. (The optimal expression is a big ugly mess with the Lambert W function.)

You can repeat this analysis with $f \circ g$ by noting that $f \circ g$ will be Lipschitz with constant $L_f L_g$ and its range is contained in that of $f$.

Ian
  • 101,645