Find a polynomial using minimax approximation

Find a polynomial with the maximum 1. degree which best approximates the $f(x)=e^x$ function in terms of minimax approximation in $[0,1]$.

Solution 1:

We are asked to find a polynomial of maximum degree $1$ which best approximates $f(x)=e^x$ function in terms of minimax approximation in the range $[0,1]$.

Consider the graph of $f(x) = e^x$ and a best possible linear approximation of $y = m x + b$.

Clearly, $f(x)$ and $y(x)$ must be equal at two points $c, d$ in $[0, 1]$, where $0 \le c \lt d \le 1$. Therefore,

$$e^c-y(c) = e^d - y(d) = 0.$$

The maximum error must be attained at exactly three points $0, 1$, and some point $a$ in $(0, 1)$. The minimax theory tells us that we must have:

$$\rho = Max_{0 \le x \le 1} \left(e^x - (m x + b)\right)$$

All of these observations give us:

$$e^0 - b = \rho, e^1 -(m+b) = \rho, e^a - (m a + b) = \rho.$$

We have four variables and this is only three equations, so we add one more equation. Since $w(x) = e^x-(m x+b)$ has a local minimum at $a$, we have $w'(a) = e^a - m = 0$.

These four equations yield:

• $m = e-1 \approx 1.718282$
• $b = \dfrac{e-(e-1)\ln(e-1)}{2} \approx 0.894067$
• $a = \ln(e-1) \approx 0.541325$
• $\rho = 1- b \approx 0.105933.$

This gives us the linear approximation:

$$y(x) = 1.718282 x + 0.894067.$$

This intersects the exponential function at $c = 0.168371$ and $d = 0.873066$.

You can compare this to other least squares methods and see the improvement in the error.

We could have formulated this as minimizing:

$$\text{min} ||f(x) - y(x)||_{\infty} =\text{min} ||e^x - (mx + b)||_{\infty}.$$

If you want to see a slightly different approach (same result of course), look at problem 11.3.