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 /(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,11 to the nearest singularity of /(x) in the complex plane, then when cN_s 《 1, the error is proportional to exp(—cP), independent of the number of subdomains. When cN_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.