A posteriori parameter choice strategy for fast multiscale methods solving ill-posed integral equations (Q421362): Difference between revisions

A modified discrepancy principle for Tikhonov regularization of an integral equation of the first kind is considered, with a multiscale discretization to obtain a fast solver. We give some details, and for this purpose we consider the first kind Fredholm integral equation \( (Ax)(s) = \int_E k(s,t) x(t) dt = y (s), \, s \in E \), where \( E \) is a bounded closed set in \( \mathbb{R}^d \), with \( d \geq 1 \), and \( k \) is a continuous non-degenerate kernel. The operator \( A \) is considered as a compact operator from \( X = L^2(E) \) into \( X \), with the standard \( L^2 \) norm on \( X \) which is denoted by \( \| \cdot \| \). It is assumed that the right-hand side \( y \) belongs to the range \( R(A) \) of \( A \), and noisy data \( y^\delta \in X \) with \( \| y - y^\delta \| \leq \delta \) are available only. It is moreover assumed that both \( A \) and \( A^* \) are bounded operators from \( X \) into a linear subspace \( H^r \subset X \), where \( H^r \) is equipped with some norm that is stronger than the norm \( \| \cdot \| \) on \( X \). For the discretization, finite-dimensional linear subspaces \( X_0 \subset X_1 \subset \dots \subset X \) are considered, where \( X_n \) is the space of piecewise polynomials of degree less than \( r \) corresponding to some partition \( E_n \) of \( E \). It is assumed that the orthogonal projection operators \( P_n: X \to X \) onto \( X_n \) satisfy \( \| I - P_n \|_{H^r \to X} \leq c_r \mu^{-rn/d} \) for \( n = 0, 1, \ldots \)~. Here, \( \mu > 0 \) is a parameter such that the maximum diameter of the subsets of the partition \( E_n \) can be estimated by \( O(\mu^{-n/d}) \). The regularization method under consideration is Tikhonov regularization \[ \widetilde{x}_n^{\alpha,\delta} = (\alpha I + \widetilde{A}_n^* \widetilde{A}_n)^{-1} \widetilde{A}_n^* P_n y^\delta, \quad \alpha > 0, \] where \( \widetilde{A}_n=\sum_{i=0}^{n} (P_i-P_{i-1}) A P_{n-i}: X \to X \), with \( P_{-1} = 0 \), is an approximation to \( A \) which in fact requires only a small fraction of the scalar products needed to compute the standard discretization \( P_{n} A P_{n} \). An estimation of the number of scalar products required for the computation of \( \widetilde{x}_n^{\alpha,\delta} \) is given in the paper. In addition, \( \widetilde{A}_n^* \) denotes the adjoint operator of \( \widetilde{A}_n \). The considered parameter choice rule is as follows: choose \( n \) sufficiently large, and then for regularization parameters \( \alpha_m = a_0 q^m, ~m = 0, 1, \ldots, \) compute the Tikhonov approximations until \[ \begin{aligned} \| \alpha_m^{1/2} (\alpha_m I + \widetilde{A}_n \widetilde{A}_n^*)^{-1/2} (\widetilde{A}_n \widetilde{x}_n^{\alpha_m,\delta} - P_n y^\delta ) \| \leq d \delta \tag{\(*\)} \end{aligned} \] is satisfied for the first time, where \( a_0 > 0 \) and \( 0 < q < 1 \) are fixed, and \( d > 1 \) denotes some constant chosen sufficiently large. For the parameter \( \alpha_m \) chosen by \((*)\), it is shown that \( \| \widetilde{x}_n^{\alpha_m,\delta} - x^\dagger \| = O(\delta^{2\nu/(2\nu+1)}) \) as \( \delta \to 0 \) holds provided that the minimum norm solution \( x^\dagger \in X \) of the equation \( Ax=y\) can be represented in the form \( x^\dagger \in R((A^*A)^\nu) \) for some \( 0 < \nu \leq 1 \). The paper concludes with the presentation of results of some numerical experiments.