Iterative Regularization Methods For Large-scale Discrete III-posed Problems

Iterative regularization methods based on Krylov subspace methods are commonly used for large-scale discrete ill-posed problems. In this thesis, we study the regularizing effects of these methods, and give some definitive theoretical analysis.LSQR, a Lanczos bidiagonalization based Krylov method, and its mathematically equivalent 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 essentially has the minimum 2-norm error when standard-form Tikhonov regularization is used, or from the other perspective, it is at least as accurate as the best regularized solution obtained by the truncated singular value decomposition(TSVD) method. We first 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, in general, is 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, but they are not for mildly ill-posed problems and additional regularization is needed.For large-scale symmetric discrete ill-posed problems, MINRES and MR-II are commonly used iterative solvers. We analyze their regularizing effects. We first prove that the regularized solutions by MINRES have filtered SVD forms. Then we show that(i) a hybrid MINRES that uses explicit regularization within projected problems is generally needed to compute a best possible regularized solution to a given ill-posed problem and(ii) the kth iterate by MINRES is more accurate than the(k-1)th iterate by MR-II until the semi-convergence of MINRES, though MR-II has globally better regularizing effects than MINRES. Moreover, we establish bounds for the distance between an underlying k-dimensional Krylov subspace and the k-dimensional dominant eigenspace. They show that MR-II has better regularizing effects for severely and moderately ill-posed problems than for mildly ill-posed problems, indicating that a hybrid MR-II is needed to get a best possible regularized solution for mildly ill-posed problems. Numerical experiments confirm our assertions. Stronger than our theory, MR-II is experimentally good enough to compute best possible regularized solutions for severely and moderately ill-posed problems. We also justify that MR-II is as equally effective as and twice as efficient as LSQR for symmetric ill-posed problems.For large-scale nonsymmetric discrete ill-posed problems, GMRES and its variant RRGMRES seem natural candidate methods. From the viewpoint of numerical experiments, we show that k-dimensional Krylov subspace is far from the k-dimensional dominant right singular space, and the Arnoldi process fails to capture the dominant SVD components. Thus, we conclude that although GMRES and its variants seem suitable for some ill-posed problems, the methods based on the Arnoldi process do not have general regularizing properties.