Brezinski / Wuytack Numerical Analysis: Historical Developments in the 20th Century

1. Auflage 2012
ISBN: 978-0-444-59858-5
Verlag: Elsevier Science & Techn.
Format: EPUB
Kopierschutz: 6 - ePub Watermark

E-Book, Englisch, 512 Seiten

Numerical analysis has witnessed many significant developments in the 20th century. This book brings together 16 papers dealing with historical developments, survey papers and papers on recent trends in selected areas of numerical analysis, such as: approximation and interpolation, solution of linear systems and eigenvalue problems, iterative methods, quadrature rules, solution of ordinary-, partial- and integral equations. The papers are reprinted from the 7-volume project of the Journal of Computational and Applied Mathematics on '/homepage/sac/cam/na2000/index.htmlNumerical Analysis 2000'. An introductory survey paper deals with the history of the first courses on numerical analysis in several countries and with the landmarks in the development of important algorithms and concepts in the field.

Autoren/Hrsg.

Brezinski, C.

Wuytack, L.

Inhaltsverzeichnis

1;Front Cover;1
2;Numerical Analysis: Historical Developments in the 20th Century;4
3;Copyright Page;5
4; Contents;6
5;Chapter 1. Numerical analysis in the twentieth century;8
5.1;The scenery;9
5.2;The actors;11
5.3;Landmarks;24
5.4;Acknowledgements:;40
5.5;References;40
6;Chapter 2. Approximation in normed linear spaces;48
6.1;Abstract;48
6.2;1. Introduction;48
6.3;2. Linear approximation;49
6.4;3. Nonlinear approximation;66
6.5;Acknowledgements;76
6.6;References;76
7;Chapter 3. A tutorial history of least squares with applications to astronomy and geodesy;84
7.1;Abstract;84
7.2;1. Introduction;84
7.3;2. An ancient history of curve and surface fitting;85
7.4;3. Weighted ordinary least squares and geodesy;89
7.5;4. Unitary factorizations and constrained least squares;93
7.6;5. The singular-value decomposition and error analysis;101
7.7;6. Matrix approximation and total least squares;106
7.8;7. Nonlinear least squares;115
7.9;References;117
8;Chapter 4. Convergence acceleration during the 20th century;120
8.1;1. Introduction;120
8.2;2. Scalar sequences;121
8.3;3. The vector case;133
8.4;4. Conclusions and perspectives;134
8.5;Acknowledgements;135
8.6;References;135
9;Chapter 5. On the history of multivariate polynomial interpolation;142
9.1;Abstract;142
9.2;1. Introduction;142
9.3;2. Kronecker, Jacobi and multivariate interpolation;143
9.4;3. Bivariate tables, the natural approach;146
9.5;4. Salzer's papers: from bivariate tables to general sets;147
9.6;5. Reduction of a problem to other simpler ones;149
9.7;6. The finite element approach;151
9.8;7. Hermite problems;151
9.9;8. Other approaches;152
9.10;Acknowledgements;152
9.11;References;153
10;Chapter 6. Numerical linear algebra algorithms and software;156
10.1;Abstract;156
10.2;1. Introduction;156
10.3;2. Dense linear algebra algorithms;157
10.4;3. The influence of computer architecture on performance;161
10.5;4. Dense linear algebra libraries;164
10.6;5. Future research directions in dense algorithms;170
10.7;6. Sparse linear algebra methods;172
10.8;7. Direct solution methods;173
10.9;8. Iterative solution methods;174
10.10;9. Libraries and standards in sparse methods;178
10.11;References;178
11;Chapter 7. Iterative solution of linear systems in the 20th century;182
11.1;Abstract;182
11.2;1. Introduction;182
11.3;2. The quest for fast solvers: a historical perspective;184
11.4;3. Relaxation-based methods;188
11.5;4. Richardson and projection methods;189
11.6;5. Second-order and polynomial acceleration;191
11.7;6. Krylov subspace methods: the first period;193
11.8;7. Krylov subspace methods: the second period;196
11.9;8. Accelerators are not enough: preconditioning methods;200
11.10;9. Multigrid methods;205
11.11;10. Outlook;206
11.12;Acknowledgements;206
11.13;References;206
12;Chapter 8. Eigenvalue computation in the 20th century;216
12.1;Abstract;216
12.2;1. Sources;216
12.3;2. Introduction;218
12.4;3. Canonical forms;219
12.5;4. Perturbation theorems;221
12.6;5. Jacobi's method;223
12.7;6. Power method;224
12.8;7. Reduction algorithms;226
12.9;8. Iterative methods;230
12.10;9. Related topics;234
12.11;10. Software;238
12.12;11. Epilogue;240
12.13;Acknowledgements;241
12.14;References;241
13;Chapter 9. Historical developments in convergence analysis for Newton's and Newton-like methods;248
13.1;Abstract;248
13.2;1. Introduction;248
13.3;2. Newton's method;249
13.4;3. Newton-like methods;254
13.5;4. Secant method;258
13.6;5. Halley's and Chebyshev's methods;259
13.7;6. A class of iterative methods for not necessarily differentiable equations;263
13.8;7. Concluding remarks;266
13.9;Acknowledgements;267
13.10;References;267
14;Chapter 10. A survey of truncated-Newton methods;272
14.1;Abstract;272
14.2;1. Introduction;272
14.3;2. Controlling the convergence rate;276
14.4;3. Guaranteeing convergence;277
14.5;4. Computing second-derivative information;279
14.6;5. Nonconvex problems;280
14.7;6. Preconditioning;281
14.8;7. Parallel algorithms;282
14.9;8. Practical behavior;282
14.10;9. Software;283
14.11;10. Constrained problems;284
14.12;11. Conclusions, recommendations;285
14.13;Acknowledgements;285
14.14;References;285
15;Chapter 11. Cubature formulae and orthogonal polynomials;288
15.1;Abstract;288
15.2;1. Introduction;288
15.3;2. Basic concepts and notations;289
15.4;3. Radon's formulae of degree 5;292
15.5;4. Multivariate orthogonal polynomials;294
15.6;5. Lower bounds;300
15.7;6. Methods of construction;303
15.8;7. Cubature formulae of arbitrary degree;312
15.9;Acknowledgements;315
15.10;References;315
16;Chapter 12. Computation of Gauss-type quadrature formulas;320
16.1;Abstract;320
16.2;1. Introduction;320
16.3;2. What to do when the recursion coefficients are known;323
16.4;3. Obtaining recursion coefficients;324
16.5;4. Gauss-type quadratures;326
16.6;5. Two-term recursion coefficients;329
16.7;6. Existence and numerical considerations;331
16.8;7. Conclusion;334
16.9;Acknowledgements;334
16.10;References;335
17;Chapter 13. A review of algebraic multigrid;338
17.1;Abstract;338
17.2;1. Introduction;338
17.3;2. Algebraic versus geometric multigrid;340
17.4;3. The classical AMG approach;342
17.5;4. Applications and performance;348
17.6;5. AMG based on mere F-relaxation;352
17.7;6. Aggregation-type AMG;355
17.8;7. Further developments and conclusions;361
17.9;References;364
18;Chapter 14. From finite differences to finite elements A short history of numerical analysis of partial differential equations;368
18.1;Abstract;368
18.2;0. Introduction;368
18.3;1. The Courant–Friedrichs–Lewy paper;371
18.4;2. Finite difference methods for elliptic problems;373
18.5;3. Finite difference methods for initial value problems;376
18.6;4. Finite differences for mixed initial–boundary value problems;384
18.7;5. Finite element methods for elliptic problems;389
18.8;6. Finite element methods for evolution equations;397
18.9;7. Some other classes of approximation methods;404
18.10;8. Numerical linear algebra for elliptic problems;409
18.11;References;413
18.12;Survey articles and books;420
19;Chapter 15. A perspective on the numerical treatment of Volterra equations;422
19.1;Abstract;422
19.2;1. Introduction;422
19.3;2. Basic theory;423
19.4;3. Some numerical methods;427
19.5;4. Relationship to ODE methods;431
19.6;5. RK processes;433
19.7;6. Collocation and related methods;436
19.8;7. Numerical analysis;439
19.9;8. Some approaches to convergence analysis;441
19.10;9. Stability;443
19.11;10. Concluding remarks;448
19.12;Acknowledgements;450
19.13;References;450
20;Chapter 16. Numerical methods for ordinary differential equations in the 20th century;456
20.1;Abstract;456
20.2;1. Introduction;456
20.3;2. Early work on numerical ordinary differential equations;457
20.4;3. The modern theory of linear multistep methods;463
20.5;4. The modern theory of Runge–Kutta methods;467
20.6;5. Nontraditional methods;474
20.7;6. Methods for stiff problems;476
20.8;7. The beginnings of differential equation software;480
20.9;8. Special problems;482
20.10;References;483
21;Chapter 17. Retarded differential equations;486
21.1;Abstract;486
21.2;1. Introduction;486
21.3;2. Background theory;488
21.4;3. Background numerical analysis;493
21.5;4. Approximate solutions — existence, uniqueness, convergence;497
21.6;5. Numerical stability;503
21.7;6. Further issues and concluding remarks;508
21.8;Acknowledgements;509
21.9;References;509

Leseproben

Approximation in normed linear spaces

G.A. Watson [e-mail]    Department of Mathematics, University of Dundee, Dundee DD1 4HN Scotland, UK

Abstract

A historical account is given of the development of methods for solving approximation problems set in normed linear spaces. Approximation of both real functions and real data is considered, with particular reference to Lp (or lp) and Chebyshev norms. As well as coverage of methods for the usual linear problems, an account is given of the development of methods for approximation by functions which are nonlinear in the free parameters, and special attention is paid to some particular nonlinear approximating families. © 2000 Elsevier Science B.V. All rights reserved.

1 Introduction

The purpose of this paper is to give a historical account of the development of numerical methods for a range of problems in best approximation, that is problems which involve the minimization of a norm. A treatment is given of approximation of both real functions and data. For the approximation of functions, the emphasis is on the use of the Chebyshev norm, while for data approximation, we consider a wider range of criteria, including the other lp norms, 1 = p < 8. As well as the usual linear problems, a general account is given of nonlinear best approximation, and we also consider some special cases. Only a passing mention is made of least-squares problems, as that is considered elsewhere. The focus is also entirely on the approximation of real quantities, and so best approximation of complex quantities is not covered. A partial justification of this is that dealing with problems in generality as complex ones would introduce additional complication not entirely justified by the additional algorithmic initiatives.

Since we are concerned here with historical development, technical details are not included for their own sake. The intention is, where appropriate, to be descriptive, rather to give a technically rigorous and detailed account of methods. However, it seemed necessary at times for the sake of comprehensibility, and in order to fully appreciate algorithmic developments, to include a reasonable amount of technical detail.

Obviously a major factor in the development of methods has been the advent of powerful computing facilities, as this has opened up opportunities to tackle a wide range of practical problems. Whereas at one time, the main consideration may have been elegance and simplicity, with attention perhaps focussed on a set of problems satisfying “classical” assumptions, those considerations now usually have to take second place to the treatment of problems which are seen to be of practical importance, for which algorithms have to be robust and efficient.

The paper is effectively divided into two parts, the first (Section 2) being concerned with approximation by linear families, and the second (Section 3) being concerned with approximation by nonlinear families. These sections themselves further subdivide into two parts, where we consider separately approximation of data and of functions, and these are dealt with in that order within the two sections, with a further breakdown in what seems to be a reasonably natural way to take account of important special cases.

For the approximation of functions, we are primarily concerned with univariate functions on an interval [a, b], because that is where most effort has been concentrated. However, some relevant comments are made on the extent to which multivariate functions may also be treated, with a few references made to this.

2 Linear approximation

The approximation of a given function defined on an interval by a linear combination of given functions is the most fundamental problem in approximation theory. The functions involved are usually continuous, and this can be thought of as a continuous infinite dimensional approximation problem. If the functions are replaced by vectors in m, then we have a class of finite dimensional or discrete problems, many of which have their origins in data fitting. That solutions to linear best approximation problems always exist is a result which goes back at least to Riesz in 1918 [174]. We will consider the finite dimensional problem first, and begin by making some general remarks, before looking at special cases.

2.1 Linear approximation in m

Let A ? m × n where m = n, and let b ? m. Then the statement of a linear best approximation problem in mcan be given as

x?Rntominimize?r?,

  (1)

where

=Ax-b,

and ?.? is a given norm on m. The dependence of r on x will generally be suppressed, unless confusion is possible.

This particular problem has attracted enormous interest. It will be assumed throughout that rank (A) = n, and there is no x such that r = 0. These are not essential, neither in theory nor in practice; however, they are conditions that are normally satisfied in practice, and their assumption considerably simplifies the presentation. If the norm is a differentiable function of x, then we can easily characterize a minimum by zero derivative conditions: these are necessary, and, exploiting convexity, also sufficient. The best known example is when the norm is the least-squares norm, when zero derivative conditions just give the usual normal equations

TAx=ATb.

The method of least squares is considered in detail elsewhere. But in a data fitting context, other lp norms, particularly those for values of p satisfying 1 = ? < 2 are also important. The reason for this is that it is common for the usual conditions justifying the use of the l2 norm not to hold, for example there may be wild points or gross errors in the data, and these other norms give reduced weight to these wild points. This is considered in Sections 2.2 and 2.3. Of great interest also has been the use of the Chebyshev norm; this is perhaps of less value in a data fitting context, but problems arise for example in continuous function approximation when the region of approximation is discretized. The problem is rich in structure and the theory is a beautiful one; we consider this case in Section 2.4.

We will restrict attention here to the problem (1), although there are many modifications of that problem which are relevant in a data fitting context. Most modifications have only been given serious treatment comparatively recently, and so they are of lesser interest from a historical point of view.

2.2 Linear l1 approximation in m

Consider now the problem (1) with the l1 norm

1=?i=1mri.

  (2)

This problem has a long history: its statement goes back well into the mid eighteenth century, and predates the introduction of least squares. Certainly, it was used in work of Laplace in 1786, in solving the overdetermined system of linear equations determining planetary orbits [110]. The first systematic methods for solving this problem seem due to Edgeworth [61]; in 1887 he gave a method based on tabulation, and in 1888 a method for the case when n = 2 which was essentially graphical and conceptual, but based on calculating descent directions. In 1930, Rhodes [167], motivated by the problem of fitting a parabola to data, tried Edgeworth’s later method but found it “cumbrous”. He gave a method where each iteration was calculated by solving 2 interpolation conditions for 2 of the parameters, and minimizing with respect to the remaining parameter. A proof that this kind of approach can give a solution was established by Singleton in 1940 [182]. A detailed historical account is given by Farebrother in a 1987 paper [63], covering the period 1793 to 1930.1

The first modern systematic study of this problem appears to be by Motzkin and Walsh [131,132] in the late 1950s, and characterization results are given in the 1964 book by Rice [172]. A convenient form of these may be deduced from these results or as a simple consequence of applying to this special case known results in abstract approximation theory: we will not attempt to go down that historical route, since it is something of a diversion from the main theme. However, it is the case that a vector x ? n solves the l1 problem if and only if there exists a vector v ? m satisfying

Tv=0,

where ?v?8 = 1, and vi = sign(ri) whenever ri ? 0. The first simple (direct) proof of this was probably given by Watson [199] in 1980. A formal treatment of the important result that when A has rank n, a...