Tricki
a repository of mathematical know-how

Use an approximation as if it were exact

Quick description

Often we want to apply a method to a general class of functions, but we only know how to do this for a certain class of functions (e.g., polynomials). Then use an approximation to our general function from our certain class, and act as if our approximation were exact.

A more sophisticated version, is to use this to update a guess by means of this approach, obtaining successively (we hope) approximations to the unknown we wish to compute.

Prerequisites

Linear algebra, calculus.

Example 1

Numerical integration is mostly done this way.

We take a polynomial interpolant p of a given function [a,b]\to\R at certain chosen points x_1<x_2<\cdots<x_N and then use \int_a^b p(x)\,dx as the approximation to \int_a^b f(x)\,dx.

The error in the result is usually best estimated by the error in the interpolant, or by noting that the method is exact for all polynomials of up to a certain degree (at least N-1), and then using the error in the interpolant to estimate the error in the integral. (See also Interpolation and approximation.)

Example 2

Solving linear or nonlinear equations iteratively.

For a linear system of equations, Ax=b where we wish to find x, if we have an approximate matrix B\approx A for which we can readily solve systems Bz=d, we can compute x iteratively via:

\begin{align} B\delta_i&=b-Ax_i\\                      x_{i+1}  &=x_i + \delta_i. \end{align}

This is known as iterative refinement.

For nonlinear systems we use the Taylor series approximation to 1st order: f(x+\delta)=f(x)+\nabla f(x)\delta, and then set the linearization to zero. If we update the value of x to be x\gets x+\delta, this gives the Newton–Raphson method.