I need to approximate $x \ln x$ on $[0,1]$ as a piecewise-linear function. If $P(x)$ is a piecewise-linear approximation, I want to minimize $$ \max_{0 \le x \le 1} |P(x) - x \ln x| \rightarrow \min_P. $$
I tried interpolation over evenly spread points $x_i = \frac{i}{n}$, for $i=0,1,\dotsc,n$. I also tried Chebyshev nodes together with additional nodes $x=0$ and $x=1$. The latter works much better. For my numerical problem, it was enough but I am interested in optimal solution (mathematical mind, you know :)
Is there a way to optimally spread points $x_0, x_1, \dotsc, x_n$ over $[0,1]$ for piecewise-linear interpolation/approximation?
Update To illustrate the difference between uniform and Chebyshev nodes, here is the error of approximation with $n=20$ points.
My guess is that for optimal nodes, the "bumps" should be of the same height.
Update 2
I have also the following idea of a numerical method.
First, let us see what is the maximum error of approximation between points $x_n$ and $x_{n+1}$.
We can find equation of an approximating (red) line $y = kx + b$, where $$ k = \frac{x_{n+1} \ln x_{n+1} - x_n \ln x_n}{x_{n+1} - x_n}, \quad b = -k x_n+x_n \ln x_n \,. $$
Next, for $x_n \le x \le x_{n+1}$, we can define the error of approximation at point $x$: $$ \delta(x) = k x + b - x \ln x \,. $$ To find the maximum error, we just solve $\delta'(x) = 0$: $$ 0 = (kx + b - x \ln x)' = k - \ln x - 1. $$ Therefore, the maximum error on $[x_n,x_{n+1}]$ is achieved at $x_c=e^{k-1}$ and it is equal to $$ d(x_n, x_{n+1}) = k x_c + b - x_c \ln x_c \,, $$ where $k$, $b$, and $x_c$ depend on $x_n$ and $x_{n+1}$ as described above. Note also that if we fix $x_n$, the $d(x_n, x_{n+1})$ is increasing function in $x_{n+1}$.
Now, the method itself. Assume we want to ensure that approximation error is not larger than $\epsilon$. Then the following iterative procedure can be applied to construct the list of points.
- Set $x_0 = 0$.
- For $n=0,1,2,\dotsc$ find (e.g. by binary search) $x_{n+1}$ that ensures $d(x_n, x_{n+1}) = \epsilon$.
- Stop when some $x_{n+1} \ge 1$. Change $x_{n+1}$ to $x_{n+1} = 1$ (not necessary but to make things nicer).
But is there an analytical solution?