共查询到20条相似文献,搜索用时 31 毫秒
1.
For the discrete linear systems resulted from the discretization of the one‐dimensional anisotropic spatial fractional diffusion equations of variable coefficients with the shifted finite‐difference formulas of the Grünwald–Letnikov type, we propose a class of respectively scaled Hermitian and skew‐Hermitian splitting iteration method and establish its asymptotic convergence theory. The corresponding induced matrix splitting preconditioner, through further replacements of the involved Toeplitz matrices with certain circulant matrices, leads to an economic variant that can be executed by fast Fourier transforms. Both theoretical analysis and numerical implementations show that this fast respectively scaled Hermitian and skew‐Hermitian splitting preconditioner can significantly improve the computational efficiency of the Krylov subspace iteration methods employed as effective linear solvers for the target discrete linear systems. 相似文献
2.
Diagonal and Toeplitz splitting iteration methods for diagonal‐plus‐Toeplitz linear systems from spatial fractional diffusion equations
下载免费PDF全文
![点击此处可从《Numerical Linear Algebra with Applications》网站下载免费的PDF全文](/ch/ext_images/free.gif)
The finite difference discretization of the spatial fractional diffusion equations gives discretized linear systems whose coefficient matrices have a diagonal‐plus‐Toeplitz structure. For solving these diagonal‐plus‐Toeplitz linear systems, we construct a class of diagonal and Toeplitz splitting iteration methods and establish its unconditional convergence theory. In particular, we derive a sharp upper bound about its asymptotic convergence rate and deduct the optimal value of its iteration parameter. The diagonal and Toeplitz splitting iteration method naturally leads to a diagonal and circulant splitting preconditioner. Analysis shows that the eigenvalues of the corresponding preconditioned matrix are clustered around 1, especially when the discretization step‐size h is small. Numerical results exhibit that the diagonal and circulant splitting preconditioner can significantly improve the convergence properties of GMRES and BiCGSTAB, and these preconditioned Krylov subspace iteration methods outperform the conjugate gradient method preconditioned by the approximate inverse circulant‐plus‐diagonal preconditioner proposed recently by Ng and Pan (M.K. Ng and J.‐Y. Pan, SIAM J. Sci. Comput. 2010;32:1442‐1464). Moreover, unlike this preconditioned conjugate gradient method, the preconditioned GMRES and BiCGSTAB methods show h‐independent convergence behavior even for the spatial fractional diffusion equations of discontinuous or big‐jump coefficients. 相似文献
3.
A. Melman. 《Mathematics of Computation》2001,70(234):649-669
We exploit the even and odd spectrum of real symmetric Toeplitz matrices for the computation of their extreme eigenvalues, which are obtained as the solutions of spectral, or secular, equations. We also present a concise convergence analysis for a method to solve these spectral equations, along with an efficient stopping rule, an error analysis, and extensive numerical results.
4.
Li‐Ying Sun 《Numerical Linear Algebra with Applications》2006,13(10):869-876
In this paper, first we present a convergence theorem of the improved modified Gauss–Seidel iterative method, referred to as the IMGS method, for H‐matrices and compare the range of parameters αi with that of the parameter ω of the SOR iterative method. Then with a more general splitting, the convergence analysis of this method for an H‐matrix and its comparison matrix is given. The spectral radii of them are also compared. Copyright © 2006 John Wiley & Sons, Ltd. 相似文献
5.
C. Estatico 《Numerical Linear Algebra with Applications》2009,16(3):237-257
Both theoretical analysis and numerical experiments in the literature have shown that the Tyrtyshnikov circulant superoptimal preconditioner for Toeplitz systems can speed up the convergence of iterative methods without amplifying the noise of the data. Here we study a family of Tyrtyshnikov‐based preconditioners for discrete ill‐posed Toeplitz systems with differentiable generating functions. In particular, we show that the distribution of the eigenvalues of these preconditioners has good regularization features, since the smallest eigenvalues stay well separated from zero. Some numerical results confirm the regularization effectiveness of this family of preconditioners. Copyright © 2009 John Wiley & Sons, Ltd. 相似文献
6.
7.
In this paper we analyze convergence of basic iterative Jacobi and Gauss–Seidel type methods for solving linear systems which result from finite element or finite volume discretization of convection–diffusion equations on unstructured meshes. In general the resulting stiffness matrices are neither M‐matrices nor satisfy a diagonal dominance criterion. We introduce two newmatrix classes and analyse the convergence of the Jacobi and Gauss–Seidel methods for matrices from these classes. A new convergence result for the Jacobi method is proved and negative results for the Gauss–Seidel method are obtained. For a few well‐known discretization methods it is shown that the resulting stiffness matrices fall into the new matrix classes. Copyright © 1999 John Wiley & Sons, Ltd. 相似文献
8.
We consider a generalized Stokes equation with problem parameters ξ?0 (size of the reaction term) and ν>0 (size of the diffusion term). We apply a standard finite element method for discretization. The main topic of the paper is a study of efficient iterative solvers for the resulting discrete saddle point problem. We investigate a coupled multigrid method with Braess–Sarazin and Vanka‐type smoothers, a preconditioned MINRES method and an inexact Uzawa method. We present a comparative study of these methods. An important issue is the dependence of the rate of convergence of these methods on the mesh size parameter and on the problem parameters ξ and ν. We give an overview of the main theoretical convergence results known for these methods. For a three‐dimensional problem, discretized by the Hood–Taylor ??2–??1 pair, we give results of numerical experiments. Copyright © 2007 John Wiley & Sons, Ltd. 相似文献
9.
We consider Anderson extrapolation to accelerate the (stationary) Richardson iterative method for sparse linear systems. Using an Anderson mixing at periodic intervals, we assess how this benefits convergence to a prescribed accuracy. The method, named alternating Anderson–Richardson, has appealing properties for high‐performance computing, such as the potential to reduce communication and storage in comparison to more conventional linear solvers. We establish sufficient conditions for convergence, and we evaluate the performance of this technique in combination with various preconditioners through numerical examples. Furthermore, we propose an augmented version of this technique. 相似文献
10.
11.
Ryma Imene
Rahla Stefano Serra‐Capizzano Cristina Tablino‐Possio 《Numerical Linear Algebra with Applications》2020,27(4)
In the present article, we consider a class of elliptic partial differential equations with Dirichlet boundary conditions and where the operator is div(?a( x )?·), with a continuous and positive over , Ω being an open and bounded subset of , d≥1. For the numerical approximation, we consider the classical Finite Elements, in the case of Friedrichs–Keller triangulations, leading, as usual, to sequences of matrices of increasing size. The new results concern the spectral analysis of the resulting matrix‐sequences in the direction of the global distribution in the Weyl sense, with a concise overview on localization, clustering, extremal eigenvalues, and asymptotic conditioning. We study in detail the case of constant coefficients on Ω=(0,1)2 and we give a brief account in the more involved case of variable coefficients and more general domains. Tools are drawn from the Toeplitz technology and from the rather new theory of Generalized Locally Toeplitz sequences. Numerical results are shown for a practical evidence of the theoretical findings. 相似文献
12.
An efficient algebraic multigrid method for quadratic discretizations of linear elasticity problems on some typical anisotropic meshes in three dimensions
下载免费PDF全文
![点击此处可从《Numerical Linear Algebra with Applications》网站下载免费的PDF全文](/ch/ext_images/free.gif)
The quality of the mesh used in the finite element discretizations will affect the efficiency of solving the discreted linear systems. The usual algebraic solvers except multigrid method do not consider the effect of the grid geometry and the mesh quality on their convergence rates. In this paper, we consider the hierarchical quadratic discretizations of three‐dimensional linear elasticity problems on some anisotropic hexahedral meshes and present a new two‐level method, which is weakly independent of the size of the resulting problems by using a special local block Gauss–Seidel smoother, that is LBGS_v iteration when used for vertex nodes or LBGS_m iteration for midside nodes. Moreover, we obtain the efficient algebraic multigrid (AMG) methods by applying DAMG (AMG based on distance matrix) or DAMG‐PCG (PCG with DAMG as a preconditioner) to the solution of the coarse level equation. The resulting AMG methods are then applied to a practical example as a long beam. The numerical results verify the efficiency and robustness of the proposed AMG algorithms. Copyright © 2015 John Wiley & Sons, Ltd. 相似文献
13.
The Least‐Squares Finite Element Method (LSFEM) is an interesting alternative to the standard variational principles, which are used to solve partial differential equations. Advantages of the LSFEM are its robustness and the resulting symmetric positive definite matrices, which allow the use of robust iterative solvers like the CG method. In this paper we consider the application of the LSFEM for Fluid‐Structure Interaction (FSI) problems. Our model uses the LSFEM for the discretisation of the instationary incompressible Navier‐Stokes equations, which is coupled with a standard Galerkin FEM model for a linear elastic structure. The results for a simple model problem agree well with results obtained by other authors with different numerical schemes. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim) 相似文献
14.
In this paper, we consider inexact Newton and Newton-like methods andprovide new convergence conditions relating the forcing terms to theconditioning of the iteration matrices. These results can be exploited wheninexact methods with iterative linear solvers are used. In this framework,preconditioning techniques can be used to improve the performance ofiterative linear solvers and to avoid the need of excessively small forcingterms. Numerical experiments validating the theoretical results arediscussed. 相似文献
15.
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 相似文献
16.
The efficiency of finite element based simulations of Helmholtz problems is primarily affected by two facts. First, the numerical solution suffers from the so-called pollution effect, which leads to very high element resolutions at higher frequencies. Furthermore, the spectral properties of the resulting system matrices, and hence the convergence of iterative solvers, deteriorate with increasing wave numbers. In this contribution the influence of different types of polynomial basis functions on the efficiency and stability of interior as well as exterior acoustic simulations is analyzed. The current investigations show that a proper choice for the polynomial shape approximation may significantly increase the performance of Krylov subspace methods. In particular, the efficiency of higher order finite and infinite elements based on Bernstein polynomial shape approximation and the corresponding iterative solution strategies is assessed for practically relevant numerical examples including the sound radiation from rolling vehicle tires. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) 相似文献
17.
In this paper, we propose an efficient numerical scheme for solving some large‐scale ill‐posed linear inverse problems arising from image restoration. In order to accelerate the computation, two different hidden structures are exploited. First, the coefficient matrix is approximated as the sum of a small number of Kronecker products. This procedure not only introduces one more level of parallelism into the computation but also enables the usage of computationally intensive matrix–matrix multiplications in the subsequent optimization procedure. We then derive the corresponding Tikhonov regularized minimization model and extend the fast iterative shrinkage‐thresholding algorithm (FISTA) to solve the resulting optimization problem. Because the matrices appearing in the Kronecker product approximation are all structured matrices (Toeplitz, Hankel, etc.), we can further exploit their fast matrix–vector multiplication algorithms at each iteration. The proposed algorithm is thus called structured FISTA (sFISTA). In particular, we show that the approximation error introduced by sFISTA is well under control and sFISTA can reach the same image restoration accuracy level as FISTA. Finally, both the theoretical complexity analysis and some numerical results are provided to demonstrate the efficiency of sFISTA. 相似文献
18.
C. Albuquerque G.‐H. Cottet 《Numerical Methods for Partial Differential Equations》2004,20(2):199-229
This article is devoted to the numerical analysis of two classes of iterative methods that combine integral formulas with finite‐difference Poisson solvers for the solution of elliptic problems. The first method is in the spirit of the Schwarz domain decomposition method for exterior domains. The second one is motivated by potential calculations in free boundary problems and can be viewed as a numerical analytic continuation algorithm. Numerical tests are presented that confirm the convergence properties predicted by numerical analysis. © 2003 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 20: 199–229, 2004 相似文献
19.
We consider preconditioned subspace iterations for the numerical solution of discretized elliptic eigenvalue problems. For these iterative solvers, the convergence theory is still an incomplete puzzle. We generalize some results from the classical convergence theory of inverse subspace iterations, as given by Parlett, and some recent results on the convergence of preconditioned vector iterations. To this end, we use a geometric cone representation and prove some new trigonometric inequalities for subspace angles and canonical angles. (© 2010 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim) 相似文献
20.
Zhong‐Zhi Bai Raymond H. Chan Zhi‐Ru Ren 《Numerical Linear Algebra with Applications》2014,21(1):108-135
By introducing a variable substitution, we transform the two‐point boundary value problem of a third‐order ordinary differential equation into a system of two second‐order ordinary differential equations (ODEs). We discretize this order‐reduced system of ODEs by both sinc‐collocation and sinc‐Galerkin methods, and average these two discretized linear systems to obtain the target system of linear equations. We prove that the discrete solution resulting from the linear system converges exponentially to the true solution of the order‐reduced system of ODEs. The coefficient matrix of the linear system is of block two‐by‐two structure, and each of its blocks is a combination of Toeplitz and diagonal matrices. Because of its algebraic properties and matrix structures, the linear system can be effectively solved by Krylov subspace iteration methods such as GMRES preconditioned by block‐diagonal matrices. We demonstrate that the eigenvalues of certain approximation to the preconditioned matrix are uniformly bounded within a rectangle on the complex plane independent of the size of the discretized linear system, and we use numerical examples to illustrate the feasibility and effectiveness of this new approach. Copyright © 2013 John Wiley & Sons, Ltd. 相似文献