On optimality of Krylov's information when solving linear operator equations (Q1179025)

The paper deals with the optimality of Krylov's information in solving linear operator equations for certain problem classes. Let \(B\) be the space of bounded linear operators on an \(n\)-dimensional Hilbert space \(H\). The pair \((A,b)\in B\times H\) is called a problem associated with the linear equation \(Ax=b\), \(A\in B\), \(b\in H\). Suppose that the only information available during the solution process consists of \(b\) being known a priori and the fact that at each step any vector from \(H\) can be multiplied on our choice of \(A\). For a class \(U\) of problems and each method \(P\) that solves the problems from \(U\), let \(x_ P(k,A,b)\) denote the \(k\)th approximate solution found by the method when applied to the problem \((A,b)\). Then the worst-case efficiency estimate for the method with respect to \(U\) can be obtained via the \(k\)th approximates. Inturn, the best possible efficiency estimate can be established by considering the worst-case efficiencies for a family of methods. The paper establishes that if the number of steps \(k\) is not greater than \((n-3)/2\), then the best possible efficiency estimate corresponds to Chebyshev-type methods for a certain variety of problem classes. In particular, the most powerful (adaptive) information for these classes is the Krylov's information. It may be noted that the earlier results of Nemirovskij and Yudin (1983) and Chou (1987) show this information to be ``almost optimal''.