Tricki
a repository of mathematical know-how

Numerical integration and differentiation

Quick description

Given a function f\colon {\R}^m\to {\R}, compute (approximately) the definite integral

 \int_A f(x)\, dx,

for some subset A\subseteq {\R}^m or to compute (approximately) the a derivatives \nabla f({\bold x}), or \partial^2 f/\partial x_i\partial x_j({\bold x}) etc., using only a finite (or small) number of function evaluations f({\bold x}_i), i=1, 2, \ldots, N.

The most efficient numerical integration methods have been developed for scalar problems (m=1), including methods such as Gauss quadrature and Romberg integration. But there are good methods for many regions in higher dimensions. Regions with high dimensionality (e.g., m\geq 6) are a particular challenge, as are integrands with singularities or localized "spikes".

Prerequisites

Calculus, interpolation.

Example 1: Integrate (or differentiate) the interpolant

If you have an effective and accurate method of interpolation, you can use that to construct an integration method as the integral of the interpolant.

Example 2: If you have a singularity that has an simple form, use product integration methods

For example, for computing integrals of the form

 \int_0^1 x^\alpha\,f(x)\,dx,

where f is smooth on [0,1], determine a polynomial interpolant p of f, and compute

 \int_0^1 x^\alpha\,p(x)\,dx.

This technique is also useful for dealing with smooth functions with localized "spikes" that would otherwise require very many integration points, even with adaptive methods: for example, consider computing

 \int_a^b k^{1/2}\,e^{-kx^2}\,f(x)\,dx

with k\gg 1. By using an interpolant of f on [a,b] and computing the resulting integral exactly, the only errors incurred are due to the interpolation of f, not the fact that the integral has a "spike".

General discussion

Comments

More examples

Some examples for multidimensional integration would be nice to see here.

To find the nth derivitive of f(x):

Use any value δ, which can be made small enough to approximate the derivitive to an arbitrary number of decimal places.
f'(x)≃(f(x+δ)-f(x))/δ
f''(x) ((f(x+2δ)-f(x+δ))-(f(x+δ)-f(x)))/δ=f(x+2δ)-2f(x+δ)+f(x)
f'''(x) (f(x+3δ)-f(x+2δ)+f(x+δ)-f(x))/δ
The pattern continues. The nth derivitive is
....................n
...................⎲
f(x+nδ)/δ+ ⎳ n(-1)^k f(x+kδ)/δ
...................k=1

The dots are there because the computer won't show spaces properly.

Angela, I think you missed

Angela, I think you missed some coefficients, correct expression should be,

f'''(x)\simeq\frac{f(x+3\delta)-3 f(x+2\delta)+3 f(x+\delta)-f(x)}{\delta^3}

And I'm sorry but its really difficult to understand the formula you write for n^{th} derivative. I think the expression you wanted to write is the following-

f^{(n)}(x)\simeq\Big(\sum\limits_{ k=0}^n (-1)^{n-k}{n \choose k}f(x+k\delta)\Big)/\delta^n