|
|
| (22 intermediate revisions by the same user not shown) |
| Line 1: |
Line 1: |
| − | ''Phillips–Tikhonov regularization''
| + | Post $\TeX$ notes. |
| − | | + | * Modified the norm subscripts to mention the space, $\left\|\cdot\right\|_1$ becomes $\left\|\cdot\right\|_{H_1}$, so as not cause confusion with the $L_p$ norms. |
| − | Fredholm integral equations of the first kind (cf. also [[Fredholm equation|Fredholm equation]]),
| + | * Removed repeated reference for Fredholm Equation |
| − | | + | * Added reference to Sobolev space |
| − | <table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120100/t1201001.png" /></td> </tr></table>
| + | --[[User:Jjg|Jjg]] 18:00, 25 April 2012 (CEST) |
| − | | |
| − | present special challenges to working scientists (cf. also [[Fredholm equation, numerical methods|Fredholm equation, numerical methods]]; [[Fredholm equation|Fredholm equation]]). Unlike equations of the second kind, for which the existence of a unique stable solution can be guaranteed under mild conditions, integral equations of the first kind are typically ill-posed (cf. also [[Ill-posed problems|Ill-posed problems]]). The blame for this misbehaviour lies with the kernel <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120100/t1201002.png" />. The data function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120100/t1201003.png" /> inherits some of the structure and smoothness of the kernel and hence, if the kernel is highly structured or very smooth, then a solution exists only for functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120100/t1201004.png" /> belonging to a quite exclusive class of data. Furthermore, null functions for the kernel may be plentiful, so when solutions exist, they are seldom unique. But the most troubling aspect of the first-kind equation is its instability: perturbations in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120100/t1201005.png" /> which are very small (with respect to reasonable metrics on the data space) may arise from very large changes in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120100/t1201006.png" />. This instability is a consequence of the Riemann–Lebesgue lemma (cf. [[Fourier series|Fourier series]]) or, more generally, from the decay to zero of the singular values of the kernel.
| |
| − | | |
| − | The basic existence and uniqueness theory for Fredholm equations of the first kind with square-integrable kernels was worked out by E. Picard [[#References|[a13]]] in the early 1900s. Toward the 1950s, iterative approximation methods for Fredholm equations of the first kind were developed (see, e.g., [[#References|[a3]]], [[#References|[a7]]]), but soon thereafter it became apparent that when these methods are applied to practical problems, the approximations are cursed by the instability noted above (see, e.g., [[#References|[a1]]], [[#References|[a9]]]). This led to the development, in the early 1960s, of a non-iterative stabilized approximation technique, now called the method of regularization, by D.L. Phillips [[#References|[a12]]] and A.N. Tikhonov [[#References|[a14]]].
| |
| − | | |
| − | The analysis of the method of regularization is best carried out in the context of a [[Hilbert space|Hilbert space]], where the integral operator is modeled by a [[Compact operator|compact operator]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120100/t1201007.png" /> from a Hilbert space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120100/t1201008.png" /> into a Hilbert space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120100/t1201009.png" />. The norm of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120100/t12010010.png" /> should be sufficiently weak to accommodate realistic data functions, while that of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120100/t12010011.png" /> should be strong enough to impose desirable structure on the solution. In the method of regularization a "damped least-squares" approximate solution of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120100/t12010012.png" /> is sought by minimizing the functional
| |
| − | | |
| − | <table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120100/t12010013.png" /></td> </tr></table>
| |
| − | | |
| − | where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120100/t12010014.png" /> is a regularization parameter. The minimizer <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120100/t12010015.png" /> of this functional is the solution of the well-posed second-kind equation
| |
| − | | |
| − | <table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120100/t12010016.png" /></td> </tr></table>
| |
| − | | |
| − | (cf. also [[Integral equation|Integral equation]]) and hence is unique and stable with respect to perturbations of the data function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120100/t12010017.png" />. The regularization parameter may be viewed as an arbiter between fidelity and stability in the approximate solution; a choice of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120100/t12010018.png" /> that is too small causes the approximate solution to inherit some of the instability of the original ill-posed problem, while too large a choice tends to over-smooth the approximate solution with consequent loss of information.
| |
| − | | |
| − | A key point in practical problems is that the data function is the result of observations and hence is subject to error. The data function in hand is then an observation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120100/t12010019.png" /> satisfying <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120100/t12010020.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120100/t12010021.png" /> is a bound for the observational error. One then takes the minimizer <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120100/t12010022.png" /> of the functional <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120100/t12010023.png" /> as an approximate solution. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120100/t12010024.png" /> is chosen so that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120100/t12010025.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120100/t12010026.png" /> as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120100/t12010027.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120100/t12010028.png" /> is the minimal-norm least-squares solution of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120100/t12010029.png" /> (cf. also [[Least squares, method of|Least squares, method of]]). If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120100/t12010030.png" /> is in the range of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120100/t12010031.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120100/t12010032.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120100/t12010033.png" />, and this order is best possible (see [[#References|[a4]]], p. 41).
| |
| − | | |
| − | V.A. Morozov [[#References|[a10]]] introduced an a posteriori parameter choice strategy (already used informally by D.L. Phillips [[#References|[a12]]]) called the discrepancy principle. According to this principle, there is a unique <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120100/t12010034.png" /> satisfying <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120100/t12010035.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120100/t12010036.png" /> as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120100/t12010037.png" />. Furthermore, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120100/t12010038.png" /> is in the range of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120100/t12010039.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120100/t12010040.png" />, but this order is best possible [[#References|[a4]]], p. 50. Discrepancy principles that attain the optimal order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120100/t12010041.png" /> have been devised by T. Raus, H. Gfrerer and H. Engl (see [[#References|[a2]]]). The <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120100/t12010042.png" /> brick wall for ordinary Tikhonov regularization can be scaled by using an iterated version of the regularization method. Iterated Tikhonov regularization consists of sequentially minimizing the functionals
| |
| − | | |
| − | <table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120100/t12010043.png" /></td> </tr></table>
| |
| − | | |
| − | where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120100/t12010044.png" /> is the minimizer of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120100/t12010045.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120100/t12010046.png" /> is a suitable sequence of regularization parameters. Under appropriate conditions, this method attains an order of approximation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120100/t12010047.png" /> for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120100/t12010048.png" /> (see [[#References|[a5]]]).
| |
| − | | |
| − | The computational implementation of the method of regularization requires a discretization procedure to produce a finite-dimensional problem. The interpretation of the method as a variational technique suggests finite-element methods, while its interpretation as an integral equation of the second kind suggests quadrature or degenerate-kernel methods (cf. also [[Degenerate kernel|Degenerate kernel]]; [[Quadrature|Quadrature]]). In any case, a successful computational experience relies on a delicate balancing of regularization norm, regularization parameter, discretization parameters, and characteristics of the data error. For more on discretized ill-posed problems, see [[#References|[a6]]].
| |
| − | | |
| − | In Tikhonov's original work, the regularizing norm <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120100/t12010049.png" /> was taken to be a Sobolev norm and the data norm <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120100/t12010050.png" /> was the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120100/t12010051.png" />-norm. Therefore, the Euler equation characterizing the regularized approximation is an [[Integro-differential equation|integro-differential equation]] and the convergence of the approximations is uniform. Phillips, however, used a regularizing [[Semi-norm|semi-norm]] (the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120100/t12010052.png" />-norm of the second derivative) and hence the Phillips method requires a more detailed analysis than Tikhonov's method (see [[#References|[a8]]], [[#References|[a11]]]).
| |
| − | | |
| − | ====References====
| |
| − | <table><TR><TD valign="top">[a1]</TD> <TD valign="top"> J. Douglas Jr., "Mathematical programming and integral equations" , ''Symp. Numerical Treatment of Ordinary Differential Equations, Integral and Integro-differential Equations (Rome, 1960)'' , Birkhäuser (1960) pp. 269–274</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top"> H.W. Engl, M. Hanke, A. Neubauer, "Regularization of inverse problems" , Kluwer Acad. Publ. (1996)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top"> V.M. Fridman, "Method of successive approximations for Fredholm integral equations of the first kind" ''Uspekhi Mat. Nauk'' , '''11''' (1956) pp. 233–234 (In Russian)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top"> C.W. Groetsch, "The theory of Tikhonov regularization for Fredholm equations of the first kind" , Pitman (1984)</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top"> M. Hanke, C.W. Groetsch, "Nonstationary iterated Tikhonov regularization" ''J. Optim. Th. Appl.'' , '''98''' (1998) pp. 37–53</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top"> P.C. Hansen, "Rank-deficient and discrete ill-posed problems" , SIAM (Soc. Industrial Applied Math.) (1998)</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top"> L. Landweber, "An iteration formula for Fredholm integral equations of the first kind" ''Amer. J. Math.'' , '''73''' (1951) pp. 615–624</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top"> A.K. Louis, "Inverse und schlecht gestellte Probleme" , Teubner (1989)</TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top"> R.W. McKelvey, "An analysis of approximative methods for Fredholm's integral equation of the first kind" ''Techn. Rep. David Taylor Model Basin, U.S. Navy Dep., Washington, D.C.'' , '''19''' (1956)</TD></TR><TR><TD valign="top">[a10]</TD> <TD valign="top"> V.A. Morozov, "On the solution of functional equations by the method of regularization" '
| |
| − | 'Soviet Math. Dokl.'' , '''7''' (1966) pp. 414–417</TD></TR><TR><TD valign="top">[a11]</TD> <TD valign="top"> V.A. Morozov, "Regularization methods for ill-posed problems" , CRC (1993)</TD></TR><TR><TD valign="top">[a12]</TD> <TD valign="top"> D.L. Phillips, "A technique for the numerical solution of certain integral equations of the first kind" ''J. Assoc. Comput. Mach.'' , '''9''' (1962) pp. 84–97</TD></TR><TR><TD valign="top">[a13]</TD> <TD valign="top"> E. Picard, "Sur un théorème générale relatif aux équations intégrales de première espèce et sur quelques problèmes de physique mathématique" ''Rend. Circ. Mat. Palermo'' , '''29''' (1910) pp. 79–97</TD></TR><TR><TD valign="top">[a14]</TD> <TD valign="top"> A.N. Tikhonov, "Solution of incorrectly formulated problems and the regularization method" ''Soviet Math. Dokl.'' , '''4''' (1963) pp. 1035–1038</TD></TR></table>
| |