SOLVING ILL-POSED LINEAR SYSTEMS WITH GMRES AND A SINGULAR PRECONDITIONER

被引:19
作者
Elden, Lars [1 ]
Simoncini, Valeria [2 ]
机构
[1] Linkping Univ, Dept Math, SE-58183 Linkping, Sweden
[2] Univ Bologna, Dipartimento Matemat, I-40127 Bologna, Italy
关键词
ill-posed; linear system; GMRES; singular preconditioner; nearly singular; ITERATIVE REGULARIZATION; RESTORATION;
D O I
10.1137/110832793
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
Almost singular linear systems arise in discrete ill-posed problems. Either because of the intrinsic structure of the problem or because of preconditioning, the spectrum of the coefficient matrix is often characterized by a sizable gap between a large group of numerically zero eigenvalues and the rest of the spectrum. Correspondingly, the right-hand side has leading eigencomponents associated with the eigenvalues away from zero. In this paper the effect of this setting in the convergence of the generalized minimal residual (GMRES) method is considered. It is shown that in the initial phase of the iterative algorithm, the residual components corresponding to the large eigenvalues are reduced in norm, and these can be monitored without extra computation. The analysis is supported by numerical experiments. In particular, ill-posed Cauchy problems for partial differential equations with variable coefficients are considered, where the preconditioner is a fast, low-rank solver for the corresponding problem with constant coefficients.
引用
收藏
页码:1369 / 1394
页数:26
相关论文
共 42 条
[1]  
[Anonymous], 1965, The algebraic eigenvalue problem
[2]  
[Anonymous], 2003, ITERATIVE METHODS SP, DOI DOI 10.1137/1.9780898718003
[4]   Decomposition methods for large linear discrete ill-posed problems [J].
Baglama, James ;
Reichel, Lothar .
JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS, 2007, 198 (02) :332-343
[5]   Convergence of polynomial restart Krylov methods for eigenvalue computations [J].
Beattie, CA ;
Embree, M ;
Sorensen, DC .
SIAM REVIEW, 2005, 47 (03) :492-515
[6]  
Beck J.V., 1985, Inverse Heat Conduction: Ill-Posed Problems
[7]   A framework for studying the regularizing properties of Krylov subspace methods [J].
Brianzi, P ;
Favati, P ;
Menchi, O ;
Romani, F .
INVERSE PROBLEMS, 2006, 22 (03) :1007-1021
[8]   Improvement of space-invariant image deblurring by preconditioned landweber iterations [J].
Brianzi, Paola ;
Di Benedetto, Fabio ;
Estatico, Claudio .
SIAM JOURNAL ON SCIENTIFIC COMPUTING, 2008, 30 (03) :1430-1458
[9]   GMRES on (nearly) singular systems [J].
Brown, PN ;
Walker, HF .
SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS, 1997, 18 (01) :37-51
[10]   On the regularizing properties of the GMRES method [J].
Calvetti, D ;
Lewis, B ;
Reichel, L .
NUMERISCHE MATHEMATIK, 2002, 91 (04) :605-625