共查询到20条相似文献,搜索用时 15 毫秒
1.
Thomas Huckle 《Numerische Mathematik》1998,79(2):213-229
The problem of solving linear equations with a Toeplitz matrix appears in many applications. Often is positive definite but ill-conditioned with many small eigenvalues. In this case fast and superfast algorithms may show
a very poor behavior or even break down. In recent papers the transformation of a Toeplitz matrix into a Cauchy-type matrix
is proposed. The resulting new linear equations can be solved in operations using standard pivoting strategies which leads to very stable fast methods also for ill-conditioned systems. The
basic tool is the formulation of Gaussian elimination for matrices with low displacement rank. In this paper, we will transform
a Hermitian Toeplitz matrix into a Cauchy-type matrix by applying the Fourier transform. We will prove some useful properties of and formulate a symmetric Gaussian elimination algorithm for positive definite . Using the symmetry and persymmetry of we can reduce the total costs of this algorithm compared with unsymmetric Gaussian elimination. For complex Hermitian , the complexity of the new algorithm is then nearly the same as for the Schur algorithm. Furthermore, it is possible to include
some strategies for ill-conditioned positive definite matrices that are well-known in optimization. Numerical examples show
that this new algorithm is fast and reliable.
Received March 24, 1995 / Revised version received December 13, 1995 相似文献
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.
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 相似文献
5.
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 相似文献
6.
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 相似文献
7.
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 相似文献
8.
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 相似文献
9.
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 相似文献
10.
Summary. Systems of integer linear (Diophantine) equations arise from various applications. In this paper we present an approach,
based upon the ABS methods, to solve a general system of linear Diophantine equations. This approach determines if the system
has a solution, generalizing the classical fundamental theorem of the single linear Diophantine equation. If so, a solution
is found along with an integer Abaffian (rank deficient) matrix such that the integer combinations of its rows span the integer
null space of the cofficient matrix, implying that every integer solution is obtained by the sum of a single solution and
an integer combination of the rows of the Abaffian. We show by a counterexample that, in general, it is not true that any
set of linearly independent rows of the Abaffian forms an integer basis for the null space, contrary to a statement by Egervary.
Finally we show how to compute the Hermite normal form for an integer matrix in the ABS framework.
Received July 9, 1999 / Revised version received May 8, 2000 / Published online May 4, 2001 相似文献
11.
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 相似文献
12.
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 相似文献
13.
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 相似文献
14.
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 相似文献
15.
S. Maset 《Numerische Mathematik》2000,87(2):355-371
Summary. This paper investigates the stability of Runge-Kutta methods when they are applied to the complex linear scalar delay differential equation . This kind of stability is called stability. We give a characterization of stable Runge-Kutta methods and then we prove that implicit Euler method is stable. Received November 3, 1998 / Revised version received March 23, 1999 / Published online July 12, 2000 相似文献
16.
Summary. We have discovered a new implementation of the
qd algorithm that has a far wider domain of stability than Rutishauser's version. Our algorithm was
developed from an examination of the {Cholesky~LR} transformation and can be adapted
to parallel computation in stark contrast to traditional qd. Our algorithm also yields
useful a posteriori upper and lower bounds on the smallest singular
value of a bidiagonal matrix.
The zero-shift bidiagonal QR of Demmel and Kahan computes the smallest singular
values to maximal relative accuracy and the others to maximal absolute accuracy
with little or no degradation in efficiency when compared with the
LINPACK code. Our algorithm obtains maximal relative accuracy for all
the singular values and runs at least four times faster than the LINPACK code.
Received August 8, 1993/Revised version received May 26, 1993 相似文献
17.
Summary.
We present generalizations of the nonsymmetric Levinson and Schur algorithms
for non-Hermitian Toeplitz matrices with some singular or
ill-conditioned
leading principal submatrices. The underlying recurrences allow us to
go from any pair of successive well-conditioned leading principal submatrices
to any such pair of larger order. If the look-ahead step size between
these pairs is bounded, our generalized Levinson and Schur recurrences
require $ operations, and the Schur recurrences can be combined
with recursive doubling so that an $ algorithm results.
The overhead (in operations and storage) of look-ahead steps is very small.
There are various options for applying these algorithms to solving linear
systems with Toeplitz matrix.
Received July 26, 1993 相似文献
18.
Summary. A breakdown (due to a division by zero) can arise in the algorithms for implementing Lanczos' method because of the non-existence
of some formal orthogonal polynomials or because the recurrence relationship used is not appropriate. Such a breakdown can
be avoided by jumping over the polynomials involved. This strategy was already used in some algorithms such as the MRZ and
its variants.
In this paper, we propose new implementations of the recurrence relations of these algorithms which only need the storage
of a fixed number of vectors, independent of the length of the jump. These new algorithms are based on Horner's rule and on
a different way for computing the coefficients of the recurrence relationships. Moreover, these new algorithms seem to be
more stable than the old ones and they provide better numerical results.
Numerical examples and comparisons with other algorithms will be given.
Received September 2, 1997 / Revised version received July 24, 1998 相似文献
19.
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 相似文献
20.
Summary. Let be a square matrix dependent on parameters and , of which we choose as the eigenvalue parameter. Many computational problems are equivalent to finding a point such that has a multiple eigenvalue at . An incomplete decomposition of a matrix dependent on several parameters is proposed. Based on the developed theory two new algorithms are
presented for computing multiple eigenvalues of with geometric multiplicity . A third algorithm is designed for the computation of multiple eigenvalues with geometric multiplicity but which also appears to have local quadratic convergence to semi-simple eigenvalues. Convergence analyses of these methods
are given. Several numerical examples are presented which illustrate the behaviour and applications of our methods.
Received December 19, 1994 / Revised version received January 18, 1996 相似文献