The algebra of truncated polynomials

Here we introduce, formally, a basic algebraic structure over the set of truncated polynomials and we show how such a structure allows to compute the partial derivatives of multivariate functions up to arbitrary order.

Formal definition

Consider the set \(\mathcal P_{n,m}\) of all polynomials of order \(\le m\) in \(n\) variables and having coefficients in \(\mathbf K\). We indicate with the symbols \(T_f, T_g, T_h\), etc. the generic members of such a set. Such a set is an algebra over the field \(\mathbf K\) if we introduce the truncated multiplication as the standard polynomial multiplication truncated at order \(m\). When needed, we will indicate such a multiplication with the symbol \(T_f \cdot T_g\).

This algebra is commonly referred to as the algebra of truncated polynomials. A first important property of this algebra is that, under the multiplication, all polynomials having a zero constant coefficient are nil-potent of order \(m+1\), as easily verified. We will indicate the generic truncated polynomial \(\in \mathcal P_{n,m}\) as \(T_f\) and often we will consider its constant part separated from the rest, writing \(T_f = f_0 + \hat f\). It is worth noting at this point how such an algebra is unitary and associative. The first property, in particular, deserves a few more words as it is a property that the algebra of (non-truncated) polynomials does not possess. Formally \(\forall T_f \in \mathcal P_{n,m}, \: \exists !\: T_g\in \mathcal P_{n,m} \Rightarrow T_g\cdot T_f = 1\). In practice:

(1)\[T_g = \frac 1{T_f} = \frac 1{f_0} \left(1 +\sum_{k=1}^m (-1)^k (\hat f / f_0)^k\right)\]

as its easily verified by performing the truncated multiplication \(T_g \cdot T_f\) and accounting for the nilpotency of \(\hat f\).

Multiplication

We here prove that the product of two truncated Taylor expansions is the truncated Taylor expansion of the product. We perform the proof for \(n=1\) as the notation is there clearer. The multivariate case is formally identical, requiring a more complex notation. The truncated Taylor expansion of the product between two functions \(f\) and \(g\) is:

\[T_{(fg)} = \sum_{k=0}^m \frac{(x-a)^k}{k!}(fg)^{(k)}\]

where we indicate with the superscript \((i)\) the \(i\)-th derivative with respect to the independent variable. We show how the same expression is derived by multiplying the Taylor expansions of \(f\) and \(g\):

\[T_f T_g = \sum_{k=0}^m \frac{(x-a)^k}{k!}(f)^{(k)}\sum_{k=0}^m \frac{(x-a)^k}{k!}(g)^{(k)} = \sum_{k=0}^m c_k (x-a)^k\]

The coefficients \(c_k\) in the last power series are determined as the Cauchy product of the two Taylor series (or discrete convolution) and are:

\[c_k = \sum_{n=0}^k \frac{f^{(n)}}{n!} \frac{g^{(k-n)}}{(k-n)!} = \frac{1}{k!}\sum_{n=0}^k {{k}\choose{n}}(f)^{(n)}(g)^{(k-n)}\]

applying now the general Leibniz rule to the last expression we get:

\[c_k = \frac{1}{k!} (fg)^{(k)}\]

which allows us to conclude:

\[T_{(fg)} = T_f \cdot T_g.\]

Reciprocal

We here prove that the reciprocal of a truncated Taylor expansion, as defined in the algebra \(\mathcal P_{n,m}\) is the Taylor expansion of the reciprocal. Consider the generic function \(f\) and its truncated Taylor expansion \(T_f\). We denote with \(T_{(1/f)}\) the truncated Taylor expansion of the reciprocal and apply the multiplication rule to derive that, necessarily, \(T_f T_{(1/f)} = 1\). We separate the constant part of \(T_f\) from the rest writing \(T_f = f_0 +\hat f\) and we compute the product between \(T_f\) and the definition of reciprocal:

\[\left(f_0 + \hat f\right)\frac 1f_0 \left(1 +\sum_{j=1}^m (-1)^j (\hat f / f_0)^j\right)= \frac 1f_0 \left(f_0 + \hat f\right)\left(1 - \frac{\hat f}{f_0} + \frac{\hat f^2}{f_0^2} - ... \right) = 1\]

which allows us to conclude:

\[T_{(1/f)} = \frac 1f_0 \left(1 +\sum_{j=1}^m (-1)^j (\hat f / f_0)^j\right)\]

Elementary functions

Consider the MacLaurin expansion of a generic function \(g(x) = \sum g_n x^n\). Consider now a multivariate function \(\hat f(\mathbf x) = \sum_{|\alpha|=1} f_\alpha \mathbf x^\alpha\) whose MacLaurin Taylor expansion does not have a constant term. The composition between these two functions will then be, trivially, \((g \circ \hat f) (x) = \sum g_n (\sum_{|\alpha|=1} f_\alpha \mathbf x^\alpha)^n\). If we now truncate such an expansion to order \(m\), we get \(T_{g\circ f}= \sum_{n=0}^m g_n (\sum_{|\alpha|=1}^m f_\alpha \mathbf x^\alpha)^n\), which can be written as:

\[T_{g\circ \hat f} = T_g\circ T_{\hat f}\]

The above equation is called the composition rule and is only valid for functions whose Taylor expansion does not have a constant term and, is thus nil-potent of order \(m+1\) in \(\mathcal P_{n,m}\). In general, we cannot compute the truncated Taylor expansion of a composition function directly composing the truncated Taylor expansions. For most elementary functions, though, we can consider \(T_f = f_0 + \hat f\) and use some addition formula to be able to ‘’extract`` \(\hat f\) and thus exploit its nil-potency. The details on how this is done differ for each particular \(f\) considered and are reported in the following subsections for some commonly used functions.

Other functions suc as tan, cosh etc. can also be treated similarly and are not reported for convenience.

Exponential

Let us consider the case of the exponential:

\[g(x) = \exp(x) = \sum_{i=0} \frac{x^i}{i!} = 1 + x + \frac {x^2}{2} + ...\]

We want to compute the truncated Taylor expansion of \(\exp(f(\mathbf x))\) starting from the truncated Taylor expansion \(T_f = f_0 + \hat f\). We thus write:

\[(g \circ f) (\mathbf x) = \exp(f(\mathbf x)) = \exp f_0 \exp (f(\mathbf x) - f_0)\]

note that, now, we can apply the composition rule to \(\exp (f(\mathbf x) - f_0)\) since the MacLaurin Taylor expansion of \(f(\mathbf x) - f_0\) does not have a constant term. Hence:

\[T_{g \circ f} = \exp f_0 T_g \circ T_{\hat f}\]

and, finally:

(2)\[T_{(\exp f)} = \exp f_0 \sum_{i=0}^m \frac{\hat f^i}{i!} = \exp f_0 \left( 1 + \hat f + \frac {\hat f^2}{2!} + ... \right)\]

Logarithm

Let us consider the case of the natural logarithm:

\[g(x) = \log(x)\]

We want to compute the truncated Taylor expansion of \(\log(f(\mathbf x))\) starting from the truncated Taylor expansion \(T_f = f_0 + \hat f\). We thus write:

\[(g \circ f) (\mathbf x) = \log(f(\mathbf x)) = \log (f_0 + (f(\mathbf x) - f_0)) = \log f_0 + \log(1 + \frac{f(\mathbf x) - f_0}{f_0})\]

We can now apply the composition rule to get:

\[T_{g \circ f} = \log f_0 + T_{\log(1+x)} \circ \frac{\hat f}{f_0}\]

and, using the known expression for MacLaurin expansion of \(\log(1+x)\), we get:

(3)\[T_{(\log f)} = \log f_0 + \sum_{i=1}^m (-1)^{i+1} \frac 1i \left(\frac{\hat f}{f_0}\right)^i = \log f_0 + \frac{\hat f}{f_0} - \frac 12 \left(\frac{\hat f}{f_0}\right)^2 + ...\]

Note that the above expression is only defined if \(f_0 \ge 0\).

Sine and cosine

Let us consider the case of the sine and cosine functions:

\[g_1(x) = \sin(x) = \sum_{i=0} (-1)^{i} \frac{x^{2i+1}}{(2i+1)!} = x - \frac{x^3}{3!} + \frac{x^5}{5!} - ...\]
\[g_2(x) = \cos(x) = \sum_{i=0} (-1)^{i} \frac{x^{2i}}{(2i)!} = 1 - \frac{x^2}{2!} + \frac{x^4}{4!} - ...\]

We want to compute the truncated Taylor expansion of \(\sin(f(\mathbf x))\), \(\cos(f(\mathbf x))\) starting from the truncated Taylor expansion \(T_f = f_0 + \hat f\). We thus write:

\[(g_1 \circ f) (\mathbf x) = \sin(f(\mathbf x)) = \sin f_0 \cos(f(\mathbf x) - f_0) + \cos f_0 \sin(f(\mathbf x) - f_0)\]
\[(g_2 \circ f) (\mathbf x) = \cos(f(\mathbf x)) = \cos f_0 \cos(f(\mathbf x) - f_0) - \sin f_0 \sin(f(\mathbf x) - f_0)\]

and, applying the composition rule to \(\cos(f(\mathbf x) - f_0)\) and \(\sin(f(\mathbf x) - f_0)\), we get:

(4)\[\begin{split}T_{(\sin f)} = \sin f_0 \left(\sum_{i=0}^{2i\le m} (-1)^{i} \frac{\hat f^{2i}}{(2i)!}\right) + \cos f_0 \left(\sum_{i=0}^{(2i+1)\le m} (-1)^{i} \frac{\hat f^{2i+1}}{(2i+1)!}\right) \\ T_{(\cos f)} = \cos f_0 \left(\sum_{i=0}^{2i\le m} (-1)^{i} \frac{\hat f^{2i}}{(2i)!}\right) - \sin f_0 \left(\sum_{i=0}^{(2i+1)\le m} (-1)^{i} \frac{\hat f^{2i+1}}{(2i+1)!}\right)\end{split}\]

Exponentiation

Let us consider the case of the power function.

\[g(x) = x^\alpha\]

We want to compute the truncated Taylor expansion of \(f(\mathbf x)^\alpha\) assuming to have access to the truncated Taylor expansion of \(f\), \(T_f = f_0 + \hat f\). We thus write:

\[(g \circ f) (\mathbf x) = f(\mathbf x) ^ \alpha = (f_0 + (f(\mathbf x) - f_0))^\alpha = f_0^\alpha \left( 1+ \frac{f(x) - f_0}{f_0}\right)^\alpha\]

We can now apply the composition rule to get:

\[T_{f(\mathbf x)^\alpha} = f_0^\alpha \left(T_{(1+x)^\alpha}\circ \frac{\hat f}{f_0}\right) =\]
(5)\[= f_0^\alpha \sum_{k=0}^m {\alpha \choose k} \left(\frac{\hat f}{f_0}\right)^k = f_0^\alpha\left(1 + \alpha \frac{\hat f}{f_0} + \frac{\alpha (\alpha - 1)}{2}\left(\frac{\hat f}{f_0}\right)^2 + ... \right)\]

Inverse functions

The case for the inverse trigonometric functions and hyperbolic functions is more complex and deserves some extended discussion.

Inverse hyperbolic tangent

We consider the inverse hyperbolic tangent function:

\[g(x) = \mbox{atanh} (x)\]

As before, we want to compute the truncated Taylor expansion of \(\mbox{atanh} (f(\mathbf x))\) assuming to have access to the truncated Taylor expansion of \(f\), \(T_f = f_0 + \hat f\). Since there is not a convenient addition formula we must seek a different expression. We start from the identity:

\[\mbox{atanh} (x) = \frac 12 \left(\log (1 + x) - \log (1 - x)\right)\]

which allows us to write:

\[(g \circ f) (\mathbf x) = \mbox{atanh} (f(\mathbf x)) = \frac 12 \left(\log (1 + f(\mathbf x)) - \log (1 - f(\mathbf x))\right)\]

and, using the addition formula for the logarithms, we get:

\[\mbox{atanh} (f(\mathbf x)) = \mbox{atanh} f_0 + \frac 12\left(\log\left(1+\frac{f-f_0}{1+f_0} \right) - \log\left(1-\frac{f-f_0}{1-f_0} \right) \right)\]

we may now apply the composition theorem and find:

\[T_{(\mbox{atanh} f)} = \mbox{atanh} f_0 + \frac 12 \left(T_{\log (1+x)} \circ \frac{\hat f}{1+f_0} - T_{\log (1-x)} \circ \frac{\hat f}{1-f_0}\right)\]

Using the Taylor expansions for the logaritmic functions we get the final expression used in AuDi:

\[T_{(\mbox{atanh} f)} = \mbox{atanh} f_0 +\frac 12 \sum_{n=1}^m \left(\frac{1}{(1-f_0)^n} + \frac{(-1)^{n+1}}{(1+f_0)^n}\right) \frac {\hat f^n}{n}\]

Inverse tangent

We consider the inverse tangent function:

\[g(x) = \mbox{atan} (x)\]

As before, we want to compute the truncated Taylor expansion of \(\mbox{atanh} (f(\mathbf x))\) assuming to have access to the truncated Taylor expansion of \(f\), \(T_f = f_0 + \hat f\). We can apply the following identity involving the imaginary unit \(i\):

\[\mbox{atan}(z) = i \mbox{atanh}(-iz)\]

and therefore write:

\[T_{(\mbox{atan} f)} = \mbox{atan} f_0 +\frac i2 \sum_{k=1}^m \left(\frac{1}{(1+if_0)^k} + \frac{(-1)^{k+1}}{(1-if_0)^k}\right) \frac {\hat f^k}{k}(-i)^k\]

We may avoid to compute the above expression using complex arithmetic by expanding explicitly its terms. Separating the even from the odd powers of $hat f$ we get:

\[\begin{split}\begin{multline*} T_{(\mbox{atan} f)} = \mbox{atan} f_0 +\frac 12 \sum_{k=1}^{2k-1\le m} \left(\frac{1}{(1+if_0)^{2k-1}} + \frac{1}{(1-if_0)^{2k-1}}\right) \frac {\hat f^{2k-1}}{2k-1}(-1)^{k+1} + \\ + \frac i2 \sum_{k=1}^{2k\le m} \left(\frac{1}{(1+if_0)^{2k}} - \frac{1}{(1-if_0)^{2k}}\right) \frac {\hat f^{2k}}{2k}(-1)^k \end{multline*}\end{split}\]

and, expanding further:

\[\begin{split}\begin{multline*} T_{(\mbox{atan} f)} = \mbox{atan} f_0 +\frac 12 \sum_{k=1}^{2k-1\le m} \left(\frac{(1-if_0)^{2k-1} + (1+if_0)^{2k-1}}{(1+f_0^2)^{2k-1}}\right) \frac {\hat f^{2k-1}}{2k-1}(-1)^{k+1} + \\ + \frac i2 \sum_{k=1}^{2k\le m} \left(\frac{(1-if_0)^{2k} - (1+if_0)^{2k}}{(1+f_0^2)^{2k}}\right) \frac {\hat f^{2k}}{2k}(-1)^k \end{multline*}\end{split}\]

Using the binomial theorem it is possible to show:

\[(1+if_0)^n + (1-if_0)^n = 2 + 2\sum_{j=1}^{2j\le n} {n \choose 2j} f_0^{2j}(-1)^j\]

and

\[(1-if_0)^n - (1+if_0)^n = - 2i\sum_{j=1}^{2j-1\le n} {n \choose 2j-1} f_0^{2j-1}(-1)^{j+1}\]

which, substituted in the expression above, return a formula not involving any more imaginary units:

\[\begin{split}\begin{multline*} T_{(\mbox{atan} f)} = \mbox{atan} f_0 + \sum_{k=1}^{2k-1\le m} \left(\frac{1 + \sum_{j=1}^{2j\le 2k-1} {2k-1 \choose 2j} f_0^{2j}(-1)^j}{(1+f_0^2)^{2k-1}}\right) \frac {\hat f^{2k-1}}{2k-1}(-1)^{k+1} + \\ + \sum_{k=1}^{2k\le m} \left(\frac{\sum_{j=1}^{2j-1\le 2k} {2k \choose 2j-1} f_0^{2j-1}(-1)^{j+1}}{(1+f_0^2)^{2k}}\right) \frac {\hat f^{2k}}{2k}(-1)^k \end{multline*}\end{split}\]

This formula is rather friendly to a computer implementation and is used in AuDi.

The other inverse functions

To compute the other inverse functions we may now use the identities:

\[\mbox{arccosh} x = \log(d + \sqrt{d^2 - 1})\]
\[\mbox{arcsinh} x = \log(d + \sqrt{1 + d^2})\]
\[\arcsin x = \arctan(d / \sqrt{1 - d^2})\]
\[\arccos x = \arctan(d / \sqrt{1 - d^2})\]

which apply also for the Taylor expansions.


Practical Examples (to be done by hand)

In the above sections we derived a number of results that allow operating on simple Taylor expansions to compute Taylor expansions of increasingly complex expressions. We summarize here those results (keep in mind that \(T_f = f_0 + \hat f\)) :

(6)\[\begin{split}T_{f\pm g} = T_f \pm T_g\\ T_{fg} = T_f \cdot T_g\\ T_{(1/f)} = \frac 1f_0 \left(1 +\sum_{k=1}^m (-1)^k (\hat f / f_0)^k\right)\\ T_{(\exp f)} = \exp f_0 \sum_{k=0}^m \frac{\hat f^k}{k!} \\ T_{(\log f)} = \log f_0 - \sum_{k=1}^m \frac{(-1)^k}k \left(\hat f / f_0\right)^k \\ T_{(\sin f)} = \sin f_0 \left(\sum_{k=0}^{2k\le m} (-1)^{k} \frac{\hat f^{2k}}{(2k)!}\right) + \cos f_0 \left(\sum_{k=0}^{(2k+1)\le m} (-1)^k \frac{\hat f^{2k+1}}{(2k+1)!}\right) \\ T_{(\cos f)} = \cos f_0 \left(\sum_{k=0}^{2k\le m} (-1)^{k} \frac{\hat f^{2k}}{(2k)!}\right) - \sin f_0 \left(\sum_{k=0}^{(2k+1)\le m} (-1)^k \frac{\hat f^{2k+1}}{(2k+1)!}\right) \\ T_{(f^\alpha)} = f_0^\alpha \sum_{k=0}^m {\alpha \choose k} \left(\hat f / f_0\right)^k\\ T_{(\mbox{atanh} f)} = \mbox{atanh} f_0 +\frac 12 \sum_{n=1}^m \left(\frac{1}{(1-f_0)^n} + \frac{(-1)^{n+1}}{(1+f_0)^n}\right) \frac {\hat f^n}{n}\\ T_{(\mbox{atan} f)} = \mbox{atan} f_0 + \sum_{k=1}^{2k-1\le m} \left(\frac{1 + \sum_{j=1}^{2j\le 2k-1} {2k-1 \choose 2j} f_0^{2j}(-1)^j}{(1+f_0^2)^{2k-1}}\right) \frac {\hat f^{2k-1}}{2k-1}(-1)^{k+1} + \\ + \sum_{k=1}^{2k\le m} \left(\frac{\sum_{j=1}^{2j-1\le 2k} {2k \choose 2j-1} f_0^{2j-1}(-1)^{j+1}}{(1+f_0^2)^{2k}}\right) \frac {\hat f^{2k}}{2k}(-1)^k\end{split}\]

It is worth mentioning here that other functions such as the inverse functions, the hyperbolic functions etc. can also be treated in this way. The above equations can be used to find Taylor expansions of increasingly complex functions by simply operating on the algebra \(\mathcal P_{n,m}\). Once a Taylor expansion is computed, its coefficients can be extracted to obtain the value of any desired derivative. We have thus built an automated differentiation system. While the formalism presented can, at first, appear complex, the system is rather simple as we hope will appear from the following examples.

Example 1 - A multiplication

Consider the simple function of two variables:

\[f(x,y) = x + 3xy + y^2\]

Its Taylor expansion \(T_f \in \mathcal P_{2,2}\) can be computed as:

\[T_f = T_x + 3T_x \cdot T_y + T_y\cdot T_y\]

Let us explicitly compute such an expression at the point \(x=3\), \(y=7\). The exact sequence of computations to be performed is:

\[T_x = 3 + 1 dx + 0 dy + 0 dxdy + 0 dx^2 + 0 dy^2\]
\[T_y = 7 + 0 dx + 1 dy + 0 dxdy + 0 dx^2 + 0 dy^2\]
\[T_x \cdot T_y = 21 + 7 d x + 3 d y + 1 dxdy + 0 dx^2 + 0 dy^2\]

and

\[T_y \cdot T_y = 49 + 0 dx + 14 dy + 0 dxdy + 0 dx^2 + 1 dy^2\]

We can then derive the final expression:

\[T_f = 115 + 22 dx + 23 dy +3 dxdy + 0 dx^2 + 1 dy^2\]

and we may easily extract the derivatives comparing this expression to the generic form of a Taylor expansion:

\[f = 115, \partial_x f = 22, \partial_y f = 23, \partial_{xy} f = 3, \partial_{xx} f = 0, \partial_{yy} f = 2,\]

Example 2 - A division

Consider the simple function of two variables:

\[f = 1 / (x + 2xy + y^2) = 1 / p\]

Its Taylor expansion \(T_f \in \mathcal P_{2,2}\) in (say) \(x=0\), \(y=1\) can be computed as follows:

\[T_x = 0 + 1 dx + 0 dy + 0 dxdy + 0 dx^2 + 0 dy^2\]
\[T_y = 1 + 0 dx + 1 dy + 0 dxdy + 0 dx^2 + 0 dy^2\]
\[T_p = 1 + 3 dx + 2 dy +2 dxdy + 0 dx^2 + 1 dy^2\]

and, applying the reciprocal rule, we conclude

\[T_f = ( 1 - \hat p + \hat p ^ 2 )\]

where \(\hat p = 3 dx + 2 dy +2 dxdy + 0 dx^2 + 1 dy^2\), hence:

\[T_f = 1 -3 dx -2 dy + 10dxdy + 9dx^2 + 3dy^2\]

which allows, as in the previous example, to compute all derivatives up to order two:

\[f = 1, \partial_x f = -3, \partial_y f = -2, \partial_{xy} f = 10, \partial_{xx} f = 18, \partial_{yy} f = 6,\]

Example 3 - An exponential

Consider the elementary function of two variables:

\[f = \exp(xy)\]

Its Taylor expansion \(T_f \in \mathcal P_{2,2}\) in (say) \(x=1\), \(y=0\) can be computed as follows:

\[T_x = 1 + 1 dx + 0 dy + 0 dxdy + 0 dx^2 + 0 dy^2\]
\[T_y = 0 + 0 d x + 1 dy + 0 dxdy + 0 dx^2 + 0 dy^2\]
\[T_x \cdot T_y = 0 + 0 dx + 1 dy + 1 dxdy + 0 dx^2 + 0dy^2\]

and, applying the rule for the exponential of Taylor series, we conclude:

\[T_f = 1 + dy + dxdy + \frac 12 dy^2\]

and,

\[f = 1, \partial_x f = 0, \partial_y f = 1, \partial_{xy} f = 1, \partial_{xx} f = 0, \partial_{yy} f = 1,\]