Abstract
The optimums-gradient method for minimizing a positive definite quadratic functionf(x) onE n has long been known to converge fors ≧+1. For theses the author studies the directions from which the iteratesx k approach their limit, and extends tos>1 a theory proved byAkaike fors=1. It is shown thatf (x k ) can never converge to its minimum value faster than linearly, except in degenerate cases where it attains the minimum in one step.
Similar content being viewed by others
References
Akaike, Hirotugu: On a successive transformation of probability distribution and its application to the analysis of the optimum gradient method. Ann. Inst. Statist. Math. Tokyo11, 1–16 (1959)
Arms, R. J.: On the asymptotic behavior of the method of steepest descent. Unpublished manuscript, 5 March 1957. Presented to Association for Computing Machinery, Houston, Texas, June 1957
Bauer, F. L., andA. S. Householder: Moments and characteristic roots. Numer. Math.2, 42–53 (1960).
Birman, M. Š.: Nekotorye ocenki dlja metoda naiskoreišego spuska. Uspehi Matem. Nauk (N.S.)5, 152–155 (1950)
Daniel, J. W.: The conjugate gradient method for linear and nonlinear operator equations. SIAM J. Numer. Anal.4, 10–26 (1967).
Faddeev, D. K., andV. I. Faddeeva: Computational methods of linear algebra. Translated byRobert C. Williams. San Francisco: W. H. Freeman and Co. 1963.
Forsythe, G. E.: Solving linear algebraic equations can be interesting. Bull. Amer. Math. Soc.59, 299–329 (1953).
——, andT. S. Motzkin: Asymptotic properties of the optimum gradient method (abstract). Bull. Amer. Math. Soc.57, 183 (1951).
Khabaza, I. M.: An iterative least-square method suitable for solving large sparse matrices. Comp. J.6, 202–206 (1963)
Meinardus, G.: Über eine Verallgemeinerung einer Ungleichung vonL. V. Kantorowitsch. Numer. Math.5, 14–23 (1963).
Ostrowski, A. M.: Solution of equations and systems of equations. Second edition. New York and London: Academic Press 1966.
Stiefel, E.: Über einige Methoden der Relaxationsrechnung. Z. Angew. Math. Physik3, 1–33 (1952).
—— Kernel polynomials in linear algebra and their numerical applications. Pp.1–22 of Further contributions to the solution of simultaneous linear equations and the determination of eigenvalues. National Bureau of Standards AppliedMathematics Series 49. Washington, D. C.: U. S. Govt. Printing Office 1958.
Szegö, G.: Orthogonal polynomials. Revised edition. New York: American Mathematical Society 1959
Author information
Authors and Affiliations
Additional information
Dedicated to ProfessorHeinrich Brinkmann for his seventieth birthday.
Research sponsored by the U.S. Office of Naval Research under project NR 044211.
Rights and permissions
About this article
Cite this article
Forsythe, G.E. On the asymptotic directions of thes-dimensional optimum gradient method. Numer. Math. 11, 57–76 (1968). https://doi.org/10.1007/BF02165472
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF02165472