Abstract
The numerical differentiation of data divides naturally into two distinct problems:
-
(i)
the differentiation of exact data, and
-
(ii)
the differentiation of non-exact (experimental) data.
In this paper, we examine the latter. Because methods developed for exact data are based on abstract formalisms which are independent of the structure within the data, they prove, except for the regularization procedure of Cullum, to be unsatisfactory for non-exact data. We therefore adopt the point of view that satisfactory methods for non-exact data must take the structure within the data into account in some natural way, and use the concepts of regression and spectrum analysis as a basis for the development of such methods. The regression procedure is used when either the structure within the non-exact data is known on independent grounds, or the assumptions which underlie the spectrum analysis procedure [viz., stationarity of the (detrended) data] do not apply. In this latter case, the data could be modelled using splines. The spectrum analysis procedure is used when the structure within the nonexact data (or a suitable transformation of it, where the transformation can be differentiated exactly) behaves as if it were generated by a stationary stochastic process. By proving that the regularization procedure of Cullum is equivalent to a certain spectrum analysis procedure, we derive a fast Fourier transform implementation for regularization (based on this equivalence) in which an acceptable value of the regularization parameter is estimated directly from a time series formulation based on this equivalence. Compared with the regularization procedure, which involvesO(n 3) operations (wheren is the number of data points), the fast Fourier transform implementation only involvesO(n logn).
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Anderssen, R. S., Bloomfield, P.: A time series approach to numerical differentiation. Technometrics (in press)
Anderssen, R. S., Seneta, E.: On smoothing techniques for the removal of periodic noise of known period. Math. Geol.3, 157–170 (1971)
Bickley, W. G.: Formulae for numerical differentiation. Math. Gaz.25, 19–27 (1941)
Birkhoff, G., de Boor, Carl: Error bounds for spline interpolation. J. Math. and Mech.13, 827–835 (1964)
Björck, Åke, Pereyra, Victor: Solution of Van der Monde systems of equations. Math. Comp.24, 893–903 (1970)
de Boor, C., Rice, J. R.: Least squares cubic spline approximation, I—Fixed Knots, II—Variable Knots. Computer Science Department Tech. Report #20 and 21, Purdue University, April, 1968
Box, G. E. P., Jenkins, G. M.: Time series analysis, forecasting and control, San Francisco. Holden-Day 1970
Brodskii, M. L.: Estimation of the remainder term in formulas of numerical differentiation [Russian], Uspekhi Mat. Nauk13 (6), 73–77 (1958)
Burchard, H. G.: Splines (with optimal knots) are better. Applicable Anal. (1973), to appear
Chakravarti, P. C.: Truncation error in interpolation and numerical differentiation, Numer. Math.3, 279–284 (1961)
Cooley, J. W., Tukey, J. W.: An algorithm for the machine calculation of complex Fourier series. Math. Comp.19, 297–301 (1965)
Cullum, J.: Regularization and numerical differentiation. IBM Research Report RC2605, Sept. 1969
Cullum, J.: Numerical differentiation and regularization. SIAM J. Numer. Anal.8, 254–265 (1971)
Dolgopolova, T. F., Ivanov, V. K.: On numerical differentiation. USSR Comp. Math. and Math. Phys.6 (4), 223–232 (1966)
Doob, J. L.: Stochastic processes. New York: John Wiley 1953
Engels, H.: Zur Anwendung der Richardson-Extrapolation auf die numerische Differentiation. Computing8, 255–272 (1971)
Galimberti, G., Pereyra, V.: Numerical differentiation and the solution of multidimensional Van der Monde systems. Math. Comp.24, 357–364 (1970)
Gentleman, W. M., Sande, G.: Fast Fourier transforms—for fun and profit. Proc. Fall Joint Computer Conference (1966), 563–578
Grenander, U., Rosenblatt, M.: Statistical analysis of stationary time series. New York: John Wiley 1957
Hamming, R. W.: Numerical methods for scientists and engineers. New York: McGraw-Hill 1963
Hamming, R. W.: The frequency approach to numerical analysis. In: Studies in numerical analysis: Papers presented to Cornelius Lanczos. London: Academic Press 1973
Hannan, E. J.: Time series analysis. London: Methuen 1960
Hannan, E. J.: Multiple time series. New York: John Wiley 1970
Hestenes, M.: Calculus of variations and optimal control theory. New York: John Wiley 1966
de Hoog, F., Weiss, R.: High order methods for first kind Volterra equations. SIAM J. Numer. Anal.10, 647–664 (1973)
de Hoog, F., Weiss, R.: On the solution of Volterra integral equations of the first kind. Numer. Math.21, 22–32 (1973)
Hunter, D. B.: An iterative method of numerical differentiation. Computer J.3, 270–271 (1960)
Jenkins, G. M., Watts, D. G.: Spectral analysis and its application. San Francisco: Holden-Day 1968
Khintchine, A. Ya.: Korrelationstheorie der stationaren stochastischen Prozesse. Math. Ann.109, 604–616 (1934)
Kranzer, H. C.: An error formula for numerical differentiation. Numer. Math.5, 439–442 (1963)
Lyness, J. N.: Numerical approximations based on the theory of complex variable. Proc. 22nd Nat. Conf. ACM Publication P-67, (1967), pp. 125–133
Lyness, J. N.: Differentiation formulas for analytic functions. Math. Comp.22, 352–362 (1968)
Lyness, J. N., Moler, C. B.: Numerical differentiation of analytic functions. SIAM J. Numer. Anal.4, 202–210 (1966)
Lyness, J. N., Moler, C. B.: Van der Monde systems and numerical differentiation. Numer. Math.8, 458–464 (1966)
Mood, A. M., Graybill, F. A.: Introduction to the theory of statistics, 2nd edition. New York: McGraw-Hill 1963
Pallaghy, C. K., Lüttge, U.: Light-induced and H+-ion fluxes and bioelectric phenomena in mesophyll cells of Atriplex spongiosa. Zeit. für Pflanz.62, 417–425 (1970)
Powell, M. J. D.: The local dependence of least squares cubic splines. SIAM J. Numer. Anal.6, 398–413 (1969)
Ralston, A.: A first course in numerical analysis. New York: McGraw-Hill 1965
Salzer, H. E.: Optimal points for numerical differentiation. Numer. Math.2, 214–227 (1960)
Salzer, H. E.: Equally-weighted formulas for numerical differentiation. Numer. Math.4, 381–392 (1963)
Schönhage, A.: Optimale Punkte für Differentiation und Integration. Numer. Math.5, 303–331 (1963)
Secrest, Don: Error bounds for interpolation and differentiation by the use of spline functions. SIAM J. Numer. Anal.2, 440–447 (1965)
Strom, Torsten: An inclusion formula for derivatives. BIT11, 196–198 (1971)
Tsuda, T.: Numerical differentiation of functions of very many variables. Numer. Math.18, 327–335 (1972)
Tukey, J. W.: An introduction to the calculations of numerical spectrum analysis. In: The spectral analysis of time series, ed. B. Harris. New York: John Wiley 1967
Vedeneev, E. P., Zhidkov, N. P.: The application of the method of regularization to the differentiation of a function of one variable, given as data [Russian]. Numerical Methods and Programming3, 255–261 (1969)
Wiener, N.: Generalised harmonic analysis. Acta Math.55, 117–258 (1930)
Wilkinson, J. H., Reinsch, C.: Linear Algebra, Die Grundlehren der mathematischen Wissenschaften, Band 186. Berlin-Heidelberg-New York: Springer 1971
Author information
Authors and Affiliations
Additional information
This research was performed with the support of (a) the Office of Naval Research under contract 0014-67-A-0151-0017 and (b) the U.S. Army Research Office—Durham, under contract DA-31-124-ARO-D-215. An earlier version appeared in preprint form as Technical Report 13, Series 2, Department of Statistics, Princeton University, April, 1972.
Rights and permissions
About this article
Cite this article
Anderssen, R.S., Bloomfield, P. Numerical differentiation procedures for non-exact data. Numer. Math. 22, 157–182 (1974). https://doi.org/10.1007/BF01436965
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF01436965