Average errors for zero finding: Lower bounds
type: Item
instance of: scholarly article
title: Average errors for zero finding: Lower bounds
zbMATH Open document ID: 0759.65019
DOI: 10.1007/BF02571454
author: Erich Novak
author: Klaus Ritter
published in: Mathematische Zeitschrift
publication date: 1993-03-07T00:00:00Z
full work available at URL: https://eudml.org/doc/174467
review text: 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.
Mathematics Subject Classification ID: 65H05
zbMATH DE Number: 126421
zbMATH Keywords: lower bounds
zbMATH Keywords: average error
zbMATH Keywords: zero finding
zbMATH Keywords: continuous functions
zbMATH Keywords: Brownian bridge
zbMATH Keywords: linear convergence
MaRDI profile type: Publication
cites work: Q5560061
cites work: Random homeomorphisms
cites work: Bisection is not optimal on the average
cites work: Average-case results for zero finding
cites work: Q4028238
cites work: Q5645216
cites work: Approximation and optimization on the Wiener space
cites work: Q4040428
cites work: Average case complexity of multivariate integration
description: scientific article; zbMATH DE number 126421