×

A posteriori parameter choice strategy for fast multiscale methods solving ill-posed integral equations. (English) Zbl 1250.65158

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.

MSC:

65R20 Numerical methods for integral equations
65J20 Numerical solutions of ill-posed problems in abstract spaces; regularization
45B05 Fredholm integral equations
45Q05 Inverse problems for integral equations
47A52 Linear operators and ill-posed problems, regularization
65J10 Numerical solutions to equations with linear operators
65J22 Numerical solution to inverse problems in abstract spaces
65R30 Numerical methods for ill-posed problems for integral equations
65R32 Numerical methods for inverse problems for integral equations
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Micchelli, C.A., Xu, Y., Zhao, Y.: Wavelet Galerkin methods for second-kind integral equations. J. Comput. Appl. Math. 86, 251–70 (1997) · Zbl 0913.65129 · doi:10.1016/S0377-0427(97)00160-X
[2] Chen, Z., Micchelli, C.A., Xu, Y.: The Petrov-Galerkin methods for second kind integral equations II: multiwavelet scheme. Adv. Comput. Math. 7, 199–233 (1997) · Zbl 0915.65134 · doi:10.1023/A:1018994802659
[3] Chen, Z., Micchelli, C.A., Xu, Y.: Fast collocation methods for second kind integral equations. SIAM J. Numer. Anal. 40, 344–375 (2002) · Zbl 1016.65107 · doi:10.1137/S0036142901389372
[4] Chen, Z., Wu, B., Xu, Y.: Multilevel augmentation methods for solving operator equations. Numer. Math. J. Chinese. Univ. 14, 31–55 (2005) · Zbl 1077.65053
[5] Chen, Z., Xu, Y., Yang, H.: Multilevel augmentation methods for solving ill-posed operator equations. Inverse Probl. 22, 155–174 (2006) · Zbl 1088.65051 · doi:10.1088/0266-5611/22/1/009
[6] Chen, Z., Cheng, S., Nelakanti, G., Yang, H.: A fast multiscale Galerkin method for the first kind ill-posed integral equations via Tikhonov regularization. Int. J. Comput. Math. 87, 565–582 (2010) · Zbl 1219.65160 · doi:10.1080/00207160802155302
[7] Solodky, S.G.: On a quasi-optimal regularized projection method for solving operator equations of the first kind. Inverse Probl. 21, 1473–1485 (2005) · Zbl 1083.65055 · doi:10.1088/0266-5611/21/4/017
[8] Rajan, M.P.: A posteriori parameter choice strategy and an efficient discretization scheme for solving ill-posed problems. Appl. Math. Comput. 204, 891–904 (2008) · Zbl 1163.65029 · doi:10.1016/j.amc.2008.07.036
[9] Maass, P., Pereverzev, S.V., Ramlau, R., Solodky, S.G.: An adaptive discretization for Tikhonov Phillips regularization with a posteriori parameter selection. Numer. Math. 87, 485–502 (2001) · Zbl 0974.65055 · doi:10.1007/PL00005421
[10] Luo, X.J.: Fast multilevel iteration methods for solving linear operator equations. J. Northeast. Math. 24(1), 1–9 (2008) · Zbl 1174.65408
[11] Luo, X.J., Li, F.C.: An optimal regularized projection method for solving ill-posed problems via dynamical systems method. J. Math. Anal. Appl. 370, 379–391 (2010) · Zbl 1201.65097 · doi:10.1016/j.jmaa.2010.05.023
[12] Pereverzev, S.V.: Optimization of projection methods for solving ill-posed problems. Computing 55, 113–124 (1995) · Zbl 0830.65044 · doi:10.1007/BF02238096
[13] Gfrerer, H.: An a posteriori parameter choice for ordinary and iterated Tikhonov regularization of ill-posed problems leading to optimal convergence rate. Math. Comput. 49, 507–522 (1987) · Zbl 0631.65057 · doi:10.1090/S0025-5718-1987-0906185-4
[14] Chen, Z., Micchelli, C.A., Xu, Y.: Discrete wavelet Petrov–Galerkin methods. Adv. Comput. Math. 16, 1–28 (2002) · Zbl 0998.65120 · doi:10.1023/A:1014273420351
[15] Micchelli, C.A., Xu, Y.: Using the matrix refinement equation for the construction of wavelets on invariant sets. Appl. Comput. Harmon. Anal. 1, 391–401 (1994) · Zbl 0815.42019 · doi:10.1006/acha.1994.1024
[16] Micchelli, C.A., Xu, Y.: Reconstruction and decomposition algorithms for biorthogonal multiwavelets. Multidimens. Syst. Signal Process. 8, 31–69 (1997) · Zbl 0872.42010 · doi:10.1023/A:1008264805830
[17] Pereverzev, S.V., Solodky, S.G.: On one approach to the discretization of the Lavrent’ev method. Ukr. Math. J. 48(2), 239–247 (1996) · Zbl 0940.65054 · doi:10.1007/BF02372049
[18] Solodky, S.G.: The optimal approximations for solving linear ill-posed problems. J. Complex. 17, 98–116 (2001) · Zbl 1005.65051 · doi:10.1006/jcom.2000.0546
[19] Nair, M.T., Rajan, M.P.: Arcangeli’s discrepancy principle for a modified projection scheme for ill-posed problems. Numer. Funct. Anal. Optim. 22, 773–787 (2001) · Zbl 0986.65057
[20] Nair, M.T., Rajan, M.P.: Arcangeli’s type discrepancy principle for a class of regularization methods using modified projection scheme. Abstr. Appl. Anal. 6, 339–356 (2001) · Zbl 1005.65054 · doi:10.1155/S1085337501000653
[21] Raus, T.: About discrepancy principle for solving ill-posed problems. Uchenye Zapiski Tartuskogo Universiteta 672, 16–26 (1984) (in Russian) · Zbl 0578.65050
[22] Neubauer, A.: An a posteriori parameter choice for Tikhonov regularization in the presence of modelling error. Appl. Numer. Math. 4, 507–519 (1987) · Zbl 0698.65032 · doi:10.1016/0168-9274(88)90013-X
[23] Chen, Z., Jiang, Y., Song, L., Yang, H.: A parameter choice strategy for a multi-level augmentation method solving ill-posed operator equations. J. Integral Equ. Appl. 20, 569–590 (2008) · Zbl 1172.65025 · doi:10.1216/JIE-2008-20-4-569
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.