共查询到20条相似文献,搜索用时 578 毫秒
1.
We study the solutions of block Toeplitz systems A
mn
u = b by the multigrid method (MGM). Here the block Toeplitz matrices A
mn are generated by a nonnegative function f (x,y) with zeros. Since the matrices A
mn are ill-conditioned, the convergence factor of classical iterative methods will approach 1 as the size of the matrices becomes large. These classical methods, therefore, are not applicable for solving ill-conditioned systems. The MGM is then proposed in this paper. For a class of block Toeplitz matrices, we show that the convergence factor of the two-grid method (TGM) is uniformly bounded below 1 independent of mn and the full MGM has convergence factor depending only on the number of levels. The cost per iteration for the MGM is of O(mn log mn) operations. Numerical results are given to explain the convergence rate. 相似文献
2.
Maziar Salahi 《Applied mathematics and computation》2011,217(20):7985-7990
Least squares problems arise frequently in many disciplines such as image restorations. In these areas, for the given least squares problem, usually the coefficient matrix is ill-conditioned. Thus if the problem data are available with certain error, then after solving least squares problem with classical approaches we might end up with a meaningless solution. Tikhonov regularization, is one of the most widely used approaches to deal with such situations. In this paper, first we briefly describe these approaches, then the robust optimization framework which includes the errors in problem data is presented. Finally, our computational experiments on several ill-conditioned standard test problems using the regularization tools, a Matlab package for least squares problem, and the robust optimization framework, show that the latter approach may be the right choice. 相似文献
3.
用遗传算法求解病态线性方程组 总被引:15,自引:0,他引:15
众所周知 ,病态方程组的条件数较大 ,当输入数据有微小扰动或计算过程中的舍入误差都可能引起输出数据的很大扰动 ,使得解严重失真 ,因此求解此类方程组是相当困难的 .本文尝试使用遗传算法来求解病态线性方程组 ,得到了较好的结果 ,并与传统的求解方法作了简单的比较 相似文献
4.
In this study we present iterative regularization methods using rational approximations, in particular, Padé approximants, which work well for ill-posed problems. We prove that the (k, j)-Padé method is a convergent and order optimal iterative regularization method in using the discrepancy principle of Morozov. Furthermore, we present a hybrid Padé method, compare it with other well-known methods and found that it is faster than the Landweber method. It is worth mentioning that this study is a completion of the paper [A. Kirsche, C. Böckmann, Rational approximations for ill-conditioned equation systems, Appl. Math. Comput. 171 (2005) 385–397] where this method was treated to solve ill-conditioned equation systems. 相似文献
5.
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. 相似文献
6.
Claudio Estatico 《BIT Numerical Mathematics》2002,42(4):753-778
Popular preconditioners for conjugate gradient methods often reveal poor regularization properties that make them useless for very ill-conditioned linear systems arising in inverse problems. Recent results have awakened the interest towards the Tyrtyshnikov superoptimal preconditioners since it has been demonstrated that they exhibit good filtering capabilities. Here, in order to improve the regularizing behaviour, we generalize the definition of superoptimal preconditioner. Later on, by means of this more general definition, we develop a particular family of preconditioners for Toeplitz highly ill-conditioned linear systems. 相似文献
7.
对阻尼牛顿算法作了适当的改进,证明了新算法的收敛性.基于新算法,运用计算机代数系统Matlab,研究了迭代次数k,参数对(μ,λ)与初值x0三者间的依赖关系,研究了病态问题在新算法下趋于稳定的渐变(瞬变)过程.数值结果表明:(1)阻尼牛顿迭代中,参数对(μ,λ)与迭代次数k间存在特有的非线性关系;(2)适当的参数对(μ,λ)与阻尼因子α的共同作用能够在迭代中大幅度地降低病态问题的Jacobi阵的条件数,使病态问题逐渐趋于稳定,从而改变原问题的收敛性与收敛速度. 相似文献
8.
Sparse covariance selection problems can be formulated as log-determinant (log-det) semidefinite programming (SDP) problems with large numbers of linear constraints. Standard primal–dual interior-point methods that are based on solving the Schur complement equation would encounter severe computational bottlenecks if they are applied to solve these SDPs. In this paper, we consider a customized inexact primal–dual path-following interior-point algorithm for solving large scale log-det SDP problems arising from sparse covariance selection problems. Our inexact algorithm solves the large and ill-conditioned linear system of equations in each iteration by a preconditioned iterative solver. By exploiting the structures in sparse covariance selection problems, we are able to design highly effective preconditioners to efficiently solve the large and ill-conditioned linear systems. Numerical experiments on both synthetic and real covariance selection problems show that our algorithm is highly efficient and outperforms other existing algorithms. 相似文献
9.
Fadi Awawdeh 《Numerical Algorithms》2010,54(3):395-409
Solving systems of nonlinear equations is a relatively complicated problem for which a number of different approaches have
been proposed. In this paper, we employ the Homotopy Analysis Method (HAM) to derive a family of iterative methods for solving
systems of nonlinear algebraic equations. Our approach yields second and third order iterative methods which are more efficient
than their classical counterparts such as Newton’s, Chebychev’s and Halley’s methods. 相似文献
10.
L. F. Yukhno 《Computational Mathematics and Mathematical Physics》2007,47(12):1893-1901
The use of modifications of certain well-known methods of the conjugate direction type for solving systems of linear algebraic equations with rectangular matrices is examined. The modified methods are shown to be superior to the original versions with respect to the round-off accumulation; the advantage is especially large for ill-conditioned matrices. Examples are given of the efficient use of the modified methods for solving certain fairly large ill-conditioned problems. 相似文献
11.
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 相似文献
12.
病态方程组的条件数较大,当输入数据有微小扰动或计算过程中的舍入误差都可能引起输出数据的很大扰动,使得解严重失真,因此求解此类方程组是相当困难的.本文尝试使用模拟退火算法来求解病态线性方程组,得到了较好的结果,并与传统的求解方法作了简单的比较. 相似文献
13.
In this paper, we discuss several (old and new) estimates for the norm of the error in the solution of systems of linear equations, and we study their properties. Then, these estimates are used for approximating the optimal value of the regularization parameter in Tikhonov’s method for ill-conditioned systems. They are also used as a stopping criterion in iterative methods, such as the conjugate gradient algorithm, which have a regularizing effect. Several numerical experiments and comparisons with other procedures show the effectiveness of our estimates. 相似文献
14.
In this paper we discuss multigrid methods for ill-conditioned symmetric positive definite block Toeplitz matrices. Our block
Toeplitz systems are general in the sense that the individual blocks are not necessarily Toeplitz, but we restrict our attention
to blocks of small size. We investigate how transfer operators for prolongation and restriction have to be chosen such that
our multigrid algorithms converge quickly. We point out why these transfer operators can be understood as block matrices as
well and how they relate to the zeroes of the generating matrix function. We explain how our new algorithms can also be combined
efficiently with the use of a natural coarse grid operator. We clearly identify a class of ill-conditioned block Toeplitz
matrices for which our algorithmic ideas are suitable. In the final section we present an outlook to well-conditioned block
Toeplitz systems and to problems of vector Laplace type. In the latter case the small size blocks can be interpreted as degrees
of freedom associated with a node. A large number of numerical experiments throughout the article confirms convincingly that
our multigrid solvers lead to optimal order convergence.
AMS subject classification (2000) 65N55, 65F10 相似文献
15.
Summary The solution of systems of linear equations with Hankel coefficient matrices can be computed with onlyO(n
2) arithmetic operations, as compared toO(n
3) operations for the general cases. However, the classical Hankel solvers require the nonsingularity of all leading principal submatrices of the Hankel matrix. The known extensions of these algorithms to general Hankel systems can handle only exactly singular submatrices, but not ill-conditioned ones, and hence they are numerically unstable. In this paper, a stable procedure for solving general nonsingular Hankel systems is presented, using a look-ahead technique to skip over singular or ill-conditioned submatrices. The proposed approach is based on a look-ahead variant of the nonsymmetric Lanczos process that was recently developed by Freund, Gutknecht, and Nachtigal. We first derive a somewhat more general formulation of this look-ahead Lanczos algorithm in terms of formally orthogonal polynomials, which then yields the look-ahead Hankel solver as a special case. We prove some general properties of the resulting look-ahead algorithm for formally orthogonal polynomials. These results are then utilized in the implementation of the Hankel solver. We report some numerical experiments for Hankel systems with ill-conditioned submatrices.The research of the first author was supported by DARPA via Cooperative Agreement NCC 2-387 between NASA and the Universities Space Research Association (USRA).The research of the second author was supported in part by NSF grant DRC-8412314 and Cooperative Agreement NCC 2-387 between NASA and the Universities Space Research Association (USRA). 相似文献
16.
Triangular systems play a fundamental role in matrix computations. It has become commonplace that triangular systems are solved to be more accurate even if they are ill-conditioned. In this paper, we define structured condition number and give structured (forward) perturbation bound. In addition, we derive the representation of optimal structured backward perturbation bound. 相似文献
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.
L. F. Yukhno 《Computational Mathematics and Mathematical Physics》2007,47(11):1737-1744
A modification of certain well-known methods of the conjugate direction type is proposed and examined. The modified methods are more stable with respect to the accumulation of round-off errors. Moreover, these methods are applicable for solving ill-conditioned systems of linear algebraic equations that, in particular, arise as approximations of ill-posed problems. Numerical results illustrating the advantages of the proposed modification are presented. 相似文献
19.
In this paper, we propose a nested simple incomplete LU decomposition (NSILU) method for preconditioning iterative methods for solving largely scale and sparse ill-conditioned hnear systems. NSILU consists of some numerical techniques such as simple modification of Schur complement, compression of ill-condition structure by permutation, nested simple ILU, and inner-outer iteration. We give detailed error analysis of NSILU and estimations of condition number of the preconditioned coefficient matrix, together with numerical comparisons. We also show an analysis of inner accuracy strategies for the inner-outer iteration approach. Our new approach NSILU is very efficient for linear systems from a kind of two-dimensional nonlinear energy equations with three different temperature variables, where most of the calculations centered around solving large number of discretized and illconditioned linear systems in large scale. Many numerical experiments are given and compared in costs of flops, CPU times, and storages to show the efficiency and effectiveness of the NSILU preconditioning method. Numerical examples include middle-scale real matrices of size n = 3180 or n = 6360, a real apphcation of solving about 755418 linear systems of size n = 6360, and a simulation of order n=814080 with structures and properties similar as the real ones. 相似文献
20.
L. Lukšan 《Journal of Optimization Theory and Applications》1996,89(3):575-595
Hybrid methods are developed for improving the Gauss-Newton method in the case of large residual or ill-conditioned nonlinear least-square problems. These methods are used usually in a form suitable for dense problems. But some standard approaches are unsuitable, and some new possibilities appear in the sparse case. We propose efficient hybrid methods for various representations of the sparse problems. After describing the basic ideas that help deriving new hybrid methods, we are concerned with designing hybrid methods for sparse Jacobian and sparse Hessian representations of the least-square problems. The efficiency of hybrid methods is demonstrated by extensive numerical experiments.This work was supported by the Czech Republic Grant Agency, Grant 201/93/0129. The author is indebted to Jan Vlek for his comments on the first draft of this paper and to anonymous referees for many useful remarks. 相似文献