Computational Physics

A5 Discretisation 565

with

λi=

gi·gi

gi·Hhi

; (A.23a)

γi=−

gi+ 1 ·Hhi

hi·Hhi

. (A.23b)

For this algorithm, the following properties can be verified:

(i) gi·gi+ 1 =0 for alli.
(ii)hi+ 1 ·Hhi=0, for alli.
(iii)gi+ 1 ·hi=0 for alli(this is equivalent to(A.16)).
(iv)gi·gj=0 for alli=j.
(v)hi·Hhj=0 for alli=j.
The proof of these statements will be considered in Problem A.2. It is now easy
to derive the following alternative formulas forλiandγi:

λi=

gi·hi

hi·Hhi

; (A.24a)

γi=

gi+ 1 ·gi+ 1

gi·gi

. (A.24b)

For an arbitrary (i.e. nonquadratic) function, the conjugate gradient method will
probably be less efficient. However, it is expected to perform significantly better
than the steepest descent method, in particular close to the minimum wherefcan be
approximated well by a quadratic form. A problem is that the above prescription can-
not be used directly as we do not know the matrixH. However, in this caseλican be
found from a line minimisation:xi+ 1 should be such that it is a minimum offalong
the linexi+λihi, in other wordshi·∇f(xi+λihi)=0. For a quadratic function as
considered above, this condition does indeed reduce to (A.24a); for a general func-
tion we use the bisection minimisation or Brent’s method. We know then the value
ofxi+ 1. The gradientsgi+ 1 can be calculated directly asgi+ 1 =−∇f(xi+ 1 ).We
usegi+ 1 andgi, together with equation(A.24b)to findγi+ 1 , and use this in(A.22b)
to findhi+ 1. We see that the function values and gradients offsuffice to construct
a sequence of directions which in the case of a quadratic function are conjugate.

A5 Discretisation

In the equations of physics, most quantities are functions of continuous variables.
Obviously, it is impossible to represent such functions numerically in a computer
since real numbers are always stored using a finite number of bits (typically 32
or 64) and therefore only a finite number of different real numbers is available.
But even storing a function for all arguments allowed by the computer resolution is