Error Analysis of Clenshaw's Algorithm for Evaluating Derivatives of a Polynomial

A forward rounding error analysis is presented for the extended Clenshaw algorithm due to Skrzipek for evaluating the derivatives of a polynomial expanded in terms of orthogonal polynomials. Reformulating in matrix notation the three-term recurrence relation satisfied by orthogonal polynomials facilitates the estimate of the rounding error for the m-th derivative, which is recursively estimated in terms of the one for the (m – 1)-th derivative. The rounding errors in an important case of Chebyshev polynomial are discussed in some detail.This revised version was published online in October 2005 with corrections to the Cover Date.     

Peculiarities of error accumulation in solving problems for simple equations of mathematical physics by finite difference methods

A mixed problem for the one-dimensional heat conduction equation with several versions of initial and boundary conditions is considered. To solve this problem, explicit and implicit schemes are used. Sweep and iterative methods are used for the implicit scheme when solving the system of equations. Numerical filtering of a finite sequence of results obtained for various grids with an increasing number of node points is used to analyze the method and rounding errors. To investigate rounding errors, the results obtained for various machine word mantissa lengths are compared. The numerical solution of a mixed problem for the wave equation is studied by similar methods. Some deterministic dependencies of the numerical method and rounding errors on the spatial coordinates, time, and the number of nodes are found. Some models of sources to describe the behavior of the errors in time are constructed. They are based on the results of computational experiments under various conditions. According to these models, which have been experimentally verified, the errors increase, decrease, or stabilize in time under the conditions, similarly to energy or mass.     

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.     

Avoiding breakdown and near-breakdown in Lanczos type algorithms

Lanczos type algorithms form a wide and interesting class of iterative methods for solving systems of linear equations. One of their main interest is that they provide the exact answer in at mostn steps wheren is the dimension of the system. However a breakdown can occur in these algorithms due to a division by a zero scalar product. After recalling the so-called method of recursive zoom (MRZ) which allows to jump over such breakdown we propose two new variants. Then the method and its variants are extended to treat the case of a near-breakdown due to a division by a scalar product whose absolute value is small which is the reason for an important propagation of rounding errors in the method. Programming the various algorithms is then analyzed and explained. Numerical results illustrating the processes are discussed. The subroutines corresponding to the algorithms described can be obtained vianetlib.     

Splineapproximationen von beliebigem Defekt zur numerischen Lösung gewöhnlicher Differentialgleichungen. Teil III

Summary In the first part [1] a general procedure is presented to obtain polynomial spline approximations for the solutions of initial value problems for ordinary differential equations; furthermore a divergence theorem is proved there. Sufficient conditions for convergence of the method are given in the second part [2]. The remaining case which has not been considered in [1] and [2] is treated in the present paper. In this special case the procedure is equivalent to an unstable two-step method with special initial values; nevertheless, convergence can be proved. Finally,A ₀-stability of the method as well as the influence of rounding errors are investigated.

     

Verification of Positive Definiteness

We present a computational, simple and fast sufficient criterion to verify positive definiteness of a symmetric or Hermitian matrix. The criterion uses only standard floating-point operations in rounding to nearest, it is rigorous, it takes into account all possible computational and rounding errors, and is also valid in the presence of underflow. It is based on a floating-point Cholesky decomposition and improves a known result. Using the criterion an efficient algorithm to compute rigorous error bounds for the solution of linear systems with symmetric positive definite matrix follows. A computational criterion to verify that a given symmetric or Hermitian matrix is not positive definite is given as well. Computational examples demonstrate the effectiveness of our criteria. AMS subject classification (2000) 65G20, 15A18     

Fehleranalyse für die Gauß-Elimination zur Berechnung der Lösung minimaler Länge

Summary Presented is a realistic, elementwise analysis for the rounding errors of a generalization of Gauss elimination for solving the linear best least squares problem without pivoting. The bounds are suitable to determine the class of well-posed problems to the given method. A mixed error analysis is given and then the effects of errors in the input data are studied. Numerical examples demonstrate the efficiency.

     

Sur la distance à l'instabilité de polynômes matriciels quadratiques

A bisection method is developed for computing the distance to instability of quadratic matrix polynomials. The computation takes rounding errors into account.     

Error analysis of an algorithm for solving an underdetermined linear system

Summary The accumulation of rounding errors in a method used to compute the solution of an underdetermined system of linear equations at the least distance from a given point is being studied. The method used is based on orthogonal matrix decompositions.This research was partially supported by the Progetto Finalizzato Informatica of the Italian National Research Council     

An Error Analysis of the Modified Clenshaw Method for Evaluating Chebyshev and Fourier Series

The propagation of rounding errors in both Clenshaw's (or Goertzel's)original algorithm and Reinsch's modified form is analysed,and a criterion is deduced for choosing between them. Theirpractical implementation is discussed, and the critical importanceof calculating the coefficients in Reinsch's recurrence by anaccurate method is demonstrated.     

Modified Gram-Schmidt-based methods for block downdating the Cholesky factorization

The hyperbolic modified Gram-Schmidt (HMGS) method is proposed for block downdating the Cholesky factorization. The method might be unsatisfactory due to rounding errors. A modified version based on the MGS process is presented and is shown to be mixed stable. Numerical tests show that the new method has the same numerical properties as the generalized LINPACK-type algorithm, and can work better than the Householder-based algorithm given by Bojanczyk and Steinhardt (1991) [9].     

Fast enclosure for the minimum norm least squares solution of the matrix equation AXB = C

Fast algorithms for enclosing the minimum norm least squares solution of the matrix equation AXB = C are proposed. To develop these algorithms, theories for obtaining error bounds of numerical solutions are established. The error bounds obtained by these algorithms are verified in the sense that all the possible rounding errors have been taken into account. Techniques for accelerating the enclosure and obtaining smaller error bounds are introduced. Numerical results show the properties of the proposed algorithms. Copyright © 2015 John Wiley & Sons, Ltd.     

On the loss of orthogonality in the second-order Arnoldi process

This note is devoted to the rounding error analysis of the second-order Arnoldi process for constructing an orthonormal basis of the second-order Krylov subspace. The effect of the rounding errors on the orthogonality of the derived vectors is given.     

Automatic Linear Correction of Rounding Errors

A new automatic method to correct the first-order effect of floating point rounding errors on the result of a numerical algorithm is presented. A correcting term and a confidence threshold are computed using algorithmic differentiation, computation of elementary rounding error and running error analysis. Algorithms for which the accuracy of the result is not affected by higher order terms are identified. The correction is applied to the final result or to sensitive intermediate results to improve the accuracy of the computed result and/or the stability of the algorithm.This revised version was published online in October 2005 with corrections to the Cover Date.     

Variants of the groupwise update strategy for short-recurrence Krylov subspace methods

Krylov subspace methods often use short-recurrences for updating approximations and the corresponding residuals. In the bi-conjugate gradient (Bi-CG) type methods, rounding errors arising from the matrix–vector multiplications used in the recursion formulas influence the convergence speed and the maximum attainable accuracy of the approximate solutions. The strategy of a groupwise update has been proposed for improving the convergence of the Bi-CG type methods in finite-precision arithmetic. In the present paper, we analyze the influence of rounding errors on the convergence properties when using alternative recursion formulas, such as those used in the bi-conjugate residual (Bi-CR) method, which are different from those used in the Bi-CG type methods. We also propose variants of a groupwise update strategy for improving the convergence speed and the accuracy of the approximate solutions. Numerical experiments demonstrate the effectiveness of the proposed method.     

Rounded data analysis based on multi-layer ranked set sampling

Observations of sampling are often subject to rounding, but are modeled as though they were unrounded. This paper examines the impact of rounding errors on parameter estimation with multi-layer ranked set sampling. It shows that the rounding errors seriously distort the behavior of covariance matrix estimate, and lead to inconsistent estimation. Taking this into account, we present a new approach to implement the estimation for this model, and further establish the strong consistency and asymptotic normality of the proposed estimators. Simulation experiments show that our estimates based on rounded multi-layer ranked set sampling are always more efficient than those based on rounded simple random sampling.     

A method of solving the stability problem for complex matrices

The aim of this paper is to determine the location of eigenvalues of a general complex matrix without explicitly computing them. Essentially, the method consists in finding a Hermitian matrixH which has the same inertia as the given matrixM, and determining the inertia ofH. H is found as the solution of the Liapunov equation , where is a matrix in upper Hessenberg form which is similar toM. The method remains applicable even if the solution of the Liapunov equation is affected by rounding errors, as long as a given criterion is satisfied. A programmed version of this method has been run on our computer with satisfactory results.This work was performed under the terms of the agreement on accosiation between the Max-Planck-Institut für Plasmaphysik and EURATOM.     

An algorithm for Gaussian quadrature given modified moments

Summary An algebraic algorithm, the long quotient- modified difference (LQMD) algorithm, is described for the Gaussian quadrature of the one-dimensional product integral f(x)w(x)dx when the weight function (x) is known through modified momentsv _l =; theP _l (x) are any polynomials of degreel satisfying 3-term recurrence relations with known coefficients. The algorithm serves to establish the co-diagonal matrix, the eigenvalues of which are the Gaussian abscissas. Applied to ordinary moments it requires far fewer divisions than the quotient-difference algorithm; if theP _l (x) are themselves orthogonal with a kernelw ₀ 03F0;, there is no instability due to rounding errors. For smooth kernels (x) it is safe to use secondorder interpolation in determining the eigenvalues by Givens' method. The Christoffel weights can be expressed as ratios of two terms which are most easily calculated in a Sturm sequence beginning with the highest value ofl. A formula for the Christoffel weights applicable for rational versions of theQR algorithm is also derived. Convergence and the propagation of rounding errors are illustrated by several examples, and anAlgol procedure is given.Based in part on a project report presented by A. F. Donovan in partial fulfilment of the requirements for the degree of B. Sc. (Honours), University of Salford (1969).     

Taylor expansion of the accumulated rounding error

The article describes analytic and algorithmic methods for determining the coefficients of the Taylor expansion of an accumulated rounding error with respect to the local rounding errors, and hence determining the influence of the local errors on the accumulated error. Second and higher order coefficients are also discussed, and some possible methods of reducing the extensive storage requirements are analyzed.     

Approximation Algorithms for MAX 4-SAT and Rounding Procedures for Semidefinite Programs

Karloff and Zwick obtained recently an optimal 7/8-approximation algorithm for MAX 3-SAT. In an attempt to see whether similar methods can be used to obtain a 7/8-approximation algorithm for MAX SAT, we consider the most natural generalization of MAX 3-SAT, namely MAX 4-SAT. We present a semidefinite programming relaxation of MAX 4-SAT and a new family of rounding procedures that try to cope well with clauses of various sizes. We study the potential, and the limitations, of the relaxation and of the proposed family of rounding procedures using a combination of theoretical and experimental means. We select two rounding procedures from the proposed family of rounding procedures. Using the first rounding procedure we seem to obtain an almost optimal 0.8721-approximation algorithm for MAX 4-SAT. Using the second rounding procedure we seem to obtain an optimal 7/8-approximation algorithm for satisfiable instances of MAX 4-SAT. On the other hand, we show that no rounding procedure from the family considered can be shown, using the current techniques, to yield an approximation algorithm for MAX 4-SAT whose performance guarantee for all instances of the problem is greater than 0.8724. We also show that the integrality ratio of the proposed relaxation, as a relaxation of MAX {1, 4}-SAT, is at most 0.8754.The 0.8721-approximation for MAX 4-SAT that we seem to obtain substantially improves the performance guarantees of all previous algorithms suggested for the problem. It is extremely close to being optimal as a (7/8 + ε)-approximation algorithm for MAX 4-SAT, for any fixed ε > 0, would imply that P = NP. Our investigation also indicates, however, that additional ideas are required in order to obtain optimal 7/8-approximation algorithms for MAX 4-SAT and MAX SAT.Although most of this paper deals specifically with the MAX 4-SAT problem, we believe that the new family of rounding procedures introduced and the methodology used in the design and in the analysis of the various rounding procedures considered have a much wider range of applicability.