Interpolation nodes for linear spline (piecewise-linear) interpolation of $x \ln x$ 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?
 A: Each piece of deviation from a linear interpolation resembles a parabola. So if we interpolate a function $f$ over a segment of width $w$, then the maximum deviation of the curve from the segment is roughly $(w/2)^2 f''/2$. To get a maximum deviation of $\epsilon$, we should choose $w=\sqrt{8\epsilon/f''}$. To be more precise, we should use a value for $f''$ in the middle of the parabola, whose location we can estimate from the previous two points of interpolation.
This leads to the following procedure: Let
\begin{align}
x_0 &=1 + 1/N\\
x_1 &= 1\\
x_{n+1} &= x_n - \sqrt{8\epsilon\big/ f''\!\left(x_n+\frac{x_n - x_{n-1}}2\right)}\\
\end{align}
Then we interpolate with the points $\{0,x_{N-1},\ldots,x_1\}$.
Here $N=20$, $f(x)=x \log x$, and by trial and error we choose $\epsilon=.00141$. This gives the points
$$\{0.0000, 0.0039, 0.0112, 0.0242, 0.0427, 0.0670, 0.0968, 0.1323, 0.1735, 0.2203, \\
\ \ 0.2727, 0.3308, 0.3945, 0.4638, 0.5388, 0.6195, 0.7057, 0.7976, 0.8951, 1.0000\}.$$
Linear interpolation on those points approximates $f$ with a maximum deviation of only $.00145$.
