AB-Algorithm and its modifications for the spectral problems of linear pencils of matrices

Summary This paper describes and algorithm and its modifications for solving spectral problems for linear pencils of matrices both regular as well as singular.     

A Newton iteration process for inverse eigenvalue problems

Summary We suppose an inverse eigenvalue problem which includes the classical additive and multiplicative inverse eigenvalue problems as special cases. For the numerical solution of this problem we propose a Newton iteration process and compare it with a known method. Finally we apply it to a numerical example.     

On the global convergence of the Eberlein method for real matrices

Summary The global convergence proof of the column-and row-cyclic Eberlein diagonalization process for real matrices is given. The convergence to a fixed matrix in Murnaghan form is obtained with the well-known exception of complex-conjugate pairs of eigenvalues whose real parts are more than double.     

On a class of Jacobi-like procedures for diagonalising arbitrary real matrices

Summary A new class of elementary matrices is presented which are convenient in Jacobi-like diagonalisation methods for arbitrary real matrices. It is shown that the presented transformations possess the normreducing property and that they produce an ultimate quadratic convergence even in the case of complex eigenvalues. Finally, a quadratically convergent Jacobi-like algorithm for real matrices with complex eigenvalues is presented.     

On a new class of elementary matrices

Summary A new class of elementary matrices, a block-generalisation of plane rotations, is presented and the application in constructing quadratically convergent block diagonalisation algorithms of Jacobi type is discussed.     

Comparison of splittings used with the conjugate gradient algorithm

We consider several possible criteria for comparing splittings used with the conjugate gradient algorithm. We present sharp upper bounds for the error at each step of the algorithm and compare several widely used splittings with respect to their effect on these sharp upper bounds. We then consider a more stringent comparison test, and present necessary and sufficient conditions for the error at each step with one splitting to be smaller than that with another, for all pairs of corresponding initial guesses.     

Realistic error bounds for a simple eigenvalue and its associated eigenvector

Summary An algorithm is described which, given an approximate simple eigenvalue and a corresponding approximate eigenvector, provides rigorous error bounds for improved versions of them. No information is required on the rest of the eigenvalues, which may indeed correspond to non-linear elementary divisors. A second algorithm is described which gives more accurate improved versions than the first but provides only error estimates rather than rigorous bounds. Both algorithms extend immediately to the generalized eigenvalue problem.Dedicated to A.S. Householder on his 75th birthday     

A quasi-Newton method for solving fixed point problems in Hilbert spaces

Summary We study the convergence properties of a projective variant of Newton's method for the approximation of fixed points of completely continuous operators in Hilbert spaces. We then discuss applications to nonlinear integral equations and we produce some numerical examples.     

Rank-one modification of the symmetric eigenproblem

Summary An algorithm is presented for computing the eigensystem of the rank-one modification of a symmetric matrix with known eigensystem. The explicit computation of the updated eigenvectors and the treatment of multiple eigenvalues are discussed. The sensitivity of the computed eigenvectors to errors in the updated eigenvalues is shown by a perturbation analysis.Support for this research was provided by NSF grants MCS 75-06510 and MCS 76-03139Support for this research was provided by the Applied Mathematics Division, Argonne National Laboratory, Argonne, IL 60439, USA     

A factorization method for the solution of constrained linear least squares problems allowing subsequent data changes

Summary In this paper we describe how to use Gram-Schmidt factorizations of Daniel et al. [1] to realize the method of [8] for solving linearly constrained linear least squares problems. The main advantage of using these factorizations is that it is relatively easy to take data changes into account, if necessary.The algorithm is compared numerically with two other codes, one of them published by Lawson and Hanson [3]. Further computational tests show the efficiency of the proposed methods, if a few data of the original problem are changed subsequently.This paper was sponsored by Deutsche Forschungsgemeinschaft, Bonn-Bad Godesberg     

Strong underrelaxation in Kaczmarz's method for inconsistent systems

Summary We investigate the behavior of Kaczmarz's method with relaxation for inconsistent systems. We show that when the relaxation parameter goes to zero, the limits of the cyclic subsequences generated by the method approach a weighted least squares solution of the system. This point minimizes the sum of the squares of the Euclidean distances to the hyperplanes of the system. If the starting point is chosen properly, then the limits approach the minimum norm weighted least squares solution. The proof is given for a block-Kaczmarz method.     

Some new results on Unsymmetric Successive Overrelaxation method

Summary The Unsymmetric Successive Overrelaxation (USSOR) iterative method is applied to the solution of the system of linear equationsA x=b, whereA is annxn nonsingular matrix. We find the values of the relaxation parameters and for which the USSOR iterative method converges. Then we characterize those matrices which are equimodular toA and for which the USSOR iterative method converges.     

A new method for the solution ofAx=b

Summary An alternative to Gauss elimination is developed to solveAx=b. The method enables one to exploit zeros in the lower triangle ofA, so that the number of multiplications needed to perform the algorithm can be substantially reduced.     

Precise domains of convergence for the block SSOR method associated withp-cyclic matrices

We apply Rouché's theorem to the functional equation relating the eigenvalues of theblock symmetric successive overrelaxation (SSOR) matrix with those of the block Jacobi iteration matrix found by Varga, Niethammer, and Cai, in order to obtain precise domains of convergence for the block SSOR iteration method associated withp-cyclic matricesA, p3. The intersection of these domains, taken over all suchp's, is shown to coincide with the exact domain of convergence of thepoint SSOR iteration method associated withH-matricesA. The latter domain was essentially discovered by Neumaier and Varga, but was recently sharpened by Hadjidimos and Neumann.Research supported in part by NSF Grant DMS 870064.     

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.     

Positivity in complex spaces and its application to Gershgorin discs

Summary The classical proof that a separated Gershgorin disc contains an eigenvalue uses a continuity argument which is not applicable to Bauers generalized Gershgorin discs. In this paper the concept of positivity, generalized to complex vector spaces, is used to establish Gershgorins result and to improve the corresponding result for Bauers generalization.Dedicated to Professor F.L. Bauer on the occasion of his 60th birthday     

A modified bisection algorithm for the determination of the eigenvalues of a symmetric tridiagonal matrix

Summary A modification to the well known bisection algorithm [1] when used to determine the eigenvalues of a real symmetric matrix is presented. In the new strategy the terms in the Sturm sequence are computed only as long as relevant information on the required eigenvalues is obtained. The resulting algorithm usingincomplete Sturm sequences can be shown to minimise the computational work required especially when only a few eigenvalues are required.The technique is also applicable to other computational methods which use the bisection process.     

Computing theCS decomposition of a partitioned orthonormal matrix

Summary This paper describes an algorithm for simultaneously diagonalizing by orthogonal transformations the blocks of a partitioned matrix having orthonormal columns.This work was supported by the Air Force Office of Scientific Research under Contract No. AFOSR-82-0078     

Least squares with a quadratic constraint

Summary We present the theory of the linear least squares problem with a quadratic constraint. New theorems characterizing properties of the solutions are given. A numerical application is discussed.     

Numerical solution for exterior problems

Summary We solve the Helmholtz equation in an exterior domain in the plane. A perfect absorption condition is introduced on a circle which contains the obstacle. This boundary condition is given explicitly by Bessel functions. We use a finite element method in the bounded domain. An explicit formula is used to compute the solution out of the circle. We give an error estimate and we present relevant numerical results.