$f(x)= \frac{1}{1+x^2}$

and when I computed the interpolating polynomial of 5 equally spaced points in [-5,5] I got

$ p(x)= 0.0053x^4 -0.1711x^2 +1$

Now I need to estimate the error in the interpolant using the error formula.


I'm trying to self learn this topic and I want to know if there is a way I can use f(x)-p(x) to solve this instead of using the right side of the formula.

If the right side is to be used, how is it possible?

The latter part of the question asks to do the sane for 17 equally spaced points so I don't think I am asked to find the 17th derivative of $ f$ .


For a polynomial interpolant we have the formula for the pointwise error $$ E_n(x) = f(x) - p_n(x) = \frac{f^{(n+1)}}{(n+1)!}\prod_{i=0}^n(x-x_i),$$ where the $x_i$ are the interpolation knots. In general, we want to work with the right hand side of the error formula (a derivation appears in the book by Quarteroni et. al.) as the function we interpolate is typically not a polynomial or rational function. Some important remarks for the error $E_n$ are:

  1. $E_x(x)$ tends to be very oscillatory.
  2. If $f^{(n+1)}(x)$ is nicely bounded on $[a,b]$, then the error can be estimated.
  3. Problems if $f^{(n+1)}(x)$ grows faster than $(n+1)!$ or if $\prod_{i=0}^n(x-x_i)$ is large.

You are correct to assume that for a large number of interpolation knots it becomes unwieldy to compute the derivative in the error formula, e.g for $n=17$ we would need $f^{(18)}(x)$. Instead we could compute a short sequence of the derivative and attempt to notice a pattern and determine if the value for $E_n(x)$ will be "well-behaved" (i.e. bounded). We'll start at $n=4$ since that was a previous problem $$ \vdots\\E_4(x) = \frac{1}{5!}\left(-\frac{240x(3x^4 - 10x^2+3)}{(1+x^2)^6}\right)\prod_{i=0}^4(x-x_i), \\ E_5(x) = \frac{1}{6!}\left(\frac{720(7x^2 - 35x^4 + 21x^2-1)}{(1+x^2)^7}\right)\prod_{i=0}^5(x-x_i), \\ E_6(x) = \frac{1}{7!}\left(-\frac{40320x(x^6 - 7x^4+7x^2-1)}{(1+x^2)^8}\right)\prod_{i=0}^6(x-x_i), \\ \vdots$$ This small slice of error calculations reveals that the growth of the terms $f^{(n+1)}(x)$ and $(n+1)!$ balance nicely. But this means that the value of $E_n$ will become large near the endpoints because the value of $f^{(n+1)}(x)/(n+1)!$ will be small but $\prod_{i=0}^n(x-x_i)$ will be large. Such a result for this particular f(x) on $[-5,5]$ has been noted previously.

The problem you are asked to consider is known as Runge's counterexample which a maliciously chosen problem that highlights the drawbacks of polynomial interpolation on equally spaced knots. In fact, it can be checked that some points $x$ exists within the interpolation interval such that $$ \lim_{n\rightarrow\infty} \left|f(x) - p_n(x)\right|\ne 0.$$ Even more alarming is it is possible to show that Lagrange interpolation diverges (see Isaacson and Keller for a complete proof). If we plot the polynomial interpolate of the Runge function for uniformly spaced knots we'll see significant, spurious oscillations (particularly near the endpoints of the interval). These oscillations are often referred to as Runge phenomena.

Can we remedy this problem for the function $f(x)$? It turns out yes we can, if we choose a set of interpolation knots which are not uniformly spaced. For example, let's choose the Tschebyscheff (Chebyshev in English translations) points of the second kind $$ x_j = \cos\left(\frac{j\pi}{n}\right),\quad j=0,\ldots,n.$$ Then we can visually see that the Runge phenomena has been removed (and one could show that convergence restored using analysis tools from Isaacson and Keller).

| cite | improve this answer | |

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.