Accession Number : ADA277565


Title :   An Introduction to the Conjugate Gradient Method that Even an Idiot Can Understand


Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE


Personal Author(s) : Shewchuk, Jonathan R


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/a277565.pdf


Report Date : 07 Mar 1994


Pagination or Media Count : 62


Abstract : The Conjugate Gradient Method is the most prominent iterative method for solving sparse systems of linear equations. Unfortunately, many textbook treatments of the topic are written so that even their own authors would be mystified, if they bothered to read their own writing. For this reason, an understanding of the method has been reserved for the elite brilliant few who have painstakingly decoded the mumblings of their forebears. Nevertheless, the Conjugate Gradient Method is a composite of simple, elegant ideas that even stupid people can understand. Of course, a reader as intelligent as yourself will learn them almost effortlessly. The idea of quadratic forms is introduced and used to derive the methods of Steepest Descent, Conjugate Directions, and Conjugate Gradients. Eigenvectors are explained and used to examine the convergence of the Jacobi Method, Steepest Descent, and Conjugate Gradients. Other topics include preconditioning and the nonlinear Conjugate Gradient Method. I have taken pains to make this article easy to read. Sixty-two illustrations are provided. Dense prose is avoided. Concepts are explained in several different ways. Most equations are coupled with an intuitive interpretation.


Descriptors :   *MATRICES(MATHEMATICS) , *POLYNOMIALS , *NUMERICAL METHODS AND PROCEDURES , LINEAR SYSTEMS , NUMERICAL QUADRATURE , STEEPEST DESCENT METHOD , GRADIENTS , CONVERGENCE , EIGENVECTORS


Subject Categories : Numerical Mathematics


Distribution Statement : APPROVED FOR PUBLIC RELEASE