numerical analysis

the branch of mathematics dealing with methods for obtaining approximate numerical solutions of mathematical problems.

[1925-30]

* * *

Branch of applied mathematics that studies methods for solving complicated equations using arithmetic operations, often so complex that they require a computer, to approximate the processes of analysis (i.e., calculus).

The arithmetic model for such an approximation is called an algorithm, the set of procedures the computer executes is called a program, and the commands that carry out the procedures are called code. An example is an algorithm for deriving π by calculating the perimeter of a regular polygon as its number of sides becomes very large. Numerical analysis is concerned not just with the numerical result of such a process but with determining whether the error at any stage is within acceptable bounds.

* * *

▪ mathematics

Introduction

      area of mathematics and computer science that creates, analyzes, and implements algorithms (algorithm) for obtaining numerical solutions to problems involving continuous variables. Such problems arise throughout the natural sciences, social sciences, engineering, medicine, and business. Since the mid 20th century, the growth in power and availability of digital computers (digital computer) has led to an increasing use of realistic mathematical models (mathematical model) in science and engineering, and numerical analysis of increasing sophistication is needed to solve these more detailed models of the world. The formal academic area of numerical analysis ranges from quite theoretical mathematical studies to computer science issues.

      With the increasing availability of computers, the new discipline of scientific computing, or computational science, emerged during the 1980s and 1990s. The discipline combines numerical analysis, symbolic mathematical computations, computer graphics, and other areas of computer science to make it easier to set up, solve, and interpret complicated mathematical models of the real world.

Common perspectives in numerical analysis

      Numerical analysis is concerned with all aspects of the numerical solution of a problem, from the theoretical development and understanding of numerical methods to their practical implementation as reliable and efficient computer programs. Most numerical analysts specialize in small subfields, but they share some common concerns, perspectives, and mathematical methods of analysis. These include the following:

● When presented with a problem that cannot be solved directly, they try to replace it with a “nearby problem” that can be solved more easily. Examples are the use of interpolation in developing numerical integration methods and root-finding methods.

● There is widespread use of the language and results of linear algebra (algebra, linear), real analysis (analysis), and functional analysis (analysis) (with its simplifying notation of norms, vector spaces (vector space), and operators).

● There is a fundamental concern with error, its size, and its analytic form. When approximating a problem, it is prudent to understand the nature of the error in the computed solution. Moreover, understanding the form of the error allows creation of extrapolation processes to improve the convergence behaviour of the numerical method.

● Numerical analysts are concerned with stability, a concept referring to the sensitivity of the solution of a problem to small changes in the data or the parameters of the problem. Consider the following example. The polynomial

p(x) = (x − 1)(x − 2)(x − 3)(x − 4)(x − 5)(x − 6)(x − 7),

or expanded, 

p(x) = x⁷ − 28x⁶ + 322x⁵ − 1,960x⁴ − 6,769x³ − 13,132x² + 13,068x − 5,040

has roots that are very sensitive to small changes in the coefficients. If the coefficient of x⁶ is changed to −28.002, then the original roots 5 and 6 are perturbed to the complex numbers 5.459  0.540i—a very significant change in values. Such a polynomial p(x) is called unstable or ill-conditioned with respect to the root-finding problem. Numerical methods for solving problems should be no more sensitive to changes in the data than the original problem to be solved. Moreover, the formulation of the original problem should be stable or well-conditioned.

● Numerical analysts are very interested in the effects of using finite precision computer arithmetic. This is especially important in numerical linear algebra, as large problems contain many rounding errors.

● Numerical analysts are generally interested in measuring the efficiency (or “cost”) of an algorithm. For example, the use of Gaussian elimination (Gauss elimination) to solve a linear system Ax = b containing n equations will require approximately ²ⁿ³/₃ arithmetic operations. Numerical analysts would want to know how this method compares with other methods for solving the problem.

Modern applications and computer software

      Numerical analysis and mathematical modeling are essential in many areas of modern life. Sophisticated numerical analysis software is commonly embedded in popular software packages (e.g., spreadsheet programs) and allows fairly detailed models to be evaluated, even when the user is unaware of the underlying mathematics. Attaining this level of user transparency requires reliable, efficient, and accurate numerical analysis software, and it requires problem-solving environments (PSE) in which it is relatively easy to model a given situation. PSEs are usually based on excellent theoretical mathematical models, made available to the user through a convenient graphical user interface.

Applications

       computer-aided engineering (CAE) is an important subject within engineering, and some quite sophisticated PSEs have been developed for this field. A wide variety of numerical analysis techniques is involved in solving such mathematical models. The models follow the basic Newtonian laws of mechanics, but there is a variety of possible specific models, and research continues on their design. One important CAE topic is that of modeling the dynamics of moving mechanical systems, a technique that involves both ordinary differential equations and algebraic equations (generally nonlinear). The numerical analysis of these mixed systems, called differential-algebraic systems, is quite difficult but necessary in order to model moving mechanical systems. Building simulators for cars, planes, and other vehicles requires solving differential-algebraic systems in real time.

      Another important application is atmospheric modeling. In addition to improving weather forecasts, such models are crucial for understanding the possible effects of human activities on the Earth's climate. In order to create a useful model, many variables must be introduced. Fundamental among these are the velocity V(x, y, z, t), pressure P(x, y, z, t), and temperature T(x, y, z, t), all given at position (x, y, z) and time t. In addition, various chemicals exist in the atmosphere, including ozone, certain chemical pollutants, carbon dioxide, and other gases and particulates, and their interactions have to be considered. The underlying equations for studying V(x, y, z, t), P(x, y, z, t), and T(x, y, z, t) are partial differential equations; and the interactions of the various chemicals are described using some quite difficult ordinary differential equations. Many types of numerical analysis procedures are used in atmospheric modeling, including computational fluid mechanics and the numerical solution of differential equations. Researchers strive to include ever finer detail in atmospheric models, primarily by incorporating data over smaller and smaller local regions in the atmosphere and implementing their models on highly parallel supercomputers.

      Modern businesses rely on optimization methods to decide how to allocate resources most efficiently. For example, optimization methods are used for inventory control, scheduling, determining the best location for manufacturing and storage facilities, and investment strategies.

Computer software (computer program)

      Software to implement common numerical analysis procedures must be reliable, accurate, and efficient. Moreover, it must be written so as to be easily portable between different computer systems. Since about 1970, a number of government-sponsored research efforts have produced specialized, high-quality numerical analysis software.

      The most popular programming language (computer programming language) for implementing numerical analysis methods is Fortran, a language developed in the 1950s that continues to be updated to meet changing needs. Other languages, such as C, C++, and Java, are also used for numerical analysis. Another approach for basic problems involves creating higher level PSEs, which often contain quite sophisticated numerical analysis, programming, and graphical tools. Best known of these PSEs is MATLAB, a commercial package that is arguably the most popular way to do numerical computing. Two popular computer programs for handling algebraic-analytic mathematics (manipulating and displaying formulas) are Maple and Mathematica.

Historical background

      Numerical algorithms are at least as old as the Egyptian Rhind papyrus (c. 1650 BC), which describes a root-finding method for solving a simple equation. Ancient Greek mathematicians made many further advancements in numerical methods. In particular, Eudoxus of Cnidus (c. 400–350 BC) created and Archimedes (c. 285–212/211 BC) perfected the method of exhaustion (exhaustion, method of) for calculating lengths, areas, and volumes of geometric figures. When used as a method to find approximations, it is in much the spirit of modern numerical integration; and it was an important precursor to the development of calculus by Isaac Newton (Newton, Sir Isaac) (1642–1727) and Gottfried Leibniz (Leibniz, Gottfried Wilhelm) (1646–1716).

      Calculus, in particular, led to accurate mathematical models for physical reality, first in the physical sciences and eventually in the other sciences, engineering, medicine, and business. These mathematical models are usually too complicated to be solved explicitly, and the effort to obtain approximate, but highly useful, solutions gave a major impetus to numerical analysis. Another important aspect of the development of numerical methods was the creation of logarithms (logarithm) about 1614 by the Scottish mathematician John Napier (Napier, John) and others. Logarithms replaced tedious multiplication and division (often involving many digits of accuracy) with simple addition and subtraction after converting the original values to their corresponding logarithms through special tables. (Mechanization of this process spurred the English inventor Charles Babbage (Babbage, Charles) (1791–1871) to build the first computer—see History of computers: The first computer (computer).)

      Newton created a number of numerical methods for solving a variety of problems, and his name is still attached to many generalizations of his original ideas. Of particular note is his work on finding roots (solutions) for general functions (function) and finding a polynomial equation that best fits a set of data (“polynomial interpolation”). Following Newton, many of the mathematical giants of the 18th and 19th centuries made major contributions to numerical analysis. Foremost among these were the Swiss Leonhard Euler (Euler, Leonhard) (1707–1783), the French Joseph-Louis Lagrange (Lagrange, Joseph-Louis, comte de l'Empire) (1736–1813), and the German Carl Friedrich Gauss (Gauss, Carl Friedrich) (1777–1855).

      One of the most important and influential of the early mathematical models in science was that given by Newton to describe the effect of gravity. According to this model, the gravitational force exerted on a body of mass m by the Earth has magnitude F = ^Gmme/_r2, where m_e is the mass of the Earth, r is the distance between the centres of the two bodies, and G is the universal gravitational constant. The force on m is directed toward the centre of gravity of the Earth. Newton's model has led to many problems that require solution by approximate means, usually involving ordinary differential equations (differential equation).

      Following the development by Newton of his basic laws of physics, many mathematicians and physicists applied these laws to obtain mathematical models for solid (solids, mechanics of) and fluid mechanics. Civil and mechanical engineers still base their models on this work, and numerical analysis is one of their basic tools. In the 19th century, phenomena involving heat, electricity, and magnetism were successfully modeled; and in the 20th century, relativistic mechanics, quantum mechanics, and other theoretical constructs were created to extend and improve the applicability of earlier ideas. One of the most widespread numerical analysis techniques for working with such models involves approximating a complex, continuous surface, structure, or process by a finite number of simple elements. Known as the finite element method (FEM), this technique was developed by the American engineer Harold Martin and others to help the Boeing Company analyze stress forces on new jet wing designs in the 1950s. FEM is widely used in stress analysis, heat transfer, fluid flow, and torsion analysis.

Theory of numerical analysis

      The following is a rough categorization of the mathematical theory underlying numerical analysis, keeping in mind that there is often a great deal of overlap between the listed areas.

Numerical linear and nonlinear algebra

      Many problems in applied mathematics involve solving systems of linear equations, with the linear system occurring naturally in some cases and as a part of the solution process in other cases. Linear systems are usually written using matrix-vector notation, Ax = b with A the matrix of coefficients for the system, x the column vector of the unknown variables x₁,…, x_n, and b a given column vector. Solving linear systems with up to 1,000 variables is now considered relatively straightforward in most cases. For small to moderately sized linear systems (say, n ≤ 1,000), the favoured numerical method is Gaussian elimination and its variants; this is simply a precisely stated algorithmic variant of the method of elimination of variables that is introduced in elementary algebra (algebra, elementary). For larger linear systems, there is a variety of approaches depending on the structure of the coefficient matrix A. Direct methods lead to a theoretically exact solution x in a finite number of steps, with Gaussian elimination the best-known example. In practice, there are errors in the computed value of x due to rounding errors in the computation, arising from the finite length of numbers in standard computer arithmetic. Iterative methods are approximate methods that create a sequence of approximating solutions of increasing accuracy.

      Nonlinear problems are often treated numerically by reducing them to a sequence of linear problems. As a simple but important example, consider the problem of solving a nonlinear equation f(x) = 0. Approximate the graph of y = f(x) by the tangent line at a point x⁽⁰⁾ near the desired root (use of parentheses is a common notational convention to distinguish successive iterations from exponentiation), and use the root of the tangent line to approximate the root of the original nonlinear function f(x). This leads to Newton's iterative method for finding successively better approximations to the desired root:

x^(k +1) = x^(k) − ^f(x(k))/_f′(x(k)), k = 0, 1, 2, …,

where f′(x) indicates the first derivative of the original function.

      This generalizes to handling systems of nonlinear equations. Let f(x) = 0 denote a system of n nonlinear equations in n unknowns x = (x₁,…, x_n). Newton's method for solving this system is given by

x^(k + 1) = x^(k) + δ^(k)

f′(x^(k))δ^(k) = −f(x^(k)), k = 0, 1, 2,…

      In this, f′(x) is a generalization of the derivative known as the Jacobian matrix of f(x), and the second equation is a linear system of order n. There are numerous other approaches to solving nonlinear systems, most based on using some type of approximation involving linear functions.

      An important related class of problems occurs under the heading of optimization. Given a real-valued function f(x) with x a vector of unknowns, a value of x that minimizes f(x) is sought. In some cases x is allowed to vary freely, and in other cases there are constraints on x. Such problems occur frequently in business applications.

Approximation theory

      This category includes the approximation of functions with simpler or more tractable functions and methods based on using such approximations. When evaluating a function f(x) with x a real or complex number, it must be kept in mind that a computer or calculator can only do a finite number of operations. Moreover, these operations are the basic arithmetic operations of addition, subtraction, multiplication, and division, together with comparison operations such as determining whether x > y is true or false. With the four basic arithmetic operations, it is possible to evaluate polynomials

p(x) = a₀ + a₁x + a₂x² + ⋯ + a_nxⁿ

as well as rational functions (polynomials divided by polynomials). By including the comparison operations, it is possible to evaluate different polynomials or rational functions on different sets of real numbers x. The evaluation of all other functions—e.g., f(x) = √x or 2^x—must be reduced to the evaluation of a polynomial or rational function that approximates the given function with sufficient accuracy. All function evaluations on calculators and computers are accomplished in this manner.

      One common method of approximation is known as interpolation. Consider a set of points (x_i,y_i) where i = 0, 1, …, n, and then find a polynomial that satisfies p(x_i) = y_i for all i = 0, 1, …, n. The polynomial p(x) is said to interpolate the given data points. Interpolation can be performed with functions other than polynomials (although these are most common), with important cases being rational functions, trigonometric polynomials, and spline functions (made by connecting several polynomial functions at their endpoints—they are commonly used in statistics and computer graphics).

      Interpolation has a number of applications. If a function f(x) is known only at a discrete set of data points x₀, …, x_n, with y_i = f(x_i), then interpolation can be used to extend the definition to nearby points x. If n is at all large, spline functions are generally preferable to simple polynomials.

      Most numerical methods for the approximation of integrals and derivatives of a given function f(x) are based on interpolation. For example, begin by constructing an interpolating function p(x), often a polynomial, that approximates f(x), and then integrate or differentiate p(x) to approximate the corresponding integral or derivative of f(x).

Solving differential (differential equation) and integral equations

      Most mathematical models used in the natural sciences and engineering are based on ordinary differential equations (ordinary differential equation), partial differential equations (partial differential equation), and integral equations (integral equation). Numerical methods for solving these equations are primarily of two types. The first type approximates the unknown function in the equation by a simpler function, often a polynomial or piecewise polynomial (spline) function, chosen to closely follow the original equation. The finite element method discussed above is the best known approach of this type. The second type of numerical method approximates the equation of interest, usually by approximating the derivatives or integrals in the equation. The approximating equation has a solution at a discrete set of points, and this solution approximates that of the original equation. Such numerical procedures are often called finite difference methods. Most initial value problems for ordinary differential equations and partial differential equations are solved in this way. Numerical methods for solving differential and integral equations often involve both approximation theory and the solution of quite large linear and nonlinear systems of equations.

Effects of computer hardware

      Almost all numerical computation is carried out on digital computers. The structure and properties of digital computers affect the structure of numerical algorithms, especially when solving large linear systems. First and foremost, the computer arithmetic must be understood. Historically, computer arithmetic varied greatly between different computer manufacturers, and this was a source of many problems when attempting to write software that could be easily ported between different computers. Variations were reduced significantly in 1985 with the development of the Institute for Electrical and Electronic Engineering (Electrical and Electronics Engineers, Institute of) (IEEE) standard for computer floating-point arithmetic. The IEEE standard has been adopted by all personal computers and workstations as well as most mainframe computers.

      For large-scale problems, especially in numerical linear algebra, it is important to know how the elements of an array A or a vector x are stored in memory. Knowing this can lead to much faster transfer of numbers from the memory into the arithmetic registers of the computer, thus leading to faster programs. A somewhat related topic is that of “pipelining.” This is a widely used technique whereby the executions of computer operations are overlapped, leading to faster execution. Machines with the same basic clock speed can have very different program execution times due to differences in pipelining and differences in the way memory is accessed.

      Most personal computers are sequential in their operation, but parallel computers are being used ever more widely in public and private research institutions. (See supercomputer.) Shared-memory parallel computers have several independent central processing units (central processing unit) (CPUs) that all access the same computer memory, whereas distributed-memory parallel computers have separate memory for each CPU. Another form of parallelism is the use of pipelining of vector arithmetic operations. Numerical algorithms must be modified to run most efficiently on whatever combination of methods a particular computer employs.

Kendall E. Atkinson

Additional Reading

Historical development and mathematical modeling

Historical accounts of numerical analysis, algorithms, and calculus are contained in Herman H. Goldstine, A History of Numerical Analysis from the 16th Through the 19th Century (1977); and Jean-Luc Chabert (ed.), A History of Algorithms: From the Pebble to the Microchip (1999; originally published in French, 1994).Modeling in the natural sciences is discussed in C.C. Lin and L.A. Segel, Mathematics Applied to Deterministic Problems in the Natural Sciences (1974, reprinted with corrections, 1988); and Dimitris Bertsimas and Robert S. Freund, Data, Models, and Decisions: The Fundamentals of Management Science (2000).

Introductions to numerical methods and numerical software

Kendall E. Atkinson, An Introduction to Numerical Analysis, 2nd ed. (1989), is a general introduction to the mathematical foundations of numerical analysis.Lloyd D. Fosdick et al., An Introduction to High-Performance Scientific Computing (1996), is an introduction to scientific computing as a distinct discipline.Numerical linear algebra, including discussions of stability, can be found in Gene H. Golub and Charles F. Van Loan, Matrix Computations, 3rd ed. (1996); and Nicholas J. Higham, Accuracy and Stability of Numerical Algorithms (1996).

Advanced topics and references

Paul Dierckx, Curve and Surface Fitting with Splines (1993), introduces spline functions in the context of computer graphics.Uri M. Ascher and Linda R. Petzold, Computer Methods for Ordinary Differential Equations and Differential-Algebraic Equations (1998), presents methods for solving differential and integral equations.Michael L. Overton, Numerical Computing with IEEE Floating Point Arithmetic (2001), is a comprehensive reference on computer arithmetic.Kendall E. Atkinson

* * *