Proof: Let X* minimize the quadratic function Q(X). Then
Q(X*)=B+A X*=0 (6.32)
Given a point X and a set of linearly independent directions S ,S ,…,S ,constants can always be found such that
X*= X + (6.33)
where the vectors S ,S ,…,S have been used as basis vectors. If the directions S are A conjugate and none of them is zero, the S , can easily be shown to be linearly independent and the can be determined as follows.
Equations (6.32) and (6.33) lead to
B+A X +A( )=0 (6.34)
Multiplying this equation throughout by S ,we obtain
S (B+A X )+ S A( )=0 (6.35)
Equation (6.35) can be rewritten as
(B+A X ) S + S A S =0 (6.36)
that is,
=- (6.37)
Now consider an iterative minimization procedure starting at point X ,and successively minimizing the quadratic Q(X) in the directions S ,S ,…,S ,where these directions satisfy Eq. (6.27). The successive points are determined by the relation
X =X + S , i=1 to n (6.38)
where is found by minimizing Q (X + S )so that S Q(X )=0 is equivalent to =0 atY= X
=
where y are the components of Y= X
S Q(X )=0 (6.39)
Since the gradient of Q at the point X , is given by
Q(X )=B+A X (6.40)
Eq. (6.39) can be written as
S {B+A(X + S )}=0 (6.41)
This equation gives
=- (6.42)
From Eq. (6.38), we can express X as
X =X + (6.43)
so that
X AS = X AS +
= X AS (6.44)
using the relation (6.27). Thus Eq. (6.42) becomes
=-(B+AX ) (6.45)
which can be seen to be identical to Eq. (6.37). Hence the minimizing step lengths are given by or . Since the optimal point X* is originally expressed as a sum of n quantities which have been shown to be equivalent to the minimizing step lengths, the minimization process leads to the minimum point in n steps or less. Since we have not made any assumption regarding X and the order of S ,S ,…,S , the process converges in n steps or less, independent of the starting point as well as the order in which the minimization directions are used.