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](https://en.wikipedia.org/wiki/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.

[![Uniform vs Chebyshev nodes](https://i.stack.imgur.com/FX1ll.png)](https://i.stack.imgur.com/FX1ll.png)

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}$.

[![error of approximation](https://i.stack.imgur.com/jhJ9o.png)](https://i.stack.imgur.com/jhJ9o.png)

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.

1. Set $x\_0 = 0$.
2. For $n=0,1,2,\dotsc$ find (e.g. by binary search) $x\_{n+1}$ that ensures $d(x\_n, x\_{n+1}) = \epsilon$.
3. 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?