×

Average errors for zero finding: Lower bounds for smooth or monotone functions. (English) Zbl 0809.65044

An error analysis of zero finding for monotone or \(C^ r(0; I)\) functions is presented. The errors for methods using \(n\) function or derivative evaluations are defined with respect to \(r\)-fold Wiener or Ulam measures and are understood in the root or residual sense. The author shows that it is impossible to obtain superlinear convergence even for classes of smooth functions which have only simple zeros.
Besides new results, the article presents a good introduction to the problem.

MSC:

65H05 Numerical computation of solutions to single equations
65G50 Roundoff error
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] Bauer, H.,Probability theory and elements of measure theory. Academic Press, New York, 1981. · Zbl 0466.60001
[2] Chay, S. C.,On quasi-Markov random fields. J. Multivariate Anal.2 (1972), 14–76. · Zbl 0228.60017 · doi:10.1016/0047-259X(72)90010-3
[3] Dowell, M. andJarrat, P.,The Pegasus method for computing the root of an equation. BIT12 (1971), 503–508. · Zbl 0249.65027 · doi:10.1007/BF01932959
[4] Graf, S., Mauldin, R. D., andWilliams, S. C.,Random homeomorphisms. Adv. Math.60 (1986), 239–359. · Zbl 0596.60005 · doi:10.1016/S0001-8708(86)80001-9
[5] Graf, S. andNovak, E.,The average error of quadrature formulas for functions of bounded variation. Rocky Mountain J. Math.20 (1990), 707–716. · Zbl 0721.41041 · doi:10.1216/rmjm/1181073094
[6] Graf, S., Novak, E., andPapageorgiou, A.,Bisection is not optimal on the average. Numer. Math.55 (1989), 481–491. · Zbl 0671.65038 · doi:10.1007/BF01396051
[7] King, R. F.,An improved Pegasus method for root finding. BIT13 (1973), 423–427. · Zbl 0266.65038 · doi:10.1007/BF01933405
[8] Kung, H. T.,The complexity of obtaining starting points for solving operator equations by Newton’s method. In:Analytic computational complexity (J. F. Traub, ed.). Academic Press, New York, 1976, pp. 35–57. · Zbl 0344.65036
[9] Lee, D. andWasilkowski, G. W.,Approximation of linear functionals on a Banach space with a Gaussian measure. J. Complexity2 (1986), 12–43. · Zbl 0602.65036 · doi:10.1016/0885-064X(86)90021-X
[10] Novak, E.,Average-case results for zero finding. J. Complexity5 (1989), 489–501. · Zbl 0691.65030 · doi:10.1016/0885-064X(89)90022-8
[11] Novak, E.,Quadrature formulas for monotone functions. Proc. Amer. Math. Soc.115 (1992), 59–68. · Zbl 0760.41019 · doi:10.1090/S0002-9939-1992-1086337-X
[12] Novak, E. andRitter, K.,Average errors for zero finding: lower bounds. Math. Z.211 (1992), 671–686. · Zbl 0759.65019 · doi:10.1007/BF02571454
[13] Novak, E. andRitter, K.,Some complexity results for zero finding for univariate functions. J. Complexity9 (1993), 15–40. · Zbl 0771.65024 · doi:10.1006/jcom.1993.1003
[14] Pan, V.,Complexity of computations with matrices and polynomials. SIAM Review34 (1992), 225–262. · Zbl 0757.65051 · doi:10.1137/1034049
[15] Parthasarathy, K. R.,Probability measures on metric spaces. Academic Press, New York, 1967. · Zbl 0153.19101
[16] Renegar, J.,On the efficiency of Newton’s method in approximating all zeros of a system of complex polynomials. Math. Oper. Res.12 (1987), 121–148. · Zbl 0618.65038 · doi:10.1287/moor.12.1.121
[17] Sacks, J. andYlvisaker, D.,Statistical design and integral approximation. In:Proc. 12th Bienn. Seminar Can. Math. Congr. 1969 (R. Pyke, ed.). Can. Math. Soc., Montreal, 1970, pp. 115–136.
[18] Shub, M. andSmale, S.,Complexity of Bezout’s theorem I, II, III. Preprint, 1992.
[19] Sikorski, K.,Study of linear information for classes of polynomial equations. Aequationes Math.37 (1989), 1–14. · Zbl 0677.65049 · doi:10.1007/BF01837941
[20] Sikorski, K.,Optimal solution of nonlinear equations. J. Complexity1 (1985), 197–209. · Zbl 0609.65036 · doi:10.1016/0885-064X(85)90011-1
[21] Smale, S.,On the efficiency of algorithms of analysis. Bull. Amer. Math. Soc., New Ser.,13 (1985), 87–121. · Zbl 0592.65032 · doi:10.1090/S0273-0979-1985-15391-1
[22] Smale, S.,Algorithms for solving equations. In:Proc. Intern. Congr. Math. 1986, Berkeley (A. M. Gleason, ed.). Amer. Math. Soc., Providence, 1987, pp. 115–136.
[23] Speckman, P.,L p approximation of autoregressive Gaussian processes. Report, University of Oregon, Department of Statistics, Eugene, 1979.
[24] Traub, J. F., Wasilkowski, G. W., andWoźniakowski, H.,Information-based complexity. Academic Press, New York, 1988. · Zbl 0654.94004
[25] Vakhania, N. N., Tarieladze, V. I., andChobanyan, S. A.,Probability distributions on Banach spaces. Reidel, Dordrecht, 1987.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.