Approximation Techniques

Many mathematical problems resist exact solution. Examples include the isomorphism problem and various dynamical systems. In order to increase the value of mathematics as an applied discipline, mathematicians have developed various methods for generating approximate solutions to intractable problems. The utility of such methods comes from the fact that it is often possible to specify a bound on the error associated with the approximation; provided the error is small enough, the approximation will not be significantly worse than an exact solution.

A survey of some approximation techniques follows.

Heuristic algorithms: in computer science and operations research, there exist many problems which are considered "intractable", i.e. no known "quick" (polynomial-time) algorithm is known for their solution. Heuristic algorithms quickly come up with approximate solutions to intractable problems.

Asymptotic methods: These consider the behaviour of a system over some restricted range of its variables. For instance, when solving a dynamical system, the researcher is often only interested in the solution of small time-scales, or over long time-scales. Given a stated assumption about the "asymptotic regime" (eg long-time) that one is interested in, it is often possible to come up with a function to which the exact solution will asymptote (eg, in the limit as t goes to infinity,) with decreasing error. Often, the approximation yielded by an asymptotic solution will in fact be valid outside of the assumed asymptotic regime. For instance, a long-time solution may be valid over "intermediate" time-scales as well. (Eg, for any t greater than 1.)

Numerical analysis: If it is possible to "discretise" a (continuous) dynamical system, i.e. come up with a discrete system which matches the continuous one over the domain of interest, then it is often possible to use matrix methods to generate an approximate solution to the original system. This algebraic system will often be quite large, but modern computers are not too worried by the size of most matrices.

This article is a stub. Help us out by expanding it.