Thumbnail
Access Restriction
Subscribed

Author Blum, E. K. ♦ Curtis, P. C.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1961
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract Let ƒ $(\textit{x})$ be a real-valued function defined and continuous on [- 1, +1] and let $\textit{T}(\textit{x})$ = $\textit{a}0/2$ + $∑∞\textit{k}=1$ $\textit{akTk}$ $(\textit{x})$ be the Fourier-Tschebycheff expansion for ƒ $(\textit{x}),$ that is, T k $(\textit{x})$ = cos $\textit{kl&thgr;},$ $\textit{ak}$ = 2/π ∫π0 ƒ (cos $\textit{&thgr;})$ cos k&thgr; d&thgr; where $\textit{x}$ = cos $\textit{&thgr;}.$ If $\textit{Pn}$ is the class of real polynomials in $\textit{x}$ of degree less than or equal to $\textit{n},$ we let $\textit{Mn}$ = $inf\textit{pePn}$ $sup-1≤\textit{x}≤1$ | ƒ $(\textit{x})$ - $\textit{p}$ $(\textit{x})$ |. $\textit{Mn}$ is called the best Tschebycheff approximation to ƒ $(\textit{x})$ by a polynomial of degree less than or equal to $\textit{n}.$ A rule of thumb in computing is that | $\textit{Mn}/\textit{a}\textit{n}+1$ | → 1 as $\textit{n}$ → ∞. In other words, the best Tschebycheff approximation to ƒ $(\textit{x})$ of degree $\textit{n}$ is asymptotically equal to the $(\textit{n}$ + 1)th coefficient in the Tschebycheff expansion. It is the purpose of this note to give upper and lower bounds for $\textit{Mn}$ in terms of the coefficients ${\textit{ak}},$ which will enable us to make precise statements about the validity of this asymptotic result. It has already been observed by Bernstein [1, p. 115] that under appropriate hypotheses on $ƒ(\textit{x})$ there exists a subsequence ${\textit{kj}}$ for which | $\textit{Mkj}/\textit{a}\textit{kj}+1$ | → 1. We show here that if ${\textit{akj}}$ is the subsequence of ${\textit{ak}}$ consisting of the nonzero coefficients, then a sufficient condition for $lim\textit{j}→∞$ | $\textit{M}\textit{kj}-1/\textit{akj}$ | = 1 (1) is for lim $\textit{j}→∞\textit{a}\textit{kj}+1$ | = 0. If this latter condition holds ƒ $(\textit{z})$ = 1/2 $\textit{a}0$ + $∑∞\textit{n}=1$ $\textit{anTn}$ $(\textit{z})$ is an entire function. An easy example shows that (1) is not valid, however, for all entire functions. We note first some easily derived bounds for $\textit{Mn}.$ If the series $\textit{T}$ $(\textit{x})$ converges to ƒ $(\textit{x}),$ then $\textit{Mn}$ ≤ $sup-1≤\textit{x}≤1$ | ƒ $(\textit{x})$ - 1/2 $\textit{a}0$ - $∑\textit{n}\textit{k}=1$ $\textit{akTk}(\textit{x})$ | ≤ $∑∞\textit{k}=\textit{n}+1$ | $\textit{ak}$ |.Therefore, if $∑∞\textit{k}=1$ | $\textit{ak}$ | < ∞, $∑∞\textit{k}=\textit{n}+1$ | $\textit{ak}$ | is an upper bound for $\textit{Mn}.$ Again, if the series $\textit{T}(\textit{x})$ converges, a lower bound for $\textit{Mn}$ is given by La Vallee Poussin [2, p. 107], i.e., $\textit{Mn}$ ≧ | $\textit{a}\textit{n}+1$ + $\textit{a}3(\textit{n}+1)$ + $\textit{a}5(\textit{n}+1)$ + ··· |. (2) Another lower bound for $\textit{Mn}$ in terms of the coefficients $\textit{an}$ may also be obtained. From the fact that the $\textit{n}th$ partial sum of the Fourier cosine series gives the best least squares approximation to ƒ (cos $\textit{&thgr;})$ we have 1/π ∫π0 ƒ(cos $\textit{&thgr;})$ - $\textit{a}0/2$ - $∑\textit{n}1$ $\textit{ak}$ cos $\textit{k&thgr;}]2$ $\textit{d&thgr;}$ ≤ $\textit{Mn}2.$ But by Parseval's theorem 1/π ∫π0 ƒ(cos $\textit{&thgr;})$ - $\textit{a}0/2$ - $∑\textit{n}1$ $\textit{ak}$ cos $\textit{k&thgr;}]2$ $\textit{d&thgr;}$ = 1/2 $∑∞\textit{n}=1$ $\textit{ak}2.$ Therefore, $\textit{Mn}$ ≧ { 1/2 $∑∞\textit{n}+1\textit{ak}2}1/2$ and, in particular, $\textit{Mn}$ ≧ 1/√2 | $\textit{am}$ | for $\textit{m}$ > $\textit{n}.$ (3) We now can prove the following result.THEOREM. $\textit{Let}$ ${\textit{akj}}$ be the subsequence of the ${\textit{ak}}$ consisting of all the nonzero coefficeints. If for all j ≧ $\textit{j}0$ | $\textit{a}\textit{kj}+1/\textit{akj}$ | ≤ &rgr; < 1, then for j ≧ $\textit{j}0,$ max (1/√2, 1 - 2&rgr;/1 - &rgr;) ≤ $\textit{M}\textit{kj}-1/|$ $\textit{akj}$ |) ≤ 1/1 - &rgr; (4) $\textit{and}$ 1/√2 ≤ $\textit{Mkj}/|$ $\textit{a}\textit{kj}+1$ | ≤ 1/1 - &rgr;. (5)PROOF. If for all $\textit{j}$ ≧ $\textit{j}0,$ $|\textit{a}\textit{kj}+1/\textit{akj}|$ ≤ &rgr; < 1, then $∑∞\textit{k}=1|\textit{ak}$ | < ∞. Therefore, for $\textit{j}$ ≧ $\textit{j}0,$ $\textit{M}\textit{kj}-1$ ≤ $∑∞\textit{n}=\textit{kj}$ | $\textit{an}$ | = ∑∞ $\textit{n}=\textit{j}|\textit{akn}$ | ≤ | $\textit{akj}$ | (1 + &rgr; + &rgr;2 + ··· = | $\textit{akj}$ | 1/1&rgr; Similarly $\textit{Mkj}$ ≤ | $\textit{a}\textit{kj}+1$ | (1/1 - &rgr;). An application of (3) proves that $\textit{Mkj}/|$ $\textit{a}\textit{kj}+1$ | ≧ 1/ √2, establishing (5). On the other hand by (2), $\textit{M}\textit{kj}-1$ ≧ | $\textit{akj}$ + $\textit{a}3\textit{kj}$ + ··· | ≧ | $\textit{akj}$ | - | $\textit{a}3\textit{kj}$ | ··· ≧ | $\textit{akj}$ | {1 - &rgr; - &rgr;2 - ···} = | $\textit{akj}$ | 1 - 2&rgr;/1 - &rgr;. Therefore, by (3), $\textit{M}\textit{kj}-1/|$ $\textit{akj}$ | ≧ max (1/√2, 1 - 2&rgr;/1 - &rgr;) and the theorem is proved.COROLLARY. $\textit{If}$ $lim\textit{j}→∞$ | $\textit{a}\textit{kj}+1/\textit{a}\textit{kj}$ | = 0, $\textit{then}$ $lim\textit{j}→∞$ | $\textit{M}\textit{kj}-1/\textit{akj}$ | = 1. REMARK. Suppose $\textit{an}$ ≠ 0 for all $\textit{n}.$ Then if $lim\textit{j}→∞$ | $\textit{a}\textit{n}+1/\textit{an}$ | = 0, $\textit{f}$ $(\textit{z})$ ≡ $1/2\textit{a}0$ + ∑ $∞\textit{n}=1$ $\textit{anTn}$ $(\textit{z})$ is an entire function. In light of the above corollary, one might conjecture that for any entire function such that $\textit{an}$ ≠ 0, $lim\textit{n}→∞$ | $\textit{M}\textit{n}-1/\textit{an}$ | = 1. This, however, is false as the following simple argument shows. Certainly for such entire functions $\textit{Mn}$ ≧ $\textit{M}\textit{n}+1$ > 0. Therefore $lim\textit{n}→∞$ $\textit{M}\textit{n}+1/Mn$ ≤ 1. But, $\textit{M}\textit{n}+1/\textit{Mn}$ = $\textit{M}\textit{n}+1/\textit{a}\textit{n}+2$ . $\textit{a}\textit{n}+2/\textit{a}\textit{n}+1$ . $\textit{a}\textit{n}+1/\textit{Mn}.$ Therefore, if $lim\textit{n}→∞$ | $\textit{M}\textit{n}-1/\textit{an}$ | = 1, $lim\textit{n}→∞$ | $\textit{M}\textit{n}+1/\textit{Mn}$ | = 1 $lim\textit{n}$ → | $\textit{a}\textit{n}+2/\textit{a}\textit{n}+1$ |. But one can easily construct examples of entire functions such that $lim\textit{n}→∞$ | $\textit{a}\textit{n}+2/\textit{a}\textit{n}+1$ | ≧ $\textit{k}$ > 1; e.g., let $\textit{a}2\textit{n}$ = $(2\textit{n})-2\textit{n}+1,$ $\textit{a}2\textit{n}+1$ = $\textit{k}$ $(2\textit{n})-2\textit{n}+1.$
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1961-10-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 8
Issue Number 4
Page Count 3
Starting Page 645
Ending Page 647


Open content in new tab

   Open content in new tab
Source: ACM Digital Library