From: Niels L Ellegaard Subject: Re: conjugate gradient Date: Mon, 17 Jan 2000 15:10:02 +0100 Newsgroups: sci.math.num-analysis Summary: How does the conjugate gradient method work? "Konstrüksiyon ABD" wrote: > > is there anyone who can send me a document explaining the theoretical > basis of conjugate gradient optimization method? I have used the following 'http://www.stanford.edu/class/cs205/notes/book/node26.html' -- Niels L Ellegaard 'http://dirac.ruc.dk/~gnalle/' ============================================================================== From: Victor Eijkhout Subject: Re: conjugate gradient Date: 17 Jan 2000 14:24:00 -0500 Newsgroups: sci.math.num-analysis "Konstrüksiyon ABD" writes: > is there anyone who can send me a document explaining the theoretical > basis of conjugate gradient optimization method? Here. Let A be a matrix and R a block of independent vectors, satisfying with H an upper Hessenberg matrix AR = RH Let R be mutually orthogonal, ie, R^tR=D, then R^tAR=DH. Since R^tAR is symmetric, H must be tridiagonal. You can deduce the coefficients from the orthogonality relations. Usually CG is presented as coupled two-term recurrences. For this write H=LDinvU, so that ARUD=RL, and write P=RU. This gives APD=RL, P=RU I've left out the detail about having to normalise R such that H has unit lower diagonal; consider it an exercise for the reader. There. Btw, Some people derived CG from minimisation properties. In the above approach (which I stole from Householder) they follow as corollary. -- Victor Eijkhout "There ought to be limits to freedom" [G.W. Bush, reacting to www.gwbush.com] ============================================================================== From: Jive Dadson Subject: Re: conjugate gradient Date: 17 Jan 2000 17:43:27 EST Newsgroups: sci.math.num-analysis Konstrüksiyon ABD wrote: > > is there anyone who can send me a document explaining the theoretical > basis of conjugate gradient optimization method? Check this out: http://www.cs.cmu.edu/~jrs/jrspapers.html "An Introduction to the Conjugate Gradient Method Without the Agonizing Pain" is a very nice paper, the cutesy title not withstanding. I particularly recommend it to people who, like me, don't have a strong background in linear algebra. The author consistently strives to make the subject matter totally clear -- a very rare quality indeed. There's a good deal of prerequisite subject matter covered. If you don't need the review, you can skip over that part. By the way, I've written a non-linear conjugate gradient function optimizer. It turned out to be quite an extensive undertaking, despite the apparent simplicity of the underlying algorithm. "The Devil is in the details," as they say. A non-linear optimizer has a lot of tricky details. Jive