Skip to main content
1 of 3
Roy Han
  • 599
  • 3
  • 11

error estimate of linear interpolation in high dimension

Consider convex functions $f,g$ on $[0,1]^d$. Let $x_1,\cdots,x_n$ be $n\geq d+1$ fixed point in $[0,1]^d$ that is equally 'distributed' in the sense that $$c_1\leq \frac{n\mathrm{vol}(K)}{\mathrm{card}(K\cap\{x_1,\cdots,x_n\})}\leq c_2$$ holds for all convex $K$ intersecting no less than $d+1$ points in $\{x_1,\cdots,x_n\}$. Let $\bar{f},\bar{g}$ be the linear interpolation of $f,g$ on $\mathrm{conv}\{x_1,\cdots,x_n\}$ defined by \begin{equation*} \begin{split} \bar{f}(x)&=\sum_{\lambda \in \Delta_n,\sum_{i=1}^n\lambda_i x_i=x}\lambda_i f(x_i),\\ \bar{g}(x)&=\sum_{\lambda \in \Delta_n,\sum_{i=1}^n\lambda_i x_i=x}\lambda_i g(x_i). \end{split} \end{equation*} Then can we get an error estimate of $$\int_{\mathrm{conv}\{x_1,\cdots,x_n\}}(\bar{f}-\bar{g})^2\ dx$$ in terms of $\{f(x_i),g(x_i)\}_{i=1}^n$?

In dimension $1$, we can write down explicitly the closed form formular for $\bar{f},\bar{g}$, and some calculation reveals that $$\frac{c_1}{6n}\sum_i \big(f(x_i)-g(x_i)\big)^2\leq\int_{\mathrm{conv}\{x_1,\cdots,x_n\}}(\bar{f}-\bar{g})^2\ dx\leq \frac{c_2}{n}\sum_i \big(f(x_i)-g(x_i)\big)^2.$$ In higher dimension, the difficulty for the estimate is we may not have the same partitioning sets for interpolation so the calculation is not so easy to be done at a local level.

Any comment shall be greatly appreciated.

Roy Han
  • 599
  • 3
  • 11