numerical analysis - General introduction, Areas of study, Software

Methods of calculation involving successive approximations, such as iterative methods. For example, to find ?10 to any required degree of accuracy, if x_n is a good approximation to ?10, use the algorithm (below) to find x_n + 1, a better approximation. Great developments have been made recently in this field, encouraged by the suitability of computers for numerical methods.

Numerical analysis is the study of approximate methods for the problems of continuous mathematics (as distinguished from discrete mathematics).

For thousands of years, man has used mathematics for construction, warfare, engineering, accounting and many other puposes.

Numerical analysis continues this long tradition of practical mathematical calculations.

Numerical analysis naturally finds applications in all fields of engineering and the physical sciences, but in the 21st century, the life sciences and even the arts have adopted elements of scientific computations.

Before the advent of modern computers numerical methods often depended on hand interpolation in large printed tables.

General introduction

We will now outline several important themes of numerical analysis.

Direct and iterative methods

Direct vs iterative methods

Consider the problem of solving 3x3 + 4 = 28 for the unknown quantity x.
Subtract 4	3x3 = 24.
Divide by 3	x3 = 8.
Take cube roots	x = 2.

For the iterative method, apply the bisection method to f(x) = 3x3 + 24. The initial values are a = 0,b = 3,f(a) = 4,f(b) = 85.

Iterative Method

a	b	mid	f(mid)
0	3	1.5	14.125
1.5	3	2.25	38.17...
1.5	2.25	1.875	23.77...
1.875	2.25	2.0625	30.32...

We conclude from this table that the solution is between 1.875 and 2.0625.

Some problems can be solved exactly by an algorithm.

However, no direct methods exist for most problems.

Discretization

A discretization example

A race car drives along a track for two hours. If we know that the race car was going at 150Km/h after one hour, we might guess that the total distance travelled is 300Km. Essentially, we have taken the continuously varying speed v(t) and approximated it using a speed which is constant on each of the three intervals of 40 minutes.

Furthermore, continuous problems must sometimes be replaced by a discrete problem whose solution is known to approximate that of the continuous problem;

The generation and propagation of errors

The study of errors forms an important part of numerical analysis.

Round-off

Round-off errors arise because it is impossible to represent all real numbers exactly on a finite-state machine (which is what all practical digital computers are).

On a pocket calculator, if one enters 0.0000000000001 (or the maximum number of zeros possible), then a +, and then 100000000000000 (again, the maximum number of zeros possible), one will obtain the number 100000000000000 again, and not 100000000000000.0000000000001.

Truncation and discretization error

Truncation errors are committed when an iterative method is terminated and the approximate solution differs from the exact solution.

Once an error is generated, it will generally propagate through the calculation.

Numerical stability and well posedness

Numerical stability and well posedness

Ill posed problem: Take the function f(x) = 1 / (x − 1). Well-posed problem: By contrast, the function is continuous so the problem of computing is well-posed. Numerically unstable method: Still, some algorithms which are meant to compute are fallible. Consider the following iteration Start with x1 an approximation of (for instance, take x1 = 1.4) and then use the iteration Then the iterates are x1 = 1.4 x2 = 1.4016 x3 = 1.4028614885... On the other hand, if we start from x1 = 1.42, we obtain the iterates x2 = 1.42026896 x3 = 1.42056... Numerically stable method: The Newton method for is x1 = 1 and and is extremely stable. The first few iterations for a = 2 are x1 = 1 x2 = 1.5 x3 = 1.416... x6 = 1.41421356237309..., which is essentially exact to the last displayed digit.

This leads to the notion of numerical stability: an algorithm is numerically stable if an error, once it is generated, does not grow too much during the calculation.

However, an algorithm that solves a well-conditioned problem may or may not be numerically stable.

Areas of study

The field of numerical analysis is divided in different disciplines according to the problem that is to be solved.

Computing values of functions

One of the simplest problems is the evaluation of a function at a given point.

Interpolation, extrapolation and regression

Examples of Interpolation, extrapolation and regression

Interpolation: If the temperature at noon was 20 degrees centigrade and at 2pm we observe that the temperature is 14 degrees centigrade, we might guess that at 1pm the temparature was in fact the average of 14 and 20, which is 17 degrees centigrade. Extrapolation: If the gross domestic product of a country has been growing an average of 5% per year and was 100 billion dollars last year, we might extrapolate that it will be 105 billion dollars this year. Regression: Given two points on a piece of paper, there is a line that goes through both points.

Interpolation solves the following problem: given the value of some unknown function at a number of points, what value does that function have at some other point between the given points?

Extrapolation is very similar to interpolation, except that now we want to find the value of the unknown function at a point which is outside the given points.

Regression is also similar, but it takes into account that the data is imprecise.

Solving equations and systems of equations

Another fundamental problem is computing the solution of some given equation.

Much effort has been put in the development of methods for solving systems of linear equations. Iterative methods such as the Jacobi method, Gauss-Seidel method, successive over-relaxation and conjugate gradient method are usually preferred for large systems.

Root-finding algorithms are used to solve nonlinear equations (they are so named since a root of a function is an argument for which the function yields zero).

Solving eigenvalue or singular value problems

Several important problems can be phrased in terms of eigenvalue decompositions or singular value decompositions.

Optimization

Optimization, differential equations

Optimization: Say you sell lemonade at a lemonade stand, and notice that at 1$, you can sell 197 glasses of lemonade per day, and that for each increase of 0.01$, you will sell one less lemonade per day. Differential equation: If you set up 100 fans to blow air from one end of the room to the other and then you drop a feather into the wind, what happens?

Optimization problems ask for the point at which a given function is maximized (or minimized).

The field of optimization is further split in several subfields, depending on the form of the objective function and the constraint.

The method of Lagrange multipliers can be used to reduce optimization problems with constraints to unconstrained optimization problems.

Evaluating integrals

Numerical integration

How much paint would you need to give the Statue of Liberty a fresh coat? However, it may be more precise to estimate each piece on its own. To further improve our estimate, we would measure the folds in her cloth, how non-spherical her head really is and so on.

Numerical integration, in some instances also known as numerical quadrature, asks for the value of a definite integral. In higher dimensions, where these methods become prohibitively expensive in terms of computational effort, one may use Monte Carlo or quasi-Monte Carlo methods, or, in modestly large dimensions, the method of sparse grids.

Differential equations

Numerical analysis is also concerned with computing (in an approximate way) the solution of differential equations, both ordinary differential equations and partial differential equations.

Partial differential equations are solved by first discretizing the equation, bringing it into a finite-dimensional subspace. This can be done by a finite element method, a finite difference method, or (particularly in engineering) a finite volume method.

Software

Since the late twentieth century, most algorithms are implemented and run on a computer.

MATLAB is a popular commercial programming language for numerical scientific calculations, but there are commercial alternatives such as S-PLUS and IDL, as well as free and open source alternatives such as FreeMat, GNU Octave (similar to Matlab), R (similar to S-PLUS) and certain variants of Python.

Many computer algebra systems such as Mathematica or Maple (free software systems include SAGE, Maxima, Axiom, calc and Yacas), can also be used for numerical computations.