# Approximation by exponential polynomials

Let $u(t) = \Sigma_{k=1}^n c_k e^{\lambda_k t} (c_k \in \mathbb C, \lambda_k \in \mathbb C)$ be an exponential polynomial of $\underline{order}$ $n$.

Define $E_n$ to be the collection of all exponential polynomial of order $n$, i.e.,

$$E_n:= \{ u : u(t) = \sum_{k=1}^n c_k e^{\lambda_k t}, c_k \in \mathbb C, \lambda_k \in \mathbb C \}.$$ Notice, that two elememts of $E_n$ may have different (disjoint) set of exponents. Only requirement for $u$ to be in $E_n$ is that it has order at most $n$.

Let $\mathbf{P}_n$ be the collection of all polynomials of $\underline{degree}$ at most $n$.

Consider a function $f = \sum_{j=1}^{M} p_{m_j}(t) e^{\lambda_j t}, p_{m_j} \in \mathbf{P}_{m_j}, \sum_{j=1}^{M} (m_j+1) \leq n$.

My question is, can one find a sequence $u_m \in E_n$ such that, $$\sup_{x\in[0,1]}| f(x)- u_m(x) |\rightarrow 0.$$

If possible, then how should one go about constructing such a sequence ?

-
As to the first question, note that exponential polynomials are a separating *-algebra, hence uniformly dense in $C^0([0,1])$ by the Stone-Weierstrass theorem. –  Pietro Majer Jun 27 '10 at 11:10
I meant to ask how to approximate $f$ from $u_m$ belonging to class $E_n$, $n$ is fixed here. I used same $n$ for the index of the sequence $u_m$ ... I made the correction –  Vagabond Jun 27 '10 at 11:21
argh... this completely changes the question, and even makes it more interesting... but my free time is over by now :( –  Pietro Majer Jun 27 '10 at 13:53
I think it's funny that you underlined the word order to clarify, but that word is extremely ambiguous anyway.... –  Harry Gindi Jun 27 '10 at 15:56

This follows from the fact that the set of $n\times n$ matrices with simple spectrum is dense in the space of all $n\times n$ matrices ${\bf M}_n(\mathbb C)$ (or that the set of polynomials of degree $n$ with simple roots is dense in the set of all complex polynomials of degree $n$).

The function $f$ solves the Cauchy problem for a linear ODE with constant complex coefficients $$y^{(N)}+a_1y^{(N-1)}+\dots+a_Ny=0,$$ $$y^{(k)}(0)=f^{(k)}(0),\quad k=0,1\dots,N-1,$$ where $N=\sum_{j=1}^{M} (m_j+1) \leq n$. The exponents $\lambda_j$, $j=1,\dots,M$ are the roots of the corresponding characteristic equation $$P(\lambda)=\lambda^{N}+a_1\lambda^{N-1}+\dots+a_N\lambda=0$$ with the multiplicities, respectively, $m_j+1$, $j=1,\dots,M$. The coefficients $a_1,\dots a_N$ can be found from the relation $$P(\lambda)=\prod\limits_{j=1}^{M}(\lambda-\lambda_j)^{m_j+1}.$$

Now, a small generic perturbation of the ODE's coefficients will produce an ODE $$y^{(N)}+a_1^{\varepsilon}y^{(N-1)}+\dots+a_N^{\varepsilon}y=0,$$ such that the roots of the corresponding characteristic equation are all simple. This implies that a solution to the latter ODE belongs to $E_n$. Finally, we may use a standard result that solutions to linear ODEs depend continuously on the coefficients (in the topology of uniform convergence on finite time intervals).

-
very elegant solution –  Pietro Majer Jun 27 '10 at 13:49

By induction on $n$. If $n=1$, no problem. If $n \geq 2$, if the polynomials $p_{m_j}$ are all constant, still no problem. So assume $p_{m_1}$ nonconstant. Approximating $f$ is the same as approximating $t \mapsto e^{-\lambda_1 t} f(t)$, so we may assume $\lambda_1=0$. Then we approximate $f'$, using induction (since $\lambda_1=0$, $\sum_{j=1}^M (m_j+1)$ is less for $f'$). Now if $f'-u_0$ is small, with $u_0(t) = \sum_{k=1}^{n-1} c_k e^{\mu_k t}$, then $f-u$ is also small, where $u(t)=f(0)-\sum_{k=1}^{n-1} c_k/\mu_k + \sum_{k=1}^{n-1} \frac{c_k}{\mu_k} e^{\mu_k t}$ (using integration). The only problem here is that maybe $\mu_k=0$ for some $k$. But we can take $\mu_k$ very small but nonzero instead, $u_0$ is still close to $f'$.

This method gives an algorithm: everything is computable, and the only approximations are in fact the choices of "replacements" for zero $\mu_k$ (if you take it to be $1/n$, you get a sequence).

-
There is the following slight thing, that is not to clear from this: If you want to approximate f'(x) = 1. You will choose one \lambda_1 = 0. So integration leads to the approximating u containing an x term. So in order for the procedure to work you will want to approximate it by u(t) = e^{\lambda t} with \lambda small. This is essentially an O(\lambda) approximation, but then integration yields a factor 1/\lambda, which destroys it –  Helge Jun 27 '10 at 12:00
I posted my own version below ... my doubts on what you wrote thus have been scattered... –  Helge Jun 27 '10 at 12:07
The point is that if $\sup_{t \in [0,1]} |f'(t)-u'(t)|=\epsilon$ and $f(0)=u(0)$, then $|f(t)-u(t)| \leq \epsilon t$ for all $t \in [0,1]$, no matter what the "formula" is. –  Homology Jun 27 '10 at 12:38

I think the following is another proof. It suffices to approximate a polynomial of degree n by an exponential polynomial of degree n + 1. Now, define $$g_{\lambda}(x) = \frac{e^{\lambda x}}{\lambda} - 1.$$ It is easy to check that $\sup_{x\in [0,1]} |g_{\lambda} - x| \leq \frac{1}{2} \lambda$. Also $g_{\lambda}$ has order $2$. Furthermore, we can compute $$|g_{\lambda}(x)^n - x^n| \leq |g_{\lambda}(x) -x| \cdot n \leq \frac{n}{2} \lambda.$$ And note that $g_{\lambda}(x)^n$ has order $n+1$. So a polynomial of degree $n$ given by $$P_n(x) = \sum_{k=0}^{n} a_k x^k$$ can be approximated by $$\sum_{k=0}^{n} a_k (g_{\lambda}(x))^k$$ up to order $n^2 \lambda$. Letting $\lambda \to 0$ implies the claim.

-
How do you get the inequality $|g_{\lambda}(x)^n-x^n| \leq n |g_{\lambda}(x)-x|$? If $\lambda$ is positive, $g_{\lambda}(1)>1$ (easily seen with a series expansion), so it seems the inequality doesn't hold. Nevertheless if we choose $\lambda$ after $n$, it seems to work. –  Homology Jun 27 '10 at 12:44
My thought was $x^n - y^n = (x- y) \left(\sum_{k=1}^{n} y^{k-1} x^{n -k}\right)$. So $|x|\leq 1$ is clear. And we have $y = g_{\lambda}(x)$. Since $g_{\lambda}$ is increasing, we have that it's maximum is attained at $1$... but as you point out this is $\gtrsim \frac{1}{\lambda}$ and not 1... argh ... –  Helge Jun 27 '10 at 13:38
Very good, +1! To fix the details, define instead, for all $x\in I:=[0,1]$ and $0< \lambda\leq 1$ : $$g_\lambda(x):=\frac{e^{\lambda x}−1}{\lambda}.$$ So for all $x\in I$ we have $g_\lambda(x)\in [0,e]$, and $|x−g_\lambda(x)|\leq \lambda e^\lambda/2$ . Now for any polynomial $P$ of degree at most $n$ , $P(g_\lambda(x))$ is in $E_{n+1}$ , and we get by the MVT, for any $x\in I$ $$|P(x)−P(g_\lambda(x))|\leq \|P'\|_{\infty,[0,e]}\lambda e^{\lambda}/2$$ and we conclude as you said letting $\lambda\to0.$ –  Pietro Majer Jun 27 '10 at 16:45
Nice. Given this explicit estimate one is tempted to ask about the degree of approximation. But I am not sure how to phrase this question ... (e.g. we probably want some large n limit somewhere). –  Helge Jun 27 '10 at 17:05

The following exploits the negative integers $k$ as $\lambda_k$ (I will go for the simpler, not necessarily for the best bounds, and make it explicit). Take a uniform approximation by polynomials $p_m$ for the function $f(t):=\log\left(\frac{1}{1-t}\right)$ on the interval $J:=[0,1-1/e]$. Assume further $0\leq p_m(t)\leq 1$ for all $t\in J$ (you can always get this). Since $$\epsilon_m:=\|f-p_m\|_{\infty,\\,J}=o(1),$$ as $m\to \infty,$ we get, putting $t:=1-e^{-x}$, that $\|x-p_m(1-e^{-x})\|_{\infty,[0,1]}=\epsilon_m$ and, more in general, a bound on the uniform distance on [0,1] between the polynomial $q(x)$ and the exponential polynomial $$q_m(x):=q\left(\\,p_m(1-e^{-x})\right).$$ Indeed, by the mean value theorem applied to $q$ and the two points $x$ and $p_m(1-e^{-x}),$ both belonging to the interval $[0,1],$ $$\| q - q_m \|\leq \\|q'\|_{\infty,\\, [0,1]}\\, \epsilon_m .$$

For instance, the Taylor expansion of order $m$ of $f$ gives $$p_m(t):=\sum_{k=1}^{m}\frac{t^{\\,k}}{k}$$ with $0\leq p_m(t)\leq 1$ for all $t\in J$ as said, and with $\epsilon_m\leq\frac{1}{m+1}.$

-
(the above is the answer to the question as stated initially, with a misleading typo) –  Pietro Majer Jun 27 '10 at 16:18
@Pietro Majer, I apologise and yes thankyou for taking the trouble to post it and for letting it remain here. So this is a right answer for the wrong question' and the fault is entirely mine. In the originl post the question was posed as can one find a sequence $u_n \in E_n$ such that, $$\sup_{x\in[0,1]}| f(x)- u_n(x) |\rightarrow 0.$$' –  Vagabond Jul 17 '10 at 16:16