2
$\begingroup$

Let say a function $f$ is defined iteratively over the set of positive integers, for instance $f(t+1)=f(f(t))$ or $f(t+1)=f(t)+f(t-1)$. Based on the recurrence relationship and initial conditions, how would you define $f(t)$ if $t$ is a fraction or an irrational number? In short, you have a function $f$ defined over the set of natural numbers, and you try to expand the domain to cover all real numbers, while at the same time making $f$ well behaved.

The classic solution is to use Newtonian series, which have been known for centuries, and described briefly in my last section. Here I propose a new approach based on Fourier methods.

My questions are:

  • For which functions $f$ is my method applicable? Can it be generalized to handle a bigger class of functions?
  • Does it produce the same resulting function as the method based on Newtonian series, when both methods are applicable?
  • Are there undesirable features attached to my method?

My method

It starts with the following result, which is a direct application of the infinite product formula for the sine function, combined with using L'Hospital rule when $t=k$ in the formula below. Many (but not all) functions satisfy

$$f(t) = \frac{\sin\pi t}{\pi}\cdot \Big[\frac{f(0)}{t} +\phi'(t)\sum_{k=1}^\infty (-1)^k \frac{f(k)}{\phi(t)-\phi(k)} \Big]$$

where $\phi$ is a well behaved function satisfying $\phi'(t)\neq 0$ if $t$ is a strictly positive integer. In all my examples I only used $\phi(t)=t^2$, thus with $\phi'(t)=2t$. So we assume here that $\phi(t)=t^2$. In short, my result states (under appropriate convergence conditions) that for many standard even function, if you know $f(0), f(1), f(2),\dots$ then you can re-construct or extent $f(t)$ to any real number $t$ using my formula. Note that for integer values of $t$, the value for $f(t)$ computed with my formula is in fact a well-defined, implicit limit.

A well known and fundamental example of a function $f$ satisfying my above formula is $f(t)=1$. Another one is $f(t)=\cos \lambda t$ if $|\lambda|<\pi$. Obviously, if the formula applies to two functions $f_1,f_2$ then it also applies to any linear combination of these two functions.

So my method will work well (that is, my formula applies) for any function $f$ that can be written either as

$$f(t)=\sum_{k=0}^\infty \alpha_k \cos \beta_k t, \mbox{ with } |\beta_k|<\pi$$

or

$$f(t)=\int_{-\infty}^\infty w(u)\cos(ut) du$$ where $w$ is a weight function with $w(u)=0$ if $|u|\geq\pi$. That is, it works if $f$ is the cosine Fourier transform of a truncated function $w$.

A counter-example

Many functions do not satisfy the first formula mentioned in my post. An example is $f(t)=t^2$. Yet, surprisingly, my formula offers a pretty good approximation, especially as $t$ becomes larger. To avoid confusion, let us denote as $f^*(t)$ the partial fraction expansion in my formula, supposed to approximate $f(t)$ as closely as possible. In the perfect case described above, we have $f^*(t) = f(t)$ for all real numbers $t$. In the imperfect case like $f(t)=t^2$, we have $f^*(t) = f(t)$ only for $t$ a positive integer. Below are two charts, the first one comparing $f(t)$ with $f^*(t)$, the second one displaying the error $f^*(t)-f(t)$ when $f(t)=t^2$ and $t\in [0, 5.5]$.

enter image description here

enter image description here

It is interesting to note that for $f(t)=\cos 3t$, the approximation is exact everywhere, while $f(t)=\cos 4t$ is one of the worst cases with a large error except if $t$ is close to a positive integer.

Method based on Newtonian series

For comparison purposes, I explain here what mathematicians typically use when confronted with this problem. The general formula (instead of my formula based on partial fraction expansions) is:

$$f(t)=\sum_{k=0}^\infty A_k \cdot G_k(t)$$ where $G_k(t)=0$ if $k=0,1,\dots, k-1$ and $G_k(k)\neq 0$. Other than that, the functions $G_k$ are arbitrary. The coefficients $A_k$ are easily computed iteratively using $$A_k=\frac{1}{G_k(k)} \cdot \Big[f(k)-\sum_{j=0}^{k-1}A_j G_j(k) \Big].$$

The Newtonian series method uses $G_k(t)=t(t-1)(t-2)\cdots (t-k+1)/k!$ with $G_0(t)=1$, resulting in $$A_k=\sum_{j=0}^k (-1)^{k-j}{k\choose j}f(j).$$

Despite $f(t)$ defined that way being an interpolation polynomial of infinite degree, it typically leads to a pretty smooth function.

$\endgroup$
2
  • 1
    $\begingroup$ I just realized this can be generalized to multidimensional functions whose values are known only on a lattice. It is somewhat related to kriging techniques and can even be generalized if values of $f(s,t)$ are known only at arbitrary (random) locations. It provides a robust, well-conditioned interpolation technique. $\endgroup$ – Vincent Granville Nov 10 '20 at 17:09
  • $\begingroup$ Also wondering how this is connected to wavelets (en.wikipedia.org/wiki/Wavelet). $\endgroup$ – Vincent Granville Nov 10 '20 at 18:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.