Abstract Generated abstract
The paper studies the computation of all simple eigenvalues of a Fredholm integral operator whose moduli exceed a prescribed threshold, for kernels belonging to specified smoothness classes and under stability and separation assumptions. It develops deterministic approximation and iteration schemes based on finite representations of the kernel, then extends them to randomized kernel approximations that improve accuracy in probability for comparable information use. Complexity estimates are derived for Sobolev-type and mixed-smoothness classes, and lower-bound arguments show that the proposed methods are optimal in order, or optimal up to logarithmic factors, with respect to computational work or kernel information in the cases considered.
Full Text
UDC 518:517.948
MATHEMATICS
A. F. SHAPKIN
ON METHODS, OPTIMAL ON CLASSES OF FUNCTIONS, FOR COMPUTING THE EIGENVALUES OF A FREDHOLM INTEGRAL OPERATOR
(Presented by Academician A. N. Tikhonov on 12 VI 1968)
The paper considers the problem of finding all eigenvalues of a Fredholm integral operator, not smaller in modulus than a prescribed number, under the condition that they are simple. Both deterministic and nondeterministic algorithms are given for solving this problem on classes of kernel functions, optimal up to a logarithmic factor. In item \(1^\circ\) the precise formulation of the problem is given. In item \(2^\circ\) deterministic methods for its solution are considered. In item \(3^\circ\), on their basis, nondeterministic methods are constructed. In item \(4^\circ\) optimality is proved, up to a logarithmic factor, with respect to the amount of computational work or the information used about the kernel.
\(1^\circ\). Consider the class of Fredholm operators defined by the following requirements. Let a Banach space \(F\) be given, the imbedding operator of which into \(L_2\) is bounded by 1, and let positive \(M_1,\ldots,M_5;\delta\) be given. We require that \(\|K\|_F \le M_1\), where \(K\) is the kernel of our integral operator \(A\), acting in the space \(L_2(\Omega_s)\); \(\Omega_s\) is the unit \(s\)-dimensional cube. In addition, we assume that \(A\) has no more than \(1+M_2\) eigenvalues \(\lambda\) such that \(|\lambda|^{-1} \le M_3+M_1^{-1}\), and all these eigenvalues are simple and
\[ |(\varphi,\psi)|^{-1}\|\varphi\|\cdot\|\psi\| \le 1+M_4, \]
\[ \|(A-\lambda)^{-1}\| \le M_5+M_3+M_1^{-1}. \tag{1} \]
Here \(\varphi\) is the eigenfunction of the operator \(A\) corresponding to the eigenvalue \(\lambda\); \(\psi\) is the eigenfunction of the adjoint operator \(A^*\), corresponding to the eigenvalue \(\lambda\); the operator \(A-\lambda\) is considered on the orthogonal complement to the function \(\varphi\), and the scalar product and norm are understood in the sense of \(L_2\). (The last remark also applies to what follows, unless the contrary is stipulated.) (1) guarantees the stability of problem (1). Finally, \(A\) is assumed not to have eigenvalues such that
\[ 0<|\lambda|^{-1}-M_3-M_1^{-1}<\delta . \tag{2} \]
Let us note that for every operator with a kernel from \(F\), all of whose eigenvalues maximal in modulus are simple, there exist corresponding \(M_1,\ldots,M_5;\delta\). The problem is posed of computing, with a prescribed accuracy \(\varepsilon>0\), on our class all eigenvalues \(\lambda\) of the operator \(A\) such that \(|\lambda|^{-1}\le M_3+M_1^{-1}\).
\(2^\circ\). Let natural numbers \(N_1,\ldots,N_{2s}\) be given. Then the functions
\[ e_{jk}^{N}(x)=\prod_{l=1}^{2s} e_{j_l k_l}^{N_l}\,x(l), \qquad j_l=1,\ldots,N_l;\ k_l=0,1,\ldots, \]
form a complete orthonormal system in \(L_2(\Omega_{2s})\), if we set
\[
e_{jk}^{N}(x)=(2N)^{1/2}Q_k(2Nx-2j+1)\quad \text{for }0<Nx-j+1<1,
\]
\[
e_{jk}^{N}(x)=0\quad \text{otherwise},
\]
where \(Q_k\) is the Legendre polynomial of degree \(k\). Here and below
\(y=(y_1,\ldots,y_{2s})\).
With the aid of S. L. Sobolev’s integral formula \((^2)\), it can be shown that the kernel \(K\) of any operator from our class with \(F=\widetilde W_2^r,\ r>s\), using its values at \(N^{2s}\) points, can be approximated in the norm of the space \(L_2\) by a linear combination \(K_N\) of the functions \(e_{jk}^{N}\) with \(N_l=N\), with accuracy up to \(O(N^{-r})\); moreover, computing its coefficients requires \(O(N^{2s})\) arithmetic operations (not counting the work of computing the values of the kernel \(K,\ N=1,2,\ldots\)). Here and below the constant in the \(O\)-symbol depends only on \(F;\ M_1,\ldots,M_5;\ \delta\). One can indicate an \(N_0\), depending on \(F;\ M_1,\ldots,M_5;\ \delta\), such that, starting from the approximate eigenvalues and functions of the operator \(A_0\) with kernel \(K_{N_0}\) and of the operator \(A_0^*\), we can, by iteration, solve economically the problem posed in item \(1^\circ\). This iterative process is constructed, by analogy with the corresponding process \((^3)\) for Fredholm equations of the second kind, as follows.
By the finite-dimensionality of the operator \(A_0\) and condition (2), one can, in a finite number of arithmetic operations, find with error \(N_0^{-r}\) its eigenvalues corresponding to the desired eigenvalues of the operator \(A\), as well as the corresponding eigenfunctions of the operators \(A_0\) and \(A_0^*\) (the error is measured in the norm of the space \(L_2\)).
Let
\[ A_0\varphi_0\approx \lambda_0\varphi_0,\qquad A_0^*\psi_0\approx \bar{\lambda}_0\psi_0,\qquad \|\varphi_0\|=\|\psi_0\|=1. \]
If \(\lambda_k,\ \varphi_k,\ \psi_k\) are known, then \(\lambda_{k+1},\ \varphi_{k+1},\ \psi_{k+1}\) are computed as follows: first the residuals are found,
\[ \pi_k=(A_k-\lambda_k)\varphi_k,\qquad \rho_k=(A_k^*-\bar{\lambda}_k)\psi_k, \]
and the quantity
\[ \gamma_k=(\varphi_k,\psi_k)\|\varphi_k\|^{-1}\|\psi_k\|^{-1}; \]
then the corrections are found,
\[ \xi_k=(A_0-\lambda_0)^{-1}P_0\pi_k,\qquad \eta_k=(A_0^*-\bar{\lambda}_0)^{-1}P_0^*\rho_k, \]
where
\[ P_0=1-\gamma_0^{-1}\|\varphi_0\|^{-1}\|\psi_0\|^{-1}\psi_0\otimes\varphi_0; \]
finally,
\[ \varphi_{k+1}=\varphi_k-\xi_k,\qquad \psi_{k+1}=\psi_k-\eta_k, \]
\[ \lambda_{k+1}=\lambda_k+\gamma_k^{-1}(\pi_k,\psi_k)\|\varphi_k\|^{-1}\|\psi_k\|^{-1}. \]
Here \(A_k\) is the operator with kernel \(K_{N_k}\). In inverting the operator \(A_0-\lambda_0\) we proceed as if \(\lambda_0\) were an exact eigenvalue of the operator \(A_0\). If we take \(N_k=N_0 2^k\), then after
\[ k=1+\bigl[\log_2(1+N_0^{-1}\varepsilon^{-1/r})\bigr] \]
iterations, requiring \(O(1+\varepsilon^{-2s/r})\) arithmetic operations, we shall have
\[ |\lambda-\lambda_k|=O(\varepsilon), \]
since \(N_0\) is chosen so that each iteration reduces the error by at least \(2^r\) times.
If \(F=S_2^r,\ r>2^{-1}\), is the space \((^4)\), then every kernel from our class, using its values at \(O(2^n n^{2s-1})\) points, can be approximated in the norm of the space \(L_2\) by a linear combination of the functions \(c_{jk}^{N}\) with accuracy up to \(O(2^{-rn}n^{2s-1})\), and computing its coefficients requires \(O(2^n n^{2s-1})\) arithmetic operations, \(n=1,2,\ldots\). This is easily shown by the method of tensor products \((^5)\). An iteration analogous to the one described, in \(O(2^n n^{3s-1})\) operations, reduces the initial error to
\[ O(2^{-rn}n^{2s-4}). \]
3°. Let us return to the case \(F=W_2^r\), and now consider nondeterministic methods. Introduce the random kernel (cf. \((6)\)):
\[ \widetilde K_N=K_N+N^{-2s}\sum_j R_N(X_j^N)\sum_k \xi_k^N(X_j^N)e_{jk}^N, \]
where \(R_N=K-K_N\), \(X_j^N\) are pairwise independent random points uniformly distributed in the supports of the functions \(e_{jk}^N\), and the summation is carried out over those values of the indices that occur in the expression for \(K_N\). We note that the computation of the Fourier coefficients of the kernel \(\widetilde K_N\) requires \(O(N^{2s})\) arithmetic operations. By means of the formulas of perturbation theory it is easy to show that, m.o., \(|\lambda-\widetilde\lambda_N|=O(N^{-r-s})\), where \(\widetilde\lambda_N\) is the eigenvalue of the operator \(\widetilde A_N\) with kernel \(\widetilde K_N\), corresponding to the eigenvalue \(\lambda\) of the operator \(A\). If in the iteration described above we take \(A_k=\widetilde A_N\), \(k=1,2,\ldots\), leaving \(A_0\) as before, then after
\[ k=1+[\log_2(1+N_0^{-1}N^{1+s/r})] \]
steps, requiring \(O(1+N^{2s}\ln N)\) operations, with probability not less than \(1-\sigma\), \(\sigma>0\), we shall have \(|\widetilde\lambda_N-\lambda_k|=O(N^{-r-s})\) for \(N\geq N_0\sigma^{-1/r}\). On the other hand, \(|\lambda-\widetilde\lambda_N|=O(\sigma^{-1}N^{-r-s})\) with probability not less than \(1-\sigma\). Therefore, with probability not less than \(1-2\sigma\), we have \(|\lambda-\lambda_k|=O(\sigma^{-1}N^{-r-s})\) for \(N\geq N_0\sigma^{-1/r}\).
Let us now pass to the case \(F=\overline S_2^r\), when
\[ \|K\|_F=\sum_m |c_m|^2(\overline m_1\cdots \overline m_{2s})^{2r},\qquad \overline m_l=\max(1,|m_l|). \]
Here \(c_m=(K,e_m)\), \(e_m(x)=\exp(2\pi i mx)\), and \(r>2^{-1}\) may also be fractional. Every kernel from our class, using its values at \(O(2^n n^{2s-1})\) points, can be approximated in the norm of the space \(L_2\) by a linear combination \(K^n\) of the functions \(e_m\) with accuracy up to \(O(2^{-rn}n^{2s-1})\), and the computation of the coefficients of this linear combination requires \(O(2^n n^{2s-1})\) arithmetic operations \((^5,^8)\). Construct the random kernel
\[ \widetilde K^n=K^n+2^{-n}\sum_{p=1}^{2^n} R^n(X_p)\sum_m e_{-m}(X_p)e_m, \]
where \(R^n=K-K^n\), \(X_p\) are pairwise independent random points uniformly distributed in \(\Omega_{2s}\), and the summation is carried out over those values of the indices that occur in the expression for \(K^n\). The computation of the Fourier coefficients of the kernel \(\widetilde K^n\) requires \(O(4^n n^{2s-1})\) arithmetic operations. Carrying out the iteration by analogy with the preceding case—it requires only \(O(2^n n^{3s})\) operations—we shall have, with probability not less than \(1-\sigma\),
\[ |\lambda-\lambda_k|=O(\sigma^{-1}2^{-rn-n/2}n^{6s-2}) \]
for \(n\geq n_0-2r^{-1}\log_2\sigma\). The number \(n_0\) plays here the same role as \(N_0\) did earlier.
4°. Let us now see how much the proposed methods differ from optimal ones on the classes considered. Suppose a deterministic method is given for computing the eigenvalues of a Fredholm operator, using information about its kernel at a finite number of points. Construct from these nodes the function \(u_0\) in the same way as is done in § 8 of \((^7)\), and put
\[ K=\pm u_0+2^{-1}(M_1+(M_3+M_1^{-1})^{-1}); \]
here the function \(u_0\) may be assumed symmetric and such that
\[ \|u_0\|_F\leq \min\{2^{-1}(M_1-(M_3+M_1^{-1})^{-1},\ (M_5+M_3+M_1^{-1})^{-1},\ (M_3+M_1^{-1}+\delta)^{-1}\}. \]
These requirements ensure that the kernel \(K\) belongs to our class. Let \(\lambda\) be the maximal eigenvalue of the operator with kernel \(K\), and let \(\varphi\) be the corresponding eigenfunction. Obviously, \(\|\varphi-1\|=O(\|u_0\|)\),
if \(\|\varphi\|=1\) and \((\varphi,1)>0\). We have
\[ \lambda=(K,k)=(\pm u_0,k)+2^{-1}(1,k)(M_1+(M_3+M_1^{-1})^{-1}). \]
where \(k\) is the kernel of the operator \(\varphi\otimes\varphi\); therefore every method for computing the eigenvalue \(\lambda\) generates a method for computing the quantity \((\pm u_0,k)\), and the absolute error of the two methods differs by \(O(\|u_0\|^2)\). Consequently, the lower estimates for the amount of computational work in computing eigenvalues and integrals of kernels on our class coincide, since \(\|k-1\|=O(\|u_0\|)\). This is precisely what is meant by the optimality of the deterministic methods considered, up to a logarithmic factor (in the case \(F=W_2^r\), even optimality in order). If the method is nondeterministic, then instead of \(\pm u_0\) one must consider the collection of functions \(w_j\) from § 9 of the same paper. We note that in the case \(F=S_2^r\) the proposed nondeterministic method is optimal up to a logarithmic factor only with respect to the quantity of information used about the kernel, and not with respect to the amount of computational work.
In conclusion, the author expresses gratitude to N. S. Bakhvalov for posing the problem and for scientific guidance.
Moscow State University
named after M. V. Lomonosov
Received
6 VI 1968
CITED LITERATURE
- M. K. Gavurin, DAN, 96, No. 6, 1093 (1954).
- S. L. Sobolev, Some Applications of Functional Analysis in Mathematical Physics, L., 1950.
- K. V. Emelyanov, A. M. Il’in, Zhurn. vychisl. matem. i matem. fiz., 7, No. 4, 905 (1967).
- S. M. Nikol’skii, DAN, 146, No. 3, 542 (1962).
- A. S. Smolyak, DAN, 148, No. 5, 1042 (1963).
- S. M. Ermakov, V. G. Zolotukhin, Probability Theory and Its Applications, 5, issue 4, 473 (1960).
- N. S. Bakhvalov, in: Numerical Methods for Solving Differential and Integral Equations and Quadrature Formulas, “Nauka,” 1964, p. 5.
- J. W. Cooley, J. W. Tukey, Math. Comp., 19, 297 (1965).