×

Six strategies for defeating the Runge phenomenon in Gaussian radial basis functions on a finite interval. (English) Zbl 1207.41011

Summary: Radial basis function (RBF) interpolation is a “meshless” strategy with great promise for adaptive approximation. Because it is meshless, there is no canonical grid to act as a starting point for function-adaptive grid modification. Uniform grids are therefore common with RBFs. Like polynomial interpolation, which is the limit of RBF interpolation when the RBF functions are very wide (the “flat limit”), RBF interpolants are vulnerable to the Runge Phenomenon, whether the grid is uniform or irregular: the \(N\)-point interpolant may diverge as \(N\rightarrow \infty \) on the interval spanned by the interpolation points even for a function \(f(x)\) that is analytic everywhere on and near this interval.In this work, we discuss six strategies for defeating the Runge Phenomenon, specializing to a uniform grid on a finite interval and one particular species of RBFs in one space dimension: \(\phi(x)=\exp( -[\alpha ^{2}/h^{2}]x^{2})\) where \(h\) is the grid spacing. Three strategies fail, but three are successful. One good strategy is to vary \(\alpha \) with the number of interpolation points \(N\) as \(N^{ - 1/4}\). Unfortunately this gives both a subgeometric rate of convergence for the approximation (error falling as \(\exp(-q\sqrt{N})\) for some constant \(q\)) and a matrix condition number that grows as \(\exp(p\sqrt{N})\) for some \(p>0\). (in order to explain why \(fixed \alpha \), independent of \(N\), is not a convergent strategy, we digress to discuss error saturation, and show experimentally that the saturation error on the finite interval is about \(0.6exp( -0.47/\alpha ^{2})\| f\|\infty \); if a user-chosen error tolerance \(\delta \) is acceptable, then the optimum choice is \(\alpha_{optimum}(\delta)=1/\sqrt{--2\log(\delta/0.06)})\). The second good strategy is RBF Extension, which uses RBF functions with centers on a interval slightly larger than the target interval to approximate \(f(x)\). A third strategy is to split the interval into two “boundary layers” and a large middle interval and apply separate RBF approximations on each. The slow-decrease-of-\(\alpha \) strategy is much cheaper, but RBF Extension is much more resistant to ill-conditioning and therefore can achieve much lower errors. The three-interval method is the least accurate, but is robust and inexpensive.

MSC:

41A30 Approximation by other special function classes
65D05 Numerical interpolation

Software:

Matlab
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Buhmann, M. D., (Radial Basis Functions: Theory and Implementations. Radial Basis Functions: Theory and Implementations, Cambridge Monographs on Applied and Computational Mathematics, vol. 12 (2003), Cambridge University Press) · Zbl 1038.41001
[2] Wendland, H., Scattered Data Approximation (2005), Cambridge University Press · Zbl 1075.65021
[3] Buhmann, M. D., Radial basis functions, Acta Numer., 9, 1-38 (2000) · Zbl 1004.65015
[4] Schaback, R.; Wendland, H., Kernel techniques: from machine learning to meshless methods, Acta Numer., 15, 543-639 (2006) · Zbl 1111.65108
[5] Fasshauer, G. E., Newton iteration with multiquadrics for the solution of nonlinear PDEs, Comput. Math. Appl., 43, 423-438 (2002) · Zbl 0999.65136
[6] Chinchapatnam, P. P.; Djidjeli, K.; Nair, P. B., Unsymmetric and symmetric meshless schemes for the unsteady convection-diffusion equation, Comput. Methods Appl. Mech. Engrg., 195, 2432-2453 (2006) · Zbl 1125.76053
[7] Fedoseyev, A. I.; Friedman, M. J.; Kansa, E. J., Continuation for nonlinear elliptic partial differential equations discretized by the multiquadric method, Internat. J. Bifur. Chaos, 10, 481-492 (2000) · Zbl 1090.65550
[8] Fedoseyev, A. I.; Friedman, M. J.; Kansa, E. J., Improved multiquadric method for elliptic partial differential equations via PDE collocation on the boundary, Comput. Math., 43, 439-455 (2002) · Zbl 0999.65137
[9] Platte, R. B.; Driscoll, T. A., Polynomials and potential theory for Gaussian radial basis function interpolation, SIAM J. Numer. Anal., 43, 750-766 (2005) · Zbl 1088.65009
[10] Fornberg, B.; Zuev, J., The Runge Phenomenon and spatially variable shape parameters in RBF interpolation, Comput. Math. Appl., 54, 379-398 (2007) · Zbl 1128.41001
[11] Boyd, J. P.; Xu, F., Divergence (Runge Phenomenon) for least-squares polynomial approximation on an equispaced grid grid and Mock-Chebyshev subset interpolation, Appl. Math. Comput., 210, 158-168 (2009) · Zbl 1171.41004
[12] Boyd, J. P., Defeating the Runge Phenomenon for equispaced polynomial interpolation via Tikhonov regularization, Appl. Math. Lett., 5, 57-59 (1992) · Zbl 0760.65007
[13] Boyd, J. P., Exponentially accurate Runge-free approximation of non-periodic functions from samples on an evenly-spaced grid, Appl. Math. Lett., 188, 1780-1789 (2007) · Zbl 1121.65049
[14] Boyd, J. P.; Ong, J. R., Exponentially-convergent strategies for defeating the Runge Phenomenon for the approximation of non-periodic functions, part I: single-interval schemes, Commun. Comput. Phys., 5, 484-497 (2009) · Zbl 1364.65025
[15] J.P. Boyd, J.R. Ong, Exponentially-convergent strategies for defeating the Runge Phenomenon for the approximation of non-periodic functions, part II: multi-interval schemes, Appl. Numer. Math. (2009) (submitted for publication).; J.P. Boyd, J.R. Ong, Exponentially-convergent strategies for defeating the Runge Phenomenon for the approximation of non-periodic functions, part II: multi-interval schemes, Appl. Numer. Math. (2009) (submitted for publication). · Zbl 1364.65025
[16] Fornberg, B.; Flyer, N., Accuracy of radial basis function interpolation and derivative approximations on 1-D infinite grids, Adv. Comput. Math., 23, 5-20 (2005) · Zbl 1067.65015
[17] Boyd, J. P.; Wang, L., Truncated Gaussian RBF differences are always inferior to finite differences of the same stencil width, Commun. Comput. Phys., 5, 42-60 (2009) · Zbl 1364.65262
[18] Boyd, J. P.; Wang, L., An analytic approximation to the cardinal functions of Gaussian radial basis functions on a one-dimensional infinite uniform lattice, Appl. Math. Comput., 215, 2215-2223 (2009) · Zbl 1178.65012
[19] Boyd, J. P.; Wang, L., Asymptotic coefficients for Gaussian radial basis function interpolants, Appl. Math. Comput., 216, 2394-2407 (2010) · Zbl 1200.41001
[20] J.P. Boyd, L. Wang, A Fourier error analysis for Gaussian radial basis functions on an infinite uniform grid, Commun. Comput. Phys. (2011) (in press).; J.P. Boyd, L. Wang, A Fourier error analysis for Gaussian radial basis functions on an infinite uniform grid, Commun. Comput. Phys. (2011) (in press).
[21] Fasshauer, G. F., (Meshfree Approximation Methods with MATLAB. Meshfree Approximation Methods with MATLAB, Interdisciplinary Mathematical Sciences (2007), World Scientific Publishing Company: World Scientific Publishing Company Singapore)
[22] Driscoll, T. A.; Heryudono, A., Adaptive residual subsampling methods for radial basis function interpolation and collocation problems, Comput. Math. Appl., 53, 927-939 (2007) · Zbl 1125.41005
[23] Boyd, J. P., Chebyshev and Fourier Spectral Methods (2001), Dover: Dover Mineola, New York, 665 pp · Zbl 0987.65122
[24] Trefethen, L. N.; Bau, D., Numerical Linear Algebra (1997), Society for Industrial and Applied Mathematics (SIAM): Society for Industrial and Applied Mathematics (SIAM) Philadelphia · Zbl 0874.65013
[25] Maz’ya, V.; Schmidt, G., On approximate approximation using Gaussian kernels, IMA J. Numer. Anal., 16, 13-29 (1996) · Zbl 0838.65005
[26] Boyd, J. P.; Bridge, L. R., Sensitivity of RBF interpolation on an otherwise uniform grid with a point omitted or slightly shifted, Appl. Numer. Math., 60, 659-672 (2010) · Zbl 1193.65014
[27] Boyd, J. P., Error saturation in Gaussian radial basis functions on a finite interval, J. Comput. Appl. Math., 234, 1435-1441 (2010) · Zbl 1189.65023
[28] J.P. Boyd, K.W. Gildersleeve, Numerical experiments on the condition number of the interpolation matrices for radial basis functions, Appl. Math. Comput. (2009) (submitted for publication).; J.P. Boyd, K.W. Gildersleeve, Numerical experiments on the condition number of the interpolation matrices for radial basis functions, Appl. Math. Comput. (2009) (submitted for publication). · Zbl 1208.65056
[29] Emdadi, A.; Kansa, E. J.; Libre, N. A.; Rahimian, M.; Shekarchi, M., Stable PDE solution methods for large multiquadric shape parameters, CMES Comput. Model. Eng. Sci., 25, 23-41 (2008) · Zbl 1232.65154
[30] Libre, N. A.; Emdadi, A.; Kansa, E. J.; Rahimian, M.; Shekarchi, M., A stabilized RBF collocation scheme for Neumann type boundary value problems, CMES Comput. Model. Eng. Sci., 24, 61-80 (2008) · Zbl 1232.65156
[31] Volokh, K. Y.; Vilnay, O., Pin-pointing solution of ill-conditioned square systems of linear equations, Appl. Math. Lett., 13, 119-124 (2000) · Zbl 0955.65031
[32] Brown, D.; Ling, L.; Kansa, E.; Levesley, J., On approximate cardinal preconditioning methods for solving PDEs with radial basis functions, Eng. Anal. Bound. Elem., 29, 343-353 (2005) · Zbl 1182.65174
[33] Dyn, N.; Levin, D.; Rippa, S., Numerical procedures for surface fitting of scattered data by radial functions, SIAM J. Sci. Comput., 7, 639-659 (1986) · Zbl 0631.65008
[34] Ling, L. V.; Kansa, E. J., Preconditioning for radial basis functions with domain decomposition methods, Math. Comput. Modelling, 40, 1413-1427 (2004) · Zbl 1077.41008
[35] Ling, L. V.; Kansa, E. J., A least-squares preconditioner for radial basis functions collocation methods, Adv. Comput. Math., 23, 31-54 (2005) · Zbl 1067.65136
[36] Schaback, R., Multivariate interpolation by polynomials and radial basis functions, Constr. Approx., 21, 293-317 (2005) · Zbl 1076.41003
[37] Schaback, R., Limit problems for interpolation by analytic radial basis functions, J. Comput. Appl. Math., 212, 127-149 (2008) · Zbl 1129.41002
[38] Fornberg, B.; Piret, C., A stable algorithm for flat radial basis functions on a sphere, SIAM J. Sci. Comput., 30, 60-80 (2007) · Zbl 1159.65307
[39] Boyd, J. P., A comparison of numerical algorithms for Fourier extension of the first, second and third kinds, J. Comput. Phys., 178, 118-160 (2002) · Zbl 0999.65132
[40] Boyd, J. P., Fourier embedded domain methods: extending a function defined on an irregular region to a rectangle so that the extension is spatially periodic and \(C^\infty \), Appl. Math. Comput., 161, 591-597 (2005) · Zbl 1061.65127
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.