The complexity of two-point boundary-value problems with analytic data (Q2365848)

The author considers the \(\varepsilon\)-complexity of a model two-point boundary value problem \(-u''+u = f\) in \(I=(-1,1)\) with natural boundary conditions \(u'(-1)=u'(1)=0\), and the class \(F\) consists of analytic functions \(f\) bounded by 1 on a disk of radius \(\rho\geq 1\) centered at the origin. The \(\varepsilon\)-complexity means the infimum of the cost of the solution which attains the error estimate less than or equal to \(\varepsilon\) under appropriate norm for any \(f\), information of \(f\) and algorithm. Assuming that the evaluation of any function in \(F\) at any point in \(I\) has cost \(c\), he finds that if \(\rho>1\), then the \(\varepsilon\)- complexity is of order \(\log(\varepsilon^{-1})\) as \(\varepsilon\to 0\), and there is a finite element \(p\)-method whose cost is optimal to within a constant factor. If \(\rho=1\), then the \(\varepsilon\)-complexity is found to be of order \(\log^ 2(\varepsilon^{-1})\) as \(\varepsilon\to 0\), and there is a finite element \((h,p)\)-method whose cost is optimal to within a constant factor. The proofs are supported by some error bounds in the approximation and interpolation theories.