共查询到20条相似文献,搜索用时 15 毫秒
1.
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 相似文献
2.
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 相似文献
3.
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 相似文献
4.
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 相似文献
5.
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 相似文献
6.
Summary. We study the -stability and error estimates of general approximate solutions for the Cauchy problem associated with multidimensional Hamilton-Jacobi
(H-J) equations. For strictly convex Hamiltonians, we obtain a priori error estimates in terms of the truncation errors and the initial perturbation errors. We then demonstrate this general theory
for two types of approximations: approximate solutions constructed by the vanishing viscosity method, and by Godunov-type
finite difference methods. If we let denote the `small scale' of such approximations (– the viscosity amplitude , the spatial grad-size , etc.), then our -error estimates are of , and are sharper than the classical -results of order one half, . The main building blocks of our theory are the notions of the semi-concave stability condition and -measure of the truncation error. The whole theory could be viewed as a multidimensional extension of the -stability theory for one-dimensional nonlinear conservation laws developed by Tadmor et. al. [34,24,25]. In addition, we
construct new Godunov-type schemes for H-J equations which consist of an exact evolution operator and a global projection operator. Here, we restrict our attention to linear projection operators (first-order schemes). We note, however,
that our convergence theory applies equally well to nonlinear projections used in the context of modern high-resolution conservation laws. We prove semi-concave stability and obtain -bounds on their associated truncation errors; -convergence of order one then follows. Second-order (central) Godunov-type schemes are also constructed. Numerical experiments
are performed; errors and orders are calculated to confirm our -theory.
Received April 20, 1998 / Revised version received November 8, 1999 / Published online August 24, 2000 相似文献
7.
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 相似文献
8.
Summary.
We estimate condition numbers of -version matrices
for tensor
product elements with two choices of reference element degrees of
freedom. In
one case (Lagrange elements) the condition numbers grow
exponentially in ,
whereas in the other (hierarchical basis functions based on
Tchebycheff
polynomials) the condition numbers grow rapidly but only
algebraically in .
We conjecture that regardless of the choice of basis the
condition numbers
grow like or faster, where is the dimension
of the spatial domain.
Received
August 8, 1992 / Revised version received March 25, 1994 相似文献
9.
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 相似文献
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.
Yongzhong Song 《Numerische Mathematik》2002,92(3):563-591
Summary. This paper investigates the comparisons of asymptotic rates of convergence of two iteration matrices. On the basis of nonnegative
matrix theory, comparisons between two nonnegative splittings and between two parallel multisplitting methods are derived.
When the coefficient matrix A is Hermitian positive (semi)definite, comparison theorems about two P-regular splittings and
two parallel multisplitting methods are proved.
Received April 4, 1998 / Revised version received October 18, 1999 / Published online November 15, 2001 相似文献
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.
Qiang >Ye 《Numerische Mathematik》1995,70(4):507-514
Summary.
A symmetric tridiagonal matrix with a multiple eigenvalue must
have a zero
subdiagonal element and must be a direct sum of two
complementary blocks, both of which have the eigenvalue.
Yet it is well known that a small spectral gap
does not necessarily imply that some
is small, as
is demonstrated by the Wilkinson matrix.
In this note, it is shown that a pair of
close eigenvalues can only arise from two
complementary blocks on the diagonal,
in spite of the fact that the
coupling the
two blocks may not be small.
In particular, some explanatory bounds are derived and a
connection to
the Lanczos algorithm is observed. The nonsymmetric problem
is also included.
Received
April 8, 1992 / Revised version received September 21,
1994 相似文献
14.
Summary. We propose globally convergent
iteration schemes for updating the eigenvalues of a symmetric
matrix after a rank-1 modification. Such calculations are the
core of the divide-and-conquer technique for the symmetric
tridiagonal eigenvalue problem. We prove the superlinear
convergence right from the start of our schemes which allows us
to improve the complexity bounds of [3]. The effectiveness of
our algorithms is confirmed by numerical results which are
reported and discussed.
Received September 22, 1993 相似文献
15.
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 相似文献
16.
K. Veselić 《Numerische Mathematik》1999,83(4):699-702
Summary. We prove that the diagonally pivoted symmetric LR algorithm on a positive definite matrix is globally convergent.
Received December 23, 1997 / Revised version received August 3, 1998 / Published online August 19, 1999 相似文献
17.
Ji-guang Sun 《Numerische Mathematik》1999,82(2):339-349
Backward errors for the symmetric matrix inverse eigenvalue problem with respect to an approximate solution are defined,
and explicit expressions of the backward errors are derived. The expressions may be useful for testing the stability of practical
algorithms.
Received August 4, 1997 / Revised version received May 11, 1998 相似文献
18.
Yiannis G. Saridakis 《Numerische Mathematik》1996,74(2):203-219
Summary. Using the theory of nonnegative matrices and regular splittings, exact convergence and divergence domains of the Unsymmetric
Successive Overrelaxation (USSOR) method, as it pertains to the class of Generalized Consistently Ordered (GCO) matrices,
are determined. Our recently derived upper bounds, for the convergence of the USSOR method, re also used as effective tools.
Received October 17, 1993 / Revised version received December 19, 1994 相似文献
19.
Igor Moret 《Numerische Mathematik》1994,68(3):341-353
Summary. Certain types
of singular solutions of nonlinear parameter-dependent
operator equations were characterized by
Griewank and Reddien [5, 6] as regular solutions of
suitable augmented systems. For their numerical
approximation an approach based on the use of
Krylov subspaces is here presented. The application
to boundary value problems is illustrated by
numerical examples.
Received March 8, 1993 / Revised version received December 13,
1993 相似文献
20.
A numerically stable, structure preserving method for computing the eigenvalues of real Hamiltonian or symplectic pencils 总被引:3,自引:0,他引:3
A new method is presented for the numerical computation of the generalized eigenvalues of real Hamiltonian or symplectic
pencils and matrices. The method is numerically backward stable and preserves the structure (i.e., Hamiltonian or symplectic).
In the case of a Hamiltonian matrix the method is closely related to the square reduced method of Van Loan, but in contrast
to that method which may suffer from a loss of accuracy of order , where is the machine precision, the new method computes the eigenvalues to full possible accuracy.
Received April 8, 1996 / Revised version received December 20, 1996 相似文献