Average errors for zero finding: Lower bounds (Q1204311)

Up to now, lower bounds for the average error for methods solving nonlinear problems of numerical analysis were not known. The authors study the nonlinear problem of zero finding for continuous functions \(f\) of one variable. They assume that \(f\) is sign changing at the endpoints of an interval and consider the average with respect to the Brownian bridge. They prove that the average error of optimal methods converges linearly in \(n\), where \(n\) is the number of knots and the error is with respect to the root or residual criterion. This result shows that the linear convergence, which holds for the root criterion in the worst case, cannot be beaten in the average case.