共查询到20条相似文献,搜索用时 11 毫秒
1.
Summary. A new algorithm for triangularizing an Toeplitz matrix is presented. The algorithm is based on the previously developed recursive algorithms that exploit the Toeplitz
structure and compute each row of the triangular factor via updating and downdating steps. A forward error analysis for this
existing recursive algorithm is presented, which allows us to monitor the conditioning of the problem, and use the method
of corrected semi-normal equations to obtain higher accuracy for certain ill-conditioned matrices. Numerical experiments show
that the new algorithm improves the accuracy significantly while the computational complexity stays in .
Received April 30, 1995 / Revised version received February 12, 1996 相似文献
2.
Roland W. Freund 《Numerische Mathematik》1994,68(1):35-69
Summary.
The Bareiss algorithm is one of the classical fast
solvers for systems of linear equations with Toeplitz
coefficient matrices.
The method takes advantage of the special structure,
and it computes the solution of a Toeplitz system
of order~ with only~
arithmetic operations, instead of~
operations.
However, the original Bareiss algorithm requires that
all leading principal submatrices be nonsingular, and
the algorithm is numerically unstable if singular or ill-conditioned
submatrices occur.
In this paper, an extension of the Bareiss algorithm to
general Toeplitz systems is presented.
Using look-ahead techniques, the proposed algorithm can skip over
arbitrary blocks of singular or ill-conditioned submatrices,
and at the same time, it still fully exploits the Toeplitz
structure.
Implementation details and operations counts are given, and
numerical experiments are reported.
We also discuss special versions of the proposed look-ahead Bareiss
algorithm for Hermitian indefinite Toeplitz systems and
banded Toeplitz systems.
Received August 27, 1993 / Revised version received March 1994 相似文献
3.
Summary. It is well known that any nonsingular M–matrix admits an LU factorization into M–matrices (with L and U lower and upper triangular respectively) and any singular M–matrix is permutation similar to an M–matrix which admits an
LU factorization into M–matrices. Varga and Cai establish necessary and sufficient conditions for a singular M–matrix (without
permutation) to allow an LU factorization with L nonsingular. We generalize these results in two directions. First, we find necessary and sufficient conditions for the existence
of an LU factorization of a singular M-matrix where L and U are both permitted to be singular. Second, we establish the minimal block structure that a block LU factorization of a singular
M–matrix can have when L and U are M–matrices.
Received November 21, 1994 / Revised version received August 4, 1997 相似文献
4.
Convergence of block two-stage iterative methods for symmetric positive definite systems 总被引:2,自引:0,他引:2
Zhi-Hao Cao 《Numerische Mathematik》2001,90(1):47-63
Summary. We study the convergence of two-stage iterative methods for solving symmetric positive definite (spd) systems. The main tool
we used to derive the iterative methods and to analyze their convergence is the diagonally compensated reduction (cf. [1]).
Received December 11, 1997 / Revised version received March 25, 1999 / Published online May 30, 2001 相似文献
5.
Bernhard Beckermann 《Numerische Mathematik》2000,85(4):553-577
Summary. We show that the Euclidean condition number of any positive definite Hankel matrix of order may be bounded from below by with , and that this bound may be improved at most by a factor . Similar estimates are given for the class of real Vandermonde matrices, the class of row-scaled real Vandermonde matrices,
and the class of Krylov matrices with Hermitian argument. Improved bounds are derived for the case where the abscissae or
eigenvalues are included in a given real interval. Our findings confirm that all such matrices – including for instance the
famous Hilbert matrix – are ill-conditioned already for “moderate” order. As application, we describe implications of our
results for the numerical condition of various tasks in Numerical Analysis such as polynomial and rational i nterpolation
at real nodes, determination of real roots of polynomials, computation of coefficients of orthogonal polynomials, or the iterative
solution of linear systems of equations.
Received December 1, 1997 / Revised version received February 25, 1999 / Published online 16 March 2000 相似文献
6.
Summary. By providing a matrix version of Koenig's theorem we reduce the problem of evaluating the coefficients of a monic factor
r(z) of degree h of a power series f(z) to that of approximating the first h entries in the first column of the inverse of an Toeplitz matrix in block Hessenberg form for sufficiently large values of n. This matrix is reduced to a band matrix if f(z) is a polynomial. We prove that the factorization problem can be also reduced to solving a matrix equation for an matrix X, where is a matrix power series whose coefficients are Toeplitz matrices. The function is reduced to a matrix polynomial of degree 2 if f(z) is a polynomial of degreeN and . These reductions allow us to devise a suitable algorithm, based on cyclic reduction and on the concept of displacement rank,
for generating a sequence of vectors that quadratically converges to the vector having as components the coefficients of the factor r(z). In the case of a polynomial f(z) of degree N, the cost of computing the entries of given is arithmetic operations, where is the cost of solving an Toeplitz-like system. In the case of analytic functions the cost depends on the numerical degree of the power series involved
in the computation. From the numerical experiments performed with several test polynomials and power series, the algorithm
has shown good numerical properties and promises to be a good candidate for implementing polynomial root-finders based on
recursive splitting strategies. Applications to solving spectral factorization problems and Markov chains are also shown.
Received September 9, 1998 / Revised version received November 14, 1999 / Published online February 5, 2001 相似文献
7.
Roy Mathias 《Numerische Mathematik》1996,74(1):85-103
Summary. Let where is a positive definite matrix and is diagonal and nonsingular. We show that if the condition number of is much less than that of then we can use algorithms based on the Cholesky factorization of to compute the eigenvalues of to high relative accuracy more efficiently than by Jacobi's method. The new methods are generally slower than tridiagonalization
methods (which do not deliver the eigenvalues to maximal relative accuracy) but can be up to 4 times faster when the condition
number of is very large.
Received April 13, 1995 相似文献
8.
Summary. In this work, we introduce and analyze two new techniques for obtaining the Q factor in the QR factorization of some (or all) columns of a fundamental solution matrix Y of a linear differential system. These techniques are based on elementary Householder and Givens transformations. We implement
and compare these new techniques with existing approaches on some examples.
Received October 27, 1997 / Revised version received September 21, 1998 / Published online August 19, 1999 相似文献
9.
Zhi-Hao Cao 《Numerische Mathematik》2001,88(4):603-606
Summary. Recently, Benzi and Szyld have published an important paper [1] concerning the existence and uniqueness of splittings for
singular matrices. However, the assertion in Theorem 3.9 on the inheriting property of P-regular splitting for singular symmetric
positive semidefinite matrices seems to be incorrect. As a complement of paper [1], in this short note we point out that if
a matrix T is resulted from a P-regular splitting of a symmetric positive semidefinite matrix A, then splittings induced by T are not all P-regular.
Received January 7, 1999 / Published online December 19, 2000 相似文献
10.
Summary. We present new theoretical results on two classes of multisplitting methods for solving linear systems iteratively. These
classes are based on overlapping blocks of the underlying coefficient matrix which is assumed to be a band matrix. We show that under suitable conditions the spectral radius of the iteration matrix does not depend on the weights of the method even if these weights are allowed to be negative. For a certain class of splittings
we prove an optimality result for with respect to the weights provided that is an M–matrix. This result is based on the fact that the multisplitting method can be represented by a single splitting
which in our situation surprisingly turns out to be a regular splitting. Furthermore we show by numerical examples that weighting
factors may considerably improve the convergence.
Received July 18, 1994 / Revised version received November 20, 1995 相似文献
11.
Semiconvergence of nonnegative splittings for singular matrices 总被引:1,自引:0,他引:1
Yongzhong Song 《Numerische Mathematik》2000,85(1):109-127
Summary. In this paper, we discuss semiconvergence of the matrix splitting methods for solving singular linear systems. The concepts
that a splitting of a matrix is regular or nonnegative are generalized and we introduce the terminologies that a splitting
is quasi-regular or quasi-nonnegative. The equivalent conditions for the semiconvergence are proved. Comparison theorem on
convergence factors for two different quasi-nonnegative splittings is presented. As an application, the semiconvergence of
the power method for solving the Markov chain is derived. The monotone convergence of the quasi-nonnegative splittings is
proved. That is, for some initial guess, the iterative sequence generated by the iterative method introduced by a quasi-nonnegative
splitting converges towards a solution of the system from below or from above.
Received August 19, 1997 / Revised version received August 20, 1998 / Published online January 27, 2000 相似文献
12.
J. Matejaš 《Numerische Mathematik》2000,87(1):171-199
Summary. A quadratic convergence bound for scaled Jacobi iterates is proved provided the initial symmetric positive definite matrix has simple eigenvalues. The bound is expressed in terms of the off-norm of the scaled initial matrix and the minimum relative gap in the spectrum. The obtained result can be used to predict the stopping moment in the two-sided and especially in the one-sided Jacobi method. Received October 31, 1997 / Revised version received March 8, 1999 / Published online July 12, 2000 相似文献
13.
Summary. This paper introduces and analyzes the convergence properties of a method that computes an approximation to the invariant
subspace associated with a group of eigenvalues of a large not necessarily diagonalizable matrix. The method belongs to the
family of projection type methods. At each step, it refines the approximate invariant subspace using a linearized Riccati's
equation which turns out to be the block analogue of the correction used in the Jacobi-Davidson method. The analysis conducted
in this paper shows that the method converges at a rate quasi-quadratic provided that the approximate invariant subspace is
close to the exact one. The implementation of the method based on multigrid techniques is also discussed and numerical experiments
are reported.
Received June 15, 2000 / Revised version received January 22, 2001 / Published online October 17, 2001 相似文献
14.
Summary. We consider the problem of minimizing
the spectral condition number of a positive definite matrix
by completion:
\noindent where is
an Hermitian positive definite
matrix, a matrix and is
a free Hermitian matrix. We reduce
this problem to an optimization problem for a convex function
in one variable. Using the minimal solution of this problem
we characterize the complete set of matrices that give the minimum
condition number.
Received October 15, 1993 相似文献
15.
Colm Art O'Cinneide 《Numerische Mathematik》1996,73(4):507-519
Summary.
Recently the author showed that the Grassmann-Taksar-Heyman
(GTH) algorithm computes the steady-state
distribution of a finite-state
Markov chain with low relative error.
Here it is shown that the
LU decomposition
computed in the course of the
GTH algorithm also has low relative error.
The proof requires a refinement of the methods used in
the earlier paper.
Received September 2, 1994 / Revised version received
July 17, 1995 相似文献
16.
Alexander N. Malyshev 《Numerische Mathematik》1999,83(3):443-454
Summary. We prove that the 2-norm distance from an matrix A to the matrices that have a multiple eigenvalue is equal to where the singular values are ordered nonincreasingly. Therefore, the 2-norm distance from A to the set of matrices with multiple eigenvalues is
Received February 19, 1998 / Revised version received July 15, 1998 / Published online: July 7, 1999 相似文献
17.
Summary. Suppose one approximates an invariant subspace of an
matrix in
which in not necessarily
self--adjoint. Suppose
that one also has an approximation for the corresponding eigenvalues. We
consider the question of how good the approximations are. Specifically, we
develop bounds on the angle between the approximating subspace and the
invariant subspace itself.
These bounds are functions
of the following three terms: (1) the residual of the approximations; (2)
singular--value separation in an associated matrix; and (3) the goodness
of the approximations to the eigenvalues.
Received December 1, 1992 / Revised version received October 20,
1993 相似文献
18.
Summary.
In this paper we propose an algorithm based on Laguerre's iteration,
rank two divide-and-conquer technique and a hybrid strategy
for computing singular values of bidiagonal matrices.
The algorithm is fully parallel in nature and evaluates singular
values to tiny relative error if necessary. It is competitive with QR
algorithm in serial mode in speed and advantageous in computing
partial singular values. Error analysis and numerical results are
presented.
Received
March 15, 1993 / Revised version received June 7, 1994 相似文献
19.
Summary.
It is well known that the zeros of a polynomial are equal to
the
eigenvalues of the associated companion matrix . In this paper
we take a
geometric view of the conditioning of these two problems and of the stability of
algorithms for polynomial zerofinding. The
is the set of zeros of all polynomials obtained by
coefficientwise perturbations of of size ;
this is a subset of the
complex plane considered earlier by Mosier, and is bounded by a
certain generalized lemniscate. The
is another subset of
defined as the set of eigenvalues of matrices
with ; it is bounded by a
level curve of the resolvent
of $A$. We find that if $A$ is first balanced in the usual EISPACK sense, then
and
are usually quite close to one another. It follows that the Matlab
ROOTS algorithm of balancing the companion matrix, then computing its eigenvalues, is a stable
algorithm for polynomial zerofinding. Experimental comparisons with the
Jenkins-Traub (IMSL) and
Madsen-Reid (Harwell) Fortran codes confirm that these three algorithms have roughly
similar stability properties.
Received June 15, 1993 相似文献
20.
Summary. This paper deals with Vandermonde matrices whose nodes are the first integer numbers. We give an analytic factorization of such matrices and explicit formulas for the entries of their inverses,
and explore their computational issues. We also give asymptotic estimates of the Frobenius norm of both and its inverse.
Received July 28, 1995 / Revised version received July 4, 1997 相似文献