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.

General discussion

Login or register to post comments
3362 reads