Abstract
Authors
Keywords
?
Paper coordinates
T. Popoviciu, Sur l’approximation des fonctions convexes d’ordre supérieur (I), Mathematica, 10 (1935), pp. 49-54 (in French).
About this paper
Journal
Mathematica
Publisher Name
published by the Romanian Academy Publishing House
DOI
Print ISSN
Online ISSN
google scholar link
??
Paper (preprint) in HTML form
Original text
Rate this translation
Your feedback will be used to help improve Google Translate
ON THE APPROXIMATION OF HIGHER-ORDER CONVEX FUNCTIONS.
Received on March 20, 1934.
That isf(x)f(x)a function defined in the interval(0.1)(0.1)
Let's define the expression[x_(1),x_(2),dots,x_(n+1);f]\left[x_{1}, x_{2}, \ldots, x_{n+1}; f\right]by the recurrence relation
That isf(x)f(x)a function defined in the interval(0.1)(0.1)
Let's define the expression[x_(1),x_(2),dots,x_(n+1);f]\left[x_{1}, x_{2}, \ldots, x_{n+1}; f\right]by the recurrence relation
{:[[x_(1),x_(2),dots,x_(n+1);f]=([x_(2),x_(3),dots,x_(n+1);f]-[x_(1),x_(2),dots,x_(n);f])/(x_(n+1)-x_(1))],[[x_(1);f]=f(x_(1)).]:}\begin{gathered} {\left[x_{1}, x_{2}, \ldots, x_{n+1}; f\right]=\frac{\left[x_{2}, x_{3}, \ldots, x_{n+1}; f\right]-\left[x_{1}, x_{2}, \ldots, x_{n}; f\right]}{x_{n+1}-x_{1}}} \\ {\left[x_{1}; f\right]=f\left(x_{1}\right) .} \end{gathered}
The quotient[x_(1),x_(2),dotsx_(n+1);f]\left[x_{1}, x_{2}, \ldots x_{n+1}; f\right]is the divided difference of ordernnof the functionf(x)f(x)relative to the distinct pointsx_(1),x_(2),dotsx_(n+1)x_{1}, x_{2}, ... x_{n+1}. Either
{: bar(lim)_([dans(0,1)])|x_(1),x_(2),dots,x_(n+1);f]|=Delta_(n)[f].\left.\varlimsup_{[\operatorname{in}(0,1)]} \mid x_{1}, x_{2}, \ldots, x_{n+1}; f\right] \mid=\Delta_{n}[f] .
Delta_(n)[f]\Delta_{n}[f]is the nth boundary off(x)f(x)In(0.1)(0.1)
Let us consider the points
(1 )
Let us consider the points
(1 )
x_(1) < x_(2) < dots. < x_(m)x_{1}<x_{2}<\ldots .<x_{m}
SO
v_(m)=sum_(i=1)^(mn-1)|[x_(i+1),x_(i+2),dots,x_(i+n+1);f]-[x_(i),x_(i+1),dots,x_(i+n);f]|v_{m}=\sum_{i=1}^{mn-1}\left|\left[x_{i+1}, x_{i+2}, \ldots, x_{i+n+1}; f\right]-\left[x_{i}, x_{i+1}, \ldots, x_{i+n}; f\right]\right|
is the nth variation off(x)f(x)on points (1).
If we set
If we set
bar(lim)_(["in "(0,1)])v_(m)=grad_(n)[f]\varlimsup_{[\text {dans }(0,1)]} v_{m}=\nabla_{n}[f]
SOV_(n)[f]V_{n}[f]is the nth total variation off(x)f(x)In(0.1)(0.1).
Finally, we will say that the functionf(x)f(x)is convex, non-concave, polynomial, non-convex or concave of ordernnIn(0.1)(0.1)if its differences divided by ordern+1n+1on any group ofn+2n+2points(0.1)(0.1)are> 0, >= 0, = 0 <= 0>0, \geq 0,=0 \leq 0Or< 0<0.
These functions form the class of order functionsnnWe
will say that the function is of the class (a,b,c,dotsa, b, c, \ldots) if it possesses order propertiesa,b,c,dotsa, b, c, \ldotsof a specific convexity. For uniformity, we can call it an order function -1\mathbf{1}any function not changing sign ( 1 ).
will say that the function is of the class (a,b,c,dotsa, b, c, \ldots) if it possesses order propertiesa,b,c,dotsa, b, c, \ldotsof a specific convexity. For uniformity, we can call it an order function -1\mathbf{1}any function not changing sign ( 1 ).
- The polynomial
P_(n)=P_(n)(x;f)=sum_(i=0)^(n)f((i)/(n))*((n)/(i))x^(i)(1-x)^(n-t)\mathrm{P}_{n}=\mathrm{P}_{n}(x ; f)=\sum_{i=0}^{n} f\left(\frac{i}{n}\right) \cdot\binom{n}{i} x^{i}(1-x)^{n-t}
is the MS Bernstein polynomial of degreennof the given function.
Let's simplify the notation.
Let's simplify the notation.
Delta_(k)^(i)◻[(i+k)/(n),(i+k-1)/(n),dots,(i)/(n);f],quad i=0,1,dots,n-k,k=1,2,dots\Delta_{k}^{i} \square\left[\frac{i+k}{n}, \frac{i+k-1}{n}, \ldots, \frac{i}{n} ; f\right], \quad i=0,1, \ldots, n-k, k=1,2, \ldots
A simple calculation gives us
(dP_(n))/(dx)=sum_(i=0)^(n-1)Delta_(1)^(i)((n-1)/(i))x^(i)(1-x^(i))^(n-1-i)\frac{d \mathrm{P}_{n}}{d x}=\sum_{i=0}^{n-1} \Delta_{1}^{i}\binom{n-1}{i} x^{i}\left(1-x^{i}\right)^{n-1-i}
and in general
(2)(d^(k)P_(n))/(dx^(k))=k!(1-(1)/(n))(1-(2)/(n))dots\frac{d^{k} \mathrm{P}_{n}}{d x^{k}}=k!\left(1-\frac{1}{n}\right)\left(1-\frac{2}{n}\right) \ldots
(2)(d^(k)P_(n))/(dx^(k))=k!(1-(1)/(n))(1-(2)/(n))dots\frac{d^{k} \mathrm{P}_{n}}{d x^{k}}=k!\left(1-\frac{1}{n}\right)\left(1-\frac{2}{n}\right) \ldots
dots(1-(k-1)/(n))sum_(l=0)^(n-k)Delta_(k)^(i)((n-k)/(i))x^(l)(1-k)^(n-k-1)\ldots\left(1-\frac{k-1}{n}\right) \sum_{l=0}^{n-k} \Delta_{k}^{i}\binom{n-k}{i} x^{l}(1-k)^{n-k-1}
We have
Delta_(0)[P_(n)] <= Delta_(0)[f]\Delta_{0}\left[\mathrm{P}_{n}\right] \leq \Delta_{0}[f]
We know that (^(2){ }^{2})
k!Delta_(k)[P_(n)]=Delta_(0)[P_(n)^((k))]k!\Delta_{k}\left[\mathrm{P}_{n}\right]=\Delta_{0}\left[\mathrm{P}_{n}^{(k)}\right]
SO
Delta^(˙)_(k)[P_(n)] <= (1-(1)/(n))(1-(2)/(n))cdots(1-(k-1)/(n))*Delta_(k)[f]\dot{\Delta}_{k}\left[\mathrm{P}_{n}\right] \leq\left(1-\frac{1}{n}\right)\left(1-\frac{2}{n}\right) \cdots\left(1-\frac{k-1}{n}\right) \cdot \Delta_{k}[f]
(^(1){ }^{1}For more details, see our Thesis On Some Properties of Functions of One or Two Real Variables. Paris 1933
.^(2){ }^{2}) See loc. cit. (1), p. 45.
.^(2){ }^{2}) See loc. cit. (1), p. 45.
We can still write
Delta_(k)[P_(n)] <= Delta_(k)[f],quad k=0,1,quadDelta_(k)[P_(n)] < Delta_(k)[f],quad k > 1,\Delta_{k}\left[\mathrm{P}_{n}\right] \leq \Delta_{k}[f], \quad k=0,1, \quad \Delta_{k}\left[\mathrm{P}_{n}\right]<\Delta_{k}[f], \quad k>1,
Therefore:
The kth bound of the polynomialP_(n)(x;f)P_{n}(x ; f)is at most equal to that of the function ifk=0,1k=0,1and is smaller ifk < 1k<12.
We can write again
The kth bound of the polynomialP_(n)(x;f)P_{n}(x ; f)is at most equal to that of the function ifk=0,1k=0,1and is smaller ifk < 1k<12.
We can write again
{:[(d^(k)P_(n))/(dx^(k))=k!(1-{:(1)/(n))(1-(2)/(n))cdots(1-(k-1)/(n))*{Delta_(k)^(n-k)+:}],[+(n-k)sum_(i=0)^(n-k-1)[Delta_(k)^(i)-Delta_(k)^(i+1)]((n-k-1)/(i))int_(x)^(1)t^(l)(1-t)^(n-k-i-1)dt]:}\begin{aligned}
\frac{d^{k} \mathrm{P}_{n}}{d x^{k}}=k!(1- & \left.\frac{1}{n}\right)\left(1-\frac{2}{n}\right) \cdots\left(1-\frac{k-1}{n}\right) \cdot\left\{\Delta_{k}^{n-k}+\right. \\
& +(n-k) \sum_{i=0}^{n-k-1}\left[\Delta_{k}^{i}-\Delta_{k}^{i+1}\right]\binom{n-k-1}{i} \int_{x}^{1} t^{l}(1-t)^{n-k-i-1} d t
\end{aligned}
and we deduce
V_(k)[P_(n)] <= V_(k)[f],quad k=0,1,quadV_(k)[P_(n)] < V_(k)[f],quad k > 1\mathrm{V}_{k}\left[\mathrm{P}_{n}\right] \leq \mathrm{V}_{k}[f], \quad k=0,1, \quad \mathrm{~V}_{k}\left[\mathrm{P}_{n}\right]<\mathrm{V}_{k}[f], \quad k>1
Therefore:
The kth total variation of the polynomialP_(n)(x;f)P_{n}(x ; f)is at most equal to that of the function ifk=0,1k=0,1and is smaller ifk > 1k>1.
The kth total variation of the polynomialP_(n)(x;f)P_{n}(x ; f)is at most equal to that of the function ifk=0,1k=0,1and is smaller ifk > 1k>1.
We can express the two preceding properties by saying that the MS Bernstein polynomial preserves bounds and variations.
3. Formula (2) further shows us that wheneverf(x)f(x)enjoys a specific convexity property (of order< n<n) the polynomialP_(n)(x;f)\mathrm{P}_{n}(x ; f)will have the same property. We assume here that convexity and polynomiality are special cases of non-concavity.
3. Formula (2) further shows us that wheneverf(x)f(x)enjoys a specific convexity property (of order< n<n) the polynomialP_(n)(x;f)\mathrm{P}_{n}(x ; f)will have the same property. We assume here that convexity and polynomiality are special cases of non-concavity.
We express this property by saying that the Bernstein polynomial preserves the class of the function.
A property demonstrated in our cited work (^(3){ }^{3}) allows us to establish that
There exist polynomials of a given class in(0,1)(0,1)this class contains a finite number of arbitrarily chosen convexity or concavity conditions.
We finally know that if the functionf(x)f(x)is continuous in(0,1)(0,1)the polynomialP_(n)(x;f)P_{n}(x ; f)tends uniformly towardsf(x)f(x)throughout the entire interval forn rarr oon \rightarrow \infty(^(4){ }^{4}). We therefore have the following property:
(^(3){ }^{3}) See loc. cit. (1) p. 20.
(4) S. Bernstein Communications of the Soc. Math. of Karkow ser. 2, vol. 13 (1912) (Quotation from the book by Messrs. Pólya and Szegö „Aufgaben und Lehrsätze” t. I. p. 230). See also S. Wigert Arkiv för Mat. Astr. och, Physik t. 20, (1927), p, 1.
(^(3){ }^{3}) See loc. cit. (1) p. 20.
(4) S. Bernstein Communications of the Soc. Math. of Karkow ser. 2, vol. 13 (1912) (Quotation from the book by Messrs. Pólya and Szegö „Aufgaben und Lehrsätze” t. I. p. 230). See also S. Wigert Arkiv för Mat. Astr. och, Physik t. 20, (1927), p, 1.
Any continuous function in(0,1)(0,1)is the limit of a sequence of polynomials preserving the bounds, variations, and class of the function, converging uniformly throughout the interval.
4. The order of the approximation by polynomialsP_(n)(x;f)\mathrm{P}_{n}(x ; f)is easily obtained. Let us designate byomega(delta)\omega(\delta)the oscillation modulus of the functionf(x)(5)f(x)(5)We have
(3)|f(x)-P_(n)(x;f)| <= sum_(i=0)^(n)|f(x)-f((i)/(n))|((n)/(i))x^(t)(1-x)^(n-t) <=\left|f(x)-\mathrm{P}_{n}(x ; f)\right| \leq \sum_{i=0}^{n}\left|f(x)-f\left(\frac{i}{n}\right)\right|\binom{n}{i} x^{t}(1-x)^{n-t} \leq
4. The order of the approximation by polynomialsP_(n)(x;f)\mathrm{P}_{n}(x ; f)is easily obtained. Let us designate byomega(delta)\omega(\delta)the oscillation modulus of the functionf(x)(5)f(x)(5)We have
(3)|f(x)-P_(n)(x;f)| <= sum_(i=0)^(n)|f(x)-f((i)/(n))|((n)/(i))x^(t)(1-x)^(n-t) <=\left|f(x)-\mathrm{P}_{n}(x ; f)\right| \leq \sum_{i=0}^{n}\left|f(x)-f\left(\frac{i}{n}\right)\right|\binom{n}{i} x^{t}(1-x)^{n-t} \leq
{:[ <= sum_(i=0)^(n)omega(|x-(i)/(n)|)((n)/(i))x^(i)(1-x)^(n-i) < ],[ < ((1)/(delta)sum_(i=0)^(n)|x-(i)/(n)|((n)/(i))x^(i)(1-x)^(n-i)+1)omega(delta)]:}\begin{aligned}
\leq \sum_{i=0}^{n} \omega & \left(\left|x-\frac{i}{n}\right|\right)\binom{n}{i} x^{i}(1-x)^{n-i}< \\
& <\left(\frac{1}{\delta} \sum_{i=0}^{n}\left|x-\frac{i}{n}\right|\binom{n}{i} x^{i}(1-x)^{n-i}+1\right) \omega(\delta)
\end{aligned}
But in the meantime((j)/(n),(j+1)/(n))\left(\frac{j}{n}, \frac{j+1}{n}\right)We have
{:[sum_(i=0)^(n)|x-(i)/(n)|((n)/(i))x^(i)(1-x)^(n-i)=2((n-1)/(j))x^(j+1)(1-x)^(n-1) <= ],[ <= 2((n-1)/(j))_(((j)/(n),(j+1)/(n)))x^(j+1)(1-x)^(n-1)=2((n-1)/(i))((1+1)^(j+1)(n-j)^(n-j))/((n+1)^(n+1))]:}\begin{aligned}
& \sum_{i=0}^{n}\left|x-\frac{i}{n}\right|\left(\frac{n}{i}\right) x^{i}(1-x)^{n-i}=2\binom{n-1}{j} x^{j+1}(1-x)^{n-1} \leq \\
& \leq 2\binom{n-1}{j}_{\left(\frac{j}{n}, \frac{j+1}{n}\right)} x^{j+1}(1-x)^{n-1}=2\binom{n-1}{i} \frac{(1+1)^{j+1}(n-j)^{n-j}}{(n+1)^{n+1}}
\end{aligned}
and we deduce
max._((0,1))sum_(i=0)^(n)|x-(i)/(n)|((n)/(i))xi(1-x)^(n-i)=M_(n)={[2((n-1)/((n)/(2)))(((n)/(2)+1)^((n)/(2)+1)((n)/(2))^((n)/(2)))/(n+1)^(n+1))","x" pair "],[(1)/(2^(n))((n-1)/((n-1)/(2)))","n" impair. "]:}\operatorname{max.}_{(0,1)} \sum_{i=0}^{n}\left|x-\frac{i}{n}\right|\binom{n}{i} x i(1-x)^{n-i}=\mathrm{M}_{n}=\left\{\begin{array}{r}2\binom{n-1}{\frac{n}{2}} \frac{\left(\frac{n}{2}+1\right)^{\frac{n}{2}+1}\left(\frac{n}{2}\right)^{\frac{n}{2}}}{n+1)^{n+1}}, x \text { pair } \\ \frac{1}{2^{n}}\binom{n-1}{\frac{n-1}{2}}, n \text { impair. }\end{array}\right.
It is immediately apparent that
max._((0,1))sum_(i=0)^(n)|x-(i)/(n)|((n)/(i))xi(1-x)^(n-i)=M_(n)={[2((n-1)/((n)/(2)))(((n)/(2)+1)^((n)/(2)+1)((n)/(2))^((n)/(2)))/(n+1)^(n+1))","x" pair "],[(1)/(2^(n))((n-1)/((n-1)/(2)))","n" impair. "]:}\operatorname{max.}_{(0,1)} \sum_{i=0}^{n}\left|x-\frac{i}{n}\right|\binom{n}{i} x i(1-x)^{n-i}=\mathrm{M}_{n}=\left\{\begin{array}{r}2\binom{n-1}{\frac{n}{2}} \frac{\left(\frac{n}{2}+1\right)^{\frac{n}{2}+1}\left(\frac{n}{2}\right)^{\frac{n}{2}}}{n+1)^{n+1}}, x \text { pair } \\ \frac{1}{2^{n}}\binom{n-1}{\frac{n-1}{2}}, n \text { impair. }\end{array}\right.
It is immediately apparent that
n^((1)/(2))M_(n)rarr(1)/(sqrt(2pi))n^{\frac{1}{2}} M_{n} \rightarrow \frac{1}{\sqrt{2 \pi}}
And
(2n-1)^((1)/(2))M_(2n+1) > (2n+1)^((1)/(2))M_(2n+1)(2 n-1)^{\frac{1}{2}} M_{2 n+1}>(2 n+1)^{\frac{1}{2}} M_{2 n+1}
"Lessons on the Approximation of Functions of a Real Variable" p. 7.
độoù
M_(1)=(1)/(2),M_(2n+1) <= (sqrt3)/(4sqrt(2n+1))quad n=1,2,dots\mathrm{M}_{1}=\frac{1}{2}, \mathrm{M}_{2 n+1} \leq \frac{\sqrt{3}}{4 \sqrt{2 n+1}} \quad n=1,2, \ldots
độoù
M_(1)=(1)/(2),M_(2n+1) <= (sqrt3)/(4sqrt(2n+1))quad n=1,2,dots\mathrm{M}_{1}=\frac{1}{2}, \mathrm{M}_{2 n+1} \leq \frac{\sqrt{3}}{4 \sqrt{2 n+1}} \quad n=1,2, \ldots
Ifnnis even (n >= 2n \geq 2) it is easily established that
M_(n) < M_(n+1)sqrt((n+2)/(n)) <= (sqrt3)/(4sqrt(n+1))sqrt((n+2)/(n)) <= (1)/(2sqrtn).\mathrm{M}_{n}<\mathrm{M}_{n+1} \sqrt{\frac{n+2}{n}} \leq \frac{\sqrt{3}}{4 \sqrt{n+1}} \sqrt{\frac{n+2}{n}} \leq \frac{1}{2 \sqrt{n}} .
So whatevernn
M_(n) <= (1)/(2sqrtn)\mathrm{M}_{n} \leq \frac{1}{2 \sqrt{n}}
Doingdelta=(1)/(sqrtn)\delta=\frac{1}{\sqrt{n}}in formula (3) we have
|f(x)-P_(n)(x;f)| < (3)/(2)omega((1)/(sqrtn))quad" dans "(0,1)(6)\left|f(x)-\mathrm{P}_{n}(x ; f)\right|<\frac{3}{2} \omega\left(\frac{1}{\sqrt{n}}\right) \quad \text { dans }(0,1)(6)
The approximation is generally indeed on the order ofomega((1)/(sqrtn))\omega\left(\frac{1}{\sqrt{n}}\right)Let the functionf(x)=|(1)/(2)-x|f(x)=\left|\frac{1}{2}-x\right|. In this case we haveomega(delta)=delta\omega(\delta)=\deltaFordelta <= (1)/(2)\delta \leq \frac{1}{2}And
P_(2n+1)((1)/(2);f)-f((1)/(2))=(1)/(2^(2n+1))((2n)/(n))quad n > 1\mathrm{P}_{2 n+1}\left(\frac{1}{2} ; f\right)-f\left(\frac{1}{2}\right)=\frac{1}{2^{2 n+1}}\binom{2 n}{n} \quad n>1
from where
max.|f(x)-P_(2n+1)(x;f)| >= (1)/(sqrt(2pi))*(1)/(sqrt(2n+1))=(1)/(sqrt(2pi))^(omega)((1)/(sqrt(2n+1)))^((7))\operatorname{max.}\left|f(x)-\mathrm{P}_{2 n+1}(x ; f)\right| \geq \frac{1}{\sqrt{2 \pi}} \cdot \frac{1}{\sqrt{2 n+1}}=\frac{1}{\sqrt{2 \pi}}{ }^{\omega}\left(\frac{1}{\sqrt{2 n+1}}\right){ }^{(7)}.
(^(6){ }^{6}The demonstration given in the aforementioned book by Messrs. Pólya and Szegö shows me that
max.|f(x)-P_(2n+1)(x;f)| >= (1)/(sqrt(2pi))*(1)/(sqrt(2n+1))=(1)/(sqrt(2pi))^(omega)((1)/(sqrt(2n+1)))^((7))\operatorname{max.}\left|f(x)-\mathrm{P}_{2 n+1}(x ; f)\right| \geq \frac{1}{\sqrt{2 \pi}} \cdot \frac{1}{\sqrt{2 n+1}}=\frac{1}{\sqrt{2 \pi}}{ }^{\omega}\left(\frac{1}{\sqrt{2 n+1}}\right){ }^{(7)}.
(^(6){ }^{6}The demonstration given in the aforementioned book by Messrs. Pólya and Szegö shows me that
|f(x)-P_(n)(x;f)| < omega((1)/((4)/(sqrtn)))+(Delta_(0)[f])/(2sqrtn)\left|f(x)-\mathrm{P}_{n}(x ; f)\right|<\omega\left(\frac{1}{\frac{4}{\sqrt{n}}}\right)+\frac{\Delta_{0}[f]}{2 \sqrt{n}}
If the function satisfies an ordinary Lipschitz condition, then
|t(x)-P_(n)(x;f)| < (3)/(2)(Delta_(1)[f])/(sqrtn).\left|t(x)-P_{n}(x ; f)\right|<\frac{3}{2} \frac{\Delta_{1}[f]}{\sqrt{n}} .
Mr. Wigert only provides an approximation.
(3)/(2)root(3)(Delta_(0)[f]*Delta_(1)[f]^(2))*(1)/(root(3)(n)).\frac{3}{2} \sqrt[3]{\Delta_{0}[f] \cdot \Delta_{1}[f]^{2}} \cdot \frac{1}{\sqrt[3]{n}} .
(7) We have assumed that the function is defined in the interval(0,1)(0,1)solely to simplify the presentation. We could have considered functions-
- (5) For the properties ofomega(delta)\omega(\delta)see for exampleC_(H)\mathrm{C}_{\mathrm{H}}. of the Chick Valley