3
$\begingroup$

Given some equally spaced data for a function on an interval, we can use line segments (pictured below), quadratic functions, various cubic schemes, and increasingly higher order polynomials to approximate the function using this equally spaced data.

enter image description here

For the linear scheme I show as an example in the figure above, as $h \rightarrow 0$, the approximation error also approaches zero, so we say the scheme is "convergent".

In general though, using increasingly higher order polynomials as approximations on the equally spaced intervals does not guarantee convergence. Wikipedia has an explanation that says that $h^{n+1}f^{(n+1)}(\xi)$ may not approach zero as $h$ approaches zero, if $f^{(n+1)}(\xi)$ dominates. Can you show this in a problematic case using pictures?

$\endgroup$
10
$\begingroup$

This problem is commonly called "Runge's phenomenon", and is similar to Gibbs' phenomenon, which is encountered when using Fourier series to approximate a function. The Wikipedia pages convergence of polynomial approximation schemes, and on Runge's phenomenon have a clear discussion, along with a picture to show the phenomenon in action:

enter image description here

Caption from Wikipedia (emphasis mine): The red curve is the Runge function. The blue curve is a 5th-order interpolating polynomial (using six equally spaced interpolating points). The green curve is a 9th-order interpolating polynomial (using ten equally spaced interpolating points). At the interpolating points, the error between the function and the interpolating polynomial is (by definition) zero. Between the interpolating points (especially in the region close to the endpoints 1 and −1), the error between the function and the interpolating polynomial gets worse for higher-order polynomials.

$\endgroup$
  • 2
    $\begingroup$ To minimize Runge's phenomena we typically don't use uniformly spaced points, but rather cosine spacing known as the Chebyshev Nodes $\endgroup$ – user7257 Jun 8 '15 at 13:48

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.