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].     

矩阵的WZ分解及其误差分析

在[1]中,对矩阵A进行WZ分解,其中矩阵W=(w_(i,j))和Z=(z_(i,j))形状如下: 1, i=j, w_(i,j)=任意,min(i,n-i+1)相似文献   

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.     

Using the Sherman-Morrison-Woodbury inversion formula for a fast solution of tridiagonal block Toeplitz systems

A fast numerical algorithm for solving systems of linear equations with tridiagonal block Toeplitz matrices is presented. The algorithm is based on a preliminary factorization of the generating quadratic matrix polynomial associated with the Toeplitz matrix, followed by the Sherman-Morrison-Woodbury inversion formula and solution of two bidiagonal and one diagonal block Toeplitz systems. Tight estimates of the condition numbers are provided for the matrix system and the main matrix systems generated during the preliminary factorization. The emphasis is put on rigorous stability analysis to rounding errors of the Sherman-Morrison-Woodbury inversion. Numerical experiments are provided to illustrate the theory.     

Error estimates for Miller's algorithm

Summary A rigorous error analysis is given of both truncation and rounding errors in Miller's algorithm for three-term scalar recursions and 2×2 matrix-vector recursions. The error bounds are shown to be very realistic and this will be supported by examples. The results are generalized to recursions of higher order.     

Pivoting strategy for rank-one modification ofLDM t-like factorization

The rank-one modification algorithm of theLDM ^t factorization was given by Bennett [1]. His method, however, could break down even when the matrix is nonsingular and well-conditioned. We introduce a pivoting strategy for avoiding possible break-down as well as for suppressing error growth in the modification process. The method is based on a symbolic formula of the rank-one modification of the factorization of a possibly singular nonsymmetric matrix. A new symbolic formula is also obtained for the inverses of the factor matrices. Repeated application of our method produces theLDM ^t-like product form factorization of a matrix. A numerical example is given to illustrate our pivoting method. An incomplete factorization algorithm is also introduced for updating positive definite matrix useful in quasi-Newton methods, in which the Fletcher and Powell algorithm [2] and the Gill, Murray and Saunders algorithm [4] are usually used.This paper is presented at the Japan SIAM Annual Meeting held at University of Tokyo, Japan, October 7–9, 1991.     

An extension of Olver's error estimation technique for linear recurrence relations

When unstable rounding error propagation prevents a linear recurrence relation being solved recursively a sufficiently accurate solution may be determined in certain cases by an inexact but well-conditioned boundary-value problem. An algorithm, based on that ofOlver for second order relations, is given for estimating the truncation error in the general case, and a practical computational technique developed for relations having solutions of exponential type.     

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     

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.     

连续代数扩域上多项式因式分解的Trager算法

多项式的因式分解是符号计算中最基本的算法,二十世纪六十年代开始出现的关于多项式因式分解的工作被认为是符号计算领域的起源．目前多项式的因式分解已经成熟,并已在Maple等符号计算软件中实现,但代数扩域上的因式分解算法还有待进一步改进．代数扩域上的基本算法是Trager算法．Weinberger等提出了基于Hensel提升的算法．这些算法是在单个扩域上做因式分解．而在吴零点分解定理中,多个代数扩域上的因式分解是非常基本的一步,主要用于不可约升列的计算．为了解决这一问题,吴文俊,胡森、王东明分别提出了基于方程求解的多个扩域上的因式分解算法．王东明、林东岱提出了另外一个算法Trager算法相似,将问题化为有理数域上的分解．他们应用了吴的三角化算法,因此算法的终止性依赖于吴方法的计算．支丽红则将提升技巧用于多个扩域上的因式分解算法．本文将Trager的算法直接推广为连续扩域上的因式分解,只涉及结式计算与有理数域上的因式分解,给出了多个代数扩域上的因式分解一个直接的算法．     

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.     

棋盘游戏与有限域上多项式分解算法

将有限域F_2上多项式分解问题转化为一种对应的棋盘游戏,利用后者的性质设计了一个F_2上m+n-2次多项式f(x)分解为一个m-1次多项式与一个n-1次多项式的判断、分解算法,并对算法的复杂度进行了分析.算法的一个优势是,如果f(x)不能按要求分解,也可以找到一个与f(x)相近(这里指系数相异项较少)的多项式的分解.     

The selection of interpolation points in the numerical approximation of second and third order derivatives

The first or higher derivatives of a function may be estimated numerically by applying Neville's polynomial extrapolation process to a sequence of approximations to the derivative, each consisting of a suitable linear combination of function values. The sequences of evaluation points which minimise the magnification of rounding errors relative to the truncation error for first, second and third order derivatives are determined, and it is shown that by defining the sequences of evaluation points by certain geometric progressions the amount of computation may be reduced without greatly increasing the rounding error magnification.     

Toeplitz型矩阵的逆矩阵的快速三角分解算法

针对有关“型”矩阵的三角分解问题 ,提出了一种 Toeplitz型矩阵的逆矩阵的快速三角分解算法 .首先假设给定 n阶非奇异矩阵 A,利用一组线性方程组的解 ,得到 A- 1的一个递推关系式 ,进而利用该关系式得到 A- 1的一种三角分解表达式 ,然后从 Toeplitz型矩阵的特殊结构出发 ,利用上述定理的结论 ,给出了Toeplitz型矩阵的逆矩阵的一种快速三角分解算法 ,算法所需运算量为 O( mn2 ) .最后 ,数值计算表明该算法的可靠性 .     

Smooth factorizations of matrix valued functions and their derivatives

Summary In this paper we study the numerical factorization of matrix valued functions in order to apply them in the numerical solution of differential algebraic equations with time varying coefficients. The main difficulty is to obtain smoothness of the factors and a numerically accessible form of their derivatives. We show how this can be achieved without numerical differentiation if the derivative of the given matrix valued function is known. These results are then applied in the numerical solution of differential algebraic Riccati equations. For this a numerical algorithm is given and its properties are demonstrated by a numerical example.     

Rounding Errors in Solving Block Hessenberg Systems

A rounding error analysis is presented for a divide-and-conquer algorithm to solve linear systems with block Hessenberg matrices. Conditions are derived under which the algorithm computes a stable solution. The algorithm is shown to be stable for block diagonally dominant matrices and for M-matrices.

     

A direct error analysis for least squares

A direct error analysis is given for orthogonal factorization methods for calculating the least squares solution of an overdetermined system of linear equations. The direct method has the interesting advantage in that it permits the separation of errors occurring in the transformation and back-substitution phases of solution. This shows the partial elimination of potentially significant terms occurring in different stages of the algorithm. Presumably it is prudent to minimize the error at each stage of the algorithm, so it is significant that numerical evidence shows column pivoting can reduce the magnitude of these terms. This is offered as an explanation for the common observation that column pivoting is beneficial in least squares calculations. We also summarize the corresponding error analysis for the calculation of the minimum norm solution of an underdetermined system using orthogonal transformations.     

Towards accurate statistical estimation of rounding errors in floating-point computations

A new method of estimatinga posteriori the statistical characteristics of the rounding errors of an arbitrary algorithm is presented. This method is based on a discrete model of the distribution of rounding errors which makes more accurate estimates possible. The analysis is given for both rounding and truncating arithmetic. Finally, some experimental results are reported.     

Factorizing words over an ordered alphabet

An efficient algorithm to obtain a factorization of words over an ordered alphabet known as Lyndon factorization is presented. Applications of this algorithm are given to the computation of the least suffix of a word and the least circular shift of a word.     

Solving cubics by polynomial fitting

A top-performance algorithm for solving cubic equations is introduced. This algorithm uses polynomial fitting for a decomposition of the given cubic into a product of a quadratic and a linear factor. This factorization can be computed extremely accurately and efficiently using a fixed-point iteration of the linearized fitting error. The polynomial fitting concept performs orders of magnitude better in terms of numerical accuracy and precision than any of the currently known and available algorithms for solving cubic equations. A special exception handler is presented for a reliable operation in the event of double, triple and tightly clustered roots.