共查询到20条相似文献,搜索用时 46 毫秒
1.
In this paper, we consider large-scale linear discrete ill-posed problems where the right-hand side contains noise. Regularization techniques such as Tikhonov regularization are needed to control the effect of the noise on the solution. In many applications such as in image restoration the coefficient matrix is given as a Kronecker product of two matrices and then Tikhonov regularization problem leads to the generalized Sylvester matrix equation. For large-scale problems, we use the global-GMRES method which is an orthogonal projection method onto a matrix Krylov subspace. We present some theoretical results and give numerical tests in image restoration. 相似文献
2.
We discuss the application of an augmented conjugate gradient to the solution of a sequence of linear systems of the same
matrix appearing in an iterative process for the solution of scattering problems. The conjugate gradient method applied to
the first system generates a Krylov subspace, then for the following systems, a modified conjugate gradient is applied using
orthogonal projections on this subspace to compute an initial guess and modified descent directions leading to a better convergence.
The scattering problem is treated via an Exact Controllability formulation and a preconditioned conjugate gradient algorithm
is introduced. The set of linear systems to be solved are associated to this preconditioning. The efficiency of the method
is tested on different 3D acoustic problems.
This revised version was published online in August 2006 with corrections to the Cover Date. 相似文献
3.
The singular value decomposition is commonly used to solve linear discrete ill-posed problems of small to moderate size. This decomposition not only can be applied to determine an approximate solution but also provides insight into properties of the problem. However, large-scale problems generally are not solved with the aid of the singular value decomposition, because its computation is considered too expensive. This paper shows that a truncated singular value decomposition, made up of a few of the largest singular values and associated right and left singular vectors, of the matrix of a large-scale linear discrete ill-posed problems can be computed quite inexpensively by an implicitly restarted Golub–Kahan bidiagonalization method. Similarly, for large symmetric discrete ill-posed problems a truncated eigendecomposition can be computed inexpensively by an implicitly restarted symmetric Lanczos method. 相似文献
4.
Summary. We describe a new iterative method for the solution of large, very ill-conditioned linear systems of equations that arise
when discretizing linear ill-posed problems. The right-hand side vector represents the given data and is assumed to be contaminated
by measurement errors. Our method applies a filter function of the form with the purpose of reducing the influence of the errors in the right-hand side vector on the computed approximate solution
of the linear system. Here is a regularization parameter. The iterative method is derived by expanding in terms of Chebyshev polynomials. The method requires only little computer memory and is well suited for the solution of
large-scale problems. We also show how a value of and an associated approximate solution that satisfies the Morozov discrepancy principle can be computed efficiently. An application
to image restoration illustrates the performance of the method.
Received January 25, 1997 / Revised version received February 9, 1998 / Published online July 28, 1999 相似文献
5.
Huidong Yang Walter Zulehner 《Journal of Computational and Applied Mathematics》2011,235(18):5367-5379
Fluid-structure interaction problems arise in many fields of application such as flows around elastic structures and blood flow in arteries. The method presented in this paper for solving such a problem is based on a reduction to an equation at the interface, involving the so-called Steklov-Poincaré operators. This interface equation is solved by a Newton iteration, for which directional derivatives involving shape derivatives with respect to the interface perturbation have to be evaluated appropriately. One step of the Newton iteration requires the solution of several decoupled linear sub-problems in the structure and the fluid domains. These sub-problems are spatially discretized by a finite element method on hybrid meshes. For the time discretization, implicit first-order methods are used for both sub-problems. The discretized equations are solved by algebraic multigrid methods. 相似文献
6.
A new parallel algorithm for the solution of banded linear systems is proposed. The scheme tears the coefficient matrix into several overlapped independent blocks in which the size of the overlap is equal to the system’s bandwidth. A corresponding splitting of the right-hand side is also provided. The resulting independent, and smaller size, linear systems are solved under the constraint that the solutions corresponding to the overlap regions are identical. This results in a linear system whose size is proportional to the sum of the overlap regions which we refer to as the “balance” system. We propose a solution strategy that does not require obtaining this “balance” system explicitly. Once the balance system is solved, retrieving the rest of the solution can be realized with almost perfect parallelism. Our proposed algorithm is a hybrid scheme that combines direct and iterative methods for solving a single banded system of linear equations on parallel architectures. It has broad applications in finite-element analysis, particularly as a parallel solver of banded preconditioners that can be used in conjunction with outer Krylov iterative schemes. 相似文献
7.
On one approach to a posteriori error estimates for evolution problems solved by the method of lines 总被引:2,自引:0,他引:2
Summary. In this paper, we describe a new technique for a posteriori error estimates suitable to parabolic and hyperbolic equations
solved by the method of lines. One of our goals is to apply known estimates derived for elliptic problems to evolution equations.
We apply the new technique to three distinct problems: a general nonlinear parabolic problem with a strongly monotonic elliptic
operator, a linear nonstationary convection-diffusion problem, and a linear second order hyperbolic problem. The error is
measured with the aid of the -norm in the space-time cylinder combined with a special time-weighted energy norm. Theory as well as computational results
are presented.
Received September 2, 1999 / Revised version received March 6, 2000 / Published online March 20, 2001 相似文献
8.
Sparse approximate inverse preconditioning for dense linear systems arising in computational electromagnetics 总被引:2,自引:0,他引:2
We investigate the use of sparse approximate inverse preconditioners for the iterative solution of linear systems with dense
complex coefficient matrices arising in industrial electromagnetic problems. An approximate inverse is computed via a Frobenius
norm approach with a prescribed nonzero pattern. Some strategies for determining the nonzero pattern of an approximate inverse
are described. The results of numerical experiments suggest that sparse approximate inverse preconditioning is a viable approach
for the solution of large-scale dense linear systems on parallel computers.
This revised version was published online in August 2006 with corrections to the Cover Date. 相似文献
9.
Q. Ni 《计算数学(英文版)》1997,15(1):36-54
1.IntroductionInthispaperweconsiderthefollowingnonlinearprogrammingproblemminimizef(x)subjecttogj(x)2o,jEJ={1,...,m}.(1'1)Extensionstoproblemincludingalsoequalityconstraintswillbepossible.Thefunctionf:W-Rlandgj:Rn-R',jEJaretwicecontinuouslydifferentiable.Inpaxticular,weapplyQP-free(withoutquadraticprogrammingsubproblems),truncatedhybridmethodsforsolvingthelarge-scaJenonlinearprogrammingproblems,inwhichthenumberofvariablesandthenumberofconstraiotsin(1.1)aregreat.Wediscussthecase,wheresecon… 相似文献
10.
The approximation to the solution of large sparse symmetric linear problems arising from nonlinear systems of equations is
considered. We are focusing herein on reusing information from previous processes while solving a succession of linear problems
with a Conjugate Gradient algorithm. We present a new Rayleigh–Ritz preconditioner that is based on the Krylov subspaces and
superconvergence properties, and consists of a suitable reuse of a given set of Ritz vectors. The relevance and the mathematical
foundations of the current approach are detailed and the construction of the preconditioner is presented either for the unconstrained
or the constrained problems. A corresponding practical preconditioner for iterative domain decomposition methods applied to
nonlinear elasticity is addressed, and numerical validation is performed on a poorly-conditioned large-scale practical problem.
This revised version was published online in June 2006 with corrections to the Cover Date. 相似文献
11.
Sergey I. Solov’ëv 《Linear algebra and its applications》2006,415(1):210-229
This paper proposes new iterative methods for the efficient computation of the smallest eigenvalue of symmetric nonlinear matrix eigenvalue problems of large order with a monotone dependence on the spectral parameter. Monotone nonlinear eigenvalue problems for differential equations have important applications in mechanics and physics. The discretization of these eigenvalue problems leads to nonlinear eigenvalue problems with very large sparse ill-conditioned matrices monotonically depending on the spectral parameter. To compute the smallest eigenvalue of large-scale matrix nonlinear eigenvalue problems, we suggest preconditioned iterative methods: preconditioned simple iteration method, preconditioned steepest descent method, and preconditioned conjugate gradient method. These methods use only matrix-vector multiplications, preconditioner-vector multiplications, linear operations with vectors, and inner products of vectors. We investigate the convergence and derive grid-independent error estimates for these methods. Numerical experiments demonstrate the practical effectiveness of the proposed methods for a model problem. 相似文献
12.
Xiao-Chuan Cai 《Numerische Mathematik》1991,60(1):41-61
Summary In this paper, we consider the solution of linear systems of algebraic equations that arise from parabolic finite element problems. We introduce three additive Schwarz type domain decomposition methods for general, not necessarily selfadjoint, linear, second order, parabolic partial differential equations and also study the convergence rates of these algorithms. The resulting preconditioned linear system of equations is solved by the generalized minimal residual method. Numerical results are also reported.This work was supported in part by the National Science Foundation under Grant NSF-CCR-8903003 at the Courant Institute, New York University and in part by the National Science Foundation under contract number DCR-8521451 and ECS-8957475 at Yale University 相似文献
13.
Christoph Börgers 《Numerische Mathematik》1989,55(2):123-136
Summary We consider the Neumann-Dirichlet domain decomposition method for the solution of linear elliptic boundary value problems. We study the following question. Suppose that the auxiliary problems on the subdomains are not solved exactly, but only with a fixed, mesh size independent accuracy. Does the speed of convergence remain mesh size independently bounded? We show that the answer is no in general, but that mesh size independent convergence can be obtained if the accuracy requirement on the subsolvers becomes increasingly severe as the mesh size tends to zero. 相似文献
14.
S. H. Lui 《Numerische Mathematik》2002,93(1):109-129
Summary The Schwarz Alternating Method can be used to solve elliptic boundary value problems on domains which consist of two or more
overlapping subdomains. The solution is approximated by an infinite sequence of functions which results from solving a sequence
of elliptic boundary value problems in each subdomain.
In this paper, proofs of convergence of some Schwarz Alternating Methods for nonlinear elliptic problems which are known to
have solutions by the monotone method (also known as the method of subsolutions and supersolutions) are given. In particular,
an additive Schwarz method for scalar as well some coupled nonlinear PDEs are shown to converge to some solution on finitely
many subdomains, even when multiple solutions are possible. In the coupled system case, each subdomain PDE is linear, decoupled
and can be solved concurrently with other subdomain PDEs. These results are applicable to several models in population biology.
This work was in part supported by a grant from the RGC of HKSAR, China (HKUST6171/99P) 相似文献
15.
Sanna Mönkölä 《Journal of Computational and Applied Mathematics》2010,234(6):1904-1911
The classical way of solving the time-harmonic linear acousto-elastic wave problem is to discretize the equations with finite elements or finite differences. This approach leads to large-scale indefinite complex-valued linear systems. For these kinds of systems, it is difficult to construct efficient iterative solution methods. That is why we use an alternative approach and solve the time-harmonic problem by controlling the solution of the corresponding time dependent wave equation.In this paper, we use an unsymmetric formulation, where fluid-structure interaction is modeled as a coupling between pressure and displacement. The coupled problem is discretized in space domain with spectral elements and in time domain with central finite differences. After discretization, exact controllability problem is reformulated as a least-squares problem, which is solved by the conjugate gradient method. 相似文献
16.
Richard E. Ewing 《BIT Numerical Mathematics》1989,29(4):850-866
The simulation of large-scale fluid flow applications often requires the efficient solution of extremely large nonsymmetric linear and nonlinear sparse systems of equations arising from the discretization of systems of partial differential equations. While preconditioned conjugate gradient methods work well for symmetric, positive-definite matrices, other methods are necessary to treat large, nonsymmetric matrices. The applications may also involve highly localized phenomena which can be addressed via local and adaptive grid refinement techniques. These local refinement methods usually cause non-standard grid connections which destroy the bandedness of the matrices and the associated ease of solution and vectorization of the algorithms. The use of preconditioned conjugate gradient or conjugate-gradient-like iterative methods in large-scale reservoir simulation applications is briefly surveyed. Then, some block preconditioning methods for adaptive grid refinement via domain decomposition techniques are presented and compared. These techniques are being used efficiently in existing large-scale simulation codes. 相似文献
17.
A Scalable Parallel Interior Point Algorithm for Stochastic Linear Programming and Robust Optimization 总被引:1,自引:0,他引:1
We present a computationally efficient implementation of an interior point algorithm for solving large-scale problems arising in stochastic linear programming and robust optimization. A matrix factorization procedure is employed that exploits the structure of the constraint matrix, and it is implemented on parallel computers. The implementation is perfectly scalable. Extensive computational results are reported for a library of standard test problems from stochastic linear programming, and also for robust optimization formulations.The results show that the codes are efficient and stable for problems with thousands of scenarios. Test problems with 130 thousand scenarios, and a deterministic equivalent linear programming formulation with 2.6 million constraints and 18.2 million variables, are solved successfully. 相似文献
18.
The computation of solution paths of large-scale continuation problems can be quite challenging because a large amount of
computations have to be carried out in an interactive computing environment. The computations involve the solution of a sequence
of large nonlinear problems, the detection of turning points and bifurcation points, as well as branch switching at bifurcation
points. These tasks can be accomplished by computing the solution of a sequence of large linear systems of equations and by
determining a few eigenvalues close to the origin, and associated eigenvectors, of the matrices of these systems. We describe
an iterative method that simultaneously solves a linear system of equations and computes a few eigenpairs associated with
eigenvalues of small magnitude of the matrix. The computation of the eigenvectors has the effect of preconditioning the linear
system, and numerical examples show that the simultaneous computation of the solution and eigenpairs can be faster than only
computing the solution. Our iterative method is based on the block-Lanczos algorithm and is applicable to continuation problems
with symmetric Jacobian matrices.
This revised version was published online in June 2006 with corrections to the Cover Date. 相似文献
19.
Thoudam Roshan 《Journal of Computational and Applied Mathematics》2011,235(6):1641-1652
The generalized equal width (GEW) equation is solved numerically by the Petrov-Galerkin method using a linear hat function as the test function and a quadratic B-spline function as the trial function. Product approximation has been used in this method. A linear stability analysis of the scheme shows it to be conditionally stable. Test problems including the single soliton and the interaction of solitons are used to validate the suggested method, which is found to be accurate and efficient. Finally, the Maxwellian initial condition pulse is studied. 相似文献
20.
In this paper we study and compare some preconditioned conjugate gradient methods for solving large-scale higher-order finite element schemes approximating two- and three-dimensional linear elasticity boundary value problems. The preconditioners discussed in this paper are derived from hierarchical splitting of the finite element space first proposed by O. Axelsson and I. Gustafsson. We especially focus our attention to the implicit construction of preconditioning operators by means of some fixpoint iteration process including multigrid techniques. Many numerical experiments confirm the efficiency of these preconditioners in comparison with classical direct methods most frequently used in practice up to now. 相似文献