Computation of the inverse Laplace transform based on a collocation method which uses only real values

We develop a numerical algorithm for inverting a Laplace transform (LT), based on Laguerre polynomial series expansion of the inverse function under the assumption that the LT is known on the real axis only. The method belongs to the class of Collocation methods (C-methods), and is applicable when the LT function is regular at infinity. Difficulties associated with these problems are due to their intrinsic ill-posedness. The main contribution of this paper is to provide computable estimates of truncation, discretization, conditioning and roundoff errors introduced by numerical computations. Moreover, we introduce the pseudoaccuracy which will be used by the numerical algorithm in order to provide uniform scaled accuracy of the computed approximation for any x   with respect to e^σx${\mathrm{e}}^{\sigma x}$. These estimates are then employed to dynamically truncate the series expansion. In other words, the number of the terms of the series acts like the regularization parameter which provides the trade-off between errors.     

Truncation and roundoff errors in three-point approximations of first and second derivatives

We use linear combinations of Taylor expansions to develop three-point finite difference expressions for the first and second derivative of a function at a given node. We derive analytical expressions for the truncation and roundoff errors associated with these finite difference formulae. Using these error expressions, we find optimal values for the stepsize and the distribution of the three points, relative to the given node. The latter are obtained assuming that the three points are equispaced. For the first derivative approximation, the distribution of the points relative to the given node is not symmetrical, while it is so for the second derivative approximation. We illustrate these results with a numerical example in which we compute upper bounds on the roundoff error.     

An efficient algorithm for the generalized centro-symmetric solution of matrix equation <Emphasis Type="Italic">A X B</Emphasis> = <Emphasis Type="Italic">C</Emphasis>

In this paper, an iterative algorithm is constructed for solving linear matrix equation AXB = C over generalized centro-symmetric matrix X. We show that, by this algorithm, a solution or the least-norm solution of the matrix equation AXB = C can be obtained within finite iteration steps in the absence of roundoff errors; we also obtain the optimal approximation solution to a given matrix X ₀ in the solution set of which. In addition, given numerical examples show that the iterative method is efficient.     

A statistical model of roundoff error for varying length floating-point arithmetic

A model is presented which explains the behavior of the roundoff error in a result quantity when computing precision is varied. A set of hypotheses concerning this a posteriori model is tested in a matrix inversion algorithm. The characteristics of the algorithms where the error model is valid are discussed. As an application of the model, the usual estimation procedure for roundoff error consisting of comparing the results computed in two different precisions is analyzed statistically.     

An analysis of the effect of rounding errors on the flow of control in numerical processes

Rounding errors may change the flow of control in numerical computing processes by leading to changes in some branching decisions of the process. In this paper some general topological and measure theoretical results associated with this effect of rounding errors are derived. The approach is based on a model of numerical computation related to program schemes. Each computing process specified by the model computes a partial functionR ⁿ R ^m using rational operations and simple tests on real numbers. The topological structure of input point sets inR ⁿ on which the computation follows the same execution path is studied. We also investigate input points, called sensitive, on which rounding errors may change the execution path followed. Conditions concerning computing processes are given which guarantee that the Lebesgue measure of sensitive points approaches zero (i.e. the probability of a branching error gets arbitrarily small) as the precision of the arithmetic increases. Most numerical processes used in practice are easily seen to satisfy these conditions.     

Computation of special functions by Padé approximants with orthogonal polynomial denominators

This paper deals with the computation of special functions of mathematics and physics in the complex domain using continued fraction (one-point or two-point Padé) approximants. We consider three families of continued fractions (Stieltjes fractions, real J-fractions and non-negative T-fractions) whose denominators are orthogonal polynomials or Laurent polynomials. Orthogonality of these denominators plays an important role in the analysis of errors due to numerical roundoff and truncation of infinite sequences of approximants. From the rigorous error bounds described one can determine the exact number of significant decimal digits contained in the approximation of a given function value. Results from computational experiments are given to illustrate the methods.Research supported in part by the National Science Foudation under Grant No. DMS-9302584.     

Adaptive error control during gradient search for an elliptic optimization problem

In this article we describe a cost effective adaptive procedure for optimization of a quantity of interest of a solution of an elliptic problem with respect to parameters in the data, using a gradient search approach. The numerical error in both the quantity of interest and the computed gradient may affect the progression of the search algorithm, while the errors generally change at each step during the search algorithm. We address this by using an accurate a posteriori estimate for the error in a quantity of interest that indicates the effect of error on the computed gradient and so provides a measure for how to refine the discretization as the search proceeds. Specifically, we devise an adaptive algorithm to refine and unrefine the finite element mesh at each step in the search algorithm. We give basic examples and apply this technique to a model of a healing wound.     

Fitting Social Network Models Using Varying Truncation Stochastic Approximation MCMC Algorithm

The exponential random graph model (ERGM) plays a major role in social network analysis. However, parameter estimation for the ERGM is a hard problem due to the intractability of its normalizing constant and the model degeneracy. The existing algorithms, such as Monte Carlo maximum likelihood estimation (MCMLE) and stochastic approximation, often fail for this problem in the presence of model degeneracy. In this article, we introduce the varying truncation stochastic approximation Markov chain Monte Carlo (SAMCMC) algorithm to tackle this problem. The varying truncation mechanism enables the algorithm to choose an appropriate starting point and an appropriate gain factor sequence, and thus to produce a reasonable parameter estimate for the ERGM even in the presence of model degeneracy. The numerical results indicate that the varying truncation SAMCMC algorithm can significantly outperform the MCMLE and stochastic approximation algorithms: for degenerate ERGMs, MCMLE and stochastic approximation often fail to produce any reasonable parameter estimates, while SAMCMC can do; for nondegenerate ERGMs, SAMCMC can work as well as or better than MCMLE and stochastic approximation. The data and source codes used for this article are available online as supplementary materials.     

Roundoff Error Analysis of the Recursive Moving Window Discrete Fourier Transform

This paper presents both worst case and average case analysis of roundoff errors occuring in the floating point computation of the recursive moving window discrete Fourier transform (DFT) with precomputed twiddle factors. We show the strong influence of precomputation errors – both within the initial fast Fourier transform (FFT) and the recursion – on the numerical stability. Numerical simulations confirm the theoretical results.     

Solving monotone inclusions with linear multi-step methods

 In this paper a new class of proximal-like algorithms for solving monotone inclusions of the form T(x)∋0 is derived. It is obtained by applying linear multi-step methods (LMM) of numerical integration in order to solve the differential inclusion , which can be viewed as a generalization of the steepest decent method for a convex function. It is proved that under suitable conditions on the parameters of the LMM, the generated sequence converges weakly to a point in the solution set T ⁻¹ (0). The LMM is very similar to the classical proximal point algorithm in that both are based on approximately evaluating the resolvants of T. Consequently, LMM can be used to derive multi-step versions of many of the optimization methods based on the classical proximal point algorithm. The convergence analysis allows errors in the computation of the iterates, and two different error criteria are analyzed, namely, the classical scheme with summable errors, and a recently proposed more constructive criterion. Received: April 2001 / Accepted: November 2002 Published online: February 14, 2003 Key Words. proximal point algorithm – monotone operator – numerical integration – strong stability – relative error criterion Mathematics Subject Classification (1991): 20E28, 20G40, 20C20     

Roundoff errors in floating-point summation

All possible schemes for the calculation of the sum ofn addends by means ofn–1 floating-point additions is considered and in case of positive addends it is shown how to use the Huffman algorithm to choose a scheme to obtain the least upper bound on the accumulated roundoff error in the result.     

Point process diagnostics based on weighted second-order statistics and their asymptotic properties

A new approach for point process diagnostics is presented. The method is based on extending second-order statistics for point processes by weighting each point by the inverse of the conditional intensity function at the point’s location. The result is generalized versions of the spectral density, R/S statistic, correlation integral and K-function, which can be used to test the fit of a complex point process model with an arbitrary conditional intensity function, rather than a stationary Poisson model. Asymptotic properties of these generalized second-order statistics are derived, using an approach based on martingale theory.     

On Functional Separately Convex Hulls

Let D be a set of vectors in R ^d . A function f: R ^d → R is called D-convex if its restriction to each line parallel to a nonzero vector of D is a convex function. For a set A⊆ R ^d , the functional D-convex hull of A, denoted by co ^D (A) , is the intersection of the zero sets of all nonnegative D -convex functions that are 0 on A . We prove some results concerning the structure of functional D -convex hulls, e.g., a Krein—Milman-type theorem and a result on separation of connected components. We give a polynomial-time algorithm for computing co ^D (A) for a finite point set A (in any fixed dimension) in the case of D being a basis of R ^d (the case of separate convexity). This research is primarily motivated by questions concerning the so-called rank-one convexity, which is a particular case of D -convexity and is important in the theory of systems of nonlinear partial differential equations and in mathematical modeling of microstructures in solids. As a direct contribution to the study of rank-one convexity, we construct a configuration of 20 symmetric 2 x 2 matrices in a general (stable) position with a nontrivial functionally rank-one convex hull (answering a question of K. Zhang on the existence of higher-dimensional nontrivial configurations of points and matrices). Received October 3, 1995, and in revised form June 24, 1996.     

Dyadic Hermite interpolation on a rectangular mesh

Given f and ∇f at the vertices of a rectangular mesh, we build an interpolating function f by a subdivision algorithm. The construction on each elementary rectangle is independent of any disjoint rectangle. From the Hermite data associated with the vertices of a rectangle R, the function f is defined on a dense subset of R. Sufficient conditions are found in order to extend f to a C ¹ function. Moreover, infinite products and generalized radii of matrices are used to study the convergence to a C ¹ function. This convergence depends on the five parameters introduced in the algorithm. This revised version was published online in June 2006 with corrections to the Cover Date.     

Worst and Average Case Roundoff Error Analysis for FFT

This paper presents both worst case and average case analysis of roundoff errors occuring in the floating point computation of fast Fourier transform (FFT) with precomputed twiddle factors and shows the strong influence of precomputation errors on the numerical stability of FFT. Numerical tests confirm the theoretical results.This revised version was published online in October 2005 with corrections to the Cover Date.     

Accurate solution of polynomial equations using Macaulay resultant matrices

We propose an algorithm for solving two polynomial equations in two variables. Our algorithm is based on the Macaulay resultant approach combined with new techniques, including randomization, to make the algorithm accurate in the presence of roundoff error. The ultimate computation is the solution of a generalized eigenvalue problem via the QZ method. We analyze the error due to roundoff of the method, showing that with high probability the roots are computed accurately, assuming that the input data (that is, the two polynomials) are well conditioned. Our analysis requires a novel combination of algebraic and numerical techniques.

     

A characterisation of certain optimal collocation points for numerical differentiation

The first derivative of a real-valued function may be approximated at a certain point by the derivative of a polynomial collocating with the function at this point and a number of other distinct points. The particular points which minimise the magnification of any rounding errors in the function values for any fixed level of truncation error are shown to be closely related to the turning points of a related Chebyshev polynomial.     

On the resolution of monotone complementarity problems

A reformulation of the nonlinear complementarity problem (NCP) as an unconstrained minimization problem is considered. It is shown that any stationary point of the unconstrained objective function is a solution of NCP if the mapping F involved in NCP is continuously differentiable and monotone, and that the level sets are bounded if F is continuous and strongly monotone. A descent algorithm is described which uses only function values of F. Some numerical results are given.     

Bernstein series solution of linear second‐order partial differential equations with mixed conditions

The purpose of this study is to present a new collocation method for numerical solution of linear PDEs under the most general conditions. The method is given with a priori error estimate. By using the residual correction procedure, the absolute error can be estimated. Also, one can specify the optimal truncation limit n, which gives better result in any norm ∥ ∥ . Finally, the effectiveness of the method is illustrated in some numerical experiments. Numerical results are consistent with the theoretical results. Copyright © 2013 John Wiley & Sons, Ltd.     

A model for understanding numerical stability

^** Email: bornemann{at}ma.tum.de We present a model of roundoff error analysis that combinessimplicity with predictive power. Though not considering allsources of roundoff within an algorithm, the model is relatedto a recursive roundoff error analysis and therefore is capableof correctly predicting stability or instability of an algorithm.By means of nontrivial examples, such as the componentwise backwardstability analysis of Gaussian elimination with a single iterativerefinement step, we demonstrate that the model even yields quantitativebackward error bounds that show all the known problem-dependentterms with the exception of dimension-dependent constants. Themodel can serve as a convenient tool for teaching or as a heuristicdevice to discover stability results before entering a furtherdetailed analysis.