Thirty years of G-stability

The 1976 paper of G. Dahlquist, [13], has had a wide-ranging impact on our understanding of numerical methods for the solution of stiff differential equation systems. The present paper surveys some of the work of Dahlquist in this area. It also shows how this has led to contributions by other authors. In particular, the paper contains a review of non-linear stability for Runge–Kutta and general linear methods. In memory of Germund Dahlquist (1925–2005).AMS subject classification (2000) 65L05, 65L06, 65L20     

Symmetric linear multistep methods

Some important early contributions of Germund Dahlquist are reviewed and their impact to recent developments in the numerical solution of ordinary differential equations is shown. This work is an elaboration of a talk presented in the Dahlquist session at the SciCADE05 conference in Nagoya. In memory of Germund Dahlquist (1925–2005).AMS subject classification (2000) 65L06, 65P10     

Dahlquist’s classical papers on stability theory

This text, which is based on the author’s talk in honour of G. Dahlquist at the SciCade05 meeting in Nagoya, describes the two classical papers from 1956 and 1963 of Dahlquist and their enormous impact on the research of decades to come; it also allows the author to present a personal testimony of his never ending admiration for the scientific and personal qualities of this great man.In memory of Germund Dahlquist (1925–2005).AMS subject classification (2000) 65F05, 65F07     

Identification of distributed systems and the theory of the regularization

The identification problems, i.e., the problems of finding unknown parameters in distributed systems from the observations are very important in modern control theory. The solutions of these identification problems can be obtained by solving the equations of the first kind. However, the solutions are often unstable. In other words, they are not continuously dependent on the data. The regularization or Tihonov's regularization is known as one of the stabilizing algorithms to solve these non well-posed problems. In this paper is studied the regularization method for identification of distributed systems. Several approximation theorems are proved to solve the equations of the first kind. Then, identification problems are reduced to the minimization of quadratic cost functionals by virtue of these theorems. On the other hand, it is known that the statistical methods for identification such as the maximum likelihood lead to the minimization problems of certain quadratic functionals. Comparing these quadratic cost functionals, the relations between the regularization and the statistical methods are discussed. Further, numerical examples are given to show the effectiveness of this method.     

Besov regularization,thresholding and wavelets for smoothing data

Smoothing of data is a problem very important for many applications ranging from 1-D signals (e.g., speech) to 2-D and 3-D signals (e.g., images). Many methods exist in the literature for facing the problem; in the present paper we point our attention on regularization. We shall treat regularization methods in a general framework which is well suited for wavelet analysis; in particular we shall investigate on the relation existing between thresholding methods and regularization. We shall also introduce a new regularization method (Besov regularization), which includes some known regularization and thresholding methods as particular cases. Numerical experiments based on some test problems will be performed in order to compare the performance of some methods of smoothing data.

AMS (MOS) Subject Classifications: 65R30, 41A60.     

A new zero-finder for Tikhonov regularization

Tikhonov regularization with the regularization parameter determined by the discrepancy principle requires the computation of a zero of a rational function. We describe a cubically convergent zero-finder for this purpose. AMS subject classification (2000)  65F22, 65H05, 65R32     

Regularization for unconstrained vector optimization of convex functionals in Banach spaces

An operator regularization method is considered for ill-posed vector optimization of weakly lower semicontinuous essentially convex functionals on reflexive Banach spaces. The regularization parameter is chosen by a modified generalized discrepancy principle. A condition for the estimation of the convergence rate of regularized solutions is derived. This article was submitted by the author in English.     

The residual method for regularizing ill-posed problems

Although the residual method, or constrained regularization, is frequently used in applications, a detailed study of its properties is still missing. This sharply contrasts the progress of the theory of Tikhonov regularization, where a series of new results for regularization in Banach spaces has been published in the recent years. The present paper intends to bridge the gap between the existing theories as far as possible. We develop a stability and convergence theory for the residual method in general topological spaces. In addition, we prove convergence rates in terms of (generalized) Bregman distances, which can also be applied to non-convex regularization functionals.We provide three examples that show the applicability of our theory. The first example is the regularized solution of linear operator equations on L^p-spaces, where we show that the results of Tikhonov regularization generalize unchanged to the residual method. As a second example, we consider the problem of density estimation from a finite number of sampling points, using the Wasserstein distance as a fidelity term and an entropy measure as regularization term. It is shown that the densities obtained in this way depend continuously on the location of the sampled points and that the underlying density can be recovered as the number of sampling points tends to infinity. Finally, we apply our theory to compressed sensing. Here, we show the well-posedness of the method and derive convergence rates both for convex and non-convex regularization under rather weak conditions.     

Local error estimation for multistep collocation methods

Multistep collocation methods for initial value problems in ordinary differential equations are known to be a subclass of multistep Runge-Kutta methods and a generalisation of the well-known class of one-step collocation methods as well as of the one-leg methods of Dahlquist. In this paper we derive an error estimation method of embedded type for multistep collocation methods based on perturbed multistep collocation methods. This parallels and generalizes the results for one-step collocation methods by Nørsett and Wanner. Simple numerical experiments show that this error estimator agrees well with a theoretical error estimate which is a generalisation of an error estimate first derived by Dahlquist for one-leg methods.     

Relaxation of Nonlocal Singular Integrals

In this paper we study well-posedness of a class of nonconvex variational principles arising in regularization theory for denoising of data with sampling errors and level set regularization methods for inverse problems. These models result in minimization of nonconvex, singular functionals involving (possibly) non-local operators.     

Adaptive partitioning techniques for ordinary differential equations

Many stiff systems of ordinary differential equations (ODEs) modeling practical problems can be partitioned into loosely coupled subsystems. In this paper the objective of the partitioning is to permit the numerical integration of one time step to be performed as the solution of a sequence of small subproblems. This reduces the computational complexity compared to solving one large system and permits efficient parallel execution under appropriate conditions. The subsystems are integrated using methods based on low order backward differentiation formulas.This paper presents an adaptive partitioning algorithm based on a classical graph algorithm and techniques for the efficient evaluation of the error introduced by the partitioning.The power of the adaptive partitioning algorithm is demonstrated by a real world example, a variable step-size integration algorithm which solves a system of ODEs originating from chemical reaction kinetics. The computational savings are substantial. In memory of Germund Dahlquist (1925–2005).AMS subject classification (2000) 65L06, 65Y05     

Iterative methods for the reconstruction of astronomical images with high dynamic range

In most cases astronomical images contain objects with very different intensities such as bright stars combined with faint nebulae. Since the noise is mainly due to photon counting (Poisson noise), the signal-to-noise ratio may be very different in different regions of the image. Moreover, the bright and faint objects have, in general, different angular scales. These features imply that the iterative methods which are most frequently used for the reconstruction of astronomical images, namely the Richardson–Lucy Method (RLM), also known in tomography as Expectation Maximization (EM) method, and the Iterative Space Reconstruction Algorithm (ISRA) do not work well in these cases. Also standard regularization approaches do not provide satisfactory results since a kind of adaptive regularization is required, in the sense that one needs a different regularization for bright and faint objects. In this paper we analyze a number of regularization functionals with this particular kind of adaptivity and we propose a simple modification of RLM and ISRA which takes into account these regularization terms. The preliminary results on a test object are promising.     

On the computation of highly oscillatory multivariate integrals with stationary points

We consider two types of highly oscillatory bivariate integrals with a nondegenerate stationary point. In each case we produce an asymptotic expansion and two kinds of quadrature algorithms: an asymptotic method and a Filon-type method. Our results emphasize the crucial role played by the behaviour at the stationary point and by the geometry of the boundary of the underlying domain. In memory of Germund Dahlquist (1925–2005). AMS subject classification (2000) Primary 65D32     

Generating numerical algorithms using a computer algebra system

An useful application of computer algebra systems is the generation of algorithms for numerical computations. We have shown in Gander and Gruntz (SIAM Rev., 1999) how computer algebra can be used in teaching to derive numerical methods. In this paper we extend this work, using essentially the capability of computer algebra system to construct and manipulate the interpolating polynomial and to compute a series expansion of a function. We will automatically generate formulas for integration and differentiation with error terms and also generate multistep methods for integrating differential equations. In memory of Germund Dahlquist (1925–2005).AMS subject classification (2000) 65D25, 65D30, 65D32, 65L06     

The logarithmic norm. History and modern theory

In his 1958 thesis Stability and Error Bounds, Germund Dahlquist introduced the logarithmic norm in order to derive error bounds in initial value problems, using differential inequalities that distinguished between forward and reverse time integration. Originally defined for matrices, the logarithmic norm can be extended to bounded linear operators, but the extensions to nonlinear maps and unbounded operators have required a functional analytic redefinition of the concept.This compact survey is intended as an elementary, but broad and largely self-contained, introduction to the versatile and powerful modern theory. Its wealth of applications range from the stability theory of IVPs and BVPs, to the solvability of algebraic, nonlinear, operator, and functional equations. In memory of Germund Dahlquist (1925–2005).AMS subject classification (2000) 65L05     

Reducibility and contractivity of Runge–Kutta methods revisited

The exact relation between a Cooper-like reducibility concept and the reducibilities introduced by Hundsdorfer, Spijker and by Dahlquist and Jeltsch is given. A shifted Runge–Kutta scheme and a transplanted differential equation is introduced in such a fashion that the input/output relation remains unchanged under these transformations. This gives a technique to prove stability and contractivity results. This is demonstrated on the example of contractivity disks. AMS subject classification (2000) 65L07     

Convex regularization of local volatility models from option prices: Convergence analysis and rates

We study a convex regularization of the local volatility surface identification problem for the Black-Scholes partial differential equation from prices of European call options. This is a highly nonlinear ill-posed problem which in practice is subject to different noise levels associated to bid-ask spreads and sampling errors. We analyze, in appropriate function spaces, different properties of the parameter-to-solution map that assigns to a given volatility surface the corresponding option prices. Using such properties, we show stability and convergence of the regularized solutions in terms of the Bregman distance with respect to a class of convex regularization functionals when the noise level goes to zero.We improve convergence rates available in the literature for the volatility identification problem. Furthermore, in the present context, we relate convex regularization with the notion of exponential families in Statistics. Finally, we connect convex regularization functionals with convex risk measures through Fenchel conjugation. We do this by showing that if the source condition for the regularization functional is satisfied, then convex risk measures can be constructed.     

Numerical method for coupling the macro and meso scales in stochastic chemical kinetics

A numerical method is developed for simulation of stochastic chemical reactions. The system is modeled by the Fokker–Planck equation for the probability density of the molecular state. The dimension of the domain of the equation is reduced by assuming that most of the molecular species have a normal distribution with a small variance. The numerical approximation preserves properties of the analytical solution such as non-negativity and constant total probability. The method is applied to a nine dimensional problem modelling an oscillating molecular clock. The oscillations stop at a fixed point with a macroscopic model but they continue with our two dimensional, mixed macroscopic and mesoscopic model. Dedicated to the memory of Germund Dahlquist (1925–2005). AMS subject classification (2000)  65M20, 65M60     

Generating functionals ofS-matrix and schwinger functions in WN-analysis. I

It is shown that the generating functionals of S-matrix and Schwinger functions are U-functionals of white noise analysis. This result is applied to the regularization of the generating functionals. Translated from Teoreticheskaya i Matematicheskaya Fizika. Vol. 111. No. 1, pp. 3–14. April, 1997.     

Nonnormality and stochastic differential equations

A highly nonnormal Jacobian may give rise to large transients. This behaviour has been shown to have implications for (a) the relevance of linearising a nonlinear system and (b) the timestep restrictions required to keep a numerical method stable. Here, we show that nonnormality also manifests itself for stochastic differential equations. We give an example of a family of systems that is stable without noise, but can be made exponentially unstable in mean-square by a noise perturbation that shrinks to zero as the nonnormality increases. We then show via finite-time convergence theory that an Euler approximation shares the same property, giving a discrete analogue of the result. In memory of Germund Dahlquist (1925–2005).AMS subject classification (2000) 65C30, 34F05