# Conjugate gradient methods

Author: Erik Zuehlke

Stewards: Dajun Yue and Fengqi You

## Contents |

# Introduction

The conjugate gradient method is a mathematical technique that can be useful for the optimization of both linear and non-linear systems. This technique is generally used as an iterative algorithm, however, it can be used as a direct method, and it will produce a numerical solution. Generally this method is used for very large systems where it is not practical to solve with a direct method. This method was developed by Magnus Hestenes and Eduard Stiefel[1].

# The Conjugate Gradient Model for Linear Systems

There are a set of linear equations that we want to solve represented in vector notation as:

**Ax**=**b**

Here **A** is an *n* x *n* known symmetric, real, and positive definite matrix, **b** is a known vector and we want to solve for the vector **x**. A unique solution to this problem is represented by the vector **x***.

There is a set of *n* conjugate vectors where . Within the set the solution **x*** can be expanded out.

So and from this

By substituting the above equations it is shown that:

Finally the coeffcients

This method solves the given system of linear equations by finding *n* conjugate vectors, and then computing the coeffcients [2,3].

# Non-Linear Conjugate Gradient Method

This is a non-linear form of the Conjugate Gradient Method and will be used to show the iterative nature of the method.

Lets start with a quadratic function

A residual should be calculated and in the non-linear case the residual is always the negative of the gradient The search direction should then be calculated using the Gram-Schmidt conjugation of the residuals[4]. A line search is then used and this is more difficult than in the linear case. A value of is found so that is minimized. This is accomplished by ensuring the gradient is orthogonal to the search direction.

To find the value of there are multiple methods. Two of the better equations are the Fletcher-Reeves (which is used in linear GC) and the Polak-Ribiere method. The former converges only if initial guess is sufficiently close to the desired minimum, while the latter can sometimes cycle infinitely but often converges more quickly.

Fletcher-Reeves:

Polak-Ribiere:

A way to guarantee the Polak-Ribiere method to converge is by choosing max{}this restarts the method if the Polak-Ribiere method becomes less than zero, and then a new search direction can be chosen[4].

# Numerical Example of the method

This will be an example of the linear method.

**Ax**=**b** is a linear system and it is described by

An initial guess of is made.

The residual will be found which is computed from the formula **r**_{0} = **b** - **Ax**_{0}. so in our case **r**_{0} =

As this is the first iteration the residual vector will be used as the initial search direction. Now α_{0} is calculated using the equation

With our first alpha found we can now compute

With the new x now calculated one must calculate the next residual using the following equation:

With our new residual we now must compute **p**_{1} but first we need to find β_{0}.

With β_{0} now the next search direction **p**_{1} can be calculated:

With this it is the last of the unique computations. To continue on in the problem one would solve for α_{2} using the same equation as was for α_{1}. Then x_{2} would be found. One would then continue on finding new residuals and search vectors until the solution converges.

# References

[1] Straeter, T. A. "On the Extension of the Davidon-Broyden Class of Rank One, Quasi-Newton Minimization Methods to an Infinite Dimensional Hilbert Space with Applications to Optimal Control Problems". NASA Technical Reports Server. NASA. Retrieved 10 October 2011.

[2] Wikipedia page for Conjugate Gradient Methods

[3] Hestenes, Magnus R.; Stiefel, Eduard (December 1952). "Methods of Conjugate Gradients for Solving Linear Systems". Journal of Research of the National Bureau of Standards 49 (6)

[4] Shewchuk, J. R. "An Introduction to the Conjugate Gradient Method Without the Agonizing Pain" 1994, August 4. Carnegie Mellon Univerisity