Iterative Methods for Solving Sets of Equations



Iterative Methods for Solving Sets of Equations

2.4.2 The Steepest Descent Method

If you move in the opposite direction of the steepest ascent you follow the steepest descent path. You may find the minimum of a function f(x,y) starting at point 0 as shown in Figure 2.4-4 using the steepest descent method. In this method you can move in the opposite direction of the initial gradient until f(x,y) stops decreasing, that is, becomes level along your direction of travel. This stopping point (1) becomes the starting point where (f is reevaluated and a new direction is followed. The process is repeated until the bottom is reached.

[pic]

Figure 2.4-4 A graphical depiction of the method of steepest descent.

The steepest descent method to find the minimum can be applied to solve a system of nonlinear equations of the form

f1(x1, x2, (, xn) = 0,

f2(x1, x2, (, xn) = 0,

[pic] [pic]

fn(x1, x2, (, xn) = 0.

This is due to the fact that the system of nonlinear equations has a solution at x = (x1, x2, (, xn) precisely when the function g defined by

g(x1, x2, (, xn) = [pic][ fi(x1, x2, (, xn)]2

has a minimum value of zero. g can also be expressed as a product of two vectors

g = f(f T

where f = [f1 f2 ( fn] and f T is the transpose of f. The method of steepest descent will generally converge linearly to the solution. The method will converge even with a poor initial guess therefore it is often used to find starting approximation for other techniques that can converge faster. A strategy for the method of steepest descent can be outlined as follows:

1. Evaluate g at an initial approximation x(0).

2. Determine a direction form x(0) using the gradient of g.

3. Move to a new appropriate position x(1) so that g(x(1)) < g(x(0)).

4. Repeat steps 2-4 with x(0) replaced by x(1).

The details procedure for the method of steepest descent is discussed in the next example.

Example 2.4-2

Use the method of steepest descent with the initial guess x = [0 0 0] to obtain the solutions to the following equations2

f1(x1, x2, x3) = 3x1 ( cos(x2 x3) ( [pic] = 0

f2(x1, x2, x3) = [pic] ( 81(x2 + 0.1)2 + sin x3 + 1.06 = 0

f2(x1, x2, x3) = [pic] + 20x3 + [pic] = 0

Solution

1. Evaluate g at an initial approximation x(0).

x(0) = [0 0 0]; f = [f1 f2 f3]

g = f(f T = [f1 f2 f3][pic] = f12 + f22 + f32 = 111.975

2. Determine a direction form x(0) using the gradient of g.

(g(x) = [pic][pic] + [pic][pic] + [pic][pic]

Note: The variable used in Matlab program will be within the bracket {} for example (g(x) {delg}.

(g(x) = [2f1[pic] + 2f2[pic] + 2f3[pic];

2f1[pic] + 2f2[pic] + 2f3[pic];

2f1[pic] + 2f2[pic] + 2f3[pic]]

(g(x){delg} = 2JT( f T = 2[pic][pic] = [pic]

The magnitude of the gradient at x(0) = [0 0 0] is

|(g(x)|{zo} = { (g12 + (g22 + (g32}1/2 = {(g(x)T((g(x)}1/2

Evaluate the unit vector in the direction of steepest ascent (descent)

z = (g(x)/ |(g(x)|

3. Move to a new appropriate position x(1) so that g(x(1)) < g(x(0)).

The direction of greatest decrease in the value of g at x is the direction given by ( (g(x), therefore x(1) is given by

x(1) = x(0) ( ((g(x)

[pic]

Figure 2.4-5 A typical behavior of g in the direction of steepest descent.

where ( is to be determined. The procedure is to fit a quadratic to three points ((1, g1), ((2, g2), and ((3, g3) then choose ( so that g is a minimum in the direction of steepest descent. The steps are

a) Let (1 = 0 at x(0), therefore g1 = g(x(0)).

b) Let (3 = 1 and evaluate g3 = g(x(0) ( (3z)

c) If g3 > g1, let (3 = (3/2 and repeat step (b)

d) Let (2 = (3/2 and evaluate g2 = g(x(0) ( (2z)

The quadratic through three points ((1, g1), ((2, g2), and ((3, g3) has the form

P(() = g1 + h1( + h3((( ( (2)

where h1 = [pic], h2 = [pic], and h3 = [pic]

At the location where [pic] = h1 + 2 h3( ( h3(2 = 0 ( (0 = 0.5((2 ( [pic])

e) Evaluate g0 = g(x(0) ( (0z)

Since a quadratic through three points can have a minimum or a maximum as shown in Figure 2.4-6, ( is chosen so that g is the lowest value between g0 and g3 as follows:

f) If g0 < g3 then ( = (0 else ( = (3

[pic][pic]

Figure 2.4-6 A quadratic through three points can have a minimum or a maximum.

4. Repeat steps 2-4 with x(0) replaced by x(1).

Table 2.4-2 lists the Matlab program with values of x for 10 iterations.

Table 2.4-2 Matlab program for the steepest descent method -------------

%

% Steepest Descent Method

% Example 1, pg.420 Faires and Burden

%

f1='3*x(1)-cos(x(2)*x(3))-.5';

f2='x(1)*x(1)-81*(x(2)+.1)^2+sin(x(3))+1.06';

f3= 'exp(-x(1)*x(2))+20*x(3)+10*pi/3-1' ;

% Initial guess

%

x=[0 0 0];

f=[eval(f1) eval(f2) eval(f3)];

g1=f*f';

for i=1:10

Jt=[3 2*x(1) -x(2)*exp(-x(1)*x(2))

x(3)*sin(x(2)*x(3)) -162*(x(2)+.1) -x(1)*exp(-x(1)*x(2))

x(2)*sin(x(2)*x(3)) cos(x(3)) 20];

% Gradient vector

%

delg=2*Jt*f';

zo=sqrt(delg'*delg);

% Unit vector in the steepest descent

%

z=delg/zo;

xs=x;a3=1;x=x-a3*z';

f=[eval(f1) eval(f2) eval(f3)];

g3=f*f';

while g3>g1

a3=a3/2;

x=xs-a3*z';

f=[eval(f1) eval(f2) eval(f3)];

g3=f*f';

end

a2=a3/2;x=xs-a2*z';

fsave3=f;

f=[eval(f1) eval(f2) eval(f3)];

g2=f*f';h1=(g2-g1)/a2;h2=(g3-g2)/(a3-a2);h3=(h2-h1)/a3;

%

% Choose a0 so that g will be minimum in z direction

%

a0=.5*(a2-h1/h3);

x=xs-a0*z';

f=[eval(f1) eval(f2) eval(f3)];

g0=f*f';fsave0=f;

if g0 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download