Review article on verification methods
To everybody interested in reliable computing:
My 163-pages review article on verification methods is now published in
Acta Numerica:
S.M. Rump. Verification methods: Rigorous results using floating-point
arithmetic.
Acta Numerica, pages 287–449, 2010.
From the abstract:
This review article is devoted to verification methods and consists of
three
parts of similar length. In Part 1 the working tools of verification
methods
are discussed, in particular floating-point and interval arithmetic; my
findings
in Section 1.5 (Historical remarks) seem new, even to experts in the field.
In Part 2, the development and limits of verification methods for
finite-dimensional
problems are discussed in some detail. In particular, we discuss how
verification is _not_ working. For example, we give a probabilistic
argument
that the so-called interval Gaussian elimination (IGA) does not work even
for
(well-conditioned) random matrices of small size. Verification methods are
discussed for problems such as dense systems of linear equations, sparse
linear
systems, systems of nonlinear equations, semi-definite programming and
other
special linear and nonlinear problems, including M-matrices, finding simple
and multiple roots of polynomials, bounds for simple and multiple
eigenvalues
or clusters, and quadrature. The necessary automatic differentiation tools
to
compute the range of gradients, Hessians, Taylor coefficients, and slopes
are
also introduced.
Concerning the important area of optimization, Neumaier (2004) gave in
his Acta Numerica article an overview on global optimization and constraint
satisfaction methods. In view of the thorough treatment there, showing the
essential role of interval methods in this area, we restrict our
discussion to a
few recent, complementary issues.
Finally, in Part 3, verification methods for infinite-dimensional
problems
are presented, namely two-point boundary value problems and semilinear
elliptic boundary value problems.
Throughout the article, many examples of the inappropriate use of
interval
operations are given. In the past such examples contributed to the dubious
reputation of interval arithmetic (see Section 1.3), whereas they are, in
fact,
simply a misuse.
One main goal of this review article is to introduce the principles of
the
design of verification algorithms, and how these principles differ from
those
for traditional numerical algorithms (see Section 1.4).
Many algorithms are presented in executable MATLAB/INTLAB code,
providing the opportunity to test the methods directly. INTLAB, the MATLAB
toolbox for reliable computing, was, for example, used by Bornemann,
Laurie, Wagon and Waldvogel (2004) in the solution of half of the problems
of the SIAM 10x10-digit challenge by Trefethen (2002).
A preversion of the article can be downloaded from my homepage
www.ti3.tu-harburg.de
Comments always welcome !
Best wishes,
Siegfried M. Rump
--
=====================================================
Prof. Dr. Siegfried M. Rump
Institute for Reliable Computing
Hamburg University of Technology
Schwarzenbergstr. 95
21071 Hamburg
Germany
phone +49 40 42878 3027
fax +49 40 42878 2489
http://www.ti3.tu-harburg.de
and
Visiting Professor at Waseda University
Faculty of Science and Engineering
Shinjuku Lambdax Bldg. 902
2-4-12 Okubo, Shinjuku-ku
Tokyo 169-0072
Japan
phone/fax in Japan +81 3 5286 3414