notes on weierstrass approximation theorem
by math154, Jul 4, 2014, 10:22 PM
http://en.wikipedia.org/wiki/Stone%E2%80%93Weierstrass_theorem#Weierstrass_approximation_theorem
First instinct is to use Lagrange interpolation. Runge's phenomenon says equally spaced nodes are bad for this. More generally even smarter things like Chebyshev nodes are bad. See comments here for some intuition: high degree means greater oscillations in between nodes, as we've only controlled nodes perfectly and it's thus hard to bound stuff between nodes. (On the other hand, I don't see good intuition a priori why something like Chebyshev nodes shouldn't work, it's just that it's more plausible that it won't work than a "smoother/more-averaged-out" approximation. In fact the Wikipedia says all absolutely continuous guys are good with Chebyshev so blah.)
Let's do a continuous/smoother version of Lagrange interpolation instead. Analogous to Lagrange interpolation polynomials (
with 
and 
for 
), we want interpolation polynomials 
such that 
when 
for some bijection 
(and quickly decays as 
leaves 
); for simplicity we just use 
, but perhaps in other contexts we'd need to do something more complicated? We'll then take 
; this is apparently related to blurring; actually, this has some issues with endpoints, but if we first reduce to 
(or write out stuff more carefully) then we're good to go. Anyway here 
works, where 
is a fixed positive integer and 
is just a scale factor to make 
, with an easy bound of 
. The rest is not hard, looking at 
using a uniform continuity bound to bound 
when 
is small. (We need uniform continuity since the same bound will apply independently of .)
Some other links:
1. The probabilistic proof with Bernstein polynomials is interesting and I don't have great intuition for why this works while the Lagrange interpolation doesn't, except that the![$f(i/n) [\binom{n}{i} x^i(1-x)^{n-i}]$](//latex.artofproblemsolving.com/2/e/6/2e61ecea3266b65f0be72b15927ef80ce7807009.png)
term has "smooth/well-behaved contribution" that peaks when 
. (Compared with Lagrange where the contribution is 
at 
, 
at the 
, and perhaps unpredictable elsewhere. That probably makes stuff around ![$[x_{i-1},x_{i+1}]$](//latex.artofproblemsolving.com/5/f/8/5f8ae149879869e82b087ee4f181d07b8f0d3285.png)
particularly hard to control, given that our main bound will probably come from uniform continuity of 
around .)
2. http://en.wikipedia.org/wiki/Approximation_theory
3. http://mathoverflow.net/questions/91116/approximation-by-polynomials (and Hermite interpolation in general).
===
Another approach: is that it suffices to approximate the absolute value function on![$[-1,1]$](//latex.artofproblemsolving.com/3/9/f/39f506ebeeeb72f62147990614a67f4e30b7c751.png)
:
http://www.dms.uaf.edu/~maxwell/AY2011/math641/Weierstrass.pdf
http://83.143.248.39/faculty/aganchev/Real%20Analysis/old%20stuff/Walsh;%20on%20stone-weierstrass.pdf
By the polynomial interpolation Wikipedia link above though, we should be able to use Chebyshev nodes to do this. Fix
. Let 
for 
, so 
for 
and 
for 
. Then ![$g(x) := \prod_{k=0}^{n} (x-t_k) = \frac{\sqrt{x^2-1}}{2^n}[(x+\sqrt{x^2-1})^n - (x-\sqrt{x^2-1})^n]$](//latex.artofproblemsolving.com/7/6/d/76dfb22f0c2079f221f9866d893ea92a267872a1.png)
with 
, so 
on .
But (by differentiating or using roots of unity) we have
if 
, and 
otherwise. So letting 
and noting that 
, we have
![\[ \frac{x - P_n(x)}{2} = g(x)\left(\frac{t_n}{x-t_n}\frac{2^{n-2}}{(-1)^n n} + \sum_{k > n/2}^{n-1} \frac{t_k}{x-t_k}\frac{2^{n-1}}{(-1)^k n}\right). \]](//latex.artofproblemsolving.com/b/1/6/b1641e06e18eaf0b8be0eb042c3079c19b210837.png)
For
we have 
, so for fixed 
, we have 
a negative number with increasing magnitude as 
increases in ![$(n/2,n]$](//latex.artofproblemsolving.com/6/7/5/6757bc5f8dce899871cf5f66c725faed73963434.png)
. So we have an alternating series, which bounds stuff by
![\[ \frac{|x-P_n(x)|}{2} \le |g(x)| \frac{2^{n-2}}{n} (1 + 2\cdot 1) \le \frac{3}{2n} \]](//latex.artofproblemsolving.com/4/a/2/4a25d6a76c6b2ee9491339ce899afa06627c7fd7.png)
for. Of course by symmetry we get the same bound for 
, so 
for all ![$x\in[-1,1]$](//latex.artofproblemsolving.com/5/2/e/52ebe6de79419fad5a4cc599c58421f8140a8e18.png)
, and we're done.
(Actually note that these are Chebyshev nodes of second kind, but not a huge difference...)
More reading:
4. Chebyshev equioscillation theorem, and theorem/reference about how well Chebyshev can do in general: http://www.siam.org/books/ot99/OT99SampleChapter.pdf
5. http://rjlipton.wordpress.com/2009/10/07/the-surprising-power-of-rational-functions/
First instinct is to use Lagrange interpolation. Runge's phenomenon says equally spaced nodes are bad for this. More generally even smarter things like Chebyshev nodes are bad. See comments here for some intuition: high degree means greater oscillations in between nodes, as we've only controlled nodes perfectly and it's thus hard to bound stuff between nodes. (On the other hand, I don't see good intuition a priori why something like Chebyshev nodes shouldn't work, it's just that it's more plausible that it won't work than a "smoother/more-averaged-out" approximation. In fact the Wikipedia says all absolutely continuous guys are good with Chebyshev so blah.)
Let's do a continuous/smoother version of Lagrange interpolation instead. Analogous to Lagrange interpolation polynomials (
with 
and 
for 
), we want interpolation polynomials 
such that 
when 
for some bijection 
(and quickly decays as 
leaves 
); for simplicity we just use 
, but perhaps in other contexts we'd need to do something more complicated? We'll then take 
; this is apparently related to blurring; actually, this has some issues with endpoints, but if we first reduce to 
(or write out stuff more carefully) then we're good to go. Anyway here 
works, where 
is a fixed positive integer and 
is just a scale factor to make 
, with an easy bound of 
. The rest is not hard, looking at 
using a uniform continuity bound to bound 
when 
is small. (We need uniform continuity since the same bound will apply independently of .)Some other links:
1. The probabilistic proof with Bernstein polynomials is interesting and I don't have great intuition for why this works while the Lagrange interpolation doesn't, except that the
![$f(i/n) [\binom{n}{i} x^i(1-x)^{n-i}]$](http://latex.artofproblemsolving.com/2/e/6/2e61ecea3266b65f0be72b15927ef80ce7807009.png)
term has "smooth/well-behaved contribution" that peaks when 
. (Compared with Lagrange where the contribution is 
at 
, 
at the 
, and perhaps unpredictable elsewhere. That probably makes stuff around ![$[x_{i-1},x_{i+1}]$](http://latex.artofproblemsolving.com/5/f/8/5f8ae149879869e82b087ee4f181d07b8f0d3285.png)
particularly hard to control, given that our main bound will probably come from uniform continuity of 
around .)2. http://en.wikipedia.org/wiki/Approximation_theory
3. http://mathoverflow.net/questions/91116/approximation-by-polynomials (and Hermite interpolation in general).
===
Another approach: is that it suffices to approximate the absolute value function on
![$[-1,1]$](http://latex.artofproblemsolving.com/3/9/f/39f506ebeeeb72f62147990614a67f4e30b7c751.png)
:http://www.dms.uaf.edu/~maxwell/AY2011/math641/Weierstrass.pdf
http://83.143.248.39/faculty/aganchev/Real%20Analysis/old%20stuff/Walsh;%20on%20stone-weierstrass.pdf
By the polynomial interpolation Wikipedia link above though, we should be able to use Chebyshev nodes to do this. Fix
. Let 
for 
, so 
for 
and 
for 
. Then ![$g(x) := \prod_{k=0}^{n} (x-t_k) = \frac{\sqrt{x^2-1}}{2^n}[(x+\sqrt{x^2-1})^n - (x-\sqrt{x^2-1})^n]$](http://latex.artofproblemsolving.com/7/6/d/76dfb22f0c2079f221f9866d893ea92a267872a1.png)
with 
, so 
on .But (by differentiating or using roots of unity) we have
if 
, and 
otherwise. So letting 
and noting that 
, we have![\[ \frac{x - P_n(x)}{2} = g(x)\left(\frac{t_n}{x-t_n}\frac{2^{n-2}}{(-1)^n n} + \sum_{k > n/2}^{n-1} \frac{t_k}{x-t_k}\frac{2^{n-1}}{(-1)^k n}\right). \]](http://latex.artofproblemsolving.com/b/1/6/b1641e06e18eaf0b8be0eb042c3079c19b210837.png)
For
we have 
, so for fixed 
, we have 
a negative number with increasing magnitude as 
increases in ![$(n/2,n]$](http://latex.artofproblemsolving.com/6/7/5/6757bc5f8dce899871cf5f66c725faed73963434.png)
. So we have an alternating series, which bounds stuff by![\[ \frac{|x-P_n(x)|}{2} \le |g(x)| \frac{2^{n-2}}{n} (1 + 2\cdot 1) \le \frac{3}{2n} \]](http://latex.artofproblemsolving.com/4/a/2/4a25d6a76c6b2ee9491339ce899afa06627c7fd7.png)
for
. Of course by symmetry we get the same bound for 
, so 
for all ![$x\in[-1,1]$](http://latex.artofproblemsolving.com/5/2/e/52ebe6de79419fad5a4cc599c58421f8140a8e18.png)
, and we're done.(Actually note that these are Chebyshev nodes of second kind, but not a huge difference...)
More reading:
4. Chebyshev equioscillation theorem, and theorem/reference about how well Chebyshev can do in general: http://www.siam.org/books/ot99/OT99SampleChapter.pdf
5. http://rjlipton.wordpress.com/2009/10/07/the-surprising-power-of-rational-functions/
This post has been edited 5 times. Last edited by math154, Jul 5, 2014, 6:32 AM
July 2014
June 2014