共查询到20条相似文献,搜索用时 15 毫秒
1.
On the convergence of line iterative methods for cyclically
reduced non-symmetrizable linear systems
Summary. We derive analytic bounds on the convergence factors associated
with block relaxation methods for solving the discrete
two-dimensional convection-diffusion equation. The analysis
applies to the reduced systems derived when one step of block
Gaussian elimination is performed on red-black ordered
two-cyclic discretizations. We consider the case where centered
finite difference discretization is used and one cell Reynolds
number is less than one in absolute value and the other is
greater than one. It is shown that line ordered relaxation
exhibits very fast rates of convergence.
Received March 3, 1992/Revised version received July 2, 1993 相似文献
2.
Summary. We consider the convergence of Orthomin(k) on singular and inconsistent linear systems. Criteria for the breakdown of Orthomin(k) are discussed and analyzed. Moreover, necessary and sufficient conditions for the convergence of Orthomin(k) for any right hand side are given, and a rate of convergence is provided as well. Finally, numerical experiments are shown to confirm the convergence theorem. Received April 1, 1995 / Revised version received October 1, 1997 / Published online July 12, 2000 相似文献
3.
Summary.
Hybrid methods for the solution of systems of linear equations
consist of a first phase where some information about the associated
coefficient matrix is acquired, and a second phase in which a
polynomial iteration designed with respect to this information is
used. Most of the hybrid algorithms proposed recently for the
solution of nonsymmetric systems rely on the direct use of
eigenvalue estimates constructed by the Arnoldi process in Phase I.
We will show the limitations of this approach and propose an
alternative, also based on the Arnoldi process, which approximates
the field of values of the coefficient matrix and of its inverse in
the Krylov subspace. We also report on numerical experiments
comparing the resulting new method with other hybrid algorithms.
Received May 27, 1993 / Revised version received
November 14, 1994 相似文献
4.
Summary.
Large, sparse nonsymmetric systems of linear equations with a
matrix whose eigenvalues lie in the right half plane may be solved by an
iterative method based on Chebyshev polynomials for an interval in the
complex plane. Knowledge of the convex hull of the spectrum of the
matrix is required in order to choose parameters upon which the
iteration depends. Adaptive Chebyshev algorithms, in which these
parameters are determined by using eigenvalue estimates computed by the
power method or modifications thereof, have been described by Manteuffel
[18]. This paper presents an adaptive Chebyshev iterative method, in
which eigenvalue estimates are computed from modified moments determined
during the iterations. The computation of eigenvalue estimates from
modified moments requires less computer storage than when eigenvalue
estimates are computed by a power method and yields faster convergence
for many problems.
Received May 13, 1992/Revised version received May 13,
1993 相似文献
5.
Existence and uniqueness of splittings for stationary iterative methods with applications to alternating methods 总被引:3,自引:0,他引:3
Summary. Given a nonsingular matrix , and a matrix of the same order, under certain very mild conditions, there is a unique splitting , such that . Moreover, all properties of the splitting are derived directly from the iteration matrix . These results do not hold when the matrix is singular. In this case, given a matrix and a splitting such that , there are infinitely many other splittings corresponding to the same matrices and , and different splittings can have different properties. For instance, when is nonnegative, some of these splittings can be regular splittings, while others can be only weak splittings. Analogous results
hold in the symmetric positive semidefinite case. Given a singular matrix , not for all iteration matrices there is a splitting corresponding to them. Necessary and sufficient conditions for the existence of such splittings are
examined. As an illustration of the theory developed, the convergence of certain alternating iterations is analyzed. Different
cases where the matrix is monotone, singular, and positive (semi)definite are studied.
Received September 5, 1995 / Revised version received April 3, 1996 相似文献
6.
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 相似文献
7.
On convergence rates of inexact Newton regularizations 总被引:1,自引:0,他引:1
Andreas Rieder 《Numerische Mathematik》2001,88(2):347-365
Summary. REGINN is an algorithm of inexact Newton type for the regularization of nonlinear ill-posed problems [Inverse Problems 15 (1999), pp. 309–327]. In the present article convergence is shown under weak smoothness assumptions (source conditions). Moreover, convergence rates are established. Some computational illustrations support the theoretical results. Received March 12, 1999 / Published online October 16, 2000 相似文献
8.
Summary.
An adaptive Richardson iteration method is described for the solution of
large sparse symmetric positive definite linear systems of equations with
multiple right-hand side vectors. This scheme ``learns' about the linear
system to be solved by computing inner products of residual matrices during
the iterations. These inner products are interpreted as block modified moments.
A block version of the modified Chebyshev algorithm is presented which yields
a block tridiagonal matrix from the block modified moments and the recursion
coefficients of the residual polynomials. The eigenvalues of this block
tridiagonal matrix define an interval, which determines the choice of relaxation
parameters for Richardson iteration. Only minor modifications are necessary
in order to obtain a scheme for the solution of symmetric indefinite linear
systems with multiple right-hand side vectors. We outline the changes required.
Received April 22, 1993 相似文献
9.
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 相似文献
10.
Martin Hanke 《Numerische Mathematik》1997,77(4):487-499
Summary. This paper investigates the convergence of the Lanczos method for computing the smallest eigenpair of a selfadjoint elliptic
differential operator via inverse iteration (without shifts). Superlinear convergence rates are established, and their sharpness
is investigated for a simple model problem. These results are illustrated numerically for a more difficult problem.
Received March 8, 1996 相似文献
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.
Summary. In this work we present a novel class of semi-iterative methods for the Drazin-inverse solution of singular linear systems,
whether consistent or inconsistent. The matrices of these systems are allowed to have arbitrary index and arbitrary spectra
in the complex plane. The methods we develop are based on orthogonal polynomials and can all be implemented by 4-term recursion
relations independently of the index. We give all the computational details of the associated algorithms. We also give a complete
convergence analysis for all methods.
Received June 28, 2000 / Revised version received May 23, 2001 / Published online January 30, 2002 相似文献
13.
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 相似文献
14.
C.V. Pao 《Numerische Mathematik》1998,79(2):261-281
This paper is concerned with numerical methods for a finite difference system of reaction-diffusion-convection equation under
nonlinear boundary condition. Various monotone iterative methods are presented, and each of these methods leads to an existence-comparison
theorem as well as a computational algorithm for numerical solutions. The monotone property of the iterations gives improved
upper and lower bounds of the solution in each iteration, and the rate of convergence of the iterations is either quadratic
or nearly quadratic depending on the property of the nonlinear function. Application is given to a model problem from chemical
engineering, and some numerical results, including a test problem with known analytical solution, are presented to illustrate
the various rates of convergence of the iterations.
Received November 2, 1995 / Revised version received February 10, 1997 相似文献
15.
Summary. We propose an algorithm for the numerical solution of
large-scale symmetric positive-definite linear complementarity problems.
Each step of the algorithm combines an application of the successive
overrelaxation
method with projection (to determine an approximation of the optimal active
set) with the preconditioned conjugate gradient method (to solve the reduced
residual systems of linear equations). Convergence of the iterates to the
solution is proved. In the experimental part we compare the efficiency of the
algorithm with several other methods. As test example we consider the
obstacle problem with different obstacles.
For problems of dimension up to 24\,000 variables, the algorithm finds the
solution in less then 7 iterations, where each iteration
requires about 10
matrix-vector multiplications.
Received July 14, 1993 / Revised version received February 1994 相似文献
16.
Summary.
Discretisation of the classical Stokes problem gives rise
to symmetric indefinite matrices with eigenvalues which,
in a precise way, are not symmetric about the origin, but which
do depend on a mesh size parameter. Convergence
estimates for the Conjugate Residual or Minimum Residual
iterative solution of such systems are given by best
minimax polynomial approximations on an inclusion set for the
eigenvalues.
In this paper, an analytic convergence estimate for such
problems is given in terms of an asymptotically small
mesh size parameter.
Received
November 16, 1993 / Revised version received August 2,
1994 相似文献
17.
Asynchronous two-stage iterative methods 总被引:9,自引:0,他引:9
Summary.
Parallel block two-stage iterative methods
for the solution of linear systems of algebraic equations are studied.
Convergence is shown for monotone matrices and for -matrices.
Two different asynchronous versions of these methods
are considered and their convergence investigated.
Received September 7, 1993 / Revised version received April
21, 1994 相似文献
18.
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 相似文献
19.
C.V. Pao 《Numerische Mathematik》1995,72(2):239-262
Summary.
Two block monotone iterative schemes for a nonlinear
algebraic system, which is a finite difference approximation of a
nonlinear elliptic boundary-value problem, are presented and are
shown to converge monotonically either from above or from below to
a solution of the system. This monotone convergence result yields
a computational algorithm for numerical solutions as well as an
existence-comparison theorem of the system, including a sufficient
condition for the uniqueness of the solution. An advantage of the
block iterative schemes is that the Thomas algorithm can be used to
compute numerical solutions of the sequence of iterations in the
same fashion as for one-dimensional problems. The block iterative
schemes are compared with the point monotone iterative schemes of
Picard, Jacobi and Gauss-Seidel, and various theoretical comparison
results among these monotone iterative schemes are given. These
comparison results demonstrate that the sequence of iterations from
the block iterative schemes converges faster than the corresponding
sequence given by the point iterative schemes. Application of the
iterative schemes is given to a logistic model problem in ecology
and numerical ressults for a test problem with known analytical
solution are given.
Received
August 1, 1993 / Revised version received November 7, 1994 相似文献
20.
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 相似文献