The fast Fourier transform and the numerical solution of one-dimensional boundary integral equations

Summary Here we present a fully discretized projection method with Fourier series which is based on a modification of the fast Fourier transform. The method is applied to systems of integro-differential equations with the Cauchy kernel, boundary integral equations from the boundary element method and, more generally, to certain elliptic pseudodifferential equations on closed smooth curves. We use Gaussian quadratures on families of equidistant partitions combined with the fast Fourier transform. This yields an extremely accurate and fast numerical scheme. We present complete asymptotic error estimates including the quadrature errors. These are quasioptimal and of exponential order for analytic data. Numerical experiments for a scattering problem, the clamped plate and plane estatostatics confirm the theoretical convergence rates and show high accuracy.     

On the discrepancy principle for iterative and parametric methods to solve linear ill-posed equations

Summary. For the numerical solution of (non-necessarily well-posed) linear equations in Banach spaces we consider a class of iterative methods which contains well-known methods like the Richardson iteration, if the associated resolvent operator fulfils a condition with respect to a sector. It is the purpose of this paper to show that for given noisy right-hand side the discrepancy principle (being a stopping rule for the iteration methods belonging to the mentioned class) defines a regularization method, and convergence rates are proved under additional smoothness conditions on the initial error. This extends similar results obtained for positive semidefinite problems in Hilbert spaces. Then we consider a class of parametric methods which under the same resolvent condition contains the method of the abstract Cauchy problem, and (under a weaker resolvent condition) the iterated method of Lavrentiev. A modified discrepancy principle is formulated for them, and finally numerical illustrations are presented. Received August 29, 1994 / Revised version received September 19, 1995     

Automatic,guaranteed integration of analytic functions

Davis introduced a method for estimating linear functionals of analytic functions by using Cauchy's Integral Formula. This is used to construct methods for numerical integration which give rigorous error bounds. By combining these bounds with strategies for order and subinterval adaptation, a program is developed for automatic integration of analytic functions. Interval analysis is used to validate the bounds.     

On the evaluation of Cauchy principal value integrals of oscillatory functions

The problem of the numerical evaluation of Cauchy principal value integrals of oscillatory functions , where −1<τ<1, has been discussed. Based on analytic continuation, if f is analytic in a sufficiently large complex region G containing [−1, 1], the integrals can be transformed into the problems of integrating two integrals on [0,+∞) with the integrand that does not oscillate, and that decays exponentially fast, which can be efficiently computed by using the Gauss-Laguerre quadrature rule. The validity of the method has been demonstrated in the provision of two numerical experiments and their results.     

$L^2$-Approximations of power and logarithmic functions with applications to numerical conformal mapping

Summary. For a bounded Jordan domain G with quasiconformal boundary L, two-sided estimates are obtained for the error in best polynomial approximation to functions of the form , and , where . Furthermore, Andrievskii's lemma that provides an upper bound for the norm of a polynomial in terms of the norm of is extended to the case when a finite linear combination (independent of n) of functions of the above form is added to . For the case when the boundary of G is piecewise analytic without cusps, the results are used to analyze the improvement in rate of convergence achieved by using augmented, rather than classical, Bieberbach polynomial approximants of the Riemann mapping function of G onto a disk. Finally, numerical results are presented that illustrate the theoretical results obtained. Received September 1, 1999 / Published online August 17, 2001     

An adaptive stabilized finite element method for the generalized Stokes problem

In this work we present an adaptive strategy (based on an a posteriori error estimator) for a stabilized finite element method for the Stokes problem, with and without a reaction term. The hierarchical type estimator is based on the solution of local problems posed on appropriate finite dimensional spaces of bubble-like functions. An equivalence result between the norm of the finite element error and the estimator is given, where the dependence of the constants on the physics of the problem is explicited. Several numerical results confirming both the theoretical results and the good performance of the estimator are given.     

Error estimates for Gaussian quadratures of analytic functions

For analytic functions the remainder term of Gaussian quadrature formula and its Kronrod extension can be represented as a contour integral with a complex kernel. We study these kernels on elliptic contours with foci at the points ±1 and the sum of semi-axes ?>1 for the Chebyshev weight functions of the first, second and third kind, and derive representation of their difference. Using this representation and following Kronrod’s method of obtaining a practical error estimate in numerical integration, we derive new error estimates for Gaussian quadratures.     

The superconvergence of the Newton-Cotes rule for Cauchy principal value integrals

We consider the general (composite) Newton-Cotes method for the computation of Cauchy principal value integrals and focus on its pointwise superconvergence phenomenon, which means that the rate of convergence of the Newton-Cotes quadrature rule is higher than what is globally possible when the singular point coincides with some a priori known point. The necessary and sufficient conditions satisfied by the superconvergence point are given. Moreover, the superconvergence estimate is obtained and the properties of the superconvergence points are investigated. Finally, some numerical examples are provided to validate the theoretical results.     

On the convergence of the Bermúdez-Moreno algorithm with constant parameters

Summary. Bermúdez-Moreno [5] presents a duality numerical algorithm for solving variational inequalities of the second kind. The performance of this algorithm strongly depends on the choice of two constant parameters. Assuming a further hypothesis of the inf-sup type, we present here a convergence theorem that improves on the one presented in [5]: we prove that the convergence is linear, and we give the expression of the asymptotic error constant and the explicit form of the optimal parameters, as a function of some constants related to the variational inequality. Finally, we present some numerical examples that confirm the theoretical results. Received June 28, 1999 / Revised version received February 19, 2001 / Published online October 17, 2001     

Extrapolation methods in Lie groups

Summary. The numerical solution of differential equations on Lie groups by extrapolation methods is investigated. The main principles of extrapolation for ordinary differential equations are extended on the general case of differential equations in noncommutative Lie groups. An asymptotic expansion of the global error is given. A symmetric method is given and quadratic asymptotic expansion of the global error is proved. The theoretical results are verified by numerical experiments. Received September 27, 1999 / Revised version received February 14, 2000 / Published online April 5, 2001     

Efficient computable error bounds for discontinuous Galerkin approximations of elliptic problems

We present guaranteed and computable both sided error bounds for the discontinuous Galerkin (DG) approximations of elliptic problems. These estimates are derived in the full DG-norm on purely functional grounds by the analysis of the respective differential problem, and thus, are applicable to any qualified DG approximation. Based on the triangle inequality, the underlying approach has the following steps for a given DG approximation: (1) computing a conforming approximation in the energy space using the Oswald interpolation operator, and (2) application of the existing functional a posteriori error estimates to the conforming approximation. Various numerical examples with varying difficulty in computing the error bounds, from simple problems of polynomial-type analytic solution to problems with analytic solution having sharp peaks, or problems with jumps in the coefficients of the partial differential equation operator, are presented which confirm the efficiency and the robustness of the estimates.     

A posteriori error analysis for numerical approximations of Friedrichs systems

The global error of numerical approximations for symmetric positive systems in the sense of Friedrichs is decomposed into a locally created part and a propagating component. Residual-based two-sided local a posteriori error bounds are derived for the locally created part of the global error. These suggest taking the -norm as well as weaker, dual norms of the computable residual as local error indicators. The dual graph norm of the residual is further bounded from above and below in terms of the norm of where h is the local mesh size. The theoretical results are illustrated by a series of numerical experiments. Received January 10, 1997 / Revised version received March 5, 1998     

Computing singular solutions to nonlinear analytic systems

Summary A method to generate an accurate approximation to a singular solution of a system of complex analytic equations is presented. Since manyreal systems extend naturally tocomplex analytic systems, this porvides a method for generating approximations to singular solutions to real systems. Examples include systems of polynomials and systems made up of trigonometric, exponential, and polynomial terms. The theorem on which the method is based is proven using results from several complex variables. No special conditions on the derivatives of the system, such as restrictions on the rank of the Jacobian matrix at the solution, are required. The numerical method itself is developed from techniques of homotopy continuation and 1-dimensional quadrature. A specific implementation is given, and the results of numerical experiments in solving five test problems are presented.     

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.     

Extrapolation at stiff differential equations

Summary Asymptotic expansions of the global error of numerical methods are well-understood, if the differential equation is non-stiff. This paper is concerned with such expansions for the implicit Euler method, the linearly implicit Euler method and the linearly implicit mid-point rule, when they are applied tostiff differential equations. In this case perturbation terms are present, whose dominant one is given explicitly. This permits us to better understand the behaviour ofextrapolation methods at stiff differential equations. Numerical examples, supporting the theoretical results, are included.     

A mollification method for ill-posed problems

Summary. A mollification method for a class of ill-posed problems is suggested. The idea of the method is very simple and natural: if the data are given inexactly then we try to find a sequence of ``mollification operators" which map the improper data into well-posedness classes of the problem (mollify the improper data). Within these mollified data our problem becomes well-posed. And when these facts are in hand we try to obtain error estimates and optimal or ``quasi-optimal" mollification parameters. The method is working not only for problems in Hilbert spaces, but also for problems in Banach spaces. Applications of the method to concrete problems, like numerical differentiation, parabolic equations backwards in time, the Cauchy problem for the Laplace equation, one- and multidimensional non-characteristic Cauchy problems for parabolic equations (in infinite or finite domains),... give us very sharp stability estimates of H\"older continuous type. In these cases the method is optimal in the sense that it gives the same order of H\"older continuous dependence on the data as for the regularized problems. Furthermore, the method may be implemented numerically using fast Fourier transforms. For the first time a uniform stability estimate of H\"older continuous type of the solution of the heat equation backwards in time in the space for all could be established by our mollification method. A new simple sharp pointwise estimate of H\"older type for the weak solution of a non-characteristic Cauchy problem for parabolic equations in a finite domain is established. Received June 25, 1993 / Revised version received February 18, 1994     

Nyström method for Cauchy singular integral equations with negative index

In this paper, the authors propose a Nyström method to approximate the solutions of Cauchy singular integral equations with constant coefficients having a negative index. They consider the equations in spaces of continuous functions with weighted uniform norm. They prove the stability and the convergence of the method and show some numerical tests that confirm the error estimates.     

The convergence of spline collocation for strongly elliptic equations on curves

Summary Most boundary element methods for two-dimensional boundary value problems are based on point collocation on the boundary and the use of splines as trial functions. Here we present a unified asymptotic error analysis for even as well as for odd degree splines subordinate to uniform or smoothly graded meshes and prove asymptotic convergence of optimal order. The equations are collocated at the breakpoints for odd degree and the internodal midpoints for even degree splines. The crucial assumption for the generalized boundary integral and integro-differential operators is strong ellipticity. Our analysis is based on simple Fourier expansions. In particular, we extend results by J. Saranen and W.L. Wendland from constant to variable coefficient equations. Our results include the first convergence proof of midpoint collocation with piecewise constant functions, i.e., the panel method for solving systems of Cauchy singular integral equations.Dedicated to Prof. Dr. Dr. h.c. mult. Lothar Collatz on the occasion of his 75th birthdayThis work was begun at the Technische Hochschule Darmstadt where Professor Arnold was supported by a North Atlantic Treaty Organization Postdoctoral Fellowship. The work of Professor Arnold is supported by NSF grant BMS-8313247. The work of Professor Wendland was supported by the Stiftung Volkswagenwerk     

Backward error analysis for multistep methods

Summary. In recent years, much insight into the numerical solution of ordinary differential equations by one-step methods has been obtained with a backward error analysis. It allows one to explain interesting phenomena such as the almost conservation of energy, the linear error growth in Hamiltonian systems, and the existence of periodic solutions and invariant tori. In the present article, the formal backward error analysis as well as rigorous, exponentially small error estimates are extended to multistep methods. A further extension to partitioned multistep methods is outlined, and numerical illustrations of the theoretical results are presented. Received January 20, 1998 / Revised version received November 20, 1998 / Published online September 24, 1999     

B-spline collocation for solution of two-point boundary value problems

A numerical method based on B-spline is developed to solve the general nonlinear two-point boundary value problems up to order 6. The standard formulation of sextic spline for the solution of boundary value problems leads to non-optimal approximations. In order to derive higher orders of accuracy, high order perturbations of the problem are generated and applied to construct the numerical algorithm. The error analysis and convergence properties of the method are studied via Green’s function approach. O(h⁶) global error estimates are obtained for numerical solution of these classes of problems. Numerical results are given to illustrate the efficiency of the proposed method. Results of numerical experiments verify the theoretical behavior of the orders of convergence.