’∇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