Foundations: Algorithms, Approximation & Error

approximation

An approximation is a value or function that stands in for the true one when the true one cannot be computed exactly, written down in closed form, or stored in finite memory — but where 'close enough' is genuinely good enough. Saying pi is about 3.14159, or that the area under a curve is the sum of a few trapezoids, are approximations: not the real thing, but near it, and near it by an amount you can control.

What turns a guess into a respectable approximation is a notion of error. An approximation x~ of a true value x has absolute error |x~ - x| and relative error |x~ - x| / |x|, and a good numerical method comes with a way to make these small (take more terms, use a smaller step h, do another iteration) and ideally a bound telling you how small. Often the error shrinks at a known rate, written O(h^p): halving h cuts the error by 2^p. So approximation is not sloppiness — it is the deliberate, quantified trade of exactness for computability.

Approximation is unavoidable, not a last resort: almost no real-world or even mid-sized mathematical problem has a usable exact answer. The discipline is to know which kind of error you are committing (truncation from cutting off a limit, round-off from finite arithmetic, data error from imperfect inputs) and to keep the total understood. The slogan of the whole field is that there is no exact answer — only a controlled, defensible approximation.

Replacing e^x by its Taylor polynomial 1 + x + x^2/2 + x^3/6 approximates e^(0.1) as 1.105166...; the true value is 1.105170..., so the absolute error is about 4e-6 — small, and predictably smaller if we add another term.

A finite, computable stand-in for an infinite process, with an error you can shrink on demand.

Smaller is not always achievable for free. Shrinking truncation error by taking h tiny eventually lets round-off error grow — there is often an optimal step, not an arbitrarily small one.

Also called
approximate solutionestimate近似值近似解