共查询到20条相似文献,搜索用时 0 毫秒
1.
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 相似文献
2.
Ji-guang Sun 《Numerische Mathematik》1998,79(4):615-641
This paper, as a continuation of the paper [20] in Numerische Mathematik, studies the subspaces associated with the generalized singular value decomposition. Second order perturbation expansions,
Fréchet derivatives and condition numbers, and perturbation bounds for the subspaces are derived.
Received January 26, 1996 / Revised version received May 14, 1997 相似文献
3.
Hongyuan Zha 《Numerische Mathematik》1996,72(3):391-417
Summary.
We present a numerical algorithm for computing a few
extreme generalized
singular values and corresponding vectors of a sparse
or structured matrix
pair .
The algorithm is based on the CS decomposition and
the Lanczos
bidiagonalization process.
At each iteration step of the
Lanczos process, the solution to
a linear least squares problem with
as
the coefficient matrix is approximately computed, and
this consists the only interface
of the algorithm with
the matrix pair .
Numerical results are also
given to demonstrate
the feasibility and efficiency of the algorithm.
Received
April 1, 1994 / Revised version received December 15, 1994 相似文献
4.
G.W. Stewart 《Numerische Mathematik》1999,83(2):313-323
Summary. In this paper we propose four algorithms to compute truncated pivoted QR approximations to a sparse matrix. Three are based
on the Gram–Schmidt algorithm and the other on Householder triangularization. All four algorithms leave the original matrix
unchanged, and the only additional storage requirements are arrays to contain the factorization itself. Thus, the algorithms
are particularly suited to determining low-rank approximations to a sparse matrix.
Received February 23, 1998 / Revised version received April 16, 1998 相似文献
5.
J.M. Melenk 《Numerische Mathematik》1999,84(1):35-69
Summary. The paper presents results on the approximation of functions which solve an elliptic differential equation by operator adapted
systems of functions. Compared with standard polynomials, these operator adapted systems have superior local approximation
properties. First, the case of Laplace's equation and harmonic polynomials as operator adapted functions is analyzed and rates
of convergence in a Sobolev space setting are given for the approximation with harmonic polynomials. Special attention is
paid to the approximation of singular functions that arise typically in corners. These results for harmonic polynomials are
extended to general elliptic equations with analytic coefficients by means of the theory of Bergman and Vekua; the approximation
results for Laplace's equation hold true verbatim, if harmonic polynomials are replaced with generalized harmonic polynomials.
The Partition of Unity Method is used in a numerical example to construct an operator adapted spectral method for Laplace's
equation that is based on approximating with harmonic polynomials locally.
Received May 26, 1997 / Revised version received September 21, 1998 / Published online September 7, 1999 相似文献
6.
Summary. We construct in this paper an analogous method to Bairstow's one, for
trigonometric polynomials with real coefficients.
We also present some numerical examples which illustrate this method.
Received November 11, 1992/Revised version received May 13, 1993 相似文献
7.
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 相似文献
8.
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 相似文献
9.
A mean-field model for superconductivity is studied from both the analytical and computational points of view. In this model,
the individual vortex-like structures occuring in practical superconductors are not resolved. Rather, these structures are
homogenized and a vortex density is solved for. The particular model studied includes effects due to the pinning of vortices.
The existence and uniqueness of solutions of a regularized version of the model are demonstrated and the behavior of these
solutions as the regularization parameter tends to zero is examined. Then, semi-discrete and fully discrete finite element
based discretizations are formulated and analyzed and the results of some computational experiments are presented.
Received January 21, 1997 相似文献
10.
M. Kappert 《Numerische Mathematik》1996,74(4):397-417
Summary. Let denote the -th partial sum of the exponential function. Carpenter et al. (1991) [1] studied the exact rate of convergence of the zeros
of the normalized partial sums to the so-called Szeg?-curve Here we apply parts of the results found by Carpenter et al. to the zeros of the normalized partial sums of and .
Received August 11, 1995 相似文献
11.
Summary. The Schur complement of a model problem is considered as a preconditioner for the Uzawa type schemes for the generalized
Stokes problem (the Stokes problem with the additional term in the motion equation). The implementation of the preconditioned method requires for each iteration only one extra solution
of the Poisson equation with Neumann boundary conditions. For a wide class of 2D and 3D domains a theorem on its convergence
is proved. In particular, it is established that the method converges with a rate that is bounded by some constant independent
of . Some finite difference and finite element methods are discussed. Numerical results for finite difference MAC scheme are
provided.
Received May 2, 1997 / Revised version received May 10, 1999 / Published online May 8, 2000 相似文献
12.
Summary.
The Generalized Conjugate Gradient method (see [1]) is an
iterative method for nonsymmetric linear systems. We obtain
generalizations of this method for nonlinear systems with nonsymmetric
Jacobians. We prove global convergence results.
Received April 29, 1992 / Revised version received November 18, 1993 相似文献
13.
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 相似文献
14.
Summary. Let ( real) be a family of real by matrices. A value of is called a Hopf value if has a conjugate pair of purely imaginary eigenvalues , . We describe a technique for detecting Hopf values based on the evolution of the Schur complement of in a bordered extension of where varies along the positive imaginary axis of the complex plane. We compare the efficiency of this method with more obvious
methods such as the use of the QR algorithm and of the determinant function of as well as with recent work on the Cayley transform. In particular, we show the advantages of the Schur complement method
in the case of large sparse matrices arising in dynamical problems by discretizing boundary value problems. The Hopf values
of the Jacobian matrices are important in this setting because they are related to the Hopf bifurcation phenomenon where steady
state solutions bifurcate into periodic solutions.
Received September 15, 1994 / Revised version received July 7, 1995 相似文献
15.
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 相似文献
16.
Summary. Stabilized methods (also called Chebyshev methods) are explicit Runge-Kutta methods with extended stability domains along
the negative real axis. These methods are intended for large mildly stiff problems, originating mainly from parabolic PDEs.
The aim of this paper is to show that with the use of orthogonal polynomials, we can construct nearly optimal stability polynomials
of second order with a three-term recurrence relation. These polynomials can be used to construct a new numerical method,
which is implemented in a code called ROCK2. This new numerical method can be seen as a combination of van der Houwen-Sommeijer-type
methods and Lebedev-type methods.
Received January 14, 2000 / Revised version received November 3, 2000 / Published online May 4, 2001 相似文献
17.
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 相似文献
18.
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 相似文献
19.
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 相似文献
20.
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 相似文献