Abstract Generated abstract
The paper studies the stable solution of linear functional equations in Hilbert spaces when both the right-hand side and the operator are known only approximately. It formulates a Tikhonov-type regularization functional on a weakly closed convex admissible set, proves existence and uniqueness of its minimizer, and analyzes the dependence of residual and penalty terms on the regularization parameter. A discrepancy principle is established for choosing this parameter, including convergence of the regularized solution as data errors vanish and error estimates under additional source-type assumptions. The results are applied to integral equations with interval error bounds, leading to a uniquely defined generalized approximate solution and a discrete formulation as a quadratic programming problem.
Full Text
UDC 517.948.35
MATHEMATICS
V. A. MOROZOV
ON THE CHOICE OF A PARAMETER IN SOLVING FUNCTIONAL EQUATIONS BY THE REGULARIZATION METHOD
(Presented by Academician Yu. N. Rabotnov on 28 X 1966)
- Let \(H\) be a real Hilbert space, \(F\) a linear normed space, and \(A\) some linear bounded operator defined on \(H\) and mapping \(H\) into \(F\). We consider the problem
\[ Au=\bar f,\qquad \bar f\in F \tag{1} \]
of finding the function \(\bar u=R[\bar f;A]\in H\) satisfying equation (1). Suppose that the function \(\bar f\in A[H]\subset F\); the function \(\bar u\) is determined uniquely by the datum \(\bar f\). The collection \(\{\bar f;A\}\) will be called the initial data of problem (1).
Let \(S(A_h)=\{A_h,\ 0<h\le h_0\}\) be a family of linear bounded operators \(A_h\), defined on \(H\), such that \(\|A-A_h\|_{H\to F}\le \zeta(h)\to 0\) as \(h\to 0\). Any collection \(\{f_\delta;A_h\}\), \(f_\delta\in F\), \(\|f_\delta-\bar f\|_F<\delta\), \(A_h\in S(A_h)\), will be called approximate data of problem (1). We consider the problem of stable solution of equation (1), i.e., determination from the approximate data \(\{f_\delta;A_h\}\) of a function \(u_{\delta h}\in H\) such that \(\|\bar u-u_{\delta h}\|\to 0\) as \(\delta,h\to 0\), where \(\|\cdot\|\) denotes the norm in \(H\). Similar problems were considered in works \((^{1-5})\).
Suppose that it is known a priori that \(\bar u\in D\), where \(D\) is some weakly closed convex set of the space \(H\) (the case \(D=H\) is allowed). Define the parametric functional \((^1)\)
\[ \Phi_{\delta h}^{\alpha}[u]=\Phi^\alpha[u;f_\delta,A_h;u^*] =\|A_hu-f_\delta\|_F^2+\alpha\|u-u^*\|^2,\qquad u\in D, \tag{2} \]
where \(\alpha>0\) is a parameter, and \(u^*\in D\) is a prescribed function.
Theorem 1. There exists a unique function \(u_{\delta h}^{\alpha}\in D\) satisfying the relation
\[ \Phi_{\delta h}^{\alpha}[u_{\delta h}^{\alpha}] =\inf_{u\in D}\Phi_{\delta h}^{\alpha}[u]. \tag{3} \]
The proof is based on the inequality
\[ \alpha\|(u_1-u_2)/2\|\le \tfrac12\Phi_{\delta h}^{\alpha}[u_1] +\tfrac12\Phi_{\delta h}^{\alpha}[u_2] -\Phi_{\delta h}^{\alpha}[(u_1+u_2)/2], \qquad u_1,u_2\in H, \]
and is carried out analogously to work \((^3)\).
Define the functions
\[ \varphi_{\delta h}(\alpha)=\Phi_{\delta h}^{\alpha}[u_{\delta h}^{\alpha}], \qquad \gamma_{\delta h}(\alpha)=\|u_{\delta h}^{\alpha}-u^*\|^2, \]
\[ \rho_{\delta h}(\alpha)=\|A_hu_{\delta h}^{\alpha}-f_\delta\|_F^2. \]
Lemma 1. For every \(\alpha>0\) the function \(\varphi_{\delta h}(\alpha)\) is continuous, monotonically increasing, and
\[ \lim_{\alpha\to+\infty}\varphi_{\delta h}(\alpha)=\|A_hu^*-f_\delta\|_F^2. \]
Lemma 2. For any \(\alpha>0\) the function \(\gamma_{\delta h}(\alpha)\) is continuous and monotonically decreasing; moreover,
\[ \lim_{\alpha\to+\infty}\gamma_{\delta h}(\alpha)=0. \]
Lemma 3. For any \(\alpha>0\) the function \(\rho_{\delta h}(\alpha)\) is continuous, monotonically increasing, and takes values in the interval
\[ \bigl(\overline{\zeta}(h;\bar u)+\delta^2,\ \|A_hu^*-f_\delta\|_F^2\bigr], \qquad \overline{\zeta}(h;\bar u)=\|A_h\bar u-A\bar u\|_F. \]
Remark 1. If the range \(Q_{A_h}=A_h(H)\subseteq F\) of each operator in the family \(S(A_h)\) is everywhere dense in \(F\), then one may assert that the function \(\rho_{\delta h}(\alpha)\) takes values in the interval \((0,\|A_hu^*-f_\delta\|_F^2\). This is fulfilled, for example, if \(A_h\equiv E\) and the space \(H\) is embedded in \(F\) \((^6)\), i.e., for the problem of reconstructing functions \((^5)\).
From the stated assertions it follows easily:
Theorem 2 (discrepancy principle). Let, for any \(\delta\) and \(h\), \(0<\delta\le\delta_0\), \(0<h\le h_0\), the condition
\[ \kappa(\delta,h;\bar u,u^*)= \bigl(\overline{\zeta}(h;\bar u)+\delta\bigr)(1+\beta(\delta,h))^{1/2} <\|A_hu^*-f_\delta\|_F, \tag{4} \]
be satisfied, where \(\beta=\beta(\delta,h)\), \(\beta(0,0)=0\), is some positive bounded function continuous at the point \((0,0)\).
Then there exists at least one value of the regularization parameter \(\alpha=\alpha(\delta,h)\ge0\) such that
\[ \rho_{\delta h}(\alpha(\delta,h))=\kappa^2(\delta,h;\bar u,u^*), \tag{5} \]
and in this case
\[ \lim_{\delta,h\to0}\|u_{\delta h}-\bar u\|=0. \]
Remark 2. If \(Q_{A_h}\) is everywhere dense in \(F\), then in relation (4) one may set \(\beta(\delta,h)\equiv0\).
Remark 3. If the space \(F\) is Hilbert, then for sufficiently small \(\delta\) and \(h\) the value of the parameter \(\alpha=\alpha(\delta,h)\) is determined uniquely by condition (5).
Remark 4. If \(\zeta(h;\bar u)\le\delta\), then the discrepancy principle in fact does not depend on the sought solution \(\bar u=R[\bar f;A]\) and is quite effective.
We note that if problem (1) has a nonunique solution, then by \(\bar u=R[\bar f;A]\) one may understand the generalized normal solution \((^7)\) of this problem, which is uniquely determined by the formula
\[ \bar u=\operatorname{pr}_{N_A}u^*+\operatorname{pr}_{H_A}\widetilde u, \qquad \widetilde u=R[\bar f;A], \]
where \(N_A=\{u;\ Au=0\}\), \(H_A=H\dotminus N_A\).
The formulated theorem is proved analogously to Theorem 4 \((^5)\).
2. The following result is a refinement of Theorem 3 \((^5)\) and can serve as a basis for choosing suitable values of the regularization parameter, as well as for estimating the deviation of the regularized solution from the exact one, if some a priori information about the exact solution of problem (1) is available. Namely, the following is true.
Theorem 3. Let \(F\) be a unitary space, the element \(u^\alpha\) realize the lower bound of the functional \(\Phi^\alpha[u;\bar f,A;u^*]\), \(u\in H\), and the element \(u_\delta^\alpha\) of the functional \(\Phi^\alpha[u;f_\delta,A;u^*]\), \(u\in H\). Then
\[ \|u_\delta^\alpha-\bar u\|\le \omega(\alpha;\bar u,u^*)+\delta/\sqrt{\alpha}, \]
where \(\omega(\alpha;\bar u,u^*)=\|u^\alpha-\bar u\|\to0\) as \(\alpha\to0\). If \(u^*-\bar u=A^*v\), where \(v\in F\), then \(\omega(\alpha;\bar u,u^*)\le\sqrt{\alpha}\|v\|_F\), and if \(u^*-\bar u=A^*A\bar v\), \(\bar v\in H\), then \(\omega(\alpha;\bar u,u^*)\le\alpha\|\bar v\|\).
- Let the function \(\bar u=\bar u(x)\in W_2^{(1)}[a,b]\) \((^6)\)* be the (unique) solution of the integral equation
\[ K[u]\equiv A(x)u(x)+\int_a^b k(x,\xi)u(\xi)\,d\xi=\bar f(x),\qquad a\leq x,\xi\leq b, \tag{6} \]
where \(A=A(x)\), \(k=k(x,\xi)\), and \(\bar f=\bar f(x)\) are continuous functions of their arguments. Suppose that continuous functions \(\tilde f(x)\) and \(\delta(x)\geq 0\) are known and are related to \(\bar f(x)\) by
\[ |\bar f(x)-\tilde f(x)|\leq \delta(x). \tag{7} \]
Using some ideas of paper \((^9)\) and of the regularization method, we define the generalized approximate solution of equation (6) with approximate data \(\{\tilde f,K\}\) as the solution \(\tilde u(x)\) of the extremal problem
\[ \|\tilde u-u^*\|_{W_2^{(1)}}^2 = \inf_{u\in\Omega}\|u-u^*\|_{W_2^{(1)}}^2, \tag{8} \]
where the set \(\Omega\) is defined as follows:
\[ \Omega=\left\{ u\in W_2^{(1)};\ \left|A(x)u(x)+\int_a^b k(x,\xi)u(\xi)\,d\xi-\tilde f(x)\right| \leq \delta(x) \right\}. \]
It is obvious that the set \(\Omega\) is closed, convex, and nonempty \((\bar u\in\Omega\) by virtue of (7)).
Theorem 4. There exists a unique function \(\tilde u\in W_2^{(1)}\) realizing equality (8), i.e., the generalized approximate solution of equation (6) is uniquely determined by prescribing the functions \(\tilde f(x)\) and \(\delta(x)\) satisfying relation (7).
Theorem 5. Let \(\varepsilon>0\) be given. There exists \(\delta_0=\delta_0(\varepsilon)>0\) such that, if the relation \(\|\delta\|_{L_2}\leq \delta_0\) is satisfied, the generalized approximate solution of equation (6) will belong to the \(\varepsilon\)-neighborhood of the function \(\bar u=\bar u(x)\): \(\|\tilde u-\bar u\|_{W_2^{(1)}}<\varepsilon\).
Remark 5. If \(k(x,\xi)\equiv \delta(x-\xi)\), then we arrive at the problem of reconstructing a function \(\bar u\in W_2^{(1)}\). The function \(\tilde f(x)\) may be interpreted as an experimentally obtained function representing \(\bar u=\bar u(x)\) with some small error in \(L_2\). Equality (8) in this case expresses definite requirements on the process of processing experimental information. The validity of Theorems 4 and 5 is preserved.
- Let us write the extremal problem (8) in discrete form. Suppose that on the interval \([a,b]\) two grids of nodes \((n\geq m)\) are defined: \(\{x\}\): \(a\leq x_1<x_2<\cdots<x_i<x_{i+1}<\cdots<x_n\leq b\), \(\{\xi\}\): \(a\leq \xi_1<\xi_2<\cdots<\xi_j<\xi_{j+1}<\cdots<\xi_m\leq b\).
Let us write the approximate equality
\[ \int_a^b k(x,\xi)u(\xi)\,d\xi \simeq \sum_{j=1}^m \chi_j k(x,\xi_j)u_j, \]
where \(u_j=u(\xi_j)\); \(\chi_j\) are the coefficients of some quadrature formula, and define the set
\[ \Omega_h= \left\{ u_j,\ j=1,2,\ldots,m;\ \left|\sum_{j=1}^m \chi_j k_{ij}u_j-\tilde f_i\right| \leq \Delta_i,\ 1\leq i\leq n \right\}, \]
where \(k_{ij}=k(x_i,\xi_j)\), \(\tilde f_i=\tilde f(x_i)\), and \(\Delta_i\geq \delta_i\) are chosen so that \(\bar u_j=\bar u(\xi_j)\in\Omega_h\).
* The norm in the space \(W_2^{(1)}\) is defined by the relation \(\|\bar u\|_{W_2^{(1)}}=\|\bar u'\|_{L_2}^2+\|\sqrt q\,\bar u\|_{L_2}^2\), where \(q=q(x)>0\) is a continuous function.
Then we arrive at the following problem:
Find the quantities $\tilde u_j \in \Omega_h$ for which the condition
\[ \Phi[\tilde u_1, \tilde u_2, \ldots, \tilde u_m] = \inf_{u_j \in \Omega_h} \Phi[u_1, u_2, \ldots, u_m], \]
is satisfied,
\[ \Phi[u_1, u_2, \ldots, u_m] = \sum_{j=1}^{m-1} \left\{ \left( \frac{u_{j+1}-u_j}{\xi_{j+1}-\xi_j} \right)^2 + \frac{q_{j+1}u_{j+1}^2+q_j u_j^2}{2} \right\} (\xi_{j+1}-\xi_j), \]
i.e., to the problem of quadratic programming \((^{10},\,^{11})\). The presence of a priori constraints on the desired solution can in most cases be reflected in the definition of the set of admissible grid functions $\Omega_h$.
Moscow State University
named after M. V. Lomonosov
Received
19 X 1966
REFERENCES
- A. N. Tikhonov, DAN, 151, No. 3, 501 (1963); 153, No. 1, 49 (1963).
- I. N. Dombrovskaya, V. K. Ivanov, Siberian Mathematical Journal, 6, No. 3, 499 (1965).
- V. A. Morozov, Vestn. Mosk. Univ., Ser. Math. and Mech., No. 4, 13 (1965).
- V. A. Morozov, Zhurnal Vychislitel’noi Matematiki i Matematicheskoi Fiziki, 6, No. 1, 170 (1966).
- V. A. Morozov, DAN, 167, No. 3, 508 (1966).
- S. L. Sobolev, Some Applications of Functional Analysis in Mathematical Physics, L., 1950.
- A. N. Tikhonov, DAN, 163, No. 3, 591 (1965).
- S. G. Mikhlin, The Problem of the Minimum of a Quadratic Functional, M.–L., 1952.
- L. V. Kantorovich, Siberian Mathematical Journal, 3, No. 5, 701 (1962).
- G. P. Kuntsi, V. Krepl, Nonlinear Programming, M., 1965.
- G. Zoutendijk, Methods of Feasible Directions, IL, 1963.