9
$\begingroup$

I've stumbled upon a method of extrapolation that I haven't seen before.

We are trying to approximate $f(0)$ for a certain function $f$, which we have only measured at points $x_0, \ldots, x_N$ in an interval $[a,b]$ that does not contain $0$. We have reason to believe that $f$ is analytic in a neighbourhood of a region of $\mathbb C$ (containing both $0$ and $[a,b]$) bounded by a simple positively oriented closed contour $\Gamma$. Suppose we can approximate $1/z$ on $\Gamma$ by a linear combination of $1/(z-x_j)$, say $$ \left| \frac{1}{z} - \sum_{j=0}^N \frac{a_j}{z-x_j} \right| \le \varepsilon \ \text{for}\ z \in \Gamma $$ Then using Cauchy's formula, $$ \left|f(0) - \sum_{j=0}^N a_j f(x_j) \right| \le \frac{M\; \text{length}(\Gamma) \varepsilon}{2\pi}$$

Rather than uniform approximation, it is more convenient to use an $L^2$ approximation. This will let us find the $a_j$ by minimizing a quadratic form. In the case where $\Gamma$ is a circle of radius $r$ centred at $0$, I get a nice closed form: $$ a_j = \frac{r^2 - x_j^2}{r^{2N+2}} \prod_{k \ne j} \frac{x_k (r^2 - x_j x_k)}{x_k - x_j}$$

I can't believe I'm the first to think of this idea. Has anyone seen something like this?

$\endgroup$
5
+50
$\begingroup$

There are extrapolation schemes in use that take essential recourse to analyticity, for example, the "z-expansion fits" described in arXiv:1008.4619 (it's sufficient to read the first two pages to see what the method is). In the details, however, these fits differ substantially from the scheme you are proposing. I have not seen anything that is very similar to your scheme.

Having said that, I worry about the stability of your scheme. You say that you "measure" the function $f$, which I assume means that, generically, you don't have exact data on $f$, but they come with statistical or systematic error. In that case, it is important that the scheme be robust against these errors. Let's look at an example that, I think, by no stretch of the imagination can be dismissed as contrived:

10 equally spaced data points at $x$ ranging from $x=0.1$ to $x=1$, with $r=1.5$, i.e., in your notation, $N=9$, $x_j = 0.1(j+1)$, $r=1.5$. Then, your coefficients $a_j $ are:

$a[0]=7.80096236306711$

$a[1]=-27.161848927028$

$a[2]=55.5523167543375$

$a[3]=-73.8548460044706$

$a[4]=66.6361882416331$

$a[5]=-41.2843129034312$

$a[6]=17.3237609884424$

$a[7]=-4.70612791676158$

$a[8]=0.746272144521954$

$a[9]=-0.0523647403501327$

The coefficients are large and alternating! This means they are prone to magnify fluctuations of the data. Let's take the simplest possible true functional dependence, $f(x)=1$. As long as you have no errors in the data, $f(x_j )=1$, you predict $f(0)=1$ with high accuracy. However, as soon as I put small random fluctuations on the data $f(x_j )$, the prediction fluctuates wildly. Here is a sequence of 10 predictions for $f(0)$ when I put random fluctuations on the $f(x_j )$ that are smaller than 1% (i.e., I'm adding $0.01 (2 \cdot rand()-1)$ in perl):

$1.978$

$1.114$

$0.529$

$1.286$

$1.032$

$-0.179$

$1.384$

$0.102$

$0.371$

$1.656$

Thus, 1% errors in the data are amplified to 100% errors in the predictions of $f(0)$, which is of course not at all surprising in view of the $a_j $. So, unfortunately, I'm not sure whether the fact that we're having a hard time finding someone who has seen a scheme of the type you describe used means that no one has thought of it before ...

$\endgroup$
  • $\begingroup$ Numerical stability is indeed an issue, which I think is inherent to all extrapolation methods. I think you can do quite a bit better than with equally spaced points: you might try an optimization to minimize the sum of squares of coefficients. $\endgroup$ – Robert Israel Sep 3 at 16:10
  • $\begingroup$ Yes, extrapolation is always dangerous, however you do it. I'm not an expert on the theory, I just have the experience of frequently grappling with data. Indeed, equal spacing is not the best-behaved thing, and if you have the luxury of choosing where to measure, you'd bunch at the edges, like at Chebyshev points. Still, I gave you a decent lever arm in my example ... it's worth exploring how much one can smooth the behavior of the coefficients. There's also the dependence on the contour - if you reduce r to be close to minimal, e.g., r=1.05 in the example, fluctuations are only 1/2 as large. $\endgroup$ – Michael Engelhardt Sep 3 at 19:48
  • $\begingroup$ Another thought, which may lead absolutely nowhere: Given the ubiquitous Cauchy/Weierstrass dichotomy in analytic function theory, I wonder whether your Cauchy-style formulation doesn't in the end have a Weierstrass equivalent, i.e., a realization in terms of an expansion in powers, polynomials or some such, more akin to standard schemes. Then one could compare and contrast ... $\endgroup$ – Michael Engelhardt Sep 3 at 20:02
  • 2
    $\begingroup$ @RobertIsrael: I think the instability is a property of the analytic continuation and not the point selection, though point selection could ostensibly make the situation worse. See arxiv.org/abs/1908.11097 $\endgroup$ – user14717 Sep 4 at 21:31

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.