<< . .

. 23
( : 26)



. . >>

cult problem. We take (6.21) from § 6.4.2,

’∇2 u + Cu(ux + uy ) = f

with the same right hand side f , initial iterate u0 = 0, 31 — 31 mesh and
homogeneous Dirichlet boundary conditions on the unit square (0, 1) — (0, 1)
that we considered before. Here, however, we set C = 100. This makes a
globalization strategy critical (Try it without one!). We set „r = „a = h2 /10.
This is a tighter tolerance that in § 6.4.2 and, because of the large value of C
and resulting ill-conditioning, is needed to obtain an accurate solution.
In Fig. 8.3 we show the progress of the iteration for the unpreconditioned
equation. For this problem we plot the progress of the iteration using · = .25
with the solid line and using the sequence given by (6.20) with the dashed



Buy this book from SIAM at http://www.ec-securehost.com/SIAM/FR16.html.
Copyright ©1995 by the Society for Industrial and Applied Mathematics. This electronic version is for personal use and may not be duplicated or distributed.




147
GLOBAL CONVERGENCE


0
10


-2
10

Relative Nonlinear Residual
-4
10


-6
10


-8
10


-10
10


-12
10
0 5 10 15 20 25 30 35
Function Evaluations




Fig. 8.2. Newton“Armijo for the arctan function.


line. We set the parameters in (6.20) to γ = .9 and ·max = .25. This problem
is very poorly conditioned and much tighter control on the inner iteration is
needed than for the other problems. The two approaches to selection of the
forcing term performed very similarly. The iterations required 75.3 (constant
·) and 75.4 (varying ·) million ¬‚oating point operations, 759 (constant ·) and
744 (varying ·) function evaluations, and 25 (constant ·) and 22 (varying ·)
outer iterations.

0
10



-1
10
Relative Nonlinear Residual




-2
10



-3
10



-4
10



-5
10
0 100 200 300 400 500 600 700 800
Function Evaluations




Fig. 8.3. Newton“Armijo for the PDE, C = 100.

We consider the preconditioned problem in Fig. 8.4. In the computation we



Buy this book from SIAM at http://www.ec-securehost.com/SIAM/FR16.html.
Copyright ©1995 by the Society for Industrial and Applied Mathematics. This electronic version is for personal use and may not be duplicated or distributed.




148 ITERATIVE METHODS FOR LINEAR AND NONLINEAR EQUATIONS

preconditioned (6.21) with the fast Poisson solver fish2d. In Fig. 8.4 we show
the progress of the iteration for the preconditioned equation. For this problem
we plot the progress of the iteration using · = .25 with the solid line and using
the sequence given by (6.20) with the dashed line. We set the parameters in
(6.20) to γ = .9 and ·max = .99.
The constant · iteration terminated after 79 function evaluations, 9 outer
iterations, and roughly 13.5 million ¬‚oating-point operations. The line search
in this case reduced the step length three times on the ¬rst iteration and twice
on the second and third.
The iteration in which {·n } is given by (6.20) terminated after 70 function
evaluations, 9 outer iterations, and 12.3 million ¬‚oating-point operations. The
line search in the non-constant · case reduced the step length three times on
the ¬rst iteration and once on the second. The most e¬cient iteration, with
the forcing term given by (6.20), required at most 16 inner iterations while the
constant · approach needed at most 10.

0
10



-1
10
Relative Nonlinear Residual




-2
10



-3
10



-4
10



-5
10
0 10 20 30 40 50 60 70 80
Function Evaluations




Fig. 8.4. Newton“Armijo for the PDE, C = 100.


8.4.3. Broyden“Armijo. We found that the Broyden“Armijo line search
failed on all the unpreconditioned convection di¬usion equation examples. In
these cases the Jacobian is not well approximated by a low rank perturbation
of the identity [112] and the ability of the inexact Newton iteration to ¬nd a
good search direction was the important factor.
We begin by revisiting the example in § 6.4.2 with C = 20. As reported
in § 6.4.2, the Newton-GMRES iteration always took full steps, terminating
in 4 outer iterations, 16 function evaluations, and 2.6 million ¬‚oating-point
operations. When compared to the Broyden™s method results in § 6.4.2,
when increases in the residual were allowed, the Broyden“Armijo costs re¬‚ect



Buy this book from SIAM at http://www.ec-securehost.com/SIAM/FR16.html.
Copyright ©1995 by the Society for Industrial and Applied Mathematics. This electronic version is for personal use and may not be duplicated or distributed.




149
GLOBAL CONVERGENCE

an improvement in e¬ciency. The Broyden iteration in § 6.4.2 took 12
iterations and 2.8 million ¬‚oating-point operations while the Broyden“Armijo
took 9 iterations and required 2 million ¬‚oating-point operations. We set
„a = „r = h2 , ·max = .5, and γ = .9 as we did in § 6.4.2.
In our implementation of brsola the three-point parabolic line search was
used. The steplength was reduced on the second iteration (twice) and the third
(once). Figure 8.5 compares the Broyden“Armijo iteration (solid line) to the
GMRES iteration (dashed line).

0
10
Relative Nonlinear Residual




-1
10




-2
10




-3
10
0 2 4 6 8 10 12 14 16
Function Evaluations




Fig. 8.5. Newton-GMRES and Broyden“Armijo for the PDE, C = 20.

For the more di¬cult problem with C = 100, the performance of the
two methods is more similar. In Fig. 8.6 we compare our implementation
of Newton“GMRES“Armijo (dashed line) to Broyden“Armijo (solid line). We
set „a = „r = h2 /10, ·max = .99, and γ = .9. The Broyden“Armijo iteration
required 34 nonlinear iterations, roughly 16 million ¬‚oating-point operations,
and 85 function evaluations. In terms of storage, the Broyden“Armijo iteration
required storage for 37 vectors while the Newton-GMRES iteration needed at
most 16 inner iterations, needing to store 21 vectors, and therefore was much
more e¬cient in terms of storage.
Restarting the Broyden iteration every 19 iterations would equalize the
storage requirements with Newton“GMRES“Armijo. Broyden™s method suf-
fers under these conditions as one can see from the comparison of Broyden“
Armijo (solid line) and Newton“GMRES“Armijo (dashed line) in Fig. 8.7. The
restarted Broyden“Armijo iteration took 19.5 million ¬‚oating-point operations,
42 outer iterates, and 123 function evaluations.
From these examples we see that Broyden“Armijo can be very e¬cient pro-
vided only a small number of iterations are needed. The storage requirements
increase as the nonlinear iteration progresses and this fact puts Broyden™s



Buy this book from SIAM at http://www.ec-securehost.com/SIAM/FR16.html.
Copyright ©1995 by the Society for Industrial and Applied Mathematics. This electronic version is for personal use and may not be duplicated or distributed.




150 ITERATIVE METHODS FOR LINEAR AND NONLINEAR EQUATIONS


0
10



-1
10




Relative Nonlinear Residual
-2
10



-3
10



-4
10



-5
10
0 10 20 30 40 50 60 70 80 90
Function Evaluations




Fig. 8.6. Newton-GMRES and Broyden“Armijo for the PDE, C = 100.

0
10



-1
10
Relative Nonlinear Residual




-2
10



-3
10



-4
10



-5
10
0 20 40 60 80 100 120 140
Function Evaluations




Fig. 8.7. Newton-GMRES and restarted Broyden“Armijo for the PDE, C = 100.


method at a disadvantage to Newton-GMRES when the number of nonlinear
iterations is large.




Buy this book from SIAM at http://www.ec-securehost.com/SIAM/FR16.html.
Copyright ©1995 by the Society for Industrial and Applied Mathematics. This electronic version is for personal use and may not be duplicated or distributed.




151
GLOBAL CONVERGENCE

8.5. Exercises on global convergence
8.5.1. How does the method proposed in [10] di¬er from the one implemented in
nsola? What could be advantages and disadvantages of that approach?

8.5.2. In what ways are the results in [25] and [70] more general than those in
this section? What ideas do these papers share with the analysis in this
section and with [3] and [88]?

8.5.3. Implement the Newton“Armijo method for single equations. Apply your
code to the following functions with x0 = 10. Explain your results.
1. f (x) = arctan(x) (i.e., Duplicate the results in § 8.1.)
2. f (x) = arctan(x2 )
3. f (x) = .9 + arctan(x)
4. f (x) = x(1 + sin(1/x))
5. f (x) = ex
6. f (x) = 2 + sin(x)
7. f (x) = 1 + x2

8.5.4. A numerical analyst buys a German sports car for $50,000. He puts
$10,000 down and takes a 7 year installment loan to pay the balance. If
the monthly payments are $713.40, what is the interest rate? Assume
monthly compounding.

8.5.5. Verify (8.8) and (8.9).

8.5.6. Show that if F is Lipschitz continuous and the iteration {xn } produced
by Algorithm nsola converges to x— with F (x— ) = 0, then F (x— ) is
singular.

8.5.7. Use nsola to duplicate the results in § 8.4.2. Vary the convection
coe¬cient in the convection-di¬usion equation and the mesh size and
report the results.

8.5.8. Experiment with other linear solvers such as GMRES(m), Bi-CGSTAB,
and TFQMR. This is interesting in the locally convergent case as well.
You might use the MATLAB code nsola to do this.

8.5.9. Modify nsol, the hybrid Newton algorithm from Chapter 5, to use the
Armijo rule. Try to do it in such a way that the chord direction is used
whenever possible.

8.5.10. Modify brsola to test the Broyden direction for the descent property
and use a two-point parabolic line search. What could you do if the
Broyden direction is not a descent direction? Apply your code to the
examples in § 8.4.



Buy this book from SIAM at http://www.ec-securehost.com/SIAM/FR16.html.
Copyright ©1995 by the Society for Industrial and Applied Mathematics. This electronic version is for personal use and may not be duplicated or distributed.




152 ITERATIVE METHODS FOR LINEAR AND NONLINEAR EQUATIONS

8.5.11. Modify nsola to use a cubic polynomial and constant reduction line
searches instead of the quadratic polynomial line search. Compare the

<< . .

. 23
( : 26)



. . >>