0
$\begingroup$

I recently asked:

Is there an analogous Gibbs phenomena to approximating sinusoidal but with polynomial terms?

because I noticed that at the edges, polynomial interpolation of equidistance points goes crazy. I want to avoid this and sample in a different way. Any way that is deterministic but avoid these explosions at the edges would be fantastic!

What is a good method to sample point as to avoid Runge's phenomenon In my particular case I am especially interested when only a few points are sampled, like 12, so answers addressing this point would be fantastic!

$\endgroup$
2
$\begingroup$

To sample $n+1$ points in $[-1,1]$ you can use the roots of the $(n+1)$-th grade Chebyshev polynomial. So you'll minimize the norm infinity over $[-1,1]$ of $\prod_{i=0}^n (x-x_i)$ among all possible sets of $n+1$ nodes. For a general interval $[a,b]$ you just need to do an affine transformation, that is, given $x_0,\ldots,x_n$ which are the roots of $T_{n+1}$ (which all lay in $[-1,1]$), take $y_0,\ldots,y_n \in [a,b]$ as $$y_i=\alpha x_i+\beta,$$ with $\alpha,\beta$ such that $a=\alpha \cdot (-1)+\beta$ and $b=\alpha \cdot 1+\beta$.

By the way, the $T_n$ polynomials satisfy the recursion $$T_0(x)=1,\quad T_1(x)=x, \quad T_n(x)=2x \cdot T_{n-1}(x)-T_{n-2}(x),$$ and their roots are for each $n\in \mathbb{N}$ $$x_k=\cos\left(\frac{2k-1}{2n} \pi\right),\quad k=1,2,\ldots,n.$$

$\endgroup$
  • $\begingroup$ interesting, so tried it using about 12 data points. Is this Chebyshev nodes sampling method less effective as the degree of the polynomial increases? Is there a condition relating the degree of the polynomial that is approximating the samples vs the number of samples that I need so that the approximation to the true function doesn't suck? $\endgroup$ – Pinocchio Nov 29 '17 at 23:30
  • $\begingroup$ also do u have an intuition (since I lack the background to probably understand the full proof) of why such such sampling method helps? $\endgroup$ – Pinocchio Nov 29 '17 at 23:36
  • 1
    $\begingroup$ Actually, it is not. For Runge's function ($f(x)=\tfrac 1 {1+25x^2}$) Chebyshev interpolation gets better and reduces oscilation of $P_n(x)$ as $n$ gets bigger. Moreover, $P_n(x) \to f(x)$ for all $x \in [-1,1]$, and even more $||f-P_n||_{\infty,[-1,1]} \to 0$ as $n \to \infty$. $\endgroup$ – Alejandro Nasif Salum Nov 30 '17 at 2:12
  • 1
    $\begingroup$ Chebyshev, Chebyshev, he's our man. If his nodes can't do it, nobody's can! $\endgroup$ – marty cohen Nov 30 '17 at 2:20
  • 1
    $\begingroup$ Let's call that #mnemonics (?) $\endgroup$ – Alejandro Nasif Salum Nov 30 '17 at 2:41

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.