What is a good way to sample data points on an interval as to avoid Runge's phenomenon but have a deterministic sampling scheme?

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!

• – Pinocchio Nov 29 '17 at 22:47

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.$$
• 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$. – Alejandro Nasif Salum Nov 30 '17 at 2:12