Given two piecewise-linear scalar functions $f(x) = a_ix+b_i$ on $[x_i, x_{i+1}], i = 1, \ldots,m$ and $g(x) = \alpha_jx+\beta_j$ on $[y_j, y_{j+1}], j = 1, \ldots,n$. How can we determine the composition $f\circ g$ quickly on the interval $[a, b]$ where $a =\min\{x_1,y_1\}, b = \max\{x_{m+1},y_{n+1}\}$.

What I would do is to write $f\circ g = f(\alpha_jx+\beta_j)$ on$ [y_j, y_{j+1}]$ then find $f(\alpha_jx+\beta_j)$. However, I think there is quick way to give the general formula for $f\circ g$ in term of $x_i$ and $y_j$. Thank you in advance!


The function $f\circ g$ is piecewise linear as a composition of piecewise linear functions. Unfortunately, my experience suggests that descriptions of compostions of piesewise linear fuctions are complicated. In order to determine $f\circ g$ it suffices to determine numbers $z_1\le \dots\le z_p$ such that $ f\circ g (x)=c_k x+d_k$ (I decided to use banal Latin letters instead logical Russian of Hebrew these :-) ) on $[z_k, z_{k+1}]$. I remark that, in general $p=O(mn)$, for instance, when $|Y\cap\bigcap_{i=1}^{m-1} f([x_i,x_{i+1}])|=O(n)$, where $Y=\{y_1,\dots, y_n\}$. Next, we can describe the sequence $\{z_k\}$ as an extension of the sequence $\{x_i\}$, that is there exist numbers $p(1),\dots, p(m-1)$ such that

$$x_1=z_{1,1}\le z_{1,2}\le\dots\le z_{1,p(1)}=x_2=z_{2,1}\le \dots\le z_{2,p(2)}=x_3\le\dots\le z_{m-1,p(m-1)}=x_m,$$

where for each $i$ $(z_{i,2}\le \dots \le z_{i,p(i)-1})$ is an enumeration ot the points $x\in [x_{i},x_{i+1}]$ such that $f(a_ix+b)=y_j$ for some $j$ taken in the increasing order when $a_i>0$ and in the decreasing order when $a_i<0$ (we have to assume that $f([x_i, x_{i+1}])\subset [y_1, y_{n}]$, because otherwise the composition $f\circ g$ can be undefined on $[x_i, x_{i+1}]$). For instance, if $a_i>0$ and $$f([x_i,x_{i+1}])\cap Y=\{y_{j(i)}, y_{j(i)+1},\dots, y_{j’(i)}\}$$ for some numbers $j(i)$ and $j’(i)$ then for each $2\le k\le p(i)-1$ we have $a_iz_{i,k}+ b_i=f(z_{i,k})=y_{j(i)+k-2}$, that is $z_{i,k}=(y_{j(i)+k-2}-b_i)/a_i$. In remains to note that for $x\in [z_{i,k},z_{i+1,k}]$ we have $c_{i,k}x+d_{i,k}\equiv \alpha_{j(i)+k-2}(a_ix+b_i)+\beta_{j(i)+k-2}$ for each $1\le k\le p(i)-1$.


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.