Some complexity results for zero finding for univariate functions (Q2365840)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Some complexity results for zero finding for univariate functions |
scientific article |
Statements
Some complexity results for zero finding for univariate functions (English)
0 references
29 June 1993
0 references
The paper gives a survey of information based complexity results for zero finding. One section presents worst case and probabilistic results for complex polynomials. Thereafter the emphasis is on zero finding for univariate, at least continuous functions with a change of sign on some interval. Asymptotic results on best possible orders of convergence are given. Then error bounds are discussed that hold for all functions in the given class \(F\) after a fixed number of steps in the worst case setting. Finally the average case setting is considered using an expected error and cost with respect to a probability measure on \(F\). In this setting methods are also studied which use a varying number of knots depending on the particular function in \(F\).
0 references
real number model
0 references
information based complexity
0 references
zero finding
0 references
worst case
0 references
complex polynomials
0 references
best possible orders of convergence
0 references
error bounds
0 references
average case
0 references