You can get away with high-degree polynomial interpretation if you have control over the node locations, see for example Nick Trefethen's chebfun: http://www.chebfun.org and book: https://people.maths.ox.ac.uk/trefethen/ATAP/