8.5.12. Does the secant method for equations in one variable always give a

direction that satis¬es (8.2) with ·n bounded away from 1? If not, when

does it? How would you implement a secant-Armijo method in such a

way that the convergence theorem 8.2.1 is applicable?

8.5.13. Under what conditions will the iteration given by nsola converge to a

root x— that is independent of the initial iterate?

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.

Bibliography

[1] E. L. Allgower and K. Georg, Simplicial and continuation methods for

approximating ¬xed points and solutions to systems of equations, SIAM Rev., 22

(1980), pp. 28“85.

[2] , Numerical Continuation Methods : An Introduction, Springer-Verlag, New

York, 1990.

[3] L. Armijo, Minimization of functions having Lipschitz-continuous ¬rst partial

derivatives, Paci¬c J. Math., 16 (1966), pp. 1“3.

[4] W. E. Arnoldi, The principle of minimized iterations in the solution of the

matrix eigenvalue problem, Quart. Appl. Math., 9 (1951), pp. 17“29.

[5] S. F. Ashby, T. A. Manteuffel, and J. S. Otto, A comparison of

adaptive Chebyshev and least squares polynomial preconditioning for Hermetian

positive de¬nite linear systems, SIAM J. Sci. Statist. Comput., 13 (1992), pp. 1“

29.

[6] K. E. Atkinson, Iterative variants of the Nystr¨m method for the numerical

o

solution of integral equations, Numer. Math., 22 (1973), pp. 17“31.

[7] , An Introduction to Numerical Analysis, 2nd. ed., John Wiley, New York,

1989.

[8] O. Axelsson, Iterative Solution Methods, Cambridge University Press, Cam-

bridge, 1994.

[9] S. Banach, Sur les op´rations dans les ensembles abstraits et leur applications

e

aux ´quations int´grales, Fund. Math, 3 (1922), pp. 133“181.

e e

[10] R. E. Bank and D. J. Rose, Global approximate Newton methods, Numer.

Math., 37 (1981), pp. 279“295.

[11] M. S. Barlett, An inverse matrix adjustment arising in discriminant analysis,

Ann. Math. Statist., 22 (1951), pp. 107“111.

[12] R. Barrett, M. Berry, T. F. Chan, J. Demmel, J. Donato, J. Don-

garra, V. Eijkhout, R. Pozo, C. Romine, and H. van der Vorst, Templates

for the Solution of Linear Systems: Building Blocks for Iterative Methods, Society

for Industrial and Applied Mathematics, Philadelphia, PA, 1993.

´ ´

[13] N. Bicanic and K. H. Johnson, Who was ˜-Raphson™?, Internat. J. Numer.

Methods. Engrg., 14 (1979), pp. 148“152.

[14] P. B. Bosma and W. A. DeRooij, E¬cient methods to calculate Chan-

drasekhar™s H-functions, Astron. Astrophys., 126 (1983), p. 283.

¨

[15] H. Brakhage, Uber die numerische Behandlung von Integralgleichungen nach

der Quadraturformelmethode, Numer. Math., 2 (1960), pp. 183“196.

[16] K. E. Brenan, S. L. Campbell, and L. R. Petzold, Numerical Solution

153

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.

154 BIBLIOGRAPHY

of Initial Value Problems in Di¬erential-Algebraic Equations, no. 14 in Classics in

Applied Mathematics, SIAM, Philadelphia, 1996.

[17] R. Brent, Algorithms for Minimization Without Deriviatives, Prentice-Hall,

Englewood Cli¬s, NJ, 1973.

[18] , Some e¬cient algorithms for solving systems of nonlinear equations, SIAM

J. Numer. Anal., 10 (1973), pp. 327“344.

[19] W. Briggs, A Multigrid Tutorial, Society for Industrial and Applied Mathemat-

ics, Philadelphia, PA, 1987.

[20] P. N. Brown, A local convergence theory for combined inexact“Newton/ ¬nite“

di¬erence projection methods, SIAM J. Numer. Anal., 24 (1987), pp. 407“434.

[21] P. N. Brown, G. D. Byrne, and A. C. Hindmarsh, VODE: A variable

coe¬cient ode solver, SIAM J. Sci. Statist. Comput., 10 (1989), pp. 1038“1051.

[22] P. N. Brown and A. C. Hindmarsh, Reduced storage matrix methods in sti¬

ODE systems, J. Appl. Math. Comput., 31 (1989), pp. 40“91.

[23] P. N. Brown, A. C. Hindmarsh, and L. R. Petzold, Using Krylov methods

in the solution of large-scale di¬erential-algebraic systems, SIAM J. Sci. Comput., 15

(1994), pp. 1467“1488.

[24] P. N. Brown and Y. Saad, Hybrid Krylov methods for nonlinear systems of

equations, SIAM J. Sci. Statist. Comput., 11 (1990), pp. 450“481.

[25] , Convergence theory of nonlinear Newton-Krylov algorithms, SIAM J.

Optim., 4 (1994), pp. 297“330.

[26] C. G. Broyden, A class of methods for solving nonlinear simultaneous equa-

tions, Math. Comput., 19 (1965), pp. 577“593.

[27] , The convergence of an algorithm for solving sparse nonlinear systems,

Math. Comput., 25 (1971), pp. 285“294.

´

[28] C. G. Broyden, J. E. Dennis, and J. J. More, On the local and superlinear

convergence of quasi-Newton methods, J. Inst. Maths. Applic., 12 (1973), pp. 223“

246.

[29] W. Burmeister, Zur Konvergenz einiger verfahren der konjugierten Richtun-

gen, in Proceedings of Internationaler Kongreß uber Anwendung der Mathematik in

¨

dem Ingenieurwissenschaften, Weimar, 1975.

[30] I. W. Busbridge, The Mathematics of Radiative Transfer, Cambridge Tracts,

No. 50, Cambridge Univ. Press, Cambridge, 1960.

[31] R. H. Byrd, J. Nocedal, and R. B. Schnabel, Representation of quasi-

Newton matrices and their use in limited memory methods, Math. Programming, 63

(1994), pp. 129“156.

[32] X.-C. Cai, W. D. Gropp, D. E. Keyes, and M. D. Tidriri, Newton-Krylov-

Schwarz methods in CFD, in Proceedings of the International Workshop on the

Navier-Stokes Equations, R. Rannacher, ed., Notes in Numerical Fluid Mechanics,

Braunschweig, 1994, Vieweg Verlag.

[33] S. L. Campbell, I. C. F. Ipsen, C. T. Kelley, and C. D. Meyer, GMRES

and the minimal polynomial, Tech. Report CRSC-TR94-10, North Carolina State

University, Center for Research in Scienti¬c Computation, July 1994. BIT, to appear.

[34] S. L. Campbell, I. C. F. Ipsen, C. T. Kelley, C. D. Meyer, and Z. Q.

Xue, Convergence estimates for solution of integral equations with GMRES, Tech.

Report CRSC-TR95-13, North Carolina State University, Center for Research in

Scienti¬c Computation, March 1995. Journal of Integral Equations and Applications,

to appear.

[35] R. Cavanaugh, Di¬erence Equations and Iterative Processes, PhD thesis,

University of Maryland, 1970.

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.

155

BIBLIOGRAPHY

[36] F. Chaitin-Chatelin, Is nonnormality a serious di¬culty ?, Tech. Report

TR/PA/94/18, CERFACS, December 1994.

[37] T. Chan, E. Gallopoulos, V. Simoncini, T. Szeto, and C. Tong, A quasi-

minimal residual variant of the Bi-CGSTAB algorithm for nonsymmetric systems,

SIAM J. Sci. Comput., 15 (1994), p. 338.

´

[38] T. Chan, R. Glowinski, J. Periaux, and O. Widlund, eds., Domain

Decomposition Methods,Proceedings of the Second International Symposium on

Domain Decomposition Methods, Los Angeles, CA, January 14“16, 1988; Society

for Industrial and Applied Mathematics, Philadelphia, PA, 1989.

[39] , eds., Domain Decomposition Methods, Proceedings of the Third Interna-

tional Symposium on Domain Decomposition Methods, Houston, TX, 1989; Society

for Industrial and Applied Mathematics, Philadelphia, PA, 1990.

[40] , eds., Domain Decomposition Methods, Proceedings of the Fourth Interna-

tional Symposium on Domain Decomposition Methods, Moscow, USSR, 1990; Soci-

ety for Industrial and Applied Mathematics, Philadelphia, PA, 1991.,

[41] S. Chandrasekhar, Radiative Transfer, Dover, New York, 1960.

´

[42] T. F. Coleman and J. J. More, Estimation of sparse Jacobian matrices and

graph coloring problems, SIAM J. Numer. Anal., 20 (1983), pp. 187“209.

[43] T. F. Coleman and C. VanLoan, Handbook for Matrix Computations,

Frontiers in Appl. Math., No. 4, Society for Industrial and Applied Mathematics,

Philadelphia, PA, 1988.

[44] P. Concus, G. H. Golub, and G. Meurant, Block preconditioning for the

conjugate gradient method, SIAM J. Sci. Statist. Comput., 6 (1985), pp. 220“252.

[45] P. Concus, G. H. Golub, and D. P. O™Leary, A generalized conjugate

gradient method for the numerical solution of elliptic partial di¬erential equations,

in Sparse Matrix Computations, J. R. Bunch and D. J. Rose, eds., Academic Press,

1976, pp. 309“332.

[46] E. J. Craig, The N-step iteration procedures, J. Math. Phys., 34 (1955), pp. 64“

73.

[47] A. R. Curtis, M. J. D. Powell, and J. K. Reid, On the estimation of sparse

Jacobian matrices, J. Inst. Math. Appl., 13 (1974), pp. 117“119.

[48] J. W. Daniel, The conjugate gradient method for linear and nonlinear operator

equations, SIAM J. Numer. Anal., 4 (1967), pp. 10“26.

[49] D. W. Decker, H. B. Keller, and C. T. Kelley, Convergence rates for

Newton™s method at singular points, SIAM J. Numer. Anal., 20 (1983), pp. 296“314.

[50] D. W. Decker and C. T. Kelley, Newton™s method at singular points I, SIAM

J. Numer. Anal., 17 (1980), pp. 66“70.

[51] , Convergence acceleration for Newton™s method at singular points, SIAM J.

Numer. Anal., 19 (1982), pp. 219“229.

[52] , Sublinear convergence of the chord method at singular points, Numer.

Math., 42 (1983), pp. 147“154.

[53] , Broyden™s method for a class of problems having singular Jacobian at the

root, SIAM J. Numer. Anal., 22 (1985), pp. 566“574.

[54] T. J. Dekker, Finding a zero by means of successive linear interpolation, in

Constructive Aspects of the Fundamental Theorem of Algebra, P. Henrici, ed., 1969,

pp. 37“48.

[55] R. Dembo, S. Eisenstat, and T. Steihaug, Inexact Newton methods, SIAM

J. Numer. Anal., 19 (1982), pp. 400“408.

[56] R. Dembo and T. Steihaug, Truncated Newton algorithms for large-scale

optimization, Math. Programming, 26 (1983), pp. 190“212.

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.

156 BIBLIOGRAPHY

[57] J. E. Dennis, On the Kantorovich hypothesis for Newton™s method, SIAM J.

Numer. Anal., 6 (1969), pp. 493“507.

[58] , Toward a uni¬ed convergence theory for Newton-like methods, in Nonlinear

Functional Analysis and Applications, L. B. Rall, ed., Academic Press, New York,

1971, pp. 425“472.

[59] J. E. Dennis, J. M. Martinez, and X. Zhang, Triangular decomposition

methods for solving reducible nonlinear systems of equations, SIAM J. Optim., 4

(1994), pp. 358“382.

´

[60] J. E. Dennis and J. J. More, A characterization of superlinear convergence

and its application to quasi-Newton methods, Math. Comput., 28 (1974), pp. 549“560.

[61] , Quasi-Newton methods, methods, motivation and theory, SIAM Rev., 19

(1977), pp. 46“89.

[62] J. E. Dennis and R. B. Schnabel, Least change secant updates for quasi-

Newton methods, SIAM Rev., 21 (1979), pp. 443“459.

[63] , Numerical Methods for Unconstrained Optimization and Nonlinear Equa-

tions, no. 16 in Classics in Applied Mathematics, SIAM, Philadelphia, 1996.

[64] J. E. Dennis and H. F. Walker, Convergence theorems for least change secant

update methods, SIAM J. Numer. Anal., 18 (1981), pp. 949“987.

[65] , Inaccuracy in quasi-Newton methods: Local improvement theorems, in

Mathematical Programming Study 22: Mathematical programming at Oberwolfach

II, North“Holland, Amsterdam, 1984, pp. 70“85.

[66] , Least-change sparse secant updates with inaccurate secant conditions,

SIAM J. Numer. Anal., 22 (1985), pp. 760“778.

[67] P. Deuflhard, R. W. Freund, and A. Walter, Fast secant methods for

the iterative solution of large nonsymmetric linear systems, Impact of Computing in

Science and Engineering, 2 (1990), pp. 244“276.

[68] W. J. Duncan, Some devices for the solution of large sets of simultaneous

linear equations (with an appendix on the reciprocation of partitioned matrices), The

London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science,

Seventh Series, 35 (1944), pp. 660“670.

[69] S. C. Eisenstat and H. F. Walker, Choosing the forcing terms in an inexact

Newton method, SIAM J. Sci. Comput., 17 (1996), pp. 16“32.

[70] , Globally convergent inexact Newton methods, SIAM J. Optim., 4 (1994),

pp. 393“422.

[71] H. C. Elman, Iterative Methods for Large, Sparse, Nonsymmetric Systems of

Linear Equations, PhD thesis, Yale University, New Haven, CT, 1982.

[72] H. C. Elman, Y. Saad, and P. E. Saylor, A hybrid Chebyshev-Krylov

subspace algorithm for solving nonsymmetric systems of linear equations, SIAM J.

Sci. Statist. Comput., 7 (1986), pp. 840“855.

[73] M. Engelman, G. Strang, and K. J. Bathe, The application of quasi-

Newton methods in ¬‚uid mechanics, Internat. J. Numer. Methods Engrg., 17 (1981),

pp. 707“718.

[74] V. Faber and T. A. Manteuffel, Necessary and su¬cient conditions for the

existence of a conjugate gradient method, SIAM J. Numer. Anal., 21 (1984), pp. 352“

362.

[75] D. Feng, P. D. Frank, and R. B. Schnabel, Local convergence analysis of

tensor methods for nonlinear equations, Math. Programming, 62 (1993), pp. 427“459.

[76] R. Fletcher, Conjugate gradient methods for inde¬nite systems, in Numerical

Analysis Dundee 1975, G. Watson, ed., Springer-Verlag, Berlin, New York, 1976,

pp. 73“89.

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.

157

BIBLIOGRAPHY

[77] R. W. Freund, A transpose-free quasi-minimal residual algorithm for non-

Hermitian linear systems, SIAM J. Sci. Comput., 14 (1993), pp. 470“482.

[78] R. W. Freund, G. H. Golub, and N. M. Nachtigal, Iterative solution of

linear systems, Acta Numerica, 1 (1991), pp. 57“100.

[79] R. W. Freund, M. H. Gutknecht, and N. M. Nachtigal, An implemen-

tation of the look-ahead Lanczos algorithm for non-Hermitian matrices, SIAM J. Sci.

Comput., 14 (1993), pp. 137“158.

[80] R. W. Freund and N. M. Nachtigal, QMR: a quasi-minimal residual

algorithm for non-hermitian linear systems, Numer. Math., 60 (1991), pp. 315“339.

[81] , An implementation of the QMR method based on coupled two-term

recurrences, SIAM J. Sci. Comput., 15 (1994), pp. 313“337.

[82] D. M. Gay, Some convergence properties of Broyden™s method, SIAM J. Numer.

Anal., 16 (1979), pp. 623“630.

[83] C. W. Gear, Numerical Initial Value Problems in Ordinary Di¬erential Equa-

tions, Prentice-Hall, Englewood Cli¬s, NJ, 1971.

[84] R. R. Gerber and F. T. Luk, A generalized Broyden™s method for solving

simultaneous linear equations, SIAM J. Numer. Anal., 18 (1981), pp. 882“890.

[85] P. E. Gill and W. Murray, Quasi-Newton methods for unconstrained

optimization, J. I. M. A., 9 (1972), pp. 91“108.

[86] , Safeguarded steplength algorithms for optimization using descent methods,

Tech. Report NAC 37, National Physical Laboratory Report, Teddington, England,

1974.

[87] P. E. Gill, W. Murray, and M. H. Wright, Practical Optimization,

Academic Press, London, 1981.

[88] A. A. Goldstein, Constructive Real Analysis, Harper and Row, New York,

1967.

[89] G. H. Golub and C. G. VanLoan, Matrix Computations, Johns Hopkins

University Press, Baltimore, 1983.

[90] A. Griewank, Analysis and modi¬cation of Newton™s method at singularities,

PhD thesis, Australian National University, 1981.

[91] , Rates of convergence for secant methods on nonlinear problems in Hilbert

space, in Numerical Analysis, Proceedings Guanajuato , Mexico 1984, Lecture Notes

in Math., No, 1230, J. P. Hennart, ed., Springer-Verlag, Heidelberg, 1986, pp. 138“

157.

[92] , The solution of boundary value problems by Broyden based secant methods,

in Computational Techniques and Applications: CTAC 85, Proceedings of CTAC,

Melbourne, August 1985, J. Noye and R. May, eds., North Holland, Amsterdam,

1986, pp. 309“321.

[93] , On the iterative solution of di¬erential and integral equations using secant

updating techniques, in The State of the Art in Numerical Analysis, A. Iserles and

M. J. D. Powell, eds., Clarendon Press, Oxford, 1987, pp. 299“324.

[94] A. Griewank and G. F. Corliss, eds., Automatic Di¬erentiation of Algo-

rithms: Theory, Implementation, and Application, Society for Industrial and Applied

Mathematics, Philadelphia, PA, 1991.

[95] A. Griewank and P. L. Toint, Local convergence analysis for partitioned

quasi-newton updates, Numer. Math., 39 (1982), pp. 429“448.

[96] , Partitioned variable metric methods for large sparse optimization problems,

Numer. Math., 39 (1982), pp. 119“137.

[97] W. A. Gruver and E. Sachs, Algorithmic Methods In Optimal Control,

Pitman, London, 1980.

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.

158 BIBLIOGRAPHY

[98] M. H. Gutknecht, Variants of BICGSTAB for matrices with complex spectrum,

SIAM J. Sci. Comput., 14 (1993), pp. 1020“1033.

[99] W. Hackbusch, Multi-Grid Methods and Applications, vol. 4 of Springer Series

in Computational Mathematics, Springer-Verlag, New York, 1985.

[100] , Multigrid methods of the second kind, in Multigrid Methods for Integral

and Di¬erential Equations, Oxford University Press, Oxford, 1985.

[101] W. E. Hart and S. O. W. Soul, Quasi-Newton methods for discretized

nonlinear boundary problems, Journal of the Institute of Applied Mathematics, 11

(1973), pp. 351“359.

[102] H. V. Henderson and S. R. Searle, On deriving the inverse of a sum of

matrices, SIAM Rev., 23 (1981), pp. 53“60.

[103] M. R. Hestenes and E. Steifel, Methods of conjugate gradient for solving

linear systems, J. of Res. Nat. Bureau Standards, 49 (1952), pp. 409“436.

[104] D. M. Hwang and C. T. Kelley, Convergence of Broyden™s method in Banach

spaces, SIAM J. Optim., 2 (1992), pp. 505“532.

[105] E. Isaacson and H. B. Keller, Analysis of numerical methods, John Wiley,

New York, 1966.

[106] L. Kantorovich and G. Akilov, Functional Analysis, 2nd ed., Pergamon

Press, New York, 1982.

[107] L. V. Kantorovich, Functional analysis and applied mathematics, Uspehi Mat.

Nauk., 3 (1948), pp. 89“185. translation by C. Benster as Nat. Bur. Standards Report

1509. Washington, D. C., 1952.

[108] H. B. Keller, Newton™s method under mild di¬erentiability conditions, J.

Comput. Sys. Sci, 4 (1970), pp. 15“28.

[109] , Lectures on Numerical Methods in Bifurcation Theory, Tata Institute of

Fundamental Research, Lectures on Mathematics and Physics, Springer-Verlag, New

York, 1987.

[110] C. T. Kelley, Solution of the Chandrasekhar H-equation by Newton™s method,

J. Math. Phys., 21 (1980), pp. 1625“1628.

[111] , A fast multilevel algorithm for integral equations, SIAM J. Numer. Anal.,

32 (1995), pp. 501“513.

[112] C. T. Kelley and E. W. Sachs, A quasi-Newton method for elliptic boundary

value problems, SIAM J. Numer. Anal., 24 (1987), pp. 516“531.

[113] , A pointwise quasi-Newton method for unconstrained optimal control

problems, Numer. Math., 55 (1989), pp. 159“176.

[114] , Fast algorithms for compact ¬xed point problems with inexact function

evaluations, SIAM J. Sci. Statist. Comput., 12 (1991), pp. 725“742.

[115] , A new proof of superlinear convergence for Broyden™s method in Hilbert

space, SIAM J. Optim., 1 (1991), pp. 146“150.

[116] , Pointwise Broyden methods, SIAM J. Optim., 3 (1993), pp. 423“441.

[117] , Multilevel algorithms for constrained compact ¬xed point problems, SIAM

J. Sci. Comput., 15 (1994), pp. 645“667.

[118] C. T. Kelley and R. Suresh, A new acceleration method for Newton™s method

at singular points, SIAM J. Numer. Anal., 20 (1983), pp. 1001“1009.

[119] C. T. Kelley and Z. Q. Xue, Inexact Newton methods for singular problems,

Optimization Methods and Software, 2 (1993), pp. 249“267.

[120] , GMRES and integral operators, SIAM J. Sci. Comput., 17 (1996), pp. 217“

226.

[121] T. Kerkhoven and Y. Saad, On acceleration methods for coupled nonlinear

elliptic systems, Numerische Mathematik, 60 (1992), pp. 525“548.

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.

159

BIBLIOGRAPHY

[122] C. Lanczos, Solution of linear equations by minimized iterations, J. Res. Natl.

Bur. Stand., 49 (1952), pp. 33“53.

[123] T. A. Manteuffel, Adaptive procedure for estimating parameters for the

nonsymmetric Tchebychev iteration, Numer. Math., 31 (1978), pp. 183“208.

[124] T. A. Manteuffel and S. Parter, Preconditioning and boundary conditions,

SIAM J. Numer. Anal., 27 (1990), pp. 656“694.

[125] E. S. Marwil, Convergence results for Schubert™s method for solving sparse

nonlinear equations, SIAM J. Numer. Anal., (1979), pp. 588“604.

[126] S. McCormick, Multilevel Adaptive Methods for Partial Di¬erential Equations,

Society for Industrial and Applied Mathematics, Philadelphia, PA, 1989.

[127] J. A. Meijerink and H. A. van der Vorst, An iterative solution method

for linear systems of which the coe¬cient matrix is a symmetric M-matrix, Math.

Comput., 31 (1977), pp. 148“162.

[128] C. D. Meyer, Matrix Analysis and Applied Linear Algebra, forthcoming.

´

[129] J. J. More, Recent developments in algorithms and software for trust region