4

I am working on this question:

For equidistant points $x_j=j, 0\leqslant j\leqslant n$, $n$ even, let $$\omega(x)=(x-x_0)(x-x_1)\ldots (x-x_n)$$ Use Stirling's formula to estimate the ratio $$\frac{\omega\left(\frac 12\right)}{\omega\left(\frac{n}{2}+\frac 12\right)}$$ for large $n$. Explain Runge phenomenon.

So far I have figured out that $$\omega(1/2)=\frac12·\left(-\frac12\right)·\left(-\frac32\right)\ldots\left(\frac12-n\right)=(-1)^n2^{-n-1}1·3·5\ldots(2n-1) =(-1)^n2^{-2n-1}\frac{(2n)!}{n!}$$ Now, I know that I have to use Stirling's Formula. But how do I compute $\omega\left(\frac{n}{2}+\frac 12\right)$, to find the ratio? Also how does the Runge phenomenon play into this?

user315747
  • 43
  • 1
    $n$ even is a clue as to where the computation should take place... You've done the work to compute $\omega\frac 12$ and so similar work will apply... – abiessu Feb 18 '16 at 22:45
  • @abiessu I still don't fully follow what you're saying. – user315747 Feb 18 '16 at 22:48
  • Just note that $\omega(\frac n2+\frac 12) = (-\frac n2-\frac 12)(-\frac n2+\frac 12)\cdots(-\frac 32)(-\frac 12)(\frac 12)(\frac 32)\cdots(\frac n2-\frac 32)(\frac n2-\frac 12)(\frac n2+\frac 12)$... (I may have one or more extra terms in there) – abiessu Feb 18 '16 at 22:55
  • This problem is really demonstrating a specific value of the Runge phenomenon, that the "error" is worse at the ends than in the middle. – abiessu Feb 18 '16 at 22:58
  • @abiessu How is this showing that the error is worse at the ends? – user315747 Feb 18 '16 at 23:01
  • You'll have to calculate the actual value to see that, but just going from intuition, you have the multiplication over $\frac 12, \frac 32, \dots, \frac n2+\frac 12$ in both quantities, but then the first quantity goes on to multiply into larger numbers all the way up to $n-\frac12$ while the second is simply squared, and both quantities have the same number of terms. If I read the problem correctly, the final ratio will be greater than $1$. – abiessu Feb 18 '16 at 23:04
  • Really, you should be able to replace $n$ with $\frac n2$ in your first computation and then square the result to get the value of $\omega(\frac n2+\frac 12)$. – abiessu Feb 18 '16 at 23:15
  • @abiessu Why would your last comment work exactly? – user315747 Feb 18 '16 at 23:25
  • Because of the symmetric nature of $\omega(\frac n2+\frac 12)$ for even $n$. – abiessu Feb 19 '16 at 01:52
  • Specifically, the $x-x_0$ term becomes $-\frac n2+\frac 12$ and the $x-x_n$ term becomes $\frac n2-\frac 12$, and all the terms in between are mirrored. So if we use notation $\omega_q$ where $q=n$ and then consider that you have calculated $\omega_n(\frac 12)$ already, then we can say that $\omega_n(\frac n2+\frac 12)=\omega_{n/2}(\frac12)|\omega_{n/2}(\frac12)|$... – abiessu Feb 19 '16 at 01:59
  • This is the more precise version compared with my intuition above. – abiessu Feb 19 '16 at 02:00
  • @abiessu Would you mind adding an answer here, so that I can understand step-by-step what I have to do? – user315747 Feb 19 '16 at 02:13

1 Answers1

2

Let us use the notation

$$\omega_q(x) = \prod_{i=0}^q(x-x_i)$$

and take the work already done to arrive at

$$\omega_n\left(\frac 12\right)=\frac12·\left(-\frac12\right)·\left(-\frac32\right)\ldots\left(\frac12-n\right)=(-1)^n2^{-n-1}1·3·5\ldots(2n-1)\\ =(-1)^n2^{-2n-1}\frac{(2n)!}{n!}$$

Given that we have $n=2m$ even, this becomes

$$\omega_{2m}\left(\frac12\right) = 2^{-4m-1}{(4m)!\over(2m)!}$$

We also wish to find the value of $\omega_n\left(\frac n2+\frac 12\right)$, and this value is $(\frac n2+\frac 12)(\frac n2-\frac 12)(\frac n2-\frac 32)\cdots(\frac 32)(\frac 12)(-\frac 12)(-\frac 32)\cdots(-\frac n2+\frac 32)(-\frac n2+\frac 12)$

It is worth noting that the terms $(\frac 12)(\frac 32)\cdots(\frac n2-\frac 12)$ have the same value as $\left|\omega_m\left(\frac 12\right)\right|=2^{-2m-1}{(2m)!\over m!}$, and therefore we have

$$\omega_n\left(\frac n2+\frac 12\right) = (-1)^m\left(\omega_m\left(\frac 12\right)\right)^2\left(\frac n2+\frac 12\right)\\ =(-1)^{m}2^{-4m-2}\left({(2m)!\over m!}\right)^2\left(m+\frac 12\right)$$

This leads us to conclude

$${\omega_n\left(\frac 12\right)\over\omega_n\left(\frac n2+\frac 12\right)}={2^{-4m-1}{(4m)!\over(2m)!}\over (-1)^{m}2^{-4m-2}\left({(2m)!\over m!}\right)^2\left(m+\frac 12\right)}\\ =(-1)^{m}{(4m)!(m!)^2\over 2((2m)!)^3\left(m+\frac 12\right)}$$

The next step would probably be to use an approximation for $(2k)!\over k!k!$ in a couple spots and see what the ratio turns out to be. If $n=4$, this becomes $-1\cdot {8!4\over 2\cdot 64\cdot 27\cdot 8\frac 52}=-{8!\over 128\cdot 27\cdot 5}=-{7\over 3}\lt -2$, and it is reasonable to expect that this ratio will increase in absolute value. By comparison, if $n=2$ we get result $1$.

abiessu
  • 8,115