共查询到20条相似文献,搜索用时 171 毫秒
1.
A REGULARIZED CONJUGATE GRADIENT METHOD FOR SYMMETRIC POSITIVE DEFINITE SYSTEM OF LINEAR EQUATIONS 总被引:3,自引:0,他引:3
Zhong-zhi Bai 《计算数学(英文版)》2002,(4)
AbstractA class of regularized conjugate gradient methods is presented for solving the large sparse system of linear equations of which the coefficient matrix is an ill-conditioned symmetric positive definite matrix. The convergence properties of these methods are discussed in depth, and the best possible choices of the parameters involved in the new methods are investigated in detail. Numerical computations show that the new methods are more efficient and robust than both classical relaxation methods and classical conjugate direction methods. 相似文献
2.
Zhong‐Zhi Bai 《Numerical Linear Algebra with Applications》2010,17(6):917-933
For the large sparse linear complementarity problems, by reformulating them as implicit fixed‐point equations based on splittings of the system matrices, we establish a class of modulus‐based matrix splitting iteration methods and prove their convergence when the system matrices are positive‐definite matrices and H+‐matrices. These results naturally present convergence conditions for the symmetric positive‐definite matrices and the M‐matrices. Numerical results show that the modulus‐based relaxation methods are superior to the projected relaxation methods as well as the modified modulus method in computing efficiency. Copyright © 2009 John Wiley & Sons, Ltd. 相似文献
3.
4.
E. F. Kaasschieter 《BIT Numerical Mathematics》1989,29(4):824-849
Discretizing a symmetric elliptic boundary value problem by a finite element method results in a system of linear equations with a symmetric positive definite coefficient matrix. This system can be solved iteratively by a preconditioned conjugate gradient method. In this paper a preconditioning matrix is proposed that can be constructed for all finite element methods if a mild condition for the node numbering is fulfilled. Such a numbering can be constructed using a variant of the reverse Cuthill-McKee algorithm. 相似文献
5.
Zhong-zhi Bai 《计算数学(英文版)》2001,19(6):651-672
1. IntroductionConsider the large sparse system of linear equationsAx = b, (1.1)where, for a fixed positive integer cr, A e L(R") is a symmetric positive definite (SPD) matrir,having the bloCked formx,b E R" are the uDknwn and the known vectors, respectively, having the correspondingblocked formsni(ni S n, i = 1, 2,', a) are a given positthe integers, satisfying Z ni = n. This systemi= 1of linear equations often arises in sultable finite element discretizations of many secondorderseifad… 相似文献
6.
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 相似文献
7.
Using the minimum function or the Fischer-Burmeister function, we obtain two reformulations of a semidefinite program as a nonlinear system of equations. Applying a Newton-type method to such a reformulation leads to a linear system of equations which has to be solved at each iteration. We discuss some properties of this linear system and show that the corresponding coefficient matrix is symmetric positive definite for the minimum function approach and positive definite but unsymmetric for the Fischer-Burmeister formulation. 相似文献
8.
Jun-Liang Dong 《Numerical Algorithms》2010,54(3):343-357
We present a shifted skew-symmetric iteration method for solving the nonsymmetric positive definite or positive semidefinite
linear complementarity problems. This method is based on the symmetric and skew-symmetric splitting of the system matrix,
which has been adopted to establish efficient splitting iteration methods for solving the nonsymmetric systems of linear equations.
Global convergence of the method is proved, and the corresponding inexact splitting iteration scheme is established and analyzed
in detail. Numerical results show that the new methods are feasible and effective for solving large sparse and nonsymmetric
linear complementarity problems. 相似文献
9.
一类特殊微分代数方程组的性质及应用顾金生,胡显承(清华大学应用数学系)THEPROPERTIESOFAKINDOFDIFFERENTIAL/ALGEBRAICEQUATIONSANDTHEIRAPPLICATIONS¥GuJin-sheng;HuXi... 相似文献
10.
本文针对求解大型稀疏非Hermitian正定线性方程组的HSS迭代方法,利用迭代法的松弛技术进行加速,提出了一种具有三个参数的超松弛HSS方法(SAHSS)和不精确的SAHSS方法(ISAHSS),它采用CG和一些Krylov子空间方法作为其内部过程,并研究了SAHSS和ISAHSS方法的收敛性.数值例子验证了新方法的有效性. 相似文献
11.
Liu Zhongyun 《高等学校计算数学学报(英文版)》2000,9(1):61-70
1 IntroductionLetAbeann×nsymmetricpositivedefinitematrix .WeconsidertheiterativesolutionofalargelinearsystemofequationsAx=bbytheparallelmultisplittingmethod .ThemultisplittingmethodwasintroducedbyO’LearyandWhite[9] andfurtherstudiedbymanyotherauthors .Butt… 相似文献
12.
In this paper, an algorithm based on a shifted inverse power iteration for computing generalized eigenvalues with corresponding eigenvectors of a large scale sparse symmetric positive definite matrix pencil is presented. It converges globally with a cubic asymptotic convergence rate, preserves sparsity of the original matrices and is fully parallelizable. The algebraic multilevel itera-tion method (AMLI) is used to improve the efficiency when symmetric positive definite linear equa-tions need to be solved. 相似文献
13.
Hermite正定对称矩阵迹的一些结果(英文) 总被引:1,自引:0,他引:1
本文研究了一类Hermite正定矩阵迹的不等式问题.利用文献[2-6]中的结果以及放缩法,获得了Hermite正定矩阵迹的极值定理、杨氏不等式和贝努利不等式,并且将许多初等不等式推广到Hermite正定矩阵迹的情形. 相似文献
14.
For large systems of linear equations, iterative methods provide attractive solution techniques. We describe the applicability
and convergence of iterative methods of Krylov subspace type for an important class of symmetric and indefinite matrix problems,
namely augmented (or KKT) systems. Specifically, we consider preconditioned minimum residual methods and discuss indefinite
versus positive definite preconditioning. For a natural choice of starting vector we prove that when the definite and indenfinite
preconditioners are related in the obvious way, MINRES (which is applicable in the case of positive definite preconditioning)
and full GMRES (which is applicable in the case of indefinite preconditioning) give residual vectors with identical Euclidean
norm at each iteration. Moreover, we show that the convergence of both methods is related to a system of normal equations
for which the LSQR algorithm can be employed. As a side result, we give a rare example of a non-trivial normal(1) matrix where
the corresponding inner product is explicitly known: a conjugate gradient method therefore exists and can be employed in this
case.
This work was supported by British Council/German Academic Exchange Service Research Collaboration Project 465 and NATO Collaborative
Research Grant CRG 960782 相似文献
15.
针对线性代数方程组Ax=b,利用矩阵分解的思想,构造一类特殊五对角与七对角对称正定阵的矩阵分解,获得这类矩阵反问题解存在的充要条件和通解表达式.最后,给出了具体算法与数值算例. 相似文献
16.
Csaba Mészáros 《Computational Optimization and Applications》2007,36(2-3):309-320
During the iterations of interior point methods symmetric indefinite systems are decomposed by LD̂L
T
factorization. This step can be performed in a special way where the symmetric indefinite system is transformed to a positive
definite one, called the normal equations system. This approach proved to be efficient in most of the cases and numerically
reliable, due to the positive definite property. It has been recognized, however, that in case the linear program contains
“dense” columns, this approach results in an undesirable fill–in during the computations and the direct factorization of the
symmetric indefinite system is more advantageous. The paper describes a new approach to detect cases where the system of normal
equations is not preferable for interior point methods and presents a new algorithm for detecting the set of columns which
is responsible for the excessive fill–in in the matrix AA
T
. By solving large–scale linear programming problems we demonstrate that our heuristic is reliable in practice.
This work was supported in part by the Hungarian Scientific Research Fund OTKA K60480. 相似文献
17.
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 相似文献
18.
The convergence of conjugate gradient methods for solving systems of linear equations with a symmetric positive definite matrix takes typically place in three phases, with a sublinear, linear and superlinear convergence rate, respectively. This behaviour can be explained using various generalized condition numbers which depend on all eigenvalues and on the initial error vector and using annihilating polynomials for the extreme eigenvalues. The analysis also indicates that it can be most efficient to use different preconditioners in different phases. 相似文献
19.
m个对角元有正增量的对称正定方程组的解 总被引:2,自引:0,他引:2
吴筑筑 《高等学校计算数学学报》2001,23(2):181-185
1 引 言某些问题的数值求解要作迭代计算 ,每次迭代需求解一个系数矩阵仅有少量变化的线性方程组 .如何减少求解该方程组的计算量 ,便成为提高总体计算效率的关键之一 .这类问题往往在一些优化问题的求解过程中遇到[1] ,因此值得研究 .为此考虑如下的问题Ⅰ .问题Ⅰ 设某问题的数值求解过程要作迭代计算 ,每次迭代需求解一个线性方程组(A+D)X =b ( 1 .1 )其中A为n阶对称正定矩阵 ,b为已知向量 ,D =diag(d1,d2 ,… ,dn) ,( 1 .2 )且D的对角元dik>0 ,k =1 ,2 ,… ,m ,1≤i1<i2 <… <im ≤n ,dik及其位置和… 相似文献
20.
Zhong-zhi Bai Jun-feng Yin Yang-feng Su 《计算数学(英文版)》2006,24(4):539-552
A shift splitting concept is introduced and, correspondingly, a shift-splitting iteration scheme and a shift-splitting preconditioner are presented, for solving the large sparse system of linear equations of which the coefficient matrix is an ill-conditioned non-Hermitian positive definite matrix. The convergence property of the shift-splitting iteration method and the eigenvalue distribution of the shift-splitting preconditioned matrix are discussed in depth, and the best possible choice of the shift is investigated in detail. Numerical computations show that the shift-splitting preconditioner can induce accurate, robust and effective preconditioned Krylov subspace iteration methods for solving the large sparse non-Hermitian positive definite systems of linear equations. 相似文献