Volume 58, pp. 348-377, 2023.

Range restricted iterative methods for linear discrete ill-posed problems

Alessandro Buccini, Lucas Onisk, and Lothar Reichel

Abstract

Linear systems of equations with a matrix whose singular values decay to zero with increasing index number, and without a significant gap, are commonly referred to as linear discrete ill-posed problems. Such systems arise, e.g., when discretizing a Fredholm integral equation of the first kind. The right-hand side vectors of linear discrete ill-posed problems that arise in science and engineering often represent an experimental measurement that is contaminated by measurement error. The solution to these problems typically is very sensitive to this error. Previous works have shown that error propagation into the computed solution may be reduced by using specially designed iterative methods that allow the user to select the subspace in which the approximate solution is computed. Since the dimension of this subspace often is quite small, its choice is important for the quality of the computed solution. This work describes algorithms for three iterative methods that modify the GMRES, block GMRES, and global GMRES methods for the solution of appropriate linear systems of equations. We contribute to the work already available on this topic by introducing two block variants for the solution of linear systems of equations with multiple right-hand side vectors. The dominant computational aspects are discussed, and software for each method is provided. Additionally, we illustrate the utility of these iterative subspace methods through numerical examples focusing on image reconstruction. This paper is accompanied by software.

Full Text (PDF) [2 MB], BibTeX

Key words

ill-posed problems, iterative method, Arnoldi process, block Arnoldi process, global Arnoldi process

AMS subject classifications

65F10, 65F22

Links to the cited ETNA articles

[14]Vol. 33 (2008-2009), pp. 207-220 L. Elbouyahyaoui, A. Messaoudi, and H. Sadok: Algebraic properties of the block GMRES and block Arnoldi methods
[16]Vol. 47 (2017), pp. 100-126 Andreas Frommer, Kathryn Lund, and Daniel B. Szyld: Block Krylov subspace methods for functions of matrices
[18]Vol. 31 (2008), pp. 204-220 Per Christian Hansen and Toke Koldborg Jensen: Noise propagation in regularizing iterations for image deblurring
[26]Vol. 20 (2005), pp. 119-138 K. Jbilou, H. Sadok, and A. Tinzefte: Oblique projection methods for linear systems with multiple right-hand sides
[27]Vol. 38 (2011), pp. 233-257 Stefan Kindermann: Convergence analysis of minimization-based noise level-free parameter choice rules for linear ill-posed problems
[28]Vol. 53 (2020), pp. 217-238 Stefan Kindermann and Kemal Raik: A simplified L-curve method as error estimator

Additional resources for this document

Additional files

< Back