Lothar Reichel

Silvia Noschese, Lothar Reichel

The numerical solution of linear discrete ill-posed problems typically requires regularization, i.e., replacement of the available ill-conditioned problem by a nearby better conditioned one. The most popular regularization methods for problems of small to moderate size are Tikhonov regularization and truncated singular value decomposition (TSVD). By considering matrix nearness problems related to Tikhonov regularization, several novel regularization methods are derived. These methods share properties with both Tikhonov regularization and TSVD, and can give approximate solutions of higher quality than either one of these methods.

Guangxin Huang, Silvia Noschese, Lothar Reichel

This paper is concerned with the solution of large-scale linear discrete ill-posed problems with error-contaminated data. Tikhonov regularization is a popular approach to determine meaningful approximate solutions of such problems. The choice of regularization matrix in Tikhonov regularization may significantly affect the quality of the computed approximate solution. This matrix should be chosen to promote the recovery of known important features of the desired solution, such as smoothness and monotonicity. We describe a novel approach to determine regularization matrices with desired properties by solving a matrix nearness problem. The constructed regularization matrix is the closest matrix in the Frobenius norm with a prescribed null space to a given matrix. Numerical examples illustrate the performance of the regularization matrices so obtained.

Silvia Gazzola, Silvia Noschese, Paolo Novati et al.

GMRES is one of the most popular iterative methods for the solution of large linear systems of equations that arise from the discretization of linear well-posed problems, such as Dirichlet boundary value problems for elliptic partial differential equations. The method is also applied to iteratively solve linear systems of equations that are obtained by discretizing linear ill-posed problems, such as many inverse problems. However, GMRES does not always perform well when applied to the latter kind of problems. This paper seeks to shed some light on reasons for the poor performance of GMRES in certain situations, and discusses some remedies based on specific kinds of preconditioning. The standard implementation of GMRES is based on the Arnoldi process, which also can be used to define a solution subspace for Tikhonov or TSVD regularization, giving rise to the Arnoldi-Tikhonov and Arnoldi-TSVD methods, respectively. The performance of the GMRES, the Arnoldi-Tikhonov, and the Arnoldi-TSVD methods is discussed. Numerical examples illustrate properties of these methods.

Ronny Ramlau, Lothar Reichel

Most of the literature on the solution of linear ill-posed operator equations, or their discretization, focuses only on the infinite-dimensional setting or only on the solution of the algebraic linear system of equations obtained by discretization. This paper discusses the influence of the discretization error on the computed solution. We consider the situation when the discretization used yields an algebraic linear system of equations with a large matrix. An approximate solution of this system is computed by first determining a reduced system of fairly small size by carrying out a few steps of the Arnoldi process. Tikhonov regularization is applied to the reduced problem and the regularization parameter is determined by the discrepancy principle. Errors incurred in each step of the solution process are discussed. Computed examples illustrate the error bounds derived.

Laura Dykes, Guangxin Huang, Silvia Noschese et al.

Many applications in science and engineering require the solution of large linear discrete ill-posed problems that are obtained by the discretization of a Fredholm integral equation of the first kind in several space-dimensions. The matrix that defines these problems is very ill-conditioned and generally numerically singular, and the right-hand side, which represents measured data, typically is contaminated by measurement error. Straightforward solution of these problems generally is not meaningful due to severe error propagation. Tikhonov regularization seeks to alleviate this difficulty by replacing the given linear discrete ill-posed problem by a penalized least-squares problem, whose solution is less sensitive to the error in the right-hand side and to round-off errors introduced during the computations. This paper discusses the construction of penalty terms that are determined by solving a matrix-nearness problem. These penalty terms allow partial transformation to standard form of Tikhonov regularization problems that stem from the discretization of integral equations on a cube in several space-dimensions.

Silvia Noschese, Lothar Reichel

Pseudospectra and structured pseudospectra are important tools for the analysis of matrices. Their computation, however, can be very demanding for all but small matrices. A new approach to compute approximations of pseudospectra and structured pseudospectra, based on determining the spectra of many suitably chosen rank-one or projected rank-one perturbations of the given matrix is proposed. The choice of rank-one or projected rank-one perturbations is inspired by Wilkinson's analysis of eigenvalue sensitivity. Numerical examples illustrate that the proposed approach gives much better insight into the pseudospectra and structured pseudospectra than random or structured random rank-one perturbations with lower computational burden. The latter approach is presently commonly used for the determination of structured pseudospectra.

Silvia Noschese, Lothar Reichel

In many applications it is important to understand the sensitivity of eigenvalues of a matrix polynomial to perturbations of the polynomial. The sensitivity commonly is described by condition numbers or pseudospectra. However, the computation of pseudospectra of matrix polynomials is very demanding computationally. This paper describes a new approach to computing approximations of pseudospectra of matrix polynomials by using rank-one or projected rank-one perturbations. These perturbations are inspired by Wilkinson's analysis of eigenvalue sensitivity. This approach allows the approximation of both structured and unstructured pseudospectra. Computed examples show the method to perform much better than a method based on random rank-one perturbations both for the approximation of structured and unstructured (i.e., standard) polynomial pseudospectra.

Silvia Noschese, Lothar Reichel

The sensitivity of eigenvalues of structured matrices under general or structured perturbations of the matrix entries has been thoroughly studied in the literature. Error bounds are available and the pseudospectrum can be computed to gain insight. Few investigations have focused on analyzing the sensitivity of eigenvectors under general or structured perturbations. The present paper discusses this sensitivity for tridiagonal Toeplitz and Toeplitz-type matrices.