108
5. Solution of Linear Equation Systems
A is symmetric and its eigenvalues are positive; such a matrix is called positive definite. (Most matrices associated with problems in fluid mechanics are
not symmetric or positive definite so we will need to generalize this method
later.) For
equivalent
F =
positive definite matrices, solving the system of equations (5.1) is
to the problem of finding the minimum of
with respect to all the $i; this may be verified by taking the derivative of F
with respect to each variable and setting it equal to zero. A way to convert the
original system into a minimization problem that does not require positive
definiteness is to take the sum of the squares of all of the equations but this
introduces additional difficulties.
The oldest and best known method for seeking the minimum of a function
is steepest descents. The function F may be thought of as a surface in (hyper)space. Suppose we have some starting guess which may be represented as a
point in that (hyper-)space. At that point, we find the steepest downward
path on the surface; it lies in the direction opposite to the gradient of the
function. We then search for the lowest point on that line. By construction,
it has a lower value of F than the starting point; in this sense, the new
estimate is closer to the solution. The new value is then used as the starting
point for the next iteration and the process is continued until it converges.
Unfortunately, while it is guaranteed to converge, steepest descents often
converges very slowly. If the contour plot of the magnitude of the function F
has a narrow valley, the method tends to oscillate back and forth across that
valley and many steps may be required to find the solution. In other words,
the method tends to use the same search directions over and over again.
Many improvements have been suggested. The easiest ones require the
new search directions to be as different from the old ones as possible. Among
these is the conjugate gradient method. We shall give only the general idea
and a description of the algorithm here; a more complete presentation can
be found in the book by Golub and van Loan (1990).
The conjugate gradient method is based on a remarkable discovery: it
is possible to minimize a function with respect to several directions simultaneously while searching in one direction a t a time. This is made possible
by a clever choice of directions. We shall describe this for the case of two
directions; suppose we wish to find values of cq and a2 in
which minimize F; that is, we try to minimize F in the p1 - p2 plane. This
problem can be reduced t o the problem of minimizing with respect to p1
and p2 individually provided that the two directions are conjugate in the
following sense:
5. Solution of Linear Equation Systems
A is symmetric and its eigenvalues are positive; such a matrix is called positive definite. (Most matrices associated with problems in fluid mechanics are
not symmetric or positive definite so we will need to generalize this method
later.) For
equivalent
F =
positive definite matrices, solving the system of equations (5.1) is
to the problem of finding the minimum of
with respect to all the $i; this may be verified by taking the derivative of F
with respect to each variable and setting it equal to zero. A way to convert the
original system into a minimization problem that does not require positive
definiteness is to take the sum of the squares of all of the equations but this
introduces additional difficulties.
The oldest and best known method for seeking the minimum of a function
is steepest descents. The function F may be thought of as a surface in (hyper)space. Suppose we have some starting guess which may be represented as a
point in that (hyper-)space. At that point, we find the steepest downward
path on the surface; it lies in the direction opposite to the gradient of the
function. We then search for the lowest point on that line. By construction,
it has a lower value of F than the starting point; in this sense, the new
estimate is closer to the solution. The new value is then used as the starting
point for the next iteration and the process is continued until it converges.
Unfortunately, while it is guaranteed to converge, steepest descents often
converges very slowly. If the contour plot of the magnitude of the function F
has a narrow valley, the method tends to oscillate back and forth across that
valley and many steps may be required to find the solution. In other words,
the method tends to use the same search directions over and over again.
Many improvements have been suggested. The easiest ones require the
new search directions to be as different from the old ones as possible. Among
these is the conjugate gradient method. We shall give only the general idea
and a description of the algorithm here; a more complete presentation can
be found in the book by Golub and van Loan (1990).
The conjugate gradient method is based on a remarkable discovery: it
is possible to minimize a function with respect to several directions simultaneously while searching in one direction a t a time. This is made possible
by a clever choice of directions. We shall describe this for the case of two
directions; suppose we wish to find values of cq and a2 in
which minimize F; that is, we try to minimize F in the p1 - p2 plane. This
problem can be reduced t o the problem of minimizing with respect to p1
and p2 individually provided that the two directions are conjugate in the
following sense: