Complexity for a class of elliptic ordinary integro-differential equations.

Consider the variational form of the ordinary integro-differential equation (OIDE) − u ″ + u + ∫ 0 1 q (⋅ , y) u (y) dy = f on the unit interval I , subject to homogeneous Neumann boundary conditions. Here, f and q respectively belong to the unit ball of H r (I) and the ball of radius M 1 of H s (I 2) , where M 1 ∈ [ 0 , 1). For ε > 0 , we want to compute ε -approximations for this problem, measuring error in the H 1 (I) sense in the worst case setting. Assuming that standard information is admissible, we find that the n th minimal error is Θ (n − min ⁡ { r , s / 2 }) , so that the information ε -complexity is Θ (ε − 1 / min ⁡ { r , s / 2 }) ; moreover, finite element methods of degree max ⁡ { r , s } are minimal-error algorithms. We use a Picard method to approximate the solution of the resulting linear systems, since Gaussian elimination will be too expensive. We find that the total ε -complexity of the problem is at least Ω (ε − 1 / min ⁡ { r , s / 2 }) and at most O (ε − 1 / min ⁡ { r , s / 2 } ln ⁡ ε − 1) , the upper bound being attained by using O (ln ⁡ ε − 1) Picard iterations. [ABSTRACT FROM AUTHOR]