Pages

▼

Thursday, April 24, 2008

The differentiation matrix for arithmetic polynomials

Calculating a difference function is a straightforward process:

\\<br />f(n)=n^3-n^2+n+2\\<br />\\<br />\begin{matrix}<br />n & f(n) & \Delta f(n) \\ <br />0 & 2 & 1\\ <br />1 & 3 & 5\\ <br />2 & 8 & 15\\ <br />3 & 23 & 31\\ <br />4 & 54 & 33\\ <br />5 & 107 & \\ <br /> & & <br />\end{matrix}<br />\\<br />\Delta f(n)=\frac{f(n+1)-f(n)}{1}=\\<br />\\<br />((n+1)^3-(n+1)^2+(n+1)+2)-(n^3-n^2+n+2)=\\<br />\\<br />3n^2+n+1\\



But it is simpler to use the differentiation matrix for arithmetic polynomials:

f(n)=2+n-n^2+n^3 \rightarrow \begin{pmatrix}<br />2 \\ <br />1 \\ <br />-1\\ <br />1\\ <br />0<br />\end{pmatrix}\\<br />\\<br />\\<br />\begin{pmatrix}<br />0 & 1 & 1 & 1 & 1\\ <br />0 & 0 & 2 & 3 & 4\\ <br />0 & 0 & 0 & 3 & 6\\ <br />0 & 0 & 0 & 0 & 4\\ <br />0 & 0 & 0 & 0 & 0<br />\end{pmatrix}<br />\begin{pmatrix}<br />2 \\ <br />1 \\ <br />-1\\ <br />1\\ <br />0<br />\end{pmatrix} =<br />\begin{pmatrix}<br />1 \\ <br />1 \\ <br />3\\ <br />0\\ <br />0<br />\end{pmatrix}\\<br />\\<br />\\<br />\begin{pmatrix}<br />1 \\ <br />1 \\ <br />3\\ <br />0\\ <br />0<br />\end{pmatrix}\rightarrow f(n)=1+n+3n^2

The 5x5 matrix above is suitable for polynomials up to degree 4. It is possible to create a (n+1)x(n+1) matrix capable of handling polynomials up to degree n.

Proof:
Exercise (hint: use falling powers).

Question: Is there a compact way ( recursive, perhaps ) of describing the matrix capable of handling polynomials up to degree n?
at

1 comment:

  1. nooneTuesday, July 8, 2008 at 3:24:00 AM GMT+2

    Absolutely. First, notice that the space of polynomials (infinite dimensional, of course), call it V, forms a vector space over your base field, say the field K. Let V(n) be the subspace of V consisting of polynomials of degree <= n. Define differentiation on V(n) in the usual sense. Then differentiation becomes a linear operator on V(n), call it D. Now, V(n) is finite dimensional (of dimension n + 1), so the matrix representation of D is (n + 1)x(n + 1), and will handle any polynomial in V(n).

    Cheers!

    William

    ReplyDelete