8
$\begingroup$

The Question.

Suppose we have $n$ linear functions $f_k$ defined on $[x_1,x_2]$. Let $f_k(x_1)=y_k$ and $f_k(x_2)=z_k$ denote the function values at the endpoints of the interval. We would like to calculate

$$\mathfrak{P}(n)=\int_{x_1}^{x_2} \prod_{k=1}^n f_k(x) \, dx$$

in terms of $x_1,x_2,$ and $y_k, z_k$ for $k\in\{1,\ldots,n\}$.

The motivation for this comes from mathematical programming-- specifically, an algorithm I'm writing that requires integrating the product of a large number of piecewise linear functions. What I would like is to find a closed form for $\mathfrak{P}(n)$.

Let's work through a few examples and see if a formula jumps out at us.

Example: $n=2$

The first thing to do is write the $f_k$ in terms of the endpoint values. Solving $f_k(x_1)=mx_1+b=y_k$ and $f_k(x_2)=mx_2+b=z_k$, we get

$$f_k(x)=\frac{z_k-y_k}{x_2-x_1}x+\frac{y_k x_2-z_kx_1}{x_2-x_1}$$

So, then, we are calculating

$$ \mathfrak{P}(2)=\int_{x_1}^{x_2} \left(\frac{z_1-y_1}{x_2-x_1}x+\frac{y_1 x_2-z_1x_1}{x_2-x_1}\right)\left(\frac{z_2-y_2}{x_2-x_1}x+\frac{y_2 x_2-z_2x_1}{x_2-x_1}\right) \, dx $$

which, God help us, is

$$ \left.\frac{x \left(3 x (y_1 z_2 (x_1+x_2)+y_2 z_1 (x_1+x_2)-2 x_1 z_1 z_2-2 x_2 y_1 y_2)+6 (x_1 z_1-x_2 y_1) (x_1 z_2-x_2 y_2)+2 x^2 (y_1-z_1) (y_2-z_2)\right)}{6 (x_1-x_2){}^2}\right|_{x_1}^{x_2} $$ Luckily, this simplifies quite a bit down to $$ \frac{1}{6} (x_2-x_1)(y_1 (2 y_2+z_2)+z_1 (y_2+2 z_2)). $$

Alright! It didn't turn out that bad.

Example: $n=3,\ldots, 6$

Let's take a look at some other values of $\mathfrak{P}$. I'll spare you the intermediate calculations.

$$\begin{eqnarray*}\mathfrak{P}(3)&=&\frac{1}{12} (x_2-x_1) (y_1 y_3 (3 y_2+z_2)+y_1 z_3 (y_2+z_2)+y_3 z_1 (y_2+z_2)+z_1 z_3 (y_2+3 z_2))\\ \mathfrak{P}(4)&=&\frac{1}{60} (x_2-x_1) (y_1 y_4 (3 y_2 (4 y_3+z_3)+z_2 (3 y_3+2 z_3))+y_1 z_4 (3 y_2 y_3+2 y_2 z_3+2 y_3 z_2+3 z_2 z_3)+y_4 z_1 (3 y_2 y_3+2 y_2 z_3+2 y_3 z_2+3 z_2 z_3)+z_1 z_4 (y_2 (2 y_3+3 z_3)+3 z_2 (y_3+4 z_3)))\\ \mathfrak{P}(5)&=&\frac{1}{60}(x_2-x_1) (y_1 y_5 (2 y_2 y_4 (5 y_3+z_3)+y_2 z_4 (2 y_3+z_3)+y_4 z_2 (2 y_3+z_3)+z_2 z_4 (y_3+z_3))+y_1 z_5 (y_2 y_4 (2 y_3+z_3)+y_2 z_4 (y_3+z_3)+y_4 z_2 (y_3+z_3)+z_2 z_4 (y_3+2 z_3))+y_5 z_1 (y_2 y_4 (2 y_3+z_3)+y_2 z_4 (y_3+z_3)+y_4 z_2 (y_3+z_3)+z_2 z_4 (y_3+2 z_3))+z_1 z_5 (y_2 y_4 (y_3+z_3)+y_2 z_4 (y_3+2 z_3)+y_4 z_2 (y_3+2 z_3)+2 z_2 z_4 (y_3+5 z_3)))\\ \mathfrak{P}(6)&=&\frac{1}{420} (x_2-x_1) (y_1 y_2 (2 y_3 y_6 (5 y_4 (6 y_5+z_5)+z_4 (5 y_5+2 z_5))+y_3 z_6 (10 y_4 y_5+4 y_4 z_5+4 y_5 z_4+3 z_4 z_5)+y_6 z_3 (10 y_4 y_5+4 y_4 z_5+4 y_5 z_4+3 z_4 z_5)+z_3 z_6 (4 y_4 y_5+3 y_4 z_5+3 y_5 z_4+4 z_4 z_5))+y_1 z_2 (y_3 y_6 (10 y_4 y_5+4 y_4 z_5+4 y_5 z_4+3 z_4 z_5)+y_3 z_6 (4 y_4 y_5+3 y_4 z_5+3 y_5 z_4+4 z_4 z_5)+y_6 z_3 (4 y_4 y_5+3 y_4 z_5+3 y_5 z_4+4 z_4 z_5)+z_3 z_6 (3 y_4 y_5+4 y_4 z_5+4 y_5 z_4+10 z_4 z_5))+y_2 z_1 (y_3 y_6 (10 y_4 y_5+4 y_4 z_5+4 y_5 z_4+3 z_4 z_5)+y_3 z_6 (4 y_4 y_5+3 y_4 z_5+3 y_5 z_4+4 z_4 z_5)+y_6 z_3 (4 y_4 y_5+3 y_4 z_5+3 y_5 z_4+4 z_4 z_5)+z_3 z_6 (3 y_4 y_5+4 y_4 z_5+4 y_5 z_4+10 z_4 z_5))+z_1 z_2 (y_3 y_6 (4 y_4 y_5+3 y_4 z_5+3 y_5 z_4+4 z_4 z_5)+y_3 z_6 (3 y_4 y_5+4 y_4 z_5+4 y_5 z_4+10 z_4 z_5)+y_6 z_3 (3 y_4 y_5+4 y_4 z_5+4 y_5 z_4+10 z_4 z_5)+2 z_3 z_6 (y_4 (2 y_5+5 z_5)+5 z_4 (y_5+6 z_5))))\end{eqnarray*}$$

There certainly seems to be some pattern here.

The coefficient has a denominator of $\operatorname{lcm}\{1,\ldots,n+1\}$ and we're always multiplying by $x_2-x_1$, so let's just get rid of that first term by looking at $\frac{\operatorname{lcm}\{1,\ldots,n+1\}}{x_2-x_1}\mathfrak{P}_n$. Maybe it will help us see the pattern if we expand everything out.

$$ \begin{eqnarray*}\frac{\operatorname{lcm}\{1,\ldots,4\}}{x_2-x_1}\mathfrak{P}_3&=&3 y_1 y_2 y_3+y_1 y_2 z_3+y_1 y_3 z_2+y_1 z_2 z_3+y_2 y_3 z_1+y_2 z_1 z_3+y_3 z_1 z_2+3 z_1 z_2 z_3\\ \frac{\operatorname{lcm}\{1,\ldots,5\}}{x_2-x_1}\mathfrak{P}_4&=&12 y_1 y_2 y_3 y_4+3 y_1 y_2 y_3 z_4+3 y_1 y_2 y_4 z_3+2 y_1 y_2 z_3 z_4+3 y_1 y_3 y_4 z_2+2 y_1 y_3 z_2 z_4+2 y_1 y_4 z_2 z_3+\cdots\\ &\cdots&3 y_1 z_2 z_3 z_4+3 y_2 y_3 y_4 z_1+2 y_2 y_3 z_1 z_4+2 y_2 y_4 z_1 z_3+3 y_2 z_1 z_3 z_4+2 y_3 y_4 z_1 z_2+3 y_3 z_1 z_2 z_4+\cdots\\&\cdots&3 y_4 z_1 z_2 z_3+12 z_1 z_2 z_3 z_4\\ \frac{\operatorname{lcm}\{1,\ldots,6\}}{x_2-x_1}\mathfrak{P}_5&=&10 y_1 y_2 y_3 y_4 y_5+2 y_1 y_2 y_3 y_4 z_5+2 y_1 y_2 y_3 y_5 z_4+y_1 y_2 y_3 z_4 z_5+2 y_1 y_2 y_4 y_5 z_3+y_1 y_2 y_4 z_3 z_5+\cdots\\&\cdots&y_1 y_2 y_5 z_3 z_4+y_1 y_2 z_3 z_4 z_5+2 y_1 y_3 y_4 y_5 z_2+y_1 y_3 y_4 z_2 z_5+y_1 y_3 y_5 z_2 z_4+y_1 y_3 z_2 z_4 z_5+\cdots\\&\cdots&y_1 y_4 y_5 z_2 z_3+y_1 y_4 z_2 z_3 z_5+y_1 y_5 z_2 z_3 z_4+2 y_1 z_2 z_3 z_4 z_5+2 y_2 y_3 y_4 y_5 z_1+y_2 y_3 y_4 z_1 z_5+\cdots\\&\cdots&y_2 y_3 y_5 z_1 z_4+y_2 y_3 z_1 z_4 z_5+y_2 y_4 y_5 z_1 z_3+y_2 y_4 z_1 z_3 z_5+y_2 y_5 z_1 z_3 z_4+2 y_2 z_1 z_3 z_4 z_5+\cdots\\&\cdots&y_3 y_4 y_5 z_1 z_2+y_3 y_4 z_1 z_2 z_5+y_3 y_5 z_1 z_2 z_4+2 y_3 z_1 z_2 z_4 z_5+y_4 y_5 z_1 z_2 z_3+2 y_4 z_1 z_2 z_3 z_5+\cdots\\&\cdots&2 y_5 z_1 z_2 z_3 z_4+10 z_1 z_2 z_3 z_4 z_5\\ \frac{\operatorname{lcm}\{1,\ldots,7\}}{x_2-x_1}\mathfrak{P}_6&=& 60 y_1 y_2 y_3 y_4 y_5 y_6+10 y_1 y_2 y_3 y_4 y_5 z_6+10 y_1 y_2 y_3 y_4 y_6 z_5+4 y_1 y_2 y_3 y_4 z_5 z_6+10 y_1 y_2 y_3 y_5 y_6 z_4+\cdots\\&\cdots& 4 y_1 y_2 y_3 y_5 z_4 z_6+4 y_1 y_2 y_3 y_6 z_4 z_5+3 y_1 y_2 y_3 z_4 z_5 z_6+10 y_1 y_2 y_4 y_5 y_6 z_3+4 y_1 y_2 y_4 y_5 z_3 z_6+\cdots\\&\cdots& 4 y_1 y_2 y_4 y_6 z_3 z_5+3 y_1 y_2 y_4 z_3 z_5 z_6+4 y_1 y_2 y_5 y_6 z_3 z_4+3 y_1 y_2 y_5 z_3 z_4 z_6+3 y_1 y_2 y_6 z_3 z_4 z_5+\cdots\\&\cdots& 4 y_1 y_2 z_3 z_4 z_5 z_6+10 y_1 y_3 y_4 y_5 y_6 z_2+4 y_1 y_3 y_4 y_5 z_2 z_6+4 y_1 y_3 y_4 y_6 z_2 z_5+3 y_1 y_3 y_4 z_2 z_5 z_6+\cdots\\&\cdots& 4 y_1 y_3 y_5 y_6 z_2 z_4+3 y_1 y_3 y_5 z_2 z_4 z_6+3 y_1 y_3 y_6 z_2 z_4 z_5+4 y_1 y_3 z_2 z_4 z_5 z_6+4 y_1 y_4 y_5 y_6 z_2 z_3+\cdots\\&\cdots& 3 y_1 y_4 y_5 z_2 z_3 z_6+3 y_1 y_4 y_6 z_2 z_3 z_5+4 y_1 y_4 z_2 z_3 z_5 z_6+3 y_1 y_5 y_6 z_2 z_3 z_4+4 y_1 y_5 z_2 z_3 z_4 z_6+\cdots\\&\cdots& 4 y_1 y_6 z_2 z_3 z_4 z_5+10 y_1 z_2 z_3 z_4 z_5 z_6+10 y_2 y_3 y_4 y_5 y_6 z_1+4 y_2 y_3 y_4 y_5 z_1 z_6+4 y_2 y_3 y_4 y_6 z_1 z_5+\cdots\\&\cdots& 3 y_2 y_3 y_4 z_1 z_5 z_6+4 y_2 y_3 y_5 y_6 z_1 z_4+3 y_2 y_3 y_5 z_1 z_4 z_6+3 y_2 y_3 y_6 z_1 z_4 z_5+4 y_2 y_3 z_1 z_4 z_5 z_6+\cdots\\&\cdots& 4 y_2 y_4 y_5 y_6 z_1 z_3+3 y_2 y_4 y_5 z_1 z_3 z_6+3 y_2 y_4 y_6 z_1 z_3 z_5+4 y_2 y_4 z_1 z_3 z_5 z_6+3 y_2 y_5 y_6 z_1 z_3 z_4+\cdots\\&\cdots& 4 y_2 y_5 z_1 z_3 z_4 z_6+4 y_2 y_6 z_1 z_3 z_4 z_5+10 y_2 z_1 z_3 z_4 z_5 z_6+4 y_3 y_4 y_5 y_6 z_1 z_2+3 y_3 y_4 y_5 z_1 z_2 z_6+\cdots\\&\cdots& 3 y_3 y_4 y_6 z_1 z_2 z_5+4 y_3 y_4 z_1 z_2 z_5 z_6+3 y_3 y_5 y_6 z_1 z_2 z_4+4 y_3 y_5 z_1 z_2 z_4 z_6+4 y_3 y_6 z_1 z_2 z_4 z_5+\cdots\\&\cdots& 10 y_3 z_1 z_2 z_4 z_5 z_6+3 y_4 y_5 y_6 z_1 z_2 z_3+4 y_4 y_5 z_1 z_2 z_3 z_6+4 y_4 y_6 z_1 z_2 z_3 z_5+10 y_4 z_1 z_2 z_3 z_5 z_6+\cdots\\&\cdots& 4 y_5 y_6 z_1 z_2 z_3 z_4+10 y_5 z_1 z_2 z_3 z_4 z_6+10 y_6 z_1 z_2 z_3 z_4 z_5+60 z_1 z_2 z_3 z_4 z_5 z_6 \end{eqnarray*} $$

The pattern in the variables is easy to see-- there are $2^n$ terms, each of which has terms $1$ through $n$ of either the $y$ or the $z$. (What I mean is, the terms are in 1-to-1 correspondence with $\{y_1,z_1\}\times \cdots \times \{y_n,z_n\}$.)

But, what are the coefficients?

$\endgroup$
  • $\begingroup$ Do you specifically want a formula for each coefficient, or will any efficient algorithm to compute $\mathfrak{P}(n)$ suffice? $\endgroup$ – Mike Earnest May 3 at 18:51
  • $\begingroup$ @MikeEarnest I was looking for the former but I'd take the latter. (Always the possibility it could turn into the former, too.) $\endgroup$ – Alexander Gruber May 3 at 18:54
  • $\begingroup$ This probably doesn't help, but if you can do substitution (since any efficient algorithm is enough), this might be equivalent to calculating $\int_0^1 \prod(m_ix+c_i) dx$ $\endgroup$ – Gareth Ma May 3 at 22:28
9
+500
$\begingroup$

By translating and rescaling you can write \begin{align*} \mathfrak{P}(n) &= (x_2 - x_1) \int_0^1 \prod_{k=1}^n (y_k(1 - x) + z_kx)\,dx \\ &= (x_2 - x_1) \int_0^1 \sum_{S \subset [n]}\left((1 - x)^{|S|}x^{n-|S|} \prod_{k \in S} y_k \prod_{k \not \in S} z_k\right)\,dx \\ &= (x_2 - x_1) \sum_{S \subset [n]} B\big(n-|S|+1\,,\, |S|+1 \big) \prod_{k \in S} y_k \prod_{k \not \in S} z_k \\ &= (x_2 - x_1) \sum_{S \subset [n]} \frac{1}{(n+1) \binom{n}{|S|}} \prod_{k \in S} y_k \prod_{k \not \in S} z_k \end{align*} where $[n] = \{1, \dots, n\}$ and $B(a, b) = \int_0^1 x^{a-1} (1-x)^{b-1} \,dx = \frac{\Gamma(a)\Gamma(b)}{\Gamma(a+b)}$ is the Beta function.


Addendum: If you need a quick way to calculate this, note that this is $$(x_2 - x_1) \sum_{j=0}^n \frac{a_j}{(n+1)\binom{n}{j}}$$ where $a_j$ is the coefficient of $x^j$ in the polynomial $\prod_{k=1}^n (xy_k + z_k)$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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