Stable computation of multiquadric interpolants for all values of the shape parameter

Spectrally accurate interpolation and approximation of derivatives used to be practical only on highly regular grids in very simple geometries. Since radial basis function (RBF) approximations permit this even for multivariate scattered data, there has been much recent interest in practical algorithms to compute these approximations effectively. Several types of RBFs feature a free parameter (e.g., c in the multiquadric, (MQ) case phi(r) = rootr(2)+c(2)). The limit of c --> infinity (increasingly flat basis functions) has not received much attention because it leads to a severely ill-conditioned problem. We present here an algorithm which avoids this difficulty, and which allows numerically stable computations of MQ RBF interpolants for all parameter values. We then find that the accuracy of the resulting approximations, in some cases, becomes orders of magnitude higher than was the case within the previously available parameter range. Our new method provides the first tool for the numerical exploration of MQ RBF interpolants in the limit of c --> infinity. The method is in no way specific to MQ basis functions and can-without any change-be applied to many other cases as well. (C) 2004 Elsevier Ltd. All rights reserved.