Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given a polynomial $y=C_0+C_1 x+C_2 x^2+C_3 x^3 + \ldots$ of some order $N$, I can easily calculate the polynomial of reduced order $M$ by taking only the first $M+1$ terms. This is equivalent to doing a Taylor series expansion with $M<=N$ around $x=0$.

But what if I want to take the Taylor series expansion around a different point $x_c$. In the end, I want the polynomial coefficients of $y_2=K_0+K_1 x + K_2 x^2 + K_3 x^3 + \ldots$ which represents the Taylor's expansion of $y$ around point $x_c$ such that $y(x_c)=y_2(x_c)$ including the first $M$ derivatives.

So given the coefficients $C_i$ with $i=0 \ldots N$, and a location $x_c$ I want to calculate the coefficients $K_j$ with $j=0 \ldots M$.

Example

Given $y=C_0+C_1 x+C_2 x^2$ ( $N=2$ ) then the tangent line ($M=1$) through $x_c$ is

$$ y_2 = (C_0-C_2 x_c^2) + (C_1+2 C_2 x_c) x $$

or $K_0 = C_0-C_2 x_c^2$, and $K_1 =C_1+2 C_2 x_c$

There must be a way to construct a ($M+1$ by $N+1$ ) matrix that transforms the coefficients $C_i$ into $K_j$. For the above example this matrix is

$$ \begin{bmatrix}K_{0}\\ K_{1}\end{bmatrix}=\begin{bmatrix}1 & 0 & -x_{c}^{2}\\ 0 & 1 & 2\, x_{c}\end{bmatrix}\begin{bmatrix}C_{0}\\ C_{1}\\ C_{2}\end{bmatrix} $$

Example #2

The reduction of a $5$-th order polynomial to a $3$-rd order around $x_c$ is

$$ \begin{bmatrix}K_{0}\\ K_{1}\\ K_{2}\\ K_{3}\end{bmatrix}=\left[\begin{array}{cccc|cc} 1 & & & & -x_{c}^{4} & -4\, x_{c}^{5}\\ & 1 & & & 4\, x_{c}^{3} & 15\, x_{c}^{4}\\ & & 1 & & -6\, x_{c}^{2} & -20\, x_{c}^{3}\\ & & & 1 & 4\, x_{c} & 10\, x_{c}^{2}\end{array}\right]\begin{bmatrix}C_{0}\\ C_{1}\\ C_{2}\\ C_{3}\\ C_{4}\\ C_{5}\end{bmatrix} $$

which is a block matrix, and not an upper diagonal one as some of the answers have indicated.

share|improve this question
    
I rewrote the answer. I did not realize at first you were trying to go back to powers of $x$. –  Arturo Magidin Feb 17 '11 at 1:06

2 Answers 2

up vote 12 down vote accepted

Note: Rewritten essentially from the ground up.

Sorry for the somewhat obfuscated previous version. I did not realize at first that you were trying to write the end result as a polynomial in $x$ instead of $(x-x_c)$, and then I was trying to bootstrap that into what I had already written.

I'm going to use $a$ instead of $x_c$, because it is a little simpler to type and harder to confuse with $x$, if you don't mind.

The simplest way to think about what you are doing is that it is the composition of three linear transformations.

  1. First you take a polynomial written in terms of the basis $\beta=[1,x,x^2,\ldots,x^N]$ of the space of polynomials degree at most $N$, and you rewrite it in terms of the basis $\gamma=[1,(x-a),(x-a)^2,\ldots,(x-a)^N]$. That is, a change of coordinates.

  2. Then you take the polynomial written in terms of $\gamma$, and you project down to the subspace generated by $[1,(x-a),\ldots,(x-a)^M]$. That is, you erase the terms of degree $M+1,\ldots,N$. Call this $P^N_M$.

  3. Finally, you take the resulting polynomial, which is written in terms of the basis $\gamma$, and you translated it back into the basis $\beta$; another change of coordinates.

Being a composition of three linear transformations, it can be represented by a matrix which is the product of three matrices, the matrices that represent the three operations.

The matrix for $P^N_M$ is the simplest one: it is a block-diagonal matrix that has the $(M+1)\times (M+1)$ identity in the first block, and the $(N-M)\times(N-M)$ zero matrix as the second block.

The matrix for step 3 is just the inverse of the matrix for step 1. To each real number $r$, we have a matrix whose columns represent the binomial expansion of $(x+r)$: $$B_r = \left(\begin{array}{cccccc} 1 & r & r^2 & r^3 & \cdots & r^N\\\ 0 & 1 & 2r & 3r^2 & \cdots & \binom{N}{1}r^{N-1}\\\ 0 & 0 & 1 & 3r & \cdots & \binom{N}{2}r^{N-2}\\\ 0 & 0 & 0 & 1 & \cdots & \binom{N}{3}r^{N-3}\\\ \vdots & \vdots & \vdots & \ddots & \vdots\\\ 0 & 0 & 0 & 0 & \cdots & \binom{N}{N-1}r\\\ 0 & 0 & 0 & 0 & \cdots & 1 \end{array}\right).$$ When you go from having the basis given by powers of $x$ to the basis given by powers of $x-a$, you do this by multiplying by $B_a$. In order to go from the basis given by the powers of $(x-a)$ to the powers of $x$, the change of variable $u=x-a$ shows that you are going form powers of $u$ to powers of $u+a = u-(-a)$, so you achieve this by multiplying by $B_{(-a)}$. Thus, your operation is given by the matrix $$B_{(-a)}P^N_MB_a.$$ Now, this is a product of three $(N+1)\times (N+1)$ matrices, so you may wonder why I have an $(N+1)\times (N+1)$ matrix and you have an $(M+1)\times (N+1)$ matrix. The reason is that because the last $N-M$ rows of $P_M$ are all zero and all matrices are upper triangular, the last $N-M$ rows of this product will likewise be zero; you are just omitting them.

So, if you have the polynomial $C_0 + C_1x + \cdots +C_Nx^N$, then your end result is the polynomial $K_0 + K_1x+\cdots +K_Nx^N$, where $$\left(\begin{array}{c} K_0\\ K_1\\ \vdots\\ K_N\end{array}\right) = B_{(-a)}P_MB_a\left(\begin{array}{c} C_0\\ C_1\\ \vdots\\ C_N\end{array}\right).$$

For your second example, you have $N=5$ and $M=3$. For $N=5$, you have \begin{align*} B_{a} &= \left(\begin{array}{cccccc} 1 & a & a^2 & a^3 & a^4 & a^5\\ 0 & 1 & 2a & 3a^2 & 4a^3 & 5a^4\\ 0 & 0 & 1 & 3a & 6a^2 & 10a^3\\ 0 & 0 & 0 & 1 & 4a & 10a^2\\ 0 & 0 & 0 & 0 & 1 & 5a\\ 0 & 0 & 0 & 0 & 0 & 1 \end{array}\right)\\ P^5_3 &= \left(\begin{array}{cccccc} 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 \end{array}\right)\\ B_{-a} &=\left(\begin{array}{rrrrrr} 1 & -a & a^2 & -a^3 & a^4 & -a^5\\ 0 & 1 & -2a & 3a^2 & -4a^3 & 5a^4\\ 0 & 0 & 1 & -3a & 6a^2 & -10a^3\\ 0 & 0 & 0 & 1 & -4a & 10a^2\\ 0 & 0 & 0 & 0 & 1 & -5a\\ 0 & 0 & 0 & 0 & 0 & 1 \end{array}\right). \end{align*} If you multiply out $B_{-a}P^5_3B_a$ you get \begin{align*} B_{-a}P^5_3B_a &= \left(\begin{array}{rrrrrr} 1 & -a & a^2 & -a^3 & a^4 & -a^5\\ 0 & 1 & -2a & 3a^2 & -4a^3 & 5a^4\\ 0 & 0 & 1 & -3a & 6a^2 & -10a^3\\ 0 & 0 & 0 & 1 & -4a & 10a^2\\ 0 & 0 & 0 & 0 & 1 & -5a\\ 0 & 0 & 0 & 0 & 0 & 1 \end{array}\right)\left(\begin{array}{cccccc} 1 & a & a^2 & a^3 & a^4 & a^5\\ 0 & 1 & 2a & 3a^2 & 4a^3 & 5a^4\\ 0 & 0 & 1 & 3a & 6a^2 & 10a^3\\ 0 & 0 & 0 & 1 & 4a & 10a^2\\ 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 \end{array}\right)\\ &= \left(\begin{array}{rrrrrr} 1 & 0 & 0 & 0 & -a^4 & -4a^5\\ 0 & 1 & 0 & 0 & 4a^3 & 15a^4\\ 0 & 0 & 1 & 0 & -6a^2 & -20a^3\\ 0 & 0 & 0 & 1 & 4a & 10a^2\\ 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 \end{array}\right) \end{align*} exactly what you have except for the two extra rows of zeros at the bottom.

Added. If you think about it, you'll see that this process will always produce a block-upper triangular matrix, with an $(M+1)\times(M+1)$ identity in the upper left and an $(N-M)\times(N-M)$ zero matrix in the bottom right; because $B_{-a}B_a = I$, the bottom rows you zero out in $B_a$ do not affect the products in the first $M+1$ columns, and they are all that matters in the last $N-M$ rows. So the only parts that need computation is the block on the upper right. This shows how it relates to your non-square matrices.

Added 2. I should have added this as soon as you said you were programming it...

There is an alternative way of computing this matrix, which may be faster when $M$ is larger than half of $N$. The idea is just to note that the matrix $P^N_M$ can be written as a difference of the identity matrix with the matrix that has the $(N-M)\times(N-M)$ identity on the bottom right and zeros elsewhere; call it $Q^N_M$; that is, $$P^N_M = I_{N+1} - Q^N_M = \left(\begin{array}{ccccc} 1 & 0 & \cdots & 0 & 0\\\ 0 & 1 & \cdots & 0 & 0\\\ \vdots & \vdots & \ddots & \vdots & \vdots \\\ 0 & 0 & \cdots & 1 & 0\\\ 0 & 0 & \cdots & 0 & 1 \end{array}\right) - \left(\begin{array}{cccccc} 0 & 0 & \cdots & 0 & 0\\\ 0 & 0 & \cdots & 0 & 0\\\ \vdots & \vdots & \ddots & \vdots & \vdots\\\ 0 & 0 & \cdots & 1 & 0\\\ 0 & 0 & \cdots & 0 & 1 \end{array}\right).$$ Then you have that $$B_{-a}P^{N}_MB_a = B_{-a}(I-Q^N_M)B_a = (B_{-a}IB_a) - B_{-a}Q^N_MB_a = I-B_{-a}Q^{N}_MB_a.$$ If $M$ is more than half of $N$, then there will be fewer operations to perform in $B_{-a}Q^N_MB_a$ than in $B_{-a}P^N_MB_a$, because $Q^N_MB_a$ has only $N-M$ nonzero rows, whereas $P^N_MB_a$ has $M+1$ nonzero rows. So you can pick which of the two computations to do: either $B_{-a}P^N_MB_a$, or $I-B_{-a}Q^N_MB_a$, and for $N$ and $M$ large, with $M$ close to $N$, using $Q^N_M$ will probably be faster than using $P^N_M$.

share|improve this answer
    
Arturo - in the examples I have done (with symbolic algebra) the resulting matrix is not diagonal, rather a block matrix with the first $M+1$ columns the identity matrix, and the rest $N-M$ columns of the form $r_{i,j}x_c^{j-i}$ where $i=0 \ldots M$ is the row and $j=0 \ldots N$ the column. –  ja72 Feb 16 '11 at 18:56
    
@ja72: You are trying to write the Taylor polynomial around $x_c$ as a polynomial in $x$, whereas I'm writing it as a polynomial in $x-x_c$, which is the usual way of doing it. –  Arturo Magidin Feb 16 '11 at 19:43
    
I think you can construct $B_{-a}$ from $B_{a}$ easily, by just changing the signs of the off diagonal terms appropriately. Is this correct? If yes, I am ready to code this into a subroutine for polynomials I have. –  ja72 Feb 18 '11 at 0:36
    
@ja72: Since the only difference is that you need to replace every ocurrence of $a$ by $-a$, all you need to do is switch the signs of every entry in which $a$ is raised to an odd power. Because the powers of $a$ are constant along off-diagonals, your thinking is correct. The off-diagonal directly above the diagonal has them all negative, the next one the same, the one after all negative, the next one (which corresponds to $a^4$) the same, etc. –  Arturo Magidin Feb 18 '11 at 1:07
    
@ja72: Please see the second addition; if you are coding a subroutine, then considering separately the case where $M\leq\frac{1}{2}N$ and $M\gt\frac{1}{2}N$ may save you resources by using the alternative computation when $M$ is large. –  Arturo Magidin Feb 19 '11 at 20:41

Here is a Mathematica routine that is (more or less) an efficient way of performing Arturo's proposal (I assume the array of coefficients cofs is arranged with constant term first, i.e. $p(x)=\sum\limits_{k=0}^n$cofs[[k + 1]]):

polxpd[cofs_?VectorQ, h_, d_] := Module[{n = Length[cofs] - 1, df},
    df = PadRight[{Last[cofs]}, d + 1];
    Do[
      Do[
        df[[j]] = df[[j - 1]] + h df[[j]];
        , {j, Min[d, n - k + 1] + 1, 2, -1}];
      df[[1]] = cofs[[k]] + h df[[1]];
      , {k, n, 1, -1}];
    Do[
      Do[
        df[[k]] -= h df[[k + 1]];
        , {k, d, j, -1}];
      , {j, d}];
    df]

Let's try it out:

polxpd[{c[0], c[1], c[2]}, h, 1] // FullSimplify
{c[0] - h^2*c[2], c[1] + 2*h*c[2]}

polxpd[c /@ Range[0, 5], h, 3] // FullSimplify
{c[0] - h^4*(c[4] + 4*h*c[5]), c[1] + h^3*(4*c[4] + 15*h*c[5]), 
 c[2] - 2*h^2*(3*c[4] + 10*h*c[5]), c[3] + 2*h*(2*c[4] + 5*h*c[5])}

Now, Arturo gave the linear-algebraic interpretation of this conversion; I'll look at this from the algorithmic point of view:

For instance, see this (modified) snippet:

n = Length[cofs] - 1;
df = {Last[cofs]};
Do[
  df[[1]] = cofs[[k]] + x df[[1]]
  , {k, n, 1, -1}];

This is nothing more than the Horner scheme (alias "synthetic division") for evaluating the polynomial at x. What is not so well known is that the Horner scheme can be hijacked so that it computes derivatives as well as polynomial values. We can "differentiate" the previous code snippet like so (i.e., automatic differentation):

n = Length[cofs] - 1;
df = {Last[cofs], 0};
Do[
  df[[2]] = df[[1]] + x df[[2]]
  df[[1]] = cofs[[k]] + x df[[1]];
  , {k, n, 1, -1}];

where the rule is $\frac{\mathrm d}{\mathrm dx}$`df[[j]]`$=$df[[j+1]]. "Differentiating" the line df = {Last[cofs]} (the leading coefficient of the polynomial) requires appending a 0 (the derivative of a constant is $0$); "differentiating" the evaluation line df[[1]] = cofs[[k]] + x df[[1]] gives df[[2]] = df[[1]] + x df[[2]] (use the product rule, and the fact that $\frac{\mathrm d}{\mathrm dx}$`cofs[[k]]`$=0$). Continuing inductively (and replacing the x with h), we obtain the first double loop of polxpd[].

Actually, the contents of df after the first double loop are the "scaled derivatives"; that is, df[[1]]$=p(h)$, df[[2]]$=p^\prime(h)$, df[[3]]$=\frac{p^{\prime\prime}(h)}{2!}$, ... and so on.

What the second double loop accomplishes is the "shifting" of the polynomial by -h; this is in fact synthetic division applied repeatedly to the coefficients output by the first double loop, as mentioned here.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.