Find the interpolation polynomial $P_n(x)$

Question

I would appreciate help with how to find the polynomial $P_n(x)$ for the question below:

Interpolate $f$ at equidistant points $x_i=[-1,1]$ such that $x_i=\frac{2i}{n}-1$, $i={0,1,2,..,n}$ with a polynomial $P_n(x)$ of degree less or equal to n. Where, $$f=\frac{1}{1+25x^2}.$$

I was thinking about doing this for $P_4(x), P_8(x), P_{12}(x)$ and $P_{16}(x)$ and then construct four graphs all presenting $f$ and respective $P_n(x)$ to be able to compare these (kinda like they did here on page 63). And my guess is that one should use $P(x)=p_1x^n+p_2^{n-1}+...+p_nx+p_{n+1}$ from the Weierstrass approximation theorem to get $P_n(x)$, but still from this I don't know how to construct the interpolation polynomial.

My thought is now that one can choose a polynomial that corresponds to P as long as it is less or equal to n? But then we won't use $x_i$ in this and therefore this must then be wrong.

Does anyone want to help me clarify how one should construct the interpolation polynomial $P_n(x)$?

Edit the example in the link above also construct $P_4(x), P_8(x), P_{12}(x)$ and $P_{16}(x)$ but never show how they did these, they only present them in the graphs, and therefore that example can't help me with this problem.

Answer 1

Use the Lagrange interpolation formula:

Given $n+1$ points $(x_1,y_1),\dots,(x_{n+1},y_{n+1})$ with distinct $x$-coordinates, there exists a unique polynomial of degree at most $n$ that passes through all of the points, given by the formula $$P(x)=\sum_{i=1}^{n+1}y_i\prod_{\substack{j=1\\j\neq i}}^{n+1}\frac{x-x_j}{x_i-x_j}.$$

You can check for yourself that this polynomial will do the trick -- at $x_i$, all terms in the sum except for the $i$th term vanish, so the evaluation is relatively straightforward.

Answer 2

I don't want to ruin the surprise, but you'll see that these interpolating polynomials will start behaving quite badly as $n$ increases... This is known as Runge's example and it is normally used to motivate the use of Chebyshev nodes.