Extrapolation methods for some singular fixed point sequences

A fixed point sequence is singular if the Jacobian matrix at the limit has 1 as an eigenvalue. The asymptotic behaviour of some singular fixed point sequences in one dimension are extended toN dimensions. Three algorithms extrapolating singular fixed point sequences inN dimensions are given. Using numerical examples three algorithms are tested and compared.     

On the convergence of the symmetric SOR method for matrices with red-black ordering

Summary We prove that if the matrixA has the structure which results from the so-called red-black ordering and ifA is anH-matrix then the symmetric SOR method (called the SSOR method) is convergent for 0<<2. In the special case thatA is even anM-matrix we show that the symmetric single-step method cannot be accelerated by the SSOR method. Symmetry of the matrixA is not assumed.     

On box schemes for elartliptic variational inequalities

General finite volume approximations in two and three space dimensions are studied for the discretization of interior and boundary obstacle problems with mixed boundary conditions. First order convergence of the finite volume (box) solution is shown in the energy norm. Based on a discrete maximum principle there are proposed two penalization techniques for the solution of the finite volume inequalities. By coupling of discretization and penalty parameters the overall error is analyzed. The iterative solution of the penalty problems is discussed. Finally, results of numerical experiments are presented to illustrate the convergence behaviour between the exact, the box and the penalty solutions.     

Extended iterative methods for the solution of operator equations

Summary Given an iterative methodM ₀, characterized byx ^(k+1=G ₀(x( ^k )) (k0) (x(⁰) prescribed) for the solution of the operator equationF(x)=0, whereF:XX is a given operator andX is a Banach space, it is shown how to obtain a family of methodsM _p characterized byx ^(k+1=G _p (x( ^k )) (k0) (x(⁰) prescribed) with order of convergence higher than that ofM _o. The infinite dimensional multipoint methods of Bosarge and Falb [2] are a special case, in whichM ₀ is Newton's method.Analogues of Theorems 2.3 and 2.36 of [2] are proved for the methodsM _p, which are referred to as extensions ofM ₀. A number of methods with order of convergence greater than two are discussed and existence-convergence theorems for some of them are proved.Finally some computational results are presented which illustrate the behaviour of the methods and their extensions when used to solve systems of nonlinear algebraic equations, and some applications currently being investigated are mentioned.     

Some vector sequence transformations with applications to systems of equations

First, recursive algorithms for implementing some vector sequence transformations are given. In a particular case, these transformations are generalizations of Shanks transformation and the G-transformation. When the sequence of vectors under transformation is generated by linear fixed point iterations, Lanczos' method and the CGS are recovered respectively. In the case of a sequence generated by nonlinear fixed point iterations, a quadratically convergent method based on the -algorithm is recovered and a nonlinear analog of the CGS method is obtained.     

On the rate of convergence of the preconditioned conjugate gradient method

Summary We derive new estimates for the rate of convergence of the conjugate gradient method by utilizing isolated eigenvalues of parts of the spectrum. We present a new generalized version of an incomplete factorization method and compare the derived estimates of the number of iterations with the number actually found for some elliptic difference equations and for a similar problem with a model empirical distribution function.     

Error bounds for computed eigenvalues and eigenvectors

Summary On the basis of an existence theorem for solutions of nonlinear systems, a method is given for finding rigorous error bounds for computed eigenvalues and eigenvectors of real matrices. It does not require the usual assumption that the true eigenvectors span the whole space. Further, a priori error estimates for eigenpairs corrected by an iterative method are given. Finally the results are illustrated with numerical examples.Dedicated to Professor Yoshikazu Nakai on his sixtieth birthday     

Connections between the PCG method applied to systems with Red/Black form and its reduced system

This paper is concerned with the (preconditioned) conjugate gradient method for solving systems of linear algebraic equationsAx=b withA having Red/Black form. The connections between the Conjugate Gradient (CG) scheme applied toAx=b and its two reduced systems are explored under certain conditions.     

Regularization of nonlinear illposed problems with closed operators

In this paper Tikhonov regularization for nonlinear illposed problems is investigated. The regularization term is characterized by a closed linear operator, permitting seminorm regularization in applications. Results for existence, stability, convergence and con- vergence rates of the solution of the regularized problem in terms of the noise level are given. An illustrating example involving parameter estimation for a one dimensional stationary heat equation is given.     

On a global descent method for polynomials

Summary Given a complex polynomialp we determine a functionf _p : such that |p(f _p (z))||p(z)|,z withk<1. This result is used to introduce a global root-finding algorithm for polynomials.     

On the invariance of perturbed null vectors under column scaling

Summary It is shown that the approximate null vector of a perturbed degenerate matrix behaves linearly under column scaling up to second order terms in the perturbation. This result has important consequences for an estimation technique known to numerical analysts as total least squares and to statisticians as latent root regression.Dedicated to F.L. Bauer on the occasion of his 60th birthdayDepartment of Computer Science and Institute for Physical Science and Technology, University of Maryland at College Park. This work was done while the author was at the Scientific Computing Division of the National Bureau of Standards     

Error bounds for computed eigenvalues and eigenvectors. II

Summary In this paper, motivated by Symm-Wilkinson's paper [5], we describe a method which finds the rigorous error bounds for a computed eigenvalue ⁽⁰⁾ and a computed eigenvectorx ⁽⁰⁾ of any matrix A. The assumption in a previous paper [6] that ⁽⁰⁾,x ⁽⁰⁾ andA are real is not necessary in this paper. In connection with this method, Symm-Wilkinson's procedure is discussed, too.     

On resolvent conditions and stability estimates

As many numerical processes for time discretization of evolution equations can be formulated as analytic mappings of the generator, they can be represented in terms of the resolvent. To obtain stability estimates for time discretizations, one therefore would like to carry known estimates on the resolvent back to the time domain. For different types of bounds of the resolvent of a linear operator, bounds for the norm of the powers of the operator and for their sum are given. Under similar bounds for the resolvent of the generator, some new stability bounds for one-step and multistep discretizations of evolution equations are then obtained.     

On invariant closed curves for one-step methods

Summary We show that a one-step method as applied to a dynamical system with a hyperbolic periodic orbit, exhibits an invariant closed curve for sufficiently small step size. This invariant curve converges to the periodic orbit with the order of the method and it inherits the stability of the periodic orbit. The dynamics of the one-step method on the invariant curve can be described by the rotation number for which we derive an asymptotic expression. Our results complement those of [2, 3] where one-step methods were shown to create invariant curves if the dynamical system has a periodic orbit which is stable in either time direction or if the system undergoes a Hopf bifurcation.     

On a direct method for the solution of nearly uncoupled Markov chains

Summary This note is concerned with the accuracy of the solution of nearly uncoupled Markov chains by a direct method based on the LU decomposition. It is shown that plain Gaussian elimination may fail in the presence of rounding errors. A modification of Gaussian elimination with diagonal pivoting and correction of small pivots is proposed and analyzed. It is shown that the accuracy of the solution is affected by two condition numbers associated with aggregation and the coupling respectively.This work was supported in part by the Air Force Office of Sponsored Research under Contract AFOSR-87-0188     

A capacitance matrix method for Dirichlet problem on polygon region

Summary An efficient algorithm for the solution of linear equations arising in a finite element method for the Dirichlet problem is given. The cost of the algorithm is proportional toN ²log₂ N (N=1/h) where the cost of solving the capacitance matrix equations isNlog₂ N on regular grids andN ^3/2log₂ N on irregular ones.     

On a computational method for the second fundamental tensor and its application to bifurcation problems

Summary An algorithm is presented for the computation of the second fundamental tensorV of a Riemannian submanifoldM ofR ⁿ . FromV the riemann curvature tensor ofM is easily obtained. Moreover,V has a close relation to the second derivative of certain functionals onM which, in turn, provides a powerful new tool for the computational determination of multiple bifurcation directions. Frequently, in applications, thed-dimensional manifoldM is defined implicitly as the zero set of a submersionF onR ⁿ . In this case, the principal cost of the algorithm for computingV(p) at a given pointpM involves only the decomposition of the JacobianDF(p) ofF atp and the projection ofd(d+1) neighboring points ontoM by means of a local iterative process usingDF(p). Several numerical examples are given which show the efficiency and dependability of the method.Dedicated to R. S. Varga on the occasion of his sixtieth birthdayThis work was in part supported by the National Science Foundation (DCR-8309926) and the Office of Naval Research (N-00014-80-C09455). The second author began some of the work while visiting the University of Heidelberg/Germany as an Alexander von Humboldt Senior U.S. Scientist     

Avoiding breakdown in the CGS algorithm

The conjugate gradient squared algorithm can suffer of similar breakdowns as Lanczos type methods for the same reason that is the non-existence of some formal orthogonal polynomials. Thus curing such breakdowns is possible by jumping over these non-existing polynomials and using only those of them which exist. The technique used is similar to that employed for avoiding breakdowns in Lanczos type methods. The implementation of these new methods is discussed. Numerical examples are given.     

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.     

Numerical stability of descent methods for solving linear equations

Summary In this paper we perform a round-off error analysis of descent methods for solving a liner systemAx=b, whereA is supposed to be symmetric and positive definite. This leads to a general result on the attainable accuracy of the computed sequence {x _i } when the method is performed in floating point arithmetic. The general theory is applied to the Gauss-Southwell method and the gradient method. Both methods appear to be well-behaved which means that these methods compute an approximationx _i to the exact solutionA ^–1 b which is the exact solution of a slightly perturbed linear system, i.e. (A+A)x _i =b, A of order A, where is the relative machine precision and · denotes the spectral norm.