Approximating exp(x) with a piecewise-linear function accurately

Question

I am looking for the best way to approximate $\exp(x)$ on a finite domain $[0,M]$ with a piecewise-linear function. My initial approach is to take $K$ evenly-spaced segments from $0$ to $M$. For each segment $[s_k, s_{k+1}]$, I add the line from point $(s_k, \exp(s_k))$ to point $(s_{k+1}, \exp(s_{k+1}))$.

But what I've noticed is that the approximation gets worse for segments closer to $M$. Intuitively, this suggests that the segments need to start large and then reduce in size as we approach $M$. But how would one approach this formally? I am also interested in heuristics, or approximations.

Answer 1

For $b$ not much larger than $a$, the maximum difference between $e^x$ and the line from $(a,e^a)$ to $(b,e^b)$, for $x\in[a,b]$, is approximately $\frac 18 (b-a)^2 e^a$.

So you should choose your points so that $(b-a)^2 e^a$ is approximately constant for each interval. After selecting the first interval, use this rule to select further intervals. They will get gradually smaller.

Answer 2

If you choose the $L^2$ norm, computing $$\Phi(a,b)=\int_a^b \Big[\alpha+\beta\, x -e^x\Big]^2\,dx$$ and minimizing, we have

$$\beta(a,b) =\frac{6}{(b-a)^3}\Big[(b-a +2)\,e^a+(b-a-2)\,e^b\Big]$$ $$\alpha(a,b)=\frac{e^b-e^a}{b-a}-\frac{1}{2} (a+b) \, \beta $$ $$2(a-b)^3\, \Phi_{\text{min}}(a,b)= \left(-e^a (a-b-2)-e^b (a-b+2)\right)\times $$ $$ \left(e^a \left(a^2-2 a (b+3)+b (b+6)+12\right)-e^b \left(a^2-2 (a+3) b+6 a+b^2+12\right)\right)$$

So, for the next point $c$, if we want to keep the same $\Phi_{\text{min}}=k$, we need to find it such that $\Phi_{\text{min}}(b,c)=k$. This does not make any problem using Newton method $$\Phi'_{\text{min}}(b,c)=\frac{\left(e^c \left(b^2-2 (b+2) c+4 b+c^2+6\right)+2 e^b (b-c-3)\right)^2}{(b-c)^4}$$

For the first $c$, we can use $c_0=b+\theta(b-a)$, the first $\theta$ being empirically set equal to $0.5$ ad the next would be updated readjusting $\theta$ from the previous iteration

Suppose that we start with $a=1$ and $b=3$; this gives $k=e^2 \left(e^2-7\right)$ and the iterates are $$\left( \begin{array}{cc} n & c_n \\ 0 & 4.000 \\ 1 & 4.133 \\ 2 & 4.104 \\ 3 & 4.101 \end{array} \right)$$

This allows a recursive definitions of the next points to be used.