Bounds for the round-off errors in the richardson second order method

The application of the Richardson second order iterative method to positive definite, symmetric linear equations is investigated. Absolute and statistical bounds for the round-off error are derived. The statistical theory agrees well with numerical experiments, until the accumulated round-off error becomes of the order of magnitude of the error in the computed solution. After this point the statistical dependence between the local round-off errors makes the observed variances larger than the theoretical variances.This paper (and the Appendix) describe research carried out while both authors were employed by Space Technology Laboratories, Inc., Los Angeles, California.Presented at the IFIP Congress, 1962, under a National Science Foundation travel grant.     

Round-off Errors and Stability in Variational Calculations

We consider the problem of the stability of a variational solutionof a linear, inhomo-geneous operator equation, in the presenceof "round-off" errors in the various inner products involved.For systems which are asymptotically diagonal (see Delves &Mead, 1971; Freeman, Delves & Reid, 1974) we produce boundson the error induced by the round-off noise, which show thatat least for sufficiently small C the solution method is stablein these cases in the sense of Mikhlin (1971) provided thatthe system is normalized ("nice" in the sense of Delves &Mead, 1971). Un-normalized A.D. systems may not be stable, butare relatively stable in a sense defined here. In addition tothese error bounds we produce estimates of the distributionof the round-off errors amongst the expansion coefficients a_i^(N).A numerical example suggests that relative stability is sufficientto ensure good variational behaviour of the calculation.     

A posteriori error analysis of round-off errors in the numerical solution of ordinary differential equations

We prove sharp, computable error estimates for the propagation of errors in the numerical solution of ordinary differential equations. The new estimates extend previous estimates of the influence of data errors and discretization errors with a new term accounting for the propagation of numerical round-off errors, showing that the accumulated round-off error is inversely proportional to the square root of the step size. As a consequence, the numeric precision eventually sets the limit for the pointwise computability of accurate solutions of any ODE. The theoretical results are supported by numerically computed solutions and error estimates for the Lorenz system and the van der Pol oscillator.     

Reducing and monitoring round-off error propagation for symplectic implicit Runge-Kutta schemes

We propose an implementation of symplectic implicit Runge-Kutta schemes for highly accurate numerical integration of non-stiff Hamiltonian systems based on fixed point iteration. Provided that the computations are done in a given floating point arithmetic, the precision of the results is limited by round-off error propagation. We claim that our implementation with fixed point iteration is near-optimal with respect to round-off error propagation under the assumption that the function that evaluates the right-hand side of the differential equations is implemented with machine numbers (of the prescribed floating point arithmetic) as input and output. In addition, we present a simple procedure to estimate the round-off error propagation by means of a slightly less precise second numerical integration. Some numerical experiments are reported to illustrate the round-off error propagation properties of the proposed implementation.     

A stabilization of the simplex method

Summary This paper considers the effect of round-off errors on the computations carried out in the simplex method of linear programming. Standard implementations are shown to be subject to computational instabilities. An alternative implementation of the simplex method based upon L U decompositions of the basic matrices is presented, and its computational stability is indicated by a round-off error analysis. Some computational results are given.     

A local-global stepsize control for multistep methods applied to semi-explicit index 1 differential-algebraic equations

In this paper we develop a new procedure to control stepsize for linear multistep methods applied to semi-explicit index 1 differential-algebraic equations. In contrast to the standard approach, the error control mechanism presented here is based on monitoring and controlling both the local and global errors of multistep formulas. As a result, such methods with the local-global stepsize control solve differential-algebraic equations with any prescribed accuracy (up to round-off errors). For implicit multistep methods we give the minimum number of both full and modified Newton iterations allowing the iterative approximations to be correctly used in the procedure of the local-global stepsize control. We also discuss validity of simple iterations for high accuracy solving differential-algebraic equations. Numerical tests support the theoretical results of the paper.     

Efficient implementation of symplectic implicit Runge-Kutta schemes with simplified Newton iterations

We are concerned with the efficient implementation of symplectic implicit Runge-Kutta (IRK) methods applied to systems of Hamiltonian ordinary differential equations by means of Newton-like iterations. We pay particular attention to time-symmetric symplectic IRK schemes (such as collocation methods with Gaussian nodes). For an s-stage IRK scheme used to integrate a \(\dim \)-dimensional system of ordinary differential equations, the application of simplified versions of Newton iterations requires solving at each step several linear systems (one per iteration) with the same \(s\dim \times s\dim \) real coefficient matrix. We propose a technique that takes advantage of the symplecticity of the IRK scheme to reduce the cost of methods based on diagonalization of the IRK coefficient matrix. This is achieved by rewriting one step of the method centered at the midpoint on the integration subinterval and observing that the resulting coefficient matrix becomes similar to a skew-symmetric matrix. In addition, we propose a C implementation (based on Newton-like iterations) of Runge-Kutta collocation methods with Gaussian nodes that make use of such a rewriting of the linear system and that takes special care in reducing the effect of round-off errors. We report some numerical experiments that demonstrate the reduced round-off error propagation of our implementation.     

Round off error analysis for Gram-Schmidt method and solution of linear least squares problems

Round off error analysis for the classical Gram-Schmidt orthogonalization method with re-orthogonalization is presented. The effect of the round-off error on the orthogonality of the derived vectors and also on the solution of the linear least squares problems when solved by the Gram-Schmidt algorithm are given. Numerical results compared favorably with the results of other methods. The classical case when no re-orthogonalization takes place is also discussed.     

Propagation of round-off error in a model of quadratic rational rotations

We investigate the propagation of round-off error for a discrete map modeling a one-dimensional linear oscillator viewed stroboscopically in phase space, with uniform, non-dissipative round-off. The probability P(r,t) of a net displacement r during t time steps can be reduced, essentially, to a weighted sum over contributions from a small number of infinite scaling sequences of periodic orbits. We show that the successive members of each scaling sequence can be built up by application of a set of substitution rules. This implies recursion relations, not only for the geometry of the orbits, but also for P(r,t) and its moments, allowing these quantities to be calculated exactly as algebraic numbers. For asymptotically large t, the moments have power-law increase, modulated by log-periodic or (in one particularly interesting case) log-quasi-periodic oscillations.     

On an interval-arithmetic matrix method

Hansen and Smith have proposed a method for solving linear algebraic systems with interval coefficients which produces good results if the intervals are narrow. In this paper we show that the error of their method isO(W ²), whereW is the width of the set of coefficients. The effects of round-off errors are not considered.Supported in part by NSF grant GJ-797.     

An estimate for the round-off error in the elimination problem

The paper demonstrates that in computing a linear form (g, x) on the solution of a system of linear equations Ax = f, the round-off error depends on the quantities ‖A⁻¹f‖ and ‖A^T−1g‖ rather than on the condition number of the coefficient matrix A. Estimates of the inherent and round-off errors in solving the above problem by the orthogonalization method are provided. Numerical results confirming theoretical conclusions are presented. Bibliography: 8 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 334, 2006, pp. 193–211.     

A local-global version of a stepsize control for Runge-Kutta methods

In this paper we develop a new procedure to control stepsize for Runge-Kutta methods applied to both ordinary differential equations and semi-explicit index 1 differential-algebraic equations. In contrast to the standard approach, the error control mechanism presented here is based on monitoring and controlling both the local and global errors of Runge-Kutta formulas. As a result, Runge-Kutta methods with the local-global stepsize control solve differential or differential-algebraic equations with any prescribed accuracy (up to round-off errors). For implicit Runge-Kutta formulas we give the sufficient number of both full and modified Newton iterations allowing the iterative approximations to be correctly used in the procedure of the local-global stepsize control. In addition, we develop a stable local-global error control mechanism which is applicable for stiff problems. Numerical tests support the theoretical results of the paper.     

On a modification of minimal iteration methods for solving systems of linear algebraic equations

Modifications of certain minimal iteration methods for solving systems of linear algebraic equations are proposed and examined. The modified methods are shown to be superior to the original versions with respect to the round-off error accumulation, which makes them applicable to solving ill-conditioned problems. Numerical results demonstrating the efficiency of the proposed modifications are given.     

Numerical computation of characteristic polynomials of Boolean functions and its applications

We study the problem of evaluation of characteristic polynomials of Boolean functions with applications to combinational circuit verification. Two Boolean functions are equivalent if and only if their corresponding characteristic polynomials are identical. However, to verify the equivalence of two Boolean functions it is often impractical to construct the corresponding characteristic polynomials due to a possible exponential blow-up of the terms of the polynomials. Instead, we compare their values at a sample point without explicitly constructing the characteristic polynomials. Specifically, we sample uniformly at random in a unit cube and determine whether two characteristic polynomials are identical by their evaluations at the sample point; the error probability is zero when there are no round-off errors. In the presence of round-off errors, we sample on regular grids and analyze the error probability. We discuss in detail the Shannon expansion for characteristic polynomial evaluation. This revised version was published online in June 2006 with corrections to the Cover Date.     

Life Expectancy of Transient Microchaotic Behaviour

The application of digital control may lead to so-called transient chaotic behaviour. In the present paper, we analyse a simple model of a digitally controlled mechanical system, which may create such vibrations. As a consequence of the digital effects, i.e., the sampling and the round-off error, the behaviour of this system can be described by a one-dimensional piecewise linear map. The lifetime of chaotic transients is usually characterized by the so-called escape rate. In the literature, the reciprocal of the escape rate is considered to be the expected duration of the transient chaotic phenomenon. We claim that this approach is not always fruitful, and present a different way of calculating the mean lifetime in the case of one-dimensional piecewise linear maps. Our method might also be used to solve diffusion problems in one-dimensional models of periodic arrays.     

On the structure of error estimates for finite-difference methods

In this paper we study in an abstract setting the structure of estimates for the global (accumulated) error in semilinear finite-difference methods. We derive error estimates, which are the most refined ones (in a sense specified precisely in this paper) that are possible for the difference methods considered. Applications and (numerical) examples are presented in the following fields: 1. Numerical solution of ordinary as well as partial differential equations with prescribed initial or boundary values. 2. Accumulation of local round-off error as well as of local discretization error. 3. The problem of fixing which methods out of a given class of finite-difference methods are most stable. 4. The construction of finite-difference methods which are convergent but not consistent with respect to a given differential equation.     

Analysis of some known methods of improving the accuracy of floating-point sums

Some well-known methods for calculating the round-off error in floating-point addition are analyzed in this paper. The methods have been introduced by Møller [16], Kahan [11] and Knuth [12]. The necessary and sufficient conditions under which these methods produce the value of the round-off error, for rounding, truncating and parity arithmetic, are given. The computer-oriented parity arithmetic is not commonly known, but it has some desirable properties, as this paper will demonstrate. Some experimental results are also reported.     

Numerical studies on nonlinear Schrödinger equations by spectral collocation method with preconditioning

In this study, we use the spectral collocation method with preconditioning to solve various nonlinear Schrödinger equations. To reduce round-off error in spectral collocation method we use preconditioning. We study the numerical accuracy of the method. The numerical results obtained by this way have been compared with the exact solution to show the efficiency of the method.     

Fourier–Taylor Approximation of Unstable Manifolds for Compact Maps: Numerical Implementation and Computer-Assisted Error Bounds

We develop and implement a semi-numerical method for computing high-order Taylor approximations of unstable manifolds for hyperbolic fixed points of compact infinite-dimensional maps. The method can follow folds in the embedding and describes precisely the dynamics on the manifold. In order to ensure the accuracy of our computations in spite of the many truncation and round-off errors, we develop a posteriori error bounds for the approximations. Deliberate control of round-off errors (using interval arithmetic) in conjunction with explicit analytical estimates leads to mathematically rigorous computer-assisted theorems describing precisely the truncation errors for our approximation of the invariant manifold. The method is applied to the Kot-Schaffer model of population dynamics with spatial dispersion.