** Next:** Conjugate direction
** Up:** KRYLOV SUBSPACE ITERATIVE METHODS
** Previous:** Null space and iterative

Before we can understand why the conjugate-direction method is so fast,
we need to see why the
steepest-descent methodsteepest descent
is so slow.
Imagine yourself sitting on the edge of a circular bowl.
If you jump off the rim, you'll slide straight to the bottom
at the center.
Now imagine an ellipsoidal bowl of very large ellipticity.
As you jump off the rim, you'll first move in the
direction of the gradient.
This is not towards the bottom at the center of the ellipse
(unless you were sitting on the major or minor axis).
We can formalize the situation.
A parametric equation for a line is
where is the parameter for moving on the line.
The process of selecting is called ``line search."
Think of a two-dimensional example
where the vector of unknowns has just two components, *x*_{1} and *x*_{2}.
Then the size of the residual vector can be
displayed with a contour plot in the plane of (*x*_{1},*x*_{2}).
Our ellipsoidal bowl has ellipsoidal contours of constant altitude.
As we move in a line across this space by adjusting ,equation(45)
gives our altitude.
This equation has a unique minimum because it is a parabola in .As we approach the minimum,
our trajectory becomes tangential to a contour line in (*x*_{1},*x*_{2})-space.
This is where we stop.
Now we compute our new residual and we compute the new gradient
.OK, we are ready for the next slide down.
When we turn ourselves from "parallel to a contour line"
to the direction of which is "perpendicular to that contour",
we are turning .Our path to the bottom of the bowl will be made of many segments,
each turning from the previous.
We will need an infinite number of such steps to reach the bottom.
It happens that the amazing conjugate-direction method
would reach the bottom in just two jumps
(because (*x*_{1},*x*_{2}) is a two dimensional space.)
Missing figure (ls-sawtooth) A search path for steepest descent.

** Next:** Conjugate direction
** Up:** KRYLOV SUBSPACE ITERATIVE METHODS
** Previous:** Null space and iterative
Stanford Exploration Project

4/27/2004