Inverse subspace problems with applications

Given a square matrix A, the inverse subspace problem is concerned with determining a closest matrix to A with a prescribed invariant subspace. When A is Hermitian, the closest matrix may be required to be Hermitian. We measure distance in the Frobenius norm and discuss applications to Krylov subspace methods for the solution of large‐scale linear systems of equations and eigenvalue problems as well as to the construction of blurring matrices. Extensions that allow the matrix A to be rectangular and applications to Lanczos bidiagonalization, as well as to the recently proposed subspace‐restricted SVD method for the solution of linear discrete ill‐posed problems, also are considered.Copyright © 2013 John Wiley & Sons, Ltd.     

Convergence estimates of nonrestarted and restarted block‐Lanczos methods

The block‐Lanczos method serves to compute a moderate number of eigenvalues and the corresponding invariant subspace of a symmetric matrix. In this paper, the convergence behavior of nonrestarted and restarted versions of the block‐Lanczos method is analyzed. For the nonrestarted version, we improve an estimate by Saad by means of a change of the auxiliary vector so that the new estimate is much more accurate in the case of clustered or multiple eigenvalues. For the restarted version, an estimate by Knyazev is generalized by extending our previous results on block steepest descent iterations and single‐vector restarted Krylov subspace iterations. The new estimates can also be reformulated and applied to invert‐block‐Lanczos methods for solving generalized matrix eigenvalue problems.     

On the computation of a truncated SVD of a large linear discrete ill-posed problem

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.     

Preconditioning CGNE iteration for inverse problems

The conjugate gradient method applied to the normal equations (CGNE ) is known as efficient method for the solution of non‐symmetric linear equations. By stopping the iteration according to a discrepancy principle, CGNE can be turned into a regularization method, and thus can be applied to the solution of inverse, in particular, ill‐posed problems. We show that CGNE for inverse problems can be further accelerated by preconditioning in Hilbert scales, derive (optimal) convergence rates with respect to data noise, and give tight bounds on the iteration numbers. The theoretical results are illustrated by numerical tests. Copyright © 2007 John Wiley & Sons, Ltd.     

On sinc discretization and banded preconditioning for linear third‐order ordinary differential equations

Some draining or coating fluid‐flow problems and problems concerning the flow of thin films of viscous fluid with a free surface can be described by third‐order ordinary differential equations (ODEs). In this paper, we solve the boundary value problems of such equations by sinc discretization and prove that the discrete solutions converge to the true solutions of the ODEs exponentially. The discrete solution is determined by a linear system with the coefficient matrix being a combination of Toeplitz and diagonal matrices. The system can be effectively solved by Krylov subspace iteration methods, such as GMRES, preconditioned by banded matrices. We demonstrate that the eigenvalues of the preconditioned matrix are uniformly bounded within a rectangle on the complex plane independent of the size of the linear system. Numerical examples are given to illustrate the effective performance of our method. Copyright © 2010 John Wiley & Sons, Ltd.     

A subspace shift technique for nonsymmetric algebraic Riccati equations associated with an M‐matrix

The worst situation in computing the minimal nonnegative solution of a nonsymmetric algebraic Riccati equation associated with an M‐matrix occurs when the corresponding linearizing matrix has two very small eigenvalues, one with positive and one with negative real part. When both eigenvalues are exactly zero, the problem is called critical or null recurrent. Although in this case the problem is ill‐conditioned and the convergence of the algorithms based on matrix iterations is slow, there exist some techniques to remove the singularity and transform the problem to a well‐behaved one. Ill‐conditioning and slow convergence appear also in close‐to‐critical problems, but when none of the eigenvalues is exactly zero, the techniques used for the critical case cannot be applied. In this paper, we introduce a new method to accelerate the convergence properties of the iterations also in close‐to‐critical cases, by working on the invariant subspace associated with the problematic eigenvalues as a whole. We present numerical experiments that confirm the efficiency of the new method.Copyright © 2012 John Wiley & Sons, Ltd.     

Iterated Tikhonov regularization with a general penalty term

Tikhonov regularization is one of the most popular approaches to solving linear discrete ill‐posed problems. The choice of the regularization matrix may significantly affect the quality of the computed solution. When the regularization matrix is the identity, iterated Tikhonov regularization can yield computed approximate solutions of higher quality than (standard) Tikhonov regularization. This paper provides an analysis of iterated Tikhonov regularization with a regularization matrix different from the identity. Computed examples illustrate the performance of this method.     

Dealing with linear dependence during the iterations of the restarted block Lanczos methods

The Lanczos method can be generalized to block form to compute multiple eigenvalues without the need of any deflation techniques. The block Lanczos method reduces a general sparse symmetric matrix to a block tridiagonal matrix via a Gram–Schmidt process. During the iterations of the block Lanczos method an off-diagonal block of the block tridiagonal matrix may become singular, implying that the new set of Lanczos vectors are linearly dependent on the previously generated vectors. Unlike the single vector Lanczos method, this occurrence of linearly dependent vectors may not imply an invariant subspace has been computed. This difficulty of a singular off-diagonal block is easily overcome in non-restarted block Lanczos methods, see [12,30]. The same schemes applied in non-restarted block Lanczos methods can also be applied in restarted block Lanczos methods. This allows the largest possible subspace to be built before restarting. However, in some cases a modification of the restart vectors is required or a singular block will continue to reoccur. In this paper we examine the different schemes mentioned in [12,30] for overcoming a singular block for the restarted block Lanczos methods, namely the restarted method reported in [12] and the Implicitly Restarted Block Lanczos (IRBL) method developed by Baglama et al. [3]. Numerical examples are presented to illustrate the different strategies discussed.     

Application of the Lanczos algorithm for solving the linear systems that occur in continuation problems

We study the Lanczos method for solving symmetric linear systems with multiple right‐hand sides. First, we propose a numerical method of implementing the Lanczos method, which can provide all approximations to the solution vectors of the remaining linear systems. We also seek possible application of this algorithm for solving the linear systems that occur in continuation problems. Sample numerical results are reported. Copyright © 2002 John Wiley & Sons, Ltd.     

Approximate source conditions in Tikhonov–Phillips regularization and consequences for inverse problems with multiplication operators

The object of this paper is threefold. First, we investigate in a Hilbert space setting the utility of approximate source conditions in the method of Tikhonov–Phillips regularization for linear ill‐posed operator equations. We introduce distance functions measuring the violation of canonical source conditions and derive convergence rates for regularized solutions based on those functions. Moreover, such distance functions are verified for simple multiplication operators in L²(0, 1). The second aim of this paper is to emphasize that multiplication operators play some interesting role in inverse problem theory. In this context, we give examples of non‐linear inverse problems in natural sciences and stochastic finance that can be written as non‐linear operator equations in L²(0, 1), for which the forward operator is a composition of a linear integration operator and a non‐linear superposition operator. The Fréchet derivative of such a forward operator is a composition of a compact integration and a non‐compact multiplication operator. If the multiplier function defining the multiplication operator has zeros, then for the linearization an additional ill‐posedness factor arises. By considering the structure of canonical source conditions for the linearized problem it could be expected that different decay rates of multiplier functions near a zero, for example the decay as a power or as an exponential function, would lead to completely different ill‐posedness situations. As third we apply the results on approximate source conditions to such composite linear problems in L²(0, 1) and indicate that only integrals of multiplier functions and not the specific character of the decay of multiplier functions in a neighbourhood of a zero determine the convergence behaviour of regularized solutions. Copyright © 2005 John Wiley & Sons, Ltd.     

A structure‐preserving doubling algorithm for Lur'e equations

We introduce a numerical method for the numerical solution of the Lur'e equations, a system of matrix equations that arises, for instance, in linear‐quadratic infinite time horizon optimal control. We focus on small‐scale, dense problems. Via a Cayley transformation, the problem is transformed to the discrete‐time case, and the structural infinite eigenvalues of the associated matrix pencil are deflated. The deflated problem is associated with a symplectic pencil with several Jordan blocks of eigenvalue 1 and even size, which arise from the nontrivial Kronecker chains at infinity of the original problem. For the solution of this modified problem, we use the structure‐preserving doubling algorithm. Implementation issues such as the choice of the parameter γ in the Cayley transform are discussed. The most interesting feature of this method, with respect to the competing approaches, is the absence of arbitrary rank decisions, which may be ill‐posed and numerically troublesome. The numerical examples presented confirm the effectiveness of this method. Copyright © 2015 John Wiley & Sons, Ltd.     

Lanczos-type Methods for Continuation Problems

We study the Lanczos type methods for continuation problems. First we indicate how the symmetric Lanczos method may be used to solve both positive definite and indefinite linear systems. Furthermore, it can be used to monitor the simple bifurcation points on the solution curve of the eigenvalue problems. This includes computing the minimum eigenvalue, the minimum singular value, and the condition number of the partial tridiagonalizations of the coefficient matrices. The Ritz vector thus obtained can be applied to compute the tangent vector at the bifurcation point for branch-switching. Next, we indicate that the block or band Lanczos method can be used to monitor the multiple bifurcations as well as to solve the multiple right hand sides. We also show that the unsymmetric Lanczos method can be exploited to compute the minimum eigenvalue of a nearly symmetric matrix, and therefore to detect the simple bifurcation point as well. Some preconditioning techniques are discussed. Sample numerical results are reported. Our test problems include second order semilinear elliptic eigenvalue problems. © 1997 by John Wiley & Sons, Ltd.     

求解病态线性方程组的收缩Lanczos方法

Lanczos方法是求解大型线性方程组的常用方法.遗憾的是,在Lanczos过程中通常会发生算法中断或数值不稳定的情况.将给出求解大型对称线性方程组的收缩Lanczos方法,即DLanczos方法.新算法将采用增广子空间技术,在Lanczos过程中向Krylov子空间加入少量绝对值较小的特征值所对应的特征向量进行收缩.数值实验表明,新算法比Lanczos方法收敛速度更快,并且适合求解病态对称线性方程组.     

TWO ALGORITHMS FOR SYMMETRIC LINEAR SYSTEMS WITH MULTIPLE RIGHT-HAND SIDES

1　ＩｎｔｒｏｄｕｃｔｉｏｎＩｎｍａｎｙａｐｐｌｉｃａｔｉｏｎｓｗｅｎｅｅｄｔｏｓｏｌｖｅｍｕｌｔｉｐｌｅｓｙｓｔｅｍｓｏｆｌｉｎｅａｒｅｑｕａｔｉｏｎｓＡｘ(ｉ) =ｂ(ｉ) ,ｉ=1,… ,ｓ (1)ｗｉｔｈｔｈｅｓａｍｅｎ×ｎｒｅａｌｓｙｍｍｅｔｒｉｃｃｏｅｆｆｉｃｉｅｎｔｍａｔｒｉｘＡ ,ｂｕｔｓｄｉｆｆｅｒｅｎｔｒｉｇｈｔ ｈａｎｄｓｉｄｅｓｂ(ｉ) (ｉ=1,… ,ｓ) .Ｉｆａｌｌｏｆｔｈｅｒｉｇｈｔ ｈａｎｄｓｉｄｅｓａｒｅａｖａｉｌａｂｌｅｓｉｍｕｌｔａｎｅｏｕｓｌｙ ,ｔｈｅｎｔｈｅｓｅｓｌｉｎｅａｒｓｙｓｔｅ…     

On the Odir iterative method for non‐symmetric indefinite linear systems

Several Krylov subspace iterative methods have been proposed for the approximation of the solution of general non‐symmetric linear systems. Odir is such a method. Here we study the restarted version of Odir for non‐symmetric indefinite linear systems and we prove convergence under certain conditions on the matrix of coefficients. These results hold for all the restarted Krylov methods equivalent to Odir. We also introduce a new truncated Odir method which is proved to converge for a large class of non‐symmetric indefinite linear systems. This new method requires one‐half of the storage of the standard Odir. Copyright © 2001 John Wiley & Sons, Ltd.     

Inertia‐based spectrum slicing for symmetric quadratic eigenvalue problems

In the quadratic eigenvalue problem (QEP) with all coefficient matrices symmetric, there can be complex eigenvalues. However, some applications need to compute real eigenvalues only. We propose a Lanczos‐based method for computing all real eigenvalues contained in a given interval of large‐scale symmetric QEPs. The method uses matrix inertias of the quadratic polynomial evaluated at different shift values. In this way, for hyperbolic problems, it is possible to make sure that all eigenvalues in the interval have been computed. We also discuss the general nonhyperbolic case. Our implementation is memory‐efficient by representing the computed pseudo‐Lanczos basis in a compact tensor product representation. We show results of computational experiments with a parallel implementation in the SLEPc library.     

A modified truncated singular value decomposition method for discrete ill‐posed problems

Truncated singular value decomposition is a popular method for solving linear discrete ill‐posed problems with a small to moderately sized matrix A. Regularization is achieved by replacing the matrix A by its best rank‐k approximant, which we denote by A_k. The rank may be determined in a variety of ways, for example, by the discrepancy principle or the L‐curve criterion. This paper describes a novel regularization approach, in which A is replaced by the closest matrix in a unitarily invariant matrix norm with the same spectral condition number as A_k. Computed examples illustrate that this regularization approach often yields approximate solutions of higher quality than the replacement of A by A_k.Copyright © 2014 John Wiley & Sons, Ltd.     

A numerical study of the SVD–MFS solution of inverse boundary value problems in two‐dimensional steady‐state linear thermoelasticity

We study the reconstruction of the missing thermal and mechanical data on an inaccessible part of the boundary in the case of two‐dimensional linear isotropic thermoelastic materials from overprescribed noisy measurements taken on the remaining accessible boundary part. This inverse problem is solved by using the method of fundamental solutions together with the method of particular solutions. The stabilization of this inverse problem is achieved using several singular value decomposition (SVD)‐based regularization methods, such as the Tikhonov regularization method (Tikhonov and Arsenin, Methods for solving ill‐posed problems, Nauka, Moscow, 1986), the damped SVD and the truncated SVD (Hansen, Rank‐deficient and discrete ill‐posed problems: numerical aspects of linear inversion, SIAM, Philadelphia, 1998), whilst the optimal regularization parameter is selected according to the discrepancy principle (Morozov, Sov Math Doklady 7 (1966), 414–417), generalized cross‐validation criterion (Golub et al. Technometrics 22 (1979), 1–35) and Hansen's L‐curve method (Hansen and O'Leary, SIAM J Sci Comput 14 (1993), 1487–503). © 2014 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 31: 168–201, 2015     

Some results on the regularization of LSQR for large-scale discrete ill-posed problems

LSQR, a Lanczos bidiagonalization based Krylov subspace iterative method, and its mathematically equivalent conjugate gradient for least squares problems (CGLS) applied to normal equations system, are commonly used for large-scale discrete ill-posed problems. It is well known that LSQR and CGLS have regularizing effects, where the number of iterations plays the role of the regularization parameter. However, it has long been unknown whether the regularizing effects are good enough to find best possible regularized solutions. Here a best possible regularized solution means that it is at least as accurate as the best regularized solution obtained by the truncated singular value decomposition (TSVD) method. We establish bounds for the distance between the k-dimensional Krylov subspace and the k-dimensional dominant right singular space. They show that the Krylov subspace captures the dominant right singular space better for severely and moderately ill-posed problems than for mildly ill-posed problems. Our general conclusions are that LSQR has better regularizing effects for the first two kinds of problems than for the third kind, and a hybrid LSQR with additional regularization is generally needed for mildly ill-posed problems. Exploiting the established bounds, we derive an estimate for the accuracy of the rank k approximation generated by Lanczos bidiagonalization. Numerical experiments illustrate that the regularizing effects of LSQR are good enough to compute best possible regularized solutions for severely and moderately ill-posed problems, stronger than our theory predicts, but they are not for mildly ill-posed problems and additional regularization is needed.     

Error estimates for large-scale ill-posed problems

The computation of an approximate solution of linear discrete ill-posed problems with contaminated data is delicate due to the possibility of severe error propagation. Tikhonov regularization seeks to reduce the sensitivity of the computed solution to errors in the data by replacing the given ill-posed problem by a nearby problem, whose solution is less sensitive to perturbation. This regularization method requires that a suitable value of the regularization parameter be chosen. Recently, Brezinski et al. (Numer Algorithms 49, 2008) described new approaches to estimate the error in approximate solutions of linear systems of equations and applied these estimates to determine a suitable value of the regularization parameter in Tikhonov regularization when the approximate solution is computed with the aid of the singular value decomposition. This paper discusses applications of these and related error estimates to the solution of large-scale ill-posed problems when approximate solutions are computed by Tikhonov regularization based on partial Lanczos bidiagonalization of the matrix. The connection between partial Lanczos bidiagonalization and Gauss quadrature is utilized to determine inexpensive bounds for a family of error estimates. In memory of Gene H. Golub. This work was supported by MIUR under the PRIN grant no. 2006017542-003 and by the University of Cagliari.