Logo

Numerical examples





Computation of an infinite integral using a dynamical extrapolation method

Let us consider the integral $K(a)=\int_0^{+\infty} f(x) dx$ with $f(x)=(\exp ^{x} + \exp^{-x})^a - \exp^{ax} - \exp^{-ax}$ and $0 < a < 2$.

This integral arises in a study of the total electronic energy of crystals using the tight binding approximation [2]. The evaluation of $K(\frac{5}{3})$ was a problem posed in [4].

$K(a)$ is computed using Romberg's integration method with the CADNA library.

A theorem like those given in [1] has been established for the dynamical control of Romberg's method [3]. Combining it with two similar theorems, we can estimate the number of exact significant digits of the result obtained, which are common with the exact value of the infinite integral (including both the truncation error and the round-off error).


To combine efficiency and reliability the same expression of $f$ is not used at both bounds of the interval. One worry is to avoid cancellations at the infinite bound of the interval.

Therefore $K(a)$ is computed as $K(a)=\int_0^l f_1(x) dx + \int_l^{+\infty} f_2(x) dx$, $l \in \mbox{R\hspace{-0.13in}I } ^{+*}$,

where $f_1(x)=\exp^{ax} \left( \left( 1 + \exp^{-2x} \right) ^a - 1 - \exp^{-2ax} \right)$

and $f_2(x)=\exp^{x\left(a-2\right)} s(x) -\exp^{-ax}$, with $s(x)=
\sum_{i=1}^{+\infty}\frac{a(a-1)...(a-i+1)}{i!}\left(\exp^{-2x} \right)^{(i-1)}$

Functions $f_1$ and $f_2$ are mathematically equivalent, but not numerically !


$s(x) = lim_{n \rightarrow \infty} s_n(x)$, with $s_n(x)=\sum_{i=1}^{n}\frac{a(a-1)...(a-i+1)}{i!}\left(\exp^{-2x} \right)^{(i-1)}$.

$s(x)$ is approximated by an iterate of the sequence $(s_n(x))$.

How to choose the optimal iterate $s_n(x)$ ? Iterations are performed until the difference between two successive iterates is not significant. Using the CADNA library, the stopping criterion is $s_n(x)=s_{n+1}(x)$.

Computations stop if $s_n(x)$ and $s_{n+1}(x)$ are stochastically equal, i.e. if the transformation of $s_n(x)$ into $s_{n+1}(x)$ is only due to round-off errors. Further iterations are useless.

We have shown that if $l\leq \frac{log(2)}{2} $, for all $x \in [l,+\infty[$, the exact significant bits of the optimal iterate $s_n(x)$ are those of $s(x)$, up to one.


$K(a)=\int_0^l f_1(x)dx +  \sum_{j=1}^{+\infty} \int_{jl}^{(j+1) l } f_2(x)dx$

$K(a)$ is approximated by computing integrals on intervals of length $l$.

Each of these integrals is computed using Romberg's method.

The approximation of an integral with Romberg's method is an iterate of a sequence which converges with an exponential speed to the exact value of this integral.

How to choose the optimal iterate ?

Approximations are computed until the difference between two successive iterates is not significant.

We have shown that, for each integral, the approximation obtained has its exact significant bits common to the exact value of the integral, up to one.


$K(a)=\int_0^l f_1(x)dx +  lim_{k \rightarrow \infty} I_k$ with $I_k = \sum_{j=1}^{k} \int_{jl}^{(j+1) l } f_2(x)dx$

How to choose the optimal iterate $I_k$ ? Iterations are performed until the difference between two successive iterates is not significant.

Finally we have shown that using the CADNA library and the stopping criteria previously described, we can estimate the number of exact significant digits of the approximation of $K(a)$ obtained, which are common with the exact value of the integral.



References

1
J.-M. Chesneaux, F. Jézéquel, Dynamical control of computations using the trapezoidal and Simpson's rules, Journal of Universal Computer Science, Vol. 4 (1), pp. 2-10, 1998.

2
W. Harrison, Total energies in the tight-binding theory, Phys. Rev., B23 (1981), pp. 5230-5245

3
F. Jézéquel, Dynamical control of computations using approximation methods, 16th IMACS world congress on Scientific Computation, Applied Mathematics and Simulation, Lausanne (Switzerland), August 2000.

4
Problem 95-7, SIAM Review, V 38, N 2, pp.324, 1996.




To get the C source code.

To get the FORTRAN source code.


More information can be requested to the CADNA team
Thanks to Baptiste Mary for the CADNA logo