Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-11-25T10:09:07.807Z Has data issue: false hasContentIssue false
  • English
  • Français

Some high-order zero-finding methods using almost orthogonal polynomials

Published online by Cambridge University Press:  17 February 2009

Richard P. Brent
Richard P. Brent
Affiliation:
Computer Centre, Australian National University, Canberra, Australia.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Some multipoint iterative methods without memory, for approximating simple zeros of functions of one variable, are described. For m > 0, n ≧ 0, and k satisfying m + 1 ≧ k > 0, there exist methods which, for each iteration, use one evaluation of f, f′, … f(m) followed by n evaluations of f(k), and have order of convergence m + 2n + 1. In particular, there are methods of order 2(n + 1) which use one function evaluation and n + 1 derivative evaluations per iteration. These methods naturally generalize the known cases n = 0 (Newton's method) and n = 1 (Jarratt's fourth-order method), and are useful if derivative evaluations are less expensive than function evaluations. To establish the order of convergence of the methods we prove some results, which may be of independent interest, on orthogonal and “almost orthogonal” polynomials. Explicit, nonlinear, Runge-Kutta methods for the solution of a special class of ordinary differential equations may be derived from the methods for finding zeros of functions. The theoretical results are illustrated by several numerical examples.

Type
Research Article
Information
The ANZIAM Journal , Volume 19 , Issue 1 , June 1975 , pp. 1 - 29
Copyright
Copyright © Australian Mathematical Society 1975

References

[1]Abramowitz, M. and Stegun, I. A., Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, National Bureau of Standards, Washington, D. C., (1964).Google Scholar
[2]de Boor, C. W. R. and Swartz, B., ‘Collocation at Gaussian points’, SIAM J. Numer. Anal., 10 (1973), 582–606.CrossRefGoogle Scholar
[3]Brent, R. P., Algorithms for Minimization without Derivatives, Prentice-Hall, Englewood Cliffs, New Jersey (1973).Google Scholar
[4]Brent, R. P., ‘Some efficient algorithms for solving systems of nonlinear equations’, SIAM J. Numer. Anal., 10 (1973), 327–344.CrossRefGoogle Scholar
[5]Brent, R. P., Efficient methods for finding zeros of functions whose derivatives are easy to evaluate, Computer Science Dept., Carnegie-Mellon Univ., Pittsburgh, Pennsylvania, (1974).Google Scholar
[6]Brent, R. P., Computer Solution of Nonlinear Equations, Academic Press, (to appear).Google Scholar
[7]Brent, R. P. and Brent, E. M., ‘Efficient computation of inverse distribution functions’, (in preparation).Google Scholar
[8]Brent, R. P., Winograd, S. and Wolfe, P., ‘Optimal iterative processes for root-finding’, Numer. Math. 20 (1973), 327–341.CrossRefGoogle Scholar
[9]Butcher, J. C., ‘On the attainable order of Runge-Kutta methods’, Math. Comp., 19 (1965), 408–417.CrossRefGoogle Scholar
[10]Davis, P. J., Interpolation and Approximation, Blaisdell, New York, (1963).Google Scholar
[11]Henrici, P., Discrete Variable Methods in Ordinary Differential Equations, Wiley, New York, (1962).Google Scholar
[12]Isaacson, E. and Keller, H. B., Analysis of Numerical Methods, Wiley, New York, (1966).Google Scholar
[13]Jarratt, P., ‘Some efficient fourth order multipoint methods for solving equations’, BIT 9 (1969), 11–124.CrossRefGoogle Scholar
[14]Jarratt, P., ‘A review of methods for solving nonlinear algebraic equations in one variable’, in Numerical Methods for Nonlinear Algebraic Equations (Rabinowitz, P., ed.), Gordon and Breach, New York, (1970), pp.1–26.Google Scholar
[15]Kacewicz, B., ‘An integral-interpolatory iterative method for the solution of scalar equations’, Computer Sci. Dept., Carnegie-Mellon Univ., Pittsburg, Pennsylvania, (1975).CrossRefGoogle Scholar
[16]King, R. F., ‘Runge-Kutta methods with constrained minimum error bounds’, Math. Comp., 20 (1966), 386–391.CrossRefGoogle Scholar
[17]King, R. F., ‘A fifth-order family of modified Newton methods’, BIT 11 (1971), 409–412.CrossRefGoogle Scholar
[18]King, R. F., ‘Tangent methods for nonlinear equations’, Numer. Math. 18 (1972), 298–304.CrossRefGoogle Scholar
[19]Kizner, W., ‘A numerical method for finding solutions of nonlinear equations’, J. SIAM 12 (1964), 424–428.Google Scholar
[20]Kung, H. T. and Traub, J. F., ‘Optimal order of one-point and multipoint iteration’, J. ACM, 21 (1974), 643–651.CrossRefGoogle Scholar
[21]Kung, H. T. and Traub, J. F., ‘Computational complexity of one-point and multipoint iteration’, in Complexity of Real Computation (Karp, R., ed.) American Math. Soc., New York, (1973).Google Scholar
[22]Kung, H. T. and Traub, J. F., ‘Optimal order and efficiency for iterations with two evaluations’ Computer Sci. Dept., Carnegie-Mellon Univ., Pittsburgh, Pennsylvania, (1973).Google Scholar
[23]Kutta, W., ‘Beitrag zur näherungsweisen Integration totaler Differentialgleichungen’, Z. Math. Phys. 46 (1901), 435–452.Google Scholar
[24]Micchelli, C. A. and Rivlin, T. J., ‘Numerical integration rules near Gaussian quadrature’, Report RC4387, IBM Research Center, Yorktown Heights, New York, (1973).CrossRefGoogle Scholar
[25]Nørsett, S. P., ‘One-step methods of Hermite type for numerical integration of stiff systems’, BIT 14 (1974), 63–77.CrossRefGoogle Scholar
[26]Ortega, J. M. and Rheinboldt, W. C., Iterative Solution of Nonlinear Equations in Several Variables, Academic Press, New York. (1970).Google Scholar
[27]Osborne, M. R., ‘Minimising truncation error in finite difference approximations to ordinary differential equations’, Math. Comp. 21 (1967), 135–145.CrossRefGoogle Scholar
[28]Osborne, M. R., ‘Collocation, difference equations, and stitched function representations’, in Topics in Numerical Analysis (Miller, J. J. H., ed., Academic Press, (1974).Google Scholar
[29]Ostrowski, A. M., Solution of Equations in Euclidean and Banach Spaces (3rd ed. of Solution of Equations and Systems of Equations), Academic Press, New York (1973).Google Scholar
[30]Shanks, E. B., ‘Solutions of differential equations by evaluations of functions’, Math. Comp. 20 (1966),21–38.CrossRefGoogle Scholar
[31]Szegö, G., Orthogonal Polynomials, AMS Colloquium Publication, Vol. 23 (1959), American Math. Soc., New York.Google Scholar
[32]Traub, J. F., Iterative Methods for the Solution of Equations, Prentice-Hall, Englewood Cliffs, New Jersey, (1964).Google Scholar
[33]Wilkinson, J. H., Rounding Errors in Algebraic Processes, HMSO, London, (1963).Google Scholar
[34]Wozniakowski, H., ‘Maximal stationary iterative methods for the solution of operator equations’, SIAM J. Numer. Anal., 11 (1974a), 934–949.CrossRefGoogle Scholar
[35]Wozniakowski, H., ‘Generalized information and maximal order of iteration for operator equations’. SIAM J. Numer. Anal., 12 (1975), 121–135.CrossRefGoogle Scholar
[36]Wozniakowski, H., Properties of maximal order methods for the solution of equations, Computer Science Dept., Carnegie-Mellon Univ., Pittsburgh, Pennsylvania, (1975).Google Scholar
[37]Wozniakowski, H., Private Communication, (1975b) (January).Google Scholar
[38]Brent, R. P., ‘A class of optimal-order zero-finding methods using derivative evaluations’, in Analytic Computational Complexity (Traub, J. F., ed.), Academic Press, New York, (1975).Google Scholar
[39]Meersman, R., ‘Optimal use of information in certain iterative processes’, in Analytic Computational Complexity (Traub, J. F., ed.), Academic Press, New York, (1975).Google Scholar