[Search] |

ABOUT:
[Introduction]POINTERS:
[Texts]## 65: Numerical analysis |

Numerical analysis involves the study of methods of computing numerical data. In many problems this implies producing a sequence of approximations; thus the questions involve the rate of convergence, the accuracy (or even validity) of the answer, and the completeness of the response. (With many problems it is difficult to decide from a program's termination whether other solutions exist.) Since many problems across mathematics can be reduced to linear algebra, this too is studied numerically; here there are significant problems with the amount of time necessary to process the initial data. Numerical solutions to differential equations require the determination not of a few numbers but of an entire function; in particular, convergence must be judged by some global criterion. Other topics include numerical simulation, optimization, and graphical analysis, and the development of robust working code.

Numerical linear algebra topics: solutions of linear systems AX = B, eigenvalues and eigenvectors, matrix factorizations. Calculus topics: numerical differentiation and integration, interpolation, solutions of nonlinear equations f(x) = 0. Statistical topics: polynomial approximation, curve fitting.

For papers involving machine computations and programs in a specific mathematical area, See Section --04 in that area. This includes computational issues in group theory, number theory, geometry, statistics, and so on; for each of these fields there are software packages or libraries of code which are discussed on those index pages. (On the other hand, most results of numerical integration, say, are in this section rather than Measure and Integration; topics in optimization are in section 65K rather than Operations Research.)

For calculations of a combinatorial nature and for graph-theoretic questions such as the traveling salesman problem or scheduling algorithms, see Combinatorics. (These are distinguished by the discrete nature of the solution sought.) Portions of that material -- particularly investigations into the complexity of the algorithms -- is also treated in Computer Science.

General issues of computer use, such as system organization and methodology, or artificial intelligence, are certainly in computer science. Topics in computer algebra or symbolic calculation are treated separately.

Issues concerning limitations of specific hardware or software are not strictly speaking part of mathematics at all but often illustrate some of the issues addressed in numerical analysis. Some of these can be seen in examples seen below.

Applications of numerical analysis occur throughout the fields of applied (numerical) mathematics, in particular in the fields of physics (sections 70-86). Many of these areas including subheading e.g. for finite element methods (which are primarily treated here in 65L - 65P).

There are also applications to areas typically considered part of pure mathematics; for example, there is substantial work done on the roots of 26C:Polynomials and rational functions.

This area is undergirded by the areas of analysis. See for example Real analysis or Complex analysis for general topics of convergence.

The study of whole numbers and their properties (e.g. solving equations in integers) is not numerical analysis at all but Number Theory.

This image slightly hand-edited for clarity.

- 65A05: Tables
- 65B: Acceleration of convergence
- 65C: Probabilistic methods, simulation and stochastic differential equations.
- 65D: Numerical approximation, Primarily algorithms; for theory, see 41-XX
- 65E05: Numerical methods in complex analysis (potential theory, etc.), For numerical methods in conformal mapping, See 30C30
- 65F: Numerical linear algebra
- 65G: Error analysis and interval analysis
- 65H: Nonlinear algebraic or transcendental equations
- 65J: Numerical analysis in abstract spaces
- 65K: Mathematical programming, optimization and variational techniques
- 65L: Ordinary differential equations
- 65M: Partial differential equations, initial value and time-dependent initial-boundary value problems
- 65N: Partial differential equations, boundary value problems
- 65P: Numerical problems in dynamical systems [See also 37Mxx] [new in 2000]
- 65Q05: Difference and functional equations, recurrence relations
- 65R: Integral equations, integral transforms, see also 45LXX
- 65S05: Graphical methods
- 65T: Numerical methods in Fourier analysis
- 65Y: Computer aspects of numerical algorithms
- 65Z05: Applications to physics [new in 2000]

This is one of the largest areas of the Math Reviews database, with many of the subfields being also large. (65N30, Finite Element Methods, is among the largest of the 5-digit areas, too). This field has more subfields than almost any other!

Browse all (old) classifications for this area at the AMS.

"The state of the art in numerical analysis", Proceedings of the conference held at the University of York, York, April 1996. Edited by I. S. Duff and G. A. Watson. The Institute of Mathematics and its Applications Conference Series. New Series, 63. The Clarendon Press, Oxford University Press, New York, 1997. 562 pp. ISBN 0-19-850014-9 MR99a:65008 (There are also older proceedings with the same title.)

Shampine, L. F.: "What everyone solving differential equations numerically should know", Computational techniques for ordinary differential equations (Proc. Conf. Univ. Manchester, Dec. 18--20, 1978), pp. 1--17, Academic Press, London-New York-Toronto, Ont., 1980. 84e:65089

Nievergelt, Yves: "Total least squares: state-of-the-art regression in numerical analysis", SIAM Rev. 36 (1994), no. 2, 258--264. MR95a:65077

Sobol, Ilya M.: "A primer for the Monte Carlo method", CRC Press, Boca Raton, FL, 1994. 107 pp. ISBN 0-8493-8673-X MR95e:65001

"State-of-the-art surveys on finite element technology", Edited by Ahmed K. Noor and Walter D. Pilkey. American Society of Mechanical Engineers (ASME), New York, 1983. 530 pp. MR85h:65003

Babuska, I.: "The *p* and *h*-*p* versions of the finite element method: the state of the art",
Finite elements (Hampton, VA, 1986), 199--239, ICASE/NASA LaRC Ser.;
Springer, New York-Berlin, 1988. MR90b:65197

PostScript/PDF versions of Numerical Recipes (well-known and oft-debated general introduction)

"Reviews in Numerical Analysis 1980-1986", AMS

There is a USENET newsgroup sci.math.num-analysis. Newsgroup FAQ:

- http://www.indra.com/~sullivan/q10.html Mathcom
- This FAQ is usually available from MIT's rtfm and its mirrors: ftp://rtfm.mit.edu/pub/usenet/news.answers/num-analysis/faq/part1 MIT's rtfm
- If not, a compressed (with gzip) version is at: ftp://ftp.mathcom.com/mathcom/nafaq.txt.gz Mathcom ftp

There is a directory of newsletters related to scientific computation at the site of the . See in addition the Numerical Analysis Digest. There is also a mailing list on Reliable Computing; send email to majordomo@interval.usl.edu with the message "subscribe reliable_computing"

Online introductory book (U.S. Department of Energy)

Old-timers may remember that optimal formulae were often precomputed; see e.g. Abramowitz, M. and Stegun, C.A. (Ed.). "Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables", 9th printing, 1972, New York: Dover.

FElt Finite Elements software.

Following is a (still rather haphazard) collection of links to some popular numerical mathematical computation software. For other links to major all-in-one mathematical computing environments see the corresponding list in 68W30: Symbolic computation; the largest of those have numerical capabilities as well.

- Pointer to Indiana University's "Knowledge Base" (Computer FAQs)
- Home page for Matlab: http://www.mathworks.com/.
- Home page for Mideva and Matcom (Matlab interpreter/compiler): http://www.mathtools.com
- Pointer to Minitab (statistical software)
- Pointer to Octave, a noncommercial alternative to Matlab
- Pointer to SciLab (free numerical software).

Finally, some pointers to classes of algorithms. Note that mathematical algorithms constitute one of the most web-accessible bodies of human knowledge available. A search at one of these sites can easily save considerable programming headaches! Highly recommended are NETLIB and GAMS. See also TOMS.

- Illustration of search of GAMS numerical software library.
- For example, the GAMS software tree has a node for numerical differentiation.
- Description of Netlib from D-Lib Magazine [Digital Libraries]
- [Offsite] Finite Element Method site
- Pointer to sample Finite Element code.
- Pointer to Numerical Recipes site, and citation to alternative text.
- Pointer to shareware versions of Numerical Recipes codes.

- Highly recommended: Numerical methods (or this European mirror)
- Numerical Analysis at Concordia. (Nice overview, including online lessons on basic topics)
- NA-Net
- NAFEMS (Professional organization)
- Internet Finite Element Resources
- German Scientific Computing Home Page
- Numerical analysis for physicists
- Numerical Recipes in C
- Numerical Recipes in C
- GAMS : Guide to Available Mathematical Software
- Netlib Repository at UTK/ORNL (Software)
- Here are the AMS and Goettingen resource pages for area 65.

- Pointers for General numerical analysis software
- Pointer to an interval arithmetic tutorial.
- Performing arithmetic on real numbers using continued fractions.
- Best way to compute numerical solutions to a quadratic polynomial.
- Calculating the roots of polynomials. (general guide).
- Laguerre's method for determining zeroes of complex analytic functions (in a region).
- Bairstow's method for finding the roots of a polynomial.
- Dekker's algorithm of finding zeros of functions.
- Software to compute all zeros of an analytic function in a rectangle.
- Example of a bad Newton's method problem.
- Example of oscillation in Newton's method.
- Humdrum instance of Newton's method.
- Use Newton's method for sets of functions of several variables? (Yes)
- Citation: variations of Newton's method (better around multiple roots).
- Improvements to Newton's method
- How might Newton's method fail?
- Computing inverses without division, using Newton's method.
- Numerical calculation of "special functions" (trig/exp/log/sqrt...)
- Numerical evaluation of the error function.
- CORDIC algorithms for evaluating elementary (trig. etc.) functions -- citations, summary, pointers to code.
- How do calculators compute sin(x) (etc.)?
- Basic algorithm for computing trigonometric functions with CORDIC algorithms.
- [OFFSITE] CORDIC bibliography and related informations.
- Citation: computation of elementary functions.
- Efficient iterative computation of sqrt(x)
- Calculating logarithms of the gamma function (and factorials).
- Applications of 3D (discrete) Fourier transforms to data compression.
- Discussion of FFT procedures for sizes not a power of two; pointers to implementations
- Pointers to FFT code and descriptions
- Interpolating a function on R^2 from values at discrete points.
- Interpolating a function on R^2 from values at discrete points.
- Overview of options and pitfalls of (1-dimensional) interpolation
- Basic pointers: netlib, gams
- Pointer to HOMPACK (numerically solve systems of polynomial equations).
- Description of AXIOM (numerically solve systems of polynomial equations by continuation).
- Citations, cautions to numerical fitting of polynomial to data
- How to fit a curve y(x)=a+b*sin(c*x+d) to data: ODRPACK
- Source code for Hough transform
- Pointer for C++ package Range -- variable precision 'range arithmetic'
- Runge-Kutta methods of integration.
- How to select points and weights for Gauss quadrature when computing numerical integrals?
- Use of orthogonal polynomials for quadrature (numerical integration a la Gauss-Legendre).
- Pointer to code for computing elliptic integrals
- Iterative construction of a conformal mapping between two domains.
- Pointers to basic Finite Element resources.
- Finite-volume method for solving partial differential equations.
- Pointers to techniques for mesh generation for PDEs.
- Mesh generation with mgnet for solving Laplace's equation.
- Summary of Runge-Kutta methods for solving ODEs.
- Adams method for solving ODEs (a predictor-corrector method).
- Gear's method for solving ODEs.
- Solving the Ricatti equation.
- Solving delay differential equations.
- Summary of basic methods for integrating PDEs.
- Basic comparison of root-finding methods
- Challenge problems for root-finding algorithms
- Various methods to find (all) the zeros of a complex function
- Hirano's method root finding
- Numerical root-finding methods appropriate with multiple roots
- Examples of failure of Newton's method
- Multidimensional secant methods (quasi-Newton methods) for finding zeros
- Continuous Newton's Method
- Intersection points of two cubic parametric curves
- Outline of Runge-Kutta method (ODE) and Jenkins-Traub method (polynomial root-finding)
- First appearance of Gaussian quadrature
- Basic description of Gauss quadrature
- General comparison of numerical integration methods
- Comparison of errors from various numerical integration algorithms
- Pointer to Clenshaw-Curtis method of integration
- Pointer to Runge Kutta 8th order methods of solving differential equations
- Semi-infinite Gauss integration rule
- Integrals over infinite range
- Filon's numerical integration formula
- Evaluating numerical integrals of oscillating functions
- Computing a double integral
- Numerical integration methods over the cube
- Gaussian integration formula on a triangle
- Numerically integrating monomials on 2- and 3-dimensional cells
- Integration in R^n: Monte Carlo or grid methods better?
- Integration and interpolation over a sphere
- Karatsuba multiplication of large integers
- Using Newton's method to divide by using multiplication
- Computing sqrt or quotients with very many digits of accuracy
- Computing derivatives numerically, using piecewise-polynomial fit, Savitsky-Golay filters or complex integration
- Interpolating from scattered data in R^3
- Thin plate splines
- Akima's interpolating spline
- Differences between Fast Fourier Transform and Discrete Fourier Transform
- Pointers to Fast Fourier Transform codes
- Does FFT require code length a power of 2?
- What is a Monte Carlo method?
- Finding inflection points from numerical data
- Numerical computation of surface minimizing a functional
- Computing best approximation of a positive function by positive functions from appropriate families
- Quick integer square root algorithm
- Methods of describing roots of high-order polynomials; decision procedure to decide whether distinct
- Reference: algorithms for solving ordinary differential equations numerically
- Tutorials on Finite Element Methods
- Different approaches in algebraic and geometric multigrid methods
- Using multigrid solvers for hyperbolic CFD problems
- Question on numerical solution of the diffusion equation
- Numerical solution of Maxwell's equations
- A collection of examples of calculator and computer errors (hardware constraints and symbolic-algebra bloopers)

Last modified 2000/12/14 by Dave Rusin. Mail: