 |
Az A. 627. feladat (2014. november) |
A. 627. Legyen \(\displaystyle n\ge1\) rögzített egész. Számítsuk ki az
\(\displaystyle \inf_{p,f}\ \max_{0\le x\le 1} \big|f(x)-p(x)\big| \)
távolságot, ahol \(\displaystyle p\) az \(\displaystyle n\)-nél alacsonyabb fokú valós együtthatós polinomokon, \(\displaystyle f\) pedig a \(\displaystyle [0, 1]\) zárt intervallumon értelmezett,
\(\displaystyle f(x) = \sum_{k=n}^\infty c_k x^k \)
alakú függvényeken fut végig, ahol \(\displaystyle c_k\ge0\) és \(\displaystyle \sum_{k=n}^\infty c_k=1\).
Schweitzer Miklós Emlékverseny, 2014
(5 pont)
A beküldési határidő 2014. december 10-én LEJÁRT.
Megoldás. Jelöljük \(\displaystyle t_n\)-nel az \(\displaystyle n\)-edik Csebisev-polinomnak a \(\displaystyle [0,1]\) intervallumra áttranszformált, főegyütthatóra normált változatát, azaz legyen
\(\displaystyle t_n(x) = \frac1{2^{2n-1}} T_n(2x-1). \)
Ha \(\displaystyle f-p=t_n\), azaz \(\displaystyle f(x)=x^n\) és \(\displaystyle p(x) = x^n-t_n(x)\), akkor
\(\displaystyle \max_{0\le x\le 1} \big|f(x)-p(x)\big| = \max_{0\le x\le 1} \big|t_n(x)\big| = \frac1{2^{2n-1}} \max_{-1\le x\le 1} \big|T_n(x)\big| = \frac1{2^{2n-1}}. \)
Célunk azt igazolni, hogy ennél kisebb érték nem lehetséges, sőt, \(\displaystyle n\ge2\) esetén a \(\displaystyle \frac1{2^{2n-1}}\) érték is csak ezzel az \(\displaystyle f,p\) választással érhető el. (Abban a speciális esetben, amikor \(\displaystyle f(x)=x^n\), ez a tény jól ismert.)
Tetszőleges \(\displaystyle f(x)\) függvény és különböző \(\displaystyle a_0,a_1,\ldots,a_n\) számok esetén legyen \(\displaystyle f[a_0,a_1,\ldots,a_n]\) az \(\displaystyle f\) függvény osztott differenciája az \(\displaystyle a_0,\ldots,a_n\) alappontokon. Az \(\displaystyle x^N\) hatvány osztott differenciáját \(\displaystyle X^N[a_0,a_1,\ldots,a_n]\) fogja jelölni. Jól ismert, hogy
| \(\displaystyle f[a_0,a_1,\ldots,a_n] = \sum_{j=0}^n \frac{f(a_j)}{\prod\limits_{k\ne j}(a_j-a_k)}, \) | (1) |
továbbá
| \(\displaystyle X^N[a_0,a_1,\ldots,a_n] = \sum_{d_0+d_1+\dots+d_n=N-n} a_0^{d_0}a_1^{d_1}\cdots a_n^{d_n} \) | (2) |
ahol a \(\displaystyle d_0,\ldots,d_n\) kitevők a nemnegatív egészeken futnak. (Ha \(\displaystyle N<n\), akkor a szumma üres, értéke \(\displaystyle 0\).)
A megoldáshoz válasszuk azokat az \(\displaystyle 1=a_0>a_1>\ldots>a_n=0\) alappontokat, ahol \(\displaystyle t_n\) extremális, azaz legyen \(\displaystyle a_k=\frac12(1+\cos\frac{k\pi}n)\); ekkor tehát \(\displaystyle t_n(a_k)=\frac{(-1)^k}{2^{2n-1}}\). A \(\displaystyle (2)\) jobboldalán minden tag nemnegatív; ha \(\displaystyle N\ge n\), akkor tagok között szerepel \(\displaystyle a_0^{N-n}=1\). Így
\(\displaystyle X^N[a_0,\ldots,a_n] = 0 \quad \text{ha } N<n; \)
\(\displaystyle X^N[a_0,\ldots,a_n] = 1 \quad \text{ha } N=n; \)
| \(\displaystyle X^N[a_0,\ldots,a_n] \ge 1 \quad \text{ha } N>n. \) | (3) |
(Az utolsó esetben csak akkor áll egyenlőség, ha \(\displaystyle n=1\), ilyenkor ugyanis a többi tag mind \(\displaystyle 0\).)
A (3) alapján, az osztott differenciát tagonként véve láthatjuk, hogy például
\(\displaystyle t_n[a_0,\ldots,a_n] = X^n[a_0,\ldots,a_n] = 1. \)
Legyen most \(\displaystyle f(x) = \sum\limits_{k=n}^\infty c_k x^k\) úgy, mint a feladatban, és legyen \(\displaystyle p(x)=-\sum\limits_{k=0}^{n-1}c_kx^k\) tetszőleges, \(\displaystyle n\)-nél kisebb fokú polinom. Legyen \(\displaystyle M=\max\limits_{[0,1]}|f-p|\), és vizsgáljuk meg az \(\displaystyle (f-p)[a_0,\ldots,a_n]\) osztott differenciát.
Az (1) szerint
| \(\displaystyle (f-p)[a_0,\ldots,a_n] = \sum_{j=0}^n \frac{f(a_j)-p(a_j)}{\prod\limits_{k\ne j}(a_j-a_k)} \le \sum_{j=0}^n \frac{M}{\Big|\prod\limits_{k\ne j}(a_j-a_k)\Big|} = \) | (4) |
\(\displaystyle = 2^{2n-1}M \sum_{j=0}^n \frac{(-1)^j/2^{2n-1}}{\prod\limits_{k\ne j}(a_j-a_k)} = 2^{2n-1}M \sum_{j=0}^n \frac{t_n(a_j)}{\prod\limits_{k\ne j}(a_j-a_k)} = 2^{2n-1}M \cdot t_n[a_0,\ldots,a_n] = 2^{2n-1}M. \)
Másrészt, az osztott differenciát tagonként véve, (3) alapján
| \(\displaystyle (f-p)[a_0,\ldots,a_n] = \sum_{k=0}^\infty c_k \cdot X^k[a_0,\ldots,a_n] \ge \sum_{k=0}^{n-1} c_k \cdot 0 + \sum_{k=n}^\infty c_k \cdot 1 = \sum_{k=n}^\infty c_k = 1. \) | (5) |
Tehát, \(\displaystyle 1 \le (f-p)[a_0,\ldots,a_n] \le 2^{2n-1}M\), amiből \(\displaystyle M\ge\dfrac1{2^{2n-1}}\).
Ha \(\displaystyle n\ge2\) akkor \(\displaystyle M=\dfrac1{2^{2n-1}}\) csak úgy lehetéges, ha (3) és (5) miatt \(\displaystyle c_{n+1}=c_{n+2}=\ldots=0\), másrészt (4) miatt \(\displaystyle f(a_j)-p(a_j)=(-1)^jM\), vagyis ha \(\displaystyle f-p\) éppen az áttranszformált Csebisev-polinom.
Ha \(\displaystyle n=1\), akkor \(\displaystyle p=\frac12\), és \(\displaystyle f\) bármi lehet.
Tehát,
\(\displaystyle \inf_{p,f}\ \max_{0\le x\le 1} \big|f(x)-p(x)\big| = \frac1{2^{2n-1}}.\)
Megjegyzés. A (2) azonosság egyszerűen igazolható például teljes indukcióval.
Statisztika:
3 dolgozat érkezett. 5 pontot kapott: Williams Kada. 3 pontot kapott: 1 versenyző. 0 pontot kapott: 1 versenyző.
A KöMaL 2014. novemberi matematika feladatai