Abstract Generated abstract
This paper addresses ill-posed inverse problems arising in mathematical physics, focusing on Fredholm equations of the first kind and the instability of recovering an unknown function from approximate data. It formulates a regularization principle using a smoothing functional composed of a residual term and a positive quadratic regularizing functional, and proves existence, uniqueness, and uniform convergence of the resulting minimizers under suitable compactness and parameter conditions. The paper also develops a finite-difference version of the method, giving convergence statements for noisy data when the regularization parameter is chosen in relation to the error level. The approach is presented as an algorithm suitable for digital computation and is indicated to extend to more general bounded operators, multidimensional domains, equations of the second kind, and nonlinear problems.
Full Text
Reports of the Academy of Sciences of the USSR
1963. Volume 151, No. 3
MATHEMATICS
Corresponding Member of the USSR Academy of Sciences A. N. TIKHONOV
ON THE SOLUTION OF ILL-POSED PROBLEMS AND THE REGULARIZATION METHOD
1. Inverse problems of mathematical physics often lead to ill-posed problems. A typical example is the Fredholm equation of the first kind
\[ A[x,z(s)] = \int_a^b K(x,s)z(s)\,ds = u(x), \qquad c \le x \le d. \tag{1} \]
This equation has a solution not for every function \(u(x)\). It is obvious that if \(K(x,s)\) has a certain degree of smoothness with respect to \(x\), then there is no function \(z(s)\in L_2\) satisfying equation (1) if \(u(x)\) has a lower degree of smoothness. We shall assume uniqueness of the solution of equation (1), i.e., we shall suppose that if for some function \(\bar u(x)\) equation (1) has a solution \(\bar z(s)\), then it has only one.
Let the function \(\bar u(x)\) be such that equation (1) has a solution \(\bar z(s)\). The purpose of the present article is to set forth an algorithm for constructing a uniform approximation to the function \(\bar z(s)\). In what follows we shall assume that \(\bar z\in \bar C_1\), where \(\bar C_1\) is the class of continuous piecewise-smooth functions.
Denote by \(U\) the class of functions \(u(x)=A[x,z(s)]\), \(z(s)\in \bar C_1\). As the norm of deviation in \(\bar C_1\) we shall take
\[ \|z\|=\max |z(s)| \qquad (a\le s\le b) \]
and as the norm of deviation in \(U\),
\[ \|u(x)\|=\left[\int_c^d u^2(x)\,dx\right]^{1/2}. \]
If the kernel \(K(x,s)\) is continuous, then the mapping \(\bar C_1\to U\) is continuous. It should be borne in mind that the inverse problem—the problem of finding \(z(s)\) from a given function \(u(x)\)—is ill-posed. Indeed, to the functions \(z_1(s)\) and \(z_2(s)=z_1(s)+p\cos\omega s\), \(z_1(s), z_2(s)\in \bar C_1\), where \(p\) is any fixed number (however large), there will correspond functions \(u_1(x)\) and \(u_2(x)\), whose norm of deviation \(\|u_1(x)-u_2(x)\|\) is arbitrarily small if \(\omega\) is sufficiently large. However, if the class of admissible solutions is a compact class \(\bar Z\), then the inverse mapping \(\bar U\to \bar Z\) will be stable \((^1)\). In other words, for any \(\varepsilon>0\) there exists a \(\delta(\varepsilon,\bar Z)\) such that from \(\|u_1-u_2\|<\delta(\varepsilon,\bar Z)\) it follows that \(\|z_1-z_2\|<\varepsilon\), if \(u_1,u_2\in \bar U=\{u(x)=A[x,z(s)],\, z\in \bar Z\}\), where \(\bar Z\) is a compact class of functions.
The construction of an algorithm for obtaining an approximate solution that uniformly approximates \(\bar z(s)\) is based on the following regularization principle: a family of functions \(z^\alpha(s)\), depending on a parameter \(\alpha\), will be called a regularized family of approximate solutions if: 1) \(u_\alpha(x)=A[x,z^\alpha(s)]\to \bar u(x)\) as \(\alpha\to 0\); 2) the functions \(z^\alpha(s)\), for any \(\alpha\), belong to a compact class of functions \(\bar Z\) containing \(\bar z(s)\). The regularized family of approximate solutions converges uniformly to \(\bar z(s)\) as \(\alpha\to 0\).
- Let a function \(\bar u(x)\) be given. Consider the functional
\[ M^\alpha[z(s), \bar u(x)] = N[z(s), \bar u(x)] + \alpha \Omega[z(s)], \tag{2} \]
where the functional \(N\) represents the quadratic deviation of \(\bar u(x)\) from \(A[x,z(s)]\)
\[ N[z(s), \bar u(x)] = \int_c^d [A[x,z(s)]-\bar u(x)]^2\,dx, \]
\[ \Omega[z(s)] = \int_a^b [k(s)z'(s)^2 + p(s)z^2(s)]\,ds \quad (k(s)>0,\; p(s)>0). \]
We shall call \(\Omega[z]\) a regularizing functional and \(M^\alpha\) a smoothing functional.
Theorem 1. For any function \(\bar u(x)\in L_2\) there exists a unique continuous, differentiable function \(z^\alpha(s)\) realizing the minimum of the smoothing functional \(M^\alpha[z(s),\bar u(x)]\).
The function \(z^\alpha(s)\) is determined by the Euler equation for the functional \(M^\alpha[z,\bar u]\):
\[ L^\alpha[z] = \alpha\left\{\frac{d}{ds}\left[k\frac{dz}{ds}\right]-pz\right\} -\left\{\int_a^b \bar K(s,\xi)z(\xi)\,d\xi-\bar b(s)\right\}=0,\quad z'(a)=z'(b)=0, \tag{3} \]
where
\[ \bar K(s,\xi)=\int_c^d K(\xi,s)\,K(\xi,\xi)\,d\xi,\qquad \bar b(s)=\int_c^d K(\xi,s)\bar u(\xi)\,d\xi. \]
With the aid of the Green’s function for the boundary-value problem
\[ L^\omega[z]=\frac{d}{ds}\left[k(s)\frac{dz}{ds}\right]-p(s)z(s)=f(s),\quad z'(a)=z'(b)=0, \tag{4} \]
defined by the Euler operator for the regularizing functional, equation (3) can be transformed into a Fredholm equation of the second kind, for which, when \(\alpha>0\), the homogeneous equation has only the trivial solution; hence the existence of \(z^\alpha(s)\) follows.
Theorem 2. If \(\bar z(s)\in \bar C_1\), \(u(x)=A[x,\bar z(s)]\), then for any \(\varepsilon>0\) there exists such an \(\alpha(\varepsilon,\bar z)\) that
\[ |z^\alpha(s)-\bar z(s)|<\varepsilon \]
for all \(\alpha<\alpha_0(\varepsilon,\bar z)\).
Indeed,
\[ M^\alpha[z^\alpha(s);\bar u(x)] \leq N[\bar z,\bar u] + \alpha\Omega[\bar z] = \alpha C^2 \quad (C^2=\Omega[\bar z]), \]
whence it follows that \(z^\alpha(s)\) satisfies the inequality
\[ 1)\quad \Omega[z(s)]\leq C^2, \]
which determines a compact class of functions \(\bar Z\), and also
\[ 2)\quad \|u^\alpha(x)-\bar u(x)\|\leq \alpha C \to 0 \quad \text{as } \alpha\to 0. \]
Hence theorem 2 follows.
Theorem 3. If \(\bar z\in \bar C_1\), then for any \(\varepsilon>0\) and any auxiliary numbers \(0<\gamma_1<\gamma_2\) there exists such a \(\delta_0(\varepsilon,\gamma_1,\gamma_2,\bar z)\) that if: 1) the norm of the deviation of the function \(u_\delta(x)\) from the function \(\bar u(x)\) is less than \(\delta\)
\[ \|u_\delta(x)-\bar u(x)\|<\delta; \]
2) \(\bar{\alpha}=\bar{\alpha}(\delta)\) satisfies the conditions
\[ \gamma_1 \leqslant \delta^2/\alpha \leqslant \gamma_2 \quad (\text{or } \delta^2/\gamma_2 \leqslant \alpha \leqslant \delta^2/\gamma_1), \]
then \(\widetilde z_{\delta}^{\,\bar{\alpha}}(s)\), realizing the minimum of the smoothing functional \(M^{\bar{\alpha}}[z,\widetilde u_\delta(x)]\), belongs to the \(\varepsilon\)-neighborhood of the function \(\bar z(s)\),
\[ \left|\widetilde z_{\delta}^{\,\bar{\alpha}}(s)-\bar z(s)\right|<\varepsilon \]
for \(\delta \leqslant \delta_0(\varepsilon,\gamma_1,\gamma_2,\bar z)\).
It is not difficult to verify by examples that the function \(\widetilde z_{\delta}^{\,\alpha}(s)\) corresponding to a fixed function \(\widetilde u_\delta(s)\), for small \(\delta\), as \(\alpha\to 0\), may leave the \(\varepsilon\)-neighborhood of \(\bar z(s)\).
- Let us pass to approximate methods for solving equation (1). Consider the method of finite differences. Take a mesh on \((a,b)\): \(s_j=jh-0.5h\) \((j=1,\ldots,n)\), and on \((c,d)\): \(x_i=ih_1-0.5h_1\) \((i=1,\ldots,m)\), where \(h=\frac{1}{n}(a-b)\) and \(h_1=\frac{1}{m}(c-d)\). Denote \(z_j=z(s_j)\), and let
\[ \sum_{j=1}^{n} K_{ij}z_jh = \int_a^b K(x_i,s)z(s)\,ds+O(h^\gamma) \]
be some quadrature formula of order \(\gamma\).
Consider the difference smoothing functional
\[ \widehat M_h^{\alpha}[\widehat z,\widehat u] = \sum_{i=1}^{m} \left\{ \sum_{j=1}^{n} K_{ij}\widehat z_jh-\widehat u_i \right\}^{2}h_1 + \alpha \sum_{j=1}^{n} \left\{ k_j(\widehat z_{j+1}-\widehat z_j)^2\frac{1}{h} + p_j\widehat z_j^{\,2}h \right\}, \]
where \(\widehat u=\{\widehat u_i\}\) is a given mesh function on \(\{x_i\}\), \(\widehat z=\{\widehat z_j\}\) is a mesh function on \(\{s_j\}\), and \(k_j>0,\ p_j>0\).
Analogously to the preceding, the following holds.
Theorem \(1'\). For any mesh function \(\widehat u\) and \(\alpha>0\) there exists a mesh function \(\widehat z^{\,\alpha}\) realizing the minimum of the smoothing functional \(\widehat M_h^{\alpha}[\widehat z,\widehat u]\).
The mesh function \(\widehat z^{\,\alpha}\) is determined from the system of equations
\[ \widehat L^{\alpha}[\widehat z] = \alpha \left\{ \frac{1}{h^2} \bigl[ k_j(\widehat z_{j+1}-\widehat z_j) - k_{j-1}(\widehat z_j-\widehat z_{j-1}) \bigr] - p_j\widehat z_j \right\} - \left\{ \sum_{l=1}^{n}\overline K_{jl}\widehat z_lh-\widehat b_j \right\} =0, \tag{3′} \]
\[ \widehat z_0=\widehat z_1,\qquad \widehat z_{n+1}=\widehat z_n, \]
where
\[ \overline K_{jl}=\sum_{i=1}^{m}K_{ij}K_{il}h_1, \qquad \widehat b_j=\sum_{i=1}^{m}K_{ij}\widehat u_i h_1, \]
and \(k_j\) and \(p_j\) are determined through \(k(x)\), \(p(x)\) by means of some homogeneous difference scheme converging to problem (4) (see \((^2)\)). In particular, for example, \(k_j=k(s_j+0.5h)\), \(p_j=p(s_j)\).
Theorem \(2'\). If \(z(s)\in \overline C_1\), then for any \(\varepsilon>0\) and any auxiliary numbers \(0<\gamma_1\leqslant\gamma_2\) there exist such \(\delta_0(\varepsilon,\gamma_1,\gamma_2,\bar z)\) and \(h_0(\varepsilon,\gamma_1,\gamma_2,\bar z)\) that if: 1) the norm of the deviation of the function \(\widetilde u_\delta(x)\) from \(\bar u(x)\) is less than \(\delta\):
\[ \|\widetilde u_\delta-\bar u\|<\delta; \]
2) \(\bar\alpha=\bar\alpha(\delta)\) satisfies the conditions
\[ \gamma_1 \leqslant \delta^2/\alpha \leqslant \gamma_2 \quad (\text{or } \delta^2/\gamma_2 \leqslant \alpha \leqslant \delta^2/\gamma_1), \]
then \(\bar z_{\delta}^{\alpha}(s)\), which realizes the minimum of the difference smoothing functional \(\hat M_h^\alpha[\hat z,\hat u_\delta]\), belongs to the \(\varepsilon\)-neighborhood of the function \(\bar z(s)\) for \(\delta \leqslant \delta_0(\varepsilon,\gamma_1,\gamma_2,\bar z)\), \(h < h_0(\varepsilon,\gamma_1,\gamma_2,\bar z)\).
Equation (3′) is an algorithm for solving equation (1), giving very effective results with the aid of electronic digital computers.
The construction of the functions \(z^\alpha(s)\) may also be carried out using expansions in series with respect to orthogonal systems.
The method set forth above is applicable to equations of the type
\[ A[x,z(s)] = u(x), \tag{1′} \]
where \(A[x,z(s)]\) is a bounded operator. If we denote
\[ \alpha(x,s)=A[x,\eta_s(\xi)], \qquad \eta_s(\xi)= \begin{cases} 1, & \xi \leqslant s,\\ 0, & \xi > s, \end{cases} \]
then equation (3) can be represented in the form
\[ \alpha\left\{k(s)z'(s)+\int_0^s p(\xi)z(\xi)\,d\xi\right\} - \left\{\int_c^d A[x,z(\xi)]\alpha(x,s)\,dx - \int_c^d \alpha(x,s)\bar u(x)\,dx\right\}=0, \]
\[ z'(a)=z'(b)=0. \]
The regularizing functional \(\Omega[z]\) may be chosen as a quadratic functional (not necessarily differential) so that the condition \(\Omega(z)\leqslant C\) determines a compact set and so that the Euler operator for \(\Omega(z)\) has a completely continuous inverse operator. This also applies to the case where the domain of definition of \(z(s)\) is a domain \(D\) of \(n\) dimensions (see the Sobolev–Kondrashev theorem\({}^{3}\)).
Smoothing functionals provide a convenient apparatus for solving equations of the second kind at an isolated point of the spectrum, as well as for solving nonlinear problems.
Received
17 IV 1963
CITED LITERATURE
\({}^{1}\) A. N. Tikhonov, Dokl. Akad. Nauk SSSR, 39, No. 5, 195 (1943); M. M. Lavrent’ev, Dokl. Akad. Nauk SSSR, 102, No. 2, 205 (1955); 106, No. 2, 389 (1956); 112, No. 2, 195 (1957). \({}^{2}\) A. N. Tikhonov, A. A. Samarskii, Zhurn. Vychisl. Matem. i Matem. Fiz., 1, issue 1, 5 (1961). \({}^{3}\) S. L. Sobolev, Some Applications of Functional Analysis in Mathematical Physics, Leningrad, 1950.