Positive diagonal solutions to the Lyapunov equations

We study various stability type conditions on a matrix A related to the consistency of the Lyapunov equation AD+DA^t positive definite, where D is a positive diagonal matrix. Such problems arise in mathematical economics, in the study of time-invariant continuous-time systems and in the study of predator-prey systems. Using a theorem of the alternative, a characterization is given for all A satisfying the above equation. In addition, some necessary conditions for consistency and some related ideas are discussed. Finally, a method for constructing a solution D to the equation is given for matrices A satisfying certain conditions.     

On the effective computation of the inertia of a non-hermitian matrix

Summary given a complex lower Hessenberg matrixA with unit codiagonal, a hermitian matrixH is constructed such that, ifH is non-singular InA= InH. IfA is real,H is real symmetric. Classical results of Fujiwara on the root-separation problem and of Schwarz on the eigenvalue-separation problem are included as special cases.The authors' research was conducted at the Universidade Estadual de Campinas and supported by the Fundação de Amparo à Pesquisa do Estado de São Paulo, Brasil, under grant n⁰ 78/0490.     

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.     

An exposá of the mullin-rota theory of polynomials of binomial type

The basic theorems of the Mullin-Rota theory of polynomials of binomial type are rederived here by a combination of the classical theory of generating functions and Rota's operator theoretical methods. As a result a certain number of new identities are obtained.     

Der fàltungsalgorithmus für dreidimensionale radon–probleme †

Filtered backprojection is an efficient numerical method for inversion of the Radon and x-ray transform. It can be adapted to the three dimensional case ([10], [11]). In this paper we present a method to calculate convolution kernels for filtered backprojection in three dimensions.     

The wavelet transform on Sobolev spaces and its approximation properties

Summary We extend the continuous wavelet transform to Sobolev spacesH ^s() for arbitrary reals and show that the transformed distribution lies in the fiber spaces . This generalisation of the wavelet transform naturally leads to a unitary operator between these spaces.Further the asymptotic behaviour of the transforms ofL ₂-functions for small scaling parameters is examined. In special cases the wevelet transform converges to a generalized derivative of its argument. We also discuss the consequences for the discrete wavelet transform arising from this property. Numerical examples illustrate the main result.Supported by the Deutsche Forschungsgemeinschaft under grant Lo 310/2-4     

Quartic X-splines

Summary The quartic periodic and nonperiodic X-spline are separated from the class of all piecewise-quartic interpolatory polynomials and their orders of convergence, smoothness and complexity of construction are examined. In particular, error estimates of interpolation of smooth functions at uniformly spaced knots by eight quartic X-splines of special interest are presented. The results are illustrated by a numerical example.     

Fast Givens rotations for orthogonal similarity transformations

Summary Fast Givens rotations with half as many multiplications are proposed for orthogonal similarity transformations and a matrix notation is introduced to describe them more easily. Applications are proposed and numerical results are examined for the Jacobi method, the reduction to Hessenberg form and the QR-algorithm for Hessenberg matrices. It can be seen that in general fast Givens rotations are competitive with Householder reflexions and offer distinct advantages for sparse matrices.     

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.     

On neighbouring matrices with quadratic elementary divisors

Summary Algorithms are presented which compute theQR factorization of an order-n Toeplitz matrix inO(n ²) operations. The first algorithm computes onlyR explicitly, and the second computes bothQ andR. The algorithms are derived from a well-known procedure for performing the rank-1 update ofQR factors, using the shift-invariance property of the Toeplitz matrix. The algorithms can be used to solve the Toeplitz least-squares problem, and can be modified to solve Toeplitz systems inO(n) space.     

Almost strictly totally positive matrices

A determinantal identity, frequently used in the study of totally positive matrices, is extended, and then used to re-prove the well-known univariate knot insertion formula for B-splines. Also we introduce a class of matrices, intermediate between totally positive and strictly totally positive matrices. The determinantal identity is used to show any minor of such matrices is positive if and only if its diagonal entries are positive. Among others, this class of matrices includes B-splines collocation matrices and Hurwitz matrices.This author acknowledges a sabbatical stay at IBM T.J. Watson Research Center in 1990, which was supported by a DGICYT grant from Spain.     

Efficient implementation of Jacobi's diagonalization method on the DAP

Summary The DAP architecture brings into consideration the Jacobi method where several non-interacting rotations can be performed in parallel. However the design of the algorithm is crucial in a parallel environment. In this paper we shall consider two techniques specifically designed to reduce the organisation and the arithmetic components of the parallel Jacobi method.     

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.     

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.     

Convergence of the shifted QR algorithm on 3×3 normal matrices

Summary This paper concerns the convergence properties of the shifted QR algorithm on 3×3 normal, Hessenberg matrices. The algorithm is viewed as an iteration on one dimensional subspaces. A class of matrices is characterized for which HQR2 is unable to approximate a solution.The author was partially supported by the NSF     

A Korovkin-type theory for finite Toeplitz operators via matrix algebras

Preconditioned conjugate gradients (PCG) are widely and successfully used methods for solving a Toeplitz linear system [59,9,20,5,34,62,6,10,28,45,44,46,49]. Frobenius-optimal preconditioners are chosen in some proper matrix algebras and are defined by minimizing the Frobenius distance from . The convergence features of these PCG have been naturally studied by means of the Weierstrass–Jackson Theorem [17,36,45], owing to the profound relationship between the spectral features of the matrices , generated by the Fourier coefficients of a continuous function f, and the analytical properties of the symbol f itself. In this paper, we capsize this point of view by showing that the optimal preconditioners can be used to define both new and just known linear positive operators uniformly approximating the function f. On the other hand, by modifying the Korovkin Theorem to study the Frobenius-optimal preconditioning problem, we provide a new and unifying tool for analyzing all Frobenius-optimal preconditioners in any generic matrix algebra related to trigonometric transforms. Finally, the multilevel case is sketched and discussed by showing that a Korovkin-type Theory also holds in a multivariate sense. Received October 1, 1996 / Revised version received May 7, 1998     

Some Remarks on a Canonical Marcenko Equation

AMS (MOS): 34A55, 35P25, 44A05

By expansion of the technique of dealing with integral transforms related to Fourier type operators P = D²- p it

is shown how a certain canonical Marcenko equation connecting P and a general Q can be expressed and derived more easily and its role as a factorization of Mar?enko data is exhibited.     

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