On information complexity of certain classes of operator equations

From MaRDI portal





Let \(e_1,e_2,\ldots,e_m,\ldots\) be some orthonormal basis in a Hilbert space \(X\) and let \(P_m\) be the orthogonal projector on \({\text{span}}\{e_1,e_2,\ldots,e_m\}\). Denote by \(X^r, 0<r<\infty,\) the linear subspace of \(X\) equipped with the norm \(\|f\|_{X^r}=\|f\|_X+\|D_rf\|_X\), where \(D_r\) is some linear operator from \(X^r\) to \(X\) such that for any \(m=1,2,\ldots\) \(\|I-P_m\|_{X^r\to X}\leq c_rm^{-r}\). The article is devoted to obtaining the exact order of information complexity for the class \(\Psi^{r,s}_\gamma\) of equations \(z=Hz+f\), where \[ \begin{aligned} H\in{\mathcal H}^{r,s}_\gamma := & \{H: X\to X^r, H^*: X\to X^s, \|(I-H)^{-1}\|_{X\to X}\leq\gamma_0,\\ & \|H\|_{X\to X^r}\leq\gamma_1,\;\|H^*\|_{X\to X^s}\leq\gamma_2,\;\|(D_rH)^*\|_{X\to X^r}\leq\gamma_3\},\\ & \gamma=(\gamma_0,\gamma_1,\gamma_2,\gamma_3),\end{aligned} \] and \(f\) belongs to the unit ball \(X^r_1\) of \(X^r\). Let \(E_N(\Psi^{r,s}_\gamma,X)\) be the minimal error which one is able to guarantee on the class \(\Psi^{r,s}_\gamma\) after the execution of no more than \(N\) arithmetic operations on the values of informations functionals. The following statement is the main result of this article: If for the pretabulated width \(\Delta_N(X^r_1,X)\) proposed by \textit{K. I. Babenko} [Foundations of numerical analysis. Moskva: ``Nauka (1986; Zbl 0624.65001)] we have the estimate \(\Delta_N(X^r_1,X)\geq cN^{-r}\) for \(N=1,2,\ldots\), then \(E_N(\Psi^{r,s}_\gamma,X)\asymp N^{-r}\) for \(0<r,s<\infty\). Moreover, the author constructs some special algorithm realizing the optimal estimate.











This page was built for publication: On information complexity of certain classes of operator equations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4940421)