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.     

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.     

Stability and Accuracy of Inexact Interior Point Methods for Convex Quadratic Programming

We consider primal–dual interior point methods where the linear system arising at each iteration is formulated in the reduced (augmented) form and solved approximately. Focusing on the iterates close to a solution, we analyze the accuracy of the so-called inexact step, i.e., the step that solves the unreduced system, when combining the effects of both different levels of accuracy in the inexact computation and different processes for retrieving the step after block elimination. Our analysis is general and includes as special cases sources of inexactness due either to roundoff and computational errors or to the iterative solution of the augmented system using typical procedures. In the roundoff case, we recover and extend some known results.     

Implementing Taylor models arithmetic with floating-point arithmetic

The implementation of Taylor models arithmetic may use floating-point arithmetic to benefit from the speed of the floatingpoint implementation. The issue is then to take into account the roundoff errors. Here, we assume that the floating-point arithmetic is compliant with the IEEE-754 standard. We show how to get tight bounds of the roundoff errors, and more generally how to get high accuracy for the coefficients as well as for the bounds on the roundoff errors     

On some topological properties of numerical algorithms

A result quantity in a numerical algorithm is considered as a function of the input data, roundoff and truncation errors. In order to investigate this functional relationship using the methods of mathematical analysis a structural model of the numerical algorithm calledR-automaton is introduced. It is shown that the functional dependence defined by anR-automaton is a continuous rational function in a neighborhood of any data point except in a point set, the Lebesgue measure of which is zero. An effective general-purpose algorithm is presented to compute the derivative of any result quantity with respect to the individual roundoff and truncation errors. Some ways of generalizing theR-automation model without losing the results achieved are finally suggested.     

Iterative algorithms for solving some tensor equations

We propose a class of iterative algorithms to solve some tensor equations via Einstein product. These algorithms use tensor computations with no matricizations involved. For any (special) initial tensor, a solution (the minimal Frobenius norm solution) of related problems can be obtained within finite iteration steps in the absence of roundoff errors. Numerical examples are provided to confirm the theoretical results, which demonstrate that this kind of iterative methods are effective and feasible for solving some tensor equations.     

Singular Stochastic Control Problems Solved by a Sparse Simplex Method

Numerical solutions of singular stochastic control problemsin bounded intervals are obtained by a sparse linear-programmingalgorithm. The algorithm terminates in a finite number of iterationsin the absence of roundoff errors. Applications to other problemsin control theory are discussed.     

On Accuracy in Computational Control Problems

In the paper we investigate the effects of roundoff‐errors in the problem of computing a minimal realization of a linear timeinvariant system. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

One-modulus residue arithmetic algorithm to solve linear equations exactly

The paper presents an error-free algorithm to solve linear equations using the residue arithmetic. Simultaneously with solving linear equation system, the exact value of determinant of the system matrix is also calculated. The algorithm removes roundoff errors and according to this kind of errors ensures stability of the solution. It is suitable for implementation for computers with possibility of vector operations.     

矩阵方程AXA^T＋BYB^T=C的双对称最小二乘解及其最佳逼近

基于共轭梯度法的思想,通过特殊的变形,建立了一类求矩阵方程AXA^T＋BYB^T=C的双对称最小二乘解的迭代算法．对任意的初始双对称矩阵．在没有舍人误差的情况下,经过有限步迭代得到它的双对称最小二乘解;在选取特殊的初始双对称矩阵时,能得到它的的极小范数双对称最小二乘解．另外,给定任意矩阵,利用此方法可得到它的最佳逼近双对称解,数值例子表明,这种方法是有效的．     

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.     

Input tracking for a parabolic equation on an infinite time interval

We study the input tracking problem for a parabolic equation on an infinite time interval on the basis of the measurement of phase coordinates. We suggest an algorithm stable under information noises and roundoff errors for the solution of the problem on the basis of constructions of dynamic inversion theory.     

Optimization of functions whose values are subject to small errors

In this paper we consider the minimization of a function whose values can only be obtained with an error. For the case when the error has certain statistical properties this problem has been investigated by Kiefer and Wolfowitz (1) and Kushner (2, 3). Kushner has shown that a certain class of algorithms converge to a stationary point with probability one. Here a different approach is used. The error is assumed to have an upper bound and it is shown that a stationary point can be obtained to within a certain accuracy, dependent on the magnitude of the error. Our results are related to works concerning roundoff errors for one dimensional optimization (4) and solution of nonlinear equations (5). The algorithm we use can be regarded as an extension of the methods used in (6), (8) and (9).Supported by: Institutet för tillämpad matematik (Sweden) and the National Science Foundation (USA) under grant MPS 72-04787-a02.     

Adaptive solution of elliptic PDE-eigenvalue problems.

In this paper we introduce a new adaptive algorithm (AFEMLA) for elliptic PDE-eigenvalue problems. In contrast to other approaches the algebraic eigenvalue problem does not have to be solved to full accuracy. We incorporate the iterative solution of the resulting finite dimensional algebraic eigenvalue problems in the adaptation process in order to balance the cost with the costs for the iterative eigenvalue method. We present error estimates that incorporate the discretization errors, approximation errors in the eigenvalue solver and roundoff errors. (© 2009 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

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.     

Superlinear Convergence of a Stabilized SQP Method to a Degenerate Solution

We describe a slight modification of the well-known sequential quadratic programming method for nonlinear programming that attains superlinear convergence to a primal-dual solution even when the Jacobian of the active constraints is rank deficient at the solution. We show that rapid convergence occurs even in the presence of the roundoff errors that are introduced when the algorithm is implemented in floating-point arithmetic.     

双变量LMEs一种异类约束最小二乘解的MCG算法

借鉴求线性矩阵方程组(LMEs)同类约束最小二乘解的修正共轭梯度法,建立了求双变量LMEs的一种异类约束最小二乘解的修正共轭梯度法,并证明了该算法的收敛性.在不考虑舍入误差的情况下,利用该算法不仅可在有限步计算后得到LMEs的一组异类约束最小二乘解,而且选取特殊初始矩阵时,可求得LMEs的极小范数异类约束最小二乘解.另外,还可求得指定矩阵在该LMEs的异类约束最小二乘解集合中的最佳逼近.算例表明,该算法是有效的.     

Exact calculation of inverse functions

We represent continuous functions on compact intervals by sequences of functions defined on finite sets of rational numbers. We call this an exact representation. This enables us to calculate the values of the function arbitrarily exactly, without roundoff errors. As an application we develop a procedure to transfer an exact representation of an increasing function into an exact representation of the corresponding inverse function. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

An iterative method for updating gyroscopic systems based on measured modal data

An efficient iterative method for updating the mass, gyroscopic and stiffness matrices simultaneously using a few of complex measured modal data is developed. By using the proposed iterative method, the unique symmetric solution can be obtained within finite iteration steps in the absence of roundoff errors by choosing a special kind of initial matrices. Numerical results show that the presented method can be used to update finite element models to get better agreement between analytical and experimental modal parameters.     

Spectral collocation method and Darvishi’s preconditionings to solve the generalized Burgers–Huxley equation

In this paper, a numerical solution of the generalized Burgers–Huxley equation is presented. This is the application of spectral collocation method. To reduce roundoff error in this method we use Darvishi’s preconditionings. The numerical results obtained by this method have been compared with the exact solution. It can be seen that they are in a good agreement with each other, because errors are very small and figures of exact and numerical solutions are very similar.