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.

Improve this question
$\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$
    – Pietro Majer
    Commented 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$
    – Federico Poloni
    Commented 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$
    – Pietro Majer
    Commented Jun 7, 2018 at 22:05

2 Answers 2

Reset to default
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}$.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ I think Federico asked for a reference, and not for a proof… $\endgroup$
    – Dirk
    Commented 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$
    – Federico Poloni
    Commented 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$
    – Liviu Nicolaescu
    Commented 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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Jackson inequality is about approximation with a generic polynomial, not an interpolating one, if I understand correctly from your link. $\endgroup$
    – Federico Poloni
    Commented 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
    Commented Jun 7, 2018 at 13:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .