4
$\begingroup$

Let $f:[0,1]\to\mathbb{R}$ be a Lipschitz function, and $\pi f$ be its piecewise linear interpolant on an equispaced grid with $n$ points.

It should be true (if I am not making mistakes with the constant) that $$ \int_0^1 |f - \pi f| \leq \frac{1}{4n} \operatorname{Lip}(f). $$

Do you have a reference that I can cite for this result, without having to re-prove it? All the references I have found by looking around assume better regularity.

$\endgroup$
3
  • 3
    $\begingroup$ In fact it is a case where it is more work going and checking the reference than doing the computation. I think that it is fair enough giving a falsifiable statement plus some hints for the proof: e.g., "the case of $n$ intervals consists of $n$ independent optimizations that reduce to the case $n=1$via rescaling; for $n=1$, $\pi f=cx$ and $\int_0^1|f-\pi f|dx\le{L^2-c^2 \over 4L}$, that is maximized for $c=0$, and yields to the sharp bound $L/4n$". $\endgroup$ Jun 7, 2018 at 13:36
  • $\begingroup$ @PietroMajer Thanks! Sorry, where does the $\frac{L^2-c^2}{4L}$ bound come from? I can't see immediately. $\endgroup$ Jun 7, 2018 at 13:54
  • 1
    $\begingroup$ That value is $\int_0^1( \min\{Lx, L(1-x)+c\} -cx)dx$ (corresponding to the optimal $f$ with $f(0)=0$, $f(1)=c$) $\endgroup$ Jun 7, 2018 at 22:05

2 Answers 2

1
$\begingroup$

Clearly it suffices to prove that for any $a<b$ we have $\DeclareMathOperator{\Lip}{Lip}$

$$ \int_a^b \big|\; f-L(f)\;\big| dx\leq \frac{b-a}{4}\Lip(f), $$ where $L(f)$ is the linear function that connects the endpoints of the graph of $f$ $$ x\mapsto f(a)+\frac{f(b)-f(a)}{b-a}x. $$ After rescaling and translations we can assume $a=0$, $b=1$, $f(a)=0$ so it suffices to prove $$ \int_0^1\big|\; f(x) -f(1) x\;\big| dx\leq \frac{1}{4}\Lip(f), $$ $\forall f\in \Lip([0,1])$, $f(0)=0$.

We have $$ \int_0^1\big|\; f(x) -f(1) x\;\big| dx=\int_0^1\Bigg|\; \int_0^x\big(\;f'(y)-f(1)\;\big)dy\;\Bigg| dx $$ $$ = \int_0^1 \Bigg|\; \int_0^xf'(y)-f(1)\;dy\;\Bigg|\; dx\leq \int_0^1 \int_0^x \big|\;f'(y)-f(1)\;\big|\;dy\; dx $$ $$ = \int_0^1 \int_y^1\big|\;f'(y)-f(1)\;\big|dx\; dy= \int_0^1 (1-y)\;\big|\;f'(y)-f(1)\;\big|\;dy $$ Now observe that $\DeclareMathOperator{\Mean}{Mean}$ $$ f(1)=\Mean(f'). $$ We need to find the optimal constant $C$ in the inequality $$ \Big\Vert g-\Mean(g)\Big\Vert_{L^\infty}\leq C\Vert g\Vert_{L^\infty},\;\;g\in L^\infty(0,1). \tag{1} $$ It is not very hard to see that $C\in [1,2]$. We deduce $$ \int_0^1\big|\; f(x) -f(1) x\;\big| dx\leq \frac{C}{2}\Vert f'\Vert_\infty. $$

Another approach.

$$ \int_0^1 (1-y)\;\big|\;f'(y)-f(1)\;\big|\;dy\leq \left(\int_0^1 (1-y)^2 dy\right)^{1/2}\left(\int_0^1 (f'(y)-f(1))^2dy\right)^{1/2}. $$ On the other hand, for any $g\in L^2(0,1)$ we have $$ \int_0^1\Big(\; g(y)-\Mean(g)\;\big)^2 dy\leq \int_0^1 g(y)^2 dy \leq \Vert g\Vert_{L^\infty}^2. $$ Hence $$ \int_0^1 (1-y)\;\big|\;f'(y)-f(1)\;\big|\;dy\leq \left(\int_0^1 (1-y)^2 dy\right)^{1/2}\Vert f'\Vert_{L^\infty}=\frac{1}{\sqrt{3}}\Lip(f). $$ I don't know yet how to improve the constant $\frac{1}{\sqrt{3}}$ to $\frac{1}{4}$.

$\endgroup$
3
  • 1
    $\begingroup$ I think Federico asked for a reference, and not for a proof… $\endgroup$
    – Dirk
    Jun 7, 2018 at 13:16
  • $\begingroup$ Indeed. In addition, it seems to me that this proof assumes that $f$ is $C^1$, not simply Lipschitz. $\endgroup$ Jun 7, 2018 at 13:47
  • 1
    $\begingroup$ It does not assume $C^1$. It uses the fact that for any absolutely continuous function $f$ $f(x)-f(0)=\int_0^x f(t) dt$. $\endgroup$ Jun 7, 2018 at 13:58
1
$\begingroup$

This is a special form of a Jackson inequality, if I am not mistaken. I fail to find the specific case you are interested in, but a start is https://www.encyclopediaofmath.org/index.php/Jackson_inequality.

Edit: As remarked, Jackson inequalities usually deal with best possible general approximations, but the name also refers to other situations. The closest result to what the OP is looking for I could find is Theorem 15 in

Sharp Jackson Inequalities for Piecewise Linear Interpolation and Rectangular Formula; Oleg L.Vinogradov, Vladimir V.Zhuk; 11th IFAC Workshop on Control Applications of Optimization 2000, St Petersburg, Russia, 3-6 July 2000; https://www.sciencedirect.com/science/article/pii/S1474667017396611

Although they formulate their result with the modulus of continuity of $f'$, they only use that the function equal the integral of the derivative and thus, their result and proof also work for the Lipschitz case (where the modulus of continuity is $L$). They also claim to have a sharp inequality for $|f(x) - \pi f(x)|$ and thus, integrating their inequality will give your case.

$\endgroup$
2
  • $\begingroup$ Jackson inequality is about approximation with a generic polynomial, not an interpolating one, if I understand correctly from your link. $\endgroup$ Jun 7, 2018 at 13:50
  • $\begingroup$ Indeed - the original paper by Jackson is also available (jstor.org/stable/1988698), and it also deals with interpolation, but with trigonometric polynomials… $\endgroup$
    – Dirk
    Jun 7, 2018 at 13:55

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.