Optimal order multilevel preconditioners for regularized ill-posed problems

In this article we design and analyze multilevel preconditioners for linear systems arising from regularized inverse problems. Using a scale-independent distance function that measures spectral equivalence of operators, it is shown that these preconditioners approximate the inverse of the operator to optimal order with respect to the spatial discretization parameter $h$. As a consequence, the number of preconditioned conjugate gradient iterations needed for solving the system will decrease when increasing the number of levels, with the possibility of performing only one fine-level residual computation if $h$ is small enough. The results are based on the previously known two-level preconditioners of Rieder (1997) (see also Hanke and Vogel (1999)), and on applying Newton-like methods to the operator equation $X^{-1} - A = 0$. We require that the associated forward problem has certain smoothing properties; however, only natural stability and approximation properties are assumed for the discrete operators. The algorithm is applied to a reverse-time parabolic equation, that is, the problem of finding the initial value leading to a given final state. We also present some results on constructing restriction operators with preassigned approximating properties that are of independent interest.