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.     

Reguläre Zerlegungen und Berechnung des Spektralradius nichtnegativer Matrizen

Summary On the basis of a Rayleigh Quotient Iteration method in [10] and a Maximal Quotient Iteration method in [5, 8] two algorithms for solving special eigenvalue problems are developed. The characteristic properties of these methods lie in the application of iterative linear methods to solving systems of linear equations. The convergence properties are investigated. We apply the algorithms to the computation of the spectralradius of a nonnegative irreducible matrix.

     

Zur Konvergenz eines Verfahrens von D.J. Evans zur iterativen Verbesserung einer Näherung für die inverse Matrix

Summary Recently D.J. Evans introduced an implicit matrix inversion process showing asymptotic behaviour which is superior to that of the well known Schulz-method. In this paper we give sufficient conditions for convergence, prove some error bounds and show that under certain conditions the iterates are converging monotonously.

Herrn Johannes Weissinger zum Siebzigsten Geburtstag gewidmet.     

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.     

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.     

Einschließung inverser Elemente durch Fixpunktverfahren

Summary In a partially ring, linearly convergent methods are constructed in order to enclose the inverse of a given element monotonously. For this purpose by means of a first approximation the original problem is transformed into a fixed-point equation with a contractive operator. The approach is describted if the element to inverse is known exactly or approximatively, too.

     

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     

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.     

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     

Convergent nonnegative matrices and iterative methods for consistent linear systems

Summary In this paper we study linear stationary iterative methods with nonnegative iteration matrices for solving singular and consistent systems of linear equationsAx=b. The iteration matrices for the schemes are obtained via regular and weak regular splittings of the coefficients matrixA. In certain cases when only some necessary, but not sufficient, conditions for the convergence of the iterations schemes exist, we consider a transformation on the iteration matrices and obtain new iterative schemes which ensure convergence to a solution toAx=b. This transformation is parameter-dependent, and in the case where all the eigenvalues of the iteration matrix are real, we show how to choose this parameter so that the asymptotic convergence rate of the new schemes is optimal. Finally, some applications to the problem of computing the stationary distribution vector for a finite homogeneous ergodic Markov chain are discussed.Research sponsored in part by US Army Research Office     

Updating the singular value decomposition

Summary LetA be anm×n matrix with known singular value decomposition. The computation of the singular value decomposition of a matrixà is considered, whereà is obtained by appending a row or a column toA whenmn or by deleting a row or a column fromA whenm>n. An algorithm is also presented for solving the updated least squares problemà y–b, obtained from the least squares problemAx–b by appending an equation, deleting an equation, appending an unknown, or deleting an unknown.This research was supported by NSF grants MCS 75-06510 and MCS 76-03139     

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.     

A class of direct methods for linear systems

Summary A class of methods of direct type for solving determined or underdetermined, full rank or deficient rank linear systems is presented and theoretically analyzed. The class can be considered as a generalization of the methods of Brent and Brown as restricted to linear systems and implicitly contains orthogonal,LU andLL ^T factorization methods.     

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     

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.     

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

Alternating methods for sets of linear equations

Summary A generalization of alternating methods for sets of linear equations is described and the number of operations calculated. It is shown that the lowest number of arithmetic operations is achieved in the SSOR algorithm.     

An alternative givens ordering

Summary A new Givens ordering is shown, empirically and by an approximate theoretical analysis, to take appreciably fewer stages than the standard scheme. Sharper error bounds than Gentleman's ensue, and the scheme is better suited to parallel computation. Other schemes, less efficient but more easily analysed, are discussed. The effect of a possible limit in practice on the number of simultaneous computations is considered.