Exponentially-convergent strategies for defeating the Runge Phenomenon for the approximation of non-periodic functions, part two: Multi-interval polynomial schemes and multidomain Chebyshev interpolation

Approximating a smooth function from its values f ( x i ) at a set of evenly spaced points x i through P-point polynomial interpolation often fails because of divergence near the endpoints, the “Runge Phenomenon”. This report shows how to achieve an error that decreases exponentially fast with P by means of polynomial interpolation on N s subdomains where N s increases with P. We rigorously prove that in the limit both N s and M, the degree on each subdomain, increase simultaneously, the approximation error converges proportionally to exp ( − constant P log ( P ) ) . Thus, division into ever-shrinking, ever-more-numerous subdomains is guaranteed to defeat the Runge Phenomenon in infinite precision arithmetic. (Numerical ill-conditioning is also discussed, but is not a great difficulty in practice, though not insignificant in theory.) Although a Chebyshev grid on each subdomain is well known to be immune to the Runge Phenomenon, it is still interesting, and the same methodology can be applied as to a uniform grid. When a Chebyshev grid is used on each subdomain, there are two regimes. If c is the distance from the middle of the interval [ − 1 , 1 ] to the nearest singularity of f ( x ) in the complex plane, then when c N s ≪ 1 , the error is proportional to exp ( − c P ) , independent of the number of subdomains. When c N s ≫ 1 , the rate of convergence slows to exp ( − constant P log ( P ) ) , the same as for equispaced interpolation. However, the Chebyshev multidomain error is always smaller than the equispaced multidomain error.