<< . .

. 25
( : 26)



. . >>

methods, in Mathematical Programming: The State of the Art, A. Bachem,
M. Gr¨schel, and B. Korte, eds., Springer-Verlag, Berlin, 1983, pp. 258“287.
o
´
[130] J. J. More and J. A. Trangenstein, On the global convergence of Broyden™s
method, Math. Comput., 30 (1976), pp. 523“540.
[131] T. E. Mott, Newton™s method and multiple roots, Amer. Math. Monthly, 64
(1957), pp. 635“638.
[132] T. W. Mullikin, Some probability distributions for neutron transport in a half
space, J. Appl. Probab., 5 (1968), pp. 357“374.
[133] W. Murray and M. L. Overton, Steplength algorithms for minimizing a
class of nondi¬erentiable functions, Computing, 23 (1979), pp. 309“331.
[134] N. M. Nachtigal, S. C. Reddy, and L. N. Trefethen, How fast are
nonsymmetric matrix iterations?, SIAM J. Matrix Anal. Appl., 13 (1992), pp. 778“
795.
[135] N. M. Nachtigal, L. Reichel, and L. N. Trefethen, A hybrid gmres
algorithm for nonsymmetric linear systems, SIAM J. Matrix Anal. Appl., 13 (1992).
[136] S. G. Nash, Preconditioning of truncated Newton methods, SIAM J. Sci. Statist.
Comput., 6 (1985), pp. 599“616.
[137] , Who was Raphson? (an answer). Electronic Posting to NA-Digest,
v92n23, 1992.
[138] J. L. Nazareth, Conjugate gradient methods less dependent on conjugacy,
SIAM Rev., 28 (1986), pp. 501“512.
[139] O. Nevanlinna, Convergence of Iterations for Linear Equations, Birkh¨user,
a
Basel, 1993.
[140] I. Newton, The Mathematical Papers of Isaac Newton (7 volumes), D. T.
Whiteside, ed., Cambridge University Press, Cambridge, 1967“1976.
[141] B. Noble, Applied Linear Algebra, Prentice Hall, Englewood Cli¬s, NJ, 1969.
[142] J. Nocedal, Theory of algorithms for unconstrained optimization, Acta Numer-
ica, 1 (1991), pp. 199“242.
[143] D. P. O™Leary, Why Broyden™s nonsymmetric method terminates on linear
equations, SIAM J. Optim., 4 (1995), pp. 231“235.
[144] J. M. Ortega, Numerical Analysis A Second Course, Classics in Appl. Math.,
No. 3, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1990.
[145] J. M. Ortega and W. C. Rheinboldt, Iterative Solution of Nonlinear
Equations in Several Variables, Academic Press, New York, 1970.
[146] A. M. Ostrowski, Solution of Equations and Systems of Equations, Academic




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.




160 BIBLIOGRAPHY

Press, New York, 1960.
[147] B. N. Parlett, The Symmetric Eigenvalue Problem, Prentice Hall, Englewood
Cli¬s, NJ, 1980.
[148] B. N. Parlett, D. R. Taylor, and Z. A. Liu, A look-ahead Lanczos
algorithm for unsymmetric matrices, Math. Comput., 44 (1985), pp. 105“124.
[149] D. W. Peaceman and H. H. Rachford, The numerical solution of parabolic
and elliptic di¬erential equations, J. Soc. Indus. Appl. Math., 11 (1955), pp. 28“41.
[150] G. Peters and J. Wilkinson, Inverse iteration, ill-conditioned equations and
Newton™s method, SIAM Rev., 29 (1979), pp. 339“360.
[151] L. R. Petzold, A description of DASSL: a di¬erential/algebraic system solver,
in Scienti¬c Computing, R. S. Stepleman et al., eds., North Holland, Amsterdam,
1983, pp. 65“68.
[152] E. Picard, M´moire sur la th´orie des ´quations aux d´riv´es partielles et la
e e e ee
m´thode des approximations successives, J. de Math. ser 4, 6 (1890), pp. 145“210.
e
[153] M. J. D. Powell, A hybrid method for nonlinear equations, in Numerical
Methods for Nonlinear Algebraic Equations, Gordon and Breach, New York, 1970,
pp. 87“114.
[154] , Convergence properties of a class of minimization algorithms, in Nonlinear
Programming 2, O. L. Mangasarian, R. R. Meyer, and S. M. Robinson, eds.,
Academic Press, New York, 1975, pp. 1“27.
[155] L. B. Rall, Convergence of the Newton process to multiple solutions, Numer.
Math., 9 (1961), pp. 23“37.
[156] J. Raphson, Analysis aequationum universalis seu ad aequationes algebraicas
resolvendas methodus generalis, et expedita, ex nova in¬nitarum serierum doctrina,
deducta ac demonstrata. Original in British Library, London, 1690.
[157] G. W. Reddien, On Newton™s method for singular problems, SIAM J. Numer.
Anal., 15 (1978), pp. 993“986.
[158] J. K. Reid, Least squares solution of sparse systems of nonlinear equations by a
modi¬ed Marquardt algorithm, in Proc. NATO Conf. at Cambridge, July 1972, North
Holand, Amsterdam, 1973, pp. 437“445.
[159] W. C. Rheinboldt, Numerical Analysis of Parametrized Nonlinear Equations,
John Wiley, New York, 1986.
[160] J. R. Rice, Experiments on Gram-Schmidt orthogonalization, Math. Comput.,
20 (1966), pp. 325“328.
[161] T. J. Rivlin, The Chebyshev Polynomials, John Wiley, New York, 1974.
[162] H. L. Royden, Real Analysis, 2nd ed., Macmillan, New York, 1968.
[163] Y. Saad, Practical use of polynomial preconditionings for the conjugate gradient
method, SIAM J. Sci. Statist. Comput., 6 (1985), pp. 865“881.
[164] , Least squares polynomials in the complex plane and their use for solving
nonsymmetric linear systems, SIAM J. Numer. Anal., 24 (1987), pp. 155“169.
[165] , ILUT: A dual threshold incomplete LU factorization, Tech. Report 92-38,
Computer Science Department, University of Minnesota, 1992.
[166] , A ¬‚exible inner-outer preconditioned GMRES algorithm, SIAM J. Sci.
Comput., (1993), pp. 461“469.
[167] Y. Saad and M. Schultz, GMRES a generalized minimal residual algorithm
for solving nonsymmetric linear systems, SIAM J. Sci. Statist. Comput., 7 (1986),
pp. 856“869.
[168] E. Sachs, Broyden™s method in Hilbert space, Math. Programming, 35 (1986),
pp. 71“82.
[169] P. E. Saylor and D. C. Smolarski, Implementation of an adaptive algorithm




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.




161
BIBLIOGRAPHY

for Richardson™s method, Linear Algebrra Appl., 154/156 (1991), pp. 615“646.
[170] R. B. Schnabel and P. D. Frank, Tensor methods for nonlinear equations,
SIAM J. Numer. Anal., 21 (1984), pp. 815“843.
¨
¨
[171] E. Schroder, Uber unendlich viele Algorithmen zur Au¬‚osung der Gleichungen,
Math. Ann., 2 (1870), pp. 317“365.
[172] L. K. Schubert, Modi¬cation of a quasi-Newton method for nonlinear equations
with sparse Jacobian, Math. Comput., 24 (1970), pp. 27“30.
[173] G. A. Schultz, R. B. Schnabel, and R. H. Byrd, A family of trust-region-
based algorithms for unconstrained minimization with strong global convergence
properties, SIAM J. Numer. Anal., 22 (1985), pp. 47“67.
[174] V. E. Shamanskii, A modi¬cation of Newton™s method, Ukran. Mat. Zh., 19
(1967), pp. 133“138. (In Russian.)
[175] A. H. Sherman, On Newton-iterative methods for the solution of systems of
nonlinear equations, SIAM J. Numer. Anal., 14 (1978), pp. 755“774.
[176] J. Sherman and W. J. Morrison, Adjustment of an inverse matrix corre-
sponding to changes in the elements of a given column or a given row of the original
matrix (abstract), Ann. Math. Statist., 20 (1949), p. 621.
[177] , Adjustment of an inverse matrix corresponding to a change in one element
of a given matrix, Ann. Math. Statist., 21 (1950), pp. 124“127.
[178] K. Sigmon, MATLAB Primer, Fourth Edition, CRC Press, Boca Raton, FL,
1994.
[179] D. C. Smolarski and P. E. Saylor, An optimum iterative method for solving
any linear system with a square matrix, BIT, 28 (1988), pp. 163“178.
[180] P. Sonneveld, CGS, a fast Lanczos-type solver for nonsymmetric linear
systems, SIAM J. Sci. Statist. Comput., 10 (1989), pp. 36“52.
[181] D. C. Sorensen, Newton™s method with a model trust region modi¬cation, SIAM
J. Numer. Anal., 19 (1982), pp. 409“426.
[182] G. Starke, Alternating direction preconditioning for nonsymmetric systems of
linear equations, SIAM J. Sci. Comput., 15 (1994), pp. 369“385.
[183] G. Starke and R. S. Varga, A hybrid Arnoldi-Faber iterative method for
nonsymmetric systems of linear equations, Numer. Math., 64 (1993), pp. 213“239.
[184] G. W. Stewart, Introduction to matrix computations, Academic Press, New
York, 1973.
[185] E. L. Stiefel, Kernel polynomials in linear algebra and their numerical
applications, U.S. National Bureau of Standards, Applied Mathematics Series, 49
(1958), pp. 1“22.
[186] P. N. Swarztrauber, The methods of cyclic reduction, Fourier analysis and
the FACR algorithm for the discrete solution of Poisson™s equation on a rectangle,
SIAM Rev., 19 (1977), pp. 490“501.
[187] , Approximate cyclic reduction for solving Poisson™s equation, SIAM J. Sci.
Statist. Comput., 8 (1987), pp. 199“209.
[188] P. N. Swarztrauber and R. A. Sweet, Algorithm 541: E¬cient FORTRAN
subprograms for the solution of elliptic partial di¬erential equations, ACM Trans.
Math. Software, 5 (1979), pp. 352“364.
[189] P. L. Toint, On sparse and symmetric matrix updating subject to a linear
equation, Math. Comput., 31 (1977), pp. 954“961.
[190] J. F. Traub, Iterative Methods for the Solution of Equations, Prentice Hall,
Englewood Cli¬s, NJ, 1964.
[191] H. A. van der Vorst, Bi-CGSTAB: A fast and smoothly converging variant to
Bi-CG for the solution of nonsymmetric systems, SIAM J. Sci. Statist. Comput., 13




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.




162 BIBLIOGRAPHY

(1992), pp. 631“644.
[192] H. A. van der Vorst and C. Vuik, The superlinear convergence behaviour
of GMRES, Journal Comput. Appl. Math., 48 (1993), pp. 327“341.
[193] R. S. Varga, Matrix Iterative Analysis, Prentice Hall, Englewood Cli¬s, NJ,
1962.
[194] E. L. Wachspress, Iterative Solution of Elliptic Systems and Applications to
the Neutron Di¬usion Equations of Reactor Physics, Prentice Hall, Englewood Cli¬s,
NJ, 1966.
[195] H. F. Walker, Implementation of the GMRES method using Householder
transformations, SIAM J. Sci. Statist. Comput., 9 (1989), pp. 815“825.
[196] , Residual smoothing and peak/plateau behavior in Krylov subspace methods,
Applied Numer. Math., 19 (1995), pp. 279“286.
[197] H. F. Walker and L. Zhou, A simpler GMRES, J. Numer. Lin. Alg. Appl.,
6 (1994), pp. 571“581.
[198] L. T. Watson, S. C. Billups, and A. P. Morgan, Algorithm 652:
HOMPACK: A suite of codes for globally convergent homotopy algorithms, ACM
Trans. Math. Software, 13 (1987), pp. 281“310.
[199] M. A. Woodbury, Inverting modi¬ed matrices, Memorandum Report 42,
Statistical Research Group, Princeton NJ, 1950.
[200] D. M. Young, Iterative Solution of Large Linear Systems, Academic Press, New
York, 1971.
[201] T. J. Ypma, The e¬ect of rounding errors on Newton-like methods, IMA J.
Numer. Anal., 3 (1983), pp. 109“118.
[202] L. Zhou and H. F. Walker, Residual smoothing techniques for iterative
methods, SIAM J. Sci. Comput., 15 (1994), pp. 297“312.




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.




Index




A-conjugacy, 20 Cauchy sequence, 67
CGNE, 25
A-norm, 12
CGNR, 25
Approximate inverse, 6, 77 CGS, 48
Armijo rule, 137 algorithm, 49
Arnoldi process, 37 Chandrasekhar H-equation, 87
solution
Backtracking, 136 Broyden™s method, 128
Bad Broyden method, 132 Newton™s method, 87
Banach Lemma, 6 Newton-GMRES, 107
Bi-CG, 47 Characteristic polynomial, 34
algorithm, 47 Chord method, 74
Bi-CGSTAB, 50 algorithm, 74
algorithm, 50 convergence, 76
¬nite di¬erence, 110 Condition number, 3
Bi-conjugacy, 47 Conjugate Gradient
Bi-Conjugate Gradient, 47 algorithm, 22
algorithm, 47 ¬nite termination, 14
Bi-orthogonality, 47 minimization property, 12
Bounded deterioration, 118, 121 use of residual polynomials, 14
Breakdown, 47 Conjugate Gradient Squared, 48
Broyden sequence, 120 algorithm, 49
Broyden™s method, 113 Conjugate transpose, 34
convergence Contraction mapping, 67
linear equations, 118 Contraction Mapping Theorem, 67
nonlinear equations, 120 Convection-Di¬usion Equation
implementation, 123 Broyden™s method, 130
limited memory, 123 Newton“Armijo, 146
restarting, 123 Newton-GMRES, 108
sparse, 133 solution
Brsol Broyden™s method, 130
algorithm, 126 Convergence theorem
Brsola Broyden™s method
algorithm, 145 linear equations, 119
163

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.




164 INDEX

nonlinear equations, 123 loss of orthogonality, 40, 41
chord method, 76, 77 modi¬ed, 40
contraction mapping, 67
H-equation, 87
¬nite di¬erence Newton, 81
solution
inexact Newton™s method, 96,
Broyden™s method, 128
99
Newton™s method, 87
Newton™s method, 71
Newton-GMRES, 107
Newton“Armijo, 141
H¨lder Continuity, 91
o
Newton-GMRES, 103
High order methods, 78
secant method, 82
Hybrid algorithms, 36
Shamanskii method, 79
Induced matrix norm
DASPK, 110
de¬nition, 3
Dennis“Mor´ Condition, 114
e
Inexact Newton method, 95
superlinear convergence, 115
Inner iteration, 100
Diagonalizable matrix, 34
Inverse power method, 94
Diagonalizing transformation, 34
Inverse secant equation, 132
Di¬erence approximation, 79
Inverse Tangent
choice of h, 80
Newton“Armijo, 146
directional derivative, 80
Iteration matrix, 5
Jacobian, 80
Iteration statistics, 91
nonlinearity, 80
Jacobi
Elementary Jordan block, 60
algorithm, 8
Fixed point, 66 convergence result, 8
Fixed-point iteration, 66 preconditioning, 9
Forcing term, 95 Jacobi preconditioning, 24
choice of, 104 Jordan block, 60
Gauss“Seidel Kantorovich Theorem, 83
algorithm, 9 Krylov subspace, 11
Givens rotation, 43
Globally convergent algorithm, 135 Left preconditioning, 36
GMRES Limited memory, 123
algorithm, 40, 45 Line Search
diagonalizable matrices, 34 parabolic
¬nite di¬erences, 101 three-point, 143
¬nite termination, 34 two-point, 142
GMRES(m), 39, 46 polynomial, 142
algorithm, 46 Line search, 135, 136
loss of orthogonality, 41 Linear PDE
minimization property, 33 Bi-CGSTAB, 57
restarts, 39, 46 Broyden™s method, 127
use of residual polynomials, 33 CGNR, 55
Gram“Schmidt process, 37 GMRES, 54



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.




165
INDEX

solution algorithm, 23
Broyden™s method, 127 Preconditioning
TFQMR, 58 conjugate gradient, 19
Lipschitz continuous GMRES, 36
de¬nition, 67 incomplete
Local improvement, 75 factorization, 24, 36
inexact, 100 Jacobi, 24
Poisson solver, 27, 36, 54
Matrix norm, 3 polynomial, 24, 36
Matrix splitting, 7 Richardson iteration, 6
Modi¬ed Bratu Problem, 132
Quasi-minimization, 52
Newton direction, 136
Quasi-Newton methods, 113
Newton™s method, 71
Quasi-residual, 51
algorithm, 74
Quasi-residual norm, 52
convergence rate, 71
¬nite di¬erences, 81 Relaxation parameter, 9
stagnation, 81 Reorthogonalization, 41
inexact, 95 Residual
monotone convergence, 92 linear, 11
termination, 72 as error estimate, 4
Newton-GMRES, 101 nonlinear
convergence rates, 103
as error estimate, 72
¬nite di¬erences, 101
relative nonlinear, 72
safeguarding, 105
Residual polynomials
Newton-iterative method, 100
application to CG, 14
Normal matrix, 34
application to CGNR, 25
Nsol
application to GMRES, 33
algorithm, 86
application to TFQMR, 52
Nsola
de¬nition, 14
algorithm, 138
Richardson iteration, 5
Nsolgm
nonlinear, 66
algorithm, 105
Right preconditioning, 36
Outer iteration, 100
Schubert algorithm, 133
Over solving, 104
Search direction, 136
Secant equation, 113
Picard iteration, 66
Secant method, 82
Poisson solver, 24, 27
convergence, 82
preconditioner
q-order, 91
for CG, 24, 27
r-order, 91
for GMRES, 36, 54
Secant update, 113
Polynomial preconditioning, 24, 36
Shamanskii method, 78
Richardson iteration, 7
algorithm, 78
Positive de¬nite matrix, 11
convergence, 79
Preconditioned CG

<< . .

. 25
( : 26)



. . >>