SOME EFFICIENT ALGORITHMS FOR SOLVING SYSTEMS OF NONLINEAR EQUATIONS

RICHARD P. BRENT

In memory of George Forsythe

Abstract

We compare the Ostrowski efficiency of some methods for solving systems of nonlinear equations without explicitly using derivatives. The methods considered include the discrete Newton method, Shamanskii’s method, the two-point secant method, and Brown’s methods. We introduce a class of secant methods and a class of methods related to Brown’s methods, but using orthogonal rather than stabilized elementary transformations. The idea of these methods is to avoid finding a new approximation to the Jacobian matrix of the system at each step, and thus increase the efficiency. Local convergence theorems are proved, and the efficiencies of the methods are calculated. Numerical results are given, and some possible extensions are mentioned.

Comments

Only the Abstract is given here. The full paper appeared as [1] and was reprinted in [3, pages 275–292]. A preliminary version appeared as [2].

References

1. R. P. Brent, “Some efficient algorithms for solving systems of nonlinear equations”, SIAM J. Numerical Analysis 10 (1973), 327–344 (George E. Forsythe memorial issue). MR 48#10096, CR 17#29965, Zbl 258.65051. rpb014.

2. R. P. Brent, On maximizing the efficiency of algorithms for solving systems of nonlinear equations, Report TR RC 3725, IBM T. J. Watson Research Laboratory, Yorktown Heights, New York (February 1972), 33 pp. rpb014pr.

3. R. P. Brent, Topics in computational complexity and the analysis of algorithms, Report TR-CS-80-14, DCS, ANU, October 1980, 375 pp. (D. Sc. thesis). rpb062.

Computer Centre, Australian National University, Canberra, Australia

1991 Mathematics Subject Classification. Primary 65H10; Secondary 65F25, 65Y20. Key words and phrases. Nonlinear equations, Brown’s method, Conte’s method, Ostrowski efficiency,

secant method, Shamanskii’s method, orthogonal factorization.

The author received his Ph.D. in Computer Science in 1971 from Stanford University under the direction of Professors Forsythe and Golub.

Most of the work in this paper was performed while the author was visiting the IBM Thomas J. Watson Research Center.

The author thanks Dr. P. Wolfe and the referees for many helpful suggestions. Received by the editors January 13, 1972. Copyright \begin{matrix}c \\ ◯ \end{matrix} 1973, SIAM. Comments \begin{matrix}c \\ ◯ \end{matrix} 1993, R. P. Brent.

rpb014a typeset using AMS-L^{A}TEX