2
$\begingroup$

Let $\Omega = [0,1]^d$ and consider $f : \Omega \to R$ Lipschitz continuous with constant 1.

Consider the regular decomposition of $\Omega$ into $d$-dimensional cubes $\Omega_i$, $i=1 ... k^d$ with $k$ subdivision intervals along each dimension.

Consider the best approximation (in the sense of $ \| \cdot \|_\infty$) of $f$ by a function $\widehat f : \Omega \to R$, which is affine on each $\Omega_i$ and also Lipschitz continuous with constant 1 (and hence continuous).

I'm looking for an error/approximation bound $\| f - \widehat f \|_\infty \leq ...$ in terms of the mesh-size $k$ and dimension $d$.

EDIT: what makes this difficult for me is the requirement that $\widehat f$ is continuous. Since this is a global property, it seems very difficult to get a meaningful bound.

$\endgroup$
1
  • 1
    $\begingroup$ I don't have an answer, but if you have some room here you might want to replace the cubical mesh by a mesh with simplexes. Then the function that matches $f$ on vertices and is affine on each simplex is $1$-Lipschitz, and not too far from $f$. $\endgroup$ Feb 5, 2018 at 21:08

1 Answer 1

1
$\begingroup$

It's easy if $d = 1$, right? So the first case of interest is $d = 2$. Here is an example which shows why I think no nontrivial bound is possible.

(Of course you can always let $\hat{f}$ be a constant function which takes a value halfway between the max and min values of $f$; then $\|f - \hat{f}\|_\infty \leq \frac{\sqrt{d}}{2}$ since the max and min values of $f$ differ by at most the diameter of $[0,1]^d$, namely $\sqrt{d}$.)

Example: define $$f(x,y) = \begin{cases}x-y&\mbox{ if }x \geq y\cr y-x&\mbox{ if }y\geq x\end{cases}$$ on $[0,1]^2$. This has Lipschitz number $\sqrt{2}$, so feel free to scale it down by that factor if you like.

Now let $\hat{f}$ be any function on $[0,1]^2$ which is continuous and affine on each of the $k^2$ sub-squares. The key point is that $\hat{f}$ is determined by its values on the $x$ and $y$ axes. That is because an affine function on a square is determined by its values at the SW, SE, and NW corners of the square. So once we know $\hat{f}$ on the left and bottom boundaries of $[0,1]^2$, an easy double induction shows that we know it everywhere. Indeed, it is not hard to see that we must have $$\hat{f}(x,y) = \hat{f}(x,0) + \hat{f}(0,y) - \hat{f}(0,0)$$ at every point.

Now $f(1,0) = f(0,1) = 1$ and $f(0,0) = f(1,1) = 0$, but if $a = \hat{f}(0,0)$, $b = \hat{f}(1,0)$, and $c = \hat{f}(0,1)$ then $\hat{f}(1,1) = b + c - a$. So if $b$ and $c$ both exceed $\frac{1}{2}$ then one of $\hat{f}(0,0)$ and $\hat{f}(1,1)$ must exceed $\frac{1}{2}$, and this shows that $\|f - \hat{f}\|_\infty \geq \frac{1}{2}$ regardless of mesh.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.