Polynomial approximation

Frequently you want to approximate functions by polynomials;
by this you generally mean
``picking a euclidean structure on functions and project onto the
space of polynomials (of some degree)''.

Note that in general higher degree approximations will change the
lower degree coefficients; the only time this doesn't happen is if
$\seq{x^k}$ is orthogonal (as in Taylor polynomials).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Recall that you can give a euclidean structure via:
- an inner product
- a norm
- a basis
- a dual basis
...and sometimes one or the other will be more natural,
but it's often very easy to convert between these.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Least-Squares

Given $n$ points $x_1,\dots,x_n$, we define the norm as
$\norm{f}^2=\sum f(x_i)^2$
  (or $\sum \bar f(x_i) f(x_i)$ if you want Hermitian over $\bC$).
Obviously the inner product is
$\left<f,g\right>=\sum \bar f(x_i) g(x_i)$.

The basis that these correspond to is the Lagrange interpolating
polynomials, and the dual basis is $\set{f \mapsto f(x_i)}$.

A rather conceptual way of computing a polynomial fitting
is Neville's algorithm: given n+1 points, it first computes n+1 deg 0
polynomials going through each point, then n deg 1 polys going
through consecutive pairs of points, etc., ending with 1 deg n poly
going through all n points; presumably there's an easy formula for the
next terms.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Taylor approximation

This arises from the dual basis
$f \mapsto f(a),f'(a),\dots$ (i.e., $f \mapsto \seq{f^{(i)}(a)}$
which yields the basis of Taylor polynomials
$(x-a)^k/k!$.

The ``norm'' is
$\norm{f}^2 = \sum f^{(i)}(a)^2$
which has the unfortunate property of being infinite on many
functions; rather, you should consider a sequence of norms
$\norm{f}_n^2 = \sum_{i=0}^n f^{(i)}(a)^2$
which does make sense.
