Numerical Differentiation of Approximated Functions with Limited Order-of-Accuracy Deterioration

We consider the problem of numerical differentiation of a function f from approximate or noisy values of f on a discrete set of points; such discrete approximate data may result from a numerical calculation (such as a finite element or finite difference solution of a partial differential equation), from experimental measurements, or, generally, from an estimate of some sort. In some such cases it is useful to guarantee that orders of accuracy are not degraded: assuming the approximating values of the function are known with an accuracy of order O(h^r), where h is the mesh size, an accuracy of O(h^r) is desired in the value of the derivatives of f. Differentiation of interpolating polynomials does not achieve this goal since, as shown in this text, n-fold differentiation of an interpolating polynomial of any degree ≥ (r − 1) obtained from function values containing errors of order O(h^r) generally gives rise to derivative errors of order O(h^(r−n)); other existing differentiation algorithms suffer from similar degradations in the order of accuracy. In this paper we present a new algorithm, the LDC method (low degree Chebyshev), which, using noisy function values of a function f on a (possibly irregular) grid, produces approximate values of derivatives f^((n)) (n = 1, 2 . . .) with limited loss in the order of accuracy. For example, for (possibly nonsmooth) O(h^r) errors in the values of an underlying infinitely differentiable function, the LDC loss in the order of accuracy is “vanishingly small”: derivatives of smooth functions are approximated by the LDC algorithm with an accuracy of order O(h^r) for all r' < r. The algorithm is very fast and simple; a variety of numerical results we present illustrate the theory and demonstrate the efficiency of the proposed methodology