For which error criteria can we solve nonlinear equations?

DOI10.1016/0885-064X(86)90017-8MaRDI QIDQ1086984zbMATH OpenOpenAlexFDO

Authors B. George

Publication date 1986

Published in Journal of Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0885-064x(86)90017-8

zbMATH Keywords

adaptive information almost optimal information error criterion root criterion worst performance

Mathematics Subject Classification ID

Numerical computation of solutions to single equations (65H05) Analysis of algorithms and problem complexity (68Q25)

Review text

For the solution of an equation \(f(x)=0\), involving a real function f on an interval [a,b], the information on f is assumed to consist of sequential (adaptive) evaluations of arbitrary functionals. The error of an algorithm based on these evaluations is defined by its worst performance. For the root criterion as error measure it is shown that there does not exist an algorithm for finding a point x such that \(| x-\alpha | \leq \epsilon\) where \(\alpha\) is a zero of f and \(\epsilon <(b-a)/2\). This holds for arbitrary information and infinitely differentiable f with simple zeros, but without assuming f(a)f(b)\(\leq 0\). For the residual criterion some almost optimal information and algorithm is given and it is shown that for n functional evaluations the residual at the computed point x satisfies \(f(x)=O(n^{-r})\) as \(n\to \infty\), where r defines the smoothness class of f. These results are then generalized to a more general error criterion.

Recommendations

Cites work

Cited in

(7)

This page was built for publication: For which error criteria can we solve nonlinear equations?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1086984)